gdb/dwarf2/cooked-index.h

   1 /* DIE indexing
   2
   3    Copyright (C) 2022-2023 Free Software Foundation, Inc.
   4
   5    This file is part of GDB.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef GDB_DWARF2_COOKED_INDEX_H
  21 #define GDB_DWARF2_COOKED_INDEX_H
  22
  23 #include "dwarf2.h"
  24 #include "dwarf2/types.h"
  25 #include "symtab.h"
  26 #include "hashtab.h"
  27 #include "dwarf2/index-common.h"
  28 #include "gdbsupport/gdb_string_view.h"
  29 #include "quick-symbol.h"
  30 #include "gdbsupport/gdb_obstack.h"
  31 #include "addrmap.h"
  32 #include "gdbsupport/iterator-range.h"
  33 #include "gdbsupport/thread-pool.h"
  34 #include "dwarf2/mapped-index.h"
  35 #include "dwarf2/tag.h"
  36 #include "gdbsupport/range-chain.h"
  37
  38 struct dwarf2_per_cu_data;
  39 struct dwarf2_per_bfd;
  40
  41 /* Flags that describe an entry in the index.  */
  42 enum cooked_index_flag_enum : unsigned char
  43 {
  44   /* True if this entry is the program's "main".  */
  45   IS_MAIN = 1,
  46   /* True if this entry represents a "static" object.  */
  47   IS_STATIC = 2,
  48   /* True if this entry is an "enum class".  */
  49   IS_ENUM_CLASS = 4,
  50   /* True if this entry uses the linkage name.  */
  51   IS_LINKAGE = 8,
  52   /* True if this entry is just for the declaration of a type, not the
  53      definition.  */
  54   IS_TYPE_DECLARATION = 16,
  55 };
  56 DEF_ENUM_FLAGS_TYPE (enum cooked_index_flag_enum, cooked_index_flag);
  57
  58 /* Return a string representation of FLAGS.  */
  59
  60 std::string to_string (cooked_index_flag flags);
  61
  62 /* Return true if LANG requires canonicalization.  This is used
  63    primarily to work around an issue computing the name of "main".
  64    This function must be kept in sync with
  65    cooked_index_shard::do_finalize.  */
  66
  67 extern bool language_requires_canonicalization (enum language lang);
  68
  69 /* A cooked_index_entry represents a single item in the index.  Note
  70    that two entries can be created for the same DIE -- one using the
  71    name, and another one using the linkage name, if any.
  72
  73    This is an "open" class and the members are all directly
  74    accessible.  It is read-only after the index has been fully read
  75    and processed.  */
  76 struct cooked_index_entry : public allocate_on_obstack
  77 {
  78   cooked_index_entry (sect_offset die_offset_, enum dwarf_tag tag_,
  79                       cooked_index_flag flags_, const char *name_,
  80                       const cooked_index_entry *parent_entry_,
  81                       dwarf2_per_cu_data *per_cu_)
  82     : name (name_),
  83       tag (tag_),
  84       flags (flags_),
  85       die_offset (die_offset_),
  86       parent_entry (parent_entry_),
  87       per_cu (per_cu_)
  88   {
  89   }
  90
  91   /* Return true if this entry matches SEARCH_FLAGS.  */
  92   bool matches (block_search_flags search_flags) const
  93   {
  94     /* Just reject type declarations.  */
  95     if ((flags & IS_TYPE_DECLARATION) != 0)
  96       return false;
  97
  98     if ((search_flags & SEARCH_STATIC_BLOCK) != 0
  99         && (flags & IS_STATIC) != 0)
 100       return true;
 101     if ((search_flags & SEARCH_GLOBAL_BLOCK) != 0
 102         && (flags & IS_STATIC) == 0)
 103       return true;
 104     return false;
 105   }
 106
 107   /* Return true if this entry matches DOMAIN.  */
 108   bool matches (domain_enum domain) const
 109   {
 110     /* Just reject type declarations.  */
 111     if ((flags & IS_TYPE_DECLARATION) != 0)
 112       return false;
 113
 114     switch (domain)
 115       {
 116       case LABEL_DOMAIN:
 117         return false;
 118
 119       case MODULE_DOMAIN:
 120         return tag == DW_TAG_module;
 121
 122       case COMMON_BLOCK_DOMAIN:
 123         return tag == DW_TAG_common_block;
 124       }
 125
 126     return true;
 127   }
 128
 129   /* Return true if this entry matches KIND.  */
 130   bool matches (enum search_domain kind) const
 131   {
 132     /* Just reject type declarations.  */
 133     if ((flags & IS_TYPE_DECLARATION) != 0)
 134       return false;
 135
 136     switch (kind)
 137       {
 138       case VARIABLES_DOMAIN:
 139         return (tag == DW_TAG_variable
 140                 || tag == DW_TAG_constant
 141                 || tag == DW_TAG_enumerator);
 142       case FUNCTIONS_DOMAIN:
 143         return tag == DW_TAG_subprogram;
 144       case TYPES_DOMAIN:
 145         return tag_is_type (tag);
 146       case MODULES_DOMAIN:
 147         return tag == DW_TAG_module;
 148       }
 149
 150     return true;
 151   }
 152
 153   /* Construct the fully-qualified name of this entry and return a
 154      pointer to it.  If allocation is needed, it will be done on
 155      STORAGE.  FOR_MAIN is true if we are computing the name of the
 156      "main" entry -- one marked DW_AT_main_subprogram.  This matters
 157      for avoiding name canonicalization and also a related race (if
 158      "main" computation is done during finalization).  */
 159   const char *full_name (struct obstack *storage, bool for_main = false) const;
 160
 161   /* Comparison modes for the 'compare' function.  See the function
 162      for a description.  */
 163   enum comparison_mode
 164   {
 165     MATCH,
 166     SORT,
 167     COMPLETE,
 168   };
 169
 170   /* Compare two strings, case-insensitively.  Return -1 if STRA is
 171      less than STRB, 0 if they are equal, and 1 if STRA is greater.
 172
 173      When comparing, '<' is considered to be less than all other
 174      printable characters.  This ensures that "t<x>" sorts before
 175      "t1", which is necessary when looking up "t".  This '<' handling
 176      is to ensure that certain C++ lookups work correctly.  It is
 177      inexact, and applied regardless of the search language, but this
 178      is ok because callers of this code do more precise filtering
 179      according to their needs.  This is also why using a
 180      case-insensitive comparison works even for languages that are
 181      case sensitive.
 182
 183      MODE controls how the comparison proceeds.
 184
 185      MODE==SORT is used when sorting and the only special '<' handling
 186      that it does is to ensure that '<' sorts before all other
 187      printable characters.  This ensures that the resulting ordering
 188      will be binary-searchable.
 189
 190      MODE==MATCH is used when searching for a symbol.  In this case,
 191      STRB must always be the search name, and STRA must be the name in
 192      the index that is under consideration.  In compare mode, early
 193      termination of STRB may match STRA -- for example, "t<int>" and
 194      "t" will be considered to be equal.  (However, if A=="t" and
 195      B=="t<int>", then this will not consider them as equal.)
 196
 197      MODE==COMPLETE is used when searching for a symbol for
 198      completion.  In this case, STRB must always be the search name,
 199      and STRA must be the name in the index that is under
 200      consideration.  In completion mode, early termination of STRB
 201      always results in a match.  */
 202   static int compare (const char *stra, const char *strb,
 203                       comparison_mode mode);
 204
 205   /* Compare two entries by canonical name.  */
 206   bool operator< (const cooked_index_entry &other) const
 207   {
 208     return compare (canonical, other.canonical, SORT) < 0;
 209   }
 210
 211   /* The name as it appears in DWARF.  This always points into one of
 212      the mapped DWARF sections.  Note that this may be the name or the
 213      linkage name -- two entries are created for DIEs which have both
 214      attributes.  */
 215   const char *name;
 216   /* The canonical name.  For C++ names, this may differ from NAME.
 217      In all other cases, this is equal to NAME.  */
 218   const char *canonical = nullptr;
 219   /* The DWARF tag.  */
 220   enum dwarf_tag tag;
 221   /* Any flags attached to this entry.  */
 222   cooked_index_flag flags;
 223   /* The offset of this DIE.  */
 224   sect_offset die_offset;
 225   /* The parent entry.  This is NULL for top-level entries.
 226      Otherwise, it points to the parent entry, such as a namespace or
 227      class.  */
 228   const cooked_index_entry *parent_entry;
 229   /* The CU from which this entry originates.  */
 230   dwarf2_per_cu_data *per_cu;
 231
 232 private:
 233
 234   /* A helper method for full_name.  Emits the full scope of this
 235      object, followed by the separator, to STORAGE.  If this entry has
 236      a parent, its write_scope method is called first.  */
 237   void write_scope (struct obstack *storage, const char *sep,
 238                     bool for_name) const;
 239 };
 240
 241 class cooked_index;
 242
 243 /* An index of interesting DIEs.  This is "cooked", in contrast to a
 244    mapped .debug_names or .gdb_index, which are "raw".  An entry in
 245    the index is of type cooked_index_entry.
 246
 247    Operations on the index are described below.  They are chosen to
 248    make it relatively simple to implement the symtab "quick"
 249    methods.  */
 250 class cooked_index_shard
 251 {
 252 public:
 253   cooked_index_shard () = default;
 254   DISABLE_COPY_AND_ASSIGN (cooked_index_shard);
 255
 256   /* Create a new cooked_index_entry and register it with this object.
 257      Entries are owned by this object.  The new item is returned.  */
 258   const cooked_index_entry *add (sect_offset die_offset, enum dwarf_tag tag,
 259                                  cooked_index_flag flags,
 260                                  const char *name,
 261                                  const cooked_index_entry *parent_entry,
 262                                  dwarf2_per_cu_data *per_cu);
 263
 264   /* Install a new fixed addrmap from the given mutable addrmap.  */
 265   void install_addrmap (addrmap_mutable *map)
 266   {
 267     gdb_assert (m_addrmap == nullptr);
 268     m_addrmap = new (&m_storage) addrmap_fixed (&m_storage, map);
 269   }
 270
 271   /* Finalize the index.  This should be called a single time, when
 272      the index has been fully populated.  It enters all the entries
 273      into the internal table.  */
 274   void finalize ();
 275
 276   /* Wait for this index's finalization to be complete.  */
 277   void wait (bool allow_quit = true) const;
 278
 279   friend class cooked_index;
 280
 281   /* A simple range over part of m_entries.  */
 282   typedef iterator_range<std::vector<cooked_index_entry *>::const_iterator>
 283        range;
 284
 285   /* Return a range of all the entries.  */
 286   range all_entries () const
 287   {
 288     wait ();
 289     return { m_entries.cbegin (), m_entries.cend () };
 290   }
 291
 292   /* Look up an entry by name.  Returns a range of all matching
 293      results.  If COMPLETING is true, then a larger range, suitable
 294      for completion, will be returned.  */
 295   range find (const std::string &name, bool completing) const;
 296
 297 private:
 298
 299   /* Return the entry that is believed to represent the program's
 300      "main".  This will return NULL if no such entry is available.  */
 301   const cooked_index_entry *get_main () const
 302   {
 303     return m_main;
 304   }
 305
 306   /* Look up ADDR in the address map, and return either the
 307      corresponding CU, or nullptr if the address could not be
 308      found.  */
 309   dwarf2_per_cu_data *lookup (CORE_ADDR addr)
 310   {
 311     return static_cast<dwarf2_per_cu_data *> (m_addrmap->find (addr));
 312   }
 313
 314   /* Create a new cooked_index_entry and register it with this object.
 315      Entries are owned by this object.  The new item is returned.  */
 316   cooked_index_entry *create (sect_offset die_offset,
 317                               enum dwarf_tag tag,
 318                               cooked_index_flag flags,
 319                               const char *name,
 320                               const cooked_index_entry *parent_entry,
 321                               dwarf2_per_cu_data *per_cu)
 322   {
 323     return new (&m_storage) cooked_index_entry (die_offset, tag, flags,
 324                                                 name, parent_entry,
 325                                                 per_cu);
 326   }
 327
 328   /* GNAT only emits mangled ("encoded") names in the DWARF, and does
 329      not emit the module structure.  However, we need this structure
 330      to do lookups.  This function recreates that structure for an
 331      existing entry.  It returns the base name (last element) of the
 332      full decoded name.  */
 333   gdb::unique_xmalloc_ptr<char> handle_gnat_encoded_entry
 334        (cooked_index_entry *entry, htab_t gnat_entries);
 335
 336   /* A helper method that does the work of 'finalize'.  */
 337   void do_finalize ();
 338
 339   /* Storage for the entries.  */
 340   auto_obstack m_storage;
 341   /* List of all entries.  */
 342   std::vector<cooked_index_entry *> m_entries;
 343   /* If we found an entry with 'is_main' set, store it here.  */
 344   cooked_index_entry *m_main = nullptr;
 345   /* The addrmap.  This maps address ranges to dwarf2_per_cu_data
 346      objects.  */
 347   addrmap *m_addrmap = nullptr;
 348   /* Storage for canonical names.  */
 349   std::vector<gdb::unique_xmalloc_ptr<char>> m_names;
 350   /* A future that tracks when the 'finalize' method is done.  Note
 351      that the 'get' method is never called on this future, only
 352      'wait'.  */
 353   gdb::future<void> m_future;
 354 };
 355
 356 /* The main index of DIEs.  The parallel DIE indexers create
 357    cooked_index_shard objects.  Then, these are all handled to a
 358    cooked_index for storage and final indexing.  The index is
 359    made by iterating over the entries previously created.  */
 360
 361 class cooked_index : public dwarf_scanner_base
 362 {
 363 public:
 364
 365   /* A convenience typedef for the vector that is contained in this
 366      object.  */
 367   using vec_type = std::vector<std::unique_ptr<cooked_index_shard>>;
 368
 369   explicit cooked_index (vec_type &&vec);
 370   ~cooked_index () override;
 371   DISABLE_COPY_AND_ASSIGN (cooked_index);
 372
 373   /* Wait until the finalization of the entire cooked_index is
 374      done.  */
 375   void wait () const
 376   {
 377     for (auto &item : m_vector)
 378       item->wait ();
 379   }
 380
 381   /* A range over a vector of subranges.  */
 382   using range = range_chain<cooked_index_shard::range>;
 383
 384   /* Look up an entry by name.  Returns a range of all matching
 385      results.  If COMPLETING is true, then a larger range, suitable
 386      for completion, will be returned.  */
 387   range find (const std::string &name, bool completing) const;
 388
 389   /* Return a range of all the entries.  */
 390   range all_entries () const
 391   {
 392     std::vector<cooked_index_shard::range> result_range;
 393     result_range.reserve (m_vector.size ());
 394     for (auto &entry : m_vector)
 395       result_range.push_back (entry->all_entries ());
 396     return range (std::move (result_range));
 397   }
 398
 399   /* Look up ADDR in the address map, and return either the
 400      corresponding CU, or nullptr if the address could not be
 401      found.  */
 402   dwarf2_per_cu_data *lookup (CORE_ADDR addr);
 403
 404   /* Return a new vector of all the addrmaps used by all the indexes
 405      held by this object.  */
 406   std::vector<const addrmap *> get_addrmaps () const;
 407
 408   /* Return the entry that is believed to represent the program's
 409      "main".  This will return NULL if no such entry is available.  */
 410   const cooked_index_entry *get_main () const;
 411
 412   cooked_index *index_for_writing () override
 413   {
 414     return this;
 415   }
 416
 417   quick_symbol_functions_up make_quick_functions () const override;
 418
 419   /* Dump a human-readable form of the contents of the index.  */
 420   void dump (gdbarch *arch) const;
 421
 422   /* Wait for the index to be completely finished.  For ordinary uses,
 423      the index code ensures this itself -- e.g., 'all_entries' will
 424      wait on the 'finalize' future.  However, on destruction, if an
 425      index is being written, it's also necessary to wait for that to
 426      complete.  */
 427   void wait_completely () override
 428   {
 429     m_write_future.wait ();
 430   }
 431
 432   /* Start writing to the index cache, if the user asked for this.  */
 433   void start_writing_index (dwarf2_per_bfd *per_bfd);
 434
 435 private:
 436
 437   /* Maybe write the index to the index cache.  */
 438   void maybe_write_index (dwarf2_per_bfd *per_bfd);
 439
 440   /* The vector of cooked_index objects.  This is stored because the
 441      entries are stored on the obstacks in those objects.  */
 442   vec_type m_vector;
 443
 444   /* A future that tracks when the 'index_write' method is done.  */
 445   gdb::future<void> m_write_future;
 446 };
 447
 448 #endif /* GDB_DWARF2_COOKED_INDEX_H */