Framework/Lua/Runtime/Compiler/Parser.cs

Recursive-descent parser for a Lua 5.1 dialect with GLua extensions. Turns a token stream from the Lexer into a resolved AST (locals and upvalues resolved to slots), tracking function scopes, loop depth and expression depth, and emits FunctionProto objects for the compiler. Used by the Lua runtime in the RoleplayFramework.

using System;
using System.Collections.Generic;

namespace RoleplayFramework.Lua.Compiler;

/// <summary>Recursive-descent parser producing a resolved AST (Lua 5.1 grammar + GLua extensions).</summary>
internal sealed class Parser
{
	// Both limits protect the host stack: parsing and evaluation recurse on it.
	const int MaxDepth = 100;
	const int MaxExprDepth = 150;

	sealed class FuncState
	{
		public FuncState Parent;
		public readonly List<Dictionary<string, int>> Blocks = new();
		public int SlotCount;
		public int ParamCount;
		public bool IsVararg;
		public readonly List<UpvalDesc> Upvals = new();
		public readonly Dictionary<string, int> UpvalIndex = new();
		public int LoopDepth;
	}

	readonly List<Token> _tokens;
	readonly string _chunk;
	int _p;
	int _depth;
	FuncState _fs;

	Parser( List<Token> tokens, string chunk )
	{
		_tokens = tokens;
		_chunk = chunk;
	}

	public static FunctionProto ParseChunk( string source, string chunkName )
	{
		var tokens = new Lexer( source, chunkName ).Tokenize();
		var p = new Parser( tokens, chunkName );
		return p.MainChunk();
	}

	// ------------------------------------------------------------ token helpers

	Token Cur => _tokens[_p];
	TokenKind Kind => _tokens[_p].Kind;
	TokenKind PeekKind( int n = 1 ) => _tokens[Math.Min( _p + n, _tokens.Count - 1 )].Kind;

	Token Advance() => _tokens[_p < _tokens.Count - 1 ? _p++ : _p];

	bool Accept( TokenKind k )
	{
		if ( Kind != k ) return false;
		Advance();
		return true;
	}

	LuaSyntaxException Error( string msg ) => new( _chunk, Cur.Line, $"{msg} near '{Cur}'" );

	Token Expect( TokenKind k, string what = null )
	{
		if ( Kind != k ) throw Error( $"'{what ?? Lexer.Describe( k )}' expected" );
		return Advance();
	}

	void ExpectMatch( TokenKind close, TokenKind open, int openLine )
	{
		if ( Kind == close ) { Advance(); return; }
		if ( openLine == Cur.Line ) throw Error( $"'{Lexer.Describe( close )}' expected" );
		throw Error( $"'{Lexer.Describe( close )}' expected (to close '{Lexer.Describe( open )}' at line {openLine})" );
	}

	string ExpectName() => Expect( TokenKind.Name, "<name>" ).Text;

	void Enter()
	{
		if ( ++_depth > MaxDepth ) throw Error( "chunk has too many syntax levels" );
	}

	void Leave() => _depth--;

	/// <summary>Records expression-tree depth so evaluation can't overflow the host stack (e.g. a+b+c+... chains).</summary>
	T Nest<T>( T e, Expr a, Expr b = null ) where T : Expr
	{
		e.Depth = 1 + Math.Max( a?.Depth ?? 0, b?.Depth ?? 0 );
		if ( e.Depth > MaxExprDepth ) throw new LuaSyntaxException( _chunk, e.Line, "expression too complex" );
		return e;
	}

	// ------------------------------------------------------------ scopes

	void OpenFunction()
	{
		_fs = new FuncState { Parent = _fs };
		_fs.Blocks.Add( new Dictionary<string, int>() );
	}

	FunctionProto CloseFunction( string name, int line, Block body )
	{
		var fs = _fs;
		_fs = fs.Parent;
		return new FunctionProto
		{
			Name = name,
			ChunkName = _chunk,
			Line = line,
			ParamCount = fs.ParamCount,
			IsVararg = fs.IsVararg,
			SlotCount = fs.SlotCount,
			Upvalues = fs.Upvals.ToArray(),
			Body = body,
		};
	}

