| // 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 |
| |
| import ( |
| "fmt" |
| |
| "cuelang.org/go/cue/ast" |
| "cuelang.org/go/cue/errors" |
| "cuelang.org/go/cue/token" |
| ) |
| |
| // TODO: unanswered questions about structural cycles: |
| // |
| // 1. When detecting a structural cycle, should we consider this as: |
| // a) an unevaluated value, |
| // b) an incomplete error (which does not affect parent validity), or |
| // c) a special value. |
| // |
| // Making it an error is the simplest way to ensure reentrancy is disallowed: |
| // without an error it would require an additional mechanism to stop reentrancy |
| // from continuing to process. Even worse, in some cases it may only partially |
| // evaluate, resulting in unexpected results. For this reason, we are taking |
| // approach `b` for now. |
| // |
| // This has some consequences of how disjunctions are treated though. Consider |
| // |
| // list: { |
| // head: _ |
| // tail: list | null |
| // } |
| // |
| // When making it an error, evaluating the above will result in |
| // |
| // list: { |
| // head: _ |
| // tail: null |
| // } |
| // |
| // because list will result in a structural cycle, and thus an error, it will be |
| // stripped from the disjunction. This may or may not be a desirable property. A |
| // nice thing is that it is not required to write `list | *null`. A disadvantage |
| // is that this is perhaps somewhat inexplicit. |
| // |
| // When not making it an error (and simply cease evaluating child arcs upon |
| // cycle detection), the result would be: |
| // |
| // list: { |
| // head: _ |
| // tail: list | null |
| // } |
| // |
| // In other words, an evaluation would result in a cycle and thus an error. |
| // Implementations can recognize such cases by having unevaluated arcs. An |
| // explicit structure cycle marker would probably be less error prone. |
| // |
| // Note that in both cases, a reference to list will still use the original |
| // conjuncts, so the result will be the same for either method in this case. |
| // |
| // |
| // 2. Structural cycle allowance. |
| // |
| // Structural cycle detection disallows reentrancy as well. This means one |
| // cannot use structs for recursive computation. This will probably preclude |
| // evaluation of some configuration. Given that there is no real alternative |
| // yet, we could allow structural cycle detection to be optionally disabled. |
| |
| // An Environment links the parent scopes for identifier lookup to a composite |
| // node. Each conjunct that make up node in the tree can be associated with |
| // a different environment (although some conjuncts may share an Environment). |
| type Environment struct { |
| Up *Environment |
| Vertex *Vertex |
| |
| // DynamicLabel is only set when instantiating a field from a pattern |
| // constraint. It is used to resolve label references. |
| DynamicLabel Feature |
| |
| // TODO(perf): make the following public fields a shareable struct as it |
| // mostly is going to be the same for child nodes. |
| |
| // Cyclic indicates a structural cycle was detected for this conjunct or one |
| // of its ancestors. |
| Cyclic bool |
| |
| // Deref keeps track of nodes that should dereference to Vertex. It is used |
| // for detecting structural cycle. |
| // |
| // The detection algorithm is based on Tomabechi's quasi-destructive graph |
| // unification. This detection requires dependencies to be resolved into |
| // fully dereferenced vertices. This is not the case in our algorithm: |
| // the result of evaluating conjuncts is placed into dereferenced vertices |
| // _after_ they are evaluated, but the Environment still points to the |
| // non-dereferenced context. |
| // |
| // In order to be able to detect structural cycles, we need to ensure that |
| // at least one node that is part of a cycle in the context in which |
| // conjunctions are evaluated dereferences correctly. |
| // |
| // The only field necessary to detect a structural cycle, however, is |
| // the Status field of the Vertex. So rather than dereferencing a node |
| // proper, it is sufficient to copy the Status of the dereferenced nodes |
| // to these nodes (will always be EvaluatingArcs). |
| Deref []*Vertex |
| |
| // Cycles contains vertices for which cycles are detected. It is used |
| // for tracking self-references within structural cycles. |
| // |
| // Unlike Deref, Cycles is not incremented with child nodes. |
| // TODO: Cycles is always a tail end of Deref, so this can be optimized. |
| Cycles []*Vertex |
| |
| cache map[Expr]Value |
| } |
| |
| type ID int32 |
| |
| // evalCached is used to look up let expressions. Caching let expressions |
| // prevents a possible combinatorial explosion. |
| func (e *Environment) evalCached(c *OpContext, x Expr) Value { |
| v, ok := e.cache[x] |
| if !ok { |
| if e.cache == nil { |
| e.cache = map[Expr]Value{} |
| } |
| env, src := c.e, c.src |
| c.e, c.src = e, x.Source() |
| v = c.eval(x) |
| c.e, c.src = env, src |
| e.cache[x] = v |
| } |
| return v |
| } |
| |
| // A Vertex is a node in the value tree. It may be a leaf or internal node. |
| // It may have arcs to represent elements of a fully evaluated struct or list. |
| // |
| // For structs, it only contains definitions and concrete fields. |
| // optional fields are dropped. |
| // |
| // It maintains source information such as a list of conjuncts that contributed |
| // to the value. |
| type Vertex struct { |
| // Parent links to a parent Vertex. This parent should only be used to |
| // access the parent's Label field to find the relative location within a |
| // tree. |
| Parent *Vertex |
| |
| // Label is the feature leading to this vertex. |
| Label Feature |
| |
| // TODO: move the following status fields to a separate struct. |
| |
| // status indicates the evaluation progress of this vertex. |
| status VertexStatus |
| |
| // isData indicates that this Vertex is to be interepreted as data: pattern |
| // and additional constraints, as well as optional fields, should be |
| // ignored. |
| isData bool |
| |
| // EvalCount keeps track of temporary dereferencing during evaluation. |
| // If EvalCount > 0, status should be considered to be EvaluatingArcs. |
| EvalCount int |
| |
| // SelfCount is used for tracking self-references. |
| SelfCount int |
| |
| // BaseValue is the value associated with this vertex. For lists and structs |
| // this is a sentinel value indicating its kind. |
| BaseValue BaseValue |
| |
| // ChildErrors is the collection of all errors of children. |
| ChildErrors *Bottom |
| |
| // The parent of nodes can be followed to determine the path within the |
| // configuration of this node. |
| // Value Value |
| Arcs []*Vertex // arcs are sorted in display order. |
| |
| // Conjuncts lists the structs that ultimately formed this Composite value. |
| // This includes all selected disjuncts. |
| // |
| // This value may be nil, in which case the Arcs are considered to define |
| // the final value of this Vertex. |
| Conjuncts []Conjunct |
| |
| // Structs is a slice of struct literals that contributed to this value. |
| // This information is used to compute the topological sort of arcs. |
| Structs []*StructLit |
| |
| // Closed contains information about how to interpret field labels for the |
| // various conjuncts with respect to which fields are allowed in this |
| // Vertex. If allows all fields if it is nil. |
| // The evaluator will first check existing fields before using this. So for |
| // simple cases, an Acceptor can always return false to close the Vertex. |
| Closed Acceptor |
| } |
| |
| // VertexStatus indicates the evaluation progress of a Vertex. |
| type VertexStatus int8 |
| |
| const ( |
| // Unprocessed indicates a Vertex has not been processed before. |
| // Value must be nil. |
| Unprocessed VertexStatus = iota |
| |
| // Evaluating means that the current Vertex is being evaluated. If this is |
| // encountered it indicates a reference cycle. Value must be nil. |
| Evaluating |
| |
| // Partial indicates that the result was only partially evaluated. It will |
| // need to be fully evaluated to get a complete results. |
| // |
| // TODO: this currently requires a renewed computation. Cache the |
| // nodeContext to allow reusing the computations done so far. |
| Partial |
| |
| // EvaluatingArcs indicates that the arcs of the Vertex are currently being |
| // evaluated. If this is encountered it indicates a structural cycle. |
| // Value does not have to be nil |
| EvaluatingArcs |
| |
| // Finalized means that this node is fully evaluated and that the results |
| // are save to use without further consideration. |
| Finalized |
| ) |
| |
| func (v *Vertex) Status() VertexStatus { |
| if v.EvalCount > 0 { |
| return EvaluatingArcs |
| } |
| return v.status |
| } |
| |
| func (v *Vertex) UpdateStatus(s VertexStatus) { |
| Assertf(v.status <= s+1, "attempt to regress status from %d to %d", v.Status(), s) |
| |
| if s == Finalized && v.BaseValue == nil { |
| // panic("not finalized") |
| } |
| v.status = s |
| } |
| |
| // Value returns the Value of v without definitions if it is a scalar |
| // or itself otherwise. |
| func (v *Vertex) Value() Value { |
| // TODO: rename to Value. |
| switch x := v.BaseValue.(type) { |
| case nil: |
| return nil |
| case *StructMarker, *ListMarker: |
| return v |
| case Value: |
| return x |
| default: |
| panic(fmt.Sprintf("unexpected type %T", v.BaseValue)) |
| } |
| } |
| |
| func (x *Vertex) IsConcrete() bool { |
| return x.Concreteness() <= Concrete |
| } |
| |
| // IsData reports whether v should be interpreted in data mode. In other words, |
| // it tells whether optional field matching and non-regular fields, like |
| // definitions and hidden fields, should be ignored. |
| func (v *Vertex) IsData() bool { |
| return v.isData || len(v.Conjuncts) == 0 |
| } |
| |
| // ToDataSingle creates a new Vertex that represents just the regular fields |
| // of this vertex. Arcs are left untouched. |
| // It is used by cue.Eval to convert nodes to data on per-node basis. |
| func (v *Vertex) ToDataSingle() *Vertex { |
| w := *v |
| w.isData = true |
| return &w |
| } |
| |
| // ToDataAll returns a new v where v and all its descendents contain only |
| // the regular fields. |
| func (v *Vertex) ToDataAll() *Vertex { |
| arcs := make([]*Vertex, 0, len(v.Arcs)) |
| for _, a := range v.Arcs { |
| if a.Label.IsRegular() { |
| arcs = append(arcs, a.ToDataAll()) |
| } |
| } |
| w := *v |
| |
| w.BaseValue = toDataAll(w.BaseValue) |
| w.Arcs = arcs |
| w.isData = true |
| w.Conjuncts = make([]Conjunct, len(v.Conjuncts)) |
| copy(w.Conjuncts, v.Conjuncts) |
| for i, c := range w.Conjuncts { |
| w.Conjuncts[i].CloseID = 0 |
| if v, _ := c.x.(Value); v != nil { |
| w.Conjuncts[i].x = toDataAll(v).(Value) |
| } |
| } |
| w.Closed = nil |
| return &w |
| } |
| |
| func toDataAll(v BaseValue) BaseValue { |
| switch x := v.(type) { |
| default: |
| return x |
| |
| case *Vertex: |
| return x.ToDataAll() |
| |
| // The following cases are always erroneous, but we handle them anyway |
| // to avoid issues with the closedness algorithm down the line. |
| case *Disjunction: |
| d := *x |
| d.Values = make([]*Vertex, len(x.Values)) |
| for i, v := range x.Values { |
| d.Values[i] = v.ToDataAll() |
| } |
| return &d |
| |
| case *Conjunction: |
| c := *x |
| c.Values = make([]Value, len(x.Values)) |
| for i, v := range x.Values { |
| // This case is okay because the source is of type Value. |
| c.Values[i] = toDataAll(v).(Value) |
| } |
| return &c |
| } |
| } |
| |
| // func (v *Vertex) IsEvaluating() bool { |
| // return v.Value == cycle |
| // } |
| |
| func (v *Vertex) IsErr() bool { |
| // if v.Status() > Evaluating { |
| if _, ok := v.BaseValue.(*Bottom); ok { |
| return true |
| } |
| // } |
| return false |
| } |
| |
| func (v *Vertex) Err(c *OpContext, state VertexStatus) *Bottom { |
| c.Unify(c, v, state) |
| if b, ok := v.BaseValue.(*Bottom); ok { |
| return b |
| } |
| return nil |
| } |
| |
| // func (v *Vertex) Evaluate() |
| |
| func (v *Vertex) Finalize(c *OpContext) { |
| c.Unify(c, v, Finalized) |
| } |
| |
| func (v *Vertex) AddErr(ctx *OpContext, b *Bottom) { |
| v.BaseValue = CombineErrors(nil, v.Value(), b) |
| v.UpdateStatus(Finalized) |
| } |
| |
| func (v *Vertex) SetValue(ctx *OpContext, state VertexStatus, value BaseValue) *Bottom { |
| v.BaseValue = value |
| v.UpdateStatus(state) |
| return nil |
| } |
| |
| // ToVertex wraps v in a new Vertex, if necessary. |
| func ToVertex(v Value) *Vertex { |
| switch x := v.(type) { |
| case *Vertex: |
| return x |
| default: |
| n := &Vertex{ |
| status: Finalized, |
| BaseValue: x, |
| } |
| n.AddConjunct(MakeRootConjunct(nil, v)) |
| return n |
| } |
| } |
| |
| // Unwrap returns the possibly non-concrete scalar value of v or nil if v is |
| // a list, struct or of undefined type. |
| func Unwrap(v Value) Value { |
| x, ok := v.(*Vertex) |
| if !ok { |
| return v |
| } |
| return x.Value() |
| } |
| |
| // Acceptor is a single interface that reports whether feature f is a valid |
| // field label for this vertex. |
| // |
| // TODO: combine this with the StructMarker functionality? |
| type Acceptor interface { |
| // Accept reports whether a given field is accepted as output. |
| // Pass an InvalidLabel to determine whether this is always open. |
| Accept(ctx *OpContext, f Feature) bool |
| |
| // MatchAndInsert finds the conjuncts for optional fields, pattern |
| // constraints, and additional constraints that match f and inserts them in |
| // arc. Use f is 0 to match all additional constraints only. |
| MatchAndInsert(c *OpContext, arc *Vertex) |
| |
| // OptionalTypes returns a bit field with the type of optional constraints |
| // that are represented by this Acceptor. |
| OptionalTypes() OptionalType |
| |
| // IsOptional reports whether a field is explicitly defined as optional, |
| // as opposed to whether it is allowed by a pattern constraint. |
| IsOptional(f Feature) bool |
| } |
| |
| // OptionalType is a bit field of the type of optional constraints in use by an |
| // Acceptor. |
| type OptionalType int |
| |
| const ( |
| HasField OptionalType = 1 << iota // X: T |
| HasDynamic // (X): T or "\(X)": T |
| HasPattern // [X]: T |
| HasAdditional // ...T |
| IsOpen // Defined for all fields |
| ) |
| |
| func (v *Vertex) Kind() Kind { |
| // This is possible when evaluating comprehensions. It is potentially |
| // not known at this time what the type is. |
| if v.BaseValue == nil { |
| return TopKind |
| } |
| return v.BaseValue.Kind() |
| } |
| |
| func (v *Vertex) OptionalTypes() OptionalType { |
| switch { |
| case v.Closed != nil: |
| return v.Closed.OptionalTypes() |
| case v.IsList(): |
| return 0 |
| default: |
| return IsOpen |
| } |
| } |
| |
| func (v *Vertex) IsClosed(ctx *OpContext) bool { |
| switch x := v.BaseValue.(type) { |
| case *ListMarker: |
| // TODO: use one mechanism. |
| if x.IsOpen { |
| return false |
| } |
| if v.Closed == nil { |
| return true |
| } |
| return !v.Closed.Accept(ctx, InvalidLabel) |
| |
| case *StructMarker: |
| if x.NeedClose { |
| return true |
| } |
| if v.Closed == nil { |
| return false |
| } |
| return !v.Closed.Accept(ctx, InvalidLabel) |
| } |
| return false |
| } |
| |
| func (v *Vertex) Accept(ctx *OpContext, f Feature) bool { |
| if !v.IsClosed(ctx) || v.Lookup(f) != nil { |
| return true |
| } |
| if v.Closed != nil { |
| return v.Closed.Accept(ctx, f) |
| } |
| return false |
| } |
| |
| func (v *Vertex) MatchAndInsert(ctx *OpContext, arc *Vertex) { |
| if v.Closed == nil { |
| return |
| } |
| if !v.Accept(ctx, arc.Label) { |
| return |
| } |
| v.Closed.MatchAndInsert(ctx, arc) |
| } |
| |
| func (v *Vertex) IsList() bool { |
| _, ok := v.BaseValue.(*ListMarker) |
| return ok |
| } |
| |
| // Lookup returns the Arc with label f if it exists or nil otherwise. |
| func (v *Vertex) Lookup(f Feature) *Vertex { |
| for _, a := range v.Arcs { |
| if a.Label == f { |
| return a |
| } |
| } |
| return nil |
| } |
| |
| // Elems returns the regular elements of a list. |
| func (v *Vertex) Elems() []*Vertex { |
| // TODO: add bookkeeping for where list arcs start and end. |
| a := make([]*Vertex, 0, len(v.Arcs)) |
| for _, x := range v.Arcs { |
| if x.Label.IsInt() { |
| a = append(a, x) |
| } |
| } |
| return a |
| } |
| |
| // GetArc returns a Vertex for the outgoing arc with label f. It creates and |
| // ads one if it doesn't yet exist. |
| func (v *Vertex) GetArc(f Feature) (arc *Vertex, isNew bool) { |
| arc = v.Lookup(f) |
| if arc == nil { |
| arc = &Vertex{Parent: v, Label: f} |
| v.Arcs = append(v.Arcs, arc) |
| isNew = true |
| } |
| return arc, isNew |
| } |
| |
| func (v *Vertex) Source() ast.Node { return nil } |
| |
| // AddConjunct adds the given Conjuncts to v if it doesn't already exist. |
| func (v *Vertex) AddConjunct(c Conjunct) *Bottom { |
| if v.BaseValue != nil { |
| // TODO: investigate why this happens at all. Removing it seems to |
| // change the order of fields in some cases. |
| // |
| // This is likely a bug in the evaluator and should not happen. |
| return &Bottom{Err: errors.Newf(token.NoPos, "cannot add conjunct")} |
| } |
| v.Conjuncts = append(v.Conjuncts, c) |
| return nil |
| } |
| |
| func (v *Vertex) AddStructs(a ...*StructLit) { |
| outer: |
| for _, s := range a { |
| for _, t := range v.Structs { |
| if t == s { |
| continue outer |
| } |
| } |
| v.Structs = append(v.Structs, s) |
| } |
| } |
| |
| // Path computes the sequence of Features leading from the root to of the |
| // instance to this Vertex. |
| func (v *Vertex) Path() []Feature { |
| return appendPath(nil, v) |
| } |
| |
| func appendPath(a []Feature, v *Vertex) []Feature { |
| if v.Parent == nil { |
| return a |
| } |
| a = appendPath(a, v.Parent) |
| if v.Label != 0 { |
| // A Label may be 0 for programmatically inserted nodes. |
| a = append(a, v.Label) |
| } |
| return a |
| } |
| |
| // An Conjunct is an Environment-Expr pair. The Environment is the starting |
| // point for reference lookup for any reference contained in X. |
| type Conjunct struct { |
| Env *Environment |
| x Node |
| |
| // CloseID is a unique number that tracks a group of conjuncts that need |
| // belong to a single originating definition. |
| CloseID ID |
| } |
| |
| func (c *Conjunct) ID() ID { |
| return c.CloseID |
| } |
| |
| // TODO(perf): replace with composite literal if this helps performance. |
| |
| // MakeRootConjunct creates a conjunct from the given environment and node. |
| // It panics if x cannot be used as an expression. |
| func MakeRootConjunct(env *Environment, x Node) Conjunct { |
| return MakeConjunct(env, x, 0) |
| } |
| |
| func MakeConjunct(env *Environment, x Node, id ID) Conjunct { |
| if env == nil { |
| // TODO: better is to pass one. |
| env = &Environment{} |
| } |
| switch x.(type) { |
| case Expr, interface{ expr() Expr }: |
| default: |
| panic(fmt.Sprintf("invalid Node type %T", x)) |
| } |
| return Conjunct{env, x, id} |
| } |
| |
| func (c *Conjunct) Source() ast.Node { |
| return c.x.Source() |
| } |
| |
| func (c *Conjunct) Field() Node { |
| return c.x |
| } |
| |
| func (c *Conjunct) Expr() Expr { |
| switch x := c.x.(type) { |
| case Expr: |
| return x |
| case interface{ expr() Expr }: |
| return x.expr() |
| default: |
| panic("unreachable") |
| } |
| } |