diff options
author | Joseph Frazer <joseph.frazer@ryansg.com> | 2020-03-11 11:20:26 -0400 |
---|---|---|
committer | Mike Gerwitz <mike.gerwitz@ryansg.com> | 2020-03-13 11:51:59 -0400 |
commit | 7e95394076d17394e08daf347f5b5f03018476a6 (patch) | |
tree | 01b9f58b066261c654e07a87742fe510e6877dca | |
parent | bc760387f6d37aa4532d2c1da58b0a5c3502e2de (diff) | |
download | tame-7e95394076d17394e08daf347f5b5f03018476a6.tar.gz tame-7e95394076d17394e08daf347f5b5f03018476a6.tar.bz2 tame-7e95394076d17394e08daf347f5b5f03018476a6.zip |
[DEV-7085] Create `SortableAsg` trait
Create a trait that sorts a graph into `Sections` that can then be used
as an IR. The `BaseAsg` should implement the trait using what was
originally in the POC.
-rw-r--r-- | tamer/src/ir/asg/base.rs | 193 | ||||
-rw-r--r-- | tamer/src/ir/asg/graph.rs | 9 | ||||
-rw-r--r-- | tamer/src/ir/asg/mod.rs | 2 | ||||
-rw-r--r-- | tamer/src/ld/poc.rs | 60 |
4 files changed, 205 insertions, 59 deletions
diff --git a/tamer/src/ir/asg/base.rs b/tamer/src/ir/asg/base.rs index 5cedf83..3139c04 100644 --- a/tamer/src/ir/asg/base.rs +++ b/tamer/src/ir/asg/base.rs @@ -19,15 +19,18 @@ //! Base concrete [`Asg`] implementation. -use super::graph::{Asg, AsgEdge, AsgError, AsgResult, Node, ObjectRef}; +use super::graph::{ + Asg, AsgEdge, AsgError, AsgResult, Node, ObjectRef, SortableAsg, +}; use super::ident::IdentKind; use super::object::{FragmentText, Object, Source}; +use super::Sections; use crate::sym::Symbol; use fixedbitset::FixedBitSet; use petgraph::graph::{ DiGraph, EdgeIndex, Graph, IndexType, Neighbors, NodeIndex, }; -use petgraph::visit::{GraphBase, IntoNeighbors, Visitable}; +use petgraph::visit::{DfsPostOrder, GraphBase, IntoNeighbors, Visitable}; /// Concrete ASG. /// @@ -302,6 +305,54 @@ where } } +impl<'a, 'i, Ix> SortableAsg<'a, 'i, Ix> for BaseAsg<'i, Ix> +where + Ix: IndexType, +{ + fn sort(&'a self, roots: &[ObjectRef<Ix>]) -> AsgResult<Sections<'a, 'i>> { + let mut deps: Sections = Sections::new(); + + // This is technically a topological sort, but functions have + // cycles. Once we have more symbol metadata, we can filter them out + // and actually invoke toposort. + let mut dfs = DfsPostOrder::empty(&self.graph); + + for index in roots { + dfs.stack.push((*index).into()); + } + + while let Some(index) = dfs.next(&self.graph) { + let ident = self.get(index).expect("missing node"); + + match ident { + Object::Ident(_, kind, _) + | Object::IdentFragment(_, kind, _, _) => match kind { + IdentKind::Meta => deps.meta.push_body(ident), + IdentKind::Worksheet => deps.worksheet.push_body(ident), + IdentKind::Param(_, _) => deps.params.push_body(ident), + IdentKind::Type(_) => deps.types.push_body(ident), + IdentKind::Func(_, _) => deps.funcs.push_body(ident), + IdentKind::MapHead + | IdentKind::Map + | IdentKind::MapTail => deps.map.push_body(ident), + IdentKind::RetMapHead + | IdentKind::RetMap + | IdentKind::RetMapTail => deps.retmap.push_body(ident), + _ => deps.rater.push_body(ident), + }, + _ => { + return Err(AsgError::UnexpectedNode(format!( + "{:?}", + ident + ))) + } + } + } + + Ok(deps) + } +} + // TODO: encapsulate Petgraph API (N.B. this is untested!) impl<'i, Ix> Visitable for BaseAsg<'i, Ix> where @@ -724,4 +775,142 @@ mod test { Ok(()) } + + macro_rules! add_sym { + ( $sut:expr, $s:ident, $expect:expr, $base:expr, $kind:expr ) => {{ + let sym_node = $sut.declare(&$s, $kind, Source::default())?; + + let (_, _) = $sut.add_dep_lookup($base, &$s); + + $expect.push($s); + + $sut.set_fragment(sym_node, FragmentText::from("foo"))?; + };}; + } + + macro_rules! assert_section_sym { + ( $iter:ident, $s:ident ) => {{ + let mut pos = 0; + for obj in $iter { + match obj { + Object::Ident(sym, _, _) + | Object::IdentFragment(sym, _, _, _) => { + assert_eq!($s.get(pos), Some(*sym)); + } + _ => panic!("unexpected object"), + } + + pos = pos + 1; + } + };}; + } + + #[test] + fn graph_sort() -> AsgResult<()> { + let mut sut = Sut::with_capacity(0, 0); + + let mut meta = vec![]; + let mut worksheet = vec![]; + let mut map = vec![]; + let mut retmap = vec![]; + + let base = Symbol::new_dummy(SymbolIndex::from_u32(1), "sym1"); + let base_node = + sut.declare(&base, IdentKind::Map, Source::default())?; + + let sym = Symbol::new_dummy(SymbolIndex::from_u32(2), "sym2"); + add_sym!(sut, sym, meta, &base, IdentKind::Meta); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(3), "sym3"); + add_sym!(sut, sym, worksheet, &base, IdentKind::Worksheet); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(4), "sym4"); + add_sym!(sut, sym, map, &base, IdentKind::MapHead); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(5), "sym5"); + add_sym!(sut, sym, map, &base, IdentKind::Map); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(6), "sym6"); + add_sym!(sut, sym, map, &base, IdentKind::MapTail); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(7), "sym7"); + add_sym!(sut, sym, retmap, &base, IdentKind::RetMapHead); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(8), "sym8"); + add_sym!(sut, sym, retmap, &base, IdentKind::RetMap); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(9), "sym9"); + add_sym!(sut, sym, retmap, &base, IdentKind::RetMapTail); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(10), "sym10"); + add_sym!(sut, sym, retmap, &base, IdentKind::RetMapTail); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(11), "sym11"); + add_sym!(sut, sym, retmap, &base, IdentKind::RetMap); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(12), "sym12"); + add_sym!(sut, sym, map, &base, IdentKind::MapHead); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(13), "sym13"); + add_sym!(sut, sym, map, &base, IdentKind::Map); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(14), "sym14"); + add_sym!(sut, sym, meta, &base, IdentKind::Meta); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(15), "sym15"); + add_sym!(sut, sym, worksheet, &base, IdentKind::Worksheet); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(16), "sym16"); + add_sym!(sut, sym, map, &base, IdentKind::MapTail); + let sym = Symbol::new_dummy(SymbolIndex::from_u32(17), "sym17"); + add_sym!(sut, sym, retmap, &base, IdentKind::RetMapHead); + + map.push(base); + + let sections = sut.sort(&vec![base_node])?; + + let iter = sections.meta.iter(); + assert_section_sym!(iter, meta); + let iter = sections.worksheet.iter(); + assert_section_sym!(iter, worksheet); + let iter = sections.map.iter(); + assert_section_sym!(iter, map); + let iter = sections.retmap.iter(); + assert_section_sym!(iter, retmap); + + Ok(()) + } + + #[test] + fn graph_sort_missing_node() -> AsgResult<()> { + let mut sut = Sut::with_capacity(0, 0); + + let sym = Symbol::new_dummy(SymbolIndex::from_u32(1), "sym"); + let dep = Symbol::new_dummy(SymbolIndex::from_u32(2), "dep"); + + let sym_node = sut.declare( + &sym, + IdentKind::Tpl, + Source { + virtual_: true, + ..Default::default() + }, + )?; + + sut.set_fragment(sym_node, FragmentText::from("foo"))?; + + let (_, _) = sut.add_dep_lookup(&sym, &dep); + + match sut.sort(&vec![sym_node]) { + Ok(_) => panic!("Unexpected success - dependency is not in graph"), + Err(AsgError::UnexpectedNode(_)) => (), + _ => { + panic!("Incorrect error result when dependency is not in graph") + } + } + + Ok(()) + } + + #[test] + fn graph_sort_no_roots() -> AsgResult<()> { + let mut sut = Sut::with_capacity(0, 0); + + let sym = Symbol::new_dummy(SymbolIndex::from_u32(1), "sym"); + let dep = Symbol::new_dummy(SymbolIndex::from_u32(2), "dep"); + + let (_, _) = sut.add_dep_lookup(&sym, &dep); + + let sections = sut.sort(&vec![])?; + + assert_eq!(Sections::new(), sections); + + Ok(()) + } } diff --git a/tamer/src/ir/asg/graph.rs b/tamer/src/ir/asg/graph.rs index 1f56e6c..75d041c 100644 --- a/tamer/src/ir/asg/graph.rs +++ b/tamer/src/ir/asg/graph.rs @@ -21,6 +21,7 @@ use super::ident::IdentKind; use super::object::{FragmentText, Object, Source}; +use super::Sections; use crate::sym::Symbol; use petgraph::graph::{IndexType, NodeIndex}; use std::result::Result; @@ -160,6 +161,14 @@ pub trait Asg<'i, Ix: IndexType> { ) -> (ObjectRef<Ix>, ObjectRef<Ix>); } +/// Sort a graph into different [`Sections`] +/// +/// Allow a graph to be partitioned into different [`Sections`] that can be +/// used as an `Intermediate Representation`. +pub trait SortableAsg<'a, 'i, Ix: IndexType> { + fn sort(&'a self, roots: &[ObjectRef<Ix>]) -> AsgResult<Sections<'a, 'i>>; +} + /// A [`Result`] with a hard-coded [`AsgError`] error type. /// /// This is the result of every [`Asg`] operation that could potentially diff --git a/tamer/src/ir/asg/mod.rs b/tamer/src/ir/asg/mod.rs index 13315d6..3f38fa2 100644 --- a/tamer/src/ir/asg/mod.rs +++ b/tamer/src/ir/asg/mod.rs @@ -187,7 +187,7 @@ mod ident; mod object; mod section; -pub use graph::{Asg, AsgError, AsgResult, ObjectRef}; +pub use graph::{Asg, AsgError, AsgResult, ObjectRef, SortableAsg}; pub use ident::{Dim, IdentKind}; pub use object::{FragmentText, Object, Source}; pub use section::{Section, SectionIterator, Sections}; diff --git a/tamer/src/ld/poc.rs b/tamer/src/ld/poc.rs index 3e6fb0a..829176a 100644 --- a/tamer/src/ld/poc.rs +++ b/tamer/src/ld/poc.rs @@ -22,20 +22,20 @@ use crate::global; use crate::ir::asg::{ - Asg, AsgError, DefaultAsg, IdentKind, Object, ObjectRef, Sections, Source, + Asg, DefaultAsg, IdentKind, Object, ObjectRef, Sections, SortableAsg, + Source, }; use crate::obj::xmle::writer::XmleWriter; use crate::obj::xmlo::reader::{XmloError, XmloEvent, XmloReader}; use crate::sym::{DefaultInterner, Interner, Symbol}; use fxhash::{FxHashMap, FxHashSet}; -use petgraph::visit::DfsPostOrder; use std::convert::TryInto; use std::error::Error; use std::fs; use std::io::BufReader; -type LinkerAsg<'i> = DefaultAsg<'i, global::ProgIdentSize>; type LinkerObjectRef = ObjectRef<global::ProgIdentSize>; +type LinkerAsg<'i> = DefaultAsg<'i, global::ProgIdentSize>; type LoadResult<'i> = Result<Option<(Option<&'i Symbol<'i>>, Option<String>)>, Box<dyn Error>>; @@ -78,7 +78,7 @@ pub fn main(package_path: &str, output: &str) -> Result<(), Box<dyn Error>> { .filter_map(|sym| depgraph.lookup(sym)), ); - let mut sorted = sort_deps(&depgraph, &roots)?; + let mut sorted = depgraph.sort(&roots)?; //println!("Sorted ({}): {:?}", sorted.len(), sorted); @@ -238,58 +238,6 @@ fn load_xmlo<'a, 'i, I: Interner<'i>>( } } -fn sort_deps<'a, 'i>( - depgraph: &'a LinkerAsg<'i>, - roots: &Vec<LinkerObjectRef>, -) -> Result<Sections<'a, 'i>, Box<dyn Error>> { - // @type=meta, @preproc:elig-class-yields - // @type={ret}map{,:head,:tail} - - let mut deps: Sections = Sections::new(); - - // This is technically a topological sort, but functions have - // cycles. Once we have more symbol metadata, we can filter them out - // and actually invoke toposort. - let mut dfs = DfsPostOrder::empty(&depgraph); - - //println!("discovered roots: {:?}", roots); - - // TODO: we'll be processing various roots separately - for index in roots { - dfs.stack.push((*index).into()); - } - - // TODO: can we encapsulate NodeIndex? - while let Some(index) = dfs.next(&depgraph) { - let ident = depgraph.get(index).expect("missing node"); - - match ident { - Object::Ident(_, kind, _) - | Object::IdentFragment(_, kind, _, _) => match kind { - IdentKind::Meta => deps.meta.push_body(ident), - IdentKind::Worksheet => deps.worksheet.push_body(ident), - IdentKind::Param(_, _) => deps.params.push_body(ident), - IdentKind::Type(_) => deps.types.push_body(ident), - IdentKind::Func(_, _) => deps.funcs.push_body(ident), - IdentKind::MapHead | IdentKind::Map | IdentKind::MapTail => { - deps.map.push_body(ident) - } - IdentKind::RetMapHead - | IdentKind::RetMap - | IdentKind::RetMapTail => deps.retmap.push_body(ident), - _ => deps.rater.push_body(ident), - }, - _ => { - return Err( - AsgError::UnexpectedNode(format!("{:?}", ident)).into() - ) - } - } - } - - Ok(deps) -} - fn get_interner_value<'a, 'i, I: Interner<'i>>( depgraph: &'a LinkerAsg<'i>, interner: &'i I, |