Preexisting bug and 1.20 regression in bitstring for generator with reduce/unique

[lukaszsamson]

Existing issue

• I have searched existing issues and could not find a duplicate.

Elixir and Erlang/OTP versions

Erlang/OTP 28 [erts-16.4.0.1] [source] [64-bit] [smp:12:12] [ds:12:12:10] [async-threads:1] [jit]

Elixir 1.20.1, 1.20.0 (compiled with Erlang/OTP 28) - regression
all supported versions - preexisting bug

Operating system

any

Current behavior

For bitstring generator terminates prematurely and looses matching chunks when uniq/reduce option is used

1.20 regression

Repro:

    bin = <<0, 1, 9, 2, 0, 3>>
    IO.inspect for(<<0::8, x::8 <- bin>>, do: x)
    IO.inspect for(<<0::8, x::8 <- bin>>, uniq: true, do: x)
    IO.inspect for(<<0::8, x::8 <- bin>>, into: %{}, do: {x, x})
    r = for(<<0::8, x::8 <- bin>>, reduce: []) do acc -> [x | acc] end
    IO.inspect r
    IO.inspect for(<<"k=", v::8, ";" <- "k=1;k=2;j=9;k=3;">>, uniq: true, do: v - ?0)

Observed on 1.20.1:

    [1, 3]
    [1]
    %{1 => 1}
    [1]
    [1, 2]

vs on 1.19.5:

[1, 3]
[1, 3]
%{1 => 1, 3 => 3}
[3, 1]
[1, 2, 3]

Notice the <<0, 3>> binary chunk is skipped on 1.20 and unique/reduced results are missing 3

Regression introduced in 8fdef5c

Likely reason:
Size is abstract form not an integer and this clause never matches

elixir/lib/elixir/src/elixir_erl_for.erl

Line 323 in 8032f1d

no_var_size(Size) when is_integer(Size) -> Size;

and expressions like x::size(8) throw unbounded_size

Preexisting bug

When size is passed as var the behaviour was broken before 1.20. I reproduced this on 1.16-1.20

k = 8
bin = <<0, 1, 9, 2, 0, 3>>
for(<<0::8, x::size(^k) <- bin>>, uniq: false, do: x)
[1, 3]
for(<<0::8, x::size(^k) <- bin>>, uniq: true, do: x)
[1]
for(<<0::8, x::size(k) <- bin>>, uniq: true, do: x)
[1]
for(<<0::8, x::size(8) <- bin>>, uniq: true, do: x)
[1, 3]

so for variable size it likely never worked

Expected behavior

Valid size expression variants should work in for generator

[sabiwara]

Findings so far:

• bin comprehensions without uniq/into opt would compile to an erlang bin comprehension
• with uniq for example, it would basically compile to a recursive fun equivalent to the following:

defmodule Foo do
  def foo(bin), do: foo(bin, {[], %{}})
  
  def foo(<<0::size(8), x::size(8), rest::bitstring>>, {list, set}) do
    acc = case set do
      %{^x => true} -> {list, set}
      %{} -> {[x | list], Map.put(set, x, true)}
    end
    foo(rest, acc)
  end
  
  # in 1.20, this clause is not here
  def foo(<<_::size(8), _::size(8), rest::bitstring>>, acc), do: foo(rest, acc)

  def foo(<<_::bitstring>>, {list, _set}), do: :lists.reverse(list)
end

The difference between 1.19.5 and 1.20.0 is the second clause of foo/2, which allows to skip the same size as the pattern when it doesn't match.
In its absence, we just jump to the third clause and break as soon as we don't match, which is inconsistent with how erlang bin comprehensions behave.

It's trivial to fix the integer case - thanks @lukaszsamson for the pointer about no_var_size, and indeed the variable case is more tricky. But it should technically be possible to make it work in Erlang, the following works:

Foo = fun(Bin) ->
  Size = 8,
  (fun
    F(<<0:Size, X:Size, Rest/bitstring>>, {List, Set}) ->
      Acc = case Set of
        #{X := true} -> {List, Set};
        #{} -> {[X | List], Set#{X => true}}
      end,
      F(Rest, Acc);
    F(<<_:Size, _:Size, Rest/bitstring>>, Acc) ->
      F(Rest, Acc);
    F(<<_/bitstring>>, {List, _Set}) ->
      lists:reverse(List)
  end)(Bin, {[], #{}})
end.
Foo(<<0, 1, 2, 2, 0, 3>>).