Source file src/cuelang.org/go/internal/core/adt/context.go

Documentation: cuelang.org/go/internal/core/adt

     1  // Copyright 2020 CUE Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package adt
    16  
    17  import (
    18  	"fmt"
    19  	"log"
    20  	"os"
    21  	"reflect"
    22  	"regexp"
    23  	"sort"
    24  	"strings"
    25  
    26  	"github.com/cockroachdb/apd/v3"
    27  	"golang.org/x/text/encoding/unicode"
    28  
    29  	"cuelang.org/go/cue/ast"
    30  	"cuelang.org/go/cue/errors"
    31  	"cuelang.org/go/cue/stats"
    32  	"cuelang.org/go/cue/token"
    33  	"cuelang.org/go/internal"
    34  )
    35  
    36  // Debug sets whether extra aggressive checking should be done.
    37  // This should typically default to true for pre-releases and default to
    38  // false otherwise.
    39  var Debug bool = os.Getenv("CUE_DEBUG") != "0"
    40  
    41  // Verbosity sets the log level. There are currently only two levels:
    42  //
    43  //	0: no logging
    44  //	1: logging
    45  var Verbosity int
    46  
    47  // DebugSort specifies that arcs be sorted consistently between implementations.
    48  //
    49  //	0: default
    50  //	1: sort by Feature: this should be consistent between implementations where
    51  //		   there is no change in the compiler and indexing code.
    52  //	2: alphabetical
    53  var DebugSort int
    54  
    55  func DebugSortArcs(c *OpContext, n *Vertex) {
    56  	if n.IsList() {
    57  		return
    58  	}
    59  	switch a := n.Arcs; DebugSort {
    60  	case 1:
    61  		sort.SliceStable(a, func(i, j int) bool {
    62  			return a[i].Label < a[j].Label
    63  		})
    64  	case 2:
    65  		sort.SliceStable(a, func(i, j int) bool {
    66  			return a[i].Label.SelectorString(c.Runtime) <
    67  				a[j].Label.SelectorString(c.Runtime)
    68  		})
    69  	}
    70  }
    71  
    72  func DebugSortFields(c *OpContext, a []Feature) {
    73  	switch DebugSort {
    74  	case 1:
    75  		sort.SliceStable(a, func(i, j int) bool {
    76  			return a[i] < a[j]
    77  		})
    78  	case 2:
    79  		sort.SliceStable(a, func(i, j int) bool {
    80  			return a[i].SelectorString(c.Runtime) <
    81  				a[j].SelectorString(c.Runtime)
    82  		})
    83  	}
    84  }
    85  
    86  // Assert panics if the condition is false. Assert can be used to check for
    87  // conditions that are considers to break an internal variant or unexpected
    88  // condition, but that nonetheless probably will be handled correctly down the
    89  // line. For instance, a faulty condition could lead to error being caught
    90  // down the road, but resulting in an inaccurate error message. In production
    91  // code it is better to deal with the bad error message than to panic.
    92  //
    93  // It is advisable for each use of Assert to document how the error is expected
    94  // to be handled down the line.
    95  func Assertf(b bool, format string, args ...interface{}) {
    96  	if Debug && !b {
    97  		panic(fmt.Sprintf("assertion failed: "+format, args...))
    98  	}
    99  }
   100  
   101  // Assertf either panics or reports an error to c if the condition is not met.
   102  func (c *OpContext) Assertf(pos token.Pos, b bool, format string, args ...interface{}) {
   103  	if !b {
   104  		if Debug {
   105  			panic(fmt.Sprintf("assertion failed: "+format, args...))
   106  		}
   107  		c.addErrf(0, pos, format, args...)
   108  	}
   109  }
   110  
   111  func init() {
   112  	log.SetFlags(log.Lshortfile)
   113  }
   114  
   115  var pMap = map[*Vertex]int{}
   116  
   117  func (c *OpContext) Logf(v *Vertex, format string, args ...interface{}) {
   118  	if Verbosity == 0 {
   119  		return
   120  	}
   121  	if v == nil {
   122  		s := fmt.Sprintf(strings.Repeat("..", c.nest)+format, args...)
   123  		_ = log.Output(2, s)
   124  		return
   125  	}
   126  	p := pMap[v]
   127  	if p == 0 {
   128  		p = len(pMap) + 1
   129  		pMap[v] = p
   130  	}
   131  	a := append([]interface{}{
   132  		strings.Repeat("..", c.nest),
   133  		p,
   134  		v.Label.SelectorString(c),
   135  		v.Path(),
   136  	}, args...)
   137  	for i := 2; i < len(a); i++ {
   138  		switch x := a[i].(type) {
   139  		case Node:
   140  			a[i] = c.Str(x)
   141  		case Feature:
   142  			a[i] = x.SelectorString(c)
   143  		}
   144  	}
   145  	s := fmt.Sprintf("%s [%d] %s/%v"+format, a...)
   146  	_ = log.Output(2, s)
   147  }
   148  
   149  // PathToString creates a pretty-printed path of the given list of features.
   150  func (c *OpContext) PathToString(path []Feature) string {
   151  	var b strings.Builder
   152  	for i, f := range path {
   153  		if i > 0 {
   154  			b.WriteByte('.')
   155  		}
   156  		b.WriteString(f.SelectorString(c))
   157  	}
   158  	return b.String()
   159  }
   160  
   161  // Runtime defines an interface for low-level representation conversion and
   162  // lookup.
   163  type Runtime interface {
   164  	// StringIndexer allows for converting string labels to and from a
   165  	// canonical numeric representation.
   166  	StringIndexer
   167  
   168  	// LoadImport loads a unique Vertex associated with a given import path. It
   169  	// returns nil if no import for this package could be found.
   170  	LoadImport(importPath string) *Vertex
   171  
   172  	// StoreType associates a CUE expression with a Go type.
   173  	StoreType(t reflect.Type, src ast.Expr, expr Expr)
   174  
   175  	// LoadType retrieves a previously stored CUE expression for a given Go
   176  	// type if available.
   177  	LoadType(t reflect.Type) (src ast.Expr, expr Expr, ok bool)
   178  
   179  	EvaluatorVersion() internal.EvaluatorVersion
   180  }
   181  
   182  type Config struct {
   183  	Runtime
   184  	Format func(Node) string
   185  }
   186  
   187  // New creates an operation context.
   188  func New(v *Vertex, cfg *Config) *OpContext {
   189  	if cfg.Runtime == nil {
   190  		panic("nil Runtime")
   191  	}
   192  	ctx := &OpContext{
   193  		Runtime:     cfg.Runtime,
   194  		Format:      cfg.Format,
   195  		vertex:      v,
   196  		Version:     cfg.Runtime.EvaluatorVersion(),
   197  		taskContext: schedConfig,
   198  	}
   199  	if v != nil {
   200  		ctx.e = &Environment{Up: nil, Vertex: v}
   201  	}
   202  	return ctx
   203  }
   204  
   205  func (c *OpContext) isDevVersion() bool {
   206  	return c.Version == internal.DevVersion
   207  }
   208  
   209  // An OpContext implements CUE's unification operation. It only
   210  // operates on values that are created with the Runtime with which an OpContext
   211  // is associated. An OpContext is not goroutine safe and only one goroutine may
   212  // use an OpContext at a time.
   213  type OpContext struct {
   214  	Runtime
   215  	Format func(Node) string
   216  
   217  	Version internal.EvaluatorVersion // Copied from Runtime
   218  
   219  	taskContext
   220  
   221  	nest int
   222  
   223  	stats        stats.Counts
   224  	freeListNode *nodeContext
   225  
   226  	e         *Environment
   227  	ci        CloseInfo
   228  	src       ast.Node
   229  	errs      *Bottom
   230  	positions []Node // keep track of error positions
   231  
   232  	// vertex is used to determine the path location in case of error. Turning
   233  	// this into a stack could also allow determining the cyclic path for
   234  	// structural cycle errors.
   235  	vertex *Vertex
   236  
   237  	// These fields are used associate scratch fields for computing closedness
   238  	// of a Vertex. These fields could have been included in StructInfo (like
   239  	// Tomabechi's unification algorithm), but we opted for an indirection to
   240  	// allow concurrent unification.
   241  	//
   242  	// TODO(perf): have two generations: one for each pass of the closedness
   243  	// algorithm, so that the results of the first pass can be reused for all
   244  	// features of a node.
   245  	generation int
   246  	closed     map[*closeInfo]*closeStats
   247  	todo       *closeStats
   248  
   249  	// inDisjunct indicates that non-monotonic checks should be skipped.
   250  	// This is used if we want to do some extra work to eliminate disjunctions
   251  	// early. The result of unification should be thrown away if this check is
   252  	// used.
   253  	//
   254  	// TODO: replace this with a mechanism to determine the correct set (per
   255  	// conjunct) of StructInfos to include in closedness checking.
   256  	inDisjunct int
   257  
   258  	// inConstaint overrides inDisjunct as field matching should always be
   259  	// enabled.
   260  	inConstraint int
   261  
   262  	// inValidator defines whether full evaluation need to be enforced, for
   263  	// instance when comparing against bottom.
   264  	inValidator int
   265  
   266  	// The current call is a validator. A builtin may return a boolean false
   267  	// along with an error message describing a validation error. If the latter
   268  	// is wrapped in an internal.ValidationError, it will only be interpreted
   269  	// as an error if this is true.
   270  	// TODO: strictly separate validators and functions.
   271  	IsValidator bool
   272  
   273  	// ErrorGraphs contains an analysis, represented as a Mermaid graph, for
   274  	// each node that has an error.
   275  	ErrorGraphs map[string]string
   276  }
   277  
   278  func (c *OpContext) CloseInfo() CloseInfo { return c.ci }
   279  
   280  func (n *nodeContext) skipNonMonotonicChecks() bool {
   281  	if n.ctx.inConstraint > 0 {
   282  		return false
   283  	}
   284  	return n.ctx.inDisjunct > 0
   285  }
   286  
   287  // Impl is for internal use only. This will go.
   288  func (c *OpContext) Impl() Runtime {
   289  	return c.Runtime
   290  }
   291  
   292  func (c *OpContext) Pos() token.Pos {
   293  	if c.src == nil {
   294  		return token.NoPos
   295  	}
   296  	return c.src.Pos()
   297  }
   298  
   299  func (c *OpContext) Source() ast.Node {
   300  	return c.src
   301  }
   302  
   303  // NewContext creates an operation context.
   304  func NewContext(r Runtime, v *Vertex) *OpContext {
   305  	return New(v, &Config{Runtime: r})
   306  }
   307  
   308  func (c *OpContext) pos() token.Pos {
   309  	if c.src == nil {
   310  		return token.NoPos
   311  	}
   312  	return c.src.Pos()
   313  }
   314  
   315  func (c *OpContext) spawn(node *Vertex) *Environment {
   316  	return spawn(c.e, node)
   317  }
   318  
   319  func spawn(env *Environment, node *Vertex) *Environment {
   320  	return &Environment{
   321  		Up:     env,
   322  		Vertex: node,
   323  	}
   324  }
   325  
   326  func (c *OpContext) Env(upCount int32) *Environment {
   327  	return c.e.up(c, upCount)
   328  }
   329  
   330  func (c *OpContext) relNode(upCount int32) *Vertex {
   331  	e := c.e.up(c, upCount)
   332  	c.unify(e.Vertex, oldOnly(partial))
   333  	return e.Vertex
   334  }
   335  
   336  func (c *OpContext) relLabel(upCount int32) Feature {
   337  	// locate current label.
   338  	e := c.e.up(c, upCount)
   339  	return e.DynamicLabel
   340  }
   341  
   342  func (c *OpContext) concreteIsPossible(op Op, x Expr) bool {
   343  	if !AssertConcreteIsPossible(op, x) {
   344  		// No need to take position of expression.
   345  		c.AddErr(c.NewPosf(token.NoPos,
   346  			"invalid operand %s ('%s' requires concrete value)", x, op))
   347  		return false
   348  	}
   349  	return true
   350  }
   351  
   352  // Assert that the given expression can evaluate to a concrete value.
   353  func AssertConcreteIsPossible(op Op, x Expr) bool {
   354  	switch v := x.(type) {
   355  	case *Bottom:
   356  	case *BoundExpr:
   357  		return false
   358  	case Value:
   359  		return v.Concreteness() == Concrete
   360  	}
   361  	return true
   362  }
   363  
   364  // HasErr reports whether any error was reported, including whether value
   365  // was incomplete.
   366  func (c *OpContext) HasErr() bool {
   367  	return c.errs != nil
   368  }
   369  
   370  func (c *OpContext) Err() *Bottom {
   371  	b := c.errs
   372  	c.errs = nil
   373  	return b
   374  }
   375  
   376  func (c *OpContext) addErrf(code ErrorCode, pos token.Pos, msg string, args ...interface{}) {
   377  	err := c.NewPosf(pos, msg, args...)
   378  	c.addErr(code, err)
   379  }
   380  
   381  func (c *OpContext) addErr(code ErrorCode, err errors.Error) {
   382  	c.AddBottom(&Bottom{Code: code, Err: err})
   383  }
   384  
   385  // AddBottom records an error in OpContext.
   386  func (c *OpContext) AddBottom(b *Bottom) {
   387  	c.errs = CombineErrors(c.src, c.errs, b)
   388  }
   389  
   390  // AddErr records an error in OpContext. It returns errors collected so far.
   391  func (c *OpContext) AddErr(err errors.Error) *Bottom {
   392  	if err != nil {
   393  		c.AddBottom(&Bottom{Err: err})
   394  	}
   395  	return c.errs
   396  }
   397  
   398  // NewErrf creates a *Bottom value and returns it. The returned uses the
   399  // current source as the point of origin of the error.
   400  func (c *OpContext) NewErrf(format string, args ...interface{}) *Bottom {
   401  	// TODO: consider renaming ot NewBottomf: this is now confusing as we also
   402  	// have Newf.
   403  	err := c.Newf(format, args...)
   404  	return &Bottom{Src: c.src, Err: err, Code: EvalError}
   405  }
   406  
   407  // AddErrf records an error in OpContext. It returns errors collected so far.
   408  func (c *OpContext) AddErrf(format string, args ...interface{}) *Bottom {
   409  	return c.AddErr(c.Newf(format, args...))
   410  }
   411  
   412  type frame struct {
   413  	env *Environment
   414  	err *Bottom
   415  	src ast.Node
   416  	ci  CloseInfo
   417  }
   418  
   419  func (c *OpContext) PushState(env *Environment, src ast.Node) (saved frame) {
   420  	saved.env = c.e
   421  	saved.err = c.errs
   422  	saved.src = c.src
   423  	saved.ci = c.ci
   424  
   425  	c.errs = nil
   426  	if src != nil {
   427  		c.src = src
   428  	}
   429  	c.e = env
   430  
   431  	return saved
   432  }
   433  
   434  func (c *OpContext) PushConjunct(x Conjunct) (saved frame) {
   435  	src := x.Expr().Source()
   436  
   437  	saved.env = c.e
   438  	saved.err = c.errs
   439  	saved.src = c.src
   440  	saved.ci = c.ci
   441  
   442  	c.errs = nil
   443  	if src != nil {
   444  		c.src = src
   445  	}
   446  	c.e = x.Env
   447  	c.ci = x.CloseInfo
   448  
   449  	return saved
   450  }
   451  
   452  func (c *OpContext) PopState(s frame) *Bottom {
   453  	err := c.errs
   454  	c.e = s.env
   455  	c.errs = s.err
   456  	c.src = s.src
   457  	c.ci = s.ci
   458  	return err
   459  }
   460  
   461  // PushArc signals c that arc v is currently being processed for the purpose
   462  // of error reporting. PopArc should be called with the returned value once
   463  // processing of v is completed.
   464  func (c *OpContext) PushArc(v *Vertex) (saved *Vertex) {
   465  	c.vertex, saved = v, c.vertex
   466  	return saved
   467  }
   468  
   469  // PopArc signals completion of processing the current arc.
   470  func (c *OpContext) PopArc(saved *Vertex) {
   471  	c.vertex = saved
   472  }
   473  
   474  // Resolve finds a node in the tree.
   475  //
   476  // Should only be used to insert Conjuncts. TODO: perhaps only return Conjuncts
   477  // and error.
   478  func (c *OpContext) Resolve(x Conjunct, r Resolver) (*Vertex, *Bottom) {
   479  	return c.resolveState(x, r, final(finalized, allKnown))
   480  }
   481  
   482  func (c *OpContext) resolveState(x Conjunct, r Resolver, state combinedFlags) (*Vertex, *Bottom) {
   483  	s := c.PushConjunct(x)
   484  
   485  	arc := r.resolve(c, state)
   486  
   487  	err := c.PopState(s)
   488  	if err != nil {
   489  		return nil, err
   490  	}
   491  
   492  	if arc.ChildErrors != nil && arc.ChildErrors.Code == StructuralCycleError {
   493  		return nil, arc.ChildErrors
   494  	}
   495  
   496  	arc = arc.Indirect()
   497  
   498  	return arc, err
   499  }
   500  
   501  // Lookup looks up r in env without further resolving the value.
   502  func (c *OpContext) Lookup(env *Environment, r Resolver) (*Vertex, *Bottom) {
   503  	s := c.PushState(env, r.Source())
   504  
   505  	arc := r.resolve(c, oldOnly(partial))
   506  
   507  	err := c.PopState(s)
   508  
   509  	if arc != nil {
   510  		arc = arc.Indirect()
   511  	}
   512  
   513  	return arc, err
   514  }
   515  
   516  // Validate calls validates value for the given validator.
   517  //
   518  // TODO(errors): return boolean instead: only the caller has enough information
   519  // to generate a proper error message.
   520  func (c *OpContext) Validate(check Validator, value Value) *Bottom {
   521  	// TODO: use a position stack to push both values.
   522  	saved := c.src
   523  	c.src = check.Source()
   524  
   525  	err := check.validate(c, value)
   526  
   527  	c.src = saved
   528  
   529  	return err
   530  }
   531  
   532  // concrete returns the concrete value of x after evaluating it.
   533  // msg is used to mention the context in which an error occurred, if any.
   534  func (c *OpContext) concrete(env *Environment, x Expr, msg interface{}) (result Value, complete bool) {
   535  	s := c.PushState(env, x.Source())
   536  
   537  	state := require(partial, concreteKnown)
   538  	w := c.evalState(x, state)
   539  	_ = c.PopState(s)
   540  
   541  	w, ok := c.getDefault(w)
   542  	if !ok {
   543  		return w, false
   544  	}
   545  	v := Unwrap(w)
   546  
   547  	complete = w != nil
   548  	if !IsConcrete(v) {
   549  		complete = false
   550  		b := c.NewErrf("non-concrete value %v in operand to %s", w, msg)
   551  		b.Code = IncompleteError
   552  		v = b
   553  	}
   554  
   555  	return v, complete
   556  }
   557  
   558  // getDefault resolves a disjunction to a single value. If there is no default
   559  // value, or if there is more than one default value, it reports an "incomplete"
   560  // error and return false. In all other cases it will return true, even if
   561  // v is already an error. v may be nil, in which case it will also return nil.
   562  func (c *OpContext) getDefault(v Value) (result Value, ok bool) {
   563  	var d *Disjunction
   564  	switch x := v.(type) {
   565  	default:
   566  		return v, true
   567  
   568  	case *Vertex:
   569  		// TODO: return vertex if not disjunction.
   570  		switch t := x.BaseValue.(type) {
   571  		case *Disjunction:
   572  			d = t
   573  
   574  		case *Vertex:
   575  			return c.getDefault(t)
   576  
   577  		default:
   578  			return x, true
   579  		}
   580  
   581  	case *Disjunction:
   582  		d = x
   583  	}
   584  
   585  	if d.NumDefaults != 1 {
   586  		c.addErrf(IncompleteError, c.pos(),
   587  			"unresolved disjunction %v (type %s)", d, d.Kind())
   588  		return nil, false
   589  	}
   590  	return c.getDefault(d.Values[0])
   591  }
   592  
   593  // Evaluate evaluates an expression within the given environment and indicates
   594  // whether the result is complete. It will always return a non-nil result.
   595  func (c *OpContext) Evaluate(env *Environment, x Expr) (result Value, complete bool) {
   596  	s := c.PushState(env, x.Source())
   597  
   598  	val := c.evalState(x, final(partial, concreteKnown))
   599  
   600  	complete = true
   601  
   602  	if err, _ := val.(*Bottom); err != nil && err.IsIncomplete() {
   603  		complete = false
   604  	}
   605  	if val == nil {
   606  		complete = false
   607  		// TODO ENSURE THIS DOESN"T HAPPEN>
   608  		val = &Bottom{
   609  			Code: IncompleteError,
   610  			Err:  c.Newf("UNANTICIPATED ERROR"),
   611  		}
   612  
   613  	}
   614  
   615  	_ = c.PopState(s)
   616  
   617  	if !complete || val == nil {
   618  		return val, false
   619  	}
   620  
   621  	return val, true
   622  }
   623  
   624  func (c *OpContext) evaluateRec(v Conjunct, state combinedFlags) Value {
   625  	x := v.Expr()
   626  	s := c.PushConjunct(v)
   627  
   628  	val := c.evalState(x, state)
   629  	if val == nil {
   630  		// Be defensive: this never happens, but just in case.
   631  		Assertf(false, "nil return value: unspecified error")
   632  		val = &Bottom{
   633  			Code: IncompleteError,
   634  			Err:  c.Newf("UNANTICIPATED ERROR"),
   635  		}
   636  	}
   637  	_ = c.PopState(s)
   638  
   639  	return val
   640  }
   641  
   642  // value evaluates expression v within the current environment. The result may
   643  // be nil if the result is incomplete. value leaves errors untouched to that
   644  // they can be collected by the caller.
   645  func (c *OpContext) value(x Expr, state combinedFlags) (result Value) {
   646  	v := c.evalState(x, state)
   647  
   648  	v, _ = c.getDefault(v)
   649  	v = Unwrap(v)
   650  	return v
   651  }
   652  
   653  func (c *OpContext) evalState(v Expr, state combinedFlags) (result Value) {
   654  	savedSrc := c.src
   655  	c.src = v.Source()
   656  	err := c.errs
   657  	c.errs = nil
   658  
   659  	defer func() {
   660  		c.errs = CombineErrors(c.src, c.errs, err)
   661  
   662  		if v, ok := result.(*Vertex); ok {
   663  			if b, _ := v.BaseValue.(*Bottom); b != nil {
   664  				switch b.Code {
   665  				case IncompleteError:
   666  				case CycleError:
   667  					if state.vertexStatus() == partial || c.isDevVersion() {
   668  						break
   669  					}
   670  					fallthrough
   671  				default:
   672  					result = b
   673  				}
   674  			}
   675  		}
   676  
   677  		// TODO: remove this when we handle errors more principally.
   678  		if b, ok := result.(*Bottom); ok {
   679  			result = c.wrapCycleError(c.src, b)
   680  			if c.errs != result {
   681  				c.errs = CombineErrors(c.src, c.errs, result)
   682  			}
   683  		}
   684  		if c.errs != nil {
   685  			result = c.errs
   686  		}
   687  		c.src = savedSrc
   688  	}()
   689  
   690  	switch x := v.(type) {
   691  	case Value:
   692  		return x
   693  
   694  	case Evaluator:
   695  		v := x.evaluate(c, state)
   696  		return v
   697  
   698  	case Resolver:
   699  		arc := x.resolve(c, state)
   700  		if c.HasErr() {
   701  			return nil
   702  		}
   703  		if arc == nil {
   704  			return nil
   705  		}
   706  
   707  		// Save the old CloseInfo and restore after evaluate to avoid detecting
   708  		// spurious cycles.
   709  		saved := c.ci
   710  		if n := arc.state; n != nil {
   711  			c.ci, _ = n.markCycle(arc, nil, x, c.ci)
   712  		}
   713  		c.ci.Inline = true
   714  
   715  		if c.isDevVersion() {
   716  			if s := arc.getState(c); s != nil {
   717  				needs := state.conditions()
   718  				runMode := state.runMode()
   719  
   720  				arc.unify(c, needs|arcTypeKnown, attemptOnly) // to set scalar
   721  
   722  				if runMode == finalize {
   723  					// arc.unify(c, needs, attemptOnly) // to set scalar
   724  					// Freeze node.
   725  					arc.state.freeze(needs)
   726  				} else {
   727  					arc.unify(c, needs, runMode)
   728  				}
   729  
   730  				v := arc
   731  				if v.ArcType == ArcPending {
   732  					if v.status == evaluating {
   733  						for ; v.Parent != nil && v.ArcType == ArcPending; v = v.Parent {
   734  						}
   735  						err := c.Newf("cycle with field %v", x)
   736  						b := &Bottom{Code: CycleError, Err: err}
   737  						v.setValue(c, v.status, b)
   738  						return b
   739  						// TODO: use this instead, as is usual for incomplete errors,
   740  						// and also move this block one scope up to also apply to
   741  						// defined arcs. In both cases, though, doing so results in
   742  						// some errors to be misclassified as evaluation error.
   743  						// c.AddBottom(b)
   744  						// return nil
   745  					}
   746  					c.undefinedFieldError(v, IncompleteError)
   747  					return nil
   748  				}
   749  			}
   750  		}
   751  		v := c.evaluate(arc, x, state)
   752  		c.ci = saved
   753  		return v
   754  
   755  	default:
   756  		// This can only happen, really, if v == nil, which is not allowed.
   757  		panic(fmt.Sprintf("unexpected Expr type %T", v))
   758  	}
   759  }
   760  
   761  // wrapCycleError converts the sentinel cycleError in a concrete one with
   762  // position information.
   763  func (c *OpContext) wrapCycleError(src ast.Node, b *Bottom) *Bottom {
   764  	if src != nil &&
   765  		b.Code == CycleError &&
   766  		len(errors.Positions(b.Err)) == 0 {
   767  		bb := *b
   768  		bb.Err = errors.Wrapf(b.Err, src.Pos(), "")
   769  		b = &bb
   770  	}
   771  	return b
   772  }
   773  
   774  // unifyNode returns a possibly partially evaluated node value.
   775  //
   776  // TODO: maybe return *Vertex, *Bottom
   777  func (c *OpContext) unifyNode(v Expr, state combinedFlags) (result Value) {
   778  	savedSrc := c.src
   779  	c.src = v.Source()
   780  	err := c.errs
   781  	c.errs = nil
   782  
   783  	defer func() {
   784  		c.errs = CombineErrors(c.src, c.errs, err)
   785  
   786  		if v, ok := result.(*Vertex); ok {
   787  			if b, _ := v.BaseValue.(*Bottom); b != nil && !b.IsIncomplete() {
   788  				result = b
   789  			}
   790  		}
   791  
   792  		// TODO: remove this when we handle errors more principally.
   793  		if b, ok := result.(*Bottom); ok {
   794  			if c.src != nil &&
   795  				b.Code == CycleError &&
   796  				b.Err.Position() == token.NoPos &&
   797  				len(b.Err.InputPositions()) == 0 {
   798  				bb := *b
   799  				bb.Err = errors.Wrapf(b.Err, c.src.Pos(), "")
   800  				result = &bb
   801  			}
   802  			c.errs = CombineErrors(c.src, c.errs, result)
   803  		}
   804  		if c.errs != nil {
   805  			result = c.errs
   806  		}
   807  		c.src = savedSrc
   808  	}()
   809  
   810  	switch x := v.(type) {
   811  	case Value:
   812  		return x
   813  
   814  	case Evaluator:
   815  		v := x.evaluate(c, state)
   816  		return v
   817  
   818  	case Resolver:
   819  		v := x.resolve(c, state)
   820  		if c.HasErr() {
   821  			return nil
   822  		}
   823  		if v == nil {
   824  			return nil
   825  		}
   826  
   827  		if c.isDevVersion() {
   828  			if n := v.getState(c); n != nil {
   829  				// Always yield to not get spurious errors.
   830  				n.process(arcTypeKnown, yield)
   831  			}
   832  		} else {
   833  			if v.isUndefined() || state.vertexStatus() > v.status {
   834  				c.unify(v, state)
   835  			}
   836  		}
   837  
   838  		return v
   839  
   840  	default:
   841  		// This can only happen, really, if v == nil, which is not allowed.
   842  		panic(fmt.Sprintf("unexpected Expr type %T", v))
   843  	}
   844  }
   845  
   846  func (c *OpContext) lookup(x *Vertex, pos token.Pos, l Feature, flags combinedFlags) *Vertex {
   847  	if c.isDevVersion() {
   848  		return x.lookup(c, pos, l, flags)
   849  	}
   850  
   851  	state := flags.vertexStatus()
   852  
   853  	if l == InvalidLabel || x == nil {
   854  		// TODO: is it possible to have an invalid label here? Maybe through the
   855  		// API?
   856  		return &Vertex{}
   857  	}
   858  
   859  	// var kind Kind
   860  	// if x.BaseValue != nil {
   861  	// 	kind = x.BaseValue.Kind()
   862  	// }
   863  
   864  	switch x.BaseValue.(type) {
   865  	case *StructMarker:
   866  		if l.Typ() == IntLabel {
   867  			c.addErrf(0, pos, "invalid struct selector %v (type int)", l)
   868  			return nil
   869  		}
   870  
   871  	case *ListMarker:
   872  		switch {
   873  		case l.Typ() == IntLabel:
   874  			switch {
   875  			case l.Index() < 0:
   876  				c.addErrf(0, pos, "invalid list index %v (index must be non-negative)", l)
   877  				return nil
   878  			case l.Index() > len(x.Arcs):
   879  				c.addErrf(0, pos, "invalid list index %v (out of bounds)", l)
   880  				return nil
   881  			}
   882  
   883  		case l.IsDef(), l.IsHidden(), l.IsLet():
   884  
   885  		default:
   886  			c.addErrf(0, pos, "invalid list index %v (type string)", l)
   887  			return nil
   888  		}
   889  
   890  	case nil:
   891  		// c.addErrf(IncompleteError, pos, "incomplete value %s", x)
   892  		// return nil
   893  
   894  	case *Bottom:
   895  
   896  	default:
   897  		kind := x.BaseValue.Kind()
   898  		if kind&(ListKind|StructKind) != 0 {
   899  			// c.addErrf(IncompleteError, pos,
   900  			// 	"cannot look up %s in incomplete type %s (type %s)",
   901  			// 	l, x.Source(), kind)
   902  			// return nil
   903  		} else if !l.IsDef() && !l.IsHidden() && !l.IsLet() {
   904  			c.addErrf(0, pos,
   905  				"invalid selector %v for value of type %s", l, kind)
   906  			return nil
   907  		}
   908  	}
   909  
   910  	a := x.Lookup(l)
   911  
   912  	var hasCycle bool
   913  
   914  	if a != nil {
   915  		// Ensure that a's status is at least of the required level. Otherwise,
   916  		// ensure that any remaining unprocessed conjuncts are processed by
   917  		// calling c.Unify(a, Partial). The ensures that need to rely on
   918  		// hasAllConjuncts, but that are finalized too early, get conjuncts
   919  		// processed beforehand.
   920  		if state > a.status {
   921  			c.unify(a, deprecated(c, state))
   922  		} else if a.state != nil {
   923  			c.unify(a, deprecated(c, partial))
   924  		}
   925  
   926  		if a.IsConstraint() {
   927  			code := IncompleteError
   928  			if hasCycle {
   929  				code = CycleError
   930  			}
   931  			label := l.SelectorString(c.Runtime)
   932  			c.AddBottom(&Bottom{
   933  				Code:      code,
   934  				Permanent: x.status >= conjuncts,
   935  				Err: c.NewPosf(pos,
   936  					"cannot reference optional field: %s", label),
   937  			})
   938  		}
   939  	} else {
   940  		if x.state != nil {
   941  			for _, e := range x.state.exprs {
   942  				if isCyclePlaceholder(e.err) {
   943  					hasCycle = true
   944  				}
   945  			}
   946  		}
   947  		code := IncompleteError
   948  		// As long as we have incomplete information, we cannot mark the
   949  		// inability to look up a field as "final", as it may resolve down the
   950  		// line.
   951  		permanent := x.status > conjuncts
   952  		if m, _ := x.BaseValue.(*ListMarker); m != nil && !m.IsOpen {
   953  			permanent = true
   954  		}
   955  		if (state > partial || permanent) && !x.Accept(c, l) {
   956  			code = 0
   957  		} else if hasCycle {
   958  			code = CycleError
   959  		}
   960  		// TODO: if the struct was a literal struct, we can also treat it as
   961  		// closed and make this a permanent error.
   962  		label := l.SelectorString(c.Runtime)
   963  
   964  		// TODO(errors): add path reference and make message
   965  		//       "undefined field %s in %s"
   966  		var err *ValueError
   967  		switch {
   968  		case isCyclePlaceholder(x.BaseValue):
   969  			err = c.NewPosf(pos, "cycle error referencing %s", label)
   970  			permanent = false
   971  		case l.IsInt():
   972  			err = c.NewPosf(pos, "index out of range [%d] with length %d",
   973  				l.Index(), len(x.Elems()))
   974  		default:
   975  			err = c.NewPosf(pos, "undefined field: %s", label)
   976  		}
   977  		c.AddBottom(&Bottom{
   978  			Code:      code,
   979  			Permanent: permanent,
   980  			Err:       err,
   981  		})
   982  	}
   983  	return a
   984  }
   985  
   986  func (c *OpContext) undefinedFieldError(v *Vertex, code ErrorCode) {
   987  	label := v.Label.SelectorString(c)
   988  	c.addErrf(code, c.pos(), "undefined field: %s", label)
   989  }
   990  
   991  func (c *OpContext) Label(src Expr, x Value) Feature {
   992  	return LabelFromValue(c, src, x)
   993  }
   994  
   995  func (c *OpContext) typeError(v Value, k Kind) {
   996  	if isError(v) {
   997  		return
   998  	}
   999  	if !IsConcrete(v) && v.Kind()&k != 0 {
  1000  		c.addErrf(IncompleteError, pos(v), "incomplete %s: %s", k, v)
  1001  	} else {
  1002  		c.AddErrf("cannot use %s (type %s) as type %s", v, v.Kind(), k)
  1003  	}
  1004  }
  1005  
  1006  func (c *OpContext) typeErrorAs(v Value, k Kind, as interface{}) {
  1007  	if as == nil {
  1008  		c.typeError(v, k)
  1009  		return
  1010  	}
  1011  	if isError(v) {
  1012  		return
  1013  	}
  1014  	if !IsConcrete(v) && v.Kind()&k != 0 {
  1015  		c.addErrf(IncompleteError, pos(v),
  1016  			"incomplete %s in %v: %s", k, as, v)
  1017  	} else {
  1018  		c.AddErrf("cannot use %s (type %s) as type %s in %v", v, v.Kind(), k, as)
  1019  	}
  1020  }
  1021  
  1022  var emptyNode = &Vertex{}
  1023  
  1024  func pos(x Node) token.Pos {
  1025  	if x.Source() == nil {
  1026  		return token.NoPos
  1027  	}
  1028  	return x.Source().Pos()
  1029  }
  1030  
  1031  func (c *OpContext) node(orig Node, x Expr, scalar bool, state combinedFlags) *Vertex {
  1032  	// TODO: always get the vertex. This allows a whole bunch of trickery
  1033  	// down the line.
  1034  	v := c.unifyNode(x, state)
  1035  
  1036  	v, ok := c.getDefault(v)
  1037  	if !ok {
  1038  		// Error already generated by getDefault.
  1039  		return emptyNode
  1040  	}
  1041  
  1042  	// The two if blocks below are rather subtle. If we have an error of
  1043  	// the sentinel value cycle, we have earlier determined that the cycle is
  1044  	// allowed and that it can be ignored here. Any other CycleError is an
  1045  	// annotated cycle error that could be taken as is.
  1046  	// TODO: do something simpler.
  1047  	if scalar {
  1048  		if w := Unwrap(v); !isCyclePlaceholder(w) {
  1049  			v = w
  1050  		}
  1051  	}
  1052  
  1053  	node, ok := v.(*Vertex)
  1054  	if ok && !isCyclePlaceholder(node.BaseValue) {
  1055  		v = node.Value()
  1056  	}
  1057  
  1058  	switch nv := v.(type) {
  1059  	case nil:
  1060  		c.addErrf(IncompleteError, pos(x),
  1061  			"%s undefined (%s is incomplete)", orig, x)
  1062  		return emptyNode
  1063  
  1064  	case *Bottom:
  1065  		// TODO: this is a bit messy. In some cases errors are already added
  1066  		// and in some cases not. Not a huge deal, as errors will be uniqued
  1067  		// down the line, but could be better.
  1068  		c.AddBottom(nv)
  1069  		return emptyNode
  1070  
  1071  	case *Vertex:
  1072  		if node == nil {
  1073  			panic("unexpected markers with nil node")
  1074  		}
  1075  
  1076  	default:
  1077  		if kind := v.Kind(); kind&StructKind != 0 {
  1078  			c.addErrf(IncompleteError, pos(x),
  1079  				"%s undefined as %s is incomplete (type %s)", orig, x, kind)
  1080  			return emptyNode
  1081  
  1082  		} else if !ok {
  1083  			c.addErrf(0, pos(x), // TODO(error): better message.
  1084  				"invalid operand %s (found %s, want list or struct)",
  1085  				x.Source(), v.Kind())
  1086  			return emptyNode
  1087  		}
  1088  	}
  1089  
  1090  	return node
  1091  }
  1092  
  1093  // Elems returns the evaluated elements of a list.
  1094  func (c *OpContext) Elems(v Value) []*Vertex {
  1095  	list := c.list(v)
  1096  	list.Finalize(c)
  1097  	return list.Elems()
  1098  }
  1099  
  1100  // RawElems returns the elements of the list without evaluating them.
  1101  func (c *OpContext) RawElems(v Value) []*Vertex {
  1102  	list := c.list(v)
  1103  	return list.Elems()
  1104  }
  1105  
  1106  func (c *OpContext) list(v Value) *Vertex {
  1107  	x, ok := v.(*Vertex)
  1108  	if !ok || !x.IsList() {
  1109  		c.typeError(v, ListKind)
  1110  		return emptyNode
  1111  	}
  1112  	return x
  1113  }
  1114  
  1115  func (c *OpContext) scalar(v Value) Value {
  1116  	v = Unwrap(v)
  1117  	switch v.(type) {
  1118  	case *Null, *Bool, *Num, *String, *Bytes:
  1119  	default:
  1120  		c.typeError(v, ScalarKinds)
  1121  	}
  1122  	return v
  1123  }
  1124  
  1125  var zero = &Num{K: NumKind}
  1126  
  1127  func (c *OpContext) Num(v Value, as interface{}) *Num {
  1128  	v = Unwrap(v)
  1129  	if isError(v) {
  1130  		return zero
  1131  	}
  1132  	x, ok := v.(*Num)
  1133  	if !ok {
  1134  		c.typeErrorAs(v, NumKind, as)
  1135  		return zero
  1136  	}
  1137  	return x
  1138  }
  1139  
  1140  func (c *OpContext) Int64(v Value) int64 {
  1141  	v = Unwrap(v)
  1142  	if isError(v) {
  1143  		return 0
  1144  	}
  1145  	x, ok := v.(*Num)
  1146  	if !ok {
  1147  		c.typeError(v, IntKind)
  1148  		return 0
  1149  	}
  1150  	i, err := x.X.Int64()
  1151  	if err != nil {
  1152  		c.AddErrf("number is not an int64: %v", err)
  1153  		return 0
  1154  	}
  1155  	return i
  1156  }
  1157  
  1158  func (c *OpContext) uint64(v Value, as string) uint64 {
  1159  	v = Unwrap(v)
  1160  	if isError(v) {
  1161  		return 0
  1162  	}
  1163  	x, ok := v.(*Num)
  1164  	if !ok {
  1165  		c.typeErrorAs(v, IntKind, as)
  1166  		return 0
  1167  	}
  1168  	if x.X.Negative {
  1169  		// TODO: improve message
  1170  		c.AddErrf("cannot convert negative number to uint64")
  1171  		return 0
  1172  	}
  1173  	if !x.X.Coeff.IsUint64() {
  1174  		// TODO: improve message
  1175  		c.AddErrf("cannot convert number %s to uint64", &x.X)
  1176  		return 0
  1177  	}
  1178  	return x.X.Coeff.Uint64()
  1179  }
  1180  
  1181  func (c *OpContext) BoolValue(v Value) bool {
  1182  	return c.boolValue(v, nil)
  1183  }
  1184  
  1185  func (c *OpContext) boolValue(v Value, as interface{}) bool {
  1186  	v = Unwrap(v)
  1187  	if isError(v) {
  1188  		return false
  1189  	}
  1190  	x, ok := v.(*Bool)
  1191  	if !ok {
  1192  		c.typeErrorAs(v, BoolKind, as)
  1193  		return false
  1194  	}
  1195  	return x.B
  1196  }
  1197  
  1198  func (c *OpContext) StringValue(v Value) string {
  1199  	return c.stringValue(v, nil)
  1200  }
  1201  
  1202  // ToBytes returns the bytes value of a scalar value.
  1203  func (c *OpContext) ToBytes(v Value) []byte {
  1204  	if x, ok := v.(*Bytes); ok {
  1205  		return x.B
  1206  	}
  1207  	return []byte(c.ToString(v))
  1208  }
  1209  
  1210  // ToString returns the string value of a scalar value.
  1211  func (c *OpContext) ToString(v Value) string {
  1212  	return c.toStringValue(v, StringKind|NumKind|BytesKind|BoolKind, nil)
  1213  
  1214  }
  1215  
  1216  func (c *OpContext) stringValue(v Value, as interface{}) string {
  1217  	return c.toStringValue(v, StringKind, as)
  1218  }
  1219  
  1220  func (c *OpContext) toStringValue(v Value, k Kind, as interface{}) string {
  1221  	v = Unwrap(v)
  1222  	if isError(v) {
  1223  		return ""
  1224  	}
  1225  	if v.Kind()&k == 0 {
  1226  		if as == nil {
  1227  			c.typeError(v, k)
  1228  		} else {
  1229  			c.typeErrorAs(v, k, as)
  1230  		}
  1231  		return ""
  1232  	}
  1233  	switch x := v.(type) {
  1234  	case *String:
  1235  		return x.Str
  1236  
  1237  	case *Bytes:
  1238  		return bytesToString(x.B)
  1239  
  1240  	case *Num:
  1241  		return x.X.String()
  1242  
  1243  	case *Bool:
  1244  		if x.B {
  1245  			return "true"
  1246  		}
  1247  		return "false"
  1248  
  1249  	default:
  1250  		c.addErrf(IncompleteError, c.pos(),
  1251  			"non-concrete value %s (type %s)", v, v.Kind())
  1252  	}
  1253  	return ""
  1254  }
  1255  
  1256  func bytesToString(b []byte) string {
  1257  	b, _ = unicode.UTF8.NewDecoder().Bytes(b)
  1258  	return string(b)
  1259  }
  1260  
  1261  func (c *OpContext) bytesValue(v Value, as interface{}) []byte {
  1262  	v = Unwrap(v)
  1263  	if isError(v) {
  1264  		return nil
  1265  	}
  1266  	x, ok := v.(*Bytes)
  1267  	if !ok {
  1268  		c.typeErrorAs(v, BytesKind, as)
  1269  		return nil
  1270  	}
  1271  	return x.B
  1272  }
  1273  
  1274  var matchNone = regexp.MustCompile("^$")
  1275  
  1276  func (c *OpContext) regexp(v Value) *regexp.Regexp {
  1277  	v = Unwrap(v)
  1278  	if isError(v) {
  1279  		return matchNone
  1280  	}
  1281  	switch x := v.(type) {
  1282  	case *String:
  1283  		if x.RE != nil {
  1284  			return x.RE
  1285  		}
  1286  		// TODO: synchronization
  1287  		p, err := regexp.Compile(x.Str)
  1288  		if err != nil {
  1289  			// FatalError? How to cache error
  1290  			c.AddErrf("invalid regexp: %s", err)
  1291  			x.RE = matchNone
  1292  		} else {
  1293  			x.RE = p
  1294  		}
  1295  		return x.RE
  1296  
  1297  	case *Bytes:
  1298  		if x.RE != nil {
  1299  			return x.RE
  1300  		}
  1301  		// TODO: synchronization
  1302  		p, err := regexp.Compile(string(x.B))
  1303  		if err != nil {
  1304  			c.AddErrf("invalid regexp: %s", err)
  1305  			x.RE = matchNone
  1306  		} else {
  1307  			x.RE = p
  1308  		}
  1309  		return x.RE
  1310  
  1311  	default:
  1312  		c.typeError(v, StringKind|BytesKind)
  1313  		return matchNone
  1314  	}
  1315  }
  1316  
  1317  // newNum creates a new number of the given kind. It reports an error value
  1318  // instead if any error occurred.
  1319  func (c *OpContext) newNum(d *apd.Decimal, k Kind, sources ...Node) Value {
  1320  	if c.HasErr() {
  1321  		return c.Err()
  1322  	}
  1323  	return &Num{Src: c.src, X: *d, K: k}
  1324  }
  1325  
  1326  func (c *OpContext) NewInt64(n int64, sources ...Node) Value {
  1327  	if c.HasErr() {
  1328  		return c.Err()
  1329  	}
  1330  	d := apd.New(n, 0)
  1331  	return &Num{Src: c.src, X: *d, K: IntKind}
  1332  }
  1333  
  1334  func (c *OpContext) NewString(s string) Value {
  1335  	if c.HasErr() {
  1336  		return c.Err()
  1337  	}
  1338  	return &String{Src: c.src, Str: s}
  1339  }
  1340  
  1341  func (c *OpContext) newBytes(b []byte) Value {
  1342  	if c.HasErr() {
  1343  		return c.Err()
  1344  	}
  1345  	return &Bytes{Src: c.src, B: b}
  1346  }
  1347  
  1348  func (c *OpContext) newBool(b bool) Value {
  1349  	if c.HasErr() {
  1350  		return c.Err()
  1351  	}
  1352  	return &Bool{Src: c.src, B: b}
  1353  }
  1354  
  1355  func (c *OpContext) newList(src ast.Node, parent *Vertex) *Vertex {
  1356  	return c.newInlineVertex(parent, &ListMarker{})
  1357  }
  1358  
  1359  // Str reports a debug string of x.
  1360  func (c *OpContext) Str(x Node) string {
  1361  	if c.Format == nil {
  1362  		return fmt.Sprintf("%T", x)
  1363  	}
  1364  	return c.Format(x)
  1365  }
  1366  
  1367  // NewList returns a new list for the given values.
  1368  func (c *OpContext) NewList(values ...Value) *Vertex {
  1369  	// TODO: consider making this a literal list instead.
  1370  	list := &ListLit{}
  1371  	v := c.newInlineVertex(nil, nil, Conjunct{Env: nil, x: list})
  1372  
  1373  	for _, x := range values {
  1374  		list.Elems = append(list.Elems, x)
  1375  	}
  1376  	v.Finalize(c)
  1377  	return v
  1378  }
  1379  

View as plain text