vm.go

// Package vm implements a simple stack-based virtual machine.
//
// We're constructed with a set of opcodes, and we process those forever,
// or until we hit a `return` statement which terminates the program.
//
// As well as a series of opcodes to execute we're also given a set
// of constants to work with.  These are loaded to the stack on-demand,
// so they can be manipulated.
package vm

import (
	"context"
	"encoding/binary"
	"fmt"
	"math"
	"reflect"
	"strings"
	"time"
	"unicode/utf8"

	"github.com/skx/evalfilter/v2/code"
	"github.com/skx/evalfilter/v2/environment"
	"github.com/skx/evalfilter/v2/object"
	"github.com/skx/evalfilter/v2/stack"
)

// BytecodeVisitor is the function-signature of the callbackup function which
// can be invoked to iterate over our generated bytecode.
//
// The callback function can be used via the `WalkBytecode` method, and the
// return values should make sense:  If there is an error then that is returned
// otherwise the bool-value will control whether the iteration continues,
// return true to keep walking, and false to abort the process.
type BytecodeVisitor func(offset int, instruction code.Opcode, argument interface{}) (bool, error)

// True is our global "true" object.
var True = &object.Boolean{Value: true}

// False is our global "false" object.
var False = &object.Boolean{Value: false}

// Null is our global "null" object.
var Null = &object.Null{}

// Void is our global "void" object.
var Void = &object.Void{}

// VM is the structure which holds our state.
type VM struct {

	// bytecode contains the actual series of instructions we'll execute.
	bytecode code.Instructions

	// constants is an array holding constants which were found in
	// the script-source.  These constants include string-literals,
	// numeric-literals, boolean values as well as variable names, the
	// names of functions, and references to object/map values.
	//
	// constants are treated as atoms, so they are unique.
	constants []object.Object

	// context is passed to us from our evalfilter, and can be
	// used by callers to implement timeouts.
	context context.Context

	// debug can be enabled to dump our execution-log as we run.
	debug bool

	// environment holds the environment, which will allow variables
	// and functions to be get/set.
	environment *environment.Environment

	// fields contains the contents of all the fields in the object
	// or map we're executing against.  We discover these via reflection
	// at run-time.
	//
	// Reflection is slow so the map here is used as a cache, avoiding
	// the need to reparse the same object multiple times.
	fields map[string]object.Object

	// functions that are defined in our scripting language
	functions map[string]environment.UserFunction

	// stack holds a pointer to our stack-object.
	//
	// We're a stack-based virtual machine so this is used for
	// much of our internal implementation.
	stack *stack.Stack
}

// New constructs a new virtual machine.
//
// If the value `OPTIMIZE` exists inside the environment we're passed
// we'll also run a series of simple optimizer steps.  These are naive,
// but do speedup carefully constructed test cases.
func New(constants []object.Object, bytecode code.Instructions, functions map[string]environment.UserFunction, env *environment.Environment) *VM {

	// If we have a `DEBUG` environment then we enable debugging.
	_, debug := env.Get("DEBUG")

	// If we have "OPTIMIZE" set then we optimize our bytecode.
	//
	// We don't need to store this flag anywhere, we'll just run
	// the optimizer immediately.
	_, optimize := env.Get("OPTIMIZE")

	// Create the machine
	vm := &VM{
		bytecode:    bytecode,
		constants:   constants,
		debug:       debug,
		environment: env,
		functions:   functions,
		stack:       stack.New(),
	}

	// Set a default context
	ctx := context.Background()
	vm.SetContext(ctx)

	// Optimize the bytecode, if we should.
	if optimize {

		// Run the optimization, which will return the
		// number of bytecode instructions "saved" or
		// reduced/removed.
		vm.optimizeBytecode()

		//
		// Now functions
		//
		tmp := make(map[string]environment.UserFunction)
		for name, fun := range functions {

			// Save the main bytecode away
			safe := vm.bytecode

			// Replace it with the bytecode from the function
			vm.bytecode = fun.Bytecode

			// Tweak it
			saved := vm.optimizeBytecode()

			if debug && optimize {
				fmt.Printf("Bytecode optimizer saved %d bytes for function %s\n", saved, name)
			}

			// Save it away
			fun.Bytecode = vm.bytecode
			tmp[name] = fun

			// And reset the saved vm-bytecode
			vm.bytecode = safe
		}
		vm.functions = tmp
	}

	return vm
}

// SetContext allows a context to be used as our virtual machine is
// running. This is most used to allow our caller to setup a
// timeout/deadline which will avoid denial-of-service problems if
// user-supplied script(s) contain infinite loops.
func (vm *VM) SetContext(ctx context.Context) {
	vm.context = ctx
}

