[Bug default/28939] New: diff output is sensitive to implementation of std::sort

[Bug default/28939] New: diff output is sensitive to implementation of std::sort

[gprocida at google dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=28939

            Bug ID: 28939
           Summary: diff output is sensitive to implementation of
                    std::sort
           Product: libabigail
           Version: unspecified
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: default
          Assignee: dodji at redhat dot com
          Reporter: gprocida at google dot com
                CC: libabigail at sourceware dot org
  Target Milestone: ---

I received a notification that at least one abidiff is sensitive to the
particular implementation of std::sort.

std::sort gives no guarantees as to the relative ordering of elements that
compare equal (!(a < b) && !(b < a)).

The comparison functor diff_less_than_functor only examines the first diff
subjects and in general there is no guarantee that sorting distinct diffs will
yield a consistent ordering.

The particular test case that was reported was this one:

--- tests/data/test-abidiff-exit/test-member-size-report0.txt   2022-01-30
18:02:19.412941913 -0800
+++ tests/output/test-abidiff-exit/test-member-size-report0.txt 2022-01-30
18:02:20.180941537 -0800
@@ -4,16 +4,15 @@
 2 functions with some indirect sub-type change:

   [C] 'function void reg1(S*, T*, T*)' at test-member-size-v1.cc:26:1 has some
indirect sub-type changes:
-    parameter 1 of type 'S*' has sub-type changes:
-      in pointed to type 'struct S' at test-member-size-v1.cc:3:1:
-        type size changed from 128 to 192 (in bits)
-        1 data member insertion:
-          'int y', at offset 128 (in bits) at test-member-size-v1.cc:6:1
-        no data member change (1 filtered);
-    parameter 2 of type 'T*' has sub-type changes:
+    parameter 3 of type 'T*' has sub-type changes:
       in pointed to type 'struct T' at test-member-size-v1.cc:14:1:
         type size changed from 192 to 256 (in bits)
-        1 data member changes (1 filtered):
+        2 data member changes:
+          type of 'S s' changed:
+            type size changed from 128 to 192 (in bits)
+            1 data member insertion:
+              'int y', at offset 128 (in bits) at test-member-size-v1.cc:6:1
+            no data member change (1 filtered);
           'int a' offset changed from 128 to 192 (in bits) (by +64 bits)


In general, dependence on the implementation of std::sort can be discovered by
randomising the input order before sorting.

There are two approaches to improving order stability:

1. increase the discrimination of the comparison function
2. use stable_sort

I'll try to post a patch that does both.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug default/28939] diff output is sensitive to implementation of std::sort

[gprocida at google dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=28939

--- Comment #1 from gprocida at google dot com ---
Patch posted for review at
https://sourceware.org/pipermail/libabigail/2022q1/004203.html.

-- 
You are receiving this mail because:
You are on the CC list for the bug.