Framework/Lua/Runtime/LuaTable.cs

Backing implementation of a Lua table for a custom Lua runtime. Keeps a 1-based array part for sequential integer keys and an insertion-ordered hash part with tombstones, and implements Get/Set, next() traversal, append, insert and remove along with array/hash migration.

using System;
using System.Collections.Generic;

namespace RoleplayFramework.Lua;

/// <summary>
/// Lua table with an array part (keys 1..n) and an insertion-ordered hash part.
/// The hash part keeps tombstones so that <see cref="Next"/> stays valid while
/// fields are cleared during traversal, matching Lua's rules for next().
/// </summary>
public sealed class LuaTable
{
	struct Entry
	{
		public LuaValue Key;
		public LuaValue Value;
	}

	readonly List<LuaValue> _array = new();
	List<Entry> _entries;
	Dictionary<LuaValue, int> _index;
	int _tombstones;

	public LuaTable Metatable { get; set; }

	public LuaTable() { }

	public LuaTable( int arrayCapacity, int hashCapacity )
	{
		if ( arrayCapacity > 0 ) _array.Capacity = arrayCapacity;
		if ( hashCapacity > 0 )
		{
			_entries = new List<Entry>( hashCapacity );
			_index = new Dictionary<LuaValue, int>( hashCapacity );
		}
	}

	/// <summary>The border used by the # operator.</summary>
	public int Length => _array.Count;

	public int HashCount => _index is null ? 0 : _index.Count - _tombstones;

	static bool TryArrayIndex( in LuaValue key, out int index )
	{
		if ( key.Type == LuaType.Number )
		{
			double d = key.Number;
			if ( d >= 1 && d <= int.MaxValue && d == Math.Floor( d ) )
			{
				index = (int)d;
				return true;
			}
		}
		index = 0;
		return false;
	}

	public LuaValue Get( LuaValue key )
	{
		if ( TryArrayIndex( key, out int i ) && i <= _array.Count )
			return _array[i - 1];

		if ( _index is null ) return LuaValue.Nil;
		return _index.TryGetValue( key, out int slot ) ? _entries[slot].Value : LuaValue.Nil;
	}

	public LuaValue Get( string key ) => Get( LuaValue.FromString( key ) );
	public LuaValue Get( int key ) => key >= 1 && key <= _array.Count ? _array[key - 1] : Get( LuaValue.FromNumber( key ) );

	public void Set( string key, LuaValue value ) => Set( LuaValue.FromString( key ), value );

	public void Set( LuaValue key, LuaValue value )
	{
		if ( key.Type == LuaType.Nil ) throw new LuaRuntimeException( "table index is nil" );
		if ( key.Type == LuaType.Number && double.IsNaN( key.Number ) ) throw new LuaRuntimeException( "table index is NaN" );

		if ( TryArrayIndex( key, out int i ) )
		{
			if ( i <= _array.Count )
			{
				_array[i - 1] = value;
				if ( value.IsNil && i == _array.Count ) TrimArray();
				return;
			}

			if ( i == _array.Count + 1 && !value.IsNil )
			{
				RemoveHash( key );
				_array.Add( value );
				MigrateFromHash();
				return;
			}
		}

		SetHash( key, value );
	}

	void TrimArray()
	{
		while ( _array.Count > 0 && _array[^1].IsNil )
			_array.RemoveAt( _array.Count - 1 );
	}

	void MigrateFromHash()
	{
		if ( _index is null || HashCount == 0 ) return;
		while ( true )
		{
			var next = LuaValue.FromNumber( _array.Count + 1 );
			if ( !_index.TryGetValue( next, out int slot ) ) return;
			var v = _entries[slot].Value;
			if ( v.IsNil ) return;
			RemoveHash( next );
			_array.Add( v );
		}
	}

	void SetHash( LuaValue key, LuaValue value )
	{
		if ( _index is not null && _index.TryGetValue( key, out int slot ) )
		{
			var e = _entries[slot];
			if ( e.Value.IsNil && !value.IsNil ) _tombstones--;
			else if ( !e.Value.IsNil && value.IsNil ) _tombstones++;
			e.Value = value;
			_entries[slot] = e;
			return;
		}

		if ( value.IsNil ) return;

		if ( _index is null )
		{
			_entries = new List<Entry>();
			_index = new Dictionary<LuaValue, int>();
		}
		else if ( _tombstones > 8 && _tombstones > _entries.Count / 2 )
		{
			Compact();
		}

		_index[key] = _entries.Count;
		_entries.Add( new Entry { Key = key, Value = value } );
	}