// Run launches our virtual machine, interpreting the bytecode-program we were
// constructed with.
//
// We terminate when we hit a return-operation, or if we ever hit the end of
// the supplied bytecode.  As programs can contain flow-control operation
// it is certainly possible they will never return.
//
// (Our compiler only implements the 'while' loop for control-flow, but it
// is possible  a hand-created program could build such a things via the
// instruction-set.)
func (vm *VM) Run(obj interface{}) (object.Object, error) {

	//
	// Sanity-check the bytecode program is non-empty
	//
	if len(vm.bytecode) < 1 {
		return nil, fmt.Errorf("the bytecode program is empty")
	}

	//
	// Make an empty map to store field/map contents.
	//
	vm.fields = make(map[string]object.Object)

	//
	// When built-in functions are invoked their return value is stored
	// upon the stack.  Usually this is OK because the return value will
	// be used for something, and thus popped-off.
	//
	// However it is possible that user-added functions place their
	// return value upon the stack, where it is never used.  This will
	// cause the stack to needlessly grow, so we ensure that we
	// reset it between runs here to avoid unbounded growth.
	//
	// (This used to be the case with the built-in functions `print`
	// and `printf`.  They would always store a value upon the stack
	// which no user would ever test/use/care-about.  This was resolved
	// via the addition of the &object.Void{} type.   However we
	// cannot assume everybody remember to use that.)
	//
	vm.stack.Clear()

	//
	// Instruction pointer and length of bytecode.
	//
	ip := 0
	ln := len(vm.bytecode)

	//
	// Loop over all the bytecode.
	//
	// NOTE: Our instruction-set supports control-flow, so it
	// is possible this function will run forever, and never terminate.
	// This is why we allow `SetContext` to setup a timeout-period.
	//
	for ip < ln {

		//
		// We've been given a context, which we'll test at every
		// iteration of our main-loop.
		//
		// This is a little slow and inefficient, but we need
		// to allow our execution to be time-limited.
		//
		select {
		case <-vm.context.Done():
			return &object.Null{},
				fmt.Errorf("timeout during execution")
		default:
			// nop
		}

		//
		// Get the next opcode
		//
		op := code.Opcode(vm.bytecode[ip])

		//
		// Find out how long it is.
		//
		opLen := code.Length(op)

		//
		// If the opcode is more than a single byte long
		// we read the argument here.
		//
		opArg := 0
		if opLen > 1 {

			//
			// Note in the future we might have to cope
			// with opcodes with more than a single argument,
			// and they might be different sizes.
			//
			opArg = int(binary.BigEndian.Uint16(vm.bytecode[ip+1 : ip+3]))
		}

		if vm.debug {
			fmt.Printf("\n\tStack: [%s]\n",
				strings.Join(vm.stack.Export(), ", "))

			if opLen > 1 {
				fmt.Printf("%04d\t%s\t%04d\n", ip, code.String(op), opArg)
			} else {
				fmt.Printf("%04d\t%s\n", ip, code.String(op))
			}

		}

		switch op {

		// NOP
		case code.OpNop:
			// NOP should only be seen if we're running
			// an unoptimized / partially optimized program.

			// Store an integer upon the stack
		case code.OpPush:
			vm.stack.Push(&object.Integer{Value: int64(opArg)})

			// Lookup variable/field, by name
		case code.OpConstant:

			if opArg >= len(vm.constants) {
				return nil, fmt.Errorf("access to constant which doesn't exist")
			}

			// move the contents of a constant onto the stack
			vm.stack.Push(vm.constants[opArg])

			// Lookup variable/field, by name
		case code.OpLookup:

			if opArg >= len(vm.constants) {
				return nil, fmt.Errorf("access to constant which doesn't exist")
			}

			// Get the name.
			name := vm.constants[opArg].Inspect()

			// Lookup the value.
			val := vm.lookup(obj, name)
			vm.stack.Push(val)

			// Setup a local variable, by name
		case code.OpLocal:
			name, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}

			// now set the value
			vm.environment.SetLocal(name.Inspect(), Null)

			// Set a variable by name
		case code.OpSet:

			var name object.Object
			var val object.Object
			var err error
			name, err = vm.stack.Pop()
			if err != nil {
				return nil, err
			}
			val, err = vm.stack.Pop()
			if err != nil {
				return nil, err
			}

			vm.environment.Set(name.Inspect(), val)

			// maths & comparisons
		case code.OpAdd, // addition
			code.OpSub,          // subtraction
			code.OpMul,          // multiplication
			code.OpDiv,          // division
			code.OpMod,          // modulus
			code.OpPower,        // power
			code.OpLess,         // comparison: <
			code.OpLessEqual,    // comparison: <=
			code.OpGreater,      // comparison: >
			code.OpGreaterEqual, // comparison: >=
			code.OpEqual,        // comparison: ==
			code.OpNotEqual,     // comparison: !=
			code.OpMatches,      // regexp match
			code.OpNotMatches,   // regexp negative match
			code.OpAnd,          // logical AND
			code.OpOr,           // logical OR
			code.OpArrayIn:      // array membership test

			// Run the test, error gets returned, otherwise
			// we're done.
			err := vm.executeBinaryOperation(op)
			if err != nil {
				return nil, err
			}

			// Store an array
		case code.OpArray:

			// The argument contains the number of
			// array elements we're going to expect
			// to be present upon the stack.

			// Make the array of the appropriate size
			elements := make([]object.Object, opArg)

			// Add on each entry.
			for opArg > 0 {
				var err error
				elements[opArg-1], err = vm.stack.Pop()
				if err != nil {
					return nil, err
				}
				opArg--
			}

			// Construct the actual array and add to the stack
			arr := &object.Array{Elements: elements}
			vm.stack.Push(arr)

			// Store a hash
		case code.OpHash:

			hashedPairs := make(map[object.HashKey]object.HashPair)

			for i := 0; i < opArg; i += 2 {

				value, err := vm.stack.Pop()
				if err != nil {
					return nil, err
				}

				key, err := vm.stack.Pop()
				if err != nil {
					return nil, err
				}

				pair := object.HashPair{Key: key, Value: value}

				hashKey, ok := key.(object.Hashable)
				if !ok {
					return nil, fmt.Errorf("unusable as hash key: %s", key.Type())
				}

				hashedPairs[hashKey.HashKey()] = pair
			}
			hash := &object.Hash{Pairs: hashedPairs}
			vm.stack.Push(hash)

			// Case statement
		case code.OpCase:
			caseVal, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}
			val, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}

			// Is this a literal match
			if val.Type() == caseVal.Type() &&
				(val.Inspect() == caseVal.Inspect()) {
				vm.stack.Push(True)
			} else if caseVal.Type() == object.REGEXP {

				// Horrid - invoke Matches() to run the test.
				args := []object.Object{val, caseVal}
				fn, ok := vm.environment.GetFunction("match")
				if !ok {
					return nil, fmt.Errorf("failed to lookup match-function")
				}
				out := fn.(func(args []object.Object) object.Object)
				ret := out(args)
				vm.stack.Push(ret)

			} else {
				vm.stack.Push(False)
			}

			// Array/String index
		case code.OpIndex:
			index, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}
			left, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}

			err = vm.executeIndexExpression(left, index)
			if err != nil {
				return nil, err
			}

			// !true -> false
		case code.OpBang:

			err := vm.executeBangOperator()
			if err != nil {
				return nil, err
			}

			// -1
		case code.OpMinus:
			err := vm.executeMinusOperator()
			if err != nil {
				return nil, err
			}

			// square root
		case code.OpSquareRoot:
			err := vm.executeSquareRoot()
			if err != nil {
				return nil, err
			}

			// Boolean literal
		case code.OpTrue:
			vm.stack.Push(True)

		case code.OpVoid:
			vm.stack.Push(Void)

			// Boolean literal
		case code.OpFalse:
			vm.stack.Push(False)

			// return from script
		case code.OpReturn:
			result, err := vm.stack.Pop()
			return result, err

			// flow-control: unconditional jump
		case code.OpJump:

			// NOTE: We reduce the offset, because
			// at the end of our loop we increment
			// it again..

			ip = opArg - opLen

			if opArg >= len(vm.bytecode) {
				return nil, fmt.Errorf("instruction pointer is out of bounds")
			}

			// flow-control: jump if stack contains non-true
		case code.OpJumpIfFalse:

			condition, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}

			// If the condition evaluated to a non-true
			// then we change the IP.
			if !condition.True() {

				// NOTE: We reduce the offset, because
				// at the end of our loop we increment
				// it again..

				ip = opArg - opLen

				if opArg >= len(vm.bytecode) {
					return nil, fmt.Errorf("instruction pointer is out of bounds")
				}
			}

			// function-call: This is messy.
			//
			// Handles builtins and user-defined functions.
		case code.OpCall:

			// The OpCall instruction is followed by an
			// argument describing the number of args the
			// function we're calling should be invoked with.

			// get the name of the function from the stack.
			fName, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}
			name := fName.Inspect()

			//
			// The argument to the call-instruction is the
			// number of arguments to pass to the function
			// we're to invoke.
			//
			// Of course these are in reverse.
			//
			// Create an array and pop each stack-argument
			// off into the correct location.
			//
			fnArgs := make([]object.Object, opArg)
			for opArg > 0 {
				fnArgs[opArg-1], err = vm.stack.Pop()
				if err != nil {
					return nil, fmt.Errorf("attempting to call function %s failed - %s", name, err.Error())
				}
				opArg--
			}

			// Get the function we're to invoke.
			fn, ok := vm.environment.GetFunction(name)
			if ok {

				// Cast the function & call it
				out := fn.(func(args []object.Object) object.Object)
				ret := out(fnArgs)

				// store the result back on the stack - unless
				// it's a weird one.
				if ret.Type() != object.VOID {
					vm.stack.Push(ret)
				}
				break
			}

			// Function isn't a built-in, so now we need to see
			// if it is a user-defined function.
			val, ok2 := vm.functions[name]
			if !ok2 {
				return nil, fmt.Errorf("the function %s does not exist", name)
			}

			// Save IP + bytecode
			oldIP := ip
			oldBytecode := vm.bytecode
			oldStack := vm.stack

			vm.stack = stack.New()
			vm.environment.AddScope()

			// switch so that we're interpreting the bytecode
			// of the compiled function-body.
			vm.bytecode = val.Bytecode

			// Sanity-check we have enough arguments
			if len(val.Arguments) != len(fnArgs) {
				return nil, fmt.Errorf("mismatch in argument-counts for %s, expected %d but got %d", name, len(val.Arguments), len(fnArgs))
			}

			// Now for each arg we set the value
			for i, name := range val.Arguments {
				vm.environment.SetLocal(name, fnArgs[i])
			}

			// Run ourselves against that new bytecode.
			//
			// This is a bit horrid.
			out, err := vm.Run(obj)

			// Did we get an error?  If so return it
			if err != nil {
				return nil, err
			}

			// Otherwise we're going to keep running from
			// where we left off - resetting the state of
			// our stack, instruction-pointer, and bytecode.
			ip = oldIP
			vm.bytecode = oldBytecode
			vm.stack = oldStack

			// Put the return-value on the stack
			if out.Type() != object.VOID {
				vm.stack.Push(out)
			}

			// Drop the scope which means function-arguments
			// are dropped.
			err = vm.environment.RemoveScope()
			if err != nil {
				return nil, err
			}

			// reset the state of an object which is to be iterated upon
		case code.OpIterationReset:

			// Create a scoped environment
			vm.environment.AddScope()
			// get object we're iterating over..
			out, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}

			// Cast it to the interface.
			helper, ok := out.(object.Iterable)
			if !ok {
				return nil, fmt.Errorf("%s object doesn't implement the Iterable interface", out.Type())
			}

			// Reset it, and place back upon the stack.
			helper.Reset()
			vm.stack.Push(out)

			// Iterate over an object that implements the Iterable interface.
		case code.OpIterationNext:
			//
			// There should be three values on the stack
			//
			//   variable name
			//   index name
			//   item
			//
			varName, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}
			idxName, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}
			obj, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}

			// Ensure that it is an iterable thing.
			helper, ok := obj.(object.Iterable)
			if !ok {
				return nil, fmt.Errorf("%s object doesn't implement the Iterable interface", obj.Type())
			}

			// Get the next value, it's index, and a
			// success/fail result.
			ret, idx, ok := helper.Next()

			if ok {

				// Set the index + name
				vm.environment.SetLocal(varName.Inspect(), ret)

				idxName := idxName.Inspect()
				if idxName != "" {
					vm.environment.SetLocal(idxName, idx)
				}

				// Push the iterable object back upon the
				// stack for the next loop.
				vm.stack.Push(obj)

				// And also push `True` so our loop will
				// continue.
				vm.stack.Push(True)
			} else {

				// The iteration is over.
				//
				// So next time we'll fall-through to after
				// the foreach-loop.
				//
				vm.stack.Push(False)

				// Remove our scoped environment now to
				// discard the name/index values that
				// might have been set.
				err := vm.environment.RemoveScope()
				if err != nil {
					return nil, err
				}

			}

			// Create an array of numbers.
		case code.OpRange:
			var min object.Object
			var max object.Object
			var err error
			max, err = vm.stack.Pop()
			if err != nil {
				return nil, err
			}
			min, err = vm.stack.Pop()
			if err != nil {
				return nil, err
			}

			if min.Type() != object.INTEGER {
				return nil, fmt.Errorf("argument for the start of the range must be an integer")
			}
			if max.Type() != object.INTEGER {
				return nil, fmt.Errorf("argument for the end of the range must be an integer")
			}

			// The actual min/max values we're going to range over.
			minI := min.(*object.Integer).Value
			maxI := max.(*object.Integer).Value

			if minI > maxI {
				return nil, fmt.Errorf("the start of a range must be smaller than the end")
			}

			// length
			l := maxI - minI + 1

			// holder for elements of the correct size
			elements := make([]object.Object, l)

			// Make the array
			var i int64
			i = 0
			for i < l {
				elements[i] = &object.Integer{Value: minI + i}
				i++
			}

			// Now store the elements
			arr := &object.Array{Elements: elements}
			vm.stack.Push(arr)

			// Increment the value of an object, by name, if the Increment
			// interface is implemented by it.
		case code.OpInc:

			if opArg >= len(vm.constants) {
				return nil, fmt.Errorf("access to constant which doesn't exist")
			}

			// Get the name of the variable whos' contents
			// we should increment.
			name := vm.constants[opArg].Inspect()

			// Lookup the current value of that object.
			val := vm.lookup(obj, name)

			// Can we use our interface?
			helper, ok := val.(object.Increment)
			if !ok {
				return nil, fmt.Errorf("%s object doesn't implement the Increment() interface", val.Type())
			}

			// Mutate & store
			helper.Increase()
			vm.environment.Set(name, val)

			// OpInc follows OpLookup, so we can drop the value we were given
			_, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}

			// Decrement the value of an object, by name, if the Decrement
			// interface is implemented by it.
		case code.OpDec:

			if opArg >= len(vm.constants) {
				return nil, fmt.Errorf("access to constant which doesn't exist")
			}

			// Get the name of the variable whos' contents
			// we should decrement.
			name := vm.constants[opArg].Inspect()

			// Lookup the current value of that object.
			val := vm.lookup(obj, name)

			// Can we use our interface?
			helper, ok := val.(object.Decrement)
			if !ok {
				return nil, fmt.Errorf("%s object doesn't implement the Decrement() interface", val.Type())
			}

			// Mutate & store
			helper.Decrease()
			vm.environment.Set(name, val)

			// OpDec follows OpLookup, so we can drop the value we were given
			_, err := vm.stack.Pop()
			if err != nil {
				return nil, err
			}

			// NOP
		case code.OpPlaceholder:

			// Unknown opcode
		default:
			return nil, fmt.Errorf("unhandled opcode: %v %s", op, code.String(op))
		}

		ip += opLen
	}

	//
	// If we get here we've hit the end of the bytecode, and we
	// didn't encounter a return-instruction.
	//
	// In the case where a user is running the script as a filter
	// then a missing return code is probably going to be treated
	// as a "false" return.  But the caller can decide that.
	//
	return Null, nil
}

