O(2^n) perf on beam_validator_strong and beam_validator_weak passes

[drathier]

Describe the bug
O(2^n) perf on beam_validator_strong and beam_validator_weak passes

To Reproduce
Comple this file, with one row uncommented each time. I've added the compile time for some rows on my machine as comments.

% Generated by purerl version 0.0.15
-module(test@ps).
-export([
  genericThingy/0
 ]).

genericThingy() -> #{to=>fun (X) ->
  case X of
    ({ inl, _ }) -> { thingy1 };
    ({ inr, { inl, _ } }) -> { thingy2 };
    %({ inr, { inr, { inl, _ } } }) -> { thingy3 };
    %({ inr, { inr, { inr, { inl, _ } } } }) -> { thingy4 };
    %({ inr, { inr, { inr, { inr, { inl, _ } } } } }) -> { thingy5 };
    %({ inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } }) -> { thingy6 };
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } }) -> { thingy7 };
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } }) -> { thingy8 };
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } }) -> { thingy9 };
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } }) -> { thingy10 };
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } }) -> { thingy11 };
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } }) -> { thingy12 };
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } }) -> { thingy13 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } }) -> { thingy14 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } }) -> { thingy15 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } }) -> { thingy16 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } }) -> { thingy17 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } }) -> { thingy18 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } }) -> { thingy19 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } } }) -> { thingy20 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } } } }) -> { thingy21 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } } } } }) -> { thingy22 }
  
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } } } } } }) -> { thingy23 } % 4+5s
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } } } } } } }) -> { thingy24 } % 9+9s
    ({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } } } } } } } }) -> { thingy25 } % 20+19s
  
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } } } } } } } } }) -> { thingy26 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } } } } } } } } } }) -> { thingy27 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } } } } } } } } } } }) -> { thingy28 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inl, _ } } } } } } } } } } } } } } } } } } } } } } } } } } } } }) -> { thingy29 }
    %({ inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, { inr, _ } } } } } } } } } } } } } } } } } } } } } } } } } } } } }) -> { thingy30 }
  end
end}.

Expected behavior
Better time complexity :)

Affected versions
Only tested 24.2.1 so far.

Additional context
Purescript automatically generates generic instances which have this shape. The input ADT in this case is 30 constructors without arguments, and the generic instance turns them into this linked-list looking shape. The erlang output above is minified.

data Thingy
  = Thingy1
  | Thingy2
  | Thingy3
  ...

derive instance Generic Thingy _

[jhogberg]

Thanks for your report! I think I've fixed the worst of it in #5920, can you try it on the original file?

[drathier]

I haven't been able to get erlc master building on my machine, but the test file and the prod file are incredibly similar, and replacing that function body with a simpler case reduces compile time down to sub-second. Thus, I'd bet that this bug is fixed, even if I can't confirm it. Big thanks.

[jhogberg]

Alright, thanks, we'll release it as a patch on 24 in a few days. :)