	void OpenScope() => _fs.Blocks.Add( new Dictionary<string, int>() );
	void CloseScope() => _fs.Blocks.RemoveAt( _fs.Blocks.Count - 1 );

	int DeclareLocal( string name )
	{
		int slot = _fs.SlotCount++;
		_fs.Blocks[^1][name] = slot;
		return slot;
	}

	static int FindLocal( FuncState fs, string name )
	{
		for ( int i = fs.Blocks.Count - 1; i >= 0; i-- )
			if ( fs.Blocks[i].TryGetValue( name, out int slot ) ) return slot;
		return -1;
	}

	static int FindUpval( FuncState fs, string name )
	{
		if ( fs.UpvalIndex.TryGetValue( name, out int idx ) ) return idx;
		if ( fs.Parent is null ) return -1;

		int slot = FindLocal( fs.Parent, name );
		if ( slot >= 0 ) return AddUpval( fs, name, true, slot );

		int up = FindUpval( fs.Parent, name );
		if ( up >= 0 ) return AddUpval( fs, name, false, up );

		return -1;
	}

	static int AddUpval( FuncState fs, string name, bool fromLocal, int index )
	{
		int i = fs.Upvals.Count;
		fs.Upvals.Add( new UpvalDesc { FromParentLocal = fromLocal, Index = index, Name = name } );
		fs.UpvalIndex[name] = i;
		return i;
	}

	Expr ResolveName( string name, int line )
	{
		int slot = FindLocal( _fs, name );
		if ( slot >= 0 ) return new LocalExpr { Slot = slot, Name = name, Line = line };
		int up = FindUpval( _fs, name );
		if ( up >= 0 ) return new UpvalExpr { Index = up, Name = name, Line = line };
		return new GlobalExpr { Key = LuaValue.FromString( name ), Line = line };
	}

	// ------------------------------------------------------------ chunk / blocks

	FunctionProto MainChunk()
	{
		OpenFunction();
		_fs.IsVararg = true;
		var body = ParseBlockStatements();
		if ( Kind != TokenKind.Eof ) throw Error( "'<eof>' expected" );
		return CloseFunction( "main chunk", 0, body );
	}

	static bool BlockFollows( TokenKind k ) => k is TokenKind.Eof or TokenKind.End or TokenKind.Else or TokenKind.ElseIf or TokenKind.Until;

	Block ParseBlock()
	{
		OpenScope();
		var b = ParseBlockStatements();
		CloseScope();
		return b;
	}

	Block ParseBlockStatements()
	{
		var list = new List<Stmt>();
		while ( !BlockFollows( Kind ) )
		{
			if ( Kind == TokenKind.Return )
			{
				list.Add( ParseReturn() );
				break;
			}
			if ( Kind == TokenKind.Break || Kind == TokenKind.Continue )
			{
				var t = Advance();
				if ( _fs.LoopDepth == 0 ) throw new LuaSyntaxException( _chunk, t.Line, $"no loop to {(t.Kind == TokenKind.Break ? "break" : "continue")}" );
				list.Add( t.Kind == TokenKind.Break ? new BreakStmt { Line = t.Line } : new ContinueStmt { Line = t.Line } );
				Accept( TokenKind.Semicolon );
				// Like Lua 5.1, break/continue must be the last statement of a block.
				if ( !BlockFollows( Kind ) ) throw Error( "'end' expected" );
				break;
			}

			var s = ParseStatement();
			if ( s is not null ) list.Add( s );
		}
		return new Block { Statements = list.ToArray() };
	}

	Stmt ParseReturn()
	{
		int line = Advance().Line;
		Expr[] exprs = Array.Empty<Expr>();
		if ( !BlockFollows( Kind ) && Kind != TokenKind.Semicolon ) exprs = ParseExprList();
		Accept( TokenKind.Semicolon );
		if ( !BlockFollows( Kind ) ) throw Error( "'<eof>' expected" );
		return new ReturnStmt { Line = line, Exprs = exprs };
	}

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

