internal/eval: another performance issue with recursive definitions

[cueckoo]

Originally opened by @philippseith in cuelang/cue#1044

With cue version 0.4.0 windows/amd64, the following combination of template, list, and default value causes cue vet/eval to hang causing high cpu load:

A: #TypedObject & {
	childs: {
    	B : #TypedObject & {
    		//type: "int"
    	}
    }
}

#TypedObject : {
	type:    #Type | *"string"
	childs: [_] : #TypedObject
}

#Type: #BasicType | #ComplexType | [#BasicType] | [#ComplexType]
#ComplexType: [_] : #Type

 #BasicType: "int" | "uint" | "string"

It successfully runs either when the A.childs.B.type is set explicitly or #Type is defined without List support, eg. as #Type: #BasicType | #ComplexType.

The same definition did work with cue 0.2.2

Strangely, relying on the default value for A.type does not cause cue to hang.

[felixhuettner]

I have a similar issue with the following snipped

#m1: {
	#f1: [...]
	f2: #f1
}

#m2: {
	#m1
	#f1: *[] | [...]
}

#s1: #m1
#s2: #m1
#s3: #m2
#s4: #m2
#s5: #m2


x: {
	#s1
	#s2
	#s3
	#s4
	#s5
}

Interstingly: at least 3 of s1 to s5 need to refer m2 for the issue to trigger

[verdverm]

This looks like a really nice and minimal reproducer for #758 !

Though could it also be related to one of the other roadmap/performance labelled issues? (😆e9)

[myitcv]

@philippseith thanks for raising this, and for the repro (as well as @felixhuettner for your repro). All of these are almost certainly related to #803 which will be addressed with upcoming changes to the evaluation engine to support structure sharing (#804). I will leave this open however in case it turns out to be an edge case of any sort.

[njhartwell]

I ran into something that I suspect is the same or related:

#Config & {
	output: {
	  processors: try: [...#Processor]
	}
}

#Config: {
	output?: #Output
}

#AllOutputs: { }

#Output: or([ for name, config in #AllOutputs {
	(name): config
}])

#Output: #Output & {
	processors?: [...#Processor]
}

#AllProcessors: {
	try: [...#Processor]
}

#Processor: or([ for name, config in #AllProcessors {
	(name): config
}])

#Processor: #Processor & {
	processors?: [...#Processor]
}

https://cuelang.org/play/?id=jhu3SJm2Q_k#cue@export@cue

Running cue eval against that (or in the playground) hangs indefinitely and pegs my CPU.

[felixhuettner]

My snippet from above no longer causes issues in v0.4.3

@njhartwell yours still hangs for me though

[mvdan]

See my reply in #803 (comment) relating to the new evaluator :)