muesli/vm.go

// vm, the virtual low level machine that runs MUESLI.
package muesli

import (
	"fmt"
	"strings"
)


// Handler function
type Handler func(vm *VM, arguments ...Value) []Value

func (handler *Handler) Call(vm *VM, arguments ...Value) []Value {
	return (*handler)(vm, arguments...)
}

// A callable Value must implement the Callable interface
type Callable interface {
	// Callable can be called
	Call(vm *VM, arguments ...Value) []Value
	// Position is the source code position where it was defined. Needed for tracebacks.
	Position() *Position
    // Signature are the types of the parameters of this function.
    Signature() Signature
}

// A helper Value has a help text available.
// This help text can be set as well.
type Helper interface {
	HelperName() string
	Help() string
	SetHelp(string) string
}


// BasicCallable is an embeddable struct that makes it easier to 
// implement the Caller and Helper interface.
type BasicCallable struct {
	// Name of the callable
	Name string
	// Help string for the callable.
	HelpText string
	// Signature of the callable for type checking.
	signature Signature
    // Position where the callable is defined.
    position Position
}

func (val BasicCallable) Signature() Signature {
	return val.signature
}

// Implement Helper interface
func (val BasicCallable) Help() string {
	return val.HelpText
}

// Implement Helper interface
func (val * BasicCallable) SetHelp(help string) string {
	val.HelpText = help
	return val.HelpText
}

// Implement Helper interface
func (val BasicCallable) HelperName() string {
	return val.Name
}

// AppendHelp appends help to an existing helper. 
func AppendHelp(helper Helper, extra string) string {
	return helper.SetHelp( helper.Help() + extra)
}

// ClearHelp rresets the help text to an empty string.
func ClearHelp(helper Helper, extra string) string {
	return helper.SetHelp("")
}

func (bc * BasicCallable) Takes(arguments ...TypeValue) *BasicCallable {
	bc.signature.SetParameters(arguments...)
	return bc
}

func (bc * BasicCallable) Returns(arguments ...TypeValue) *BasicCallable {
	bc.signature.SetReturns(arguments...)
	return bc
}


func (val BasicCallable) String() string {
	return val.Name
}

func (val BasicCallable) Type() TypeValue {
	return TypeValue("Callable")
}

func (from BasicCallable) Convert(to interface{}) error {
	return NewErrorValuef("Cannot convert the callable value %v to %v: Not implemented.", from, to)
}

func (val *BasicCallable) Call(vm *VM, arguments ...Value) []Value {
	panic("Not implemented")
}

// A struct to store a built in function
type BuiltinValue struct {
	BasicCallable
	Handler
}

func NewBasicCallable(name string) BasicCallable {
	return BasicCallable{name, "", NoSignature(), Position{name, 1, 1}}
}


func NewBuiltinValue(name string, handler Handler) *BuiltinValue {
	result := &BuiltinValue{}
	result.Name = name
	result.Handler = handler
	return result
}

// A block in a script.
type BlockValue struct {
	BasicCallable
	Ast *Ast
}

func NewBlockValue(definition *Ast) *BlockValue {
	result := &BlockValue{}
	result.Name = fmt.Sprintf("<block:%s>", definition.String())
	result.Ast = definition
	return result
}

func (block * BlockValue) Position() *Position {
	if block == nil {
		return nil
	}

	if block.Ast == nil {
		return nil
	}	
	pos := block.Ast.Token().Position
	return &pos
}

func (defined * DefinedValue) Position() *Position {
	if defined == nil {
		return nil
	}

	if defined.Body == nil {
		return nil
	}	
	return defined.Body.Position()
}

func (cv BasicCallable) Position() *Position {
	return &cv.position
}

// A script defined function
type DefinedValue struct {	
	BasicCallable
	Body *BlockValue
}

func NewDefinedValue(name string, signature Signature, body *BlockValue) *DefinedValue {
	result := &DefinedValue{}
	result.Name = name
	result.Body = body
	result.signature = signature
	return result
}

