diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:18:25 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:18:25 +0000 |
commit | 5363f350887b1e5b5dd21a86f88c8af9d7fea6da (patch) | |
tree | 35ca005eb6e0e9a1ba3bb5dbc033209ad445dc17 /vendor/chalk-solve/src/coherence.rs | |
parent | Adding debian version 1.66.0+dfsg1-1. (diff) | |
download | rustc-5363f350887b1e5b5dd21a86f88c8af9d7fea6da.tar.xz rustc-5363f350887b1e5b5dd21a86f88c8af9d7fea6da.zip |
Merging upstream version 1.67.1+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/chalk-solve/src/coherence.rs')
-rw-r--r-- | vendor/chalk-solve/src/coherence.rs | 149 |
1 files changed, 149 insertions, 0 deletions
diff --git a/vendor/chalk-solve/src/coherence.rs b/vendor/chalk-solve/src/coherence.rs new file mode 100644 index 000000000..5528b9a21 --- /dev/null +++ b/vendor/chalk-solve/src/coherence.rs @@ -0,0 +1,149 @@ +use indexmap::IndexMap; +use petgraph::prelude::*; +use rustc_hash::FxHashMap; + +use crate::solve::Solver; +use crate::RustIrDatabase; +use chalk_ir::interner::Interner; +use chalk_ir::{self, ImplId, TraitId}; +use std::fmt; +use std::sync::Arc; + +pub mod orphan; +mod solve; + +pub struct CoherenceSolver<'a, I: Interner> { + db: &'a dyn RustIrDatabase<I>, + solver_builder: &'a dyn Fn() -> Box<dyn Solver<I>>, + trait_id: TraitId<I>, +} + +#[derive(Debug)] +pub enum CoherenceError<I: Interner> { + OverlappingImpls(TraitId<I>), + FailedOrphanCheck(TraitId<I>), +} + +impl<I: Interner> fmt::Display for CoherenceError<I> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + CoherenceError::OverlappingImpls(id) => { + write!(f, "overlapping impls of trait `{:?}`", id) + } + CoherenceError::FailedOrphanCheck(id) => { + write!(f, "impl for trait `{:?}` violates the orphan rules", id) + } + } + } +} + +impl<I: Interner> std::error::Error for CoherenceError<I> {} + +/// Stores the specialization priorities for a set of impls. +/// This basically encodes which impls specialize one another. +#[derive(Clone, Debug, Default, PartialEq, Eq)] +pub struct SpecializationPriorities<I: Interner> { + map: IndexMap<ImplId<I>, SpecializationPriority>, +} + +impl<I: Interner> SpecializationPriorities<I> { + pub fn new() -> Self { + Self { + map: IndexMap::new(), + } + } + + /// Lookup the priority of an impl in the set (panics if impl is not in set). + pub fn priority(&self, impl_id: ImplId<I>) -> SpecializationPriority { + self.map[&impl_id] + } + + /// Store the priority of an impl (used during construction). + /// Panics if we have already stored the priority for this impl. + fn insert(&mut self, impl_id: ImplId<I>, p: SpecializationPriority) { + let old_value = self.map.insert(impl_id, p); + assert!(old_value.is_none()); + } +} + +/// Impls with higher priority take precedence over impls with lower +/// priority (if both apply to the same types). Impls with equal +/// priority should never apply to the same set of input types. +#[derive(Copy, Clone, Default, PartialOrd, Ord, PartialEq, Eq, Debug)] +pub struct SpecializationPriority(usize); + +impl<'a, I> CoherenceSolver<'a, I> +where + I: Interner, +{ + /// Constructs a new `CoherenceSolver`. + pub fn new( + db: &'a dyn RustIrDatabase<I>, + solver_builder: &'a dyn Fn() -> Box<dyn Solver<I>>, + trait_id: TraitId<I>, + ) -> Self { + Self { + db, + solver_builder, + trait_id, + } + } + + pub fn specialization_priorities( + &self, + ) -> Result<Arc<SpecializationPriorities<I>>, CoherenceError<I>> { + let mut result = SpecializationPriorities::<I>::new(); + + let forest = self.build_specialization_forest()?; + + // TypeVisitable every root in the forest & set specialization + // priority for the tree that is the root of. + for root_idx in forest.externals(Direction::Incoming) { + self.set_priorities(root_idx, &forest, 0, &mut result); + } + + Ok(Arc::new(result)) + } + + // Build the forest of specialization relationships. + fn build_specialization_forest(&self) -> Result<Graph<ImplId<I>, ()>, CoherenceError<I>> { + let mut forest = DiGraph::new(); + let mut node_map = FxHashMap::default(); + + // Find all specializations. Record them in the forest + // by adding an edge from the less special to the more special. + self.visit_specializations_of_trait(|less_special, more_special| { + let less_special_node = *node_map + .entry(less_special) + .or_insert_with(|| forest.add_node(less_special)); + let more_special_node = *node_map + .entry(more_special) + .or_insert_with(|| forest.add_node(more_special)); + forest.update_edge(less_special_node, more_special_node, ()); + })?; + + Ok(forest) + } + + // Recursively set priorities for those node and all of its children. + fn set_priorities( + &self, + idx: NodeIndex, + forest: &Graph<ImplId<I>, ()>, + p: usize, + map: &mut SpecializationPriorities<I>, + ) { + // Get the impl datum recorded at this node and reset its priority + { + let impl_id = forest + .node_weight(idx) + .expect("index should be a valid index into graph"); + map.insert(*impl_id, SpecializationPriority(p)); + } + + // TypeVisitable all children of this node, setting their priority to this + 1 + for child_idx in forest.neighbors(idx) { + self.set_priorities(child_idx, forest, p + 1, map); + } + } +} |