search

cuelang / cue

CUE has moved to https://github.com/cue-lang/cue
https://cuelang.org
Apache License 2.0
3.09k stars 171 forks source link

cue: unifying schema with package instance value that embeds that same schema does not terminate #565

Closed myitcv closed 3 years ago

myitcv commented 3 years ago

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

$ cue version
v0.3.0-alpha4.0.20201022063748-aee9955c790b

Does this issue reproduce with the latest release?

Yes

What did you do?

cd $(mktemp -d)
cat <<EOD | txtar-x
-- cue.mod/pkg/github.com/play-with-go/preguide/preguide.cue --
package preguide

import (
    "list"
    "path"
    "regexp"
)

#StepType: int

#StepTypeCommand:     #StepType & 1
#StepTypeCommandFile: #StepType & 2
#StepTypeUpload:      #StepType & 3
#StepTypeUploadFile:  #StepType & 4

#Guide: {

    #Step: (#Command | #CommandFile | #Upload | #UploadFile ) & {
        Name:     string
        StepType: #StepType
        Terminal: string
    }

    #stepCommon: {
        Name:     string
        StepType: #StepType
        Terminal: string
    }

    #uploadCommon: {
        Target: string

        Language: *regexp.FindSubmatch("^.(.*)", path.Ext(Target))[1] | string

        Renderer: #Renderer
    }

    #Command: {
        #stepCommon
        StepType: #StepTypeCommand
        Source:   string
    }

    #CommandFile: {
        #stepCommon
        StepType: #StepTypeCommandFile
        Path:     string
    }

    #Upload: {
        #stepCommon
        #uploadCommon
        StepType: #StepTypeUpload
        Source:   string
    }

    #UploadFile: {
        #stepCommon
        #uploadCommon
        StepType: #StepTypeUploadFile
        Path:     string
    }

    Networks: [...string]

    Env: [...string]

    Presteps: [...#Prestep]

    Delims: *["{{", "}}"] | [string, string]

    Steps: [string]: [#Language]: #Step

    Steps: [name=string]: [#Language]: {
        // TODO: remove post upgrade to latest CUE? Because at that point
        // the defaulting in #TerminalName will work
        Terminal: *#TerminalNames[0] | string

        Name: name
    }

    Scenarios: [string]: #Scenario
    Scenarios: [name=string]: {
        Name: name
    }

    _#ScenarioName: or([ for name, _ in Scenarios {name}])

    for scenario, _ in Scenarios for terminal, _ in Terminals {
        Terminals: "\(terminal)": Scenarios: "\(scenario)": #TerminalScenario
    }

    #TerminalNames: [ for k, _ in Terminals {k}]
    #ok: true & and([ for s in Steps for l in s {list.Contains(#TerminalNames, l.Terminal)}])

    Terminals: [string]: #Terminal

    Terminals: [name=string]: {
        Name: name
    }

    Defs: [string]: _
}

#Terminal: {
    Name:        string
    Description: string
    Scenarios: [string]: #TerminalScenario
}

#TerminalScenario: {
    Image: string
}

#Scenario: {
    Name:        string
    Description: string
}

#Prestep: {
    Package: string
    Path:    *"/" | string
    Args?:   _
}

#Language: "ab" | "aa" | "af" | "ak" | "sq" | "am" | "ar" | "an" | "hy" | "as" | "av" | "ae" | "ay" | "az" | "bm" | "ba" | "eu" | "be" | "bn" |
    "bh" | "bi" | "bs" | "br" | "bg" | "my" | "ca" | "ch" | "ce" | "ny" | "zy" | "cv" | "kw" | "co" | "cr" | "hr" | "cs" | "da" | "dv" |
    "nl" | "dz" | "en" | "eo" | "et" | "ee" | "fo" | "fj" | "fi" | "fr" | "ff" | "gl" | "ka" | "de" | "el" | "gn" | "gu" | "ht" | "ha" |
    "he" | "hz" | "hi" | "ho" | "hu" | "ia" | "id" | "ie" | "ga" | "ig" | "ik" | "io" | "is" | "it" | "iu" | "ja" | "jv" | "kl" | "kn" |
    "kr" | "ks" | "kk" | "km" | "ki" | "rw" | "ky" | "kv" | "kg" | "ko" | "ku" | "kj" | "la" | "lb" | "lg" | "li" | "ln" | "lo" | "lt" |
    "lu" | "lv" | "gv" | "mk" | "mg" | "ms" | "ml" | "mt" | "mi" | "mr" | "mh" | "mn" | "na" | "nv" | "nd" | "ne" | "ng" | "nb" | "nn" |
    "no" | "ii" | "nr" | "oc" | "oj" | "cu" | "om" | "or" | "os" | "pa" | "pi" | "fa" | "pl" | "ps" | "pt" | "qu" | "rm" | "rn" | "ro" |
    "ru" | "sa" | "sc" | "sd" | "se" | "sm" | "sg" | "sr" | "gd" | "sn" | "si" | "sk" | "sl" | "so" | "st" | "es" | "su" | "sw" | "ss" |
    "sv" | "ta" | "te" | "tg" | "th" | "ti" | "bo" | "tk" | "tl" | "tn" | "to" | "tr" | "ts" | "tt" | "tw" | "ty" | "ug" | "uk" | "ur" |
    "uz" | "ve" | "vi" | "vo" | "wa" | "cy" | "wo" | "fy" | "xh" | "yi" | "yo" | "za" | "zu"

