evalv3: stackoverflow when using the function pattern

[ydubreuil]

What version of CUE are you using (cue version)?

$ cue version
cue version v0.12.0

go version go1.23.5
      -buildmode exe
       -compiler gc
  DefaultGODEBUG asynctimerchan=1,gotypesalias=0,httpservecontentkeepheaders=1,tls3des=1,tlskyber=0,x509keypairleaf=0,x509negativeserial=1
     CGO_ENABLED 1
          GOARCH amd64
            GOOS linux
         GOAMD64 v1
cue.lang.version v0.12.0

Does this issue reproduce with the latest stable release?

Yes

What did you do?

Ran the following test script:

# -- evalv2 --
env CUE_EXPERIMENT=evalv3=0
exec cue eval -e tree main.cue
cmp stdout stdout.golden

# -- evalv3 --
env CUE_EXPERIMENT=evalv3=1
exec cue eval -e tree main.cue
cmp stdout stdout.golden

-- main.cue --
#Workspace: {
	workspaceA?: {}
	workspaceB?: {}
}

#AccountConfig: {
	workspaces: #Workspace
	siblings?: [...string]
}

#AccountConfigSub1: {
	#AccountConfig
	workspaces: "workspaceA": {}
}

#AccountConfigSub2: {
	#AccountConfig
	workspaces: "workspaceB": {}
}

tree: env1: {
	"region1": {
		"env1-r1-account-sub1": #AccountConfigSub1
		"env1-r1-account-sub2-1": #AccountConfigSub2
	}
}

#lookupSiblings: {
	envtree: {...}
	out: [
		for region, v in envtree
		for account, config in v
		if config.workspaces."workspaceB" != _|_ { account },
	]
}

tree: ENVTREE=env1: [_]: [_]: #AccountConfig & {
	siblings: (#lookupSiblings & {envtree: ENVTREE}).out
}
-- stdout.golden --
env1: {
    region1: {
        "env1-r1-account-sub1": {
            workspaces: {
                workspaceA: {}
            }
            siblings: ["env1-r1-account-sub2-1"]
        }
        "env1-r1-account-sub2-1": {
            workspaces: {
                workspaceB: {}
            }
            siblings: ["env1-r1-account-sub2-1"]
        }
    }
}

What did you expect to see?

The same result as the one generated by the old evaluator:

Passing test.

What did you see instead?

A panic log from the Go runtime:

runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc07eb80320 stack=[0xc07eb80000, 0xc09eb80000]
fatal error: stack overflow

runtime stack:
runtime.throw({0x10388d0?, 0x7d9e78ff8d40?})
        /usr/lib/go/src/runtime/panic.go:1067 +0x48 fp=0x7d9e78ff8d00 sp=0x7d9e78ff8cd0 pc=0x4769e8
runtime.newstack()
        /usr/lib/go/src/runtime/stack.go:1117 +0x5bd fp=0x7d9e78ff8e40 sp=0x7d9e78ff8d00 pc=0x458f3d
runtime.morestack()
        /usr/lib/go/src/runtime/asm_amd64.s:621 +0x7a fp=0x7d9e78ff8e48 sp=0x7d9e78ff8e40 pc=0x47d5da

goroutine 1 gp=0xc0000061c0 m=10 mp=0xc000680008 [running]:
runtime.growslice(0x0?, 0x1?, 0x0?, 0x1?, 0xfb39a0?)
        /usr/lib/go/src/runtime/slice.go:177 +0x765 fp=0xc07eb80330 sp=0xc07eb80328 pc=0x479465
cuelang.org/go/internal/core/adt.(*Vertex).addConjunctUnchecked(0xc0f1ffda40, {0x0, {0x11e6e60, 0xc0f202a588}, {0x0, 0xc0f2030900, 0x0, 0x0, 0x0, 0x0, ...}})
        /home/ydubreuil/go/pkg/mod/cuelang.org/[email protected]/internal/core/adt/composite.go:1409 +0x4e fp=0xc07eb803b8 sp=0xc07eb80330 pc=0x6e856e
cuelang.org/go/internal/core/adt.(*Vertex).assignConjunct(0x4174cb?, 0x7d9e5244d048?, 0xc0f2030900, {0x0, {0x11e6e60, 0xc0f202a588}, {0x0, 0xc0f2030900, 0x0, 0x0, ...}}, ...)
        /home/ydubreuil/go/pkg/mod/cuelang.org/[email protected]/internal/core/adt/fields.go:404 +0x129 fp=0xc07eb804c0 sp=0xc07eb803b8 pc=0x72a009
cuelang.org/go/internal/core/adt.(*closeContext).getKeyedCC(0xc0f2030360, 0xc0023c0960, 0xc0f2030900, {0x8?, 0x0?, 0x68?, 0xc0f2029380?}, 0x0, 0x1)
        /home/ydubreuil/go/pkg/mod/cuelang.org/[email protected]/internal/core/adt/fields.go:427 +0x239 fp=0xc07eb805b0 sp=0xc07eb804c0 pc=0x72a3d9
