eval.go

// Copyright 2021 CUE Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Package eval contains the high level CUE evaluation strategy.
//
// CUE allows for a significant amount of freedom in order of evaluation due to
// the commutativity of the unification operation. This package implements one
// of the possible strategies.
package adt

// TODO:
//   - result should be nodeContext: this allows optionals info to be extracted
//     and computed.
//

import (
	"fmt"
	"html/template"
	"strings"

	"cuelang.org/go/cue/ast"
	"cuelang.org/go/cue/errors"
	"cuelang.org/go/cue/token"
)

// TODO TODO TODO TODO TODO TODO  TODO TODO TODO  TODO TODO TODO  TODO TODO TODO
//
// - Reuse work from previous cycles. For instance, if we can guarantee that a
//   value is always correct for partial results, we can just process the arcs
//   going from Partial to Finalized, without having to reevaluate the value.
//
// - Test closedness far more thoroughly.
//

type Stats struct {
	DisjunctCount int
	UnifyCount    int

	Freed    int
	Retained int
	Reused   int
	Allocs   int
}

// Leaks reports the number of nodeContext structs leaked. These are typically
// benign, as they will just be garbage collected, as long as the pointer from
// the original nodes has been eliminated or the original nodes are also not
// referred to. But Leaks may have notable impact on performance, and thus
// should be avoided.
func (s *Stats) Leaks() int {
	return s.Allocs + s.Reused - s.Freed
}

var stats = template.Must(template.New("stats").Parse(`{{"" -}}

Leaks:  {{.Leaks}}
Freed:  {{.Freed}}
Reused: {{.Reused}}
Allocs: {{.Allocs}}
Retain: {{.Retained}}

Unifications: {{.UnifyCount}}
Disjuncts:    {{.DisjunctCount}}`))

func (s *Stats) String() string {
	buf := &strings.Builder{}
	_ = stats.Execute(buf, s)
	return buf.String()
}

func (c *OpContext) Stats() *Stats {
	return &c.stats
}

// TODO: Note: NewContext takes essentially a cue.Value. By making this
// type more central, we can perhaps avoid context creation.

// func NewContext(r Runtime, v *Vertex) *OpContext {
// 	e := NewUnifier(r)
// 	return e.NewContext(v)
// }

var structSentinel = &StructMarker{}

var incompleteSentinel = &Bottom{
	Code: IncompleteError,
	Err:  errors.Newf(token.NoPos, "incomplete"),
}

// evaluate returns the evaluated value associated with v. It may return a
// partial result. That is, if v was not yet unified, it may return a
// concrete value that must be the result assuming the configuration has no
// errors.
//
// This semantics allows CUE to break reference cycles in a straightforward
// manner.
//
// Vertex v must still be evaluated at some point to catch the underlying
// error.
//
// TODO: return *Vertex
func (c *OpContext) evaluate(v *Vertex, state VertexStatus) Value {
	if v.isUndefined() {
		// Use node itself to allow for cycle detection.
		c.Unify(v, state)
	}

	if n := v.state; n != nil {
		if n.errs != nil && !n.errs.IsIncomplete() {
			return n.errs
		}
		if n.scalar != nil && isCyclePlaceholder(v.BaseValue) {
			return n.scalar
		}
	}

	switch x := v.BaseValue.(type) {
	case *Bottom:
		if x.IsIncomplete() {
			c.AddBottom(x)
			return nil
		}
		return x

	case nil:
		if v.state != nil {
			switch x := v.state.getValidators().(type) {
			case Value:
				return x
			default:
				w := *v
				w.BaseValue = x
				return &w
			}
		}
		Assertf(false, "no BaseValue: state: %v; requested: %v", v.status, state)
	}

	if v.status < Finalized && v.state != nil {
		// TODO: errors are slightly better if we always add addNotify, but
		// in this case it is less likely to cause a performance penalty.
		// See https://github.com/cuelang/cue/issues/661. It may be possible to
		// relax this again once we have proper tests to prevent regressions of
		// that issue.
		if !v.state.done() || v.state.errs != nil {
			v.state.addNotify(c.vertex)
		}
	}

	return v
}

// Unify fully unifies all values of a Vertex to completion and stores
// the result in the Vertex. If unify was called on v before it returns
// the cached results.
func (c *OpContext) Unify(v *Vertex, state VertexStatus) {
	// defer c.PopVertex(c.PushVertex(v))

	// Ensure a node will always have a nodeContext after calling Unify if it is
	// not yet Finalized.
	n := v.getNodeContext(c)
	defer v.freeNode(n)

	if state <= v.Status() {
		if v.Status() != Partial && state != Partial {
			return
		}
	}

	switch v.Status() {
	case Evaluating:
		n.insertConjuncts()
		return

	case EvaluatingArcs:
		Assertf(v.status > 0, "unexpected status %d", v.status)
		return

	case 0:
		if v.Label.IsDef() {
			v.Closed = true
		}

		if v.Parent != nil {
			if v.Parent.Closed {
				v.Closed = true
			}
		}

		// TODO(perf): ideally we should always perform a closedness check if
		// state is Finalized. This is currently not possible when computing a
		// partial disjunction as the closedness information is not yet
		// complete, possibly leading to a disjunct to be rejected prematurely.
		// It is probably possible to fix this if we could add StructInfo
		// structures demarked per conjunct.
		//
		// In practice this should not be a problem: when disjuncts originate
		// from the same disjunct, they will have the same StructInfos, and thus
		// Equal is able to equate them even in the precense of optional field.
		// In general, combining any limited set of disjuncts will soon reach
		// a fixed point where duplicate elements can be eliminated this way.
		//
		// Note that not checking closedness is irrelevant for disjunctions of
		// scalars. This means it also doesn't hurt performance where structs
		// have a discriminator field (e.g. Kubernetes). We should take care,
		// though, that any potential performance issues are eliminated for
		// Protobuf-like oneOf fields.
		ignore := state != Finalized || n.skipNonMonotonicChecks()

		if !v.Label.IsInt() && v.Parent != nil && !ignore {
			// Visit arcs recursively to validate and compute error.
			if _, err := verifyArc2(c, v.Label, v, v.Closed); err != nil {
				// Record error in child node to allow recording multiple
				// conflicts at the appropriate place, to allow valid fields to
				// be represented normally and, most importantly, to avoid
				// recursive processing of a disallowed field.
				v.SetValue(c, Finalized, err)
				return
			}
		}

		defer c.PopArc(c.PushArc(v))

		c.stats.UnifyCount++

		// Clear any remaining error.
		if err := c.Err(); err != nil {
			panic("uncaught error")
		}

		// Set the cache to a cycle error to ensure a cyclic reference will result
		// in an error if applicable. A cyclic error may be ignored for
		// non-expression references. The cycle error may also be removed as soon
		// as there is evidence what a correct value must be, but before all
		// validation has taken place.
		//
		// TODO(cycle): having a more recursive algorithm would make this
		// special cycle handling unnecessary.
		v.BaseValue = cycle

		v.UpdateStatus(Evaluating)

		n.conjuncts = v.Conjuncts
		n.insertConjuncts()

		fallthrough

	case Partial:
		defer c.PopArc(c.PushArc(v))

		v.status = Evaluating

		// Use maybeSetCache for cycle breaking
		for n.maybeSetCache(); n.expandOne(); n.maybeSetCache() {
		}

		n.doNotify()

		if !n.done() {
			switch {
			case len(n.disjunctions) > 0 && isCyclePlaceholder(v.BaseValue):
				// We disallow entering computations of disjunctions with
				// incomplete data.
				if state == Finalized {
					b := c.NewErrf("incomplete cause disjunction")
					b.Code = IncompleteError
					n.errs = CombineErrors(nil, n.errs, b)
					v.SetValue(n.ctx, Finalized, b)
				} else {
					n.node.UpdateStatus(Partial)
				}
				return

			case state <= AllArcs:
				n.node.UpdateStatus(Partial)
				return
			}
		}

		if s := v.Status(); state <= s {
			// We have found a partial result. There may still be errors
			// down the line which may result from further evaluating this
			// field, but that will be caught when evaluating this field
			// for real.

			// This also covers the case where a recursive evaluation triggered
			// this field to become finalized in the mean time. In that case
			// we can avoid running another expandDisjuncts.
			return
		}

		// Disjunctions should always be finalized. If there are nested
		// disjunctions the last one should be finalized.
		disState := state
		if len(n.disjunctions) > 0 && disState != Finalized {
			disState = Finalized
		}
		n.expandDisjuncts(disState, n, maybeDefault, false, true)

		n.finalizeDisjuncts()

		switch len(n.disjuncts) {
		case 0:
		case 1:
			x := n.disjuncts[0].result
			x.state = nil
			*v = x

		default:
			d := n.createDisjunct()
			v.BaseValue = d
			// The conjuncts will have too much information. Better have no
			// information than incorrect information.
			for _, d := range d.Values {
				// We clear the conjuncts for now. As these disjuncts are for API
				// use only, we will fill them out when necessary (using Defaults).
				d.Conjuncts = nil

				// TODO: use a more principled form of dereferencing. For instance,
				// disjuncts could already be assumed to be the given Vertex, and
				// the the main vertex could be dereferenced during evaluation.
				for _, a := range d.Arcs {
					for _, x := range a.Conjuncts {
						// All the environments for embedded structs need to be
						// dereferenced.
						for env := x.Env; env != nil && env.Vertex == v; env = env.Up {
							env.Vertex = d
						}
					}
				}
			}
			v.Arcs = nil
			// v.Structs = nil // TODO: should we keep or discard the Structs?
			// TODO: how to represent closedness information? Do we need it?
		}

		// If the state has changed, it is because a disjunct has been run, or
		// because a single disjunct has replaced it. Restore the old state as
		// to not confuse memory management.
		v.state = n

		// We don't do this in postDisjuncts, as it should only be done after
		// completing all disjunctions.
		if !n.done() {
			if err := n.incompleteErrors(); err != nil {
				b, _ := n.node.BaseValue.(*Bottom)
				if b != err {
					err = CombineErrors(n.ctx.src, b, err)
				}
				n.node.BaseValue = err
			}
		}

		if state != Finalized {
			return
		}

		if v.BaseValue == nil {
			v.BaseValue = n.getValidators()
		}

		// Free memory here?
		v.UpdateStatus(Finalized)

	case AllArcs:
		defer c.PopArc(c.PushArc(v))

		n.completeArcs(state)

	case Finalized:
	}
}

// insertConjuncts inserts conjuncts previously uninserted.
func (n *nodeContext) insertConjuncts() {
	for len(n.conjuncts) > 0 {
		nInfos := len(n.node.Structs)
		p := &n.conjuncts[0]
		n.conjuncts = n.conjuncts[1:]
		n.addExprConjunct(*p)

		// Record the OptionalTypes for all structs that were inferred by this
		// Conjunct. This information can be used by algorithms such as trim.
		for i := nInfos; i < len(n.node.Structs); i++ {
			p.CloseInfo.FieldTypes |= n.node.Structs[i].types
		}
	}
}

// finalizeDisjuncts: incomplete errors are kept around and not removed early.
// This call filters the incomplete errors and removes them
//
// This also collects all errors of empty disjunctions. These cannot be
// collected during the finalization state of individual disjuncts. Care should
// be taken to only call this after all disjuncts have been finalized.
func (n *nodeContext) finalizeDisjuncts() {
	a := n.disjuncts
	if len(a) == 0 {
		return
	}
	k := 0
	for i, d := range a {
		switch d.finalDone() {
		case true:
			a[k], a[i] = d, a[k]
			k++
		default:
			if err := d.incompleteErrors(); err != nil {
				n.disjunctErrs = append(n.disjunctErrs, err)
			}
		}
		d.free()
	}
	if k == 0 {
		n.makeError()
	}
	n.disjuncts = a[:k]
}

func (n *nodeContext) doNotify() {
	if n.errs == nil || len(n.notify) == 0 {
		return
	}
	for _, v := range n.notify {
		if v.state == nil {
			if b, ok := v.BaseValue.(*Bottom); ok {
				v.BaseValue = CombineErrors(nil, b, n.errs)
			} else {
				v.BaseValue = n.errs
			}
		} else {
			v.state.addBottom(n.errs)
		}
	}
	n.notify = n.notify[:0]
}

func (n *nodeContext) postDisjunct(state VertexStatus) {
	ctx := n.ctx

	for {
		// Use maybeSetCache for cycle breaking
		for n.maybeSetCache(); n.expandOne(); n.maybeSetCache() {
		}

		if aList, id := n.addLists(); aList != nil {
			n.updateNodeType(ListKind, aList, id)
		} else {
			break
		}
	}

	if n.aStruct != nil {
		n.updateNodeType(StructKind, n.aStruct, n.aStructID)
	}

	switch err := n.getErr(); {
	case err != nil:
		n.node.BaseValue = err
		n.errs = nil

	default:
		if isCyclePlaceholder(n.node.BaseValue) {
			if !n.done() {
				n.node.BaseValue = n.incompleteErrors()
			} else {
				n.node.BaseValue = nil
			}
		}
		// TODO: this ideally should be done here. However, doing so causes
		// a somewhat more aggressive cutoff in disjunction cycles, which cause
		// some incompatibilities. Fix in another CL.
		//
		// else if !n.done() {
		// 	n.expandOne()
		// 	if err := n.incompleteErrors(); err != nil {
		// 		n.node.BaseValue = err
		// 	}
		// }

		// We are no longer evaluating.
		// n.node.UpdateStatus(Partial)
		n.node.UpdateStatus(Evaluating)

		// Either set to Conjunction or error.
		// TODO: verify and simplify the below code to determine whether
		// something is a struct.
		markStruct := false
		if n.aStruct != nil {
			markStruct = true
		} else if len(n.node.Structs) > 0 {
			markStruct = n.kind&StructKind != 0 && !n.hasTop
		}
		v := n.node.Value()
		if n.node.BaseValue == nil && markStruct {
			n.node.BaseValue = &StructMarker{}
			v = n.node
		}
		if v != nil && IsConcrete(v) {
			// Also check when we already have errors as we may find more
			// serious errors and would like to know about all errors anyway.

			if n.lowerBound != nil {
				if b := ctx.Validate(n.lowerBound, v); b != nil {
					// TODO(errors): make Validate return boolean and generate
					// optimized conflict message. Also track and inject IDs
					// to determine origin location.s
					if e, _ := b.Err.(*ValueError); e != nil {
						e.AddPosition(n.lowerBound)
						e.AddPosition(v)
					}
					n.addBottom(b)
				}
			}
			if n.upperBound != nil {
				if b := ctx.Validate(n.upperBound, v); b != nil {
					// TODO(errors): make Validate return boolean and generate
					// optimized conflict message. Also track and inject IDs
					// to determine origin location.s
					if e, _ := b.Err.(*ValueError); e != nil {
						e.AddPosition(n.upperBound)
						e.AddPosition(v)
					}
					n.addBottom(b)
				}
			}
			// MOVE BELOW
			// TODO(perf): only delay processing of actual non-monotonic checks.
			skip := n.skipNonMonotonicChecks()
			if v := n.node.Value(); v != nil && IsConcrete(v) && !skip {
				for _, v := range n.checks {
					// TODO(errors): make Validate return bottom and generate
					// optimized conflict message. Also track and inject IDs
					// to determine origin location.s
					if b := ctx.Validate(v, n.node); b != nil {
						n.addBottom(b)
					}
				}
			}
		} else if state == Finalized {
			n.node.BaseValue = n.getValidators()
		}

		if v == nil {
			break
		}

		switch {
		case v.Kind() == ListKind:
			for _, a := range n.node.Arcs {
				if a.Label.Typ() == StringLabel {
					n.addErr(ctx.Newf("list may not have regular fields"))
					// TODO(errors): add positions for list and arc definitions.

				}
			}

			// case !isStruct(n.node) && v.Kind() != BottomKind:
			// 	for _, a := range n.node.Arcs {
			// 		if a.Label.IsRegular() {
			// 			n.addErr(errors.Newf(token.NoPos,
			// 				// TODO(errors): add positions of non-struct values and arcs.
			// 				"cannot combine scalar values with arcs"))
			// 		}
			// 	}
		}
	}

	if err := n.getErr(); err != nil {
		if b, _ := n.node.BaseValue.(*Bottom); b != nil {
			err = CombineErrors(nil, b, err)
		}
		n.node.BaseValue = err
		// TODO: add return: if evaluation of arcs is important it can be done
		// later. Logically we're done.
	}

	n.completeArcs(state)
}

func (n *nodeContext) incompleteErrors() *Bottom {
	// collect incomplete errors.
	var err *Bottom // n.incomplete
	for _, d := range n.dynamicFields {
		err = CombineErrors(nil, err, d.err)
	}
	for _, c := range n.forClauses {
		err = CombineErrors(nil, err, c.err)
	}
	for _, c := range n.ifClauses {
		err = CombineErrors(nil, err, c.err)
	}
	for _, x := range n.exprs {
		err = CombineErrors(nil, err, x.err)
	}
	if err == nil {
		// safeguard.
		err = incompleteSentinel
	}
	return err
}

func (n *nodeContext) completeArcs(state VertexStatus) {

	if state <= AllArcs {
		n.node.UpdateStatus(AllArcs)
		return
	}

	n.node.UpdateStatus(EvaluatingArcs)

	ctx := n.ctx

	if cyclic := n.hasCycle && !n.hasNonCycle; cyclic {
		n.node.BaseValue = CombineErrors(nil,
			n.node.Value(),
			&Bottom{
				Code:  StructuralCycleError,
				Err:   ctx.Newf("structural cycle"),
				Value: n.node.Value(),
				// TODO: probably, this should have the referenced arc.
			})
		// Don't process Arcs. This is mostly to ensure that no Arcs with
		// an Unprocessed status remain in the output.
		n.node.Arcs = nil
	} else {
		// Visit arcs recursively to validate and compute error.
		for _, a := range n.node.Arcs {
			if a.nonMonotonicInsertGen >= a.nonMonotonicLookupGen && a.nonMonotonicLookupGen > 0 {
				err := ctx.Newf(
					"cycle: new field %s inserted by if clause that was previously evaluated by another if clause", a.Label.SelectorString(ctx))
				err.AddPosition(n.node)
				n.node.BaseValue = &Bottom{Err: err}
			} else if a.nonMonotonicReject {
				err := ctx.Newf(
					"cycle: field %s was added after an if clause evaluated it",
					a.Label.SelectorString(ctx))
				err.AddPosition(n.node)
				n.node.BaseValue = &Bottom{Err: err}
			}

			// Call UpdateStatus here to be absolutely sure the status is set
			// correctly and that we are not regressing.
			n.node.UpdateStatus(EvaluatingArcs)
			ctx.Unify(a, state)
			// Don't set the state to Finalized if the child arcs are not done.
			if state == Finalized && a.status < Finalized {
				state = AllArcs
			}
			if err, _ := a.BaseValue.(*Bottom); err != nil {
				n.node.AddChildError(err)
			}
		}
	}

	n.node.UpdateStatus(state)
}

// TODO: this is now a sentinel. Use a user-facing error that traces where
// the cycle originates.
var cycle = &Bottom{
	Err:  errors.Newf(token.NoPos, "cycle error"),
	Code: CycleError,
}

func isCyclePlaceholder(v BaseValue) bool {
	return v == cycle
}

func (n *nodeContext) createDisjunct() *Disjunction {
	a := make([]*Vertex, len(n.disjuncts))
	p := 0
	hasDefaults := false
	for i, x := range n.disjuncts {
		v := new(Vertex)
		*v = x.result
		v.state = nil
		switch x.defaultMode {
		case isDefault:
			a[i] = a[p]
			a[p] = v
			p++
			hasDefaults = true

		case notDefault:
			hasDefaults = true
			fallthrough
		case maybeDefault:
			a[i] = v
		}
	}
	// TODO: disambiguate based on concrete values.
	// TODO: consider not storing defaults.
	// if p > 0 {
	// 	a = a[:p]
	// }
	return &Disjunction{
		Values:      a,
		NumDefaults: p,
		HasDefaults: hasDefaults,
	}
}

type arcKey struct {
	arc *Vertex
	id  CloseInfo
}

// A nodeContext is used to collate all conjuncts of a value to facilitate
// unification. Conceptually order of unification does not matter. However,
// order has relevance when performing checks of non-monotic properities. Such
// checks should only be performed once the full value is known.
type nodeContext struct {
	nextFree *nodeContext
	refCount int

	ctx  *OpContext
	node *Vertex

	// usedArcs is a list of arcs that were looked up during non-monotonic operations, but do not exist yet.
	usedArcs []*Vertex

	// TODO: (this is CL is first step)
	// filter *Vertex a subset of composite with concrete fields for
	// bloom-like filtering of disjuncts. We should first verify, however,
	// whether some breath-first search gives sufficient performance, as this
	// should already ensure a quick-fail for struct disjunctions with
	// discriminators.

	arcMap []arcKey

	// snapshot holds the last value of the vertex before calling postDisjunct.
	snapshot Vertex

	// Result holds the last evaluated value of the vertex after calling
	// postDisjunct.
	result Vertex

	// Current value (may be under construction)
	scalar   Value // TODO: use Value in node.
	scalarID CloseInfo

	// Concrete conjuncts
	kind       Kind
	kindExpr   Expr        // expr that adjust last value (for error reporting)
	kindID     CloseInfo   // for error tracing
	lowerBound *BoundValue // > or >=
	upperBound *BoundValue // < or <=
	checks     []Validator // BuiltinValidator, other bound values.
	errs       *Bottom

	// Conjuncts holds a reference to the Vertex Arcs that still need
	// processing. It does NOT need to be copied.
	conjuncts []Conjunct

	// notify is used to communicate errors in cyclic dependencies.
	// TODO: also use this to communicate increasingly more concrete values.
	notify []*Vertex

	// Struct information
	dynamicFields []envDynamic
	ifClauses     []envYield
	forClauses    []envYield
	aStruct       Expr
	aStructID     CloseInfo

	// Expression conjuncts
	lists  []envList
	vLists []*Vertex
	exprs  []envExpr

	hasTop      bool
	hasCycle    bool // has conjunct with structural cycle
	hasNonCycle bool // has conjunct without structural cycle

	// Disjunction handling
	disjunctions []envDisjunct

	// usedDefault indicates the for each of possibly multiple parent
	// disjunctions whether it is unified with a default disjunct or not.
	// This is then later used to determine whether a disjunction should
	// be treated as a marked disjunction.
	usedDefault []defaultInfo

	defaultMode  defaultMode
	disjuncts    []*nodeContext
	buffer       []*nodeContext
	disjunctErrs []*Bottom
}

type defaultInfo struct {
	// parentMode indicates whether this values was used as a default value,
	// based on the parent mode.
	parentMode defaultMode

	// The result of default evaluation for a nested disjunction.
	nestedMode defaultMode

	origMode defaultMode
}

func (n *nodeContext) addNotify(v *Vertex) {
	if v != nil {
		n.notify = append(n.notify, v)
	}
}

func (n *nodeContext) clone() *nodeContext {
	d := n.ctx.newNodeContext(n.node)

	d.refCount++

	d.ctx = n.ctx
	d.node = n.node

	d.scalar = n.scalar
	d.scalarID = n.scalarID
	d.kind = n.kind
	d.kindExpr = n.kindExpr
	d.kindID = n.kindID
	d.aStruct = n.aStruct
	d.aStructID = n.aStructID
	d.hasTop = n.hasTop

	d.lowerBound = n.lowerBound
	d.upperBound = n.upperBound
	d.errs = n.errs
	d.hasTop = n.hasTop
	d.hasCycle = n.hasCycle
	d.hasNonCycle = n.hasNonCycle

	// d.arcMap = append(d.arcMap, n.arcMap...) // XXX add?
	// d.usedArcs = append(d.usedArcs, n.usedArcs...) // XXX: add?
	d.notify = append(d.notify, n.notify...)
	d.checks = append(d.checks, n.checks...)
	d.dynamicFields = append(d.dynamicFields, n.dynamicFields...)
	d.ifClauses = append(d.ifClauses, n.ifClauses...)
	d.forClauses = append(d.forClauses, n.forClauses...)
	d.lists = append(d.lists, n.lists...)
	d.vLists = append(d.vLists, n.vLists...)
	d.exprs = append(d.exprs, n.exprs...)
	d.usedDefault = append(d.usedDefault, n.usedDefault...)

	// No need to clone d.disjunctions

	return d
}

func (c *OpContext) newNodeContext(node *Vertex) *nodeContext {
	if n := c.freeListNode; n != nil {
		c.stats.Reused++
		c.freeListNode = n.nextFree

		*n = nodeContext{
			ctx:           c,
			node:          node,
			kind:          TopKind,
			usedArcs:      n.usedArcs[:0],
			arcMap:        n.arcMap[:0],
			notify:        n.notify[:0],
			checks:        n.checks[:0],
			dynamicFields: n.dynamicFields[:0],
			ifClauses:     n.ifClauses[:0],
			forClauses:    n.forClauses[:0],
			lists:         n.lists[:0],
			vLists:        n.vLists[:0],
			exprs:         n.exprs[:0],
			disjunctions:  n.disjunctions[:0],
			usedDefault:   n.usedDefault[:0],
			disjunctErrs:  n.disjunctErrs[:0],
			disjuncts:     n.disjuncts[:0],
			buffer:        n.buffer[:0],
		}

		return n
	}
	c.stats.Allocs++

	return &nodeContext{
		ctx:  c,
		node: node,
		kind: TopKind,
	}
}

func (v *Vertex) getNodeContext(c *OpContext) *nodeContext {
	if v.state == nil {
		if v.status == Finalized {
			return nil
		}
		v.state = c.newNodeContext(v)
	} else if v.state.node != v {
		panic("getNodeContext: nodeContext out of sync")
	}
	v.state.refCount++
	return v.state
}

func (v *Vertex) freeNode(n *nodeContext) {
	if n == nil {
		return
	}
	if n.node != v {
		panic("freeNode: unpaired free")
	}
	if v.state != nil && v.state != n {
		panic("freeNode: nodeContext out of sync")
	}
	if n.refCount--; n.refCount == 0 {
		if v.status == Finalized {
			v.freeNodeState()
		} else {
			n.ctx.stats.Retained++
		}
	}
}

func (v *Vertex) freeNodeState() {
	if v.state == nil {
		return
	}
	state := v.state
	v.state = nil

	state.ctx.freeNodeContext(state)
}

func (n *nodeContext) free() {
	if n.refCount--; n.refCount == 0 {
		n.ctx.freeNodeContext(n)
	}
}

func (c *OpContext) freeNodeContext(n *nodeContext) {
	c.stats.Freed++
	n.nextFree = c.freeListNode
	c.freeListNode = n
	n.node = nil
	n.refCount = 0
}

// TODO(perf): return a dedicated ConflictError that can track original
// positions on demand.
func (n *nodeContext) addConflict(
	v1, v2 Node,
	k1, k2 Kind,
	id1, id2 CloseInfo) {

	ctx := n.ctx

	var err *ValueError
	if k1 == k2 {
		err = ctx.NewPosf(token.NoPos,
			"conflicting values %s and %s", ctx.Str(v1), ctx.Str(v2))
	} else {
		err = ctx.NewPosf(token.NoPos,
			"conflicting values %s and %s (mismatched types %s and %s)",
			ctx.Str(v1), ctx.Str(v2), k1, k2)
	}

	err.AddPosition(v1)
	err.AddPosition(v2)
	err.AddClosedPositions(id1)
	err.AddClosedPositions(id2)

	n.addErr(err)
}

func (n *nodeContext) updateNodeType(k Kind, v Expr, id CloseInfo) bool {
	ctx := n.ctx
	kind := n.kind & k

	switch {
	case n.kind == BottomKind,
		k == BottomKind:
		return false

	case kind == BottomKind:
		if n.kindExpr != nil {
			n.addConflict(n.kindExpr, v, n.kind, k, n.kindID, id)
		} else {
			n.addErr(ctx.Newf(
				"conflicting value %s (mismatched types %s and %s)",
				ctx.Str(v), n.kind, k))
		}
	}

	if n.kind != kind || n.kindExpr == nil {
		n.kindExpr = v
	}
	n.kind = kind
	return kind != BottomKind
}

func (n *nodeContext) done() bool {
	return len(n.dynamicFields) == 0 &&
		len(n.ifClauses) == 0 &&
		len(n.forClauses) == 0 &&
		len(n.exprs) == 0
}

// finalDone is like done, but allows for cycle errors, which can be ignored
// as they essentially indicate a = a & _.
func (n *nodeContext) finalDone() bool {
	for _, x := range n.exprs {
		if x.err.Code != CycleError {
			return false
		}
	}
	return len(n.dynamicFields) == 0 &&
		len(n.ifClauses) == 0 &&
		len(n.forClauses) == 0
}

// hasErr is used to determine if an evaluation path, for instance a single
// path after expanding all disjunctions, has an error.
func (n *nodeContext) hasErr() bool {
	if n.node.ChildErrors != nil {
		return true
	}
	if n.node.Status() > Evaluating && n.node.IsErr() {
		return true
	}
	return n.ctx.HasErr() || n.errs != nil
}

func (n *nodeContext) getErr() *Bottom {
	n.errs = CombineErrors(nil, n.errs, n.ctx.Err())
	return n.errs
}