#Step:        #Guide.#Step
#Command:     #Guide.#Command
#CommandFile: #Guide.#CommandFile
#Upload:      #Guide.#Upload
#UploadFile:  #Guide.#UploadFile

#PrestepServiceConfig: [string]: #PrestepConfig

#PrestepConfig: {
    Endpoint: string

    Networks: [...string]

    Env: [...string]
}

#Renderer: (*#RenderFull | #RenderLineRanges | #RenderDiff) & _#rendererCommon

#RendererType: int

#RendererTypeFull:       #RendererType & 1
#RendererTypeLineRanges: #RendererType & 2
#RendererTypeDiff:       #RendererType & 3

_#rendererCommon: {
    RendererType: #RendererType
    ...
}

#RenderFull: {
    _#rendererCommon
    RendererType: #RendererTypeFull
}

#RenderLineRanges: {
    _#rendererCommon
    RendererType: #RendererTypeLineRanges
    Ellipsis:     *"..." | string
    Lines: [...[int, int]]
}

#RenderDiff: {
    _#rendererCommon
    RendererType: #RendererTypeDiff
    Pre:          string
}

-- go.mod --
module mod.com

go 1.16

require cuelang.org/go v0.3.0-alpha4.0.20201022063748-aee9955c790b
-- main.go --
package main

import (
    "cuelang.org/go/cue"
    "cuelang.org/go/cue/load"
)

func main() {
    bps := load.Instances([]string{"github.com/play-with-go/preguide", "./myguide"}, nil)
    is := cue.Build(bps)

    guide := is[0].LookupDef("#Guide")
    v := is[1].Value()

    if err := guide.Err(); err != nil {
        panic(err)
    }
    if err := v.Err(); err != nil {
        panic(err)
    }

    res := v.Unify(guide)
    if err := res.Err(); err != nil {
        panic(err)
    }
}
-- myguide/steps.cue --
package steps

import "github.com/play-with-go/preguide"

preguide.#Guide

Scenarios: go115: preguide.#Scenario & {
    Description: "Go 1.15"
}

Terminals: term1: preguide.#Terminal & {
    Description: "The main terminal"
    Scenarios: go115: Image: "this_will_never_be_used"
}

Steps: step0: en: preguide.#Command & {
    Source: """
        mkdir nooutput
        """
}
EOD
go mod tidy
go run main.go

What did you expect to see?

The code to terminate in a reasonably short time.

What did you see instead?

It never terminates (left for ~10 mins, still running); CPU at 100%. Stack looks something like this:

