1package semver 2 3import ( 4 "fmt" 5 "regexp" 6 "sort" 7 "strings" 8 "sync" 9) 10 11var constraintRegex *regexp.Regexp 12var constraintRangeRegex *regexp.Regexp 13 14const cvRegex string = `v?([0-9|x|X|\*]+)(\.[0-9|x|X|\*]+)?(\.[0-9|x|X|\*]+)?` + 15 `(-([0-9A-Za-z\-]+(\.[0-9A-Za-z\-]+)*))?` + 16 `(\+([0-9A-Za-z\-]+(\.[0-9A-Za-z\-]+)*))?` 17 18func init() { 19 constraintOps := []string{ 20 "", 21 "=", 22 "!=", 23 ">", 24 "<", 25 ">=", 26 "=>", 27 "<=", 28 "=<", 29 "~", 30 "~>", 31 "^", 32 } 33 34 ops := make([]string, 0, len(constraintOps)) 35 for _, op := range constraintOps { 36 ops = append(ops, regexp.QuoteMeta(op)) 37 } 38 39 constraintRegex = regexp.MustCompile(fmt.Sprintf( 40 `^\s*(%s)\s*(%s)\s*$`, 41 strings.Join(ops, "|"), 42 cvRegex)) 43 44 constraintRangeRegex = regexp.MustCompile(fmt.Sprintf( 45 `\s*(%s)\s* - \s*(%s)\s*`, 46 cvRegex, cvRegex)) 47} 48 49// Constraint is the interface that wraps checking a semantic version against 50// one or more constraints to find a match. 51type Constraint interface { 52 // Constraints compose the fmt.Stringer interface. This method is the 53 // bijective inverse of NewConstraint(): if a string yielded from this 54 // method is passed to NewConstraint(), a byte-identical instance of the 55 // original Constraint will be returend. 56 fmt.Stringer 57 58 // ImpliedCaretString converts the Constraint to a string in the same manner 59 // as String(), but treats the empty operator as equivalent to ^, rather 60 // than =. 61 // 62 // In the same way that String() is the inverse of NewConstraint(), this 63 // method is the inverse of to NewConstraintIC(). 64 ImpliedCaretString() string 65 66 // Matches checks that a version satisfies the constraint. If it does not, 67 // an error is returned indcating the problem; if it does, the error is nil. 68 Matches(v Version) error 69 70 // Intersect computes the intersection between the receiving Constraint and 71 // passed Constraint, and returns a new Constraint representing the result. 72 Intersect(Constraint) Constraint 73 74 // Union computes the union between the receiving Constraint and the passed 75 // Constraint, and returns a new Constraint representing the result. 76 Union(Constraint) Constraint 77 78 // MatchesAny returns a bool indicating whether there exists any version that 79 // satisfies both the receiver constraint, and the passed Constraint. 80 // 81 // In other words, this reports whether an intersection would be non-empty. 82 MatchesAny(Constraint) bool 83 84 // Restrict implementation of this interface to this package. We need the 85 // flexibility of an interface, but we cover all possibilities here; closing 86 // off the interface to external implementation lets us safely do tricks 87 // with types for magic types (none and any) 88 _private() 89} 90 91// realConstraint is used internally to differentiate between any, none, and 92// unionConstraints, vs. Version and rangeConstraints. 93type realConstraint interface { 94 Constraint 95 _real() 96} 97 98// CacheConstraints controls whether or not parsed constraints are cached 99var CacheConstraints = true 100var constraintCache = make(map[string]ccache) 101var constraintCacheIC = make(map[string]ccache) 102var constraintCacheLock sync.RWMutex 103 104type ccache struct { 105 c Constraint 106 err error 107} 108 109// NewConstraint takes a string representing a set of semver constraints, and 110// returns a corresponding Constraint object. Constraints are suitable 111// for checking Versions for admissibility, or combining with other Constraint 112// objects. 113// 114// If an invalid constraint string is passed, more information is provided in 115// the returned error string. 116func NewConstraint(in string) (Constraint, error) { 117 return newConstraint(in, false, constraintCache) 118} 119 120// NewConstraintIC ("Implied Caret") is the same as NewConstraint, except that 121// it treats an absent operator as being equivalent to ^ instead of =. 122func NewConstraintIC(in string) (Constraint, error) { 123 return newConstraint(in, true, constraintCacheIC) 124} 125 126func newConstraint(in string, ic bool, cache map[string]ccache) (Constraint, error) { 127 if CacheConstraints { 128 constraintCacheLock.RLock() 129 if final, exists := cache[in]; exists { 130 constraintCacheLock.RUnlock() 131 return final.c, final.err 132 } 133 constraintCacheLock.RUnlock() 134 } 135 136 // Rewrite - ranges into a comparison operation. 137 c := rewriteRange(in) 138 139 ors := strings.Split(c, "||") 140 or := make([]Constraint, len(ors)) 141 for k, v := range ors { 142 cs := strings.Split(v, ",") 143 result := make([]Constraint, len(cs)) 144 for i, s := range cs { 145 pc, err := parseConstraint(s, ic) 146 if err != nil { 147 if CacheConstraints { 148 constraintCacheLock.Lock() 149 cache[in] = ccache{err: err} 150 constraintCacheLock.Unlock() 151 } 152 return nil, err 153 } 154 155 result[i] = pc 156 } 157 or[k] = Intersection(result...) 158 } 159 160 final := Union(or...) 161 162 if CacheConstraints { 163 constraintCacheLock.Lock() 164 cache[in] = ccache{c: final} 165 constraintCacheLock.Unlock() 166 } 167 168 return final, nil 169} 170 171// Intersection computes the intersection between N Constraints, returning as 172// compact a representation of the intersection as possible. 173// 174// No error is indicated if all the sets are collectively disjoint; you must inspect the 175// return value to see if the result is the empty set (by calling IsNone() on 176// it). 177func Intersection(cg ...Constraint) Constraint { 178 // If there's zero or one constraints in the group, we can quit fast 179 switch len(cg) { 180 case 0: 181 // Zero members, only sane thing to do is return none 182 return None() 183 case 1: 184 // Just one member means that's our final constraint 185 return cg[0] 186 } 187 188 car, cdr := cg[0], cg[1:] 189 for _, c := range cdr { 190 if IsNone(car) { 191 return None() 192 } 193 car = car.Intersect(c) 194 } 195 196 return car 197} 198 199// Union takes a variable number of constraints, and returns the most compact 200// possible representation of those constraints. 201// 202// This effectively ORs together all the provided constraints. If any of the 203// included constraints are the set of all versions (any), that supercedes 204// everything else. 205func Union(cg ...Constraint) Constraint { 206 // If there's zero or one constraints in the group, we can quit fast 207 switch len(cg) { 208 case 0: 209 // Zero members, only sane thing to do is return none 210 return None() 211 case 1: 212 // One member, so the result will just be that 213 return cg[0] 214 } 215 216 // Preliminary pass to look for 'any' in the current set (and bail out early 217 // if found), but also construct a []realConstraint for everything else 218 var real constraintList 219 220 for _, c := range cg { 221 switch tc := c.(type) { 222 case any: 223 return c 224 case none: 225 continue 226 case Version: 227 //heap.Push(&real, tc) 228 real = append(real, tc) 229 case rangeConstraint: 230 //heap.Push(&real, tc) 231 real = append(real, tc) 232 case unionConstraint: 233 real = append(real, tc...) 234 //for _, c2 := range tc { 235 //heap.Push(&real, c2) 236 //} 237 default: 238 panic("unknown constraint type") 239 } 240 } 241 // TODO wtf why isn't heap working...so, ugh, have to do this 242 243 // Sort both the versions and ranges into ascending order 244 sort.Sort(real) 245 246 // Iteratively merge the constraintList elements 247 var nuc unionConstraint 248 for _, c := range real { 249 if len(nuc) == 0 { 250 nuc = append(nuc, c) 251 continue 252 } 253 254 last := nuc[len(nuc)-1] 255 switch lt := last.(type) { 256 case Version: 257 switch ct := c.(type) { 258 case Version: 259 // Two versions in a row; only append if they're not equal 260 if !lt.Equal(ct) { 261 nuc = append(nuc, ct) 262 } 263 case rangeConstraint: 264 // Last was version, current is range. constraintList sorts by 265 // min version, so it's guaranteed that the version will be less 266 // than the range's min, guaranteeing that these are disjoint. 267 // 268 // ...almost. If the min of the range is the same as the 269 // version, then a union should merge the two by making the 270 // range inclusive at the bottom. 271 if lt.Equal(ct.min) { 272 ct.includeMin = true 273 nuc[len(nuc)-1] = ct 274 } else { 275 nuc = append(nuc, c) 276 } 277 } 278 case rangeConstraint: 279 switch ct := c.(type) { 280 case Version: 281 // Last was range, current is version. constraintList sort invariants guarantee 282 // that the version will be greater than the min, so we have to 283 // determine if the version is less than the max. If it is, we 284 // subsume it into the range with a Union call. 285 // 286 // Lazy version: just union them and let rangeConstraint figure 287 // it out, then switch on the result type. 288 c2 := lt.Union(ct) 289 if crc, ok := c2.(realConstraint); ok { 290 nuc[len(nuc)-1] = crc 291 } else { 292 // Otherwise, all it can be is a union constraint. First 293 // item in the union will be the same range, second will be the 294 // version, so append onto nuc from one back from the end 295 nuc = append(nuc[:len(nuc)-1], c2.(unionConstraint)...) 296 } 297 case rangeConstraint: 298 if lt.MatchesAny(ct) || areAdjacent(lt, ct) { 299 // If the previous range overlaps or is adjacent to the 300 // current range, we know they'll be able to merge together, 301 // so overwrite the last item in nuc with the result of that 302 // merge (which is what Union will produce) 303 nuc[len(nuc)-1] = lt.Union(ct).(realConstraint) 304 } else { 305 nuc = append(nuc, c) 306 } 307 } 308 } 309 } 310 311 if len(nuc) == 1 { 312 return nuc[0] 313 } 314 return nuc 315} 316