github-starred/semver
2
0
Fork 0
mirror of https://github.com/semver/semver.git synced 2026-07-11 06:53:03 -05:00
Code Issues 1.0k Packages Projects Releases 4 Wiki Activity

[GH-ISSUE #826] Reorder subregex patterns to match valid semver strings?d #2275

New Issue
Open
opened 2026-04-20 10:16:59 -05:00 by GiteaMirror · 6 comments
GiteaMirror commented 2026-04-20 10:16:59 -05:00
Owner
Copy Link

Originally created by @sebastien-rosset on GitHub (Apr 22, 2022).
Original GitHub issue: https://github.com/semver/semver/issues/826

This is a proposal to slightly change the order of the prerelease subregex expressions in the documented regex. This will make it possible to find semver strings inside a body of text.

These strings are valid according to semver v2:

1.20.2----
1.20.2-alpha-0.0.1.123.308
1.20.2-alpha-0.0.1.123-308
1.20.2-alpha-0.0.1.123----308

With the start and end of string anchors, all of these strings match the documented regex: ^(?P<major>0|[1-9]\d*)\.(?P<minor>0|[1-9]\d*)\.(?P<patch>0|[1-9]\d*)(?:-(?P<prerelease>(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*)(?:\.(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*))*))?(?:\+(?P<buildmetadata>[0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$.

Suppose these semver strings are inside a larger body of text. For example, the text is:

service abc version 1.20.2-alpha-0.0.1.123-308 is starting.
service abc version 1.20.2-alpha-0.0.1.123-308 stopped.

Using a regex, it's possible to iteratively find all occurrences of the semver strings in the body of text. One way to do this is to remove the anchors from the documented regex. However, in that case, the regex find will yield an incomplete value:

1.20.2-alpha-0.0.1.123-308         => regex match is '1.20.2-alpha-0.0.1.123'
1.20.2-alpha-0.0.1.123----308    => regex match is '1.20.2-alpha-0.0.1.123'

The problem occurs because when matching 0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*, there are three sub-regex patterns and the engine matches from left to right, without trying to find the longest match. Hence the match will stop at 123.

Reordering the subregex patterns works: (?<major>0|[1-9]\d*)\.(?<minor>0|[1-9]\d*)\.(?<patch>0|[1-9]\d*)(?:-(?<prerelease>(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0)(?:\.(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0))*))?(?:\+(?<buildmetadata>[0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?

As a side benefit, the regex seems to be a bit more efficient because the engine does not have to backtrack.

Originally created by @sebastien-rosset on GitHub (Apr 22, 2022). Original GitHub issue: https://github.com/semver/semver/issues/826 This is a proposal to slightly change the order of the prerelease subregex expressions in the documented regex. This will make it possible to find semver strings inside a body of text. These strings are valid according to semver v2: ``` 1.20.2---- 1.20.2-alpha-0.0.1.123.308 1.20.2-alpha-0.0.1.123-308 1.20.2-alpha-0.0.1.123----308 ``` With the start and end of string anchors, all of these strings match the documented regex: `^(?P<major>0|[1-9]\d*)\.(?P<minor>0|[1-9]\d*)\.(?P<patch>0|[1-9]\d*)(?:-(?P<prerelease>(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*)(?:\.(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*))*))?(?:\+(?P<buildmetadata>[0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$`. Suppose these semver strings are inside a larger body of text. For example, the text is: ``` service abc version 1.20.2-alpha-0.0.1.123-308 is starting. service abc version 1.20.2-alpha-0.0.1.123-308 stopped. ``` Using a regex, it's possible to iteratively find all occurrences of the semver strings in the body of text. One way to do this is to remove the anchors from the documented regex. However, in that case, the regex `find` will yield an incomplete value: ``` 1.20.2-alpha-0.0.1.123-308 => regex match is '1.20.2-alpha-0.0.1.123' 1.20.2-alpha-0.0.1.123----308 => regex match is '1.20.2-alpha-0.0.1.123' ``` The problem occurs because when matching `0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*`, there are three sub-regex patterns and the engine matches from left to right, without trying to find the longest match. Hence the match will stop at `123`. Reordering the subregex patterns works: `(?<major>0|[1-9]\d*)\.(?<minor>0|[1-9]\d*)\.(?<patch>0|[1-9]\d*)(?:-(?<prerelease>(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0)(?:\.(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0))*))?(?:\+(?<buildmetadata>[0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?` As a side benefit, the regex seems to be a bit more efficient because the engine does not have to backtrack.
GiteaMirror commented 2026-04-20 10:17:01 -05:00
Author
Owner
Copy Link

@sebastien-rosset commented on GitHub (Apr 22, 2022):

Performance wasn't my goal, but the updated regex seems to have slightly better performance:

package main

import (
        "regexp"
        "testing"
)

var rOriginal *regexp.Regexp = regexp.MustCompile(`^(?P<major>0|[1-9]\d*)\.(?P<minor>0|[1-9]\d*)\.(?P<patch>0|[1-9]\d*)(?:-(?P<prerelease>(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*)(?:\.(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*))*))?(?:\+(?P<buildmetadata>[0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$`)
var rUpdated *regexp.Regexp = regexp.MustCompile(`^(?P<major>0|[1-9]\d*)\.(?P<minor>0|[1-9]\d*)\.(?P<patch>0|[1-9]\d*)(?:-(?P<prerelease>(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|0|[1-9]\d*)(?:\.(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|0|[1-9]\d*))*))?(?:\+(?P<buildmetadata>[0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$`)


func BenchmarkSemverRegexOriginal(b *testing.B) {
        for n := 0; n < b.N; n++ {
                rOriginal.MatchString("1.20.2-alpha-0.0.1.123-308")
        }
}

func BenchmarkSemverRegexUpdated(b *testing.B) {
        for n := 0; n < b.N; n++ {
                rUpdated.MatchString("1.20.2-alpha-0.0.1.123-308")
        }
}

go test -bench=.
goos: linux
goarch: amd64
cpu: Intel(R) Xeon(R) CPU E5-2698 v3 @ 2.30GHz
BenchmarkSemverRegexOriginal-8   	  725662	      1651 ns/op
BenchmarkSemverRegexUpdated-8    	  874554	      1280 ns/op
PASS
ok  	_/tmp/test	2.357s
<!-- gh-comment-id:1106045801 --> @sebastien-rosset commented on GitHub (Apr 22, 2022): Performance wasn't my goal, but the updated regex seems to have slightly better performance: ```go package main import ( "regexp" "testing" ) var rOriginal *regexp.Regexp = regexp.MustCompile(`^(?P<major>0|[1-9]\d*)\.(?P<minor>0|[1-9]\d*)\.(?P<patch>0|[1-9]\d*)(?:-(?P<prerelease>(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*)(?:\.(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*))*))?(?:\+(?P<buildmetadata>[0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$`) var rUpdated *regexp.Regexp = regexp.MustCompile(`^(?P<major>0|[1-9]\d*)\.(?P<minor>0|[1-9]\d*)\.(?P<patch>0|[1-9]\d*)(?:-(?P<prerelease>(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|0|[1-9]\d*)(?:\.(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|0|[1-9]\d*))*))?(?:\+(?P<buildmetadata>[0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$`) func BenchmarkSemverRegexOriginal(b *testing.B) { for n := 0; n < b.N; n++ { rOriginal.MatchString("1.20.2-alpha-0.0.1.123-308") } } func BenchmarkSemverRegexUpdated(b *testing.B) { for n := 0; n < b.N; n++ { rUpdated.MatchString("1.20.2-alpha-0.0.1.123-308") } } ``` ```console go test -bench=. goos: linux goarch: amd64 cpu: Intel(R) Xeon(R) CPU E5-2698 v3 @ 2.30GHz BenchmarkSemverRegexOriginal-8 725662 1651 ns/op BenchmarkSemverRegexUpdated-8 874554 1280 ns/op PASS ok _/tmp/test 2.357s ```
GiteaMirror commented 2026-04-20 10:17:02 -05:00
Author
Owner
Copy Link

@jwdonahue commented on GitHub (May 3, 2022):

Does your regex work correctly against all of the test strings?

https://regex101.com/r/Ly7O1x/3/

The official regex matches a SemVer string as defined by the spec and rejects those that don't match, including non-SemVer prefix and postfix content that might be on the line. I don't see where you've eliminated back tracking, but my regex foo is a tad rusty. We did put in some effort to reduce backtracking, but I seem to recall we could not eliminate it.

Your benchmark code needs some work. For one thing, it lacks a warm-up cycle, and for another, it should iterate many times over each of those loops, but randomly select their order on each pass (or some other arrangement that eliminates warm-up and ordering effects). I don't know much about go, but care should be taken to measure CPU time spent executing the regex bits, not time spent suspended by the operating environment in other code. On modern systems, that usually involves system level perf counters for the respective execution threads. I would also expect to see a lot more test strings. It's easy to optimize a regex for just one test string, eliminate the regex!

I would certainly support reordering (provided it works for all of our test strings), but not removing the anchors. Our tests depend on those, but reordering would reduce the likelihood of someone introducing errors, if/when they need to remove the anchors for their specific application.

Nice catch btw.

<!-- gh-comment-id:1115724906 --> @jwdonahue commented on GitHub (May 3, 2022): Does your regex work correctly against all of the test strings? https://regex101.com/r/Ly7O1x/3/ The official regex matches a SemVer string as defined by the spec and rejects those that don't match, including non-SemVer prefix and postfix content that might be on the line. I don't see where you've eliminated back tracking, but my regex foo is a tad rusty. We did put in some effort to reduce backtracking, but I seem to recall we could not eliminate it. Your benchmark code needs some work. For one thing, it lacks a warm-up cycle, and for another, it should iterate many times over each of those loops, but randomly select their order on each pass (or some other arrangement that eliminates warm-up and ordering effects). I don't know much about go, but care should be taken to measure CPU time spent executing the regex bits, not time spent suspended by the operating environment in other code. On modern systems, that usually involves system level perf counters for the respective execution threads. I would also expect to see a lot more test strings. It's easy to optimize a regex for just one test string, eliminate the regex! ----- I would certainly support reordering (provided it works for all of our test strings), but not removing the anchors. Our tests depend on those, but reordering would reduce the likelihood of someone introducing errors, if/when they need to remove the anchors for their specific application. Nice catch btw.
GiteaMirror commented 2026-04-20 10:17:05 -05:00
Author
Owner
Copy Link

@wg1k commented on GitHub (Jun 6, 2022):

I was about to make a similar proposal and got here.

I've found that reordering the conditionals in the non-anchors version seems to improve the performance slightly.

I changed the internal order of major, minor, patch and prerelease.

Original:

^(0|[1-9]\d*)\.(0|[1-9]\d*)\.(0|[1-9]\d*)(?:-((?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*)(?:\.(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*))*))?(?:\+([0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$

Modified:

^([1-9]\d*|0)\.([1-9]\d*|0)\.([1-9]\d*|0)(?:-((?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0)(?:\.(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0))*))?(?:\+([0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$

It seems to work correctly against the test suite and reports 2406 steps vs 2518 in the original with PCRE and PCRE2.
Please, review https://regex101.com/r/DnUaMG/2

Original: https://regex101.com/r/vkijKf/1/

<!-- gh-comment-id:1147180295 --> @wg1k commented on GitHub (Jun 6, 2022): I was about to make a similar proposal and got here. I've found that reordering the conditionals in the non-anchors version seems to improve the performance slightly. I changed the internal order of `major`, `minor`, `patch` and `prerelease`. Original: ``` ^(0|[1-9]\d*)\.(0|[1-9]\d*)\.(0|[1-9]\d*)(?:-((?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*)(?:\.(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*))*))?(?:\+([0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$ ``` Modified: ```regex ^([1-9]\d*|0)\.([1-9]\d*|0)\.([1-9]\d*|0)(?:-((?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0)(?:\.(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0))*))?(?:\+([0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$ ``` It seems to work correctly against the test suite and reports 2406 steps vs 2518 in the original with PCRE and PCRE2. Please, review https://regex101.com/r/DnUaMG/2 Original: https://regex101.com/r/vkijKf/1/
GiteaMirror commented 2026-04-20 10:17:07 -05:00
Author
Owner
Copy Link

@wg1k commented on GitHub (Jun 6, 2022):

My modified with-anchors version https://regex101.com/r/FFKHyH/1 contains the same reorder proposed by @sebastien-rosset (it passes the tests) in the prerelease plus my changes in major, minor and patch.

^(?P<major>[1-9]\d*|0)\.(?P<minor>[1-9]\d*|0)\.(?P<patch>[1-9]\d*|0)(?:-(?P<prerelease>(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0)(?:\.(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0))*))?(?:\+(?P<buildmetadata>[0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$

Same 2406 steps result.

<!-- gh-comment-id:1147258127 --> @wg1k commented on GitHub (Jun 6, 2022): My modified with-anchors version https://regex101.com/r/FFKHyH/1 contains the same reorder proposed by @sebastien-rosset (it passes the tests) in the `prerelease` plus my changes in `major`, `minor` and `patch`. ``` ^(?P<major>[1-9]\d*|0)\.(?P<minor>[1-9]\d*|0)\.(?P<patch>[1-9]\d*|0)(?:-(?P<prerelease>(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0)(?:\.(?:\d*[a-zA-Z-][0-9a-zA-Z-]*|[1-9]\d*|0))*))?(?:\+(?P<buildmetadata>[0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$ ``` Same 2406 steps result.
GiteaMirror commented 2026-04-20 10:17:10 -05:00
Author
Owner
Copy Link

@jwdonahue commented on GitHub (May 3, 2023):

Fewer steps is good. Not sure it's worth the effort of changing the FAQ for a 4.5% performance increase on something that is rarely used against more than a handful of strings at one time. I wonder if the improvement still holds, if you remove the degenerate forms from the oracles?

My primary motivation for pushing for a standard SemVer regex was driven by my finding several hundred incorrect SemVer implementations on GitHub alone, most of which were regex's. So we went looking for a regex that was clear (as regex's go), correct, and not prone to infinite backtracking or timeouts. So basically, "the one true, recognizably correct, reasonably efficient implementation" of a SemVer regex.

I am not against updating the FAQ for this, but if we do, let's make sure it's the last time we ever modify the regex bits. We need a much larger set of oracles taken from the real world.

<!-- gh-comment-id:1533857566 --> @jwdonahue commented on GitHub (May 3, 2023): Fewer steps is good. Not sure it's worth the effort of changing the FAQ for a 4.5% performance increase on something that is rarely used against more than a handful of strings at one time. I wonder if the improvement still holds, if you remove the degenerate forms from the oracles? My primary motivation for pushing for a standard SemVer regex was driven by my finding several hundred incorrect SemVer implementations on GitHub alone, most of which were regex's. So we went looking for a regex that was clear (as regex's go), correct, and not prone to infinite backtracking or timeouts. So basically, "the one true, recognizably correct, reasonably efficient implementation" of a SemVer regex. I am not against updating the FAQ for this, but if we do, let's make sure it's the last time we ever modify the regex bits. We need a much larger set of oracles taken from the real world.
GiteaMirror commented 2026-04-20 10:17:10 -05:00
Author
Owner
Copy Link

@jwdonahue commented on GitHub (May 3, 2023):

See also #788. Apparently the \d* accepts non-ascii digits, which is definitely out of spec, but maybe not unacceptable. I definitely have code that would be broken (I avoid using regex's in production code) if the spec allowed characters outside the range of [0-9][A-Z][a-z].-+.

<!-- gh-comment-id:1533875657 --> @jwdonahue commented on GitHub (May 3, 2023): See also #788. Apparently the \d* accepts non-ascii digits, which is definitely out of spec, but maybe not unacceptable. I definitely have code that would be broken (I avoid using regex's in production code) if the spec allowed characters outside the range of [0-9][A-Z][a-z]\.-+.
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
Clear labels
bug
consensus seeking
duplicate
extend
layout
pull-request
Mirrored from GitHub Pull Request
 question
RFC
spelling/grammar
staled
update
waiting for PR
won't fix
No Label
Milestone
No items
No Milestone
Projects
Clear projects
No project
Assignees
Clear assignees
GiteaMirror ninjasurge
No Assignees
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: github-starred/semver#2275
Delete Branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?