// inspectObject discovers the names/values of all structure fields, or
// map contents.
//
// This method is called the first time any reference is made to a field
// value - which means we don't eat the cost unless we need it, and we
// don't have to call reflection more than once.  (Reflection is s-l-o-w.)
func (vm *VM) inspectObject(obj interface{}) {

	//
	// If the reference is nil we have nothing to walk.
	//
	if obj == nil {
		return
	}

	//
	// Get the value, be it a "thing", or a pointer to a thing.
	//
	val := reflect.Indirect(reflect.ValueOf(obj))

	//
	// Is this a map?
	//
	if val.Kind() == reflect.Map {

		//
		// Get all keys in the map.
		//
		for _, key := range val.MapKeys() {

			// The name of the key.
			name := key.Interface().(string)

			// The actual thing inside it
			field := val.MapIndex(key).Elem()

			// Convert to an object
			ret := vm.primitiveToObject(field)

			// Store it in our map
			vm.fields[name] = ret
		}
		return
	}

	//
	// OK this is an object, so we walk over the fields within it.
	//
	for i := 0; i < val.NumField(); i++ {

		// Get the field
		field := val.Field(i)

		// Get the name
		typeField := val.Type().Field(i)
		name := typeField.Name

		// Convert the value to one of our objects
		ret := vm.primitiveToObject(field)

		// Store it in our map
		vm.fields[name] = ret
	}
}

