evaluator: cyclic data structure fails to evaluate if not top level

[myitcv]

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

$ cue version
cue version +c942d0af linux/arm64

Does this issue reproduce with the latest release?

Yes

What did you do?

Distilled from https://github.com/cue-lang/cue/discussions/1676

The example below presents three cases that should all evaluate to the same result.

1. where a cyclic data structure is defined at the top level and referenced from a field within a struct that is then used as part of a unification with the data
2. where a cyclic data structure defined as part of a non-top-level field is referenced directly as part of a unification with the data
3. where a struct containing a cyclic data structure is unified with the data

# case 1
exec cue eval -e o x.cue o1.cue
cmp stdout stdout.golden

# case 2
exec cue eval -e o x.cue o2.cue
cmp stdout stdout.golden

# case 3
exec cue eval -e o x.cue o3.cue
cmp stdout stdout.golden

-- x.cue --
package x

#Secret: {
	$secret: id: string
}

secrets: #Secret | {[string]: secrets}

src1: output: secrets
src2: output: #Secret | {[string]: output}

out: {
	FOO: $secret: id: "100"
	ONE: TWO: THREE: $secret: id: "123"
}
-- o1.cue --
package x

o: src1 & {
	output: out
}
-- o2.cue --
package x

o: output: src2.output & out
-- o3.cue --
package x

o: src2 & {
	output: out
}
-- stdout.golden --
output: {
    FOO: {
        $secret: {
            id: "100"
        }
    }
    ONE: {
        TWO: {
            THREE: {
                $secret: {
                    id: "123"
                }
            }
        }
    }
}

What did you expect to see?

A passing test.

What did you see instead?

# case 1 (0.016s)
# case 2 (0.015s)
# case 3 (0.014s)
> exec cue eval -e o x.cue o3.cue
[stderr]
o.output: 4 errors in empty disjunction:
o.output: field not allowed: FOO:
    ./o3.cue:3:4
    ./o3.cue:4:10
    ./x.cue:3:10
    ./x.cue:10:15
    ./x.cue:13:2
o.output.FOO: 2 errors in empty disjunction:
o.output.FOO: field not allowed: FOO:
    ./o3.cue:3:4
    ./o3.cue:4:10
    ./x.cue:3:10
    ./x.cue:10:15
    ./x.cue:10:36
    ./x.cue:13:2
    ./x.cue:13:7
o.output.FOO.FOO: structural cycle
[exit status 1]
FAIL: /tmp/testscript218994319/repro.txt/script.txt:10: unexpected command failure

i.e. case 3 fails to evaluate with structural cycle errors.

[myitcv]

cc @helderco

[mpvl]

I can confirm this is fixed in the cycle/comprehension rework I have locally in my client.

[mpvl]

Almost done with the cycle rework. And now I noticed it is not fixed. Not sure why it was working before, but upon further investigation, this is actually working as intended! (My apologies for the big twist!)

It is quite subtle, but understandable. Consider

src2: output: #Secret | {[string]: output}

vs

src2: output: #Secret | {[string]: secrets}   // s/output}/secrets}/

The second one would also work.

The big difference between the latter case, case o1 and o2 on the one hand and o3 on the other hand, is that in the former cases the reference of the pattern constraint refers to a value that is not unified into o. This means that each time when this reference is dereferenced, it gets a fresh copy of secrets.

In the failing case, however, the reference to secrets is replaced with output, and o is unified with the entirety of src2, which includes the output field itself. In this case, output will reference the struct in the resulting field, not the original field. This means it will also contain the fields that are unified in at o. As there are two fields which both reference output at different levels, this will result in a continuous invocation of output, which will lead to a cycle.

It essentially then results in something like:

a: [string]: b: a
a: c: b: {}

which results in a cycle as whenever a is referenced it also inserts a field that triggers the pattern on a new level.

Note that the difference here is akin to having a list:

Foo: #List: {
    Next:   #List | null
    Value: _
}
list: Foo.#List & {Value: 3, Next: Value: 1}

which works, versus

