core/adt/closed.go

// 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 {
	return v.Closed || v.IsInOneOf(DefinitionSpan)
}

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
}