From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 7E6F53858407; Thu, 3 Mar 2022 14:29:02 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7E6F53858407 From: "gprocida at google dot com" To: libabigail@sourceware.org Subject: [Bug default/28939] New: diff output is sensitive to implementation of std::sort Date: Thu, 03 Mar 2022 14:29:02 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: libabigail X-Bugzilla-Component: default X-Bugzilla-Version: unspecified X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: gprocida at google dot com X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Resolution: X-Bugzilla-Priority: P2 X-Bugzilla-Assigned-To: dodji at redhat dot com X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter cc target_milestone Message-ID: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://sourceware.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-BeenThere: libabigail@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Mailing list of the Libabigail project List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 03 Mar 2022 14:29:02 -0000 https://sourceware.org/bugzilla/show_bug.cgi?id=3D28939 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 w= ill 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. --=20 You are receiving this mail because: You are on the CC list for the bug.=