internal/core/eval: fixes to closedness algorithm
- Drop closeIDs that are no longer used.
Change-Id: I7f27b327c4470d016acb97efc055982fc144b454
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/6704
Reviewed-by: CUE cueckoo <cueckoo@gmail.com>
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/testdata/fulleval/035_optionals_with_label_filters.txtar b/cue/testdata/fulleval/035_optionals_with_label_filters.txtar
index 9204d37..e9c1cf8 100644
--- a/cue/testdata/fulleval/035_optionals_with_label_filters.txtar
+++ b/cue/testdata/fulleval/035_optionals_with_label_filters.txtar
@@ -113,10 +113,6 @@
./in.cue:9:2
./in.cue:22:8
./in.cue:23:8
-jobs3.fooTest1: field `cmd` not allowed:
- ./in.cue:2:7
- ./in.cue:6:8
- ./in.cue:23:18
jobs2.fooTest.name: invalid value "badName" (out of bound =~"^test"):
./in.cue:9:22
@@ -162,11 +158,7 @@
// ./in.cue:9:2
// ./in.cue:22:8
// ./in.cue:23:8
- fooTest1: (_|_){
- // [eval] jobs3.fooTest1: field `cmd` not allowed:
- // ./in.cue:2:7
- // ./in.cue:6:8
- // ./in.cue:23:18
+ fooTest1: (#struct){
name: (string){ "badName" }
cmd: (string){ string }
}
diff --git a/cue/testdata/resolve/035_excluded_embedding_from_closing.txtar b/cue/testdata/resolve/035_excluded_embedding_from_closing.txtar
index e719e07..ebd92c4 100644
--- a/cue/testdata/resolve/035_excluded_embedding_from_closing.txtar
+++ b/cue/testdata/resolve/035_excluded_embedding_from_closing.txtar
@@ -65,7 +65,6 @@
-- out/eval --
Errors:
V.b: field `extra` not allowed:
- ./in.cue:1:5
./in.cue:6:10
./in.cue:11:5
V.c: field `e` not allowed:
@@ -102,7 +101,6 @@
}
b: (_|_){
// [eval] V.b: field `extra` not allowed:
- // ./in.cue:1:5
// ./in.cue:6:10
// ./in.cue:11:5
open: (int){ int }
diff --git a/internal/ci/workflows.cue b/internal/ci/workflows.cue
index 6d2d564..1a5c1a5 100644
--- a/internal/ci/workflows.cue
+++ b/internal/ci/workflows.cue
@@ -7,7 +7,7 @@
workflowsDir: *"./" | string @tag(workflowsDir)
-workflows: [...{file: string, schema: json.#Workflow}]
+workflows: [...{file: string, schema: (json.#Workflow&{})}]
workflows: [
{
file: "test.yml"
@@ -29,7 +29,7 @@
// TODO: drop when cuelang.org/issue/390 is fixed.
// Declare definitions for sub-schemas
-#job: (json.#Workflow.jobs & {x: _}).x
+#job: ((json.#Workflow & {}).jobs & {x: _}).x
#step: ((#job & {steps: _}).steps & [_])[0]
#latestGo: "1.14.3"
diff --git a/internal/core/eval/closed.go b/internal/core/eval/closed.go
index 5c9ae62..56a0d7f 100644
--- a/internal/core/eval/closed.go
+++ b/internal/core/eval/closed.go
@@ -162,11 +162,19 @@
// 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 {
- and = append(and, c)
+ if c != nil {
+ and = append(and, c)
+ }
}
switch len(and) {
case 0:
@@ -190,11 +198,17 @@
// 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 {
- if sub := replace[c.ID]; sub != nil {
+ 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
+ }
}
}
@@ -213,11 +227,14 @@
return c
}
- if k == 1 {
+ 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]}
}
-
- 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
@@ -387,3 +404,17 @@
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
+}
diff --git a/internal/core/eval/closed_test.go b/internal/core/eval/closed_test.go
index 144ecce..c0ed278 100644
--- a/internal/core/eval/closed_test.go
+++ b/internal/core/eval/closed_test.go
@@ -27,6 +27,28 @@
replace map[uint32]*CloseDef
want *CloseDef
}{{
+ desc: "introduce new",
+ close: nil,
+ replace: map[uint32]*CloseDef{
+ 0: {ID: 2, IsAnd: false, List: nil},
+ },
+ want: &CloseDef{
+ ID: 0x02,
+ },
+ }, {
+ desc: "auto insert missing 0",
+ close: &CloseDef{
+ ID: 1,
+ },
+ replace: map[uint32]*CloseDef{
+ 0: {ID: 2, IsAnd: false, List: nil},
+ 1: nil, // keep 1
+ },
+ want: &CloseDef{
+ IsAnd: true,
+ List: []*CloseDef{{ID: 1}, {ID: 2}},
+ },
+ }, {
desc: "a: #A & #B",
close: &CloseDef{
ID: 1,
@@ -40,18 +62,38 @@
List: []*CloseDef{{ID: 2}, {ID: 3}},
},
}, {
+ desc: "eliminateUnusedToEmpty",
+ close: &CloseDef{
+ ID: 1,
+ },
+ replace: map[uint32]*CloseDef{
+ 0: nil,
+ },
+ want: nil,
+ }, {
// Eliminate an embedding for which there are no more entries.
- // desc: "eliminateOneEmbedding",
- // close: &CloseDef{
- // ID: 0,
- // List: []*CloseDef{
- // {ID: 2},
- // {ID: 3},
- // },
- // },
- // replace: map[uint32]*CloseDef{2: nil},
- // want: &CloseDef{ID: 2},
- // }, {
+ desc: "eliminateOneEmbedding",
+ close: &CloseDef{
+ ID: 0,
+ List: []*CloseDef{
+ {ID: 2},
+ {ID: 3},
+ },
+ },
+ replace: map[uint32]*CloseDef{2: nil},
+ want: &CloseDef{ID: 2},
+ }, {
+ desc: "eliminateAllEmbeddings",
+ close: &CloseDef{
+ ID: 2,
+ List: []*CloseDef{
+ {ID: 2},
+ {ID: 3},
+ },
+ },
+ replace: map[uint32]*CloseDef{0: {ID: 4}, 4: nil},
+ want: &CloseDef{ID: 4},
+ }, {
// Do not eliminate an embedding that has a replacement.
desc: "eliminateOneEmbeddingByMultiple",
close: &CloseDef{
diff --git a/internal/core/eval/eval.go b/internal/core/eval/eval.go
index 896c983..8b58c7e 100644
--- a/internal/core/eval/eval.go
+++ b/internal/core/eval/eval.go
@@ -570,7 +570,28 @@
n.needClose = n.needClose || a.isClosed
}
- updated := updateClosed(c, n.replace)
+ replace := n.replace
+ if replace == nil {
+ replace = map[uint32]*CloseDef{}
+ }
+
+ // Mark any used CloseID to keep, if not already replaced.
+ for _, x := range n.optionals {
+ if _, ok := replace[x.env.CloseID]; !ok {
+ replace[x.env.CloseID] = nil
+ }
+ }
+ for _, a := range n.node.Arcs {
+ for _, c := range a.Conjuncts {
+ if c.Env != nil {
+ if _, ok := replace[c.Env.CloseID]; !ok {
+ replace[c.Env.CloseID] = nil
+ }
+ }
+ }
+ }
+
+ updated := updateClosed(c, replace)
if updated == nil && n.needClose {
updated = &CloseDef{Src: n.node}
}
@@ -1044,7 +1065,7 @@
// values on which they depend fail.
ctx.Unify(ctx, arc, adt.Finalized)
- if arc.Label.IsDef() {
+ if arc.Label.IsDef() { // should test whether closed, not isDef?
id := n.eval.nextID()
n.insertClosed(arc, id, cyclic, arc)
} else {