// convert a primitive into one of our internal objects.
func (vm *VM) primitiveToObject(field reflect.Value) object.Object {

	var ret object.Object

	//
	// Time gets special handling
	//
	timeKind := reflect.TypeOf(time.Time{}).Kind()

	//
	// Invalid value?  Return null
	//
	if !field.IsValid() {
		return &object.Null{}
	}

	switch field.Kind() {

	case reflect.Map:
		ret = vm.createHash(field)
	case reflect.Slice:
		ret = vm.createArrayFromSlice(field)
	case reflect.Int, reflect.Int64:
		ret = &object.Integer{Value: field.Int()}
	case reflect.Float32, reflect.Float64:
		ret = &object.Float{Value: field.Float()}
	case reflect.String:
		ret = &object.String{Value: field.String()}
	case reflect.Bool:
		ret = &object.Boolean{Value: field.Bool()}
	case timeKind:
		time, ok := field.Interface().(time.Time)
		if ok {
			ret = &object.Integer{Value: time.Unix()}
		}
	default:
		fmt.Printf("Failed to reflect on %T\n", field.Interface())
	}

	return ret
}

// create one of our internal hash-objects via reflection.
//
// This may well recurse.
func (vm *VM) createHash(field reflect.Value) object.Object {
	hashedPairs := make(map[object.HashKey]object.HashPair)

	for _, key := range field.MapKeys() {

		// Get the key value - note this supports way more
		// than we allow here.  (As not all of our objects
		// can be used as hash-keys.)
		k := vm.primitiveToObject(key)

		// The actual thing inside it.
		val := field.MapIndex(key).Elem()

		// Get the value.
		v := vm.primitiveToObject(val)

		pair := object.HashPair{Key: k, Value: v}
		hashedPairs[k.(object.Hashable).HashKey()] = pair
	}

	return &object.Hash{Pairs: hashedPairs}
}

