diff options
Diffstat (limited to 'vendor/polonius-engine/src/output/initialization.rs')
| -rw-r--r-- | vendor/polonius-engine/src/output/initialization.rs | 284 |
1 files changed, 284 insertions, 0 deletions
diff --git a/vendor/polonius-engine/src/output/initialization.rs b/vendor/polonius-engine/src/output/initialization.rs new file mode 100644 index 000000000..30409d965 --- /dev/null +++ b/vendor/polonius-engine/src/output/initialization.rs @@ -0,0 +1,284 @@ +use std::time::Instant; + +use crate::facts::FactTypes; +use crate::output::{InitializationContext, Output}; + +use datafrog::{Iteration, Relation, RelationLeaper}; + +// This represents the output of an intermediate elaboration step (step 1). +struct TransitivePaths<T: FactTypes> { + path_moved_at: Relation<(T::Path, T::Point)>, + path_assigned_at: Relation<(T::Path, T::Point)>, + path_accessed_at: Relation<(T::Path, T::Point)>, + path_begins_with_var: Relation<(T::Path, T::Variable)>, +} + +struct InitializationStatus<T: FactTypes> { + var_maybe_partly_initialized_on_exit: Relation<(T::Variable, T::Point)>, + move_error: Relation<(T::Path, T::Point)>, +} + +pub(super) struct InitializationResult<T: FactTypes>( + pub(super) Relation<(T::Variable, T::Point)>, + pub(super) Relation<(T::Path, T::Point)>, +); + +// Step 1: compute transitive closures of path operations. This would elaborate, +// for example, an access to x into an access to x.f, x.f.0, etc. We do this for: +// - access to a path +// - initialization of a path +// - moves of a path +// FIXME: transitive rooting in a variable (path_begins_with_var) +// Note that this step may not be entirely necessary! +fn compute_transitive_paths<T: FactTypes>( + child_path: Vec<(T::Path, T::Path)>, + path_assigned_at_base: Vec<(T::Path, T::Point)>, + path_moved_at_base: Vec<(T::Path, T::Point)>, + path_accessed_at_base: Vec<(T::Path, T::Point)>, + path_is_var: Vec<(T::Path, T::Variable)>, +) -> TransitivePaths<T> { + let mut iteration = Iteration::new(); + let child_path: Relation<(T::Path, T::Path)> = child_path.into(); + + let ancestor_path = iteration.variable::<(T::Path, T::Path)>("ancestor"); + + // These are the actual targets: + let path_moved_at = iteration.variable::<(T::Path, T::Point)>("path_moved_at"); + let path_assigned_at = iteration.variable::<(T::Path, T::Point)>("path_initialized_at"); + let path_accessed_at = iteration.variable::<(T::Path, T::Point)>("path_accessed_at"); + let path_begins_with_var = iteration.variable::<(T::Path, T::Variable)>("path_begins_with_var"); + + // ancestor_path(Parent, Child) :- child_path(Child, Parent). + ancestor_path.extend(child_path.iter().map(|&(child, parent)| (parent, child))); + + // path_moved_at(Path, Point) :- path_moved_at_base(Path, Point). + path_moved_at.insert(path_moved_at_base.into()); + + // path_assigned_at(Path, Point) :- path_assigned_at_base(Path, Point). + path_assigned_at.insert(path_assigned_at_base.into()); + + // path_accessed_at(Path, Point) :- path_accessed_at_base(Path, Point). + path_accessed_at.insert(path_accessed_at_base.into()); + + // path_begins_with_var(Path, Var) :- path_is_var(Path, Var). + path_begins_with_var.insert(path_is_var.into()); + + while iteration.changed() { + // ancestor_path(Grandparent, Child) :- + // ancestor_path(Parent, Child), + // child_path(Parent, Grandparent). + ancestor_path.from_join( + &ancestor_path, + &child_path, + |&_parent, &child, &grandparent| (grandparent, child), + ); + + // moving a path moves its children + // path_moved_at(Child, Point) :- + // path_moved_at(Parent, Point), + // ancestor_path(Parent, Child). + path_moved_at.from_join(&path_moved_at, &ancestor_path, |&_parent, &p, &child| { + (child, p) + }); + + // initialising x at p initialises all x:s children + // path_assigned_at(Child, point) :- + // path_assigned_at(Parent, point), + // ancestor_path(Parent, Child). + path_assigned_at.from_join(&path_assigned_at, &ancestor_path, |&_parent, &p, &child| { + (child, p) + }); + + // accessing x at p accesses all x:s children at p (actually, + // accesses should be maximally precise and this shouldn't happen?) + // path_accessed_at(Child, point) :- + // path_accessed_at(Parent, point), + // ancestor_path(Parent, Child). + path_accessed_at.from_join(&path_accessed_at, &ancestor_path, |&_parent, &p, &child| { + (child, p) + }); + + // path_begins_with_var(Child, Var) :- + // path_begins_with_var(Parent, Var) + // ancestor_path(Parent, Child). + path_begins_with_var.from_join( + &path_begins_with_var, + &ancestor_path, + |&_parent, &var, &child| (child, var), + ); + } + + TransitivePaths { + path_assigned_at: path_assigned_at.complete(), + path_moved_at: path_moved_at.complete(), + path_accessed_at: path_accessed_at.complete(), + path_begins_with_var: path_begins_with_var.complete(), + } +} + +// Step 2: Compute path initialization and deinitialization across the CFG. +fn compute_move_errors<T: FactTypes>( + ctx: TransitivePaths<T>, + cfg_edge: &Relation<(T::Point, T::Point)>, + output: &mut Output<T>, +) -> InitializationStatus<T> { + let mut iteration = Iteration::new(); + // Variables + + // var_maybe_partly_initialized_on_exit(var, point): Upon leaving `point`, + // `var` is partially initialized for some path through the CFG, that is + // there has been an initialization of var, and var has not been moved in + // all paths through the CFG. + let var_maybe_partly_initialized_on_exit = + iteration.variable::<(T::Variable, T::Point)>("var_maybe_partly_initialized_on_exit"); + + // path_maybe_initialized_on_exit(path, point): Upon leaving `point`, the + // move path `path` is initialized for some path through the CFG. + let path_maybe_initialized_on_exit = + iteration.variable::<(T::Path, T::Point)>("path_maybe_initialized_on_exit"); + + // path_maybe_uninitialized_on_exit(Path, Point): There exists at least one + // path through the CFG to Point such that `Path` has been moved out by the + // time we arrive at `Point` without it being re-initialized for sure. + let path_maybe_uninitialized_on_exit = + iteration.variable::<(T::Path, T::Point)>("path_maybe_uninitialized_on_exit"); + + // move_error(Path, Point): There is an access to `Path` at `Point`, but + // `Path` is potentially moved (or never initialised). + let move_error = iteration.variable::<(T::Path, T::Point)>("move_error"); + + // Initial propagation of static relations + + // path_maybe_initialized_on_exit(path, point) :- path_assigned_at(path, point). + path_maybe_initialized_on_exit.insert(ctx.path_assigned_at.clone()); + + // path_maybe_uninitialized_on_exit(path, point) :- path_moved_at(path, point). + path_maybe_uninitialized_on_exit.insert(ctx.path_moved_at.clone()); + + while iteration.changed() { + // path_maybe_initialized_on_exit(path, point2) :- + // path_maybe_initialized_on_exit(path, point1), + // cfg_edge(point1, point2), + // !path_moved_at(path, point2). + path_maybe_initialized_on_exit.from_leapjoin( + &path_maybe_initialized_on_exit, + ( + cfg_edge.extend_with(|&(_path, point1)| point1), + ctx.path_moved_at.extend_anti(|&(path, _point1)| path), + ), + |&(path, _point1), &point2| (path, point2), + ); + + // path_maybe_uninitialized_on_exit(path, point2) :- + // path_maybe_uninitialized_on_exit(path, point1), + // cfg_edge(point1, point2) + // !path_assigned_at(path, point2). + path_maybe_uninitialized_on_exit.from_leapjoin( + &path_maybe_uninitialized_on_exit, + ( + cfg_edge.extend_with(|&(_path, point1)| point1), + ctx.path_assigned_at.extend_anti(|&(path, _point1)| path), + ), + |&(path, _point1), &point2| (path, point2), + ); + + // var_maybe_partly_initialized_on_exit(var, point) :- + // path_maybe_initialized_on_exit(path, point). + // path_begins_with_var(path, var). + var_maybe_partly_initialized_on_exit.from_leapjoin( + &path_maybe_initialized_on_exit, + ctx.path_begins_with_var.extend_with(|&(path, _point)| path), + |&(_path, point), &var| (var, point), + ); + + // move_error(Path, TargetNode) :- + // path_maybe_uninitialized_on_exit(Path, SourceNode), + // cfg_edge(SourceNode, TargetNode), + // path_accessed_at(Path, TargetNode). + move_error.from_leapjoin( + &path_maybe_uninitialized_on_exit, + ( + cfg_edge.extend_with(|&(_path, source_node)| source_node), + ctx.path_accessed_at + .extend_with(|&(path, _source_node)| path), + ), + |&(path, _source_node), &target_node| (path, target_node), + ); + } + + if output.dump_enabled { + for &(path, location) in path_maybe_initialized_on_exit.complete().iter() { + output + .path_maybe_initialized_on_exit + .entry(location) + .or_default() + .push(path); + } + + for &(path, location) in path_maybe_uninitialized_on_exit.complete().iter() { + output + .path_maybe_uninitialized_on_exit + .entry(location) + .or_default() + .push(path); + } + } + + InitializationStatus { + var_maybe_partly_initialized_on_exit: var_maybe_partly_initialized_on_exit.complete(), + move_error: move_error.complete(), + } +} + +// Compute two things: +// +// - an over-approximation of the initialization of variables. This is used in +// the origin_live_on_entry computations to determine when a drop may happen; a +// definitely moved variable would not be actually dropped. +// - move errors. +// +// The process is split into two stages: +// +// 1. Compute the transitive closure of path accesses. That is, accessing `f.a` +// would access `f.a.b`, etc. +// 2. Use this to compute both paths that may be initialized and paths that may +// have been deinitialized, which in turn can be used to find move errors (an +// access to a path that may be deinitialized). +pub(super) fn compute<T: FactTypes>( + ctx: InitializationContext<T>, + cfg_edge: &Relation<(T::Point, T::Point)>, + output: &mut Output<T>, +) -> InitializationResult<T> { + let timer = Instant::now(); + + let transitive_paths = compute_transitive_paths::<T>( + ctx.child_path, + ctx.path_assigned_at_base, + ctx.path_moved_at_base, + ctx.path_accessed_at_base, + ctx.path_is_var, + ); + info!("initialization phase 1 completed: {:?}", timer.elapsed()); + + let InitializationStatus { + var_maybe_partly_initialized_on_exit, + move_error, + } = compute_move_errors::<T>(transitive_paths, cfg_edge, output); + info!( + "initialization phase 2: {} move errors in {:?}", + move_error.elements.len(), + timer.elapsed() + ); + + if output.dump_enabled { + for &(var, location) in var_maybe_partly_initialized_on_exit.iter() { + output + .var_maybe_partly_initialized_on_exit + .entry(location) + .or_default() + .push(var); + } + } + + InitializationResult(var_maybe_partly_initialized_on_exit, move_error) +} |