// getValidators sets the vertex' Value in case there was no concrete value.
func (n *nodeContext) getValidators() BaseValue {
	ctx := n.ctx

	a := []Value{}
	// if n.node.Value != nil {
	// 	a = append(a, n.node.Value)
	// }
	kind := TopKind
	if n.lowerBound != nil {
		a = append(a, n.lowerBound)
		kind &= n.lowerBound.Kind()
	}
	if n.upperBound != nil {
		a = append(a, n.upperBound)
		kind &= n.upperBound.Kind()
	}
	for _, c := range n.checks {
		// Drop !=x if x is out of bounds with another bound.
		if b, _ := c.(*BoundValue); b != nil && b.Op == NotEqualOp {
			if n.upperBound != nil &&
				SimplifyBounds(ctx, n.kind, n.upperBound, b) != nil {
				continue
			}
			if n.lowerBound != nil &&
				SimplifyBounds(ctx, n.kind, n.lowerBound, b) != nil {
				continue
			}
		}
		a = append(a, c)
		kind &= c.Kind()
	}
	if kind&^n.kind != 0 {
		a = append(a, &BasicType{K: n.kind})
	}

	var v BaseValue
	switch len(a) {
	case 0:
		// Src is the combined input.
		v = &BasicType{K: n.kind}

	case 1:
		v = a[0].(Value) // remove cast

	default:
		v = &Conjunction{Values: a}
	}

	return v
}

// TODO: this function can probably go as this is now handled in the nodeContext.
func (n *nodeContext) maybeSetCache() {
	if n.node.Status() > Partial { // n.node.BaseValue != nil
		return
	}
	if n.scalar != nil {
		n.node.BaseValue = n.scalar
	}
	// NOTE: this is now handled by associating the nodeContext
	// if n.errs != nil {
	// 	n.node.SetValue(n.ctx, Partial, n.errs)
	// }
}

type envExpr struct {
	c   Conjunct
	err *Bottom
}

type envDynamic struct {
	env   *Environment
	field *DynamicField
	id    CloseInfo
	err   *Bottom
}

type envYield struct {
	env   *Environment
	yield Yielder
	id    CloseInfo
	err   *Bottom
}

type envList struct {
	env     *Environment
	list    *ListLit
	n       int64 // recorded length after evaluator
	elipsis *Ellipsis
	id      CloseInfo
}

func (n *nodeContext) addBottom(b *Bottom) {
	n.errs = CombineErrors(nil, n.errs, b)
	// TODO(errors): consider doing this
	// n.kindExpr = n.errs
	// n.kind = 0
}

func (n *nodeContext) addErr(err errors.Error) {
	if err != nil {
		n.addBottom(&Bottom{Err: err})
	}
}

// addExprConjuncts will attempt to evaluate an Expr and insert the value
// into the nodeContext if successful or queue it for later evaluation if it is
// incomplete or is not value.
func (n *nodeContext) addExprConjunct(v Conjunct) {
	env := v.Env
	id := v.CloseInfo

	switch x := v.Expr().(type) {
	case *Vertex:
		if x.IsData() {
			n.addValueConjunct(env, x, id)
		} else {
			n.addVertexConjuncts(env, id, x, x, true)
		}

	case Value:
		n.addValueConjunct(env, x, id)

	case *BinaryExpr:
		if x.Op == AndOp {
			n.addExprConjunct(MakeConjunct(env, x.X, id))
			n.addExprConjunct(MakeConjunct(env, x.Y, id))
		} else {
			n.evalExpr(v)
		}

	case *StructLit:
		n.addStruct(env, x, id)

	case *ListLit:
		n.lists = append(n.lists, envList{env: env, list: x, id: id})

	case *DisjunctionExpr:
		n.addDisjunction(env, x, id)

	default:
		// Must be Resolver or Evaluator.
		n.evalExpr(v)
	}
}

// evalExpr is only called by addExprConjunct. If an error occurs, it records
// the error in n and returns nil.
func (n *nodeContext) evalExpr(v Conjunct) {
	// Require an Environment.
	ctx := n.ctx

	closeID := v.CloseInfo

	// TODO: see if we can do without these counters.
	for _, d := range v.Env.Deref {
		d.EvalCount++
	}
	for _, d := range v.Env.Cycles {
		d.SelfCount++
	}
	defer func() {
		for _, d := range v.Env.Deref {
			d.EvalCount--
		}
		for _, d := range v.Env.Cycles {
			d.SelfCount++
		}
	}()

	switch x := v.Expr().(type) {
	case Resolver:
		arc, err := ctx.Resolve(v.Env, x)
		if err != nil && !err.IsIncomplete() {
			n.addBottom(err)
			break
		}
		if arc == nil {
			n.exprs = append(n.exprs, envExpr{v, err})
			break
		}

		n.addVertexConjuncts(v.Env, v.CloseInfo, v.Expr(), arc, false)

	case Evaluator:
		// Interpolation, UnaryExpr, BinaryExpr, CallExpr
		// Could be unify?
		val := ctx.evaluateRec(v.Env, v.Expr(), Partial)
		if b, ok := val.(*Bottom); ok && b.IsIncomplete() {
			n.exprs = append(n.exprs, envExpr{v, b})
			break
		}

		if v, ok := val.(*Vertex); ok {
			// Handle generated disjunctions (as in the 'or' builtin).
			// These come as a Vertex, but should not be added as a value.
			b, ok := v.BaseValue.(*Bottom)
			if ok && b.IsIncomplete() && len(v.Conjuncts) > 0 {
				for _, c := range v.Conjuncts {
					c.CloseInfo = closeID
					n.addExprConjunct(c)
				}
				break
			}
		}

		// TODO: also to through normal Vertex handling here. At the moment
		// addValueConjunct handles StructMarker.NeedsClose, as this is always
		// only needed when evaluation an Evaluator, and not a Resolver.
		// The two code paths should ideally be merged once this separate
		// mechanism is eliminated.
		//
		// if arc, ok := val.(*Vertex); ok && !arc.IsData() {
		// 	n.addVertexConjuncts(v.Env, closeID, v.Expr(), arc)
		// 	break
		// }

		// TODO: insert in vertex as well
		n.addValueConjunct(v.Env, val, closeID)

	default:
		panic(fmt.Sprintf("unknown expression of type %T", x))
	}
}

func (n *nodeContext) addVertexConjuncts(env *Environment, closeInfo CloseInfo, x Expr, arc *Vertex, inline bool) {

	// We need to ensure that each arc is only unified once (or at least) a
	// bounded time, witch each conjunct. Comprehensions, for instance, may
	// distribute a value across many values that get unified back into the
	// same value. If such a value is a disjunction, than a disjunction of N
	// disjuncts will result in a factor N more unifications for each
	// occurrence of such value, resulting in exponential running time. This
	// is especially common values that are used as a type.
	//
	// However, unification is idempotent, so each such conjunct only needs
	// to be unified once. This cache checks for this and prevents an
	// exponential blowup in such case.
	//
	// TODO(perf): this cache ensures the conjuncts of an arc at most once
	// per ID. However, we really need to add the conjuncts of an arc only
	// once total, and then add the close information once per close ID
	// (pointer can probably be shared). Aside from being more performant,
	// this is probably the best way to guarantee that conjunctions are
	// linear in this case.
	key := arcKey{arc, closeInfo}
	for _, k := range n.arcMap {
		if key == k {
			return
		}
	}
	n.arcMap = append(n.arcMap, key)

	// Pass detection of structural cycles from parent to children.
	cyclic := false
	if env != nil {
		// If a reference is in a tainted set, so is the value it refers to.
		cyclic = env.Cyclic
	}

	status := arc.Status()

	switch status {
	case Evaluating:
		// Reference cycle detected. We have reached a fixed point and
		// adding conjuncts at this point will not change the value. Also,
		// continuing to pursue this value will result in an infinite loop.

		// TODO: add a mechanism so that the computation will only have to
		// be done once?

		if arc == n.node {
			// TODO: we could use node sharing here. This may avoid an
			// exponential blowup during evaluation, like is possible with
			// YAML.
			return
		}

	case EvaluatingArcs:
		// Structural cycle detected. Continue evaluation as usual, but
		// keep track of whether any other conjuncts without structural
		// cycles are added. If not, evaluation of child arcs will end
		// with this node.

		// For the purpose of determining whether at least one non-cyclic
		// conjuncts exists, we consider all conjuncts of a cyclic conjuncts
		// also cyclic.

		cyclic = true
		n.hasCycle = true

		// As the EvaluatingArcs mechanism bypasses the self-reference
		// mechanism, we need to separately keep track of it here.
		// If this (originally) is a self-reference node, adding them
		// will result in recursively adding the same reference. For this
		// we also mark the node as evaluating.
		if arc.SelfCount > 0 {
			return
		}

		// This count is added for values that are directly added below.
		// The count is handled separately for delayed values.
		arc.SelfCount++
		defer func() { arc.SelfCount-- }()
	}

	closeInfo = closeInfo.SpawnRef(arc, IsDef(x), x)

	if arc.status == 0 && !inline {
		// This is a rare condition, but can happen in certain
		// evaluation orders. Unfortunately, adding this breaks
		// resolution of cyclic mutually referring disjunctions. But it
		// is necessary to prevent lookups in unevaluated structs.
		// TODO(cycles): this can probably most easily be fixed with a
		// having a more recursive implementation.
		n.ctx.Unify(arc, AllArcs)
	}

	for _, c := range arc.Conjuncts {
		var a []*Vertex
		if env != nil {
			a = env.Deref
		}
		if inline {
			c = updateCyclic(c, cyclic, nil, nil)
		} else {
			c = updateCyclic(c, cyclic, arc, a)
		}

		// Note that we are resetting the tree here. We hereby assume that
		// closedness conflicts resulting from unifying the referenced arc were
		// already caught there and that we can ignore further errors here.
		c.CloseInfo = closeInfo
		n.addExprConjunct(c)
	}
}

// isDef reports whether an expressions is a reference that references a
// definition anywhere in its selection path.
//
// TODO(performance): this should be merged with resolve(). But for now keeping
// this code isolated makes it easier to see what it is for.
func isDef(x Expr) bool {
	switch r := x.(type) {
	case *FieldReference:
		return r.Label.IsDef()

	case *SelectorExpr:
		if r.Sel.IsDef() {
			return true
		}
		return isDef(r.X)

	case *IndexExpr:
		return isDef(r.X)
	}
	return false
}

// updateCyclicStatus looks for proof of non-cyclic conjuncts to override
// a structural cycle.
func (n *nodeContext) updateCyclicStatus(env *Environment) {
	if env == nil || !env.Cyclic {
		n.hasNonCycle = true
	}
}

func updateCyclic(c Conjunct, cyclic bool, deref *Vertex, a []*Vertex) Conjunct {
	env := c.Env
	switch {
	case env == nil:
		if !cyclic && deref == nil {
			return c
		}
		env = &Environment{Cyclic: cyclic}
	case deref == nil && env.Cyclic == cyclic && len(a) == 0:
		return c
	default:
		// The conjunct may still be in use in other fields, so we should
		// make a new copy to mark Cyclic only for this case.
		e := *env
		e.Cyclic = e.Cyclic || cyclic
		env = &e
	}
	if deref != nil || len(a) > 0 {
		cp := make([]*Vertex, 0, len(a)+1)
		cp = append(cp, a...)
		if deref != nil {
			cp = append(cp, deref)
		}
		env.Deref = cp
	}
	if deref != nil {
		env.Cycles = append(env.Cycles, deref)
	}
	return MakeConjunct(env, c.Expr(), c.CloseInfo)
}

func (n *nodeContext) addValueConjunct(env *Environment, v Value, id CloseInfo) {
	n.updateCyclicStatus(env)

	ctx := n.ctx

	if x, ok := v.(*Vertex); ok {
		if m, ok := x.BaseValue.(*StructMarker); ok {
			n.aStruct = x
			n.aStructID = id
			if m.NeedClose {
				id = id.SpawnRef(x, IsDef(x), x)
				id.IsClosed = true
			}
		}

		cyclic := env != nil && env.Cyclic

		if !x.IsData() {
			// TODO: this really shouldn't happen anymore.
			if isComplexStruct(ctx, x) {
				// This really shouldn't happen, but just in case.
				n.addVertexConjuncts(env, id, x, x, true)
				return
			}

			for _, c := range x.Conjuncts {
				c = updateCyclic(c, cyclic, nil, nil)
				c.CloseInfo = id
				n.addExprConjunct(c) // TODO: Pass from eval
			}
			return
		}

		// TODO: evaluate value?
		switch v := x.BaseValue.(type) {
		default:
			panic(fmt.Sprintf("invalid type %T", x.BaseValue))

		case *ListMarker:
			n.vLists = append(n.vLists, x)
			return

		case *StructMarker:

		case Value:
			n.addValueConjunct(env, v, id)
		}

		if len(x.Arcs) == 0 {
			return
		}

		s := &StructLit{}

		// Keep ordering of Go struct for topological sort.
		n.node.AddStruct(s, env, id)
		n.node.Structs = append(n.node.Structs, x.Structs...)

		for _, a := range x.Arcs {
			// TODO(errors): report error when this is a regular field.
			c := MakeConjunct(nil, a, id)
			c = updateCyclic(c, cyclic, nil, nil)
			n.insertField(a.Label, c)
			s.MarkField(a.Label)
		}
		return
	}

	switch b := v.(type) {
	case *Bottom:
		n.addBottom(b)
		return
	case *Builtin:
		if v := b.BareValidator(); v != nil {
			n.addValueConjunct(env, v, id)
			return
		}
	}

	if !n.updateNodeType(v.Kind(), v, id) {
		return
	}

	switch x := v.(type) {
	case *Disjunction:
		n.addDisjunctionValue(env, x, id)

	case *Conjunction:
		for _, x := range x.Values {
			n.addValueConjunct(env, x, id)
		}

	case *Top:
		n.hasTop = true

	case *BasicType:
		// handled above

	case *BoundValue:
		switch x.Op {
		case LessThanOp, LessEqualOp:
			if y := n.upperBound; y != nil {
				n.upperBound = nil
				v := SimplifyBounds(ctx, n.kind, x, y)
				if err := valueError(v); err != nil {
					err.AddPosition(v)
					err.AddPosition(n.upperBound)
					err.AddClosedPositions(id)
				}
				n.addValueConjunct(env, v, id)
				return
			}
			n.upperBound = x

		case GreaterThanOp, GreaterEqualOp:
			if y := n.lowerBound; y != nil {
				n.lowerBound = nil
				v := SimplifyBounds(ctx, n.kind, x, y)
				if err := valueError(v); err != nil {
					err.AddPosition(v)
					err.AddPosition(n.lowerBound)
					err.AddClosedPositions(id)
				}
				n.addValueConjunct(env, v, id)
				return
			}
			n.lowerBound = x

		case EqualOp, NotEqualOp, MatchOp, NotMatchOp:
			// This check serves as simplifier, but also to remove duplicates.
			k := 0
			match := false
			for _, c := range n.checks {
				if y, ok := c.(*BoundValue); ok {
					switch z := SimplifyBounds(ctx, n.kind, x, y); {
					case z == y:
						match = true
					case z == x:
						continue
					}
				}
				n.checks[k] = c
				k++
			}
			n.checks = n.checks[:k]
			if !match {
				n.checks = append(n.checks, x)
			}
			return
		}

	case Validator:
		// This check serves as simplifier, but also to remove duplicates.
		for i, y := range n.checks {
			if b := SimplifyValidator(ctx, x, y); b != nil {
				n.checks[i] = b
				return
			}
		}
		n.updateNodeType(x.Kind(), x, id)
		n.checks = append(n.checks, x)

	case *Vertex:
	// handled above.

	case Value: // *NullLit, *BoolLit, *NumLit, *StringLit, *BytesLit, *Builtin
		if y := n.scalar; y != nil {
			if b, ok := BinOp(ctx, EqualOp, x, y).(*Bool); !ok || !b.B {
				n.addConflict(x, y, x.Kind(), y.Kind(), n.scalarID, id)
			}
			// TODO: do we need to explicitly add again?
			// n.scalar = nil
			// n.addValueConjunct(c, BinOp(c, EqualOp, x, y))
			break
		}
		n.scalar = x
		n.scalarID = id

	default:
		panic(fmt.Sprintf("unknown value type %T", x))
	}

	if n.lowerBound != nil && n.upperBound != nil {
		if u := SimplifyBounds(ctx, n.kind, n.lowerBound, n.upperBound); u != nil {
			if err := valueError(u); err != nil {
				err.AddPosition(n.lowerBound)
				err.AddPosition(n.upperBound)
				err.AddClosedPositions(id)
			}
			n.lowerBound = nil
			n.upperBound = nil
			n.addValueConjunct(env, u, id)
		}
	}
}