	void RemoveHash( LuaValue key )
	{
		if ( _index is null ) return;
		if ( !_index.TryGetValue( key, out int slot ) ) return;
		var e = _entries[slot];
		if ( !e.Value.IsNil )
		{
			e.Value = LuaValue.Nil;
			_entries[slot] = e;
			_tombstones++;
		}
	}

	// Only called when inserting a new key, which Lua forbids during traversal anyway.
	void Compact()
	{
		var live = new List<Entry>( _entries.Count - _tombstones );
		foreach ( var e in _entries )
			if ( !e.Value.IsNil ) live.Add( e );

		_entries = live;
		_index.Clear();
		for ( int i = 0; i < live.Count; i++ ) _index[live[i].Key] = i;
		_tombstones = 0;
	}

	/// <summary>
	/// Lua's next(): returns false when traversal is finished.
	/// Throws if <paramref name="key"/> is not a key of this table.
	/// </summary>
	public bool Next( LuaValue key, out LuaValue nextKey, out LuaValue nextValue )
	{
		int arrayStart;
		int hashStart;

		if ( key.IsNil )
		{
			arrayStart = 0;
			hashStart = 0;
		}
		else if ( TryArrayIndex( key, out int ai ) && ai <= _array.Count )
		{
			arrayStart = ai;
			hashStart = 0;
		}
		else if ( _index is not null && _index.TryGetValue( key, out int slot ) )
		{
			arrayStart = _array.Count;
			hashStart = slot + 1;
		}
		else if ( TryArrayIndex( key, out _ ) )
		{
			// An array key past the end: the traversal cleared trailing array elements (allowed in Lua), which
			// shrank the array part. Everything after it lives in the hash part.
			arrayStart = _array.Count;
			hashStart = 0;
		}
		else
		{
			throw new LuaRuntimeException( "invalid key to 'next'" );
		}

		for ( int i = arrayStart; i < _array.Count; i++ )
		{
			if ( _array[i].IsNil ) continue;
			nextKey = LuaValue.FromNumber( i + 1 );
			nextValue = _array[i];
			return true;
		}

		if ( _entries is not null )
		{
			for ( int i = hashStart; i < _entries.Count; i++ )
			{
				var e = _entries[i];
				if ( e.Value.IsNil ) continue;
				nextKey = e.Key;
				nextValue = e.Value;
				return true;
			}
		}

		nextKey = LuaValue.Nil;
		nextValue = LuaValue.Nil;
		return false;
	}

	/// <summary>Appends to the array part (t[#t+1] = v).</summary>
	public void Append( LuaValue value ) => Set( LuaValue.FromNumber( _array.Count + 1 ), value );

	/// <summary>Inserts at a 1-based position in the array part, shifting later elements up.</summary>
	public void Insert( int pos, LuaValue value )
	{
		if ( pos < 1 || pos > _array.Count + 1 ) throw new LuaRuntimeException( "bad argument #2 to 'insert' (position out of bounds)" );
		if ( value.IsNil ) { if ( pos == _array.Count + 1 ) return; }
		_array.Insert( pos - 1, value );
		MigrateFromHash();
	}

	/// <summary>Removes at a 1-based position in the array part, shifting later elements down.</summary>
	public LuaValue RemoveAt( int pos )
	{
		if ( pos < 1 || pos > _array.Count ) return LuaValue.Nil;
		var v = _array[pos - 1];
		_array.RemoveAt( pos - 1 );
		TrimArray();
		return v;
	}

	/// <summary>Direct access to the array part for library functions (1-based length = Count).</summary>
	internal List<LuaValue> ArrayPart => _array;

	public IEnumerable<KeyValuePair<LuaValue, LuaValue>> Pairs()
	{
		var k = LuaValue.Nil;
		while ( Next( k, out var nk, out var nv ) )
		{
			yield return new KeyValuePair<LuaValue, LuaValue>( nk, nv );
			k = nk;
		}
	}
}