diff options
Diffstat (limited to 'vendor/datafrog/examples')
| -rw-r--r-- | vendor/datafrog/examples/borrow_check.rs | 115 | ||||
| -rw-r--r-- | vendor/datafrog/examples/graspan1.rs | 62 |
2 files changed, 177 insertions, 0 deletions
diff --git a/vendor/datafrog/examples/borrow_check.rs b/vendor/datafrog/examples/borrow_check.rs new file mode 100644 index 000000000..8f2197aef --- /dev/null +++ b/vendor/datafrog/examples/borrow_check.rs @@ -0,0 +1,115 @@ +extern crate datafrog; +use datafrog::Iteration; + +type Region = u32; +type Borrow = u32; +type Point = u32; + +fn main() { + 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(Vec::new().into()); + region_live_at.insert(Vec::new().into()); + cfg_edge_p.insert(Vec::new().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, ®ion_live_at, |&(r1, q), &r2, &()| { + ((r2, q), r1) + }); + subset.from_join(&subset_2, ®ion_live_at, |&(r2, q), &r1, &()| (r1, r2, q)); + } + + subset_r1p.complete() + }; + + let _requires = { + // Create a new iteration context, ... + let mut iteration2 = Iteration::new(); + + // .. some variables, .. + let requires = iteration2.variable::<(Region, Borrow, Point)>("requires"); + requires.insert(Vec::new().into()); + + let requires_rp = iteration2.variable::<((Region, Point), Borrow)>("requires_rp"); + let requires_bp = iteration2.variable::<((Borrow, Point), Region)>("requires_bp"); + + let requires_1 = iteration2.variable::<(Point, (Borrow, Region))>("requires_1"); + let requires_2 = iteration2.variable::<((Region, Point), Borrow)>("requires_2"); + + let subset_r1p = iteration2.variable::<((Region, Point), Region)>("subset_r1p"); + subset_r1p.insert(subset); + + let killed = Vec::new().into(); + let region_live_at = iteration2.variable::<((Region, Point), ())>("region_live_at"); + let cfg_edge_p = iteration2.variable::<(Point, Point)>("cfg_edge_p"); + + // .. and then start iterating rules! + while iteration2.changed() { + 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)); + + // requires(R, B, Q) :- + // requires(R, B, P), + // !killed(B, P), + // cfg_edge(P, Q), + // (region_live_at(R, Q); universal_region(R)). + + requires_1.from_antijoin(&requires_bp, &killed, |&(b, p), &r| (p, (b, r))); + requires_2.from_join(&requires_1, &cfg_edge_p, |&_p, &(b, r), &q| ((r, q), b)); + requires.from_join(&requires_2, ®ion_live_at, |&(r, q), &b, &()| (r, b, q)); + } + + requires.complete() + }; + + // borrow_live_at(B, P) :- requires(R, B, P), region_live_at(R, P) + + // borrow_live_at(B, P) :- requires(R, B, P), universal_region(R). +} diff --git a/vendor/datafrog/examples/graspan1.rs b/vendor/datafrog/examples/graspan1.rs new file mode 100644 index 000000000..31225b11d --- /dev/null +++ b/vendor/datafrog/examples/graspan1.rs @@ -0,0 +1,62 @@ +extern crate datafrog; +use datafrog::Iteration; + +fn main() { + let timer = ::std::time::Instant::now(); + + // Make space for input data. + let mut nodes = Vec::new(); + let mut edges = Vec::new(); + + // Read input data from a handy file. + use std::fs::File; + use std::io::{BufRead, BufReader}; + + let filename = std::env::args().nth(1).unwrap(); + let file = BufReader::new(File::open(filename).unwrap()); + for readline in file.lines() { + let line = readline.expect("read error"); + if !line.is_empty() && !line.starts_with('#') { + let mut elts = line[..].split_whitespace(); + let src: u32 = elts.next().unwrap().parse().expect("malformed src"); + let dst: u32 = elts.next().unwrap().parse().expect("malformed dst"); + let typ: &str = elts.next().unwrap(); + match typ { + "n" => { + nodes.push((dst, src)); + } + "e" => { + edges.push((src, dst)); + } + unk => panic!("unknown type: {}", unk), + } + } + } + + println!("{:?}\tData loaded", timer.elapsed()); + + // Create a new iteration context, ... + let mut iteration = Iteration::new(); + + // .. some variables, .. + let variable1 = iteration.variable::<(u32, u32)>("nodes"); + let variable2 = iteration.variable::<(u32, u32)>("edges"); + + // .. load them with some initial values, .. + variable1.insert(nodes.into()); + variable2.insert(edges.into()); + + // .. and then start iterating rules! + while iteration.changed() { + // N(a,c) <- N(a,b), E(b,c) + variable1.from_join(&variable1, &variable2, |_b, &a, &c| (c, a)); + } + + let reachable = variable1.complete(); + + println!( + "{:?}\tComputation complete (nodes_final: {})", + timer.elapsed(), + reachable.len() + ); +} |