conjunct.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 "fmt"
    18  
    19  // This file contains functionality for processing conjuncts to insert the
    20  // corresponding values in the Vertex.
    21  //
    22  // Conjuncts are divided into two classes:
    23  // - literal values that need no evaluation: these are inserted directly into
    24  //   the Vertex.
    25  // - field or value expressions that need to be evaluated: these are inserted
    26  //   as a task into the Vertex' associated scheduler for later evaluation.
    27  //   The implementation of these tasks can be found in tasks.go.
    28  //
    29  // The main entrypoint is scheduleConjunct.
    30  
    31  // scheduleConjunct splits c into parts to be incrementally processed and queues
    32  // these parts up for processing. it will itself not cause recursive processing.
    33  func (n *nodeContext) scheduleConjunct(c Conjunct, id CloseInfo) {
    34  	// Explanation of switch statement:
    35  	//
    36  	// A Conjunct can be a leaf or, through a ConjunctGroup, a tree. The tree
    37  	// reflects the history of how the conjunct was inserted in terms of
    38  	// definitions and embeddings. This, in turn, is used to compute closedness.
    39  	//
    40  	// Once all conjuncts for a Vertex have been collected, this tree contains
    41  	// all the information needed to trace its histroy: if a Vertex is
    42  	// referenced in an expression, this tree can be used to insert the
    43  	// conjuncts keeping closedness in mind.
    44  	//
    45  	// In the collection phase, however, this is not sufficient. CUE computes
    46  	// conjuncts "out of band". This means that conjuncts accumulate in
    47  	// different parts of the tree in an indeterminate order. closeContext is
    48  	// used to account for this.
    49  	//
    50  	// Basically, if the closeContext associated with c belongs to n, we take
    51  	// it that the conjunct needs to be inserted at the point in the tree
    52  	// associated by this closeContext. If, on the other hand, the closeContext
    53  	// is not defined or does not belong to this node, we take this conjunct
    54  	// is inserted by means of a reference. In this case we assume that the
    55  	// computation of the tree has completed and the tree can be used to reflect
    56  	// the closedness structure.
    57  	//
    58  	// TODO: once the evaluator is done and all tests pass, consider having
    59  	// two different entry points to account for these cases.
    60  	switch cc := c.CloseInfo.cc; {
    61  	case cc == nil || cc.src != n.node:
    62  		// In this case, a Conjunct is inserted from another Arc. If the
    63  		// conjunct represents an embedding or definition, we need to create a
    64  		// new closeContext to represent this.
    65  		if id.cc == nil {
    66  			id.cc = n.node.rootCloseContext()
    67  		}
    68  		if id.cc == cc {
    69  			panic("inconsistent state")
    70  		}
    71  		var t closeNodeType
    72  		if c.CloseInfo.FromDef {
    73  			t |= closeDef
    74  		}
    75  		if c.CloseInfo.FromEmbed {
    76  			t |= closeEmbed
    77  		}
    78  		if t != 0 {
    79  			id, _ = id.spawnCloseContext(t)
    80  		}
    81  		if !id.cc.done {
    82  			id.cc.incDependent(DEFER, nil)
    83  			defer id.cc.decDependent(n.ctx, DEFER, nil)
    84  		}
    85  
    86  		if id.cc.src != n.node {
    87  			panic("inconsistent state")
    88  		}
    89  	default:
    90  
    91  		// In this case, the conjunct is inserted as the result of an expansion
    92  		// of a conjunct in place, not a reference. In this case, we must use
    93  		// the cached closeContext.
    94  		id.cc = cc
    95  
    96  		// Note this subtlety: we MUST take the cycle info from c when this is
    97  		// an in place evaluated node, otherwise we must take that of id.
    98  		id.CycleInfo = c.CloseInfo.CycleInfo
    99  	}
   100  
   101  	if id.cc.needsCloseInSchedule != nil {
   102  		dep := id.cc.needsCloseInSchedule
   103  		id.cc.needsCloseInSchedule = nil
   104  		defer id.cc.decDependent(n.ctx, EVAL, dep)
   105  	}
   106  
   107  	env := c.Env
   108  
   109  	if id.cc.isDef {
   110  		n.node.Closed = true
   111  	}
   112  
   113  	switch x := c.Elem().(type) {
   114  	case *ConjunctGroup:
   115  		for _, c := range *x {
   116  			// TODO(perf): can be one loop
   117  
   118  			cc := c.CloseInfo.cc
   119  			if cc.src == n.node && cc.needsCloseInSchedule != nil {
   120  				// We need to handle this specifically within the ConjunctGroup
   121  				// loop, because multiple conjuncts may be using the same root
   122  				// closeContext. This can be merged once Vertex.Conjuncts is an
   123  				// interface, requiring any list to be a root conjunct.
   124  
   125  				dep := cc.needsCloseInSchedule
   126  				cc.needsCloseInSchedule = nil
   127  				defer cc.decDependent(n.ctx, EVAL, dep)
   128  			}
   129  		}
   130  		for _, c := range *x {
   131  			n.scheduleConjunct(c, id)
   132  		}
   133  
   134  	case *Vertex:
   135  		if x.IsData() {
   136  			n.insertValueConjunct(env, x, id)
   137  		} else {
   138  			n.scheduleVertexConjuncts(c, x, id)
   139  		}
   140  
   141  	case Value:
   142  		n.insertValueConjunct(env, x, id)
   143  
   144  	case *BinaryExpr:
   145  		if x.Op == AndOp {
   146  			n.scheduleConjunct(MakeConjunct(env, x.X, id), id)
   147  			n.scheduleConjunct(MakeConjunct(env, x.Y, id), id)
   148  			return
   149  		}
   150  		// Even though disjunctions and conjunctions are excluded, the result
   151  		// must may still be list in the case of list arithmetic. This could
   152  		// be a scalar value only once this is no longer supported.
   153  		n.scheduleTask(handleExpr, env, x, id)
   154  
   155  	case *StructLit:
   156  		n.scheduleStruct(env, x, id)
   157  
   158  	case *ListLit:
   159  		env := &Environment{
   160  			Up:     env,
   161  			Vertex: n.node,
   162  		}
   163  		n.scheduleTask(handleListLit, env, x, id)
   164  
   165  	case *DisjunctionExpr:
   166  		panic("unimplemented")
   167  		// n.addDisjunction(env, x, id)
   168  
   169  	case *Comprehension:
   170  		// always a partial comprehension.
   171  		n.insertComprehension(env, x, id)
   172  
   173  	case Resolver:
   174  		n.scheduleTask(handleResolver, env, x, id)
   175  
   176  	case Evaluator:
   177  		// Interpolation, UnaryExpr, CallExpr
   178  		n.scheduleTask(handleExpr, env, x, id)
   179  
   180  	default:
   181  		panic("unreachable")
   182  	}
   183  
   184  	n.ctx.stats.Conjuncts++
   185  }
   186  
   187  // scheduleStruct records all elements of this conjunct in the structure and
   188  // then processes it. If an element needs to be inserted for evaluation,
   189  // it may be scheduled.
   190  func (n *nodeContext) scheduleStruct(env *Environment,
   191  	s *StructLit,
   192  	ci CloseInfo) {
   193  	n.updateCyclicStatus(ci)
   194  
   195  	// NOTE: This is a crucial point in the code:
   196  	// Unification dereferencing happens here. The child nodes are set to
   197  	// an Environment linked to the current node. Together with the De Bruijn
   198  	// indices, this determines to which Vertex a reference resolves.
   199  
   200  	childEnv := &Environment{
   201  		Up:     env,
   202  		Vertex: n.node,
   203  	}
   204  
   205  	hasEmbed := false
   206  	hasEllipsis := false
   207  
   208  	// shouldClose := ci.cc.isDef || ci.cc.isClosedOnce
   209  	// s.Init()
   210  
   211  	// TODO: do we still need to AddStruct and do we still need to Disable?
   212  	parent := n.node.AddStruct(s, childEnv, ci)
   213  	parent.Disable = true // disable until processing is done.
   214  	ci.IsClosed = false
   215  
   216  	// TODO: precompile
   217  loop1:
   218  	for _, d := range s.Decls {
   219  		switch d.(type) {
   220  		case *Ellipsis:
   221  			hasEllipsis = true
   222  			break loop1
   223  		}
   224  	}
   225  
   226  	// TODO(perf): precompile whether struct has embedding.
   227  loop2:
   228  	for _, d := range s.Decls {
   229  		switch d.(type) {
   230  		case *Comprehension, Expr:
   231  			// No need to increment and decrement, as there will be at least
   232  			// one entry.
   233  			ci, _ = ci.spawnCloseContext(0)
   234  			// Note: adding a count is not needed here, as there will be an
   235  			// embed spawn below.
   236  			hasEmbed = true
   237  			break loop2
   238  		}
   239  	}
   240  
   241  	// First add fixed fields and schedule expressions.
   242  	for _, d := range s.Decls {
   243  		switch x := d.(type) {
   244  		case *Field:
   245  			if x.Label.IsString() && x.ArcType == ArcMember {
   246  				n.aStruct = s
   247  				n.aStructID = ci
   248  			}
   249  			fc := MakeConjunct(childEnv, x, ci)
   250  			// fc.CloseInfo.cc = nil // TODO: should we add this?
   251  			n.insertArc(x.Label, x.ArcType, fc, ci, true)
   252  
   253  		case *LetField:
   254  			lc := MakeConjunct(childEnv, x, ci)
   255  			n.insertArc(x.Label, ArcMember, lc, ci, true)
   256  
   257  		case *Comprehension:
   258  			ci, cc := ci.spawnCloseContext(closeEmbed)
   259  			cc.incDependent(DEFER, nil)
   260  			defer cc.decDependent(n.ctx, DEFER, nil)
   261  			n.insertComprehension(childEnv, x, ci)
   262  			hasEmbed = true
   263  
   264  		case *Ellipsis:
   265  			// Can be added unconditionally to patterns.
   266  			ci.cc.isDef = false
   267  			ci.cc.isClosed = false
   268  
   269  		case *DynamicField:
   270  			if x.ArcType == ArcMember {
   271  				n.aStruct = s
   272  				n.aStructID = ci
   273  			}
   274  			n.scheduleTask(handleDynamic, childEnv, x, ci)
   275  
   276  		case *BulkOptionalField:
   277  
   278  			// All do not depend on each other, so can be added at once.
   279  			n.scheduleTask(handlePatternConstraint, childEnv, x, ci)
   280  
   281  		case Expr:
   282  			// TODO: perhaps special case scalar Values to avoid creating embedding.
   283  			ci, cc := ci.spawnCloseContext(closeEmbed)
   284  
   285  			// TODO: do we need to increment here?
   286  			cc.incDependent(DEFER, nil) // decrement deferred below
   287  			defer cc.decDependent(n.ctx, DEFER, nil)
   288  
   289  			ec := MakeConjunct(childEnv, x, ci)
   290  			n.scheduleConjunct(ec, ci)
   291  			hasEmbed = true
   292  		}
   293  	}
   294  	if hasEllipsis {
   295  		ci.cc.hasEllipsis = true
   296  	}
   297  	if !hasEmbed {
   298  		n.aStruct = s
   299  		n.aStructID = ci
   300  		ci.cc.hasNonTop = true
   301  	}
   302  
   303  	// TODO: probably no longer necessary.
   304  	parent.Disable = false
   305  }
   306  
   307  // scheduleVertexConjuncts injects the conjuncst of src n. If src was not fully
   308  // evaluated, it subscribes dst for future updates.
   309  func (n *nodeContext) scheduleVertexConjuncts(c Conjunct, arc *Vertex, closeInfo CloseInfo) {
   310  	// Don't add conjuncts if a node is referring to itself.
   311  	if n.node == arc {
   312  		return
   313  	}
   314  
   315  	// We need to ensure that each arc is only unified once (or at least) a
   316  	// bounded time, witch each conjunct. Comprehensions, for instance, may
   317  	// distribute a value across many values that get unified back into the
   318  	// same value. If such a value is a disjunction, than a disjunction of N
   319  	// disjuncts will result in a factor N more unifications for each
   320  	// occurrence of such value, resulting in exponential running time. This
   321  	// is especially common values that are used as a type.
   322  	//
   323  	// However, unification is idempotent, so each such conjunct only needs
   324  	// to be unified once. This cache checks for this and prevents an
   325  	// exponential blowup in such case.
   326  	//
   327  	// TODO(perf): this cache ensures the conjuncts of an arc at most once
   328  	// per ID. However, we really need to add the conjuncts of an arc only
   329  	// once total, and then add the close information once per close ID
   330  	// (pointer can probably be shared). Aside from being more performant,
   331  	// this is probably the best way to guarantee that conjunctions are
   332  	// linear in this case.
   333  
   334  	ciKey := closeInfo
   335  	ciKey.Refs = nil
   336  	ciKey.Inline = false
   337  	key := arcKey{arc, ciKey}
   338  	for _, k := range n.arcMap {
   339  		if key == k {
   340  			return
   341  		}
   342  	}
   343  	n.arcMap = append(n.arcMap, key)
   344  
   345  	if IsDef(c.Expr()) {
   346  		// TODO: or should we always insert the wrapper (for errors)?
   347  		ci, dc := closeInfo.spawnCloseContext(closeDef)
   348  		closeInfo = ci
   349  
   350  		dc.incDependent(DEFER, nil) // decrement deferred below
   351  		defer dc.decDependent(n.ctx, DEFER, nil)
   352  	}
   353  
   354  	if state := arc.getState(n.ctx); state != nil {
   355  		state.addNotify2(n.node, closeInfo)
   356  	}
   357  
   358  	for i := 0; i < len(arc.Conjuncts); i++ {
   359  		c := arc.Conjuncts[i]
   360  
   361  		// Note that we are resetting the tree here. We hereby assume that
   362  		// closedness conflicts resulting from unifying the referenced arc were
   363  		// already caught there and that we can ignore further errors here.
   364  		// c.CloseInfo = closeInfo
   365  
   366  		// We can use the original, but we know it will not be used
   367  
   368  		n.scheduleConjunct(c, closeInfo)
   369  	}
   370  }
   371  
   372  func (n *nodeContext) addNotify2(v *Vertex, c CloseInfo) []receiver {
   373  	n.completeNodeTasks()
   374  
   375  	// No need to do the notification mechanism if we are already complete.
   376  	old := n.notify
   377  	if n.meets(allAncestorsProcessed) {
   378  		return old
   379  	}
   380  
   381  	// Create a "root" closeContext to reflect the entry point of the
   382  	// reference into n.node relative to cc within v. After that, we can use
   383  	// assignConjunct to add new conjuncts.
   384  
   385  	// TODO: dedup: only add if t does not already exist. First check if this
   386  	// is even possible by adding a panic.
   387  	root := n.node.rootCloseContext()
   388  	if root.isDecremented {
   389  		return old
   390  	}
   391  
   392  	for _, r := range n.notify {
   393  		if r.v == v && r.cc == c.cc {
   394  			return old
   395  		}
   396  	}
   397  
   398  	cc := c.cc
   399  
   400  	if root.linkNotify(v, cc, c.CycleInfo) {
   401  		n.notify = append(n.notify, receiver{v, cc})
   402  		n.completeNodeTasks()
   403  	}
   404  
   405  	return old
   406  }
   407  
   408  // Literal conjuncts
   409  
   410  func (n *nodeContext) insertValueConjunct(env *Environment, v Value, id CloseInfo) {
   411  	n.updateCyclicStatus(id)
   412  
   413  	ctx := n.ctx
   414  
   415  	switch x := v.(type) {
   416  	case *Vertex:
   417  		if m, ok := x.BaseValue.(*StructMarker); ok {
   418  			n.aStruct = x
   419  			n.aStructID = id
   420  			if m.NeedClose {
   421  				// TODO: In the new evaluator this is used to mark a struct
   422  				// as closed in the debug output. Once the old evaluator is
   423  				// gone, we could simplify this.
   424  				id.IsClosed = true
   425  				if ctx.isDevVersion() {
   426  					var cc *closeContext
   427  					id, cc = id.spawnCloseContext(0)
   428  					cc.isClosedOnce = true
   429  				}
   430  			}
   431  		}
   432  
   433  		if !x.IsData() {
   434  			c := MakeConjunct(env, x, id)
   435  			n.scheduleVertexConjuncts(c, x, id)
   436  			return
   437  		}
   438  
   439  		// TODO: evaluate value?
   440  		switch v := x.BaseValue.(type) {
   441  		default:
   442  			panic(fmt.Sprintf("invalid type %T", x.BaseValue))
   443  
   444  		case *ListMarker:
   445  			// TODO: arguably we know now that the type _must_ be a list.
   446  			n.scheduleTask(handleListVertex, env, x, id)
   447  
   448  			return
   449  
   450  		case *StructMarker:
   451  			for _, a := range x.Arcs {
   452  				if a.ArcType != ArcMember {
   453  					continue
   454  				}
   455  				// TODO(errors): report error when this is a regular field.
   456  				c := MakeConjunct(nil, a, id)
   457  				n.insertArc(a.Label, a.ArcType, c, id, true)
   458  			}
   459  
   460  		case Value:
   461  			n.insertValueConjunct(env, v, id)
   462  		}
   463  
   464  		return
   465  
   466  	case *Bottom:
   467  		id.cc.hasNonTop = true
   468  		n.addBottom(x)
   469  		return
   470  
   471  	case *Builtin:
   472  		id.cc.hasNonTop = true
   473  		if v := x.BareValidator(); v != nil {
   474  			n.insertValueConjunct(env, v, id)
   475  			return
   476  		}
   477  	}
   478  
   479  	if !n.updateNodeType(v.Kind(), v, id) {
   480  		return
   481  	}
   482  
   483  	switch x := v.(type) {
   484  	case *Disjunction:
   485  		n.addDisjunctionValue(env, x, id)
   486  
   487  	case *Conjunction:
   488  		for _, x := range x.Values {
   489  			n.insertValueConjunct(env, x, id)
   490  		}
   491  
   492  	case *Top:
   493  		n.hasTop = true
   494  		id.cc.hasTop = true
   495  
   496  	case *BasicType:
   497  		id.cc.hasNonTop = true
   498  
   499  	case *BoundValue:
   500  		id.cc.hasNonTop = true
   501  		switch x.Op {
   502  		case LessThanOp, LessEqualOp:
   503  			if y := n.upperBound; y != nil {
   504  				n.upperBound = nil
   505  				v := SimplifyBounds(ctx, n.kind, x, y)
   506  				if err := valueError(v); err != nil {
   507  					err.AddPosition(v)
   508  					err.AddPosition(n.upperBound)
   509  					err.AddClosedPositions(id)
   510  				}
   511  				n.insertValueConjunct(env, v, id)
   512  				return
   513  			}
   514  			n.upperBound = x
   515  
   516  		case GreaterThanOp, GreaterEqualOp:
   517  			if y := n.lowerBound; y != nil {
   518  				n.lowerBound = nil
   519  				v := SimplifyBounds(ctx, n.kind, x, y)
   520  				if err := valueError(v); err != nil {
   521  					err.AddPosition(v)
   522  					err.AddPosition(n.lowerBound)
   523  					err.AddClosedPositions(id)
   524  				}
   525  				n.insertValueConjunct(env, v, id)
   526  				return
   527  			}
   528  			n.lowerBound = x
   529  
   530  		case EqualOp, NotEqualOp, MatchOp, NotMatchOp:
   531  			// This check serves as simplifier, but also to remove duplicates.
   532  			k := 0
   533  			match := false
   534  			for _, c := range n.checks {
   535  				if y, ok := c.(*BoundValue); ok {
   536  					switch z := SimplifyBounds(ctx, n.kind, x, y); {
   537  					case z == y:
   538  						match = true
   539  					case z == x:
   540  						continue
   541  					}
   542  				}
   543  				n.checks[k] = c
   544  				k++
   545  			}
   546  			n.checks = n.checks[:k]
   547  			if !match {
   548  				n.checks = append(n.checks, x)
   549  			}
   550  			return
   551  		}
   552  
   553  	case Validator:
   554  		// This check serves as simplifier, but also to remove duplicates.
   555  		for i, y := range n.checks {
   556  			if b := SimplifyValidator(ctx, x, y); b != nil {
   557  				n.checks[i] = b
   558  				return
   559  			}
   560  		}
   561  		n.updateNodeType(x.Kind(), x, id)
   562  		n.checks = append(n.checks, x)
   563  
   564  	case *Vertex:
   565  	// handled above.
   566  
   567  	case Value: // *NullLit, *BoolLit, *NumLit, *StringLit, *BytesLit, *Builtin
   568  		if y := n.scalar; y != nil {
   569  			if b, ok := BinOp(ctx, EqualOp, x, y).(*Bool); !ok || !b.B {
   570  				n.reportConflict(x, y, x.Kind(), y.Kind(), n.scalarID, id)
   571  			}
   572  			break
   573  		}
   574  		n.scalar = x
   575  		n.scalarID = id
   576  		n.signal(scalarKnown)
   577  
   578  	default:
   579  		panic(fmt.Sprintf("unknown value type %T", x))
   580  	}
   581  
   582  	if n.lowerBound != nil && n.upperBound != nil {
   583  		if u := SimplifyBounds(ctx, n.kind, n.lowerBound, n.upperBound); u != nil {
   584  			if err := valueError(u); err != nil {
   585  				err.AddPosition(n.lowerBound)
   586  				err.AddPosition(n.upperBound)
   587  				err.AddClosedPositions(id)
   588  			}
   589  			n.lowerBound = nil
   590  			n.upperBound = nil
   591  			n.insertValueConjunct(env, u, id)
   592  		}
   593  	}
   594  }
   595
View as plain text