chalk_solve/
coherence.rs

1use indexmap::IndexMap;
2use petgraph::prelude::*;
3use rustc_hash::FxHashMap;
4
5use crate::solve::Solver;
6use crate::RustIrDatabase;
7use chalk_ir::interner::Interner;
8use chalk_ir::{self, ImplId, TraitId};
9use std::fmt;
10use std::sync::Arc;
11
12pub mod orphan;
13mod solve;
14
15pub struct CoherenceSolver<'a, I: Interner> {
16    db: &'a dyn RustIrDatabase<I>,
17    solver_builder: &'a dyn Fn() -> Box<dyn Solver<I>>,
18    trait_id: TraitId<I>,
19}
20
21#[derive(Debug)]
22pub enum CoherenceError<I: Interner> {
23    OverlappingImpls(TraitId<I>),
24    FailedOrphanCheck(TraitId<I>),
25}
26
27impl<I: Interner> fmt::Display for CoherenceError<I> {
28    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
29        match self {
30            CoherenceError::OverlappingImpls(id) => {
31                write!(f, "overlapping impls of trait `{:?}`", id)
32            }
33            CoherenceError::FailedOrphanCheck(id) => {
34                write!(f, "impl for trait `{:?}` violates the orphan rules", id)
35            }
36        }
37    }
38}
39
40impl<I: Interner> std::error::Error for CoherenceError<I> {}
41
42/// Stores the specialization priorities for a set of impls.
43/// This basically encodes which impls specialize one another.
44#[derive(Clone, Debug, Default, PartialEq, Eq)]
45pub struct SpecializationPriorities<I: Interner> {
46    map: IndexMap<ImplId<I>, SpecializationPriority>,
47}
48
49impl<I: Interner> SpecializationPriorities<I> {
50    pub fn new() -> Self {
51        Self {
52            map: IndexMap::new(),
53        }
54    }
55
56    /// Lookup the priority of an impl in the set (panics if impl is not in set).
57    pub fn priority(&self, impl_id: ImplId<I>) -> SpecializationPriority {
58        self.map[&impl_id]
59    }
60
61    /// Store the priority of an impl (used during construction).
62    /// Panics if we have already stored the priority for this impl.
63    fn insert(&mut self, impl_id: ImplId<I>, p: SpecializationPriority) {
64        let old_value = self.map.insert(impl_id, p);
65        assert!(old_value.is_none());
66    }
67}
68
69/// Impls with higher priority take precedence over impls with lower
70/// priority (if both apply to the same types). Impls with equal
71/// priority should never apply to the same set of input types.
72#[derive(Copy, Clone, Default, PartialOrd, Ord, PartialEq, Eq, Debug)]
73pub struct SpecializationPriority(usize);
74
75impl<'a, I> CoherenceSolver<'a, I>
76where
77    I: Interner,
78{
79    /// Constructs a new `CoherenceSolver`.
80    pub fn new(
81        db: &'a dyn RustIrDatabase<I>,
82        solver_builder: &'a dyn Fn() -> Box<dyn Solver<I>>,
83        trait_id: TraitId<I>,
84    ) -> Self {
85        Self {
86            db,
87            solver_builder,
88            trait_id,
89        }
90    }
91
92    pub fn specialization_priorities(
93        &self,
94    ) -> Result<Arc<SpecializationPriorities<I>>, CoherenceError<I>> {
95        let mut result = SpecializationPriorities::<I>::new();
96
97        let forest = self.build_specialization_forest()?;
98
99        // TypeVisitable every root in the forest & set specialization
100        // priority for the tree that is the root of.
101        for root_idx in forest.externals(Direction::Incoming) {
102            self.set_priorities(root_idx, &forest, 0, &mut result);
103        }
104
105        Ok(Arc::new(result))
106    }
107
108    // Build the forest of specialization relationships.
109    fn build_specialization_forest(&self) -> Result<Graph<ImplId<I>, ()>, CoherenceError<I>> {
110        let mut forest = DiGraph::new();
111        let mut node_map = FxHashMap::default();
112
113        // Find all specializations. Record them in the forest
114        // by adding an edge from the less special to the more special.
115        self.visit_specializations_of_trait(|less_special, more_special| {
116            let less_special_node = *node_map
117                .entry(less_special)
118                .or_insert_with(|| forest.add_node(less_special));
119            let more_special_node = *node_map
120                .entry(more_special)
121                .or_insert_with(|| forest.add_node(more_special));
122            forest.update_edge(less_special_node, more_special_node, ());
123        })?;
124
125        Ok(forest)
126    }
127
128    // Recursively set priorities for those node and all of its children.
129    fn set_priorities(
130        &self,
131        idx: NodeIndex,
132        forest: &Graph<ImplId<I>, ()>,
133        p: usize,
134        map: &mut SpecializationPriorities<I>,
135    ) {
136        // Get the impl datum recorded at this node and reset its priority
137        {
138            let impl_id = forest
139                .node_weight(idx)
140                .expect("index should be a valid index into graph");
141            map.insert(*impl_id, SpecializationPriority(p));
142        }
143
144        // TypeVisitable all children of this node, setting their priority to this + 1
145        for child_idx in forest.neighbors(idx) {
146            self.set_priorities(child_idx, forest, p + 1, map);
147        }
148    }
149}
chalk_solve/coherence.rs

chalk_solve/
coherence.rs
