Framework/Lua/Runtime/Compiler/Ast.cs

The AST and tree-walking evaluator for the Lua interpreter in the RoleplayFramework. Defines expression node types (locals, upvalues, globals, index, calls, tables, operators) and statement node types (assign, local, loops, returns), each with Eval/Exec implementations, plus frame, upvalue descriptor and function prototype types used by the parser and runtime.

using System;
using System.Collections.Generic;

namespace RoleplayFramework.Lua.Compiler;

// Tree-walking interpreter. The parser resolves every name to a local slot, an upvalue index
// or a global at compile time, so execution never does name lookups for locals.

internal enum ExecResult : byte { Normal, Break, Continue, Return }

internal sealed class Frame
{
	public Cell[] Slots;
	public LuaValue[] Varargs;
	public LuaClosure Closure;
	public LuaState State;
	public LuaValue[] Returns;
	public int Line;
}

internal struct UpvalDesc
{
	public bool FromParentLocal;
	public int Index;
	public string Name;
}

internal sealed class FunctionProto
{
	public string Name;
	public string ChunkName;
	public int Line;
	public int ParamCount;
	public bool IsVararg;
	public int SlotCount;
	public UpvalDesc[] Upvalues;
	public Block Body;
}

// ---------------------------------------------------------------- expressions

internal abstract class Expr
{
	public int Line;
	/// <summary>Nesting depth of this expression tree (set by the parser).</summary>
	public int Depth;
	public abstract LuaValue Eval( Frame f );
	public virtual bool IsMulti => false;
	public virtual LuaValue[] EvalMulti( Frame f ) => new[] { Eval( f ) };
	/// <summary>Describes the variable for error messages, e.g. "global 'foo'".</summary>
	public virtual string Describe() => null;

	public static LuaValue[] EvalList( Frame f, Expr[] exprs )
	{
		int n = exprs.Length;
		if ( n == 0 ) return LuaValue.EmptyArray;

		var last = exprs[n - 1];
		if ( !last.IsMulti )
		{
			var r = new LuaValue[n];
			for ( int i = 0; i < n; i++ ) r[i] = exprs[i].Eval( f );
			return r;
		}

		if ( n == 1 ) return last.EvalMulti( f );

		var firsts = new LuaValue[n - 1];
		for ( int i = 0; i < n - 1; i++ ) firsts[i] = exprs[i].Eval( f );
		var tail = last.EvalMulti( f );
		var all = new LuaValue[firsts.Length + tail.Length];
		firsts.CopyTo( all, 0 );
		tail.CopyTo( all, firsts.Length );
		return all;
	}
}

internal interface IAssignable
{
	/// <summary>Evaluates the target's object/key ahead of the right-hand side.</summary>
	object Prepare( Frame f );
	void Assign( Frame f, object prepared, LuaValue value );
}

internal sealed class ConstExpr : Expr
{
	public LuaValue Value;
	public override LuaValue Eval( Frame f ) => Value;
}

internal sealed class VarargExpr : Expr
{
	public override bool IsMulti => true;
	public override LuaValue Eval( Frame f ) => f.Varargs.Length > 0 ? f.Varargs[0] : LuaValue.Nil;
	public override LuaValue[] EvalMulti( Frame f ) => f.Varargs;
}

internal sealed class ParenExpr : Expr
{
	public Expr Inner;
	public override LuaValue Eval( Frame f ) => Inner.Eval( f );
}

internal sealed class LocalExpr : Expr, IAssignable
{
	public int Slot;
	public string Name;
	public override LuaValue Eval( Frame f ) => f.Slots[Slot].Value;
	public override string Describe() => $"local '{Name}'";
	public object Prepare( Frame f ) => null;
	public void Assign( Frame f, object prepared, LuaValue value ) => f.Slots[Slot].Value = value;
}

internal sealed class UpvalExpr : Expr, IAssignable
{
	public int Index;
	public string Name;
	public override LuaValue Eval( Frame f ) => f.Closure.Upvalues[Index].Value;
	public override string Describe() => $"upvalue '{Name}'";
	public object Prepare( Frame f ) => null;
	public void Assign( Frame f, object prepared, LuaValue value ) => f.Closure.Upvalues[Index].Value = value;
}

