...

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

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

     1  // Copyright 2023 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  
    21  // This file holds the logic for the insertion of fields and pattern
    22  // constraints, including tracking closedness.
    23  //
    24  //
    25  // DESIGN GOALS
    26  //
    27  // Key to performance is to fail early during evaluation. This is especially
    28  // true for disjunctions. In CUE evaluation, conjuncts may be evaluated in a
    29  // fairly arbitrary order. We want to retain this flexibility while also failing
    30  // on disallowed fields as soon as we have enough data to tell for certain.
    31  //
    32  // Keeping track of which fields are allowed means keeping provenance data on
    33  // whether certain conjuncts originate from embeddings or definitions, as well
    34  // as how they group together with other conjuncts. These data structure should
    35  // allow for a "mark and unwind" approach to allow for backtracking when
    36  // computing disjunctions.
    37  //
    38  // References to the same CUE value may be added as conjuncts through various
    39  // paths. For instance, a reference to a definition may be added directly, or
    40  // through embedding. How they are added affects which set of fields are
    41  // allowed. This can make the removal of duplicate conjuncts hard. A solution
    42  // should make it straightforward to deduplicate conjuncts if they have the same
    43  // impact on field inclusion.
    44  //
    45  // All conjuncts associated with field constraints, including optional fields
    46  // and pattern constraints, should be collated, deduplicated, and evaluated as
    47  // if they were regular fields. This allows comparisons between values to be
    48  // meaningful and helps to filter disjuncts.
    49  //
    50  // The provenance data generated by this algorithm should ideally be easily
    51  // usable in external APIs.
    52  //
    53  //
    54  // DATA STRUCTURES
    55  //
    56  // Conjuncts
    57  //
    58  // To keep track of conjunct provenance, each conjunct has a few flags that
    59  // indicates whether it orignates from
    60  //   - an embedding
    61  //   - a definition
    62  //   - a reference (optional and unimplemented)
    63  //
    64  // Conjuncts with the same origin are represented as a single Conjunct in the
    65  // Vertex, where this conjunct is a list of these conjuncts. In other words, the
    66  // conjuncts of a Vertex are really a forest (group of trees) of conjuncts that,
    67  // recursively, reflect the provenance of the conjuncts contained within it.
    68  //
    69  // The current implementation uses a Vertex for listing conjuncts with the same
    70  // origin. This Vertex is marked as "Dynamic", as it does not have a CUE path
    71  // that leads to them.
    72  //
    73  //
    74  // Constraints
    75  //
    76  // Vertex values separately keep track of pattern constraints. These consist of
    77  // a list of patterns with associated conjuncts, and a CUE expression that
    78  // represents the set of allowed fields. This information is mostly for equality
    79  // checking: by the time this data is produced, conjuncts associated with
    80  // patterns are already inserted into the computed subfields.
    81  //
    82  // Note that this representation assumes that patterns are always accrued
    83  // cumulatively: a field that is allowed will accrue the conjuncts of any
    84  // matched pattern, even if it originates from an embedding that itself does not
    85  // allow this field.
    86  //
    87  //
    88  // ALGORITHM
    89  //
    90  // When processing the conjuncts of a Vertex, subfields are tracked per
    91  // "grouping" (the list of conjuncts of the same origin). Each grouping keeps a
    92  // counter of the number of unprocessed conjuncts and subgroups associated with
    93  // it. Field inclusion (closedness) can be computed as soon as all subconjuncts
    94  // and subgroups are processed.
    95  //
    96  // Conjuncts of subfields are inserted in such a way that they reflect the same
    97  // grouping as the parent Vertex, plus any grouping that may be added by the
    98  // subfield itself.
    99  //
   100  // It would be possible, though, to collapse certain (combinations of) groups
   101  // that contain only a single conjunct. This can limit the size of such conjunct
   102  // trees.
   103  //
   104  // As conjuncts are added within their grouping context, it is possible to
   105  // uniquely identify conjuncts only by Vertex and expression pointer,
   106  // disregarding the Environment.
   107  //
   108  //
   109  // EXAMPLE DATA STRUCTURE
   110  //
   111  //    a: #A
   112  //    #A: {
   113  //        #B
   114  //        x: r1
   115  //    }
   116  //    #B: y: r2
   117  //    r1: z: r3
   118  //    r2: 2
   119  //    r3: foo: 2
   120  //
   121  // gets evaluated into:
   122  //
   123  //    V_a: Arcs{
   124  //        x: V_x [ V_def(#A)[ r1 ] ]
   125  //        y: V_y [ V_def(#A)[ V_embed(#B)[ r2 ] ] ]
   126  //    }
   127  //
   128  // When evaluating V_x, its Arcs, in turn become:
   129  //
   130  //    V_x: Arcs{
   131  //        z: V_z [ V_def(#A)[ V_ref(r1)[ r3 ]) ]]
   132  //    }
   133  //
   134  // The V_def(#A) is necessary here to ensure that closedness information can be
   135  // computed, if necessary. The V_ref's, however, are optional, and can be
   136  // omitted if provenance is less important:
   137  //
   138  //    V_x: Arcs{
   139  //        z: V_z [ V_def(#A)[ r3 ]]
   140  //    }
   141  //
   142  // Another possible optimization is to eliminate Vertices if there is only one
   143  // conjunct: the embedding and definition flags in the conjunct can be
   144  // sufficient in that case. The provenance data could potentially be derived
   145  // from the Environment in that case. If an embedding conjunct is itself the
   146  // only conjunct in a list, the embedding bit can be eliminated. So V_y in the
   147  // above example could be reduced to
   148  //
   149  //    V_y [ V_def(#A)[ r2 ] ]
   150  //
   151  
   152  // TODO(perf):
   153  // - the data structures could probably be collapsed with Conjunct. and the
   154  //   Vertex inserted into the Conjuncts could be a special ConjunctGroup.
   155  
   156  type closeContext struct {
   157  	// Used to recursively insert Vertices.
   158  	parent *closeContext
   159  
   160  	dependencies []*ccDep // For testing only. See debug.go
   161  
   162  	// externalDeps lists the closeContexts associated with a root node for
   163  	// which there are outstanding decrements (can only be NOTIFY or ARC). This
   164  	// is used to break counter cycles, if necessary.
   165  	//
   166  	// This is only used for root closedContext and only for debugging.
   167  	// TODO: move to nodeContext.
   168  	externalDeps []ccArcRef
   169  
   170  	// child links to a sequence which additional patterns need to be verified
   171  	// against (&&). If there are more than one, these additional nodes are
   172  	// linked with next. Only closed nodes with patterns are added. Arc sets are
   173  	// already merged during processing.
   174  	child *closeContext
   175  
   176  	// next holds a linked list of nodes to process.
   177  	// See comments above and see linkPatterns.
   178  	next *closeContext
   179  
   180  	// if conjunctCount is 0, pattern constraints can be merged and the
   181  	// closedness can be checked. To ensure that this is true, there should
   182  	// be an additional increment at the start before any processing is done.
   183  	conjunctCount int
   184  
   185  	src *Vertex
   186  
   187  	// isDef indicates whether the closeContext is created as part of a
   188  	// definition.
   189  	isDef bool
   190  
   191  	// hasEllipsis indicates whether the node contains an ellipsis.
   192  	hasEllipsis bool
   193  
   194  	// hasTop indicates a node has at least one top conjunct.
   195  	hasTop bool
   196  
   197  	// hasNonTop indicates a node has at least one conjunct that is not top.
   198  	hasNonTop bool
   199  
   200  	// isClosedOnce is true if this closeContext is the result of calling the
   201  	// close builtin.
   202  	isClosedOnce bool
   203  
   204  	// isEmbed indicates whether the closeContext is created as part of an
   205  	// embedding.
   206  	isEmbed bool
   207  
   208  	// isClosed is true if a node is a def, it became closed because of a
   209  	// reference or if it is closed by the close builtin.
   210  	//
   211  	// isClosed must only be set to true if all fields and pattern constraints
   212  	// that define the domain of the node have been added.
   213  	isClosed bool
   214  
   215  	// isTotal is true if a node contains an ellipsis and is defined for all
   216  	// values.
   217  	isTotal bool
   218  
   219  	// done is true if all dependencies have been decremented.
   220  	done bool
   221  
   222  	// isDecremented is used to keep track of whether the evaluator decremented
   223  	// a closedContext for the ROOT depKind.
   224  	isDecremented bool
   225  
   226  	// needsCloseInSchedule is non-nil if a closeContext that was created
   227  	// as an arc still needs to be decremented. It points to the creating arc
   228  	// for reporting purposes.
   229  	needsCloseInSchedule *closeContext
   230  
   231  	// parentConjuncts represent the parent of this embedding or definition.
   232  	// Any closeContext is represented by a ConjunctGroup in parent of the
   233  	// expression tree.
   234  	parentConjuncts conjunctGrouper
   235  	// TODO: Only needed if more than one conjuncts.
   236  
   237  	// arcs represents closeContexts for sub fields and notification targets
   238  	// associated with this node that reflect the same point in the expression
   239  	// tree as this closeContext. In both cases the are keyed by Vertex.
   240  	arcs []ccArc
   241  
   242  	// parentIndex is the position in the parent's arcs slice that corresponds
   243  	// to this closeContext. This is currently unused. The intention is to use
   244  	// this to allow groups with single elements (which will be the majority)
   245  	// to be represented in place in the parent.
   246  	parentIndex int
   247  
   248  	group *ConjunctGroup
   249  
   250  	// Patterns contains all patterns of the current closeContext.
   251  	// It is used in the construction of Expr.
   252  	Patterns []Value
   253  
   254  	// Expr contains the Expr that is used for checking whether a Feature
   255  	// is allowed in this context. It is only complete after the full
   256  	// context has been completed, but it can be used for initial checking
   257  	// once isClosed is true.
   258  	Expr Value
   259  }
   260  
   261  // Label is a convenience function to return the label of the associated Vertex.
   262  func (c *closeContext) Label() Feature {
   263  	return c.src.Label
   264  }
   265  
   266  type ccArc struct {
   267  	kind        depKind
   268  	decremented bool
   269  	key         *closeContext
   270  	cc          *closeContext
   271  }
   272  
   273  // A ccArcRef x refers to the x.src.arcs[x.index].
   274  // We use this instead of pointers, because the address may change when
   275  // growing a slice. We use this instead mechanism instead of a pointers so
   276  // that we do not need to maintain separate free buffers once we use pools of
   277  // closeContext.
   278  type ccArcRef struct {
   279  	src   *closeContext
   280  	index int
   281  }
   282  
   283  type conjunctGrouper interface {
   284  	assignConjunct(root *closeContext, c Conjunct, check, checkClosed bool) (arc *closeContext, pos int, added bool)
   285  }
   286  
   287  func (n *nodeContext) getArc(f Feature, mode ArcType) (arc *Vertex, isNew bool) {
   288  	v := n.node
   289  	for _, a := range v.Arcs {
   290  		if a.Label == f {
   291  			if f.IsLet() {
   292  				a.MultiLet = true
   293  				// TODO: add return here?
   294  			}
   295  			a.updateArcType(mode)
   296  			return a, false
   297  		}
   298  	}
   299  
   300  	arc = &Vertex{
   301  		Parent:    v,
   302  		Label:     f,
   303  		ArcType:   mode,
   304  		nonRooted: v.IsDynamic || v.Label.IsLet() || v.nonRooted,
   305  	}
   306  	if n.scheduler.frozen&fieldSetKnown != 0 {
   307  		b := n.ctx.NewErrf("field %v not allowed by earlier comprehension or reference cycle", f)
   308  		n.ctx.AddBottom(b)
   309  		// This may panic for list arithmetic. Safer to leave out for now.
   310  		arc.ArcType = ArcNotPresent
   311  	}
   312  	v.Arcs = append(v.Arcs, arc)
   313  	return arc, true
   314  }
   315  
   316  func (v *Vertex) assignConjunct(root *closeContext, c Conjunct, check, checkClosed bool) (a *closeContext, pos int, added bool) {
   317  	// TODO: consider clearing CloseInfo.cc.
   318  	// c.CloseInfo.cc = nil
   319  
   320  	arc := root.src
   321  
   322  	pos = len(arc.Conjuncts)
   323  
   324  	added = !check || !arc.hasConjunct(c)
   325  	if added {
   326  		c.CloseInfo.cc = root
   327  		arc.addConjunctUnchecked(c)
   328  	}
   329  
   330  	return root, pos, added
   331  }
   332  
   333  func (cc *closeContext) getKeyedCC(key *closeContext, c CycleInfo, checkClosed bool) *closeContext {
   334  	for _, a := range cc.arcs {
   335  		if a.key == key {
   336  			return a.cc
   337  		}
   338  	}
   339  
   340  	group := &ConjunctGroup{}
   341  
   342  	if cc.parentConjuncts == cc {
   343  		panic("parent is self")
   344  	}
   345  
   346  	parent, pos, _ := cc.parentConjuncts.assignConjunct(key, Conjunct{
   347  		CloseInfo: CloseInfo{
   348  			FromDef:   cc.isDef,
   349  			FromEmbed: cc.isEmbed,
   350  			CycleInfo: c,
   351  		},
   352  		x: group,
   353  	}, false, checkClosed)
   354  
   355  	arc := &closeContext{
   356  		parent:          parent,
   357  		parentConjuncts: parent,
   358  		parentIndex:     pos,
   359  
   360  		src:   key.src,
   361  		group: group,
   362  
   363  		isDef:                cc.isDef,
   364  		isEmbed:              cc.isEmbed,
   365  		needsCloseInSchedule: cc,
   366  	}
   367  
   368  	arc.parent.incDependent(PARENT, arc)
   369  
   370  	// If the parent, w.r.t. the subfield relation was already processed,
   371  	// there is no need to register the notification.
   372  	arc.incDependent(EVAL, cc) // matched in REF(decrement:nodeDone)
   373  
   374  	// A let field never depends on its parent. So it is okay to filter here.
   375  	if !arc.Label().IsLet() {
   376  		// prevent a dependency on self.
   377  		if key.src != cc.src {
   378  			cc.addDependency(ARC, key, arc, key)
   379  		}
   380  	}
   381  
   382  	v := key.src
   383  	if checkClosed && v.Parent != nil && v.Parent.state != nil {
   384  		v.Parent.state.checkArc(cc, v)
   385  	}
   386  
   387  	return arc
   388  }
   389  
   390  func (cc *closeContext) linkNotify(dst *Vertex, key *closeContext, c CycleInfo) bool {
   391  	for _, a := range cc.arcs {
   392  		if a.key == key {
   393  			return false
   394  		}
   395  	}
   396  
   397  	cc.addDependency(NOTIFY, key, key, dst.cc)
   398  	return true
   399  }
   400  
   401  func (cc *closeContext) assignConjunct(root *closeContext, c Conjunct, check, checkClosed bool) (arc *closeContext, pos int, added bool) {
   402  	arc = cc.getKeyedCC(root, c.CloseInfo.CycleInfo, checkClosed)
   403  
   404  	pos = len(*arc.group)
   405  
   406  	c.CloseInfo.cc = nil
   407  	added = !check || !hasConjunct(*arc.group, c)
   408  	if added {
   409  		c.CloseInfo.cc = arc
   410  
   411  		if c.CloseInfo.cc.src != arc.src {
   412  			panic("Inconsistent src")
   413  		}
   414  		*arc.group = append(*arc.group, c)
   415  	}
   416  
   417  	return arc, pos, added
   418  }
   419  
   420  // spawnCloseContext wraps the closeContext in c with a new one and returns
   421  // this new context along with an updated CloseInfo. The new values reflect
   422  // that the set of fields represented by c are now, for instance, enclosed in
   423  // an embedding or a definition.
   424  //
   425  // This call is used when preparing ADT values for evaluation.
   426  func (c CloseInfo) spawnCloseContext(t closeNodeType) (CloseInfo, *closeContext) {
   427  	cc := c.cc
   428  	if cc == nil {
   429  		panic("nil closeContext")
   430  	}
   431  
   432  	c.cc = &closeContext{
   433  		parent:          cc,
   434  		src:             cc.src,
   435  		parentConjuncts: cc,
   436  	}
   437  
   438  	cc.incDependent(PARENT, c.cc) // REF(decrement: spawn)
   439  
   440  	switch t {
   441  	case closeDef:
   442  		c.cc.isDef = true
   443  	case closeEmbed:
   444  		c.cc.isEmbed = true
   445  	}
   446  
   447  	return c, c.cc
   448  }
   449  
   450  // addDependency adds a dependent arc to c. If child is an arc, child.src == key
   451  func (c *closeContext) addDependency(kind depKind, key, child, root *closeContext) {
   452  	// NOTE: do not increment
   453  	// - either root closeContext or otherwise resulting from sub closeContext
   454  	//   all conjuncts will be added now, notified, or scheduled as task.
   455  
   456  	child.incDependent(kind, c) // matched in decDependent REF(arcs)
   457  
   458  	for _, a := range c.arcs {
   459  		if a.key == key {
   460  			panic("addArc: Label already exists")
   461  		}
   462  	}
   463  
   464  	// TODO: this tests seems sensible, but panics. Investigate what could
   465  	// trigger this.
   466  	// if child.src.Parent != c.src {
   467  	// 	panic("addArc: inconsistent parent")
   468  	// }
   469  	if child.src.cc != root.src.cc {
   470  		panic("addArc: inconsistent root")
   471  	}
   472  	c.arcs = append(c.arcs, ccArc{
   473  		kind: kind,
   474  		key:  key,
   475  		cc:   child,
   476  	})
   477  	root.externalDeps = append(root.externalDeps, ccArcRef{
   478  		src:   c,
   479  		index: len(c.arcs) - 1,
   480  	})
   481  }
   482  
   483  // incDependent needs to be called for any conjunct or child closeContext
   484  // scheduled for c that is queued for later processing and not scheduled
   485  // immediately.
   486  func (c *closeContext) incDependent(kind depKind, dependant *closeContext) (debug *ccDep) {
   487  	if c.src == nil {
   488  		panic("incDependent: unexpected nil state")
   489  	}
   490  
   491  	debug = c.addDependent(kind, dependant)
   492  
   493  	if c.done {
   494  		ctx := c.src.state.ctx
   495  		openDebugGraph(ctx, c.src, "incDependent: already checked")
   496  
   497  		panic(fmt.Sprintf("incDependent: already closed: %p", c))
   498  	}
   499  
   500  	c.conjunctCount++
   501  	return debug
   502  }
   503  
   504  // decDependent needs to be called for any conjunct or child closeContext for
   505  // which a corresponding incDependent was called after it has been successfully
   506  // processed.
   507  func (c *closeContext) decDependent(ctx *OpContext, kind depKind, dependant *closeContext) {
   508  	v := c.src
   509  
   510  	c.matchDecrement(v, kind, dependant)
   511  
   512  	if c.conjunctCount == 0 {
   513  		panic(fmt.Sprintf("negative reference counter %d %p", c.conjunctCount, c))
   514  	}
   515  
   516  	c.conjunctCount--
   517  	if c.conjunctCount > 0 {
   518  		return
   519  	}
   520  
   521  	c.done = true
   522  
   523  	p := c.parent
   524  
   525  	if c.isDef && !c.hasEllipsis && (!c.hasTop || c.hasNonTop) {
   526  		c.isClosed = true
   527  		if p != nil {
   528  			p.isDef = true
   529  		}
   530  	}
   531  
   532  	if c.isClosedOnce {
   533  		c.isClosed = true
   534  		if p != nil {
   535  			p.isClosedOnce = true
   536  		}
   537  	}
   538  
   539  	for i, a := range c.arcs {
   540  		cc := a.cc
   541  		if a.decremented {
   542  			continue
   543  		}
   544  		c.arcs[i].decremented = true
   545  		cc.decDependent(ctx, a.kind, c) // REF(arcs)
   546  	}
   547  
   548  	c.finalizePattern()
   549  
   550  	if p == nil {
   551  		// Root pattern, set allowed patterns.
   552  		if pcs := v.PatternConstraints; pcs != nil {
   553  			if pcs.Allowed != nil {
   554  				panic("unexpected allowed set")
   555  			}
   556  			pcs.Allowed = c.Expr
   557  			return
   558  		}
   559  		return
   560  	}
   561  
   562  	if c.hasEllipsis {
   563  		p.hasEllipsis = true
   564  	}
   565  	if c.hasTop {
   566  		p.hasTop = true
   567  	}
   568  	if c.hasNonTop {
   569  		p.hasNonTop = true
   570  	}
   571  
   572  	if !c.isEmbed && c.isClosed {
   573  		// Merge the two closeContexts and ensure that the patterns and fields
   574  		// are mutually compatible according to the closedness rules.
   575  		injectClosed(ctx, c, p)
   576  		p.Expr = mergeConjunctions(p.Expr, c.Expr)
   577  	} else {
   578  		// Do not check closedness of fields for embeddings.
   579  		// The pattern constraints of the embedding still need to be added
   580  		// to the current context.
   581  		p.linkPatterns(c)
   582  	}
   583  
   584  	p.decDependent(ctx, PARENT, c) // REF(decrement: spawn)
   585  
   586  	// If we have started decrementing a child closeContext, the parent started
   587  	// as well. If it is still marked as needing an EVAL decrement, which can
   588  	// happen if processing started before the node was added, it is safe to
   589  	// decrement it now. In this case the NOTIFY and ARC dependencies will keep
   590  	// the nodes alive until they can be completed.
   591  	if dep := p.needsCloseInSchedule; dep != nil {
   592  		p.needsCloseInSchedule = nil
   593  		p.decDependent(ctx, EVAL, dep)
   594  	}
   595  }
   596  
   597  // linkPatterns merges the patterns of child into c, if needed.
   598  func (c *closeContext) linkPatterns(child *closeContext) {
   599  	if len(child.Patterns) > 0 {
   600  		child.next = c.child
   601  		c.child = child
   602  	}
   603  }
   604  
   605  // checkArc validates that the node corresponding to cc allows a field with
   606  // label v.Label.
   607  func (n *nodeContext) checkArc(cc *closeContext, v *Vertex) *Vertex {
   608  	f := v.Label
   609  	ctx := n.ctx
   610  
   611  	if f.IsHidden() || f.IsLet() {
   612  		return v
   613  	}
   614  
   615  	if cc.isClosed && !matchPattern(ctx, cc.Expr, f) {
   616  		ctx.notAllowedError(n.node, v)
   617  	}
   618  	if n.scheduler.frozen&fieldSetKnown != 0 {
   619  		for _, a := range n.node.Arcs {
   620  			if a.Label == f {
   621  				return v
   622  			}
   623  		}
   624  		var b *Bottom
   625  		// TODO: include cycle data and improve error message.
   626  		if f.IsInt() {
   627  			b = ctx.NewErrf(
   628  				"element at index %v not allowed by earlier comprehension or reference cycle", f)
   629  		} else {
   630  			b = ctx.NewErrf(
   631  				"field %v not allowed by earlier comprehension or reference cycle", f)
   632  		}
   633  		v.SetValue(ctx, b)
   634  	}
   635  
   636  	return v
   637  }
   638  
   639  // insertConjunct inserts conjunct c into cc.
   640  func (cc *closeContext) insertConjunct(key *closeContext, c Conjunct, id CloseInfo, check, checkClosed bool) bool {
   641  	arc, _, added := cc.assignConjunct(key, c, check, checkClosed)
   642  	if key.src != arc.src {
   643  		panic("inconsistent src")
   644  	}
   645  
   646  	if !added {
   647  		return false
   648  	}
   649  
   650  	if n := key.src.state; n != nil {
   651  		c.CloseInfo.cc = nil
   652  		id.cc = arc
   653  		n.scheduleConjunct(c, id)
   654  
   655  		for _, rec := range n.notify {
   656  			if n.node.ArcType == ArcPending {
   657  				panic("unexpected pending arc")
   658  			}
   659  			cc.insertConjunct(rec.cc, c, id, check, checkClosed)
   660  		}
   661  	}
   662  
   663  	return true
   664  }
   665  
   666  // insertArc inserts conjunct c into n. If check is true it will not add c if it
   667  // was already added.
   668  // Returns the arc of n.node with label f.
   669  func (n *nodeContext) insertArc(f Feature, mode ArcType, c Conjunct, id CloseInfo, check bool) *Vertex {
   670  	if n == nil {
   671  		panic("nil nodeContext")
   672  	}
   673  	if n.node == nil {
   674  		panic("nil node")
   675  	}
   676  	cc := id.cc
   677  	if cc == nil {
   678  		panic("nil closeContext")
   679  	}
   680  
   681  	v, insertedArc := n.getArc(f, mode)
   682  
   683  	if v.ArcType == ArcNotPresent {
   684  		n.node.reportFieldCycleError(n.ctx, c.Source().Pos(), f)
   685  		return v
   686  	}
   687  
   688  	if !cc.insertConjunct(v.rootCloseContext(), c, id, check, true) {
   689  		return v
   690  	}
   691  
   692  	if !insertedArc {
   693  		return v
   694  	}
   695  
   696  	// Match and insert patterns.
   697  	if pcs := n.node.PatternConstraints; pcs != nil {
   698  		for _, pc := range pcs.Pairs {
   699  			if matchPattern(n.ctx, pc.Pattern, f) {
   700  				for _, c := range pc.Constraint.Conjuncts {
   701  					n.addConstraint(v, mode, c, check)
   702  				}
   703  			}
   704  		}
   705  	}
   706  
   707  	return v
   708  }
   709  
   710  // addConstraint adds a constraint to arc of n.
   711  //
   712  // In order to resolve LabelReferences, it is not always possible to walk up
   713  // the parent Vertex chain to determan the label, because a label reference
   714  // may point past a point of referral. For instance,
   715  //
   716  //	test: [ID=_]: name: ID
   717  //	test: A: {}
   718  //	B: test.A & {}  // B.name should be "A", not "B".
   719  //
   720  // The arc must be the node arc to which the conjunct is added.
   721  func (n *nodeContext) addConstraint(arc *Vertex, mode ArcType, c Conjunct, check bool) {
   722  	// TODO(perf): avoid cloning the Environment, if:
   723  	// - the pattern constraint has no LabelReference
   724  	//   (require compile-time support)
   725  	// - there are no references in the conjunct pointing to this node.
   726  	// - consider adding this value to the Conjunct struct
   727  	f := arc.Label
   728  	bulkEnv := *c.Env
   729  	bulkEnv.DynamicLabel = f
   730  	c.Env = &bulkEnv
   731  
   732  	// TODO(constraintNode): this should ideally be
   733  	//    cc := id.cc
   734  	// or
   735  	//    cc := c.CloseInfo.cc.src.cc
   736  	//
   737  	// Where id is the closeContext corresponding to the field, or the root
   738  	// context. But it is a bit hard to figure out how to account for this, as
   739  	// either this information is not available or the root context results in
   740  	// errors for the other use of addConstraint. For this reason, we keep
   741  	// things symmetric for now and will keep things as is, just avoiding the
   742  	// closedness check.
   743  	cc := c.CloseInfo.cc
   744  
   745  	arc, _ = n.getArc(f, mode)
   746  
   747  	root := arc.rootCloseContext()
   748  	cc.insertConjunct(root, c, c.CloseInfo, check, false)
   749  }
   750  
   751  func (n *nodeContext) insertPattern(pattern Value, c Conjunct) {
   752  	ctx := n.ctx
   753  	cc := c.CloseInfo.cc
   754  
   755  	// Collect patterns in root vertex. This allows comparing disjuncts for
   756  	// equality as well as inserting new arcs down the line as they are
   757  	// inserted.
   758  	if !n.insertConstraint(pattern, c) {
   759  		return
   760  	}
   761  
   762  	// Match against full set of arcs from root, but insert in current vertex.
   763  	// Hypothesis: this may not be necessary. Maybe for closedness.
   764  	// TODO: may need to replicate the closedContext for patterns.
   765  	// Also: Conjuncts for matching other arcs in this node may be different
   766  	// for matching arcs using v.foo?, if we need to ensure that conjuncts
   767  	// from arcs and patterns are grouped under the same vertex.
   768  	// TODO: verify. See test Pattern 1b
   769  	for _, a := range n.node.Arcs {
   770  		if matchPattern(n.ctx, pattern, a.Label) {
   771  			// TODO: is it necessary to check for uniqueness here?
   772  			n.addConstraint(a, a.ArcType, c, true)
   773  		}
   774  	}
   775  
   776  	if cc.isTotal {
   777  		return
   778  	}
   779  	if isTotal(pattern) {
   780  		cc.isTotal = true
   781  		cc.Patterns = cc.Patterns[:0]
   782  		return
   783  	}
   784  
   785  	// insert pattern in current set.
   786  	// TODO: normalize patterns
   787  	// TODO: do we only need to do this for closed contexts?
   788  	for _, pc := range cc.Patterns {
   789  		if Equal(ctx, pc, pattern, 0) {
   790  			return
   791  		}
   792  	}
   793  	cc.Patterns = append(cc.Patterns, pattern)
   794  }
   795  
   796  // isTotal reports whether pattern value p represents a full domain, that is,
   797  // whether it is of type BasicType or Top.
   798  func isTotal(p Value) bool {
   799  	switch p.(type) {
   800  	case *BasicType:
   801  		return true
   802  	case *Top:
   803  		return true
   804  	}
   805  	return false
   806  }
   807  
   808  // injectClosed updates dst so that it only allows fields allowed by closed.
   809  //
   810  // It first ensures that the fields contained in dst are allowed by the fields
   811  // and patterns defined in closed. It reports an error in the nodeContext if
   812  // this is not the case.
   813  func injectClosed(ctx *OpContext, closed, dst *closeContext) {
   814  	// TODO: check that fields are not void arcs.
   815  outer:
   816  	for _, a := range dst.arcs {
   817  		ca := a.cc
   818  		f := ca.Label()
   819  		if f.IsHidden() || f.IsLet() {
   820  			continue
   821  		}
   822  		for _, b := range closed.arcs {
   823  			cb := b.cc
   824  			if f == cb.Label() {
   825  				continue outer
   826  			}
   827  		}
   828  		if !matchPattern(ctx, closed.Expr, ca.Label()) {
   829  			ctx.notAllowedError(closed.src, ca.src)
   830  			continue
   831  		}
   832  	}
   833  
   834  	if !dst.isClosed {
   835  		// Since dst is not closed, it is safe to take all patterns from
   836  		// closed.
   837  		// This is only necessary for passing up patterns into embeddings. For
   838  		// (the conjunction of) definitions the construction is handled
   839  		// elsewhere.
   840  		// TODO(perf): reclaim slice memory
   841  		dst.Patterns = closed.Patterns
   842  
   843  		dst.isClosed = true
   844  	}
   845  }
   846  
   847  func (ctx *OpContext) addPositions(c Conjunct) {
   848  	if x, ok := c.x.(*ConjunctGroup); ok {
   849  		for _, c := range *x {
   850  			ctx.addPositions(c)
   851  		}
   852  	}
   853  	if pos := c.Field(); pos != nil {
   854  		ctx.AddPosition(pos)
   855  	}
   856  }
   857  
   858  // notAllowedError reports a field not allowed error in n and sets the value
   859  // for arc f to that error.
   860  func (ctx *OpContext) notAllowedError(v, arc *Vertex) {
   861  	defer ctx.PopArc(ctx.PushArc(arc))
   862  
   863  	defer ctx.ReleasePositions(ctx.MarkPositions())
   864  
   865  	for _, c := range arc.Conjuncts {
   866  		ctx.addPositions(c)
   867  	}
   868  	// XXX(0.7): Find another way to get this provenance information. Not
   869  	// currently stored in new evaluator.
   870  	// for _, s := range x.Structs {
   871  	//  s.AddPositions(ctx)
   872  	// }
   873  
   874  	if arc.ArcType == ArcPending {
   875  		arc.ArcType = ArcNotPresent
   876  		return
   877  	}
   878  	// TODO: setting arc instead of n.node eliminates subfields. This may be
   879  	// desirable or not, but it differs, at least from <=v0.6 behavior.
   880  	arc.SetValue(ctx, ctx.NewErrf("field not allowed"))
   881  
   882  	// TODO: remove? We are now setting it on both fields, which seems to be
   883  	// necessary for now. But we should remove this as it often results in
   884  	// a duplicate error.
   885  	// v.SetValue(ctx, ctx.NewErrf("field not allowed"))
   886  
   887  	// TODO: create a special kind of error that gets the positions
   888  	// of the relevant locations upon request from the arc.
   889  }
   890  
   891  // mergeConjunctions combines two values into one. It never modifies an
   892  // existing conjunction.
   893  func mergeConjunctions(a, b Value) Value {
   894  	if a == nil {
   895  		return b
   896  	}
   897  	if b == nil {
   898  		return a
   899  	}
   900  	ca, _ := a.(*Conjunction)
   901  	cb, _ := b.(*Conjunction)
   902  	n := 2
   903  	if ca != nil {
   904  		n += len(ca.Values) - 1
   905  	}
   906  	if cb != nil {
   907  		n += len(cb.Values) - 1
   908  	}
   909  	vs := make([]Value, 0, n)
   910  	if ca != nil {
   911  		vs = append(vs, ca.Values...)
   912  	} else {
   913  		vs = append(vs, a)
   914  	}
   915  	if cb != nil {
   916  		vs = append(vs, cb.Values...)
   917  	} else {
   918  		vs = append(vs, b)
   919  	}
   920  	// TODO: potentially order conjuncts to make matching more likely.
   921  	return &Conjunction{Values: vs}
   922  }
   923  
   924  // finalizePattern updates c.Expr to a CUE Value representing all fields allowed
   925  // by the pattern constraints of c. If this context or any of its direct
   926  // children is closed, the result will be a conjunction of all these closed
   927  // values. Otherwise it will be a disjunction of all its children. A nil value
   928  // represents all values.
   929  func (c *closeContext) finalizePattern() {
   930  	switch {
   931  	case c.Expr != nil: // Patterns and expression are already set.
   932  		if !c.isClosed {
   933  			panic("c.Expr set unexpectedly")
   934  		}
   935  		return
   936  	case c.isTotal: // All values are allowed always.
   937  		return
   938  	}
   939  
   940  	// As this context is not closed, the pattern is somewhat meaningless.
   941  	// It may still be useful for analysis.
   942  	or := c.Patterns
   943  
   944  	for cc := c.child; cc != nil; cc = cc.next {
   945  		if cc.isTotal {
   946  			return
   947  		}
   948  		// Could be closed, in which case it must also be an embedding.
   949  
   950  		// TODO: simplify the values.
   951  		switch x := cc.Expr.(type) {
   952  		case nil:
   953  		case *Disjunction:
   954  			or = append(or, x.Values...)
   955  		default:
   956  			or = append(or, x)
   957  		}
   958  	}
   959  
   960  	switch len(or) {
   961  	case 0:
   962  	case 1:
   963  		c.Expr = or[0]
   964  	default:
   965  		// TODO: potentially order conjuncts to make matching more likely.
   966  		c.Expr = &Disjunction{Values: or}
   967  	}
   968  }
   969  

View as plain text