VS Pro 16.3.0 Preview 2 - complex expressions causing compiler to effectively hang, suspect some exponential cost

vsfeedback commented 5 years ago

This issue has been moved from a ticket on Developer Community.

16.2.3 would compile our work code, 16.3.0 Preview 2 seemed to hang forever.

It is hard to provide a stereotype of the problem without all prod code. Extracting the essence ended with a section of code that would take a disproportionately long time to compile; but would complete in about a minute.

I repeated the troublesome clause 4 more times, which causes RAM usage to blow up into the 10s of gigabytes (I went up to 40 then shut it off).

Leaving this code up in the 2019 IDE will cause it to crash during analysis within a few minutes; but compiling even via the command line will consume all the machine’s ram (and never complete).

The attached CS file, or the code below, will cause all manner of mayhem. If you remove the indicated duplicates of the 4-line clauses, compilation should complete but there will still be trouble with the IDE, and it will still take way too long to compile for such a tiny program.

using System;

namespace PreviewFail
{

    public sealed class A1<T>
    {

    }

    public sealed class O<T>
    {
        public R M<R>(Func<T, R> w, Func<R> wo) => throw new Exception("Irrelevant");
    }

    public sealed class WO<T>
    {
        private WO() { }
        public static WO<T> Build(A1<T> arr) => new WO<T>();

        public O<WO<T>> F(Func<T, bool> filter) => new O<WO<T>>();
    }

    public static class WO
    {
        public static WO<T> Build<T>(A1<T> arr) => WO<T>.Build(arr);
        // public static WO<T> Build<T>(int a) => throw new Exception("Irrelevant");
    }

    public sealed class CO<T>
    {
        private CO()
        {

        }
        public static CO<T> FWO(WO<T> wo) => new CO<T>();
    }

    public static class CO
    {
        public static CO<T> FWO<T>(WO<T> wo) => CO<T>.FWO(wo);
        // public static CO<T> FWO<T>(int a) => throw new Exception("Irrelevant");
    }
    public sealed class CP
    {

    }

    // public sealed class W { }

    public static class CantCompile
    {

        public static U L<T, U>(this T original, Func<T, U> transformed) => transformed(original);

        // Otherwise, success.
        public static T L<T>(Func<T> get) => get();
        public static void L<T>(this T original, Action<T> run) => run(original);

        public static void Doit()
        {

            // values don't matter
            A1<WD> aa = null;
            A1<WD> ab = null;

            Func<bool, CP, int> getTheChoice =
                WO.Build(aa).L(rw =>
                WO.Build(ab).L(uw =>
                CO.FWO(rw).L(rwc =>
                CO.FWO(uw).L(uwc =>

                rw.F(WD.FacetA.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fa =>
                rw.F(WD.FacetB.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fb =>
                    rw.F(WD.FacetC.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fc =>

                    rw.F(WD.FacetD.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fd =>
                    uw.F(WD.FacetA.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fe =>
                    uw.F(WD.FacetB.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(ff =>
                    uw.F(WD.FacetC.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fg =>

                    // Repeating this clause to drive up the problem. I think it's going geometric
                    rw.F(WD.FacetD.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fd1 =>
                    uw.F(WD.FacetA.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fe1 =>
                    uw.F(WD.FacetB.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(ff1 =>
                    uw.F(WD.FacetC.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fg1 =>

                    rw.F(WD.FacetD.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fd2 =>
                    uw.F(WD.FacetA.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fe2 =>
                    uw.F(WD.FacetB.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(ff2 =>
                    uw.F(WD.FacetC.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fg2 =>

                    rw.F(WD.FacetD.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fd3 =>
                    uw.F(WD.FacetA.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fe3 =>
                    uw.F(WD.FacetB.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(ff3 =>
                    uw.F(WD.FacetC.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fg3 =>

                    rw.F(WD.FacetD.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fd4 =>
                    uw.F(WD.FacetA.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fe4 =>
                    uw.F(WD.FacetB.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(ff4 =>
                    uw.F(WD.FacetC.ISV).M(x => x, () => throw new Exception("")).L(CO.FWO).L(fg4 =>

                    new Func<bool, CP, int>(
                        (bool someBool, CP cp) =>
                                1234
                                ))) )))) )))) )))) ))))

                 )))))))));
        }
    }

    public sealed class WD
    {
        public static readonly ST.AC<WD, ED<long>> FacetA = null;
        public static readonly ST.AC<WD, ED<int>> FacetB = null;
        public static readonly ST.AC<WD, ED<long>> FacetC = null;
        public static readonly ST.AC<WD, ED<int>> FacetD = null;

        public sealed class ED<T>
        {
        }
    }

    public static class ST
    {
        public sealed class AC<TOST, TContained>
        {
            public Func<TOST, bool> ISV => throw new Exception("Irrelevant");
        }
    }
}

Original Comments

Visual Studio Feedback System on 8/22/2019, 00:07 AM:

We have directed your feedback to the appropriate engineering team for further evaluation. The team will review the feedback and notify you about the next steps.

Original Solutions

(no solutions)

gafter commented 5 years ago

If this is nested invocations with lambdas, binding actually requires exponential time. Compiling is reducable to 3SAT. See https://blogs.msdn.microsoft.com/ericlippert/2007/03/26/lambda-expressions-vs-anonymous-methods-part-four/ and https://blogs.msdn.microsoft.com/ericlippert/2007/03/28/lambda-expressions-vs-anonymous-methods-part-five/

MattLamari commented 5 years ago

It was tricky to isolate my contrived solution. At least I better understand what's happening. However, the original body of code - which I can't share - would compile on 16.2 and choke up forever on 16.3, so something around this did change.

gafter commented 5 years ago

@MattLamari One thing that might have changed is the number of overloads of the methods you're using in your example. The APIs you are working with might have changed by adding new overloads.

dotnet / roslyn