evaluator: bounded recursion regression

[caleblloyd]

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

v0.5.0-alpha.1.0.20221101144719-b3bcc7aaf3d0 built from commit b3bcc7a

Does this issue reproduce with the latest release?

Reproduces starting in v0.5.0-alpha.1

Works as expected in v0.4.3

What did you do?

Following example at https://cuetorials.com/deep-dives/recursion/#bounded-recursion

Package r

recurse.cue:

package r

import "list"

#RecurseN: {
	// this is the bound on our recursion
	#maxiter: uint | *4

	// This is the function list element
	// we generate this to simulate recursion
	#funcFactory: {
		#next: _
		#func: _
	}

	// this is our "recursion unrolling"
	for k, v in list.Range(0, #maxiter, 1) {
		// this is where we build up our indexed functions and the references between them
		#funcs: "\(k)": (#funcFactory & {#next: #funcs["\(k+1)"]}).#func
	}

	// our final value needs to be null
	#funcs: "\(#maxiter)": null

	// we embed the head of the list so that the values
	// we write this into can be used like other CUE "functions"
	#funcs["0"]
}

depth.cue:

package r

import "list"

#DepthF: {
	#next: _
	#func: {
		#in:    _
		#basic: int | number | string | bytes | null
		out: {
			// if we have a basic type, we are at a leaf, depth is 1
			if (#in & #basic) != _|_ {1}

			// if we are not a basic type, then we are 1 + the max of children
			if (#in & #basic) == _|_ {
				// this is our "recursion" for each child
				let depths = [ for k, v in #in {(#next & {#in: v}).out}]
				list.Max(depths) + 1
			}
		}
	}
}

#Depth: #RecurseN & {#maxiter: 11, #funcFactory: #DepthF}

tree: {
	a: {
		foo: "bar"
		a: b: c: "d"
	}
	cow: "moo"
}

d: #Depth & {#in: tree}

Then run the command cue export --out cue ./r

What did you expect to see?

tree: {
        a: {
                foo: "bar"
                a: b: c: "d"
        }
        cow: "moo"
}
d: out: 5

What did you see instead?

d: undefined field: #maxiter:
    ./r/recurse.cue:17:28
d: cannot add field #funcs: was already used:
    ./r/recurse.cue:23:2

[myitcv]

Thanks for raising this, @caleblloyd. Confirmed and bisected to 748a685.

What did you do?

go mod tidy
go run cuelang.org/go/cmd/cue export
cmp stdout stdout.golden

-- go.mod --
module mod.com

go 1.18

require cuelang.org/go v0.4.4-0.20220622094641-748a68589747

-- deps.go --
//go:build tools
// +build tools

package tools

import (
	_ "cuelang.org/go/cmd/cue"
)
-- depth.cue --
package r

import "list"

#DepthF: {
	#next: _
	#func: {
		#in:    _
		#basic: int | number | string | bytes | null
		out: {
			// if we have a basic type, we are at a leaf, depth is 1
			if (#in & #basic) != _|_ {1}

			// if we are not a basic type, then we are 1 + the max of children
			if (#in & #basic) == _|_ {
				// this is our "recursion" for each child
				let depths = [ for k, v in #in {(#next & {#in: v}).out}]
				list.Max(depths) + 1
			}
		}
	}
}

#Depth: #RecurseN & {#maxiter: 11, #funcFactory: #DepthF}

tree: {
	a: {
		foo: "bar"
		a: b: c: "d"
	}
	cow: "moo"
}

d: #Depth & {#in: tree}
-- recurse.cue --
package r

import "list"

#RecurseN: {
	// this is the bound on our recursion
	#maxiter: uint | *4

	// This is the function list element
	// we generate this to simulate recursion
	#funcFactory: {
		#next: _
		#func: _
	}

	// this is our "recursion unrolling"
	for k, v in list.Range(0, #maxiter, 1) {
		// this is where we build up our indexed functions and the references between them
		#funcs: "\(k)": (#funcFactory & {#next: #funcs["\(k+1)"]}).#func
	}

	// our final value needs to be null
	#funcs: "\(#maxiter)": null

	// we embed the head of the list so that the values
	// we write this into can be used like other CUE "functions"
	#funcs["0"]
}
-- stdout.golden --
{
    "tree": {
        "a": {
            "foo": "bar",
            "a": {
                "b": {
                    "c": "d"
                }
            }
        },
        "cow": "moo"
    },
    "d": {
        "out": 5
    }
}

What did you expect to see?

Passing test.

What did you see instead?

> go run cuelang.org/go/cmd/cue export
[stderr]
d: undefined field: #maxiter:
    ./recurse.cue:17:28
d: cannot add field #funcs: was already used:
    ./recurse.cue:23:2
exit status 1

[mpvl]

The underlying problem is a spurious structural cycle. The below is a simplification of what triggers it.

#maxiter: 2

// Trigger lookup of a.x0 before the "regular" evaluation of a.
x: a.x0

a: {
	for k, _ in [0, 1] {
		"x\(k)": (#DepthF & {#in: a["x\(k+1)"]}).#out
	}
}

a: x2: null // no cycle with {}!!!

#DepthF: {
	#in: _
	#out: {}
}

[mpvl]

Another issue that is exposed by this once the cycle issue is fixed:

X: 1

for v in [0, X] + [] {
	x: "x\(v)": {}
}

x: _

x.x0

The issue is that X's evaluation is triggered by the evaluation of x.x0 before X has been added to the root. Normally these cases are handled fine, but the addition of + [] prevents its correct handling.