vendor/polonius-engine/src/output/location_insensitive.rs

   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.
   4 //
   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.
  10
  11 use datafrog::{Iteration, Relation, RelationLeaper};
  12 use std::time::Instant;
  13
  14 use crate::facts::FactTypes;
  15 use crate::output::{Context, Output};
  16
  17 pub(super) fn compute<T: FactTypes>(
  18     ctx: &Context<'_, T>,
  19     result: &mut Output<T>,
  20 ) -> Relation<(T::Loan, T::Point)> {
  21     let timer = Instant::now();
  22
  23     let potential_errors = {
  24         // Static inputs
  25         let origin_live_on_entry = &ctx.origin_live_on_entry;
  26         let invalidates = &ctx.invalidates;
  27
  28         // Create a new iteration context, ...
  29         let mut iteration = Iteration::new();
  30
  31         // .. some variables, ..
  32         let subset = iteration.variable::<(T::Origin, T::Origin)>("subset");
  33         let requires = iteration.variable::<(T::Origin, T::Loan)>("requires");
  34
  35         let potential_errors = iteration.variable::<(T::Loan, T::Point)>("potential_errors");
  36
  37         // load initial facts.
  38
  39         // subset(origin1, origin2) :- outlives(origin1, origin2, _point)
  40         subset.extend(
  41             ctx.outlives
  42                 .iter()
  43                 .map(|&(origin1, origin2, _point)| (origin1, origin2)),
  44         );
  45
  46         // requires(origin, loan) :- borrow_region(origin, loan, _point).
  47         requires.extend(
  48             ctx.borrow_region
  49                 .iter()
  50                 .map(|&(origin, loan, _point)| (origin, loan)),
  51         );
  52
  53         // .. and then start iterating rules!
  54         while iteration.changed() {
  55             // requires(origin2, loan) :-
  56             //   requires(origin1, loan),
  57             //   subset(origin1, origin2).
  58             //
  59             // Note: Since `subset` is effectively a static input, this join can be ported to
  60             // a leapjoin. Doing so, however, was 7% slower on `clap`.
  61             requires.from_join(&requires, &subset, |&_origin1, &loan, &origin2| {
  62                 (origin2, loan)
  63             });
  64
  65             // borrow_live_at(loan, point) :-
  66             //   requires(origin, loan),
  67             //   origin_live_on_entry(origin, point)
  68             //
  69             // potential_errors(loan, point) :-
  70             //   invalidates(loan, point),
  71             //   borrow_live_at(loan, point).
  72             //
  73             // Note: we don't need to materialize `borrow_live_at` here
  74             // so we can inline it in the `potential_errors` relation.
  75             //
  76             potential_errors.from_leapjoin(
  77                 &requires,
  78                 (
  79                     origin_live_on_entry.extend_with(|&(origin, _loan)| origin),
  80                     invalidates.extend_with(|&(_origin, loan)| loan),
  81                 ),
  82                 |&(_origin, loan), &point| (loan, point),
  83             );
  84         }
  85
  86         if result.dump_enabled {
  87             let subset = subset.complete();
  88             for &(origin1, origin2) in subset.iter() {
  89                 result
  90                     .subset_anywhere
  91                     .entry(origin1)
  92                     .or_default()
  93                     .insert(origin2);
  94             }
  95
  96             let requires = requires.complete();
  97             for &(origin, loan) in requires.iter() {
  98                 result
  99                     .restricts_anywhere
 100                     .entry(origin)
 101                     .or_default()
 102                     .insert(loan);
 103             }
 104         }
 105
 106         potential_errors.complete()
 107     };
 108
 109     info!(
 110         "potential_errors is complete: {} tuples, {:?}",
 111         potential_errors.len(),
 112         timer.elapsed()
 113     );
 114
 115     potential_errors
 116 }