/
constraint_set.rs
148 lines (127 loc) · 4.98 KB
/
constraint_set.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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
use rustc::ty::RegionVid;
use rustc_data_structures::indexed_vec::{Idx, IndexVec};
use borrow_check::nll::type_check::Locations;
use std::fmt;
use std::cmp::Ordering;
use std::ops::Deref;
#[derive(Clone, Default)]
crate struct ConstraintSet {
constraints: IndexVec<ConstraintIndex, OutlivesConstraint>,
}
impl ConstraintSet {
pub fn push(&mut self, constraint: OutlivesConstraint) {
debug!(
"add_outlives({:?}: {:?} @ {:?})",
constraint.sup, constraint.sub, constraint.locations
);
if constraint.sup == constraint.sub {
// 'a: 'a is pretty uninteresting
return;
}
self.constraints.push(constraint);
}
/// Once all constraints have been added, `link()` is used to thread together the constraints
/// based on which would be affected when a particular region changes. See the next field of
/// `OutlivesContraint` for more details.
/// link returns a map that is needed later by `each_affected_by_dirty`.
pub fn link(&mut self, len: usize) -> IndexVec<RegionVid, Option<ConstraintIndex>> {
let mut map = IndexVec::from_elem_n(None, len);
for (idx, constraint) in self.constraints.iter_enumerated_mut().rev() {
let mut head = &mut map[constraint.sub];
debug_assert!(constraint.next.is_none());
constraint.next = *head;
*head = Some(idx);
}
map
}
/// When a region R1 changes, we need to reprocess all constraints R2: R1 to take into account
/// any new elements that R1 now has. This method will quickly enumerate all such constraints
/// (that is, constraints where R1 is in the "subregion" position).
/// To use it, invoke with `map[R1]` where map is the map returned by `link`;
/// the callback op will be invoked for each affected constraint.
pub fn each_affected_by_dirty(
&self,
mut opt_dep_idx: Option<ConstraintIndex>,
mut op: impl FnMut(ConstraintIndex),
) {
while let Some(dep_idx) = opt_dep_idx {
op(dep_idx);
opt_dep_idx = self.constraints[dep_idx].next;
}
}
}
impl Deref for ConstraintSet {
type Target = IndexVec<ConstraintIndex, OutlivesConstraint>;
fn deref(&self) -> &Self::Target { &self.constraints }
}
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct OutlivesConstraint {
// NB. The ordering here is not significant for correctness, but
// it is for convenience. Before we dump the constraints in the
// debugging logs, we sort them, and we'd like the "super region"
// to be first, etc. (In particular, span should remain last.)
/// The region SUP must outlive SUB...
pub sup: RegionVid,
/// Region that must be outlived.
pub sub: RegionVid,
/// Later on, we thread the constraints onto a linked list
/// grouped by their `sub` field. So if you had:
///
/// Index | Constraint | Next Field
/// ----- | ---------- | ----------
/// 0 | `'a: 'b` | Some(2)
/// 1 | `'b: 'c` | None
/// 2 | `'c: 'b` | None
pub next: Option<ConstraintIndex>,
/// Where did this constraint arise?
pub locations: Locations,
}
impl fmt::Debug for OutlivesConstraint {
fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
write!(
formatter,
"({:?}: {:?}) due to {:?}",
self.sup, self.sub, self.locations
)
}
}
/// Constraints that are considered interesting can be categorized to
/// determine why they are interesting.
#[derive(Debug, Eq, PartialEq)]
crate enum ConstraintCategory {
Assignment,
CallArgument,
Cast,
Other,
}
impl Ord for ConstraintCategory {
fn cmp(&self, other: &Self) -> Ordering {
if self == other {
return Ordering::Equal;
}
match (self, other) {
(ConstraintCategory::Assignment, _) => Ordering::Greater,
(_, ConstraintCategory::Assignment) => Ordering::Less,
(ConstraintCategory::CallArgument, _) => Ordering::Greater,
(_, ConstraintCategory::CallArgument) => Ordering::Less,
(ConstraintCategory::Cast, _) => Ordering::Greater,
(_, ConstraintCategory::Cast) => Ordering::Less,
(ConstraintCategory::Other, _) => Ordering::Greater,
}
}
}
impl PartialOrd for ConstraintCategory {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
newtype_index!(ConstraintIndex { DEBUG_FORMAT = "ConstraintIndex({})" });