diff --git a/cue/binop.go b/cue/binop.go
index a637f56..682dd89 100644
--- a/cue/binop.go
+++ b/cue/binop.go
@@ -450,7 +450,7 @@
 		return x
 	}
 	arcs := make(arcs, 0, len(x.arcs)+len(y.arcs))
-	obj := &structLit{binSrc(src.Pos(), op, x, other), x.emit, nil, nil, arcs}
+	obj := &structLit{binSrc(src.Pos(), op, x, other), x.emit, nil, nil, arcs, nil}
 	defer ctx.pushForwards(x, obj, y, obj).popForwards()
 
 	tx, ex := evalLambda(ctx, x.template)
diff --git a/cue/copy.go b/cue/copy.go
index 39ef674..880c769 100644
--- a/cue/copy.go
+++ b/cue/copy.go
@@ -31,7 +31,7 @@
 	case *structLit:
 		arcs := make(arcs, len(x.arcs))
 
-		obj := &structLit{x.baseValue, nil, nil, nil, arcs}
+		obj := &structLit{x.baseValue, nil, nil, nil, arcs, nil}
 
 		defer ctx.pushForwards(x, obj).popForwards()
 
diff --git a/cue/resolve_test.go b/cue/resolve_test.go
index f44da59..6c9032c 100644
--- a/cue/resolve_test.go
+++ b/cue/resolve_test.go
@@ -807,7 +807,7 @@
 			}
 			a x: "hey"
 		`,
-		out: `<1>{a: <2>{x: _|_(((<0>.y + "?") & "hey"):constraint violated: _|_("hey":delayed constraint ((<0>.y + "?") & "hey") violated)), y: _|_(cycle detected)}}`,
+		out: `<0>{a: <1>{x: _|_(((<2>.y + "?") & "hey"):constraint violated: _|_(("hey!?" & "hey"):failed to unify: hey!? != hey)), y: "hey!"}}`,
 	}, {
 		desc: "resolved self-reference cycles with disjunctions",
 		in: `
