diff_test.go

package glua

import (
	"context"
	"encoding/hex"
	"fmt"
	"math/rand/v2"
	"os"
	"os/exec"
	"path/filepath"
	"regexp"
	"strconv"
	"strings"
	"testing"
	"time"
)

// Differential fuzzing against C Lua 5.4.9: random programs, run by both, must give the same
// results or the same error messages. It needs the C Lua binary (bench/build-clua.sh, or
// GLUA_CLUA) and skips without it.
//
//	go test -run TestDifferential                          # 400 programs, a new seed each run
//	GLUA_DIFF_N=100000 GLUA_DIFF_SEED=7 go test -run TestDifferential -timeout 1h

func TestDifferential(t *testing.T) {
	if _, err := os.Stat(cluaPath()); err != nil {
		t.Skip("no C Lua: run bench/build-clua.sh")
	}
	if raceEnabled || stackStress {
		t.Skip("slow")
	}
	n, seed := 400, rand.Uint64()
	if s := os.Getenv("GLUA_DIFF_N"); s != "" {
		n, _ = strconv.Atoi(s)
	}
	if s := os.Getenv("GLUA_DIFF_SEED"); s != "" {
		seed, _ = strconv.ParseUint(s, 10, 64)
	}
	t.Logf("seed %d", seed)
	g := &progGen{r: rand.New(rand.NewPCG(seed, 1))}
	const batch = 500
	for start := 0; start < n; start += batch {
		var b strings.Builder
		b.WriteString("-- generated by TestDifferential\n") // the driver skips what comes before the first case
		var cases []luaCase
		for i := start; i < min(start+batch, n); i++ {
			name := fmt.Sprintf("p%d", i)
			src := g.program()
			cases = append(cases, luaCase{name, src})
			fmt.Fprintf(&b, "--== %s\n%s\n", name, src)
		}
		dir := t.TempDir()
		path := filepath.Join(dir, "cases.lua")
		if err := os.WriteFile(path, []byte(strings.TrimSuffix(b.String(), "\n")), 0o644); err != nil {
			t.Fatal(err)
		}
		driver := filepath.Join(dir, "driver.lua")
		if err := os.WriteFile(driver, []byte(cluaDriver), 0o644); err != nil {
			t.Fatal(err)
		}
		cStart := time.Now()
		ctx, cancel := context.WithTimeout(context.Background(), time.Minute)
		out, err := exec.CommandContext(ctx, cluaPath(), driver, path).CombinedOutput()
		timedOut := ctx.Err() != nil
		cancel()
		cTime := time.Since(cStart)
		if timedOut {
			t.Logf("C Lua did not finish the batch at %d in a minute; skipped", start)
			continue
		}
		if err != nil {
			t.Fatalf("C Lua: %v\n%s", err, out)
		}
		want := map[string]string{}
		for line := range strings.Lines(string(out)) {
			name, res, _ := strings.Cut(strings.TrimSuffix(line, "\n"), "\t")
			want[name] = res
		}
		failed := 0
		goStart := time.Now()
		for _, c := range cases {
			cs := time.Now()
			got := outcome(c.name, c.src)
			if d := time.Since(cs); d > 2*time.Second {
				t.Logf("%s took %v in glua:\n%s", c.name, d, c.src)
			}
			norm := func(s string) string {
				s = hexAddrs(s)
				return fmodArg.ReplaceAllString(nanSign.Replace(addrs.ReplaceAllString(s, "0x")), "#? to 'fmod' (number expected)")
			}
			if norm(got) != norm(want[c.name]) {
				t.Errorf("%s differs (seed %d)\n%s\n got: %s\nwant: %s", c.name, seed, c.src, got, want[c.name])
				if failed++; failed > 5 && os.Getenv("GLUA_DIFF_ALL") == "" {
					t.FailNow()
				}
			}
		}
		if d := time.Since(goStart); d > 10*time.Second || cTime > 10*time.Second {
			t.Logf("batch at %d: C Lua %v, glua %v", start, cTime, d)
		}
	}
}

// hexAddrs hides addresses inside the hex-encoded strings of a rendered result, as addrs
// does outside them: tostring of a table or function gives one. Padding around an address,
// from string.format's widths, goes too, as its length depends on the address's. So does
// the sign of a NaN, which C libraries do not agree on, as nanSign does outside strings.
func hexAddrs(s string) string {
	return hexStr.ReplaceAllStringFunc(s, func(m string) string {
		b, err := hex.DecodeString(m[4:])
		if err != nil {
			return m
		}
		return "str:" + hex.EncodeToString([]byte(nanSign.Replace(paddedAddr.ReplaceAllString(string(b), "$1 0x"))))
	})
}

var (
	hexStr     = regexp.MustCompile(`str:[0-9a-f]*`)
	paddedAddr = regexp.MustCompile(` *([a-z]+:) 0x[0-9a-f]+ *`)
)

// fmodArg hides which argument math.fmod names when neither is a number: C Lua checks both
// in one call expression, so the order depends on the compiler, and gcc differs between
// amd64 and arm64.
var fmodArg = regexp.MustCompile(`#[12] to 'fmod' \(number expected, got [a-z ]+\)`)

// progGen writes random Lua programs from a small grammar: locals, arithmetic, strings,
// tables, library calls, control flow and pcall, all deterministic.
type progGen struct {
	r     *rand.Rand
	vars  []string // expressions that read a variable
	names []string // the variables, which can be assigned
	depth int
	b     strings.Builder
}