// createArrayFromSlice creates an object.Array value from the
// given object/map slice
//
// This may well recurse.
func (vm *VM) createArrayFromSlice(field reflect.Value) object.Object {

	// Elements we've found
	var el []object.Object

	// Find the length of the slice
	l := field.Len()

	// For each entry
	for i := 0; i < l; i++ {

		// Cast the array-member to an interface
		in := field.Index(i).Interface()

		//
		// Now we're in horrible-land
		//
		// We want to work out the type of the
		// array-member.  Of course every member
		// will have the same type, unless we're
		// in the case of an array of interfaces.
		//
		// The following code will try to cast
		// to all "reasonable" values, which will
		// cover either case.
		//
		// It is still horrible though, and that
		// should be noted.
		//

		// Is it a string?
		s, ok := in.(string)
		if ok {
			el = append(el, &object.String{Value: s})
			continue
		}

		// Is it a bool?
		b, ok := in.(bool)
		if ok {
			el = append(el, &object.Boolean{Value: b})
			continue
		}

		// is it a float?
		f, ok := in.(float32)
		if ok {
			el = append(el, &object.Float{Value: float64(f)})
			continue
		}
		ff, ok := in.(float64)
		if ok {
			el = append(el, &object.Float{Value: ff})
			continue
		}

		// is it an integer?
		d, ok := in.(int)
		if ok {
			el = append(el, &object.Integer{Value: int64(d)})
			continue
		}
		dd, ok := in.(int32)
		if ok {
			el = append(el, &object.Integer{Value: int64(dd)})
			continue
		}
		ddd, ok := in.(int64)
		if ok {
			el = append(el, &object.Integer{Value: ddd})
			continue
		}

		// Is it a time value?
		tm, ok := in.(time.Time)
		if ok {
			el = append(el, &object.Integer{Value: tm.Unix()})
			continue
		}

		fmt.Printf("Failed to convert array-member to object")
	}

	return &object.Array{Elements: el}
}