	Stmt ParseStatement()
	{
		Enter();
		try
		{
			int line = Cur.Line;
			switch ( Kind )
			{
				case TokenKind.Semicolon:
					Advance();
					return null;

				case TokenKind.If: return ParseIf();

				case TokenKind.While:
					{
						Advance();
						var cond = ParseExpr();
						Expect( TokenKind.Do );
						_fs.LoopDepth++;
						var body = ParseBlock();
						_fs.LoopDepth--;
						ExpectMatch( TokenKind.End, TokenKind.While, line );
						return new WhileStmt { Line = line, Cond = cond, Body = body };
					}

				case TokenKind.Do:
					{
						Advance();
						var body = ParseBlock();
						ExpectMatch( TokenKind.End, TokenKind.Do, line );
						return new DoStmt { Line = line, Body = body };
					}

				case TokenKind.For: return ParseFor();

				case TokenKind.Repeat:
					{
						Advance();
						_fs.LoopDepth++;
						OpenScope();
						var body = ParseBlockStatements();
						ExpectMatch( TokenKind.Until, TokenKind.Repeat, line );
						var cond = ParseExpr(); // sees the body's locals
						CloseScope();
						_fs.LoopDepth--;
						return new RepeatStmt { Line = line, Body = body, Cond = cond };
					}

				case TokenKind.Function: return ParseFunctionStatement();

				case TokenKind.Local:
					Advance();
					if ( Accept( TokenKind.Function ) )
					{
						var name = ExpectName();
						int slot = DeclareLocal( name );
						var fn = ParseFunctionBody( name, line, false );
						return new LocalFunctionStmt { Line = line, Slot = slot, Func = fn };
					}
					return ParseLocal( line );

				default:
					return ParseExprStatement();
			}
		}
		finally { Leave(); }
	}

	Stmt ParseIf()
	{
		int line = Advance().Line;
		var conds = new List<Expr>();
		var blocks = new List<Block>();
		conds.Add( ParseExpr() );
		Expect( TokenKind.Then );
		blocks.Add( ParseBlock() );
		Block elseBlock = null;

		while ( true )
		{
			if ( Accept( TokenKind.ElseIf ) )
			{
				conds.Add( ParseExpr() );
				Expect( TokenKind.Then );
				blocks.Add( ParseBlock() );
				continue;
			}
			if ( Accept( TokenKind.Else ) )
			{
				elseBlock = ParseBlock();
			}
			ExpectMatch( TokenKind.End, TokenKind.If, line );
			break;
		}

		return new IfStmt { Line = line, Conds = conds.ToArray(), Blocks = blocks.ToArray(), Else = elseBlock };
	}

	Stmt ParseFor()
	{
		int line = Advance().Line;
		var first = ExpectName();

		if ( Kind == TokenKind.Assign )
		{
			Advance();
			var start = ParseExpr();
			Expect( TokenKind.Comma );
			var limit = ParseExpr();
			Expr step = null;
			if ( Accept( TokenKind.Comma ) ) step = ParseExpr();
			Expect( TokenKind.Do );

			OpenScope();
			int slot = DeclareLocal( first );
			_fs.LoopDepth++;
			var body = ParseBlock();
			_fs.LoopDepth--;
			CloseScope();
			ExpectMatch( TokenKind.End, TokenKind.For, line );
			return new NumericForStmt { Line = line, Slot = slot, Start = start, Limit = limit, Step = step, Body = body };
		}

		var names = new List<string> { first };
		while ( Accept( TokenKind.Comma ) ) names.Add( ExpectName() );
		Expect( TokenKind.In );
		var exprs = ParseExprList();
		Expect( TokenKind.Do );

		OpenScope();
		var slots = new int[names.Count];
		for ( int i = 0; i < names.Count; i++ ) slots[i] = DeclareLocal( names[i] );
		_fs.LoopDepth++;
		var gbody = ParseBlock();
		_fs.LoopDepth--;
		CloseScope();
		ExpectMatch( TokenKind.End, TokenKind.For, line );
		return new GenericForStmt { Line = line, Slots = slots, Exprs = exprs, Body = gbody };
	}

