1 files changed, 65 insertions, 0 deletions
diff --git a/src/chomp/cst.rs b/src/chomp/cst.rs
new file mode 100644
index 0000000..8e3163b
--- /dev/null
+++ b/src/chomp/cst.rs
@@ -0,0 +1,65 @@
+use std::rc::Rc;
+
+use super::Context;
+
+#[derive(Debug)]
+pub struct Name;
+
+#[derive(Debug)]
+pub enum Shape {
+    Epsilon,
+    Literal(String),
+    Variable(usize),
+    Cat(Vec<Rc<Shape>>),
+    Alt(Vec<Rc<Shape>>),
+    Fix(Rc<Shape>),
+    Call(Vec<Rc<Shape>>),
+    Lambda(Vec<Name>, Rc<Shape>),
+    Let(Name, Rc<Shape>, Rc<Shape>),
+}
+
+pub(crate) fn as_tree(ctx: &mut Context, shape: &Rc<Shape>) -> Rc<super::ast::Tree> {
+    fn lambda_as_tree(ctx: &mut Context, count: usize, inner: &Rc<Shape>) -> Rc<super::ast::Tree> {
+        if count == 0 {
+            ctx.as_tree(inner)
+        } else {
+            ctx.new_lambda(|ctx| lambda_as_tree(ctx, count - 1, inner))
+        }
+    }
+
+    match shape.as_ref() {
+        Shape::Epsilon => ctx.tree_interner.epsilon(),
+        Shape::Literal(l) => ctx.tree_interner.literal(l.to_owned()),
+        Shape::Variable(idx) => ctx.lookup_tree_variable(*idx),
+        Shape::Cat(v) => {
+            let epsilon = ctx.tree_interner.epsilon();
+            v.into_iter().fold(epsilon, |front, back| {
+                let back = ctx.as_tree(back);
+                ctx.tree_interner.cat(front, back)
+            })
+        }
+        Shape::Alt(v) => {
+            let bottom = ctx.tree_interner.bottom();
+            v.into_iter().fold(bottom, |left, right| {
+                let right = ctx.as_tree(right);
+                ctx.tree_interner.alt(left, right)
+            })
+        }
+        Shape::Fix(inner) => {
+            let inner = ctx.as_tree(inner);
+            ctx.tree_interner.fix(inner)
+        }
+        Shape::Call(v) => {
+            let identity = ctx.tree_interner.identity();
+            v.into_iter().fold(identity, |fun, arg| {
+                let arg = ctx.as_tree(arg);
+                ctx.tree_interner.call(fun, arg)
+            })
+        }
+        Shape::Lambda(names, inner) => lambda_as_tree(ctx, names.len(), inner),
+        Shape::Let(_, bind, inner) => {
+            let bind = ctx.as_tree(bind);
+            ctx.new_let(bind, |ctx| ctx.as_tree(inner))
+        }
+    }
+}