bytecode

Documentation

Overview

Package bytecode contains a custom bytecode compiler and virtual machine.

Initially, an Evy program is turned into a sequence of tokens by the [lexer]. Then, the parser generates an Abstract Syntax Tree (AST) from the tokens. The Compiler of this package walks the AST and writes the instructions to custom bytecode. For more on the AST refer to the parser package documentation.

The VM can read the bytecode and execute the encoded instructions, providing a runtime similar to the [evaluator]. The virtual machine is a straight-forward stack implementation that does not use any additional registers.

Index

• Constants
• Variables
• func Make(op Opcode, operands ...int) ([]byte, error)
• func ReadOperands(def *OpDefinition, ins Instructions) ([]int, int)
• func ReadUint16(ins Instructions) uint16
• type Bytecode
• type Compiler
  • func NewCompiler() *Compiler
  • func (c *Compiler) Bytecode() *Bytecode
  • func (c *Compiler) Compile(node parser.Node) error
• type Instructions
  • func (ins Instructions) String() string
• type OpDefinition
  • func Lookup(op Opcode) (*OpDefinition, error)
• type Opcode
• type Symbol
• type SymbolScope
• type SymbolTable
  • func NewSymbolTable() *SymbolTable
  • func (s *SymbolTable) Define(name string) Symbol
  • func (s *SymbolTable) Resolve(name string) (Symbol, bool)
• type VM
  • func NewVM(bytecode *Bytecode) *VM
  • func (vm *VM) Run() error

Constants

const (
	// StackSize defines an upper limit for the size of the stack.
	StackSize = 2048
	// GlobalsSize is the total number of globals that can be specified
	// in an evy program.
	GlobalsSize = 65536
)

Variables

var (
	// ErrInternal and errors wrapping ErrInternal report internal
	// errors of the VM that should not occur during normal
	// program execution.
	ErrInternal = errors.New("internal error")
	// ErrPanic and errors wrapping ErrPanic report runtime errors, such
	// as an index out of bounds or a stack overflow.
	ErrPanic = errors.New("user error")
	// ErrUnknownOpcode is returned when an unknown opcode is encountered.
	ErrUnknownOpcode = fmt.Errorf("%w: unknown opcode", ErrInternal)
)

var (
	// ErrUndefinedVar is returned when a variable name cannot
	// be resolved in the symbol table.
	ErrUndefinedVar = fmt.Errorf("%w: undefined variable", ErrPanic)
	// ErrUnknownOperator is returned when an operator cannot
	// be resolved.
	ErrUnknownOperator = fmt.Errorf("%w: unknown operator", ErrInternal)
	// ErrUnsupportedExpression is returned when an expression is not
	// supported by the compiler, this indicates an error in the compiler
	// itself, as all parseable evy expressions should be supported.
	ErrUnsupportedExpression = fmt.Errorf("%w: unsupported expression", ErrInternal)
)

var (
	// ErrStackOverflow is returned when the stack exceeds its size limit.
	ErrStackOverflow = fmt.Errorf("%w: stack overflow", ErrPanic)
	// ErrDivideByZero is returned when a division by zero would
	// produce an invalid result. In Golang, floating point division
	// by zero produces +Inf, and modulo by zero produces NaN.
	ErrDivideByZero = fmt.Errorf("%w: division by zero", ErrPanic)
)

Functions

func Make

func Make(op Opcode, operands ...int) ([]byte, error)

Make assembles and returns a single bytecode instruction out of an Opcode and an optional list of operands. An error will be returned if there is no definition for the provided Opcode.

func ReadOperands

func ReadOperands(def *OpDefinition, ins Instructions) ([]int, int)

ReadOperands will read from the provided Instructions based on the width of the provided OpDefinition. It returns the operands and the read offset inside the Instructions.

func ReadUint16

func ReadUint16(ins Instructions) uint16

ReadUint16 is exposed to allow reading without performing a Lookup to get an OpDefinition to pass to ReadOperands.

Types

type Bytecode

type Bytecode struct {
	Constants    []value
	Instructions Instructions
}

Bytecode represents raw evy bytecode.

type Compiler

type Compiler struct {
	// contains filtered or unexported fields
}

Compiler is responsible for turning a parsed evy program into bytecode.

func NewCompiler

func NewCompiler() *Compiler

NewCompiler returns a new compiler.

func (*Compiler) Bytecode

func (c *Compiler) Bytecode() *Bytecode

Bytecode renders the compiler instructions into Bytecode.

func (*Compiler) Compile

