-
-
Save dylanede/63d95a146bef23d6066f46c2ab4e1228 to your computer and use it in GitHub Desktop.
Why does this code below produce the output in output.txt?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#[macro_use] extern crate adapton; | |
use adapton::macros::*; | |
use adapton::engine::*; | |
use std::fmt::Debug; | |
use std::hash::Hash; | |
use std::cmp::Ordering; | |
#[derive(PartialEq, Eq, Hash, Clone, Debug)] | |
enum Node<Key, Value> { | |
Branch(Key, Art<Value>, Name, Art<Node<Key, Value>>, Name, Art<Node<Key, Value>>), | |
Leaf(Key, Art<Value>), | |
Empty | |
} | |
impl<Key, Value> Node<Key, Value> where Key : Ord + Clone + Debug + Hash + 'static, Value : Eq + Clone + Hash + Debug + 'static { | |
fn insert(self, name: Name, key: Key, value: Art<Value>) { | |
match self { | |
Node::Empty => { | |
cell!([Some(name)]? Node::Leaf(key, value)); | |
} | |
Node::Leaf(current_key, current_value) => { | |
let (l, r) = fork!(name.clone()); | |
let (l_n, r_n) = if current_key < key { | |
(cell!([Some(l.clone())]? Node::Empty), cell!([Some(r.clone())]? Node::Leaf(key, value))) | |
} else { | |
(cell!([Some(l.clone())]? Node::Leaf(key, value)), cell!([Some(r.clone())]? Node::Empty)) | |
}; | |
cell!([Some(name)]? Node::Branch(current_key, current_value, l, l_n, r, r_n)); | |
} | |
Node::Branch(current_key, current_value, l, l_n, r, r_n) => { | |
if current_key < key { | |
get!(r_n).insert(r, key, value); | |
} else { | |
get!(l_n).insert(l, key, value); | |
} | |
} | |
} | |
} | |
fn lookup(self, key: Key) -> Art<Option<Value>> { | |
match self { | |
Node::Empty => thunk!(None), | |
Node::Leaf(current_key, value) => { | |
println!("Comparing {:?} with leaf key {:?}", key, current_key); | |
if key == current_key { thunk!(Some(get!(value))) } else { thunk!(None) } | |
}, | |
Node::Branch(current_key, value, _, l, _, r) => { | |
println!("Comparing {:?} with branch key {:?}", key, current_key); | |
match key.cmp(¤t_key) { | |
Ordering::Equal => thunk!(Some(get!(value))), | |
Ordering::Less => { thunk!(get!(get!(l).lookup(key.clone()))) }, | |
Ordering::Greater => { thunk!(get!(get!(r).lookup(key.clone()))) } | |
} | |
} | |
} | |
} | |
} | |
#[derive(Clone)] | |
struct Tree<Key, Value> { | |
name: Name, | |
root: Art<Node<Key, Value>> | |
} | |
impl<Key, Value> Tree<Key, Value> where Key : Ord + Clone + Debug + Hash + 'static, Value : Eq + Clone + Hash + Debug + 'static { | |
fn new(name: Name) -> Tree<Key, Value> { | |
Tree { | |
name: name.clone(), | |
root: cell!([Some(name)]? Node::Empty) | |
} | |
} | |
fn insert(&self, key: Key, value: Art<Value>) { | |
get!(self.root).insert(self.name.clone(), key, value); | |
} | |
fn lookup(&self, key: Key) -> Art<Option<Value>> { | |
get!(self.root).lookup(key) | |
} | |
} | |
fn main() { | |
manage::init_dcg(); | |
let tree = Tree::new(name_of_str("foo")); | |
tree.insert(1, cell!("Ham")); | |
tree.insert(5, cell!("Spam")); | |
tree.insert(4, cell!("Eggs")); | |
tree.insert(3, cell!("Foo")); | |
tree.insert(0, cell!("Spam")); | |
let lookup_tree = tree.clone(); | |
let maybe_value = lookup_tree.lookup(2); | |
println!("{:?}", get!(maybe_value)); | |
println!("{:?}", get!(maybe_value)); | |
tree.insert(2, cell!("Bar")); | |
println!("{:?}", get!(maybe_value)); | |
println!("{:?}", get!(maybe_value)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Comparing 2 with branch key 1 | |
produce Loc { path:[], id:Usize(5) } | |
Comparing 2 with branch key 5 | |
produce Loc { path:[], id:Usize(6) } | |
Comparing 2 with branch key 4 | |
produce Loc { path:[], id:Usize(7) } | |
Comparing 2 with leaf key 3 | |
produce Loc { path:[], id:Usize(8) } | |
None | |
None | |
Comparing 2 with branch key 3 | |
produce Loc { path:[], id:Usize(10) } | |
Comparing 2 with leaf key 2 | |
produce Loc { path:[], id:Usize(11) } | |
Comparing 2 with branch key 4 | |
produce Loc { path:[], id:Usize(12) } | |
Comparing 2 with branch key 3 | |
produce Loc { path:[], id:Usize(13) } | |
Comparing 2 with leaf key 2 | |
produce Loc { path:[], id:Usize(14) } | |
Comparing 2 with branch key 5 | |
produce Loc { path:[], id:Usize(15) } | |
Comparing 2 with branch key 4 | |
produce Loc { path:[], id:Usize(16) } | |
Comparing 2 with branch key 3 | |
produce Loc { path:[], id:Usize(17) } | |
Comparing 2 with leaf key 2 | |
produce Loc { path:[], id:Usize(18) } | |
Some("Bar") | |
Some("Bar") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Cool experiment!
I suspect the issue could be that you aren't reusing any of the thunks you are creating. The
thunk!(...)
macro, with no arguments, uses a global counter to name the thunk, which probably isn't what you wanted or expected there.In general, whenever I'm trying to understand the behavior of Adapton on a small program, I use the "reflection" mechanism to trace the behavior of the Adapton engine. This will expose behavior about how thunks are identified, allocated and reused in the program. Unfortunately, I don't yet have a good set of docs for that feature of the engine, but here's one example of using it, to demonstrate another feature of the engine:
https://docs.rs/adapton/0/adapton/index.html#use-force_map-for-more-precise-dependencies
What's really useful for me is generating an HTML representation of both small and large examples, e.g., see the
--trace-html
flag for this example benchmark applicationIf you are able to collect this HTML output, then I can help you interpret it. It will show instances of this "trace" structure, which organizes the internal steps of the Adapton engine into a tree structure.