Home | History | Annotate | Download | only in m_debuginfo
      1 
      2 /*--------------------------------------------------------------------*/
      3 /*--- Representation of source level types.              tytypes.c ---*/
      4 /*--------------------------------------------------------------------*/
      5 
      6 /*
      7    This file is part of Valgrind, a dynamic binary instrumentation
      8    framework.
      9 
     10    Copyright (C) 2008-2017 OpenWorks LLP
     11       info (at) open-works.co.uk
     12 
     13    This program is free software; you can redistribute it and/or
     14    modify it under the terms of the GNU General Public License as
     15    published by the Free Software Foundation; either version 2 of the
     16    License, or (at your option) any later version.
     17 
     18    This program is distributed in the hope that it will be useful, but
     19    WITHOUT ANY WARRANTY; without even the implied warranty of
     20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     21    General Public License for more details.
     22 
     23    You should have received a copy of the GNU General Public License
     24    along with this program; if not, write to the Free Software
     25    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
     26    02111-1307, USA.
     27 
     28    The GNU General Public License is contained in the file COPYING.
     29 
     30    Neither the names of the U.S. Department of Energy nor the
     31    University of California nor the names of its contributors may be
     32    used to endorse or promote products derived from this software
     33    without prior written permission.
     34 */
     35 
     36 #include "pub_core_basics.h"
     37 #include "pub_core_debuginfo.h"
     38 #include "pub_core_libcassert.h"
     39 #include "pub_core_libcbase.h"
     40 #include "pub_core_libcprint.h"
     41 #include "pub_core_xarray.h"   /* to keep priv_tytypes.h happy */
     42 
     43 #include "priv_misc.h"         /* dinfo_zalloc/free/strdup */
     44 #include "priv_d3basics.h"     /* ML_(evaluate_Dwarf3_Expr) et al */
     45 #include "priv_tytypes.h"      /* self */
     46 
     47 
     48 /* Does this TyEnt denote a type, as opposed to some other kind of
     49    thing? */
     50 
     51 Bool ML_(TyEnt__is_type)( const TyEnt* te )
     52 {
     53    switch (te->tag) {
     54       case Te_EMPTY: case Te_INDIR: case Te_UNKNOWN:
     55       case Te_Atom:  case Te_Field: case Te_Bound:
     56          return False;
     57       case Te_TyBase:   case Te_TyPtr:     case Te_TyRef:
     58       case Te_TyPtrMbr: case Te_TyRvalRef: case Te_TyTyDef:
     59       case Te_TyStOrUn: case Te_TyEnum:    case Te_TyArray:
     60       case Te_TyFn:     case Te_TyQual:    case Te_TyVoid:
     61          return True;
     62       default:
     63          vg_assert(0);
     64    }
     65 }
     66 
     67 
     68 /* Print a TyEnt, debug-style. */
     69 
     70 static void pp_XArray_of_cuOffs ( const XArray* xa )
     71 {
     72    Word i;
     73    VG_(printf)("{");
     74    for (i = 0; i < VG_(sizeXA)(xa); i++) {
     75       UWord cuOff = *(UWord*)VG_(indexXA)(xa, i);
     76       VG_(printf)("0x%05lx", cuOff);
     77       if (i+1 < VG_(sizeXA)(xa))
     78          VG_(printf)(",");
     79    }
     80    VG_(printf)("}");
     81 }
     82 
     83 void ML_(pp_TyEnt)( const TyEnt* te )
     84 {
     85    VG_(printf)("0x%05lx  ", te->cuOff);
     86    switch (te->tag) {
     87       case Te_EMPTY:
     88          VG_(printf)("EMPTY");
     89          break;
     90       case Te_INDIR:
     91          VG_(printf)("INDIR(0x%05lx)", te->Te.INDIR.indR);
     92          break;
     93       case Te_UNKNOWN:
     94          VG_(printf)("UNKNOWN");
     95          break;
     96       case Te_Atom:
     97          VG_(printf)("Te_Atom(%s%lld,\"%s\")",
     98                      te->Te.Atom.valueKnown ? "" : "unknown:",
     99                      te->Te.Atom.value, te->Te.Atom.name);
    100          break;
    101       case Te_Field:
    102          if (te->Te.Field.nLoc == -1)
    103             VG_(printf)("Te_Field(ty=0x%05lx,pos.offset=%ld,\"%s\")",
    104                         te->Te.Field.typeR, te->Te.Field.pos.offset,
    105                         te->Te.Field.name ? te->Te.Field.name : "");
    106          else
    107             VG_(printf)("Te_Field(ty=0x%05lx,nLoc=%ld,pos.loc=%p,\"%s\")",
    108                         te->Te.Field.typeR, te->Te.Field.nLoc,
    109                         te->Te.Field.pos.loc,
    110                         te->Te.Field.name ? te->Te.Field.name : "");
    111          break;
    112       case Te_Bound:
    113          VG_(printf)("Te_Bound[");
    114          if (te->Te.Bound.knownL)
    115             VG_(printf)("%lld", te->Te.Bound.boundL);
    116          else
    117             VG_(printf)("??");
    118          VG_(printf)(",");
    119          if (te->Te.Bound.knownU)
    120             VG_(printf)("%lld", te->Te.Bound.boundU);
    121          else
    122             VG_(printf)("??");
    123          VG_(printf)("]");
    124          break;
    125       case Te_TyBase:
    126          VG_(printf)("Te_TyBase(%d,%c,\"%s\")",
    127                      te->Te.TyBase.szB, te->Te.TyBase.enc,
    128                      te->Te.TyBase.name ? te->Te.TyBase.name
    129                                         : "(null)" );
    130          break;
    131       case Te_TyPtr:
    132          VG_(printf)("Te_TyPtr(%d,0x%05lx)", te->Te.TyPorR.szB,
    133                      te->Te.TyPorR.typeR);
    134          break;
    135       case Te_TyRef:
    136          VG_(printf)("Te_TyRef(%d,0x%05lx)", te->Te.TyPorR.szB,
    137                      te->Te.TyPorR.typeR);
    138          break;
    139       case Te_TyPtrMbr:
    140          VG_(printf)("Te_TyMbr(%d,0x%05lx)", te->Te.TyPorR.szB,
    141                      te->Te.TyPorR.typeR);
    142          break;
    143       case Te_TyRvalRef:
    144          VG_(printf)("Te_TyRvalRef(%d,0x%05lx)", te->Te.TyPorR.szB,
    145                      te->Te.TyPorR.typeR);
    146          break;
    147       case Te_TyTyDef:
    148          VG_(printf)("Te_TyTyDef(0x%05lx,\"%s\")",
    149                      te->Te.TyTyDef.typeR,
    150                      te->Te.TyTyDef.name ? te->Te.TyTyDef.name
    151                                          : "" );
    152          break;
    153       case Te_TyStOrUn:
    154          if (te->Te.TyStOrUn.complete) {
    155             VG_(printf)("Te_TyStOrUn(%lu,%c,%p,\"%s\")",
    156                         te->Te.TyStOrUn.szB,
    157                         te->Te.TyStOrUn.isStruct ? 'S' : 'U',
    158                         te->Te.TyStOrUn.fieldRs,
    159                         te->Te.TyStOrUn.name ? te->Te.TyStOrUn.name
    160                                              : "" );
    161             pp_XArray_of_cuOffs( te->Te.TyStOrUn.fieldRs );
    162          } else {
    163             VG_(printf)("Te_TyStOrUn(INCOMPLETE,\"%s\")",
    164                         te->Te.TyStOrUn.name);
    165          }
    166          break;
    167       case Te_TyEnum:
    168          VG_(printf)("Te_TyEnum(%d,%p,\"%s\")",
    169                      te->Te.TyEnum.szB, te->Te.TyEnum.atomRs,
    170                      te->Te.TyEnum.name ? te->Te.TyEnum.name
    171                                         : "" );
    172          if (te->Te.TyEnum.atomRs)
    173             pp_XArray_of_cuOffs( te->Te.TyEnum.atomRs );
    174          break;
    175       case Te_TyArray:
    176          VG_(printf)("Te_TyArray(0x%05lx,%p)",
    177                      te->Te.TyArray.typeR, te->Te.TyArray.boundRs);
    178          if (te->Te.TyArray.boundRs)
    179             pp_XArray_of_cuOffs( te->Te.TyArray.boundRs );
    180          break;
    181       case Te_TyFn:
    182          VG_(printf)("Te_TyFn");
    183          break;
    184       case Te_TyQual:
    185          VG_(printf)("Te_TyQual(%c,0x%05lx)", te->Te.TyQual.qual,
    186                      te->Te.TyQual.typeR);
    187          break;
    188       case Te_TyVoid:
    189          VG_(printf)("Te_TyVoid%s",
    190                      te->Te.TyVoid.isFake ? "(fake)" : "");
    191          break;
    192       default:
    193          vg_assert(0);
    194    }
    195 }
    196 
    197 
    198 /* Print a whole XArray of TyEnts, debug-style */
    199 
    200 void ML_(pp_TyEnts)( const XArray* tyents, const HChar* who )
    201 {
    202    Word i, n;
    203    VG_(printf)("------ %s ------\n", who);
    204    n = VG_(sizeXA)( tyents );
    205    for (i = 0; i < n; i++) {
    206       const TyEnt* tyent = VG_(indexXA)( tyents, i );
    207       VG_(printf)("   [%5ld]  ", i);
    208       ML_(pp_TyEnt)( tyent );
    209       VG_(printf)("\n");
    210    }
    211 }
    212 
    213 
    214 /* Print a TyEnt, C style, chasing stuff as necessary. */
    215 
    216 static void pp_TyBound_C_ishly ( const XArray* tyents, UWord cuOff )
    217 {
    218    TyEnt* ent = ML_(TyEnts__index_by_cuOff)( tyents, NULL, cuOff );
    219    if (!ent) {
    220       VG_(printf)("**bounds-have-invalid-cuOff**");
    221       return;
    222    }
    223    vg_assert(ent->tag == Te_Bound);
    224    if (ent->Te.Bound.knownL && ent->Te.Bound.knownU
    225        && ent->Te.Bound.boundL == 0) {
    226       VG_(printf)("[%lld]", 1 + ent->Te.Bound.boundU);
    227    }
    228    else
    229    if (ent->Te.Bound.knownL && (!ent->Te.Bound.knownU)
    230        && ent->Te.Bound.boundL == 0) {
    231       VG_(printf)("[]");
    232    }
    233    else
    234       ML_(pp_TyEnt)( ent );
    235 }
    236 
    237 void ML_(pp_TyEnt_C_ishly)( const XArray* /* of TyEnt */ tyents,
    238                             UWord cuOff )
    239 {
    240    TyEnt* ent = ML_(TyEnts__index_by_cuOff)( tyents, NULL, cuOff );
    241    if (!ent) {
    242       VG_(printf)("**type-has-invalid-cuOff**");
    243       return;
    244    }
    245    switch (ent->tag) {
    246       case Te_TyBase:
    247          if (!ent->Te.TyBase.name) goto unhandled;
    248          VG_(printf)("%s", ent->Te.TyBase.name);
    249          break;
    250       case Te_TyPtr:
    251          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
    252          VG_(printf)("*");
    253          break;
    254       case Te_TyRef:
    255          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
    256          VG_(printf)("&");
    257          break;
    258       case Te_TyPtrMbr:
    259          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
    260          VG_(printf)("*");
    261          break;
    262       case Te_TyRvalRef:
    263          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
    264          VG_(printf)("&&");
    265          break;
    266       case Te_TyEnum:
    267          VG_(printf)("enum %s", ent->Te.TyEnum.name ? ent->Te.TyEnum.name
    268                                                     : "<anonymous>" );
    269          break;
    270       case Te_TyStOrUn:
    271          VG_(printf)("%s %s",
    272                      ent->Te.TyStOrUn.isStruct ? "struct" : "union",
    273                      ent->Te.TyStOrUn.name ? ent->Te.TyStOrUn.name
    274                                            : "<anonymous>" );
    275          break;
    276       case Te_TyArray:
    277          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyArray.typeR);
    278          if (ent->Te.TyArray.boundRs) {
    279             Word    w;
    280             XArray* xa = ent->Te.TyArray.boundRs;
    281             for (w = 0; w < VG_(sizeXA)(xa); w++) {
    282                pp_TyBound_C_ishly( tyents, *(UWord*)VG_(indexXA)(xa, w) );
    283             }
    284          } else {
    285             VG_(printf)("%s", "[??]");
    286          }
    287          break;
    288       case Te_TyTyDef:
    289          VG_(printf)("%s", ent->Te.TyTyDef.name ? ent->Te.TyTyDef.name
    290                                                 : "<anonymous>" );
    291          break;
    292       case Te_TyFn:
    293          VG_(printf)("%s", "<function_type>");
    294          break;
    295       case Te_TyQual:
    296          switch (ent->Te.TyQual.qual) {
    297             case 'C': VG_(printf)("const "); break;
    298             case 'V': VG_(printf)("volatile "); break;
    299             case 'R': VG_(printf)("restrict "); break;
    300             default: goto unhandled;
    301          }
    302          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyQual.typeR);
    303          break;
    304       case Te_TyVoid:
    305          VG_(printf)("%svoid",
    306                      ent->Te.TyVoid.isFake ? "fake" : "");
    307          break;
    308       case Te_UNKNOWN:
    309          ML_(pp_TyEnt)(ent);
    310          break;
    311       default:
    312          goto unhandled;
    313    }
    314    return;
    315 
    316   unhandled:
    317    VG_(printf)("pp_TyEnt_C_ishly:unhandled: ");
    318    ML_(pp_TyEnt)(ent);
    319    vg_assert(0);
    320 }
    321 
    322 
    323 /* 'ents' is an XArray of TyEnts, sorted by their .cuOff fields.  Find
    324    the entry which has .cuOff field as specified.  Returns NULL if not
    325    found.  Asserts if more than one entry has the specified .cuOff
    326    value. */
    327 
    328 void ML_(TyEntIndexCache__invalidate) ( TyEntIndexCache* cache )
    329 {
    330    Word i;
    331    for (i = 0; i < N_TYENT_INDEX_CACHE; i++) {
    332       cache->ce[i].cuOff0 = 0;    /* not actually necessary */
    333       cache->ce[i].ent0   = NULL; /* "invalid entry" */
    334       cache->ce[i].cuOff1 = 0;    /* not actually necessary */
    335       cache->ce[i].ent1   = NULL; /* "invalid entry" */
    336    }
    337 }
    338 
    339 TyEnt* ML_(TyEnts__index_by_cuOff) ( const XArray* /* of TyEnt */ ents,
    340                                      TyEntIndexCache* cache,
    341                                      UWord cuOff_to_find )
    342 {
    343    Bool  found;
    344    Word  first, last;
    345    TyEnt key, *res;
    346 
    347    /* crude stats, aggregated over all caches */
    348    static UWord cacheQs = 0 - 1;
    349    static UWord cacheHits = 0;
    350 
    351    if (0 && 0 == (cacheQs & 0xFFFF))
    352       VG_(printf)("cache: %'lu queries, %'lu misses\n",
    353                   cacheQs, cacheQs - cacheHits);
    354 
    355    if (LIKELY(cache != NULL)) {
    356       UWord h = cuOff_to_find % (UWord)N_TYENT_INDEX_CACHE;
    357       cacheQs++;
    358       // dude, like, way 0, dude.
    359       if (cache->ce[h].cuOff0 == cuOff_to_find && cache->ce[h].ent0 != NULL) {
    360          // dude, way 0 is a total hit!
    361          cacheHits++;
    362          return cache->ce[h].ent0;
    363       }
    364       // dude, check out way 1, dude.
    365       if (cache->ce[h].cuOff1 == cuOff_to_find && cache->ce[h].ent1 != NULL) {
    366          // way 1 hit
    367          UWord  tc;
    368          TyEnt* te;
    369          cacheHits++;
    370          // dude, way 1 is the new way 0.  move with the times, dude.
    371          tc = cache->ce[h].cuOff0;
    372          te = cache->ce[h].ent0;
    373          cache->ce[h].cuOff0 = cache->ce[h].cuOff1;
    374          cache->ce[h].ent0   = cache->ce[h].ent1;
    375          cache->ce[h].cuOff1 = tc;
    376          cache->ce[h].ent1   = te;
    377          return cache->ce[h].ent0;
    378       }
    379    }
    380 
    381    /* We'll have to do it the hard way */
    382    key.cuOff = cuOff_to_find;
    383    key.tag   = Te_EMPTY;
    384    found = VG_(lookupXA)( ents, &key, &first, &last );
    385    //found = VG_(lookupXA_UNBOXED)( ents, cuOff_to_find, &first, &last,
    386    //                               offsetof(TyEnt,cuOff) );
    387    if (!found)
    388       return NULL;
    389    /* If this fails, the array is invalid in the sense that there is
    390       more than one entry with .cuOff == cuOff_to_find. */
    391    vg_assert(first == last);
    392    res = (TyEnt*)VG_(indexXA)( ents, first );
    393 
    394    if (LIKELY(cache != NULL) && LIKELY(res != NULL)) {
    395       /* this is a bit stupid, computing this twice.  Oh well.
    396          Perhaps some magic gcc transformation will common them up.
    397          re "res != NULL", since .ent of NULL denotes 'invalid entry',
    398          we can't cache the result when res == NULL. */
    399       UWord h = cuOff_to_find % (UWord)N_TYENT_INDEX_CACHE;
    400       cache->ce[h].cuOff1 = cache->ce[h].cuOff0;
    401       cache->ce[h].ent1   = cache->ce[h].ent0;
    402       cache->ce[h].cuOff0 = cuOff_to_find;
    403       cache->ce[h].ent0   = res;
    404    }
    405 
    406    return res;
    407 }
    408 
    409 
    410 /* Generates a total ordering on TyEnts based only on their .cuOff
    411    fields. */
    412 
    413 Word ML_(TyEnt__cmp_by_cuOff_only) ( const TyEnt* te1, const TyEnt* te2 )
    414 {
    415    if (te1->cuOff < te2->cuOff) return -1;
    416    if (te1->cuOff > te2->cuOff) return 1;
    417    return 0;
    418 }
    419 
    420 
    421 /* Generates a total ordering on TyEnts based on everything except
    422    their .cuOff fields. */
    423 static inline Word UWord__cmp ( UWord a, UWord b ) {
    424    if (a < b) return -1;
    425    if (a > b) return 1;
    426    return 0;
    427 }
    428 static inline Word Long__cmp ( Long a, Long b ) {
    429    if (a < b) return -1;
    430    if (a > b) return 1;
    431    return 0;
    432 }
    433 static inline Word Bool__cmp ( Bool a, Bool b ) {
    434    vg_assert( ((UWord)a) <= 1 );
    435    vg_assert( ((UWord)b) <= 1 );
    436    if (a < b) return -1;
    437    if (a > b) return 1;
    438    return 0;
    439 }
    440 static inline Word UChar__cmp ( UChar a, UChar b ) {
    441    if (a < b) return -1;
    442    if (a > b) return 1;
    443    return 0;
    444 }
    445 static inline Word Int__cmp ( Int a, Int b ) {
    446    if (a < b) return -1;
    447    if (a > b) return 1;
    448    return 0;
    449 }
    450 static Word XArray_of_UWord__cmp ( const XArray* a, const XArray* b ) {
    451    Word i, r;
    452    Word aN = VG_(sizeXA)( a );
    453    Word bN = VG_(sizeXA)( b );
    454    if (aN < bN) return -1;
    455    if (aN > bN) return 1;
    456    for (i = 0; i < aN; i++) {
    457       r = UWord__cmp( *(UWord*)VG_(indexXA)( a, i ),
    458                       *(UWord*)VG_(indexXA)( b, i ) );
    459       if (r != 0) return r;
    460    }
    461    return 0;
    462 }
    463 static Word Bytevector__cmp ( const UChar* a, const UChar* b, Word n ) {
    464    Word i, r;
    465    vg_assert(n >= 0);
    466    for (i = 0; i < n; i++) {
    467       r = UChar__cmp( a[i], b[i] );
    468       if (r != 0) return r;
    469    }
    470    return 0;
    471 }
    472 static Word Asciiz__cmp ( const HChar* a, const HChar* b ) {
    473    /* A wrapper around strcmp that handles NULL strings safely. */
    474    if (a == NULL && b == NULL) return 0;
    475    if (a == NULL && b != NULL) return -1;
    476    if (a != NULL && b == NULL) return 1;
    477    return VG_(strcmp)(a, b);
    478 }
    479 
    480 Word ML_(TyEnt__cmp_by_all_except_cuOff) ( const TyEnt* te1, const TyEnt* te2 )
    481 {
    482    Word r;
    483    if (te1->tag < te2->tag) return -1;
    484    if (te1->tag > te2->tag) return 1;
    485    switch (te1->tag) {
    486    case Te_EMPTY:
    487       return 0;
    488    case Te_INDIR:
    489       r = UWord__cmp(te1->Te.INDIR.indR, te2->Te.INDIR.indR);
    490       return r;
    491    case Te_Atom:
    492       r = Bool__cmp(te1->Te.Atom.valueKnown, te2->Te.Atom.valueKnown);
    493       if (r != 0) return r;
    494       r = Long__cmp(te1->Te.Atom.value, te2->Te.Atom.value);
    495       if (r != 0) return r;
    496       r = Asciiz__cmp(te1->Te.Atom.name, te2->Te.Atom.name);
    497       return r;
    498    case Te_Field:
    499       r = Bool__cmp(te1->Te.Field.isStruct, te2->Te.Field.isStruct);
    500       if (r != 0) return r;
    501       r = UWord__cmp(te1->Te.Field.typeR, te2->Te.Field.typeR);
    502       if (r != 0) return r;
    503       r = Asciiz__cmp(te1->Te.Field.name, te2->Te.Field.name);
    504       if (r != 0) return r;
    505       r = UWord__cmp(te1->Te.Field.nLoc, te2->Te.Field.nLoc);
    506       if (r != 0) return r;
    507       if (te1->Te.Field.nLoc == -1)
    508          r = Long__cmp(te1->Te.Field.pos.offset, te2->Te.Field.pos.offset);
    509       else
    510          r = Bytevector__cmp(te1->Te.Field.pos.loc, te2->Te.Field.pos.loc,
    511                              te1->Te.Field.nLoc);
    512       return r;
    513    case Te_Bound:
    514       r = Bool__cmp(te1->Te.Bound.knownL, te2->Te.Bound.knownL);
    515       if (r != 0) return r;
    516       r = Bool__cmp(te1->Te.Bound.knownU, te2->Te.Bound.knownU);
    517       if (r != 0) return r;
    518       r = Long__cmp(te1->Te.Bound.boundL, te2->Te.Bound.boundL);
    519       if (r != 0) return r;
    520       r = Long__cmp(te1->Te.Bound.boundU, te2->Te.Bound.boundU);
    521       return r;
    522    case Te_TyBase:
    523       r = UChar__cmp(te1->Te.TyBase.enc, te2->Te.TyBase.enc);
    524       if (r != 0) return r;
    525       r = Int__cmp(te1->Te.TyBase.szB, te2->Te.TyBase.szB);
    526       if (r != 0) return r;
    527       r = Asciiz__cmp(te1->Te.TyBase.name, te2->Te.TyBase.name);
    528       return r;
    529    case Te_TyPtr:
    530    case Te_TyRef:
    531    case Te_TyPtrMbr:
    532    case Te_TyRvalRef:
    533       r = Int__cmp(te1->Te.TyPorR.szB, te2->Te.TyPorR.szB);
    534       if (r != 0) return r;
    535       r = UWord__cmp(te1->Te.TyPorR.typeR, te2->Te.TyPorR.typeR);
    536       return r;
    537    case Te_TyTyDef:
    538       r = UWord__cmp(te1->Te.TyTyDef.typeR, te2->Te.TyTyDef.typeR);
    539       if (r != 0) return r;
    540       r = Asciiz__cmp(te1->Te.TyTyDef.name, te2->Te.TyTyDef.name);
    541       return r;
    542    case Te_TyStOrUn:
    543       r = Bool__cmp(te1->Te.TyStOrUn.isStruct, te2->Te.TyStOrUn.isStruct);
    544       if (r != 0) return r;
    545       r = Bool__cmp(te1->Te.TyStOrUn.complete, te2->Te.TyStOrUn.complete);
    546       if (r != 0) return r;
    547       r = UWord__cmp(te1->Te.TyStOrUn.szB, te2->Te.TyStOrUn.szB);
    548       if (r != 0) return r;
    549       r = Asciiz__cmp(te1->Te.TyStOrUn.name, te2->Te.TyStOrUn.name);
    550       if (r != 0) return r;
    551       r = XArray_of_UWord__cmp(te1->Te.TyStOrUn.fieldRs,
    552                                te2->Te.TyStOrUn.fieldRs);
    553       return r;
    554    case Te_TyEnum:
    555       r = Int__cmp(te1->Te.TyEnum.szB, te2->Te.TyEnum.szB);
    556       if (r != 0) return r;
    557       r = Asciiz__cmp(te1->Te.TyEnum.name, te2->Te.TyEnum.name);
    558       if (r != 0) return r;
    559       r = XArray_of_UWord__cmp(te1->Te.TyEnum.atomRs, te2->Te.TyEnum.atomRs);
    560       return r;
    561    case Te_TyArray:
    562       r = UWord__cmp(te1->Te.TyArray.typeR, te2->Te.TyArray.typeR);
    563       if (r != 0) return r;
    564       r = XArray_of_UWord__cmp(te1->Te.TyArray.boundRs,
    565                                te2->Te.TyArray.boundRs);
    566       return r;
    567    case Te_TyFn:
    568       return 0;
    569    case Te_TyQual:
    570       r = UWord__cmp(te1->Te.TyQual.typeR, te2->Te.TyQual.typeR);
    571       if (r != 0) return r;
    572       r = UChar__cmp(te1->Te.TyQual.qual, te2->Te.TyQual.qual);
    573       return r;
    574    case Te_TyVoid:
    575       r = Bool__cmp(te1->Te.TyVoid.isFake, te2->Te.TyVoid.isFake);
    576       return r;
    577    default:
    578       vg_assert(0);
    579    }
    580 }
    581 
    582 
    583 /* Free up all directly or indirectly heap-allocated stuff attached to
    584    this TyEnt, and set its tag to Te_EMPTY.  The .cuOff field is
    585    unchanged. */
    586 
    587 void ML_(TyEnt__make_EMPTY) ( TyEnt* te )
    588 {
    589    UWord saved_cuOff;
    590    /* First, free up any fields in mallocville. */
    591    switch (te->tag) {
    592       case Te_EMPTY:
    593          break;
    594       case Te_INDIR:
    595          break;
    596       case Te_UNKNOWN:
    597          break;
    598       case Te_Atom:
    599          if (te->Te.Atom.name) ML_(dinfo_free)(te->Te.Atom.name);
    600          break;
    601       case Te_Field:
    602          if (te->Te.Field.name) ML_(dinfo_free)(te->Te.Field.name);
    603          if (te->Te.Field.nLoc > 0 && te->Te.Field.pos.loc)
    604             ML_(dinfo_free)(te->Te.Field.pos.loc);
    605          break;
    606       case Te_Bound:
    607          break;
    608       case Te_TyBase:
    609          if (te->Te.TyBase.name) ML_(dinfo_free)(te->Te.TyBase.name);
    610          break;
    611       case Te_TyPtr:
    612       case Te_TyRef:
    613       case Te_TyPtrMbr:
    614       case Te_TyRvalRef:
    615          break;
    616       case Te_TyTyDef:
    617          if (te->Te.TyTyDef.name) ML_(dinfo_free)(te->Te.TyTyDef.name);
    618          break;
    619       case Te_TyStOrUn:
    620          if (te->Te.TyStOrUn.name) ML_(dinfo_free)(te->Te.TyStOrUn.name);
    621          VG_(deleteXA)(te->Te.TyStOrUn.fieldRs);
    622          break;
    623       case Te_TyEnum:
    624          if (te->Te.TyEnum.name) ML_(dinfo_free)(te->Te.TyEnum.name);
    625          if (te->Te.TyEnum.atomRs) VG_(deleteXA)(te->Te.TyEnum.atomRs);
    626          break;
    627       case Te_TyArray:
    628          if (te->Te.TyArray.boundRs) VG_(deleteXA)(te->Te.TyArray.boundRs);
    629          break;
    630       case Te_TyFn:
    631          break;
    632       case Te_TyQual:
    633          break;
    634       case Te_TyVoid:
    635          break;
    636       default:
    637          vg_assert(0);
    638    }
    639    /* Now clear it out and set to Te_EMPTY. */
    640    saved_cuOff = te->cuOff;
    641    VG_(memset)(te, 0, sizeof(*te));
    642    te->cuOff = saved_cuOff;
    643    te->tag = Te_EMPTY;
    644 }
    645 
    646 
    647 /* How big is this type?  If .b in the returned struct is False, the
    648    size is unknown. */
    649 
    650 static MaybeULong mk_MaybeULong_Nothing ( void ) {
    651    MaybeULong mul;
    652    mul.ul = 0;
    653    mul.b  = False;
    654    return mul;
    655 }
    656 static MaybeULong mk_MaybeULong_Just ( ULong ul ) {
    657    MaybeULong mul;
    658    mul.ul = ul;
    659    mul.b  = True;
    660    return mul;
    661 }
    662 static MaybeULong mul_MaybeULong ( MaybeULong mul1, MaybeULong mul2 ) {
    663    if (!mul1.b) { vg_assert(mul1.ul == 0); return mul1; }
    664    if (!mul2.b) { vg_assert(mul2.ul == 0); return mul2; }
    665    mul1.ul *= mul2.ul;
    666    return mul1;
    667 }
    668 
    669 MaybeULong ML_(sizeOfType)( const XArray* /* of TyEnt */ tyents,
    670                             UWord cuOff )
    671 {
    672    Word       i;
    673    MaybeULong eszB;
    674    TyEnt*     ent = ML_(TyEnts__index_by_cuOff)(tyents, NULL, cuOff);
    675    TyEnt*     ent2;
    676    vg_assert(ent);
    677    vg_assert(ML_(TyEnt__is_type)(ent));
    678    switch (ent->tag) {
    679       case Te_TyBase:
    680          vg_assert(ent->Te.TyBase.szB > 0);
    681          return mk_MaybeULong_Just( ent->Te.TyBase.szB );
    682       case Te_TyQual:
    683          return ML_(sizeOfType)( tyents, ent->Te.TyQual.typeR );
    684       case Te_TyTyDef:
    685          ent2 = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    686                                             ent->Te.TyTyDef.typeR);
    687          vg_assert(ent2);
    688          if (ent2->tag == Te_UNKNOWN)
    689             return mk_MaybeULong_Nothing(); /*UNKNOWN*/
    690          return ML_(sizeOfType)( tyents, ent->Te.TyTyDef.typeR );
    691       case Te_TyPtr:
    692       case Te_TyRef:
    693       case Te_TyPtrMbr:
    694       case Te_TyRvalRef:
    695          vg_assert(ent->Te.TyPorR.szB == 4 || ent->Te.TyPorR.szB == 8);
    696          return mk_MaybeULong_Just( ent->Te.TyPorR.szB );
    697       case Te_TyStOrUn:
    698          return ent->Te.TyStOrUn.complete
    699                    ? mk_MaybeULong_Just( ent->Te.TyStOrUn.szB )
    700                    : mk_MaybeULong_Nothing();
    701       case Te_TyEnum:
    702          return mk_MaybeULong_Just( ent->Te.TyEnum.szB );
    703       case Te_TyArray:
    704          ent2 = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    705                                             ent->Te.TyArray.typeR);
    706          vg_assert(ent2);
    707          if (ent2->tag == Te_UNKNOWN)
    708             return mk_MaybeULong_Nothing(); /*UNKNOWN*/
    709          eszB = ML_(sizeOfType)( tyents, ent->Te.TyArray.typeR );
    710          for (i = 0; i < VG_(sizeXA)( ent->Te.TyArray.boundRs ); i++) {
    711             UWord bo_cuOff
    712                = *(UWord*)VG_(indexXA)(ent->Te.TyArray.boundRs, i);
    713             TyEnt* bo
    714               = ML_(TyEnts__index_by_cuOff)( tyents, NULL, bo_cuOff );
    715             vg_assert(bo);
    716             vg_assert(bo->tag == Te_Bound);
    717             if (!(bo->Te.Bound.knownL && bo->Te.Bound.knownU))
    718                return mk_MaybeULong_Nothing(); /*UNKNOWN*/
    719             eszB = mul_MaybeULong(
    720                       eszB,
    721                       mk_MaybeULong_Just( (ULong)(bo->Te.Bound.boundU
    722                                                   - bo->Te.Bound.boundL + 1) ));
    723          }
    724          return eszB;
    725       case Te_TyVoid:
    726          return mk_MaybeULong_Nothing(); /*UNKNOWN*/
    727       default:
    728          VG_(printf)("ML_(sizeOfType): unhandled: ");
    729          ML_(pp_TyEnt)(ent);
    730          VG_(printf)("\n");
    731          vg_assert(0);
    732    }
    733 }
    734 
    735 
    736 /* Describe where in the type 'offset' falls.  Caller must
    737    deallocate the resulting XArray. */
    738 
    739 static void copy_UWord_into_XA ( XArray* /* of HChar */ xa,
    740                                  UWord uw ) {
    741    HChar buf[32];     // large enough
    742    VG_(sprintf)(buf, "%lu", uw);
    743    VG_(addBytesToXA)( xa, buf, VG_(strlen)(buf));
    744 }
    745 
    746 XArray* /*HChar*/ ML_(describe_type)( /*OUT*/PtrdiffT* residual_offset,
    747                                       const XArray* /* of TyEnt */ tyents,
    748                                       UWord ty_cuOff,
    749                                       PtrdiffT offset )
    750 {
    751    TyEnt*  ty;
    752    XArray* xa = VG_(newXA)( ML_(dinfo_zalloc), "di.tytypes.dt.1",
    753                             ML_(dinfo_free),
    754                             sizeof(HChar) );
    755 
    756    ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL, ty_cuOff);
    757 
    758    while (True) {
    759       vg_assert(ty);
    760       vg_assert(ML_(TyEnt__is_type)(ty));
    761 
    762       switch (ty->tag) {
    763 
    764          /* These are all atomic types; there is nothing useful we can
    765             do. */
    766          case Te_TyEnum:
    767          case Te_TyFn:
    768          case Te_TyVoid:
    769          case Te_TyPtr:
    770          case Te_TyRef:
    771          case Te_TyPtrMbr:
    772          case Te_TyRvalRef:
    773          case Te_TyBase:
    774             goto done;
    775 
    776          case Te_TyStOrUn: {
    777             Word       i;
    778             GXResult   res;
    779             MaybeULong mul;
    780             XArray*    fieldRs;
    781             UWord      fieldR;
    782             TyEnt*     field = NULL;
    783             PtrdiffT   offMin = 0, offMax1 = 0;
    784             if (!ty->Te.TyStOrUn.isStruct) goto done;
    785             fieldRs = ty->Te.TyStOrUn.fieldRs;
    786             if (VG_(sizeXA)(fieldRs) == 0
    787                 && (ty->Te.TyStOrUn.typeR == 0)) goto done;
    788             for (i = 0; i < VG_(sizeXA)( fieldRs ); i++ ) {
    789                fieldR = *(UWord*)VG_(indexXA)( fieldRs, i );
    790                field = ML_(TyEnts__index_by_cuOff)(tyents, NULL, fieldR);
    791                vg_assert(field);
    792                vg_assert(field->tag == Te_Field);
    793                vg_assert(field->Te.Field.nLoc < 0
    794                          || (field->Te.Field.nLoc > 0
    795                              && field->Te.Field.pos.loc));
    796                if (field->Te.Field.nLoc == -1) {
    797                   res.kind = GXR_Addr;
    798                   res.word = field->Te.Field.pos.offset;
    799                } else {
    800                   /* Re data_bias in this call, we should really send in
    801                      a legitimate value.  But the expression is expected
    802                      to be a constant expression, evaluation of which
    803                      will not need to use DW_OP_addr and hence we can
    804                      avoid the trouble of plumbing the data bias through
    805                      to this point (if, indeed, it has any meaning; from
    806                      which DebugInfo would we take the data bias? */
    807                    res =  ML_(evaluate_Dwarf3_Expr)(
    808                           field->Te.Field.pos.loc, field->Te.Field.nLoc,
    809                           NULL/*fbGX*/, NULL/*RegSummary*/,
    810                           0/*data_bias*/,
    811                           True/*push_initial_zero*/);
    812                   if (0) {
    813                      VG_(printf)("QQQ ");
    814                      ML_(pp_GXResult)(res);
    815                      VG_(printf)("\n");
    816                   }
    817                }
    818                if (res.kind != GXR_Addr)
    819                   continue;
    820                mul = ML_(sizeOfType)( tyents, field->Te.Field.typeR );
    821                if (mul.b != True)
    822                   goto done; /* size of field is unknown (?!) */
    823                offMin  = res.word;
    824                offMax1 = offMin + (PtrdiffT)mul.ul;
    825                if (offMin == offMax1)
    826                   continue;
    827                vg_assert(offMin < offMax1);
    828                if (offset >= offMin && offset < offMax1)
    829                   break;
    830             }
    831             /* Did we find a suitable field? */
    832             vg_assert(i >= 0 && i <= VG_(sizeXA)( fieldRs ));
    833             if (i == VG_(sizeXA)( fieldRs )) {
    834                ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    835                                                    ty->Te.TyStOrUn.typeR);
    836                vg_assert(ty);
    837                if (ty->tag == Te_UNKNOWN) goto done;
    838                vg_assert(ML_(TyEnt__is_type)(ty));
    839                continue;
    840             }
    841             /* Yes.  'field' is it. */
    842             vg_assert(field);
    843             if (!field->Te.Field.name) goto done;
    844             VG_(addBytesToXA)( xa, ".", 1 );
    845             VG_(addBytesToXA)( xa, field->Te.Field.name,
    846                                VG_(strlen)(field->Te.Field.name) );
    847             offset -= offMin;
    848             ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    849                                              field->Te.Field.typeR );
    850             vg_assert(ty);
    851             if (ty->tag == Te_UNKNOWN) goto done;
    852             /* keep going; look inside the field. */
    853             break;
    854          }
    855 
    856          case Te_TyArray: {
    857             MaybeULong mul;
    858             UWord      size, eszB, ix;
    859             UWord      boundR;
    860             TyEnt*     elemTy;
    861             TyEnt*     bound;
    862             /* Just deal with the simple, common C-case: 1-D array,
    863                zero based, known size. */
    864             elemTy = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    865                                                  ty->Te.TyArray.typeR);
    866             vg_assert(elemTy);
    867             if (elemTy->tag == Te_UNKNOWN) goto done;
    868             vg_assert(ML_(TyEnt__is_type)(elemTy));
    869             if (!ty->Te.TyArray.boundRs)
    870                goto done;
    871             if (VG_(sizeXA)( ty->Te.TyArray.boundRs ) != 1) goto done;
    872             boundR = *(UWord*)VG_(indexXA)( ty->Te.TyArray.boundRs, 0 );
    873             bound = ML_(TyEnts__index_by_cuOff)(tyents, NULL, boundR);
    874             vg_assert(bound);
    875             vg_assert(bound->tag == Te_Bound);
    876             if (!(bound->Te.Bound.knownL && bound->Te.Bound.knownU
    877                   && bound->Te.Bound.boundL == 0
    878                   && bound->Te.Bound.boundU >= bound->Te.Bound.boundL))
    879                goto done;
    880             size = bound->Te.Bound.boundU - bound->Te.Bound.boundL + 1;
    881             vg_assert(size >= 1);
    882             mul = ML_(sizeOfType)( tyents, ty->Te.TyArray.typeR );
    883             if (mul.b != True)
    884                goto done; /* size of element type not known */
    885             eszB = mul.ul;
    886             if (eszB == 0) goto done;
    887             ix = offset / eszB;
    888             VG_(addBytesToXA)( xa, "[", 1 );
    889             copy_UWord_into_XA( xa, ix );
    890             VG_(addBytesToXA)( xa, "]", 1 );
    891             ty = elemTy;
    892             offset -= ix * eszB;
    893             /* keep going; look inside the array element. */
    894             break;
    895          }
    896 
    897          case Te_TyQual: {
    898             ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    899                                              ty->Te.TyQual.typeR);
    900             vg_assert(ty);
    901             if (ty->tag == Te_UNKNOWN) goto done;
    902             break;
    903          }
    904 
    905          case Te_TyTyDef: {
    906             ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    907                                              ty->Te.TyTyDef.typeR);
    908             vg_assert(ty);
    909             if (ty->tag == Te_UNKNOWN) goto done;
    910             break;
    911          }
    912 
    913          default: {
    914             VG_(printf)("ML_(describe_type): unhandled: ");
    915             ML_(pp_TyEnt)(ty);
    916             VG_(printf)("\n");
    917             vg_assert(0);
    918          }
    919 
    920       }
    921    }
    922 
    923   done:
    924    *residual_offset = offset;
    925    VG_(addBytesToXA)( xa, "\0", 1 );
    926    return xa;
    927 }
    928 
    929 /*--------------------------------------------------------------------*/
    930 /*--- end                                                tytypes.c ---*/
    931 /*--------------------------------------------------------------------*/
    932