internal/core/eval: minor performance improvements for disjunctions
This also remove some duplicates.
This makes Issue #758 a bit more pallatable, although
the core issue remains.
Change-Id: I0d7c60c96cc7ebf65380c677626215f586d7a7e9
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/8801
Reviewed-by: CUE cueckoo <cueckoo@gmail.com>
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/testdata/disjunctions/embed.txtar b/cue/testdata/disjunctions/embed.txtar
index 5d8e063..3a98652 100644
--- a/cue/testdata/disjunctions/embed.txtar
+++ b/cue/testdata/disjunctions/embed.txtar
@@ -159,10 +159,6 @@
e: (string){ string }
}, (#struct){
d: (string){ string }
- }, (#struct){
- d: (string){ string }
- }, (#struct){
- d: (string){ string }
e: (string){ string }
}, (#struct){
a: (string){ string }
@@ -186,12 +182,6 @@
}, (#struct){
a: (string){ string }
d: (string){ string }
- }, (#struct){
- a: (string){ string }
- d: (string){ string }
- }, (#struct){
- a: (string){ string }
- d: (string){ string }
e: (string){ string }
}, (#struct){
b: (string){ string }
@@ -215,12 +205,6 @@
}, (#struct){
b: (string){ string }
d: (string){ string }
- }, (#struct){
- b: (string){ string }
- d: (string){ string }
- }, (#struct){
- b: (string){ string }
- d: (string){ string }
e: (string){ string }
}) }
a: (struct){ |(*(#struct){
diff --git a/cue/types.go b/cue/types.go
index e78c41f..8e09deb 100644
--- a/cue/types.go
+++ b/cue/types.go
@@ -1831,7 +1831,7 @@
if v.v == nil || other.v == nil {
return false
}
- return adt.Equal(v.ctx().opCtx, v.v, other.v, false)
+ return adt.Equal(v.ctx().opCtx, v.v, other.v, adt.CheckStructural)
}
// Format prints a debug version of a value.
diff --git a/internal/core/adt/disjunct.go b/internal/core/adt/disjunct.go
index 636f07d..f03a338 100644
--- a/internal/core/adt/disjunct.go
+++ b/internal/core/adt/disjunct.go
@@ -122,7 +122,7 @@
state VertexStatus,
parent *nodeContext,
parentMode defaultMode, // default mode of this disjunct
- recursive bool) {
+ recursive, last bool) {
n.ctx.stats.DisjunctCount++
@@ -210,6 +210,7 @@
n.disjuncts = n.buffer[:0]
n.buffer = a[:0]
+ last := i+1 == len(n.disjunctions)
skipNonMonotonicChecks := i+1 < len(n.disjunctions)
if skipNonMonotonicChecks {
n.ctx.inDisjunct++
@@ -228,7 +229,7 @@
newMode := mode(d.hasDefaults, v.Default)
- cn.expandDisjuncts(state, n, newMode, true)
+ cn.expandDisjuncts(state, n, newMode, true, last)
}
case d.value != nil:
@@ -241,7 +242,7 @@
newMode := mode(d.hasDefaults, i < d.value.NumDefaults)
- cn.expandDisjuncts(state, n, newMode, true)
+ cn.expandDisjuncts(state, n, newMode, true, last)
}
}
}
@@ -365,7 +366,11 @@
outer:
for _, d := range n.disjuncts {
for k, v := range p.disjuncts {
- if Equal(n.ctx, &v.result, &d.result, true) {
+ flags := CheckStructural
+ if last {
+ flags |= IgnoreOptional
+ }
+ if Equal(n.ctx, &v.result, &d.result, flags) {
m := maybeDefault
for _, u := range d.usedDefault {
m = combineDefault(m, u.nestedMode)
diff --git a/internal/core/adt/equality.go b/internal/core/adt/equality.go
index de57df9..d1b5a1d 100644
--- a/internal/core/adt/equality.go
+++ b/internal/core/adt/equality.go
@@ -14,17 +14,30 @@
package adt
-func Equal(ctx *OpContext, v, w Value, optional bool) bool {
+type Flag uint16
+
+const (
+ // IgnoreOptional allows optional information to be ignored. This only
+ // applies when CheckStructural is given.
+ IgnoreOptional Flag = 1 << iota
+
+ // CheckStructural indicates that closedness information should be
+ // considered for equality. Equal may return false even when values are
+ // equal.
+ CheckStructural Flag = 1 << iota
+)
+
+func Equal(ctx *OpContext, v, w Value, flags Flag) bool {
if x, ok := v.(*Vertex); ok {
- return equalVertex(ctx, x, w, optional)
+ return equalVertex(ctx, x, w, flags)
}
if y, ok := w.(*Vertex); ok {
- return equalVertex(ctx, y, v, optional)
+ return equalVertex(ctx, y, v, flags)
}
- return equalTerminal(ctx, v, w, optional)
+ return equalTerminal(ctx, v, w, flags)
}
-func equalVertex(ctx *OpContext, x *Vertex, v Value, opt bool) bool {
+func equalVertex(ctx *OpContext, x *Vertex, v Value, flags Flag) bool {
y, ok := v.(*Vertex)
if !ok {
return false
@@ -47,7 +60,7 @@
if x.IsClosed(ctx) != y.IsClosed(ctx) {
return false
}
- if opt && !equalClosed(ctx, x, y) {
+ if flags != 0 && !equalClosed(ctx, x, y, flags) {
return false
}
@@ -55,7 +68,7 @@
for _, a := range x.Arcs {
for _, b := range y.Arcs {
if a.Label == b.Label {
- if !Equal(ctx, a, b, opt) {
+ if !Equal(ctx, a, b, flags) {
return false
}
continue loop1
@@ -81,7 +94,7 @@
return true // both are struct or list.
}
- return equalTerminal(ctx, v, w, opt)
+ return equalTerminal(ctx, v, w, flags)
}
// equalClosed tests if x and y have the same set of close information.
@@ -93,16 +106,21 @@
//
// For all these refinements it would be necessary to have well-working
// structure sharing so as to not repeatedly recompute optional arcs.
-func equalClosed(ctx *OpContext, x, y *Vertex) bool {
- return verifyStructs(x, y) && verifyStructs(y, x)
+func equalClosed(ctx *OpContext, x, y *Vertex, flags Flag) bool {
+ return verifyStructs(x, y, flags) && verifyStructs(y, x, flags)
}
-func verifyStructs(x, y *Vertex) bool {
+func verifyStructs(x, y *Vertex, flags Flag) bool {
outer:
for _, s := range x.Structs {
- if s.closeInfo == nil || s.closeInfo.span|DefinitionSpan == 0 {
+ if (flags&IgnoreOptional != 0) && !s.StructLit.HasOptional() {
continue
}
+ if s.closeInfo == nil || s.closeInfo.span&DefinitionSpan == 0 {
+ if !s.StructLit.HasOptional() {
+ continue
+ }
+ }
for _, t := range y.Structs {
if s.StructLit == t.StructLit {
continue outer
@@ -113,7 +131,7 @@
return true
}
-func equalTerminal(ctx *OpContext, v, w Value, opt bool) bool {
+func equalTerminal(ctx *OpContext, v, w Value, flags Flag) bool {
if v == w {
return true
}
@@ -130,7 +148,7 @@
case *BoundValue:
if y, ok := w.(*BoundValue); ok {
- return x.Op == y.Op && Equal(ctx, x.Value, y.Value, opt)
+ return x.Op == y.Op && Equal(ctx, x.Value, y.Value, flags)
}
case *BasicType:
@@ -145,7 +163,7 @@
}
// always ordered the same
for i, xe := range x.Values {
- if !Equal(ctx, xe, y.Values[i], opt) {
+ if !Equal(ctx, xe, y.Values[i], flags) {
return false
}
}
@@ -159,7 +177,7 @@
return false
}
for i, xe := range x.Values {
- if !Equal(ctx, xe, y.Values[i], opt) {
+ if !Equal(ctx, xe, y.Values[i], flags) {
return false
}
}
diff --git a/internal/core/adt/eval.go b/internal/core/adt/eval.go
index 7386e66..330c54b 100644
--- a/internal/core/adt/eval.go
+++ b/internal/core/adt/eval.go
@@ -306,7 +306,7 @@
if len(n.disjunctions) > 0 && disState != Finalized {
disState = Finalized
}
- n.expandDisjuncts(disState, n, maybeDefault, false)
+ n.expandDisjuncts(disState, n, maybeDefault, false, true)
n.finalizeDisjuncts()
diff --git a/internal/core/adt/simplify.go b/internal/core/adt/simplify.go
index dea3066..4bf0876 100644
--- a/internal/core/adt/simplify.go
+++ b/internal/core/adt/simplify.go
@@ -214,7 +214,7 @@
return nil
}
for i, a := range x.Args {
- if !Equal(ctx, a, y.Args[i], false) {
+ if !Equal(ctx, a, y.Args[i], CheckStructural) {
return nil
}
}
