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;
}
}
}