forked from rust-lang/chalk
/
coherence.rs
112 lines (95 loc) · 3.65 KB
/
coherence.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
use petgraph::prelude::*;
use crate::ChalkSolveDatabase;
use chalk_ir::{self, Identifier, ImplId, TraitId};
use derive_new::new;
use failure::Fallible;
use std::collections::BTreeMap;
use std::sync::Arc;
pub mod orphan;
mod solve;
#[derive(new)]
pub struct CoherenceSolver<'db, DB>
where
DB: ChalkSolveDatabase,
{
db: &'db DB,
trait_id: TraitId,
}
#[derive(Fail, Debug)]
pub enum CoherenceError {
#[fail(display = "overlapping impls of trait {:?}", _0)]
OverlappingImpls(Identifier),
#[fail(display = "impl for trait {:?} violates the orphan rules", _0)]
FailedOrphanCheck(Identifier),
}
/// 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 {
map: BTreeMap<ImplId, SpecializationPriority>,
}
impl SpecializationPriorities {
/// Lookup the priority of an impl in the set (panics if impl is not in set).
pub fn priority(&self, impl_id: ImplId) -> 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, 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<'db, DB> CoherenceSolver<'db, DB>
where
DB: ChalkSolveDatabase,
{
pub fn specialization_priorities(&self) -> Fallible<Arc<SpecializationPriorities>> {
let mut result = SpecializationPriorities::default();
let forest = self.build_specialization_forest()?;
// Visit 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) -> Fallible<Graph<ImplId, ()>> {
// The forest is returned as a graph but built as a GraphMap; this is
// so that we never add multiple nodes with the same ItemId.
let mut forest = DiGraphMap::new();
// Find all specializations (implemented in coherence/solve)
// 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| {
forest.add_edge(less_special, more_special, ());
})?;
Ok(forest.into_graph())
}
// Recursively set priorities for those node and all of its children.
fn set_priorities(
&self,
idx: NodeIndex,
forest: &Graph<ImplId, ()>,
p: usize,
map: &mut SpecializationPriorities,
) {
// 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));
}
// Visit 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);
}
}
}