internal sealed class GlobalExpr : Expr, IAssignable
{
	public LuaValue Key;
	public override LuaValue Eval( Frame f )
	{
		var env = f.Closure.Env;
		var v = env.Get( Key );
		if ( v.IsNil && env.Metatable is not null ) return f.State.Index( LuaValue.FromTable( env ), Key );
		return v;
	}
	public override string Describe() => $"global '{Key.AsString}'";
	public object Prepare( Frame f ) => null;
	public void Assign( Frame f, object prepared, LuaValue value )
	{
		var env = f.Closure.Env;
		if ( env.Metatable is null ) env.Set( Key, value );
		else f.State.SetIndex( LuaValue.FromTable( env ), Key, value );
	}
}

internal sealed class IndexExpr : Expr, IAssignable
{
	public Expr Obj;
	public Expr Key;

	sealed class Prepared { public LuaValue Obj; public LuaValue Key; }

	public override LuaValue Eval( Frame f )
	{
		var o = Obj.Eval( f );
		var k = Key.Eval( f );
		if ( o.Type == LuaType.Table )
		{
			var t = (LuaTable)o.Obj;
			var v = t.Get( k );
			if ( !v.IsNil || t.Metatable is null ) return v;
		}
		else if ( o.Type == LuaType.Nil )
		{
			f.Line = Line;
			throw new LuaRuntimeException( IndexError( o ) );
		}
		f.Line = Line;
		return f.State.Index( o, k );
	}

	string IndexError( LuaValue o )
	{
		var d = Obj.Describe();
		return d is null ? $"attempt to index a {o.TypeName} value" : $"attempt to index {d} (a {o.TypeName} value)";
	}

	public override string Describe() => Key is ConstExpr c && c.Value.IsString ? $"field '{c.Value.AsString}'" : null;

	public object Prepare( Frame f ) => new Prepared { Obj = Obj.Eval( f ), Key = Key.Eval( f ) };

	public void Assign( Frame f, object prepared, LuaValue value )
	{
		var p = (Prepared)prepared;
		AssignTo( f, p.Obj, p.Key, value );
	}

	public void AssignTo( Frame f, LuaValue o, LuaValue k, LuaValue value )
	{
		f.Line = Line;
		if ( o.Type == LuaType.Table )
		{
			var t = (LuaTable)o.Obj;
			if ( t.Metatable is null ) { t.Set( k, value ); return; }
		}
		else if ( o.Type == LuaType.Nil )
		{
			throw new LuaRuntimeException( IndexError( o ) );
		}
		f.State.SetIndex( o, k, value );
	}
}

internal sealed class CallExpr : Expr
{
	public Expr Fn;
	public Expr[] Args;

	public override bool IsMulti => true;

	public override LuaValue Eval( Frame f )
	{
		var r = EvalMulti( f );
		return r.Length > 0 ? r[0] : LuaValue.Nil;
	}

	public override LuaValue[] EvalMulti( Frame f )
	{
		var fn = Fn.Eval( f );
		var args = EvalList( f, Args );
		f.Line = Line;
		if ( fn.Type != LuaType.Function && f.State.GetMetamethod( fn, "__call" ).IsNil )
		{
			var d = Fn.Describe();
			throw new LuaRuntimeException( d is null ? $"attempt to call a {fn.TypeName} value" : $"attempt to call {d} (a {fn.TypeName} value)" );
		}
		return f.State.Call( fn, args );
	}
}

internal sealed class MethodCallExpr : Expr
{
	public Expr Obj;
	public string Method;
	public Expr[] Args;

	public override bool IsMulti => true;

	public override LuaValue Eval( Frame f )
	{
		var r = EvalMulti( f );
		return r.Length > 0 ? r[0] : LuaValue.Nil;
	}

	public override LuaValue[] EvalMulti( Frame f )
	{
		var o = Obj.Eval( f );
		f.Line = Line;
		if ( o.IsNil )
		{
			var d = Obj.Describe();
			throw new LuaRuntimeException( d is null ? "attempt to index a nil value" : $"attempt to index {d} (a nil value)" );
		}

		var fn = f.State.Index( o, LuaValue.FromString( Method ) );

		LuaValue[] args;
		if ( Args.Length == 0 )
		{
			args = new[] { o };
		}
		else
		{
			var rest = EvalList( f, Args );
			args = new LuaValue[rest.Length + 1];
			args[0] = o;
			rest.CopyTo( args, 1 );
		}

		f.Line = Line;
		if ( fn.Type != LuaType.Function && f.State.GetMetamethod( fn, "__call" ).IsNil )
			throw new LuaRuntimeException( $"attempt to call method '{Method}' (a {fn.TypeName} value)" );

		return f.State.Call( fn, args );
	}
}

