env_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  	"strings"
    10  	"testing"
    11  )
    12  
    13  func TestDiscriminator(t *testing.T) {
    14  	x, y, z := newIdent("x"), newIdent("y"), newIdent("z")
    15  	a := NewValue(NewStringExact("a"))
    16  	b := NewValue(NewStringExact("b"))
    17  	c := NewValue(NewStringExact("c"))
    18  
    19  	checkDisc := func(t *testing.T, e envSet, want *ident) {
    20  		t.Helper()
    21  		if e.root.kind != envSum {
    22  			t.Fatalf("want sum, got kind %d", e.root.kind)
    23  		}
    24  		if e.root.discriminator != want {
    25  			name := func(id *ident) string {
    26  				if id == nil {
    27  					return "<nil>"
    28  				}
    29  				return id.name
    30  			}
    31  			t.Errorf("want discriminator %s, got %s", name(want), name(e.root.discriminator))
    32  		}
    33  	}
    34  
    35  	t.Run("bind", func(t *testing.T) {
    36  		checkDisc(t, topEnv.bind(x, a, b), x)
    37  	})
    38  
    39  	// Each environment binds both x and y, so either can be the
    40  	// discriminator.
    41  	xa := topEnv.bind(x, a).bind(y, a)
    42  	xb := topEnv.bind(x, b).bind(y, b)
    43  	xc := topEnv.bind(x, c).bind(y, a)
    44  
    45  	t.Run("union", func(t *testing.T) {
    46  		checkDisc(t, unionEnvs(x, xa, xb), x)
    47  		checkDisc(t, unionEnvs(y, xa, xb), y)
    48  	})
    49  
    50  	t.Run("union fallback", func(t *testing.T) {
    51  		// The second environment doesn't bind x, but both bind y.
    52  		checkDisc(t, unionEnvs(x, xa, topEnv.bind(y, b)), y)
    53  	})
    54  
    55  	t.Run("infer later candidate", func(t *testing.T) {
    56  		// The first operand suggests y, but only the second operand's
    57  		// discriminator, x, is bound by every term.
    58  		u := unionEnvs(y, xa, xb)
    59  		checkDisc(t, envSet{newEnvExprSum(u.root, topEnv.bind(x, b, c).root)}, x)
    60  	})
    61  
    62  	t.Run("union no discriminator", func(t *testing.T) {
    63  		// No ident is bound by both environments.
    64  		checkDisc(t, unionEnvs(x, xa, topEnv.bind(z, b)), nil)
    65  	})
    66  
    67  	t.Run("flatten", func(t *testing.T) {
    68  		// A sum of sums with the same discriminator has that discriminator.
    69  		u := unionEnvs(x, xa, xb)
    70  		checkDisc(t, envSet{newEnvExprSum(u.root, xc.root)}, x)
    71  		checkDisc(t, envSet{newEnvExprSum(topEnv.bind(x, a).root, topEnv.bind(x, b, c).root)}, x)
    72  	})
    73  
    74  	t.Run("substitute", func(t *testing.T) {
    75  		// Substituting another ident keeps the discriminator.
    76  		u := unionEnvs(x, xa, xb, xc)
    77  		checkDisc(t, envSet{u.root.substitute(y, a)}, x)
    78  		// Substituting the discriminator removes it, but the result can
    79  		// have another discriminator.
    80  		xa2 := topEnv.bind(x, a).bind(y, b)
    81  		u = unionEnvs(x, xa, xb, xa2)
    82  		checkDisc(t, envSet{u.root.substitute(x, a)}, y)
    83  	})
    84  
    85  	t.Run("common factors", func(t *testing.T) {
    86  		// z is bound the same way in every environment, so it should be
    87  		// factored out of the sum, leaving a sum with discriminator x.
    88  		zc := topEnv.bind(z, c)
    89  		u := unionEnvs(x, crossEnvs(zc, xa), crossEnvs(zc, xb))
    90  		if u.root.kind != envProduct || len(u.root.operands) != 2 || u.root.operands[0] != zc.root {
    91  			t.Fatalf("want product of z binding and sum, got %v", u)
    92  		}
    93  		checkDisc(t, envSet{u.root.operands[1]}, x)
    94  	})
    95  
    96  	t.Run("unify", func(t *testing.T) {
    97  		read := func(s string) Closure {
    98  			c, err := Read(strings.NewReader(s), "<test>", ReadOpts{})
    99  			if err != nil {
   100  				t.Fatal(err)
   101  			}
   102  			return c
   103  		}
   104  		u, err := Unify(read("!sum [{x: a, y: 1}, {x: b, y: 2}, {x: c, y: 1}]"), read("{y: 1}"))
   105  		if err != nil {
   106  			t.Fatal(err)
   107  		}
   108  		checkDisc(t, u.env, u.val.Domain.(Var).id)
   109  	})
   110  }
   111  
   112  // BenchmarkIndependentSums unifies a def with two independent fields that
   113  // each have n alternatives, all of which survive unification. Without
   114  // factoring the binding of one field out of the sum created for the other,
   115  // the environment grows quadratically in n.
   116  func BenchmarkIndependentSums(b *testing.B) {
   117  	for _, n := range []int{100, 400} {
   118  		b.Run(fmt.Sprint("n=", n), func(b *testing.B) {
   119  			var xs, ys []string
   120  			for i := range n {
   121  				xs = append(xs, fmt.Sprint("a", i))
   122  				ys = append(ys, fmt.Sprint("b", i))
   123  			}
   124  			sums := fmt.Sprintf("{x: !sum [%s], y: !sum [%s]}", strings.Join(xs, ", "), strings.Join(ys, ", "))
   125  			c1, err := Read(strings.NewReader(`{x: "a.*", y: "b.*"}`), "<pattern>", ReadOpts{})
   126  			if err != nil {
   127  				b.Fatal(err)
   128  			}
   129  			c2, err := Read(strings.NewReader(sums), "<sums>", ReadOpts{})
   130  			if err != nil {
   131  				b.Fatal(err)
   132  			}
   133  			for b.Loop() {
   134  				if _, err := Unify(c1, c2); err != nil {
   135  					b.Fatal(err)
   136  				}
   137  			}
   138  		})
   139  	}
   140  }
   141
View as plain text