cue: map API values to more native ADT
Before, Unify would add a Vertex as conjuncts and let
the evaluator treat this as a special case. The result was
not entirely correct and hard to fix. WIth this change, Unify
maps directly to a correct ADT by introduce a "phantom"
parent with the correct closed struct.
Fixes #567
Fixes #563
Fixes #561
Change-Id: I11d0e345772695d5ed6fcfd7c6b9e0f2cb2110a4
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/7746
Reviewed-by: CUE cueckoo <cueckoo@gmail.com>
Reviewed-by: Paul Jolly <paul@myitcv.org.uk>
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/types.go b/cue/types.go
index e8f97f2..f5570f5 100644
--- a/cue/types.go
+++ b/cue/types.go
@@ -1636,13 +1636,10 @@
var value = convert.GoValueToValue(ctx.opCtx, x, true)
n, _ := value.(*adt.Vertex)
if n == nil {
- n = &adt.Vertex{Label: v.v.Label}
+ n = &adt.Vertex{}
n.AddConjunct(adt.MakeRootConjunct(nil, value))
- } else {
- n.Label = v.v.Label
}
n.Finalize(ctx.opCtx)
- n.Parent = v.v.Parent
w := makeValue(v.idx, n)
return v.Unify(w)
}
@@ -1728,23 +1725,21 @@
// Value v and w must be obtained from the same build.
// TODO: remove this requirement.
func (v Value) Unify(w Value) Value {
- // ctx := v.ctx()
if v.v == nil {
return w
}
if w.v == nil {
return v
}
- n := &adt.Vertex{Label: v.v.Label}
- n.AddConjunct(adt.MakeRootConjunct(nil, v.v))
- n.AddConjunct(adt.MakeRootConjunct(nil, w.v))
+
+ n := &adt.Vertex{}
+
+ eval.AddVertex(n, v.v)
+ eval.AddVertex(n, w.v)
ctx := v.idx.newContext()
n.Finalize(ctx.opCtx)
- // We do not set the parent until here as we don't want to "inherit" the
- // closedness setting from v.
- n.Parent = v.v.Parent
return makeValue(v.idx, n)
}
@@ -1761,6 +1756,12 @@
panic("accept must exist")
}
+ // TODO: take a similar approach for UnifyAccept as for Unify. In this
+ // case though, the fields should be added as an embeding.
+ //
+ // n := &adt.Vertex{}
+ // eval.EmbedVertex(n, v.v)
+ // eval.EmbedVertex(n, w.v)
n := &adt.Vertex{Parent: v.v.Parent, Label: v.v.Label}
n.AddConjunct(adt.MakeRootConjunct(nil, v.v))
n.AddConjunct(adt.MakeRootConjunct(nil, w.v))
@@ -1782,7 +1783,6 @@
return false
}
return eval.Equal(v.ctx().opCtx, v.v, other.v)
-
}
// Format prints a debug version of a value.
diff --git a/cue/types_test.go b/cue/types_test.go
index 5bda591..bc08bd0 100644
--- a/cue/types_test.go
+++ b/cue/types_test.go
@@ -44,6 +44,60 @@
return insts[0]
}
+func TestAPI(t *testing.T) {
+ testCases := []struct {
+ input string
+ fun func(i *Instance) Value
+ want string
+ skip bool
+ }{{
+ // Issue #567
+ input: `
+ #runSpec: {action: foo: int}
+
+ v: {ction: foo: 1}
+ `,
+ fun: func(i *Instance) Value {
+ runSpec := i.LookupDef("#runSpec")
+ v := i.Lookup("v")
+ res := runSpec.Unify(v)
+ return res
+ },
+ want: "_|_(#runSpec: field `ction` not allowed)",
+ }, {
+ // Issue #567
+ input: `
+ #runSpec: {action: foo: int}
+
+ v: {action: Foo: 1}
+ `,
+ fun: func(i *Instance) Value {
+ runSpec := i.LookupDef("#runSpec")
+ v := i.Lookup("v")
+ res := runSpec.Unify(v)
+ return res
+ },
+ want: "_|_(#runSpec.action: field `Foo` not allowed)",
+ }}
+ for _, tc := range testCases {
+ if tc.skip {
+ continue
+ }
+ t.Run("", func(t *testing.T) {
+ var r Runtime
+ inst, err := r.Compile("in", tc.input)
+ if err != nil {
+ t.Fatal(err)
+ }
+ v := tc.fun(inst)
+ got := fmt.Sprintf("%+v", v)
+ if got != tc.want {
+ t.Errorf("got:\n%s\nwant:\n%s", got, tc.want)
+ }
+ })
+ }
+}
+
func TestValueType(t *testing.T) {
testCases := []struct {
value string
@@ -2574,7 +2628,6 @@
}
}
-// TODO: stack overflow
func TestPathCorrection(t *testing.T) {
testCases := []struct {
input string
diff --git a/internal/core/eval/closed.go b/internal/core/eval/closed.go
index 8fbd14d..3491dfa 100644
--- a/internal/core/eval/closed.go
+++ b/internal/core/eval/closed.go
@@ -70,11 +70,17 @@
Canopy []CloseDef
Fields []*fieldSet
- // TODO: remove (unused as not fine-grained enough)
- // isClosed is now used as an approximate filter.
+ // TODO: isClosed could be removed if we can include closedness fully
+ // in the ClosedDefs representing conjuncts. This, in turn, will allow
+ // various optimizations, like having to record field sets for data
+ // vertices.
isClosed bool
isList bool
openList bool
+
+ // ignore tells to the closedness check for one level. This allows
+ // constructed parent nodes that do not have field sets defined.
+ ignore bool
}
func (a *acceptor) clone() *acceptor {
@@ -191,6 +197,30 @@
type Entry = fieldSet
+// TODO: this may be an idea to get rid of acceptor.isClosed. There
+// are various more things to consider, though.
+//
+// func (c *acceptor) isRequired(id adt.ID) bool {
+// req := false
+// c.visitAnd(id, func(id adt.ID, n CloseDef) bool {
+// if n.isRequired() {
+// req = true
+// return false
+// }
+// c.visitEmbed(id, func(id adt.ID, n CloseDef) bool {
+// if n.isRequired() {
+// req = true
+// return false
+// }
+// req = req || c.isRequired(id)
+// return true
+// })
+
+// return true
+// })
+// return req
+// }
+
func (c *acceptor) visitAllFieldSets(f func(f *fieldSet)) {
for _, set := range c.Fields {
for ; set != nil; set = set.next {
@@ -313,7 +343,7 @@
func isComplexStruct(v *adt.Vertex) bool {
m, _ := v.Value.(*adt.StructMarker)
if m == nil {
- return true
+ return false
}
a, _ := v.Closed.(*acceptor)
if a == nil {
@@ -334,10 +364,15 @@
}
// InsertSubtree inserts the closedness information of v into c as an embedding
-// at the current position and inserts conjuncts of v into n (if not nil).
-// It inserts it as an embedding and not and to cover either case. The idea is
-// that one of the values were supposed to be closed, a separate node entry
-// would already have been created.
+// at the current position and inserts conjuncts of v into n (if not nil). It
+// inserts it as an embedding and not and to cover either case. The idea is that
+// one of the values were supposed to be closed, a separate node entry would
+// already have been created.
+//
+// TODO: get rid of this. This is now only used in newDisjunctionAcceptor,
+// which, in turn, is rarely used for analyzing disjunction values in the API.
+// This code is not ideal and buggy (see comment below), but it doesn't seem
+// worth improving it and we can probably do without.
func (c *acceptor) InsertSubtree(at adt.ID, n *nodeContext, v *adt.Vertex, cyclic bool) adt.ID {
if len(c.Canopy) == 0 {
c.Canopy = append(c.Canopy, CloseDef{})
@@ -346,6 +381,15 @@
panic(fmt.Sprintf("at >= len(canopy) (%d >= %d)", at, len(c.Canopy)))
}
+ // TODO: like with AddVertex, this really should use the acceptor of the
+ // parent. This seems not to work, though.
+ //
+ // var a *acceptor
+ // if v.Parent != nil && v.Parent.Closed != nil {
+ // a = closedInfo(v.Parent)
+ // } else {
+ // a = &acceptor{}
+ // }
a := closedInfo(v)
a.node(0)
@@ -363,12 +407,13 @@
c.Canopy = append(c.Canopy, a.Canopy...)
// Shift all IDs for the new offset.
- for i, x := range c.Canopy[id:] {
+ for i := int(id); i < len(c.Canopy); i++ {
+ x := c.Canopy[i]
if x.And != -1 {
- c.Canopy[int(id)+i].And += id
+ c.Canopy[i].And += id
}
if x.NextEmbed != 0 {
- c.Canopy[int(id)+i].NextEmbed += id
+ c.Canopy[i].NextEmbed += id
}
}
@@ -383,6 +428,187 @@
return id
}
+func appendConjuncts(v *adt.Vertex, a []adt.Conjunct) {
+ for _, c := range a {
+ v.AddConjunct(c)
+ }
+}
+
+// AddVertex add a Vertex to a new destination node. The caller may
+// call AddVertex multiple times on dst. None of the fields of dst
+// should be set by the caller. AddVertex takes care of setting the
+// Label and Parent.
+func AddVertex(dst, src *adt.Vertex) {
+ if dst.Parent == nil {
+ // Create "fake" parent that holds the combined closed data.
+ // We do not set the parent until here as we don't want to "inherit" the
+ // closedness setting from v.
+ dst.Parent = &adt.Vertex{Parent: src.Parent}
+ dst.Label = src.Label
+ }
+
+ if src.IsData() {
+ dst.AddConjunct(adt.MakeConjunct(nil, src, 0))
+ return
+ }
+
+ var srcC *acceptor
+ if src.Parent != nil && src.Parent.Closed != nil {
+ srcC = closedInfo(src.Parent)
+ } else {
+ srcC = &acceptor{}
+ }
+ dstC := closedInfo(dst.Parent)
+ dstC.ignore = true
+
+ isDef := src.Label.IsDef()
+ addClose := isDef || srcC.isClosed
+
+ if addClose {
+ dstC.node(0)
+ } else if len(dstC.Canopy) == 0 {
+ // we can copy it as is (assuming 0 is )
+ appendConjuncts(dst, src.Conjuncts)
+ dstC.Canopy = append(dstC.Canopy, srcC.Canopy...)
+ return
+ }
+
+ offset := adt.ID(len(dstC.Canopy))
+ top := offset
+
+ switch {
+ case len(srcC.Canopy) == 0 && !addClose:
+ appendConjuncts(dst, src.Conjuncts)
+ return
+
+ case len(srcC.Canopy) == 1:
+ c := srcC.Canopy[0]
+ if !addClose && !c.IsDef && !c.IsClosed {
+ appendConjuncts(dst, src.Conjuncts)
+ return
+ }
+ c.IsDef = addClose
+ dstC.Canopy = append(dstC.Canopy, c)
+
+ case addClose:
+ srcC.node(0)
+ isClosed := false
+ srcC.visitAnd(0, func(id adt.ID, c CloseDef) bool {
+ if c.IsClosed || c.IsDef {
+ isClosed = true
+ return false
+ }
+ return true
+ })
+
+ if !isClosed {
+ // need to embed and close.
+ dstC.Canopy = append(dstC.Canopy,
+ CloseDef{
+ And: offset,
+ IsDef: true,
+ NextEmbed: offset + 1,
+ },
+ CloseDef{
+ And: embedRoot,
+ })
+
+ offset += 2
+ }
+ fallthrough
+
+ default:
+ dstC.Canopy = append(dstC.Canopy, srcC.Canopy...)
+ }
+
+ // Shift all IDs for the new offset.
+ for i := int(offset); i < len(dstC.Canopy); i++ {
+ x := dstC.Canopy[i]
+ if x.And != -1 {
+ dstC.Canopy[i].And += offset
+ }
+ if x.NextEmbed != 0 {
+ dstC.Canopy[i].NextEmbed += offset
+ }
+ }
+
+ topAnd := dstC.Canopy[top].And
+ atAnd := dstC.Canopy[0].And
+ dstC.Canopy[top].And = atAnd
+ dstC.Canopy[0].And = topAnd
+
+ for _, c := range src.Conjuncts {
+ c.CloseID += offset
+ if err := dst.AddConjunct(c); err != nil {
+ panic(err)
+ }
+ }
+}
+
+// TODO: This is roughly the equivalent of AddVertex for use with
+// UnifyAccept. It is based on the old InsertSubTree. We should use
+// this at some point, but ideally we should have a better way to
+// represent closedness in the first place that is more flexible in
+// handling API usage.
+//
+// func EmbedVertex(dst, src *adt.Vertex) {
+// if dst.Parent == nil {
+// // Create "fake" parent that holds the combined closed data.
+// // We do not set the parent until here as we don't want to "inherit" the
+// // closedness setting from v.
+// dst.Parent = &adt.Vertex{Parent: src.Parent}
+// dst.Label = src.Label
+// }
+//
+// if src.IsData() {
+// dst.AddConjunct(adt.MakeConjunct(nil, src, 0))
+// return
+// }
+//
+// var a *acceptor
+// if src.Parent != nil && src.Parent.Closed != nil {
+// a = closedInfo(src.Parent)
+// } else {
+// a = &acceptor{}
+// }
+// a.node(0)
+//
+// c := closedInfo(dst.Parent)
+// c.ignore = true
+// c.node(0)
+//
+// id := adt.ID(len(c.Canopy))
+// y := CloseDef{
+// And: embedRoot,
+// NextEmbed: c.Canopy[0].NextEmbed,
+// }
+// c.Canopy[0].NextEmbed = id
+//
+// c.Canopy = append(c.Canopy, y)
+// id = adt.ID(len(c.Canopy))
+//
+// // First entry is at the embedded node location.
+// c.Canopy = append(c.Canopy, a.Canopy...)
+//
+// // Shift all IDs for the new offset.
+// for i := int(id); i < len(c.Canopy); i++ {
+// x := c.Canopy[i]
+// if x.And != -1 {
+// c.Canopy[i].And += id
+// }
+// if x.NextEmbed != 0 {
+// c.Canopy[i].NextEmbed += id
+// }
+// }
+//
+// for _, c := range src.Conjuncts {
+// c.CloseID += id
+// if err := dst.AddConjunct(c); err != nil {
+// panic(err)
+// }
+// }
+// }
+
func (c *acceptor) verifyArc(ctx *adt.OpContext, f adt.Feature, v *adt.Vertex) (found bool, err *adt.Bottom) {
defer ctx.ReleasePositions(ctx.MarkPositions())
diff --git a/internal/core/eval/eval.go b/internal/core/eval/eval.go
index db3e806..74e236a 100644
--- a/internal/core/eval/eval.go
+++ b/internal/core/eval/eval.go
@@ -312,7 +312,7 @@
}
v.Arcs = nil
// v.Structs = nil // TODO: should we keep or discard the Structs?
- v.Closed = newDisjunctionAcceptor(d)
+ v.Closed = newDisjunctionAcceptor(d) // TODO: remove?
default:
if r := n.result(); r.Value != nil {
@@ -341,7 +341,7 @@
closedInfo, _ = v.Parent.Closed.(*acceptor)
}
- if !v.Label.IsInt() && closedInfo != nil {
+ if !v.Label.IsInt() && closedInfo != nil && !closedInfo.ignore {
ci := closedInfo
// Visit arcs recursively to validate and compute error.
switch ok, err := ci.verifyArc(c, v.Label, v); {
@@ -355,7 +355,7 @@
return shared
case !ok: // hidden field
- // A hidden field is except from checking. Ensure that the
+ // A hidden field is exempt from checking. Ensure that the
// closedness doesn't carry over into children.
// TODO: make this more fine-grained per package, allowing
// checked restrictions to be defined within the package.
@@ -1086,6 +1086,13 @@
id := v.CloseID
switch x := v.Expr().(type) {
+ case *adt.Vertex:
+ if x.IsData() {
+ n.addValueConjunct(env, x, id)
+ } else {
+ n.addVertexConjuncts(env, id, x, x)
+ }
+
case adt.Value:
n.addValueConjunct(env, x, id)
@@ -1178,6 +1185,17 @@
}
}
+ // TODO: also to through normal Vertex handling here. At the moment
+ // addValueConjunct handles StructMarker.NeedsClose, as this is always
+ // only needed when evaluation an Evaluator, and not a Resolver.
+ // The two code paths should ideally be merged once this separate
+ // mechanism is eliminated.
+ //
+ // if arc, ok := val.(*adt.Vertex); ok && !arc.IsData() {
+ // n.addVertexConjuncts(v.Env, closeID, v.Expr(), arc)
+ // break
+ // }
+
// TODO: insert in vertex as well
n.addValueConjunct(v.Env, val, closeID)
@@ -1372,9 +1390,11 @@
cyclic := env != nil && env.Cyclic
- if !x.IsData() && len(x.Conjuncts) > 0 {
+ if !x.IsData() {
+ // TODO: this really shouldn't happen anymore.
if isComplexStruct(x) {
- closedInfo(n.node).InsertSubtree(id, n, x, cyclic)
+ // This really shouldn't happen, but just in case.
+ n.addVertexConjuncts(env, id, x, x)
return
}
diff --git a/internal/core/eval/vertex_test.go b/internal/core/eval/vertex_test.go
index 04dcb13..c86cf51 100644
--- a/internal/core/eval/vertex_test.go
+++ b/internal/core/eval/vertex_test.go
@@ -113,8 +113,8 @@
t.Run("", func(t *testing.T) {
n := &adt.Vertex{}
- n.AddConjunct(adt.MakeRootConjunct(nil, tc.a))
- n.AddConjunct(adt.MakeRootConjunct(nil, tc.b))
+ eval.AddVertex(n, tc.a)
+ eval.AddVertex(n, tc.b)
n.Finalize(ctx)
got := debug.NodeString(r, n, &debug.Config{Compact: !tc.verbose})
diff --git a/pkg/list/testdata/gen.txtar b/pkg/list/testdata/gen.txtar
index 01cbcb5..fc6635e 100644
--- a/pkg/list/testdata/gen.txtar
+++ b/pkg/list/testdata/gen.txtar
@@ -76,12 +76,12 @@
error in call to list.Slice: slice bounds out of range
error in call to list.Take: negative index
0: error in call to list.SortStrings: element 0 of list argument 0: cannot use value 1 (type int) as string
-x: error in call to list.Sort: conflicting values number and {b:2} (mismatched types number and struct)
-x: error in call to list.Sort: conflicting values string and {b:2} (mismatched types string and struct)
-x: error in call to list.Sort: empty disjunction: 2 related errors:
-y: error in call to list.Sort: conflicting values number and {a:1} (mismatched types number and struct)
-y: error in call to list.Sort: conflicting values string and {a:1} (mismatched types string and struct)
-y: error in call to list.Sort: empty disjunction: 2 related errors:
+Ascending.x: error in call to list.Sort: conflicting values number and {b:2} (mismatched types number and struct)
+Ascending.x: error in call to list.Sort: conflicting values string and {b:2} (mismatched types string and struct)
+Ascending.x: error in call to list.Sort: empty disjunction: 2 related errors:
+Ascending.y: error in call to list.Sort: conflicting values number and {a:1} (mismatched types number and struct)
+Ascending.y: error in call to list.Sort: conflicting values string and {a:1} (mismatched types string and struct)
+Ascending.y: error in call to list.Sort: empty disjunction: 2 related errors:
t3: cannot use "foo" (type string) as list in argument 1 to list.Avg:
./in.cue:5:14
t14: cannot use "foo" (type string) as int in argument 2 to list.FlattenN:
@@ -270,12 +270,12 @@
}
}
t40: (_|_){
- // [eval] x: error in call to list.Sort: conflicting values number and {b:2} (mismatched types number and struct)
- // x: error in call to list.Sort: conflicting values string and {b:2} (mismatched types string and struct)
- // x: error in call to list.Sort: empty disjunction: 2 related errors:
- // y: error in call to list.Sort: conflicting values number and {a:1} (mismatched types number and struct)
- // y: error in call to list.Sort: conflicting values string and {a:1} (mismatched types string and struct)
- // y: error in call to list.Sort: empty disjunction: 2 related errors:
+ // [eval] Ascending.x: error in call to list.Sort: conflicting values number and {b:2} (mismatched types number and struct)
+ // Ascending.x: error in call to list.Sort: conflicting values string and {b:2} (mismatched types string and struct)
+ // Ascending.x: error in call to list.Sort: empty disjunction: 2 related errors:
+ // Ascending.y: error in call to list.Sort: conflicting values number and {a:1} (mismatched types number and struct)
+ // Ascending.y: error in call to list.Sort: conflicting values string and {a:1} (mismatched types string and struct)
+ // Ascending.y: error in call to list.Sort: empty disjunction: 2 related errors:
}
t41: (#list){
0: (string){ "a" }
@@ -310,11 +310,11 @@
t52: (bool){ true }
t53: (bool){ false }
t54: (_|_){
- // [eval] x: error in call to list.Sort: conflicting values number and {b:2} (mismatched types number and struct)
- // x: error in call to list.Sort: conflicting values string and {b:2} (mismatched types string and struct)
- // x: error in call to list.Sort: empty disjunction: 2 related errors:
- // y: error in call to list.Sort: conflicting values number and {a:1} (mismatched types number and struct)
- // y: error in call to list.Sort: conflicting values string and {a:1} (mismatched types string and struct)
- // y: error in call to list.Sort: empty disjunction: 2 related errors:
+ // [eval] Ascending.x: error in call to list.Sort: conflicting values number and {b:2} (mismatched types number and struct)
+ // Ascending.x: error in call to list.Sort: conflicting values string and {b:2} (mismatched types string and struct)
+ // Ascending.x: error in call to list.Sort: empty disjunction: 2 related errors:
+ // Ascending.y: error in call to list.Sort: conflicting values number and {a:1} (mismatched types number and struct)
+ // Ascending.y: error in call to list.Sort: conflicting values string and {a:1} (mismatched types string and struct)
+ // Ascending.y: error in call to list.Sort: empty disjunction: 2 related errors:
}
}
diff --git a/pkg/list/testdata/issues.txtar b/pkg/list/testdata/issues.txtar
new file mode 100644
index 0000000..5108373
--- /dev/null
+++ b/pkg/list/testdata/issues.txtar
@@ -0,0 +1,102 @@
+-- in.cue --
+import "list"
+
+issue563: {
+ #MyDef: {
+ name: string
+ ...
+ }
+
+ _all: [
+ _a,
+ _b,
+ ]
+
+ _a: [...#MyDef] & [
+ { name: "a" },
+ { name: "b" },
+ { name: "c" },
+ ]
+
+ _b: [...#MyDef] & [
+ { name: "1" },
+ { name: "2" },
+ { name: "3" },
+ ]
+
+ output: [...#MyDef] & list.FlattenN(_all, 1)
+}
+-- out/list --
+(struct){
+ issue563: (struct){
+ #MyDef: (#struct){
+ name: (string){ string }
+ }
+ _all: (#list){
+ 0: (#list){
+ 0: (#struct){
+ name: (string){ "a" }
+ }
+ 1: (#struct){
+ name: (string){ "b" }
+ }
+ 2: (#struct){
+ name: (string){ "c" }
+ }
+ }
+ 1: (#list){
+ 0: (#struct){
+ name: (string){ "1" }
+ }
+ 1: (#struct){
+ name: (string){ "2" }
+ }
+ 2: (#struct){
+ name: (string){ "3" }
+ }
+ }
+ }
+ _a: (#list){
+ 0: (#struct){
+ name: (string){ "a" }
+ }
+ 1: (#struct){
+ name: (string){ "b" }
+ }
+ 2: (#struct){
+ name: (string){ "c" }
+ }
+ }
+ _b: (#list){
+ 0: (#struct){
+ name: (string){ "1" }
+ }
+ 1: (#struct){
+ name: (string){ "2" }
+ }
+ 2: (#struct){
+ name: (string){ "3" }
+ }
+ }
+ output: (#list){
+ 0: (#struct){
+ name: (string){ "a" }
+ }
+ 1: (#struct){
+ name: (string){ "b" }
+ }
+ 2: (#struct){
+ name: (string){ "c" }
+ }
+ 3: (#struct){
+ name: (string){ "1" }
+ }
+ 4: (#struct){
+ name: (string){ "2" }
+ }
+ 5: (#struct){
+ name: (string){ "3" }
+ }
+ }
+ }
+}