func (c *Compiler) Compile(node parser.Node) error

Compile accepts an AST node and renders it to bytecode internally.

type Instructions

type Instructions []byte

Instructions represents raw bytecode, which is composed of opcodes and an optional number of operands after each opcode.

func (Instructions) String

func (ins Instructions) String() string

String prints opcodes and their associated operands.

type OpDefinition

type OpDefinition struct {
	Name          string
	OperandWidths []int
}

OpDefinition defines a name and expected operand width for each OpCode.

func Lookup

func Lookup(op Opcode) (*OpDefinition, error)

Lookup returns an OpDefinition for the value of an Opcode, any unknown value will result in an error.

type Opcode

type Opcode byte

Opcode defines the type of operation to be performed when reading the bytecode.

const (
	// OpConstant defines a constant that will be referred to by index
	// in the bytecode.
	OpConstant Opcode = iota
	// OpGetGlobal retrieves a symbol from the symbol table at the
	// specified index.
	OpGetGlobal
	// OpSetGlobal adds a symbol to the specified index in the symbol
	// table.
	OpSetGlobal
	// OpAdd instructs the virtual machine to perform an addition.
	OpAdd
	// OpSubtract instructs the virtual machine to perform a subtraction.
	OpSubtract
	// OpMultiply instructs the virtual machine to perform a multiplication.
	OpMultiply
	// OpDivide instructs the virtual machine to perform a division.
	OpDivide
	// OpModulo instructs the virtual machine to perform a modulo operation.
	// Modulo returns the remainder of dividing the left side of an expression
	// by the right.
	OpModulo
	// OpTrue represents the boolean literal true.
	OpTrue
	// OpFalse represents the boolean literal false.
	OpFalse
	// OpNot represents the not unary operator, which performs logical
	// negation on a boolean operand.
	OpNot
	// OpMinus represents the minus unary operator, which negates the
	// value of a numeric operand.
	OpMinus
	// OpEqual represents the equality operator.
	OpEqual
	// OpNotEqual represents the inequality operator.
	OpNotEqual
	// OpNumLessThan represents a less than operator for numeric
	// operands.
	OpNumLessThan
	// OpNumLessThanEqual represents a less than or equal operator for
	// numeric operands.
	OpNumLessThanEqual
	// OpNumGreaterThan represents a greater than operator for numeric
	// operands.
	OpNumGreaterThan
	// OpNumGreaterThanEqual represents a greater than or equal operator
	// for numeric operands.
	OpNumGreaterThanEqual
	// OpStringLessThan represents a less than operator for string
	// operands. Strings are compared using lexicographic order.
	OpStringLessThan
	// OpStringLessThanEqual represents a less than or equal operator for
	// string operands. Strings are compared using lexicographic order.
	OpStringLessThanEqual
	// OpStringGreaterThan represents a greater than operator for string
	// operands. Strings are compared using lexicographic order.
	OpStringGreaterThan
	// OpStringGreaterThanEqual represents a greater than or equal operator
	// for string operands. Strings are compared using lexicographic order.
	OpStringGreaterThanEqual
	// OpStringConcatenate represents a + operator used to concatenate two
	// strings.
	OpStringConcatenate
)

type Symbol

type Symbol struct {
	Name  string
	Scope SymbolScope
	Index int
}

Symbol is a variable inside an evy program.

type SymbolScope

type SymbolScope string

SymbolScope defines a type of scope that a symbol can be defined inside.

const (
	// GlobalScope is the top level scope of an evy program.
	GlobalScope SymbolScope = "GLOBAL"
)

type SymbolTable

type SymbolTable struct {
	// contains filtered or unexported fields
}

SymbolTable is a mapping of string identifiers to symbols.

func NewSymbolTable

func NewSymbolTable() *SymbolTable

NewSymbolTable returns a new SymbolTable.

func (*SymbolTable) Define

func (s *SymbolTable) Define(name string) Symbol

Define adds a symbol definition to the table or returns an already defined symbol with the same name.

func (*SymbolTable) Resolve

func (s *SymbolTable) Resolve(name string) (Symbol, bool)

Resolve returns the Symbol with the specified name, or false if there is no such Symbol.

type VM

type VM struct {
	// contains filtered or unexported fields
}

VM is responsible for executing evy programs from bytecode.

func NewVM

func NewVM(bytecode *Bytecode) *VM

NewVM returns a new VM.

func (*VM) Run

func (vm *VM) Run() error

Run executes the provided bytecode instructions in order, any error will stop the execution.