fastpath_test.go

     1  // Copyright 2026 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package unify
     6  
     7  import (
     8  	"fmt"
     9  	"math/rand/v2"
    10  	"slices"
    11  	"strings"
    12  	"testing"
    13  )
    14  
    15  // TestFastPaths checks that unification optimizations don't change the results
    16  // of unification by comparing unification of random inputs with and without
    17  // them. Some optimizations change the order of the results, so this ignores
    18  // the order.
    19  func TestFastPaths(t *testing.T) {
    20  	n := 500
    21  	if testing.Short() {
    22  		n = 100
    23  	}
    24  	for seed := range uint64(n) {
    25  		r := rand.New(rand.NewPCG(seed, 0))
    26  		var inputs []string
    27  		for range 2 + r.IntN(2) {
    28  			inputs = append(inputs, randYAML(r, 0))
    29  		}
    30  
    31  		fast := unifyAllString(inputs)
    32  		debugNoFastPaths = true
    33  		slow := unifyAllString(inputs)
    34  		debugNoFastPaths = false
    35  
    36  		if fast != slow {
    37  			t.Errorf("seed %d: results differ\ninputs:\n%s\nwith fast paths:\n%s\nwithout fast paths:\n%s", seed, strings.Join(inputs, "\n"), fast, slow)
    38  		}
    39  	}
    40  }
    41  
    42  // unifyAllString unifies inputs and returns a string containing all values of
    43  // the result, sorted, or the error or panic message.
    44  func unifyAllString(inputs []string) (res string) {
    45  	defer func() {
    46  		if p := recover(); p != nil {
    47  			res = fmt.Sprintf("panic: %v", p)
    48  		}
    49  	}()
    50  
    51  	var cs []Closure
    52  	for i, in := range inputs {
    53  		c, err := Read(strings.NewReader(in), fmt.Sprintf("input%d", i), ReadOpts{})
    54  		if err != nil {
    55  			return fmt.Sprintf("error: %v", err)
    56  		}
    57  		cs = append(cs, c)
    58  	}
    59  	c, err := Unify(cs...)
    60  	if err != nil {
    61  		return fmt.Sprintf("error: %v", err)
    62  	}
    63  	const limit = 100
    64  	var vals []string
    65  	for v := range c.All() {
    66  		if len(vals) == limit {
    67  			return fmt.Sprintf("more than %d values", limit)
    68  		}
    69  		vals = append(vals, fmt.Sprintf("- %s", v))
    70  	}
    71  	slices.Sort(vals)
    72  	return strings.Join(vals, "")
    73  }
    74  
    75  // randYAML returns a random YAML def. The values are biased toward sums,
    76  // variables, and small alphabets so that inputs are likely to partly unify.
    77  // In practice, almost all inputs unify to at least one value, and most to
    78  // several.
    79  // They follow a fixed schema so that unification rarely fails with a kind
    80  // mismatch: field f is a string, g is a def, and h is a tuple.
    81  //
    82  // Unification can create infinite values (and overflow the stack) when the
    83  // same variable appears in some alternatives of a sum and elsewhere, so this
    84  // never generates variables inside sums.
    85  func randYAML(r *rand.Rand, depth int) string {
    86  	return randDef(r, depth, true)
    87  }
    88  
    89  // randSum returns either a value generated by gen or a sum of 2 or 3 values
    90  // generated by gen. It passes whether variables are allowed to gen.
    91  func randSum(r *rand.Rand, vars bool, gen func(vars bool) string) string {
    92  	if r.IntN(2) == 0 {
    93  		return gen(vars)
    94  	}
    95  	var elts []string
    96  	for range 2 + r.IntN(2) {
    97  		elts = append(elts, gen(false))
    98  	}
    99  	return "!sum [" + strings.Join(elts, ", ") + "]"
   100  }
   101  
   102  func randDef(r *rand.Rand, depth int, vars bool) string {
   103  	if vars && depth == 1 && r.IntN(8) == 0 {
   104  		// Use $d at only one depth. Otherwise, it may be unified with a
   105  		// value that contains it.
   106  		return "$d"
   107  	}
   108  	return randSum(r, vars, func(vars bool) string {
   109  		var fields []string
   110  		if r.IntN(4) != 0 {
   111  			fields = append(fields, "f: "+randString(r, vars))
   112  		}
   113  		if depth < 2 && r.IntN(2) == 0 {
   114  			fields = append(fields, "g: "+randDef(r, depth+1, vars))
   115  		}
   116  		if depth < 2 && r.IntN(3) == 0 {
   117  			fields = append(fields, "h: "+randTuple(r, vars))
   118  		}
   119  		return "{" + strings.Join(fields, ", ") + "}"
   120  	})
   121  }
   122  
   123  func randTuple(r *rand.Rand, vars bool) string {
   124  	return randSum(r, vars, func(vars bool) string {
   125  		if r.IntN(3) == 0 {
   126  			// Named variables in !repeat elements don't work.
   127  			return "!repeat [" + randString(r, false) + "]"
   128  		}
   129  		var elts []string
   130  		for range 1 + r.IntN(2) {
   131  			elts = append(elts, randString(r, vars))
   132  		}
   133  		return "[" + strings.Join(elts, ", ") + "]"
   134  	})
   135  }
   136  
   137  func randString(r *rand.Rand, vars bool) string {
   138  	if vars && r.IntN(3) == 0 {
   139  		return "$" + []string{"x", "y"}[r.IntN(2)]
   140  	}
   141  	return randSum(r, vars, func(bool) string {
   142  		switch r.IntN(6) {
   143  		case 0:
   144  			return "_"
   145  		case 1:
   146  			return `"a|b"`
   147  		}
   148  		return []string{"a", "b", "c"}[r.IntN(3)]
   149  	})
   150  }
   151
View as plain text