[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.

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,