func valueError(v Value) *ValueError {
	if v == nil {
		return nil
	}
	b, _ := v.(*Bottom)
	if b == nil {
		return nil
	}
	err, _ := b.Err.(*ValueError)
	if err == nil {
		return nil
	}
	return err
}

// addStruct collates the declarations of a struct.
//
// addStruct fulfills two additional pivotal functions:
//   1) Implement vertex unification (this happens through De Bruijn indices
//      combined with proper set up of Environments).
//   2) Implied closedness for definitions.
//
func (n *nodeContext) addStruct(
	env *Environment,
	s *StructLit,
	closeInfo CloseInfo) {

	n.updateCyclicStatus(env) // to handle empty structs.

	ctx := n.ctx

	// NOTE: This is a crucial point in the code:
	// Unification derferencing happens here. The child nodes are set to
	// an Environment linked to the current node. Together with the De Bruijn
	// indices, this determines to which Vertex a reference resolves.

	// TODO(perf): consider using environment cache:
	// var childEnv *Environment
	// for _, s := range n.nodeCache.sub {
	// 	if s.Up == env {
	// 		childEnv = s
	// 	}
	// }
	childEnv := &Environment{
		Up:     env,
		Vertex: n.node,
	}
	if env != nil {
		childEnv.Cyclic = env.Cyclic
		childEnv.Deref = env.Deref
	}

	s.Init()

	if s.HasEmbed && !s.IsFile() {
		closeInfo = closeInfo.SpawnGroup(nil)
	}

	parent := n.node.AddStruct(s, childEnv, closeInfo)
	closeInfo.IsClosed = false
	parent.Disable = true // disable until processing is done.

	for _, d := range s.Decls {
		switch x := d.(type) {
		case *Field:
			// handle in next iteration.

		case *OptionalField:
			if x.Label.IsString() {
				n.aStruct = s
				n.aStructID = closeInfo
			}

		case *DynamicField:
			n.aStruct = s
			n.aStructID = closeInfo
			n.dynamicFields = append(n.dynamicFields, envDynamic{childEnv, x, closeInfo, nil})

		case *ForClause:
			// Why is this not an embedding?
			n.forClauses = append(n.forClauses, envYield{childEnv, x, closeInfo, nil})

		case Yielder:
			// Why is this not an embedding?
			n.ifClauses = append(n.ifClauses, envYield{childEnv, x, closeInfo, nil})

		case Expr:
			// add embedding to optional

			// TODO(perf): only do this if addExprConjunct below will result in
			// a fieldSet. Otherwise the entry will just be removed next.
			id := closeInfo.SpawnEmbed(x)

			// push and opo embedding type.
			n.addExprConjunct(MakeConjunct(childEnv, x, id))

		case *BulkOptionalField:
			n.aStruct = s
			n.aStructID = closeInfo

		case *Ellipsis:
			n.aStruct = s
			n.aStructID = closeInfo

		default:
			panic("unreachable")
		}
	}

	if !s.HasEmbed {
		n.aStruct = s
		n.aStructID = closeInfo
	}

	// Apply existing fields
	for _, arc := range n.node.Arcs {
		// Reuse Acceptor interface.
		parent.MatchAndInsert(ctx, arc)
	}

	parent.Disable = false

	for _, d := range s.Decls {
		switch x := d.(type) {
		case *Field:
			if x.Label.IsString() {
				n.aStruct = s
				n.aStructID = closeInfo
			}
			n.insertField(x.Label, MakeConjunct(childEnv, x, closeInfo))
		}
	}
}

// TODO(perf): if an arc is the only arc with that label added to a Vertex, and
// if there are no conjuncts of optional fields to be added, then the arc could
// be added as is until any of these conditions change. This would allow
// structure sharing in many cases. One should be careful, however, to
// recursively track arcs of previously unified evaluated vertices ot make this
// optimization meaningful.
//
// An alternative approach to avoid evaluating optional arcs (if we take that
// route) is to not recursively evaluate those arcs, even for Finalize. This is
// possible as it is not necessary to evaluate optional arcs to evaluate
// disjunctions.
func (n *nodeContext) insertField(f Feature, x Conjunct) *Vertex {
	ctx := n.ctx
	arc, isNew := n.node.GetArc(ctx, f)

	arc.addConjunct(x)

	switch {
	case isNew:
		for _, s := range n.node.Structs {
			if s.Disable {
				continue
			}
			s.MatchAndInsert(ctx, arc)
		}

	case arc.state != nil:
		s := arc.state
		switch {
		case arc.Status() <= AllArcs:
			// This may happen when a struct has multiple comprehensions, where
			// the insertion of one of which depends on the outcome of another.

			// TODO: to something more principled by allowing values to
			// monotonically increase.
			arc.status = Partial
			arc.BaseValue = nil
			s.disjuncts = s.disjuncts[:0]
			s.disjunctErrs = s.disjunctErrs[:0]

			fallthrough

		default:
			arc.state.addExprConjunct(x)
		}

	case arc.Status() == 0:
	default:
		n.addErr(ctx.NewPosf(pos(x.Field()),
			"cannot add field %s: was already used",
			f.SelectorString(ctx)))
	}
	return arc
}

// expandOne adds dynamic fields to a node until a fixed point is reached.
// On each iteration, dynamic fields that cannot resolve due to incomplete
// values are skipped. They will be retried on the next iteration until no
// progress can be made. Note that a dynamic field may add more dynamic fields.
//
// forClauses are processed after all other clauses. A struct may be referenced
// before it is complete, meaning that fields added by other forms of injection
// may influence the result of a for clause _after_ it has already been
// processed. We could instead detect such insertion and feed it to the
// ForClause to generate another entry or have the for clause be recomputed.
// This seems to be too complicated and lead to iffy edge cases.
// TODO(errors): detect when a field is added to a struct that is already used
// in a for clause.
func (n *nodeContext) expandOne() (done bool) {
	// Don't expand incomplete expressions if we detected a cycle.
	if n.done() || (n.hasCycle && !n.hasNonCycle) {
		return false
	}

	var progress bool

	if progress = n.injectDynamic(); progress {
		return true
	}

	if progress = n.injectEmbedded(&(n.ifClauses)); progress {
		return true
	}

	if progress = n.injectEmbedded(&(n.forClauses)); progress {
		return true
	}

	// Do expressions after comprehensions, as comprehensions can never
	// refer to embedded scalars, whereas expressions may refer to generated
	// fields if we were to allow attributes to be defined alongside
	// scalars.
	exprs := n.exprs
	n.exprs = n.exprs[:0]
	for _, x := range exprs {
		n.addExprConjunct(x.c)

		// collect and and or
	}
	if len(n.exprs) < len(exprs) {
		return true
	}

	// No progress, report error later if needed: unification with
	// disjuncts may resolve this later later on.
	return false
}