// Execute an operation against two arguments, i.e "foo == bar", "2 + 3", etc.
//
// This is a crazy-big function, because we have to cope with different operand
// types and operators.
func (vm *VM) executeBinaryOperation(op code.Opcode) error {
	var left object.Object
	var right object.Object
	var err error

	right, err = vm.stack.Pop()
	if err != nil {
		return err
	}
	left, err = vm.stack.Pop()
	if err != nil {
		return err
	}

	switch {
	case left.Type() == object.INTEGER && right.Type() == object.INTEGER:
		return vm.evalIntegerInfixExpression(op, left, right)
	case left.Type() == object.FLOAT && right.Type() == object.FLOAT:
		return vm.evalFloatInfixExpression(op, left, right)
	case left.Type() == object.FLOAT && right.Type() == object.INTEGER:
		return vm.evalFloatIntegerInfixExpression(op, left, right)
	case left.Type() == object.INTEGER && right.Type() == object.FLOAT:
		return vm.evalIntegerFloatInfixExpression(op, left, right)
	case left.Type() == object.STRING && right.Type() == object.STRING:
		return vm.evalStringInfixExpression(op, left, right)
	case left.Type() == object.STRING && right.Type() == object.REGEXP:
		return vm.evalStringRegexpExpression(op, left, right)
	case op == code.OpAnd:
		// if left is false skip right
		if !left.True() {
			vm.stack.Push(False)
			return nil
		}
		if right.True() {
			vm.stack.Push(True)
		} else {
			vm.stack.Push(False)
		}
		return nil
	case op == code.OpOr:
		// if left is true skip right
		if left.True() {
			vm.stack.Push(True)
			return nil
		}
		if right.True() {
			vm.stack.Push(True)
		} else {
			vm.stack.Push(False)
		}
		return nil
	case op == code.OpArrayIn:

		// Ensure we're invoked with an array
		if right.Type() != object.ARRAY {
			return fmt.Errorf("operand for 'in' must be an array, not %s", right.Type())
		}

		// Get the array.
		values := right.(*object.Array)

		// For each element ..
		for _, entry := range values.Elements {

			// If the type and values are equal then
			// the array DOES contain the value.
			if (left.Type() == entry.Type()) &&
				(left.Inspect() == entry.Inspect()) {
				vm.stack.Push(True)
				return nil
			}
		}

		// Examined all members of the array.  No match.
		vm.stack.Push(False)
		return nil

	case left.Type() == object.BOOLEAN && right.Type() == object.BOOLEAN:
		return vm.evalBooleanInfixExpression(op, left, right)
	case left.Type() != right.Type():
		return fmt.Errorf("type mismatch: %s %s %s",
			left.Type(), code.String(op), right.Type())
	default:
		return fmt.Errorf("unknown operator: %s %s %s",
			left.Type(), code.String(op), right.Type())
	}
}

// integer OP integer
func (vm *VM) evalIntegerInfixExpression(op code.Opcode, left, right object.Object) error {
	leftVal := left.(*object.Integer).Value
	rightVal := right.(*object.Integer).Value

	switch op {
	case code.OpAdd:
		vm.stack.Push(&object.Integer{Value: leftVal + rightVal})
	case code.OpSub:
		vm.stack.Push(&object.Integer{Value: leftVal - rightVal})
	case code.OpMul:
		vm.stack.Push(&object.Integer{Value: leftVal * rightVal})
	case code.OpDiv:
		if rightVal == 0 {
			return fmt.Errorf("attempted division by zero: %d / %d", leftVal, rightVal)
		}
		vm.stack.Push(&object.Integer{Value: leftVal / rightVal})
	case code.OpMod:
		vm.stack.Push(&object.Integer{Value: leftVal % rightVal})
	case code.OpPower:
		vm.stack.Push(&object.Integer{Value: int64(math.Pow(float64(leftVal), float64(rightVal)))})
	case code.OpLess:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal < rightVal))
	case code.OpLessEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal <= rightVal))
	case code.OpGreater:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal > rightVal))
	case code.OpGreaterEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal >= rightVal))
	case code.OpEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal == rightVal))
	case code.OpNotEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal != rightVal))
	default:
		return (fmt.Errorf("unknown operator: %s %s %s", left.Type(), code.String(op), right.Type()))
	}

	return nil
}

// float OP float
func (vm *VM) evalFloatInfixExpression(op code.Opcode, left, right object.Object) error {
	leftVal := left.(*object.Float).Value
	rightVal := right.(*object.Float).Value

	switch op {
	case code.OpAdd:
		vm.stack.Push(&object.Float{Value: leftVal + rightVal})
	case code.OpSub:
		vm.stack.Push(&object.Float{Value: leftVal - rightVal})
	case code.OpMul:
		vm.stack.Push(&object.Float{Value: leftVal * rightVal})
	case code.OpDiv:
		if rightVal == 0 {
			return fmt.Errorf("attempted division by zero: %f / %f", leftVal, rightVal)
		}
		vm.stack.Push(&object.Float{Value: leftVal / rightVal})
	case code.OpMod:
		vm.stack.Push(&object.Float{Value: float64(int(leftVal) % int(rightVal))})
	case code.OpPower:
		vm.stack.Push(&object.Float{Value: math.Pow(leftVal, rightVal)})
	case code.OpLess:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal < rightVal))
	case code.OpLessEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal <= rightVal))
	case code.OpGreater:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal > rightVal))
	case code.OpGreaterEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal >= rightVal))
	case code.OpEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal == rightVal))
	case code.OpNotEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal != rightVal))
	default:
		return (fmt.Errorf("unknown operator: %s %s %s", left.Type(), code.String(op), right.Type()))
	}

	return nil
}

// float OP int
func (vm *VM) evalFloatIntegerInfixExpression(op code.Opcode, left, right object.Object) error {
	leftVal := left.(*object.Float).Value
	rightVal := float64(right.(*object.Integer).Value)

	switch op {
	case code.OpAdd:
		vm.stack.Push(&object.Float{Value: leftVal + rightVal})
	case code.OpSub:
		vm.stack.Push(&object.Float{Value: leftVal - rightVal})
	case code.OpMul:
		vm.stack.Push(&object.Float{Value: leftVal * rightVal})
	case code.OpDiv:
		if rightVal == 0 {
			return fmt.Errorf("attempted division by zero: %f / %f", leftVal, rightVal)
		}
		vm.stack.Push(&object.Float{Value: leftVal / rightVal})
	case code.OpMod:
		vm.stack.Push(&object.Float{Value: float64(int(leftVal) % int(rightVal))})
	case code.OpPower:
		vm.stack.Push(&object.Float{Value: math.Pow(leftVal, rightVal)})
	case code.OpLess:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal < rightVal))
	case code.OpLessEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal <= rightVal))
	case code.OpGreater:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal > rightVal))
	case code.OpGreaterEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal >= rightVal))
	case code.OpEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal == rightVal))
	case code.OpNotEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal != rightVal))
	default:
		return (fmt.Errorf("unknown operator: %s %s %s", left.Type(), code.String(op), right.Type()))
	}

	return nil
}