cuelang.org/go/internal/core/adt.(*closeContext).assignConjunct(0x9?, 0x30?, 0x20?, {0x0, {0x11e6e60, 0xc0f202a570}, {0x0, 0x0, 0x0, 0x0, ...}}, ...)
        /home/ydubreuil/go/pkg/mod/cuelang.org/[email protected]/internal/core/adt/fields.go:478 +0x5a fp=0xc07eb806d0 sp=0xc07eb805b0 pc=0x72a6ba
cuelang.org/go/internal/core/adt.(*closeContext).getKeyedCC(0xc0f20306c0, 0xc0023c0960, 0xc0f2030900, {0x48?, 0x8?, 0xb8?, 0xc0f2029380?}, 0x0, 0x1)
        /home/ydubreuil/go/pkg/mod/cuelang.org/[email protected]/internal/core/adt/fields.go:427 +0x239 fp=0xc07eb807c0 sp=0xc07eb806d0 pc=0x72a3d9
cuelang.org/go/internal/core/adt.(*closeContext).assignConjunct(0x8?, 0x412465?, 0x120?, {0xc0f2032160, {0x11e6e88, 0xc000c17ce0}, {0x0, 0xc0f20306c0, 0x0, 0x0, ...}}, ...)
        /home/ydubreuil/go/pkg/mod/cuelang.org/[email protected]/internal/core/adt/fields.go:478 +0x5a fp=0xc07eb808e0 sp=0xc07eb807c0 pc=0x72a6ba
cuelang.org/go/internal/core/adt.(*closeContext).insertConjunct(0x100e360?, 0xc0023c0960, 0xc0f2030900, {0xc0f2032160, {0x11e6e88, 0xc000c17ce0}, {0x0, 0xc0f20306c0, 0x0, 0x0, ...}}, ...)
        /home/ydubreuil/go/pkg/mod/cuelang.org/[email protected]/internal/core/adt/fields.go:671 +0x65 fp=0xc07eb80988 sp=0xc07eb808e0 pc=0x72b245
cuelang.org/go/internal/core/adt.(*nodeContext).insertArcCC(0xc0f202ec08, 0x621, 0x0, {0xc0f2032160, {0x11e6e88, 0xc000c17ce0}, {0x0, 0xc0f20306c0, 0x0, 0x0, ...}}, ...)
        /home/ydubreuil/go/pkg/mod/cuelang.org/[email protected]/internal/core/adt/fields.go:755 +0x205 fp=0xc07eb80ad8 sp=0xc07eb80988 pc=0x72b6c5
cuelang.org/go/internal/core/adt.(*nodeContext).insertArc(...)
        /home/ydubreuil/go/pkg/mod/cuelang.org/[email protected]/internal/core/adt/fields.go:714
...

If instead of using the function pattern the code inside #lookupSiblings.out is put at the call site, then there's no stack overflow panic and the new evaluator correctly evaluates tree.

cc @gotwarlost

[mvdan]

Reduced a bit:

# With the old evaluator.
env CUE_EXPERIMENT=evalv3=0
exec cue export input.cue

# With the new evaluator.
env CUE_EXPERIMENT=evalv3=1
exec cue export input.cue

-- input.cue --
package p

#lookup: {
	input: {...}
	output: [
		for _, v in input
		if v.show != _|_ { v },
	]
}

root: {
	self: show: true
	others: (#lookup & {input: root}).output
}

As of 0e42b0b:

# With the old evaluator. (0.010s)
> env CUE_EXPERIMENT=evalv3=0
> exec cue export input.cue
[stdout]
{
    "root": {
        "self": {
            "show": true
        },
        "others": [
            {
                "show": true
            }
        ]
    }
}
# With the new evaluator. (6.962s)
> env CUE_EXPERIMENT=evalv3=1
> exec cue export input.cue
[stderr]
runtime: goroutine stack exceeds 1000000000-byte limit

[myitcv]

Two further observations regarding the reduction in #3731 (comment):

• Before https://cuelang.org/cl/1206384, evalv3 reported this as a structural cycle
• The problem persists even if we set CUE_DEBUG=openinline=0

[mpvl]

This turns out to be quite an interesting one. The problem can be reduced to something not using the function pattern:

X: {
    input: a: _
    output: input.a
}
root: {
    a: _a.output
    _a: X & {input: root}
}

[myitcv]

Confirming that as of c479844 (which is now in tip) this still passes as expected, but also that we do not need to set CUE_DEBUG=openinline=0 in order for it to pass. The test passes with:

• CUE_DEBUG unset
• CUE_DEBUG=openinline=0
• CUE_DEBUG=openinline=1