[Bug default/26591] New: detect pathologically redundant types in abixml

[Bug default/26591] New: detect pathologically redundant types in abixml

[dodji at redhat dot com]

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

            Bug ID: 26591
           Summary: detect pathologically redundant types in abixml
           Product: libabigail
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: default
          Assignee: dodji at redhat dot com
          Reporter: dodji at redhat dot com
                CC: libabigail at sourceware dot org
  Target Milestone: ---

In general, a current version of libabigail tries hard to de-duplicate types. 
As a result, the idea is that abixml file have non-duplicated types.

This means that in theory, type ids as specified by the value of the attribute
id="type-id-xxxx" should be defined only once in the abixml file.

But then that is the theory.

In practice, there are cases where two types can have the same ID.  That
usually involves a sub-type.

For instance, sub-ranges of arrays are sub-types that are always part of array
types in C and C++ (In Ada, though, they can be a type on their own).  So
sub-ranges are duplicated in practice, but then I don't think that's a problem.

Another valid instance of duplicated type is when there are declaration-only
types, in C++, which have different member types.  For instance, a type Foo
might be declared in a header file with a member type Bar0;  then in another
header file, Foo might be declared again with another member type Bar1.  So
just to be able to define Bar0 and Bar1 in the abixml, we need to show declare
Foo twice, with the same type id.

In C++, I am guessing that the other "fair" case of duplicated ID would be
violations of the "One Definition Rule", because libabigail doesn't detect
these.

All other cases (included those listed here) of duplicated type IDs should be
detected so that they can be either documented or be flagged as being symptoms
a problem related to type comparison in libabigail.

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

[Bug default/26591] detect pathologically redundant types in abixml

[dodji at redhat dot com]

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

dodji at redhat dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

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

[Bug default/26591] detect pathologically redundant types in abixml

[dodji at redhat dot com]

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

--- Comment #1 from dodji at redhat dot com ---
Giuliano Procida wrote a one-liner script that finds duplicated IDs in all the
abixml files of the source distribution of libabigail.

It's a good start to audit the system and see why types are duplicated there.

Here is it:

find tests -name '*abi' | while read x; do sed -En "s;.* id='([^']*)'.*;\1;p"
$x | sort | uniq -c | grep -vw 1 | sort -nr | sed "s;^;$x: ;"; done

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida+abigail at google dot com]

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

Giuliano Procida <gprocida+abigail at google dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gprocida+abigail at google dot com

--- Comment #2 from Giuliano Procida <gprocida+abigail at google dot com> ---
This relates to current master, commit
8ae8dcb8d5b87dafd0b9fdd716654e4bf3284c95.

Looking for duplicate type ids in ABI XML (ignoring subranges)...

find tests -name '*.abi' -or -name '*.xml' | while read f; do <"$f" fgrep -v
'<subrange ' | sed -rn "s;.* id='([^']*)'.*;\1;p" | sort | uniq -c | sed 's;^
*;;' | grep -vw "^1" | sed "s;^;$f:;"; done

There are lots of duplicates (and exactly 2 of each type id seems to be a
common pattern). I saw one case where "void" type-id-4 had been emitted several
times.

However, duplicate type-ids being defined non-identically is a bit more serious
and we've noticed this in an internal bug report. Maybe canonicalisation has
gone wrong, the type definitions should have been merged, or some type elements
are just being emitted in the wrong places.

tests/data/test-read-dwarf/test12-pr18844.so.abi type-id-3888 (6 definitions)
is an example of this.

There seems to be a separate issue with anonymous types and duplicate type ids.
There are two identical definitions of type-id-2652 in
tests/data/test-diff-suppr/test45-abi.xml. However, they are contained in
(presumably identical) anonymous unions that have been given different internal
names.

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida+abigail at google dot com]

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

--- Comment #3 from Giuliano Procida <gprocida+abigail at google dot com> ---
This is a small but probably not minimal example to illustrate one issue
clearly.