// int OP float
func (vm *VM) evalIntegerFloatInfixExpression(op code.Opcode, left, right object.Object) error {
	leftVal := float64(left.(*object.Integer).Value)
	rightVal := right.(*object.Float).Value

	switch op {
	case code.OpAdd:
		vm.stack.Push(&object.Float{Value: leftVal + rightVal})
	case code.OpSub:
		vm.stack.Push(&object.Float{Value: leftVal - rightVal})
	case code.OpMul:
		vm.stack.Push(&object.Float{Value: leftVal * rightVal})
	case code.OpDiv:
		if rightVal == 0 {
			return fmt.Errorf("attempted division by zero: %f / %f", leftVal, rightVal)
		}
		vm.stack.Push(&object.Float{Value: leftVal / rightVal})
	case code.OpMod:
		vm.stack.Push(&object.Float{Value: float64(int(leftVal) % int(rightVal))})
	case code.OpPower:
		vm.stack.Push(&object.Float{Value: math.Pow(leftVal, rightVal)})
	case code.OpLess:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal < rightVal))
	case code.OpLessEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal <= rightVal))
	case code.OpGreater:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal > rightVal))
	case code.OpGreaterEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal >= rightVal))
	case code.OpEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal == rightVal))
	case code.OpNotEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(leftVal != rightVal))
	default:
		return (fmt.Errorf("unknown operator: %s %s %s", left.Type(), code.String(op), right.Type()))
	}

	return nil
}

// string OP string
func (vm *VM) evalStringInfixExpression(op code.Opcode, left object.Object, right object.Object) error {
	l := left.(*object.String)
	r := right.(*object.String)

	switch op {
	case code.OpEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(l.Value == r.Value))
	case code.OpNotEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(l.Value != r.Value))
	case code.OpGreaterEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(l.Value >= r.Value))
	case code.OpGreater:
		vm.stack.Push(vm.nativeBoolToBooleanObject(l.Value > r.Value))
	case code.OpLessEqual:
		vm.stack.Push(vm.nativeBoolToBooleanObject(l.Value <= r.Value))
	case code.OpLess:
		vm.stack.Push(vm.nativeBoolToBooleanObject(l.Value < r.Value))
	case code.OpAdd:
		vm.stack.Push(&object.String{Value: l.Value + r.Value})
	case code.OpArrayIn:
		if strings.Contains(r.Value, l.Value) {
			vm.stack.Push(True)
		} else {
			vm.stack.Push(False)
		}
	default:
		return (fmt.Errorf("unknown operator: %s %s %s", left.Type(), code.String(op), right.Type()))
	}

	return nil
}

func (vm *VM) evalStringRegexpExpression(op code.Opcode, left object.Object, right object.Object) error {
	l := left.(*object.String)
	r := right.(*object.Regexp)

	switch op {
	case code.OpMatches:
		args := []object.Object{l, r}
		fn, ok := vm.environment.GetFunction("match")
		if !ok {
			return (fmt.Errorf("failed to lookup match-function"))
		}
		out := fn.(func(args []object.Object) object.Object)
		ret := out(args)

		if ret.(*object.Boolean).Value {
			vm.stack.Push(True)
		} else {
			vm.stack.Push(False)
		}
	case code.OpNotMatches:
		args := []object.Object{l, r}
		fn, ok := vm.environment.GetFunction("match")
		if !ok {
			return (fmt.Errorf("failed to lookup match-function"))
		}
		out := fn.(func(args []object.Object) object.Object)
		ret := out(args)

		if ret.(*object.Boolean).Value {
			vm.stack.Push(False)
		} else {
			vm.stack.Push(True)
		}
	default:
		return (fmt.Errorf("unknown operator: %s %s %s", left.Type(), code.String(op), right.Type()))
	}

	return nil
}

// bool OP bool
func (vm *VM) evalBooleanInfixExpression(op code.Opcode, left object.Object, right object.Object) error {
	// convert the bools to strings.
	l := &object.String{Value: left.Inspect()}
	r := &object.String{Value: right.Inspect()}

	// then reuse our implementation, which will work
	// but might give some "interesting" results.
	//
	// e.g. "false < true"
	//
	return (vm.evalStringInfixExpression(op, l, r))
}

// Implement the "!" (prefix) operator.
func (vm *VM) executeBangOperator() error {
	operand, err := vm.stack.Pop()
	if err != nil {
		return err
	}

	switch operand {
	case True:
		vm.stack.Push(False)
	case False:
		vm.stack.Push(True)
	case Null:
		vm.stack.Push(True)
	default:
		vm.stack.Push(False)
	}
	return nil
}

// Allow negative numbers.
func (vm *VM) executeMinusOperator() error {
	operand, err := vm.stack.Pop()
	if err != nil {
		return err
	}
	var res object.Object

	switch obj := operand.(type) {
	case *object.Integer:
		res = &object.Integer{Value: -obj.Value}
	case *object.Float:
		res = &object.Float{Value: -obj.Value}
	default:
		return fmt.Errorf("unsupported type for negation: %s", operand.Type())
	}

	vm.stack.Push(res)
	return nil
}

