internal/core/adt: initial commit
Defines Abstract Data Types. These are internal
types used by the CUE evaluator.
Change-Id: Ibb109bf3b5d63525199cab05ec609595bee0a5bf
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/6500
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
Reviewed-by: CUE cueckoo <cueckoo@gmail.com>
diff --git a/internal/core/adt/adt.go b/internal/core/adt/adt.go
new file mode 100644
index 0000000..2a91ff9
--- /dev/null
+++ b/internal/core/adt/adt.go
@@ -0,0 +1,289 @@
+// 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 "cuelang.org/go/cue/ast"
+
+// A Node is any abstract data type representing an value or expression.
+type Node interface {
+ Source() ast.Node
+ node() // enforce internal.
+}
+
+// A Decl represents all valid StructLit elements.
+type Decl interface {
+ Node
+ declNode()
+}
+
+// An Elem represents all value ListLit elements.
+//
+// All Elem values can be used as a Decl.
+type Elem interface {
+ Decl
+ elemNode()
+}
+
+// An Expr corresponds to an ast.Expr.
+//
+// All Expr values can be used as an Elem or Decl.
+type Expr interface {
+ Elem
+ expr()
+}
+
+// A Value represents a node in the evaluated data graph.
+//
+// All Values values can also be used as a Expr.
+type Value interface {
+ Expr
+ Concreteness() Concreteness
+ Kind() Kind
+}
+
+// An Evaluator provides a method to convert to a value.
+type Evaluator interface {
+ Node
+ // TODO: Eval(c Context, env *Environment) Value
+}
+
+// A Resolver represents a reference somewhere else within a tree that resolves
+// a value.
+type Resolver interface {
+ Node
+ // TODO: Resolve(c Context, env *Environment) Arc
+}
+
+// A Yielder represents 0 or more labeled values of structs or lists.
+type Yielder interface {
+ Node
+ yielderNode()
+ // TODO: Yield()
+}
+
+// A Validator validates a Value. All Validators are Values.
+type Validator interface {
+ // TODO: Validate(c Context, v Value) *Bottom
+ Value
+}
+
+// Value
+
+func (x *Vertex) Concreteness() Concreteness {
+ // Depends on concreteness of value.
+ if x.Value == nil {
+ return Concrete // Should be indetermined.
+ }
+ return x.Value.Concreteness()
+}
+
+func (x *ListMarker) Concreteness() Concreteness { return Concrete }
+func (x *StructMarker) Concreteness() Concreteness { return Concrete }
+
+func (*Conjunction) Concreteness() Concreteness { return Constraint }
+func (*Disjunction) Concreteness() Concreteness { return Constraint }
+func (*BoundValue) Concreteness() Concreteness { return Constraint }
+func (*BuiltinValidator) Concreteness() Concreteness { return Constraint }
+
+// Value and Expr
+
+func (*Bottom) Concreteness() Concreteness { return BottomLevel }
+func (*Null) Concreteness() Concreteness { return Concrete }
+func (*Bool) Concreteness() Concreteness { return Concrete }
+func (*Num) Concreteness() Concreteness { return Concrete }
+func (*String) Concreteness() Concreteness { return Concrete }
+func (*Bytes) Concreteness() Concreteness { return Concrete }
+func (*Top) Concreteness() Concreteness { return Any }
+func (*BasicType) Concreteness() Concreteness { return Type }
+
+// Expr
+
+func (*StructLit) expr() {}
+func (*ListLit) expr() {}
+func (*DisjunctionExpr) expr() {}
+
+// Expr and Value
+
+func (*Bottom) expr() {}
+func (*Null) expr() {}
+func (*Bool) expr() {}
+func (*Num) expr() {}
+func (*String) expr() {}
+func (*Bytes) expr() {}
+func (*Top) expr() {}
+func (*BasicType) expr() {}
+func (*Vertex) expr() {}
+func (*ListMarker) expr() {}
+func (*StructMarker) expr() {}
+func (*Conjunction) expr() {}
+func (*Disjunction) expr() {}
+func (*BoundValue) expr() {}
+func (*BuiltinValidator) expr() {}
+
+// Expr and Resolver
+
+func (*FieldReference) expr() {}
+func (*LabelReference) expr() {}
+func (*DynamicReference) expr() {}
+func (*ImportReference) expr() {}
+func (*LetReference) expr() {}
+
+// Expr and Evaluator
+
+func (*BoundExpr) expr() {}
+func (*SelectorExpr) expr() {}
+func (*IndexExpr) expr() {}
+func (*SliceExpr) expr() {}
+func (*Interpolation) expr() {}
+func (*UnaryExpr) expr() {}
+func (*BinaryExpr) expr() {}
+func (*CallExpr) expr() {}
+
+// Decl and Expr (so allow attaching original source in Conjunct)
+
+func (*Field) declNode() {}
+func (x *Field) expr() Expr { return x.Value }
+func (*OptionalField) declNode() {}
+func (x *OptionalField) expr() Expr { return x.Value }
+func (*BulkOptionalField) declNode() {}
+func (x *BulkOptionalField) expr() Expr { return x.Value }
+func (*DynamicField) declNode() {}
+func (x *DynamicField) expr() Expr { return x.Value }
+
+// Decl and Yielder
+
+func (*LetClause) declNode() {}
+func (*LetClause) yielderNode() {}
+
+// Decl and Elem
+
+func (*StructLit) declNode() {}
+func (*StructLit) elemNode() {}
+func (*ListLit) declNode() {}
+func (*ListLit) elemNode() {}
+func (*Ellipsis) elemNode() {}
+func (*Ellipsis) declNode() {}
+func (*Bottom) declNode() {}
+func (*Bottom) elemNode() {}
+func (*Null) declNode() {}
+func (*Null) elemNode() {}
+func (*Bool) declNode() {}
+func (*Bool) elemNode() {}
+func (*Num) declNode() {}
+func (*Num) elemNode() {}
+func (*String) declNode() {}
+func (*String) elemNode() {}
+func (*Bytes) declNode() {}
+func (*Bytes) elemNode() {}
+func (*Top) declNode() {}
+func (*Top) elemNode() {}
+func (*BasicType) declNode() {}
+func (*BasicType) elemNode() {}
+func (*BoundExpr) declNode() {}
+func (*BoundExpr) elemNode() {}
+func (*Vertex) declNode() {}
+func (*Vertex) elemNode() {}
+func (*ListMarker) declNode() {}
+func (*ListMarker) elemNode() {}
+func (*StructMarker) declNode() {}
+func (*StructMarker) elemNode() {}
+func (*Conjunction) declNode() {}
+func (*Conjunction) elemNode() {}
+func (*Disjunction) declNode() {}
+func (*Disjunction) elemNode() {}
+func (*BoundValue) declNode() {}
+func (*BoundValue) elemNode() {}
+func (*BuiltinValidator) declNode() {}
+func (*BuiltinValidator) elemNode() {}
+func (*FieldReference) declNode() {}
+func (*FieldReference) elemNode() {}
+func (*LabelReference) declNode() {}
+func (*LabelReference) elemNode() {}
+func (*DynamicReference) declNode() {}
+func (*DynamicReference) elemNode() {}
+func (*ImportReference) declNode() {}
+func (*ImportReference) elemNode() {}
+func (*LetReference) declNode() {}
+func (*LetReference) elemNode() {}
+func (*SelectorExpr) declNode() {}
+func (*SelectorExpr) elemNode() {}
+func (*IndexExpr) declNode() {}
+func (*IndexExpr) elemNode() {}
+func (*SliceExpr) declNode() {}
+func (*SliceExpr) elemNode() {}
+func (*Interpolation) declNode() {}
+func (*Interpolation) elemNode() {}
+func (*UnaryExpr) declNode() {}
+func (*UnaryExpr) elemNode() {}
+func (*BinaryExpr) declNode() {}
+func (*BinaryExpr) elemNode() {}
+func (*CallExpr) declNode() {}
+func (*CallExpr) elemNode() {}
+func (*DisjunctionExpr) declNode() {}
+func (*DisjunctionExpr) elemNode() {}
+
+// Decl, Elem, and Yielder
+
+func (*ForClause) declNode() {}
+func (*ForClause) elemNode() {}
+func (*ForClause) yielderNode() {}
+func (*IfClause) declNode() {}
+func (*IfClause) elemNode() {}
+func (*IfClause) yielderNode() {}
+
+// Yielder
+
+func (*ValueClause) yielderNode() {}
+
+// Node
+
+func (*Vertex) node() {}
+func (*Conjunction) node() {}
+func (*Disjunction) node() {}
+func (*BoundValue) node() {}
+func (*BuiltinValidator) node() {}
+func (*Bottom) node() {}
+func (*Null) node() {}
+func (*Bool) node() {}
+func (*Num) node() {}
+func (*String) node() {}
+func (*Bytes) node() {}
+func (*Top) node() {}
+func (*BasicType) node() {}
+func (*StructLit) node() {}
+func (*ListLit) node() {}
+func (*BoundExpr) node() {}
+func (*FieldReference) node() {}
+func (*LabelReference) node() {}
+func (*DynamicReference) node() {}
+func (*ImportReference) node() {}
+func (*LetReference) node() {}
+func (*SelectorExpr) node() {}
+func (*IndexExpr) node() {}
+func (*SliceExpr) node() {}
+func (*Interpolation) node() {}
+func (*UnaryExpr) node() {}
+func (*BinaryExpr) node() {}
+func (*CallExpr) node() {}
+func (*DisjunctionExpr) node() {}
+func (*Field) node() {}
+func (*OptionalField) node() {}
+func (*BulkOptionalField) node() {}
+func (*DynamicField) node() {}
+func (*Ellipsis) node() {}
+func (*ForClause) node() {}
+func (*IfClause) node() {}
+func (*LetClause) node() {}
+func (*ValueClause) node() {}
diff --git a/internal/core/adt/composite.go b/internal/core/adt/composite.go
new file mode 100644
index 0000000..bd5f99b
--- /dev/null
+++ b/internal/core/adt/composite.go
@@ -0,0 +1,163 @@
+// 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 (
+ "cuelang.org/go/cue/ast"
+ "cuelang.org/go/cue/errors"
+ "cuelang.org/go/cue/token"
+)
+
+// 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
+}
+
+// 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 *Vertex // Do we need this?
+
+ // Label is the feature leading to this vertex.
+ Label Feature
+
+ // Value is the value associated with this vertex. For lists and structs
+ // this is a sentinel value indicating its kind.
+ Value Value
+
+ // 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 information is used to compute
+ // the topological sort of arcs.
+ Conjuncts []Conjunct
+
+ // Structs is a slice of struct literals that contributed to this value.
+ Structs []*StructLit
+}
+
+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.Value == nil {
+ return TopKind
+ }
+ return v.Value.Kind()
+}
+
+func (v *Vertex) IsList() bool {
+ _, ok := v.Value.(*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
+}
+
+// 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 {
+ for _, x := range v.Conjuncts {
+ if x == c {
+ return nil
+ }
+ }
+ if v.Value != nil {
+ // 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
+}
+
+// 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)
+ return append(a, v.Label)
+}
+
+// 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
+}
+
+// TODO(perf): replace with composite literal if this helps performance.
+
+// MakeConjunct creates a conjunct from the given environment and node.
+// It panics if x cannot be used as an expression.
+func MakeConjunct(env *Environment, x Node) Conjunct {
+ switch x.(type) {
+ case Expr, interface{ expr() Expr }:
+ default:
+ panic("invalid Node type")
+ }
+ return Conjunct{env, x}
+}
+
+func (c *Conjunct) Source() ast.Node {
+ return c.x.Source()
+}
+
+func (c *Conjunct) Expr() Expr {
+ switch x := c.x.(type) {
+ case Expr:
+ return x
+ case interface{ expr() Expr }:
+ return x.expr()
+ default:
+ panic("unreachable")
+ }
+}
diff --git a/internal/core/adt/doc.go b/internal/core/adt/doc.go
new file mode 100644
index 0000000..ba251b5
--- /dev/null
+++ b/internal/core/adt/doc.go
@@ -0,0 +1,78 @@
+// 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 represents partially and fully evaluated CUE types.
+//
+// This package introduces several categories of types that indicate some set of
+// values that may be used in a certain situation. Concrete types may belong to
+// multiple categories.
+//
+//
+// Abstract Types
+//
+// The following types describe the a place where a value may be used:
+//
+// Decl a value than can be used as a StructLit element.
+// Elem a value than can be used as a ListLit element.
+// Expr represents an Expr in the CUE grammar.
+// Value a fully evaluated value that has no references (except for
+// children in composite values).
+// Node any of the above values.
+//
+// The following types categorize nodes by function:
+//
+// Resolver a reference to position in the result tree.
+// Evaluator evaluates to 1 value.
+// Yielder evaluates to 0 or more values.
+// Validator validates another value.
+//
+//
+// Reference resolution algorithm
+//
+// A Resolver is resolved within the context of an Environment. In CUE, a
+// reference is evaluated by substituting it with a copy of the value to which
+// it refers. If the copied value itself contains references we can distinguish
+// two different cases. References that refer to values within the copied
+// reference (not regarding selectors) will henceforth point to the copied node.
+// References that point to outside the referened value will keep refering to
+// their original value.
+//
+// a: b: {
+// c: int
+// d: c
+// e: f
+// }
+// f: 4
+// g: a.b { // d.c points to inside the referred value, e.f, not.
+// c: 3
+// }
+//
+// The implementation doesn't actually copy referred values, but rather resolves
+// references with the aid of an Environment. During compile time, each
+// references is associated with the label and a number indicating in which
+// parent scope (offset from the current) this label needs to be looked up. An
+// Environment keeps track of the point at which a value was referenced,
+// providing enough information to look up the labeled value. This Environment
+// is the identical for all references within a fields conjunct. Often, an
+// Environment can even be shared among conjuncts.
+//
+//
+// Values
+//
+// Values are fully evaluated expressions. As this means that all references
+// will have been eliminated, Values are fully defined without the need for an
+// Environment. Additionally, Values represent a fully evaluated form, stripped
+// of any comprehensions, optional fields or embeddings.
+//
+package adt
diff --git a/internal/core/adt/expr.go b/internal/core/adt/expr.go
new file mode 100644
index 0000000..c36ea9c
--- /dev/null
+++ b/internal/core/adt/expr.go
@@ -0,0 +1,546 @@
+// 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 (
+ "regexp"
+
+ "github.com/cockroachdb/apd/v2"
+
+ "cuelang.org/go/cue/ast"
+ "cuelang.org/go/cue/errors"
+ "cuelang.org/go/cue/token"
+)
+
+// A StructLit represents an unevaluated struct literal or file body.
+type StructLit struct {
+ Src ast.Node // ast.File or ast.StructLit
+ Decls []Decl
+
+ // administrative fields like hasreferences.
+ // hasReferences bool
+}
+
+func (x *StructLit) Source() ast.Node { return x.Src }
+
+// FIELDS
+//
+// Fields can also be used as expressions whereby the value field is the
+// expression this allows retaining more context.
+
+// Field represents a field with a fixed label. It can be a regular field,
+// definition or hidden field.
+//
+// foo: bar
+// #foo: bar
+// _foo: bar
+//
+// Legacy:
+//
+// Foo :: bar
+//
+type Field struct {
+ Src *ast.Field
+
+ Label Feature
+ Value Expr
+}
+
+func (x *Field) Source() ast.Node { return x.Src }
+
+// An OptionalField represents an optional regular field.
+//
+// foo?: expr
+//
+type OptionalField struct {
+ Src *ast.Field
+ Label Feature
+ Value Expr
+}
+
+func (x *OptionalField) Source() ast.Node { return x.Src }
+
+// A BulkOptionalField represents a set of optional field.
+//
+// [expr]: expr
+//
+type BulkOptionalField struct {
+ Src *ast.Field // Elipsis or Field
+ Filter Expr
+ Value Expr
+ Label Feature // for reference and formatting
+}
+
+func (x *BulkOptionalField) Source() ast.Node { return x.Src }
+
+// A Ellipsis represents a set of optional fields of a given type.
+//
+// ...T
+//
+type Ellipsis struct {
+ Src *ast.Ellipsis
+ Value Expr
+}
+
+func (x *Ellipsis) Source() ast.Node { return x.Src }
+
+// A DynamicField represents a regular field for which the key is computed.
+//
+// "\(expr)": expr
+// (expr): expr
+//
+type DynamicField struct {
+ Src *ast.Field
+ Key Expr
+ Value Expr
+}
+
+func (x *DynamicField) IsOptional() bool {
+ return x.Src.Optional != token.NoPos
+}
+
+func (x *DynamicField) Source() ast.Node { return x.Src }
+
+// Expressions
+
+// A ListLit represents an unevaluated list literal.
+//
+// [a, for x in src { ... }, b, ...T]
+//
+type ListLit struct {
+ Src *ast.ListLit
+
+ // scalars, comprehensions, ...T
+ Elems []Elem
+}
+
+func (x *ListLit) Source() ast.Node { return x.Src }
+
+// -- Literals
+
+// Bottom represents an error or bottom symbol.
+type Bottom struct {
+ Src ast.Node
+ Err errors.Error
+}
+
+func (x *Bottom) Source() ast.Node { return x.Src }
+func (x *Bottom) Kind() Kind { return BottomKind }
+
+// Null represents null. It can be used as a Value and Expr.
+type Null struct {
+ Src ast.Node
+}
+
+func (x *Null) Source() ast.Node { return x.Src }
+func (x *Null) Kind() Kind { return NullKind }
+
+// Bool is a boolean value. It can be used as a Value and Expr.
+type Bool struct {
+ Src ast.Node
+ B bool
+}
+
+func (x *Bool) Source() ast.Node { return x.Src }
+func (x *Bool) Kind() Kind { return BoolKind }
+
+// Num is a numeric value. It can be used as a Value and Expr.
+type Num struct {
+ Src ast.Node
+ K Kind // needed?
+ X apd.Decimal // Is integer if the apd.Decimal is an integer.
+}
+
+func (x *Num) Source() ast.Node { return x.Src }
+func (x *Num) Kind() Kind { return x.K }
+
+// String is a string value. It can be used as a Value and Expr.
+type String struct {
+ Src ast.Node
+ Str string
+ RE *regexp.Regexp // only set if needed
+}
+
+func (x *String) Source() ast.Node { return x.Src }
+func (x *String) Kind() Kind { return StringKind }
+
+// Bytes is a bytes value. It can be used as a Value and Expr.
+type Bytes struct {
+ Src ast.Node
+ B []byte
+ RE *regexp.Regexp // only set if needed
+}
+
+func (x *Bytes) Source() ast.Node { return x.Src }
+func (x *Bytes) Kind() Kind { return BytesKind }
+
+// -- composites: the evaluated fields of a composite are recorded in the arc
+// vertices.
+
+type ListMarker struct {
+ Src ast.Node
+}
+
+func (x *ListMarker) Source() ast.Node { return x.Src }
+func (x *ListMarker) Kind() Kind { return ListKind }
+func (x *ListMarker) node() {}
+
+type StructMarker struct {
+ Closed bool
+}
+
+func (x *StructMarker) Source() ast.Node { return nil }
+func (x *StructMarker) Kind() Kind { return StructKind }
+func (x *StructMarker) node() {}
+
+// -- top types
+
+// Top represents all possible values. It can be used as a Value and Expr.
+type Top struct{ Src *ast.Ident }
+
+func (x *Top) Source() ast.Node { return x.Src }
+func (x *Top) Kind() Kind { return TopKind }
+
+// BasicType represents all values of a certain Kind. It can be used as a Value
+// and Expr.
+//
+// string
+// int
+// num
+// bool
+//
+type BasicType struct {
+ Src *ast.Ident
+ K Kind
+}
+
+func (x *BasicType) Source() ast.Node { return x.Src }
+func (x *BasicType) Kind() Kind { return x.K }
+
+// TODO: should we use UnaryExpr for Bound now we have BoundValue?
+
+// BoundExpr represents an unresolved unary comparator.
+//
+// <a
+// =~MyPattern
+//
+type BoundExpr struct {
+ Src *ast.UnaryExpr
+ Op Op
+ Expr Expr
+}
+
+func (x *BoundExpr) Source() ast.Node { return x.Src }
+
+// A BoundValue is a fully evaluated unary comparator that can be used to
+// validate other values.
+//
+// <5
+// =~"Name$"
+//
+type BoundValue struct {
+ Src ast.Node
+ Op Op
+ Value Value
+ K Kind
+}
+
+func (x *BoundValue) Source() ast.Node { return x.Src }
+func (x *BoundValue) Kind() Kind { return x.K }
+
+// -- References
+
+// A FieldReference represents a lexical reference to a field.
+//
+// a
+//
+type FieldReference struct {
+ Src *ast.Ident
+ UpCount int32
+ Label Feature
+}
+
+func (x *FieldReference) Source() ast.Node { return x.Src }
+
+// A LabelReference refers to the string or integer value of a label.
+//
+// [X=Pattern]: b: X
+//
+type LabelReference struct {
+ Src *ast.Ident
+ UpCount int32
+}
+
+// TODO: should this implement resolver at all?
+
+func (x *LabelReference) Source() ast.Node { return x.Src }
+
+// A DynamicReference is like a LabelReference, but with a computed label.
+//
+// X=(x): X
+// X="\(x)": X
+//
+type DynamicReference struct {
+ Src *ast.Ident
+ UpCount int32
+ Label Expr
+
+ // TODO: only use aliases and store the actual expression only in the scope.
+ // The feature is unique for every instance. This will also allow dynamic
+ // fields to be ordered among normal fields.
+ //
+ // This could also be used to assign labels to embedded values, if they
+ // don't match a label.
+ Alias Feature
+}
+
+func (x *DynamicReference) Source() ast.Node { return x.Src }
+
+// An ImportReference refers to an imported package.
+//
+// import "strings"
+//
+// strings.ToLower("Upper")
+//
+type ImportReference struct {
+ Src *ast.Ident
+ ImportPath Feature
+ Label Feature // for informative purposes
+}
+
+func (x *ImportReference) Source() ast.Node { return x.Src }
+
+// A LetReference evaluates a let expression in its original environment.
+//
+// let X = x
+//
+type LetReference struct {
+ Src *ast.Ident
+ UpCount int32
+ Label Feature // for informative purposes
+ X Expr
+}
+
+func (x *LetReference) Source() ast.Node { return x.Src }
+
+// A SelectorExpr looks up a fixed field in an expression.
+//
+// X.Sel
+//
+type SelectorExpr struct {
+ Src *ast.SelectorExpr
+ X Expr
+ Sel Feature
+}
+
+func (x *SelectorExpr) Source() ast.Node { return x.Src }
+
+// IndexExpr is like a selector, but selects an index.
+//
+// X[Index]
+//
+type IndexExpr struct {
+ Src *ast.IndexExpr
+ X Expr
+ Index Expr
+}
+
+func (x *IndexExpr) Source() ast.Node { return x.Src }
+
+// A SliceExpr represents a slice operation. (Not currently in spec.)
+//
+// X[Lo:Hi:Stride]
+//
+type SliceExpr struct {
+ Src *ast.SliceExpr
+ X Expr
+ Lo Expr
+ Hi Expr
+ Stride Expr
+}
+
+func (x *SliceExpr) Source() ast.Node { return x.Src }
+
+// An Interpolation is a string interpolation.
+//
+// "a \(b) c"
+//
+type Interpolation struct {
+ Src *ast.Interpolation
+ K Kind // string or bytes
+ Parts []Expr // odd: strings, even sources
+}
+
+func (x *Interpolation) Source() ast.Node { return x.Src }
+
+// UnaryExpr is a unary expression.
+//
+// Op X
+// -X !X +X
+//
+type UnaryExpr struct {
+ Src *ast.UnaryExpr
+ Op Op
+ X Expr
+}
+
+func (x *UnaryExpr) Source() ast.Node { return x.Src }
+
+// BinaryExpr is a binary expression.
+//
+// X + Y
+// X & Y
+//
+type BinaryExpr struct {
+ Src *ast.BinaryExpr
+ Op Op
+ X Expr
+ Y Expr
+}
+
+func (x *BinaryExpr) Source() ast.Node { return x.Src }
+
+// -- builtins
+
+// A CallExpr represents a call to a builtin.
+//
+// len(x)
+// strings.ToLower(x)
+//
+type CallExpr struct {
+ Src *ast.CallExpr
+ Fun Expr
+ Args []Expr
+}
+
+func (x *CallExpr) Source() ast.Node { return x.Src }
+
+// A BuiltinValidator is a Value that results from evaluation a partial call
+// to a builtin (using CallExpr).
+//
+// strings.MinRunes(4)
+//
+type BuiltinValidator struct {
+ Src *ast.CallExpr
+ Fun Expr // TODO: should probably be builtin.
+ Args []Value // any but the first value
+ // call *builtin // function must return a bool
+}
+
+func (x *BuiltinValidator) Source() ast.Node { return x.Src }
+func (x *BuiltinValidator) Kind() Kind { return TopKind }
+
+// A Disjunction represents a disjunction, where each disjunct may or may not
+// be marked as a default.
+type DisjunctionExpr struct {
+ Src *ast.BinaryExpr
+ Values []Disjunct
+
+ HasDefaults bool
+}
+
+// A Disjunct is used in Disjunction.
+type Disjunct struct {
+ Val Expr
+ Default bool
+}
+
+func (x *DisjunctionExpr) Source() ast.Node {
+ if x.Src == nil {
+ return nil
+ }
+ return x.Src
+}
+
+// A Conjunction is a conjunction of values that cannot be represented as a
+// single value. It is the result of unification.
+type Conjunction struct {
+ Values []Value
+}
+
+func (x *Conjunction) Source() ast.Node { return nil }
+func (x *Conjunction) Kind() Kind { return TopKind }
+
+// A disjunction is a disjunction of values. It is the result of expanding
+// a DisjunctionExpr if the expression cannot be represented as a single value.
+type Disjunction struct {
+ Src ast.Expr
+
+ // Values are the non-error disjuncts of this expression. The first
+ // NumDefault values are default values.
+ Values []*Vertex
+
+ Errors *Bottom // []bottom
+
+ // NumDefaults indicates the number of default values.
+ NumDefaults int
+}
+
+func (x *Disjunction) Source() ast.Node { return x.Src }
+func (x *Disjunction) Kind() Kind {
+ k := BottomKind
+ for _, v := range x.Values {
+ k |= v.Kind()
+ }
+ return k
+}
+
+// A ForClause represents a for clause of a comprehension. It can be used
+// as a struct or list element.
+//
+// for k, v in src {}
+//
+type ForClause struct {
+ Syntax *ast.ForClause
+ Key Feature
+ Value Feature
+ Src Expr
+ Dst Yielder
+}
+
+func (x *ForClause) Source() ast.Node { return x.Syntax }
+
+// An IfClause represents an if clause of a comprehension. It can be used
+// as a struct or list element.
+//
+// if cond {}
+//
+type IfClause struct {
+ Src *ast.IfClause
+ Condition Expr
+ Dst Yielder
+}
+
+func (x *IfClause) Source() ast.Node { return x.Src }
+
+// An LetClause represents a let clause in a comprehension.
+//
+// for k, v in src {}
+//
+type LetClause struct {
+ Src *ast.LetClause
+ Label Feature
+ Expr Expr
+ Dst Yielder
+}
+
+func (x *LetClause) Source() ast.Node { return x.Src }
+
+// A ValueClause represents the value part of a comprehension.
+type ValueClause struct {
+ *StructLit
+}
+
+func (x *ValueClause) Source() ast.Node { return x.Src }
diff --git a/internal/core/adt/feature.go b/internal/core/adt/feature.go
new file mode 100644
index 0000000..684a74e
--- /dev/null
+++ b/internal/core/adt/feature.go
@@ -0,0 +1,137 @@
+// 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 (
+ "strconv"
+
+ "cuelang.org/go/cue/ast"
+ "cuelang.org/go/cue/errors"
+ "cuelang.org/go/cue/token"
+ "cuelang.org/go/internal"
+)
+
+// A Feature is an encoded form of a label which comprises a compact
+// representation of an integer or string label as well as a label type.
+type Feature uint32
+
+// InvalidLabel is an encoding of an erroneous label.
+const InvalidLabel Feature = 0x7 // 0xb111
+
+// MaxIndex indicates the maximum number of unique strings that are used for
+// labeles within this CUE implementation.
+const MaxIndex int64 = 1<<28 - 1
+
+// A StringIndexer coverts strings to and from an index that is unique for a
+// given string.
+type StringIndexer interface {
+ // ToIndex returns a unique positive index for s (0 < index < 2^28-1).
+ //
+ // For each pair of strings s and t it must return the same index if and
+ // only if s == t.
+ StringToIndex(s string) (index int64)
+
+ // ToString returns a string s for index such that ToIndex(s) == index.
+ IndexToString(index int64) string
+}
+
+// SelectorString reports the shortest string representation of f when used as a
+// selector.
+func (f Feature) SelectorString(index StringIndexer) string {
+ if f == 0 {
+ return "_"
+ }
+ x := f.Index()
+ switch f.Typ() {
+ case IntLabel:
+ return strconv.Itoa(int(x))
+ case StringLabel:
+ s := index.IndexToString(int64(x))
+ if ast.IsValidIdent(s) && !internal.IsDefOrHidden(s) {
+ return s
+ }
+ return strconv.Quote(s)
+ default:
+ return index.IndexToString(int64(x))
+ }
+}
+
+// MakeLabel creates a label. It reports an error if the index is out of range.
+func MakeLabel(p token.Pos, index int64, f FeatureType) (Feature, errors.Error) {
+ if 0 > index || index > MaxIndex {
+ return InvalidLabel,
+ errors.Newf(p, "int label out of range (%d not >=0 and <= %d)",
+ index, MaxIndex)
+ }
+ return Feature(index)<<indexShift | Feature(f), nil
+}
+
+// A FeatureType indicates the type of label.
+type FeatureType int8
+
+const (
+ StringLabel FeatureType = 0 // 0b000
+ IntLabel FeatureType = 1 // 0b001
+ DefinitionLabel FeatureType = 3 // 0b011
+ HiddenLabel FeatureType = 6 // 0b110
+ HiddenDefinitionLabel FeatureType = 7 // 0b111
+
+ // letLabel FeatureType = 0b010
+
+ fTypeMask Feature = 7 // 0b111
+
+ indexShift = 3
+)
+
+// IsValid reports whether f is a valid label.
+func (f Feature) IsValid() bool { return f != InvalidLabel }
+
+// Typ reports the type of label.
+func (f Feature) Typ() FeatureType { return FeatureType(f & fTypeMask) }
+
+// IsRegular reports whether a label represents a data field.
+func (f Feature) IsRegular() bool { return f.Typ() <= IntLabel }
+
+// IsString reports whether a label represents a regular field.
+func (f Feature) IsString() bool { return f.Typ() == StringLabel }
+
+// IsDef reports whether the label is a definition (an identifier starting with
+// # or #_.
+func (f Feature) IsDef() bool {
+ if f == InvalidLabel {
+ // TODO(perf): do more mask trickery to avoid this branch.
+ return false
+ }
+ return f.Typ()&DefinitionLabel == DefinitionLabel
+}
+
+// IsInt reports whether this is an integer index.
+func (f Feature) IsInt() bool { return f.Typ() == IntLabel }
+
+// IsHidden reports whether this label is hidden (an identifier starting with
+// _ or #_).
+func (f Feature) IsHidden() bool {
+ if f == InvalidLabel {
+ // TODO(perf): do more mask trickery to avoid this branch.
+ return false
+ }
+ return f.Typ()&HiddenLabel == HiddenLabel
+}
+
+// Index reports the abstract index associated with f.
+func (f Feature) Index() int { return int(f >> indexShift) }
+
+// TODO: should let declarations be implemented as fields?
+// func (f Feature) isLet() bool { return f.typ() == letLabel }
diff --git a/internal/core/adt/kind.go b/internal/core/adt/kind.go
new file mode 100644
index 0000000..cd82b4e
--- /dev/null
+++ b/internal/core/adt/kind.go
@@ -0,0 +1,174 @@
+// Copyright 2018 The 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"
+ "math/bits"
+ "strings"
+)
+
+// Concreteness is a measure of the level of concreteness of a value, where
+// lower values mean more concrete.
+type Concreteness int
+
+const (
+ BottomLevel Concreteness = iota
+
+ // Concrete indicates a concrete scalar value, list or struct.
+ Concrete
+
+ // Constraint indicates a non-concrete scalar value that is more specific,
+ // than a top-level type.
+ Constraint
+
+ // PrimitiveType indicates a top-level specific type, for instance, string,
+ // bytes, number, or bool.
+ Type
+
+ // Any indicates any value, or top.
+ Any
+)
+
+// IsConcrete returns whether a value is concrete.
+func IsConcrete(v Value) bool {
+ if x, ok := v.(*Vertex); ok {
+ v = x.Value
+ }
+ if v == nil {
+ return false
+ }
+ return v.Concreteness() <= Concrete
+}
+
+// Kind reports the Value kind.
+type Kind uint16
+
+const (
+ NullKind Kind = (1 << iota)
+ BoolKind
+ IntKind
+ FloatKind
+ StringKind
+ BytesKind
+ ListKind
+ StructKind
+
+ allKinds
+
+ _numberKind
+
+ NumberKind = IntKind | FloatKind
+
+ BottomKind Kind = 0
+
+ NumKind = IntKind | FloatKind
+ TopKind Kind = (allKinds - 1) // all kinds, but not references
+ ScalarKinds = NullKind | BoolKind |
+ IntKind | FloatKind | StringKind | BytesKind
+)
+
+// IsAnyOf reports whether k is any of the given kinds.
+//
+// For instances, k.IsAnyOf(String|Bytes) reports whether k overlaps with
+// the String or Bytes kind.
+func (k Kind) IsAnyOf(of Kind) bool {
+ return k&of != BottomKind
+}
+
+// CanString reports whether the given type can convert to a string.
+func (k Kind) CanString() bool {
+ return k&StringKind|ScalarKinds != BottomKind
+}
+
+// String returns the representation of the Kind as
+// a CUE expression. For example:
+//
+// (IntKind|ListKind).String()
+//
+// will return:
+//
+// (int|[...])
+func (k Kind) String() string {
+ return toString(k, kindStrs)
+}
+
+// TypeString is like String, but returns a string representation of a valid
+// CUE type.
+func (k Kind) TypeString() string {
+ return toString(k, typeStrs)
+}
+
+func toString(k Kind, m map[Kind]string) string {
+ if k == BottomKind {
+ return "_|_"
+ }
+ if k == TopKind {
+ return "_"
+ }
+ if (k & NumberKind) == NumberKind {
+ k = (k &^ NumberKind) | _numberKind
+ }
+ var buf strings.Builder
+ multiple := bits.OnesCount(uint(k)) > 1
+ if multiple {
+ buf.WriteByte('(')
+ }
+ for count := 0; ; count++ {
+ n := bits.TrailingZeros(uint(k))
+ if n == bits.UintSize {
+ break
+ }
+ bit := Kind(1 << uint(n))
+ k &^= bit
+ s, ok := m[bit]
+ if !ok {
+ s = fmt.Sprintf("bad(%d)", n)
+ }
+ if count > 0 {
+ buf.WriteByte('|')
+ }
+ buf.WriteString(s)
+ }
+ if multiple {
+ buf.WriteByte(')')
+ }
+ return buf.String()
+}
+
+var kindStrs = map[Kind]string{
+ NullKind: "null",
+ BoolKind: "bool",
+ IntKind: "int",
+ FloatKind: "float",
+ StringKind: "string",
+ BytesKind: "bytes",
+ StructKind: "struct",
+ ListKind: "list",
+ _numberKind: "number",
+}
+
+// used to generate a parseable CUE type.
+var typeStrs = map[Kind]string{
+ NullKind: "null",
+ BoolKind: "bool",
+ IntKind: "int",
+ FloatKind: "float",
+ StringKind: "string",
+ BytesKind: "bytes",
+ StructKind: "{...}",
+ ListKind: "[...]",
+ _numberKind: "number",
+}
diff --git a/internal/core/adt/kind_test.go b/internal/core/adt/kind_test.go
new file mode 100644
index 0000000..749a6dd
--- /dev/null
+++ b/internal/core/adt/kind_test.go
@@ -0,0 +1,68 @@
+// 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 "testing"
+
+func TestKindString(t *testing.T) {
+ testCases := []struct {
+ input Kind
+ want string
+ }{{
+ input: BottomKind,
+ want: "_|_",
+ }, {
+ input: IntKind | ListKind,
+ want: `(int|[...])`,
+ }, {
+ input: NullKind,
+ want: "null",
+ }, {
+ input: IntKind,
+ want: "int",
+ }, {
+ input: FloatKind,
+ want: "float",
+ }, {
+ input: StringKind,
+ want: "string",
+ }, {
+ input: BytesKind,
+ want: "bytes",
+ }, {
+ input: StructKind,
+ want: "{...}",
+ }, {
+ input: ListKind,
+ want: "[...]",
+ }, {
+ input: NumberKind,
+ want: "number",
+ }, {
+ input: BoolKind | NumberKind | ListKind,
+ want: "(bool|[...]|number)",
+ }, {
+ input: 1 << 15,
+ want: "bad(15)",
+ }}
+ for _, tc := range testCases {
+ t.Run(tc.want, func(t *testing.T) {
+ got := tc.input.TypeString()
+ if got != tc.want {
+ t.Errorf("\n got %v;\nwant %v", got, tc.want)
+ }
+ })
+ }
+}
diff --git a/internal/core/adt/op.go b/internal/core/adt/op.go
new file mode 100644
index 0000000..6383290
--- /dev/null
+++ b/internal/core/adt/op.go
@@ -0,0 +1,141 @@
+// Copyright 2018 The 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 "cuelang.org/go/cue/token"
+
+// Op indicates the operation at the top of an expression tree of the expression
+// use to evaluate a value.
+type Op int
+
+func (o Op) String() string {
+ return opToString[o]
+}
+
+// Values of Op.
+const (
+ NoOp Op = iota
+
+ AndOp
+ OrOp
+
+ SelectorOp
+ IndexOp
+ SliceOp
+ CallOp
+
+ BoolAndOp
+ BoolOrOp
+
+ EqualOp
+ NotOp
+ NotEqualOp
+ LessThanOp
+ LessEqualOp
+ GreaterThanOp
+ GreaterEqualOp
+
+ MatchOp
+ NotMatchOp
+
+ AddOp
+ SubtractOp
+ MultiplyOp
+ FloatQuotientOp
+ IntQuotientOp
+ IntRemainderOp
+ IntDivideOp
+ IntModuloOp
+
+ InterpolationOp
+)
+
+var opToString = map[Op]string{
+ AndOp: "&",
+ OrOp: "|",
+ BoolAndOp: "&&",
+ BoolOrOp: "||",
+ EqualOp: "==",
+ NotOp: "!",
+ NotEqualOp: "!=",
+ LessThanOp: "<",
+ LessEqualOp: "<=",
+ GreaterThanOp: ">",
+ GreaterEqualOp: ">=",
+ MatchOp: "=~",
+ NotMatchOp: "!~",
+ AddOp: "+",
+ SubtractOp: "-",
+ MultiplyOp: "*",
+ FloatQuotientOp: "/",
+ IntQuotientOp: "quo",
+ IntRemainderOp: "rem",
+ IntDivideOp: "div",
+ IntModuloOp: "mod",
+
+ SelectorOp: ".",
+ IndexOp: "[]",
+ SliceOp: "[:]",
+ CallOp: "()",
+
+ InterpolationOp: `\()`,
+}
+
+// OpFromToken converts a token.Token to an Op.
+func OpFromToken(t token.Token) Op {
+ return tokenMap[t]
+}
+
+// Token returns the token.Token corresponding to the Op.
+func (op Op) Token() token.Token {
+ return opMap[op]
+}
+
+var tokenMap = map[token.Token]Op{
+ token.OR: OrOp, // |
+ token.AND: AndOp, // &
+
+ token.ADD: AddOp, // +
+ token.SUB: SubtractOp, // -
+ token.MUL: MultiplyOp, // *
+ token.QUO: FloatQuotientOp, // /
+
+ token.IDIV: IntDivideOp, // div
+ token.IMOD: IntModuloOp, // mod
+ token.IQUO: IntQuotientOp, // quo
+ token.IREM: IntRemainderOp, // rem
+
+ token.LAND: BoolAndOp, // &&
+ token.LOR: BoolOrOp, // ||
+
+ token.EQL: EqualOp, // ==
+ token.LSS: LessThanOp, // <
+ token.GTR: GreaterThanOp, // >
+ token.NOT: NotOp, // !
+
+ token.NEQ: NotEqualOp, // !=
+ token.LEQ: LessEqualOp, // <=
+ token.GEQ: GreaterEqualOp, // >=
+ token.MAT: MatchOp, // =~
+ token.NMAT: NotMatchOp, // !~
+}
+
+var opMap = map[Op]token.Token{}
+
+func init() {
+ for t, o := range tokenMap {
+ opMap[o] = t
+ }
+}