func (defined *DefinedValue) Call(vm *VM, arguments ...Value) []Value {
	vm.Trace("Call defined value: %v %v %v", defined, defined.signature, arguments)
    for i , arg := range arguments {
		if i >= len(defined.signature.Parameters) {
			break
		}
		param := defined.signature.Parameters[i]
		expectedType := param.Type
		vm.Trace("Signature check: %d %v", i, param)

        if !expectedType.IsMatch(arg.Type()) {
			return Fail(NewErrorValuef("Argument %d type mismatch: %s<->%s", i, expectedType, arg.Type()))
		}
		vm.Register(param.Name.String(), arg)
        vm.Trace("DefinedValue.Call: vm.Register: %v %v", param.Name.String(), arg)
	}
	
	res := defined.Body.Call(vm, arguments...)
	return res
}

func (defined *DefinedValue) Help() string {
	help := defined.BasicCallable.Help()
	extra := "["
	for _, parameter := range defined.signature.Parameters {
		extra = fmt.Sprintf("%s %s %s", extra, parameter.Name, parameter.Type)
	}
	extra = extra + "]:"
	return extra + help
}

// Assert that DefinedValue is callable.
var _ Callable = &DefinedValue{}


const (
	CoverTypeValue   = TypeValue("Cover")
	BuiltinTypeValue = TypeValue("Builtin")
	DefinedTypeValue = TypeValue("Defined")
	BlockTypeValue = TypeValue("Block")
)

func (v CoverValue) Type() TypeValue   { return CoverTypeValue }
func (v BuiltinValue) Type() TypeValue { return BuiltinTypeValue }
func (v DefinedValue) Type() TypeValue { return DefinedTypeValue }
func (v BlockValue) Type() TypeValue { return BlockTypeValue }

func (from CoverValue) Convert(to interface{}) error {
	return NewErrorValuef("Cannot convert the cover value %v to %v", from, to)
}

func (from BuiltinValue) Convert(to interface{}) error {
	return NewErrorValuef("Cannot convert the builtin value %v to %v", from, to)
}

func (from DefinedValue) Convert(to interface{}) error {
	return NewErrorValuef("Cannot convert the defined value %v to %v", from, to)
}

func (from BlockValue) Convert(to interface{}) error {
	if toValue, isOk := to.(*BlockValue) ; isOk {
		(*toValue) = from
		return nil
	} 
	return NewErrorValuef("Cannot convert the block value %v to %v", from, to)
}

func (cv * CoverValue) AddOverloadWithSignature(name string, callable Callable, signature Signature) Overload {
	ov := Overload { Name: name, Callable: callable }
	cv.Overloads[signature] = ov
	return ov
}


func (cv * CoverValue) AddOverloadCallable(name string, callable Callable) Overload {	
	return cv.AddOverloadWithSignature(name, callable, callable.Signature())
}

func (cv * CoverValue) AddOverload(name string, callable Callable, tv ... TypeValue) error {
	signature := Signature{}
	length := len(tv)
	if length > len(signature.Parameters) {
		length = len(signature.Parameters)
	}
	
	for i := 0; i < length; i++ {
		signature.Parameters[i].Type = tv[i]
	}
	
	cv.AddOverloadWithSignature(name, callable, signature)
	return nil
}

func (vm * VM) AddOverloadCallable(from, target string, level int, callable Callable) error {
	var cover *CoverValue
	var ok bool	
	lookup := vm.Lookup(from)
	if lookup == nil { 
		cover = vm.RegisterCover(from, level)
	} else if cover, ok = lookup.(*CoverValue) ; !ok {
		return fmt.Errorf("%s exists and is not a cover value", from)
	}

	cover.AddOverloadCallable(target, callable)
	return nil
}


func (vm *VM) LookupCallable(target string) (Callable, error) {
	var callable Callable
	var ok bool
	lookup := vm.Lookup(target)
	if lookup == nil { 
		return nil, fmt.Errorf("%s is not defined", target)
	}
	
	if callable, ok = lookup.(Callable) ; !ok {
		return nil, fmt.Errorf("%s is not a callable value", target)
	}
	return callable, nil
}

