1-module(elixir_bitstring).
2-export([expand/4, format_error/1]).
3-import(elixir_errors, [form_error/4]).
4-include("elixir.hrl").
5
6expand_match(Expr, {E, OriginalE}) ->
7  {EExpr, EE} = elixir_expand:expand(Expr, E),
8  {EExpr, {EE, OriginalE}}.
9
10expand(Meta, Args, E, RequireSize) ->
11  case ?key(E, context) of
12    match ->
13      {EArgs, Alignment, {EA, _}} =
14        expand(Meta, fun expand_match/2, Args, [], {E, E}, 0, RequireSize),
15
16      case find_match(EArgs) of
17        false ->
18          {{'<<>>', [{alignment, Alignment} | Meta], EArgs}, EA};
19        Match ->
20          form_error(Meta, EA, ?MODULE, {nested_match, Match})
21      end;
22    _ ->
23      PairE = {elixir_env:prepare_write(E), E},
24
25      {EArgs, Alignment, {EA, _}} =
26        expand(Meta, fun elixir_expand:expand_arg/2, Args, [], PairE, 0, RequireSize),
27
28      {{'<<>>', [{alignment, Alignment} | Meta], EArgs}, elixir_env:close_write(EA, E)}
29  end.
30
31expand(_BitstrMeta, _Fun, [], Acc, E, Alignment, _RequireSize) ->
32  {lists:reverse(Acc), Alignment, E};
33expand(BitstrMeta, Fun, [{'::', Meta, [Left, Right]} | T], Acc, E, Alignment, RequireSize) ->
34  {ELeft, {EL, OriginalE}} = expand_expr(Meta, Left, Fun, E),
35
36  MatchOrRequireSize = RequireSize or is_match_size(T, EL),
37  EType = expr_type(ELeft),
38  {ERight, EAlignment, ES} = expand_specs(EType, Meta, Right, EL, OriginalE, MatchOrRequireSize),
39
40  EAcc = concat_or_prepend_bitstring(Meta, ELeft, ERight, Acc, ES, MatchOrRequireSize),
41  expand(BitstrMeta, Fun, T, EAcc, {ES, OriginalE}, alignment(Alignment, EAlignment), RequireSize);
42expand(BitstrMeta, Fun, [H | T], Acc, E, Alignment, RequireSize) ->
43  Meta = extract_meta(H, BitstrMeta),
44  {ELeft, {ES, OriginalE}} = expand_expr(Meta, H, Fun, E),
45
46  MatchOrRequireSize = RequireSize or is_match_size(T, ES),
47  EType = expr_type(ELeft),
48  ERight = infer_spec(EType, Meta),
49
50  InferredMeta = [{inferred_bitstring_spec, true} | Meta],
51  EAcc = concat_or_prepend_bitstring(InferredMeta, ELeft, ERight, Acc, ES, MatchOrRequireSize),
52  expand(Meta, Fun, T, EAcc, {ES, OriginalE}, Alignment, RequireSize).
53
54extract_meta({_, Meta, _}, _) -> Meta;
55extract_meta(_, Meta) -> Meta.
56
57%% Variables defined outside the binary can be accounted
58%% on subparts, however we can't assign new variables.
59is_match_size([_ | _], #{context := match}) -> true;
60is_match_size(_, _) -> false.
61
62expr_type(Integer) when is_integer(Integer) -> integer;
63expr_type(Float) when is_float(Float) -> float;
64expr_type(Binary) when is_binary(Binary) -> binary;
65expr_type({'<<>>', _, _}) -> bitstring;
66expr_type(_) -> default.
67
68infer_spec(bitstring, Meta) -> {bitstring, Meta, []};
69infer_spec(binary, Meta) -> {binary, Meta, []};
70infer_spec(float, Meta) -> {float, Meta, []};
71infer_spec(integer, Meta) -> {integer, Meta, []};
72infer_spec(default, Meta) -> {integer, Meta, []}.
73
74concat_or_prepend_bitstring(_Meta, {'<<>>', _, []}, _ERight, Acc, _E, _RequireSize) ->
75  Acc;
76concat_or_prepend_bitstring(Meta, {'<<>>', PartsMeta, Parts} = ELeft, ERight, Acc, E, RequireSize) ->
77  case E of
78    #{context := match} when RequireSize ->
79      case lists:last(Parts) of
80        {'::', SpecMeta, [Bin, {binary, _, []}]} when not is_binary(Bin) ->
81          form_error(SpecMeta, E, ?MODULE, unsized_binary);
82
83        {'::', SpecMeta, [_, {bitstring, _, []}]} ->
84          form_error(SpecMeta, E, ?MODULE, unsized_binary);
85
86        _ ->
87          ok
88      end;
89    _ ->
90      ok
91  end,
92
93  case ERight of
94    {binary, _, []} ->
95      {alignment, Alignment} = lists:keyfind(alignment, 1, PartsMeta),
96
97      if
98        Alignment == 0 ->
99          lists:reverse(Parts, Acc);
100
101        is_integer(Alignment) ->
102          form_error(Meta, E, ?MODULE, {unaligned_binary, ELeft});
103
104        true ->
105          [{'::', Meta, [ELeft, ERight]} | Acc]
106      end;
107    {bitstring, _, []} ->
108      lists:reverse(Parts, Acc)
109  end;
110concat_or_prepend_bitstring(Meta, ELeft, ERight, Acc, _E, _RequireSize) ->
111  [{'::', Meta, [ELeft, ERight]} | Acc].
112
113%% Handling of alignment
114
115alignment(Left, Right) when is_integer(Left), is_integer(Right) -> (Left + Right) rem 8;
116alignment(_, _) -> unknown.
117
118compute_alignment(_, Size, Unit) when is_integer(Size), is_integer(Unit) -> (Size * Unit) rem 8;
119compute_alignment(default, Size, Unit) -> compute_alignment(integer, Size, Unit);
120compute_alignment(integer, default, Unit) -> compute_alignment(integer, 8, Unit);
121compute_alignment(integer, Size, default) -> compute_alignment(integer, Size, 1);
122compute_alignment(bitstring, Size, default) -> compute_alignment(bitstring, Size, 1);
123compute_alignment(binary, Size, default) -> compute_alignment(binary, Size, 8);
124compute_alignment(binary, _, _) -> 0;
125compute_alignment(float, _, _) -> 0;
126compute_alignment(utf32, _, _) -> 0;
127compute_alignment(utf16, _, _) -> 0;
128compute_alignment(utf8, _, _) -> 0;
129compute_alignment(_, _, _) -> unknown.
130
131%% Expands the expression of a bitstring, that is, the LHS of :: or
132%% an argument of the bitstring (such as "foo" in "<<foo>>").
133%% If we are inside a match/guard, we inline interpolations explicitly,
134%% otherwise they are inlined by elixir_rewrite.erl.
135
136expand_expr(_Meta, {{'.', _, [Mod, to_string]}, _, [Arg]} = AST, Fun, {#{context := Context}, _} = E)
137    when Context /= nil, (Mod == 'Elixir.Kernel') orelse (Mod == 'Elixir.String.Chars') ->
138  case Fun(Arg, E) of
139    {EBin, EE} when is_binary(EBin) -> {EBin, EE};
140    _ -> Fun(AST, E) % Let it raise
141  end;
142expand_expr(Meta, Component, Fun, E) ->
143  case Fun(Component, E) of
144    {EComponent, {ErrorE, _}} when is_list(EComponent); is_atom(EComponent) ->
145      form_error(Meta, ErrorE, ?MODULE, {invalid_literal, EComponent});
146    {_, _} = Expanded ->
147      Expanded
148  end.
149
150%% Expands and normalizes types of a bitstring.
151
152expand_specs(ExprType, Meta, Info, E, OriginalE, RequireSize) ->
153  Default =
154    #{size => default,
155      unit => default,
156      sign => default,
157      type => default,
158      endianness => default},
159  {#{size := Size, unit := Unit, type := Type, endianness := Endianness, sign := Sign}, ES} =
160    expand_each_spec(Meta, unpack_specs(Info, []), Default, E, OriginalE),
161  MergedType = type(Meta, ExprType, Type, E),
162  validate_size_required(Meta, RequireSize, ExprType, MergedType, Size, ES),
163  SizeAndUnit = size_and_unit(Meta, ExprType, Size, Unit, ES),
164  Alignment = compute_alignment(MergedType, Size, Unit),
165  [H | T] = build_spec(Meta, Size, Unit, MergedType, Endianness, Sign, SizeAndUnit, ES),
166  {lists:foldl(fun(I, Acc) -> {'-', Meta, [Acc, I]} end, H, T), Alignment, ES}.
167
168type(_, default, default, _) ->
169  integer;
170type(_, ExprType, default, _) ->
171  ExprType;
172type(_, binary, Type, _) when Type == binary; Type == bitstring; Type == utf8; Type == utf16; Type == utf32 ->
173  Type;
174type(_, bitstring, Type, _) when Type == binary; Type == bitstring ->
175  Type;
176type(_, integer, Type, _) when Type == integer; Type == float; Type == utf8; Type == utf16; Type == utf32 ->
177  Type;
178type(_, float, Type, _) when Type == float ->
179  Type;
180type(_, default, Type, _) ->
181  Type;
182type(Meta, Other, Value, E) ->
183  form_error(Meta, E, ?MODULE, {bittype_mismatch, Value, Other, type}).
184
185expand_each_spec(Meta, [{Expr, _, Args} = H | T], Map, E, OriginalE) when is_atom(Expr) ->
186  case validate_spec(Expr, Args) of
187    {Key, Arg} ->
188      {Value, EE} = expand_spec_arg(Arg, E, OriginalE),
189      validate_spec_arg(Meta, Key, Value, EE, OriginalE),
190
191      case maps:get(Key, Map) of
192        default -> ok;
193        Value -> ok;
194        Other -> form_error(Meta, E, ?MODULE, {bittype_mismatch, Value, Other, Key})
195      end,
196
197      expand_each_spec(Meta, T, maps:put(Key, Value, Map), EE, OriginalE);
198    none ->
199      case 'Elixir.Macro':expand(H, elixir_env:linify({?line(Meta), E})) of
200        H ->
201          form_error(Meta, E, ?MODULE, {undefined_bittype, H});
202        NewTypes ->
203          expand_each_spec(Meta, unpack_specs(NewTypes, []) ++ T, Map, E, OriginalE)
204      end
205  end;
206expand_each_spec(Meta, [Expr | _], _Map, E, _OriginalE) ->
207  form_error(Meta, E, ?MODULE, {undefined_bittype, Expr});
208expand_each_spec(_Meta, [], Map, E, _OriginalE) ->
209  {Map, E}.
210
211unpack_specs({'-', _, [H, T]}, Acc) ->
212  unpack_specs(H, unpack_specs(T, Acc));
213unpack_specs({'*', _, [{'_', _, Atom}, Unit]}, Acc) when is_atom(Atom) ->
214  [{unit, [], [Unit]} | Acc];
215unpack_specs({'*', _, [Size, Unit]}, Acc) ->
216  [{size, [], [Size]}, {unit, [], [Unit]} | Acc];
217unpack_specs(Size, Acc) when is_integer(Size) ->
218  [{size, [], [Size]} | Acc];
219unpack_specs({Expr, Meta, Args}, Acc) when is_atom(Expr) ->
220  ListArgs = if is_atom(Args) -> []; is_list(Args) -> Args end,
221  [{Expr, Meta, ListArgs} | Acc];
222unpack_specs(Other, Acc) ->
223  [Other | Acc].
224
225validate_spec(big, [])       -> {endianness, big};
226validate_spec(little, [])    -> {endianness, little};
227validate_spec(native, [])    -> {endianness, native};
228validate_spec(size, [Size])  -> {size, Size};
229validate_spec(unit, [Unit])  -> {unit, Unit};
230validate_spec(integer, [])   -> {type, integer};
231validate_spec(float, [])     -> {type, float};
232validate_spec(binary, [])    -> {type, binary};
233validate_spec(bytes, [])     -> {type, binary};
234validate_spec(bitstring, []) -> {type, bitstring};
235validate_spec(bits, [])      -> {type, bitstring};
236validate_spec(utf8, [])      -> {type, utf8};
237validate_spec(utf16, [])     -> {type, utf16};
238validate_spec(utf32, [])     -> {type, utf32};
239validate_spec(signed, [])    -> {sign, signed};
240validate_spec(unsigned, [])  -> {sign, unsigned};
241validate_spec(_, _)          -> none.
242
243expand_spec_arg(Expr, E, _OriginalE) when is_atom(Expr); is_integer(Expr) ->
244  {Expr, E};
245expand_spec_arg(Expr, #{context := match} = E, _OriginalE) ->
246  {EExpr, EE} = elixir_expand:expand(Expr, E#{context := nil, prematch_vars := raise}),
247  {EExpr, EE#{context := match, prematch_vars := ?key(E, prematch_vars)}};
248expand_spec_arg(Expr, E, OriginalE) ->
249  elixir_expand:expand(Expr, elixir_env:reset_read(E, OriginalE)).
250
251validate_spec_arg(Meta, size, Value, E, OriginalE) ->
252  case Value of
253    {Var, VarMeta, Context} when is_atom(Var) and is_atom(Context) ->
254      Tuple = {Var, elixir_utils:var_context(VarMeta, Context)},
255
256      case is_valid_spec_arg_var(Tuple, E, OriginalE) of
257        true -> ok;
258        false -> form_error(Meta, E, ?MODULE, {undefined_var_in_spec, Value})
259      end;
260
261    _ when is_integer(Value) ->
262      ok;
263
264    _ ->
265      form_error(Meta, E, ?MODULE, {bad_size_argument, Value})
266  end;
267validate_spec_arg(Meta, unit, Value, E, _OriginalE) when not is_integer(Value) ->
268  form_error(Meta, E, ?MODULE, {bad_unit_argument, Value});
269validate_spec_arg(_Meta, _Key, _Value, _E, _OriginalE) ->
270  ok.
271
272is_valid_spec_arg_var(Var, E, #{context := match} = OriginalE) ->
273  case OriginalE of
274    #{prematch_vars := {#{Var := _}, _}} -> true;
275    _ -> is_var(Var, E) andalso not is_var(Var, OriginalE)
276  end;
277is_valid_spec_arg_var(_Var, _E, _OriginalE) ->
278  true.
279
280is_var(Var, #{current_vars := {Read, _}}) ->
281  maps:is_key(Var, Read).
282
283validate_size_required(Meta, true, default, Type, default, E) when Type == binary; Type == bitstring ->
284  form_error(Meta, E, ?MODULE, unsized_binary);
285validate_size_required(_, _, _, _, _, _) ->
286  ok.
287
288size_and_unit(Meta, bitstring, Size, Unit, E) when Size /= default; Unit /= default ->
289  form_error(Meta, E, ?MODULE, bittype_literal_bitstring);
290size_and_unit(Meta, binary, Size, Unit, E) when Size /= default; Unit /= default ->
291  form_error(Meta, E, ?MODULE, bittype_literal_string);
292size_and_unit(_Meta, _ExprType, Size, Unit, _E) ->
293  add_arg(unit, Unit, add_arg(size, Size, [])).
294
295add_arg(_Key, default, Spec) -> Spec;
296add_arg(Key, Arg, Spec) -> [{Key, [], [Arg]} | Spec].
297
298build_spec(Meta, Size, Unit, Type, Endianness, Sign, Spec, E) when Type == utf8; Type == utf16; Type == utf32 ->
299  if
300    Size /= default; Unit /= default ->
301      form_error(Meta, E, ?MODULE, bittype_utf);
302    Sign /= default ->
303      form_error(Meta, E, ?MODULE, bittype_signed);
304    true ->
305      add_spec(Type, add_spec(Endianness, Spec))
306  end;
307
308build_spec(Meta, _Size, Unit, Type, _Endianness, Sign, Spec, E) when Type == binary; Type == bitstring ->
309  if
310    Type == bitstring, Unit /= default, Unit /= 1 ->
311      form_error(Meta, E, ?MODULE, {bittype_mismatch, Unit, 1, unit});
312    Sign /= default ->
313      form_error(Meta, E, ?MODULE, bittype_signed);
314    true ->
315      %% Endianness is supported but has no effect, so we just ignore it.
316      add_spec(Type, Spec)
317  end;
318
319build_spec(Meta, Size, Unit, Type, Endianness, Sign, Spec, E) when Type == integer; Type == float ->
320  NumberSize = number_size(Size, Unit),
321  if
322    Type == float, is_integer(NumberSize) ->
323      case valid_float_size(NumberSize) of
324        true ->
325          add_spec(Type, add_spec(Endianness, add_spec(Sign, Spec)));
326        false ->
327          form_error(Meta, E, ?MODULE, {bittype_float_size, NumberSize})
328      end;
329    Size == default, Unit /= default ->
330      form_error(Meta, E, ?MODULE, bittype_unit);
331    true ->
332      add_spec(Type, add_spec(Endianness, add_spec(Sign, Spec)))
333  end.
334
335number_size(Size, default) when is_integer(Size) -> Size;
336number_size(Size, Unit) when is_integer(Size) -> Size * Unit;
337number_size(Size, _) -> Size.
338
339%% TODO: Simplify when we require OTP 24
340valid_float_size(16) -> erlang:system_info(otp_release) >= "24";
341valid_float_size(32) -> true;
342valid_float_size(64) -> true;
343valid_float_size(_) -> false.
344
345add_spec(default, Spec) -> Spec;
346add_spec(Key, Spec) -> [{Key, [], []} | Spec].
347
348find_match([{'=', _, [_Left, _Right]} = Expr | _Rest]) ->
349  Expr;
350find_match([{_, _, Args} | Rest]) when is_list(Args) ->
351  case find_match(Args) of
352    false -> find_match(Rest);
353    Match -> Match
354  end;
355find_match([_Arg | Rest]) ->
356  find_match(Rest);
357find_match([]) ->
358  false.
359
360format_error({unaligned_binary, Expr}) ->
361  Message = "expected ~ts to be a binary but its number of bits is not divisible by 8",
362  io_lib:format(Message, ['Elixir.Macro':to_string(Expr)]);
363format_error(unsized_binary) ->
364  "a binary field without size is only allowed at the end of a binary pattern, "
365  "at the right side of binary concatenation and and never allowed in binary generators. "
366  "The following examples are invalid:\n\n"
367  "    rest <> \"foo\"\n"
368  "    <<rest::binary, \"foo\">>\n\n"
369  "They are invalid because there is a bits/bitstring component not at the end. "
370  "However, the \"reverse\" would work:\n\n"
371  "    \"foo\" <> rest\n"
372  "    <<\"foo\", rest::binary>>\n\n";
373format_error(bittype_literal_bitstring) ->
374  "literal <<>> in bitstring supports only type specifiers, which must be one of: "
375    "binary or bitstring";
376format_error(bittype_literal_string) ->
377  "literal string in bitstring supports only endianness and type specifiers, which must be one of: "
378    "little, big, native, utf8, utf16, utf32, bits, bytes, binary or bitstring";
379format_error(bittype_utf) ->
380  "size and unit are not supported on utf types";
381format_error(bittype_signed) ->
382  "signed and unsigned specifiers are supported only on integer and float types";
383format_error(bittype_unit) ->
384  "integer and float types require a size specifier if the unit specifier is given";
385format_error({bittype_float_size, Other}) ->
386  Message =
387    case erlang:system_info(otp_release) >= "24" of
388      true -> "16, 32, or 64";
389      false -> "32 or 64"
390    end,
391  io_lib:format("float requires size*unit to be ~s (default), got: ~p", [Message, Other]);
392format_error({invalid_literal, Literal}) ->
393  io_lib:format("invalid literal ~ts in <<>>", ['Elixir.Macro':to_string(Literal)]);
394format_error({undefined_bittype, Expr}) ->
395  io_lib:format("unknown bitstring specifier: ~ts", ['Elixir.Macro':to_string(Expr)]);
396format_error({bittype_mismatch, Val1, Val2, Where}) ->
397  io_lib:format("conflicting ~ts specification for bit field: \"~p\" and \"~p\"", [Where, Val1, Val2]);
398format_error({bad_unit_argument, Unit}) ->
399  io_lib:format("unit in bitstring expects an integer as argument, got: ~ts",
400                ['Elixir.Macro':to_string(Unit)]);
401format_error({bad_size_argument, Size}) ->
402  io_lib:format("size in bitstring expects an integer or a variable as argument, got: ~ts",
403                ['Elixir.Macro':to_string(Size)]);
404format_error({nested_match, Expr}) ->
405  Message =
406    "cannot pattern match inside a bitstring "
407      "that is already in match, got: ~ts",
408  io_lib:format(Message, ['Elixir.Macro':to_string(Expr)]);
409format_error({undefined_var_in_spec, Var}) ->
410  Message =
411    "undefined variable \"~ts\" in bitstring segment. If the size of the binary is a "
412      "variable, the variable must be defined prior to its use in the binary/bitstring match "
413      "itself, or outside the pattern match",
414  io_lib:format(Message, ['Elixir.Macro':to_string(Var)]).
415