...

Source file src/cuelang.org/go/internal/core/adt/states.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  // TODO: clean up following notes:
    18  
    19  // Used in expr.go:
    20  // - ctx.value  (uses: noncrete scalar allowed, concrete scalar, concrete composite)
    21  //   - evalState
    22  // - ctx.node (need to know all fields)
    23  // - ctx.lookup
    24  // - ctx.concrete
    25  //
    26  // - ctx.relLabel
    27  //     OK: always exists
    28  // - ctx.relNode (upcount + unify(partial))
    29  //     OK: node always exists.
    30  //
    31  // - ctx.evalState (in validation of comparison against bottom)
    32  //
    33  // - arc.Finalize (finalized)
    34  // - CompleteArcs (conjuncts)
    35  //
    36  
    37  // lookup in p1
    38  //    - process remaining field todos
    39  
    40  // lookup:
    41  // if node is currently processing, just look up directly and create
    42  // field with notification.
    43  //
    44  // if node has not been processed, process once.
    45  //
    46  // Any dynamic fields should have been triggered by the existence of a new
    47  // arc. This will either cascade the evaluation or not.
    48  
    49  // p1: {
    50  // 	(p1.baz): "bar" // t1
    51  // 	(p1.foo): "baz" // t2
    52  // 	baz: "foo"
    53  // }
    54  //
    55  // <p1, fieldsKnown> -> t1 -> <p1.baz, scalar>
    56  // <p1.foo, scalar> -> t1
    57  // <p1, fieldsKnown> -> t2 -> <p1.foo, scalar>
    58  
    59  // p2: {
    60  // 	(p2[p2.baz]): "bar"
    61  // 	(p2.foo): "baz"
    62  // 	baz: "qux"
    63  // 	qux: "foo"
    64  // }
    65  
    66  // b -> a - > b: detected cycle in b:
    67  //
    68  //		xxx register expression (a-10) being processed as a post constraint.
    69  //		add task to pending.
    70  //		register value as waiting for scalar to be completed later.
    71  //		return with cycle/ in complete error.
    72  //
    73  //	  - in b:
    74  //	    xxx register expression (b+10) as post constraint.
    75  //	    add task to pending
    76  //	    register value as waiting for scalar to be completed later.
    77  //	    5 is processed and set
    78  //	    this completes the task in b
    79  //	    this sets a scalar in b
    80  //	    this completes the expression in a
    81  //
    82  //	    b: a - 10
    83  //	    a: b + 10
    84  //	    a: 5
    85  //
    86  //	    a: a
    87  //	    a: 5
    88  //
    89  
    90  // These are the condition types of the CUE evaluator. A scheduler
    91  // is associated with a single Vertex. So when these states refer to a Vertex,
    92  // it is the Vertex associated with the scheduler.
    93  //
    94  // There are core conditions and condition sets. The core conditions are
    95  // determined during operation as conditions are met. The condition sets are
    96  // used to indicate a set of required or provided conditions.
    97  //
    98  // Core conditions can be signal conditions or counter conditions. A counter
    99  // condition is triggered if all conjuncts that contribute to the computation
   100  // of this condition have been met. A signal condition is triggered as soon as
   101  // evidence is found that this condition is met. Unless otherwise specified,
   102  // conditions are counter conditions.
   103  const (
   104  	// allAncestorsProcessed indicates that all conjuncts that could be added
   105  	// to the Vertex by any of its ancestors have been added. In other words,
   106  	// all ancestors schedulers have reached the state fieldConjunctsKnown.
   107  	//
   108  	// This is a signal condition. It is explicitly set in unify when a
   109  	// parent meets fieldConjunctsKnown|allAncestorsProcessed.
   110  	allAncestorsProcessed condition = 1 << iota
   111  
   112  	// Really: all ancestor subfield tasks processed.
   113  
   114  	// arcTypeKnown means that the ArcType value of a Vertex is fully
   115  	// determined. The ArcType of all fields of a Vertex need to be known
   116  	// before the complete set of fields of this Vertex can be known.
   117  	arcTypeKnown
   118  
   119  	// valueKnown means that it is known what the "type" of the value would be
   120  	// if present.
   121  	valueKnown
   122  
   123  	// scalarKnown indicates that a Vertex has either a concrete scalar value or
   124  	// that it is known that it will never have a scalar value.
   125  	//
   126  	// This is a signal condition that is reached when:
   127  	//    - a node is set to a concrete scalar value
   128  	//    - a node is set to an error
   129  	//    - or if XXXstate is reached.
   130  	//
   131  	// TODO: rename to something better?
   132  	scalarKnown
   133  
   134  	// listTypeKnown indicates that it is known that lists unified with this
   135  	// Vertex should be interpreted as integer indexed lists, as associative
   136  	// lists, or an error.
   137  	//
   138  	// This is a signal condition that is reached when:
   139  	//    - allFieldsKnown is reached (all expressions have )
   140  	//    - it is unified with an associative list type
   141  	listTypeKnown
   142  
   143  	// fieldConjunctsKnown means that all the conjuncts of all fields are
   144  	// known.
   145  	fieldConjunctsKnown
   146  
   147  	// fieldSetKnown means that all fields of this node are known. This is true
   148  	// if all tasks that can add a field have been processed and if
   149  	// all pending arcs have been resolved.
   150  	fieldSetKnown
   151  
   152  	// // allConjunctsKnown means that all conjuncts have been registered as a
   153  	// // task. allParentsProcessed must be true for this to be true.
   154  	// allConjunctsKnown
   155  
   156  	// allTasksCompleted means that all tasks of a Vertex have been completed
   157  	// with the exception of validation tasks. A Vertex may still not be
   158  	// finalized.
   159  	allTasksCompleted
   160  
   161  	// subFieldsProcessed means that all tasks of a Vertex, including those of
   162  	// its arcs have been completed.
   163  	//
   164  	// This is a signal condition that is met if all arcs have reached the
   165  	// the state finalStateKnown.
   166  	//
   167  	subFieldsProcessed
   168  
   169  	leftOfMaxCoreCondition
   170  
   171  	finalStateKnown condition = leftOfMaxCoreCondition - 1
   172  
   173  	preValidation condition = finalStateKnown //&^ validationCompleted
   174  
   175  	conditionsUsingCounters = arcTypeKnown |
   176  		valueKnown |
   177  		fieldConjunctsKnown |
   178  		allTasksCompleted
   179  
   180  	// The xConjunct condition sets indicate a conjunct MAY contribute the to
   181  	// final result. For some conjuncts it may not be known what the
   182  	// contribution will be. In such a cases the set that reflects all possible
   183  	// contributions should be used. For instance, an embedded reference may
   184  	// resolve to a scalar or struct.
   185  	//
   186  	// All conjunct states include allTasksCompleted.
   187  
   188  	// a genericConjunct is one for which the contributions to the states
   189  	// are not known in advance. For instance, an embedded reference can be
   190  	// anything. In such case, all conditions are included.
   191  	genericConjunct = allTasksCompleted |
   192  		scalarKnown |
   193  		valueKnown |
   194  		fieldConjunctsKnown
   195  
   196  	// a fieldConjunct is on that only adds a new field to the struct.
   197  	fieldConjunct = allTasksCompleted |
   198  		fieldConjunctsKnown
   199  
   200  	// a scalarConjunct is one that is guaranteed to result in a scalar or
   201  	// list value.
   202  	scalarConjunct = allTasksCompleted |
   203  		scalarKnown |
   204  		valueKnown
   205  
   206  	// needsX condition sets are used to indicate which conditions need to be
   207  	// met.
   208  
   209  	needFieldConjunctsKnown = fieldConjunctsKnown |
   210  		allAncestorsProcessed
   211  
   212  	needFieldSetKnown = fieldSetKnown |
   213  		allAncestorsProcessed
   214  
   215  	needTasksDone = allAncestorsProcessed | allTasksCompleted
   216  
   217  	// concreteKnown means that we know whether a value is concrete or not.
   218  	// At the moment this is equal to 'scalarKnown'.
   219  	concreteKnown = scalarKnown
   220  )
   221  
   222  // schedConfig configures a taskContext with the states needed for the
   223  // CUE evaluator. It is used in OpContext.New as a template for creating
   224  // new taskContexts.
   225  var schedConfig = taskContext{
   226  	counterMask: conditionsUsingCounters,
   227  	autoUnblock: listTypeKnown | scalarKnown | arcTypeKnown,
   228  	complete:    stateCompletions,
   229  }
   230  
   231  // stateCompletions indicates the completion of conditions based on the
   232  // completions of other conditions.
   233  func stateCompletions(s *scheduler) condition {
   234  	x := s.completed
   235  	v := s.node.node
   236  	s.node.Logf("=== stateCompletions: %v  %v", v.Label, s.completed)
   237  	if x.meets(allAncestorsProcessed) {
   238  		x |= conditionsUsingCounters &^ s.provided
   239  		// If we have a pending arc, a sub arc may still cause the arc to
   240  		// become not pending. For instance, if 'a' is pending in the following
   241  		//   if x != _!_ {
   242  		//       a: b: 1
   243  		//   }
   244  		// it may still become not pending if 'b' becomes a regular arc.
   245  		if s.counters[arcTypeKnown] == 0 && x.meets(subFieldsProcessed) {
   246  			x |= arcTypeKnown
   247  		}
   248  	}
   249  	switch {
   250  	case v.ArcType == ArcMember, v.ArcType == ArcNotPresent:
   251  		x |= arcTypeKnown
   252  	case x&arcTypeKnown != 0 && v.ArcType == ArcPending:
   253  		v.ArcType = ArcNotPresent
   254  	}
   255  
   256  	if x.meets(valueKnown) {
   257  		// NOTE: in this case, scalarKnown is not the same as concreteKnown,
   258  		// especially if this arc is Pending, as it may still become concrete.
   259  		// We probably want to separate this out.
   260  		if v.ArcType == ArcMember || v.ArcType == ArcNotPresent {
   261  			x |= scalarKnown
   262  		}
   263  		x |= listTypeKnown
   264  	}
   265  
   266  	if x.meets(needFieldConjunctsKnown | needTasksDone) {
   267  		switch {
   268  		case x.meets(subFieldsProcessed):
   269  			x |= fieldSetKnown
   270  		default:
   271  			for _, a := range v.Arcs {
   272  				if a.ArcType == ArcPending {
   273  					return x
   274  				}
   275  			}
   276  			x |= fieldSetKnown
   277  		}
   278  	}
   279  	return x
   280  }
   281  
   282  // allChildConjunctsKnown indicates that all conjuncts have been added by
   283  // the parents and every conjunct that may add fields to subfields have been
   284  // processed.
   285  func (v *Vertex) allChildConjunctsKnown() bool {
   286  	if v == nil {
   287  		return true
   288  	}
   289  
   290  	return v.state.meets(fieldConjunctsKnown | allAncestorsProcessed)
   291  }
   292  
   293  func (n *nodeContext) scheduleTask(r *runner, env *Environment, x Node, ci CloseInfo) *task {
   294  	t := &task{
   295  		run:  r,
   296  		node: n,
   297  
   298  		env: env,
   299  		id:  ci,
   300  		x:   x,
   301  	}
   302  	n.insertTask(t)
   303  	return t
   304  }
   305  
   306  // require ensures that a given condition is met for the given Vertex by
   307  // evaluating it. It yields execution back to the scheduler if it cannot
   308  // be completed at this point.
   309  func (c *OpContext) require(v *Vertex, needs condition) {
   310  	state := v.getState(c)
   311  	if state == nil {
   312  		return
   313  	}
   314  	state.process(needs, yield)
   315  }
   316  
   317  // scalarValue evaluates the given expression and either returns a
   318  // concrete value or schedules the task for later evaluation.
   319  func (ctx *OpContext) scalarValue(t *task, x Expr) Value {
   320  	return ctx.value(x, require(0, scalarKnown))
   321  }
   322  

View as plain text