1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use datafrog
::Relation
;
12 use rustc_hash
::{FxHashMap, FxHashSet}
;
14 use std
::collections
::{BTreeMap, BTreeSet}
;
16 use crate::facts
::{AllFacts, Atom, FactTypes}
;
21 mod location_insensitive
;
24 #[derive(Debug, Clone, Copy)]
26 /// Simple rules, but slower to execute
29 /// Optimized variant of the rules
32 /// Fast to compute, but imprecise: there can be false-positives
33 /// but no false-negatives. Tailored for quick "early return" situations.
36 /// Compares the `Naive` and `DatafrogOpt` variants to ensure they indeed
37 /// compute the same errors.
40 /// Combination of the fast `LocationInsensitive` pre-pass, followed by
41 /// the more expensive `DatafrogOpt` variant.
46 /// Optimized variants that ought to be equivalent to "naive"
47 pub const OPTIMIZED
: &'
static [Algorithm
] = &[Algorithm
::DatafrogOpt
];
49 pub fn variants() -> [&'
static str; 5] {
53 "LocationInsensitive",
60 impl ::std
::str::FromStr
for Algorithm
{
62 fn from_str(s
: &str) -> Result
<Self, Self::Err
> {
63 match s
.to_lowercase().as_ref() {
64 "naive" => Ok(Algorithm
::Naive
),
65 "datafrogopt" => Ok(Algorithm
::DatafrogOpt
),
66 "locationinsensitive" => Ok(Algorithm
::LocationInsensitive
),
67 "compare" => Ok(Algorithm
::Compare
),
68 "hybrid" => Ok(Algorithm
::Hybrid
),
69 _
=> Err(String
::from(
70 "valid values: Naive, DatafrogOpt, LocationInsensitive, Compare, Hybrid",
76 #[derive(Clone, Debug)]
77 pub struct Output
<T
: FactTypes
> {
78 pub errors
: FxHashMap
<T
::Point
, Vec
<T
::Loan
>>,
79 pub subset_errors
: FxHashMap
<T
::Point
, BTreeSet
<(T
::Origin
, T
::Origin
)>>,
80 pub move_errors
: FxHashMap
<T
::Point
, Vec
<T
::Path
>>,
82 pub dump_enabled
: bool
,
84 // these are just for debugging
85 pub borrow_live_at
: FxHashMap
<T
::Point
, Vec
<T
::Loan
>>,
86 pub restricts
: FxHashMap
<T
::Point
, BTreeMap
<T
::Origin
, BTreeSet
<T
::Loan
>>>,
87 pub restricts_anywhere
: FxHashMap
<T
::Origin
, BTreeSet
<T
::Loan
>>,
88 pub origin_live_on_entry
: FxHashMap
<T
::Point
, Vec
<T
::Origin
>>,
89 pub invalidates
: FxHashMap
<T
::Point
, Vec
<T
::Loan
>>,
90 pub subset
: FxHashMap
<T
::Point
, BTreeMap
<T
::Origin
, BTreeSet
<T
::Origin
>>>,
91 pub subset_anywhere
: FxHashMap
<T
::Origin
, BTreeSet
<T
::Origin
>>,
92 pub var_live_on_entry
: FxHashMap
<T
::Point
, Vec
<T
::Variable
>>,
93 pub var_drop_live_on_entry
: FxHashMap
<T
::Point
, Vec
<T
::Variable
>>,
94 pub path_maybe_initialized_on_exit
: FxHashMap
<T
::Point
, Vec
<T
::Path
>>,
95 pub known_contains
: FxHashMap
<T
::Origin
, BTreeSet
<T
::Loan
>>,
96 pub var_maybe_partly_initialized_on_exit
: FxHashMap
<T
::Point
, Vec
<T
::Variable
>>,
99 /// Subset of `AllFacts` dedicated to initialization
100 struct InitializationContext
<T
: FactTypes
> {
101 child_path
: Vec
<(T
::Path
, T
::Path
)>,
102 path_is_var
: Vec
<(T
::Path
, T
::Variable
)>,
103 path_assigned_at_base
: Vec
<(T
::Path
, T
::Point
)>,
104 path_moved_at_base
: Vec
<(T
::Path
, T
::Point
)>,
105 path_accessed_at_base
: Vec
<(T
::Path
, T
::Point
)>,
108 /// Subset of `AllFacts` dedicated to liveness
109 struct LivenessContext
<T
: FactTypes
> {
110 var_used_at
: Vec
<(T
::Variable
, T
::Point
)>,
111 var_defined_at
: Vec
<(T
::Variable
, T
::Point
)>,
112 var_dropped_at
: Vec
<(T
::Variable
, T
::Point
)>,
113 use_of_var_derefs_origin
: Vec
<(T
::Variable
, T
::Origin
)>,
114 drop_of_var_derefs_origin
: Vec
<(T
::Variable
, T
::Origin
)>,
117 /// Subset of `AllFacts` dedicated to borrow checking, and data ready to use by the variants
118 struct Context
<'ctx
, T
: FactTypes
> {
119 // `Relation`s used as static inputs, by all variants
120 origin_live_on_entry
: Relation
<(T
::Origin
, T
::Point
)>,
121 invalidates
: Relation
<(T
::Loan
, T
::Point
)>,
123 // static inputs used via `Variable`s, by all variants
124 outlives
: &'ctx Vec
<(T
::Origin
, T
::Origin
, T
::Point
)>,
125 borrow_region
: &'ctx Vec
<(T
::Origin
, T
::Loan
, T
::Point
)>,
127 // static inputs used by variants other than `LocationInsensitive`
128 cfg_node
: &'ctx BTreeSet
<T
::Point
>,
129 killed
: Relation
<(T
::Loan
, T
::Point
)>,
130 known_contains
: Relation
<(T
::Origin
, T
::Loan
)>,
131 placeholder_origin
: Relation
<(T
::Origin
, ())>,
132 placeholder_loan
: Relation
<(T
::Loan
, T
::Origin
)>,
134 // while this static input is unused by `LocationInsensitive`, it's depended on by initialization
135 // and liveness, so already computed by the time we get to borrowcking.
136 cfg_edge
: Relation
<(T
::Point
, T
::Point
)>,
138 // Partial results possibly used by other variants as input
139 potential_errors
: Option
<FxHashSet
<T
::Loan
>>,
142 impl<T
: FactTypes
> Output
<T
> {
143 /// All variants require the same initial preparations, done in multiple
144 /// successive steps:
145 /// - compute initialization data
146 /// - compute liveness
147 /// - prepare static inputs as shared `Relation`s
148 /// - in cases where `LocationInsensitive` variant is ran as a filtering pre-pass,
149 /// partial results can also be stored in the context, so that the following
150 /// variant can use it to prune its own input data
151 pub fn compute(all_facts
: &AllFacts
<T
>, algorithm
: Algorithm
, dump_enabled
: bool
) -> Self {
152 let mut result
= Output
::new(dump_enabled
);
154 // TODO: remove all the cloning thereafter, but that needs to be done in concert with rustc
156 let cfg_edge
= all_facts
.cfg_edge
.clone().into();
159 let initialization_ctx
= InitializationContext
{
160 child_path
: all_facts
.child_path
.clone(),
161 path_is_var
: all_facts
.path_is_var
.clone(),
162 path_assigned_at_base
: all_facts
.path_assigned_at_base
.clone(),
163 path_moved_at_base
: all_facts
.path_moved_at_base
.clone(),
164 path_accessed_at_base
: all_facts
.path_accessed_at_base
.clone(),
167 let initialization
::InitializationResult
::<T
>(
168 var_maybe_partly_initialized_on_exit
,
170 ) = initialization
::compute(initialization_ctx
, &cfg_edge
, &mut result
);
172 // FIXME: move errors should prevent the computation from continuing: we can't compute
173 // liveness and analyze loans accurately when there are move errors, and should early
175 for &(path
, location
) in move_errors
.iter() {
176 result
.move_errors
.entry(location
).or_default().push(path
);
180 let liveness_ctx
= LivenessContext
{
181 var_used_at
: all_facts
.var_used_at
.clone(),
182 var_defined_at
: all_facts
.var_defined_at
.clone(),
183 var_dropped_at
: all_facts
.var_dropped_at
.clone(),
184 use_of_var_derefs_origin
: all_facts
.use_of_var_derefs_origin
.clone(),
185 drop_of_var_derefs_origin
: all_facts
.drop_of_var_derefs_origin
.clone(),
188 let mut origin_live_on_entry
= liveness
::compute_live_origins(
191 var_maybe_partly_initialized_on_exit
,
195 let cfg_node
= cfg_edge
197 .map(|&(point1
, _
)| point1
)
198 .chain(cfg_edge
.iter().map(|&(_
, point2
)| point2
))
201 liveness
::make_universal_regions_live
::<T
>(
202 &mut origin_live_on_entry
,
204 &all_facts
.universal_region
,
207 // 3) Borrow checking
209 // Prepare data as datafrog relations, ready to join.
211 // Note: if rustc and polonius had more interaction, we could also delay or avoid
212 // generating some of the facts that are now always present here. For example,
213 // the `LocationInsensitive` variant doesn't use the `killed` or `invalidates`
214 // relations, so we could technically delay passing them from rustc, when
215 // using this or the `Hybrid` variant, to after the pre-pass has made sure
216 // we actually need to compute the full analysis. If these facts happened to
217 // be recorded in separate MIR walks, we might also avoid generating those facts.
219 let origin_live_on_entry
= origin_live_on_entry
.into();
221 // TODO: also flip the order of this relation's arguments in rustc
222 // from `invalidates(point, loan)` to `invalidates(loan, point)`.
223 // to avoid this allocation.
224 let invalidates
= Relation
::from_iter(
228 .map(|&(point
, loan
)| (loan
, point
)),
231 let killed
= all_facts
.killed
.clone().into();
233 // `known_subset` is a list of all the `'a: 'b` subset relations the user gave:
234 // it's not required to be transitive. `known_contains` is its transitive closure: a list
235 // of all the known placeholder loans that each of these placeholder origins contains.
236 // Given the `known_subset`s `'a: 'b` and `'b: 'c`: in the `known_contains` relation, `'a`
237 // will also contain `'c`'s placeholder loan.
238 let known_subset
= all_facts
.known_subset
.clone().into();
240 Output
::<T
>::compute_known_contains(&known_subset
, &all_facts
.placeholder
);
242 let placeholder_origin
: Relation
<_
> = Relation
::from_iter(
246 .map(|&origin
| (origin
, ())),
249 let placeholder_loan
= Relation
::from_iter(
253 .map(|&(origin
, loan
)| (loan
, origin
)),
256 // Ask the variants to compute errors in their own way
257 let mut ctx
= Context
{
258 origin_live_on_entry
,
262 outlives
: &all_facts
.outlives
,
263 borrow_region
: &all_facts
.borrow_region
,
268 potential_errors
: None
,
271 let errors
= match algorithm
{
272 Algorithm
::LocationInsensitive
=> location_insensitive
::compute(&ctx
, &mut result
),
273 Algorithm
::Naive
=> {
274 let (errors
, subset_errors
) = naive
::compute(&ctx
, &mut result
);
276 // Record illegal subset errors
277 for &(origin1
, origin2
, location
) in subset_errors
.iter() {
282 .insert((origin1
, origin2
));
287 Algorithm
::DatafrogOpt
=> datafrog_opt
::compute(&ctx
, &mut result
),
288 Algorithm
::Hybrid
=> {
289 // WIP: the `LocationInsensitive` variant doesn't compute any illegal subset
290 // relation errors. So using it as a quick pre-filter for illegal accesses
291 // errors will also end up skipping checking for subset errors.
293 // Execute the fast `LocationInsensitive` computation as a pre-pass:
294 // if it finds no possible errors, we don't need to do the more complex
295 // computations as they won't find errors either, and we can return early.
296 let potential_errors
= location_insensitive
::compute(&ctx
, &mut result
);
297 if potential_errors
.is_empty() {
300 // Record these potential errors as they can be used to limit the next
301 // variant's work to only these loans.
302 ctx
.potential_errors
=
303 Some(potential_errors
.iter().map(|&(loan
, _
)| loan
).collect());
305 datafrog_opt
::compute(&ctx
, &mut result
)
308 Algorithm
::Compare
=> {
309 // Ensure the `Naive` and `DatafrogOpt` errors are the same
310 let (naive_errors
, _
) = naive
::compute(&ctx
, &mut result
);
311 let opt_errors
= datafrog_opt
::compute(&ctx
, &mut result
);
313 // TODO: compare illegal subset relations errors as well here ?
315 let mut naive_errors_by_point
= FxHashMap
::default();
316 for &(loan
, point
) in naive_errors
.iter() {
317 naive_errors_by_point
319 .or_insert_with(Vec
::new
)
323 let mut opt_errors_by_point
= FxHashMap
::default();
324 for &(loan
, point
) in opt_errors
.iter() {
327 .or_insert_with(Vec
::new
)
331 if compare_errors(&naive_errors_by_point
, &opt_errors_by_point
) {
333 "The errors reported by the naive algorithm differ from ",
334 "the errors reported by the optimized algorithm. ",
335 "See the error log for details."
338 debug
!("Naive and optimized algorithms reported the same errors.");
345 // Record illegal access errors
346 for &(loan
, location
) in errors
.iter() {
347 result
.errors
.entry(location
).or_default().push(loan
);
350 // Record more debugging info when asked to do so
352 for &(origin
, location
) in ctx
.origin_live_on_entry
.iter() {
354 .origin_live_on_entry
360 for &(origin
, loan
) in ctx
.known_contains
.iter() {
372 /// Computes the transitive closure of the `known_subset` relation, so that we have
373 /// the full list of placeholder loans contained by the placeholder origins.
374 fn compute_known_contains(
375 known_subset
: &Relation
<(T
::Origin
, T
::Origin
)>,
376 placeholder
: &[(T
::Origin
, T
::Loan
)],
377 ) -> Relation
<(T
::Origin
, T
::Loan
)> {
378 let mut iteration
= datafrog
::Iteration
::new();
379 let known_contains
= iteration
.variable("known_contains");
381 // known_contains(Origin1, Loan1) :-
382 // placeholder(Origin1, Loan1).
383 known_contains
.extend(placeholder
.iter());
385 while iteration
.changed() {
386 // known_contains(Origin2, Loan1) :-
387 // known_contains(Origin1, Loan1),
388 // known_subset(Origin1, Origin2).
389 known_contains
.from_join(
392 |&_origin1
, &loan1
, &origin2
| (origin2
, loan1
),
396 known_contains
.complete()
399 fn new(dump_enabled
: bool
) -> Self {
401 errors
: FxHashMap
::default(),
402 subset_errors
: FxHashMap
::default(),
404 borrow_live_at
: FxHashMap
::default(),
405 restricts
: FxHashMap
::default(),
406 restricts_anywhere
: FxHashMap
::default(),
407 origin_live_on_entry
: FxHashMap
::default(),
408 invalidates
: FxHashMap
::default(),
409 move_errors
: FxHashMap
::default(),
410 subset
: FxHashMap
::default(),
411 subset_anywhere
: FxHashMap
::default(),
412 var_live_on_entry
: FxHashMap
::default(),
413 var_drop_live_on_entry
: FxHashMap
::default(),
414 path_maybe_initialized_on_exit
: FxHashMap
::default(),
415 var_maybe_partly_initialized_on_exit
: FxHashMap
::default(),
416 known_contains
: FxHashMap
::default(),
420 pub fn errors_at(&self, location
: T
::Point
) -> &[T
::Loan
] {
421 match self.errors
.get(&location
) {
427 pub fn borrows_in_scope_at(&self, location
: T
::Point
) -> &[T
::Loan
] {
428 match self.borrow_live_at
.get(&location
) {
437 ) -> Cow
<'_
, BTreeMap
<T
::Origin
, BTreeSet
<T
::Loan
>>> {
438 assert
!(self.dump_enabled
);
439 match self.restricts
.get(&location
) {
440 Some(map
) => Cow
::Borrowed(map
),
441 None
=> Cow
::Owned(BTreeMap
::default()),
445 pub fn regions_live_at(&self, location
: T
::Point
) -> &[T
::Origin
] {
446 assert
!(self.dump_enabled
);
447 match self.origin_live_on_entry
.get(&location
) {
456 ) -> Cow
<'_
, BTreeMap
<T
::Origin
, BTreeSet
<T
::Origin
>>> {
457 assert
!(self.dump_enabled
);
458 match self.subset
.get(&location
) {
459 Some(v
) => Cow
::Borrowed(v
),
460 None
=> Cow
::Owned(BTreeMap
::default()),
465 /// Compares errors reported by Naive implementation with the errors
466 /// reported by the optimized implementation.
467 fn compare_errors
<Loan
: Atom
, Point
: Atom
>(
468 all_naive_errors
: &FxHashMap
<Point
, Vec
<Loan
>>,
469 all_opt_errors
: &FxHashMap
<Point
, Vec
<Loan
>>,
471 let points
= all_naive_errors
.keys().chain(all_opt_errors
.keys());
473 let mut differ
= false;
474 for point
in points
{
475 let mut naive_errors
= all_naive_errors
.get(&point
).cloned().unwrap_or_default();
478 let mut opt_errors
= all_opt_errors
.get(&point
).cloned().unwrap_or_default();
481 for err
in naive_errors
.iter() {
482 if !opt_errors
.contains(err
) {
484 "Error {0:?} at {1:?} reported by naive, but not opt.",
491 for err
in opt_errors
.iter() {
492 if !naive_errors
.contains(err
) {
494 "Error {0:?} at {1:?} reported by opt, but not naive.",
509 impl Atom
for usize {
510 fn index(self) -> usize {
516 errors1
: &FxHashMap
<usize, Vec
<usize>>,
517 errors2
: &FxHashMap
<usize, Vec
<usize>>,
519 let diff1
= compare_errors(errors1
, errors2
);
520 let diff2
= compare_errors(errors2
, errors1
);
521 assert_eq
!(diff1
, diff2
);
526 fn test_compare_errors() {
527 let empty
= FxHashMap
::default();
528 assert_eq
!(false, compare(&empty
, &empty
));
529 let mut empty_vec
= FxHashMap
::default();
530 empty_vec
.insert(1, vec
![]);
531 empty_vec
.insert(2, vec
![]);
532 assert_eq
!(false, compare(&empty
, &empty_vec
));
534 let mut singleton1
= FxHashMap
::default();
535 singleton1
.insert(1, vec
![10]);
536 assert_eq
!(false, compare(&singleton1
, &singleton1
));
537 let mut singleton2
= FxHashMap
::default();
538 singleton2
.insert(1, vec
![11]);
539 assert_eq
!(false, compare(&singleton2
, &singleton2
));
540 let mut singleton3
= FxHashMap
::default();
541 singleton3
.insert(2, vec
![10]);
542 assert_eq
!(false, compare(&singleton3
, &singleton3
));
544 assert_eq
!(true, compare(&singleton1
, &singleton2
));
545 assert_eq
!(true, compare(&singleton2
, &singleton3
));
546 assert_eq
!(true, compare(&singleton1
, &singleton3
));
548 assert_eq
!(true, compare(&empty
, &singleton1
));
549 assert_eq
!(true, compare(&empty
, &singleton2
));
550 assert_eq
!(true, compare(&empty
, &singleton3
));
552 let mut errors1
= FxHashMap
::default();
553 errors1
.insert(1, vec
![11]);
554 errors1
.insert(2, vec
![10]);
555 assert_eq
!(false, compare(&errors1
, &errors1
));
556 assert_eq
!(true, compare(&errors1
, &singleton1
));
557 assert_eq
!(true, compare(&errors1
, &singleton2
));
558 assert_eq
!(true, compare(&errors1
, &singleton3
));