evaluator: structural cycle reported where there isn't one

[myitcv]

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

$ cue version
cue version v0.0.0-20230322203908-ee55e9a263da

go version go1.20
      -buildmode exe
       -compiler gc
     CGO_ENABLED 1
          GOARCH arm64
            GOOS linux
             vcs git
    vcs.revision ee55e9a263dadda6b5aa65e93bc455c4426def70
        vcs.time 2023-03-22T20:39:08Z
    vcs.modified true

Does this issue reproduce with the latest release?

Yes it does with ee55e9a263da

What did you do?

# 2 substitutions
exec cue export x.cue 2_subs.cue
cmp stdout stdout.golden

# 3 substitutions
exec cue export x.cue 3_subs.cue
cmp stdout stdout.golden

-- x.cue --
package x

import (
    "list"
    "strings"
)

#s: {#_1: string, #_2: string, #_3: string, strings.Replace(#_1, #_2, #_3, -1)}

#sub: {
    #a: string

    // We can't use X=[#a, ...] yet because that is still disallowed
    _#X: [#a, for i in list.Range(0, len(#subs), 1) {#subs[i] & {#_1: _#X[i], _}}]

    // Embedding would not be necessary if the X=[] form was allowed
    _#X[len(_#X)-1]
}

res: #sub & {#a: "aaa", _}
-- 2_subs.cue --
package x

// subs is a series of string substitutions we want to apply
#subs: [
    #s & {#_2: "a", #_3: "b", _},
    #s & {#_2: "c", #_3: "d", _},
]
-- 3_subs.cue --
package x

// subs is a series of string substitutions we want to apply
#subs: [
    #s & {#_2: "a", #_3: "b", _},
    #s & {#_2: "c", #_3: "d", _},
    #s & {#_2: "e", #_3: "f", _},
]
-- stdout.golden --
{
    "res": "bbb"
}

What did you expect to see?

Passing test.

What did you see instead?

$ ts repro.txtar
# 2 substitutions (0.012s)
# 3 substitutions (0.012s)
> exec cue export x.cue 3_subs.cue
[stderr]
#sub.#_1.#_1.#_1: structural cycle:
    ./x.cue:8:61
#sub._#X.3.#_1.#_1.#_1: structural cycle:
    ./x.cue:8:61
[exit status 1]
FAIL: /tmp/testscript4061071106/repro.txtar/script.txtar:6: unexpected command failure

i.e. using three substitutions instead of two triggers a structural cycle, even though (in this situation) the additional substitution is identical to the previous two substitutions.

[mpvl]

Is this a regression? If so, do you have a bisection?

[mpvl]

Here is a simplified reproducer:

res: {
    #X[3] // Must be at least 3 to cause structural cycle.

    // expanding comprehension eliminates cycle.
    #X: ["X", for i, _ in #subs {#s, #str: #X[i]}]
}

#s: {#str: string, #str + "a"}
#subs: [0, 1, 2]

The embedding (#X[3]) is needed to cause a back-to-front evaluation chain which visits the same nodes in a nested fashion. Expanding the comprehension eliminates the structural cycle. This tells me that the issue probably is that comprehension elements are not treated as a "new" node and thus do not disable cycle detection. Comprehension elements should behave exactly the same as if their expressions were expanded, of course.

[myitcv]

Apologies, I don't know why I didn't bisect this off the bat.

Just updated my repro above because in bisecting I realised the test doesn't pass when it should because the 3rd substitution causes an additional replace.

With the change my script bisects to 887f56497cbc2178e9cb1e9be78d8abae78ea0cd.

For completeness' sake, your repro bisects to the same commit.

[myitcv]

Updated the original description to remove my environment-specific setup.

And to confirm this is a regression since v0.4.3, not since v0.5.0.

[mvdan]

Since we are very close to the final v0.6.0 release (https://github.com/cue-lang/cue/milestone/9) and this issue is neither a regression from v0.5.0 nor a critical bug like a panic, I'm pushing it back slightly to v0.7, which we'll start working on as soon as v0.6.0 is out.