evaluator: infinite loop with recursive and

[cuematthew]

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

commit 8145bdd3b238d888870ec43955137121eba07e89

What did you do?

exec cue export list.cue

-- list.cue --
_self: {
    x: [...and(x)]
}
_self
x: [1]

What did you expect to see?

Structural cycle error. Probably. You could argue it should be smart enough to cope.

What did you see instead?

With eval2, the stack explodes with a crash. With eval3 it infinite loops.

Curiously, this can't be simplified further. The following is simpler:

x: [...and(x)]
x: [1]

This simpler version causes a stack explosion on eval2, but on eval3, it doesn't error, and does return the result x: [1]

[mvdan]

marking as "needs fix" because endless evaluation or panics are definitely bugs.

[zolero]

Is there any work around for this right now? I'm also stuck here. Maybe some sort of hacky workaround?

[cuematthew]

@zolero There's even a non-hacky workaround! I found this issue because I was experimenting with different ways of ensuring all values within a list are "the same". The problem is that "the same" can mean a few different things. I assume you're attempting something similar?

Myself and @rogpeppe came up with a few different approaches:

tests: [_]: {
    input!:  _
    results: _strategies
    results: [_]: list: input
}

tests: emptyList: input: []
tests: allSame: input: [7, 7, 7]
tests: allConstraints: input: [<3, <2, <6]

_strategies: t1: {
    #listOfSameInt: self={
        if len(self) > 0 {
            [... self[0] & int]
        }
    }
    list: #listOfSameInt
}

_strategies: t2: {
    _self: {
        list: [...]

        listCheck: {for e in list {e}}
    }

    _self
}

_strategies: t3: {
    _self: {
        list: [...{for e in list {e}}]
    }
    _self
}

If you load it into the playground, eg https://cuelang.org/play/?id=3MRAXM5l5MF#w=function&i=cue&f=eval&o=cue you'll see some interesting differences in the result when it comes to a list of constraints. I think the behaviour there is all correct, but it's worth thinking about, depending on what you're trying to do.

I'm pretty sure x: [...and(x)] should fail with a structural-cycle-error. This is because the x inside and(x) refers not to the elements of the list, but to the whole list. Consequently, it's stating that all the elements of the list must unify with the list itself, which probably implies a list that infinitely nests itself, and so it's a structural cycle error. EDIT: Having spent more time thinking about and, I no longer think this explanation is at all correct.

[zolero]

First, thanks for your detailed explanation. Well right now I'm a little too new to cue language but I'm 'already' diving deep into some graph relational matter... which is validating schema.org json-ld schema's. I've managed to generate quiet a big cue schema out of it. Which is pretty damn impressive...

Schema Org - Specification - schema-org-spec.cue

Now I would like to transform the schema spec into a validator for JSON-LD data but I think it just won't finish executing the validation because of those loops and probably because of it's size as well.

NewsArticle: news-article.json

cue vet --verbose .schema-org-spec.cue .\news-article.json -d '#NewsArticle'

There are not too many good validators yet for this schema even though it's a widely used one.

[cuematthew]

I think this discussion runs the risk of going some way beyond the scope of this ticket. There are both slack and discord servers for CUE which are linked from the top right of https://cuelang.org. It's probably a good idea to look for help and advice on those forums, if you've not already.

[cuematthew]

Just as one final note on this, I'm now quite convinced this should not be an error (can you tell I've only been here a few weeks?!). Notably, this works fine:

_self: {
    x: [...y]
    y: and(x)
}