internal/core/adt: some optimizations for pattern constraints
Along the lines of the optimizations done for Issue #572.
This doesn't improve much, but prevents some allocations
and effect is still noticeable.
Change-Id: I0558e2b3da8710919ddaa1fdbeeb4da0b704d1e1
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/8563
Reviewed-by: CUE cueckoo <cueckoo@gmail.com>
Reviewed-by: Paul Jolly <paul@myitcv.org.uk>
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/internal/core/adt/closed.go b/internal/core/adt/closed.go
index 3e1e434..9cf590b 100644
--- a/internal/core/adt/closed.go
+++ b/internal/core/adt/closed.go
@@ -310,6 +310,8 @@
ctx.generation++
ctx.todo = nil
+ var optionalTypes OptionalType
+
// TODO(perf): more aggressively determine whether a struct is open or
// closed: open structs do not have to be checked, yet they can particularly
// be the ones with performance isssues, for instanced as a result of
@@ -319,11 +321,12 @@
continue
}
markCounts(ctx, s.CloseInfo)
+ optionalTypes |= s.types
}
- str := ""
- if f.IsString() {
- str = f.StringValue(ctx)
+ var str Value
+ if optionalTypes&(HasComplexPattern|HasDynamic) != 0 && f.IsString() {
+ str = f.ToValue(ctx)
}
for _, s := range n.Structs {
@@ -444,7 +447,7 @@
return x
}
-func verifyArc(ctx *OpContext, s *StructInfo, f Feature, label string) bool {
+func verifyArc(ctx *OpContext, s *StructInfo, f Feature, label Value) bool {
isRegular := f.IsRegular()
o := s.StructLit
@@ -464,21 +467,24 @@
return false
}
- if f.IsString() {
+ if len(o.Dynamic) > 0 && f.IsString() {
+ if label == nil && f.IsString() {
+ label = f.ToValue(ctx)
+ }
for _, b := range o.Dynamic {
v := env.evalCached(ctx, b.Key)
s, ok := v.(*String)
if !ok {
continue
}
- if label == s.Str {
+ if label.(*String).Str == s.Str {
return true
}
}
}
for _, b := range o.Bulk {
- if matchBulk(ctx, env, b, f) {
+ if matchBulk(ctx, env, b, f, label) {
return true
}
}
diff --git a/internal/core/adt/composite.go b/internal/core/adt/composite.go
index 7cbaef4..6f19b19 100644
--- a/internal/core/adt/composite.go
+++ b/internal/core/adt/composite.go
@@ -130,6 +130,9 @@
// evalCached is used to look up let expressions. Caching let expressions
// prevents a possible combinatorial explosion.
func (e *Environment) evalCached(c *OpContext, x Expr) Value {
+ if v, ok := x.(Value); ok {
+ return v
+ }
v, ok := e.cache[x]
if !ok {
if e.cache == nil {
@@ -488,11 +491,12 @@
type OptionalType int
const (
- HasField OptionalType = 1 << iota // X: T
- HasDynamic // (X): T or "\(X)": T
- HasPattern // [X]: T
- HasAdditional // ...T
- IsOpen // Defined for all fields
+ HasField OptionalType = 1 << iota // X: T
+ HasDynamic // (X): T or "\(X)": T
+ HasPattern // [X]: T
+ HasComplexPattern // anything but a basic type
+ HasAdditional // ...T
+ IsOpen // Defined for all fields
)
func (v *Vertex) Kind() Kind {
diff --git a/internal/core/adt/expr.go b/internal/core/adt/expr.go
index 12d0b6f..d4130ce 100644
--- a/internal/core/adt/expr.go
+++ b/internal/core/adt/expr.go
@@ -121,6 +121,11 @@
case *BulkOptionalField:
o.Bulk = append(o.Bulk, x)
o.types |= HasPattern
+ switch x.Filter.(type) {
+ case *BasicType, *Top:
+ default:
+ o.types |= HasComplexPattern
+ }
case *Ellipsis:
expr := x.Value
@@ -617,6 +622,56 @@
}
}
+func (x *BoundValue) validateStr(c *OpContext, a string) bool {
+ if str, ok := x.Value.(*String); ok {
+ b := str.Str
+ switch x.Op {
+ case LessEqualOp:
+ return a <= b
+ case LessThanOp:
+ return a < b
+ case GreaterEqualOp:
+ return a >= b
+ case GreaterThanOp:
+ return a > b
+ case EqualOp:
+ return a == b
+ case NotEqualOp:
+ return a != b
+ case MatchOp:
+ return c.regexp(x.Value).MatchString(a)
+ case NotMatchOp:
+ return !c.regexp(x.Value).MatchString(a)
+ }
+ }
+ return x.validate(c, &String{Str: a}) == nil
+}
+
+func (x *BoundValue) validateInt(c *OpContext, a int64) bool {
+ switch n := x.Value.(type) {
+ case *Num:
+ b, err := n.X.Int64()
+ if err != nil {
+ break
+ }
+ switch x.Op {
+ case LessEqualOp:
+ return a <= b
+ case LessThanOp:
+ return a < b
+ case GreaterEqualOp:
+ return a >= b
+ case GreaterThanOp:
+ return a > b
+ case EqualOp:
+ return a == b
+ case NotEqualOp:
+ return a != b
+ }
+ }
+ return x.validate(c, c.NewInt64(a)) == nil
+}
+
// A NodeLink is used during computation to refer to an existing Vertex.
// It is used to signal a potential cycle or reference.
// Note that a NodeLink may be used as a value. This should be taken into
diff --git a/internal/core/adt/optional.go b/internal/core/adt/optional.go
index 8a452c9..64cd4c4 100644
--- a/internal/core/adt/optional.go
+++ b/internal/core/adt/optional.go
@@ -40,6 +40,11 @@
return
}
+ var label Value
+ if o.types&HasComplexPattern != 0 && arc.Label.IsString() {
+ label = arc.Label.ToValue(c)
+ }
+
if len(o.Bulk) > 0 {
bulkEnv := *env
bulkEnv.DynamicLabel = arc.Label
@@ -51,7 +56,7 @@
// if matched && f.additional {
// continue
// }
- if matchBulk(c, env, b, arc.Label) {
+ if matchBulk(c, env, b, arc.Label, label) {
matched = true
info := closeInfo.SpawnSpan(b.Value, ConstraintSpan)
arc.AddConjunct(MakeConjunct(&bulkEnv, b, info))
@@ -77,67 +82,43 @@
}
}
-func matchBulk(c *OpContext, env *Environment, x *BulkOptionalField, f Feature) bool {
- v, ok := c.Evaluate(env, x.Filter)
- if !ok {
- // TODO: handle dynamically
- return false
- }
+func matchBulk(c *OpContext, env *Environment, x *BulkOptionalField, f Feature, label Value) bool {
+ v := env.evalCached(c, x.Filter)
- m := getMatcher(c, env, v)
- if m == nil {
- return false
- }
-
- c.inConstraint++
- ret := m.Match(c, env, f)
- c.inConstraint--
- return ret
-}
-
-func getMatcher(c *OpContext, env *Environment, v Value) fieldMatcher {
- switch f := v.(type) {
+ // Fast-track certain cases.
+ switch x := v.(type) {
case *Top:
- return typeMatcher(TopKind)
+ return true
case *BasicType:
- return typeMatcher(f.K)
+ return x.K&StringKind != 0
- default:
- return newPatternMatcher(c, env, v)
+ case *BoundValue:
+ switch x.Kind() {
+ case StringKind:
+ if label == nil {
+ label = f.ToValue(c)
+ }
+ str := label.(*String).Str
+ return x.validateStr(c, str)
+
+ case IntKind:
+ return x.validateInt(c, int64(f.Index()))
+ }
}
-}
-type fieldMatcher interface {
- Match(c *OpContext, env *Environment, f Feature) bool
-}
-
-type typeMatcher Kind
-
-func (m typeMatcher) Match(c *OpContext, env *Environment, f Feature) bool {
- switch f.Typ() {
- case StringLabel:
- return Kind(m)&StringKind != 0
-
- case IntLabel:
- return Kind(m)&IntKind != 0
+ n := Vertex{}
+ m := MakeRootConjunct(env, v)
+ n.AddConjunct(m)
+ if label == nil {
+ label = f.ToValue(c)
}
- return false
-}
+ n.AddConjunct(MakeRootConjunct(m.Env, label))
-type patternMatcher Conjunct
+ c.inConstraint++
+ n.Finalize(c)
+ c.inConstraint--
-func (m patternMatcher) Match(c *OpContext, env *Environment, f Feature) bool {
- v := Vertex{}
- v.AddConjunct(Conjunct(m))
- label := f.ToValue(c)
- v.AddConjunct(MakeRootConjunct(m.Env, label))
- v.Finalize(c)
- b, _ := v.BaseValue.(*Bottom)
+ b, _ := n.BaseValue.(*Bottom)
return b == nil
}
-
-func newPatternMatcher(ctx *OpContext, env *Environment, x Value) fieldMatcher {
- c := MakeRootConjunct(env, x)
- return patternMatcher(c)
-}