If the use of a class member type (I've tried with both typedefs and classes)
appears before the class containing that type, then `abidw` ends up emitting
various types twice.

$ head -100 h.h a.cc b.cc
==> h.h <==
struct A {
  typedef int T1;
  typedef int T2;
};

==> a.cc <==
#include "h.h"

A::T1 Afun(A) { return 0; }

==> b.cc <==
#include "h.h"

struct B {
  typedef A::T2 T;
};

B::T Bfun(B) { return 0; }
$ g++ -Wall -Wextra -g -c a.cc
$ g++ -Wall -Wextra -g -c b.cc
$ g++ -Wall -Wextra -g --shared a.o b.o -o ab.so
$ g++ -Wall -Wextra -g --shared b.o a.o -o ba.so
$ build/tools/abidw ab.so | fgrep -v '<subrange ' | sed -rn "s;.*
id='([^']*)'.*;\1;p" | sort | uniq -c | sed 's;^ *;;' | grep -vw "^1"
$ build/tools/abidw ba.so | fgrep -v '<subrange ' | sed -rn "s;.*
id='([^']*)'.*;\1;p" | sort | uniq -c | sed 's;^ *;;' | grep -vw "^1"
2 type-id-1
2 type-id-2
2 type-id-3
2 type-id-4
$ build/tools/abidw a.o | grep typedef-decl
        <typedef-decl name='T1' type-id='type-id-1' filepath='.../h.h' line='2'
column='1' id='type-id-3'/>
$ build/tools/abidw b.o | grep typedef-decl
        <typedef-decl name='T' type-id='type-id-4' filepath='.../b.cc' line='4'
column='1' id='type-id-3'/>
        <typedef-decl name='T2' type-id='type-id-1' filepath='.../h.h' line='3'
column='1' id='type-id-4'/>

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida+abigail at google dot com]

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

--- Comment #4 from Giuliano Procida <gprocida+abigail at google dot com> ---
Here's a slightly smaller example.

$ head -10 h.h a.cc b.cc
==> h.h <==
struct A {
  typedef int T2;
};

==> a.cc <==
#include "h.h"

A::T2 Afun(A) { return 0; }

==> b.cc <==
#include "h.h"

struct B {
  typedef A::T2 T;
};

B::T Bfun(B) { return 0; }

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida+abigail at google dot com]

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

--- Comment #5 from Giuliano Procida <gprocida+abigail at google dot com> ---
And an even smaller one:

$ head -10 a.cc b.cc
==> a.cc <==
struct A { typedef int T; };
A::T Afun(A) { return 0; }

==> b.cc <==
struct A { typedef int T; };
A::T Bfun() { return 0; }

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida+abigail at google dot com]

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

--- Comment #6 from Giuliano Procida <gprocida+abigail at google dot com> ---
One of the worst cases of duplicate type ids being used for different types
(genuinely different it seems, not fragments of each other) is type-id-60 in
tests/data/test-read-dwarf/PR22122-libftdc.so.

This is a snippet of abidw tests/data/test-read-dwarf/PR22122-libftdc.so |
c++filt.

      <class-decl name='__anonymous_struct__' is-anonymous='yes'
visibility='default' is-declaration-only='yes' id='type-id-60'>
        <member-function access='public'>
          <function-decl name='intrusive_ptr'
mangled-name='boost::intrusive_ptr<mongo::SharedBuffer::Holder>::intrusive_ptr()'
filepath='src/third_party/boost-1.60.0/boost/smart_ptr/intrusive_ptr.hpp'
line='62' column='1' visibility='default' binding='global' size-in-bits='64'>
            <parameter type-id='type-id-63' is-artificial='yes'/>
            <return type-id='type-id-26'/>
          </function-decl>
        </member-function>
        <member-function access='public' destructor='yes'>
          <function-decl name='~intrusive_ptr'
mangled-name='boost::intrusive_ptr<mongo::SharedBuffer::Holder>::~intrusive_ptr()'
filepath='src/third_party/boost-1.60.0/boost/smart_ptr/intrusive_ptr.hpp'
line='95' column='1' visibility='default' binding='global' size-in-bits='64'>
            <parameter type-id='type-id-63' is-artificial='yes'/>
            <return type-id='type-id-26'/>
          </function-decl>
        </member-function>
      </class-decl>
      <class-decl name='__anonymous_struct__1' is-anonymous='yes'
