internal/core/adt: fix performance issue with disjunctions
Fixes a performance TODO, which was a deliberate regression
to deal with a semantic bug.
Fixes #651
Change-Id: I9d95dc9d250064e79552425331912f58175cc094
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/8282
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/testdata/benchmarks/dedupelem.txtar b/cue/testdata/benchmarks/dedupelem.txtar
index b83f06c..ca1ed5b 100644
--- a/cue/testdata/benchmarks/dedupelem.txtar
+++ b/cue/testdata/benchmarks/dedupelem.txtar
@@ -19,7 +19,7 @@
foo.0.type: conflicting values "int" and "float":
./in.cue:3:16
./in.cue:5:14
- ./in.cue:6:30
+ ./in.cue:5:30
foo.0.type: conflicting values "string" and "float":
./in.cue:5:14
./in.cue:10:14
@@ -41,7 +41,7 @@
// foo.0.type: conflicting values "int" and "float":
// ./in.cue:3:16
// ./in.cue:5:14
- // ./in.cue:6:30
+ // ./in.cue:5:30
// foo.0.type: conflicting values "string" and "float":
// ./in.cue:5:14
// ./in.cue:10:14
diff --git a/cue/testdata/benchmarks/mergeddisjunction.txtar b/cue/testdata/benchmarks/mergeddisjunction.txtar
new file mode 100644
index 0000000..56ae636
--- /dev/null
+++ b/cue/testdata/benchmarks/mergeddisjunction.txtar
@@ -0,0 +1,223 @@
+// Here one comprehension creates a number of distinct values, each of which
+// with a disjunction, then another comprehension maps them back to the
+// same value, creating a large number of disjunctions.
+//
+// The disjunctions cannot be identified as equal in the general case. If no
+// care is taken, disjunction elimination will be exponential, causing over
+// a billion disjuncts to process in the below example. With the proper
+// optimizations, there is a small, constant number of disjunction ops per
+// disjunct.
+//
+// Issue #651
+-- in.cue --
+list: [
+ 0, 1, 2, 3, 4, 5, 6, 7, 8,
+ 9, 10, 11, 12, 13, 14, 15, 16,
+ 17, 18, 19, 20, 21, 22, 23, 24,
+ 25, 26, 27, 28, 29, 30,
+]
+a: [X=string]: text: *"default" | string
+
+a: {
+ for i in list {
+ "\(i)": text: string
+ }
+}
+
+b: {
+ for x in a {
+ "\(x.text)": { text: x.text }
+ }
+}
+-- out/eval --
+(struct){
+ list: (#list){
+ 0: (int){ 0 }
+ 1: (int){ 1 }
+ 2: (int){ 2 }
+ 3: (int){ 3 }
+ 4: (int){ 4 }
+ 5: (int){ 5 }
+ 6: (int){ 6 }
+ 7: (int){ 7 }
+ 8: (int){ 8 }
+ 9: (int){ 9 }
+ 10: (int){ 10 }
+ 11: (int){ 11 }
+ 12: (int){ 12 }
+ 13: (int){ 13 }
+ 14: (int){ 14 }
+ 15: (int){ 15 }
+ 16: (int){ 16 }
+ 17: (int){ 17 }
+ 18: (int){ 18 }
+ 19: (int){ 19 }
+ 20: (int){ 20 }
+ 21: (int){ 21 }
+ 22: (int){ 22 }
+ 23: (int){ 23 }
+ 24: (int){ 24 }
+ 25: (int){ 25 }
+ 26: (int){ 26 }
+ 27: (int){ 27 }
+ 28: (int){ 28 }
+ 29: (int){ 29 }
+ 30: (int){ 30 }
+ }
+ a: (struct){
+ "0": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "1": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "2": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "3": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "4": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "5": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "6": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "7": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "8": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "9": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "10": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "11": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "12": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "13": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "14": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "15": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "16": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "17": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "18": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "19": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "20": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "21": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "22": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "23": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "24": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "25": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "26": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "27": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "28": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "29": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ "30": (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ }
+ b: (struct){
+ default: (struct){
+ text: (string){ |(*(string){ "default" }, (string){ string }) }
+ }
+ }
+}
+-- out/compile --
+--- in.cue
+{
+ list: [
+ 0,
+ 1,
+ 2,
+ 3,
+ 4,
+ 5,
+ 6,
+ 7,
+ 8,
+ 9,
+ 10,
+ 11,
+ 12,
+ 13,
+ 14,
+ 15,
+ 16,
+ 17,
+ 18,
+ 19,
+ 20,
+ 21,
+ 22,
+ 23,
+ 24,
+ 25,
+ 26,
+ 27,
+ 28,
+ 29,
+ 30,
+ ]
+ a: {
+ [string]: {
+ text: (*"default"|string)
+ }
+ }
+ a: {
+ for _, i in 〈1;list〉 {
+ "\(〈1;i〉)": {
+ text: string
+ }
+ }
+ }
+ b: {
+ for _, x in 〈1;a〉 {
+ "\(〈1;x〉.text)": {
+ text: 〈2;x〉.text
+ }
+ }
+ }
+}
diff --git a/cue/testdata/disjunctions/elimination.txtar b/cue/testdata/disjunctions/elimination.txtar
new file mode 100644
index 0000000..b33f099
--- /dev/null
+++ b/cue/testdata/disjunctions/elimination.txtar
@@ -0,0 +1,788 @@
+// Ensure that disjunction elimination is not done prematurely.
+
+// Issue #651
+
+-- in.cue --
+import "struct"
+
+// Closedness checks should not be triggered too early, or with an improper
+// subset of StructInfos. Blindly finalizing partial disjuncts will end up
+// doing a closedness check with not all embeddings present, which can lead to
+// a field being rejected prematurely.
+//
+// It should be recursively disabled.
+disambiguateClosed: {
+ b: #Def & a
+ a: #Def
+ #Def: { {x: true} | {y: true} }
+}
+
+// Checks should never be disabled for field matching.
+alwaysCheckMatchers1: {
+ b: {[=~"^xxxx$"]: int} | null
+ b: {c: string} | null
+ b: c: "yyyyy"
+}
+
+alwaysCheckPatterns2: {
+ a: #X
+ a: b
+
+ b: #X
+ b: c: "yyyyy"
+
+ #X: string | {
+ c: string
+ {[=~"^xxxx$"]: int}
+ }
+}
+
+nestedNonMonotonic: resolved: n1: {
+ x: { a: struct.MinFields(2) } | null
+ x: { a: c: 1 } | null
+ x: { a: d: 1 } | null
+}
+
+nestedNonMonotonic: resolved: n2: {
+ x: { a: b: struct.MinFields(2) } | null
+ x: { a: b: c: 1 } | null
+ x: { a: b: d: 1 } | null
+}
+
+nestedNonMonotonic: eliminated: n1: p1: {
+ x: { a: struct.MaxFields(1) } | null
+ x: { a: c: 1 } | null
+ x: { a: d: 1 } | null
+}
+
+nestedNonMonotonic: eliminated: n1: p2: {
+ x: { a: c: 1 } | null
+ x: { a: struct.MaxFields(1) } | null
+ x: { a: d: 1 } | null
+}
+
+nestedNonMonotonic: eliminated: n1: p2: {
+ x: { a: c: 1 } | null
+ x: { a: d: 1 } | null
+ x: { a: struct.MaxFields(1) } | null
+}
+
+nestedNonMonotonic: eliminated: n2: p1: {
+ x: { a: b: struct.MaxFields(1) } | null
+ x: { a: b: c: 1 } | null
+ x: { a: b: d: 1 } | null
+}
+
+nestedNonMonotonic: eliminated: n2: p2: {
+ x: { a: b: c: 1 } | null
+ x: { a: b: struct.MaxFields(1) } | null
+ x: { a: b: d: 1 } | null
+}
+
+nestedNonMonotonic: eliminated: n2: p2: {
+ x: { a: b: c: 1 } | null
+ x: { a: b: d: 1 } | null
+ x: { a: b: struct.MaxFields(1) } | null
+}
+
+nestedNonMonotonic: incomplete: a: n1: p1: {
+ x: { a: struct.MinFields(2) } | null
+ x: { a: c: 1 } | null
+}
+
+nestedNonMonotonic: incomplete: a: n1: p2: {
+ x: { a: c: 1 } | null
+ x: { a: struct.MinFields(2) } | null
+}
+
+nestedNonMonotonic: incomplete: a: n2: p1: {
+ x: { a: b: struct.MinFields(2) } | null
+ x: { a: b: c: 1 } | null
+}
+
+nestedNonMonotonic: incomplete: a: n2: p2: {
+ x: { a: b: c: 1 } | null
+ x: { a: b: struct.MinFields(2) } | null
+}
+
+
+nestedNonMonotonic: incomplete: b: n1: p1: {
+ x: { a: struct.MinFields(3) } | null
+ x: { a: c: 1 } | null
+ x: { a: d: 1 } | null
+}
+
+nestedNonMonotonic: incomplete: b: n1: p2: {
+ x: { a: c: 1 } | null
+ x: { a: struct.MinFields(3) } | null
+ x: { a: d: 1 } | null
+}
+
+nestedNonMonotonic: incomplete: b: n1: p3: {
+ x: { a: c: 1 } | null
+ x: { a: d: 1 } | null
+ x: { a: struct.MinFields(3) } | null
+}
+
+nestedNonMonotonic: incomplete: b: n2: p1: {
+ x: { a: b: struct.MinFields(3) } | null
+ x: { a: b: c: 1 } | null
+ x: { a: b: d: 1 } | null
+}
+
+nestedNonMonotonic: incomplete: b: n2: p1: {
+ x: { a: b: c: 1 } | null
+ x: { a: b: struct.MinFields(3) } | null
+ x: { a: b: d: 1 } | null
+}
+
+nestedNonMonotonic: incomplete: b: n2: p1: {
+ x: { a: b: c: 1 } | null
+ x: { a: b: d: 1 } | null
+ x: { a: b: struct.MinFields(3) } | null
+}
+
+-- out/eval --
+(struct){
+ disambiguateClosed: (struct){
+ b: (struct){ |((#struct){
+ x: (bool){ true }
+ }, (#struct){
+ y: (bool){ true }
+ }) }
+ a: (struct){ |((#struct){
+ x: (bool){ true }
+ }, (#struct){
+ y: (bool){ true }
+ }) }
+ #Def: (struct){ |((#struct){
+ x: (bool){ true }
+ }, (#struct){
+ y: (bool){ true }
+ }) }
+ }
+ alwaysCheckMatchers1: (struct){
+ b: (struct){
+ c: (string){ "yyyyy" }
+ }
+ }
+ alwaysCheckPatterns2: (struct){
+ a: (#struct){
+ c: (string){ "yyyyy" }
+ }
+ b: (#struct){
+ c: (string){ "yyyyy" }
+ }
+ #X: ((string|struct)){ |((string){ string }, (#struct){
+ c: (string){ string }
+ }) }
+ }
+ nestedNonMonotonic: (struct){
+ resolved: (struct){
+ n1: (struct){
+ x: ((null|struct)){ |((struct){
+ a: (struct){
+ c: (int){ 1 }
+ d: (int){ 1 }
+ }
+ }, (null){ null }) }
+ }
+ n2: (struct){
+ x: ((null|struct)){ |((struct){
+ a: (struct){
+ b: (struct){
+ c: (int){ 1 }
+ d: (int){ 1 }
+ }
+ }
+ }, (null){ null }) }
+ }
+ }
+ eliminated: (struct){
+ n1: (struct){
+ p1: (struct){
+ x: (null){ null }
+ }
+ p2: (struct){
+ x: (null){ null }
+ }
+ }
+ n2: (struct){
+ p1: (struct){
+ x: (null){ null }
+ }
+ p2: (struct){
+ x: (null){ null }
+ }
+ }
+ }
+ incomplete: (struct){
+ a: (struct){
+ n1: (struct){
+ p1: (struct){
+ x: ((null|struct)){ |((struct){
+ a: (_|_){
+ // [incomplete] nestedNonMonotonic.incomplete.a.n1.p1.x.a: invalid value {c:1} (does not satisfy struct.MinFields(2)): len(fields) < MinFields(2) (1 < 2):
+ // ./in.cue:84:13
+ // ./in.cue:84:30
+ c: (int){ 1 }
+ }
+ }, (null){ null }) }
+ }
+ p2: (struct){
+ x: ((null|struct)){ |((struct){
+ a: (_|_){
+ // [incomplete] nestedNonMonotonic.incomplete.a.n1.p2.x.a: invalid value {c:1} (does not satisfy struct.MinFields(2)): len(fields) < MinFields(2) (1 < 2):
+ // ./in.cue:90:13
+ // ./in.cue:90:30
+ c: (int){ 1 }
+ }
+ }, (null){ null }) }
+ }
+ }
+ n2: (struct){
+ p1: (struct){
+ x: ((null|struct)){ |((struct){
+ a: (struct){
+ b: (_|_){
+ // [incomplete] nestedNonMonotonic.incomplete.a.n2.p1.x.a.b: invalid value {c:1} (does not satisfy struct.MinFields(2)): len(fields) < MinFields(2) (1 < 2):
+ // ./in.cue:94:16
+ // ./in.cue:94:33
+ c: (int){ 1 }
+ }
+ }
+ }, (null){ null }) }
+ }
+ p2: (struct){
+ x: ((null|struct)){ |((struct){
+ a: (struct){
+ b: (_|_){
+ // [incomplete] nestedNonMonotonic.incomplete.a.n2.p2.x.a.b: invalid value {c:1} (does not satisfy struct.MinFields(2)): len(fields) < MinFields(2) (1 < 2):
+ // ./in.cue:100:16
+ // ./in.cue:100:33
+ c: (int){ 1 }
+ }
+ }
+ }, (null){ null }) }
+ }
+ }
+ }
+ b: (struct){
+ n1: (struct){
+ p1: (struct){
+ x: ((null|struct)){ |((struct){
+ a: (_|_){
+ // [incomplete] nestedNonMonotonic.incomplete.b.n1.p1.x.a: invalid value {c:1,d:1} (does not satisfy struct.MinFields(3)): len(fields) < MinFields(3) (2 < 3):
+ // ./in.cue:105:13
+ // ./in.cue:105:30
+ c: (int){ 1 }
+ d: (int){ 1 }
+ }
+ }, (null){ null }) }
+ }
+ p2: (struct){
+ x: ((null|struct)){ |((struct){
+ a: (_|_){
+ // [incomplete] nestedNonMonotonic.incomplete.b.n1.p2.x.a: invalid value {c:1,d:1} (does not satisfy struct.MinFields(3)): len(fields) < MinFields(3) (2 < 3):
+ // ./in.cue:112:13
+ // ./in.cue:112:30
+ c: (int){ 1 }
+ d: (int){ 1 }
+ }
+ }, (null){ null }) }
+ }
+ p3: (struct){
+ x: ((null|struct)){ |((struct){
+ a: (_|_){
+ // [incomplete] nestedNonMonotonic.incomplete.b.n1.p3.x.a: invalid value {c:1,d:1} (does not satisfy struct.MinFields(3)): len(fields) < MinFields(3) (2 < 3):
+ // ./in.cue:119:13
+ // ./in.cue:119:30
+ c: (int){ 1 }
+ d: (int){ 1 }
+ }
+ }, (null){ null }) }
+ }
+ }
+ n2: (struct){
+ p1: (struct){
+ x: ((null|struct)){ |((struct){
+ a: (struct){
+ b: (_|_){
+ // [incomplete] nestedNonMonotonic.incomplete.b.n2.p1.x.a.b: invalid value {c:1,d:1} (does not satisfy struct.MinFields(3)): len(fields) < MinFields(3) (2 < 3):
+ // ./in.cue:137:16
+ // ./in.cue:137:33
+ c: (int){ 1 }
+ d: (int){ 1 }
+ }
+ }
+ }, (null){ null }) }
+ }
+ }
+ }
+ }
+ }
+}
+-- out/compile --
+--- in.cue
+{
+ disambiguateClosed: {
+ b: (〈0;#Def〉 & 〈0;a〉)
+ a: 〈0;#Def〉
+ #Def: {
+ ({
+ x: true
+ }|{
+ y: true
+ })
+ }
+ }
+ alwaysCheckMatchers1: {
+ b: ({
+ [=~"^xxxx$"]: int
+ }|null)
+ b: ({
+ c: string
+ }|null)
+ b: {
+ c: "yyyyy"
+ }
+ }
+ alwaysCheckPatterns2: {
+ a: 〈0;#X〉
+ a: 〈0;b〉
+ b: 〈0;#X〉
+ b: {
+ c: "yyyyy"
+ }
+ #X: (string|{
+ c: string
+ {
+ [=~"^xxxx$"]: int
+ }
+ })
+ }
+ nestedNonMonotonic: {
+ resolved: {
+ n1: {
+ x: ({
+ a: 〈import;struct〉.MinFields(2)
+ }|null)
+ x: ({
+ a: {
+ c: 1
+ }
+ }|null)
+ x: ({
+ a: {
+ d: 1
+ }
+ }|null)
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ resolved: {
+ n2: {
+ x: ({
+ a: {
+ b: 〈import;struct〉.MinFields(2)
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ c: 1
+ }
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ d: 1
+ }
+ }
+ }|null)
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ eliminated: {
+ n1: {
+ p1: {
+ x: ({
+ a: 〈import;struct〉.MaxFields(1)
+ }|null)
+ x: ({
+ a: {
+ c: 1
+ }
+ }|null)
+ x: ({
+ a: {
+ d: 1
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ eliminated: {
+ n1: {
+ p2: {
+ x: ({
+ a: {
+ c: 1
+ }
+ }|null)
+ x: ({
+ a: 〈import;struct〉.MaxFields(1)
+ }|null)
+ x: ({
+ a: {
+ d: 1
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ eliminated: {
+ n1: {
+ p2: {
+ x: ({
+ a: {
+ c: 1
+ }
+ }|null)
+ x: ({
+ a: {
+ d: 1
+ }
+ }|null)
+ x: ({
+ a: 〈import;struct〉.MaxFields(1)
+ }|null)
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ eliminated: {
+ n2: {
+ p1: {
+ x: ({
+ a: {
+ b: 〈import;struct〉.MaxFields(1)
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ c: 1
+ }
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ d: 1
+ }
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ eliminated: {
+ n2: {
+ p2: {
+ x: ({
+ a: {
+ b: {
+ c: 1
+ }
+ }
+ }|null)
+ x: ({
+ a: {
+ b: 〈import;struct〉.MaxFields(1)
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ d: 1
+ }
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ eliminated: {
+ n2: {
+ p2: {
+ x: ({
+ a: {
+ b: {
+ c: 1
+ }
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ d: 1
+ }
+ }
+ }|null)
+ x: ({
+ a: {
+ b: 〈import;struct〉.MaxFields(1)
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ incomplete: {
+ a: {
+ n1: {
+ p1: {
+ x: ({
+ a: 〈import;struct〉.MinFields(2)
+ }|null)
+ x: ({
+ a: {
+ c: 1
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ incomplete: {
+ a: {
+ n1: {
+ p2: {
+ x: ({
+ a: {
+ c: 1
+ }
+ }|null)
+ x: ({
+ a: 〈import;struct〉.MinFields(2)
+ }|null)
+ }
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ incomplete: {
+ a: {
+ n2: {
+ p1: {
+ x: ({
+ a: {
+ b: 〈import;struct〉.MinFields(2)
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ c: 1
+ }
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ incomplete: {
+ a: {
+ n2: {
+ p2: {
+ x: ({
+ a: {
+ b: {
+ c: 1
+ }
+ }
+ }|null)
+ x: ({
+ a: {
+ b: 〈import;struct〉.MinFields(2)
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ incomplete: {
+ b: {
+ n1: {
+ p1: {
+ x: ({
+ a: 〈import;struct〉.MinFields(3)
+ }|null)
+ x: ({
+ a: {
+ c: 1
+ }
+ }|null)
+ x: ({
+ a: {
+ d: 1
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ incomplete: {
+ b: {
+ n1: {
+ p2: {
+ x: ({
+ a: {
+ c: 1
+ }
+ }|null)
+ x: ({
+ a: 〈import;struct〉.MinFields(3)
+ }|null)
+ x: ({
+ a: {
+ d: 1
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ incomplete: {
+ b: {
+ n1: {
+ p3: {
+ x: ({
+ a: {
+ c: 1
+ }
+ }|null)
+ x: ({
+ a: {
+ d: 1
+ }
+ }|null)
+ x: ({
+ a: 〈import;struct〉.MinFields(3)
+ }|null)
+ }
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ incomplete: {
+ b: {
+ n2: {
+ p1: {
+ x: ({
+ a: {
+ b: 〈import;struct〉.MinFields(3)
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ c: 1
+ }
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ d: 1
+ }
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ incomplete: {
+ b: {
+ n2: {
+ p1: {
+ x: ({
+ a: {
+ b: {
+ c: 1
+ }
+ }
+ }|null)
+ x: ({
+ a: {
+ b: 〈import;struct〉.MinFields(3)
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ d: 1
+ }
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ }
+ nestedNonMonotonic: {
+ incomplete: {
+ b: {
+ n2: {
+ p1: {
+ x: ({
+ a: {
+ b: {
+ c: 1
+ }
+ }
+ }|null)
+ x: ({
+ a: {
+ b: {
+ d: 1
+ }
+ }
+ }|null)
+ x: ({
+ a: {
+ b: 〈import;struct〉.MinFields(3)
+ }
+ }|null)
+ }
+ }
+ }
+ }
+ }
+}
diff --git a/internal/core/adt/context.go b/internal/core/adt/context.go
index e1c4f9b..4a9ce1d 100644
--- a/internal/core/adt/context.go
+++ b/internal/core/adt/context.go
@@ -177,6 +177,26 @@
generation int
closed map[*closeInfo]*closeStats
todo *closeStats
+
+ // inDisjunct indicates that non-monotonic checks should be skipped.
+ // This is used if we want to do some extra work to eliminate disjunctions
+ // early. The result of unificantion should be thrown away if this check is
+ // used.
+ //
+ // TODO: replace this with a mechanism to determine the correct set (per
+ // conjunct) of StructInfos to include in closedness checking.
+ inDisjunct int
+
+ // inConstaint overrides inDisjunct as field matching should always be
+ // enabled.
+ inConstraint int
+}
+
+func (n *nodeContext) skipNonMonotonicChecks() bool {
+ if n.ctx.inConstraint > 0 {
+ return false
+ }
+ return n.ctx.inDisjunct > 0
}
// Impl is for internal use only. This will go.
diff --git a/internal/core/adt/disjunct.go b/internal/core/adt/disjunct.go
index d7b8f2f..7f3475f 100644
--- a/internal/core/adt/disjunct.go
+++ b/internal/core/adt/disjunct.go
@@ -141,7 +141,8 @@
m := *n
n.postDisjunct(state)
- if n.hasErr() {
+ switch {
+ case n.hasErr():
// TODO: consider finalizing the node thusly:
// if recursive {
// n.node.Finalize(n.ctx)
@@ -157,6 +158,9 @@
// Perhaps introduce an Err() method.
err = x.ChildErrors
}
+ if err.IsIncomplete() {
+ break
+ }
if err != nil {
parent.disjunctErrs = append(parent.disjunctErrs, err)
}
@@ -178,7 +182,8 @@
case len(n.disjunctions) > 0:
// Process full disjuncts to ensure that erroneous disjuncts are
- // eliminated.
+ // eliminated as early as possible.
+ state = Finalized
n.disjuncts = append(n.disjuncts, n)
@@ -187,16 +192,10 @@
n.disjuncts = n.buffer[:0]
n.buffer = a[:0]
- state := state
- if i+1 < len(n.disjunctions) {
- // If this is not the last disjunction, set it to
- // partial evaluation. This will disable the closedness
- // check and any other non-monotonic check that should
- // not be done unless there is complete information.
- state = Partial
+ skipNonMonotonicChecks := i+1 < len(n.disjunctions)
+ if skipNonMonotonicChecks {
+ n.ctx.inDisjunct++
}
- // TODO(perf): ideally always finalize. See comment below
- // state = Finalized
for _, dn := range a {
switch {
@@ -231,6 +230,10 @@
}
}
+ if skipNonMonotonicChecks {
+ n.ctx.inDisjunct--
+ }
+
if len(n.disjuncts) == 0 {
n.makeError()
}
@@ -268,12 +271,6 @@
outer:
for _, d := range n.disjuncts {
for _, v := range p.disjuncts {
- // TODO(perf): not checking equality here may lead to polynomial
- // blowup. Doesn't seem to affect large configurations, though,
- // where this could matter at the moment.
- if state != Finalized {
- break
- }
if Equal(n.ctx, &v.result, &d.result) {
if d.defaultMode == isDefault {
v.defaultMode = isDefault
diff --git a/internal/core/adt/eval.go b/internal/core/adt/eval.go
index 9f7d233..d09a5c2 100644
--- a/internal/core/adt/eval.go
+++ b/internal/core/adt/eval.go
@@ -201,14 +201,33 @@
v.Closed = true
}
- ignore := false
if v.Parent != nil {
if v.Parent.Closed {
v.Closed = true
}
}
- if !v.Label.IsInt() && v.Parent != nil && !ignore && state == Finalized {
+ // TODO(perf): ideally we should always perform a closedness check if
+ // state is Finalized. This is currently not possible when computing a
+ // partial disjunction as the closedness information is not yet
+ // complete, possibly leading to a disjunct to be rejected prematurely.
+ // It is probably possible to fix this if we could add StructInfo
+ // structures demarked per conjunct.
+ //
+ // In practice this should not be a problem: when disjuncts originate
+ // from the same disjunct, they will have the same StructInfos, and thus
+ // Equal is able to equate them even in the precense of optional field.
+ // In general, combining any limited set of disjuncts will soon reach
+ // a fixed point where duplicate elements can be eliminated this way.
+ //
+ // Note that not checking closedness is irrelevant for disjunctions of
+ // scalars. This means it also doesn't hurt performance where structs
+ // have a discriminator field (e.g. Kubernetes). We should take care,
+ // though, that any potential performance issues are eliminated for
+ // Protobuf-like oneOf fields.
+ ignore := state != Finalized || n.skipNonMonotonicChecks()
+
+ if !v.Label.IsInt() && v.Parent != nil && !ignore {
// Visit arcs recursively to validate and compute error.
if _, err := verifyArc2(c, v.Label, v, v.Closed); err != nil {
// Record error in child node to allow recording multiple
@@ -474,7 +493,9 @@
}
}
// MOVE BELOW
- if v := n.node.Value(); v != nil && IsConcrete(v) {
+ // TODO(perf): only delay processing of actual non-monotonic checks.
+ skip := n.skipNonMonotonicChecks()
+ if v := n.node.Value(); v != nil && IsConcrete(v) && !skip {
for _, v := range n.checks {
// TODO(errors): make Validate return bottom and generate
// optimized conflict message. Also track and inject IDs
diff --git a/internal/core/adt/optional.go b/internal/core/adt/optional.go
index c648431..05568bd 100644
--- a/internal/core/adt/optional.go
+++ b/internal/core/adt/optional.go
@@ -88,7 +88,11 @@
if m == nil {
return false
}
- return m.Match(c, env, f)
+
+ c.inConstraint++
+ ret := m.Match(c, env, f)
+ c.inConstraint--
+ return ret
}
func getMatcher(c *OpContext, env *Environment, v Value) fieldMatcher {
