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

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

     1  // Copyright 2021 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 eval contains the high level CUE evaluation strategy.
    16  //
    17  // CUE allows for a significant amount of freedom in order of evaluation due to
    18  // the commutativity of the unification operation. This package implements one
    19  // of the possible strategies.
    20  package adt
    21  
    22  // TODO:
    23  //   - result should be nodeContext: this allows optionals info to be extracted
    24  //     and computed.
    25  //
    26  
    27  import (
    28  	"fmt"
    29  
    30  	"cuelang.org/go/cue/ast"
    31  	"cuelang.org/go/cue/errors"
    32  	"cuelang.org/go/cue/stats"
    33  	"cuelang.org/go/cue/token"
    34  )
    35  
    36  // TODO TODO TODO TODO TODO TODO  TODO TODO TODO  TODO TODO TODO  TODO TODO TODO
    37  //
    38  // - Reuse work from previous cycles. For instance, if we can guarantee that a
    39  //   value is always correct for partial results, we can just process the arcs
    40  //   going from Partial to Finalized, without having to reevaluate the value.
    41  //
    42  // - Test closedness far more thoroughly.
    43  //
    44  
    45  func (c *OpContext) Stats() *stats.Counts {
    46  	return &c.stats
    47  }
    48  
    49  // TODO: Note: NewContext takes essentially a cue.Value. By making this
    50  // type more central, we can perhaps avoid context creation.
    51  
    52  // func NewContext(r Runtime, v *Vertex) *OpContext {
    53  // 	e := NewUnifier(r)
    54  // 	return e.NewContext(v)
    55  // }
    56  
    57  var structSentinel = &StructMarker{}
    58  
    59  var incompleteSentinel = &Bottom{
    60  	Code: IncompleteError,
    61  	Err:  errors.Newf(token.NoPos, "incomplete"),
    62  }
    63  
    64  // evaluate returns the evaluated value associated with v. It may return a
    65  // partial result. That is, if v was not yet unified, it may return a
    66  // concrete value that must be the result assuming the configuration has no
    67  // errors.
    68  //
    69  // This semantics allows CUE to break reference cycles in a straightforward
    70  // manner.
    71  //
    72  // Vertex v must still be evaluated at some point to catch the underlying
    73  // error.
    74  //
    75  // TODO: return *Vertex
    76  func (c *OpContext) evaluate(v *Vertex, r Resolver, state combinedFlags) Value {
    77  	if v.isUndefined() {
    78  		// Use node itself to allow for cycle detection.
    79  		c.unify(v, state)
    80  
    81  		if v.ArcType == ArcPending {
    82  			if v.status == evaluating {
    83  				for ; v.Parent != nil && v.ArcType == ArcPending; v = v.Parent {
    84  				}
    85  				err := c.Newf("cycle with field %v", r)
    86  				b := &Bottom{Code: CycleError, Err: err}
    87  				v.setValue(c, v.status, b)
    88  				return b
    89  				// TODO: use this instead, as is usual for incomplete errors,
    90  				// and also move this block one scope up to also apply to
    91  				// defined arcs. In both cases, though, doing so results in
    92  				// some errors to be misclassified as evaluation error.
    93  				// c.AddBottom(b)
    94  				// return nil
    95  			}
    96  			c.undefinedFieldError(v, IncompleteError)
    97  			return nil
    98  		}
    99  	}
   100  
   101  	if n := v.state; n != nil {
   102  		if n.errs != nil && !n.errs.IsIncomplete() {
   103  			return n.errs
   104  		}
   105  		if n.scalar != nil && isCyclePlaceholder(v.BaseValue) {
   106  			return n.scalar
   107  		}
   108  	}
   109  
   110  	switch x := v.BaseValue.(type) {
   111  	case *Bottom:
   112  		if x.IsIncomplete() {
   113  			c.AddBottom(x)
   114  			return nil
   115  		}
   116  		return x
   117  
   118  	case nil:
   119  		if v.state != nil {
   120  			switch x := v.state.getValidators(finalized).(type) {
   121  			case Value:
   122  				return x
   123  			default:
   124  				w := *v
   125  				w.BaseValue = x
   126  				return &w
   127  			}
   128  		}
   129  		// This may happen if the evaluator is invoked outside of regular
   130  		// evaluation, such as in dependency analysis.
   131  		return nil
   132  	}
   133  
   134  	if v.status < finalized && v.state != nil {
   135  		// TODO: errors are slightly better if we always add addNotify, but
   136  		// in this case it is less likely to cause a performance penalty.
   137  		// See https://cuelang.org/issue/661. It may be possible to
   138  		// relax this again once we have proper tests to prevent regressions of
   139  		// that issue.
   140  		if !v.state.done() || v.state.errs != nil {
   141  			v.state.addNotify(c.vertex, nil)
   142  		}
   143  	}
   144  
   145  	return v
   146  }
   147  
   148  // unify unifies values of a Vertex to and stores the result in the Vertex. If
   149  // unify was called on v before it returns the cached results.
   150  // state can be used to indicate to which extent processing should continue.
   151  // state == finalized means it is evaluated to completion. See vertexStatus
   152  // for more details.
   153  func (c *OpContext) unify(v *Vertex, flags combinedFlags) {
   154  	if c.isDevVersion() {
   155  		requires, mode := flags.conditions(), flags.runMode()
   156  		v.unify(c, requires, mode)
   157  		return
   158  	}
   159  
   160  	// defer c.PopVertex(c.PushVertex(v))
   161  	if Debug {
   162  		c.nest++
   163  		c.Logf(v, "Unify")
   164  		defer func() {
   165  			c.Logf(v, "END Unify")
   166  			c.nest--
   167  		}()
   168  	}
   169  
   170  	// Ensure a node will always have a nodeContext after calling Unify if it is
   171  	// not yet Finalized.
   172  	n := v.getNodeContext(c, 1)
   173  	defer v.freeNode(n)
   174  
   175  	state := flags.vertexStatus()
   176  
   177  	// TODO(cycle): verify this happens in all cases when we need it.
   178  	if n != nil && v.Parent != nil && v.Parent.state != nil {
   179  		n.depth = v.Parent.state.depth + 1
   180  	}
   181  
   182  	if state <= v.Status() &&
   183  		state == partial &&
   184  		v.isDefined() &&
   185  		n != nil && n.scalar != nil {
   186  		return
   187  	}
   188  
   189  	switch v.Status() {
   190  	case evaluating:
   191  		n.insertConjuncts(state)
   192  		return
   193  
   194  	case evaluatingArcs:
   195  		Assertf(v.status > 0, "unexpected status %d", v.status)
   196  		return
   197  
   198  	case 0:
   199  		if v.Label.IsDef() {
   200  			v.Closed = true
   201  		}
   202  
   203  		if v.Parent != nil {
   204  			if v.Parent.Closed {
   205  				v.Closed = true
   206  			}
   207  		}
   208  
   209  		defer c.PopArc(c.PushArc(v))
   210  
   211  		v.updateStatus(evaluating)
   212  
   213  		if p := v.Parent; p != nil && p.state != nil && v.Label.IsString() {
   214  			for _, s := range p.state.node.Structs {
   215  				if s.Disable {
   216  					continue
   217  				}
   218  				s.MatchAndInsert(n.ctx, v)
   219  			}
   220  		}
   221  
   222  		c.stats.Unifications++
   223  
   224  		// Set the cache to a cycle error to ensure a cyclic reference will result
   225  		// in an error if applicable. A cyclic error may be ignored for
   226  		// non-expression references. The cycle error may also be removed as soon
   227  		// as there is evidence what a correct value must be, but before all
   228  		// validation has taken place.
   229  		//
   230  		// TODO(cycle): having a more recursive algorithm would make this
   231  		// special cycle handling unnecessary.
   232  		v.BaseValue = cycle
   233  
   234  		if c.HasErr() {
   235  			n.addBottom(c.errs)
   236  		}
   237  
   238  		// NOTE: safeguard against accidentally entering the 'unprocessed' state
   239  		// twice.
   240  		n.conjuncts = n.conjuncts[:0]
   241  
   242  		for i, c := range v.Conjuncts {
   243  			n.addConjunction(c, i)
   244  		}
   245  		if n.insertConjuncts(state) {
   246  			n.maybeSetCache()
   247  			v.updateStatus(partial)
   248  			return
   249  		}
   250  
   251  		fallthrough
   252  
   253  	case partial, conjuncts:
   254  		// TODO: remove this optimization or make it correct.
   255  		// No need to do further processing when we have errors and all values
   256  		// have been considered.
   257  		// TODO: is checkClosed really still necessary here?
   258  		if v.status == conjuncts && (n.hasErr() || !n.checkClosed(state)) {
   259  			if err := n.getErr(); err != nil {
   260  				b, _ := v.BaseValue.(*Bottom)
   261  				v.BaseValue = CombineErrors(nil, b, err)
   262  			}
   263  			break
   264  		}
   265  
   266  		defer c.PopArc(c.PushArc(v))
   267  
   268  		n.insertConjuncts(state)
   269  
   270  		v.status = evaluating
   271  
   272  		// Use maybeSetCache for cycle breaking
   273  		for n.maybeSetCache(); n.expandOne(partial); n.maybeSetCache() {
   274  		}
   275  
   276  		n.doNotify()
   277  
   278  		if !n.done() {
   279  			switch {
   280  			case state < conjuncts:
   281  				n.node.updateStatus(partial)
   282  				return
   283  
   284  			case state == conjuncts:
   285  				if err := n.incompleteErrors(true); err != nil && err.Code < CycleError {
   286  					n.node.AddErr(c, err)
   287  				} else {
   288  					n.node.updateStatus(partial)
   289  				}
   290  				return
   291  			}
   292  		}
   293  
   294  		// Disjunctions should always be finalized. If there are nested
   295  		// disjunctions the last one should be finalized.
   296  		disState := state
   297  		if len(n.disjunctions) > 0 && disState != finalized {
   298  			disState = finalized
   299  		}
   300  		n.expandDisjuncts(disState, n, maybeDefault, false, true)
   301  
   302  		n.finalizeDisjuncts()
   303  
   304  		switch len(n.disjuncts) {
   305  		case 0:
   306  		case 1:
   307  			x := n.disjuncts[0].result
   308  			x.state = nil
   309  			x.cyclicReferences = n.node.cyclicReferences
   310  			*v = x
   311  
   312  		default:
   313  			d := n.createDisjunct()
   314  			v.BaseValue = d
   315  			// The conjuncts will have too much information. Better have no
   316  			// information than incorrect information.
   317  			for _, d := range d.Values {
   318  				d, ok := d.(*Vertex)
   319  				if !ok {
   320  					continue
   321  				}
   322  				// We clear the conjuncts for now. As these disjuncts are for API
   323  				// use only, we will fill them out when necessary (using Defaults).
   324  				d.Conjuncts = nil
   325  
   326  				// TODO: use a more principled form of dereferencing. For instance,
   327  				// disjuncts could already be assumed to be the given Vertex, and
   328  				// the main vertex could be dereferenced during evaluation.
   329  				for _, a := range d.Arcs {
   330  					for _, x := range a.Conjuncts {
   331  						// All the environments for embedded structs need to be
   332  						// dereferenced.
   333  						for env := x.Env; env != nil && env.Vertex == v; env = env.Up {
   334  							env.Vertex = d
   335  						}
   336  					}
   337  				}
   338  			}
   339  			v.Arcs = nil
   340  			v.ChildErrors = nil
   341  			// v.Structs = nil // TODO: should we keep or discard the Structs?
   342  			// TODO: how to represent closedness information? Do we need it?
   343  		}
   344  
   345  		// If the state has changed, it is because a disjunct has been run, or
   346  		// because a single disjunct has replaced it. Restore the old state as
   347  		// to not confuse memory management.
   348  		v.state = n
   349  
   350  		// We don't do this in postDisjuncts, as it should only be done after
   351  		// completing all disjunctions.
   352  		if !n.done() {
   353  			if err := n.incompleteErrors(true); err != nil {
   354  				b, _ := n.node.BaseValue.(*Bottom)
   355  				if b != err {
   356  					err = CombineErrors(n.ctx.src, b, err)
   357  				}
   358  				n.node.BaseValue = err
   359  			}
   360  		}
   361  
   362  		assertStructuralCycle(n)
   363  
   364  		if state != finalized {
   365  			return
   366  		}
   367  
   368  		if v.BaseValue == nil {
   369  			v.BaseValue = n.getValidators(finalized)
   370  		}
   371  
   372  		// Free memory here?
   373  		v.updateStatus(finalized)
   374  
   375  	case finalized:
   376  	}
   377  }
   378  
   379  // insertConjuncts inserts conjuncts previously not inserted.
   380  func (n *nodeContext) insertConjuncts(state vertexStatus) bool {
   381  	unreachableForDev(n.ctx)
   382  
   383  	// Exit early if we have a concrete value and only need partial results.
   384  	if state == partial {
   385  		for n.conjunctsPartialPos < len(n.conjuncts) {
   386  			c := &n.conjuncts[n.conjunctsPartialPos]
   387  			n.conjunctsPartialPos++
   388  			if c.done {
   389  				continue
   390  			}
   391  			if v, ok := c.C.Elem().(Value); ok && IsConcrete(v) {
   392  				c.done = true
   393  				n.addValueConjunct(c.C.Env, v, c.C.CloseInfo)
   394  			}
   395  		}
   396  		if n.scalar != nil && n.node.isDefined() {
   397  			return true
   398  		}
   399  	}
   400  	for n.conjunctsPos < len(n.conjuncts) {
   401  		nInfos := len(n.node.Structs)
   402  		p := &n.conjuncts[n.conjunctsPos]
   403  		n.conjunctsPos++
   404  		if p.done {
   405  			continue
   406  		}
   407  
   408  		// Initially request a Partial state to allow cyclic references to
   409  		// resolve more naturally first. This results in better error messages
   410  		// and less operations.
   411  		n.addExprConjunct(p.C, partial)
   412  		p.done = true
   413  
   414  		// Record the OptionalTypes for all structs that were inferred by this
   415  		// Conjunct. This information can be used by algorithms such as trim.
   416  		for i := nInfos; i < len(n.node.Structs); i++ {
   417  			n.node.Conjuncts[p.index].CloseInfo.FieldTypes |= n.node.Structs[i].types
   418  		}
   419  	}
   420  	return false
   421  }
   422  
   423  // finalizeDisjuncts: incomplete errors are kept around and not removed early.
   424  // This call filters the incomplete errors and removes them
   425  //
   426  // This also collects all errors of empty disjunctions. These cannot be
   427  // collected during the finalization state of individual disjuncts. Care should
   428  // be taken to only call this after all disjuncts have been finalized.
   429  func (n *nodeContext) finalizeDisjuncts() {
   430  	a := n.disjuncts
   431  	if len(a) == 0 {
   432  		return
   433  	}
   434  	k := 0
   435  	for i, d := range a {
   436  		switch d.finalDone() {
   437  		case true:
   438  			a[k], a[i] = d, a[k]
   439  			k++
   440  		default:
   441  			if err := d.incompleteErrors(true); err != nil {
   442  				n.disjunctErrs = append(n.disjunctErrs, err)
   443  			}
   444  		}
   445  		d.free()
   446  	}
   447  	if k == 0 {
   448  		n.makeError()
   449  	}
   450  	n.disjuncts = a[:k]
   451  }
   452  
   453  func (n *nodeContext) doNotify() {
   454  	if n.errs == nil || len(n.notify) == 0 {
   455  		return
   456  	}
   457  	for _, rec := range n.notify {
   458  		v := rec.v
   459  		if v.state == nil {
   460  			if b, ok := v.BaseValue.(*Bottom); ok {
   461  				v.BaseValue = CombineErrors(nil, b, n.errs)
   462  			} else {
   463  				v.BaseValue = n.errs
   464  			}
   465  		} else {
   466  			v.state.addBottom(n.errs)
   467  		}
   468  	}
   469  	n.notify = n.notify[:0]
   470  }
   471  
   472  func (n *nodeContext) postDisjunct(state vertexStatus) {
   473  	ctx := n.ctx
   474  	unreachableForDev(ctx)
   475  
   476  	for {
   477  		// Use maybeSetCache for cycle breaking
   478  		for n.maybeSetCache(); n.expandOne(state); n.maybeSetCache() {
   479  		}
   480  
   481  		if !n.addLists(oldOnly(state)) {
   482  			break
   483  		}
   484  	}
   485  
   486  	if n.aStruct != nil {
   487  		n.updateNodeType(StructKind, n.aStruct, n.aStructID)
   488  	}
   489  
   490  	if len(n.selfComprehensions) > 0 {
   491  		// Up to here all comprehensions with sources other than this node will
   492  		// have had a chance to run. We can now run self-referencing
   493  		// comprehensions with the restriction that they cannot add new arcs.
   494  		//
   495  		// Note: we should only set this in case of self-referential
   496  		// comprehensions. A comprehension in a parent node may still add
   497  		// arcs to this node, even if it has reached AllConjunctsDone status,
   498  		// as long as any evaluation did not rely on its specific set of arcs.
   499  		// Example:
   500  		//
   501  		//	a: {
   502  		//		b: _env: c: 1
   503  		//
   504  		//		// Using dynamic field ("b") prevents the evaluation of the
   505  		//		// comprehension to be pushed down to env: and instead evaluates
   506  		//		// it before b is completed. Even though b needs to reach state
   507  		//		// AllConjunctsDone before evaluating b._env, it is still okay
   508  		//		// to add arcs to b after this evaluation: only the set of arcs
   509  		//		// in b._env needs to be frozen after that.
   510  		//		for k2, v2 in b._env {
   511  		//			("b"): env: (k2): v2
   512  		//		}
   513  		//	}
   514  		n.node.LockArcs = true
   515  
   516  		n.injectSelfComprehensions(state)
   517  	}
   518  
   519  	for n.expandOne(state) {
   520  	}
   521  
   522  	switch err := n.getErr(); {
   523  	case err != nil:
   524  		if err.Code < IncompleteError && n.node.ArcType == ArcPending {
   525  			n.node.ArcType = ArcMember
   526  		}
   527  		n.node.BaseValue = err
   528  		n.errs = nil
   529  
   530  	default:
   531  		if isCyclePlaceholder(n.node.BaseValue) {
   532  			if !n.done() {
   533  				n.node.BaseValue = n.incompleteErrors(true)
   534  			} else {
   535  				n.node.BaseValue = nil
   536  			}
   537  		}
   538  		// TODO: this ideally should be done here. However, doing so causes
   539  		// a somewhat more aggressive cutoff in disjunction cycles, which cause
   540  		// some incompatibilities. Fix in another CL.
   541  		//
   542  		// else if !n.done() {
   543  		// 	n.expandOne()
   544  		// 	if err := n.incompleteErrors(); err != nil {
   545  		// 		n.node.BaseValue = err
   546  		// 	}
   547  		// }
   548  
   549  		// We are no longer evaluating.
   550  
   551  		n.validateValue(state)
   552  
   553  		v := n.node.Value()
   554  
   555  		// TODO(perf): only delay processing of actual non-monotonic checks.
   556  		skip := n.skipNonMonotonicChecks()
   557  		if v != nil && IsConcrete(v) && !skip {
   558  			for _, v := range n.checks {
   559  				// TODO(errors): make Validate return bottom and generate
   560  				// optimized conflict message. Also track and inject IDs
   561  				// to determine origin location.s
   562  				if b := ctx.Validate(v, n.node); b != nil {
   563  					n.addBottom(b)
   564  				}
   565  			}
   566  		}
   567  
   568  		if v == nil {
   569  			break
   570  		}
   571  
   572  		switch {
   573  		case v.Kind() == ListKind:
   574  			for _, a := range n.node.Arcs {
   575  				if a.Label.Typ() == StringLabel && a.IsDefined(ctx) {
   576  					n.addErr(ctx.Newf("list may not have regular fields"))
   577  					// TODO(errors): add positions for list and arc definitions.
   578  
   579  				}
   580  			}
   581  
   582  			// case !isStruct(n.node) && v.Kind() != BottomKind:
   583  			// 	for _, a := range n.node.Arcs {
   584  			// 		if a.Label.IsRegular() {
   585  			// 			n.addErr(errors.Newf(token.NoPos,
   586  			// 				// TODO(errors): add positions of non-struct values and arcs.
   587  			// 				"cannot combine scalar values with arcs"))
   588  			// 		}
   589  			// 	}
   590  		}
   591  	}
   592  
   593  	n.completeArcs(state)
   594  }
   595  
   596  // validateValue checks collected bound validators and checks them against
   597  // the current value. If there is no value, it sets the current value
   598  // to these validators itself.
   599  //
   600  // Before it does this, it also checks whether n is of another incompatible
   601  // type, like struct. This prevents validators from being inadvertently set.
   602  // TODO: optimize this function for new implementation.
   603  func (n *nodeContext) validateValue(state vertexStatus) {
   604  	ctx := n.ctx
   605  
   606  	// Either set to Conjunction or error.
   607  	// TODO: verify and simplify the below code to determine whether
   608  	// something is a struct.
   609  	markStruct := false
   610  	if n.aStruct != nil {
   611  		markStruct = true
   612  	} else if len(n.node.Structs) > 0 {
   613  		markStruct = n.kind&StructKind != 0 && !n.hasTop
   614  	}
   615  	v := n.node.Value()
   616  	if n.node.BaseValue == nil && markStruct {
   617  		n.node.BaseValue = &StructMarker{}
   618  		v = n.node
   619  	}
   620  	if v != nil && IsConcrete(v) {
   621  		// Also check when we already have errors as we may find more
   622  		// serious errors and would like to know about all errors anyway.
   623  
   624  		if n.lowerBound != nil {
   625  			if b := ctx.Validate(n.lowerBound, v); b != nil {
   626  				// TODO(errors): make Validate return boolean and generate
   627  				// optimized conflict message. Also track and inject IDs
   628  				// to determine origin location.s
   629  				if e, _ := b.Err.(*ValueError); e != nil {
   630  					e.AddPosition(n.lowerBound)
   631  					e.AddPosition(v)
   632  				}
   633  				n.addBottom(b)
   634  			}
   635  		}
   636  		if n.upperBound != nil {
   637  			if b := ctx.Validate(n.upperBound, v); b != nil {
   638  				// TODO(errors): make Validate return boolean and generate
   639  				// optimized conflict message. Also track and inject IDs
   640  				// to determine origin location.s
   641  				if e, _ := b.Err.(*ValueError); e != nil {
   642  					e.AddPosition(n.upperBound)
   643  					e.AddPosition(v)
   644  				}
   645  				n.addBottom(b)
   646  			}
   647  		}
   648  
   649  	} else if state == finalized {
   650  		n.node.BaseValue = n.getValidators(finalized)
   651  	}
   652  }
   653  
   654  // incompleteErrors reports all errors from uncompleted conjuncts.
   655  // If final is true, errors are permanent and reported to parents.
   656  func (n *nodeContext) incompleteErrors(final bool) *Bottom {
   657  	// collect incomplete errors.
   658  	var err *Bottom // n.incomplete
   659  	for _, d := range n.dynamicFields {
   660  		err = CombineErrors(nil, err, d.err)
   661  	}
   662  	for _, c := range n.comprehensions {
   663  		if c.err == nil {
   664  			continue
   665  		}
   666  		err = CombineErrors(nil, err, c.err)
   667  
   668  		// TODO: use this code once possible.
   669  		//
   670  		// Add comprehension to ensure incomplete error is inserted. This
   671  		// ensures that the error is reported in the Vertex where the
   672  		// comprehension was defined, and not just in the node below. This, in
   673  		// turn, is necessary to support certain logic, like export, that
   674  		// expects to be able to detect an "incomplete" error at the first level
   675  		// where it is necessary.
   676  		// if c.node.status != Finalized {
   677  		// 	n := c.node.getNodeContext(n.ctx)
   678  		// 	n.comprehensions = append(n.comprehensions, c)
   679  		// } else {
   680  		// 	n.node.AddErr(n.ctx, err)
   681  		// }
   682  		// n := d.node.getNodeContext(ctx)
   683  		// n.addBottom(err)
   684  		if final && c.vertex != nil && c.vertex.status != finalized {
   685  			c.vertex.state.addBottom(err)
   686  			c.vertex = nil
   687  		}
   688  	}
   689  	for _, c := range n.selfComprehensions {
   690  		if c.err == nil {
   691  			continue
   692  		}
   693  
   694  		err = CombineErrors(nil, err, c.err)
   695  
   696  		// TODO: use this code once possible.
   697  		//
   698  		// Add comprehension to ensure incomplete error is inserted. This
   699  		// ensures that the error is reported in the Vertex where the
   700  		// comprehension was defined, and not just in the node below. This, in
   701  		// turn, is necessary to support certain logic, like export, that
   702  		// expects to be able to detect an "incomplete" error at the first level
   703  		// where it is necessary.
   704  		// if c.node.status != Finalized {
   705  		// 	n := c.node.getNodeContext(n.ctx)
   706  		// 	n.comprehensions = append(n.comprehensions, c)
   707  		// } else {
   708  		// 	n.node.AddErr(n.ctx, err)
   709  		// }
   710  		// n := d.node.getNodeContext(ctx)
   711  		// n.addBottom(err)
   712  		if c.vertex != nil && c.vertex.status != finalized {
   713  			c.vertex.state.addBottom(err)
   714  			c.vertex = nil
   715  		}
   716  	}
   717  	for _, x := range n.exprs {
   718  		err = CombineErrors(nil, err, x.err)
   719  	}
   720  	if err == nil {
   721  		// safeguard.
   722  		err = incompleteSentinel
   723  	}
   724  	if err.Code < IncompleteError {
   725  		n.node.ArcType = ArcMember
   726  	}
   727  	return err
   728  }
   729  
   730  // TODO(perf): ideally we should always perform a closedness check if
   731  // state is Finalized. This is currently not possible when computing a
   732  // partial disjunction as the closedness information is not yet
   733  // complete, possibly leading to a disjunct to be rejected prematurely.
   734  // It is probably possible to fix this if we could add StructInfo
   735  // structures demarked per conjunct.
   736  //
   737  // In practice this should not be a problem: when disjuncts originate
   738  // from the same disjunct, they will have the same StructInfos, and thus
   739  // Equal is able to equate them even in the presence of optional field.
   740  // In general, combining any limited set of disjuncts will soon reach
   741  // a fixed point where duplicate elements can be eliminated this way.
   742  //
   743  // Note that not checking closedness is irrelevant for disjunctions of
   744  // scalars. This means it also doesn't hurt performance where structs
   745  // have a discriminator field (e.g. Kubernetes). We should take care,
   746  // though, that any potential performance issues are eliminated for
   747  // Protobuf-like oneOf fields.
   748  func (n *nodeContext) checkClosed(state vertexStatus) bool {
   749  	unreachableForDev(n.ctx)
   750  
   751  	ignore := state != finalized || n.skipNonMonotonicChecks()
   752  
   753  	v := n.node
   754  	if !v.Label.IsInt() && v.Parent != nil && !ignore && v.ArcType <= ArcRequired {
   755  		ctx := n.ctx
   756  		// Visit arcs recursively to validate and compute error.
   757  		if _, err := verifyArc2(ctx, v.Label, v, v.Closed); err != nil {
   758  			// Record error in child node to allow recording multiple
   759  			// conflicts at the appropriate place, to allow valid fields to
   760  			// be represented normally and, most importantly, to avoid
   761  			// recursive processing of a disallowed field.
   762  			v.SetValue(ctx, err)
   763  			return false
   764  		}
   765  	}
   766  	return true
   767  }
   768  
   769  func (n *nodeContext) completeArcs(state vertexStatus) {
   770  	unreachableForDev(n.ctx)
   771  
   772  	if DebugSort > 0 {
   773  		DebugSortArcs(n.ctx, n.node)
   774  	}
   775  
   776  	if n.node.hasAllConjuncts || n.node.Parent == nil {
   777  		n.node.setParentDone()
   778  	}
   779  
   780  	// At this point, if this arc is of type arcVoid, it means that the value
   781  	// may still be modified by child arcs. So in this case we must now process
   782  	// all arcs to be sure we get the correct result.
   783  	// For other cases we terminate early as this results in considerably
   784  	// better error messages.
   785  	if state <= conjuncts &&
   786  		// Is allowed to go one step back. See Vertex.UpdateStatus.
   787  		n.node.status <= state+1 &&
   788  		(!n.node.hasPendingArc || n.node.ArcType == ArcMember) {
   789  
   790  		n.node.updateStatus(conjuncts)
   791  		return
   792  	}
   793  
   794  	n.node.updateStatus(evaluatingArcs)
   795  
   796  	ctx := n.ctx
   797  
   798  	if !assertStructuralCycle(n) {
   799  		k := 0
   800  		// Visit arcs recursively to validate and compute error.
   801  		for _, a := range n.node.Arcs {
   802  			// Call UpdateStatus here to be absolutely sure the status is set
   803  			// correctly and that we are not regressing.
   804  			n.node.updateStatus(evaluatingArcs)
   805  
   806  			wasVoid := a.ArcType == ArcPending
   807  
   808  			ctx.unify(a, oldOnly(finalized))
   809  
   810  			if a.ArcType == ArcPending {
   811  				continue
   812  			}
   813  
   814  			// Errors are allowed in let fields. Handle errors and failure to
   815  			// complete accordingly.
   816  			if !a.Label.IsLet() && a.ArcType <= ArcRequired {
   817  				// Don't set the state to Finalized if the child arcs are not done.
   818  				if state == finalized && a.status < finalized {
   819  					state = conjuncts
   820  				}
   821  
   822  				if err, _ := a.BaseValue.(*Bottom); err != nil {
   823  					n.node.AddChildError(err)
   824  				}
   825  			}
   826  
   827  			n.node.Arcs[k] = a
   828  			k++
   829  
   830  			switch {
   831  			case a.ArcType > ArcRequired, !a.Label.IsString():
   832  			case n.kind&StructKind == 0:
   833  				if !n.node.IsErr() {
   834  					n.reportFieldMismatch(pos(a.Value()), nil, a.Label, n.node.Value())
   835  				}
   836  			case !wasVoid:
   837  			case n.kind == TopKind:
   838  				// Theoretically it may be possible that a "void" arc references
   839  				// this top value where it really should have been a struct. One
   840  				// way to solve this is to have two passes over the arcs, where
   841  				// the first pass additionally analyzes whether comprehensions
   842  				// will yield values and "un-voids" an arc ahead of the rest.
   843  				//
   844  				// At this moment, though, I fail to see a possibility to create
   845  				// faulty CUE using this mechanism, though. At most error
   846  				// messages are a bit unintuitive. This may change once we have
   847  				// functionality to reflect on types.
   848  				if _, ok := n.node.BaseValue.(*Bottom); !ok {
   849  					n.node.BaseValue = &StructMarker{}
   850  					n.kind = StructKind
   851  				}
   852  			}
   853  		}
   854  		n.node.Arcs = n.node.Arcs[:k]
   855  
   856  		for _, c := range n.postChecks {
   857  			f := ctx.PushState(c.env, c.expr.Source())
   858  
   859  			// TODO(errors): make Validate return bottom and generate
   860  			// optimized conflict message. Also track and inject IDs
   861  			// to determine origin location.s
   862  			v := ctx.evalState(c.expr, oldOnly(finalized))
   863  			v, _ = ctx.getDefault(v)
   864  			v = Unwrap(v)
   865  
   866  			switch _, isError := v.(*Bottom); {
   867  			case isError == c.expectError:
   868  			default:
   869  				n.node.AddErr(ctx, &Bottom{
   870  					Src:  c.expr.Source(),
   871  					Code: CycleError,
   872  					Err: ctx.NewPosf(pos(c.expr),
   873  						"circular dependency in evaluation of conditionals: %v changed after evaluation",
   874  						ctx.Str(c.expr)),
   875  				})
   876  			}
   877  
   878  			ctx.PopState(f)
   879  		}
   880  	}
   881  
   882  	if err := n.getErr(); err != nil {
   883  		n.errs = nil
   884  		if b, _ := n.node.BaseValue.(*Bottom); b != nil {
   885  			err = CombineErrors(nil, b, err)
   886  		}
   887  		n.node.BaseValue = err
   888  	}
   889  
   890  	b, hasErr := n.node.BaseValue.(*Bottom)
   891  	if !hasErr && b != cycle {
   892  		n.checkClosed(state)
   893  	}
   894  
   895  	// Strip struct literals that were not initialized and are not part
   896  	// of the output.
   897  	//
   898  	// TODO(perf): we could keep track if any such structs exist and only
   899  	// do this removal if there is a change of shrinking the list.
   900  	k := 0
   901  	for _, s := range n.node.Structs {
   902  		if s.initialized {
   903  			n.node.Structs[k] = s
   904  			k++
   905  		}
   906  	}
   907  	n.node.Structs = n.node.Structs[:k]
   908  
   909  	n.node.updateStatus(finalized)
   910  }
   911  
   912  // TODO: this is now a sentinel. Use a user-facing error that traces where
   913  // the cycle originates.
   914  var cycle = &Bottom{
   915  	Err:  errors.Newf(token.NoPos, "cycle error"),
   916  	Code: CycleError,
   917  }
   918  
   919  func isCyclePlaceholder(v BaseValue) bool {
   920  	return v == cycle
   921  }
   922  
   923  func (n *nodeContext) createDisjunct() *Disjunction {
   924  	a := make([]Value, len(n.disjuncts))
   925  	p := 0
   926  	hasDefaults := false
   927  	for i, x := range n.disjuncts {
   928  		v := new(Vertex)
   929  		*v = x.result
   930  		v.state = nil
   931  		switch x.defaultMode {
   932  		case isDefault:
   933  			a[i] = a[p]
   934  			a[p] = v
   935  			p++
   936  			hasDefaults = true
   937  
   938  		case notDefault:
   939  			hasDefaults = true
   940  			fallthrough
   941  		case maybeDefault:
   942  			a[i] = v
   943  		}
   944  	}
   945  	// TODO: disambiguate based on concrete values.
   946  	// TODO: consider not storing defaults.
   947  	// if p > 0 {
   948  	// 	a = a[:p]
   949  	// }
   950  	return &Disjunction{
   951  		Values:      a,
   952  		NumDefaults: p,
   953  		HasDefaults: hasDefaults,
   954  	}
   955  }
   956  
   957  type arcKey struct {
   958  	arc *Vertex
   959  	id  CloseInfo
   960  }
   961  
   962  // A nodeContext is used to collate all conjuncts of a value to facilitate
   963  // unification. Conceptually order of unification does not matter. However,
   964  // order has relevance when performing checks of non-monotic properties. Such
   965  // checks should only be performed once the full value is known.
   966  type nodeContext struct {
   967  	nextFree *nodeContext
   968  	refCount int
   969  
   970  	// Keep node out of the nodeContextState to make them more accessible
   971  	// for source-level debuggers.
   972  	node *Vertex
   973  
   974  	nodeContextState
   975  
   976  	scheduler
   977  
   978  	// Below are slices that need to be managed when cloning and reclaiming
   979  	// nodeContexts for reuse. We want to ensure that, instead of setting
   980  	// slices to nil, we truncate the existing buffers so that they do not
   981  	// need to be reallocated upon reuse of the nodeContext.
   982  
   983  	arcMap []arcKey // not copied for cloning
   984  
   985  	// notify is used to communicate errors in cyclic dependencies.
   986  	// TODO: also use this to communicate increasingly more concrete values.
   987  	notify []receiver
   988  
   989  	// Conjuncts holds a reference to the Vertex Arcs that still need
   990  	// processing. It does NOT need to be copied.
   991  	conjuncts       []conjunct
   992  	cyclicConjuncts []cyclicConjunct
   993  
   994  	dynamicFields      []envDynamic
   995  	comprehensions     []envYield
   996  	selfComprehensions []envYield // comprehensions iterating over own struct.
   997  
   998  	// Expression conjuncts
   999  	lists  []envList
  1000  	vLists []*Vertex
  1001  	exprs  []envExpr
  1002  
  1003  	checks     []Validator // BuiltinValidator, other bound values.
  1004  	postChecks []envCheck  // Check non-monotonic constraints, among other things.
  1005  
  1006  	// Disjunction handling
  1007  	disjunctions []envDisjunct
  1008  
  1009  	// usedDefault indicates the for each of possibly multiple parent
  1010  	// disjunctions whether it is unified with a default disjunct or not.
  1011  	// This is then later used to determine whether a disjunction should
  1012  	// be treated as a marked disjunction.
  1013  	usedDefault []defaultInfo
  1014  
  1015  	disjuncts    []*nodeContext
  1016  	buffer       []*nodeContext
  1017  	disjunctErrs []*Bottom
  1018  
  1019  	// snapshot holds the last value of the vertex before calling postDisjunct.
  1020  	snapshot Vertex
  1021  
  1022  	// Result holds the last evaluated value of the vertex after calling
  1023  	// postDisjunct.
  1024  	result Vertex
  1025  }
  1026  
  1027  type conjunct struct {
  1028  	C Conjunct
  1029  
  1030  	// done marks that this conjunct has been inserted. This prevents a
  1031  	// conjunct from being processed more than once, for instance, when
  1032  	// insertConjuncts is called more than once for the same node.
  1033  	done  bool
  1034  	index int // index of the original conjunct in Vertex.Conjuncts
  1035  }
  1036  
  1037  type nodeContextState struct {
  1038  	// State info
  1039  
  1040  	hasTop      bool
  1041  	hasCycle    bool // has conjunct with structural cycle
  1042  	hasNonCycle bool // has conjunct without structural cycle
  1043  
  1044  	depth       int32
  1045  	defaultMode defaultMode
  1046  
  1047  	// Value info
  1048  
  1049  	kind     Kind
  1050  	kindExpr Expr      // expr that adjust last value (for error reporting)
  1051  	kindID   CloseInfo // for error tracing
  1052  
  1053  	// Current value (may be under construction)
  1054  	scalar   Value // TODO: use Value in node.
  1055  	scalarID CloseInfo
  1056  
  1057  	aStruct   Expr
  1058  	aStructID CloseInfo
  1059  
  1060  	// List fields
  1061  	listIsClosed bool
  1062  	maxListLen   int
  1063  	maxNode      Expr
  1064  
  1065  	lowerBound *BoundValue // > or >=
  1066  	upperBound *BoundValue // < or <=
  1067  	errs       *Bottom
  1068  
  1069  	// Slice positions
  1070  
  1071  	// conjunctsPos is an index into conjuncts indicating the next conjunct
  1072  	// to process. This is used to avoids processing a conjunct twice in some
  1073  	// cases where there is an evaluation cycle.
  1074  	conjunctsPos int
  1075  	// conjunctsPartialPos is like conjunctsPos, but for the 'partial' phase
  1076  	// of processing where conjuncts are only processed as concrete scalars.
  1077  	conjunctsPartialPos int
  1078  
  1079  	arcPos int
  1080  }
  1081  
  1082  // A receiver receives notifications.
  1083  type receiver struct {
  1084  	v  *Vertex
  1085  	cc *closeContext
  1086  }
  1087  
  1088  // Logf substitutes args in format. Arguments of type Feature, Value, and Expr
  1089  // are printed in human-friendly formats. The printed string is prefixed and
  1090  // indented with the path associated with the current nodeContext.
  1091  func (n *nodeContext) Logf(format string, args ...interface{}) {
  1092  	n.ctx.Logf(n.node, format, args...)
  1093  }
  1094  
  1095  type defaultInfo struct {
  1096  	// parentMode indicates whether this values was used as a default value,
  1097  	// based on the parent mode.
  1098  	parentMode defaultMode
  1099  
  1100  	// The result of default evaluation for a nested disjunction.
  1101  	nestedMode defaultMode
  1102  
  1103  	origMode defaultMode
  1104  }
  1105  
  1106  func (n *nodeContext) addNotify(v *Vertex, cc *closeContext) {
  1107  	unreachableForDev(n.ctx)
  1108  
  1109  	if v != nil && !n.node.hasAllConjuncts {
  1110  		n.notify = append(n.notify, receiver{v, cc})
  1111  	}
  1112  }
  1113  
  1114  func (n *nodeContext) clone() *nodeContext {
  1115  	d := n.ctx.newNodeContext(n.node)
  1116  
  1117  	d.refCount++
  1118  
  1119  	d.ctx = n.ctx
  1120  	d.node = n.node
  1121  
  1122  	d.nodeContextState = n.nodeContextState
  1123  
  1124  	d.arcMap = append(d.arcMap, n.arcMap...)
  1125  	d.notify = append(d.notify, n.notify...)
  1126  
  1127  	n.scheduler.cloneInto(&d.scheduler)
  1128  
  1129  	d.conjuncts = append(d.conjuncts, n.conjuncts...)
  1130  	d.cyclicConjuncts = append(d.cyclicConjuncts, n.cyclicConjuncts...)
  1131  	d.dynamicFields = append(d.dynamicFields, n.dynamicFields...)
  1132  	d.comprehensions = append(d.comprehensions, n.comprehensions...)
  1133  	d.selfComprehensions = append(d.selfComprehensions, n.selfComprehensions...)
  1134  	d.lists = append(d.lists, n.lists...)
  1135  	d.vLists = append(d.vLists, n.vLists...)
  1136  	d.exprs = append(d.exprs, n.exprs...)
  1137  	d.checks = append(d.checks, n.checks...)
  1138  	d.postChecks = append(d.postChecks, n.postChecks...)
  1139  
  1140  	d.usedDefault = append(d.usedDefault, n.usedDefault...)
  1141  
  1142  	// Do not clone other disjunction-related slices, like disjuncts and buffer:
  1143  	// disjunction slices are managed by disjunction processing directly.
  1144  
  1145  	return d
  1146  }
  1147  
  1148  func (c *OpContext) newNodeContext(node *Vertex) *nodeContext {
  1149  	if n := c.freeListNode; n != nil {
  1150  		c.stats.Reused++
  1151  		c.freeListNode = n.nextFree
  1152  
  1153  		*n = nodeContext{
  1154  			scheduler: scheduler{ctx: c},
  1155  			node:      node,
  1156  			nodeContextState: nodeContextState{
  1157  				kind: TopKind,
  1158  			},
  1159  			arcMap:             n.arcMap[:0],
  1160  			conjuncts:          n.conjuncts[:0],
  1161  			cyclicConjuncts:    n.cyclicConjuncts[:0],
  1162  			notify:             n.notify[:0],
  1163  			checks:             n.checks[:0],
  1164  			postChecks:         n.postChecks[:0],
  1165  			dynamicFields:      n.dynamicFields[:0],
  1166  			comprehensions:     n.comprehensions[:0],
  1167  			selfComprehensions: n.selfComprehensions[:0],
  1168  			lists:              n.lists[:0],
  1169  			vLists:             n.vLists[:0],
  1170  			exprs:              n.exprs[:0],
  1171  			disjunctions:       n.disjunctions[:0],
  1172  			usedDefault:        n.usedDefault[:0],
  1173  			disjunctErrs:       n.disjunctErrs[:0],
  1174  			disjuncts:          n.disjuncts[:0],
  1175  			buffer:             n.buffer[:0],
  1176  		}
  1177  		n.scheduler.clear()
  1178  		n.scheduler.node = n
  1179  
  1180  		return n
  1181  	}
  1182  	c.stats.Allocs++
  1183  
  1184  	n := &nodeContext{
  1185  		scheduler: scheduler{
  1186  			ctx: c,
  1187  		},
  1188  		node: node,
  1189  
  1190  		nodeContextState: nodeContextState{kind: TopKind},
  1191  	}
  1192  	n.scheduler.node = n
  1193  	return n
  1194  }
  1195  
  1196  func (v *Vertex) getNodeContext(c *OpContext, ref int) *nodeContext {
  1197  	unreachableForDev(c)
  1198  
  1199  	if v.state == nil {
  1200  		if v.status == finalized {
  1201  			return nil
  1202  		}
  1203  		v.state = c.newNodeContext(v)
  1204  	} else if v.state.node != v {
  1205  		panic("getNodeContext: nodeContext out of sync")
  1206  	}
  1207  	v.state.refCount += ref
  1208  	return v.state
  1209  }
  1210  
  1211  func (v *Vertex) freeNode(n *nodeContext) {
  1212  	if n == nil {
  1213  		return
  1214  	}
  1215  	if n.node != v {
  1216  		panic("freeNode: unpaired free")
  1217  	}
  1218  	if v.state != nil && v.state != n {
  1219  		panic("freeNode: nodeContext out of sync")
  1220  	}
  1221  	if n.refCount--; n.refCount == 0 {
  1222  		if v.status == finalized {
  1223  			v.freeNodeState()
  1224  		} else {
  1225  			n.ctx.stats.Retained++
  1226  		}
  1227  	}
  1228  }
  1229  
  1230  func (v *Vertex) freeNodeState() {
  1231  	if v.state == nil {
  1232  		return
  1233  	}
  1234  	state := v.state
  1235  	v.state = nil
  1236  
  1237  	state.ctx.freeNodeContext(state)
  1238  }
  1239  
  1240  func (n *nodeContext) free() {
  1241  	if n.refCount--; n.refCount == 0 {
  1242  		n.ctx.freeNodeContext(n)
  1243  	}
  1244  }
  1245  
  1246  func (c *OpContext) freeNodeContext(n *nodeContext) {
  1247  	c.stats.Freed++
  1248  	n.nextFree = c.freeListNode
  1249  	c.freeListNode = n
  1250  	n.node = nil
  1251  	n.refCount = 0
  1252  	n.scheduler.clear()
  1253  }
  1254  
  1255  // TODO(perf): return a dedicated ConflictError that can track original
  1256  // positions on demand.
  1257  func (n *nodeContext) reportConflict(
  1258  	v1, v2 Node,
  1259  	k1, k2 Kind,
  1260  	ids ...CloseInfo) {
  1261  
  1262  	ctx := n.ctx
  1263  
  1264  	var err *ValueError
  1265  	if k1 == k2 {
  1266  		err = ctx.NewPosf(token.NoPos, "conflicting values %s and %s", v1, v2)
  1267  	} else {
  1268  		err = ctx.NewPosf(token.NoPos,
  1269  			"conflicting values %s and %s (mismatched types %s and %s)",
  1270  			v1, v2, k1, k2)
  1271  	}
  1272  
  1273  	err.AddPosition(v1)
  1274  	err.AddPosition(v2)
  1275  	for _, id := range ids {
  1276  		err.AddClosedPositions(id)
  1277  	}
  1278  
  1279  	n.addErr(err)
  1280  }
  1281  
  1282  // reportFieldMismatch reports the mixture of regular fields with non-struct
  1283  // values. Either s or f needs to be given.
  1284  func (n *nodeContext) reportFieldMismatch(
  1285  	p token.Pos,
  1286  	s *StructLit,
  1287  	f Feature,
  1288  	scalar Expr,
  1289  	id ...CloseInfo) {
  1290  
  1291  	ctx := n.ctx
  1292  
  1293  	if f == InvalidLabel {
  1294  		for _, a := range s.Decls {
  1295  			if x, ok := a.(*Field); ok && x.Label.IsRegular() {
  1296  				f = x.Label
  1297  				p = pos(x)
  1298  				break
  1299  			}
  1300  		}
  1301  		if f == InvalidLabel {
  1302  			n.reportConflict(scalar, s, n.kind, StructKind, id...)
  1303  			return
  1304  		}
  1305  	}
  1306  
  1307  	err := ctx.NewPosf(p, "cannot combine regular field %q with %v", f, scalar)
  1308  
  1309  	if s != nil {
  1310  		err.AddPosition(s)
  1311  	}
  1312  
  1313  	for _, ci := range id {
  1314  		err.AddClosedPositions(ci)
  1315  	}
  1316  
  1317  	n.addErr(err)
  1318  }
  1319  
  1320  func (n *nodeContext) updateNodeType(k Kind, v Expr, id CloseInfo) bool {
  1321  	ctx := n.ctx
  1322  	kind := n.kind & k
  1323  
  1324  	switch {
  1325  	case n.kind == BottomKind,
  1326  		k == BottomKind:
  1327  		return false
  1328  
  1329  	case kind != BottomKind:
  1330  
  1331  	// TODO: we could consider changing the reporting for structs, but this
  1332  	// makes only sense in case they are for embeddings. Otherwise the type
  1333  	// of a struct is more relevant for the failure.
  1334  	// case k == StructKind:
  1335  	// 	s, _ := v.(*StructLit)
  1336  	// 	n.reportFieldMismatch(token.NoPos, s, 0, n.kindExpr, id, n.kindID)
  1337  
  1338  	case n.kindExpr != nil:
  1339  		n.reportConflict(n.kindExpr, v, n.kind, k, n.kindID, id)
  1340  
  1341  	default:
  1342  		n.addErr(ctx.Newf(
  1343  			"conflicting value %s (mismatched types %s and %s)",
  1344  			v, n.kind, k))
  1345  	}
  1346  
  1347  	if n.kind != kind || n.kindExpr == nil {
  1348  		n.kindExpr = v
  1349  	}
  1350  	n.kind = kind
  1351  	return kind != BottomKind
  1352  }
  1353  
  1354  func (n *nodeContext) done() bool {
  1355  	// TODO(v0.7): verify that done() is checking for the right conditions in
  1356  	// the new evaluator implementation.
  1357  	return len(n.dynamicFields) == 0 &&
  1358  		len(n.comprehensions) == 0 &&
  1359  		len(n.exprs) == 0
  1360  }
  1361  
  1362  // finalDone is like done, but allows for cycle errors, which can be ignored
  1363  // as they essentially indicate a = a & _.
  1364  func (n *nodeContext) finalDone() bool {
  1365  	// TODO(v0.7): update for new evaluator?
  1366  	for _, x := range n.exprs {
  1367  		if x.err.Code != CycleError {
  1368  			return false
  1369  		}
  1370  	}
  1371  	return len(n.dynamicFields) == 0 &&
  1372  		len(n.comprehensions) == 0 &&
  1373  		len(n.selfComprehensions) == 0
  1374  }
  1375  
  1376  // hasErr is used to determine if an evaluation path, for instance a single
  1377  // path after expanding all disjunctions, has an error.
  1378  func (n *nodeContext) hasErr() bool {
  1379  	if n.node.ChildErrors != nil {
  1380  		return true
  1381  	}
  1382  	if n.node.status > evaluating && n.node.IsErr() {
  1383  		return true
  1384  	}
  1385  	return n.ctx.HasErr() || n.errs != nil
  1386  }
  1387  
  1388  func (n *nodeContext) getErr() *Bottom {
  1389  	n.errs = CombineErrors(nil, n.errs, n.ctx.Err())
  1390  	return n.errs
  1391  }
  1392  
  1393  // getValidators sets the vertex' Value in case there was no concrete value.
  1394  func (n *nodeContext) getValidators(state vertexStatus) BaseValue {
  1395  	ctx := n.ctx
  1396  
  1397  	a := []Value{}
  1398  	// if n.node.Value != nil {
  1399  	// 	a = append(a, n.node.Value)
  1400  	// }
  1401  	kind := TopKind
  1402  	if n.lowerBound != nil {
  1403  		a = append(a, n.lowerBound)
  1404  		kind &= n.lowerBound.Kind()
  1405  	}
  1406  	if n.upperBound != nil {
  1407  		a = append(a, n.upperBound)
  1408  		kind &= n.upperBound.Kind()
  1409  	}
  1410  	for _, c := range n.checks {
  1411  		// Drop !=x if x is out of bounds with another bound.
  1412  		if b, _ := c.(*BoundValue); b != nil && b.Op == NotEqualOp {
  1413  			if n.upperBound != nil &&
  1414  				SimplifyBounds(ctx, n.kind, n.upperBound, b) != nil {
  1415  				continue
  1416  			}
  1417  			if n.lowerBound != nil &&
  1418  				SimplifyBounds(ctx, n.kind, n.lowerBound, b) != nil {
  1419  				continue
  1420  			}
  1421  		}
  1422  		a = append(a, c)
  1423  		kind &= c.Kind()
  1424  	}
  1425  
  1426  	if kind&^n.kind != 0 {
  1427  		a = append(a, &BasicType{
  1428  			Src: n.kindExpr.Source(), // TODO:Is this always a BasicType?
  1429  			K:   n.kind,
  1430  		})
  1431  	}
  1432  
  1433  	var v BaseValue
  1434  	switch len(a) {
  1435  	case 0:
  1436  		// Src is the combined input.
  1437  		if state >= conjuncts || n.kind&^CompositKind == 0 {
  1438  			v = &BasicType{K: n.kind}
  1439  		}
  1440  
  1441  	case 1:
  1442  		v = a[0]
  1443  
  1444  	default:
  1445  		v = &Conjunction{Values: a}
  1446  	}
  1447  
  1448  	return v
  1449  }
  1450  
  1451  // TODO: this function can probably go as this is now handled in the nodeContext.
  1452  func (n *nodeContext) maybeSetCache() {
  1453  	// Set BaseValue to scalar, but only if it was not set before. Most notably,
  1454  	// errors should not be discarded.
  1455  	_, isErr := n.node.BaseValue.(*Bottom)
  1456  	if n.scalar != nil && (!isErr || isCyclePlaceholder(n.node.BaseValue)) {
  1457  		n.node.BaseValue = n.scalar
  1458  	}
  1459  	// NOTE: this is now handled by associating the nodeContext
  1460  	// if n.errs != nil {
  1461  	// 	n.node.SetValue(n.ctx, Partial, n.errs)
  1462  	// }
  1463  }
  1464  
  1465  type envExpr struct {
  1466  	c   Conjunct
  1467  	err *Bottom
  1468  }
  1469  
  1470  type envDynamic struct {
  1471  	env   *Environment
  1472  	field *DynamicField
  1473  	id    CloseInfo
  1474  	err   *Bottom
  1475  }
  1476  
  1477  type envList struct {
  1478  	env     *Environment
  1479  	list    *ListLit
  1480  	n       int64 // recorded length after evaluator
  1481  	elipsis *Ellipsis
  1482  	id      CloseInfo
  1483  	ignore  bool // has a self-referencing comprehension and is postponed
  1484  	self    bool // was added as a postponed self-referencing comprehension
  1485  	index   int
  1486  }
  1487  
  1488  type envCheck struct {
  1489  	env         *Environment
  1490  	expr        Expr
  1491  	expectError bool
  1492  }
  1493  
  1494  func (n *nodeContext) addBottom(b *Bottom) {
  1495  	n.errs = CombineErrors(nil, n.errs, b)
  1496  	// TODO(errors): consider doing this
  1497  	// n.kindExpr = n.errs
  1498  	// n.kind = 0
  1499  }
  1500  
  1501  func (n *nodeContext) addErr(err errors.Error) {
  1502  	if err != nil {
  1503  		n.addBottom(&Bottom{Err: err})
  1504  	}
  1505  }
  1506  
  1507  // addExprConjuncts will attempt to evaluate an Expr and insert the value
  1508  // into the nodeContext if successful or queue it for later evaluation if it is
  1509  // incomplete or is not value.
  1510  func (n *nodeContext) addExprConjunct(v Conjunct, state vertexStatus) {
  1511  	unreachableForDev(n.ctx)
  1512  
  1513  	env := v.Env
  1514  	id := v.CloseInfo
  1515  
  1516  	switch x := v.Elem().(type) {
  1517  	case *Vertex:
  1518  		if x.IsData() {
  1519  			n.addValueConjunct(env, x, id)
  1520  		} else {
  1521  			n.addVertexConjuncts(v, x, true)
  1522  		}
  1523  
  1524  	case Value:
  1525  		n.addValueConjunct(env, x, id)
  1526  
  1527  	case *BinaryExpr:
  1528  		if x.Op == AndOp {
  1529  			n.addExprConjunct(MakeConjunct(env, x.X, id), state)
  1530  			n.addExprConjunct(MakeConjunct(env, x.Y, id), state)
  1531  			return
  1532  		} else {
  1533  			n.evalExpr(v, state)
  1534  		}
  1535  
  1536  	case *StructLit:
  1537  		n.addStruct(env, x, id)
  1538  
  1539  	case *ListLit:
  1540  		childEnv := &Environment{
  1541  			Up:     env,
  1542  			Vertex: n.node,
  1543  		}
  1544  		n.lists = append(n.lists, envList{env: childEnv, list: x, id: id})
  1545  
  1546  	case *DisjunctionExpr:
  1547  		n.addDisjunction(env, x, id)
  1548  
  1549  	case *Comprehension:
  1550  		// always a partial comprehension.
  1551  		n.insertComprehension(env, x, id)
  1552  		return
  1553  
  1554  	default:
  1555  		// Must be Resolver or Evaluator.
  1556  		n.evalExpr(v, state)
  1557  	}
  1558  	n.ctx.stats.Conjuncts++
  1559  }
  1560  
  1561  // evalExpr is only called by addExprConjunct. If an error occurs, it records
  1562  // the error in n and returns nil.
  1563  func (n *nodeContext) evalExpr(v Conjunct, state vertexStatus) {
  1564  	unreachableForDev(n.ctx)
  1565  
  1566  	// Require an Environment.
  1567  	ctx := n.ctx
  1568  
  1569  	closeID := v.CloseInfo
  1570  
  1571  	switch x := v.Expr().(type) {
  1572  	case Resolver:
  1573  		// We elevate a field evaluated to the Conjuncts state to Finalized
  1574  		// later. For now we allow partial evaluation so that we can break
  1575  		// cycles and postpone incomplete evaluations until more information is
  1576  		// available down the line.
  1577  		if state == finalized {
  1578  			state = conjuncts
  1579  		}
  1580  		arc, err := ctx.resolveState(v, x, oldOnly(state))
  1581  		if err != nil && (!err.IsIncomplete() || err.Permanent) {
  1582  			n.addBottom(err)
  1583  			break
  1584  		}
  1585  		if arc == nil {
  1586  			n.exprs = append(n.exprs, envExpr{v, err})
  1587  			break
  1588  		}
  1589  
  1590  		// We complete the evaluation. Some optimizations will only work when an
  1591  		// arc is already finalized. So this ensures that such optimizations get
  1592  		// triggered more often.
  1593  		//
  1594  		// NOTE(let finalization): aside from being an optimization, this also
  1595  		// ensures that let arcs that are not contained as fields of arcs, but
  1596  		// rather are held in the cash, are finalized. This, in turn, is
  1597  		// necessary to trigger the notification mechanism, where appropriate.
  1598  		//
  1599  		// A node should not Finalize itself as it may erase the state object
  1600  		// which is still assumed to be present down the line
  1601  		// (see https://cuelang.org/issues/2171).
  1602  		if arc.status == conjuncts && arc != n.node && arc.hasAllConjuncts {
  1603  			arc.Finalize(ctx)
  1604  		}
  1605  
  1606  		ci, skip := n.markCycle(arc, v.Env, x, v.CloseInfo)
  1607  		if skip {
  1608  			return
  1609  		}
  1610  		v.CloseInfo = ci
  1611  
  1612  		n.addVertexConjuncts(v, arc, false)
  1613  
  1614  	case Evaluator:
  1615  		// Interpolation, UnaryExpr, BinaryExpr, CallExpr
  1616  		// Could be unify?
  1617  		val := ctx.evaluateRec(v, oldOnly(partial))
  1618  		if b, ok := val.(*Bottom); ok &&
  1619  			b.IsIncomplete() {
  1620  			n.exprs = append(n.exprs, envExpr{v, b})
  1621  			break
  1622  		}
  1623  
  1624  		if v, ok := val.(*Vertex); ok {
  1625  			// Handle generated disjunctions (as in the 'or' builtin).
  1626  			// These come as a Vertex, but should not be added as a value.
  1627  			b, ok := v.BaseValue.(*Bottom)
  1628  			if ok && b.IsIncomplete() && len(v.Conjuncts) > 0 {
  1629  				for _, c := range v.Conjuncts {
  1630  					c.CloseInfo = closeID
  1631  					n.addExprConjunct(c, state)
  1632  				}
  1633  				break
  1634  			}
  1635  		}
  1636  
  1637  		// TODO: also to through normal Vertex handling here. At the moment
  1638  		// addValueConjunct handles StructMarker.NeedsClose, as this is always
  1639  		// only needed when evaluation an Evaluator, and not a Resolver.
  1640  		// The two code paths should ideally be merged once this separate
  1641  		// mechanism is eliminated.
  1642  		//
  1643  		// if arc, ok := val.(*Vertex); ok && !arc.IsData() {
  1644  		// 	n.addVertexConjuncts(v.Env, closeID, v.Expr(), arc)
  1645  		// 	break
  1646  		// }
  1647  
  1648  		// TODO: insert in vertex as well
  1649  		n.addValueConjunct(v.Env, val, closeID)
  1650  
  1651  	default:
  1652  		panic(fmt.Sprintf("unknown expression of type %T", x))
  1653  	}
  1654  }
  1655  
  1656  func (n *nodeContext) addVertexConjuncts(c Conjunct, arc *Vertex, inline bool) {
  1657  	unreachableForDev(n.ctx)
  1658  
  1659  	closeInfo := c.CloseInfo
  1660  
  1661  	// We need to ensure that each arc is only unified once (or at least) a
  1662  	// bounded time, witch each conjunct. Comprehensions, for instance, may
  1663  	// distribute a value across many values that get unified back into the
  1664  	// same value. If such a value is a disjunction, than a disjunction of N
  1665  	// disjuncts will result in a factor N more unifications for each
  1666  	// occurrence of such value, resulting in exponential running time. This
  1667  	// is especially common values that are used as a type.
  1668  	//
  1669  	// However, unification is idempotent, so each such conjunct only needs
  1670  	// to be unified once. This cache checks for this and prevents an
  1671  	// exponential blowup in such case.
  1672  	//
  1673  	// TODO(perf): this cache ensures the conjuncts of an arc at most once
  1674  	// per ID. However, we really need to add the conjuncts of an arc only
  1675  	// once total, and then add the close information once per close ID
  1676  	// (pointer can probably be shared). Aside from being more performant,
  1677  	// this is probably the best way to guarantee that conjunctions are
  1678  	// linear in this case.
  1679  
  1680  	ckey := closeInfo
  1681  	ckey.Refs = nil
  1682  	ckey.Inline = false
  1683  	key := arcKey{arc, ckey}
  1684  	for _, k := range n.arcMap {
  1685  		if key == k {
  1686  			return
  1687  		}
  1688  	}
  1689  	n.arcMap = append(n.arcMap, key)
  1690  
  1691  	status := arc.status
  1692  
  1693  	switch status {
  1694  	case evaluating:
  1695  		// Reference cycle detected. We have reached a fixed point and
  1696  		// adding conjuncts at this point will not change the value. Also,
  1697  		// continuing to pursue this value will result in an infinite loop.
  1698  
  1699  		// TODO: add a mechanism so that the computation will only have to
  1700  		// be done once?
  1701  
  1702  		if arc == n.node {
  1703  			// TODO: we could use node sharing here. This may avoid an
  1704  			// exponential blowup during evaluation, like is possible with
  1705  			// YAML.
  1706  			return
  1707  		}
  1708  
  1709  	case evaluatingArcs:
  1710  		// There is a structural cycle, but values may be processed nonetheless
  1711  		// if there is a non-cyclic conjunct. See cycle.go.
  1712  	}
  1713  
  1714  	// Performance: the following if check filters cases that are not strictly
  1715  	// necessary for correct functioning. Not updating the closeInfo may cause
  1716  	// some position information to be lost for top-level positions of merges
  1717  	// resulting form APIs. These tend to be fairly uninteresting.
  1718  	// At the same time, this optimization may prevent considerable slowdown
  1719  	// in case an API does many calls to Unify.
  1720  	x := c.Expr()
  1721  	if !inline || arc.IsClosedStruct() || arc.IsClosedList() {
  1722  		closeInfo = closeInfo.SpawnRef(arc, IsDef(x), x)
  1723  	}
  1724  
  1725  	if arc.status == 0 && !inline {
  1726  		// This is a rare condition, but can happen in certain
  1727  		// evaluation orders. Unfortunately, adding this breaks
  1728  		// resolution of cyclic mutually referring disjunctions. But it
  1729  		// is necessary to prevent lookups in unevaluated structs.
  1730  		// TODO(cycles): this can probably most easily be fixed with a
  1731  		// having a more recursive implementation.
  1732  		n.ctx.unify(arc, oldOnly(partial))
  1733  	}
  1734  
  1735  	// Don't add conjuncts if a node is referring to itself.
  1736  	if n.node == arc {
  1737  		return
  1738  	}
  1739  
  1740  	if arc.state != nil {
  1741  		arc.state.addNotify(n.node, nil)
  1742  	}
  1743  
  1744  	for _, c := range arc.Conjuncts {
  1745  		// Note that we are resetting the tree here. We hereby assume that
  1746  		// closedness conflicts resulting from unifying the referenced arc were
  1747  		// already caught there and that we can ignore further errors here.
  1748  		c.CloseInfo = closeInfo
  1749  		n.addExprConjunct(c, partial)
  1750  	}
  1751  }
  1752  
  1753  func (n *nodeContext) addValueConjunct(env *Environment, v Value, id CloseInfo) {
  1754  	n.updateCyclicStatus(id)
  1755  
  1756  	ctx := n.ctx
  1757  
  1758  	if x, ok := v.(*Vertex); ok {
  1759  		if m, ok := x.BaseValue.(*StructMarker); ok {
  1760  			n.aStruct = x
  1761  			n.aStructID = id
  1762  			if m.NeedClose {
  1763  				id.IsClosed = true
  1764  			}
  1765  		}
  1766  
  1767  		if !x.IsData() {
  1768  			// TODO: this really shouldn't happen anymore.
  1769  			if isComplexStruct(ctx, x) {
  1770  				// This really shouldn't happen, but just in case.
  1771  				n.addVertexConjuncts(MakeConjunct(env, x, id), x, true)
  1772  				return
  1773  			}
  1774  
  1775  			for _, c := range x.Conjuncts {
  1776  				c.CloseInfo = id
  1777  				n.addExprConjunct(c, partial) // TODO: Pass from eval
  1778  			}
  1779  			return
  1780  		}
  1781  
  1782  		// TODO: evaluate value?
  1783  		switch v := x.BaseValue.(type) {
  1784  		default:
  1785  			panic(fmt.Sprintf("invalid type %T", x.BaseValue))
  1786  
  1787  		case *ListMarker:
  1788  			n.vLists = append(n.vLists, x)
  1789  			return
  1790  
  1791  		case *StructMarker:
  1792  
  1793  		case Value:
  1794  			n.addValueConjunct(env, v, id)
  1795  		}
  1796  
  1797  		if len(x.Arcs) == 0 {
  1798  			return
  1799  		}
  1800  
  1801  		s := &StructLit{}
  1802  
  1803  		// Keep ordering of Go struct for topological sort.
  1804  		n.node.AddStruct(s, env, id)
  1805  		n.node.Structs = append(n.node.Structs, x.Structs...)
  1806  
  1807  		for _, a := range x.Arcs {
  1808  			if !a.definitelyExists() {
  1809  				continue
  1810  			}
  1811  			// TODO(errors): report error when this is a regular field.
  1812  			c := MakeConjunct(nil, a, id)
  1813  			n.insertField(a.Label, a.ArcType, c)
  1814  			s.MarkField(a.Label)
  1815  		}
  1816  		return
  1817  	}
  1818  
  1819  	switch b := v.(type) {
  1820  	case *Bottom:
  1821  		n.addBottom(b)
  1822  		return
  1823  	case *Builtin:
  1824  		if v := b.BareValidator(); v != nil {
  1825  			n.addValueConjunct(env, v, id)
  1826  			return
  1827  		}
  1828  	}
  1829  
  1830  	if !n.updateNodeType(v.Kind(), v, id) {
  1831  		return
  1832  	}
  1833  
  1834  	switch x := v.(type) {
  1835  	case *Disjunction:
  1836  		n.addDisjunctionValue(env, x, id)
  1837  
  1838  	case *Conjunction:
  1839  		for _, x := range x.Values {
  1840  			n.addValueConjunct(env, x, id)
  1841  		}
  1842  
  1843  	case *Top:
  1844  		n.hasTop = true
  1845  
  1846  	case *BasicType:
  1847  		// handled above
  1848  
  1849  	case *BoundValue:
  1850  		switch x.Op {
  1851  		case LessThanOp, LessEqualOp:
  1852  			if y := n.upperBound; y != nil {
  1853  				n.upperBound = nil
  1854  				v := SimplifyBounds(ctx, n.kind, x, y)
  1855  				if err := valueError(v); err != nil {
  1856  					err.AddPosition(v)
  1857  					err.AddPosition(n.upperBound)
  1858  					err.AddClosedPositions(id)
  1859  				}
  1860  				n.addValueConjunct(env, v, id)
  1861  				return
  1862  			}
  1863  			n.upperBound = x
  1864  
  1865  		case GreaterThanOp, GreaterEqualOp:
  1866  			if y := n.lowerBound; y != nil {
  1867  				n.lowerBound = nil
  1868  				v := SimplifyBounds(ctx, n.kind, x, y)
  1869  				if err := valueError(v); err != nil {
  1870  					err.AddPosition(v)
  1871  					err.AddPosition(n.lowerBound)
  1872  					err.AddClosedPositions(id)
  1873  				}
  1874  				n.addValueConjunct(env, v, id)
  1875  				return
  1876  			}
  1877  			n.lowerBound = x
  1878  
  1879  		case EqualOp, NotEqualOp, MatchOp, NotMatchOp:
  1880  			// This check serves as simplifier, but also to remove duplicates.
  1881  			k := 0
  1882  			match := false
  1883  			for _, c := range n.checks {
  1884  				if y, ok := c.(*BoundValue); ok {
  1885  					switch z := SimplifyBounds(ctx, n.kind, x, y); {
  1886  					case z == y:
  1887  						match = true
  1888  					case z == x:
  1889  						continue
  1890  					}
  1891  				}
  1892  				n.checks[k] = c
  1893  				k++
  1894  			}
  1895  			n.checks = n.checks[:k]
  1896  			if !match {
  1897  				n.checks = append(n.checks, x)
  1898  			}
  1899  			return
  1900  		}
  1901  
  1902  	case Validator:
  1903  		// This check serves as simplifier, but also to remove duplicates.
  1904  		for i, y := range n.checks {
  1905  			if b := SimplifyValidator(ctx, x, y); b != nil {
  1906  				n.checks[i] = b
  1907  				return
  1908  			}
  1909  		}
  1910  		n.updateNodeType(x.Kind(), x, id)
  1911  		n.checks = append(n.checks, x)
  1912  
  1913  	case *Vertex:
  1914  	// handled above.
  1915  
  1916  	case Value: // *NullLit, *BoolLit, *NumLit, *StringLit, *BytesLit, *Builtin
  1917  		if y := n.scalar; y != nil {
  1918  			if b, ok := BinOp(ctx, EqualOp, x, y).(*Bool); !ok || !b.B {
  1919  				n.reportConflict(x, y, x.Kind(), y.Kind(), n.scalarID, id)
  1920  			}
  1921  			// TODO: do we need to explicitly add again?
  1922  			// n.scalar = nil
  1923  			// n.addValueConjunct(c, BinOp(c, EqualOp, x, y))
  1924  			break
  1925  		}
  1926  		n.scalar = x
  1927  		n.scalarID = id
  1928  		if n.node.status >= conjuncts {
  1929  			n.node.BaseValue = x
  1930  		}
  1931  
  1932  	default:
  1933  		panic(fmt.Sprintf("unknown value type %T", x))
  1934  	}
  1935  
  1936  	if n.lowerBound != nil && n.upperBound != nil {
  1937  		if u := SimplifyBounds(ctx, n.kind, n.lowerBound, n.upperBound); u != nil {
  1938  			if err := valueError(u); err != nil {
  1939  				err.AddPosition(n.lowerBound)
  1940  				err.AddPosition(n.upperBound)
  1941  				err.AddClosedPositions(id)
  1942  			}
  1943  			n.lowerBound = nil
  1944  			n.upperBound = nil
  1945  			n.addValueConjunct(env, u, id)
  1946  		}
  1947  	}
  1948  }
  1949  
  1950  func valueError(v Value) *ValueError {
  1951  	if v == nil {
  1952  		return nil
  1953  	}
  1954  	b, _ := v.(*Bottom)
  1955  	if b == nil {
  1956  		return nil
  1957  	}
  1958  	err, _ := b.Err.(*ValueError)
  1959  	if err == nil {
  1960  		return nil
  1961  	}
  1962  	return err
  1963  }
  1964  
  1965  // addStruct collates the declarations of a struct.
  1966  //
  1967  // addStruct fulfills two additional pivotal functions:
  1968  //  1. Implement vertex unification (this happens through De Bruijn indices
  1969  //     combined with proper set up of Environments).
  1970  //  2. Implied closedness for definitions.
  1971  func (n *nodeContext) addStruct(
  1972  	env *Environment,
  1973  	s *StructLit,
  1974  	closeInfo CloseInfo) {
  1975  
  1976  	n.updateCyclicStatus(closeInfo)
  1977  
  1978  	// NOTE: This is a crucial point in the code:
  1979  	// Unification dereferencing happens here. The child nodes are set to
  1980  	// an Environment linked to the current node. Together with the De Bruijn
  1981  	// indices, this determines to which Vertex a reference resolves.
  1982  
  1983  	childEnv := &Environment{
  1984  		Up:     env,
  1985  		Vertex: n.node,
  1986  	}
  1987  
  1988  	s.Init()
  1989  
  1990  	if s.HasEmbed && !s.IsFile() {
  1991  		closeInfo = closeInfo.SpawnGroup(nil)
  1992  	}
  1993  
  1994  	parent := n.node.AddStruct(s, childEnv, closeInfo)
  1995  	closeInfo.IsClosed = false
  1996  
  1997  	parent.Disable = true // disable until processing is done.
  1998  
  1999  	for _, d := range s.Decls {
  2000  		switch x := d.(type) {
  2001  		case *Field:
  2002  			if x.Label.IsString() && x.ArcType == ArcMember {
  2003  				n.aStruct = s
  2004  				n.aStructID = closeInfo
  2005  			}
  2006  			n.insertField(x.Label, x.ArcType, MakeConjunct(childEnv, x, closeInfo))
  2007  
  2008  		case *LetField:
  2009  			arc := n.insertField(x.Label, ArcMember, MakeConjunct(childEnv, x, closeInfo))
  2010  			if x.IsMulti {
  2011  				arc.MultiLet = x.IsMulti
  2012  			}
  2013  
  2014  		case *DynamicField:
  2015  			n.aStruct = s
  2016  			n.aStructID = closeInfo
  2017  			n.dynamicFields = append(n.dynamicFields, envDynamic{childEnv, x, closeInfo, nil})
  2018  
  2019  		case *Comprehension:
  2020  			n.insertComprehension(childEnv, x, closeInfo)
  2021  
  2022  		case Expr:
  2023  			// add embedding to optional
  2024  
  2025  			// TODO(perf): only do this if addExprConjunct below will result in
  2026  			// a fieldSet. Otherwise the entry will just be removed next.
  2027  			id := closeInfo.SpawnEmbed(x)
  2028  
  2029  			c := MakeConjunct(childEnv, x, id)
  2030  			n.addExprConjunct(c, partial)
  2031  
  2032  		case *BulkOptionalField, *Ellipsis:
  2033  			// Nothing to do here. Note that the presence of these fields do not
  2034  			// excluded embedded scalars: only when they match actual fields
  2035  			// does it exclude those.
  2036  
  2037  		default:
  2038  			panic("unreachable")
  2039  		}
  2040  	}
  2041  
  2042  	if !s.HasEmbed {
  2043  		n.aStruct = s
  2044  		n.aStructID = closeInfo
  2045  	}
  2046  
  2047  	parent.Disable = false
  2048  
  2049  }
  2050  
  2051  // TODO(perf): if an arc is the only arc with that label added to a Vertex, and
  2052  // if there are no conjuncts of optional fields to be added, then the arc could
  2053  // be added as is until any of these conditions change. This would allow
  2054  // structure sharing in many cases. One should be careful, however, to
  2055  // recursively track arcs of previously unified evaluated vertices ot make this
  2056  // optimization meaningful.
  2057  //
  2058  // An alternative approach to avoid evaluating optional arcs (if we take that
  2059  // route) is to not recursively evaluate those arcs, even for Finalize. This is
  2060  // possible as it is not necessary to evaluate optional arcs to evaluate
  2061  // disjunctions.
  2062  func (n *nodeContext) insertField(f Feature, mode ArcType, x Conjunct) *Vertex {
  2063  	ctx := n.ctx
  2064  	if ctx.isDevVersion() {
  2065  		return n.insertArc(f, mode, x, x.CloseInfo, true)
  2066  	}
  2067  
  2068  	arc, isNew := n.node.GetArc(ctx, f, mode)
  2069  	if f.IsLet() && !isNew {
  2070  		arc.MultiLet = true
  2071  		return arc
  2072  	}
  2073  	if arc.hasConjunct(x) {
  2074  		return arc
  2075  	}
  2076  
  2077  	switch {
  2078  	case arc.state != nil:
  2079  		arc.state.addConjunctDynamic(x)
  2080  
  2081  	case arc.IsUnprocessed() || arc.status != finalized:
  2082  		arc.addConjunctUnchecked(x)
  2083  
  2084  	default:
  2085  		n.addBottom(&Bottom{
  2086  			Code: IncompleteError,
  2087  			Err: ctx.NewPosf(pos(x.Field()),
  2088  				"cannot add field %s: was already used",
  2089  				f.SelectorString(ctx)),
  2090  		})
  2091  	}
  2092  	return arc
  2093  }
  2094  
  2095  func (n *nodeContext) insertFieldUnchecked(f Feature, mode ArcType, x Conjunct) *Vertex {
  2096  	ctx := n.ctx
  2097  	if ctx.isDevVersion() {
  2098  		return n.insertArc(f, mode, x, x.CloseInfo, false)
  2099  	}
  2100  
  2101  	arc, isNew := n.node.GetArc(ctx, f, mode)
  2102  	if f.IsLet() && !isNew {
  2103  		arc.MultiLet = true
  2104  		return arc
  2105  	}
  2106  	arc.addConjunctUnchecked(x)
  2107  	return arc
  2108  }
  2109  
  2110  // expandOne adds dynamic fields to a node until a fixed point is reached.
  2111  // On each iteration, dynamic fields that cannot resolve due to incomplete
  2112  // values are skipped. They will be retried on the next iteration until no
  2113  // progress can be made. Note that a dynamic field may add more dynamic fields.
  2114  //
  2115  // forClauses are processed after all other clauses. A struct may be referenced
  2116  // before it is complete, meaning that fields added by other forms of injection
  2117  // may influence the result of a for clause _after_ it has already been
  2118  // processed. We could instead detect such insertion and feed it to the
  2119  // ForClause to generate another entry or have the for clause be recomputed.
  2120  // This seems to be too complicated and lead to iffy edge cases.
  2121  // TODO(errors): detect when a field is added to a struct that is already used
  2122  // in a for clause.
  2123  func (n *nodeContext) expandOne(state vertexStatus) (done bool) {
  2124  	unreachableForDev(n.ctx)
  2125  
  2126  	// Don't expand incomplete expressions if we detected a cycle.
  2127  	if n.done() || (n.hasCycle && !n.hasNonCycle) {
  2128  		return false
  2129  	}
  2130  
  2131  	var progress bool
  2132  
  2133  	if progress = n.injectDynamic(); progress {
  2134  		return true
  2135  	}
  2136  
  2137  	if progress = n.injectComprehensions(state); progress {
  2138  		return true
  2139  	}
  2140  
  2141  	// Do expressions after comprehensions, as comprehensions can never
  2142  	// refer to embedded scalars, whereas expressions may refer to generated
  2143  	// fields if we were to allow attributes to be defined alongside
  2144  	// scalars.
  2145  	exprs := n.exprs
  2146  	n.exprs = n.exprs[:0]
  2147  	for _, x := range exprs {
  2148  		n.addExprConjunct(x.c, state)
  2149  
  2150  		// collect and or
  2151  	}
  2152  	if len(n.exprs) < len(exprs) {
  2153  		return true
  2154  	}
  2155  
  2156  	// No progress, report error later if needed: unification with
  2157  	// disjuncts may resolve this later on.
  2158  	return false
  2159  }
  2160  
  2161  // injectDynamic evaluates and inserts dynamic declarations.
  2162  func (n *nodeContext) injectDynamic() (progress bool) {
  2163  	unreachableForDev(n.ctx)
  2164  
  2165  	ctx := n.ctx
  2166  	k := 0
  2167  
  2168  	a := n.dynamicFields
  2169  	for _, d := range n.dynamicFields {
  2170  		var f Feature
  2171  		x := d.field.Key
  2172  		// Push state to capture and remove errors.
  2173  		s := ctx.PushState(d.env, x.Source())
  2174  		v := ctx.evalState(x, oldOnly(finalized))
  2175  		b := ctx.PopState(s)
  2176  
  2177  		if b != nil && b.IsIncomplete() {
  2178  			d.err, _ = v.(*Bottom)
  2179  			a[k] = d
  2180  			k++
  2181  			continue
  2182  		}
  2183  		if b, _ := v.(*Bottom); b != nil {
  2184  			n.addValueConjunct(nil, b, d.id)
  2185  			continue
  2186  		}
  2187  		f = ctx.Label(d.field.Key, v)
  2188  		if f.IsInt() {
  2189  			n.addErr(ctx.NewPosf(pos(d.field.Key), "integer fields not supported"))
  2190  		}
  2191  		n.insertField(f, d.field.ArcType, MakeConjunct(d.env, d.field, d.id))
  2192  	}
  2193  
  2194  	progress = k < len(n.dynamicFields)
  2195  
  2196  	n.dynamicFields = a[:k]
  2197  
  2198  	return progress
  2199  }
  2200  
  2201  // addLists evaluates the queued list conjuncts and inserts its arcs into the
  2202  // Vertex.
  2203  //
  2204  // TODO: association arrays:
  2205  // If an association array marker was present in a struct, create a struct node
  2206  // instead of a list node. In either case, a node may only have list fields
  2207  // or struct fields and not both.
  2208  //
  2209  // addLists should be run after the fixpoint expansion:
  2210  //   - it enforces that comprehensions may not refer to the list itself
  2211  //   - there may be no other fields within the list.
  2212  //
  2213  // TODO(embeddedScalars): for embedded scalars, there should be another pass
  2214  // of evaluation expressions after expanding lists.
  2215  func (n *nodeContext) addLists(state combinedFlags) (progress bool) {
  2216  	if len(n.lists) == 0 && len(n.vLists) == 0 {
  2217  		return false
  2218  	}
  2219  
  2220  	var oneOfTheLists Expr
  2221  	var anID CloseInfo
  2222  
  2223  	isOpen := true
  2224  	max := 0
  2225  	var maxNode Expr
  2226  
  2227  	if m, ok := n.node.BaseValue.(*ListMarker); ok {
  2228  		isOpen = m.IsOpen
  2229  		max = len(n.node.Arcs)
  2230  	}
  2231  
  2232  	c := n.ctx
  2233  
  2234  	for _, l := range n.vLists {
  2235  		// XXX: set hasNonCycle if appropriate.
  2236  
  2237  		oneOfTheLists = l
  2238  
  2239  		elems := l.Elems()
  2240  		isClosed := l.IsClosedList()
  2241  
  2242  		switch {
  2243  		case len(elems) < max:
  2244  			if isClosed {
  2245  				n.invalidListLength(len(elems), max, l, maxNode)
  2246  				continue
  2247  			}
  2248  
  2249  		case len(elems) > max:
  2250  			if !isOpen {
  2251  				n.invalidListLength(max, len(elems), maxNode, l)
  2252  				continue
  2253  			}
  2254  			isOpen = !isClosed
  2255  			max = len(elems)
  2256  			maxNode = l
  2257  
  2258  		case isClosed:
  2259  			isOpen = false
  2260  			maxNode = l
  2261  		}
  2262  
  2263  		for _, a := range elems {
  2264  			if a.Conjuncts == nil {
  2265  				n.insertField(a.Label, ArcMember, MakeRootConjunct(nil, a))
  2266  				continue
  2267  			}
  2268  			for _, c := range a.Conjuncts {
  2269  				n.insertField(a.Label, ArcMember, c)
  2270  			}
  2271  		}
  2272  	}
  2273  
  2274  outer:
  2275  	// updateCyclicStatus may grow the list of values, so we cannot use range.
  2276  	for i := 0; i < len(n.lists); i++ {
  2277  		l := n.lists[i]
  2278  
  2279  		n.updateCyclicStatus(l.id)
  2280  
  2281  		if l.self {
  2282  			n.node.LockArcs = true
  2283  		}
  2284  
  2285  		index := int64(0)
  2286  		hasComprehension := false
  2287  		for j, elem := range l.list.Elems {
  2288  			switch x := elem.(type) {
  2289  			case *Comprehension:
  2290  				err := c.yield(nil, l.env, x, state, func(e *Environment) {
  2291  					label, err := MakeLabel(x.Source(), index, IntLabel)
  2292  					n.addErr(err)
  2293  					index++
  2294  					c := MakeConjunct(e, x.Value, l.id)
  2295  					n.insertField(label, ArcMember, c)
  2296  				})
  2297  				hasComprehension = true
  2298  				if err != nil {
  2299  					if err.ForCycle && !l.self {
  2300  						// The list has a comprehension that refers to the list
  2301  						// itself. This means we should postpone evaluating this
  2302  						// list until all other lists have been evaluated.
  2303  						n.lists[i].ignore = true
  2304  						l.self = true
  2305  						n.lists = append(n.lists, l)
  2306  					} else {
  2307  						n.addBottom(err)
  2308  					}
  2309  					continue outer
  2310  				}
  2311  
  2312  			case *Ellipsis:
  2313  				if j != len(l.list.Elems)-1 {
  2314  					n.addErr(c.Newf("ellipsis must be last element in list"))
  2315  				}
  2316  
  2317  				n.lists[i].elipsis = x
  2318  
  2319  			default:
  2320  				label, err := MakeLabel(x.Source(), index, IntLabel)
  2321  				n.addErr(err)
  2322  				index++ // TODO: don't use insertField.
  2323  				n.insertField(label, ArcMember, MakeConjunct(l.env, x, l.id))
  2324  			}
  2325  
  2326  			// Terminate early in case of runaway comprehension.
  2327  			if !isOpen && int(index) > max {
  2328  				n.invalidListLength(max, len(l.list.Elems), maxNode, l.list)
  2329  				continue outer
  2330  			}
  2331  		}
  2332  
  2333  		oneOfTheLists = l.list
  2334  		anID = l.id
  2335  
  2336  		switch closed := n.lists[i].elipsis == nil; {
  2337  		case int(index) < max:
  2338  			if closed {
  2339  				n.invalidListLength(int(index), max, l.list, maxNode)
  2340  				continue
  2341  			}
  2342  
  2343  		case int(index) > max,
  2344  			closed && isOpen,
  2345  			(!closed == isOpen) && !hasComprehension:
  2346  			max = int(index)
  2347  			maxNode = l.list
  2348  			isOpen = !closed
  2349  		}
  2350  
  2351  		n.lists[i].n = index
  2352  	}
  2353  
  2354  	// add additionalItem values to list and construct optionals.
  2355  	elems := n.node.Elems()
  2356  	for _, l := range n.vLists {
  2357  		if !l.IsClosedList() {
  2358  			continue
  2359  		}
  2360  
  2361  		newElems := l.Elems()
  2362  		if len(newElems) >= len(elems) {
  2363  			continue // error generated earlier, if applicable.
  2364  		}
  2365  
  2366  		for _, arc := range elems[len(newElems):] {
  2367  			l.MatchAndInsert(c, arc)
  2368  		}
  2369  	}
  2370  
  2371  	for _, l := range n.lists {
  2372  		if l.elipsis == nil || l.ignore {
  2373  			continue
  2374  		}
  2375  
  2376  		s := l.list.info
  2377  		if s == nil {
  2378  			s = &StructLit{Decls: []Decl{l.elipsis}}
  2379  			s.Init()
  2380  			l.list.info = s
  2381  		}
  2382  		info := n.node.AddStruct(s, l.env, l.id)
  2383  
  2384  		for _, arc := range elems[l.n:] {
  2385  			info.MatchAndInsert(c, arc)
  2386  		}
  2387  	}
  2388  
  2389  	sources := []ast.Expr{}
  2390  	// Add conjuncts for additional items.
  2391  	for _, l := range n.lists {
  2392  		if l.elipsis == nil || l.ignore {
  2393  			continue
  2394  		}
  2395  		if src, _ := l.elipsis.Source().(ast.Expr); src != nil {
  2396  			sources = append(sources, src)
  2397  		}
  2398  	}
  2399  
  2400  	if m, ok := n.node.BaseValue.(*ListMarker); !ok {
  2401  		n.node.setValue(c, partial, &ListMarker{
  2402  			Src:    ast.NewBinExpr(token.AND, sources...),
  2403  			IsOpen: isOpen,
  2404  		})
  2405  	} else {
  2406  		if expr, _ := m.Src.(ast.Expr); expr != nil {
  2407  			sources = append(sources, expr)
  2408  		}
  2409  		m.Src = ast.NewBinExpr(token.AND, sources...)
  2410  		m.IsOpen = m.IsOpen && isOpen
  2411  	}
  2412  
  2413  	n.lists = n.lists[:0]
  2414  	n.vLists = n.vLists[:0]
  2415  
  2416  	n.updateNodeType(ListKind, oneOfTheLists, anID)
  2417  
  2418  	return true
  2419  }
  2420  
  2421  func (n *nodeContext) invalidListLength(na, nb int, a, b Expr) {
  2422  	n.addErr(n.ctx.Newf("incompatible list lengths (%d and %d)", na, nb))
  2423  }
  2424  

View as plain text