ugly.rs

use std::collections::{BTreeMap, BTreeSet, HashSet};
​
use crate::facts::{AllFacts, Loan, Point, Region};
use crate::output::Output;
​
use crate::intern::InternerTables;
​
use datafrog::{Iteration, Relation, Variable};
​
fn optional_map_into<T1: Ord, T2: Ord, F: Fn(&T1)->Option<T2>>(
    input: &Variable<T1>,
    output: &Variable<T2>,
    logic: F) {
​
    let mut results = Vec::new();
    let recent = input.recent.borrow();
    for tuple in recent.iter() {
        let derived = logic(tuple);
        if let Some(derived) = derived {
            results.push(derived);
        }        
    }
​
    output.insert(results.into());
}
​
#[inline(always)]
fn from_optional_map<Tuple: Ord, T2: Ord, F: Fn(&T2)->Option<Tuple>>(v: &Variable<Tuple>, input: &Variable<T2>, logic: F) {
    optional_map_into(input, v, logic)
}
​
// fn antijoin_into<Key: Ord, Val1: Ord, Val2: Ord, Result: Ord, F: Fn(&Key, &Val1)->Result>(
//     input1: &Variable<(Key, Val1)>,
//     input2: &Variable<(Key, Val2)>,
//     output: &Variable<Result>,
// logic: F) {
​
// }
​
pub(super) fn compute(dump_enabled: bool, mut all_facts: AllFacts, _intern: &InternerTables) -> Output {
    let all_points: BTreeSet<Point> = all_facts
        .cfg_edge
        .iter()
        .map(|&(p, _)| p)
        .chain(all_facts.cfg_edge.iter().map(|&(_, q)| q))
        .collect();
​
    for &r in &all_facts.universal_region {
        for &p in &all_points {
            all_facts.region_live_at.push((r, p));
        }
    }
​
    let mut result = Output::new(dump_enabled);
​
    let subset_ = {
        // Create a new iteration context, ...
        let mut iteration1 = Iteration::new();
​
        // .. some variables, ..
        let subset = iteration1.variable::<(Region, Region, Point)>("subset");
​
        // different indices for `subset`.
        let subset_r1p = iteration1.variable::<((Region, Point), Region)>("subset_r1p");
        let subset_r2p = iteration1.variable::<((Region, Point), Region)>("subset_r2p");
        let subset_p = iteration1.variable::<(Point, (Region, Region))>("subset_p");
​
        // temporaries as we perform a multi-way join.
        let subset_1 = iteration1.variable::<((Region, Point), Region)>("subset_1");
        let subset_2 = iteration1.variable::<((Region, Point), Region)>("subset_2");
​
        let region_live_at = iteration1.variable::<((Region, Point), ())>("region_live_at");
        let cfg_edge_p = iteration1.variable::<(Point, Point)>("cfg_edge_p");
​
        // load initial facts.
        subset.insert(all_facts.outlives.into());
        region_live_at.insert(Relation::from(all_facts.region_live_at.iter().map(|&(r, p)| ((r, p), ()))));
        cfg_edge_p.insert(all_facts.cfg_edge.clone().into());
​
        // .. and then start iterating rules!
        while iteration1.changed() {
​
            // remap fields to re-index by keys.
            subset_r1p.from_map(&subset, |&(r1,r2,p)| ((r1,p),r2));
            subset_r2p.from_map(&subset, |&(r1,r2,p)| ((r2,p),r1));
            subset_p.from_map(&subset, |&(r1,r2,p)| (p,(r1,r2)));
​
            // R0: subset(R1, R2, P) :- outlives(R1, R2, P).
            // Already loaded; outlives is static.
​
            // R1: subset(R1, R3, P) :-
            //   subset(R1, R2, P),
            //   subset(R2, R3, P).
            subset.from_join(&subset_r2p, &subset_r1p, |&(_r2,p),&r1,&r3| (r1,r3,p));
​
            // R2: subset(R1, R2, Q) :-
            //   subset(R1, R2, P),
            //   cfg_edge(P, Q),
            //   region_live_at(R1, Q),
            //   region_live_at(R2, Q).
​
            subset_1.from_join(&subset_p, &cfg_edge_p, |&_p, &(r1,r2), &q| ((r1,q),r2));
            subset_2.from_join(&subset_1, &region_live_at, |&(r1,q),&r2,&()| ((r2,q),r1));
            subset.from_join(&subset_2, &region_live_at, |&(r2,q),&r1,&()| (r1,r2,q));
​
        }
​
        subset.complete()
    };
​
    for (r1, r2, location) in &subset_.elements {
        result
            .subset
            .entry(*location)
            .or_insert(BTreeMap::new())
            .entry(*r1)
            .or_insert(BTreeSet::new())
            .insert(*r2);
        result.region_degrees.update_degrees(*r1, *r2, *location);
    }
​
    println!("subset is complete: {}", subset_.len());
​
    let requires = {
        // Create a new iteration context, ...
        let mut iteration2 = Iteration::new();
​
        // .. some variables, ..
        let requires = iteration2.variable::<(Region, Loan, Point)>("requires");
        requires.insert(all_facts.borrow_region.into());
​
        let subset = iteration2.variable::<(Region, Region, Point)>("subset");
        subset.insert(subset_);
​
        // some indexes
        let requires_rp = iteration2.variable::<((Region, Point), Loan)>("requires_rp");
        let requires_bp = iteration2.variable::<((Loan, Point), Region)>("requires_bp");
​
        let requires_1 = iteration2.variable::<(Point, (Loan, Region))>("requires_1");
        let requires_2 = iteration2.variable::<((Region, Point), Loan)>("requires_2");
​
        let subset_r1p = iteration2.variable::<((Region, Point), Region)>("subset_r1p");
        // subset_r1p.insert(subset);
​
        // let killed = all_facts.killed.into();
        // let killed = iteration2.variable::<((Loan, Point), ())>("killed");
        // let killed = Relation::from(all_facts.killed.iter().map(|&(l, p)| ((l, p), ())));
        
        let region_live_at = iteration2.variable::<((Region, Point), ())>("region_live_at");
        let cfg_edge_p = iteration2.variable::<(Point, Point)>("cfg_edge_p");
​
        // load initial facts.
        region_live_at.insert(Relation::from(all_facts.region_live_at.iter().map(|&(r, p)| ((r, p), ()))));
        cfg_edge_p.insert(all_facts.cfg_edge.into());
​
        // .. and then start iterating rules!
​
        let mut killed = HashSet::new();
        for &k in &all_facts.killed {
            killed.insert(k);
        }
​
        let mut _it = -1;
        while iteration2.changed() {
            _it += 1;
​
            // println!("iteration {}", it);
​
            subset_r1p.from_map(&subset, |&(r1,r2,p)| ((r1,p),r2));
            requires_rp.from_map(&requires, |&(r,b,p)| ((r,p),b));
            requires_bp.from_map(&requires, |&(r,b,p)| ((b,p),r));
​
            // requires(R, B, P) :- borrow_region(R, B, P).
            // Already loaded; borrow_region is static.
​
            // requires(R2, B, P) :-
            //   requires(R1, B, P),
            //   subset(R1, R2, P).
            requires.from_join(&requires_rp, &subset_r1p, |&(_r1, p), &b, &r2| (r2, b, p));
​
            // up to here, timely outputs the same thing
​
            
​
            // requires(R, B, Q) :-
            //   requires(R, B, P),
            //   !killed(B, P),
            //   cfg_edge(P, Q),
            //   region_live_at(R, Q).
​
            // requires_1.from_antijoin(&requires_bp, &killed, |&(b,p),&r| (p,(b,r)));
            
            // tmp:            
            // requires_1.from_map(&requires_bp, |&((b,p),r)| {
            //     println!("({}, {:?}), {:?}", intern.loans.rev_strings[p.index()], p, r);
            //     (p, (b, r))
            // });
​
            // the worst antijoin of all time
            from_optional_map(&requires_1, &requires_bp, |&((b,p),r)| {
                if killed.contains(&(b, p)) {
                    return None;
                }
​
                Some((p, (b, r)))
            });
​
​
            // println!("requires_1 len: {}", requires_1.tuples.borrow().len());
​
            // tmp:
            // requires.from_map(&requires_1, |&(p,(b,r))| (r, b, p));
​
            requires_2.from_join(&requires_1, &cfg_edge_p, |&_p, &(b,r), &q| ((r,q),b));
            
            // println!("requires_2 len: {}", requires_2.tuples.borrow().len());
​
            // tmp:
            // requires.from_map(&requires_2, |&((r,q),b)| (r, b, q));
​
            requires.from_join(&requires_2, &region_live_at, |&(r,p),&b,&()| (r,b,p));
            // println!("requires len: {}", requires.tuples.borrow().len());
​
            // for v in &iteration2.variables {
            //     v.dump();
            // }
​
            // println!("requires len: {}", requires.recent.borrow().len());
​
            // println!("");
        }
​
        requires.complete()
    };
​
    for (region, borrow, location) in &requires.elements {
        result
            .restricts
            .entry(*location)
            .or_insert(BTreeMap::new())
            .entry(*region)
            .or_insert(BTreeSet::new())
            .insert(*borrow);
    }
​
    println!("requires is complete: {}", requires.len());
​
    let borrow_live_at = {
        // Create a new iteration context, ...
        let mut iteration3 = Iteration::new();
​
        // .. some variables, ..
        let borrow_live_at = iteration3.variable::<(Loan, Point)>("borrow_live_at");
​
        let requires_ = iteration3.variable::<(Region, Loan, Point)>("requires");
        requires_.insert(requires);
​
        let requires_rp = iteration3.variable::<((Region, Point), Loan)>("requires_rp");
        let region_live_at = iteration3.variable::<((Region, Point), ())>("region_live_at");
​
        // load initial facts.
        region_live_at.insert(Relation::from(all_facts.region_live_at.iter().map(|&(r, p)| ((r, p), ()))));
​
        while iteration3.changed() {
            requires_rp.from_map(&requires_, |&(r,b,p)| ((r,p),b));
​
            // borrow_live_at(B, P) :- requires(R, B, P), region_live_at(R, P)
            borrow_live_at.from_join(&requires_rp, &region_live_at, |&(_r,p), &b, &()| (b, p));
        }
​
        borrow_live_at.complete()
    };
​
    println!("borrow_live_at is complete: {}", borrow_live_at.len());
​
    for (borrow, location) in &borrow_live_at.elements {
        result
            .borrow_live_at
            .entry(*location)
            .or_insert(Vec::new())
            .push(*borrow);
    }
​
    result
}