vivacity_resolver/
intervals.rs

1//! Port of `Composer\Semver\Intervals` (docs/reference/resolver/
2//! semver-Intervals.php): a constraint becomes a list of numeric intervals
3//! `[bound, bound]` plus a set of branches (`dev-*`) that are either included
4//! or excluded; `isSubsetOf`, `haveIntersections` and `compactConstraint`
5//! derive from it. PoolBuilder uses it to know whether an already loaded
6//! package covers a new constraint, and to merge constraints.
7
8use crate::constraint::{Constraint, Op};
9use crate::phpver::version_compare;
10use std::cmp::Ordering;
11
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub struct Interval {
14    pub start: Constraint,
15    pub end: Constraint,
16}
17
18#[derive(Debug, Clone, PartialEq, Eq)]
19pub struct Branches {
20    pub names: Vec<String>,
21    pub exclude: bool,
22}
23
24#[derive(Debug, Clone, PartialEq, Eq)]
25pub struct Intervals {
26    pub numeric: Vec<Interval>,
27    pub branches: Branches,
28}
29
30pub fn from_zero() -> Constraint {
31    Constraint::new(Op::Ge, "0.0.0.0-dev")
32}
33
34pub fn until_positive_infinity() -> Constraint {
35    Constraint::new(Op::Lt, format!("{}.0.0.0", i64::MAX))
36}
37
38fn any_dev() -> Branches {
39    Branches {
40        names: Vec::new(),
41        exclude: true,
42    }
43}
44
45fn no_dev() -> Branches {
46    Branches {
47        names: Vec::new(),
48        exclude: false,
49    }
50}
51
52fn op_of(c: &Constraint) -> Op {
53    match c {
54        Constraint::Single { op, .. } => *op,
55        _ => Op::Eq,
56    }
57}
58
59fn version_of(c: &Constraint) -> &str {
60    match c {
61        Constraint::Single { version, .. } => version,
62        _ => "",
63    }
64}
65
66/// `Intervals::isSubsetOf($candidate, $constraint)`.
67pub fn is_subset_of(candidate: &Constraint, constraint: &Constraint) -> bool {
68    if matches!(constraint, Constraint::MatchAll) {
69        return true;
70    }
71    if matches!(candidate, Constraint::MatchNone) || matches!(constraint, Constraint::MatchNone) {
72        return false;
73    }
74    let intersection = generate(
75        &Constraint::Multi {
76            constraints: vec![candidate.clone(), constraint.clone()],
77            conjunctive: true,
78        },
79        false,
80    );
81    let cand = generate(candidate, false);
82    if intersection.numeric.len() != cand.numeric.len() {
83        return false;
84    }
85    for (a, b) in intersection.numeric.iter().zip(cand.numeric.iter()) {
86        if b.start.to_string() != a.start.to_string() || b.end.to_string() != a.end.to_string() {
87            return false;
88        }
89    }
90    if intersection.branches.exclude != cand.branches.exclude {
91        return false;
92    }
93    if intersection.branches.names.len() != cand.branches.names.len() {
94        return false;
95    }
96    intersection
97        .branches
98        .names
99        .iter()
100        .zip(cand.branches.names.iter())
101        .all(|(a, b)| a == b)
102}
103
104/// `Intervals::haveIntersections($a, $b)`.
105pub fn have_intersections(a: &Constraint, b: &Constraint) -> bool {
106    if matches!(a, Constraint::MatchAll) || matches!(b, Constraint::MatchAll) {
107        return true;
108    }
109    if matches!(a, Constraint::MatchNone) || matches!(b, Constraint::MatchNone) {
110        return false;
111    }
112    let i = generate(
113        &Constraint::Multi {
114            constraints: vec![a.clone(), b.clone()],
115            conjunctive: true,
116        },
117        true,
118    );
119    !i.numeric.is_empty() || i.branches.exclude || !i.branches.names.is_empty()
120}
121
122/// `Intervals::compactConstraint($constraint)`.
123pub fn compact_constraint(constraint: &Constraint) -> Constraint {
124    if !matches!(constraint, Constraint::Multi { .. }) {
125        return constraint.clone();
126    }
127    let intervals = generate(constraint, false);
128    let mut constraints: Vec<Constraint> = Vec::new();
129    let mut has_numeric_match_all = false;
130    let zero = from_zero().to_string();
131    let inf = until_positive_infinity().to_string();
132    if intervals.numeric.len() == 1
133        && intervals.numeric[0].start.to_string() == zero
134        && intervals.numeric[0].end.to_string() == inf
135    {
136        constraints.push(intervals.numeric[0].start.clone());
137        has_numeric_match_all = true;
138    } else {
139        let mut unequal: Vec<Constraint> = Vec::new();
140        let count = intervals.numeric.len();
141        for i in 0..count {
142            let interval = &intervals.numeric[i];
143            if op_of(&interval.end) == Op::Lt && i + 1 < count {
144                let next = &intervals.numeric[i + 1];
145                if version_of(&interval.end) == version_of(&next.start)
146                    && op_of(&next.start) == Op::Gt
147                {
148                    if unequal.is_empty() && interval.start.to_string() != zero {
149                        unequal.push(interval.start.clone());
150                    }
151                    unequal.push(Constraint::new(Op::Ne, version_of(&interval.end)));
152                    continue;
153                }
154            }
155            if !unequal.is_empty() {
156                if interval.end.to_string() != inf {
157                    unequal.push(interval.end.clone());
158                }
159                if unequal.len() > 1 {
160                    constraints.push(Constraint::Multi {
161                        constraints: std::mem::take(&mut unequal),
162                        conjunctive: true,
163                    });
164                } else {
165                    constraints.push(unequal.remove(0));
166                }
167                continue;
168            }
169            if version_of(&interval.start) == version_of(&interval.end)
170                && op_of(&interval.start) == Op::Ge
171                && op_of(&interval.end) == Op::Le
172            {
173                constraints.push(Constraint::new(Op::Eq, version_of(&interval.start)));
174                continue;
175            }
176            if interval.start.to_string() == zero {
177                constraints.push(interval.end.clone());
178            } else if interval.end.to_string() == inf {
179                constraints.push(interval.start.clone());
180            } else {
181                constraints.push(Constraint::Multi {
182                    constraints: vec![interval.start.clone(), interval.end.clone()],
183                    conjunctive: true,
184                });
185            }
186        }
187    }
188
189    let mut dev: Vec<Constraint> = Vec::new();
190    if intervals.branches.names.is_empty() {
191        if intervals.branches.exclude && has_numeric_match_all {
192            return Constraint::MatchAll;
193        }
194    } else {
195        for name in &intervals.branches.names {
196            dev.push(if intervals.branches.exclude {
197                Constraint::new(Op::Ne, name.clone())
198            } else {
199                Constraint::new(Op::Eq, name.clone())
200            });
201        }
202        if intervals.branches.exclude {
203            if constraints.len() > 1 {
204                let mut all = vec![Constraint::Multi {
205                    constraints,
206                    conjunctive: false,
207                }];
208                all.extend(dev);
209                return Constraint::Multi {
210                    constraints: all,
211                    conjunctive: true,
212                };
213            }
214            if constraints.len() == 1 && constraints[0].to_string() == zero {
215                if dev.len() > 1 {
216                    return Constraint::Multi {
217                        constraints: dev,
218                        conjunctive: true,
219                    };
220                }
221                return dev.remove(0);
222            }
223            constraints.extend(dev);
224            return Constraint::Multi {
225                constraints,
226                conjunctive: true,
227            };
228        }
229        constraints.extend(dev);
230    }
231    if constraints.len() > 1 {
232        return Constraint::Multi {
233            constraints,
234            conjunctive: false,
235        };
236    }
237    if constraints.len() == 1 {
238        return constraints.remove(0);
239    }
240    Constraint::MatchNone
241}
242
243/// `Intervals::get` / `generateIntervals`.
244pub fn generate(constraint: &Constraint, stop_on_first_valid: bool) -> Intervals {
245    // `Intervals::$intervalsCache` (keyed by textual form in Composer):
246    // keyed by structural value here, same result.
247    thread_local! {
248        static CACHE: std::cell::RefCell<std::collections::HashMap<(Constraint, bool), Intervals>> =
249            std::cell::RefCell::new(std::collections::HashMap::new());
250    }
251    let key = (constraint.clone(), stop_on_first_valid);
252    if let Some(hit) = CACHE.with(|c| c.borrow().get(&key).cloned()) {
253        return hit;
254    }
255    let out = generate_uncached(constraint, stop_on_first_valid);
256    CACHE.with(|c| {
257        c.borrow_mut().insert(key, out.clone());
258    });
259    out
260}
261
262fn generate_uncached(constraint: &Constraint, stop_on_first_valid: bool) -> Intervals {
263    match constraint {
264        Constraint::MatchAll => Intervals {
265            numeric: vec![Interval {
266                start: from_zero(),
267                end: until_positive_infinity(),
268            }],
269            branches: any_dev(),
270        },
271        Constraint::MatchNone => Intervals {
272            numeric: Vec::new(),
273            branches: no_dev(),
274        },
275        Constraint::Single { .. } => single(constraint),
276        Constraint::Multi {
277            constraints,
278            conjunctive,
279        } => multi(constraints, *conjunctive, stop_on_first_valid),
280    }
281}
282
283/// `array_diff($a, $b)` / `array_intersect` / `array_merge` on lists of
284/// strings (order of `$a` preserved, duplicates preserved).
285fn diff(a: &[String], b: &[String]) -> Vec<String> {
286    a.iter().filter(|x| !b.contains(x)).cloned().collect()
287}
288fn intersect(a: &[String], b: &[String]) -> Vec<String> {
289    a.iter().filter(|x| b.contains(x)).cloned().collect()
290}
291fn unique(a: Vec<String>) -> Vec<String> {
292    let mut out: Vec<String> = Vec::new();
293    for x in a {
294        if !out.contains(&x) {
295            out.push(x);
296        }
297    }
298    out
299}
300
301fn multi(constraints: &[Constraint], conjunctive: bool, stop_on_first_valid: bool) -> Intervals {
302    let mut numeric_groups: Vec<Vec<Interval>> = Vec::new();
303    let mut constraint_branches: Vec<Branches> = Vec::new();
304    for c in constraints {
305        let res = generate(c, false);
306        numeric_groups.push(res.numeric);
307        constraint_branches.push(res.branches);
308    }
309    let mut branches;
310    if !conjunctive {
311        branches = no_dev();
312        for b in &constraint_branches {
313            if b.exclude {
314                if branches.exclude {
315                    branches.names = intersect(&branches.names, &b.names);
316                } else {
317                    branches.exclude = true;
318                    branches.names = diff(&b.names, &branches.names);
319                }
320            } else if branches.exclude {
321                branches.names = diff(&branches.names, &b.names);
322            } else {
323                branches.names.extend(b.names.iter().cloned());
324            }
325        }
326    } else {
327        branches = any_dev();
328        for b in &constraint_branches {
329            if b.exclude {
330                if branches.exclude {
331                    branches.names.extend(b.names.iter().cloned());
332                } else {
333                    branches.names = diff(&branches.names, &b.names);
334                }
335            } else if branches.exclude {
336                branches.names = diff(&b.names, &branches.names);
337                branches.exclude = false;
338            } else {
339                branches.names = intersect(&branches.names, &b.names);
340            }
341        }
342    }
343    branches.names = unique(branches.names);
344
345    if numeric_groups.len() == 1 {
346        return Intervals {
347            numeric: numeric_groups.remove(0),
348            branches,
349        };
350    }
351
352    struct Border {
353        version: String,
354        op: Op,
355        start: bool,
356    }
357    let mut borders: Vec<Border> = Vec::new();
358    for group in &numeric_groups {
359        for interval in group {
360            borders.push(Border {
361                version: version_of(&interval.start).to_owned(),
362                op: op_of(&interval.start),
363                start: true,
364            });
365            borders.push(Border {
366                version: version_of(&interval.end).to_owned(),
367                op: op_of(&interval.end),
368                start: false,
369            });
370        }
371    }
372    let sort_order = |op: Op| -> i32 {
373        match op {
374            Op::Ge => -3,
375            Op::Lt => -2,
376            Op::Gt => 2,
377            Op::Le => 3,
378            _ => 0,
379        }
380    };
381    // usort: stable sort on (version_compare, operator order).
382    borders.sort_by(|a, b| {
383        let order = version_compare(&a.version, &b.version);
384        if order == Ordering::Equal {
385            sort_order(a.op).cmp(&sort_order(b.op))
386        } else {
387            order
388        }
389    });
390
391    let mut active = 0i32;
392    let mut intervals: Vec<Interval> = Vec::new();
393    let threshold = if conjunctive {
394        numeric_groups.len() as i32
395    } else {
396        1
397    };
398    let mut start: Option<Constraint> = None;
399    for border in &borders {
400        if border.start {
401            active += 1;
402        } else {
403            active -= 1;
404        }
405        if start.is_none() && active >= threshold {
406            start = Some(Constraint::new(border.op, border.version.clone()));
407        } else if let Some(s) = &start {
408            if active < threshold {
409                let empty = version_compare(version_of(s), &border.version) == Ordering::Equal
410                    && ((op_of(s) == Op::Gt && border.op == Op::Le)
411                        || (op_of(s) == Op::Ge && border.op == Op::Lt));
412                if !empty {
413                    intervals.push(Interval {
414                        start: s.clone(),
415                        end: Constraint::new(border.op, border.version.clone()),
416                    });
417                    if stop_on_first_valid {
418                        break;
419                    }
420                }
421                start = None;
422            }
423        }
424    }
425    Intervals {
426        numeric: intervals,
427        branches,
428    }
429}
430
431fn single(constraint: &Constraint) -> Intervals {
432    let op = op_of(constraint);
433    let version = version_of(constraint);
434    if version.starts_with("dev-") {
435        let mut numeric = Vec::new();
436        let mut branches = no_dev();
437        if op == Op::Ne {
438            numeric.push(Interval {
439                start: from_zero(),
440                end: until_positive_infinity(),
441            });
442            branches = Branches {
443                names: vec![version.to_owned()],
444                exclude: true,
445            };
446        } else if op == Op::Eq {
447            branches.names.push(version.to_owned());
448        }
449        return Intervals { numeric, branches };
450    }
451    match op {
452        Op::Gt | Op::Ge => Intervals {
453            numeric: vec![Interval {
454                start: constraint.clone(),
455                end: until_positive_infinity(),
456            }],
457            branches: no_dev(),
458        },
459        Op::Lt | Op::Le => Intervals {
460            numeric: vec![Interval {
461                start: from_zero(),
462                end: constraint.clone(),
463            }],
464            branches: no_dev(),
465        },
466        Op::Ne => Intervals {
467            numeric: vec![
468                Interval {
469                    start: from_zero(),
470                    end: Constraint::new(Op::Lt, version),
471                },
472                Interval {
473                    start: Constraint::new(Op::Gt, version),
474                    end: until_positive_infinity(),
475                },
476            ],
477            branches: any_dev(),
478        },
479        Op::Eq => Intervals {
480            numeric: vec![Interval {
481                start: Constraint::new(Op::Ge, version),
482                end: Constraint::new(Op::Le, version),
483            }],
484            branches: no_dev(),
485        },
486    }
487}
488
489#[cfg(test)]
490mod tests {
491    use super::*;
492    use crate::constraint::parse_constraints;
493
494    fn c(s: &str) -> Constraint {
495        parse_constraints(s).unwrap().constraint
496    }
497
498    #[test]
499    fn subsets_and_compaction() {
500        assert!(is_subset_of(&c("^1.2"), &c("^1.0")));
501        assert!(!is_subset_of(&c("^1.0"), &c("^1.2")));
502        assert!(is_subset_of(&c("1.5.0"), &c("^1.0")));
503        assert!(!is_subset_of(&c("dev-main"), &c("^1.0")));
504        assert!(is_subset_of(&c("dev-main"), &c("*")));
505        assert!(have_intersections(&c("^1.0"), &c(">=1.5")));
506        assert!(!have_intersections(&c("^1.0"), &c("^2.0")));
507        let merged = compact_constraint(&Constraint::Multi {
508            constraints: vec![c("^1.0"), c("^1.5")],
509            conjunctive: false,
510        });
511        assert_eq!(merged.to_string(), "[>= 1.0.0.0-dev < 2.0.0.0-dev]");
512        let both = compact_constraint(&Constraint::Multi {
513            constraints: vec![c("^1.0"), c("^2.0")],
514            conjunctive: false,
515        });
516        assert_eq!(both.to_string(), "[>= 1.0.0.0-dev < 3.0.0.0-dev]");
517        let ne = compact_constraint(&Constraint::Multi {
518            constraints: vec![c(">=1.0"), c("!=1.5.0")],
519            conjunctive: true,
520        });
521        assert_eq!(ne.to_string(), "[>= 1.0.0.0-dev != 1.5.0.0]");
522    }
523}
vivacity_resolver/intervals.rs

vivacity_resolver/
intervals.rs