// injectDynamic evaluates and inserts dynamic declarations.
func (n *nodeContext) injectDynamic() (progress bool) {
	ctx := n.ctx
	k := 0

	a := n.dynamicFields
	for _, d := range n.dynamicFields {
		var f Feature
		v, complete := ctx.Evaluate(d.env, d.field.Key)
		if !complete {
			d.err, _ = v.(*Bottom)
			a[k] = d
			k++
			continue
		}
		if b, _ := v.(*Bottom); b != nil {
			n.addValueConjunct(nil, b, d.id)
			continue
		}
		f = ctx.Label(d.field.Key, v)
		n.insertField(f, MakeConjunct(d.env, d.field, d.id))
	}

	progress = k < len(n.dynamicFields)

	n.dynamicFields = a[:k]

	return progress
}

// injectEmbedded evaluates and inserts embeddings. It first evaluates all
// embeddings before inserting the results to ensure that the order of
// evaluation does not matter.
func (n *nodeContext) injectEmbedded(all *[]envYield) (progress bool) {
	ctx := n.ctx
	type envStruct struct {
		env *Environment
		s   *StructLit
	}
	var sa []envStruct
	f := func(env *Environment, st *StructLit) {
		sa = append(sa, envStruct{env, st})
	}

	k := 0
	for i := 0; i < len(*all); i++ {
		d := (*all)[i]
		sa = sa[:0]

		if err := ctx.Yield(d.env, d.yield, f); err != nil {
			if err.IsIncomplete() {
				d.err = err
				(*all)[k] = d
				k++
			} else {
				// continue to collect other errors.
				n.addBottom(err)
			}
			continue
		}

		if len(sa) == 0 {
			continue
		}
		id := d.id.SpawnSpan(d.yield, ComprehensionSpan)

		n.ctx.nonMonotonicInsertNest++
		for _, st := range sa {
			n.addStruct(st.env, st.s, id)
		}
		n.ctx.nonMonotonicInsertNest--
	}

	progress = k < len(*all)

	*all = (*all)[:k]

	return progress
}

// addLists
//
// TODO: association arrays:
// If an association array marker was present in a struct, create a struct node
// instead of a list node. In either case, a node may only have list fields
// or struct fields and not both.
//
// addLists should be run after the fixpoint expansion:
//    - it enforces that comprehensions may not refer to the list itself
//    - there may be no other fields within the list.
//
// TODO(embeddedScalars): for embedded scalars, there should be another pass
// of evaluation expressions after expanding lists.
func (n *nodeContext) addLists() (oneOfTheLists Expr, anID CloseInfo) {
	if len(n.lists) == 0 && len(n.vLists) == 0 {
		return nil, CloseInfo{}
	}

	isOpen := true
	max := 0
	var maxNode Expr

	if m, ok := n.node.BaseValue.(*ListMarker); ok {
		isOpen = m.IsOpen
		max = len(n.node.Arcs)
	}

	c := n.ctx

	for _, l := range n.vLists {
		oneOfTheLists = l

		elems := l.Elems()
		isClosed := l.IsClosed(c)

		switch {
		case len(elems) < max:
			if isClosed {
				n.invalidListLength(len(elems), max, l, maxNode)
				continue
			}

		case len(elems) > max:
			if !isOpen {
				n.invalidListLength(max, len(elems), maxNode, l)
				continue
			}
			isOpen = !isClosed
			max = len(elems)
			maxNode = l

		case isClosed:
			isOpen = false
			maxNode = l
		}

		for _, a := range elems {
			if a.Conjuncts == nil {
				x := a.BaseValue.(Value)
				n.insertField(a.Label, MakeConjunct(nil, x, CloseInfo{}))
				continue
			}
			for _, c := range a.Conjuncts {
				n.insertField(a.Label, c)
			}
		}
	}

outer:
	for i, l := range n.lists {
		n.updateCyclicStatus(l.env)

		index := int64(0)
		hasComprehension := false
		for j, elem := range l.list.Elems {
			switch x := elem.(type) {
			case Yielder:
				err := c.Yield(l.env, x, func(e *Environment, st *StructLit) {
					label, err := MakeLabel(x.Source(), index, IntLabel)
					n.addErr(err)
					index++
					c := MakeConjunct(e, st, l.id)
					n.insertField(label, c)
				})
				hasComprehension = true
				if err != nil {
					n.addBottom(err)
					continue outer
				}

			case *Ellipsis:
				if j != len(l.list.Elems)-1 {
					n.addErr(c.Newf("ellipsis must be last element in list"))
				}

				n.lists[i].elipsis = x

			default:
				label, err := MakeLabel(x.Source(), index, IntLabel)
				n.addErr(err)
				index++ // TODO: don't use insertField.
				n.insertField(label, MakeConjunct(l.env, x, l.id))
			}

			// Terminate early n case of runaway comprehension.
			if !isOpen && int(index) > max {
				n.invalidListLength(max, int(index), maxNode, l.list)
				continue outer
			}
		}

		oneOfTheLists = l.list
		anID = l.id

		switch closed := n.lists[i].elipsis == nil; {
		case int(index) < max:
			if closed {
				n.invalidListLength(int(index), max, l.list, maxNode)
				continue
			}

		case int(index) > max,
			closed && isOpen,
			(!closed == isOpen) && !hasComprehension:
			max = int(index)
			maxNode = l.list
			isOpen = !closed
		}

		n.lists[i].n = index
	}

	// add additionalItem values to list and construct optionals.
	elems := n.node.Elems()
	for _, l := range n.vLists {
		if !l.IsClosed(c) {
			continue
		}

		newElems := l.Elems()
		if len(newElems) >= len(elems) {
			continue // error generated earlier, if applicable.
		}

		for _, arc := range elems[len(newElems):] {
			l.MatchAndInsert(c, arc)
		}
	}

	for _, l := range n.lists {
		if l.elipsis == nil {
			continue
		}

		s := &StructLit{Decls: []Decl{l.elipsis}}
		s.Init()
		info := n.node.AddStruct(s, l.env, l.id)

		for _, arc := range elems[l.n:] {
			info.MatchAndInsert(c, arc)
		}
	}

	sources := []ast.Expr{}
	// Add conjuncts for additional items.
	for _, l := range n.lists {
		if l.elipsis == nil {
			continue
		}
		if src, _ := l.elipsis.Source().(ast.Expr); src != nil {
			sources = append(sources, src)
		}
	}

	if m, ok := n.node.BaseValue.(*ListMarker); !ok {
		n.node.SetValue(c, Partial, &ListMarker{
			Src:    ast.NewBinExpr(token.AND, sources...),
			IsOpen: isOpen,
		})
	} else {
		if expr, _ := m.Src.(ast.Expr); expr != nil {
			sources = append(sources, expr)
		}
		m.Src = ast.NewBinExpr(token.AND, sources...)
		m.IsOpen = m.IsOpen && isOpen
	}

	n.lists = n.lists[:0]
	n.vLists = n.vLists[:0]

	return oneOfTheLists, anID
}

func (n *nodeContext) invalidListLength(na, nb int, a, b Expr) {
	n.addErr(n.ctx.Newf("incompatible list lengths (%d and %d)", na, nb))
}