gopairs

README

gopairs

gopairs は、LuaJIT（Lua 5.1 互換）のテーブルに対して整数キーを特定の順序で挿入したときに pairs(t) が返すキーの順序を、Pure Go で再現するライブラリです。

注意：仕様上の正しい選択

Lua の仕様では、順序が必要な場合は ipairs(t) を使うべきです。
pairs(t) の順序は実装依存であり、保証されていません。

このライブラリは、pairs(t) の順序に依存せざるを得ない既存コードとの互換性を確保するためのものです。
将来的には Lua 側を ipairs(t) に移行することを推奨します。

対象バージョンと制限

• キー種別: 整数キー（int）のみ対応（LuaJIT の数値ハッシュパスを再現）
  • 非整数キー（文字列、浮動小数点、その他）には対応していません
• 配列部分（array part）のシミュレートは未対応。
  • 小さい連続した正整数キー（例: 1,2,3,... や 10,11,12）が含まれる場合、pairs(t) の順序が一致しません（配列部分が先に走査されるため）。
  • 安全に使えるキー範囲の目安: 100 以上の整数キー、または疎なキー（連続しない）。
  • 1〜100 程度の小さいキーが混在する可能性がある場合は、使用前に十分な検証をお願いします。
• LuaJIT の v2.1 タグ系列を再現
  • PuC-Rio Lua、gopher-lua、その他の Lua 実装とは順序が一致しない可能性が高いです

インストール

go get github.com/naycoma/gopairs

使い方

package main

import (
   "fmt"

   "github.com/naycoma/gopairs"
)

func main() {
   // gopairs.Debug.Store(true)

   // Unique
   keys := []int{1010, 496, -826, -475, 866}

   order := gopairs.GetPairsOrder(keys)

   fmt.Println("Input keys:", keys)
   fmt.Println("LuaJIT pairs order:", order)
   // Output: [866, -475, 1010, 496, -826]
}

GetPairsOrder は、渡したスライスの順序通りに t[k] = true を実行したときの pairs(t) のキー出現順を返します。

LuaJIT v2.1 の詳細な挙動

LuaJIT の pairs() 順序は以下の内部挙動に強く依存しており、これらをすべて正確に再現しないと一致しません：

1. 数値専用ハッシュ関数
   lj_tab.c の hashrot / hashnum を使用。標準的なハッシュとは異なり、回転と減算による特殊な混ぜ方（HASH_ROT1=14, ROT2=5, ROT3=13）。

2. 初期サイズと動的リサイズ
   空テーブルは hsize=1（hmask=0）から開始。
   ハッシュ部分が満杯になると自動で2倍拡張（hsize = 1 << newhbits）。

3. リサイズ時の再挿入順序（重要）
   古いノードを**配列インデックス順（0 → 1 → 2 → ...）**で新テーブルに再挿入。
   注意: oldhmask == 0 の場合でも index 0 のノードは再挿入される。

4. 衝突解決（Robin Hood 風）

   • 明示的な next チェインを使用。
   • 衝突時、空きノードを探して既存ノードを移動。
   • collide != mainpos の場合、既存ノードを移動した後、元の main position の val を nil にクリア。
   • これにより pairs() 時にそのスロットがスキップされる。

5. pairs() のイテレーション
   ハッシュ配列を index 0 から hmask まで前方に走査。
   チェインを辿らず、val が non-nil のノードのみを返す（tvisnil(&n->val) チェック）。

これらを1つでも間違えると、とくに複数回の衝突・リサイズが発生するケースで順序がずれます。

デバッグ出力

gopairs.Debug.Store(true)

以下の詳細が stderr に出力されます：

• キー挿入時の main position と衝突情報
• リサイズ発生時と再挿入されるキー
• チェイン操作の詳細

テスト

go test -v

注意: テストを実行するには、luajit コマンド（LuaJIT v2.1 相当）が PATH 上に必要です。
テストは実際の LuaJIT を実行して正解順序を取得し、gopairs の出力と比較しています。

ライセンス

MIT License

参考

• LuaJIT Repository v2.1
• src/lj_tab.c（lj_tab_newkey, lj_tab_resize, lj_tab_next）

Documentation

Index

• Constants
• Variables
• func GetPairsOrder(keys []int) []int
• type GCtab
• type Node
• type TValue
  • func (tv *TValue) Float64() float64
  • func (tv *TValue) SetFloat64(f float64)

Constants

const (
	HASH_ROT1 = 14
	HASH_ROT2 = 5
	HASH_ROT3 = 13
	LJ_NIL    = ^uint64(0) // 0xFFFFFFFFFFFFFFFF
)

Variables

var Debug atomic.Bool

デバッグ出力

Functions

func GetPairsOrder

func GetPairsOrder(keys []int) []int

GetPairsOrder は、指定された挿入順の整数キーに対して、 LuaJIT の pairs(t) が返す正確な順序を計算して返します。

Types

type GCtab

type GCtab struct {
	// contains filtered or unexported fields
}

type Node

type Node struct {
	// contains filtered or unexported fields
}

type TValue

type TValue struct {
	// contains filtered or unexported fields
}

func (*TValue) Float64

func (tv *TValue) Float64() float64

func (*TValue) SetFloat64

func (tv *TValue) SetFloat64(f float64)