internal sealed class FunctionExpr : Expr
{
	public FunctionProto Proto;

	public override LuaValue Eval( Frame f )
	{
		var descs = Proto.Upvalues;
		var ups = descs.Length == 0 ? Array.Empty<Cell>() : new Cell[descs.Length];
		for ( int i = 0; i < descs.Length; i++ )
		{
			ups[i] = descs[i].FromParentLocal ? f.Slots[descs[i].Index] : f.Closure.Upvalues[descs[i].Index];
		}
		return LuaValue.FromFunction( new LuaClosure( Proto, ups, f.Closure.Env ) );
	}
}

internal enum BinOp : byte { Add, Sub, Mul, Div, Mod, Pow, Concat, Eq, Ne, Lt, Le, Gt, Ge }

internal sealed class BinaryExpr : Expr
{
	public BinOp Op;
	public Expr A;
	public Expr B;

	public override LuaValue Eval( Frame f )
	{
		var a = A.Eval( f );
		var b = B.Eval( f );

		if ( a.Type == LuaType.Number && b.Type == LuaType.Number )
		{
			double x = a.Number, y = b.Number;
			switch ( Op )
			{
				case BinOp.Add: return LuaValue.FromNumber( x + y );
				case BinOp.Sub: return LuaValue.FromNumber( x - y );
				case BinOp.Mul: return LuaValue.FromNumber( x * y );
				case BinOp.Div: return LuaValue.FromNumber( x / y );
				case BinOp.Mod: return LuaValue.FromNumber( LuaState.Mod( x, y ) );
				case BinOp.Pow: return LuaValue.FromNumber( Math.Pow( x, y ) );
				case BinOp.Eq: return LuaValue.FromBool( x == y );
				case BinOp.Ne: return LuaValue.FromBool( x != y );
				case BinOp.Lt: return LuaValue.FromBool( x < y );
				case BinOp.Le: return LuaValue.FromBool( x <= y );
				case BinOp.Gt: return LuaValue.FromBool( x > y );
				case BinOp.Ge: return LuaValue.FromBool( x >= y );
			}
		}

		f.Line = Line;
		var s = f.State;
		switch ( Op )
		{
			case BinOp.Eq: return LuaValue.FromBool( s.ValuesEqual( a, b ) );
			case BinOp.Ne: return LuaValue.FromBool( !s.ValuesEqual( a, b ) );
			case BinOp.Lt: return LuaValue.FromBool( s.LessThan( a, b ) );
			case BinOp.Le: return LuaValue.FromBool( s.LessEqual( a, b ) );
			case BinOp.Gt: return LuaValue.FromBool( s.LessThan( b, a ) );
			case BinOp.Ge: return LuaValue.FromBool( s.LessEqual( b, a ) );
			case BinOp.Concat: return s.Concat( a, b );
			default: return s.Arith( Op, a, b );
		}
	}
}

internal sealed class AndExpr : Expr
{
	public Expr A, B;
	public override LuaValue Eval( Frame f )
	{
		var a = A.Eval( f );
		return a.IsTruthy ? B.Eval( f ) : a;
	}
}

internal sealed class OrExpr : Expr
{
	public Expr A, B;
	public override LuaValue Eval( Frame f )
	{
		var a = A.Eval( f );
		return a.IsTruthy ? a : B.Eval( f );
	}
}

internal enum UnOp : byte { Neg, Not, Len }

internal sealed class UnaryExpr : Expr
{
	public UnOp Op;
	public Expr A;

	public override LuaValue Eval( Frame f )
	{
		var a = A.Eval( f );
		switch ( Op )
		{
			case UnOp.Not: return LuaValue.FromBool( !a.IsTruthy );
			case UnOp.Neg:
				if ( a.Type == LuaType.Number ) return LuaValue.FromNumber( -a.Number );
				f.Line = Line;
				return f.State.Unm( a );
			default:
				f.Line = Line;
				if ( a.Type == LuaType.String ) return LuaValue.FromNumber( a.AsString.Length );
				return f.State.Len( a, A.Describe() );
		}
	}
}

internal sealed class TableExpr : Expr
{
	public Expr[] Positional = Array.Empty<Expr>();
	public Expr[] Keys = Array.Empty<Expr>();
	public Expr[] Values = Array.Empty<Expr>();
	// Order of evaluation: entries are evaluated in source order.
	public (bool positional, int index)[] Order = Array.Empty<(bool, int)>();

