Skip to main content

semantic_versions/
range.rs

1use std::fmt;
2use std::str::FromStr;
3
4use crate::identifier::Identifiers;
5use crate::version::{build, numeric, pre_release, split_reference, Cursor, Version};
6use crate::{Error, MAX_LENGTH};
7
8/// A comparator operator. `Eq` is written without an operator (`1.2.3`).
9#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
10pub enum Op {
11    /// `<`
12    Lt,
13    /// `<=`
14    Lte,
15    /// `>`
16    Gt,
17    /// `>=`
18    Gte,
19    /// `=` (written as a bare version)
20    Eq,
21}
22
23impl Op {
24    fn as_str(self) -> &'static str {
25        match self {
26            Op::Lt => "<",
27            Op::Lte => "<=",
28            Op::Gt => ">",
29            Op::Gte => ">=",
30            Op::Eq => "",
31        }
32    }
33}
34
35/// A primitive comparator: an operator and a version, or "any" (matches every
36/// version). A build on the comparator's version is a **build channel**: a
37/// prefix filter on the candidate's build, orthogonal to the numeric bound. A
38/// pre-release on it declares a **pre-release channel** for its tuple.
39#[derive(Debug, Clone, PartialEq, Eq)]
40pub struct Comparator {
41    /// The operator.
42    pub op: Op,
43    /// The bound, or `None` for the "any" comparator.
44    pub version: Option<Version>,
45}
46
47impl Comparator {
48    fn any() -> Self {
49        Comparator {
50            op: Op::Eq,
51            version: None,
52        }
53    }
54
55    fn new(op: Op, version: Version) -> Self {
56        // `>=0.0.0` bounds nothing: it is the "any" comparator.
57        if op == Op::Gte
58            && version.major == 0
59            && version.minor == 0
60            && version.patch == 0
61            && version.pre().is_empty()
62            && version.build().is_empty()
63        {
64            return Comparator::any();
65        }
66        Comparator {
67            op,
68            version: Some(version),
69        }
70    }
71
72    /// True for the comparator that matches every version.
73    pub fn is_any(&self) -> bool {
74        self.version.is_none()
75    }
76
77    fn is_null(&self) -> bool {
78        matches!(&self.version, Some(v) if self.op == Op::Lt
79            && v.major == 0 && v.minor == 0 && v.patch == 0
80            && v.pre().as_str() == "0" && v.build().is_empty())
81    }
82
83    /// True if `version` passes the numeric bound and, when the comparator
84    /// declares a build channel, carries a build in that channel.
85    #[inline]
86    pub fn test(&self, version: &Version) -> bool {
87        let Some(bound) = &self.version else {
88            return true;
89        };
90        let ord = version.cmp_ignoring_build(bound);
91        let numeric = match self.op {
92            Op::Lt => ord.is_lt(),
93            Op::Lte => ord.is_le(),
94            Op::Gt => ord.is_gt(),
95            Op::Gte => ord.is_ge(),
96            Op::Eq => ord.is_eq(),
97        };
98        if !numeric {
99            return false;
100        }
101        let channel = bound.build();
102        channel.is_empty() || version.build().starts_with(channel)
103    }
104}
105
106impl fmt::Display for Comparator {
107    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
108        match &self.version {
109            None => Ok(()),
110            Some(v) => write!(f, "{}{}", self.op.as_str(), v),
111        }
112    }
113}
114
115#[derive(Debug, Clone, PartialEq, Eq)]
116struct Set {
117    comparators: Vec<Comparator>,
118    /// `*-*`: pre-releases on every tuple are admitted.
119    universal_pre: bool,
120    /// `X.Y.Z-*`: any pre-release of these tuples is admitted.
121    any_pre: Vec<(u64, u64, u64)>,
122}
123
124impl Set {
125    #[inline]
126    fn test(&self, v: &Version) -> bool {
127        if !self.comparators.iter().all(|c| c.test(v)) {
128            return false;
129        }
130        // Stable versions are unaffected by pre-release channels.
131        if v.pre().is_empty() || self.universal_pre {
132            return true;
133        }
134        if self
135            .any_pre
136            .iter()
137            .any(|&(a, b, c)| a == v.major && b == v.minor && c == v.patch)
138        {
139            return true;
140        }
141        // A pre-release is admitted only by a comparator that declares a channel
142        // on the same tuple whose identifiers it begins with.
143        self.comparators.iter().any(|c| match &c.version {
144            Some(b) if !b.pre().is_empty() && b.same_tuple(v) => v.pre().starts_with(b.pre()),
145            _ => false,
146        })
147    }
148}
149
150/// A parsed range: one or more comparator sets joined by `||`, optionally
151/// scoped to a context (`npm:react@^18`).
152#[derive(Debug, Clone, PartialEq, Eq)]
153pub struct Range {
154    context: Option<Box<str>>,
155    sets: Vec<Set>,
156}
157
158impl Range {
159    /// Parse a range. Advanced syntax (hyphen, x-ranges, `~`, `~>`, `^`, `-*`,
160    /// `*-*`) desugars to primitive comparators exactly as in the specification.
161    pub fn parse(input: &str) -> Result<Self, Error> {
162        if input.len() > MAX_LENGTH {
163            return Err(Error::TooLong);
164        }
165        let (context, body) = split_reference(input);
166        let mut sets = Vec::new();
167        for part in body.split("||") {
168            sets.push(parse_set(part.trim(), input)?);
169        }
170        if sets.len() > 1 {
171            // Drop sets that can match nothing (unless that is all there is),
172            // and collapse to "any" if any set matches everything.
173            let first = sets[0].clone();
174            sets.retain(|s| !s.comparators.first().is_some_and(Comparator::is_null));
175            if sets.is_empty() {
176                sets.push(first);
177            } else if sets.len() > 1 {
178                if let Some(any) = sets
179                    .iter()
180                    .find(|s| s.comparators.len() == 1 && s.comparators[0].is_any())
181                {
182                    sets = vec![any.clone()];
183                }
184            }
185        }
186        Ok(Range {
187            context: context.map(Into::into),
188            sets,
189        })
190    }
191
192    /// The context this range is scoped to, if any.
193    pub fn context(&self) -> Option<&str> {
194        self.context.as_deref()
195    }
196
197    /// The desugared comparator sets.
198    pub fn comparator_sets(&self) -> impl Iterator<Item = &[Comparator]> {
199        self.sets.iter().map(|s| s.comparators.as_slice())
200    }
201
202    /// True if `version` satisfies the range. A context-scoped range only
203    /// admits versions of the same context.
204    #[inline]
205    pub fn test(&self, version: &Version) -> bool {
206        if let Some(c) = &self.context {
207            if version.context() != Some(&**c) {
208                return false;
209            }
210        }
211        self.sets.iter().any(|s| s.test(version))
212    }
213
214    /// Alias of [`Range::test`].
215    pub fn satisfies(&self, version: &Version) -> bool {
216        self.test(version)
217    }
218}
219
220impl fmt::Display for Range {
221    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
222        for (i, set) in self.sets.iter().enumerate() {
223            if i > 0 {
224                f.write_str("||")?;
225            }
226            let mut first = true;
227            for c in &set.comparators {
228                if c.is_any() {
229                    continue;
230                }
231                if !first {
232                    f.write_str(" ")?;
233                }
234                first = false;
235                write!(f, "{c}")?;
236            }
237        }
238        Ok(())
239    }
240}
241
242impl FromStr for Range {
243    type Err = Error;
244    fn from_str(s: &str) -> Result<Self, Self::Err> {
245        Range::parse(s)
246    }
247}
248
249// --------------------------------------------------------------- desugaring
250
251/// One component of a partial version: a number or a wildcard (`x`, `X`, `*`,
252/// or absent).
253#[derive(Clone, Copy)]
254enum Xr {
255    X,
256    N(u64),
257}
258
259impl Xr {
260    fn n(self) -> u64 {
261        match self {
262            Xr::N(n) => n,
263            Xr::X => 0,
264        }
265    }
266    fn is_x(self) -> bool {
267        matches!(self, Xr::X)
268    }
269}
270
271struct Partial {
272    major: Xr,
273    minor: Xr,
274    patch: Xr,
275    pre: Identifiers,
276    build: Identifiers,
277}
278
279fn xr(cur: &mut Cursor<'_>, input: &str) -> Result<Xr, Error> {
280    match cur.peek() {
281        Some(b'x' | b'X' | b'*') => {
282            cur.i += 1;
283            Ok(Xr::X)
284        }
285        Some(c) if c.is_ascii_digit() => Ok(Xr::N(numeric(cur, input)?)),
286        _ => Err(Error::InvalidRange(input.to_string())),
287    }
288}
289
290/// `<xr> [ "." <xr> [ "." <xr> <qualifier>? ] ]`
291fn partial(s: &str, input: &str) -> Result<Partial, Error> {
292    let mut cur = Cursor::new(s);
293    let major = xr(&mut cur, input)?;
294    let mut p = Partial {
295        major,
296        minor: Xr::X,
297        patch: Xr::X,
298        pre: Identifiers::empty(),
299        build: Identifiers::empty(),
300    };
301    if cur.eat(b'.') {
302        p.minor = xr(&mut cur, input)?;
303        if cur.eat(b'.') {
304            p.patch = xr(&mut cur, input)?;
305            if cur.eat(b'-') {
306                p.pre = pre_release(&mut cur, input)
307                    .map_err(|_| Error::InvalidRange(input.to_string()))?;
308            }
309            if cur.eat(b'+') {
310                p.build =
311                    build(&mut cur, input).map_err(|_| Error::InvalidRange(input.to_string()))?;
312            }
313        }
314    }
315    if !cur.done() {
316        return Err(Error::InvalidRange(input.to_string()));
317    }
318    Ok(p)
319}
320
321fn ver(major: u64, minor: u64, patch: u64, pre: Identifiers) -> Version {
322    Version::new(major, minor, patch).with_pre(pre)
323}
324
325fn zero() -> Identifiers {
326    Identifiers::from_validated("0")
327}
328
329fn none() -> Identifiers {
330    Identifiers::empty()
331}
332
333/// Attach a build channel to every comparator a `~`/`^` desugars to.
334fn with_channel(mut comps: Vec<Comparator>, channel: &Identifiers) -> Vec<Comparator> {
335    if !channel.is_empty() {
336        for c in comps.iter_mut() {
337            if let Some(v) = c.version.take() {
338                c.version = Some(v.with_build(channel.clone()));
339            }
340        }
341        // A channel can turn `>=0.0.0` back into a real bound.
342        for c in comps.iter_mut() {
343            if c.version.is_none() {
344                *c = Comparator {
345                    op: Op::Gte,
346                    version: Some(Version::new(0, 0, 0).with_build(channel.clone())),
347                };
348            }
349        }
350    }
351    comps
352}
353
354fn tilde(p: Partial) -> Vec<Comparator> {
355    let Partial {
356        major,
357        minor,
358        patch,
359        pre,
360        build,
361    } = p;
362    if major.is_x() {
363        return vec![Comparator::any()];
364    }
365    let (m, mi) = (major.n(), minor.n());
366    let out = if minor.is_x() {
367        vec![
368            Comparator::new(Op::Gte, ver(m, 0, 0, none())),
369            Comparator::new(Op::Lt, ver(m + 1, 0, 0, zero())),
370        ]
371    } else if patch.is_x() {
372        vec![
373            Comparator::new(Op::Gte, ver(m, mi, 0, none())),
374            Comparator::new(Op::Lt, ver(m, mi + 1, 0, zero())),
375        ]
376    } else {
377        vec![
378            Comparator::new(Op::Gte, ver(m, mi, patch.n(), pre)),
379            Comparator::new(Op::Lt, ver(m, mi + 1, 0, zero())),
380        ]
381    };
382    with_channel(out, &build)
383}
384
385fn caret(p: Partial) -> Vec<Comparator> {
386    let Partial {
387        major,
388        minor,
389        patch,
390        pre,
391        build,
392    } = p;
393    if major.is_x() {
394        return vec![Comparator::any()];
395    }
396    let (m, mi, pa) = (major.n(), minor.n(), patch.n());
397    let out = if minor.is_x() {
398        vec![
399            Comparator::new(Op::Gte, ver(m, 0, 0, none())),
400            Comparator::new(Op::Lt, ver(m + 1, 0, 0, zero())),
401        ]
402    } else if patch.is_x() {
403        let upper = if m == 0 {
404            ver(0, mi + 1, 0, zero())
405        } else {
406            ver(m + 1, 0, 0, zero())
407        };
408        vec![
409            Comparator::new(Op::Gte, ver(m, mi, 0, none())),
410            Comparator::new(Op::Lt, upper),
411        ]
412    } else {
413        let upper = if m == 0 {
414            if mi == 0 {
415                ver(0, 0, pa + 1, zero())
416            } else {
417                ver(0, mi + 1, 0, zero())
418            }
419        } else {
420            ver(m + 1, 0, 0, zero())
421        };
422        vec![
423            Comparator::new(Op::Gte, ver(m, mi, pa, pre)),
424            Comparator::new(Op::Lt, upper),
425        ]
426    };
427    with_channel(out, &build)
428}
429
430/// A plain or x-range comparator with an optional operator.
431fn xrange(op: Op, p: Partial) -> Vec<Comparator> {
432    let Partial {
433        major,
434        minor,
435        patch,
436        pre,
437        build,
438    } = p;
439    let xm = major.is_x() || minor.is_x();
440    let any_x = xm || patch.is_x();
441    if major.is_x() {
442        return match op {
443            Op::Gt | Op::Lt => vec![Comparator::new(Op::Lt, ver(0, 0, 0, zero()))],
444            _ => vec![Comparator::any()],
445        };
446    }
447    let m = major.n();
448    let mi = if xm { 0 } else { minor.n() };
449    if any_x && op != Op::Eq {
450        return vec![match op {
451            Op::Gt => {
452                if xm {
453                    Comparator::new(Op::Gte, ver(m + 1, 0, 0, none()))
454                } else {
455                    Comparator::new(Op::Gte, ver(m, mi + 1, 0, none()))
456                }
457            }
458            Op::Lte => {
459                if xm {
460                    Comparator::new(Op::Lt, ver(m + 1, 0, 0, zero()))
461                } else {
462                    Comparator::new(Op::Lt, ver(m, mi + 1, 0, zero()))
463                }
464            }
465            Op::Lt => Comparator::new(Op::Lt, ver(m, mi, 0, zero())),
466            _ => Comparator::new(op, ver(m, mi, 0, none())),
467        }];
468    }
469    if xm {
470        return vec![
471            Comparator::new(Op::Gte, ver(m, 0, 0, none())),
472            Comparator::new(Op::Lt, ver(m + 1, 0, 0, zero())),
473        ];
474    }
475    if patch.is_x() {
476        return vec![
477            Comparator::new(Op::Gte, ver(m, mi, 0, none())),
478            Comparator::new(Op::Lt, ver(m, mi + 1, 0, zero())),
479        ];
480    }
481    vec![Comparator::new(
482        op,
483        ver(m, mi, patch.n(), pre).with_build(build),
484    )]
485}
486
487/// `<partial> - <partial>`: an inclusive span. Builds on either endpoint are
488/// ignored; a pre-release on an endpoint is kept as that endpoint's channel.
489fn hyphen(from: Partial, to: Partial) -> Vec<Comparator> {
490    let mut out = Vec::new();
491    if !from.major.is_x() {
492        let v = if from.minor.is_x() {
493            ver(from.major.n(), 0, 0, none())
494        } else if from.patch.is_x() {
495            ver(from.major.n(), from.minor.n(), 0, none())
496        } else {
497            ver(from.major.n(), from.minor.n(), from.patch.n(), from.pre)
498        };
499        out.push(Comparator::new(Op::Gte, v));
500    }
501    if !to.major.is_x() {
502        out.push(if to.minor.is_x() {
503            Comparator::new(Op::Lt, ver(to.major.n() + 1, 0, 0, zero()))
504        } else if to.patch.is_x() {
505            Comparator::new(Op::Lt, ver(to.major.n(), to.minor.n() + 1, 0, zero()))
506        } else {
507            Comparator::new(
508                Op::Lte,
509                ver(to.major.n(), to.minor.n(), to.patch.n(), to.pre),
510            )
511        });
512    }
513    if out.is_empty() {
514        out.push(Comparator::any());
515    }
516    out
517}
518
519/// `X.Y.Z-*` with an optional operator: the empty-prefix pre-release channel.
520fn tuple_pre(tok: &str) -> Option<(&str, u64, u64, u64)> {
521    let body = tok.strip_suffix("-*")?;
522    let (op, rest) = ["<=", ">=", "^", "~", "<", ">", "="]
523        .iter()
524        .find_map(|op| body.strip_prefix(op).map(|r| (*op, r)))
525        .unwrap_or(("", body));
526    let mut cur = Cursor::new(rest);
527    let a = numeric(&mut cur, tok).ok()?;
528    if !cur.eat(b'.') {
529        return None;
530    }
531    let b = numeric(&mut cur, tok).ok()?;
532    if !cur.eat(b'.') {
533        return None;
534    }
535    let c = numeric(&mut cur, tok).ok()?;
536    cur.done().then_some((op, a, b, c))
537}
538
539fn comparator_token(tok: &str, input: &str) -> Result<Vec<Comparator>, Error> {
540    if tok.is_empty() || tok == "*" {
541        return Ok(vec![Comparator::any()]);
542    }
543    if let Some(rest) = tok.strip_prefix('^') {
544        return Ok(caret(partial(rest, input)?));
545    }
546    if let Some(rest) = tok.strip_prefix("~>").or_else(|| tok.strip_prefix('~')) {
547        return Ok(tilde(partial(rest, input)?));
548    }
549    let (op, rest) = if let Some(r) = tok.strip_prefix(">=") {
550        (Op::Gte, r)
551    } else if let Some(r) = tok.strip_prefix("<=") {
552        (Op::Lte, r)
553    } else if let Some(r) = tok.strip_prefix('>') {
554        (Op::Gt, r)
555    } else if let Some(r) = tok.strip_prefix('<') {
556        (Op::Lt, r)
557    } else if let Some(r) = tok.strip_prefix('=') {
558        (Op::Eq, r)
559    } else {
560        (Op::Eq, tok)
561    };
562    Ok(xrange(op, partial(rest, input)?))
563}
564
565fn same_comparator(a: &Comparator, b: &Comparator) -> bool {
566    a.op == b.op
567        && match (&a.version, &b.version) {
568            (None, None) => true,
569            (Some(x), Some(y)) => {
570                x.major == y.major
571                    && x.minor == y.minor
572                    && x.patch == y.patch
573                    && x.pre() == y.pre()
574                    && x.build() == y.build()
575            }
576            _ => false,
577        }
578}
579
580const OPERATORS: [&str; 8] = ["<", "<=", ">", ">=", "=", "~", "~>", "^"];
581
582fn parse_set(s: &str, input: &str) -> Result<Set, Error> {
583    let mut universal_pre = false;
584    let mut any_pre = Vec::new();
585    let mut tokens: Vec<std::borrow::Cow<'_, str>> = Vec::new();
586    for tok in s.split_whitespace() {
587        if tok == "*-*" {
588            universal_pre = true;
589            tokens.push(">=0.0.0-0".into());
590        } else if let Some((op, a, b, c)) = tuple_pre(tok) {
591            any_pre.push((a, b, c));
592            tokens.push(format!("{op}{a}.{b}.{c}-0").into());
593        } else {
594            tokens.push(tok.into());
595        }
596    }
597
598    let mut comps: Vec<Comparator> = Vec::new();
599    if tokens.len() == 3 && tokens[1] == "-" {
600        comps = hyphen(partial(&tokens[0], input)?, partial(&tokens[2], input)?);
601    } else {
602        let mut i = 0;
603        while i < tokens.len() {
604            // `>= 1.2.3`, `~ 1.2`, `^ 1`: an operator separated from its version.
605            if OPERATORS.contains(&&*tokens[i]) && i + 1 < tokens.len() {
606                let joined = format!("{}{}", tokens[i], tokens[i + 1]);
607                comps.extend(comparator_token(&joined, input)?);
608                i += 2;
609            } else {
610                comps.extend(comparator_token(&tokens[i], input)?);
611                i += 1;
612            }
613        }
614        if comps.is_empty() {
615            comps.push(Comparator::any());
616        }
617    }
618
619    // A comparator that can match nothing makes the whole set match nothing.
620    if let Some(null) = comps.iter().find(|c| c.is_null()) {
621        return Ok(Set {
622            comparators: vec![null.clone()],
623            universal_pre,
624            any_pre,
625        });
626    }
627    // Deduplicate by value (keeping first occurrence) and drop a redundant "any".
628    let mut unique: Vec<Comparator> = Vec::with_capacity(comps.len());
629    for c in comps {
630        if !unique.iter().any(|u| same_comparator(u, &c)) {
631            unique.push(c);
632        }
633    }
634    if unique.len() > 1 {
635        unique.retain(|c| !c.is_any());
636    }
637    Ok(Set {
638        comparators: unique,
639        universal_pre,
640        any_pre,
641    })
642}