ccs2/
search.rs

1use std::{collections::VecDeque, fmt::Display, path::Path};
2
3use crate::{
4    ast::{
5        self, Constraint, ImportResolver, JoinedBy, Key, PersistentStr, Property, PropertyValue,
6        Specificity,
7    },
8    dag::{self, Node, NodeType},
9    load_helper,
10    tracer::ClonablePropertyTracer,
11};
12
13// TODO: Make thread-safety opt-in? These should be the only changes...
14// rpds docs say Rc -> Arc doubles runtime of some operations.
15type PersistentQueue<T> = rpds::QueueSync<T>;
16type PersistentSet<T> = rpds::HashTrieSetSync<T>;
17type PersistentMap<K, V> = rpds::HashTrieMapSync<K, V>;
18type Dag = std::sync::Arc<crate::dag::Dag>;
19
20/// Represents a problem finding a property in the current context
21///
22/// See [`SearchResult`]
23#[derive(thiserror::Error, Debug, Clone)]
24pub enum SearchError {
25    #[error("Failed to find property '{name}' {context}")]
26    MissingPropertyError {
27        name: String,
28        context: DisplayContext,
29    },
30    #[error("Property '{name}' has no values {context}")]
31    EmptyPropertyError {
32        name: String,
33        context: DisplayContext,
34    },
35    #[error("Found {count} properties matching '{name}' {context}")]
36    AmbiguousPropertyError {
37        count: usize,
38        name: String,
39        context: DisplayContext,
40    },
41}
42
43pub type SearchResult<T> = std::result::Result<T, SearchError>;
44
45/// A public-facing [`Key`] converter, which allows creating a valid `Key` for constraints
46///
47/// Currently we only support standalone `Key`s, or key-value pairs (via 2-tuples).
48pub trait AsKey {
49    fn as_key(&self) -> Key;
50}
51
52impl AsKey for &str {
53    fn as_key(&self) -> Key {
54        Key::new_lit(self, [])
55    }
56}
57
58impl<T: AsRef<str>, U: AsRef<str>> AsKey for (T, U) {
59    fn as_key(&self) -> Key {
60        Key::new_lit(self.0.as_ref(), [self.1.as_ref().into()])
61    }
62}
63
64#[derive(Clone)]
65pub struct Context<Acc, Tracer> {
66    dag: Dag,
67    tracer: Tracer,
68    state: ContextState<Acc>,
69}
70impl<Acc: Accumulator, Tracer: ClonablePropertyTracer> Context<Acc, Tracer> {
71    pub fn load(
72        path: impl AsRef<Path>,
73        resolver: impl ImportResolver,
74        tracer: Tracer,
75    ) -> crate::CcsResult<Self> {
76        let content = load_helper::load(path)?;
77        Ok(Self::from_ccs_with(&content, resolver, tracer)?)
78    }
79
80    pub fn from_ccs_with(
81        ccs: impl AsRef<str>,
82        resolver: impl ImportResolver,
83        tracer: Tracer,
84    ) -> crate::AstResult<Self> {
85        let rules = ast::parse(ccs, resolver)?;
86        let mut tree = ast::RuleTreeNode::default();
87        rules.add_to(&mut tree);
88        let dag = std::sync::Arc::new(dag::Dag::build(tree));
89
90        Ok(Self {
91            dag,
92            tracer,
93            state: Default::default(),
94        }
95        .augment_all([], true))
96    }
97
98    pub fn augment(&self, key: impl AsKey) -> Self {
99        let key = key.as_key();
100        self.augment_all([key.clone()], false)
101    }
102
103    pub fn get_single_property(&self, name: impl AsRef<str>) -> SearchResult<PropertyValue> {
104        let name = name.as_ref().to_string();
105
106        let contenders = self.state.props.get(name.as_str());
107        let mut properties = match contenders {
108            Some(contenders) => contenders.values(),
109            None => {
110                let err = SearchError::MissingPropertyError {
111                    name,
112                    context: self.state.display_context(),
113                };
114                self.tracer.on_error(err.clone());
115                return Err(err);
116            }
117        };
118        if properties.len() == 0 {
119            let err = SearchError::EmptyPropertyError {
120                name,
121                context: self.state.display_context(),
122            };
123            self.tracer.on_error(err.clone());
124            Err(err)
125        } else if properties.len() > 1 {
126            let err = SearchError::AmbiguousPropertyError {
127                count: properties.len(),
128                name,
129                context: self.state.display_context(),
130            };
131            self.tracer.on_error(err.clone());
132            Err(err)
133        } else {
134            let matching = properties.next().unwrap();
135            self.tracer
136                .on_found(&name, matching, self.state.display_context());
137            Ok(matching.clone())
138        }
139    }
140
141    pub fn get_single_value(&self, prop: impl AsRef<str>) -> SearchResult<PersistentStr> {
142        Ok(self.get_single_property(prop)?.value.clone())
143    }
144
145    fn with_new_state(&self, state: ContextState<Acc>) -> Self {
146        Self {
147            dag: self.dag.clone(),
148            tracer: self.tracer.clone(),
149            state,
150        }
151    }
152
153    fn augment_all(
154        &self,
155        keys: impl IntoIterator<Item = Key>, // TODO: this causes an unnecessary Arc alloc
156        activate_root: bool,
157    ) -> Self {
158        let mut state = self.state.clone();
159
160        let mut keys = CurrentConstraints::from_iter(keys.into_iter().map(Into::into));
161        // Only add the initial keys to this context; don't want to track activations
162        for key in keys.iter().cloned() {
163            state.debug_context = state.debug_context.enqueue(key);
164        }
165
166        if activate_root {
167            let prop_node = self.dag.get_data(self.dag.prop_node);
168            let root_constraints = VecDeque::from_iter(prop_node.constraints.iter().cloned());
169            // TODO: This is messy and creates duplicate work
170            keys = root_constraints.into_iter().chain(keys).collect();
171            state = state.activate(&mut keys, &self.dag, self.dag.prop_node, None);
172        }
173        while let Some(constraint) = keys.pop_front() {
174            assert!(constraint.key.values.len() < 2);
175            let value = constraint.key.values.first().cloned();
176            state = state.match_step(&mut keys, &self.dag, &constraint.key.name, value.as_deref());
177        }
178        self.with_new_state(state)
179    }
180
181    pub fn get_debug_context(&self) -> DisplayContext {
182        self.state.display_context()
183    }
184
185    pub fn get_dag_stats(&self) -> dag::Stats {
186        self.dag.stats()
187    }
188
189    #[cfg(feature = "dot")]
190    pub fn dag_to_dot_str(&self) -> String {
191        use crate::dag::dot::*;
192        let digraph = dag_to_digraph(&self.dag, &self.state.tallies);
193        format!("{:?}", to_dot(&digraph))
194    }
195}
196
197pub trait Accumulator: Default + Clone + std::fmt::Debug {
198    fn accum(self, prop: PropertyValue, specificity: Specificity) -> Self;
199    fn values(&self) -> impl ExactSizeIterator<Item = &PropertyValue>;
200}
201
202// TODO really this should probably be a map from value to specificity, where only the highest specificity
203// for a given specific value/origin is retained
204#[allow(dead_code)] // Temporarily keeping this around, but don't really need it
205#[derive(Clone, Debug, Default)]
206struct SetAccumulator {
207    values: PersistentSet<(PropertyValue, Specificity)>,
208}
209impl Accumulator for SetAccumulator {
210    fn accum(self, prop: PropertyValue, specificity: Specificity) -> Self {
211        SetAccumulator {
212            values: self.values.insert((prop, specificity)),
213        }
214    }
215    fn values(&self) -> impl ExactSizeIterator<Item = &PropertyValue> {
216        self.values.iter().map(|(v, _)| v)
217    }
218}
219
220#[derive(Clone, Debug)]
221pub struct MaxAccumulator {
222    specificity: Specificity,
223    values: PersistentSet<PropertyValue>,
224}
225impl Accumulator for MaxAccumulator {
226    fn accum(self, prop: PropertyValue, specificity: Specificity) -> Self {
227        if specificity > self.specificity {
228            MaxAccumulator {
229                specificity,
230                values: PersistentSet::from_iter([prop]),
231            }
232        } else if specificity == self.specificity {
233            MaxAccumulator {
234                specificity: self.specificity,
235                values: self.values.insert(prop),
236            }
237        } else {
238            self
239        }
240    }
241    fn values(&self) -> impl ExactSizeIterator<Item = &PropertyValue> {
242        self.values.iter()
243    }
244}
245impl Default for MaxAccumulator {
246    fn default() -> Self {
247        Self {
248            specificity: Specificity::zero(),
249            values: Default::default(),
250        }
251    }
252}
253
254pub type Tallies = PersistentMap<Node, usize>;
255type CurrentConstraints = VecDeque<Constraint>;
256
257#[derive(Default, Clone, Debug)]
258struct ContextState<Acc> {
259    tallies: Tallies,
260    or_specificities: PersistentMap<Node, Specificity>,
261    props: PersistentMap<PersistentStr, Acc>,
262    poisoned: PersistentSet<Node>,
263    debug_context: PersistentQueue<Constraint>,
264}
265impl<Acc: Accumulator> ContextState<Acc> {
266    fn insert_or_specificity(&self, n: Node, specificity: Specificity) -> Self {
267        let mut new_state = self.clone();
268        new_state.or_specificities = new_state.or_specificities.insert(n, specificity);
269        new_state
270    }
271
272    // TODO: Replacement functions are very error-prone. Easy to forget to update the state
273    #[must_use]
274    fn with_tallies(&self, tallies: Tallies) -> Self {
275        let mut new_state = self.clone();
276        new_state.tallies = tallies;
277        new_state
278    }
279
280    #[must_use]
281    fn accum_tally(&self, g: &Dag, n: Node) -> (Self, bool) {
282        let mut count = *self.tallies.get(&n).unwrap_or(&g.get_data(n).tally_count);
283        if count > 0 {
284            count -= 1;
285            let tallies = self.tallies.insert(n, count);
286            let activated = count == 0;
287            return (self.with_tallies(tallies), activated);
288        }
289        (self.clone(), false)
290    }
291
292    #[must_use]
293    fn activate_and(
294        mut self,
295        g: &Dag,
296        n: Node,
297        _propagated_specificity: Option<Specificity>,
298    ) -> (Self, Option<Specificity>) {
299        let (state, zeroed) = self.accum_tally(g, n);
300        self = state;
301        if zeroed {
302            let n_data = g.get_data(n);
303            if let NodeType::And(specificity) = n_data.op {
304                (self, Some(specificity))
305            } else {
306                panic!("Attempted activate_and with an OR node: {n:?}, {n_data:?}");
307            }
308        } else {
309            (self, None)
310        }
311    }
312
313    #[must_use]
314    fn activate_or(
315        self,
316        _g: &Dag,
317        n: Node,
318        propagated_specificity: Option<Specificity>,
319    ) -> (Self, Option<Specificity>) {
320        let prev_spec = *self
321            .or_specificities
322            .get(&n)
323            .unwrap_or(&Specificity::zero());
324        if let Some(propagated_specificity) = propagated_specificity {
325            if propagated_specificity > prev_spec {
326                (
327                    self.insert_or_specificity(n, propagated_specificity),
328                    Some(propagated_specificity),
329                )
330            } else {
331                (self, None)
332            }
333        } else {
334            (self, Some(prev_spec))
335        }
336    }
337
338    #[must_use]
339    fn update_props(
340        mut self,
341        new_props: impl IntoIterator<Item = Property>,
342        activation_specificity: Specificity,
343    ) -> Self {
344        for Property(name, prop_val) in new_props {
345            let prop_vals = self.props.get(&name).unwrap_or(&Acc::default()).clone();
346            let prop_specificity =
347                Specificity::new(prop_val.override_level, 0, 0, 0) + activation_specificity;
348            self.props = self
349                .props
350                .insert(name, prop_vals.accum(prop_val, prop_specificity));
351        }
352        self
353    }
354
355    #[must_use]
356    fn activate(
357        mut self,
358        active_constraints: &mut CurrentConstraints,
359        g: &Dag,
360        n: Node,
361        propagated_specificity: Option<Specificity>,
362    ) -> Self {
363        let activator = if matches!(g.get_data(n).op, NodeType::And(..)) {
364            Self::activate_and
365        } else {
366            Self::activate_or
367        };
368        let (new_state, activation_specificity) = activator(self, g, n, propagated_specificity);
369        self = new_state;
370        if let Some(activation_specificity) = activation_specificity {
371            let n_data = g.get_data(n);
372            for constraint in &n_data.constraints {
373                active_constraints.push_back(constraint.clone());
374            }
375
376            self = self.update_props(n_data.props.clone(), activation_specificity);
377            for n in &n_data.children {
378                self = Self::activate(
379                    self,
380                    active_constraints,
381                    g,
382                    *n,
383                    Some(activation_specificity),
384                )
385            }
386            self
387        } else {
388            self
389        }
390    }
391
392    #[must_use]
393    fn poison(mut self, g: &Dag, n: Node) -> Self {
394        let mut fully_poisoned = false;
395        if matches!(g.get_data(n).op, NodeType::And(..)) {
396            // a bit of care is required here, since we build tally-one
397            // conjunction nodes for literals, even when they represent
398            // disjunctions of multiple values.
399            // TODO this is starting to feel a bit too cute and tricky,
400            // might be time to build those in a more obvious way and use
401            // a more explicit technique to ensure uniqueness of literal
402            // values in context.
403            // but anyway, because of that, and because we always activate
404            // prior to poisoning, we can avoid incorrectly poisoning a
405            // literal node just by checking to see whether it's already
406            // been fully activated. that's the only scenario in which this
407            // can happen, so it's sufficient to detect it.
408            if self.tallies.get(&n).is_some_and(|t| *t != 0) && !self.poisoned.contains(&n) {
409                fully_poisoned = true;
410            }
411        } else {
412            (self, fully_poisoned) = self.accum_tally(g, n);
413        }
414
415        if fully_poisoned {
416            self.poisoned = self.poisoned.insert(n);
417            for n in &g.get_data(n).children {
418                self = self.poison(g, *n);
419            }
420        }
421        self
422    }
423
424    #[must_use]
425    fn match_step(
426        mut self,
427        active_constraints: &mut CurrentConstraints,
428        g: &Dag,
429        key: &str,
430        value: Option<&str>,
431    ) -> Self {
432        if let Some(matcher) = g.children.get(key) {
433            if let Some(wildcard) = matcher.wildcard {
434                self = self.activate(active_constraints, g, wildcard, None);
435            }
436            if let Some(value) = value
437                && let Some(positive_values) = matcher.positive_values.get(value)
438            {
439                for node in positive_values {
440                    self = self.activate(active_constraints, g, *node, None);
441                }
442            }
443            // TODO negative matches here too
444            if !self.poisoned.is_empty() {
445                for (v2, nodes) in &matcher.positive_values {
446                    // TODO here, there's a question... if value is None, do
447                    // we insist that no value ever be asserted for key and
448                    // poison everything? or do we remain agnostic, with the
449                    // idea that key.value is still a monotonic refinement of
450                    // just key? for now we assume the former.
451                    if value != Some(v2) {
452                        for node in nodes {
453                            self = self.poison(g, *node);
454                        }
455                    }
456                }
457            }
458        }
459
460        self
461    }
462
463    fn display_context(&self) -> DisplayContext {
464        DisplayContext(self.debug_context.clone())
465    }
466}
467
468/// Contains the constraints which have been applied to the current context. Formats nicely for
469/// debugging and logging.
470#[derive(Clone)]
471pub struct DisplayContext(pub PersistentQueue<Constraint>);
472impl Display for DisplayContext {
473    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
474        write!(f, "in context: [ {} ]", self.0.iter().joined_by(" > "))
475    }
476}
477impl std::fmt::Debug for DisplayContext {
478    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
479        write!(f, "Context[{}]", self.0.iter().joined_by(", "))
480    }
481}
482
483#[cfg(test)]
484mod tests {
485    use super::*;
486    use crate::{ast::NullResolver, tracer::NullTracer};
487
488    impl Context<MaxAccumulator, NullTracer> {
489        pub fn from_ccs(ccs: impl AsRef<str>) -> crate::AstResult<Self> {
490            Self::from_ccs_with(ccs, NullResolver(), NullTracer {})
491        }
492    }
493
494    #[test]
495    fn get_single_value() {
496        let ctx = Context::from_ccs(
497            r#"
498                a = 1
499                a = 2
500
501                c = 4.3
502                d = "cannotcast"
503            "#,
504        )
505        .unwrap();
506
507        assert!(matches!(
508            ctx.get_single_value("a"),
509            Err(SearchError::AmbiguousPropertyError { count: 2, .. })
510        ));
511
512        assert!(matches!(
513            ctx.get_single_value("b"),
514            Err(SearchError::MissingPropertyError { .. })
515        ));
516
517        assert_eq!(&*ctx.get_single_value("c").unwrap(), "4.3");
518    }
519
520    #[test]
521    fn with_root_node() {
522        let context = Context::from_ccs(
523            r#"
524                a, f b e, c {
525                    c d {
526                        x = y
527                    }
528                    e f {
529                        foobar = abc
530                    }
531                }
532                a, c, b e f : baz = quux
533
534                x = outerx
535                baz = outerbaz
536                foobar = outerfoobar
537                noothers = val
538                
539                multi {
540                    x = failure
541                    level {
542                        x = success
543                    }
544                }
545
546                z.underconstraint {
547                    c = success
548                }
549                @constrain z.underconstraint
550                c = failure
551            "#,
552        )
553        .unwrap();
554
555        assert_eq!(&*context.get_single_value("baz").unwrap(), "outerbaz");
556
557        let in_a = context.augment("a");
558        assert_eq!(&*in_a.get_single_value("baz").unwrap(), "quux");
559        assert_eq!(&*context.get_single_value("x").unwrap(), "outerx");
560
561        let in_c = context.augment("c");
562        assert_eq!(&*in_c.get_single_value("x").unwrap(), "outerx");
563
564        let in_cd = in_c.augment("d");
565        assert_eq!(&*in_cd.get_single_value("x").unwrap(), "y");
566
567        assert_eq!(&*in_cd.get_single_value("noothers").unwrap(), "val");
568
569        assert_eq!(&*context.get_single_value("c").unwrap(), "success");
570
571        let lvl1 = context.augment("multi");
572        let lvl2 = lvl1.augment("level");
573
574        assert_eq!(&*lvl2.get_single_value("x").unwrap(), "success");
575    }
576}
577
578#[cfg(all(test, feature = "dot"))]
579mod dot_examples {
580    use super::*;
581    use crate::ast::macros::*;
582
583    #[test]
584    fn activations_to_dot_1() {
585        let ccs = r#"
586                a b c {
587                    x = 1
588                }
589                a b {
590                    y = 2
591                }
592                b c (e, f, g) {
593                    z = 3
594                }
595                b d (e, f) {
596                    w = 4
597                }
598                b {
599                    s = 5
600                }
601            "#;
602        let context = Context::from_ccs(ccs).unwrap();
603        let context = context.augment_all([key!("b"), key!("d")], false);
604        println!("{}", context.dag_to_dot_str());
605    }
606}
ccs2/search.rs

ccs2/
search.rs
