unify.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  	"cuelang.org/go/cue/token"
    21  )
    22  
    23  func (v *Vertex) getState(c *OpContext) *nodeContext {
    24  	if v.status == finalized { // TODO: use BaseValue != nil
    25  		return nil
    26  	}
    27  	if v.state == nil {
    28  		v.state = c.newNodeContext(v)
    29  		v.state.initNode()
    30  		v.state.refCount = 1
    31  	}
    32  
    33  	// An additional refCount for the current user.
    34  	v.state.refCount += 1
    35  
    36  	// TODO: see if we can get rid of ref counting after new evaluator is done:
    37  	// the recursive nature of the new evaluator should make this unnecessary.
    38  
    39  	return v.state
    40  }
    41  
    42  // initNode initializes a nodeContext for the evaluation of the given Vertex.
    43  func (n *nodeContext) initNode() {
    44  	v := n.node
    45  	if v.Parent != nil && v.Parent.state != nil {
    46  		v.state.depth = v.Parent.state.depth + 1
    47  		n.blockOn(allAncestorsProcessed)
    48  	}
    49  
    50  	n.blockOn(scalarKnown | listTypeKnown | arcTypeKnown)
    51  
    52  	if v.Label.IsDef() {
    53  		v.Closed = true
    54  	}
    55  
    56  	if v.Parent != nil {
    57  		if v.Parent.Closed {
    58  			v.Closed = true
    59  		}
    60  	}
    61  
    62  	ctx := n.ctx
    63  
    64  	ctx.stats.Unifications++
    65  
    66  	// Set the cache to a cycle error to ensure a cyclic reference will result
    67  	// in an error if applicable. A cyclic error may be ignored for
    68  	// non-expression references. The cycle error may also be removed as soon
    69  	// as there is evidence what a correct value must be, but before all
    70  	// validation has taken place.
    71  	//
    72  	// TODO(cycle): having a more recursive algorithm would make this
    73  	// special cycle handling unnecessary.
    74  	v.BaseValue = cycle
    75  
    76  	defer ctx.PopArc(ctx.PushArc(v))
    77  
    78  	root := n.node.rootCloseContext()
    79  	root.incDependent(INIT, nil) // decremented below
    80  
    81  	for _, c := range v.Conjuncts {
    82  		ci := c.CloseInfo
    83  		ci.cc = root
    84  		n.scheduleConjunct(c, ci)
    85  	}
    86  
    87  	root.decDependent(ctx, INIT, nil)
    88  }
    89  
    90  func (v *Vertex) unify(c *OpContext, needs condition, mode runMode) bool {
    91  	if Debug {
    92  		c.nest++
    93  		c.Logf(v, "Unify %v", fmt.Sprintf("%p", v))
    94  		defer func() {
    95  			c.Logf(v, "END Unify")
    96  			c.nest--
    97  		}()
    98  	}
    99  
   100  	if mode == ignore {
   101  		return false
   102  	}
   103  
   104  	n := v.getState(c)
   105  	if n == nil {
   106  		return true // already completed
   107  	}
   108  	defer n.free()
   109  
   110  	// Typically a node processes all conjuncts before processing its fields.
   111  	// So this condition is very likely to trigger. If for some reason the
   112  	// parent has not been processed yet, we could attempt to process more
   113  	// of its tasks to increase the chances of being able to find the
   114  	// information we are looking for here. For now we just continue as is,
   115  	// though.
   116  	// For dynamic nodes, the parent only exists to provide a path context.
   117  	if v.Label.IsLet() || v.IsDynamic || v.Parent.allChildConjunctsKnown() {
   118  		n.signal(allAncestorsProcessed)
   119  	}
   120  
   121  	defer c.PopArc(c.PushArc(v))
   122  
   123  	nodeOnlyNeeds := needs &^ (subFieldsProcessed)
   124  	n.process(nodeOnlyNeeds, mode)
   125  	n.updateScalar()
   126  
   127  	// First process all but the subfields.
   128  	switch {
   129  	case n.meets(nodeOnlyNeeds):
   130  		// pass through next phase.
   131  	case mode != finalize:
   132  		return false
   133  	}
   134  
   135  	if isCyclePlaceholder(n.node.BaseValue) {
   136  		n.node.BaseValue = nil
   137  	}
   138  	if n.aStruct != nil {
   139  		n.updateNodeType(StructKind, n.aStruct, n.aStructID)
   140  	}
   141  
   142  	n.validateValue(finalized)
   143  
   144  	if err, ok := n.node.BaseValue.(*Bottom); ok {
   145  		for _, arc := range n.node.Arcs {
   146  			if arc.Label.IsLet() {
   147  				continue
   148  			}
   149  			c := MakeConjunct(nil, err, c.CloseInfo())
   150  			if arc.state != nil {
   151  				arc.state.scheduleConjunct(c, c.CloseInfo)
   152  			}
   153  		}
   154  	}
   155  
   156  	if n.node.Label.IsLet() || n.meets(allAncestorsProcessed) {
   157  		if cc := v.rootCloseContext(); !cc.isDecremented { // TODO: use v.cc
   158  			cc.decDependent(c, ROOT, nil) // REF(decrement:nodeDone)
   159  			cc.isDecremented = true
   160  		}
   161  	}
   162  
   163  	// At this point, no more conjuncts will be added, so we could decrement
   164  	// the notification counters.
   165  
   166  	switch {
   167  	case n.completed&subFieldsProcessed != 0:
   168  		// done
   169  
   170  	case needs&subFieldsProcessed != 0:
   171  		if DebugSort > 0 {
   172  			DebugSortArcs(n.ctx, n.node)
   173  		}
   174  
   175  		switch {
   176  		case assertStructuralCycle(n):
   177  		case n.completeAllArcs(needs, mode):
   178  		}
   179  
   180  		n.signal(subFieldsProcessed)
   181  
   182  		if v.BaseValue == nil {
   183  			v.BaseValue = n.getValidators(finalized)
   184  		}
   185  		if v := n.node.Value(); v != nil && IsConcrete(v) {
   186  			// Ensure that checks are not run again when this value is used
   187  			// in a validator.
   188  			checks := n.checks
   189  			n.checks = n.checks[:0]
   190  			for _, v := range checks {
   191  				// TODO(errors): make Validate return bottom and generate
   192  				// optimized conflict message. Also track and inject IDs
   193  				// to determine origin location.s
   194  				if b := c.Validate(v, n.node); b != nil {
   195  					n.addBottom(b)
   196  				}
   197  			}
   198  		}
   199  
   200  	case needs&fieldSetKnown != 0:
   201  		n.evalArcTypes()
   202  	}
   203  
   204  	if err := n.getErr(); err != nil {
   205  		n.errs = nil
   206  		if b, _ := n.node.BaseValue.(*Bottom); b != nil {
   207  			err = CombineErrors(nil, b, err)
   208  		}
   209  		n.node.BaseValue = err
   210  	}
   211  
   212  	if mask := n.completed & needs; mask != 0 {
   213  		// TODO: phase3: validation
   214  		n.signal(mask)
   215  	}
   216  
   217  	// validationCompleted
   218  	if n.completed&(subFieldsProcessed) != 0 {
   219  		n.node.updateStatus(finalized)
   220  
   221  		for _, r := range n.node.cc.externalDeps {
   222  			src := r.src
   223  			a := &src.arcs[r.index]
   224  			if a.decremented {
   225  				continue
   226  			}
   227  			a.decremented = true
   228  			if n := src.src.getState(n.ctx); n != nil {
   229  				n.completeNodeConjuncts()
   230  			}
   231  			src.src.unify(n.ctx, needTasksDone, attemptOnly)
   232  			a.cc.decDependent(c, a.kind, src) // REF(arcs)
   233  		}
   234  
   235  		if DebugDeps {
   236  			RecordDebugGraph(n.ctx, n.node, "Finalize")
   237  		}
   238  	}
   239  
   240  	return n.meets(needs)
   241  }
   242  
   243  // Once returning, all arcs plus conjuncts that can be known are known.
   244  //
   245  // Proof:
   246  //   - if there is a cycle, all completeNodeConjuncts will be called
   247  //     repeatedly for all nodes in this cycle, and all tasks on the cycle
   248  //     will have run at least once.
   249  //   - any tasks that were blocking on values on this circle to be completed
   250  //     will thus have to be completed at some point in time if they can.
   251  //   - any tasks that were blocking on values outside of this ring will have
   252  //     initiated its own execution, which is either not cyclic, and thus
   253  //     completes, or is on a different cycle, in which case it completes as
   254  //     well.
   255  func (n *nodeContext) completeNodeConjuncts() {
   256  	const conjunctsKnown = fieldConjunctsKnown | valueKnown // | fieldSetKnown
   257  
   258  	if n.meets(conjunctsKnown) {
   259  		return
   260  	}
   261  
   262  	if p := n.node.Parent; p != nil && p.state != nil {
   263  		p.state.completeNodeConjuncts()
   264  	}
   265  
   266  	// This only attempts, but it ensures that all references are processed.
   267  	n.process(conjunctsKnown, attemptOnly)
   268  }
   269  
   270  // Goal:
   271  // - complete notifications
   272  // - decrement reference counts for root and notify.
   273  // NOT:
   274  // - complete value. That is reserved for Unify.
   275  func (n *nodeContext) completeNodeTasks() (ok bool) {
   276  	v := n.node
   277  	c := n.ctx
   278  
   279  	if Debug {
   280  		c.nest++
   281  		defer func() {
   282  			c.nest--
   283  		}()
   284  	}
   285  
   286  	if p := v.Parent; p != nil && p.state != nil {
   287  		if !v.IsDynamic && n.completed&allAncestorsProcessed == 0 {
   288  			p.state.completeNodeTasks()
   289  		}
   290  	}
   291  
   292  	if v.IsDynamic || v.Parent.allChildConjunctsKnown() {
   293  		n.signal(allAncestorsProcessed)
   294  	}
   295  
   296  	if len(n.scheduler.tasks) != n.scheduler.taskPos {
   297  		// TODO: do we need any more requirements here?
   298  		const needs = valueKnown | fieldConjunctsKnown
   299  
   300  		n.process(needs, attemptOnly)
   301  		n.updateScalar()
   302  	}
   303  
   304  	// As long as ancestors are not processed, it is still possible for
   305  	// conjuncts to be inserted. Until that time, it is not okay to decrement
   306  	// theroot. It is not necessary to wait on tasks to complete, though,
   307  	// as pending tasks will have their own dependencies on root, meaning it
   308  	// is safe to decrement here.
   309  	if !n.meets(allAncestorsProcessed) && !n.node.Label.IsLet() {
   310  		return false
   311  	}
   312  
   313  	// At this point, no more conjuncts will be added, so we could decrement
   314  	// the notification counters.
   315  
   316  	if cc := v.rootCloseContext(); !cc.isDecremented { // TODO: use v.cc
   317  		cc.isDecremented = true
   318  
   319  		cc.decDependent(n.ctx, ROOT, nil) // REF(decrement:nodeDone)
   320  	}
   321  
   322  	return true
   323  }
   324  
   325  func (n *nodeContext) updateScalar() {
   326  	// Set BaseValue to scalar, but only if it was not set before. Most notably,
   327  	// errors should not be discarded.
   328  	_, isErr := n.node.BaseValue.(*Bottom)
   329  	if n.scalar != nil && (!isErr || isCyclePlaceholder(n.node.BaseValue)) {
   330  		n.node.BaseValue = n.scalar
   331  		n.signal(scalarKnown)
   332  	}
   333  }
   334  
   335  func (n *nodeContext) completeAllArcs(needs condition, mode runMode) bool {
   336  	if n.node.status == evaluatingArcs {
   337  		// NOTE: this was an "incomplete" error pre v0.6. If this is a problem
   338  		// we could make this a CycleError. Technically, this may be correct,
   339  		// as it is possible to make the values exactly as the inserted
   340  		// values. It seems more user friendly to just disallow this, though.
   341  		// TODO: make uniform error messages
   342  		// see compbottom2.cue:
   343  		n.ctx.addErrf(CycleError, pos(n.node), "mutual dependency")
   344  	}
   345  
   346  	n.node.updateStatus(evaluatingArcs)
   347  
   348  	// XXX(0.7): only set success if needs complete arcs.
   349  	success := true
   350  	// Visit arcs recursively to validate and compute error.
   351  	for n.arcPos < len(n.node.Arcs) {
   352  		a := n.node.Arcs[n.arcPos]
   353  		n.arcPos++
   354  
   355  		if !a.unify(n.ctx, needs, finalize) {
   356  			success = false
   357  		}
   358  
   359  		// At this point we need to ensure that all notification cycles
   360  		// for Arc a have been processed.
   361  
   362  		if a.ArcType == ArcPending {
   363  			// TODO: cancel tasks?
   364  			a.ArcType = ArcNotPresent
   365  			continue
   366  		}
   367  
   368  		// Errors are allowed in let fields. Handle errors and failure to
   369  		// complete accordingly.
   370  		if !a.Label.IsLet() && a.ArcType <= ArcRequired {
   371  			if err, _ := a.BaseValue.(*Bottom); err != nil {
   372  				n.node.AddChildError(err)
   373  			}
   374  			success = true // other arcs are irrelevant
   375  		}
   376  
   377  		// TODO: harmonize this error with "cannot combine"
   378  		switch {
   379  		case a.ArcType > ArcRequired, !a.Label.IsString():
   380  		case n.kind&StructKind == 0:
   381  			if !n.node.IsErr() {
   382  				n.reportFieldMismatch(pos(a.Value()), nil, a.Label, n.node.Value())
   383  			}
   384  			// case !wasVoid:
   385  			// case n.kind == TopKind:
   386  			// 	// Theoretically it may be possible that a "void" arc references
   387  			// 	// this top value where it really should have been a struct. One
   388  			// 	// way to solve this is to have two passes over the arcs, where
   389  			// 	// the first pass additionally analyzes whether comprehensions
   390  			// 	// will yield values and "un-voids" an arc ahead of the rest.
   391  			// 	//
   392  			// 	// At this moment, though, I fail to see a possibility to create
   393  			// 	// faulty CUE using this mechanism, though. At most error
   394  			// 	// messages are a bit unintuitive. This may change once we have
   395  			// 	// functionality to reflect on types.
   396  			// 	if _, ok := n.node.BaseValue.(*Bottom); !ok {
   397  			// 		n.node.BaseValue = &StructMarker{}
   398  			// 		n.kind = StructKind
   399  			// 	}
   400  		}
   401  	}
   402  
   403  	k := 0
   404  	for _, a := range n.node.Arcs {
   405  		if a.ArcType != ArcNotPresent {
   406  			n.node.Arcs[k] = a
   407  			k++
   408  		}
   409  	}
   410  	n.node.Arcs = n.node.Arcs[:k]
   411  
   412  	return success
   413  }
   414  
   415  func (n *nodeContext) evalArcTypes() {
   416  	for _, a := range n.node.Arcs {
   417  		if a.ArcType != ArcPending {
   418  			continue
   419  		}
   420  		a.unify(n.ctx, arcTypeKnown, yield)
   421  		// Ensure the arc is processed up to the desired level
   422  		if a.ArcType == ArcPending {
   423  			// TODO: cancel tasks?
   424  			a.ArcType = ArcNotPresent
   425  		}
   426  	}
   427  }
   428  
   429  func (v *Vertex) lookup(c *OpContext, pos token.Pos, f Feature, flags combinedFlags) *Vertex {
   430  	task := c.current()
   431  	needs := flags.conditions()
   432  	runMode := flags.runMode()
   433  
   434  	c.Logf(c.vertex, "LOOKUP %v", f)
   435  
   436  	state := v.getState(c)
   437  	if state != nil {
   438  		// If the scheduler associated with this vertex was already running,
   439  		// it means we have encountered a cycle. In that case, we allow to
   440  		// proceed with partial data, in which case a "pending" arc will be
   441  		// created to be completed later.
   442  
   443  		// Report error for now.
   444  		if state.hasErr() {
   445  			c.AddBottom(state.getErr())
   446  		}
   447  		state.completeNodeTasks()
   448  	}
   449  
   450  	// TODO: remove because unnecessary?
   451  	if task.state != taskRUNNING {
   452  		return nil // abort, task is blocked or terminated in a cycle.
   453  	}
   454  
   455  	// TODO: verify lookup types.
   456  
   457  	arc := v.Lookup(f)
   458  	// TODO: clean up this logic:
   459  	// - signal arcTypeKnown when ArcMember or ArcNotPresent is set,
   460  	//   similarly to scalarKnown.
   461  	// - make it clear we want to yield if it is now known if a field exists.
   462  
   463  	var arcState *nodeContext
   464  	switch {
   465  	case arc != nil:
   466  		if arc.ArcType == ArcMember {
   467  			return arc
   468  		}
   469  		arcState = arc.getState(c)
   470  
   471  	case state == nil || state.meets(needTasksDone):
   472  		// This arc cannot exist.
   473  		v.reportFieldIndexError(c, pos, f)
   474  		return nil
   475  
   476  	default:
   477  		arc = &Vertex{Parent: state.node, Label: f, ArcType: ArcPending}
   478  		v.Arcs = append(v.Arcs, arc)
   479  		arcState = arc.getState(c)
   480  	}
   481  
   482  	if arcState != nil && (!arcState.meets(needTasksDone) || !arcState.meets(arcTypeKnown)) {
   483  		needs |= arcTypeKnown
   484  		// If this arc is not ArcMember, which it is not at this point,
   485  		// any pending arcs could influence the field set.
   486  		for _, a := range arc.Arcs {
   487  			if a.ArcType == ArcPending {
   488  				needs |= fieldSetKnown
   489  				break
   490  			}
   491  		}
   492  		arcState.completeNodeTasks()
   493  
   494  		// Child nodes, if pending and derived from a comprehension, may
   495  		// still cause this arc to become not pending.
   496  		if arc.ArcType != ArcMember {
   497  			for _, a := range arcState.node.Arcs {
   498  				if a.ArcType == ArcPending {
   499  					a.unify(c, arcTypeKnown, runMode)
   500  				}
   501  			}
   502  		}
   503  
   504  		switch runMode {
   505  		case ignore, attemptOnly:
   506  			// TODO: should we avoid notifying ArcPending vertices here?
   507  			arcState.addNotify2(task.node.node, task.id)
   508  			return arc
   509  
   510  		case yield:
   511  			arcState.process(needs, yield)
   512  			// continue processing, as successful processing may still result
   513  			// in an invalid field.
   514  
   515  		case finalize:
   516  			// TODO: should we try to use finalize? Using it results in errors and this works. It would be more principled, though.
   517  			arcState.process(needs, yield)
   518  		}
   519  	}
   520  
   521  	switch arc.ArcType {
   522  	case ArcMember:
   523  		return arc
   524  
   525  	case ArcOptional, ArcRequired:
   526  		label := f.SelectorString(c.Runtime)
   527  		b := &Bottom{
   528  			Code: IncompleteError,
   529  			Err: c.NewPosf(pos,
   530  				"cannot reference optional field: %s", label),
   531  		}
   532  		c.AddBottom(b)
   533  		// TODO: yield failure
   534  		return nil
   535  
   536  	case ArcNotPresent:
   537  		v.reportFieldCycleError(c, pos, f)
   538  		return nil
   539  
   540  	case ArcPending:
   541  		// should not happen.
   542  		panic("unreachable")
   543  	}
   544  
   545  	v.reportFieldIndexError(c, pos, f)
   546  	return nil
   547  }
   548
View as plain text