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