refactor; start adding expect tests

2 files changed, 1307 insertions, 0 deletions

diff --git a/src/eval/builtins.rs b/src/eval/builtins.rs
new file mode 100644
index 0000000..7820a8e
--- /dev/null
+++ b/src/eval/builtins.rs
@@ -0,0 +1,256 @@
+use std::{collections::HashMap, sync::LazyLock};
+
+use crate::{
+    ast,
+    eval::{Context, Error, Result, Value},
+    Wrap,
+};
+
+macro_rules! builtins {
+    ($($f:ident),* $(,)?) => {
+        pub static BUILTINS: LazyLock<HashMap<&'static str, Box<dyn Fn(&mut Context, &[ast::Expr]) -> Result + Sync + Send>>> =
+            LazyLock::new(|| {
+                [
+                    $((
+                        stringify!($f),
+                        Box::new($f) as Box<dyn Fn(&mut Context, &[ast::Expr]) -> Result + Sync + Send>,
+                    )),*
+                ]
+                    .into_iter()
+                    .collect()
+            });
+    }
+}
+
+builtins! {
+    print,
+    println,
+
+    // string
+    isupper,
+    islower,
+    substr,
+
+    // node
+    text,
+    parent,
+    children,
+    kind,
+
+    // list
+    length,
+    member,
+    push,
+    pop,
+    isempty,
+}
+
+fn print(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    for arg in args {
+        let val = ctx.eval_expr(arg)?;
+        let mut default_stream =Box::new(std::io::stdout()) as Box<dyn std::io::Write> ;
+        let stream = ctx
+            .output_stream
+            .as_mut()
+            .unwrap_or(&mut default_stream);
+        write!(stream, "{val}").unwrap();
+    }
+    Ok(Value::Unit)
+}
+
+fn println(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    print(ctx, args)?;
+    print(ctx, &[ast::Expr::Lit(ast::Literal::Str("\n".to_owned()))])
+}
+
+fn isupper(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    Ok(ctx
+        .eval_expr(&get_args::<1>(args)?[0])?
+        .as_str()?
+        .chars()
+        .all(|c| c.is_ascii_uppercase())
+        .into())
+}
+
+fn islower(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    Ok(ctx
+        .eval_expr(&get_args::<1>(args)?[0])?
+        .as_str()?
+        .chars()
+        .all(|c| c.is_ascii_lowercase())
+        .into())
+}
+
+fn substr(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    if let Ok([string, start, end]) = get_args::<3>(args) {
+        let v = ctx.eval_expr(string)?;
+        let s = v.as_str()?;
+        let start = ctx.eval_expr(start)?.as_int()?;
+        let end = ctx.eval_expr(end)?.as_int()?;
+        if start < 0 || start >= s.len() as i128 || end >= s.len() as i128 || start > end {
+            return Err(Error::InvalidStringSlice {
+                length: s.len(),
+                start,
+                end,
+            });
+        }
+        Ok(s[start as usize..end as usize].into())
+    } else {
+        let [string, end] = get_args::<2>(args)?;
+        let v = ctx.eval_expr(string)?;
+        let s = v.as_str()?;
+        let end = ctx.eval_expr(end)?.as_int()?;
+        if end >= s.len() as i128 {
+            return Err(Error::InvalidStringSlice {
+                length: s.len(),
+                start: 0,
+                end,
+            });
+        }
+        Ok(s[..end as usize].into())
+    }
+}
+
+fn text(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    let v = ctx.eval_expr(&get_args::<1>(args)?[0])?;
+    let id = v.as_node()?;
+    let node = ctx.get_node_by_id(id).unwrap();
+    let text = node
+        .utf8_text(ctx.input_src.as_ref().unwrap().as_bytes())
+        .unwrap();
+    text.to_owned().wrap(Value::String).wrap(Ok)
+}
+
+fn parent(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    let v = ctx.eval_expr(&get_args::<1>(args)?[0])?;
+    let id = v.as_node()?;
+    let node = ctx.get_node_by_id(id).unwrap();
+    let parent = node.parent();
+    parent
+        .map(|n| Value::Node(n.id()))
+        .ok_or(Error::NoParentNode(node))
+}
+
+fn children(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    let v = ctx.eval_expr(&get_args::<1>(args)?[0])?;
+    let id = v.as_node()?;
+    let node = ctx.get_node_by_id(id).unwrap();
+    let children = node
+        .children(&mut node.walk())
+        .map(|c| Value::Node(c.id()))
+        .collect::<Vec<_>>();
+    Ok(Value::List(children))
+}
+
+fn length(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    let v = ctx.eval_expr(&get_args::<1>(args)?[0])?;
+    let l = v.as_list()?;
+    (l.len() as i128).wrap(Value::Integer).wrap(Ok)
+}
+
+fn kind(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    let v = ctx.eval_expr(&get_args::<1>(args)?[0])?;
+    let id = v.as_node()?;
+    let node = ctx.get_node_by_id(id).unwrap();
+    node.kind().to_owned().wrap(Value::String).wrap(Ok)
+}
+
+fn member(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    let [list_expr, element_expr] = get_args::<2>(args)?;
+    let list = ctx.eval_expr(&list_expr)?;
+    let v = list.as_list()?;
+    let element = ctx.eval_expr(&element_expr)?;
+    v.iter()
+        .any(|item| item == &element)
+        .wrap(Value::Boolean)
+        .wrap(Ok)
+}
+
+fn push(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    let [lhs, rhs] = get_args::<2>(args)?;
+    let ast::Expr::Ident(ident) = lhs else {
+        return Err(Error::MalformedExpr(format!(
+            "malformed assigment, lhs: {:?}",
+            lhs
+        )));
+    };
+    let element = ctx.eval_expr(&rhs)?;
+    let variable = ctx.lookup_mut(ident)?;
+    variable.mutate(|v| match &mut v.value {
+        Value::List(l) => {
+            l.push(element);
+            Ok(Value::Unit)
+        }
+        _ => Err(v.ty().expected([ast::Type::List])),
+    })
+}
+
+fn pop(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    let [lhs] = get_args::<1>(args)?;
+    let ast::Expr::Ident(ident) = lhs else {
+        return Err(Error::MalformedExpr(format!(
+            "malformed assigment, lhs: {:?}",
+            lhs
+        )));
+    };
+    let variable = ctx.lookup_mut(ident)?;
+    variable.mutate(|v| match &mut v.value {
+        Value::List(l) => l
+            .pop()
+            .ok_or_else(|| Error::ArrayOutOfBounds { idx: 0, len: 0 }),
+        _ => Err(v.ty().expected([ast::Type::List])),
+    })
+}
+
+fn isempty(ctx: &mut Context, args: &[ast::Expr]) -> Result {
+    let v = ctx.eval_expr(&get_args::<1>(args)?[0])?;
+    match v.ty() {
+        ast::Type::List => v
+            .as_list()
+            .unwrap()
+            .is_empty()
+            .wrap(Value::Boolean)
+            .wrap(Ok),
+        ast::Type::String => v
+            .as_str()
+            .unwrap()
+            .is_empty()
+            .wrap(Value::Boolean)
+            .wrap(Ok),
+        _ => Err(v.ty().expected([ast::Type::List])),
+    }
+}
+
+fn get_args<const N: usize>(args: &[ast::Expr]) -> std::result::Result<&[ast::Expr; N], Error> {
+    args.try_into().map_err(|_| Error::IncorrectArgFormat {
+        wanted: N,
+        got: args.len(),
+    })
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use crate::{ast::*, eval::*};
+
+    #[test]
+    fn test_ts_builtins() {
+        let language = tree_sitter_python::language();
+        let mut ctx = Context::new(language).with_program(Program::new());
+
+        assert_eq!(
+            ctx.eval_block(&Block {
+                body: vec![Statement::decl(Type::List, "a", Expr::list([Expr::int(5)]),)]
+            }),
+            Ok(Value::Unit)
+        );
+        assert_eq!(
+            ctx.lookup(&String::from("a")).unwrap().clone(),
+            Variable {
+                ty: Type::List,
+                name: "a".to_owned(),
+                value: vec![5usize.into()].into(),
+            }
+        );
+    }
+}
diff --git a/src/eval/mod.rs b/src/eval/mod.rs
new file mode 100644
index 0000000..c4460c0
--- /dev/null
+++ b/src/eval/mod.rs
@@ -0,0 +1,1051 @@
+//! tree walking interpreter for tbsp
+
+use crate::{ast, Wrap};
+use std::{collections::HashMap, fmt, io};
+
+mod builtins;
+
+#[derive(Debug, PartialEq, Eq, Clone)]
+pub struct Variable {
+    pub ty: ast::Type,
+    pub name: ast::Identifier,
+    pub value: Value,
+}
+
+impl Variable {
+    fn value(&self) -> &Value {
+        &self.value
+    }
+
+    pub(crate) fn ty(&self) -> ast::Type {
+        self.ty
+    }
+
+    fn assign(&mut self, value: Value) -> Result {
+        if self.ty() == value.ty() {
+            self.value = value;
+            Ok(self.value.clone())
+        } else {
+            Err(value.ty().expected([self.ty()]))
+        }
+    }
+
+    pub(crate) fn mutate(&mut self, f: impl FnOnce(&mut Self) -> Result) -> Result {
+        f(self)
+    }
+}
+
+#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
+pub enum Value {
+    Unit,
+    Integer(i128),
+    String(String),
+    Boolean(bool),
+    Node(NodeId),
+    List(Vec<Value>),
+}
+
+type NodeId = usize;
+
+impl Value {
+    pub(crate) fn ty(&self) -> ast::Type {
+        match self {
+            Self::Unit => ast::Type::Unit,
+            Self::Integer(_) => ast::Type::Integer,
+            Self::String(_) => ast::Type::String,
+            Self::Boolean(_) => ast::Type::Boolean,
+            Self::Node(_) => ast::Type::Node,
+            Self::List(_) => ast::Type::List,
+        }
+    }
+
+    fn default(ty: ast::Type) -> Self {
+        match ty {
+            ast::Type::Unit => Self::Unit,
+            ast::Type::Integer => Self::default_int(),
+            ast::Type::String => Self::default_string(),
+            ast::Type::Boolean => Self::default_bool(),
+            ast::Type::Node => unreachable!(),
+            ast::Type::List => Self::default_list(),
+        }
+    }
+
+    fn default_int() -> Self {
+        Self::Integer(0)
+    }
+
+    fn default_bool() -> Self {
+        Self::Boolean(false)
+    }
+
+    fn default_string() -> Self {
+        Self::String(String::default())
+    }
+
+    fn default_list() -> Self {
+        Self::List(Vec::new())
+    }
+
+    fn as_boolean(&self) -> std::result::Result<bool, Error> {
+        match self {
+            Self::Boolean(b) => Ok(*b),
+            v => Err(v.ty().expected([ast::Type::Boolean])),
+        }
+    }
+
+    pub(crate) fn as_str(&self) -> std::result::Result<&str, Error> {
+        match self {
+            Self::String(s) => Ok(s.as_str()),
+            v => Err(v.ty().expected([ast::Type::String])),
+        }
+    }
+
+    pub(crate) fn as_int(&self) -> std::result::Result<i128, Error> {
+        match self {
+            Self::Integer(i) => Ok(*i),
+            v => Err(v.ty().expected([ast::Type::Integer])),
+        }
+    }
+
+    pub(crate) fn as_node(&self) -> std::result::Result<NodeId, Error> {
+        match self {
+            Self::Node(id) => Ok(*id),
+            v => Err(v.ty().expected([ast::Type::Node])),
+        }
+    }
+
+    pub(crate) fn as_list(&self) -> std::result::Result<Vec<Value>, Error> {
+        match self {
+            Self::List(values) => Ok(values.clone()),
+            v => Err(v.ty().expected([ast::Type::List])),
+        }
+    }
+
+    fn add(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Integer(s), Self::Integer(o)) => Ok(Self::Integer(*s + *o)),
+            (Self::String(s), Self::String(o)) => Ok(Self::String(format!("{s}{o}"))),
+            (Self::List(l), o) => Ok(Self::List(l.iter().cloned().chain([o.clone()]).collect())),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Arith(ast::ArithOp::Add),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn sub(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Integer(s), Self::Integer(o)) => Ok(Self::Integer(*s - *o)),
+            (Self::String(s), Self::String(o)) => {
+                Ok(Self::String(s.strip_suffix(o).unwrap_or(s).to_owned()))
+            }
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Arith(ast::ArithOp::Sub),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn mul(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Integer(s), Self::Integer(o)) => Ok(Self::Integer(*s * *o)),
+            (Self::Integer(s), Self::String(o)) => Ok(Self::String(o.repeat(*s as usize))),
+            (Self::String(_), Self::Integer(_)) => other.mul(self),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Arith(ast::ArithOp::Mul),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn div(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Integer(s), Self::Integer(o)) => Ok(Self::Integer(*s / *o)),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Arith(ast::ArithOp::Div),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn mod_(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Integer(s), Self::Integer(o)) => Ok(Self::Integer(*s % *o)),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Arith(ast::ArithOp::Mod),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn equals(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Integer(s), Self::Integer(o)) => Ok(Self::Boolean(s == o)),
+            (Self::String(s), Self::String(o)) => Ok(Self::Boolean(s == o)),
+            (Self::Boolean(s), Self::Boolean(o)) => Ok(Self::Boolean(s == o)),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Cmp(ast::CmpOp::Eq),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn greater_than(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Integer(s), Self::Integer(o)) => Ok(Self::Boolean(s > o)),
+            (Self::String(s), Self::String(o)) => Ok(Self::Boolean(s.cmp(o).is_gt())),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Cmp(ast::CmpOp::Gt),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn less_than(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Integer(s), Self::Integer(o)) => Ok(Self::Boolean(s < o)),
+            (Self::String(s), Self::String(o)) => Ok(Self::Boolean(s.cmp(o).is_lt())),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Cmp(ast::CmpOp::Lt),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn greater_than_equals(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Integer(s), Self::Integer(o)) => Ok(Self::Boolean(s >= o)),
+            (Self::String(s), Self::String(o)) => Ok(Self::Boolean(s.cmp(o).is_ge())),
+            (Self::Boolean(s), Self::Boolean(o)) => Ok(Self::Boolean(s == o)),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Cmp(ast::CmpOp::Gte),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn less_than_equals(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Integer(s), Self::Integer(o)) => Ok(Self::Boolean(s <= o)),
+            (Self::String(s), Self::String(o)) => Ok(Self::Boolean(s.cmp(o).is_le())),
+            (Self::Boolean(s), Self::Boolean(o)) => Ok(Self::Boolean(s == o)),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Cmp(ast::CmpOp::Lte),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn not(&self) -> Result {
+        match self {
+            Self::Boolean(s) => Ok(Self::Boolean(!s)),
+            _ => Err(Error::UndefinedUnaryOp(ast::UnaryOp::Not, self.ty())),
+        }
+    }
+
+    fn and(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Boolean(s), Self::Boolean(o)) => Ok(Self::Boolean(*s && *o)),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Logic(ast::LogicOp::And),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+
+    fn or(&self, other: &Self) -> Result {
+        match (self, other) {
+            (Self::Boolean(s), Self::Boolean(o)) => Ok(Self::Boolean(*s || *o)),
+            _ => Err(Error::UndefinedBinOp(
+                ast::BinOp::Logic(ast::LogicOp::Or),
+                self.ty(),
+                other.ty(),
+            )),
+        }
+    }
+}
+
+impl fmt::Display for Value {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::Unit => write!(f, "()"),
+            Self::Integer(i) => write!(f, "{i}"),
+            Self::String(s) => write!(f, "{s}"),
+            Self::Boolean(b) => write!(f, "{b}"),
+            Self::Node(id) => write!(f, "<node #{id}>"),
+            Self::List(items) => {
+                write!(f, "[")?;
+                let mut iterable = items.iter().peekable();
+                while let Some(item) = iterable.next() {
+                    if iterable.peek().is_none() {
+                        write!(f, "{item}")?;
+                    } else {
+                        write!(f, "{item}, ")?;
+                    }
+                }
+                write!(f, "]")
+            }
+        }
+    }
+}
+
+impl From<bool> for Value {
+    fn from(value: bool) -> Self {
+        Self::Boolean(value)
+    }
+}
+
+impl From<i128> for Value {
+    fn from(value: i128) -> Self {
+        Self::Integer(value)
+    }
+}
+
+impl From<usize> for Value {
+    fn from(value: usize) -> Self {
+        (value as i128).into()
+    }
+}
+
+impl From<&str> for Value {
+    fn from(value: &str) -> Self {
+        Self::String(value.to_owned())
+    }
+}
+
+impl From<Vec<Value>> for Value {
+    fn from(value: Vec<Value>) -> Self {
+        Self::List(value)
+    }
+}
+
+#[derive(Debug, PartialEq, Eq)]
+pub enum Error {
+    FailedLookup(ast::Identifier),
+    TypeMismatch {
+        expected: Vec<ast::Type>,
+        got: ast::Type,
+    },
+    UndefinedBinOp(ast::BinOp, ast::Type, ast::Type),
+    UndefinedUnaryOp(ast::UnaryOp, ast::Type),
+    AlreadyBound(ast::Identifier),
+    MalformedExpr(String),
+    InvalidNodeKind(String),
+    NoParentNode(tree_sitter::Node<'static>),
+    IncorrectArgFormat {
+        wanted: usize,
+        got: usize,
+    },
+    InvalidStringSlice {
+        length: usize,
+        start: i128,
+        end: i128,
+    },
+    ArrayOutOfBounds {
+        idx: i128,
+        len: usize,
+    },
+    // current node is only set in visitors, not in BEGIN or END blocks
+    CurrentNodeNotPresent,
+}
+
+impl ast::Type {
+    pub fn expected<const N: usize>(self, expected: [Self; N]) -> Error {
+        Error::TypeMismatch {
+            expected: expected.to_vec(),
+            got: self,
+        }
+    }
+}
+
+pub type Result = std::result::Result<Value, Error>;
+
+pub struct Context<'s> {
+    variables: HashMap<ast::Identifier, Variable>,
+    language: tree_sitter::Language,
+    program: ast::Program,
+    pub(crate) input_src: Option<String>,
+    cursor: Option<tree_sitter::TreeCursor<'static>>,
+    tree: Option<&'static tree_sitter::Tree>,
+    cache: HashMap<NodeId, tree_sitter::Node<'static>>,
+    output_stream: Option<Box<dyn io::Write + 's>>,
+}
+
+impl<'s> fmt::Debug for Context<'s> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("Context")
+            .field("variables", &self.variables)
+            .field("language", &self.language)
+            .field("input_src", &self.input_src)
+            .field(
+                "cursor",
+                if self.cursor.is_some() {
+                    &"Some(<cursor>)"
+                } else {
+                    &"None"
+                },
+            )
+            .finish()
+    }
+}
+
+impl<'s> Context<'s> {
+    pub fn new(language: tree_sitter::Language) -> Self {
+        Self {
+            program: Default::default(),
+            variables: Default::default(),
+            language,
+            input_src: None,
+            cursor: None,
+            tree: None,
+            cache: HashMap::default(),
+            output_stream: Some(Box::new(io::stdout()) as Box<dyn io::Write + 's>),
+        }
+    }
+
+    pub fn cache_node(&mut self, node: tree_sitter::Node<'static>) {
+        self.cache.entry(node.id()).or_insert(node);
+    }
+
+    pub fn get_node_by_id(&mut self, id: usize) -> Option<tree_sitter::Node<'static>> {
+        let root_node = self.tree.as_ref().map(|t| t.root_node())?;
+        self.get_node_by_id_helper(root_node, id)
+    }
+
+    fn get_node_by_id_helper(
+        &mut self,
+        start: tree_sitter::Node<'static>,
+        id: usize,
+    ) -> Option<tree_sitter::Node<'static>> {
+        self.cache_node(start);
+
+        if let Some(found) = self.cache.get(&id) {
+            return Some(*found);
+        }
+
+        if start.id() == id {
+            return Some(start);
+        } else {
+            for child in start.children(&mut start.walk()) {
+                if let Some(n) = self.get_node_by_id_helper(child, id) {
+                    return Some(n);
+                };
+            }
+        }
+
+        None
+    }
+
+    pub fn with_program(mut self, program: ast::Program) -> Self {
+        self.program = program;
+        self
+    }
+
+    pub fn with_input(mut self, src: String) -> Self {
+        self.input_src = Some(src);
+        self
+    }
+
+    pub fn with_tree(mut self, tree: tree_sitter::Tree) -> Self {
+        let tree = Box::leak(Box::new(tree));
+        self.cursor = Some(tree.walk());
+        self.tree = Some(tree);
+        self
+    }
+
+    pub fn with_output_stream(mut self, stream: Box<dyn io::Write + 's>) -> Self {
+        self.output_stream = Some(stream);
+        self
+    }
+
+    pub(crate) fn eval_expr(&mut self, expr: &ast::Expr) -> Result {
+        match expr {
+            ast::Expr::Unit => Ok(Value::Unit),
+            ast::Expr::Lit(lit) => self.eval_lit(lit),
+            ast::Expr::Ident(ident) => self.lookup(ident).map(Variable::value).cloned(),
+            ast::Expr::Bin(lhs, op, rhs) => self.eval_bin(&*lhs, *op, &*rhs),
+            ast::Expr::Unary(expr, op) => self.eval_unary(&*expr, *op),
+            ast::Expr::Call(call) => self.eval_call(&*call),
+            ast::Expr::List(list) => self.eval_list(&*list),
+            ast::Expr::Index(target, idx) => self.eval_index(&*target, &*idx),
+            ast::Expr::If(if_expr) => self.eval_if(if_expr),
+            ast::Expr::Block(block) => self.eval_block(block),
+            ast::Expr::Node => self.eval_node(),
+            ast::Expr::FieldAccess(expr, items) => self.eval_field_access(expr, items),
+        }
+    }
+
+    fn eval_lit(&mut self, lit: &ast::Literal) -> Result {
+        match lit {
+            ast::Literal::Str(s) => Ok(Value::String(s.to_owned())),
+            ast::Literal::Int(i) => Ok(Value::Integer(*i)),
+            ast::Literal::Bool(b) => Ok(Value::Boolean(*b)),
+        }
+    }
+
+    fn eval_node(&mut self) -> Result {
+        self.cursor
+            .as_ref()
+            .ok_or(Error::CurrentNodeNotPresent)?
+            .node()
+            .id()
+            .wrap(Value::Node)
+            .wrap_ok()
+    }
+
+    pub(crate) fn lookup(
+        &mut self,
+        ident: &ast::Identifier,
+    ) -> std::result::Result<&Variable, Error> {
+        self.variables
+            .get(ident)
+            .ok_or_else(|| Error::FailedLookup(ident.to_owned()))
+    }
+
+    pub(crate) fn lookup_mut(
+        &mut self,
+        ident: &ast::Identifier,
+    ) -> std::result::Result<&mut Variable, Error> {
+        self.variables
+            .get_mut(ident)
+            .ok_or_else(|| Error::FailedLookup(ident.to_owned()))
+    }
+
+    fn bind(
+        &mut self,
+        ident: &ast::Identifier,
+        ty: ast::Type,
+    ) -> std::result::Result<&mut Variable, Error> {
+        if self.lookup(ident).is_err() {
+            self.variables
+                .entry(ident.to_owned())
+                .or_insert_with(|| Variable {
+                    name: ident.to_owned(),
+                    value: Value::default(ty),
+                    ty,
+                })
+                .wrap_ok()
+        } else {
+            Err(Error::AlreadyBound(ident.to_owned()))
+        }
+    }
+
+    fn eval_bin(&mut self, lhs: &ast::Expr, op: ast::BinOp, rhs: &ast::Expr) -> Result {
+        match op {
+            ast::BinOp::Assign(op) => self.eval_assign(lhs, op, rhs),
+            ast::BinOp::Arith(op) => self.eval_arith(lhs, op, rhs),
+            ast::BinOp::Cmp(op) => self.eval_cmp(lhs, op, rhs),
+            ast::BinOp::Logic(op) => self.eval_logic(lhs, op, rhs),
+        }
+    }
+
+    fn eval_assign(
+        &mut self,
+        lhs: &ast::Expr,
+        ast::AssignOp { op }: ast::AssignOp,
+        rhs: &ast::Expr,
+    ) -> Result {
+        let ast::Expr::Ident(ident) = lhs else {
+            return Err(Error::MalformedExpr(format!(
+                "malformed assigment, lhs: {:?}",
+                lhs
+            )));
+        };
+        let value = self.eval_expr(rhs)?;
+        let variable = self.lookup_mut(ident)?;
+        match op {
+            None => variable.assign(value),
+            Some(ast::ArithOp::Add) => variable.assign(variable.value().add(&value)?),
+            Some(ast::ArithOp::Sub) => variable.assign(variable.value().sub(&value)?),
+            Some(ast::ArithOp::Mul) => variable.assign(variable.value().mul(&value)?),
+            Some(ast::ArithOp::Div) => variable.assign(variable.value().div(&value)?),
+            Some(ast::ArithOp::Mod) => variable.assign(variable.value().mod_(&value)?),
+        }
+    }
+
+    fn eval_arith(&mut self, lhs: &ast::Expr, op: ast::ArithOp, rhs: &ast::Expr) -> Result {
+        let l = self.eval_expr(lhs)?;
+        let r = self.eval_expr(rhs)?;
+        match op {
+            ast::ArithOp::Add => l.add(&r),
+            ast::ArithOp::Sub => l.sub(&r),
+            ast::ArithOp::Mul => l.mul(&r),
+            ast::ArithOp::Div => l.div(&r),
+            ast::ArithOp::Mod => l.mod_(&r),
+        }
+    }
+
+    fn eval_cmp(&mut self, lhs: &ast::Expr, op: ast::CmpOp, rhs: &ast::Expr) -> Result {
+        let l = self.eval_expr(lhs)?;
+        let r = self.eval_expr(rhs)?;
+
+        match op {
+            ast::CmpOp::Eq => l.equals(&r),
+            ast::CmpOp::Gt => l.greater_than(&r),
+            ast::CmpOp::Lt => l.less_than(&r),
+            ast::CmpOp::Neq => l.equals(&r).and_then(|v| v.not()),
+            ast::CmpOp::Gte => l.greater_than_equals(&r),
+            ast::CmpOp::Lte => l.less_than_equals(&r),
+        }
+    }
+
+    fn eval_logic(&mut self, lhs: &ast::Expr, op: ast::LogicOp, rhs: &ast::Expr) -> Result {
+        let l = self.eval_expr(lhs)?;
+
+        // short-circuit
+        let l_value = l.as_boolean()?;
+
+        match op {
+            ast::LogicOp::Or => {
+                if l_value {
+                    return Ok(l);
+                } else {
+                    let r = self.eval_expr(rhs)?;
+                    l.or(&r)
+                }
+            }
+            ast::LogicOp::And => {
+                if !l_value {
+                    return Ok(l);
+                } else {
+                    let r = self.eval_expr(rhs)?;
+                    l.and(&r)
+                }
+            }
+        }
+    }
+
+    fn eval_unary(&mut self, expr: &ast::Expr, op: ast::UnaryOp) -> Result {
+        let val = self.eval_expr(expr)?;
+        match op {
+            ast::UnaryOp::Not => val.not(),
+        }
+    }
+
+    fn eval_if(&mut self, if_expr: &ast::IfExpr) -> Result {
+        let cond = self.eval_expr(&if_expr.condition)?;
+
+        if cond.as_boolean()? {
+            self.eval_block(&if_expr.then)
+        } else {
+            self.eval_block(&if_expr.else_)
+        }
+    }
+
+    fn eval_call(&mut self, call: &ast::Call) -> Result {
+        ((&*builtins::BUILTINS)
+            .get(call.function.as_str())
+            .ok_or_else(|| Error::FailedLookup(call.function.to_owned()))?)(
+            self,
+            call.parameters.as_slice(),
+        )
+    }
+
+    fn eval_list(&mut self, list: &ast::List) -> Result {
+        let mut vals = vec![];
+        for i in &list.items {
+            vals.push(self.eval_expr(i)?);
+        }
+        Ok(vals.into())
+    }
+
+    fn eval_index(&mut self, target: &ast::Expr, idx: &ast::Expr) -> Result {
+        let mut target = self.eval_expr(target)?.as_list()?;
+        let idx = self.eval_expr(idx)?.as_int()?;
+        if idx < 0 || idx >= target.len() as i128 {
+            Err(Error::ArrayOutOfBounds {
+                idx,
+                len: target.len(),
+            })
+        } else {
+            Ok(target.remove(idx as usize))
+        }
+    }
+
+    fn eval_declaration(&mut self, decl: &ast::Declaration) -> Result {
+        let initial_value = match decl.init.as_ref() {
+            Some(init) => Some(self.eval_expr(&*init)?),
+            None => None,
+        };
+        let variable = self.bind(&decl.name, decl.ty)?;
+
+        if let Some(init) = initial_value {
+            variable.assign(init)?;
+        }
+
+        Ok(Value::Unit)
+    }
+
+    fn eval_statement(&mut self, stmt: &ast::Statement) -> Result {
+        match stmt {
+            ast::Statement::Bare(expr) => self.eval_expr(expr),
+            ast::Statement::Declaration(decl) => self.eval_declaration(decl),
+        }
+    }
+
+    fn eval_block(&mut self, block: &ast::Block) -> Result {
+        for stmt in block.body.iter() {
+            self.eval_statement(stmt)?;
+        }
+        Ok(Value::Unit)
+    }
+
+    fn eval_field_access(&mut self, expr: &ast::Expr, field: &ast::Identifier) -> Result {
+        let v = self.eval_expr(expr)?;
+        let base = v.as_node()?;
+        let base_node = self.get_node_by_id(base).unwrap();
+        base_node
+            .child_by_field_name(field)
+            .ok_or(Error::InvalidNodeKind(field.clone()))
+            .map(|n| n.id())
+            .map(Value::Node)
+    }
+
+    fn goto_first_child(&mut self) -> bool {
+        self.cursor
+            .as_mut()
+            .map(|c| c.goto_first_child())
+            .unwrap_or_default()
+    }
+
+    pub fn eval(&mut self) -> Result {
+        let program = std::mem::take(&mut self.program);
+        let mut has_next = true;
+        let mut postorder = Vec::new();
+
+        // BEGIN block
+        if let Some(block) = program.begin() {
+            self.eval_block(block)?;
+        }
+
+        while has_next {
+            let current_node = self.cursor.as_ref().unwrap().node();
+            postorder.push(current_node);
+
+            if let Some(block) = program.stanza_by_node(current_node, ast::Modifier::Enter) {
+                self.eval_block(block)?;
+            }
+
+            has_next = self.goto_first_child();
+
+            if !has_next {
+                has_next = self.cursor.as_mut().unwrap().goto_next_sibling();
+                if let Some(block) = postorder
+                    .pop()
+                    .and_then(|n| program.stanza_by_node(n, ast::Modifier::Leave))
+                {
+                    self.eval_block(block)?;
+                };
+            }
+
+            while !has_next && self.cursor.as_mut().unwrap().goto_parent() {
+                has_next = self.cursor.as_mut().unwrap().goto_next_sibling();
+                if let Some(block) = postorder
+                    .pop()
+                    .and_then(|n| program.stanza_by_node(n, ast::Modifier::Leave))
+                {
+                    self.eval_block(block)?;
+                };
+            }
+        }
+
+        // END block
+        if let Some(block) = program.end() {
+            self.eval_block(block)?;
+        }
+
+        Ok(Value::Unit)
+    }
+}
+
+pub fn evaluate(file: &str, program: &str, language: tree_sitter::Language) -> Result {
+    let mut parser = tree_sitter::Parser::new();
+    let _ = parser.set_language(&language);
+
+    let tree = parser.parse(file, None).unwrap();
+
+    let program = ast::Program::new().from_str(program).unwrap();
+    let mut ctx = Context::new(language)
+        .with_input(file.to_owned())
+        .with_tree(tree)
+        .with_output_stream(Box::new(io::stdout()))
+        .with_program(program);
+
+    ctx.eval()
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use crate::ast::*;
+    use expect_test::{expect, Expect};
+
+    fn gen_test(file: &str, program: &str, expected: Expect) {
+        let language = tree_sitter_python::language();
+        let mut parser = tree_sitter::Parser::new();
+        let _ = parser.set_language(&language);
+        let tree = parser.parse(file, None).unwrap();
+        let program = ast::Program::new().from_str(program).unwrap();
+
+        let mut output = Vec::new();
+        let mut ctx = Context::new(language)
+            .with_input(file.to_owned())
+            .with_tree(tree)
+            .with_program(program)
+            .with_output_stream(Box::new(&mut output) as Box<dyn io::Write>);
+
+        ctx.eval().unwrap();
+
+        drop(ctx);
+
+        expected.assert_eq(&String::from_utf8(output).unwrap())
+    }
+
+    #[test]
+    fn bin() {
+        let language = tree_sitter_python::language();
+        let mut ctx = Context::new(language).with_program(Program::new());
+        assert_eq!(
+            ctx.eval_expr(&Expr::bin(Expr::int(5), "+", Expr::int(10),)),
+            Ok(Value::Integer(15))
+        );
+        assert_eq!(
+            ctx.eval_expr(&Expr::bin(Expr::int(5), "==", Expr::int(10),)),
+            Ok(Value::Boolean(false))
+        );
+        assert_eq!(
+            ctx.eval_expr(&Expr::bin(Expr::int(5), "<", Expr::int(10),)),
+            Ok(Value::Boolean(true))
+        );
+        assert_eq!(
+            ctx.eval_expr(&Expr::bin(
+                Expr::bin(Expr::int(5), "<", Expr::int(10),),
+                "&&",
+                Expr::false_(),
+            )),
+            Ok(Value::Boolean(false))
+        );
+    }
+
+    #[test]
+    fn test_evaluate_blocks() {
+        let language = tree_sitter_python::language();
+        let mut ctx = Context::new(language).with_program(Program::new());
+        assert_eq!(
+            ctx.eval_block(&Block {
+                body: vec![
+                    Statement::Declaration(Declaration {
+                        ty: Type::Integer,
+                        name: "a".to_owned(),
+                        init: None,
+                    }),
+                    Statement::Bare(Expr::bin(Expr::ident("a"), "+=", Expr::int(5),)),
+                ]
+            }),
+            Ok(Value::Unit)
+        );
+        assert_eq!(
+            ctx.lookup(&String::from("a")).unwrap().clone(),
+            Variable {
+                ty: Type::Integer,
+                name: "a".to_owned(),
+                value: Value::Integer(5)
+            }
+        );
+    }
+
+    #[test]
+    fn test_evaluate_if() {
+        let language = tree_sitter_python::language();
+        let mut ctx = Context::new(language).with_program(Program::new());
+        assert_eq!(
+            ctx.eval_block(&Block {
+                body: vec![
+                    Statement::Declaration(Declaration {
+                        ty: Type::Integer,
+                        name: "a".to_owned(),
+                        init: Some(Expr::int(1).boxed()),
+                    }),
+                    Statement::Bare(Expr::If(IfExpr {
+                        condition: Expr::true_().boxed(),
+                        then: Block {
+                            body: vec![Statement::Bare(Expr::bin(
+                                Expr::Ident("a".to_owned()),
+                                "+=",
+                                Expr::int(5),
+                            ))]
+                        },
+                        else_: Block {
+                            body: vec![Statement::Bare(Expr::bin(
+                                Expr::ident("a"),
+                                "+=",
+                                Expr::int(10),
+                            ))]
+                        }
+                    }))
+                ]
+            }),
+            Ok(Value::Unit)
+        );
+        assert_eq!(
+            ctx.lookup(&String::from("a")).unwrap().clone(),
+            Variable {
+                ty: Type::Integer,
+                name: "a".to_owned(),
+                value: Value::Integer(6)
+            }
+        );
+    }
+
+    #[test]
+    fn test_substring() {
+        let language = tree_sitter_python::language();
+        let mut ctx = Context::new(language).with_program(Program::new());
+        assert_eq!(
+            ctx.eval_block(&Block {
+                body: vec![
+                    Statement::Declaration(Declaration {
+                        ty: Type::String,
+                        name: "a".to_owned(),
+                        init: Some(Expr::str("foobar").boxed()),
+                    }),
+                    Statement::Declaration(Declaration {
+                        ty: Type::String,
+                        name: "b".to_owned(),
+                        init: Some(
+                            Expr::call(
+                                "substr",
+                                [Expr::Ident("a".to_owned()), Expr::int(0), Expr::int(3),]
+                            )
+                            .boxed()
+                        ),
+                    }),
+                ]
+            }),
+            Ok(Value::Unit)
+        );
+        assert_eq!(
+            ctx.lookup(&String::from("b")).unwrap().clone(),
+            Variable {
+                ty: Type::String,
+                name: "b".to_owned(),
+                value: "foo".into()
+            }
+        );
+    }
+
+    #[test]
+    fn test_list() {
+        let language = tree_sitter_python::language();
+        let mut ctx = Context::new(language).with_program(Program::new());
+        assert_eq!(
+            ctx.eval_block(&Block {
+                body: vec![Statement::Declaration(Declaration {
+                    ty: Type::List,
+                    name: "a".to_owned(),
+                    init: Some(
+                        Expr::List(List {
+                            items: vec![Expr::int(5)]
+                        })
+                        .boxed()
+                    ),
+                }),]
+            }),
+            Ok(Value::Unit)
+        );
+        assert_eq!(
+            ctx.lookup(&String::from("a")).unwrap().clone(),
+            Variable {
+                ty: Type::List,
+                name: "a".to_owned(),
+                value: vec![5usize.into()].into(),
+            }
+        );
+    }
+
+    #[test]
+    fn list_builtins() {
+        gen_test(
+            "",
+            "BEGIN {
+                list a = [5];
+                print(a);
+            }
+            ",
+            expect!["[5]"]
+        );
+
+        gen_test(
+            "",
+            "BEGIN {
+                list a = [5, 4, 3];
+                print(length(a));
+            }
+            ",
+            expect!["3"]
+        );
+
+        gen_test(
+            "",
+            r#"BEGIN {
+                list a = [5, 4, 3];
+                print(member(a, 3));
+                print(", ");
+                print(member(a, 6));
+            }
+            "#,
+            expect!["true, false"]
+        );
+
+        gen_test(
+            "",
+            r#"BEGIN {
+                list a = [5];
+                println(a);
+                push(a, 4);
+                println(a);
+                push(a, 3);
+                println(a);
+                pop(a);
+                println(a);
+                pop(a);
+                println(a);
+            }
+            "#,
+            expect![[r#"
+                [5]
+                [5, 4]
+                [5, 4, 3]
+                [5, 4]
+                [5]
+            "#]]
+        );
+
+        gen_test(
+            "",
+            r#"BEGIN {
+                list a = [5];
+                println(isempty(a));
+                pop(a);
+                println(isempty(a));
+            }
+            "#,
+            expect![[r#"
+                false
+                true
+            "#]]
+        );
+
+    }
+}