	public override LuaValue Eval( Frame f )
	{
		var t = new LuaTable( Positional.Length, Keys.Length );
		int n = 1;
		for ( int o = 0; o < Order.Length; o++ )
		{
			var (positional, index) = Order[o];
			if ( positional )
			{
				var e = Positional[index];
				// Only the very last field of the constructor expands multiple results.
				if ( o == Order.Length - 1 && e.IsMulti )
				{
					foreach ( var v in e.EvalMulti( f ) ) t.Set( LuaValue.FromNumber( n++ ), v );
				}
				else
				{
					t.Set( LuaValue.FromNumber( n++ ), e.Eval( f ) );
				}
			}
			else
			{
				var k = Keys[index].Eval( f );
				var v = Values[index].Eval( f );
				f.Line = Keys[index].Line;
				if ( k.IsNil ) throw new LuaRuntimeException( "table index is nil" );
				t.Set( k, v );
			}
		}
		return LuaValue.FromTable( t );
	}
}

// ---------------------------------------------------------------- statements

internal abstract class Stmt
{
	public int Line;
	public abstract ExecResult Exec( Frame f );
}

internal sealed class Block
{
	public Stmt[] Statements;

	public ExecResult Exec( Frame f )
	{
		var stmts = Statements;
		var state = f.State;
		for ( int i = 0; i < stmts.Length; i++ )
		{
			var s = stmts[i];
			f.Line = s.Line;
			state.Step();
			var r = s.Exec( f );
			if ( r != ExecResult.Normal ) return r;
		}
		return ExecResult.Normal;
	}
}

internal sealed class LocalStmt : Stmt
{
	public int[] Slots;
	public Expr[] Exprs;

	public override ExecResult Exec( Frame f )
	{
		if ( Slots.Length == 1 && Exprs.Length == 1 )
		{
			f.Slots[Slots[0]] = new Cell( Exprs[0].Eval( f ) );
			return ExecResult.Normal;
		}

		var values = Expr.EvalList( f, Exprs );
		for ( int i = 0; i < Slots.Length; i++ )
			f.Slots[Slots[i]] = new Cell( i < values.Length ? values[i] : LuaValue.Nil );
		return ExecResult.Normal;
	}
}

internal sealed class AssignStmt : Stmt
{
	public Expr[] Targets;
	public Expr[] Exprs;

	public override ExecResult Exec( Frame f )
	{
		if ( Targets.Length == 1 && Exprs.Length == 1 )
		{
			var target = (IAssignable)Targets[0];
			if ( target is IndexExpr ie )
			{
				var o = ie.Obj.Eval( f );
				var k = ie.Key.Eval( f );
				var v = Exprs[0].Eval( f );
				ie.AssignTo( f, o, k, v );
			}
			else
			{
				target.Assign( f, null, Exprs[0].Eval( f ) );
			}
			return ExecResult.Normal;
		}

		var prepared = new object[Targets.Length];
		for ( int i = 0; i < Targets.Length; i++ ) prepared[i] = ((IAssignable)Targets[i]).Prepare( f );
		var values = Expr.EvalList( f, Exprs );
		for ( int i = 0; i < Targets.Length; i++ )
			((IAssignable)Targets[i]).Assign( f, prepared[i], i < values.Length ? values[i] : LuaValue.Nil );
		return ExecResult.Normal;
	}
}

internal sealed class CallStmt : Stmt
{
	public Expr Call;
	public override ExecResult Exec( Frame f )
	{
		Call.EvalMulti( f );
		return ExecResult.Normal;
	}
}

internal sealed class DoStmt : Stmt
{
	public Block Body;
	public override ExecResult Exec( Frame f ) => Body.Exec( f );
}

internal sealed class WhileStmt : Stmt
{
	public Expr Cond;
	public Block Body;

	public override ExecResult Exec( Frame f )
	{
		var state = f.State;
		while ( Cond.Eval( f ).IsTruthy )
		{
			state.Step();
			var r = Body.Exec( f );
			if ( r == ExecResult.Break ) break;
			if ( r == ExecResult.Return ) return r;
		}
		return ExecResult.Normal;
	}
}

internal sealed class RepeatStmt : Stmt
{
	public Block Body;
	public Expr Cond;

	public override ExecResult Exec( Frame f )
	{
		var state = f.State;
		while ( true )
		{
			state.Step();
			var r = Body.Exec( f );
			if ( r == ExecResult.Break ) break;
			if ( r == ExecResult.Return ) return r;
			if ( Cond.Eval( f ).IsTruthy ) break;
		}
		return ExecResult.Normal;
	}
}

