Source file src/cuelang.org/go/internal/core/adt/composite.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  
    20  	"cuelang.org/go/cue/ast"
    21  	"cuelang.org/go/cue/errors"
    22  	"cuelang.org/go/cue/token"
    23  )
    24  
    25  // TODO: unanswered questions about structural cycles:
    26  //
    27  // 1. When detecting a structural cycle, should we consider this as:
    28  //    a) an unevaluated value,
    29  //    b) an incomplete error (which does not affect parent validity), or
    30  //    c) a special value.
    31  //
    32  // Making it an error is the simplest way to ensure reentrancy is disallowed:
    33  // without an error it would require an additional mechanism to stop reentrancy
    34  // from continuing to process. Even worse, in some cases it may only partially
    35  // evaluate, resulting in unexpected results. For this reason, we are taking
    36  // approach `b` for now.
    37  //
    38  // This has some consequences of how disjunctions are treated though. Consider
    39  //
    40  //     list: {
    41  //        head: _
    42  //        tail: list | null
    43  //     }
    44  //
    45  // When making it an error, evaluating the above will result in
    46  //
    47  //     list: {
    48  //        head: _
    49  //        tail: null
    50  //     }
    51  //
    52  // because list will result in a structural cycle, and thus an error, it will be
    53  // stripped from the disjunction. This may or may not be a desirable property. A
    54  // nice thing is that it is not required to write `list | *null`. A disadvantage
    55  // is that this is perhaps somewhat inexplicit.
    56  //
    57  // When not making it an error (and simply cease evaluating child arcs upon
    58  // cycle detection), the result would be:
    59  //
    60  //     list: {
    61  //        head: _
    62  //        tail: list | null
    63  //     }
    64  //
    65  // In other words, an evaluation would result in a cycle and thus an error.
    66  // Implementations can recognize such cases by having unevaluated arcs. An
    67  // explicit structure cycle marker would probably be less error prone.
    68  //
    69  // Note that in both cases, a reference to list will still use the original
    70  // conjuncts, so the result will be the same for either method in this case.
    71  //
    72  //
    73  // 2. Structural cycle allowance.
    74  //
    75  // Structural cycle detection disallows reentrancy as well. This means one
    76  // cannot use structs for recursive computation. This will probably preclude
    77  // evaluation of some configuration. Given that there is no real alternative
    78  // yet, we could allow structural cycle detection to be optionally disabled.
    79  
    80  // An Environment links the parent scopes for identifier lookup to a composite
    81  // node. Each conjunct that make up node in the tree can be associated with
    82  // a different environment (although some conjuncts may share an Environment).
    83  type Environment struct {
    84  	Up     *Environment
    85  	Vertex *Vertex
    86  
    87  	// DynamicLabel is only set when instantiating a field from a pattern
    88  	// constraint. It is used to resolve label references.
    89  	DynamicLabel Feature
    90  
    91  	// TODO(perf): make the following public fields a shareable struct as it
    92  	// mostly is going to be the same for child nodes.
    93  
    94  	// TODO: This can probably move into the nodeContext, making it a map from
    95  	// conjunct to Value.
    96  	cache map[cacheKey]Value
    97  }
    98  
    99  type cacheKey struct {
   100  	Expr Expr
   101  	Arc  *Vertex
   102  }
   103  
   104  func (e *Environment) up(ctx *OpContext, count int32) *Environment {
   105  	for ; count > 0; count-- {
   106  		e = e.Up
   107  		ctx.Assertf(ctx.Pos(), e.Vertex != nil, "Environment.up encountered a nil vertex")
   108  	}
   109  	return e
   110  }
   111  
   112  type ID int32
   113  
   114  // evalCached is used to look up dynamic field pattern constraint expressions.
   115  func (e *Environment) evalCached(c *OpContext, x Expr) Value {
   116  	if v, ok := x.(Value); ok {
   117  		return v
   118  	}
   119  	key := cacheKey{x, nil}
   120  	v, ok := e.cache[key]
   121  	if !ok {
   122  		if e.cache == nil {
   123  			e.cache = map[cacheKey]Value{}
   124  		}
   125  		env, src := c.e, c.src
   126  		c.e, c.src = e, x.Source()
   127  		// Save and restore errors to ensure that only relevant errors are
   128  		// associated with the cash.
   129  		err := c.errs
   130  		v = c.evalState(x, require(partial, allKnown)) // TODO: should this be finalized?
   131  		c.e, c.src = env, src
   132  		c.errs = err
   133  		if b, ok := v.(*Bottom); !ok || !b.IsIncomplete() {
   134  			e.cache[key] = v
   135  		}
   136  	}
   137  	return v
   138  }
   139  
   140  // A Vertex is a node in the value tree. It may be a leaf or internal node.
   141  // It may have arcs to represent elements of a fully evaluated struct or list.
   142  //
   143  // For structs, it only contains definitions and concrete fields.
   144  // optional fields are dropped.
   145  //
   146  // It maintains source information such as a list of conjuncts that contributed
   147  // to the value.
   148  type Vertex struct {
   149  	// Parent links to a parent Vertex. This parent should only be used to
   150  	// access the parent's Label field to find the relative location within a
   151  	// tree.
   152  	Parent *Vertex
   153  
   154  	// State:
   155  	//   eval: nil, BaseValue: nil -- unevaluated
   156  	//   eval: *,   BaseValue: nil -- evaluating
   157  	//   eval: *,   BaseValue: *   -- finalized
   158  	//
   159  	state *nodeContext
   160  
   161  	// cc manages the closedness logic for this Vertex. It is created
   162  	// by rootCloseContext.
   163  	// TODO: move back to nodeContext, but be sure not to clone it.
   164  	cc *closeContext
   165  
   166  	// Label is the feature leading to this vertex.
   167  	Label Feature
   168  
   169  	// TODO: move the following fields to nodeContext.
   170  
   171  	// status indicates the evaluation progress of this vertex.
   172  	status vertexStatus
   173  
   174  	// hasAllConjuncts indicates that the set of conjuncts is complete.
   175  	// This is the case if the conjuncts of all its ancestors have been
   176  	// processed.
   177  	hasAllConjuncts bool
   178  
   179  	// isData indicates that this Vertex is to be interpreted as data: pattern
   180  	// and additional constraints, as well as optional fields, should be
   181  	// ignored.
   182  	isData bool
   183  
   184  	// Closed indicates whether this Vertex is recursively closed. This is the
   185  	// case, for instance, if it is a node in a definition or if one of the
   186  	// conjuncts, or ancestor conjuncts, is a definition.
   187  	Closed bool
   188  
   189  	// MultiLet indicates whether multiple let fields were added from
   190  	// different sources. If true, a LetReference must be resolved using
   191  	// the per-Environment value cache.
   192  	MultiLet bool
   193  
   194  	// After this is set, no more arcs may be added during evaluation. This is
   195  	// set, for instance, after a Vertex is used as a source for comprehensions,
   196  	// or any other operation that relies on the set of arcs being constant.
   197  	LockArcs bool
   198  
   199  	// IsDynamic signifies whether this struct is computed as part of an
   200  	// expression and not part of the static evaluation tree.
   201  	// Used for cycle detection.
   202  	IsDynamic bool
   203  
   204  	nonRooted bool // indicates that there is no path from the root of the tree.
   205  
   206  	// hasPendingArc is set if this Vertex has a void arc (e.g. for comprehensions)
   207  	hasPendingArc bool
   208  
   209  	// ArcType indicates the level of optionality of this arc.
   210  	ArcType ArcType
   211  
   212  	// cyclicReferences is a linked list of internal references pointing to this
   213  	// Vertex. This is used to shorten the path of some structural cycles.
   214  	cyclicReferences *RefNode
   215  
   216  	// BaseValue is the value associated with this vertex. For lists and structs
   217  	// this is a sentinel value indicating its kind.
   218  	BaseValue BaseValue
   219  
   220  	// ChildErrors is the collection of all errors of children.
   221  	ChildErrors *Bottom
   222  
   223  	// The parent of nodes can be followed to determine the path within the
   224  	// configuration of this node.
   225  	// Value  Value
   226  	Arcs []*Vertex // arcs are sorted in display order.
   227  
   228  	// PatternConstraints are additional constraints that match more nodes.
   229  	// Constraints that match existing Arcs already have their conjuncts
   230  	// mixed in.
   231  	// TODO: either put in StructMarker/ListMarker or integrate with Arcs
   232  	// so that this pointer is unnecessary.
   233  	PatternConstraints *Constraints
   234  
   235  	// Conjuncts lists the structs that ultimately formed this Composite value.
   236  	// This includes all selected disjuncts.
   237  	//
   238  	// This value may be nil, in which case the Arcs are considered to define
   239  	// the final value of this Vertex.
   240  	Conjuncts []Conjunct
   241  
   242  	// Structs is a slice of struct literals that contributed to this value.
   243  	// This information is used to compute the topological sort of arcs.
   244  	Structs []*StructInfo
   245  }
   246  
   247  // rootCloseContext creates a closeContext for this Vertex or returns the
   248  // existing one.
   249  func (v *Vertex) rootCloseContext() *closeContext {
   250  	if v.cc == nil {
   251  		v.cc = &closeContext{
   252  			group:           &ConjunctGroup{},
   253  			parent:          nil,
   254  			src:             v,
   255  			parentConjuncts: v,
   256  		}
   257  		v.cc.incDependent(ROOT, nil) // matched in REF(decrement:nodeDone)
   258  	}
   259  	return v.cc
   260  }
   261  
   262  // newInlineVertex creates a Vertex that is needed for computation, but for
   263  // which there is no CUE path defined from the root Vertex.
   264  func (ctx *OpContext) newInlineVertex(parent *Vertex, v BaseValue, a ...Conjunct) *Vertex {
   265  	return &Vertex{
   266  		Parent:    parent,
   267  		BaseValue: v,
   268  		IsDynamic: true,
   269  		ArcType:   ArcMember,
   270  		Conjuncts: a,
   271  	}
   272  }
   273  
   274  // updateArcType updates v.ArcType if t is more restrictive.
   275  func (v *Vertex) updateArcType(t ArcType) {
   276  	if t >= v.ArcType {
   277  		return
   278  	}
   279  	if v.ArcType == ArcNotPresent {
   280  		return
   281  	}
   282  	if s := v.state; s != nil && s.ctx.isDevVersion() {
   283  		c := s.ctx
   284  		if s.scheduler.frozen.meets(arcTypeKnown) {
   285  			parent := v.Parent
   286  			parent.reportFieldCycleError(c, c.Source().Pos(), v.Label)
   287  			return
   288  		}
   289  	}
   290  	v.ArcType = t
   291  }
   292  
   293  // isDefined indicates whether this arc is a "value" field, and not a constraint
   294  // or void arc.
   295  func (v *Vertex) isDefined() bool {
   296  	return v.ArcType == ArcMember
   297  }
   298  
   299  // IsConstraint reports whether the Vertex is an optional or required field.
   300  func (v *Vertex) IsConstraint() bool {
   301  	return v.ArcType == ArcOptional || v.ArcType == ArcRequired
   302  }
   303  
   304  // IsDefined indicates whether this arc is defined meaning it is not a
   305  // required or optional constraint and not a "void" arc.
   306  // It will evaluate the arc, and thus evaluate any comprehension, to make this
   307  // determination.
   308  func (v *Vertex) IsDefined(c *OpContext) bool {
   309  	if v.isDefined() {
   310  		return true
   311  	}
   312  	v.Finalize(c)
   313  	return v.isDefined()
   314  }
   315  
   316  // Rooted reports whether there is a path from the root of the tree to this
   317  // Vertex.
   318  func (v *Vertex) Rooted() bool {
   319  	return !v.nonRooted && !v.Label.IsLet() && !v.IsDynamic
   320  }
   321  
   322  type ArcType uint8
   323  
   324  const (
   325  	// ArcMember means that this arc is a normal non-optional field
   326  	// (including regular, hidden, and definition fields).
   327  	ArcMember ArcType = iota
   328  
   329  	// ArcRequired is like optional, but requires that a field be specified.
   330  	// Fields are of the form foo!.
   331  	ArcRequired
   332  
   333  	// ArcOptional represents fields of the form foo? and defines constraints
   334  	// for foo in case it is defined.
   335  	ArcOptional
   336  
   337  	// ArcPending means that it is not known yet whether an arc exists and that
   338  	// its conjuncts need to be processed to find out. This happens when an arc
   339  	// is provisionally added as part of a comprehension, but when this
   340  	// comprehension has not yet yielded any results.
   341  	ArcPending
   342  
   343  	// ArcNotPresent indicates that this arc is not present and, unlike
   344  	// ArcPending, needs no further processing.
   345  	ArcNotPresent
   346  
   347  	// TODO: define a type for optional arcs. This will be needed for pulling
   348  	// in optional fields into the Vertex, which, in turn, is needed for
   349  	// structure sharing, among other things.
   350  	// We could also define types for required fields and potentially lets.
   351  )
   352  
   353  func (a ArcType) String() string {
   354  	switch a {
   355  	case ArcMember:
   356  		return "Member"
   357  	case ArcOptional:
   358  		return "Optional"
   359  	case ArcRequired:
   360  		return "Required"
   361  	case ArcPending:
   362  		return "Pending"
   363  	case ArcNotPresent:
   364  		return "NotPresent"
   365  	}
   366  	return fmt.Sprintf("ArcType(%d)", a)
   367  }
   368  
   369  // definitelyExists reports whether an arc is a constraint or member arc.
   370  // TODO: we should check that users of this call ensure there are no
   371  // ArcPendings.
   372  func (v *Vertex) definitelyExists() bool {
   373  	return v.ArcType < ArcPending
   374  }
   375  
   376  // ConstraintFromToken converts a given AST constraint token to the
   377  // corresponding ArcType.
   378  func ConstraintFromToken(t token.Token) ArcType {
   379  	switch t {
   380  	case token.OPTION:
   381  		return ArcOptional
   382  	case token.NOT:
   383  		return ArcRequired
   384  	}
   385  	return ArcMember
   386  }
   387  
   388  // Token reports the token corresponding to the constraint represented by a,
   389  // or token.ILLEGAL otherwise.
   390  func (a ArcType) Token() (t token.Token) {
   391  	switch a {
   392  	case ArcOptional:
   393  		t = token.OPTION
   394  	case ArcRequired:
   395  		t = token.NOT
   396  	}
   397  	return t
   398  }
   399  
   400  // Suffix reports the field suffix for the given ArcType if it is a
   401  // constraint or the empty string otherwise.
   402  func (a ArcType) Suffix() string {
   403  	switch a {
   404  	case ArcOptional:
   405  		return "?"
   406  	case ArcRequired:
   407  		return "!"
   408  
   409  	// For debugging internal state. This is not CUE syntax.
   410  	case ArcPending:
   411  		return "*"
   412  	case ArcNotPresent:
   413  		return "-"
   414  	}
   415  	return ""
   416  }
   417  
   418  func (v *Vertex) Clone() *Vertex {
   419  	c := *v
   420  	c.state = nil
   421  	return &c
   422  }
   423  
   424  type StructInfo struct {
   425  	*StructLit
   426  
   427  	Env *Environment
   428  
   429  	CloseInfo
   430  
   431  	// Embed indicates the struct in which this struct is embedded (originally),
   432  	// or nil if this is a root structure.
   433  	// Embed   *StructInfo
   434  	// Context *RefInfo // the location from which this struct originates.
   435  	Disable bool
   436  
   437  	Embedding bool
   438  }
   439  
   440  // TODO(perf): this could be much more aggressive for eliminating structs that
   441  // are immaterial for closing.
   442  func (s *StructInfo) useForAccept() bool {
   443  	if c := s.closeInfo; c != nil {
   444  		return !c.noCheck
   445  	}
   446  	return true
   447  }
   448  
   449  // vertexStatus indicates the evaluation progress of a Vertex.
   450  type vertexStatus int8
   451  
   452  const (
   453  	// unprocessed indicates a Vertex has not been processed before.
   454  	// Value must be nil.
   455  	unprocessed vertexStatus = iota
   456  
   457  	// evaluating means that the current Vertex is being evaluated. If this is
   458  	// encountered it indicates a reference cycle. Value must be nil.
   459  	evaluating
   460  
   461  	// partial indicates that the result was only partially evaluated. It will
   462  	// need to be fully evaluated to get a complete results.
   463  	//
   464  	// TODO: this currently requires a renewed computation. Cache the
   465  	// nodeContext to allow reusing the computations done so far.
   466  	partial
   467  
   468  	// conjuncts is the state reached when all conjuncts have been evaluated,
   469  	// but without recursively processing arcs.
   470  	conjuncts
   471  
   472  	// evaluatingArcs indicates that the arcs of the Vertex are currently being
   473  	// evaluated. If this is encountered it indicates a structural cycle.
   474  	// Value does not have to be nil
   475  	evaluatingArcs
   476  
   477  	// finalized means that this node is fully evaluated and that the results
   478  	// are save to use without further consideration.
   479  	finalized
   480  )
   481  
   482  func (s vertexStatus) String() string {
   483  	switch s {
   484  	case unprocessed:
   485  		return "unprocessed"
   486  	case evaluating:
   487  		return "evaluating"
   488  	case partial:
   489  		return "partial"
   490  	case conjuncts:
   491  		return "conjuncts"
   492  	case evaluatingArcs:
   493  		return "evaluatingArcs"
   494  	case finalized:
   495  		return "finalized"
   496  	default:
   497  		return "unknown"
   498  	}
   499  }
   500  
   501  func (v *Vertex) Status() vertexStatus {
   502  	return v.status
   503  }
   504  
   505  // ForceDone prevents v from being evaluated.
   506  func (v *Vertex) ForceDone() {
   507  	v.updateStatus(finalized)
   508  }
   509  
   510  // IsUnprocessed reports whether v is unprocessed.
   511  func (v *Vertex) IsUnprocessed() bool {
   512  	return v.status == unprocessed
   513  }
   514  
   515  func (v *Vertex) updateStatus(s vertexStatus) {
   516  	Assertf(v.status <= s+1, "attempt to regress status from %d to %d", v.Status(), s)
   517  
   518  	if s == finalized && v.BaseValue == nil {
   519  		// TODO: for debugging.
   520  		// panic("not finalized")
   521  	}
   522  	v.status = s
   523  }
   524  
   525  // setParentDone signals v that the conjuncts of all ancestors have been
   526  // processed.
   527  // If all conjuncts of this node have been set, all arcs will be notified
   528  // of this parent being done.
   529  //
   530  // Note: once a vertex has started evaluation (state != nil), insertField will
   531  // cause all conjuncts to be immediately processed. This means that if all
   532  // ancestors of this node processed their conjuncts, and if this node has
   533  // processed all its conjuncts as well, all nodes that it embedded will have
   534  // received all their conjuncts as well, after which this node will have been
   535  // notified of these conjuncts.
   536  func (v *Vertex) setParentDone() {
   537  	v.hasAllConjuncts = true
   538  	// Could set "Conjuncts" flag of arc at this point.
   539  	if n := v.state; n != nil && len(n.conjuncts) == n.conjunctsPos {
   540  		for _, a := range v.Arcs {
   541  			a.setParentDone()
   542  		}
   543  	}
   544  }
   545  
   546  // Value returns the Value of v without definitions if it is a scalar
   547  // or itself otherwise.
   548  func (v *Vertex) Value() Value {
   549  	switch x := v.BaseValue.(type) {
   550  	case nil:
   551  		return nil
   552  	case *StructMarker, *ListMarker:
   553  		return v
   554  	case Value:
   555  		// TODO: recursively descend into Vertex?
   556  		return x
   557  	default:
   558  		panic(fmt.Sprintf("unexpected type %T", v.BaseValue))
   559  	}
   560  }
   561  
   562  // isUndefined reports whether a vertex does not have a useable BaseValue yet.
   563  func (v *Vertex) isUndefined() bool {
   564  	if !v.isDefined() {
   565  		return true
   566  	}
   567  	switch v.BaseValue {
   568  	case nil, cycle:
   569  		return true
   570  	}
   571  	return false
   572  }
   573  
   574  func (x *Vertex) IsConcrete() bool {
   575  	return x.Concreteness() <= Concrete
   576  }
   577  
   578  // IsData reports whether v should be interpreted in data mode. In other words,
   579  // it tells whether optional field matching and non-regular fields, like
   580  // definitions and hidden fields, should be ignored.
   581  func (v *Vertex) IsData() bool {
   582  	return v.isData || len(v.Conjuncts) == 0
   583  }
   584  
   585  // ToDataSingle creates a new Vertex that represents just the regular fields
   586  // of this vertex. Arcs are left untouched.
   587  // It is used by cue.Eval to convert nodes to data on per-node basis.
   588  func (v *Vertex) ToDataSingle() *Vertex {
   589  	w := *v
   590  	w.isData = true
   591  	w.state = nil
   592  	w.status = finalized
   593  	return &w
   594  }
   595  
   596  // ToDataAll returns a new v where v and all its descendents contain only
   597  // the regular fields.
   598  func (v *Vertex) ToDataAll(ctx *OpContext) *Vertex {
   599  	arcs := make([]*Vertex, 0, len(v.Arcs))
   600  	for _, a := range v.Arcs {
   601  		if !a.IsDefined(ctx) {
   602  			continue
   603  		}
   604  		if a.Label.IsRegular() {
   605  			arcs = append(arcs, a.ToDataAll(ctx))
   606  		}
   607  	}
   608  	w := *v
   609  	w.state = nil
   610  	w.status = finalized
   611  
   612  	w.BaseValue = toDataAll(ctx, w.BaseValue)
   613  	w.Arcs = arcs
   614  	w.isData = true
   615  	w.Conjuncts = make([]Conjunct, len(v.Conjuncts))
   616  	// TODO(perf): this is not strictly necessary for evaluation, but it can
   617  	// hurt performance greatly. Drawback is that it may disable ordering.
   618  	for _, s := range w.Structs {
   619  		s.Disable = true
   620  	}
   621  	copy(w.Conjuncts, v.Conjuncts)
   622  	for i, c := range w.Conjuncts {
   623  		if v, _ := c.x.(Value); v != nil {
   624  			w.Conjuncts[i].x = toDataAll(ctx, v).(Value)
   625  		}
   626  	}
   627  	return &w
   628  }
   629  
   630  func toDataAll(ctx *OpContext, v BaseValue) BaseValue {
   631  	switch x := v.(type) {
   632  	default:
   633  		return x
   634  
   635  	case *Vertex:
   636  		return x.ToDataAll(ctx)
   637  
   638  	// The following cases are always erroneous, but we handle them anyway
   639  	// to avoid issues with the closedness algorithm down the line.
   640  	case *Disjunction:
   641  		d := *x
   642  		d.Values = make([]Value, len(x.Values))
   643  		for i, v := range x.Values {
   644  			switch x := v.(type) {
   645  			case *Vertex:
   646  				d.Values[i] = x.ToDataAll(ctx)
   647  			default:
   648  				d.Values[i] = x
   649  			}
   650  		}
   651  		return &d
   652  
   653  	case *Conjunction:
   654  		c := *x
   655  		c.Values = make([]Value, len(x.Values))
   656  		for i, v := range x.Values {
   657  			// This case is okay because the source is of type Value.
   658  			c.Values[i] = toDataAll(ctx, v).(Value)
   659  		}
   660  		return &c
   661  	}
   662  }
   663  
   664  // func (v *Vertex) IsEvaluating() bool {
   665  // 	return v.Value == cycle
   666  // }
   667  
   668  func (v *Vertex) IsErr() bool {
   669  	// if v.Status() > Evaluating {
   670  	if _, ok := v.BaseValue.(*Bottom); ok {
   671  		return true
   672  	}
   673  	// }
   674  	return false
   675  }
   676  
   677  func (v *Vertex) Err(c *OpContext) *Bottom {
   678  	v.Finalize(c)
   679  	if b, ok := v.BaseValue.(*Bottom); ok {
   680  		return b
   681  	}
   682  	return nil
   683  }
   684  
   685  // func (v *Vertex) Evaluate()
   686  
   687  func (v *Vertex) Finalize(c *OpContext) {
   688  	// Saving and restoring the error context prevents v from panicking in
   689  	// case the caller did not handle existing errors in the context.
   690  	err := c.errs
   691  	c.errs = nil
   692  	c.unify(v, final(finalized, allKnown))
   693  	c.errs = err
   694  }
   695  
   696  // CompleteArcs ensures the set of arcs has been computed.
   697  func (v *Vertex) CompleteArcs(c *OpContext) {
   698  	c.unify(v, final(conjuncts, allKnown))
   699  }
   700  
   701  func (v *Vertex) AddErr(ctx *OpContext, b *Bottom) {
   702  	v.SetValue(ctx, CombineErrors(nil, v.Value(), b))
   703  }
   704  
   705  // SetValue sets the value of a node.
   706  func (v *Vertex) SetValue(ctx *OpContext, value BaseValue) *Bottom {
   707  	return v.setValue(ctx, finalized, value)
   708  }
   709  
   710  func (v *Vertex) setValue(ctx *OpContext, state vertexStatus, value BaseValue) *Bottom {
   711  	v.BaseValue = value
   712  	// TODO: should not set status here for new evaluator.
   713  	v.updateStatus(state)
   714  	return nil
   715  }
   716  
   717  // ToVertex wraps v in a new Vertex, if necessary.
   718  func ToVertex(v Value) *Vertex {
   719  	switch x := v.(type) {
   720  	case *Vertex:
   721  		return x
   722  	default:
   723  		n := &Vertex{
   724  			status:    finalized,
   725  			BaseValue: x,
   726  		}
   727  		n.AddConjunct(MakeRootConjunct(nil, v))
   728  		return n
   729  	}
   730  }
   731  
   732  // Unwrap returns the possibly non-concrete scalar value of v, v itself for
   733  // lists and structs, or nil if v is an undefined type.
   734  func Unwrap(v Value) Value {
   735  	x, ok := v.(*Vertex)
   736  	if !ok {
   737  		return v
   738  	}
   739  	x = x.Indirect()
   740  	if n := x.state; n != nil && isCyclePlaceholder(x.BaseValue) {
   741  		if n.errs != nil && !n.errs.IsIncomplete() {
   742  			return n.errs
   743  		}
   744  		if n.scalar != nil {
   745  			return n.scalar
   746  		}
   747  	}
   748  	return x.Value()
   749  }
   750  
   751  // Indirect unrolls indirections of Vertex values. These may be introduced,
   752  // for instance, by temporary bindings such as comprehension values.
   753  // It returns v itself if v does not point to another Vertex.
   754  func (v *Vertex) Indirect() *Vertex {
   755  	for {
   756  		arc, ok := v.BaseValue.(*Vertex)
   757  		if !ok {
   758  			return v
   759  		}
   760  		v = arc
   761  	}
   762  }
   763  
   764  // OptionalType is a bit field of the type of optional constraints in use by an
   765  // Acceptor.
   766  type OptionalType int8
   767  
   768  const (
   769  	HasField          OptionalType = 1 << iota // X: T
   770  	HasDynamic                                 // (X): T or "\(X)": T
   771  	HasPattern                                 // [X]: T
   772  	HasComplexPattern                          // anything but a basic type
   773  	HasAdditional                              // ...T
   774  	IsOpen                                     // Defined for all fields
   775  )
   776  
   777  func (v *Vertex) Kind() Kind {
   778  	// This is possible when evaluating comprehensions. It is potentially
   779  	// not known at this time what the type is.
   780  	switch {
   781  	// TODO: using this line would be more stable.
   782  	// case v.status != finalized && v.state != nil:
   783  	case v.state != nil:
   784  		return v.state.kind
   785  	case v.BaseValue == nil:
   786  		return TopKind
   787  	default:
   788  		return v.BaseValue.Kind()
   789  	}
   790  }
   791  
   792  func (v *Vertex) OptionalTypes() OptionalType {
   793  	var mask OptionalType
   794  	for _, s := range v.Structs {
   795  		mask |= s.OptionalTypes()
   796  	}
   797  	return mask
   798  }
   799  
   800  // IsOptional reports whether a field is explicitly defined as optional,
   801  // as opposed to whether it is allowed by a pattern constraint.
   802  func (v *Vertex) IsOptional(label Feature) bool {
   803  	for _, a := range v.Arcs {
   804  		if a.Label == label {
   805  			return a.IsConstraint()
   806  		}
   807  	}
   808  	return false
   809  }
   810  
   811  func (v *Vertex) accepts(ok, required bool) bool {
   812  	return ok || (!required && !v.Closed)
   813  }
   814  
   815  func (v *Vertex) IsClosedStruct() bool {
   816  	switch x := v.BaseValue.(type) {
   817  	default:
   818  		return false
   819  
   820  	case *StructMarker:
   821  		if x.NeedClose {
   822  			return true
   823  		}
   824  
   825  	case *Disjunction:
   826  	}
   827  	return isClosed(v)
   828  }
   829  
   830  func (v *Vertex) IsClosedList() bool {
   831  	if x, ok := v.BaseValue.(*ListMarker); ok {
   832  		return !x.IsOpen
   833  	}
   834  	return false
   835  }
   836  
   837  // TODO: return error instead of boolean? (or at least have version that does.)
   838  func (v *Vertex) Accept(ctx *OpContext, f Feature) bool {
   839  	if f.IsHidden() || f.IsLet() {
   840  		return true
   841  	}
   842  
   843  	if x, ok := v.BaseValue.(*Disjunction); ok {
   844  		for _, v := range x.Values {
   845  			if x, ok := v.(*Vertex); ok && x.Accept(ctx, f) {
   846  				return true
   847  			}
   848  		}
   849  		return false
   850  	}
   851  
   852  	if f.IsInt() {
   853  		switch v.BaseValue.(type) {
   854  		case *ListMarker:
   855  			// TODO(perf): use precomputed length.
   856  			if f.Index() < len(v.Elems()) {
   857  				return true
   858  			}
   859  			return !v.IsClosedList()
   860  
   861  		default:
   862  			return v.Kind()&ListKind != 0
   863  		}
   864  	}
   865  
   866  	if k := v.Kind(); k&StructKind == 0 && f.IsString() {
   867  		// If the value is bottom, we may not really know if this used to
   868  		// be a struct.
   869  		if k != BottomKind || len(v.Structs) == 0 {
   870  			return false
   871  		}
   872  	}
   873  
   874  	if !v.IsClosedStruct() || v.Lookup(f) != nil {
   875  		return true
   876  	}
   877  
   878  	// TODO(perf): collect positions in error.
   879  	defer ctx.ReleasePositions(ctx.MarkPositions())
   880  
   881  	return v.accepts(Accept(ctx, v, f))
   882  }
   883  
   884  // MatchAndInsert finds the conjuncts for optional fields, pattern
   885  // constraints, and additional constraints that match f and inserts them in
   886  // arc. Use f is 0 to match all additional constraints only.
   887  func (v *Vertex) MatchAndInsert(ctx *OpContext, arc *Vertex) {
   888  	if !v.Accept(ctx, arc.Label) {
   889  		return
   890  	}
   891  
   892  	// Go backwards to simulate old implementation.
   893  	for i := len(v.Structs) - 1; i >= 0; i-- {
   894  		s := v.Structs[i]
   895  		if s.Disable {
   896  			continue
   897  		}
   898  		s.MatchAndInsert(ctx, arc)
   899  	}
   900  }
   901  
   902  func (v *Vertex) IsList() bool {
   903  	_, ok := v.BaseValue.(*ListMarker)
   904  	return ok
   905  }
   906  
   907  // Lookup returns the Arc with label f if it exists or nil otherwise.
   908  func (v *Vertex) Lookup(f Feature) *Vertex {
   909  	for _, a := range v.Arcs {
   910  		if a.Label == f {
   911  			a = a.Indirect()
   912  			return a
   913  		}
   914  	}
   915  	return nil
   916  }
   917  
   918  // Elems returns the regular elements of a list.
   919  func (v *Vertex) Elems() []*Vertex {
   920  	// TODO: add bookkeeping for where list arcs start and end.
   921  	a := make([]*Vertex, 0, len(v.Arcs))
   922  	for _, x := range v.Arcs {
   923  		if x.Label.IsInt() {
   924  			a = append(a, x)
   925  		}
   926  	}
   927  	return a
   928  }
   929  
   930  // GetArc returns a Vertex for the outgoing arc with label f. It creates and
   931  // ads one if it doesn't yet exist.
   932  func (v *Vertex) GetArc(c *OpContext, f Feature, t ArcType) (arc *Vertex, isNew bool) {
   933  	unreachableForDev(c)
   934  
   935  	arc = v.Lookup(f)
   936  	if arc != nil {
   937  		arc.updateArcType(t)
   938  		return arc, false
   939  	}
   940  
   941  	if v.LockArcs {
   942  		// TODO(errors): add positions.
   943  		if f.IsInt() {
   944  			c.addErrf(EvalError, token.NoPos,
   945  				"element at index %v not allowed by earlier comprehension or reference cycle", f)
   946  		} else {
   947  			c.addErrf(EvalError, token.NoPos,
   948  				"field %v not allowed by earlier comprehension or reference cycle", f)
   949  		}
   950  	}
   951  	// TODO: consider setting Dynamic here from parent.
   952  	arc = &Vertex{
   953  		Parent:    v,
   954  		Label:     f,
   955  		ArcType:   t,
   956  		nonRooted: v.IsDynamic || v.Label.IsLet() || v.nonRooted,
   957  	}
   958  	v.Arcs = append(v.Arcs, arc)
   959  	if t == ArcPending {
   960  		v.hasPendingArc = true
   961  	}
   962  	return arc, true
   963  }
   964  
   965  func (v *Vertex) Source() ast.Node {
   966  	if v != nil {
   967  		if b, ok := v.BaseValue.(Value); ok {
   968  			return b.Source()
   969  		}
   970  	}
   971  	return nil
   972  }
   973  
   974  // AddConjunct adds the given Conjuncts to v if it doesn't already exist.
   975  func (v *Vertex) AddConjunct(c Conjunct) *Bottom {
   976  	if v.BaseValue != nil && !isCyclePlaceholder(v.BaseValue) {
   977  		// TODO: investigate why this happens at all. Removing it seems to
   978  		// change the order of fields in some cases.
   979  		//
   980  		// This is likely a bug in the evaluator and should not happen.
   981  		return &Bottom{Err: errors.Newf(token.NoPos, "cannot add conjunct")}
   982  	}
   983  	if !v.hasConjunct(c) {
   984  		v.addConjunctUnchecked(c)
   985  	}
   986  	return nil
   987  }
   988  
   989  func (v *Vertex) hasConjunct(c Conjunct) (added bool) {
   990  	switch f := c.x.(type) {
   991  	case *BulkOptionalField, *Ellipsis:
   992  	case *Field:
   993  		v.updateArcType(f.ArcType)
   994  	case *DynamicField:
   995  		v.updateArcType(f.ArcType)
   996  	default:
   997  		v.ArcType = ArcMember
   998  	}
   999  	return hasConjunct(v.Conjuncts, c)
  1000  }
  1001  
  1002  func hasConjunct(cs []Conjunct, c Conjunct) bool {
  1003  	for _, x := range cs {
  1004  		// TODO: disregard certain fields from comparison (e.g. Refs)?
  1005  		if x.CloseInfo.closeInfo == c.CloseInfo.closeInfo &&
  1006  			x.x == c.x &&
  1007  			x.Env.Up == c.Env.Up && x.Env.Vertex == c.Env.Vertex {
  1008  			return true
  1009  		}
  1010  	}
  1011  	return false
  1012  }
  1013  
  1014  func (n *nodeContext) addConjunction(c Conjunct, index int) {
  1015  	unreachableForDev(n.ctx)
  1016  
  1017  	// NOTE: This does not split binary expressions for comprehensions.
  1018  	// TODO: split for comprehensions and rewrap?
  1019  	if x, ok := c.Elem().(*BinaryExpr); ok && x.Op == AndOp {
  1020  		c.x = x.X
  1021  		n.conjuncts = append(n.conjuncts, conjunct{C: c, index: index})
  1022  		c.x = x.Y
  1023  		n.conjuncts = append(n.conjuncts, conjunct{C: c, index: index})
  1024  	} else {
  1025  		n.conjuncts = append(n.conjuncts, conjunct{C: c, index: index})
  1026  	}
  1027  }
  1028  
  1029  func (v *Vertex) addConjunctUnchecked(c Conjunct) {
  1030  	index := len(v.Conjuncts)
  1031  	v.Conjuncts = append(v.Conjuncts, c)
  1032  	if n := v.state; n != nil && !n.ctx.isDevVersion() {
  1033  		n.addConjunction(c, index)
  1034  
  1035  		// TODO: can we remove notifyConjunct here? This method is only
  1036  		// used if either Unprocessed is 0, in which case there will be no
  1037  		// notification recipients, or for "pushed down" comprehensions,
  1038  		// which should also have been added at an earlier point.
  1039  		n.notifyConjunct(c)
  1040  	}
  1041  }
  1042  
  1043  // addConjunctDynamic adds a conjunct to a vertex and immediately evaluates
  1044  // it, whilst doing the same for any vertices on the notify list, recursively.
  1045  func (n *nodeContext) addConjunctDynamic(c Conjunct) {
  1046  	unreachableForDev(n.ctx)
  1047  
  1048  	n.node.Conjuncts = append(n.node.Conjuncts, c)
  1049  	n.addExprConjunct(c, partial)
  1050  	n.notifyConjunct(c)
  1051  
  1052  }
  1053  
  1054  func (n *nodeContext) notifyConjunct(c Conjunct) {
  1055  	unreachableForDev(n.ctx)
  1056  
  1057  	for _, rec := range n.notify {
  1058  		arc := rec.v
  1059  		if !arc.hasConjunct(c) {
  1060  			if arc.state == nil {
  1061  				// TODO: continuing here is likely to result in a faulty
  1062  				// (incomplete) configuration. But this may be okay. The
  1063  				// CUE_DEBUG=0 flag disables this assertion.
  1064  				n.ctx.Assertf(n.ctx.pos(), Debug, "unexpected nil state")
  1065  				n.ctx.addErrf(0, n.ctx.pos(), "cannot add to field %v", arc.Label)
  1066  				continue
  1067  			}
  1068  			arc.state.addConjunctDynamic(c)
  1069  		}
  1070  	}
  1071  }
  1072  
  1073  func (v *Vertex) AddStruct(s *StructLit, env *Environment, ci CloseInfo) *StructInfo {
  1074  	info := StructInfo{
  1075  		StructLit: s,
  1076  		Env:       env,
  1077  		CloseInfo: ci,
  1078  	}
  1079  	for _, t := range v.Structs {
  1080  		if *t == info { // TODO: check for different identity.
  1081  			return t
  1082  		}
  1083  	}
  1084  	t := &info
  1085  	v.Structs = append(v.Structs, t)
  1086  	return t
  1087  }
  1088  
  1089  // Path computes the sequence of Features leading from the root to of the
  1090  // instance to this Vertex.
  1091  //
  1092  // NOTE: this is for debugging purposes only.
  1093  func (v *Vertex) Path() []Feature {
  1094  	return appendPath(nil, v)
  1095  }
  1096  
  1097  func appendPath(a []Feature, v *Vertex) []Feature {
  1098  	if v.Parent == nil {
  1099  		return a
  1100  	}
  1101  	a = appendPath(a, v.Parent)
  1102  	if v.Label != 0 {
  1103  		// A Label may be 0 for programmatically inserted nodes.
  1104  		a = append(a, v.Label)
  1105  	}
  1106  	return a
  1107  }
  1108  
  1109  // An Conjunct is an Environment-Expr pair. The Environment is the starting
  1110  // point for reference lookup for any reference contained in X.
  1111  type Conjunct struct {
  1112  	Env *Environment
  1113  	x   Node
  1114  
  1115  	// CloseInfo is a unique number that tracks a group of conjuncts that need
  1116  	// belong to a single originating definition.
  1117  	CloseInfo CloseInfo
  1118  }
  1119  
  1120  // TODO(perf): replace with composite literal if this helps performance.
  1121  
  1122  // MakeRootConjunct creates a conjunct from the given environment and node.
  1123  // It panics if x cannot be used as an expression.
  1124  func MakeRootConjunct(env *Environment, x Node) Conjunct {
  1125  	return MakeConjunct(env, x, CloseInfo{})
  1126  }
  1127  
  1128  func MakeConjunct(env *Environment, x Node, id CloseInfo) Conjunct {
  1129  	if env == nil {
  1130  		// TODO: better is to pass one.
  1131  		env = &Environment{}
  1132  	}
  1133  	switch x.(type) {
  1134  	case Elem, interface{ expr() Expr }:
  1135  	default:
  1136  		panic(fmt.Sprintf("invalid Node type %T", x))
  1137  	}
  1138  	return Conjunct{env, x, id}
  1139  }
  1140  
  1141  func (c *Conjunct) Source() ast.Node {
  1142  	return c.x.Source()
  1143  }
  1144  
  1145  func (c *Conjunct) Field() Node {
  1146  	switch x := c.x.(type) {
  1147  	case *Comprehension:
  1148  		return x.Value
  1149  	default:
  1150  		return c.x
  1151  	}
  1152  }
  1153  
  1154  // Elem retrieves the Elem form of the contained conjunct.
  1155  // If it is a Field, it will return the field value.
  1156  func (c *Conjunct) Elem() Elem {
  1157  	switch x := c.x.(type) {
  1158  	case interface{ expr() Expr }:
  1159  		return x.expr()
  1160  	case Elem:
  1161  		return x
  1162  	default:
  1163  		panic("unreachable")
  1164  	}
  1165  }
  1166  
  1167  // Expr retrieves the expression form of the contained conjunct. If it is a
  1168  // field or comprehension, it will return its associated value. This is only to
  1169  // be used for syntactic operations where evaluation of the expression is not
  1170  // required. To get an expression paired with the correct environment, use
  1171  // EnvExpr.
  1172  //
  1173  // TODO: rename to RawExpr.
  1174  func (c *Conjunct) Expr() Expr {
  1175  	return ToExpr(c.x)
  1176  }
  1177  
  1178  // EnvExpr returns the expression form of the contained conjunct alongside an
  1179  // Environment in which this expression should be evaluated.
  1180  func (c Conjunct) EnvExpr() (*Environment, Expr) {
  1181  	return EnvExpr(c.Env, c.Elem())
  1182  }
  1183  
  1184  // EnvExpr returns the expression represented by Elem alongside an Environment
  1185  // with the necessary adjustments in which the resulting expression can be
  1186  // evaluated.
  1187  func EnvExpr(env *Environment, elem Elem) (*Environment, Expr) {
  1188  	for {
  1189  		if c, ok := elem.(*Comprehension); ok {
  1190  			env = linkChildren(env, c)
  1191  			c := MakeConjunct(env, c.Value, CloseInfo{})
  1192  			elem = c.Elem()
  1193  			continue
  1194  		}
  1195  		break
  1196  	}
  1197  	return env, ToExpr(elem)
  1198  }
  1199  
  1200  // ToExpr extracts the underlying expression for a Node. If something is already
  1201  // an Expr, it will return it as is, if it is a field, it will return its value,
  1202  // and for comprehensions it returns the yielded struct.
  1203  func ToExpr(n Node) Expr {
  1204  	switch x := n.(type) {
  1205  	case Expr:
  1206  		return x
  1207  	case interface{ expr() Expr }:
  1208  		return x.expr()
  1209  	case *Comprehension:
  1210  		return ToExpr(x.Value)
  1211  	default:
  1212  		panic("unreachable")
  1213  	}
  1214  }
  1215  

View as plain text