@@ -1087,6 +1087,43 @@
 				`,
 		out: `<0>{res: [<1>{<>: <2>(X: string)-><3>{a: (<3>.c + <3>.b.str), c: "X", b: <4>{str: string}}, x: <5>{a: "XDDDD", c: "X", b: <6>{str: "DDDD"}}}], ` +
 			`t: <7>{<>: <2>(X: string)-><3>{a: (<3>.c + <3>.b.str), c: "X", b: <4>{str: string}}, x: <8>{a: "XDDDD", c: "X", b: <9>{str: "DDDD"}}}}`,
+	}, {
+		// TODO: A nice property for CUE to have would be that evaluation time
+		// is proportional to the number of output nodes (note that this is
+		// not the same as saying that the running time is O(n)).
+		// We should probably disallow shenanigans like the one below. But until
+		// this is allowed, it should at least be correct. At least we are not
+		// making reentrant coding easy.
+		desc: "reentrance",
+		in: `
+		// This indirection is needed to avoid binding references to fib
+		// within fib to the instantiated version.
+		fibRec: {nn: int, out: (fib & {n: nn}).out}
+		fib: {
+			n: int
+
+			out: (fibRec & {nn: n - 2}).out + (fibRec & {nn: n - 1}).out if n >= 2
+			out: n if n < 2
+		}
+		fib2: (fib & {n: 2}).out
+		fib7: (fib & {n: 7}).out
+		fib12: (fib & {n: 12}).out
+		`,
+		out: `<0>{fibRec: <1>{nn: int, out: _|_((<2>.fib & <3>{n: <4>.nn}).out:undefined field "out")}, fib: <5>{n: int}, ` +
+			`fib2: 1, ` +
+			`fib7: 13, ` +
+			`fib12: 144}`,
+	}}
+	rewriteHelper(t, testCases, evalFull)
+}
+
+func TestX(t *testing.T) {
+	t.Skip()
+
+	// Don't remove. For debugging.
+	testCases := []testCase{{
+		in: `
+		`,
 	}}
 	rewriteHelper(t, testCases, evalFull)
 }
diff --git a/cue/rewrite_test.go b/cue/rewrite_test.go
index a6db968..19e8d8b 100644
--- a/cue/rewrite_test.go
+++ b/cue/rewrite_test.go
@@ -74,7 +74,7 @@
 			}
 			x = e.(*structLit)
 		}
-		x.expand(ctx)
+		x = x.expandFields(ctx)
 		arcs := make(arcs, len(x.arcs))
 		for i, a := range x.arcs {
 			v := x.at(ctx, i)
@@ -89,7 +89,7 @@
 			t = v
 		}
 		emit := testResolve(ctx, x.emit, m)
-		obj := &structLit{x.baseValue, emit, t, nil, arcs}
+		obj := &structLit{x.baseValue, emit, t, nil, arcs, nil}
 		return obj
 	case *list:
 		a := make([]value, len(x.a))
diff --git a/cue/strip.go b/cue/strip.go
index 3822ab2..aaf585a 100644
--- a/cue/strip.go
+++ b/cue/strip.go
@@ -30,7 +30,7 @@
 	eval := ctx.manifest(v)
 	switch x := eval.(type) {
 	case *structLit:
-		x.expand(ctx)
+		x = x.expandFields(ctx)
 		if x.template != nil {
 			arcs := make(arcs, len(x.arcs))
 			for i, a := range x.arcs {
@@ -38,7 +38,7 @@
 				arcs[i] = arc{a.feature, v, nil}
 			}
 			// TODO: verify that len(x.comprehensions) == 0
-			return &structLit{x.baseValue, x.emit, nil, nil, arcs}, false
+			return &structLit{x.baseValue, x.emit, nil, nil, arcs, nil}, false
 		}
 	}
 	return eval, true
diff --git a/cue/types.go b/cue/types.go
index 42a3a54..8f669e3 100644
--- a/cue/types.go
+++ b/cue/types.go
@@ -794,7 +794,8 @@
 	}
 	obj := v.eval(ctx).(*structLit)
 
-	obj.expand(ctx) // expand comprehensions
+	// TODO: This is expansion appropriate?
+	obj = obj.expandFields(ctx) // expand comprehensions
 
 	// check if any labels are hidden
 	f := label(0)
@@ -818,6 +819,7 @@
 			obj.template,
 			nil,
 			arcs,
+			nil,
 		}
 
 	}
@@ -829,7 +831,7 @@
 		return structValue{}, err
 	}
 	obj := v.eval(ctx).(*structLit)
-	obj.expand(ctx)
+	obj = obj.expandFields(ctx)
 
 	return structValue{ctx, v.path, obj}, nil
 }
diff --git a/cue/validate.go b/cue/validate.go
index 336f411..7e17216 100644
--- a/cue/validate.go
+++ b/cue/validate.go
@@ -22,7 +22,7 @@
 	}
 	switch x := eval.(type) {
 	case *structLit:
-		x.expand(ctx)
+		x = x.expandFields(ctx)
 		for i := range x.arcs {
 			if err := validate(ctx, x.at(ctx, i)); err != nil {
 				return err
diff --git a/cue/value.go b/cue/value.go
index 3be1282..b458284 100644
--- a/cue/value.go
+++ b/cue/value.go
@@ -563,7 +563,8 @@
 	comprehensions []*fieldComprehension
 
 	// TODO: consider hoisting the template arc to its own value.
-	arcs []arc
+	arcs     []arc
+	expanded *structLit
 }
 
 func newStruct(src source) *structLit {
@@ -580,7 +581,7 @@
 
 // lookup returns the node for the given label f, if present, or nil otherwise.
 func (x *structLit) lookup(ctx *context, f label) (v evaluated, raw value) {
-	x.expand(ctx)
+	x = x.expandFields(ctx)
 	// Lookup is done by selector or index references. Either this is done on
 	// literal nodes or nodes obtained from references. In the later case,
 	// noderef will have ensured that the ancestors were evaluated.
@@ -593,7 +594,7 @@
 }
 
 func (x *structLit) iterAt(ctx *context, i int) (evaluated, value, label) {
-	x.expand(ctx)
+	x = x.expandFields(ctx)
 	if i >= len(x.arcs) {
 		return nil, nil, 0
 	}
@@ -602,7 +603,7 @@
 }
 
 func (x *structLit) at(ctx *context, i int) evaluated {
-	x.expand(ctx)
+	x = x.expandFields(ctx)
 	// if x.emit != nil && isBottom(x.emit) {
 	// 	return x.emit.(evaluated)
 	// }
@@ -642,15 +643,22 @@
 	return x.arcs[i].cache
 }
 
-func (x *structLit) expand(ctx *context) {
+func (x *structLit) expandFields(ctx *context) *structLit {
+	if x.expanded != nil {
+		return x.expanded
+	}
 	if x.comprehensions == nil {
-		return
+		x.expanded = x
+		return x
 	}
 
-	comprehensions := x.comprehensions
-	x.comprehensions = nil
+	x.expanded = x
 
+	comprehensions := x.comprehensions
+	emit := x.emit
+	template := x.template
 	newArcs := []arc{}
+
 	for _, c := range comprehensions {
 		result := c.clauses.yield(ctx, func(k, v evaluated) *bottom {
 			if !k.kind().isAnyOf(stringKind) {
@@ -658,10 +666,10 @@
 			}
 			if c.isTemplate {
 				// TODO: disallow altogether or only when it refers to fields.
-				if x.template == nil {
-					x.template = v
+				if template == nil {
+					template = v
 				} else {
-					x.template = mkBin(ctx, c.Pos(), opUnify, x.template, v)
+					template = mkBin(ctx, c.Pos(), opUnify, template, v)
 				}
 				return nil
 			}
@@ -679,7 +687,7 @@
 		switch {
 		case result == nil:
 		case isBottom(result):
-			x.emit = result
+			emit = result
 		default:
 			panic("should not happen")
 		}
@@ -688,6 +696,11 @@
 	// new arcs may be merged with old ones, but only if the old ones were not
 	// referred to in the evaluation of any of the arcs.
 	// TODO(perf): improve big O
+	arcs := make([]arc, 0, len(x.arcs)+len(newArcs))
+	arcs = append(arcs, x.arcs...)
+	x = &structLit{x.baseValue, emit, template, nil, arcs, nil}
+	x.expanded = x
+
 outer:
 	for _, na := range newArcs {
 		f := na.feature
@@ -705,6 +718,7 @@
 		x.arcs = append(x.arcs, arc{feature: f, v: na.v})
 	}
 	sort.Stable(x)
+	return x
 }
 
 func (x *structLit) applyTemplate(ctx *context, i int, v evaluated) evaluated {
@@ -1130,7 +1144,7 @@
 
 	switch src := source.(type) {
 	case *structLit:
-		src.expand(ctx)
+		src = src.expandFields(ctx)
 		for i, a := range src.arcs {
 			key := &stringLit{
 				x.baseValue,
diff --git a/doc/ref/spec.md b/doc/ref/spec.md
index 2d30c51..7e0691c 100644
--- a/doc/ref/spec.md
+++ b/doc/ref/spec.md
@@ -2073,6 +2073,23 @@
 ```
 
 <!--
+Consider banning any construct that makes CUE not having a linear
+running time expressed in the number of nodes in the output.
+
+This would require restricting constructs like:
+
+(fib&{n:2}).out
+
+fib: {
+        n: int
+
+        out: (fib&{n:n-2}).out + (fib&{n:n-1}).out if n >= 2
+        out: fib({n:n-2}).out + fib({n:n-1}).out if n >= 2
+        out: n if n < 2
+}
+
+-->
+<!--
 ### Unused fields
 
 TODO: rules for detection of unused fields
@@ -2081,7 +2098,6 @@
 -->
 
 
-
 ## Modules, instances, and packages
 
 CUE configurations are constructed combining _instances_.