internal/core/dep: support dynamic dependencies
This mix of evaluation interleaved with conjunction
tracking seems most desirable for workflow
dependencies.
Change-Id: I61c8fbbc71139550613b0bf5c65e4351053eaebc
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/7641
Reviewed-by: CUE cueckoo <cueckoo@gmail.com>
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/internal/core/dep/dep.go b/internal/core/dep/dep.go
index 71ab3e4..ae9cda7 100644
--- a/internal/core/dep/dep.go
+++ b/internal/core/dep/dep.go
@@ -79,6 +79,19 @@
return visit(c, n, f, true, true)
}
+// VisitFields calls f for n and all its descendent arcs that have a conjunct
+// that originates from a conjunct in n. Only the conjuncts of n that ended up
+// as a conjunct in an actual field are visited and they are visited for each
+// field in which the occurs.
+func VisitFields(c *adt.OpContext, n *adt.Vertex, f VisitFunc) error {
+ m := marked{}
+
+ m.markExpr(n)
+
+ dynamic(c, n, f, m, true)
+ return nil
+}
+
var empty *adt.Vertex
func init() {
diff --git a/internal/core/dep/dep_test.go b/internal/core/dep/dep_test.go
index 3ec0c00..d4d6313 100644
--- a/internal/core/dep/dep_test.go
+++ b/internal/core/dep/dep_test.go
@@ -62,6 +62,10 @@
name: "all",
root: "a",
fn: dep.VisitAll,
+ }, {
+ name: "dynamic",
+ root: "a",
+ fn: dep.VisitFields,
}}
for _, tc := range testCases {
@@ -88,7 +92,6 @@
// DO NOT REMOVE: for Testing purposes.
func TestX(t *testing.T) {
- // a and a.b are the fields for which to determine the references.
in := `
`
@@ -117,7 +120,7 @@
deps := []string{}
- _ = dep.VisitAll(ctxt, n, func(d dep.Dependency) error {
+ _ = dep.VisitFields(ctxt, n, func(d dep.Dependency) error {
str := cue.MakeValue(ctxt, d.Node).Path().String()
if i := d.Import(); i != nil {
path := i.ImportPath.StringValue(ctxt)
diff --git a/internal/core/dep/mixed.go b/internal/core/dep/mixed.go
new file mode 100644
index 0000000..601bbfd
--- /dev/null
+++ b/internal/core/dep/mixed.go
@@ -0,0 +1,146 @@
+// 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 dep
+
+import (
+ "fmt"
+
+ "cuelang.org/go/internal/core/adt"
+)
+
+// dynamic visits conjuncts of structs that are defined by the root for all
+// of its fields, recursively.
+//
+// The current algorithm visits all known conjuncts and descends into the
+// evaluated Vertex. A more correct and more performant algorithm would be to
+// descend into the conjuncts and evaluate the necessary values, like fields
+// and comprehension sources.
+func dynamic(c *adt.OpContext, n *adt.Vertex, f VisitFunc, m marked, top bool) {
+ found := false
+ for _, c := range n.Conjuncts {
+ if m[c.Expr()] {
+ found = true
+ break
+ }
+ }
+
+ if !found {
+ return
+ }
+
+ if visit(c, n, f, false, top) != nil {
+ return
+ }
+
+ for _, a := range n.Arcs {
+ dynamic(c, a, f, m, false)
+ }
+}
+
+type marked map[adt.Expr]bool
+
+// TODO: factor out the below logic as either a low-level dependency analyzer or
+// some walk functionality.
+
+// markExpr visits all nodes in an expression to mark dependencies.
+func (m marked) markExpr(x adt.Expr) {
+ m[x] = true
+
+ switch x := x.(type) {
+ default:
+
+ case nil:
+ case *adt.Vertex:
+ for _, c := range x.Conjuncts {
+ m.markExpr(c.Expr())
+ }
+
+ case *adt.BinaryExpr:
+ if x.Op == adt.AndOp {
+ m.markExpr(x.X)
+ m.markExpr(x.Y)
+ }
+
+ case *adt.StructLit:
+ for _, e := range x.Decls {
+ switch x := e.(type) {
+ case *adt.Field:
+ m.markExpr(x.Value)
+
+ case *adt.OptionalField:
+ m.markExpr(x.Value)
+
+ case *adt.BulkOptionalField:
+ m.markExpr(x.Value)
+
+ case *adt.DynamicField:
+ m.markExpr(x.Value)
+
+ case *adt.Ellipsis:
+ m.markExpr(x.Value)
+
+ case adt.Expr:
+ m.markExpr(x)
+
+ case adt.Yielder:
+ m.markYielder(x)
+
+ default:
+ panic(fmt.Sprintf("unreachable %T", x))
+ }
+ }
+
+ case *adt.ListLit:
+ for _, e := range x.Elems {
+ switch x := e.(type) {
+ case adt.Expr:
+ m.markExpr(x)
+
+ case adt.Yielder:
+ m.markYielder(x)
+
+ case *adt.Ellipsis:
+ m.markExpr(x.Value)
+
+ default:
+ panic(fmt.Sprintf("unreachable %T", x))
+ }
+ }
+
+ case *adt.DisjunctionExpr:
+ for _, d := range x.Values {
+ m.markExpr(d.Val)
+ }
+
+ case adt.Yielder:
+ m.markYielder(x)
+ }
+}
+
+func (m marked) markYielder(y adt.Yielder) {
+ switch x := y.(type) {
+ case *adt.ForClause:
+ m.markYielder(x.Dst)
+
+ case *adt.IfClause:
+ m.markYielder(x.Dst)
+
+ case *adt.LetClause:
+ m.markYielder(x.Dst)
+
+ case *adt.ValueClause:
+ m.markExpr(x.StructLit)
+ }
+}
diff --git a/internal/core/dep/testdata/alias.txtar b/internal/core/dep/testdata/alias.txtar
index 51f3efa..be5f21d 100644
--- a/internal/core/dep/testdata/alias.txtar
+++ b/internal/core/dep/testdata/alias.txtar
@@ -12,3 +12,6 @@
-- out/dependencies/all --
c
d
+-- out/dependencies/dynamic --
+c
+d
diff --git a/internal/core/dep/testdata/call.txtar b/internal/core/dep/testdata/call.txtar
index 5336504..4082fbe 100644
--- a/internal/core/dep/testdata/call.txtar
+++ b/internal/core/dep/testdata/call.txtar
@@ -11,3 +11,6 @@
-- out/dependencies/all --
"encoding/json".Marshal
str
+-- out/dependencies/dynamic --
+"encoding/json".Marshal
+str
diff --git a/internal/core/dep/testdata/composed.txtar b/internal/core/dep/testdata/composed.txtar
new file mode 100644
index 0000000..78cfeaf
--- /dev/null
+++ b/internal/core/dep/testdata/composed.txtar
@@ -0,0 +1,14 @@
+-- in.cue --
+t1: {$id: "foo"} & {
+ ref: t1.stdout
+ cmd: ["sh", "-c", "echo hello"]
+ stdout: string
+}
+a: b: {$id: "foo"} & {
+ text: t1.stdout
+}
+-- out/dependencies/field --
+-- out/dependencies/all --
+t1.stdout
+-- out/dependencies/dynamic --
+t1.stdout
diff --git a/internal/core/dep/testdata/expr.txtar b/internal/core/dep/testdata/expr.txtar
index 88c48ea..1816962 100644
--- a/internal/core/dep/testdata/expr.txtar
+++ b/internal/core/dep/testdata/expr.txtar
@@ -20,3 +20,9 @@
e
d
e
+-- out/dependencies/dynamic --
+d
+d
+c
+c[0]
+e
diff --git a/internal/core/dep/testdata/field.txtar b/internal/core/dep/testdata/field.txtar
index e993bc3..42af863 100644
--- a/internal/core/dep/testdata/field.txtar
+++ b/internal/core/dep/testdata/field.txtar
@@ -21,3 +21,8 @@
c
c
c
+-- out/dependencies/dynamic --
+pattern
+name
+c
+c
diff --git a/internal/core/dep/testdata/incomplete.txtar b/internal/core/dep/testdata/incomplete.txtar
index fdf83ad..f22b60b 100644
--- a/internal/core/dep/testdata/incomplete.txtar
+++ b/internal/core/dep/testdata/incomplete.txtar
@@ -18,3 +18,10 @@
e
c.d
c.d
+-- out/dependencies/dynamic --
+c.d
+c
+c
+e
+c.d
+c.d
diff --git a/internal/core/dep/testdata/list.txtar b/internal/core/dep/testdata/list.txtar
index 217194a..3ae09ce 100644
--- a/internal/core/dep/testdata/list.txtar
+++ b/internal/core/dep/testdata/list.txtar
@@ -9,3 +9,6 @@
-- out/dependencies/all --
d
e
+-- out/dependencies/dynamic --
+d
+e
diff --git a/internal/core/dep/testdata/listcomprehension.txtar b/internal/core/dep/testdata/listcomprehension.txtar
index d2a458f..b4908a4 100644
--- a/internal/core/dep/testdata/listcomprehension.txtar
+++ b/internal/core/dep/testdata/listcomprehension.txtar
@@ -9,3 +9,10 @@
-- out/dependencies/all --
c
d
+-- out/dependencies/dynamic --
+c
+d
+c[0].a
+d
+c[1].a
+d
diff --git a/internal/core/dep/testdata/self.txtar b/internal/core/dep/testdata/self.txtar
index 70bf1f5..c8c8214 100644
--- a/internal/core/dep/testdata/self.txtar
+++ b/internal/core/dep/testdata/self.txtar
@@ -16,3 +16,8 @@
-- out/dependencies/field --
-- out/dependencies/all --
m
+-- out/dependencies/dynamic --
+m
+a.b.y
+a.b.x.f
+a.b
diff --git a/internal/core/dep/testdata/structcomprehension.txtar b/internal/core/dep/testdata/structcomprehension.txtar
index 62ffd8f..594866c 100644
--- a/internal/core/dep/testdata/structcomprehension.txtar
+++ b/internal/core/dep/testdata/structcomprehension.txtar
@@ -17,3 +17,10 @@
c
e
d
+-- out/dependencies/dynamic --
+c
+e
+c[0]
+d
+c[1]
+d