goroutine 1 [runnable]:
cuelang.org/go/internal/core/adt.(*Builtin).call(0xc00031cdc0, 0xc0006fd490, 0xc0000e0a80, 0xc000268090, 0x1, 0x1, 0x0, 0x1)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/adt/expr.go:979 +0x896
cuelang.org/go/internal/core/adt.(*CallExpr).evaluate(0xc000342e40, 0xc0006fd490, 0xc000342e40, 0x7fb41c427758)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/adt/expr.go:927 +0x1db
cuelang.org/go/internal/core/adt.(*OpContext).evalState(0xc0006fd490, 0xad8578, 0xc000342e40, 0xadc002, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/adt/context.go:484 +0x4ec
cuelang.org/go/internal/core/adt.(*OpContext).value(0xc0006fd490, 0xad8578, 0xc000342e40, 0x0, 0x1)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/adt/context.go:454 +0x45
cuelang.org/go/internal/core/adt.(*CallExpr).evaluate(0xc000342de0, 0xc0006fd490, 0xc000342de0, 0x7fb41c427758)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/adt/expr.go:904 +0xfb
cuelang.org/go/internal/core/adt.(*OpContext).evalState(0xc0006fd490, 0xad8578, 0xc000342de0, 0xc000794102, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/adt/context.go:484 +0x4ec
cuelang.org/go/internal/core/adt.(*OpContext).node(0xc0006fd490, 0xad8578, 0xc000342de0, 0x40be02, 0xc000012000)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/adt/context.go:610 +0x66
cuelang.org/go/internal/core/adt.(*IndexExpr).resolve(0xc000342e70, 0xc0006fd490, 0xc0003398b0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/adt/expr.go:608 +0x4b
cuelang.org/go/internal/core/adt.(*OpContext).Resolve(0xc0006fd490, 0xc00047c320, 0x7fb41c4276d8, 0xc000342e70, 0xc000342e70, 0xc0009f3601)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/adt/context.go:323 +0xdb
cuelang.org/go/internal/core/eval.(*nodeContext).evalExpr(0xc00093ad80, 0xc00047c320, 0xad2338, 0xc000342e70, 0x32)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:1129 +0x48b
cuelang.org/go/internal/core/eval.(*nodeContext).addExprConjunct(0xc00093ad80, 0xc00047c320, 0xad2338, 0xc000342e70, 0x32)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:1099 +0xaa
cuelang.org/go/internal/core/eval.(*nodeContext).expandOne(0xc00093ad80, 0xc00047d2c0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:1730 +0x147
cuelang.org/go/internal/core/eval.(*nodeContext).insertSingleDisjunct(0xc00093ad80, 0x8, 0xc00047d2c0, 0xc000206780, 0x2, 0x2, 0x1, 0x39, 0x0, 0x2, ...)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:291 +0x16a
cuelang.org/go/internal/core/eval.(*nodeContext).insertDisjuncts(0xc00093ad80, 0xc000342db0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:224 +0x505
cuelang.org/go/internal/core/eval.(*nodeContext).tryDisjuncts(0xc00093ad80, 0xc00060f090)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:186 +0x2f
cuelang.org/go/internal/core/eval.(*Evaluator).evalVertex(0xc00048f740, 0xc0006fd490, 0xc00067a000, 0xc00051f404, 0x0, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:436 +0x371
cuelang.org/go/internal/core/eval.(*Evaluator).UnifyAccept(0xc00048f740, 0xc0006fd490, 0xc00067a000, 0xc00038f404, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:282 +0xa9
cuelang.org/go/internal/core/eval.(*Evaluator).Unify(0xc00048f740, 0xc0006fd490, 0xc00067a000, 0xc000342f04)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:256 +0x50
cuelang.org/go/internal/core/eval.(*nodeContext).postDisjunct(0xc0004a6900)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:610 +0x20d
cuelang.org/go/internal/core/eval.(*nodeContext).updateResult(0xc0004a6900, 0xc000343101)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:130 +0x32
cuelang.org/go/internal/core/eval.(*nodeContext).tryDisjuncts(0xc0004a6900, 0xc000514460)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:186 +0x16b
cuelang.org/go/internal/core/eval.(*Evaluator).evalVertex(0xc00048f740, 0xc0006fd490, 0xc0006faea0, 0x4, 0x0, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:436 +0x371
cuelang.org/go/internal/core/eval.(*Evaluator).UnifyAccept(0xc00048f740, 0xc0006fd490, 0xc0006faea0, 0x5d3304, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:282 +0xa9
cuelang.org/go/internal/core/eval.(*Evaluator).Unify(0xc00048f740, 0xc0006fd490, 0xc0006faea0, 0xc000343104)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:256 +0x50
cuelang.org/go/internal/core/eval.(*nodeContext).postDisjunct(0xc000502600)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:610 +0x20d
cuelang.org/go/internal/core/eval.(*nodeContext).updateResult(0xc000502600, 0xc000343101)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:130 +0x32
cuelang.org/go/internal/core/eval.(*nodeContext).tryDisjuncts(0xc000502600, 0xc000515a00)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:186 +0x16b
cuelang.org/go/internal/core/eval.(*Evaluator).evalVertex(0xc00048f740, 0xc0006fd490, 0xc0006fae10, 0x4, 0x0, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:436 +0x371
cuelang.org/go/internal/core/eval.(*Evaluator).UnifyAccept(0xc00048f740, 0xc0006fd490, 0xc0006fae10, 0x5d3304, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:282 +0xa9
cuelang.org/go/internal/core/eval.(*Evaluator).Unify(0xc00048f740, 0xc0006fd490, 0xc0006fae10, 0xc000343104)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:256 +0x50
cuelang.org/go/internal/core/eval.(*nodeContext).postDisjunct(0xc000502480)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:610 +0x20d
cuelang.org/go/internal/core/eval.(*nodeContext).updateResult(0xc000502480, 0xc000343101)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:130 +0x32
cuelang.org/go/internal/core/eval.(*nodeContext).tryDisjuncts(0xc000502480, 0xc000300600)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:186 +0x16b
cuelang.org/go/internal/core/eval.(*Evaluator).evalVertex(0xc00048f740, 0xc0006fd490, 0xc00028a990, 0xc000523704, 0x0, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:436 +0x371
cuelang.org/go/internal/core/eval.(*Evaluator).UnifyAccept(0xc00048f740, 0xc0006fd490, 0xc00028a990, 0x5d3304, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:282 +0xa9
cuelang.org/go/internal/core/eval.(*Evaluator).Unify(0xc00048f740, 0xc0006fd490, 0xc00028a990, 0xc000343404)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:256 +0x50
cuelang.org/go/internal/core/eval.(*nodeContext).postDisjunct(0xc000583200)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:610 +0x20d
cuelang.org/go/internal/core/eval.(*nodeContext).updateResult(0xc000583200, 0xc000583201)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:130 +0x32
cuelang.org/go/internal/core/eval.(*nodeContext).tryDisjuncts(0xc000583200, 0xc000300200)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/disjunct.go:186 +0x16b
cuelang.org/go/internal/core/eval.(*Evaluator).evalVertex(0xc00048f740, 0xc0006fd490, 0xc000289cb0, 0x675804, 0x0, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:436 +0x371
cuelang.org/go/internal/core/eval.(*Evaluator).UnifyAccept(0xc00048f740, 0xc0006fd490, 0xc000289cb0, 0xc00048f704, 0x0, 0x0)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:282 +0xa9
cuelang.org/go/internal/core/eval.(*Evaluator).Unify(0xc00048f740, 0xc0006fd490, 0xc000289cb0, 0x4)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/eval/eval.go:256 +0x50
cuelang.org/go/internal/core/adt.(*Vertex).Finalize(...)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/internal/core/adt/composite.go:352
cuelang.org/go/cue.Value.Unify(0xc000020e00, 0xc000276120, 0xc000020e00, 0xc000276480, 0xc000276480, 0x2)
        /home/myitcv/gostuff/pkg/mod/cuelang.org/go@v0.3.0-alpha4.0.20201022063748-aee9955c790b/cue/types.go:1665 +0x2d3
main.main()
        /tmp/tmp.jMc1MlczXF/main.go:22 +0x1cf

If you remove the embedding preguide.#Guide in myguide/steps.cue then go run main.go takes ~0.6 secs.

mpvl commented 3 years ago

This looks like it is an exponential behavior thing. Narrowed it down to

-- cue.mod/pkg/github.com/play-with-go/preguide/preguide.cue --
package preguide

#Guide: {
        #Step: #Command | #Upload | #UploadFile

        #uploadCommon: {
                Target:   string
                Language: *(Target + "") | string
        }

        #Command: Source: string

        #Upload: {
                #uploadCommon
                Source: string
        }

        #UploadFile: {
                #uploadCommon// Must be an embedding.
        }

        Steps: [string]: en: #Step // Must be an indirection.
}
-- myguide/steps.cue --
package steps

import "github.com/play-with-go/preguide"

preguide.#Guide

Steps: step0: en: preguide.#Guide.#Command & {
        Source: """
                mkdir nooutput
                """
}

which does terminate, but very slowly.

myitcv commented 3 years ago

Like #567, this appears to have regressed as part of https://cue-review.googlesource.com/c/cue/+/6742

myitcv commented 3 years ago

Noting that this is markedly better as of v0.3.0-alpha5.0.20201129154919-e77ccb1c2e96. 6.1s vs 0.09s, but still clearly an issue.

cueckoo commented 3 years ago

This issue has been migrated to https://github.com/cue-lang/cue/issues/565.

For more details about CUE's migration to a new home, please see https://github.com/cue-lang/cue/issues/1078.