Foo: #List: {
    Next:   #List | null
    Value: _
}
list: Foo & {#List: {Value: 3, Next: Value: 1}}

which doesn't work as it is essentially redefining #List to have a fixed value of 3, while simultaneously demanding that the next element be 1.

Strictly speaking, it is not even necessary to include output to create cycles with pattern constraints. Consider the following example:

y: [string]: b: y
x: y
x: c: y

This result in a structural cycle at: x.c.b.b.b.b. As the two fields x each reference the y at different depth, the field b of the pattern constraint will trigger a match of the constraint alternating between the two conjuncts of x. That is not what's going on with secrets, but it illustrates how the use of pattern constraints may cause cycles if one is not careful.

As this is a simplified reproducer, I don't know enough of the context to recommend how this could be avoided.

[helderco]

Thanks @mpvl, the intent is to type a structure like this (i.e., variable key depth, ending in a $secret):

{
    FOO: {
        $secret: {}
    }
    ONE: {
        TWO: {
            THREE: {
                $secret: {}
            }
        }
    }
}

Is it possible?

[helderco]

I attempted this, but isn't working in practice:

exec cue eval x.cue

-- x.cue --
src: {
	#Secret: {
		$secret: _id: string
	}

	a: {
		output: _#out
		_#out: #Secret | {[!~"\\$secret"]: _#out}
	}

}

out: {
	FOO: $secret: _id: "100"
	ONE: TWO: THREE: $secret: _id: "123"
}

final: src & {
	a: output: out
}

From https://github.com/cue-lang/cue/discussions/1676#discussioncomment-2656886

[eonpatapon]

Maybe what doesn't works for you in practice is when you have separate packages ? Ie: #Secret comes from a separate package.

Because in this case hidden fields will not unify.

For example:

a/a.cue

package a

#A: {
	_x: 1
	a:  string
}

x.cue

package x

import (
	"example.com/x/a"
)

x: a.#A & {
	a:  "foo"
	_x: 24
}

 cue eval
x: {
    a: "foo"
}

As you can see _x is unified only in the scope of the package. If in the same package there would be an error as 1 cannot be unified with 24.

Sorry if this is irrelevant as I don't know exactly how dagger manages this _id field.

[helderco]

@eonpatapon We're filling with cue.Hid():

var secretIDPath = cue.MakePath(
	cue.Str("$dagger"),
	cue.Str("secret"),
	cue.Hid("_id", pkg.DaggerPackage),
)
// ...
v.FillPath(secretIDPath, s.id)

https://github.com/dagger/dagger/blob/b4f934a6ea2d9787fb66bf2cbfac8d4f9ded4141/plancontext/secret.go#L39

Wouldn't this be a better representation?

exec cue eval x.cue

-- cue.mod/module.cue --
module: "example.com"
-- core/types.cue --
package core

#Secret: {
	$secret: _id: string
}

out: {
	FOO: $secret: _id: "100"
	ONE: TWO: THREE: $secret: _id: "123"
}
-- x.cue --
package x

import "example.com/core"

src: {
	a: {
		output: _#out
		_#out: core.#Secret | {[!~"\\$secret"]: _#out}
	}

}

final: src & {
	a: output: core.out
}

Output:

...
final: {
    a: {
        output: {
            FOO: {
                $secret: {}
            }
            ONE: {
                TWO: {
                    THREE: {
                        $secret: {}
                    }
                }
            }
        }
    }
}

[jlongtine]

I just tried @helderco's latest example with 537831: internal/core/adt: reimplementation of cycle algorithm | https://review.gerrithub.io/c/cue-lang/cue/+/537831

And, it works! So, this CL should hopefully solve the issues we're encountering with this.

[helderco]

My example works even in current version, as you can see in the output, but just in CUE. When I say it doesn't work in "practice" I mean in Dagger.

[myitcv]

@jlongtine - per our conversation on Friday, please can we see a version of what you and @helderco are doing in Dagger here? We're missing too much context in the cut down repro to help beyond @mpvl's explanation in https://github.com/cue-lang/cue/issues/1680#issuecomment-1117943928. That comment effectively amounts to "this is working as intended" - with more context I think we will be better placed to collectively identify the right solution.

[helderco]

Sorry @myitcv, I should have been clearer, there's actually two errors we're dealing with here.

This is how this progressed:

1. Structural cycle cause by output: #Secret | {[string]: output}
2. Fixed cycle with _#out: dagger.#Secret | {[string]: _#out} and output: _#out but shows an unresolved disjunction
3. Tried to fix with _#out: dagger.#Secret | {[!~"\\$dagger"]: _#out}... appears to resolve the disjunction (when debugging the value) but still has an attached "unresolved disjunction" error

The first one only happened when using a FillPath. The latter two it's just the opposite, only work with FillPath.

So I think we can close this issue which is about the first error, and continue with the unresolved disjunction in:

• https://github.com/cue-lang/cue/discussions/1676

I'll add more details there.