func (g *progGen) pick(xs ...string) string { return xs[g.r.IntN(len(xs))] }

func (g *progGen) program() string {
	if g.r.IntN(3) == 0 {
		return g.libProgram()
	}
	g.b.Reset()
	g.vars, g.names = g.vars[:0], g.names[:0]
	for range 2 + g.r.IntN(4) {
		g.local()
	}
	for range g.r.IntN(5) {
		g.stmt(0)
	}
	fmt.Fprintf(&g.b, "return %s, %s", g.expr(), g.expr())
	return g.b.String()
}

func (g *progGen) local() {
	name := fmt.Sprintf("v%d", len(g.vars))
	fmt.Fprintf(&g.b, "local %s = %s\n", name, g.expr())
	g.vars = append(g.vars, name)
	g.names = append(g.names, name)
}

func (g *progGen) stmt(level int) {
	if level > 2 {
		return
	}
	switch g.r.IntN(7) {
	case 0:
		g.local()
	case 1:
		if len(g.names) > 0 {
			fmt.Fprintf(&g.b, "%s = %s\n", g.names[g.r.IntN(len(g.names))], g.expr())
		}
	case 2:
		fmt.Fprintf(&g.b, "if %s then\n", g.expr())
		g.stmt(level + 1)
		g.b.WriteString("else\n")
		g.stmt(level + 1)
		g.b.WriteString("end\n")
	case 3:
		v := fmt.Sprintf("i%d", g.r.IntN(100))
		fmt.Fprintf(&g.b, "for %s = %s, %s, %s do\n", v, g.small(), g.small(), g.pick("1", "2", "-1", "3"))
		if len(g.names) > 0 {
			acc := g.names[g.r.IntN(len(g.names))]
			fmt.Fprintf(&g.b, "%s = %s\n", acc, g.binop(acc, v))
		}
		g.b.WriteString("end\n")
	case 4:
		e := fmt.Sprintf("e%d", len(g.vars))
		fmt.Fprintf(&g.b, "local ok%d, %s = pcall(function() return %s end)\n", len(g.vars), e, g.expr())
		g.vars, g.names = append(g.vars, e), append(g.names, e)
	case 5:
		name := fmt.Sprintf("v%d", len(g.vars))
		fmt.Fprintf(&g.b, "local %s = {%s, %s, k = %s}\n", name, g.expr(), g.expr(), g.expr())
		g.vars = append(g.vars, name+"[1]", name+".k", "#"+name)
	case 6:
		name := fmt.Sprintf("f%d", len(g.vars))
		fmt.Fprintf(&g.b, "local function %s(a, b) return %s end\n", name, g.binop("a", "b"))
		g.vars = append(g.vars, fmt.Sprintf("%s(%s, %s)", name, g.atom(), g.atom()))
	}
}

func (g *progGen) small() string { return strconv.Itoa(g.r.IntN(9) - 2) }

func (g *progGen) atom() string {
	if len(g.vars) > 0 && g.r.IntN(2) == 0 {
		return g.vars[g.r.IntN(len(g.vars))]
	}
	return g.pick("0", "1", "-1", "2", "3", "7", "10", "255", "-7", "100",
		"9223372036854775807", "math.mininteger", "0.5", "-2.5", "3.0", "1e15", "1e300", "-0.0",
		"1/0", "0x10", "0xff", "'abc'", "''", "'10'", "' 3 '", "'0x1A'", "'1e2'", "'héllo'",
		"true", "false", "nil", "'a,b,,c'", "'%d'")
}

func (g *progGen) binop(a, b string) string {
	op := g.pick("+", "-", "*", "/", "//", "%", "^", "..", "==", "~=", "<", "<=", ">", ">=",
		"and", "or", "&", "|", "~", "<<", ">>")
	return "(" + a + " " + op + " " + b + ")"
}

func (g *progGen) expr() string {
	if g.depth > 3 {
		return g.atom()
	}
	g.depth++
	defer func() { g.depth-- }()
	switch g.r.IntN(12) {
	case 0, 1, 2:
		return g.atom()
	case 3, 4, 5:
		return g.binop(g.expr(), g.expr())
	case 6:
		return "(" + g.pick("-", "not ", "#", "~") + g.expr() + ")"
	case 7:
		return g.pick("math.floor", "math.ceil", "math.abs", "math.tointeger", "math.type", "tostring",
			"tonumber", "type", "string.upper", "string.len", "string.reverse", "math.sqrt") + "(" + g.expr() + ")"
	case 8:
		if g.r.IntN(10) == 0 { // a small count: C Lua repeats an empty string count times
			return "string.rep(" + g.expr() + ", " + g.small() + ")"
		}
		return g.pick("math.max", "math.min", "math.fmod", "math.ult", "string.byte",
			"select", "string.sub", "rawequal", "tonumber") + "(" + g.expr() + ", " + g.expr() + ")"
	case 9:
		return g.pick("string.format('%d|%s', ", "string.format('%5.2f %x', ", "string.format('%q %g', ",
			"string.find(", "string.match(", "string.gsub(", "utf8.char(") + g.expr() + ", " + g.expr() + ")"
	case 10:
		return "select(2, pcall(" + g.pick("error", "table.concat", "setmetatable",
			"string.char", "utf8.codepoint") + ", " + g.expr() + "))"
	default:
		return "table.concat({" + g.expr() + ", " + g.expr() + "}, " + g.pick("','", "''", "'-'") + ")"
	}
}