tables.go

package lua

import (
	"math"
)

type table struct {
	array             []value
	hash              map[value]value
	metaTable         *table
	flags             byte
	iterationKeys     []value
	iterationKeyIndex map[value]int // key -> index in iterationKeys for O(1) lookup
}

func newTable() *table                     { return &table{hash: make(map[value]value)} }
func (t *table) invalidateTagMethodCache() { t.flags = 0 }
func (t *table) atString(k string) value   { return t.hash[k] }

func newTableWithSize(arraySize, hashSize int) *table {
	t := new(table)
	if arraySize > 0 {
		t.array = make([]value, arraySize)
	}
	if hashSize > 0 {
		t.hash = make(map[value]value, hashSize)
	} else {
		t.hash = make(map[value]value)
	}
	return t
}

func (l *State) fastTagMethod(table *table, event tm) value {
	if table == nil || table.flags&1<<event != 0 {
		return nil
	}
	return table.tagMethod(event, l.global.tagMethodNames[event])
}

func (t *table) extendArray(last int) {
	t.array = append(t.array, make([]value, last-len(t.array))...)
	for k, v := range t.hash {
		var i int
		switch n := k.(type) {
		case int64:
			i = int(n)
		case float64:
			if float64(int(n)) != n {
				continue
			}
			i = int(n)
		default:
			continue
		}
		if 0 < i && i <= len(t.array) {
			t.array[i-1] = v
			delete(t.hash, k)
		}
	}
}

func (t *table) atInt(k int) value {
	if 0 < k && k <= len(t.array) {
		return t.array[k-1]
	}
	// Try int64 key first (Lua 5.3 style), then float64 for backwards compat
	if v := t.hash[int64(k)]; v != nil {
		return v
	}
	return t.hash[float64(k)]
}

func (t *table) maybeResizeArray(key int) bool {
	// Precondition: key > len(t.array).
	occupancy := 0
	for _, v := range t.array {
		if v != nil {
			occupancy++
		}
	}
	for k, v := range t.hash {
		if v == nil {
			continue
		}
		var i int
		switch n := k.(type) {
		case int64:
			i = int(n)
		case float64:
			if float64(int(n)) != n {
				continue
			}
			i = int(n)
		default:
			continue
		}
		if i <= key {
			occupancy++
		}
	}
	if occupancy >= key>>1 {
		t.extendArray(max(occupancy*2, key)) // TODO Tune growth function.
		return true
	}
	return false
}

func (t *table) addOrInsertHash(k, v value) {
	if _, ok := t.hash[k]; !ok {
		t.iterationKeys = nil // invalidate iterations when adding an entry
		t.iterationKeyIndex = nil
	}
	t.hash[k] = v
}

func (t *table) putAtInt(k int, v value) {
	if 0 < k && k <= len(t.array) {
		t.array[k-1] = v
	} else if k > 0 && v != nil && t.maybeResizeArray(k) {
		t.array[k-1] = v
	} else if v == nil {
		// Delete both int64 and float64 keys for backwards compat
		delete(t.hash, int64(k))
		delete(t.hash, float64(k))
	} else {
		t.addOrInsertHash(int64(k), v)
	}
}

func (t *table) at(k value) value {
	switch k := k.(type) {
	case nil:
		return nil
	case int64:
		i := int(k)
		if 0 < i && i <= len(t.array) {
			return t.array[i-1]
		}
		// Try int64 first, then float64 for backwards compat
		if v := t.hash[k]; v != nil {
			return v
		}
		return t.hash[float64(k)]
	case float64:
		if i := int(k); float64(i) == k { // OPT: Inlined copy of atInt.
			if 0 < i && i <= len(t.array) {
				return t.array[i-1]
			}
			// Try int64 first, then float64 for backwards compat
			if v := t.hash[int64(i)]; v != nil {
				return v
			}
			return t.hash[k]
		}
	case string:
		return t.hash[k]
	}
	return t.hash[k]
}

