summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Wood <david@davidtw.co>2018-05-29 18:22:01 +0100
committerDavid Wood <david@davidtw.co>2018-05-29 18:22:01 +0100
commit4500fe004be6690971f2cab95f823d447d479699 (patch)
treec965d70f0c622baeb9c6b959c7ec6e28c39262f5
parentEnsure that depth first search does not get stuck in cycles. (diff)
downloadgrust-4500fe004be6690971f2cab95f823d447d479699.tar.gz
grust-4500fe004be6690971f2cab95f823d447d479699.tar.bz2
grust-4500fe004be6690971f2cab95f823d447d479699.tar.xz
Refactored DFS to be much cleaner. Added continue after noting that borrow is out of scope at location.
-rw-r--r--src/librustc_mir/dataflow/impls/borrows.rs126
1 files changed, 27 insertions, 99 deletions
diff --git a/src/librustc_mir/dataflow/impls/borrows.rs b/src/librustc_mir/dataflow/impls/borrows.rs
index 317b62b22d..af6eb517b1 100644
--- a/src/librustc_mir/dataflow/impls/borrows.rs
+++ b/src/librustc_mir/dataflow/impls/borrows.rs
@@ -15,13 +15,13 @@ use rustc;
15use rustc::hir; 15use rustc::hir;
16use rustc::hir::def_id::DefId; 16use rustc::hir::def_id::DefId;
17use rustc::middle::region; 17use rustc::middle::region;
18use rustc::mir::{self, Location, Place, Mir, TerminatorKind}; 18use rustc::mir::{self, Location, Place, Mir};
19use rustc::ty::TyCtxt; 19use rustc::ty::TyCtxt;
20use rustc::ty::{RegionKind, RegionVid}; 20use rustc::ty::{RegionKind, RegionVid};
21use rustc::ty::RegionKind::ReScope; 21use rustc::ty::RegionKind::ReScope;
22 22
23use rustc_data_structures::bitslice::BitwiseOperator; 23use rustc_data_structures::bitslice::BitwiseOperator;
24use rustc_data_structures::fx::FxHashMap; 24use rustc_data_structures::fx::{FxHashMap, FxHashSet};
25use rustc_data_structures::indexed_set::IdxSet; 25use rustc_data_structures::indexed_set::IdxSet;
26use rustc_data_structures::indexed_vec::IndexVec; 26use rustc_data_structures::indexed_vec::IndexVec;
27use rustc_data_structures::sync::Lrc; 27use rustc_data_structures::sync::Lrc;
@@ -60,104 +60,33 @@ fn precompute_borrows_out_of_scope<'a, 'tcx>(
60 borrow_index: BorrowIndex, 60 borrow_index: BorrowIndex,
61 borrow_region: RegionVid, 61 borrow_region: RegionVid,
62 location: Location, 62 location: Location,
63 visited_locations: &mut Vec<Location>
64) { 63) {
65 // Check if we have already visited this location and skip 64 // Keep track of places we've locations to check and locations that we have checked.
66 // it if we have - avoids infinite loops. 65 let mut stack = vec![ location ];
67 if visited_locations.contains(&location) { return; } 66 let mut visited = FxHashSet();
68 visited_locations.push(location.clone()); 67 visited.insert(location);
69 68
70 // Next, add the borrow index to the current location's vector if the region does 69 while let Some(location) = stack.pop() {
71 // not contain the point at that location (or create a new vector if required). 70 // If region does not contain a point at the location, then add to list and skip
72 if !regioncx.region_contains_point(borrow_region, location) { 71 // successor locations.
73 borrows_out_of_scope_at_location 72 if !regioncx.region_contains_point(borrow_region, location) {
74 .entry(location.clone()) 73 borrows_out_of_scope_at_location
75 .and_modify(|m| m.push(borrow_index)) 74 .entry(location)
76 .or_insert(vec![ borrow_index ]); 75 .or_insert(vec![])
77 } 76 .push(borrow_index);
77 continue;
78 }
78 79
79 let bb_data = &mir[location.block]; 80 // Add successors to locations to visit, if not visited before.
80 // If we are past the last statement, then check the terminator 81 let bb_data = &mir[location.block];
81 // to determine which location to proceed to.
82 if location.statement_index == bb_data.statements.len() {
83 if let Some(ref terminator) = bb_data.terminator { 82 if let Some(ref terminator) = bb_data.terminator {
84 match terminator.kind { 83 for block in terminator.successors() {
85 TerminatorKind::Goto { target } | 84 let loc = block.start_location();
86 TerminatorKind::FalseEdges { real_target: target, .. } | 85 if visited.insert(loc) {
87 TerminatorKind::FalseUnwind { real_target: target, .. } => { 86 stack.push(loc);
88 precompute_borrows_out_of_scope( 87 }
89 mir, regioncx, borrows_out_of_scope_at_location, 88 }
90 borrow_index, borrow_region, target.start_location(), 89 }
91 visited_locations
92 );
93 },
94 TerminatorKind::SwitchInt { ref targets, .. } => {
95 for block in targets {
96 precompute_borrows_out_of_scope(
97 mir, regioncx, borrows_out_of_scope_at_location,
98 borrow_index, borrow_region, block.start_location(),
99 visited_locations
100 );
101 }
102 },
103 TerminatorKind::Drop { target, unwind, .. } |
104 TerminatorKind::DropAndReplace { target, unwind, .. } => {
105 precompute_borrows_out_of_scope(
106 mir, regioncx, borrows_out_of_scope_at_location,
107 borrow_index, borrow_region, target.start_location(),
108 visited_locations
109 );
110
111 if let Some(unwind_block) = unwind {
112 precompute_borrows_out_of_scope(
113 mir, regioncx, borrows_out_of_scope_at_location,
114 borrow_index, borrow_region, unwind_block.start_location(),
115 visited_locations
116 );
117 }
118 },
119 TerminatorKind::Call { ref destination, cleanup, .. } => {
120 if let Some((_, block)) = destination {
121 precompute_borrows_out_of_scope(
122 mir, regioncx, borrows_out_of_scope_at_location,
123 borrow_index, borrow_region, block.start_location(),
124 visited_locations
125 );
126 }
127
128 if let Some(block) = cleanup {
129 precompute_borrows_out_of_scope(
130 mir, regioncx, borrows_out_of_scope_at_location,
131 borrow_index, borrow_region, block.start_location(),
132 visited_locations
133 );
134 }
135 },
136 TerminatorKind::Assert { target, cleanup, .. } |
137 TerminatorKind::Yield { resume: target, drop: cleanup, .. } => {
138 precompute_borrows_out_of_scope(
139 mir, regioncx, borrows_out_of_scope_at_location,
140 borrow_index, borrow_region, target.start_location(),
141 visited_locations
142 );
143
144 if let Some(block) = cleanup {
145 precompute_borrows_out_of_scope(
146 mir, regioncx, borrows_out_of_scope_at_location,
147 borrow_index, borrow_region, block.start_location(),
148 visited_locations
149 );
150 }
151 },
152 _ => {},
153 };
154 };
155 // If we're not on the last statement, then go to the next
156 // statement in this block.
157 } else {
158 precompute_borrows_out_of_scope(mir, regioncx, borrows_out_of_scope_at_location,
159 borrow_index, borrow_region,
160 location.successor_within_block(), visited_locations);
161 } 90 }
162} 91}
163 92
@@ -182,8 +111,7 @@ impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
182 111
183 precompute_borrows_out_of_scope(mir, &nonlexical_regioncx, 112 precompute_borrows_out_of_scope(mir, &nonlexical_regioncx,
184 &mut borrows_out_of_scope_at_location, 113 &mut borrows_out_of_scope_at_location,
185 borrow_index, borrow_region, location, 114 borrow_index, borrow_region, location);
186 &mut Vec::new());
187 } 115 }
188 116
189 Borrows { 117 Borrows {