internal sealed class IfStmt : Stmt
{
	public Expr[] Conds;
	public Block[] Blocks;
	public Block Else;

	public override ExecResult Exec( Frame f )
	{
		for ( int i = 0; i < Conds.Length; i++ )
		{
			if ( Conds[i].Eval( f ).IsTruthy ) return Blocks[i].Exec( f );
		}
		return Else is null ? ExecResult.Normal : Else.Exec( f );
	}
}

internal sealed class NumericForStmt : Stmt
{
	public int Slot;
	public Expr Start, Limit, Step;
	public Block Body;

	public override ExecResult Exec( Frame f )
	{
		var state = f.State;
		double start = ForNumber( f, Start.Eval( f ), "initial" );
		double limit = ForNumber( f, Limit.Eval( f ), "limit" );
		double step = Step is null ? 1 : ForNumber( f, Step.Eval( f ), "step" );

		for ( double i = start; step > 0 ? i <= limit : i >= limit; i += step )
		{
			state.Step();
			f.Slots[Slot] = new Cell( LuaValue.FromNumber( i ) );
			var r = Body.Exec( f );
			if ( r == ExecResult.Break ) break;
			if ( r == ExecResult.Return ) return r;
		}
		return ExecResult.Normal;
	}

	double ForNumber( Frame f, LuaValue v, string what )
	{
		if ( v.Type == LuaType.Number ) return v.Number;
		if ( v.Type == LuaType.String && LuaValue.TryParseNumber( v.AsString, out var d ) ) return d;
		f.Line = Line;
		throw new LuaRuntimeException( $"'for' {what} value must be a number" );
	}
}

internal sealed class GenericForStmt : Stmt
{
	public int[] Slots;
	public Expr[] Exprs;
	public Block Body;

	public override ExecResult Exec( Frame f )
	{
		var state = f.State;
		var init = Expr.EvalList( f, Exprs );
		var fn = init.Length > 0 ? init[0] : LuaValue.Nil;
		var s = init.Length > 1 ? init[1] : LuaValue.Nil;
		var control = init.Length > 2 ? init[2] : LuaValue.Nil;

		// Fast path for pairs()/next over a plain table.
		bool isNext = fn.Obj is LuaFunction lf && ReferenceEquals( lf, state.NextFunction ) && s.Type == LuaType.Table;
		var callArgs = new LuaValue[2];

		while ( true )
		{
			state.Step();
			LuaValue k, v = LuaValue.Nil;
			LuaValue[] results = null;

			if ( isNext )
			{
				f.Line = Line;
				if ( !((LuaTable)s.Obj).Next( control, out k, out v ) ) break;
			}
			else
			{
				callArgs = new[] { s, control };
				f.Line = Line;
				if ( fn.Type != LuaType.Function && state.GetMetamethod( fn, "__call" ).IsNil )
					throw new LuaRuntimeException( $"attempt to call a {fn.TypeName} value" );
				results = state.Call( fn, callArgs );
				k = results.Length > 0 ? results[0] : LuaValue.Nil;
				if ( k.IsNil ) break;
			}

			control = k;
			for ( int i = 0; i < Slots.Length; i++ )
			{
				LuaValue val;
				if ( results is null ) val = i == 0 ? k : i == 1 ? v : LuaValue.Nil;
				else val = i < results.Length ? results[i] : LuaValue.Nil;
				f.Slots[Slots[i]] = new Cell( val );
			}

			var r = Body.Exec( f );
			if ( r == ExecResult.Break ) break;
			if ( r == ExecResult.Return ) return r;
		}
		return ExecResult.Normal;
	}
}

internal sealed class LocalFunctionStmt : Stmt
{
	public int Slot;
	public FunctionExpr Func;

	public override ExecResult Exec( Frame f )
	{
		var cell = new Cell();
		f.Slots[Slot] = cell;
		cell.Value = Func.Eval( f );
		return ExecResult.Normal;
	}
}

internal sealed class ReturnStmt : Stmt
{
	public Expr[] Exprs;
	public override ExecResult Exec( Frame f )
	{
		f.Returns = Expr.EvalList( f, Exprs );
		return ExecResult.Return;
	}
}

internal sealed class BreakStmt : Stmt
{
	public override ExecResult Exec( Frame f ) => ExecResult.Break;
}

internal sealed class ContinueStmt : Stmt
{
	public override ExecResult Exec( Frame f ) => ExecResult.Continue;
}