comprehension.go

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

     1  // Copyright 2021 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  // Comprehension algorithm
    18  //
    19  // Comprehensions are expanded for, if, and let clauses that yield 0 or more
    20  // structs to be embedded in the enclosing list or struct.
    21  //
    22  // CUE allows cascading of insertions, as in:
    23  //
    24  //     a?: int
    25  //     b?: int
    26  //     if a != _|_ {
    27  //         b: 2
    28  //     }
    29  //     if b != _|_ {
    30  //         c: 3
    31  //         d: 4
    32  //     }
    33  //
    34  // even though CUE does not allow the result of a comprehension to depend
    35  // on another comprehension within a single struct. The way this works is that
    36  // for fields with a fixed prefix path in a comprehension value, the
    37  // comprehension is assigned to these respective fields.
    38  //
    39  // More concretely, the above example is rewritten to:
    40  //
    41  //    a?: int
    42  //    b: if a != _|_ { 2 }
    43  //    c: if b != _|_ { 3 }
    44  //    d: if b != _|_ { 4 }
    45  //
    46  // where the fields with if clause are only inserted if their condition
    47  // resolves to true. (Note that this is not valid CUE; it may be in the future.)
    48  //
    49  // With this rewrite, any dependencies in comprehension expressions will follow
    50  // the same rules, more or less, as with normal evaluation.
    51  //
    52  // Note that a single comprehension may be distributed across multiple fields.
    53  // The evaluator will ensure, however, that a comprehension is only evaluated
    54  // once.
    55  //
    56  //
    57  // Closedness
    58  //
    59  // The comprehension algorithm uses the usual closedness mechanism for marking
    60  // fields that belong to a struct: it adds the StructLit associated with the
    61  // comprehension value to the respective arc.
    62  //
    63  // One noteworthy point is that the fields of a struct are only legitimate for
    64  // actual results. For instance, if an if clause evaluates to false, the
    65  // value is not embedded.
    66  //
    67  // To account for this, the comprehension algorithm relies on the fact that
    68  // the closedness information is computed as a separate step. So even if
    69  // the StructLit is added early, its fields will only count once it is
    70  // initialized, which is only done when at least one result is added.
    71  //
    72  
    73  // envComprehension caches the result of a single comprehension.
    74  type envComprehension struct {
    75  	comp   *Comprehension
    76  	vertex *Vertex // The Vertex from which the comprehension originates.
    77  
    78  	// runtime-related fields
    79  
    80  	err *Bottom
    81  
    82  	// envs holds all the environments that define a single "yield" result in
    83  	// combination with the comprehension struct.
    84  	envs []*Environment // nil: unprocessed, non-nil: done.
    85  	done bool           // true once the comprehension has been evaluated
    86  
    87  	// StructLits to Init (activate for closedness check)
    88  	// when at least one value is yielded.
    89  	structs []*StructLit
    90  }
    91  
    92  // envYield defines a comprehension for a specific field within a comprehension
    93  // value. Multiple envYields can be associated with a single envComprehension.
    94  // An envComprehension only needs to be evaluated once for multiple envYields.
    95  type envYield struct {
    96  	*envComprehension                // The original comprehension.
    97  	leaf              *Comprehension // The leaf Comprehension
    98  
    99  	// Values specific to the field corresponding to this envYield
   100  
   101  	// This envYield was added to selfComprehensions
   102  	self bool
   103  	// This envYield was successfully executed and the resulting conjuncts were
   104  	// added.
   105  	inserted bool
   106  
   107  	env  *Environment // The adjusted Environment.
   108  	id   CloseInfo    // CloseInfo for the field.
   109  	expr Node         // The adjusted expression.
   110  }
   111  
   112  // ValueClause represents a wrapper Environment in a chained clause list
   113  // to account for the unwrapped struct. It is never created by the compiler
   114  // and serves as a dynamic element only.
   115  type ValueClause struct {
   116  	Node
   117  
   118  	// The node in which to resolve lookups in the comprehension's value struct.
   119  	arc *Vertex
   120  }
   121  
   122  func (v *ValueClause) yield(s *compState) {
   123  	s.yield(s.ctx.spawn(v.arc))
   124  }
   125  
   126  // insertComprehension registers a comprehension with a node, possibly pushing
   127  // down its evaluation to the node's children. It will only evaluate one level
   128  // of fields at a time.
   129  func (n *nodeContext) insertComprehension(
   130  	env *Environment,
   131  	c *Comprehension,
   132  	ci CloseInfo,
   133  ) {
   134  	// TODO(perf): this implementation causes the parent's clauses
   135  	// to be evaluated for each nested comprehension. It would be
   136  	// possible to simply store the envComprehension of the parent's
   137  	// result and have each subcomprehension reuse those. This would
   138  	// also avoid the below allocation and would probably allow us
   139  	// to get rid of the ValueClause type.
   140  
   141  	ec := c.comp
   142  	if ec == nil {
   143  		ec = &envComprehension{
   144  			comp:   c,
   145  			vertex: n.node,
   146  
   147  			err:  nil,   // shut up linter
   148  			envs: nil,   // shut up linter
   149  			done: false, // shut up linter
   150  		}
   151  	}
   152  
   153  	if ec.done && len(ec.envs) == 0 {
   154  		return
   155  	}
   156  
   157  	x := c.Value
   158  
   159  	if !n.ctx.isDevVersion() {
   160  		ci = ci.SpawnEmbed(c)
   161  		ci.closeInfo.span |= ComprehensionSpan
   162  	}
   163  
   164  	var decls []Decl
   165  	switch v := ToExpr(x).(type) {
   166  	case *StructLit:
   167  		numFixed := 0
   168  		var fields []Decl
   169  		for _, d := range v.Decls {
   170  			switch f := d.(type) {
   171  			case *Field:
   172  				numFixed++
   173  
   174  				// Create partial comprehension
   175  				c := &Comprehension{
   176  					Syntax:  c.Syntax,
   177  					Clauses: c.Clauses,
   178  					Value:   f,
   179  					arcType: f.ArcType,
   180  
   181  					comp:   ec,
   182  					parent: c,
   183  					arc:    n.node,
   184  				}
   185  
   186  				conjunct := MakeConjunct(env, c, ci)
   187  				n.node.state.insertFieldUnchecked(f.Label, ArcPending, conjunct)
   188  				fields = append(fields, f)
   189  
   190  			case *LetField:
   191  				// TODO: consider merging this case with the LetField case.
   192  
   193  				numFixed++
   194  
   195  				// Create partial comprehension
   196  				c := &Comprehension{
   197  					Syntax:  c.Syntax,
   198  					Clauses: c.Clauses,
   199  					Value:   f,
   200  
   201  					comp:   ec,
   202  					parent: c,
   203  					arc:    n.node,
   204  				}
   205  
   206  				conjunct := MakeConjunct(env, c, ci)
   207  				arc := n.node.state.insertFieldUnchecked(f.Label, ArcMember, conjunct)
   208  				arc.MultiLet = f.IsMulti
   209  
   210  				fields = append(fields, f)
   211  
   212  			default:
   213  				decls = append(decls, d)
   214  			}
   215  		}
   216  
   217  		if len(fields) > 0 {
   218  			// Create a stripped struct that only includes fixed fields.
   219  			// TODO(perf): this StructLit may be inserted more than once in
   220  			// the same vertex: once taking the StructLit of the referred node
   221  			// and once for inserting the Conjunct of the original node.
   222  			// Is this necessary (given closedness rules), and is this posing
   223  			// a performance problem?
   224  			st := v
   225  			if len(fields) < len(v.Decls) {
   226  				st = &StructLit{
   227  					Src:   v.Src,
   228  					Decls: fields,
   229  				}
   230  			}
   231  			n.node.AddStruct(st, env, ci)
   232  			switch {
   233  			case !ec.done:
   234  				ec.structs = append(ec.structs, st)
   235  			case len(ec.envs) > 0:
   236  				st.Init()
   237  			}
   238  		}
   239  
   240  		switch numFixed {
   241  		case 0:
   242  			// Add comprehension as is.
   243  
   244  		case len(v.Decls):
   245  			// No comprehension to add at this level.
   246  			return
   247  
   248  		default:
   249  			// Create a new StructLit with only the fields that need to be
   250  			// added at this level.
   251  			x = &StructLit{Decls: decls}
   252  		}
   253  	}
   254  
   255  	if n.ctx.isDevVersion() {
   256  		t := n.scheduleTask(handleComprehension, env, x, ci)
   257  		t.comp = ec
   258  		t.leaf = c
   259  	} else {
   260  		n.comprehensions = append(n.comprehensions, envYield{
   261  			envComprehension: ec,
   262  			leaf:             c,
   263  			env:              env,
   264  			id:               ci,
   265  			expr:             x,
   266  		})
   267  	}
   268  }
   269  
   270  type compState struct {
   271  	ctx   *OpContext
   272  	comp  *Comprehension
   273  	i     int
   274  	f     YieldFunc
   275  	state vertexStatus
   276  }
   277  
   278  // yield evaluates a Comprehension within the given Environment and calls
   279  // f for each result.
   280  func (c *OpContext) yield(
   281  	node *Vertex, // errors are associated with this node
   282  	env *Environment, // env for field for which this yield is called
   283  	comp *Comprehension,
   284  	state combinedFlags,
   285  	f YieldFunc, // called for every result
   286  ) *Bottom {
   287  	s := &compState{
   288  		ctx:   c,
   289  		comp:  comp,
   290  		f:     f,
   291  		state: state.vertexStatus(),
   292  	}
   293  	y := comp.Clauses[0]
   294  
   295  	saved := c.PushState(env, y.Source())
   296  	if node != nil {
   297  		defer c.PopArc(c.PushArc(node))
   298  	}
   299  
   300  	s.i++
   301  	y.yield(s)
   302  	s.i--
   303  
   304  	return c.PopState(saved)
   305  }
   306  
   307  func (s *compState) yield(env *Environment) (ok bool) {
   308  	c := s.ctx
   309  	if s.i >= len(s.comp.Clauses) {
   310  		s.f(env)
   311  		return true
   312  	}
   313  	dst := s.comp.Clauses[s.i]
   314  	saved := c.PushState(env, dst.Source())
   315  
   316  	s.i++
   317  	dst.yield(s)
   318  	s.i--
   319  
   320  	if b := c.PopState(saved); b != nil {
   321  		c.AddBottom(b)
   322  		return false
   323  	}
   324  	return !c.HasErr()
   325  }
   326  
   327  // injectComprehension evaluates and inserts embeddings. It first evaluates all
   328  // embeddings before inserting the results to ensure that the order of
   329  // evaluation does not matter.
   330  func (n *nodeContext) injectComprehensions(state vertexStatus) (progress bool) {
   331  	unreachableForDev(n.ctx)
   332  
   333  	workRemaining := false
   334  
   335  	// We use variables, instead of range, as the list may grow dynamically.
   336  	for i := 0; i < len(n.comprehensions); i++ {
   337  		d := &n.comprehensions[i]
   338  		if d.self || d.inserted {
   339  			continue
   340  		}
   341  		if err := n.processComprehension(d, state); err != nil {
   342  			// TODO:  Detect that the nodes are actually equal
   343  			if err.ForCycle && err.Value == n.node {
   344  				n.selfComprehensions = append(n.selfComprehensions, *d)
   345  				progress = true
   346  				d.self = true
   347  				return
   348  			}
   349  
   350  			d.err = err
   351  			workRemaining = true
   352  
   353  			continue
   354  
   355  			// TODO: add this when it can be done without breaking other
   356  			// things.
   357  			//
   358  			// // Add comprehension to ensure incomplete error is inserted.
   359  			// // This ensures that the error is reported in the Vertex
   360  			// // where the comprehension was defined, and not just in the
   361  			// // node below. This, in turn, is necessary to support
   362  			// // certain logic, like export, that expects to be able to
   363  			// // detect an "incomplete" error at the first level where it
   364  			// // is necessary.
   365  			// n := d.node.getNodeContext(ctx)
   366  			// n.addBottom(err)
   367  
   368  		}
   369  		progress = true
   370  	}
   371  
   372  	if !workRemaining {
   373  		n.comprehensions = n.comprehensions[:0] // Signal that all work is done.
   374  	}
   375  
   376  	return progress
   377  }
   378  
   379  // injectSelfComprehensions processes comprehensions that were earlier marked
   380  // as iterating over the node in which they are defined. Such comprehensions
   381  // are legal as long as they do not modify the arc set of the node.
   382  func (n *nodeContext) injectSelfComprehensions(state vertexStatus) {
   383  	unreachableForDev(n.ctx)
   384  
   385  	// We use variables, instead of range, as the list may grow dynamically.
   386  	for i := 0; i < len(n.selfComprehensions); i++ {
   387  		n.processComprehension(&n.selfComprehensions[i], state)
   388  	}
   389  	n.selfComprehensions = n.selfComprehensions[:0] // Signal that all work is done.
   390  }
   391  
   392  // processComprehension processes a single Comprehension conjunct.
   393  // It returns an incomplete error if there was one. Fatal errors are
   394  // processed as a "successfully" completed computation.
   395  func (n *nodeContext) processComprehension(d *envYield, state vertexStatus) *Bottom {
   396  	ctx := n.ctx
   397  
   398  	// Compute environments, if needed.
   399  	if !d.done {
   400  		var envs []*Environment
   401  		f := func(env *Environment) {
   402  			envs = append(envs, env)
   403  		}
   404  
   405  		if err := ctx.yield(d.vertex, d.env, d.comp, oldOnly(state), f); err != nil {
   406  			if err.IsIncomplete() {
   407  				return err
   408  			}
   409  
   410  			// continue to collect other errors.
   411  			d.done = true
   412  			d.inserted = true
   413  			if d.vertex != nil {
   414  				d.vertex.state.addBottom(err)
   415  				ctx.PopArc(d.vertex)
   416  			}
   417  			return nil
   418  		}
   419  
   420  		d.envs = envs
   421  
   422  		if len(d.envs) > 0 {
   423  			for _, s := range d.structs {
   424  				s.Init()
   425  			}
   426  		}
   427  		d.structs = nil
   428  		d.done = true
   429  	}
   430  
   431  	d.inserted = true
   432  
   433  	if len(d.envs) == 0 {
   434  		return nil
   435  	}
   436  
   437  	v := n.node
   438  	for c := d.leaf; c.parent != nil; c = c.parent {
   439  		v.updateArcType(c.arcType)
   440  		if v.ArcType == ArcNotPresent {
   441  			parent := v.Parent
   442  			b := parent.reportFieldCycleError(ctx, d.comp.Syntax.Pos(), v.Label)
   443  			d.envComprehension.vertex.state.addBottom(b)
   444  			ctx.current().err = b
   445  			ctx.current().state = taskFAILED
   446  			return nil
   447  		}
   448  		v = c.arc
   449  	}
   450  
   451  	id := d.id
   452  
   453  	for _, env := range d.envs {
   454  		if n.node.ArcType == ArcNotPresent {
   455  			b := n.node.reportFieldCycleError(ctx, d.comp.Syntax.Pos(), n.node.Label)
   456  			ctx.current().err = b
   457  			n.yield()
   458  			return nil
   459  		}
   460  
   461  		env = linkChildren(env, d.leaf)
   462  
   463  		if ctx.isDevVersion() {
   464  			n.scheduleConjunct(Conjunct{env, d.expr, id}, id)
   465  		} else {
   466  			n.addExprConjunct(Conjunct{env, d.expr, id}, state)
   467  		}
   468  	}
   469  
   470  	return nil
   471  }
   472  
   473  // linkChildren adds environments for the chain of vertices to a result
   474  // environment.
   475  func linkChildren(env *Environment, c *Comprehension) *Environment {
   476  	if c.parent != nil {
   477  		env = linkChildren(env, c.parent)
   478  		env = spawn(env, c.arc)
   479  	}
   480  	return env
   481  }
   482
View as plain text