internal/core/adt: optimize cycle detection for disjunctions

The cyclicReferences optimization was not implemented for
disjunction, because it was rather hard to do and we plan to
reimplement disjunction anyway. However, this optimization turns
out to be crucial for performance.

Fixes #1940
Fixes #1684

Related but fixed earlier:

Closes #758

Signed-off-by: Marcel van Lohuizen <mpvl@gmail.com>
Change-Id: I6fbbbace591e313df3b5759c3ab8047a893fb6ba
Reviewed-on: https://review.gerrithub.io/c/cue-lang/cue/+/543675
Reviewed-by: Daniel Martí <mvdan@mvdan.cc>
Reviewed-by: Roger Peppe <rogpeppe@gmail.com>
Unity-Result: CUEcueckoo <cueckoo@cuelang.org>
TryBot-Result: CUEcueckoo <cueckoo@cuelang.org>
diff --git a/cmd/cue/cmd/testdata/script/issue217.txtar b/cmd/cue/cmd/testdata/script/issue217.txtar
index 6d2e337..b17b06a 100644
--- a/cmd/cue/cmd/testdata/script/issue217.txtar
+++ b/cmd/cue/cmd/testdata/script/issue217.txtar
@@ -24,7 +24,7 @@
 #A: string | [#A]
 -- eval-stdout --
 x: {
-    a: string | [string]
-    b: string | [string]
+    a: string
+    b: string
 }
 #A: string
diff --git a/cue/testdata/benchmarks/issue1684.txtar b/cue/testdata/benchmarks/issue1684.txtar
new file mode 100644
index 0000000..892859c
--- /dev/null
+++ b/cue/testdata/benchmarks/issue1684.txtar
@@ -0,0 +1,120 @@
+#Issue: 1684
+
+// TODO: significantly reduce the number of counts in this evaluation.
+-- stats.txt --
+Leaks:  0
+Freed:  384153
+Reused: 384113
+Allocs: 40
+Retain: 0
+
+Unifications: 285437
+Conjuncts:    1347594
+Disjuncts:    384153
+
+-- in.cue --
+#Secret: {
+	$secret: id: string
+}
+#secrets: #Secret | {[string]: #secrets}
+
+out: #secrets & {
+	FOO: $secret: id: "100"
+	ONE: TWO: THREE: $secret: id: "123"
+}
+
+#Secret: {
+	$secret: _id: string
+}
+#secrets: #Secret | {[string]: #secrets}
+
+out: #secrets & {
+	FOO: $secret: _id: "100"
+	ONE: TWO: THREE: $secret: _id: "123"
+}
+-- out/eval --
+(struct){
+  #Secret: (#struct){
+    $secret: (#struct){
+      id: (string){ string }
+      _id: (string){ string }
+    }
+  }
+  #secrets: (#struct){ |((#struct){
+      $secret: (#struct){
+        id: (string){ string }
+        _id: (string){ string }
+      }
+    }, (#struct){
+    }) }
+  out: (#struct){
+    FOO: (#struct){
+      $secret: (#struct){
+        id: (string){ "100" }
+        _id: (string){ "100" }
+      }
+    }
+    ONE: (#struct){
+      TWO: (#struct){
+        THREE: (#struct){
+          $secret: (#struct){
+            id: (string){ "123" }
+            _id: (string){ "123" }
+          }
+        }
+      }
+    }
+  }
+}
+-- out/compile --
+--- in.cue
+{
+  #Secret: {
+    $secret: {
+      id: string
+    }
+  }
+  #secrets: (〈0;#Secret〉|{
+    [string]: 〈1;#secrets〉
+  })
+  out: (〈0;#secrets〉 & {
+    FOO: {
+      $secret: {
+        id: "100"
+      }
+    }
+    ONE: {
+      TWO: {
+        THREE: {
+          $secret: {
+            id: "123"
+          }
+        }
+      }
+    }
+  })
+  #Secret: {
+    $secret: {
+      _id: string
+    }
+  }
+  #secrets: (〈0;#Secret〉|{
+    [string]: 〈1;#secrets〉
+  })
+  out: (〈0;#secrets〉 & {
+    FOO: {
+      $secret: {
+        _id: "100"
+      }
+    }
+    ONE: {
+      TWO: {
+        THREE: {
+          $secret: {
+            _id: "123"
+          }
+        }
+      }
+    }
+  })
+}
diff --git a/cue/testdata/benchmarks/listdisj.txtar b/cue/testdata/benchmarks/listdisj.txtar
new file mode 100644
index 0000000..be98db2
--- /dev/null
+++ b/cue/testdata/benchmarks/listdisj.txtar
@@ -0,0 +1,77 @@
+#Issue: 1940
+
+-- stats.txt --
+Leaks:  0
+Freed:  447
+Reused: 439
+Allocs: 8
+Retain: 0
+
+Unifications: 287
+Conjuncts:    894
+Disjuncts:    447
+
+-- in.cue --
+#T:
+	["a", #T] |
+	["b", #T] |
+	["c", #T] |
+	["d", ...#T]
+
+x: #T
+y: #T
+z: #T
+v: #T
+
+#X: x
+#X: y
+#X: z
+#X: v
+#X: #T
+-- out/compile --
+--- in.cue
+{
+  #T: ([
+    "a",
+    〈1;#T〉,
+  ]|[
+    "b",
+    〈1;#T〉,
+  ]|[
+    "c",
+    〈1;#T〉,
+  ]|[
+    "d",
+    ...〈1;#T〉,
+  ])
+  x: 〈0;#T〉
+  y: 〈0;#T〉
+  z: 〈0;#T〉
+  v: 〈0;#T〉
+  #X: 〈0;x〉
+  #X: 〈0;y〉
+  #X: 〈0;z〉
+  #X: 〈0;v〉
+  #X: 〈0;#T〉
+}
+-- out/eval --
+(struct){
+  #T: (list){
+    0: (string){ "d" }
+  }
+  x: (list){
+    0: (string){ "d" }
+  }
+  y: (list){
+    0: (string){ "d" }
+  }
+  z: (list){
+    0: (string){ "d" }
+  }
+  v: (list){
+    0: (string){ "d" }
+  }
+  #X: (list){
+    0: (string){ "d" }
+  }
+}
diff --git a/cue/testdata/cycle/self.txtar b/cue/testdata/cycle/self.txtar
index dda5428..c1a5372 100644
--- a/cue/testdata/cycle/self.txtar
+++ b/cue/testdata/cycle/self.txtar
@@ -94,7 +94,7 @@
 	#A: {#A} | string
 }
 
