vendor/chalk-solve/src/coherence.rs

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