Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJoseph Frazer <joseph.frazer@ryansg.com>2020-03-11 11:20:26 -0400
committerMike Gerwitz <mike.gerwitz@ryansg.com>2020-03-13 11:51:59 -0400
commit7e95394076d17394e08daf347f5b5f03018476a6 (patch)
tree01b9f58b066261c654e07a87742fe510e6877dca
parentbc760387f6d37aa4532d2c1da58b0a5c3502e2de (diff)
downloadtame-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.rs193
-rw-r--r--tamer/src/ir/asg/graph.rs9
-rw-r--r--tamer/src/ir/asg/mod.rs2
-rw-r--r--tamer/src/ld/poc.rs60
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,