-// TODO: x and #A should yield the same result.
+// x and #A should yield the same result.
 disjList: _
 disjList: ok1: {
 	#A: string | [#A]
@@ -454,9 +454,7 @@
   disjList: (struct){
     ok1: (struct){
       #A: (string){ string }
-      x: ((string|list)){ |((string){ string }, (#list){
-          0: (string){ string }
-        }) }
+      x: (string){ string }
       y: (#list){
         0: (#list){
           0: (#list){
@@ -468,21 +466,15 @@
       }
     }
     ok2: (struct){
-      x: ((string|list)){ |((string){ string }, (#list){
-          0: (string){ string }
-        }) }
+      x: (string){ string }
       #A: (string){ string }
     }
     ok3: (struct){
       #A: (string){ string }
-      x: ((string|list)){ |((#list){
-          0: (string){ string }
-        }, (string){ string }) }
+      x: (string){ string }
     }
     ok4: (struct){
-      x: ((string|list)){ |((#list){
-          0: (string){ string }
-        }, (string){ string }) }
+      x: (string){ string }
       #A: (string){ string }
     }
   }
@@ -533,9 +525,7 @@
   }
   dynamicList: (struct){
     ok1: (struct){
-      x: ((string|list)){ |((string){ string }, (#list){
-          0: (string){ string }
-        }) }
+      x: (string){ string }
       y: (#list){
         0: (#list){
           0: (#list){
@@ -548,21 +538,15 @@
       foo: (string){ string }
     }
     ok2: (struct){
-      x: ((string|list)){ |((string){ string }, (#list){
-          0: (string){ string }
-        }) }
+      x: (string){ string }
       foo: (string){ string }
     }
     ok3: (struct){
-      x: ((string|list)){ |((#list){
-          0: (string){ string }
-        }, (string){ string }) }
+      x: (string){ string }
       foo: (string){ string }
     }
     ok4: (struct){
-      x: ((string|list)){ |((#list){
-          0: (string){ string }
-        }, (string){ string }) }
+      x: (string){ string }
       foo: (string){ string }
     }
   }
diff --git a/cue/testdata/disjunctions/elimination.txtar b/cue/testdata/disjunctions/elimination.txtar
index bde16e6..67f6b70 100644
--- a/cue/testdata/disjunctions/elimination.txtar
+++ b/cue/testdata/disjunctions/elimination.txtar
@@ -246,6 +246,18 @@
 	#X: #T
 }
 
+issue1940: {
+	#T: ["a", #T] | ["b", #T] | ["c", #T] | ["d", [...#T]]
+
+	#A: type: #T
+
+	#B: [string]: #A
+
+	#C: #B & {
+		x: #A
+	}
+}
+
 -- out/eval --
 (struct){
   disambiguateClosed: (struct){
@@ -619,22 +631,37 @@
     #T: (list){
       0: (string){ "d" }
     }
-    x: (#list){ |((#list){
-        0: (string){ "a" }
-        1: (list){
-          0: (string){ "d" }
-        }
-      }, (list){
+    x: (list){
+      0: (string){ "d" }
+    }
+    #X: (list){
+      0: (string){ "d" }
+    }
+  }
+  issue1940: (struct){
+    #T: (#list){
+      0: (string){ "d" }
+      1: (list){
+      }
+    }
+    #A: (#struct){
+      type: (#list){
         0: (string){ "d" }
-      }) }
-    #X: (#list){ |((#list){
-        0: (string){ "a" }
         1: (list){
-          0: (string){ "d" }
         }
-      }, (list){
-        0: (string){ "d" }
-      }) }
+      }
+    }
+    #B: (#struct){
+    }
+    #C: (#struct){
+      x: (#struct){
+        type: (#list){
+          0: (string){ "d" }
+          1: (list){
+          }
+        }
+      }
+    }
   }
 }
 -- out/compile --