visibility='default' is-declaration-only='yes' id='type-id-60'>
        <member-type access='private'>
          <typedef-decl name='rval_reference_type' type-id='type-id-152'
filepath='src/third_party/boost-1.60.0/boost/optional/optional.hpp' line='777'
column='1' id='type-id-153'/>
        </member-type>
        <member-function access='public'>
          <function-decl name='optional'
mangled-name='boost::optional<std::vector<mongo::BSONObj,
std::allocator<mongo::BSONObj> > >::optional()'
filepath='src/third_party/boost-1.60.0/boost/optional/optional.hpp' line='786'
column='1' visibility='default' binding='global' size-in-bits='64'>
            <parameter type-id='type-id-63' is-artificial='yes'/>
            <return type-id='type-id-26'/>
          </function-decl>
        </member-function>
        <member-function access='public'>
          <function-decl name='optional'
mangled-name='boost::optional<mongo::FTDCBSONUtil::FTDCType>::optional(mongo::FTDCBSONUtil::FTDCType&&)'
filepath='src/third_party/boost-1.60.0/boost/optional/optional.hpp' line='799'
column='1' visibility='default' binding='global' size-in-bits='64'>
            <parameter type-id='type-id-63' is-artificial='yes'/>
            <parameter type-id='type-id-153'/>
            <return type-id='type-id-26'/>
          </function-decl>
        </member-function>
      </class-decl>

Both are anonymous, declaration-only classes but contain member functions that
clearly belong to named, defined templated types.

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida+abigail at google dot com]

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

--- Comment #7 from Giuliano Procida <gprocida+abigail at google dot com> ---
More regarding comment 6.

There is special coding in the XML reader (!is_decl_only) which causes any
subelements of declaration-only types to be completely ignored.

So we could prune such pieces from the XML without changing existing behaviour.
However, if I disable the special coding, abidiff starts tripping up on
invisible differences.

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida+abigail at google dot com]

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

--- Comment #8 from Giuliano Procida <gprocida+abigail at google dot com> ---
I am trying to tackle one source of duplicate type ids: write_decl_in_scope.

The current behaviour likely reflects an implicit design choice, one which I
would like some clarification on. Consider the case of code like this:

= test.h =
struct N {
 struct A {
  struct B {
   typedef int C;
   ...
  };
  ...
 };
 ...
};

= foo.cc =
N::A::B::C foo;

= bar.cc =
N::A::B bar;

The variable foo has a type which doesn't depend on the "...", but B depends on
the first "..." but not the later ones.

If foo were the only symbol, we would could choose to omit the other bits of
the types. (I'm not sure if libabigail does this.)

If bar were the only symbol, we should emit B's definition in full, but could
chose to omit the rest of A. (libabigail actually omits C, but it could be like
that in the DWARF.)

If both foo and bar are processed in that order, it would be good not to
duplicate the definition of C. libabigail currently does duplicate this.
There's no duplication if bar precedes foo.

I see two ways forward:

1. Somehow work out that an enclosing type definition will be emitted anyway
(so just emit that instead, now or later). I can see this being a bit tricky
with multiply-nested types. However, there is probably some existing logic
there already (compare ABIs from g++ -Wall -Wextra -g -shared foo.cc bar.cc -o
test.o and g++ -Wall -Wextra -g -shared bar.cc foo.cc -o test.o).

2. Always emit the outermost enclosing types, now, and not later. This will
make some ABI files larger but should stop there being multiple definitions of
types like C. In the case of the foo, bar example, this would mean additionally
exposing the last "..." in the ABI, even if it's not directly reachable from
the symbols.

I have a tentative patch that does 2. I'll post it for review soon.

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida+abigail at google dot com]

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

