cue: fix regression in merge
This reimplements the template stripper.
It is considerably more code, but easier to understand,
more performant, but more importantly, easier to debug.
Fixes #38.
Change-Id: Id4e6988941b43e47f02cbbd3c2fdfdc10ac2ffa7
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/1880
Reviewed-by: Marcel van Lohuizen <mpvl@google.com>
diff --git a/cue/instance.go b/cue/instance.go
index b2c17f2..e3b0fbf 100644
--- a/cue/instance.go
+++ b/cue/instance.go
@@ -17,7 +17,6 @@
import (
"cuelang.org/go/cue/ast"
"cuelang.org/go/cue/build"
- "cuelang.org/go/cue/token"
"cuelang.org/go/internal"
"golang.org/x/exp/errors/fmt"
)
@@ -146,21 +145,17 @@
return inst[0]
}
+ values := []value{}
for _, i := range inst {
if i.Err != nil {
return i
}
+ values = append(values, i.rootValue)
}
+ merged := &mergedValues{values: values}
ctx := inst[0].newContext()
- merged := stripTemplates(ctx, inst[0].rootValue)
-
- for _, i := range inst[1:] {
- x := stripTemplates(ctx, i.rootValue)
- merged = mkBin(ctx, token.NoPos, opUnify, merged, x)
- }
-
st, ok := ctx.manifest(merged).(*structLit)
if !ok {
return nil
diff --git a/cue/instance_test.go b/cue/instance_test.go
index fb99905..da8569c 100644
--- a/cue/instance_test.go
+++ b/cue/instance_test.go
@@ -82,6 +82,20 @@
),
out: `{obj:{alpha:{a:A,b:2},beta:{a:B,b:3}}}`,
}, {
+ desc: "top-level comprehensions",
+ instances: insts(`
+ t: {"\(k)": 10 for k, x in s}
+ s <Name>: {}
+ s foo a: 1
+ `,
+ `
+ t: {"\(k)": 10 for k, x in s}
+ s <Name>: {}
+ s bar b: 2
+ `,
+ ),
+ out: `{t:{foo:10,bar:10},s:{foo:{a:1},bar:{b:2}}}`,
+ }, {
desc: "error",
instances: insts(`a:`),
out: `{}`,
diff --git a/cue/strip.go b/cue/strip.go
index 9e8ac78..22defda 100644
--- a/cue/strip.go
+++ b/cue/strip.go
@@ -14,32 +14,112 @@
package cue
-// This file defines a rewriter that strips a fully evaluated value of its
-// template.
+import (
+ "sort"
+)
-// TODO: currently strip templates does a full evaluation as it is hard to keep
-// nodeRef and copied structs in sync. This is far from efficient, but it is the
-// easiest to get correct.
-
-// stripTemplates evaluates v and strips the result of templates.
-func stripTemplates(ctx *context, v value) value {
- return rewrite(ctx, v, stripRewriter)
+// A mergedValues type merges structs without unifying their templates.
+// It evaluates structs in parallel and then creates a new mergedValues
+// for each duplicate arc. The mergedValues do not reappear once there is
+// only a single value per arc.
+//
+// This is used to merge different instances which may have incompatible
+// specializations, but have disjuncts objects that may otherwise be shared
+// in the same namespace.
+type mergedValues struct {
+ baseValue
+ values []value
}
-func stripRewriter(ctx *context, v value) (value, bool) {
- eval := ctx.manifest(v)
- switch x := eval.(type) {
- case *structLit:
- x = x.expandFields(ctx)
- if x.template != nil {
- arcs := make(arcs, len(x.arcs))
- for i, a := range x.arcs {
- a.setValue(rewrite(ctx, x.at(ctx, i), stripRewriter))
- arcs[i] = a
+func (x *mergedValues) evalPartial(ctx *context) evaluated {
+ var structs []*structLit
+ for _, v := range x.values {
+ v = v.evalPartial(ctx)
+ o, ok := v.(*structLit)
+ if !ok {
+ v := x.values[0]
+ for _, w := range x.values[1:] {
+ v = mkBin(ctx, w.Pos(), opUnify, v, w)
}
- // TODO: verify that len(x.comprehensions) == 0
- return &structLit{x.baseValue, x.emit, nil, nil, arcs, nil}, false
+ return v.evalPartial(ctx)
+ }
+ o = o.expandFields(ctx)
+ structs = append(structs, o)
+ }
+
+ // Pre-expand the arcs so that we can discard the templates.
+ obj := &structLit{
+ baseValue: structs[0].baseValue,
+ }
+ var arcs arcs
+ for _, v := range structs {
+ for i := 0; i < len(v.arcs); i++ {
+ w := v.iterAt(ctx, i)
+ arcs = append(arcs, w)
}
}
- return eval, true
+ obj.arcs = arcs
+ sort.Stable(obj)
+
+ values := []value{}
+ for _, v := range structs {
+ if v.emit != nil {
+ values = append(values, v.emit)
+ }
+ }
+ switch len(values) {
+ case 0:
+ case 1:
+ obj.emit = values[0]
+ default:
+ obj.emit = &mergedValues{values[0].base(), values}
+ }
+
+ // merge arcs
+ k := 0
+ for i := 0; i < len(arcs); k++ {
+ a := arcs[i]
+ // TODO: consider storing the evaluated value. This is a performance
+ // versus having more information tradeoff. It results in the same
+ // value.
+ values := []value{a.v}
+ for i++; i < len(arcs) && a.feature == arcs[i].feature; i++ {
+ values = append(values, arcs[i].v)
+ a.optional = a.optional && arcs[i].optional
+ var err evaluated
+ a.attrs, err = unifyAttrs(ctx, a.v, a.attrs, arcs[i].attrs)
+ if err != nil {
+ return err
+ }
+ }
+ if len(values) == 1 {
+ arcs[k] = a
+ continue
+ }
+ a.cache = nil
+ a.v = &mergedValues{a.v.base(), values}
+ arcs[k] = a
+ }
+ obj.arcs = arcs[:k]
+ return obj
+}
+
+func (x *mergedValues) kind() kind {
+ k := x.values[0].kind()
+ for _, v := range x.values {
+ k = unifyType(k, v.kind())
+ }
+ return k
+}
+
+func (x *mergedValues) rewrite(ctx *context, fn rewriteFunc) value {
+ vs := make([]value, len(x.values))
+ for i, v := range x.values {
+ vs[i] = rewrite(ctx, v, fn)
+ }
+ return &mergedValues{x.baseValue, vs}
+}
+
+func (x *mergedValues) subsumesImpl(ctx *context, v value, mode subsumeMode) bool {
+ return false
}
diff --git a/cue/strip_test.go b/cue/strip_test.go
deleted file mode 100644
index 897e213..0000000
--- a/cue/strip_test.go
+++ /dev/null
@@ -1,61 +0,0 @@
-// Copyright 2018 The 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 cue
-
-import "testing"
-
-func TestStripTemplates(t *testing.T) {
- testCases := []testCase{{
- desc: "basic",
- in: `
- foo <Name>: { name: Name }
- foo bar: { units: 5 }
- `,
- out: `<0>{foo: <1>{bar: <2>{name: "bar", units: 5}}}`,
- }, {
- desc: "top-level template",
- in: `
- <Name>: { name: Name }
- bar: { units: 5 }
- `,
- out: `<0>{bar: <1>{name: "bar", units: 5}}`,
- }, {
- desc: "with reference",
- in: `
- before: foo.bar
- foo <Name>: { name: Name }
- foo bar: { units: 5 }
- after: foo.bar
- `,
- out: `<0>{before: <1>{name: "bar", units: 5}, foo: <2>{bar: <3>{name: "bar", units: 5}}, after: <4>{name: "bar", units: 5}}`,
- }, {
- desc: "nested",
- in: `
- <X1> foo <X2> bar <X3>: { name: X1+X2+X3 }
- a foo b bar c: { morning: true }
- `,
- out: `<0>{a: <1>{foo: <2>{b: <3>{bar: <4>{c: <5>{name: "abc", morning: true}}}}}}`}}
- for _, tc := range testCases {
- t.Run("", func(t *testing.T) {
- ctx, obj := compileFile(t, tc.in)
-
- v := stripTemplates(ctx, obj)
-
- if got := debugStr(ctx, v); got != tc.out {
- t.Errorf("output differs:\ngot %s\nwant %s", got, tc.out)
- }
- })
- }
-}