// The square root operation is just too cute :).
func (vm *VM) executeSquareRoot() error {
	operand, err := vm.stack.Pop()
	if err != nil {
		return err
	}
	var res object.Object

	switch obj := operand.(type) {
	case *object.Integer:
		res = &object.Float{Value: math.Sqrt(float64(obj.Value))}
	case *object.Float:
		res = &object.Float{Value: math.Sqrt(obj.Value)}
	default:
		return fmt.Errorf("unsupported type for square-root: %s", operand.Type())
	}

	vm.stack.Push(res)
	return nil
}

// convert a native (go) boolean to an Object
func (vm *VM) nativeBoolToBooleanObject(input bool) *object.Boolean {
	if input {
		return True
	}
	return False
}

// lookup the name of the given field/map-member.
func (vm *VM) lookup(obj interface{}, name string) object.Object {

	//
	// Remove legacy "$" prefix, if present.
	//
	name = strings.TrimPrefix(name, "$")

	//
	// Look for this as a variable first, they take precedence.
	//
	if val, ok := vm.environment.Get(name); ok {
		return val
	}

	//
	// Now we assume this is a reference to a map-key, or
	// object member.
	//
	// If we've not discovered them then do so now
	//
	if len(vm.fields) == 0 {
		vm.inspectObject(obj)
	}

	//
	// Now perform the lookup
	//
	if cached, found := vm.fields[name]; found {
		return cached
	}

	//
	// If it was not found it is an unknown/unset value.
	//
	return Null
}

// executeIndexExpression performs a string/array indexing operation.
func (vm *VM) executeIndexExpression(left, index object.Object) error {

	// Check arguments
	if left.Type() != object.ARRAY && left.Type() != object.HASH && left.Type() != object.STRING {
		return fmt.Errorf("the index operator can only be applied to arrays, hashes, and strings, not %s", left.Type())
	}
	if left.Type() == object.HASH {
		return vm.executeHashIndex(left, index)
	}
	if index.Type() != object.INTEGER {
		return fmt.Errorf("index operator must be given an integer, not %s", index.Type())
	}

	// Get the index we should lookup
	idx := index.(*object.Integer).Value

	// Looking at a string?
	if left.Type() == object.STRING {

		str := left.(*object.String).Inspect()

		// Count the characters
		l := utf8.RuneCountInString(str)
		if idx < 0 || int(idx) > l {
			vm.stack.Push(Null)
			return nil
		}

		// Get the characters as an array of runes
		chars := []rune(str)

		// Now index
		val := &object.String{Value: string(chars[idx])}

		vm.stack.Push(val)
		return nil
	}

	// OK here we know we're dealing with an array.
	arrayObject := left.(*object.Array)

	// bounds-check
	max := int64(len(arrayObject.Elements) - 1)
	if idx < 0 || idx > max {
		vm.stack.Push(Null)
		return nil
	}

	// Return the appropriate object.
	vm.stack.Push(arrayObject.Elements[idx])
	return nil
}

func (vm *VM) executeHashIndex(hash, index object.Object) error {
	hashObject := hash.(*object.Hash)

	key, ok := index.(object.Hashable)
	if !ok {
		return fmt.Errorf("unusable as hash key: %s", index.Type())
	}

	pair, ok := hashObject.Pairs[key.HashKey()]
	if !ok {
		vm.stack.Push(Null)
		return nil
	}

	vm.stack.Push(pair.Value)
	return nil
}

// walkBytecode iterates over a block of bytecode, invoking the callback
// on every instruction.
//
// This is a helper used by WalkBytecode and WalkFunctionBytecode.
func (vm *VM) walkBytecodeHelper(bytecode code.Instructions, callback BytecodeVisitor) error {

	//
	// We're going to walk over the bytecode from start to finish.
	//
	ip := 0
	ln := len(bytecode)

	//
	// Walk the bytecode.
	//
	for ip < ln {

		//
		// Get the next opcode
		//
		op := code.Opcode(bytecode[ip])

		//
		// Find out how long it is.
		//
		opLen := code.Length(op)

		//
		// If the opcode is more than a single byte long we read the argument here.
		//
		opArg := 0
		if opLen > 1 {

			//
			// Note in the future we might have to cope
			// with opcodes with more than a single argument,
			// and they might be different sizes.
			//
			opArg = int(binary.BigEndian.Uint16(bytecode[ip+1 : ip+3]))
		}

		var err error
		var ret bool

		// Pass either the argument, or nil.
		if opLen > 1 {
			ret, err = callback(ip, op, opArg)
		} else {
			ret, err = callback(ip, op, nil)
		}

		// Error?  Then return that, and stop walking.
		if err != nil {
			return err
		}

		// The callback returned false?  Then stop walking.
		if !ret {
			return nil
		}

		ip += opLen
	}

	// No error, walk is complete.
	return nil
}

// WalkBytecode invokes the specified callbackup function upon every
// instruction in our bytecode program.
//
// This is primarily used for our optimizer, but it is also used
// for the implementation of the Dump command in our evalfilter
// package.
func (vm *VM) WalkBytecode(callback BytecodeVisitor) error {
	return (vm.walkBytecodeHelper(vm.bytecode, callback))
}

// WalkFunctionBytecode invokes the specified callbackup function upon every
// instruction in the bytecode corresponding to the named function.
//
// This is primarily used for the implementation of the Dump command in our
// evalfilter package.
func (vm *VM) WalkFunctionBytecode(name string, callback BytecodeVisitor) error {
	//
	// Get the function and test it exists
	//
	fun, ok := vm.functions[name]
	if !ok {
		return fmt.Errorf("function not found %s", name)
	}

	//
	// OK we found a function, walk the compiled bytecode.
	//
	return (vm.walkBytecodeHelper(fun.Bytecode, callback))
}