func (t *table) put(l *State, k, v value) {
	switch k := k.(type) {
	case nil:
		l.runtimeError("table index is nil")
	case int64:
		t.putAtInt(int(k), v)
	case float64:
		if i := int(k); float64(i) == k {
			t.putAtInt(i, v)
		} else if math.IsNaN(k) {
			l.runtimeError("table index is NaN")
		} else if v == nil {
			delete(t.hash, k)
		} else {
			t.addOrInsertHash(k, v)
		}
	case string:
		if v == nil {
			delete(t.hash, k)
		} else {
			t.addOrInsertHash(k, v)
		}
	default:
		if v == nil {
			delete(t.hash, k)
		} else {
			t.addOrInsertHash(k, v)
		}
	}
}

// OPT: tryPut is an optimized variant of the at/put pair used by setTableAt to avoid hashing the key twice.
func (t *table) tryPut(l *State, k, v value) bool {
	switch k := k.(type) {
	case nil:
	case int64:
		i := int(k)
		if 0 < i && i <= len(t.array) && t.array[i-1] != nil {
			t.array[i-1] = v
			return true
		} else if t.hash[k] != nil && v != nil {
			t.hash[k] = v
			return true
		}
	case float64:
		if i := int(k); float64(i) == k && 0 < i && i <= len(t.array) && t.array[i-1] != nil {
			t.array[i-1] = v
			return true
		} else if math.IsNaN(k) {
			return false
		} else if t.hash[k] != nil && v != nil {
			t.hash[k] = v
			return true
		}
	case string:
		if t.hash[k] != nil && v != nil {
			t.hash[k] = v
			return true
		}
	default:
		if t.hash[k] != nil && v != nil {
			t.hash[k] = v
			return true
		}
	}
	return false
}

func (t *table) unboundSearch(j int) int {
	i := j
	for j++; nil != t.atInt(j); {
		i = j
		if j *= 2; j < 0 {
			for i = 1; nil != t.atInt(i); i++ {
			}
			return i - 1
		}
	}
	for j-i > 1 {
		m := (i + j) / 2
		if nil == t.atInt(m) {
			j = m
		} else {
			i = m
		}
	}
	return i
}

func (t *table) length() int {
	j := len(t.array)
	if j > 0 && t.array[j-1] == nil {
		i := 0
		for j-i > 1 {
			m := (i + j) / 2
			if t.array[m-1] == nil {
				j = m
			} else {
				i = m
			}
		}
		return i
	} else if t.hash == nil {
		return j
	}
	return t.unboundSearch(j)
}

func arrayIndex(k value) int {
	switch n := k.(type) {
	case int64:
		return int(n)
	case float64:
		if i := int(n); float64(i) == n {
			return i
		}
	}
	return -1
}

func (l *State) next(t *table, key int) bool {
	i, k := 0, l.stack[key]
	keyInHash := false
	if k == nil { // first iteration
	} else if i = arrayIndex(k); 0 < i && i <= len(t.array) {
		k = nil
	} else if _, ok := t.hash[k]; ok {
		keyInHash = true
		i = len(t.array)
	} else {
		// Key not in hash - might have been deleted during iteration
		// We'll check iterationKeys below; if not found there, error
		i = len(t.array)
	}
	for ; i < len(t.array); i++ {
		if t.array[i] != nil {
			l.stack[key] = int64(i + 1)
			l.stack[key+1] = t.array[i]
			return true
		}
	}
	if t.iterationKeys == nil {
		keys := make([]value, len(t.hash))
		idx := make(map[value]int, len(t.hash))
		j := 0
		for hk := range t.hash {
			keys[j] = hk
			idx[hk] = j
			j++
		}
		t.iterationKeys = keys
		t.iterationKeyIndex = idx
	}
	// Determine starting position in iterationKeys
	startPos := 0
	if k != nil {
		// Look up current key's position via O(1) index map
		if pos, ok := t.iterationKeyIndex[k]; ok {
			startPos = pos + 1
		} else {
			// Key not found in index — invalid key
			if !keyInHash {
				l.runtimeError("invalid key to 'next'")
			}
			return false
		}
	}
	// Find next valid entry starting from startPos
	for j := startPos; j < len(t.iterationKeys); j++ {
		hk := t.iterationKeys[j]
		if hk == nil {
			continue
		}
		// Check if key was deleted from hash
		if _, present := t.hash[hk]; !present {
			t.iterationKeys[j] = nil
			delete(t.iterationKeyIndex, hk)
			continue
		}
		l.stack[key] = hk
		l.stack[key+1] = t.hash[hk]
		return true
	}
	return false // no more elements
}