	Stmt ParseFunctionStatement()
	{
		int line = Advance().Line;
		var nameTok = Cur;
		string fullName = ExpectName();
		Expr target = ResolveName( fullName, nameTok.Line );
		bool isMethod = false;

		while ( Kind == TokenKind.Dot || Kind == TokenKind.Colon )
		{
			bool colon = Kind == TokenKind.Colon;
			Advance();
			var key = ExpectName();
			fullName += (colon ? ":" : ".") + key;
			target = new IndexExpr { Line = line, Obj = target, Key = new ConstExpr { Value = LuaValue.FromString( key ), Line = line } };
			if ( colon ) { isMethod = true; break; }
		}

		var fn = ParseFunctionBody( fullName, line, isMethod );
		return new AssignStmt { Line = line, Targets = new[] { target }, Exprs = new Expr[] { fn } };
	}

	Stmt ParseLocal( int line )
	{
		var names = new List<string>();
		do { names.Add( ExpectName() ); } while ( Accept( TokenKind.Comma ) );

		Expr[] exprs = Array.Empty<Expr>();
		if ( Accept( TokenKind.Assign ) ) exprs = ParseExprList();

		// Declare after parsing the initialisers: `local x = x` reads the outer x.
		var slots = new int[names.Count];
		for ( int i = 0; i < names.Count; i++ ) slots[i] = DeclareLocal( names[i] );

		if ( exprs.Length == 0 )
			exprs = new Expr[] { new ConstExpr { Value = LuaValue.Nil, Line = line } };

		return new LocalStmt { Line = line, Slots = slots, Exprs = exprs };
	}

	Stmt ParseExprStatement()
	{
		int line = Cur.Line;
		var e = ParseSuffixedExpr();

		if ( Kind == TokenKind.Assign || Kind == TokenKind.Comma )
		{
			var targets = new List<Expr> { e };
			while ( Accept( TokenKind.Comma ) ) targets.Add( ParseSuffixedExpr() );
			Expect( TokenKind.Assign );
			var exprs = ParseExprList();

			foreach ( var t in targets )
				if ( t is not IAssignable ) throw new LuaSyntaxException( _chunk, line, "syntax error (cannot assign to this expression)" );

			return new AssignStmt { Line = line, Targets = targets.ToArray(), Exprs = exprs };
		}

		if ( e is not CallExpr && e is not MethodCallExpr ) throw Error( "syntax error" );
		return new CallStmt { Line = line, Call = e };
	}

	// ------------------------------------------------------------ functions

	FunctionExpr ParseFunctionBody( string name, int line, bool isMethod )
	{
		OpenFunction();
		if ( isMethod ) { DeclareLocal( "self" ); _fs.ParamCount++; }

		Expect( TokenKind.LParen );
		if ( Kind != TokenKind.RParen )
		{
			do
			{
				if ( Accept( TokenKind.Ellipsis ) ) { _fs.IsVararg = true; break; }
				DeclareLocal( ExpectName() );
				_fs.ParamCount++;
			} while ( Accept( TokenKind.Comma ) );
		}
		Expect( TokenKind.RParen );

		var loopDepth = _fs.LoopDepth;
		var body = ParseBlockStatements();
		ExpectMatch( TokenKind.End, TokenKind.Function, line );
		var proto = CloseFunction( name, line, body );
		return new FunctionExpr { Line = line, Proto = proto };
	}

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

	Expr[] ParseExprList()
	{
		var list = new List<Expr> { ParseExpr() };
		while ( Accept( TokenKind.Comma ) ) list.Add( ParseExpr() );
		return list.ToArray();
	}

	Expr ParseExpr() => ParseSubExpr( 0 );

	// Lua 5.1 priorities: left / right binding power.
	static bool BinaryPriority( TokenKind k, out int left, out int right )
	{
		switch ( k )
		{
			case TokenKind.Or: left = 1; right = 1; return true;
			case TokenKind.And: left = 2; right = 2; return true;
			case TokenKind.Less: case TokenKind.Greater: case TokenKind.LessEq: case TokenKind.GreaterEq:
			case TokenKind.Eq: case TokenKind.NotEq:
				left = 3; right = 3; return true;
			case TokenKind.Concat: left = 5; right = 4; return true;
			case TokenKind.Plus: case TokenKind.Minus: left = 6; right = 6; return true;
			case TokenKind.Star: case TokenKind.Slash: case TokenKind.Percent: left = 7; right = 7; return true;
			case TokenKind.Caret: left = 10; right = 9; return true;
		}
		left = right = 0;
		return false;
	}

