internal/diff: avoid cycle when diffing
Also introduce a MaxDepth constant and use it
consistently.
Change-Id: I82d07ae3fdad903382a8291743f0beeabb147ce9
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/5460
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/subsume.go b/cue/subsume.go
index 57834a5..05881cb 100644
--- a/cue/subsume.go
+++ b/cue/subsume.go
@@ -64,6 +64,10 @@
// recorded values where an error occurred.
gt, lt evaluated
missing label
+
+ // depth is used to work around undetected cycles.
+ // TODO(eval): remove once cycle detection is implemented.
+ depth int
}
type subsumeMode int
@@ -98,6 +102,12 @@
// subsumption could be proven. For concreted values it returns the exact
// relation. It never returns a false positive.
func (s *subsumer) subsumes(gt, lt value) (result bool) {
+ if s.depth > internal.MaxDepth {
+ return true
+ }
+ s.depth++
+ defer func() { s.depth-- }()
+
ctx := s.ctx
var v, w evaluated
if s.mode&subChoose == 0 {
diff --git a/cue/types.go b/cue/types.go
index 9b71831..8da7660 100644
--- a/cue/types.go
+++ b/cue/types.go
@@ -2013,8 +2013,8 @@
func (x *validator) walk(v Value, opts options) {
// TODO(#42): we can get rid of the arbitrary evaluation depth once CUE has
// proper structural cycle detection. See Issue #42. Currently errors
- // occuring at a depth > 20 will not be detected.
- if x.depth > 20 {
+ // occuring at a depth > internal.MaxDepth will not be detected.
+ if x.depth > internal.MaxDepth {
return
}
ctx := v.ctx()
diff --git a/cue/validate.go b/cue/validate.go
index 5673524..08d17f0 100644
--- a/cue/validate.go
+++ b/cue/validate.go
@@ -14,6 +14,8 @@
package cue
+import "cuelang.org/go/internal"
+
// validate returns whether there is any error, recursively.
func validate(ctx *context, v value) (err *bottom) {
eval := v.evalPartial(ctx)
@@ -26,7 +28,7 @@
if err != nil {
return err
}
- if ctx.maxDepth++; ctx.maxDepth > 20 {
+ if ctx.maxDepth++; ctx.maxDepth > internal.MaxDepth {
return nil
}
for i, a := range x.arcs {
diff --git a/internal/diff/diff.go b/internal/diff/diff.go
index e3a5013..6c8689a 100644
--- a/internal/diff/diff.go
+++ b/internal/diff/diff.go
@@ -44,7 +44,7 @@
// Diff returns an edit script representing the difference between x and y.
func (p *Profile) Diff(x, y cue.Value) (Kind, *EditScript) {
- d := differ{cfg: p}
+ d := differ{cfg: *p}
return d.diffValue(x, y)
}
@@ -157,7 +157,7 @@
func (e Edit) YPos() int { return int(e.yPos - 1) }
type differ struct {
- cfg *Profile
+ cfg Profile
options []cue.Option
errs errors.Error
}
@@ -186,6 +186,11 @@
fallthrough
default:
+ // In concrete mode we do not care about non-concrete values.
+ if d.cfg.Concrete {
+ return Identity, nil
+ }
+
if !x.Equals(y) {
return Modified, nil
}
diff --git a/internal/diff/diff_test.go b/internal/diff/diff_test.go
index e4b7a47..c52a2a1 100644
--- a/internal/diff/diff_test.go
+++ b/internal/diff/diff_test.go
@@ -23,10 +23,11 @@
func TestDiff(t *testing.T) {
testCases := []struct {
- name string
- x, y string
- kind Kind
- diff string
+ name string
+ x, y string
+ kind Kind
+ diff string
+ profile *Profile
}{{
name: "identity struct",
x: `{
@@ -302,6 +303,69 @@
- }
}
`,
+ }, {
+ x: `
+ Directory :: {
+ {
+ // Directory from another directory (e.g. subdirectory)
+ from: Directory
+ } | {
+ // Reference to remote directory
+ ref: string
+ } | {
+ // Use a local directory
+ local: string
+ }
+ path: string | *"/"
+ }
+ `,
+ y: `
+ Directory :: {
+ {
+ // Directory from another directory (e.g. subdirectory)
+ from: Directory
+ } | {
+ // Reference to remote directory
+ ref: string
+ } | {
+ // Use a local directory
+ local: string
+ }
+ path: string | *"/"
+ }
+ `,
+ profile: Final,
+ }, {
+ x: `
+ Directory :: {
+ {
+ // Directory from another directory (e.g. subdirectory)
+ from: Directory
+ } | {
+ // Reference to remote directory
+ ref: string
+ } | {
+ // Use a local directory
+ local: string
+ }
+ path: string | *"/"
+ }
+ `,
+ y: `
+ Directory :: {
+ {
+ // Directory from another directory (e.g. subdirectory)
+ from: Directory
+ } | {
+ // Reference to remote directory
+ ref: string
+ } | {
+ // Use a local directory
+ local: string
+ }
+ path: string | *"/"
+ }
+ `,
}}
for _, tc := range testCases {
t.Run(tc.name, func(t *testing.T) {
@@ -314,7 +378,11 @@
if err != nil {
t.Fatal(err)
}
- kind, script := Diff(x.Value(), y.Value())
+ p := tc.profile
+ if p == nil {
+ p = Schema
+ }
+ kind, script := p.Diff(x.Value(), y.Value())
if kind != tc.kind {
t.Fatalf("got %d; want %d", kind, tc.kind)
}
diff --git a/internal/internal.go b/internal/internal.go
index cdf28dc..f12f267 100644
--- a/internal/internal.go
+++ b/internal/internal.go
@@ -206,3 +206,12 @@
func (e *decorated) Is(err error) bool {
return xerrors.Is(e.info, err) || xerrors.Is(e.cueError, err)
}
+
+// MaxDepth indicates the maximum evaluation depth. This is there to break
+// cycles in the absence of cycle detection.
+//
+// It is registered in a central place to make it easy to find all spots where
+// cycles are broken in this brute-force manner.
+//
+// TODO(eval): have cycle detection.
+const MaxDepth = 20
