internal/core/adt/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 adt

 // This file implements the closedness algorithm.

 // Outline of algorithm
 //
 // To compute closedness each Vertex is associated with a tree which has
 // leaf nodes with sets of allowed labels, and interior nodes that describe
 // how these sets may be combines: Or, for embedding, or And for definitions.
 //
 // Each conjunct of a Vertex is associated with such a leaf node. Each
 // conjunct that evaluates to a struct is added to the list of Structs, which
 // in the end forms this tree. If a conjunct is embedded, or references another
 // struct or definition, it adds interior node to reflect this.
 //
 // To test whether a feature is allowed, it must satisfy the resulting
 // expression tree.
 //
 // In order to avoid having to copy the tree for each node, the tree is linked
 // from leaf node to root, rather than the other way around. This allows
 // parent nodes to be shared as the tree grows and ensures that the growth
 // of the tree is bounded by the number of conjuncts. As a consequence, this
 // requires a two-pass algorithm:
 //
 //    - walk up to mark which nodes are required and count the number of
 //      child nodes that need to be satisfied.
 //    - verify fields in leaf structs and mark parent leafs as satisfied
 //      when appropriate.
 //
 // A label is allowed if all required root nodes are marked as accepted after
 // these two passes.
 //

 // A note on embeddings: it is important to keep track which conjuncts originate
 // from an embedding, as an embedded value 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.

 // TODO(perf):
 // - less nodes
 // - disable StructInfo nodes that can no longer pass a feature
 // - sort StructInfos active ones first.

 // TODO(errors): return a dedicated ConflictError that can track original
 // positions on demand.

 func (v *Vertex) IsInOneOf(t SpanType) bool {
 	for _, s := range v.Structs {
 		if s.CloseInfo.IsInOneOf(t) {
 			return true
 		}
 	}
 	return false
 }

 // IsRecursivelyClosed returns true if this value is either a definition or unified
 // with a definition.
 func (v *Vertex) IsRecursivelyClosed() bool {
 	if v.IsInOneOf(DefinitionSpan) {
 		return true
 	}
 	for p := v; p != nil; p = p.Parent {
 		if p.Label.IsDef() {
 			return true
 		}
 	}
 	return false
 }

 type closeNodeType uint8

 const (
 	// a closeRef node is created when there is a non-definition reference.
 	// These nodes are not necessary for computing results, but may be
 	// relevant down the line to group closures through embedded values and
 	// to track position information for failures.
 	closeRef closeNodeType = iota

 	// closeDef indicates this node was introduced as a result of referencing
 	// a definition.
 	closeDef

 	// closeEmbed indicates this node was added as a result of an embedding.
 	closeEmbed

 	_ = closeRef // silence the linter
 )

 // TODO: merge with closeInfo: this is a leftover of the refactoring.
 type CloseInfo struct {
 	*closeInfo

 	IsClosed   bool
 	FieldTypes OptionalType
 }

 func (c CloseInfo) Location() Node {
 	if c.closeInfo == nil {
 		return nil
 	}
 	return c.closeInfo.location
 }

 func (c CloseInfo) SpanMask() SpanType {
 	if c.closeInfo == nil {
 		return 0
 	}
 	return c.span
 }

 func (c CloseInfo) RootSpanType() SpanType {
 	if c.closeInfo == nil {
 		return 0
 	}
 	return c.root
 }

 func (c CloseInfo) IsInOneOf(t SpanType) bool {
 	if c.closeInfo == nil {
 		return false
 	}
 	return c.span&t != 0
 }

 // TODO(perf): remove: error positions should always be computed on demand
 // in dedicated error types.
 func (c *CloseInfo) AddPositions(ctx *OpContext) {
 	for s := c.closeInfo; s != nil; s = s.parent {
 		if loc := s.location; loc != nil {
 			ctx.AddPosition(loc)
 		}
 	}
 }

 // TODO(perf): use on StructInfo. Then if parent and expression are the same
 // it is possible to use cached value.
 func (c CloseInfo) SpawnEmbed(x Expr) CloseInfo {
 	var span SpanType
 	if c.closeInfo != nil {
 		span = c.span
 	}

 	c.closeInfo = &closeInfo{
 		parent:   c.closeInfo,
 		location: x,
 		mode:     closeEmbed,
 		root:     EmbeddingSpan,
 		span:     span | EmbeddingSpan,
 	}
 	return c
 }

 // SpawnGroup is used for structs that contain embeddings that may end up
 // closing the struct. This is to force that `b` is not allowed in
 //
 //      a: {#foo} & {b: int}
 //
 func (c CloseInfo) SpawnGroup(x Expr) CloseInfo {
 	var span SpanType
 	if c.closeInfo != nil {
 		span = c.span
 	}
 	c.closeInfo = &closeInfo{
 		parent:   c.closeInfo,
 		location: x,
 		span:     span,
 	}
 	return c
 }

 // SpawnSpan is used to track that a value is introduced by a comprehension
 // or constraint. Definition and embedding spans are introduced with SpawnRef
 // and SpawnEmbed, respectively.
 func (c CloseInfo) SpawnSpan(x Node, t SpanType) CloseInfo {
 	var span SpanType
 	if c.closeInfo != nil {
 		span = c.span
 	}
 	c.closeInfo = &closeInfo{
 		parent:   c.closeInfo,
 		location: x,
 		root:     t,
 		span:     span | t,
 	}
 	return c
 }

 func (c CloseInfo) SpawnRef(arc *Vertex, isDef bool, x Expr) CloseInfo {
 	var span SpanType
 	if c.closeInfo != nil {
 		span = c.span
 	}
 	c.closeInfo = &closeInfo{
 		parent:   c.closeInfo,
 		location: x,
 		span:     span,
 	}
 	if isDef {
 		c.mode = closeDef
 		c.closeInfo.root = DefinitionSpan
 		c.closeInfo.span |= DefinitionSpan
 	}
 	return 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
 }

 // A SpanType is used to indicate whether a CUE value is within the scope of
 // a certain CUE language construct, the span type.
 type SpanType uint8

 const (
 	// EmbeddingSpan means that this value was embedded at some point and should
 	// not be included as a possible root node in the todo field of OpContext.
 	EmbeddingSpan SpanType = 1 << iota
 	ConstraintSpan
 	ComprehensionSpan
 	DefinitionSpan
 )

 type closeInfo struct {
 	// location records the expression that led to this node's introduction.
 	location Node

 	// The parent node in the tree.
 	parent *closeInfo

 	// TODO(performance): if references are chained, we could have a separate
 	// parent pointer to skip the chain.

 	// mode indicates whether this node was added as part of an embedding,
 	// definition or non-definition reference.
 	mode closeNodeType

 	// noCheck means this struct is irrelevant for closedness checking. This can
 	// happen when:
 	//  - it is a sibling of a new definition.
 	noCheck bool // don't process for inclusion info

 	root SpanType
 	span SpanType
 }

 // closeStats holds the administrative fields for a closeInfo value. Each
 // closeInfo is associated with a single closeStats value per unification
 // operator. This association is done through an OpContext. This allows the
 // same value to be used in multiple concurrent unification operations.
 // NOTE: there are other parts of the algorithm that are not thread-safe yet.
 type closeStats struct {
 	// the other fields of this closeStats value are only valid if generation
 	// is equal to the generation in OpContext. This allows for lazy
 	// initialization of closeStats.
 	generation int

 	// These counts keep track of how many required child nodes need to be
 	// completed before this node is accepted.
 	requiredCount int
 	acceptedCount int

 	// accepted is set if this node is accepted.
 	accepted bool

 	required bool
 	next     *closeStats
 }

 func (c *closeInfo) isClosed() bool {
 	return c.mode == closeDef
 }

 func isClosed(v *Vertex) bool {
 	for _, s := range v.Structs {
 		if s.IsClosed {
 			return true
 		}
 		for c := s.closeInfo; c != nil; c = c.parent {
 			if c.isClosed() {
 				return true
 			}
 		}
 	}
 	return false
 }

 // Accept determines whether f is allowed in n. It uses the OpContext for
 // caching administrative fields.
 func Accept(ctx *OpContext, n *Vertex, f Feature) (found, required bool) {
 	ctx.generation++
 	ctx.todo = nil

 	var optionalTypes OptionalType

 	// TODO(perf): more aggressively determine whether a struct is open or
 	// closed: open structs do not have to be checked, yet they can particularly
 	// be the ones with performance isssues, for instanced as a result of
 	// embedded for comprehensions.
 	for _, s := range n.Structs {
 		if !s.useForAccept() {
 			continue
 		}
 		markCounts(ctx, s.CloseInfo)
 		optionalTypes |= s.types
 	}

 	if f.Index() == MaxIndex {
 		f = 0
 	}

 	var str Value
 	if optionalTypes&(HasComplexPattern|HasDynamic) != 0 && f.IsString() && f > 0 {
 		str = f.ToValue(ctx)
 	}

 	for _, s := range n.Structs {
 		if !s.useForAccept() {
 			continue
 		}
 		if verifyArc(ctx, s, f, str) {
 			// Beware: don't add to below expression: this relies on the
 			// side effects of markUp.
 			ok := markUp(ctx, s.closeInfo, 0)
 			found = found || ok
 		}
 	}

 	// Reject if any of the roots is not accepted.
 	for x := ctx.todo; x != nil; x = x.next {
 		if !x.accepted {
 			return false, true
 		}
 	}

 	return found, ctx.todo != nil
 }

 func markCounts(ctx *OpContext, info CloseInfo) {
 	if info.IsClosed {
 		markRequired(ctx, info.closeInfo)
 		return
 	}
 	for s := info.closeInfo; s != nil; s = s.parent {
 		if s.isClosed() {
 			markRequired(ctx, s)
 			return
 		}
 	}
 }

 func markRequired(ctx *OpContext, info *closeInfo) {
 	count := 0
 	for ; ; info = info.parent {
 		var s closeInfo
 		if info != nil {
 			s = *info
 		}

 		x := getScratch(ctx, info)

 		x.requiredCount += count

 		if x.required {
 			return
 		}

 		if s.span&EmbeddingSpan == 0 {
 			x.next = ctx.todo
 			ctx.todo = x
 		}

 		x.required = true

 		if info == nil {
 			return
 		}

 		count = 0
 		if s.mode != closeEmbed {
 			count = 1
 		}
 	}
 }

 func markUp(ctx *OpContext, info *closeInfo, count int) bool {
 	for ; ; info = info.parent {
 		var s closeInfo
 		if info != nil {
 			s = *info
 		}

 		x := getScratch(ctx, info)

 		x.acceptedCount += count

 		if x.acceptedCount < x.requiredCount {
 			return false
 		}

 		x.accepted = true

 		if info == nil {
 			return true
 		}

 		count = 0
 		if x.required && s.mode != closeEmbed {
 			count = 1
 		}
 	}
 }

 // getScratch: explain generation.
 func getScratch(ctx *OpContext, s *closeInfo) *closeStats {
 	m := ctx.closed
 	if m == nil {
 		m = map[*closeInfo]*closeStats{}
 		ctx.closed = m
 	}

 	x := m[s]
 	if x == nil {
 		x = &closeStats{}
 		m[s] = x
 	}

 	if x.generation != ctx.generation {
 		*x = closeStats{generation: ctx.generation}
 	}

 	return x
 }

 func verifyArc(ctx *OpContext, s *StructInfo, f Feature, label Value) bool {
 	isRegular := f.IsRegular()

 	o := s.StructLit
 	env := s.Env

 	if isRegular && (len(o.Additional) > 0 || o.IsOpen) {
 		return true
 	}

 	for _, g := range o.Fields {
 		if f == g.Label {
 			return true
 		}
 	}

 	if !isRegular {
 		return false
 	}

 	// Do not record errors during this validation.
 	errs := ctx.errs
 	defer func() { ctx.errs = errs }()

 	if len(o.Dynamic) > 0 && f.IsString() && label != nil {
 		for _, b := range o.Dynamic {
 			v := env.evalCached(ctx, b.Key)
 			s, ok := v.(*String)
 			if !ok {
 				continue
 			}
 			if label.(*String).Str == s.Str {
 				return true
 			}
 		}
 	}

 	for _, b := range o.Bulk {
 		if matchBulk(ctx, env, b, f, label) {
 			return true
 		}
 	}

 	// TODO(perf): delay adding this position: create a special error type that
 	// computes all necessary positions on demand.
 	if ctx != nil {
 		ctx.AddPosition(s.StructLit)
 	}

 	return false
 }
	// 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 adt

	// This file implements the closedness algorithm.

	// Outline of algorithm
	//
	// To compute closedness each Vertex is associated with a tree which has
	// leaf nodes with sets of allowed labels, and interior nodes that describe
	// how these sets may be combines: Or, for embedding, or And for definitions.
	//
	// Each conjunct of a Vertex is associated with such a leaf node. Each
	// conjunct that evaluates to a struct is added to the list of Structs, which
	// in the end forms this tree. If a conjunct is embedded, or references another
	// struct or definition, it adds interior node to reflect this.
	//
	// To test whether a feature is allowed, it must satisfy the resulting
	// expression tree.
	//
	// In order to avoid having to copy the tree for each node, the tree is linked
	// from leaf node to root, rather than the other way around. This allows
	// parent nodes to be shared as the tree grows and ensures that the growth
	// of the tree is bounded by the number of conjuncts. As a consequence, this
	// requires a two-pass algorithm:
	//
	// - walk up to mark which nodes are required and count the number of
	// child nodes that need to be satisfied.
	// - verify fields in leaf structs and mark parent leafs as satisfied
	// when appropriate.
	//
	// A label is allowed if all required root nodes are marked as accepted after
	// these two passes.
	//

	// A note on embeddings: it is important to keep track which conjuncts originate
	// from an embedding, as an embedded value 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.

	// TODO(perf):
	// - less nodes
	// - disable StructInfo nodes that can no longer pass a feature
	// - sort StructInfos active ones first.

	// TODO(errors): return a dedicated ConflictError that can track original
	// positions on demand.

	func (v *Vertex) IsInOneOf(t SpanType) bool {
	for _, s := range v.Structs {
	if s.CloseInfo.IsInOneOf(t) {
	return true
	}
	}
	return false
	}

	// IsRecursivelyClosed returns true if this value is either a definition or unified
	// with a definition.
	func (v *Vertex) IsRecursivelyClosed() bool {
	if v.IsInOneOf(DefinitionSpan) {
	return true
	}
	for p := v; p != nil; p = p.Parent {
	if p.Label.IsDef() {
	return true
	}
	}
	return false
	}

	type closeNodeType uint8

	const (
	// a closeRef node is created when there is a non-definition reference.
	// These nodes are not necessary for computing results, but may be
	// relevant down the line to group closures through embedded values and
	// to track position information for failures.
	closeRef closeNodeType = iota

	// closeDef indicates this node was introduced as a result of referencing
	// a definition.
	closeDef

	// closeEmbed indicates this node was added as a result of an embedding.
	closeEmbed

	_ = closeRef // silence the linter
	)

	// TODO: merge with closeInfo: this is a leftover of the refactoring.
	type CloseInfo struct {
	*closeInfo

	IsClosed bool
	FieldTypes OptionalType
	}

	func (c CloseInfo) Location() Node {
	if c.closeInfo == nil {
	return nil
	}
	return c.closeInfo.location
	}

	func (c CloseInfo) SpanMask() SpanType {
	if c.closeInfo == nil {
	return 0
	}
	return c.span
	}

	func (c CloseInfo) RootSpanType() SpanType {
	if c.closeInfo == nil {
	return 0
	}
	return c.root
	}

	func (c CloseInfo) IsInOneOf(t SpanType) bool {
	if c.closeInfo == nil {
	return false
	}
	return c.span&t != 0
	}

	// TODO(perf): remove: error positions should always be computed on demand
	// in dedicated error types.
	func (c CloseInfo) AddPositions(ctx OpContext) {
	for s := c.closeInfo; s != nil; s = s.parent {
	if loc := s.location; loc != nil {
	ctx.AddPosition(loc)
	}
	}
	}

	// TODO(perf): use on StructInfo. Then if parent and expression are the same
	// it is possible to use cached value.
	func (c CloseInfo) SpawnEmbed(x Expr) CloseInfo {
	var span SpanType
	if c.closeInfo != nil {
	span = c.span
	}

	c.closeInfo = &closeInfo{
	parent: c.closeInfo,
	location: x,
	mode: closeEmbed,
	root: EmbeddingSpan,
	span: span \| EmbeddingSpan,
	}
	return c
	}

	// SpawnGroup is used for structs that contain embeddings that may end up
	// closing the struct. This is to force that `b` is not allowed in
	//
	// a: {#foo} & {b: int}
	//
	func (c CloseInfo) SpawnGroup(x Expr) CloseInfo {
	var span SpanType
	if c.closeInfo != nil {
	span = c.span
	}
	c.closeInfo = &closeInfo{
	parent: c.closeInfo,
	location: x,
	span: span,
	}
	return c
	}

	// SpawnSpan is used to track that a value is introduced by a comprehension
	// or constraint. Definition and embedding spans are introduced with SpawnRef
	// and SpawnEmbed, respectively.
	func (c CloseInfo) SpawnSpan(x Node, t SpanType) CloseInfo {
	var span SpanType
	if c.closeInfo != nil {
	span = c.span
	}
	c.closeInfo = &closeInfo{
	parent: c.closeInfo,
	location: x,
	root: t,
	span: span \| t,
	}
	return c
	}

	func (c CloseInfo) SpawnRef(arc *Vertex, isDef bool, x Expr) CloseInfo {
	var span SpanType
	if c.closeInfo != nil {
	span = c.span
	}
	c.closeInfo = &closeInfo{
	parent: c.closeInfo,
	location: x,
	span: span,
	}
	if isDef {
	c.mode = closeDef
	c.closeInfo.root = DefinitionSpan
	c.closeInfo.span \|= DefinitionSpan
	}
	return 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
	}

	// A SpanType is used to indicate whether a CUE value is within the scope of
	// a certain CUE language construct, the span type.
	type SpanType uint8

	const (
	// EmbeddingSpan means that this value was embedded at some point and should
	// not be included as a possible root node in the todo field of OpContext.
	EmbeddingSpan SpanType = 1 << iota
	ConstraintSpan
	ComprehensionSpan
	DefinitionSpan
	)

	type closeInfo struct {
	// location records the expression that led to this node's introduction.
	location Node

	// The parent node in the tree.
	parent *closeInfo

	// TODO(performance): if references are chained, we could have a separate
	// parent pointer to skip the chain.

	// mode indicates whether this node was added as part of an embedding,
	// definition or non-definition reference.
	mode closeNodeType

	// noCheck means this struct is irrelevant for closedness checking. This can
	// happen when:
	// - it is a sibling of a new definition.
	noCheck bool // don't process for inclusion info

	root SpanType
	span SpanType
	}

	// closeStats holds the administrative fields for a closeInfo value. Each
	// closeInfo is associated with a single closeStats value per unification
	// operator. This association is done through an OpContext. This allows the
	// same value to be used in multiple concurrent unification operations.
	// NOTE: there are other parts of the algorithm that are not thread-safe yet.
	type closeStats struct {
	// the other fields of this closeStats value are only valid if generation
	// is equal to the generation in OpContext. This allows for lazy
	// initialization of closeStats.
	generation int

	// These counts keep track of how many required child nodes need to be
	// completed before this node is accepted.
	requiredCount int
	acceptedCount int

	// accepted is set if this node is accepted.
	accepted bool

	required bool
	next *closeStats
	}

	func (c *closeInfo) isClosed() bool {
	return c.mode == closeDef
	}

	func isClosed(v *Vertex) bool {
	for _, s := range v.Structs {
	if s.IsClosed {
	return true
	}
	for c := s.closeInfo; c != nil; c = c.parent {
	if c.isClosed() {
	return true
	}
	}
	}
	return false
	}

	// Accept determines whether f is allowed in n. It uses the OpContext for
	// caching administrative fields.
	func Accept(ctx OpContext, n Vertex, f Feature) (found, required bool) {
	ctx.generation++
	ctx.todo = nil

	var optionalTypes OptionalType

	// TODO(perf): more aggressively determine whether a struct is open or
	// closed: open structs do not have to be checked, yet they can particularly
	// be the ones with performance isssues, for instanced as a result of
	// embedded for comprehensions.
	for _, s := range n.Structs {
	if !s.useForAccept() {
	continue
	}
	markCounts(ctx, s.CloseInfo)
	optionalTypes \|= s.types
	}

	if f.Index() == MaxIndex {
	f = 0
	}

	var str Value
	if optionalTypes&(HasComplexPattern\|HasDynamic) != 0 && f.IsString() && f > 0 {
	str = f.ToValue(ctx)
	}

	for _, s := range n.Structs {
	if !s.useForAccept() {
	continue
	}
	if verifyArc(ctx, s, f, str) {
	// Beware: don't add to below expression: this relies on the
	// side effects of markUp.
	ok := markUp(ctx, s.closeInfo, 0)
	found = found \|\| ok
	}
	}

	// Reject if any of the roots is not accepted.
	for x := ctx.todo; x != nil; x = x.next {
	if !x.accepted {
	return false, true
	}
	}

	return found, ctx.todo != nil
	}

	func markCounts(ctx *OpContext, info CloseInfo) {
	if info.IsClosed {
	markRequired(ctx, info.closeInfo)
	return
	}
	for s := info.closeInfo; s != nil; s = s.parent {
	if s.isClosed() {
	markRequired(ctx, s)
	return
	}
	}
	}

	func markRequired(ctx OpContext, info closeInfo) {
	count := 0
	for ; ; info = info.parent {
	var s closeInfo
	if info != nil {
	s = *info
	}

	x := getScratch(ctx, info)

	x.requiredCount += count

	if x.required {
	return
	}

	if s.span&EmbeddingSpan == 0 {
	x.next = ctx.todo
	ctx.todo = x
	}

	x.required = true

	if info == nil {
	return
	}

	count = 0
	if s.mode != closeEmbed {
	count = 1
	}
	}
	}

	func markUp(ctx OpContext, info closeInfo, count int) bool {
	for ; ; info = info.parent {
	var s closeInfo
	if info != nil {
	s = *info
	}

	x := getScratch(ctx, info)

	x.acceptedCount += count

	if x.acceptedCount < x.requiredCount {
	return false
	}

	x.accepted = true

	if info == nil {
	return true
	}

	count = 0
	if x.required && s.mode != closeEmbed {
	count = 1
	}
	}
	}

	// getScratch: explain generation.
	func getScratch(ctx OpContext, s closeInfo) *closeStats {
	m := ctx.closed
	if m == nil {
	m = map[closeInfo]closeStats{}
	ctx.closed = m
	}

	x := m[s]
	if x == nil {
	x = &closeStats{}
	m[s] = x
	}

	if x.generation != ctx.generation {
	*x = closeStats{generation: ctx.generation}
	}

	return x
	}

	func verifyArc(ctx OpContext, s StructInfo, f Feature, label Value) bool {
	isRegular := f.IsRegular()

	o := s.StructLit
	env := s.Env

	if isRegular && (len(o.Additional) > 0 \|\| o.IsOpen) {
	return true
	}

	for _, g := range o.Fields {
	if f == g.Label {
	return true
	}
	}

	if !isRegular {
	return false
	}

	// Do not record errors during this validation.
	errs := ctx.errs
	defer func() { ctx.errs = errs }()

	if len(o.Dynamic) > 0 && f.IsString() && label != nil {
	for _, b := range o.Dynamic {
	v := env.evalCached(ctx, b.Key)
	s, ok := v.(*String)
	if !ok {
	continue
	}
	if label.(*String).Str == s.Str {
	return true
	}
	}
	}

	for _, b := range o.Bulk {
	if matchBulk(ctx, env, b, f, label) {
	return true
	}
	}

	// TODO(perf): delay adding this position: create a special error type that
	// computes all necessary positions on demand.
	if ctx != nil {
	ctx.AddPosition(s.StructLit)
	}

	return false
	}