cmd/cue/cmd: prevent infinite loops while building dependency graph
The existing implementatin resulted in an infinite loop in two cases:
1. In the v.Equals(after) call when the 'after' dependencies were cyclic
2. In the task.Walk function when task fields cyclically referenced
other tasks
This commit solves both cases by
- stepping out of the Walk lambda when it had already been evaluated
with the given parameter; and
- removing the special case for 'after' dependencies as it is no longer
necessary.
Relevent tests are included.
Updates #245
Change-Id: I914ff9aad96eb43ae89964000dea60ccd44c38a2
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/4910
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cmd/cue/cmd/custom.go b/cmd/cue/cmd/custom.go
index 22e5a79..5ab3cdf 100644
--- a/cmd/cue/cmd/custom.go
+++ b/cmd/cue/cmd/custom.go
@@ -283,13 +283,23 @@
exitIfErr(cmd, inst, err, true)
}
+ visited := make(map[string]bool)
task.Walk(func(v cue.Value) bool {
if v == task {
return true
}
- if after.Err() == nil && v.Equals(after) {
- return false
+
+ // Prevent inifinite walks
+ _, vPath := v.Reference()
+ if vPath != nil {
+ vPath := string(keyForReference(vPath...))
+ _, isVisited := visited[vPath]
+ if isVisited {
+ return false
+ }
+ visited[vPath] = true
}
+
for _, r := range appendReferences(nil, cr.root, v) {
if dep := cr.findTask(r); dep != nil && t != dep {
// TODO(string): consider adding dependencies
diff --git a/cmd/cue/cmd/testdata/script/cmd_dep_cycle.txt b/cmd/cue/cmd/testdata/script/cmd_dep_cycle.txt
new file mode 100644
index 0000000..56f6cfd
--- /dev/null
+++ b/cmd/cue/cmd/testdata/script/cmd_dep_cycle.txt
@@ -0,0 +1,33 @@
+! cue cmd cycle
+cmp stderr expect-stderr
+! cue cmd aftercycle
+cmp stderr expect-stderr
+cue cmd interlockedTasks
+cmp stdout interlocked-stdout
+
+-- expect-stderr --
+cyclic dependency in tasks
+-- interlocked-stdout --
+v
+v
+-- after_tool.cue --
+package home
+
+import (
+ "tool/cli"
+)
+
+command: interlockedTasks: {
+ t1: cli.Print & { text: ref.value, ref: t2, value: "v" }
+ t2: cli.Print & { text: ref.value, ref: t1, value: "v" }
+}
+
+command: aftercycle: {
+ t1: cli.Print & { $after: t2, text: "t1" }
+ t2: cli.Print & { $after: t1, text: "t2" }
+}
+
+command: cycle: {
+ t1: cli.Print & { text: t2.text }
+ t2: cli.Print & { text: t1.text }
+}