// AddOverloadByName overloads the from command to call the target command 
// if the argument list matches the signature based on the given type values
func (vm * VM) AddOverload(from, target string, level int, tv... TypeValue) error {
	var cover *CoverValue
	var callable Callable
	var ok bool	
	var err error

	lookup := vm.Lookup(from)
	if lookup == nil { 
		cover = vm.RegisterCover(from, level)
	} else if cover, ok = lookup.(*CoverValue) ; !ok {
		return fmt.Errorf("%s exists and is not a cover value", from)
	}
	
	callable, err = vm.LookupCallable(target)
	if err != nil {
		return err
	}
	
	return cover.AddOverload(target, callable, tv...)	
}

// AddOverloadByName overloads the from command to call the target command 
// if the argment lists matches the signature of the target command.
func (vm * VM) AddOverloadByName(from, target string, level int) error {
	callable, err := vm.LookupCallable(target)
	if err != nil {
		return err
	}
	return vm.AddOverloadCallable(from, target, level, callable)
}

type OverloadDescription struct {
	Target string
	Types []TypeValue
	Level int
}

func (vm * VM) AddOverloads(from string, descriptions ... OverloadDescription) error {
	for _, od := range descriptions {
		err := vm.AddOverload(from, od.Target, od.Level, od.Types...)
		if err != nil {
			panic(fmt.Errorf("internal error: could not register overloads: %s", err))
		}
	}
	return nil
}

func Over(target string, level int, types ... TypeValue) OverloadDescription {
	return OverloadDescription { Target: target, Level: level, Types: types}
}

func (vm * VM) SetHelp(target, help string) error {
	var helper Helper
	var ok bool	
	lookup := vm.Lookup(target)
	if lookup == nil {
		return fmt.Errorf("%s not found", target) 
	} else if helper, ok = lookup.(Helper) ; !ok {
		return fmt.Errorf("%s exists but cannot set help text.", target)
	}
	helper.SetHelp(help)	
	return nil
} 


// Scope of symbols defined in the VM, hierarchical
type Scope struct {
	parent   *Scope
	children []*Scope
	symbols  map[string]Value
}

func NewScope(parent *Scope) *Scope {
	return &Scope{parent, make([]*Scope, 0), make(map[string]Value)}
}


func (scope *Scope) Lookup(name string) Value {
	value, ok := scope.symbols[name]
	if ok {
		return value
	}
	if scope.parent != nil {
		return scope.parent.Lookup(name)
	}
	return NilValue
}

func (scope *Scope) Register(name string, value Value) Value {
	scope.symbols[name] = value
	return value
}

func (scope * Scope) Known(filter func(string, Value) bool) map[string]Value {
	res := make(map[string]Value)
	if scope.parent != nil {
		res = scope.parent.Known(filter)
	}
	for k, v := range scope.symbols {
		if (filter == nil) || filter(k, v) {
			res[k] = v
		}
	}
	return res
}

func (scope * Scope) ForEachDefined(do func(string, Value) (bool, error)) (bool, error)  {
	var res bool = true
	var err error
	
	if (do == nil) {
		return false, fmt.Errorf("do may not be nil")
	}
			
	if scope.parent != nil {
		res, err = scope.parent.ForEachDefined(do)
	}
	if res == false || err != nil {
		return res, err
	}
	for k, v := range scope.symbols {
		res, err = do(k, v)
		if res == false || err != nil {
			return res, err
		}		
	}
	return res, err
}


func (scope* Scope) DefinedHelpers() []Helper {
	res := []Helper{}
	scope.ForEachDefined(func (k string, v Value) (bool, error) {
		helper, hok := v.(Helper)
		if hok {
			res = append(res, helper)
		}
		return true, nil
	})
	return res
}


// Frame of execution of a function
type Frame struct {	
	parent    *Frame
	arguments []Value
	results   []Value
	failed    bool
	returned  bool
	position  *Position
}

func NewFrame(parent *Frame, position *Position) *Frame {
	return &Frame{parent, EmptyValueArray(), EmptyValueArray(), false, false, position}
}

type Tracer interface {
	Trace(vm VM, fmt string, args ... interface{}) bool
}

// Virtual machine
type VM struct {
	TopScope *Scope // Top level scope
	TopFrame *Frame // Top level scope
	*Scope          // Current Scope
	*Frame          // Current frame
	Tracer			// Tracer to emit tracing info to, could be used for logging or debugging
	ExitStatus int
}

func NewVM() *VM {
	vm := &VM{NewScope(nil), NewFrame(nil, nil), nil, nil, nil, 0}
	vm.Scope = vm.TopScope
	vm.Frame = vm.TopFrame
	return vm
}

func (vm *VM) Trace(fm string, args ... interface{}) {
	if vm.Tracer != nil {
		vm.Tracer.Trace(*vm, fm, args...)
	}
}

func (vm *VM) PushNewFrame(position *Position) *Frame {	
	frame := NewFrame(vm.Frame, position)
	vm.Trace("PushFrame %v->%v\n", vm.Frame, frame)
	vm.Frame = frame
	return frame
}

func (vm *VM) PushNewScope() *Scope {
	scope := NewScope(vm.Scope)
	vm.Scope = scope
	return scope
}

func (vm *VM) Return(results ...Value) []Value {
	return results
}


func (vm *VM) PopFrame() *Frame {
	oldFrame := vm.Frame
	vm.Trace("PopFrame %v->%v\n", vm.Frame, vm.Frame.parent)
	if (vm.Frame != vm.TopFrame) && (vm.Frame.parent != nil) {
		frame := vm.Frame
		vm.Frame = frame.parent
		// Copy frame results up.
		vm.Frame.returned = oldFrame.returned
		vm.Frame.failed = oldFrame.failed
		vm.Frame.results = oldFrame.results
		return frame
	}
	return nil
}

func (vm *VM) PopScope() *Scope {
	if (vm.Scope != vm.TopScope) && (vm.Scope.parent != nil) {
		scope := vm.Scope
		vm.Scope = scope.parent
		return scope
	}
	return nil
}

func (block * BlockValue) Call(vm *VM, arguments ...Value) []Value {
    ast := block.Ast
    // Now, don't run the block itself but the Statements node
    // that should be in it.
    children := ast.Children()
    if len(children) < 1 {
        return Fail(fmt.Errorf("Block has no statements."))
    } 
    if len(children) > 1 {
        return Fail(fmt.Errorf("Block has too many statements."))
    } 
    statements := children[0]
	arr := vm.RunAst(*statements, arguments...)
	return arr
}

func (builtin * BuiltinValue) Call(vm *VM, arguments ...Value) []Value {
	err := builtin.signature.TypeCheck(arguments...)
	if err != nil { 
		return Fail(ErrorValue{err})
	}
    handler := builtin.Handler
	return handler.Call(vm, arguments...)
}


func (vm *VM) AddTrace(err error) error {
	res := ""
	for frame := vm.Frame; frame != nil; frame = frame.parent {
		if frame.position == nil {
			res = fmt.Sprintf("%s\nIn frame %v", res, frame)
		} else {
			res = fmt.Sprintf("%s\nIn %s", res, frame.position.String())
		}
	}
	return fmt.Errorf("%s: %s", res, err)
}

func (vm *VM) CallCallable(callable Callable, arguments ...Value) []Value {
	defer vm.PopScope()
	defer vm.PopFrame()
	vm.PushNewFrame(callable.Position())
	vm.PushNewScope()
	result := callable.Call(vm, arguments...)
	return result
}

func (vm *VM) CallNamed(name string, arguments ...Value) []Value {
	value := vm.Lookup(name)
	if value == nil {
		return ReturnError(vm.AddTrace(NewErrorValuef("Cannot call %s: not found.", name)))
	}
	
	if callable, ok := value.(Callable) ; ok {
		return vm.CallCallable(callable, arguments...)
	} else {
		return ReturnError(vm.AddTrace(NewErrorValuef("Cannot call %s: %v. Not callable", name, value)))
	}
}

/*
func (vm * VM) CallNamedFramed(name string, arguments ...) []Value {
	frame := vm.PushNewFrame()

}
*/

