// 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, if
// 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 and define a logical expression on the field sets
// computed for each conjunct.
//
// While evaluating each conjunct, nodeContext keeps track what changes need to
// be made to ClosedDef based on the evaluation of the current conjuncts.
// 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 overal control and use of the functionality in this file is used
// in eval.go.

import (
	"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 {
	tree     *CloseDef
	fields   []fieldSet
	isClosed bool
	isList   bool
	openList bool
}

func (a *acceptor) Accept(c *adt.OpContext, f adt.Feature) bool {
	if a.isList {
		return a.openList
	}
	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) {
	for _, fs := range a.fields {
		fs.MatchAndInsert(c, v)
	}
}

func (a *acceptor) OptionalTypes() (mask adt.OptionalType) {
	for _, f := range a.fields {
		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 {
	tree := &CloseDef{Src: x}
	sets := []fieldSet{}
	for _, d := range x.Values {
		if a, _ := d.Closed.(*acceptor); a != nil {
			sets = append(sets, a.fields...)
			tree.List = append(tree.List, a.tree)
		}
	}
	if len(tree.List) == 0 && len(sets) == 0 {
		return nil
	}
	return &acceptor{tree: tree, fields: sets}
}

// CloseDef defines how individual FieldSets (corresponding to conjuncts)
// combine to determine whether a field is contained in a closed set.
//
// Nodes with a non-empty List and IsAnd is false represent embeddings.
// The ID is the node that contained the embedding in that case.
//
// Nodes with a non-empty List and IsAnd is true represent conjunctions of
// definitions. In this case, a field must be contained in each definition.
//
// If a node has both conjunctions of definitions and embeddings, only the
// former are maintained. Conjunctions of definitions define an upper bound
// of the set of allowed fields in that case and the embeddings will not add
// any value.
type CloseDef struct {
	Src   adt.Node // for error reporting
	ID    uint32
	IsAnd bool
	List  []*CloseDef
}

// isOr reports whether this is a node representing embeddings.
func isOr(c *CloseDef) bool {
	return len(c.List) > 0 && !c.IsAnd
}

// updateClosed transforms c into a new node with all non-AND nodes with an
// ID matching one in replace substituted with the replace value.
//
// Vertex only keeps track of a flat list of conjuncts and does not keep track
// of the hierarchy of how these were derived. This function allows rewriting
// a CloseDef tree based on replacement information gathered during evaluation
// of this flat list.
//
func updateClosed(c *CloseDef, replace map[uint32]*CloseDef) *CloseDef { // used in eval.go
	// Insert an entry for CloseID 0 if we are about to replace it. By default
	// 0, which is the majority case, is omitted.
	if c != nil && replace[0] != nil && !containsClosed(c, 0) {
		c = &CloseDef{IsAnd: true, List: []*CloseDef{c, {}}}
	}

	switch {
	case c == nil:
		and := []*CloseDef{}
		for _, c := range replace {
			if c != nil {
				and = append(and, c)
			}
		}
		switch len(and) {
		case 0:
		case 1:
			c = and[0]
		default:
			c = &CloseDef{IsAnd: true, List: and}
		}
		// needClose
	case len(replace) > 0:
		c = updateClosedRec(c, replace)
	}
	return c
}

func updateClosedRec(c *CloseDef, replace map[uint32]*CloseDef) *CloseDef {
	if c == nil {
		return nil
	}

	// If c is a leaf or AND node, replace it outright. If both are an OR node,
	// merge the lists.
	if len(c.List) == 0 || !c.IsAnd {
		switch sub, ok := replace[c.ID]; {
		case sub != nil:
			if isOr(sub) && isOr(c) {
				sub.List = append(sub.List, c.List...)
			}
			return sub

		case !ok:
			if len(c.List) == 0 {
				return nil // drop from list
			}
		}
	}

	changed := false
	buf := make([]*CloseDef, len(c.List))
	k := 0
	for _, c := range c.List {
		n := updateClosedRec(c, replace)
		changed = changed || n != c
		if n != nil {
			buf[k] = n
			k++
		}
	}
	if !changed {
		return c
	}

	switch k {
	case 0:
		return nil
	case 1:
		return buf[0]
	default:
		return &CloseDef{Src: c.Src, ID: c.ID, IsAnd: c.IsAnd, List: buf[:k]}
	}
}

// UpdateReplace is called after evaluating a conjunct at the top of the arc
// to update the replacement information with the gathered CloseDef info.
func (n *nodeContext) updateReplace(env *adt.Environment) { // used in eval.go
	if n.newClose == nil {
		return
	}

	if n.replace == nil {
		n.replace = make(map[uint32]*CloseDef)
	}

	id := uint32(0)
	if env != nil {
		id = env.CloseID
	}

	n.replace[id] = updateClose(n.replace[id], n.newClose)
	n.newClose = nil
}

// appendList creates a new CloseDef with the elements of the list of orig
// and updated appended. It will take the ID of orig. It does not alter
// either orig or update.
func appendLists(orig, update *CloseDef) *CloseDef {
	list := make([]*CloseDef, len(orig.List)+len(update.List))
	copy(list[copy(list, orig.List):], update.List)
	c := *orig
	c.List = list
	return &c
}

// updateClose merges update into orig without altering either.
//
// The merge takes into account whether it is an embedding node or not.
// Most notably, if an "And" node is combined with an embedding, the
// embedding information may be discarded.
func updateClose(orig, update *CloseDef) *CloseDef {
	switch {
	case orig == nil:
		return update
	case isOr(orig):
		if !isOr(update) {
			return update
		}
		return appendLists(orig, update)
	case isOr(update):
		return orig
	case len(orig.List) == 0 && len(update.List) == 0:
		return &CloseDef{IsAnd: true, List: []*CloseDef{orig, update}}
	case len(orig.List) == 0:
		update.List = append(update.List, orig)
		return update
	default: // isAnd(orig)
		return appendLists(orig, update)
	}
}

func (n *nodeContext) addAnd(c *CloseDef) { // used in eval.go
	switch {
	case n.newClose == nil:
		n.newClose = c
	case isOr(n.newClose):
		n.newClose = c
	case len(n.newClose.List) == 0:
		n.newClose = &CloseDef{
			IsAnd: true,
			List:  []*CloseDef{n.newClose, c},
		}
	default:
		n.newClose.List = append(n.newClose.List, c)
	}
}

func (n *nodeContext) addOr(parentID uint32, c *CloseDef) { // used in eval.go
	switch {
	case n.newClose == nil:
		d := &CloseDef{ID: parentID, List: []*CloseDef{{ID: parentID}}}
		if c != nil {
			d.List = append(d.List, c)
		}
		n.newClose = d
	case isOr(n.newClose):
		d := n.newClose
		if c != nil {
			d.List = append(d.List, c)
		}
	}
}

// verifyArcAllowed checks whether f is an allowed label within the current
// node. It traverses c considering the "or" semantics of embeddings and the
// "and" semantics of conjunctions. It generates an error if a field is not
// allowed.
func (n *acceptor) verifyArcAllowed(ctx *adt.OpContext, f adt.Feature) *adt.Bottom {
	defer ctx.ReleasePositions(ctx.MarkPositions())

	// TODO(perf): this will also generate a message for f == 0. Do something
	// more clever and only generate this when it is a user error.
	filter := f.IsString() || f == adt.InvalidLabel
	if filter && !n.verifyArcRecursive(ctx, n.tree, f) {
		label := f.SelectorString(ctx)
		return ctx.NewErrf("field `%s` not allowed", label)
	}
	return nil
}

func (n *acceptor) verifyArcRecursive(ctx *adt.OpContext, c *CloseDef, f adt.Feature) bool {
	if len(c.List) == 0 {
		return n.verifyDefinition(ctx, c.ID, f)
	}
	if c.IsAnd {
		for _, c := range c.List {
			if !n.verifyArcRecursive(ctx, c, f) {
				return false
			}
		}
		return true
	}
	for _, c := range c.List {
		if n.verifyArcRecursive(ctx, c, f) {
			return true
		}
	}
	return false
}

// verifyDefinition reports whether f is a valid member for any of the fieldSets
// with the same closeID.
func (n *acceptor) verifyDefinition(ctx *adt.OpContext, closeID uint32, f adt.Feature) (ok bool) {
	for _, o := range n.fields {
		if o.env.CloseID != closeID {
			continue
		}

		if len(o.additional) > 0 || o.isOpen {
			return true
		}

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

		for _, b := range o.bulk {
			if b.check.Match(ctx, f) {
				return true
			}
		}
	}
	collectPositions(ctx, n.tree)
	for _, o := range n.fields {
		if o.pos != nil {
			ctx.AddPosition(o.pos)
		}
	}
	return false
}

func collectPositions(ctx *adt.OpContext, c *CloseDef) {
	if c.Src != nil {
		ctx.AddPosition(c.Src)
	}
	for _, x := range c.List {
		collectPositions(ctx, x)
	}
}

// containsClosed reports whether c contains any CloseDef with ID x,
// recursively.
func containsClosed(c *CloseDef, x uint32) bool {
	if c.ID == x && !c.IsAnd {
		return true
	}
	for _, e := range c.List {
		if containsClosed(e, x) {
			return true
		}
	}
	return false
}