vendor/polonius-engine/src/output/naive.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 //! A version of the Naive datalog analysis using Datafrog.
  12
  13 use datafrog::{Iteration, Relation, RelationLeaper};
  14 use std::time::Instant;
  15
  16 use crate::facts::FactTypes;
  17 use crate::output::{Context, Output};
  18
  19 pub(super) fn compute<T: FactTypes>(
  20     ctx: &Context<'_, T>,
  21     result: &mut Output<T>,
  22 ) -> (
  23     Relation<(T::Loan, T::Point)>,
  24     Relation<(T::Origin, T::Origin, T::Point)>,
  25 ) {
  26     let timer = Instant::now();
  27
  28     let (errors, subset_errors) = {
  29         // Static inputs
  30         let origin_live_on_entry_rel = &ctx.origin_live_on_entry;
  31         let cfg_edge_rel = &ctx.cfg_edge;
  32         let cfg_node = ctx.cfg_node;
  33         let killed_rel = &ctx.killed;
  34         let known_contains = &ctx.known_contains;
  35         let placeholder_origin = &ctx.placeholder_origin;
  36         let placeholder_loan = &ctx.placeholder_loan;
  37
  38         // Create a new iteration context, ...
  39         let mut iteration = Iteration::new();
  40
  41         // .. some variables, ..
  42         let subset = iteration.variable::<(T::Origin, T::Origin, T::Point)>("subset");
  43         let requires = iteration.variable::<(T::Origin, T::Loan, T::Point)>("requires");
  44         let borrow_live_at = iteration.variable::<((T::Loan, T::Point), ())>("borrow_live_at");
  45
  46         // `invalidates` facts, stored ready for joins
  47         let invalidates = iteration.variable::<((T::Loan, T::Point), ())>("invalidates");
  48
  49         // different indices for `subset`.
  50         let subset_o1p = iteration.variable_indistinct("subset_o1p");
  51         let subset_o2p = iteration.variable_indistinct("subset_o2p");
  52
  53         // different index for `requires`.
  54         let requires_op = iteration.variable_indistinct("requires_op");
  55
  56         // we need `origin_live_on_entry` in both variable and relation forms.
  57         // (respectively, for the regular join and the leapjoin).
  58         let origin_live_on_entry_var =
  59             iteration.variable::<((T::Origin, T::Point), ())>("origin_live_on_entry");
  60
  61         // output relations: illegal accesses errors, and illegal subset relations errors
  62         let errors = iteration.variable("errors");
  63         let subset_errors = iteration.variable::<(T::Origin, T::Origin, T::Point)>("subset_errors");
  64
  65         // load initial facts.
  66         subset.extend(ctx.outlives.iter());
  67         requires.extend(ctx.borrow_region.iter());
  68         invalidates.extend(
  69             ctx.invalidates
  70                 .iter()
  71                 .map(|&(loan, point)| ((loan, point), ())),
  72         );
  73         origin_live_on_entry_var.extend(
  74             origin_live_on_entry_rel
  75                 .iter()
  76                 .map(|&(origin, point)| ((origin, point), ())),
  77         );
  78
  79         // Placeholder loans are contained by their placeholder origin at all points of the CFG.
  80         //
  81         // contains(Origin, Loan, Node) :-
  82         //   cfg_node(Node),
  83         //   placeholder(Origin, Loan).
  84         let mut placeholder_loans = Vec::with_capacity(placeholder_loan.len() * cfg_node.len());
  85         for &(loan, origin) in placeholder_loan.iter() {
  86             for &node in cfg_node.iter() {
  87                 placeholder_loans.push((origin, loan, node));
  88             }
  89         }
  90
  91         requires.extend(placeholder_loans);
  92
  93         // .. and then start iterating rules!
  94         while iteration.changed() {
  95             // Cleanup step: remove symmetries
  96             // - remove regions which are `subset`s of themselves
  97             //
  98             // FIXME: investigate whether is there a better way to do that without complicating
  99             // the rules too much, because it would also require temporary variables and
 100             // impact performance. Until then, the big reduction in tuples improves performance
 101             // a lot, even if we're potentially adding a small number of tuples
 102             // per round just to remove them in the next round.
 103             subset
 104                 .recent
 105                 .borrow_mut()
 106                 .elements
 107                 .retain(|&(origin1, origin2, _)| origin1 != origin2);
 108
 109             // remap fields to re-index by keys.
 110             subset_o1p.from_map(&subset, |&(origin1, origin2, point)| {
 111                 ((origin1, point), origin2)
 112             });
 113             subset_o2p.from_map(&subset, |&(origin1, origin2, point)| {
 114                 ((origin2, point), origin1)
 115             });
 116
 117             requires_op.from_map(&requires, |&(origin, loan, point)| ((origin, point), loan));
 118
 119             // subset(origin1, origin2, point) :- outlives(origin1, origin2, point).
 120             // Already loaded; outlives is static.
 121
 122             // subset(origin1, origin3, point) :-
 123             //   subset(origin1, origin2, point),
 124             //   subset(origin2, origin3, point).
 125             subset.from_join(
 126                 &subset_o2p,
 127                 &subset_o1p,
 128                 |&(_origin2, point), &origin1, &origin3| (origin1, origin3, point),
 129             );
 130
 131             // subset(origin1, origin2, point2) :-
 132             //   subset(origin1, origin2, point1),
 133             //   cfg_edge(point1, point2),
 134             //   origin_live_on_entry(origin1, point2),
 135             //   origin_live_on_entry(origin2, point2).
 136             subset.from_leapjoin(
 137                 &subset,
 138                 (
 139                     cfg_edge_rel.extend_with(|&(_origin1, _origin2, point1)| point1),
 140                     origin_live_on_entry_rel.extend_with(|&(origin1, _origin2, _point1)| origin1),
 141                     origin_live_on_entry_rel.extend_with(|&(_origin1, origin2, _point1)| origin2),
 142                 ),
 143                 |&(origin1, origin2, _point1), &point2| (origin1, origin2, point2),
 144             );
 145
 146             // requires(origin, loan, point) :- borrow_region(origin, loan, point).
 147             // Already loaded; borrow_region is static.
 148
 149             // requires(origin2, loan, point) :-
 150             //   requires(origin1, loan, point),
 151             //   subset(origin1, origin2, point).
 152             requires.from_join(
 153                 &requires_op,
 154                 &subset_o1p,
 155                 |&(_origin1, point), &loan, &origin2| (origin2, loan, point),
 156             );
 157
 158             // requires(origin, loan, point2) :-
 159             //   requires(origin, loan, point1),
 160             //   !killed(loan, point1),
 161             //   cfg_edge(point1, point2),
 162             //   origin_live_on_entry(origin, point2).
 163             requires.from_leapjoin(
 164                 &requires,
 165                 (
 166                     killed_rel.filter_anti(|&(_origin, loan, point1)| (loan, point1)),
 167                     cfg_edge_rel.extend_with(|&(_origin, _loan, point1)| point1),
 168                     origin_live_on_entry_rel.extend_with(|&(origin, _loan, _point1)| origin),
 169                 ),
 170                 |&(origin, loan, _point1), &point2| (origin, loan, point2),
 171             );
 172
 173             // borrow_live_at(loan, point) :-
 174             //   requires(origin, loan, point),
 175             //   origin_live_on_entry(origin, point).
 176             borrow_live_at.from_join(
 177                 &requires_op,
 178                 &origin_live_on_entry_var,
 179                 |&(_origin, point), &loan, _| ((loan, point), ()),
 180             );
 181
 182             // errors(loan, point) :-
 183             //   invalidates(loan, point),
 184             //   borrow_live_at(loan, point).
 185             errors.from_join(&invalidates, &borrow_live_at, |&(loan, point), _, _| {
 186                 (loan, point)
 187             });
 188
 189             // subset_errors(Origin1, Origin2, Point) :-
 190             //   requires(Origin2, Loan1, Point),
 191             //   placeholder(Origin2, _),
 192             //   placeholder(Origin1, Loan1),
 193             //   !known_contains(Origin2, Loan1).
 194             subset_errors.from_leapjoin(
 195                 &requires,
 196                 (
 197                     placeholder_origin.filter_with(|&(origin2, _loan1, _point)| (origin2, ())),
 198                     placeholder_loan.extend_with(|&(_origin2, loan1, _point)| loan1),
 199                     known_contains.filter_anti(|&(origin2, loan1, _point)| (origin2, loan1)),
 200                     // remove symmetries:
 201                     datafrog::ValueFilter::from(|&(origin2, _loan1, _point), &origin1| {
 202                         origin2 != origin1
 203                     }),
 204                 ),
 205                 |&(origin2, _loan1, point), &origin1| (origin1, origin2, point),
 206             );
 207         }
 208
 209         // Handle verbose output data
 210         if result.dump_enabled {
 211             let subset = subset.complete();
 212             assert!(
 213                 subset
 214                     .iter()
 215                     .filter(|&(origin1, origin2, _)| origin1 == origin2)
 216                     .count()
 217                     == 0,
 218                 "unwanted subset symmetries"
 219             );
 220             for &(origin1, origin2, location) in subset.iter() {
 221                 result
 222                     .subset
 223                     .entry(location)
 224                     .or_default()
 225                     .entry(origin1)
 226                     .or_default()
 227                     .insert(origin2);
 228             }
 229
 230             let requires = requires.complete();
 231             for &(origin, loan, location) in requires.iter() {
 232                 result
 233                     .restricts
 234                     .entry(location)
 235                     .or_default()
 236                     .entry(origin)
 237                     .or_default()
 238                     .insert(loan);
 239             }
 240
 241             let borrow_live_at = borrow_live_at.complete();
 242             for &((loan, location), _) in borrow_live_at.iter() {
 243                 result
 244                     .borrow_live_at
 245                     .entry(location)
 246                     .or_default()
 247                     .push(loan);
 248             }
 249         }
 250
 251         (errors.complete(), subset_errors.complete())
 252     };
 253
 254     info!(
 255         "analysis done: {} `errors` tuples, {} `subset_errors` tuples, {:?}",
 256         errors.len(),
 257         subset_errors.len(),
 258         timer.elapsed()
 259     );
 260
 261     (errors, subset_errors)
 262 }