--- Comment #9 from Giuliano Procida <gprocida+abigail at google dot com> ---
The tentative patch is here
https://github.com/myxoid/libabigail/commits/xml-writer-cleanup. It's a bit too
large to post due to the impact on test files.

The actual commit is currently
https://github.com/myxoid/libabigail/commit/e127d893ee415f5bdbe5a972047a483c3c9df5ee.

Let me know what you think. Thanks.

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida at google dot com]

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

gprocida at google dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gprocida at google dot com

--- Comment #10 from gprocida at google dot com ---
Dodji, I think your recent changes may have cleared up at least some of these.

I may be worth running the shell fragment in comment 1 going back 20 commits or
so, to see what progress has been like.

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

[Bug default/26591] detect pathologically redundant types in abixml

[maennich at android dot com]

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

Matthias Maennich <maennich at android dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |maennich at android dot com

--- Comment #11 from Matthias Maennich <maennich at android dot com> ---
Hi Dodji,

We came across this as we were digging into an unrelated issue.

The duplicate types mentioned in comment 6 appear to correlate to
DW_AT_signature (part of DWARF 4 type units - see
https://dwarfstd.org/ShowIssue.php?issue=080930.1). The test files
that make use of this feature are:

tests/data/test-read-dwarf/test15-pr18892.so - GCC 4.9.2
tests/data/test-read-dwarf/libtest23.so - GCC 4.8.5
tests/data/test-read-dwarf/PR22122-libftdc.so - Clang 3.9.1

abidw gets incomplete type information as a result.

LLVM added support to LLDB's DWARF parser here:
https://reviews.llvm.org/D62246.

The feature doesn't currently appear in Android binaries (kernel or framework
libraries).

Both GCC and Clang appear to require -fdebug-types-section to enable
this feature. At least it should be straightforward doing with /
without comparisons.

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

[Bug default/26591] detect pathologically redundant types in abixml

[mark at klomp dot org]

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

Mark Wielaard <mark at klomp dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mark at klomp dot org

--- Comment #12 from Mark Wielaard <mark at klomp dot org> ---
(In reply to Matthias Maennich from comment #11)
> We came across this as we were digging into an unrelated issue.
> 
> The duplicate types mentioned in comment 6 appear to correlate to
> DW_AT_signature (part of DWARF 4 type units - see
> https://dwarfstd.org/ShowIssue.php?issue=080930.1). The test files
> that make use of this feature are:
> 
> tests/data/test-read-dwarf/test15-pr18892.so - GCC 4.9.2
> tests/data/test-read-dwarf/libtest23.so - GCC 4.8.5
> tests/data/test-read-dwarf/PR22122-libftdc.so - Clang 3.9.1
> 
> abidw gets incomplete type information as a result.

Is there a specific bug for handling debug_types?

libdw should handle these just fine without the program even needing to know
about the different section type. dwarf_formref_die () will return a Dwarf_Die
however the attribute refers to it (if it uses a signature then that gets
looked up internally by libdw).

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida at google dot com]

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

--- Comment #13 from gprocida at google dot com ---
In recent testing, we've only noticed trouble with
tests/data/test-read-dwarf/PR22122-libftdc.so.

So perhaps it's the combination of debug_types and Clang (3.9.1) that is the
issue.

I didn't find anything libabigail-specific for debug_types in Bugzilla.

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

[Bug default/26591] detect pathologically redundant types in abixml

[gprocida at google dot com]

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

--- Comment #14 from gprocida at google dot com ---
I made a tiny start on this:

static Dwarf_Die*
check_signature(Dwarf_Die* die, Dwarf_Die* signature_die)
{
  Dwarf_Attribute attr;
  return die && dwarf_attr_integrate(die, DW_AT_signature, &attr)
      && dwarf_formref_die(&attr, signature_die) ? signature_die : die;
}

and then in build_ir_node_from_die:

  Dwarf_Die signature;
  die = check_signature(die, &signature);

However, it breaks assumptions about canonical DIEs. Or at least, I get
assertion failures in compute_canonical_die:

    ABG_ASSERT(dwarf_offdie(dwarf_per_die_source(source), die_offset, &die));

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