	const int UnaryPriority = 8;

	Expr ParseSubExpr( int limit )
	{
		Enter();
		try
		{
			Expr e;
			int line = Cur.Line;
			if ( Kind == TokenKind.Not || Kind == TokenKind.Minus || Kind == TokenKind.Hash )
			{
				var op = Advance().Kind;
				var operand = ParseSubExpr( UnaryPriority );
				e = Nest( FoldUnary( op, operand, line ), operand );
			}
			else
			{
				e = ParseSimpleExpr();
			}

			while ( BinaryPriority( Kind, out int left, out int right ) && left > limit )
			{
				var opTok = Advance();
				var rhs = ParseSubExpr( right );
				e = Nest( MakeBinary( opTok.Kind, e, rhs, opTok.Line ), e, rhs );
			}
			return e;
		}
		finally { Leave(); }
	}

	static Expr FoldUnary( TokenKind op, Expr operand, int line )
	{
		if ( op == TokenKind.Minus && operand is ConstExpr c && c.Value.IsNumber )
			return new ConstExpr { Line = line, Value = LuaValue.FromNumber( -c.Value.Number ) };

		var u = op switch { TokenKind.Not => UnOp.Not, TokenKind.Minus => UnOp.Neg, _ => UnOp.Len };
		return new UnaryExpr { Line = line, Op = u, A = operand };
	}

	static Expr MakeBinary( TokenKind k, Expr a, Expr b, int line )
	{
		switch ( k )
		{
			case TokenKind.And: return new AndExpr { Line = line, A = a, B = b };
			case TokenKind.Or: return new OrExpr { Line = line, A = a, B = b };
		}

		var op = k switch
		{
			TokenKind.Plus => BinOp.Add,
			TokenKind.Minus => BinOp.Sub,
			TokenKind.Star => BinOp.Mul,
			TokenKind.Slash => BinOp.Div,
			TokenKind.Percent => BinOp.Mod,
			TokenKind.Caret => BinOp.Pow,
			TokenKind.Concat => BinOp.Concat,
			TokenKind.Eq => BinOp.Eq,
			TokenKind.NotEq => BinOp.Ne,
			TokenKind.Less => BinOp.Lt,
			TokenKind.LessEq => BinOp.Le,
			TokenKind.Greater => BinOp.Gt,
			_ => BinOp.Ge,
		};
		return new BinaryExpr { Line = line, Op = op, A = a, B = b };
	}

	Expr ParseSimpleExpr()
	{
		var t = Cur;
		switch ( t.Kind )
		{
			case TokenKind.Number: Advance(); return new ConstExpr { Line = t.Line, Value = LuaValue.FromNumber( t.Number ) };
			case TokenKind.String: Advance(); return new ConstExpr { Line = t.Line, Value = LuaValue.FromString( t.Text ) };
			case TokenKind.Nil: Advance(); return new ConstExpr { Line = t.Line, Value = LuaValue.Nil };
			case TokenKind.True: Advance(); return new ConstExpr { Line = t.Line, Value = LuaValue.True };
			case TokenKind.False: Advance(); return new ConstExpr { Line = t.Line, Value = LuaValue.False };
			case TokenKind.Ellipsis:
				Advance();
				if ( !_fs.IsVararg ) throw new LuaSyntaxException( _chunk, t.Line, "cannot use '...' outside a vararg function" );
				return new VarargExpr { Line = t.Line };
			case TokenKind.LBrace: return ParseTable();
			case TokenKind.Function:
				Advance();
				return ParseFunctionBody( "anonymous", t.Line, false );
			default:
				return ParseSuffixedExpr();
		}
	}

