domain.go

     1  // Copyright 2025 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  	"iter"
    10  	"maps"
    11  	"reflect"
    12  	"regexp"
    13  	"slices"
    14  	"strconv"
    15  	"strings"
    16  )
    17  
    18  // A Domain is a non-empty set of values, all of the same kind.
    19  //
    20  // Domain may be a scalar:
    21  //
    22  //   - [String] - Represents string-typed values.
    23  //
    24  // Or a composite:
    25  //
    26  //   - [Def] - A mapping from fixed keys to [Domain]s.
    27  //
    28  //   - [Tuple] - A fixed-length sequence of [Domain]s or
    29  //     all possible lengths repeating a [Domain].
    30  //
    31  // Or top or bottom:
    32  //
    33  //   - [Top] - Represents all possible values of all kinds.
    34  //
    35  //   - nil - Represents no values.
    36  //
    37  // Or a variable:
    38  //
    39  //   - [Var] - A value captured in the environment.
    40  type Domain interface {
    41  	Exact() bool
    42  	WhyNotExact() string
    43  
    44  	// decode stores this value in a Go value. If this value is not exact, this
    45  	// returns a potentially wrapped *inexactError.
    46  	decode(reflect.Value) error
    47  }
    48  
    49  type inexactError struct {
    50  	valueType string
    51  	goType    string
    52  }
    53  
    54  func (e *inexactError) Error() string {
    55  	return fmt.Sprintf("cannot store inexact %s value in %s", e.valueType, e.goType)
    56  }
    57  
    58  type decodeError struct {
    59  	path string
    60  	err  error
    61  }
    62  
    63  func newDecodeError(path string, err error) *decodeError {
    64  	if err, ok := err.(*decodeError); ok {
    65  		return &decodeError{path: path + "." + err.path, err: err.err}
    66  	}
    67  	return &decodeError{path: path, err: err}
    68  }
    69  
    70  func (e *decodeError) Unwrap() error {
    71  	return e.err
    72  }
    73  
    74  func (e *decodeError) Error() string {
    75  	return fmt.Sprintf("%s: %s", e.path, e.err)
    76  }
    77  
    78  // Top represents all possible values of all possible types.
    79  type Top struct{}
    80  
    81  func (t Top) Exact() bool         { return false }
    82  func (t Top) WhyNotExact() string { return "is top" }
    83  
    84  func (t Top) decode(rv reflect.Value) error {
    85  	// We can decode Top into a pointer-typed value as nil.
    86  	if rv.Kind() != reflect.Pointer {
    87  		return &inexactError{"top", rv.Type().String()}
    88  	}
    89  	rv.SetZero()
    90  	return nil
    91  }
    92  
    93  // A Def is a mapping from field names to [Value]s. Any fields not explicitly
    94  // listed have [Value] [Top].
    95  type Def struct {
    96  	fields map[string]*Value
    97  }
    98  
    99  // A DefBuilder builds a [Def] one field at a time. The zero value is an empty
   100  // [Def].
   101  type DefBuilder struct {
   102  	fields map[string]*Value
   103  }
   104  
   105  func (b *DefBuilder) Add(name string, v *Value) {
   106  	if b.fields == nil {
   107  		b.fields = make(map[string]*Value)
   108  	}
   109  	if old, ok := b.fields[name]; ok {
   110  		panic(fmt.Sprintf("duplicate field %q, added value is %v, old value is %v", name, v, old))
   111  	}
   112  	b.fields[name] = v
   113  }
   114  
   115  // Build constructs a [Def] from the fields added to this builder.
   116  func (b *DefBuilder) Build() Def {
   117  	return Def{maps.Clone(b.fields)}
   118  }
   119  
   120  // Exact returns true if all field Values are exact.
   121  func (d Def) Exact() bool {
   122  	for _, v := range d.fields {
   123  		if !v.Exact() {
   124  			return false
   125  		}
   126  	}
   127  	return true
   128  }
   129  
   130  // WhyNotExact returns why the value is not exact
   131  func (d Def) WhyNotExact() string {
   132  	for s, v := range d.fields {
   133  		if !v.Exact() {
   134  			w := v.WhyNotExact()
   135  			return "field " + s + ": " + w
   136  		}
   137  	}
   138  	return ""
   139  }
   140  
   141  func (d Def) decode(rv reflect.Value) error {
   142  	if rv.Kind() != reflect.Struct {
   143  		return fmt.Errorf("cannot decode Def into %s", rv.Type())
   144  	}
   145  
   146  	var lowered map[string]string // Lower case -> canonical for d.fields.
   147  	rt := rv.Type()
   148  	for fi := range rv.NumField() {
   149  		fType := rt.Field(fi)
   150  		if fType.PkgPath != "" {
   151  			continue
   152  		}
   153  		v := d.fields[fType.Name]
   154  		if v == nil {
   155  			v = topValue
   156  
   157  			// Try a case-insensitive match
   158  			canon, ok := d.fields[strings.ToLower(fType.Name)]
   159  			if ok {
   160  				v = canon
   161  			} else {
   162  				if lowered == nil {
   163  					lowered = make(map[string]string, len(d.fields))
   164  					for k := range d.fields {
   165  						l := strings.ToLower(k)
   166  						if k != l {
   167  							lowered[l] = k
   168  						}
   169  					}
   170  				}
   171  				canon, ok := lowered[strings.ToLower(fType.Name)]
   172  				if ok {
   173  					v = d.fields[canon]
   174  				}
   175  			}
   176  		}
   177  		if err := decodeReflect(v, rv.Field(fi)); err != nil {
   178  			return newDecodeError(fType.Name, err)
   179  		}
   180  	}
   181  	return nil
   182  }
   183  
   184  func (d Def) keys() []string {
   185  	return slices.Sorted(maps.Keys(d.fields))
   186  }
   187  
   188  func (d Def) All() iter.Seq2[string, *Value] {
   189  	// TODO: We call All fairly often. It's probably bad to sort this every
   190  	// time.
   191  	keys := slices.Sorted(maps.Keys(d.fields))
   192  	return func(yield func(string, *Value) bool) {
   193  		for _, k := range keys {
   194  			if !yield(k, d.fields[k]) {
   195  				return
   196  			}
   197  		}
   198  	}
   199  }
   200  
   201  // A Tuple is a sequence of Values in one of two forms: 1. a fixed-length tuple,
   202  // where each Value can be different or 2. a "repeated tuple", which is a Value
   203  // repeated 0 or more times.
   204  type Tuple struct {
   205  	vs []*Value
   206  
   207  	// repeat, if non-nil, means this Tuple consists of an element repeated 0 or
   208  	// more times. If repeat is non-nil, vs must be nil. This is a generator
   209  	// function because we don't necessarily want *exactly* the same Value
   210  	// repeated. For example, in YAML encoding, a !sum in a repeated tuple needs
   211  	// a fresh variable in each instance.
   212  	repeat []func(envSet) (*Value, envSet)
   213  }
   214  
   215  func NewTuple(vs ...*Value) Tuple {
   216  	return Tuple{vs: vs}
   217  }
   218  
   219  func NewRepeat(gens ...func(envSet) (*Value, envSet)) Tuple {
   220  	return Tuple{repeat: gens}
   221  }
   222  
   223  func (d Tuple) Exact() bool {
   224  	if d.repeat != nil {
   225  		return false
   226  	}
   227  	for _, v := range d.vs {
   228  		if !v.Exact() {
   229  			return false
   230  		}
   231  	}
   232  	return true
   233  }
   234  
   235  func (d Tuple) WhyNotExact() string {
   236  	if d.repeat != nil {
   237  		return "d.repeat is not nil"
   238  	}
   239  	for i, v := range d.vs {
   240  		if !v.Exact() {
   241  			w := v.WhyNotExact()
   242  			return "index " + strconv.FormatInt(int64(i), 10) + ": " + w
   243  		}
   244  	}
   245  	return ""
   246  }
   247  
   248  func (d Tuple) decode(rv reflect.Value) error {
   249  	if d.repeat != nil {
   250  		return &inexactError{"repeated tuple", rv.Type().String()}
   251  	}
   252  	// TODO: We could also do arrays.
   253  	if rv.Kind() != reflect.Slice {
   254  		return fmt.Errorf("cannot decode Tuple into %s", rv.Type())
   255  	}
   256  	if rv.IsNil() || rv.Cap() < len(d.vs) {
   257  		rv.Set(reflect.MakeSlice(rv.Type(), len(d.vs), len(d.vs)))
   258  	} else {
   259  		rv.SetLen(len(d.vs))
   260  	}
   261  	for i, v := range d.vs {
   262  		if err := decodeReflect(v, rv.Index(i)); err != nil {
   263  			return newDecodeError(fmt.Sprintf("%d", i), err)
   264  		}
   265  	}
   266  	return nil
   267  }
   268  
   269  // A String represents a set of strings. It can represent the intersection of a
   270  // set of regexps, or a single exact string. In general, the domain of a String
   271  // is non-empty, but we do not attempt to prove emptiness of a regexp value.
   272  type String struct {
   273  	kind  stringKind
   274  	re    []*regexp.Regexp // Intersection of regexps
   275  	exact string
   276  }
   277  
   278  type stringKind int
   279  
   280  const (
   281  	stringRegex stringKind = iota
   282  	stringExact
   283  )
   284  
   285  func NewStringRegex(exprs ...string) (String, error) {
   286  	if len(exprs) == 0 {
   287  		exprs = []string{""}
   288  	}
   289  	v := String{kind: -1}
   290  	for _, expr := range exprs {
   291  		if expr == "" {
   292  			// Skip constructing the regexp. It won't have a "literal prefix"
   293  			// and so we wind up thinking this is a regexp instead of an exact
   294  			// (empty) string.
   295  			v = String{kind: stringExact, exact: ""}
   296  			continue
   297  		}
   298  
   299  		re, err := regexp.Compile(`\A(?:` + expr + `)\z`)
   300  		if err != nil {
   301  			return String{}, fmt.Errorf("parsing value: %s", err)
   302  		}
   303  
   304  		// An exact value narrows the whole domain to exact, so we're done, but
   305  		// should keep parsing.
   306  		if v.kind == stringExact {
   307  			continue
   308  		}
   309  
   310  		if exact, complete := re.LiteralPrefix(); complete {
   311  			v = String{kind: stringExact, exact: exact}
   312  		} else {
   313  			v.kind = stringRegex
   314  			v.re = append(v.re, re)
   315  		}
   316  	}
   317  	return v, nil
   318  }
   319  
   320  func NewStringExact(s string) String {
   321  	return String{kind: stringExact, exact: s}
   322  }
   323  
   324  // Exact returns whether this Value is known to consist of a single string.
   325  func (d String) Exact() bool {
   326  	return d.kind == stringExact
   327  }
   328  
   329  func (d String) WhyNotExact() string {
   330  	if d.kind == stringExact {
   331  		return ""
   332  	}
   333  	return "string is not exact"
   334  }
   335  
   336  func (d String) decode(rv reflect.Value) error {
   337  	if d.kind != stringExact {
   338  		return &inexactError{"regex", rv.Type().String()}
   339  	}
   340  	switch rv.Kind() {
   341  	default:
   342  		return fmt.Errorf("cannot decode String into %s", rv.Type())
   343  	case reflect.String:
   344  		rv.SetString(d.exact)
   345  	case reflect.Int:
   346  		i, err := strconv.Atoi(d.exact)
   347  		if err != nil {
   348  			return fmt.Errorf("cannot decode String into %s: %s", rv.Type(), err)
   349  		}
   350  		rv.SetInt(int64(i))
   351  	case reflect.Bool:
   352  		b, err := strconv.ParseBool(d.exact)
   353  		if err != nil {
   354  			return fmt.Errorf("cannot decode String into %s: %s", rv.Type(), err)
   355  		}
   356  		rv.SetBool(b)
   357  	}
   358  	return nil
   359  }
   360
View as plain text