@@ -1325,4 +1352,30 @@
     #X: 〈0;x〉
     #X: 〈0;#T〉
   }
+  issue1940: {
+    #T: ([
+      "a",
+      〈1;#T〉,
+    ]|[
+      "b",
+      〈1;#T〉,
+    ]|[
+      "c",
+      〈1;#T〉,
+    ]|[
+      "d",
+      [
+        ...〈2;#T〉,
+      ],
+    ])
+    #A: {
+      type: 〈1;#T〉
+    }
+    #B: {
+      [string]: 〈1;#A〉
+    }
+    #C: (〈0;#B〉 & {
+      x: 〈1;#A〉
+    })
+  }
 }
diff --git a/internal/core/adt/disjunct.go b/internal/core/adt/disjunct.go
index ea5c3fd..c8960f1 100644
--- a/internal/core/adt/disjunct.go
+++ b/internal/core/adt/disjunct.go
@@ -126,6 +126,13 @@
 
 	n.ctx.stats.Disjuncts++
 
+	// refNode is used to collect cyclicReferences for all disjuncts to be
+	// passed up to the parent node. Note that because the node in the parent
+	// context is overwritten in the course of expanding disjunction to retain
+	// pointer identity, it is not possible to simply record the refNodes in the
+	// parent directly.
+	var refNode *RefNode
+
 	node := n.node
 	defer func() {
 		n.node = node
@@ -227,6 +234,17 @@
 						newMode := mode(d.hasDefaults, v.Default)
 
 						cn.expandDisjuncts(state, n, newMode, true, last)
+
+						// Record the cyclicReferences of the conjunct in the
+						// parent list.
+						// TODO: avoid the copy. It should be okay to "steal"
+						// this list and avoid the copy. But this change is best
+						// done in a separate CL.
+						for r := n.node.cyclicReferences; r != nil; r = r.Next {
+							s := *r
+							s.Next = refNode
+							refNode = &s
+						}
 					}
 
 				case d.value != nil:
@@ -240,6 +258,13 @@
 						newMode := mode(d.hasDefaults, i < d.value.NumDefaults)
 
 						cn.expandDisjuncts(state, n, newMode, true, last)
+
+						// See comment above.
+						for r := n.node.cyclicReferences; r != nil; r = r.Next {
+							s := *r
+							s.Next = refNode
+							refNode = &s
+						}
 					}
 				}
 			}
@@ -390,6 +415,14 @@
 
 		n.disjuncts = n.disjuncts[:0]
 	}
+
+	// Record the refNodes in the parent.
+	for r := refNode; r != nil; {
+		next := r.Next
+		r.Next = parent.node.cyclicReferences
+		parent.node.cyclicReferences = r
+		r = next
+	}
 }
 
 func (n *nodeContext) makeError() {
diff --git a/internal/core/adt/eval.go b/internal/core/adt/eval.go
index 670948c..d8a9724 100644
--- a/internal/core/adt/eval.go
+++ b/internal/core/adt/eval.go
@@ -297,6 +297,7 @@
 		case 1:
 			x := n.disjuncts[0].result
 			x.state = nil
+			x.cyclicReferences = n.node.cyclicReferences
 			*v = x
 
 		default: