search

uwiger / sext

Sortable Erlang Term Serialization
Apache License 2.0
106 stars 52 forks source link

Failing property that checks sort order for proplists with {Atom, Val} pairs. #18

Closed jonmeredith closed 6 years ago

jonmeredith commented 8 years ago

I was playing with encoding proplists and found something odd with my testing. It generates proplists of [{Type, Val}] where Type is integer, float or binary and Val is something appropriate. Is this valid behavior? Seems like it should be.

CE1:

[[{float,0.0},{float,0.0},{int,0},{float,0.0}],
 [{float,0.0},{float,1.0},{int,0},{float,0.0}]]

CE2:

[[{float,0.0},{float,0.0},{int,1},{float,0.0},{float,0.0}],
 [{float,0.0},{float,0.0},{int,0},{float,0.0},{float,0.0}]]

CE3:

[[{float,0.0},{float,0.0},{float,0.0},{float,0.0},{int,0}],
 [{float,0.0},{float,-1.0},{float,0.0},{float,0.0},{int,0}]]
KeySeq = [{[{float,0.0},{float,-1.0},{float,0.0},{float,0.0},{int,0}],1},
          {[{float,0.0},{float,0.0},{float,0.0},{float,0.0},{int,0}],2}]
BinKeySeq = [{<<17,16,0,0,0,2,12,179,91,45,246,27,160,8,9,255,255,255,254,127,
                191,223,239,247,251,253,254,255,127,191,223,239,247,251,253,
                254,255,127,191,223,239,247,251,253,254,255,127,191,223,239,
                247,251,253,254,255,127,191,223,239,247,251,253,254,255,127,
                191,223,239,247,251,253,254,255,127,191,223,239,247,251,253,
                254,255,127,191,223,239,247,251,253,254,255,127,191,223,239,
                247,251,253,254,255,127,191,223,239,247,251,253,254,255,127,
                191,223,239,247,251,253,254,255,127,191,223,239,247,251,253,
                254,255,127,191,223,239,247,251,253,254,255,127,191,223,239,
                247,251,253,254,255,127,191,223,239,247,251,253,254,255,127,
                191,223,239,247,251,253,254,254,127,191,223,239,247,251,253,
                255,251,16,0,0,0,2,12,179,91,45,246,27,160,8,9,255,255,255,254,
                127,191,223,239,247,251,253,254,255,127,191,223,239,247,251,
                253,254,255,127,191,223,239,247,251,253,254,255,127,191,223,
                239,247,251,253,254,255,127,191,223,239,247,251,253,254,255,
                127,191,223,239,247,251,253,254,255,127,191,223,239,247,251,
                253,254,255,127,191,223,239,247,251,253,254,255,127,191,223,
                239,247,251,253,254,255,127,191,223,239,247,251,253,254,255,
                127,191,223,239,247,251,253,254,255,127,191,223,239,247,251,
                253,254,255,127,191,223,239,247,251,253,254,255,127,191,223,
                239,247,251,253,254,255,127,191,223,239,247,251,253,254,255,
                127,191,223,239,247,251,253,254,254,127,191,223,239,247,251,
                253,255,251,16,0,0,0,2,12,179,91,45,246,27,160,8,9,255,255,255,
                254,127,191,223,239,247,251,253,254,255,127,191,223,239,247,
                251,253,254,255,127,191,223,239,247,251,253,254,255,127,191,
                223,239,247,251,253,254,255,127,191,223,239,247,251,253,254,
                255,127,191,223,239,247,251,253,254,255,127,191,223,239,247,
                251,253,254,255,127,191,223,239,247,251,253,254,255,127,191,
                223,239,247,251,253,254,255,127,191,223,239,247,251,253,254,
                255,127,191,223,239,247,251,253,254,255,127,191,223,239,247,
                251,253,254,255,127,191,223,239,247,251,253,254,255,127,191,
                223,239,247,251,253,254,255,127,191,223,239,247,251,253,254,
                255,127,191,223,239,247,251,253,254,254,127,191,223,239,247,
                251,253,255,251,16,0,0,0,2,12,179,91,45,246,27,160,8,10,0,0,0,
                1,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,
                4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,
                32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,
                128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,
                2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,
                16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,1,128,
                64,32,16,8,4,2,0,4,16,0,0,0,2,12,180,219,174,128,8,10,0,0,0,0,2>>,
              2},
             {<<17,16,0,0,0,2,12,179,91,45,246,27,160,8,10,0,0,0,1,128,64,32,
                16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,
                64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,
                0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,
                4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,
                32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,
                128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,1,128,64,32,16,8,4,
                2,0,4,16,0,0,0,2,12,179,91,45,246,27,160,8,9,255,255,255,252,
                127,191,223,239,247,251,253,255,251,16,0,0,0,2,12,179,91,45,
                246,27,160,8,9,255,255,255,254,127,191,223,239,247,251,253,254,
                255,127,191,223,239,247,251,253,254,255,127,191,223,239,247,
                251,253,254,255,127,191,223,239,247,251,253,254,255,127,191,
                223,239,247,251,253,254,255,127,191,223,239,247,251,253,254,
                255,127,191,223,239,247,251,253,254,255,127,191,223,239,247,
                251,253,254,255,127,191,223,239,247,251,253,254,255,127,191,
                223,239,247,251,253,254,255,127,191,223,239,247,251,253,254,
                255,127,191,223,239,247,251,253,254,255,127,191,223,239,247,
                251,253,254,255,127,191,223,239,247,251,253,254,255,127,191,
                223,239,247,251,253,254,255,127,191,223,239,247,251,253,254,
                254,127,191,223,239,247,251,253,255,251,16,0,0,0,2,12,179,91,
                45,246,27,160,8,10,0,0,0,1,128,64,32,16,8,4,2,1,0,128,64,32,16,
                8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,
                32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,
                128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,
                2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,
                16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,64,32,16,8,4,2,1,0,128,
                64,32,16,8,4,2,1,1,128,64,32,16,8,4,2,0,4,16,0,0,0,2,12,180,
                219,174,128,8,10,0,0,0,0,2>>,
              1}]
[2,1] /= [1,2]
-> false
{ts,false}

Ran as

1> sext_eqc:run(10000, ts, fun sext_eqc:prop_sort_lists_of_tuples/0).
EQC test: ts (10000)... Starting Quviq QuickCheck version 1.36.1
   (compiled at {{2015,9,11},{11,37,51}})
Licence for Basho reserved until {{2015,11,17},{17,18,36}}
....................................................................................................(x10)....................................................................................................(x100)..............................................(x10).......(x1)....Failed! After 5775 tests.
uwiger commented 8 years ago

Hi Jon,

I don't have access to a full eqc version at the moment. However, when running some manual tests using uwiger/master, I think what you're seeing is the result of floats being extremely weird in terms of sorting and comparison.

Specifically, I notice that the first 0.0 in the first key is encoded as a ?neg4, whereas the same element in the second key is encoded as a ?pos4 (which is how it gets encoded each time I manually enter the term in the shell and call sext:encode/1).

Enjoy the hilarity:

1> B1 = <<17,16,0,0,0,2,12,179,91,45,246,27,160,8,9,255,255,255,254...>>.
...
%% The first encoded key from your example
2> Dec = sext:decode(B1).
[{float,0.0},{float,0.0},{float,0.0},{float,0.0},{int,0}]
3> sext:encode(Dec). 
<<17,16,0,0,0,2,12,179,91,45,246,27,160,8,9,255,255,255,
  254,127,191,223,239,247,251,253,254,255,127,...>>
%% i.e. same encoding
4> v(3) == B1.
true
5> Man = [{float,0.0},{float,0.0},{float,0.0},{float,0.0},{int,0}]. % copy-pasted from Dec
[{float,0.0},{float,0.0},{float,0.0},{float,0.0},{int,0}]
6> sext:encode(Man).
<<17,16,0,0,0,2,12,179,91,45,246,27,160,8,10,0,0,0,1,128,
  64,32,16,8,4,2,1,0,128,...>>
%% different encoding!!
7> Dec =:= Man.
true
22> sext:encode(Dec) == sext:encode(Man).
false

It's because of this sort of ambiguity that the sext eqc suite normalizes all floats using the bit syntax before running comparisons.