// ScopeUp Returns the levelth scope up from the current one where 0 is the 
// current scope. Returns the toplevel scope if l is greater than the current
// scope stack depth.
func (vm * VM) ScopeUp(level int) *Scope {
	scope := vm.Scope
	for now := 0; now < level; now++ {
		if scope.parent == nil {
			return scope
		}
		scope = scope.parent
	}
	return scope
}

// RegisterTop registers a value at top level scope.
func (vm *VM) RegisterTop(name string, value Value) Value {
	scope := vm.TopScope
	return scope.Register(name, value)
}

// RegisterUp registers in level scopes up from the current scope,
// or at toplevel if the level is greater than the total depth
func (vm *VM) RegisterUp(name string, value Value, level int) Value {
	scope := vm.ScopeUp(level)	
	return scope.Register(name, value)
}

func (vm *VM) Register(name string, value Value) Value {
	return vm.Scope.Register(name, value)
}

func (vm *VM) RegisterCover(name string, level int) *CoverValue {
	value := NewCoverValue(name)
	vm.RegisterUp(name, value, level)
	return value
}

func (vm *VM) RegisterBuiltin(name string, handler Handler) *BuiltinValue {
	value := NewBuiltinValue(name, handler)
	vm.Register(name, value)
	return value
}

func (vm *VM) RegisterDefined(name string, signature Signature, block *BlockValue, level int) *DefinedValue {
	value := NewDefinedValue(name, signature, block)
	vm.RegisterUp(name, value, level)
	return value
}

// RegisterBuiltinWithHelp
func (vm *VM) RegisterBuiltinWithHelp(name string, handler Handler, help string) *BuiltinValue {
	res := vm.RegisterBuiltin(name, handler)
	vm.SetHelp(name, help)
	return res
}

func (vm *VM) Fail() {
	vm.Frame.failed = true
}

func (vm *VM) RunAst(ast Ast, args ...Value) []Value {
    var result []Value
    /*pos := ast.Token().Position
    vm.PushNewFrame(&pos)
    defer vm.PopFrame()
    */ 
    // vm.Logf("RunAst: %s\n", ast.Kind().String())
    // Leaf nodes, both declared and in practice are self evaluating.
    if ast.Kind().IsLeaf() || ast.CountChildren() < 1 {
        result = ast.Eval(vm)
        if vm.Frame.returned || vm.Frame.failed {
            result = vm.Frame.results
            vm.Frame.returned = false
            vm.Frame.failed = false
        }
    } else {
        var subResult = []Value{}
        // Depth first recursion.
        for i, child := range ast.Children() {
            sub := vm.RunAst(*child)
            subResult = append(subResult, sub...)
            vm.Trace("RunAst: %d %v %v %v\n", i, child, sub, vm.Frame)
            /*
            if frame.failed && frame.parent != nil {
                // XXX failures are like panics and propagate up the call tree
                * // Or should they? 
                frame.parent.failed = true
                frame.parent.results = frame.results 
            }
            */

            if vm.Frame.returned || vm.Frame.failed {
                subResult = vm.Frame.results
                vm.Frame.returned = false
                vm.Frame.failed = false
                break;
            }
        }
        // vm.Logf("RunAst subResult: %v\n", subResult) 
        result = ast.Eval(vm, subResult...)
    }
    // vm.Logf("RunAst result: %v\n", result) 
	return result
}


func (vm *VM) DefinedHelpers() []Helper {
	return vm.Scope.DefinedHelpers()
}

func (vm * VM) BackTraceFrames() []*Frame {
	bt := []*Frame{}
		
	for frame := vm.Frame ; frame.parent != nil ; frame = frame.parent	 {
		bt = append(bt, frame)
	}
			
	return bt
}

func (vm * VM) BackTracePositions() []*Position {
	bt := []*Position{}
		
	for frame := vm.Frame ; frame.parent != nil ; frame = frame.parent	 {
		bt = append(bt, frame.position)
	}
			
	return bt
}

func (vm * VM) BackTraceStrings() []string {
	bt := []string{}
		
	for frame := vm.Frame ; frame.parent != nil ; frame = frame.parent	 {
		bt = append(bt, frame.position.String())
	}
			
	return bt
}

func (vm * VM) BackTrace() string {
	return strings.Join(vm.BackTraceStrings(), "\n")
}