Bit syntax matching gotchas

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Bit syntax matching gotchas

Björn Gustavsson-4
There are some gotchas in the bit syntax that comes up now and then on
the mailing list, and also as a bug report at the end of last year:
http://bugs.erlang.org/browse/ERL-44

We have decided to try do something about it in OTP 19. We have
discussed various solutions internally in the OTP group, and I have
spent far too much time lately thinking about it.

Here follows first my summary of the issues, and then my suggestion
how the compiler should be modified.

BACKGROUND ABOUT BIT SYNTAX CONSTRUCTION

When constructing binaries, there is an implicit masking of the
values. All of the following constructions give the same result:

<<255>>
<<16#FF>>
<<16#FFFF>>
<<-1>>

There have been complaints about the implicit masking behaviour, but
there is a lot of code that depends on it, so it would be unwise to
change it.

THE PROBLEM

There is no similar masking when matching values. That means that all
of the following expressions will all fail to match:

<<-1>> = <<-1>>
<<-1/unsigned>> = <<-1>
<<16#FF>> = <<16#FFFF>>
<<-12345/signed>> = <<-12345/signed>>

Let's look at how the compiler internally implements matching. Take
this function as an example:

f(<<-1:8/unsigned>>) -> ok.

It will be rewritten to:

f(<<V:8/unsigned>>) when V =:= -1 -> ok.

That is, an unsigned value (in the range 0-255) will be stored in the
variable V, which will then be compared to -1.

POSSIBLE SOLUTION #1

The most obvious solution is probably to let the compiler warn for the
above cases. The matching would still fail. The developer will need to
fix their code. For example:

<<-1/signed>> = <<-1>>


POSSIBLE SOLUTION #2

There is one problem with the solution #1. It is not possible to
produce a warning for the following example:

f(Val) ->
  <<Val:8>> = <<Val:8>>,
  Val.

So in addition to warning when possible, another solution is to mask
values also when matching. Internally, the compiler could rewrite the
function to something like:

f(Val) ->
  <<NewVar:8>> = <<Val:8>>,
  Val = NewVar band 16#FF,
  Val.

Similar rewriting should be done for literal integer, so the following
expression would now match:

<<-1>> = <<-1>>


WHICH SOLUTION?

Just to make to sure that I don't reject solution #2 just because it
seems like a lot work to implement, I have actually implemented it.

Now that I have implemented solution #2, I want to reject it.

The reason I reject it is that the matching previously bound variables
is uncommon. Even in the compiler test suites it is uncommon (test
suites typically match bound variables more often than production code
do).

Therefore, solution #2 would make behaviour of matching more
consistent with construction, but would not significantly increase the
number of correct programs. Also, if clauses that previously didn't
match start to match, then code that has not been executed before will
be executed. Code that has not been tested usually doesn't work.

Solution #1 would point all cases when literal integers could not
possibly match and force the developer to fix them.

Therefore I choose solution #1.


YOUR INPUT?

Are there better way to fix bit syntax matching? Anything I have
forgotten or not thought about?

/Björn

--
Björn Gustavsson, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Bit syntax matching gotchas

José Valim-2
Björn, in solution #1, would you warn only when matching or also when constructing? Is the warning only at compile-time or also at runtime? For example, would you warn for:

    X = -1.
    <<X>>.

We may have a third option which is to control the masking behaviour with a new flag. From Erlang 19, we could warn if you are relying on masking and you would need to pick to mask (/integer-mask) or fix your code. The default after the warning is removed is to always raise. The mask option wouldn't be supported when matching, making it clear the masking behaviour is construction only.

I am not sure this is a *good* option but I thought I would mention it anyway. :)




José Valim
Skype: jv.ptec
Founder and Director of R&D

On Wed, Feb 3, 2016 at 7:17 AM, Björn Gustavsson <[hidden email]> wrote:
There are some gotchas in the bit syntax that comes up now and then on
the mailing list, and also as a bug report at the end of last year:
http://bugs.erlang.org/browse/ERL-44

We have decided to try do something about it in OTP 19. We have
discussed various solutions internally in the OTP group, and I have
spent far too much time lately thinking about it.

Here follows first my summary of the issues, and then my suggestion
how the compiler should be modified.

BACKGROUND ABOUT BIT SYNTAX CONSTRUCTION

When constructing binaries, there is an implicit masking of the
values. All of the following constructions give the same result:

<<255>>
<<16#FF>>
<<16#FFFF>>
<<-1>>

There have been complaints about the implicit masking behaviour, but
there is a lot of code that depends on it, so it would be unwise to
change it.

THE PROBLEM

There is no similar masking when matching values. That means that all
of the following expressions will all fail to match:

<<-1>> = <<-1>>
<<-1/unsigned>> = <<-1>
<<16#FF>> = <<16#FFFF>>
<<-12345/signed>> = <<-12345/signed>>

Let's look at how the compiler internally implements matching. Take
this function as an example:

f(<<-1:8/unsigned>>) -> ok.

It will be rewritten to:

f(<<V:8/unsigned>>) when V =:= -1 -> ok.

That is, an unsigned value (in the range 0-255) will be stored in the
variable V, which will then be compared to -1.

POSSIBLE SOLUTION #1

The most obvious solution is probably to let the compiler warn for the
above cases. The matching would still fail. The developer will need to
fix their code. For example:

<<-1/signed>> = <<-1>>


POSSIBLE SOLUTION #2

There is one problem with the solution #1. It is not possible to
produce a warning for the following example:

f(Val) ->
  <<Val:8>> = <<Val:8>>,
  Val.

So in addition to warning when possible, another solution is to mask
values also when matching. Internally, the compiler could rewrite the
function to something like:

f(Val) ->
  <<NewVar:8>> = <<Val:8>>,
  Val = NewVar band 16#FF,
  Val.

Similar rewriting should be done for literal integer, so the following
expression would now match:

<<-1>> = <<-1>>


WHICH SOLUTION?

Just to make to sure that I don't reject solution #2 just because it
seems like a lot work to implement, I have actually implemented it.

Now that I have implemented solution #2, I want to reject it.

The reason I reject it is that the matching previously bound variables
is uncommon. Even in the compiler test suites it is uncommon (test
suites typically match bound variables more often than production code
do).

Therefore, solution #2 would make behaviour of matching more
consistent with construction, but would not significantly increase the
number of correct programs. Also, if clauses that previously didn't
match start to match, then code that has not been executed before will
be executed. Code that has not been tested usually doesn't work.

Solution #1 would point all cases when literal integers could not
possibly match and force the developer to fix them.

Therefore I choose solution #1.


YOUR INPUT?

Are there better way to fix bit syntax matching? Anything I have
forgotten or not thought about?

/Björn

--
Björn Gustavsson, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Bit syntax matching gotchas

Björn Gustavsson-4
On Wed, Feb 3, 2016 at 12:00 PM, José Valim
<[hidden email]> wrote:
> Björn, in solution #1, would you warn only when matching or also when
> constructing? Is the warning only at compile-time or also at runtime? For
> example, would you warn for:
>
>     X = -1.
>     <<X>>.

Yes, I have considered warning for construction too.
The warnings would only occur at compile-time.

There would NOT be a warning for your example, though.
More on that below.

> We may have a third option which is to control the masking behaviour with a
> new flag. From Erlang 19, we could warn if you are relying on masking and
> you would need to pick to mask (/integer-mask) or fix your code. The default
> after the warning is removed is to always raise. The mask option wouldn't be
> supported when matching, making it clear the masking behaviour is
> construction only.

How could the compiler warn you that you depend on masking?

Consider this code:

f(A) ->
  <<A:16>>.

The compiler has no way of knowing whether masking is
needed or not.

We have no plans for changing how construction works in
OTP 19.


Regarding construction, note that signed/unsigned is
ignored. All of the following examples construct the
same binary:

<<255>>
<<-1>>
<<-1/signed>>
<<-1/unsigned>>

Since signed/unsigned has never been enforced
for construction, starting to warn for <<-1>> and
<<-1/unsigned>> would cause many new annoying
warnings. Therefore, no warnings should be
produced.

However, the following examples should produce
warnings:

<<-55555:8>>
<<100000:8>>

The two values above cannot be represented in
8 bits, which points to a real bug.

/Björn


--
Björn Gustavsson, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Bit syntax matching gotchas

zxq9-2
On 2016年2月3日 水曜日 16:06:49 Björn Gustavsson wrote:
> However, the following examples should produce
> warnings:
>
> <<-55555:8>>
> <<100000:8>>
>
> The two values above cannot be represented in
> 8 bits, which points to a real bug.

I have to admit that I've abused the bejesus out of this "bug" quite a bit
without ever considering it to be peculiar. I do remember being surprised
when I was first exploring Erlang and saw this happen, though:

  1> A = 10000.
  10000
  2> B = <<A>>.
  <<16>>

It made sense after a moment, especially once I played some more, but I
don't recall the peculiar properties of this ever being explained anywhere
in practical terms.

>How could the compiler warn you that you depend on masking?
>
>Consider this code:
>
>f(A) ->
>  <<A:16>>.

I suppose something like this would provide enough information:

  -spec f(<<_:32>>) -> <<_:16>>.
  f(A) ->
      <<A:16>>.

Or to be absolutely explicit:

  chop(In, Size) when is_binary(In) ->
      Mask = bit_size(In) - Size,
      <<_:Mask, Out:Size>> = In,
      <<Out:Size>>.

Is there a better way of doing that? I still expect to see things like
`<<Chopped:Size>> = SomeBin` all over the place.

Meh.

I do a fair amount of value assertion here and there in code, just not
usually with binary syntax involved (that is, I do `A = B`, but never
`<<A>> = <<B>>`). Some of the examples you presented have bizarre outcomes,
though. When `A /= A`, syntax aside, something is wrong with the world.

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Bit syntax matching gotchas

Ameretat Reith
In reply to this post by Björn Gustavsson-4
On Wed, 3 Feb 2016 07:17:02 +0100
Björn Gustavsson <[hidden email]> wrote:
 
> We have decided to try do something about it in OTP 19. We have
> discussed various solutions internally in the OTP group, and I have
> spent far too much time lately thinking about it.

Thanks for working on this.

> The reason I reject it is that the matching previously bound variables
> is uncommon. Even in the compiler test suites it is uncommon (test
> suites typically match bound variables more often than production code
> do).

Not that common but nothing prevents coder to write:

update_token(NewToken, ID) ->
  case NewToken of
    <<Time:16, _:PrefLen/bytes, ID:Len/bytes>> when (Now-Time) < 60
    ...

That looked logical to me and it took some time to understand I should
change my code to:

update_token(NewToken, ID) ->
  case NewToken of
    <<Time:16, _:PrefLen/bytes, ReceivedID/bytes>> when
      ReceivedID =:= <<ID:Len/bytes>>, (Now-Time) < 60


> Therefore, solution #2 would make behaviour of matching more
> consistent with construction, but would not significantly increase the
> number of correct programs. Also, if clauses that previously didn't
> match start to match, then code that has not been executed before will
> be executed.

I don't think this is very bad.  The code that now will be executed is
most probably intended by coder to be executed and it may solve a
hidden bug too.  My above code surely intended to match, otherwise why
I bothered myself to specify the size?

Alas, this change effects cannot warned to coder.

> YOUR INPUT?

Now that I know how matching and construction differ, I can accept
solution #1 and I prefer less language changes too.  But if language
correctness really matters, solution #2 is better.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Bit syntax matching gotchas

Björn Gustavsson-4
On Fri, Feb 5, 2016 at 1:35 AM, Ameretat Reith <[hidden email]> wrote:
> On Wed, 3 Feb 2016 07:17:02 +0100
> Björn Gustavsson <[hidden email]> wrote:
[...]

>> The reason I reject it is that the matching previously bound variables
>> is uncommon. Even in the compiler test suites it is uncommon (test
>> suites typically match bound variables more often than production code
>> do).
>
> Not that common but nothing prevents coder to write:
>
> update_token(NewToken, ID) ->
>   case NewToken of
>     <<Time:16, _:PrefLen/bytes, ID:Len/bytes>> when (Now-Time) < 60
>     ...
>
> That looked logical to me and it took some time to understand I should
> change my code to:
>
> update_token(NewToken, ID) ->
>   case NewToken of
>     <<Time:16, _:PrefLen/bytes, ReceivedID/bytes>> when
>       ReceivedID =:= <<ID:Len/bytes>>, (Now-Time) < 60

Your examples don't compile because of undefined variables.
Assuming that Len and PrefLen should be the same
variable, I don't see why you would need to change
from the first example to the second. It seems that
both of your examples would work if you fix the
unbound variables.

I did not write in may mail that matching of bound
variables will not work. I only wrote that we would not
add any automatic masking of integer values. That is,
the following example works fine:

t() ->
  t(16#FF, <<16#FF>>).

t(A, Bin) ->
  <<A:8>> = Bin.

In the following example there will be a badmatch exception:

t() ->
  t(16#FFFF, <<16#FF>>).

t(A, Bin) ->
  <<A:8>> = Bin.

Solution #2 that I rejected would have made the second
example match too.

/Björn

--
Björn Gustavsson, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Bit syntax matching gotchas

Richard A. O'Keefe-2
In reply to this post by Björn Gustavsson-4


On 3/02/16 7:17 pm, Björn Gustavsson wrote:
> There are some gotchas in the bit syntax that comes up now and then on
> the mailing list, and also as a bug report at the end of last year:
> http://bugs.erlang.org/browse/ERL-44

I am sorry to be so late replying to this, but things have been (a)
frantic and
(b) horrible.
> BACKGROUND ABOUT BIT SYNTAX CONSTRUCTION When constructing binaries,
> there is an implicit masking of the values. All of the following
> constructions give the same result: <<255>> <<16#FF>> <<16#FFFF>> <<-1>>

That always felt so WRONG to me.
If I *want* masking, I can write <<X band 16#FF>>.

I really do not understand why this kind of thing was ever
considered acceptable:

3> <<X>> = <<X>>.
** exception error: no match of right hand side value <<"ÿ">>

If you stop doing the masking (except where there is an explicit
'band' licensing it) then
(a) some modules will break
(b) the fix will be easy
(c) the fixed code will be backwards portable
> There have been complaints about the implicit masking behaviour, but
> there is a lot of code that depends on it, so it would be unwise to
> change it.

I don't buy that, sorry.

Make a new option:

-bit_syntax(safe|dangerous).

allowed once per module.  dangerous is the current behaviour,
safe raises an exception for overflow.

In R19, introduce it, with dangerous as the default.
In R20, make the compiler issue a warning if a module has a bit syntax
form that would be ambiguous and doesn't state the desired behaviour.
In R21, make safe the default.
In R22, make the compiler issue a warning if a module has
-bit_syntax(dangerous).
In R23, remove the option.

This process *FIXES* the problem.

Instead of safe/dangerous, consistent/inconsistent might be better.
> POSSIBLE SOLUTION #1 The most obvious solution is probably to let the
> compiler warn for the above cases. The matching would still fail. The
> developer will need to fix their code. For example: <<-1/signed>> =
> <<-1>> POSSIBLE SOLUTION #2 There is one problem with the solution #1.
> It is not possible to produce a warning for the following example:
> f(Val) -> <<Val:8>> = <<Val:8>>, Val.

Then solution #1 is not a solution.  But why isn't it possible?
The problem arises whenever you have <<...X:N...>> and
the compiler has no proof that X fits in N bits.  This is just
such a case.
> The proble So in addition to warning when possible, another solution
> is to mask values also when matching. Internally, the compiler could
> rewrite the function to something like: f(Val) -> <<NewVar:8>> =
> <<Val:8>>, Val = NewVar band 16#FF, Val. Similar rewriting should be
> done for literal integer, so the following expression would now match:
> <<-1>> = <<-1>>

What exactly is the rewriting?
0> <<NuVar>> = <<-1>>,
10> -1 = NuVar band 255.
** exception error: no match of right hand side value 255

That's not a match.
> Solution #1 would point all cases when literal integers could not
> possibly match and force the developer to fix them. Therefore I choose
> solution #1.

The problem is not a problem with literal integers.
It is a problem with ANYTHING that doesn't fit being quietly
truncated in one context but not the other.

Anything that leaves matching and building contexts
inconsistent is not a solution.  If a match cannot
*return* a value in a certain place, the corresponding
build should not *accept* that value in that place.


The idea that this can't be fixed because there is code
depending on the old behaviour reminds me of two famous
bugs.
(C) C's switch statement is a botch, with 'break' being
     used both for "exit this loop" and "exit this switch".
     This was fixed in C's grandparent BCPL where 'break'
     was used for "exit this loop" only and 'endcase' was
     used for "exit this switch only".  C's designers were
     aware of that correction to BCPL, but felt they could
     not adopt it because they "already had 100 users".
(X) Excel notoriously gets its leap year calculations wrong
     but Microsoft have announced that this feature will not
     be changed in case there are users who depend on the bug.
I'm also reminded of a bug that was squashed.
(B) Burroughs Algol has pointers.  That made it possible for
     you to write
         EBCDIC POINTER P;
         BEGIN
            EBCDIC ARRAY A[0:79];
            P := A;
         END;
     and then use P.  They didn't notice the problem for a while.
     They then made a temporary fix for the operating system so
     that when you exited a block that declared an array, the OS
     would sweep your stack looking for pointers to it.  They also
     made an addition to the language, so that you could write
         EBCDIC ARRAY B[0:131];
         EBCDIC POINTER P FOR B;
         BEGIN
            EBCDIC ARRAY A[0:79];
            P := A;  %% This is a syntax error!
         END;
     Customers were given about a year to fix their programs,
     then warnings were turned into hard errors and the OS patch
     was removed, and presto chango, absence of dangling pointers
     proved by the compilers.  Burroughs Algol is still available
     -- I have a personal copy of the MCP and software that runs
     in a VM on a Windows box; now all I need is a Windows box --
     and for 30 years that class of bugs has been GONE.

The C bug has been perpetuated into C++, Java,  and JavaScript and
people are *still* making 'break' mistakes, all because people chose
to perpetuate old bugs rather than eliminate them.

The longer any match/build inconsistency is allowed to remain
in bit syntax, the more pain it will cause.



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions