internal/core/eval/closed.go - cue - Git at Google

 // Copyright 2020 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

 // The file implements the majority of the closed struct semantics. The data is
 // recorded in the Closed field of a Vertex.
 //
 // Each vertex has a set of conjuncts that make up the values of the vertex.
 // Each Conjunct may originate from various sources, like an embedding, field
 // definition or regular value. For the purpose of computing the value, the
 // source of the conjunct is irrelevant. The origin does matter, however, for
 // determining whether a field is allowed in a closed struct. The Closed field
 // keeps track of the kind of origin for this purpose.
 //
 // More precisely, the CloseDef struct explains how the conjuncts of an arc were
 // combined for instance due to a conjunction with closed struct or through an
 // embedding. Each Vertex may be associated with a slice of CloseDefs. The
 // position of a CloseDef in a file corresponds to an adt.ID.
 //
 // While evaluating each conjunct, new CloseDefs are added to indicate how a
 // conjunct relates to its parent as needed. For instance, if a field references
 // a definition, all other previous checks are useless, as the newly referred to
 // definitions define an upper bound and will contain all the information that
 // is necessary to determine whether a field may be included.
 //
 // Most of the logic in this file concerns itself with the combination of
 // multiple CloseDef values as well as traversing the structure to validate
 // whether an arc is allowed. The actual fieldSet logic is in optional.go The
 // overall control and use of the functionality in this file is used in eval.go.

 import (
 	"fmt"

 	"cuelang.org/go/internal/core/adt"
 )

 // acceptor implements adt.Acceptor.
 //
 // Note that it keeps track of whether it represents a closed struct. An
 // acceptor is also used to associate an CloseDef with a Vertex, and not
 // all CloseDefs represent a closed struct: a value that contains embeddings may
 // eventually turn into a closed struct. Consider
 //
 //    a: {
 //       b
 //       d: e: int
 //    }
 //    b: d: {
 //       #A & #B
 //    }
 //
 // At the point of evaluating `a`, the struct is not yet closed. However,
 // descending into `d` will trigger the inclusion of definitions which in turn
 // causes the struct to be closed. At this point, it is important to know that
 // `b` originated from an embedding, as otherwise `e` may not be allowed.
 //
 type acceptor struct {
 	Canopy []CloseDef
 	Fields []*fieldSet

 	// TODO: remove (unused as not fine-grained enough)
 	// isClosed is now used as an approximate filter.
 	isClosed bool
 	isList   bool
 	openList bool
 }

 func (a *acceptor) clone() *acceptor {
 	canopy := make([]CloseDef, len(a.Canopy))
 	copy(canopy, a.Canopy)
 	for i := range canopy {
 		canopy[i].IsClosed = false
 	}
 	return &acceptor{
 		Canopy:   canopy,
 		isClosed: a.isClosed,
 	}
 }

 func (a *acceptor) Accept(c *adt.OpContext, f adt.Feature) bool {
 	if a.isList {
 		return a.openList
 	}

 	// TODO: remove these two checks and always pass InvalidLabel.
 	if !a.isClosed {
 		return true
 	}
 	if f == adt.InvalidLabel {
 		return false
 	}
 	if f.IsInt() {
 		return a.openList
 	}
 	return a.verifyArcAllowed(c, f, nil)
 }

 func (a *acceptor) MatchAndInsert(c *adt.OpContext, v *adt.Vertex) {
 	a.visitAllFieldSets(func(fs *fieldSet) {
 		fs.MatchAndInsert(c, v)
 	})
 }

 func (a *acceptor) OptionalTypes() (mask adt.OptionalType) {
 	a.visitAllFieldSets(func(f *fieldSet) {
 		mask |= f.OptionalTypes()
 	})
 	return mask
 }

 // A disjunction acceptor represents a disjunction of all possible fields. Note
 // that this is never used in evaluation as evaluation stops at incomplete nodes
 // and a disjunction is incomplete. When the node is referenced, the original
 // conjuncts are used instead.
 //
 // The value may be used in the API, though, where it may be an argument to
 // UnifyAccept.
 //
 // TODO(perf): it would be sufficient to only implement the Accept method of an
 // Acceptor. This could be implemented as an allocation-free wrapper type around
 // a Disjunction. This will require a bit more API cleaning, though.
 func newDisjunctionAcceptor(x *adt.Disjunction) adt.Acceptor {
 	n := &acceptor{}

 	for _, d := range x.Values {
 		if a, _ := d.Closed.(*acceptor); a != nil {
 			offset := n.InsertSubtree(0, nil, d, false)
 			a.visitAllFieldSets(func(f *fieldSet) {
 				g := *f
 				g.id += offset
 				n.insertFieldSet(g.id, &g)
 			})
 		}
 	}

 	return n
 }

 // CloseDef defines how individual fieldSets (corresponding to conjuncts)
 // combine to determine whether a field is contained in a closed set.
 //
 // A CloseDef combines multiple conjuncts and embeddings. All CloseDefs are
 // stored in slice. References to other CloseDefs are indices within this slice.
 // Together they define the top of the tree of the expression tree of how
 // conjuncts combine together (a canopy).
 type CloseDef struct {
 	Src adt.Node

 	// And is used to track the IDs of a set of conjuncts. If IsDef or IsClosed
 	// is true, a field is only allowed if at least one of the corresponding
 	// fieldsets associated with this node or its embeddings allows it.
 	//
 	// And nodes are linked in a ring, meaning that the last node points back
 	// to the first node. This allows a traversal of all and nodes to commence
 	// at any point in the ring.
 	And adt.ID

 	// NextEmbed indicates the first ID for a linked list of embedded
 	// expressions. The node corresponding to the actual embedding is at
 	// position NextEmbed+1. The linked-list nodes all have a value of -1 for
 	// And. NextEmbed is 0 for the last element in the list.
 	NextEmbed adt.ID

 	// IsDef indicates this node is associated with a definition and that all
 	// expressions are recursively closed. This value is "sticky" when a child
 	// node copies the closedness data from a parent node.
 	IsDef bool

 	// IsClosed indicates this node is associated with the result of close().
 	// A child vertex should not "inherit" this value.
 	IsClosed bool
 }

 func (n *CloseDef) isRequired() bool {
 	return n.IsDef || n.IsClosed
 }

 const embedRoot adt.ID = -1

 type Entry = fieldSet

 func (c *acceptor) visitAllFieldSets(f func(f *fieldSet)) {
 	for _, set := range c.Fields {
 		for ; set != nil; set = set.next {
 			f(set)
 		}
 	}
 }

 func (c *acceptor) visitAnd(id adt.ID, f func(id adt.ID, n CloseDef) bool) bool {
 	for i := id; ; {
 		x := c.Canopy[i]

 		if !f(i, x) {
 			return false
 		}

 		if i = x.And; i == id {
 			break
 		}
 	}
 	return true
 }

 func (c *acceptor) visitOr(id adt.ID, f func(id adt.ID, n CloseDef) bool) bool {
 	if !f(id, c.Canopy[id]) {
 		return false
 	}
 	return c.visitEmbed(id, f)
 }

 func (c *acceptor) visitEmbed(id adt.ID, f func(id adt.ID, n CloseDef) bool) bool {
 	for i := c.Canopy[id].NextEmbed; i != 0; i = c.Canopy[i].NextEmbed {
 		if id := i + 1; !f(id, c.Canopy[id]) {
 			return false
 		}
 	}
 	return true
 }

 func (c *acceptor) node(id adt.ID) *CloseDef {
 	if len(c.Canopy) == 0 {
 		c.Canopy = append(c.Canopy, CloseDef{})
 	}
 	return &c.Canopy[id]
 }

 func (c *acceptor) fieldSet(at adt.ID) *fieldSet {
 	if int(at) >= len(c.Fields) {
 		return nil
 	}
 	return c.Fields[at]
 }

 func (c *acceptor) insertFieldSet(at adt.ID, e *fieldSet) {
 	c.node(0) // Ensure the canopy is at least length 1.
 	if len(c.Fields) < len(c.Canopy) {
 		a := make([]*fieldSet, len(c.Canopy))
 		copy(a, c.Fields)
 		c.Fields = a
 	}
 	e.next = c.Fields[at]
 	c.Fields[at] = e
 }

 // InsertDefinition appends a new CloseDef to Canopy representing a reference to
 // a definition at the given position. It returns the position of the new
 // CloseDef.
 func (c *acceptor) InsertDefinition(at adt.ID, src adt.Node) (id adt.ID) {
 	if len(c.Canopy) == 0 {
 		c.Canopy = append(c.Canopy, CloseDef{})
 	}
 	if int(at) >= len(c.Canopy) {
 		panic(fmt.Sprintf("at >= len(canopy) (%d >= %d)", at, len(c.Canopy)))
 	}
 	// New there is a new definition, the parent location (invariant) is no
 	// longer a required entry and could be dropped if there were no more
 	// fields.
 	//    #orig: #d     // only fields in #d are sufficient to check.
 	//    #orig: {a: b}
 	c.Canopy[at].IsDef = false

 	id = adt.ID(len(c.Canopy))
 	y := CloseDef{
 		Src:       src,
 		And:       c.Canopy[at].And,
 		NextEmbed: 0,
 		IsDef:     true,
 	}
 	c.Canopy[at].And = id
 	c.Canopy = append(c.Canopy, y)

 	return id
 }

 // InsertEmbed appends a new CloseDef to Canopy representing the use of an
 // embedding at the given position. It returns the position of the new CloseDef.
 func (c *acceptor) InsertEmbed(at adt.ID, src adt.Node) (id adt.ID) {
 	if len(c.Canopy) == 0 {
 		c.Canopy = append(c.Canopy, CloseDef{})
 	}
 	if int(at) >= len(c.Canopy) {
 		panic(fmt.Sprintf("at >= len(canopy) (%d >= %d)", at, len(c.Canopy)))
 	}

 	id = adt.ID(len(c.Canopy))
 	y := CloseDef{
 		And:       -1,
 		NextEmbed: c.Canopy[at].NextEmbed,
 	}
 	z := CloseDef{Src: src, And: id + 1}
 	c.Canopy[at].NextEmbed = id
 	c.Canopy = append(c.Canopy, y, z)

 	return id + 1
 }

 // isComplexStruct reports whether the Closed information should be copied as a
 // subtree into the parent node using InsertSubtree. If not, the conjuncts can
 // just be inserted at the current ID.
 func isComplexStruct(v *adt.Vertex) bool {
 	m, _ := v.Value.(*adt.StructMarker)
 	if m == nil {
 		return true
 	}
 	a, _ := v.Closed.(*acceptor)
 	if a == nil {
 		return false
 	}
 	if a.isClosed {
 		return true
 	}
 	switch len(a.Canopy) {
 	case 0:
 		return false
 	case 1:
 		// TODO: should we check for closedness?
 		x := a.Canopy[0]
 		return x.isRequired()
 	}
 	return true
 }

 // InsertSubtree inserts the closedness information of v into c as an embedding
 // at the current position and inserts conjuncts of v into n (if not nil).
 // It inserts it as an embedding and not and to cover either case. The idea is
 // that one of the values were supposed to be closed, a separate node entry
 // would already have been created.
 func (c *acceptor) InsertSubtree(at adt.ID, n *nodeContext, v *adt.Vertex, cyclic bool) adt.ID {
 	if len(c.Canopy) == 0 {
 		c.Canopy = append(c.Canopy, CloseDef{})
 	}
 	if int(at) >= len(c.Canopy) {
 		panic(fmt.Sprintf("at >= len(canopy) (%d >= %d)", at, len(c.Canopy)))
 	}

 	a := closedInfo(v)
 	a.node(0)

 	id := adt.ID(len(c.Canopy))
 	y := CloseDef{
 		And:       embedRoot,
 		NextEmbed: c.Canopy[at].NextEmbed,
 	}
 	c.Canopy[at].NextEmbed = id

 	c.Canopy = append(c.Canopy, y)
 	id = adt.ID(len(c.Canopy))

 	// First entry is at the embedded node location.
 	c.Canopy = append(c.Canopy, a.Canopy...)

 	// Shift all IDs for the new offset.
 	for i, x := range c.Canopy[id:] {
 		if x.And != -1 {
 			c.Canopy[int(id)+i].And += id
 		}
 		if x.NextEmbed != 0 {
 			c.Canopy[int(id)+i].NextEmbed += id
 		}
 	}

 	if n != nil {
 		for _, c := range v.Conjuncts {
 			c = updateCyclic(c, cyclic, nil)
 			c.CloseID += id
 			n.addExprConjunct(c)
 		}
 	}

 	return id
 }

 func (c *acceptor) verifyArc(ctx *adt.OpContext, f adt.Feature, v *adt.Vertex) (found bool, err *adt.Bottom) {

 	defer ctx.ReleasePositions(ctx.MarkPositions())

 	c.node(0) // ensure at least a size of 1.
 	if c.verify(ctx, f) {
 		return true, nil
 	}

 	// TODO: also disallow non-hidden definitions.
 	if !f.IsString() && f != adt.InvalidLabel {
 		return false, nil
 	}

 	if v != nil {
 		for _, c := range v.Conjuncts {
 			if pos := c.Field(); pos != nil {
 				ctx.AddPosition(pos)
 			}
 		}
 	}

 	// collect positions from tree.
 	for _, c := range c.Canopy {
 		if c.Src != nil {
 			ctx.AddPosition(c.Src)
 		}
 	}

 	label := f.SelectorString(ctx)
 	return false, ctx.NewErrf("field `%s` not allowed", label)
 }

 func (c *acceptor) verifyArcAllowed(ctx *adt.OpContext, f adt.Feature, v *adt.Vertex) bool {

 	// TODO: also disallow non-hidden definitions.
 	if !f.IsString() && f != adt.InvalidLabel {
 		return true
 	}

 	defer ctx.ReleasePositions(ctx.MarkPositions())

 	c.node(0) // ensure at least a size of 1.
 	return c.verify(ctx, f)
 }

 func (c *acceptor) verify(ctx *adt.OpContext, f adt.Feature) bool {
 	ok, required := c.verifyAnd(ctx, 0, f)
 	return ok || (!required && !c.isClosed)
 }

 // verifyAnd reports whether f is contained in all closed conjuncts at id and,
 // if not, whether the precense of at least one entry is required.
 func (c *acceptor) verifyAnd(ctx *adt.OpContext, id adt.ID, f adt.Feature) (found, required bool) {
 	for i := id; ; {
 		x := c.Canopy[i]

 		if ok, req := c.verifySets(ctx, i, f); ok {
 			found = true
 		} else if ok, isClosed := c.verifyEmbed(ctx, i, f); ok {
 			found = true
 		} else if req || x.isRequired() {
 			// Not found for a closed entry so this indicates a failure.
 			return false, true
 		} else if isClosed {
 			// The node itself isn't closed, but an embedding indicates it
 			// should. See cue/testdata/definitions/embed.txtar.
 			required = true
 		}

 		if i = x.And; i == id {
 			break
 		}
 	}

 	return found, required
 }

 // verifyEmbed reports whether any of the embeddings for the node at id allows f
 // and, if not, whether the embeddings imply that the enclosing node should be
 // closed. The latter is the case when embedded struct itself is closed.
 func (c *acceptor) verifyEmbed(ctx *adt.OpContext, id adt.ID, f adt.Feature) (found, isClosed bool) {

 	for i := c.Canopy[id].NextEmbed; i != 0; i = c.Canopy[i].NextEmbed {
 		ok, req := c.verifyAnd(ctx, i+1, f)
 		if ok {
 			return true, false
 		}
 		if req {
 			isClosed = true
 		}
 	}
 	return false, isClosed
 }

 func (c *acceptor) verifySets(ctx *adt.OpContext, id adt.ID, f adt.Feature) (found, required bool) {
 	o := c.fieldSet(id)
 	if o == nil {
 		return false, false
 	}
 	for isRegular := f.IsRegular(); o != nil; o = o.next {
 		if isRegular && (len(o.additional) > 0 || o.isOpen) {
 			return true, false
 		}

 		for _, g := range o.fields {
 			if f == g.label {
 				return true, false
 			}
 		}

 		if !isRegular {
 			continue
 		}

 		for _, b := range o.bulk {
 			if b.check.Match(ctx, f) {
 				return true, false
 			}
 		}
 	}

 	// TODO: this is the same location where code is registered as the old code,
 	// but
 	for o := c.Fields[id]; o != nil; o = o.next {
 		if o.pos != nil {
 			ctx.AddPosition(o.pos)
 		}
 	}
 	return false, false
 }

 type info struct {
 	referred bool
 	up       adt.ID
 	replace  adt.ID
 	reverse  adt.ID
 }

 func (c *acceptor) Compact(all []adt.Conjunct) (compacted []CloseDef) {
 	a := c.Canopy
 	if len(a) == 0 {
 		return nil
 	}

 	marked := make([]info, len(a))

 	c.markParents(0, marked)

 	// Mark all entries that cannot be dropped.
 	for _, x := range all {
 		c.markUsed(x.CloseID, marked)
 	}

 	// Compute compact numbers and reverse.
 	k := adt.ID(0)
 	for i, x := range marked {
 		if x.referred {
 			marked[i].replace = k
 			marked[k].reverse = adt.ID(i)
 			k++
 		}
 	}

 	compacted = make([]CloseDef, k)

 	for i := range compacted {
 		orig := c.Canopy[marked[i].reverse]

 		and := orig.And
 		if and != embedRoot {
 			and = marked[orig.And].replace
 		}
 		compacted[i] = CloseDef{
 			Src:   orig.Src,
 			And:   and,
 			IsDef: orig.IsDef,
 		}

 		last := adt.ID(i)
 		for or := orig.NextEmbed; or != 0; or = c.Canopy[or].NextEmbed {
 			if marked[or].referred {
 				compacted[last].NextEmbed = marked[or].replace
 				last = marked[or].replace
 			}
 		}
 	}

 	// Update conjuncts
 	for i, x := range all {
 		all[i].CloseID = marked[x.ID()].replace
 	}

 	return compacted
 }

 func (c *acceptor) markParents(parent adt.ID, info []info) {
 	// Ands are arranged in a ring, so check for parent, not 0.
 	c.visitAnd(parent, func(i adt.ID, x CloseDef) bool {
 		c.visitEmbed(i, func(j adt.ID, x CloseDef) bool {
 			info[j-1].up = i
 			info[j].up = i
 			c.markParents(j, info)
 			return true
 		})
 		return true
 	})
 }

 func (c *acceptor) markUsed(id adt.ID, marked []info) {
 	if marked[id].referred {
 		return
 	}

 	if id > 0 && c.Canopy[id-1].And == embedRoot {
 		marked[id-1].referred = true
 	}

 	for i := id; !marked[i].referred; i = c.Canopy[i].And {
 		marked[i].referred = true
 	}

 	c.markUsed(marked[id].up, marked)
 }
	// Copyright 2020 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

	// The file implements the majority of the closed struct semantics. The data is
	// recorded in the Closed field of a Vertex.
	//
	// Each vertex has a set of conjuncts that make up the values of the vertex.
	// Each Conjunct may originate from various sources, like an embedding, field
	// definition or regular value. For the purpose of computing the value, the
	// source of the conjunct is irrelevant. The origin does matter, however, for
	// determining whether a field is allowed in a closed struct. The Closed field
	// keeps track of the kind of origin for this purpose.
	//
	// More precisely, the CloseDef struct explains how the conjuncts of an arc were
	// combined for instance due to a conjunction with closed struct or through an
	// embedding. Each Vertex may be associated with a slice of CloseDefs. The
	// position of a CloseDef in a file corresponds to an adt.ID.
	//
	// While evaluating each conjunct, new CloseDefs are added to indicate how a
	// conjunct relates to its parent as needed. For instance, if a field references
	// a definition, all other previous checks are useless, as the newly referred to
	// definitions define an upper bound and will contain all the information that
	// is necessary to determine whether a field may be included.
	//
	// Most of the logic in this file concerns itself with the combination of
	// multiple CloseDef values as well as traversing the structure to validate
	// whether an arc is allowed. The actual fieldSet logic is in optional.go The
	// overall control and use of the functionality in this file is used in eval.go.

	import (
	"fmt"

	"cuelang.org/go/internal/core/adt"
	)

	// acceptor implements adt.Acceptor.
	//
	// Note that it keeps track of whether it represents a closed struct. An
	// acceptor is also used to associate an CloseDef with a Vertex, and not
	// all CloseDefs represent a closed struct: a value that contains embeddings may
	// eventually turn into a closed struct. Consider
	//
	// a: {
	// b
	// d: e: int
	// }
	// b: d: {
	// #A & #B
	// }
	//
	// At the point of evaluating `a`, the struct is not yet closed. However,
	// descending into `d` will trigger the inclusion of definitions which in turn
	// causes the struct to be closed. At this point, it is important to know that
	// `b` originated from an embedding, as otherwise `e` may not be allowed.
	//
	type acceptor struct {
	Canopy []CloseDef
	Fields []*fieldSet

	// TODO: remove (unused as not fine-grained enough)
	// isClosed is now used as an approximate filter.
	isClosed bool
	isList bool
	openList bool
	}

	func (a acceptor) clone() acceptor {
	canopy := make([]CloseDef, len(a.Canopy))
	copy(canopy, a.Canopy)
	for i := range canopy {
	canopy[i].IsClosed = false
	}
	return &acceptor{
	Canopy: canopy,
	isClosed: a.isClosed,
	}
	}

	func (a acceptor) Accept(c adt.OpContext, f adt.Feature) bool {
	if a.isList {
	return a.openList
	}

	// TODO: remove these two checks and always pass InvalidLabel.
	if !a.isClosed {
	return true
	}
	if f == adt.InvalidLabel {
	return false
	}
	if f.IsInt() {
	return a.openList
	}
	return a.verifyArcAllowed(c, f, nil)
	}

	func (a acceptor) MatchAndInsert(c adt.OpContext, v *adt.Vertex) {
	a.visitAllFieldSets(func(fs *fieldSet) {
	fs.MatchAndInsert(c, v)
	})
	}

	func (a *acceptor) OptionalTypes() (mask adt.OptionalType) {
	a.visitAllFieldSets(func(f *fieldSet) {
	mask \|= f.OptionalTypes()
	})
	return mask
	}

	// A disjunction acceptor represents a disjunction of all possible fields. Note
	// that this is never used in evaluation as evaluation stops at incomplete nodes
	// and a disjunction is incomplete. When the node is referenced, the original
	// conjuncts are used instead.
	//
	// The value may be used in the API, though, where it may be an argument to
	// UnifyAccept.
	//
	// TODO(perf): it would be sufficient to only implement the Accept method of an
	// Acceptor. This could be implemented as an allocation-free wrapper type around
	// a Disjunction. This will require a bit more API cleaning, though.
	func newDisjunctionAcceptor(x *adt.Disjunction) adt.Acceptor {
	n := &acceptor{}

	for _, d := range x.Values {
	if a, _ := d.Closed.(*acceptor); a != nil {
	offset := n.InsertSubtree(0, nil, d, false)
	a.visitAllFieldSets(func(f *fieldSet) {
	g := *f
	g.id += offset
	n.insertFieldSet(g.id, &g)
	})
	}
	}

	return n
	}

	// CloseDef defines how individual fieldSets (corresponding to conjuncts)
	// combine to determine whether a field is contained in a closed set.
	//
	// A CloseDef combines multiple conjuncts and embeddings. All CloseDefs are
	// stored in slice. References to other CloseDefs are indices within this slice.
	// Together they define the top of the tree of the expression tree of how
	// conjuncts combine together (a canopy).
	type CloseDef struct {
	Src adt.Node

	// And is used to track the IDs of a set of conjuncts. If IsDef or IsClosed
	// is true, a field is only allowed if at least one of the corresponding
	// fieldsets associated with this node or its embeddings allows it.
	//
	// And nodes are linked in a ring, meaning that the last node points back
	// to the first node. This allows a traversal of all and nodes to commence
	// at any point in the ring.
	And adt.ID

	// NextEmbed indicates the first ID for a linked list of embedded
	// expressions. The node corresponding to the actual embedding is at
	// position NextEmbed+1. The linked-list nodes all have a value of -1 for
	// And. NextEmbed is 0 for the last element in the list.
	NextEmbed adt.ID

	// IsDef indicates this node is associated with a definition and that all
	// expressions are recursively closed. This value is "sticky" when a child
	// node copies the closedness data from a parent node.
	IsDef bool

	// IsClosed indicates this node is associated with the result of close().
	// A child vertex should not "inherit" this value.
	IsClosed bool
	}

	func (n *CloseDef) isRequired() bool {
	return n.IsDef \|\| n.IsClosed
	}

	const embedRoot adt.ID = -1

	type Entry = fieldSet

	func (c acceptor) visitAllFieldSets(f func(f fieldSet)) {
	for _, set := range c.Fields {
	for ; set != nil; set = set.next {
	f(set)
	}
	}
	}

	func (c *acceptor) visitAnd(id adt.ID, f func(id adt.ID, n CloseDef) bool) bool {
	for i := id; ; {
	x := c.Canopy[i]

	if !f(i, x) {
	return false
	}

	if i = x.And; i == id {
	break
	}
	}
	return true
	}

	func (c *acceptor) visitOr(id adt.ID, f func(id adt.ID, n CloseDef) bool) bool {
	if !f(id, c.Canopy[id]) {
	return false
	}
	return c.visitEmbed(id, f)
	}

	func (c *acceptor) visitEmbed(id adt.ID, f func(id adt.ID, n CloseDef) bool) bool {
	for i := c.Canopy[id].NextEmbed; i != 0; i = c.Canopy[i].NextEmbed {
	if id := i + 1; !f(id, c.Canopy[id]) {
	return false
	}
	}
	return true
	}

	func (c acceptor) node(id adt.ID) CloseDef {
	if len(c.Canopy) == 0 {
	c.Canopy = append(c.Canopy, CloseDef{})
	}
	return &c.Canopy[id]
	}

	func (c acceptor) fieldSet(at adt.ID) fieldSet {
	if int(at) >= len(c.Fields) {
	return nil
	}
	return c.Fields[at]
	}

	func (c acceptor) insertFieldSet(at adt.ID, e fieldSet) {
	c.node(0) // Ensure the canopy is at least length 1.
	if len(c.Fields) < len(c.Canopy) {
	a := make([]*fieldSet, len(c.Canopy))
	copy(a, c.Fields)
	c.Fields = a
	}
	e.next = c.Fields[at]
	c.Fields[at] = e
	}

	// InsertDefinition appends a new CloseDef to Canopy representing a reference to
	// a definition at the given position. It returns the position of the new
	// CloseDef.
	func (c *acceptor) InsertDefinition(at adt.ID, src adt.Node) (id adt.ID) {
	if len(c.Canopy) == 0 {
	c.Canopy = append(c.Canopy, CloseDef{})
	}
	if int(at) >= len(c.Canopy) {
	panic(fmt.Sprintf("at >= len(canopy) (%d >= %d)", at, len(c.Canopy)))
	}
	// New there is a new definition, the parent location (invariant) is no
	// longer a required entry and could be dropped if there were no more
	// fields.
	// #orig: #d // only fields in #d are sufficient to check.
	// #orig: {a: b}
	c.Canopy[at].IsDef = false

	id = adt.ID(len(c.Canopy))
	y := CloseDef{
	Src: src,
	And: c.Canopy[at].And,
	NextEmbed: 0,
	IsDef: true,
	}
	c.Canopy[at].And = id
	c.Canopy = append(c.Canopy, y)

	return id
	}

	// InsertEmbed appends a new CloseDef to Canopy representing the use of an
	// embedding at the given position. It returns the position of the new CloseDef.
	func (c *acceptor) InsertEmbed(at adt.ID, src adt.Node) (id adt.ID) {
	if len(c.Canopy) == 0 {
	c.Canopy = append(c.Canopy, CloseDef{})
	}
	if int(at) >= len(c.Canopy) {
	panic(fmt.Sprintf("at >= len(canopy) (%d >= %d)", at, len(c.Canopy)))
	}

	id = adt.ID(len(c.Canopy))
	y := CloseDef{
	And: -1,
	NextEmbed: c.Canopy[at].NextEmbed,
	}
	z := CloseDef{Src: src, And: id + 1}
	c.Canopy[at].NextEmbed = id
	c.Canopy = append(c.Canopy, y, z)

	return id + 1
	}

	// isComplexStruct reports whether the Closed information should be copied as a
	// subtree into the parent node using InsertSubtree. If not, the conjuncts can
	// just be inserted at the current ID.
	func isComplexStruct(v *adt.Vertex) bool {
	m, _ := v.Value.(*adt.StructMarker)
	if m == nil {
	return true
	}
	a, _ := v.Closed.(*acceptor)
	if a == nil {
	return false
	}
	if a.isClosed {
	return true
	}
	switch len(a.Canopy) {
	case 0:
	return false
	case 1:
	// TODO: should we check for closedness?
	x := a.Canopy[0]
	return x.isRequired()
	}
	return true
	}

	// InsertSubtree inserts the closedness information of v into c as an embedding
	// at the current position and inserts conjuncts of v into n (if not nil).
	// It inserts it as an embedding and not and to cover either case. The idea is
	// that one of the values were supposed to be closed, a separate node entry
	// would already have been created.
	func (c acceptor) InsertSubtree(at adt.ID, n nodeContext, v *adt.Vertex, cyclic bool) adt.ID {
	if len(c.Canopy) == 0 {
	c.Canopy = append(c.Canopy, CloseDef{})
	}
	if int(at) >= len(c.Canopy) {
	panic(fmt.Sprintf("at >= len(canopy) (%d >= %d)", at, len(c.Canopy)))
	}

	a := closedInfo(v)
	a.node(0)

	id := adt.ID(len(c.Canopy))
	y := CloseDef{
	And: embedRoot,
	NextEmbed: c.Canopy[at].NextEmbed,
	}
	c.Canopy[at].NextEmbed = id

	c.Canopy = append(c.Canopy, y)
	id = adt.ID(len(c.Canopy))

	// First entry is at the embedded node location.
	c.Canopy = append(c.Canopy, a.Canopy...)

	// Shift all IDs for the new offset.
	for i, x := range c.Canopy[id:] {
	if x.And != -1 {
	c.Canopy[int(id)+i].And += id
	}
	if x.NextEmbed != 0 {
	c.Canopy[int(id)+i].NextEmbed += id
	}
	}

	if n != nil {
	for _, c := range v.Conjuncts {
	c = updateCyclic(c, cyclic, nil)
	c.CloseID += id
	n.addExprConjunct(c)
	}
	}

	return id
	}

	func (c acceptor) verifyArc(ctx adt.OpContext, f adt.Feature, v adt.Vertex) (found bool, err adt.Bottom) {

	defer ctx.ReleasePositions(ctx.MarkPositions())

	c.node(0) // ensure at least a size of 1.
	if c.verify(ctx, f) {
	return true, nil
	}

	// TODO: also disallow non-hidden definitions.
	if !f.IsString() && f != adt.InvalidLabel {
	return false, nil
	}

	if v != nil {
	for _, c := range v.Conjuncts {
	if pos := c.Field(); pos != nil {
	ctx.AddPosition(pos)
	}
	}
	}

	// collect positions from tree.
	for _, c := range c.Canopy {
	if c.Src != nil {
	ctx.AddPosition(c.Src)
	}
	}

	label := f.SelectorString(ctx)
	return false, ctx.NewErrf("field `%s` not allowed", label)
	}

	func (c acceptor) verifyArcAllowed(ctx adt.OpContext, f adt.Feature, v *adt.Vertex) bool {

	// TODO: also disallow non-hidden definitions.
	if !f.IsString() && f != adt.InvalidLabel {
	return true
	}

	defer ctx.ReleasePositions(ctx.MarkPositions())

	c.node(0) // ensure at least a size of 1.
	return c.verify(ctx, f)
	}

	func (c acceptor) verify(ctx adt.OpContext, f adt.Feature) bool {
	ok, required := c.verifyAnd(ctx, 0, f)
	return ok \|\| (!required && !c.isClosed)
	}

	// verifyAnd reports whether f is contained in all closed conjuncts at id and,
	// if not, whether the precense of at least one entry is required.
	func (c acceptor) verifyAnd(ctx adt.OpContext, id adt.ID, f adt.Feature) (found, required bool) {
	for i := id; ; {
	x := c.Canopy[i]

	if ok, req := c.verifySets(ctx, i, f); ok {
	found = true
	} else if ok, isClosed := c.verifyEmbed(ctx, i, f); ok {
	found = true
	} else if req \|\| x.isRequired() {
	// Not found for a closed entry so this indicates a failure.
	return false, true
	} else if isClosed {
	// The node itself isn't closed, but an embedding indicates it
	// should. See cue/testdata/definitions/embed.txtar.
	required = true
	}

	if i = x.And; i == id {
	break
	}
	}

	return found, required
	}

	// verifyEmbed reports whether any of the embeddings for the node at id allows f
	// and, if not, whether the embeddings imply that the enclosing node should be
	// closed. The latter is the case when embedded struct itself is closed.
	func (c acceptor) verifyEmbed(ctx adt.OpContext, id adt.ID, f adt.Feature) (found, isClosed bool) {

	for i := c.Canopy[id].NextEmbed; i != 0; i = c.Canopy[i].NextEmbed {
	ok, req := c.verifyAnd(ctx, i+1, f)
	if ok {
	return true, false
	}
	if req {
	isClosed = true
	}
	}
	return false, isClosed
	}

	func (c acceptor) verifySets(ctx adt.OpContext, id adt.ID, f adt.Feature) (found, required bool) {
	o := c.fieldSet(id)
	if o == nil {
	return false, false
	}
	for isRegular := f.IsRegular(); o != nil; o = o.next {
	if isRegular && (len(o.additional) > 0 \|\| o.isOpen) {
	return true, false
	}

	for _, g := range o.fields {
	if f == g.label {
	return true, false
	}
	}

	if !isRegular {
	continue
	}

	for _, b := range o.bulk {
	if b.check.Match(ctx, f) {
	return true, false
	}
	}
	}

	// TODO: this is the same location where code is registered as the old code,
	// but
	for o := c.Fields[id]; o != nil; o = o.next {
	if o.pos != nil {
	ctx.AddPosition(o.pos)
	}
	}
	return false, false
	}

	type info struct {
	referred bool
	up adt.ID
	replace adt.ID
	reverse adt.ID
	}

	func (c *acceptor) Compact(all []adt.Conjunct) (compacted []CloseDef) {
	a := c.Canopy
	if len(a) == 0 {
	return nil
	}

	marked := make([]info, len(a))

	c.markParents(0, marked)

	// Mark all entries that cannot be dropped.
	for _, x := range all {
	c.markUsed(x.CloseID, marked)
	}

	// Compute compact numbers and reverse.
	k := adt.ID(0)
	for i, x := range marked {
	if x.referred {
	marked[i].replace = k
	marked[k].reverse = adt.ID(i)
	k++
	}
	}

	compacted = make([]CloseDef, k)

	for i := range compacted {
	orig := c.Canopy[marked[i].reverse]

	and := orig.And
	if and != embedRoot {
	and = marked[orig.And].replace
	}
	compacted[i] = CloseDef{
	Src: orig.Src,
	And: and,
	IsDef: orig.IsDef,
	}

	last := adt.ID(i)
	for or := orig.NextEmbed; or != 0; or = c.Canopy[or].NextEmbed {
	if marked[or].referred {
	compacted[last].NextEmbed = marked[or].replace
	last = marked[or].replace
	}
	}
	}

	// Update conjuncts
	for i, x := range all {
	all[i].CloseID = marked[x.ID()].replace
	}

	return compacted
	}

	func (c *acceptor) markParents(parent adt.ID, info []info) {
	// Ands are arranged in a ring, so check for parent, not 0.
	c.visitAnd(parent, func(i adt.ID, x CloseDef) bool {
	c.visitEmbed(i, func(j adt.ID, x CloseDef) bool {
	info[j-1].up = i
	info[j].up = i
	c.markParents(j, info)
	return true
	})
	return true
	})
	}

	func (c *acceptor) markUsed(id adt.ID, marked []info) {
	if marked[id].referred {
	return
	}

	if id > 0 && c.Canopy[id-1].And == embedRoot {
	marked[id-1].referred = true
	}

	for i := id; !marked[i].referred; i = c.Canopy[i].And {
	marked[i].referred = true
	}

	c.markUsed(marked[id].up, marked)
	}