muesli/ast.go

// Abstract Syntax tree for the MUESLI interpreter
package muesli

import "fmt"


/* AST node kind */
type Ast struct {
	Parent * Ast
    Child  * Ast
    Before * Ast
    After  * Ast
	AstKind
	*Token
}


func NewAst(kind AstKind, parent * Ast, token * Token) *Ast {
    child := &Ast{parent, nil, nil, nil,  kind, token}
    return child
}

func (ast * Ast) LastSibling() * Ast {
    res := ast
    for res != nil && res.After != nil {
        res = res.After
    }
    return res
}

func (ast * Ast) LastChild() * Ast {
    return ast.Child.LastSibling()
}

/* Detaches, I.E removes this node and all it's children from the parent tree. */
func (ast * Ast) Remove() * Ast {
    parent := ast.Parent
    before := ast.Before
    after  := ast.After
    if before != nil {
        before.After = after
    }
    if after != nil {
        after.Before = before
    }
    if parent != nil {
        /* Special case if ast is the first child of it's parent. */
        if ast == parent.Child {
            parent.Child = after
        }
    }
    ast.Parent = nil
    return ast
}

func (ast * Ast) InsertSibling(sibling * Ast) * Ast {
    after := ast.After
    ast.After = sibling
    sibling.Before = ast
    sibling.After  = after
    if after != nil {
        after.Before = sibling
    }
    sibling.Parent = ast.Parent
    return sibling
}

func (ast * Ast) AppendSibling(sibling * Ast) * Ast {
    return ast.LastSibling().InsertSibling(sibling)
}

func (ast * Ast) AppendChild(child * Ast) * Ast {
    child.Parent = ast
    if ast.Child == nil {
        ast.Child = child
    } else {
        ast.Child.AppendSibling(child)
    }
    return child
}

func (ast * Ast) NewSibling(kind AstKind, token * Token) * Ast {
    sibling := NewAst(kind, ast.Parent, token)
    return ast.AppendSibling(sibling)
}

func (ast * Ast) NewChild(kind AstKind, token * Token) * Ast {
    sibling := NewAst(kind, ast.Parent, token)
    return ast.AppendChild(sibling)
}

func (ast * Ast) Walk(walker func(node * Ast) * Ast) * Ast {
    if found := walker(ast); found != nil {
        return found
    }
    if ast.Child != nil {
        if found := ast.Child.Walk(walker); found != nil {
            return found
        }
    }
    if ast.After != nil {
        if found := ast.After.Walk(walker); found != nil {
            return found
        }
    }
    return nil
}

func (ast * Ast) String() string {
    return fmt.Sprintf("Ast %d %v", ast.AstKind, ast.Token)
}

func (ast * Ast) Display() {
    ast.Walk(func(node * Ast) * Ast {
        fmt.Printf("Tree: %s\n", node)
        return nil
    })
}

func (ast * Ast) Depth() int {
    var depth int = 0;
    parent := ast.Parent
    for parent != nil {
        depth ++;
        parent = parent.Parent
    }
    return depth
}

func (ast * Ast) CountChildren() int {
    var count int = 0;
    child := ast.Child
    for child != nil {
        count ++;
        child = child.After
    }
    return count;
}