vivacity_resolver/
rule.rs

1//! Port of `Rule`, `GenericRule`, `Rule2Literals`, `MultiConflictRule` and
2//! `RuleSet` (docs/reference/resolver/). Rules live in the `RuleSet` and
3//! are referred to by their `ruleById`; literals are signed pool ids.
4
5use crate::constraint::Constraint;
6use crate::package::Link;
7use std::collections::HashMap;
8
9/// `Rule::RULE_*`.
10#[derive(Debug, Clone)]
11pub enum Reason {
12    /// `RULE_ROOT_REQUIRE`: `['packageName' => ..., 'constraint' => ...]`.
13    RootRequire {
14        package_name: String,
15        constraint: Constraint,
16        /// `$constraint->getPrettyString()`.
17        pretty: String,
18    },
19    /// `RULE_FIXED`: `['package' => ...]` (arena index).
20    Fixed { package: usize },
21    /// `RULE_PACKAGE_CONFLICT`: the link.
22    PackageConflict(Link),
23    /// `RULE_PACKAGE_REQUIRES`: the link.
24    PackageRequires(Link),
25    /// `RULE_PACKAGE_SAME_NAME`: the replaced name.
26    PackageSameName(String),
27    /// `RULE_LEARNED`: index into `learnedPool`.
28    Learned(usize),
29    /// `RULE_PACKAGE_ALIAS`: the alias (arena index).
30    PackageAlias { alias: usize },
31    /// `RULE_PACKAGE_INVERSE_ALIAS`: the aliased package (arena index).
32    PackageInverseAlias { package: usize },
33    /// `RULE_LOCKED_FILTER_LIST_REMOVED`.
34    LockedFilterListRemoved { package: usize },
35}
36
37impl Reason {
38    pub fn code(&self) -> u8 {
39        match self {
40            Reason::RootRequire { .. } => 2,
41            Reason::Fixed { .. } => 3,
42            Reason::PackageConflict(_) => 6,
43            Reason::PackageRequires(_) => 7,
44            Reason::PackageSameName(_) => 10,
45            Reason::Learned(_) => 12,
46            Reason::PackageAlias { .. } => 13,
47            Reason::PackageInverseAlias { .. } => 14,
48            Reason::LockedFilterListRemoved { .. } => 15,
49        }
50    }
51}
52
53/// PHP class of the rule: determines the hash (hence deduplication) and
54/// the shape of the watches.
55#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
56pub enum RuleKind {
57    Generic,
58    TwoLiterals,
59    MultiConflict,
60}
61
62/// `RuleSet::TYPE_*`.
63#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
64pub enum RuleType {
65    Package = 0,
66    Request = 1,
67    Learned = 4,
68}
69
70#[derive(Debug, Clone)]
71pub struct Rule {
72    pub kind: RuleKind,
73    /// Sorted ascending (`sort($literals)`), except Rule2Literals: [min, max],
74    /// which is the same thing.
75    pub literals: Vec<i64>,
76    pub reason: Reason,
77    /// None = 255: never added to the RuleSet (duplicate learned rule, still
78    /// used as a reason and as a watch node).
79    pub rule_type: Option<RuleType>,
80    pub disabled: bool,
81}
82
83impl Rule {
84    /// `new GenericRule($literals, ...)`.
85    pub fn generic(mut literals: Vec<i64>, reason: Reason) -> Rule {
86        literals.sort_unstable();
87        Rule {
88            kind: RuleKind::Generic,
89            literals,
90            reason,
91            rule_type: None,
92            disabled: false,
93        }
94    }
95
96    /// `new Rule2Literals($l1, $l2, ...)`.
97    pub fn two_literals(l1: i64, l2: i64, reason: Reason) -> Rule {
98        Rule {
99            kind: RuleKind::TwoLiterals,
100            literals: if l1 < l2 { vec![l1, l2] } else { vec![l2, l1] },
101            reason,
102            rule_type: None,
103            disabled: false,
104        }
105    }
106
107    /// `new MultiConflictRule($literals, ...)` (at least 3 literals).
108    pub fn multi_conflict(mut literals: Vec<i64>, reason: Reason) -> Rule {
109        literals.sort_unstable();
110        Rule {
111            kind: RuleKind::MultiConflict,
112            literals,
113            reason,
114            rule_type: None,
115            disabled: false,
116        }
117    }
118
119    pub fn is_assertion(&self) -> bool {
120        self.kind == RuleKind::Generic && self.literals.len() == 1
121    }
122
123    pub fn is_enabled(&self) -> bool {
124        !self.disabled
125    }
126
127    /// `getRequiredPackage`.
128    pub fn required_package<'a>(&'a self, arena: &'a [crate::package::Package]) -> Option<&'a str> {
129        match &self.reason {
130            Reason::RootRequire { package_name, .. } => Some(package_name),
131            Reason::Fixed { package } | Reason::LockedFilterListRemoved { package } => {
132                Some(&arena[*package].name)
133            }
134            Reason::PackageRequires(link) => Some(&link.target),
135            _ => None,
136        }
137    }
138}
139
140/// Deduplication key: the PHP hash (xxh3 of the literals for GenericRule,
141/// `"l1,l2"` for Rule2Literals, xxh3 prefixed with `c:` for
142/// MultiConflictRule) followed by `equals`; equivalent to (class,
143/// literals), up to 32-bit collisions across classes.
144#[derive(Debug, Clone, PartialEq, Eq, Hash)]
145struct RuleKey {
146    kind: RuleKind,
147    literals: Vec<i64>,
148}
149
150/// `Composer\DependencyResolver\RuleSet`. `rules` is the storage of all
151/// rules (including those rejected by `add` as duplicates, which the solver
152/// keeps using); `rule_by_id` is `ruleById`.
153#[derive(Debug, Default)]
154pub struct RuleSet {
155    pub rules: Vec<Rule>,
156    /// `ruleById`: registered rules, in insertion order.
157    pub rule_by_id: Vec<usize>,
158    /// `rules[$type]`: rules by type, in insertion order.
159    by_type: [Vec<usize>; 3],
160    keys: HashMap<RuleKey, usize>,
161}
162
163impl RuleSet {
164    pub fn new() -> RuleSet {
165        RuleSet::default()
166    }
167
168    fn slot(rule_type: RuleType) -> usize {
169        match rule_type {
170            RuleType::Package => 0,
171            RuleType::Request => 1,
172            RuleType::Learned => 2,
173        }
174    }
175
176    /// `add`: the rule is stored; it is registered (type set, `ruleById`)
177    /// only if no identical rule exists. Returns (storage index,
178    /// registered?).
179    pub fn add(&mut self, mut rule: Rule, rule_type: RuleType) -> (usize, bool) {
180        let key = RuleKey {
181            kind: rule.kind,
182            literals: rule.literals.clone(),
183        };
184        let id = self.rules.len();
185        if self.keys.contains_key(&key) {
186            self.rules.push(rule);
187            return (id, false);
188        }
189        rule.rule_type = Some(rule_type);
190        self.rules.push(rule);
191        self.rule_by_id.push(id);
192        self.by_type[Self::slot(rule_type)].push(id);
193        self.keys.insert(key, id);
194        (id, true)
195    }
196
197    /// `count()`: registered rules.
198    pub fn len(&self) -> usize {
199        self.rule_by_id.len()
200    }
201
202    pub fn is_empty(&self) -> bool {
203        self.rule_by_id.is_empty()
204    }
205
206    /// `getIteratorFor($type)`: ids of one type, in order.
207    pub fn ids_of_type(&self, rule_type: RuleType) -> &[usize] {
208        &self.by_type[Self::slot(rule_type)]
209    }
210
211    /// `getIterator()`: PACKAGE then REQUEST then LEARNED (sorted types).
212    pub fn ids_in_iterator_order(&self) -> Vec<usize> {
213        let mut out = Vec::with_capacity(self.rules.len());
214        for slot in &self.by_type {
215            out.extend(slot.iter().copied());
216        }
217        out
218    }
219}
vivacity_resolver/rule.rs

vivacity_resolver/
rule.rs