	Expr ParsePrimaryExpr()
	{
		var t = Cur;
		if ( t.Kind == TokenKind.Name )
		{
			Advance();
			return ResolveName( t.Text, t.Line );
		}
		if ( t.Kind == TokenKind.LParen )
		{
			Advance();
			var inner = ParseExpr();
			ExpectMatch( TokenKind.RParen, TokenKind.LParen, t.Line );
			// Parentheses truncate multiple results to one.
			return inner.IsMulti ? new ParenExpr { Line = t.Line, Inner = inner } : inner;
		}
		throw Error( "unexpected symbol" );
	}

	Expr ParseSuffixedExpr()
	{
		var e = ParsePrimaryExpr();
		while ( true )
		{
			var t = Cur;
			switch ( t.Kind )
			{
				case TokenKind.Dot:
					{
						Advance();
						var name = ExpectName();
						e = Nest( new IndexExpr { Line = t.Line, Obj = e, Key = new ConstExpr { Line = t.Line, Value = LuaValue.FromString( name ) } }, e );
						break;
					}
				case TokenKind.LBracket:
					{
						Advance();
						var key = ParseExpr();
						Expect( TokenKind.RBracket );
						e = Nest( new IndexExpr { Line = t.Line, Obj = e, Key = key }, e, key );
						break;
					}
				case TokenKind.Colon:
					{
						Advance();
						var name = ExpectName();
						var args = ParseCallArgs();
						e = Nest( new MethodCallExpr { Line = t.Line, Obj = e, Method = name, Args = args }, e, Deepest( args ) );
						break;
					}
				case TokenKind.LParen:
				case TokenKind.String:
				case TokenKind.LBrace:
					{
						var args = ParseCallArgs();
						e = Nest( new CallExpr { Line = t.Line, Fn = e, Args = args }, e, Deepest( args ) );
						break;
					}
				default:
					return e;
			}
		}
	}

	static Expr Deepest( Expr[] list )
	{
		Expr best = null;
		foreach ( var x in list ) if ( best is null || x.Depth > best.Depth ) best = x;
		return best;
	}

	Expr[] ParseCallArgs()
	{
		var t = Cur;
		if ( t.Kind == TokenKind.String )
		{
			Advance();
			return new Expr[] { new ConstExpr { Line = t.Line, Value = LuaValue.FromString( t.Text ) } };
		}
		if ( t.Kind == TokenKind.LBrace ) return new[] { ParseTable() };

		Expect( TokenKind.LParen, "function arguments" );
		if ( Accept( TokenKind.RParen ) ) return Array.Empty<Expr>();
		var list = ParseExprList();
		ExpectMatch( TokenKind.RParen, TokenKind.LParen, t.Line );
		return list;
	}

	Expr ParseTable()
	{
		int line = Expect( TokenKind.LBrace ).Line;
		var positional = new List<Expr>();
		var keys = new List<Expr>();
		var values = new List<Expr>();
		var order = new List<(bool, int)>();

		while ( Kind != TokenKind.RBrace )
		{
			if ( Kind == TokenKind.LBracket )
			{
				Advance();
				var k = ParseExpr();
				Expect( TokenKind.RBracket );
				Expect( TokenKind.Assign );
				order.Add( (false, keys.Count) );
				keys.Add( k );
				values.Add( ParseExpr() );
			}
			else if ( Kind == TokenKind.Name && PeekKind() == TokenKind.Assign )
			{
				var nt = Advance();
				Advance();
				order.Add( (false, keys.Count) );
				keys.Add( new ConstExpr { Line = nt.Line, Value = LuaValue.FromString( nt.Text ) } );
				values.Add( ParseExpr() );
			}
			else
			{
				order.Add( (true, positional.Count) );
				positional.Add( ParseExpr() );
			}

			if ( !Accept( TokenKind.Comma ) && !Accept( TokenKind.Semicolon ) ) break;
		}
		ExpectMatch( TokenKind.RBrace, TokenKind.LBrace, line );

		return new TableExpr
		{
			Line = line,
			Positional = positional.ToArray(),
			Keys = keys.ToArray(),
			Values = values.ToArray(),
			Order = order.ToArray(),
		};
	}
}