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 #include "defs.h" 21 #include "dwarf2/cooked-index.h" 22 #include "dwarf2/read.h" 23 #include "cp-support.h" 24 #include "c-lang.h" 25 #include "ada-lang.h" 26 #include "split-name.h" 27 #include <algorithm> 28 #include "safe-ctype.h" 29 #include "gdbsupport/selftest.h" 30 31 /* See cooked-index.h. */ 32 33 bool 34 language_requires_canonicalization (enum language lang) 35 { 36 return (lang == language_ada 37 || lang == language_c 38 || lang == language_cplus); 39 } 40 41 /* See cooked-index.h. */ 42 43 int 44 cooked_index_entry::compare (const char *stra, const char *strb, 45 comparison_mode mode) 46 { 47 auto munge = [] (char c) -> unsigned char 48 { 49 /* We want to sort '<' before any other printable character. 50 So, rewrite '<' to something just before ' '. */ 51 if (c == '<') 52 return '\x1f'; 53 return TOLOWER ((unsigned char) c); 54 }; 55 56 while (*stra != '\0' 57 && *strb != '\0' 58 && (munge (*stra) == munge (*strb))) 59 { 60 ++stra; 61 ++strb; 62 } 63 64 unsigned char c1 = munge (*stra); 65 unsigned char c2 = munge (*strb); 66 67 if (c1 == c2) 68 return 0; 69 70 /* When completing, if STRB ends earlier than STRA, consider them as 71 equal. When comparing, if STRB ends earlier and STRA ends with 72 '<', consider them as equal. */ 73 if (mode == COMPLETE || (mode == MATCH && c1 == munge ('<'))) 74 { 75 if (c2 == '\0') 76 return 0; 77 } 78 79 return c1 < c2 ? -1 : 1; 80 } 81 82 #if GDB_SELF_TEST 83 84 namespace { 85 86 void 87 test_compare () 88 { 89 /* Convenience aliases. */ 90 const auto mode_compare = cooked_index_entry::MATCH; 91 const auto mode_sort = cooked_index_entry::SORT; 92 const auto mode_complete = cooked_index_entry::COMPLETE; 93 94 SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd", 95 mode_compare) == 0); 96 SELF_CHECK (cooked_index_entry::compare ("abcd", "abcd", 97 mode_complete) == 0); 98 99 SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE", 100 mode_compare) < 0); 101 SELF_CHECK (cooked_index_entry::compare ("ABCDE", "abcd", 102 mode_compare) > 0); 103 SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE", 104 mode_complete) < 0); 105 SELF_CHECK (cooked_index_entry::compare ("ABCDE", "abcd", 106 mode_complete) == 0); 107 108 SELF_CHECK (cooked_index_entry::compare ("name", "name<>", 109 mode_compare) < 0); 110 SELF_CHECK (cooked_index_entry::compare ("name<>", "name", 111 mode_compare) == 0); 112 SELF_CHECK (cooked_index_entry::compare ("name", "name<>", 113 mode_complete) < 0); 114 SELF_CHECK (cooked_index_entry::compare ("name<>", "name", 115 mode_complete) == 0); 116 117 SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<arg>", 118 mode_compare) == 0); 119 SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<ag>", 120 mode_compare) > 0); 121 SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<arg>", 122 mode_complete) == 0); 123 SELF_CHECK (cooked_index_entry::compare ("name<arg>", "name<ag>", 124 mode_complete) > 0); 125 126 SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>", 127 "name<arg<more>>", 128 mode_compare) == 0); 129 130 SELF_CHECK (cooked_index_entry::compare ("name", "name<arg<more>>", 131 mode_compare) < 0); 132 SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>", "name", 133 mode_compare) == 0); 134 SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>", "name<arg<", 135 mode_compare) > 0); 136 SELF_CHECK (cooked_index_entry::compare ("name<arg<more>>", "name<arg<", 137 mode_complete) == 0); 138 139 SELF_CHECK (cooked_index_entry::compare ("", "abcd", mode_compare) < 0); 140 SELF_CHECK (cooked_index_entry::compare ("", "abcd", mode_complete) < 0); 141 SELF_CHECK (cooked_index_entry::compare ("abcd", "", mode_compare) > 0); 142 SELF_CHECK (cooked_index_entry::compare ("abcd", "", mode_complete) == 0); 143 144 SELF_CHECK (cooked_index_entry::compare ("func", "func<type>", 145 mode_sort) < 0); 146 SELF_CHECK (cooked_index_entry::compare ("func<type>", "func1", 147 mode_sort) < 0); 148 } 149 150 } /* anonymous namespace */ 151 152 #endif /* GDB_SELF_TEST */ 153 154 /* See cooked-index.h. */ 155 156 const char * 157 cooked_index_entry::full_name (struct obstack *storage, bool for_main) const 158 { 159 const char *local_name = for_main ? name : canonical; 160 161 if ((flags & IS_LINKAGE) != 0 || parent_entry == nullptr) 162 return local_name; 163 164 const char *sep = nullptr; 165 switch (per_cu->lang ()) 166 { 167 case language_cplus: 168 case language_rust: 169 sep = "::"; 170 break; 171 172 case language_go: 173 case language_d: 174 case language_ada: 175 sep = "."; 176 break; 177 178 default: 179 return local_name; 180 } 181 182 parent_entry->write_scope (storage, sep, for_main); 183 obstack_grow0 (storage, local_name, strlen (local_name)); 184 return (const char *) obstack_finish (storage); 185 } 186 187 /* See cooked-index.h. */ 188 189 void 190 cooked_index_entry::write_scope (struct obstack *storage, 191 const char *sep, 192 bool for_main) const 193 { 194 if (parent_entry != nullptr) 195 parent_entry->write_scope (storage, sep, for_main); 196 const char *local_name = for_main ? name : canonical; 197 obstack_grow (storage, local_name, strlen (local_name)); 198 obstack_grow (storage, sep, strlen (sep)); 199 } 200 201 /* See cooked-index.h. */ 202 203 const cooked_index_entry * 204 cooked_index::add (sect_offset die_offset, enum dwarf_tag tag, 205 cooked_index_flag flags, const char *name, 206 const cooked_index_entry *parent_entry, 207 dwarf2_per_cu_data *per_cu) 208 { 209 cooked_index_entry *result = create (die_offset, tag, flags, name, 210 parent_entry, per_cu); 211 m_entries.push_back (result); 212 213 /* An explicitly-tagged main program should always override the 214 implicit "main" discovery. */ 215 if ((flags & IS_MAIN) != 0) 216 m_main = result; 217 218 return result; 219 } 220 221 /* See cooked-index.h. */ 222 223 void 224 cooked_index::finalize () 225 { 226 m_future = gdb::thread_pool::g_thread_pool->post_task ([this] () 227 { 228 do_finalize (); 229 }); 230 } 231 232 /* See cooked-index.h. */ 233 234 gdb::unique_xmalloc_ptr<char> 235 cooked_index::handle_gnat_encoded_entry (cooked_index_entry *entry, 236 htab_t gnat_entries) 237 { 238 std::string canonical = ada_decode (entry->name, false, false); 239 if (canonical.empty ()) 240 return {}; 241 std::vector<gdb::string_view> names = split_name (canonical.c_str (), 242 split_style::DOT); 243 gdb::string_view tail = names.back (); 244 names.pop_back (); 245 246 const cooked_index_entry *parent = nullptr; 247 for (const auto &name : names) 248 { 249 uint32_t hashval = dwarf5_djb_hash (name); 250 void **slot = htab_find_slot_with_hash (gnat_entries, &name, 251 hashval, INSERT); 252 /* CUs are processed in order, so we only need to check the most 253 recent entry. */ 254 cooked_index_entry *last = (cooked_index_entry *) *slot; 255 if (last == nullptr || last->per_cu != entry->per_cu) 256 { 257 gdb::unique_xmalloc_ptr<char> new_name 258 = make_unique_xstrndup (name.data (), name.length ()); 259 last = create (entry->die_offset, DW_TAG_namespace, 260 0, new_name.get (), parent, 261 entry->per_cu); 262 last->canonical = last->name; 263 m_names.push_back (std::move (new_name)); 264 *slot = last; 265 } 266 267 parent = last; 268 } 269 270 entry->parent_entry = parent; 271 return make_unique_xstrndup (tail.data (), tail.length ()); 272 } 273 274 /* See cooked-index.h. */ 275 276 void 277 cooked_index::do_finalize () 278 { 279 auto hash_name_ptr = [] (const void *p) 280 { 281 const cooked_index_entry *entry = (const cooked_index_entry *) p; 282 return htab_hash_pointer (entry->name); 283 }; 284 285 auto eq_name_ptr = [] (const void *a, const void *b) -> int 286 { 287 const cooked_index_entry *ea = (const cooked_index_entry *) a; 288 const cooked_index_entry *eb = (const cooked_index_entry *) b; 289 return ea->name == eb->name; 290 }; 291 292 /* We can use pointer equality here because names come from 293 .debug_str, which will normally be unique-ified by the linker. 294 Also, duplicates are relatively harmless -- they just mean a bit 295 of extra memory is used. */ 296 htab_up seen_names (htab_create_alloc (10, hash_name_ptr, eq_name_ptr, 297 nullptr, xcalloc, xfree)); 298 299 auto hash_entry = [] (const void *e) 300 { 301 const cooked_index_entry *entry = (const cooked_index_entry *) e; 302 return dwarf5_djb_hash (entry->canonical); 303 }; 304 305 auto eq_entry = [] (const void *a, const void *b) -> int 306 { 307 const cooked_index_entry *ae = (const cooked_index_entry *) a; 308 const gdb::string_view *sv = (const gdb::string_view *) b; 309 return (strlen (ae->canonical) == sv->length () 310 && strncasecmp (ae->canonical, sv->data (), sv->length ()) == 0); 311 }; 312 313 htab_up gnat_entries (htab_create_alloc (10, hash_entry, eq_entry, 314 nullptr, xcalloc, xfree)); 315 316 for (cooked_index_entry *entry : m_entries) 317 { 318 /* Note that this code must be kept in sync with 319 language_requires_canonicalization. */ 320 gdb_assert (entry->canonical == nullptr); 321 if ((entry->flags & IS_LINKAGE) != 0) 322 entry->canonical = entry->name; 323 else if (entry->per_cu->lang () == language_ada) 324 { 325 gdb::unique_xmalloc_ptr<char> canon_name 326 = handle_gnat_encoded_entry (entry, gnat_entries.get ()); 327 if (canon_name == nullptr) 328 entry->canonical = entry->name; 329 else 330 { 331 entry->canonical = canon_name.get (); 332 m_names.push_back (std::move (canon_name)); 333 } 334 } 335 else if (entry->per_cu->lang () == language_cplus 336 || entry->per_cu->lang () == language_c) 337 { 338 void **slot = htab_find_slot (seen_names.get (), entry, 339 INSERT); 340 if (*slot == nullptr) 341 { 342 gdb::unique_xmalloc_ptr<char> canon_name 343 = (entry->per_cu->lang () == language_cplus 344 ? cp_canonicalize_string (entry->name) 345 : c_canonicalize_name (entry->name)); 346 if (canon_name == nullptr) 347 entry->canonical = entry->name; 348 else 349 { 350 entry->canonical = canon_name.get (); 351 m_names.push_back (std::move (canon_name)); 352 } 353 } 354 else 355 { 356 const cooked_index_entry *other 357 = (const cooked_index_entry *) *slot; 358 entry->canonical = other->canonical; 359 } 360 } 361 else 362 entry->canonical = entry->name; 363 } 364 365 m_names.shrink_to_fit (); 366 m_entries.shrink_to_fit (); 367 std::sort (m_entries.begin (), m_entries.end (), 368 [] (const cooked_index_entry *a, const cooked_index_entry *b) 369 { 370 return *a < *b; 371 }); 372 } 373 374 /* See cooked-index.h. */ 375 376 cooked_index::range 377 cooked_index::find (const std::string &name, bool completing) 378 { 379 wait (); 380 381 cooked_index_entry::comparison_mode mode = (completing 382 ? cooked_index_entry::COMPLETE 383 : cooked_index_entry::MATCH); 384 385 auto lower = std::lower_bound (m_entries.begin (), m_entries.end (), name, 386 [=] (const cooked_index_entry *entry, 387 const std::string &n) 388 { 389 return cooked_index_entry::compare (entry->canonical, n.c_str (), mode) < 0; 390 }); 391 392 auto upper = std::upper_bound (m_entries.begin (), m_entries.end (), name, 393 [=] (const std::string &n, 394 const cooked_index_entry *entry) 395 { 396 return cooked_index_entry::compare (entry->canonical, n.c_str (), mode) > 0; 397 }); 398 399 return range (lower, upper); 400 } 401 402 cooked_index_vector::cooked_index_vector (vec_type &&vec) 403 : m_vector (std::move (vec)) 404 { 405 for (auto &idx : m_vector) 406 idx->finalize (); 407 } 408 409 /* See cooked-index.h. */ 410 411 dwarf2_per_cu_data * 412 cooked_index_vector::lookup (CORE_ADDR addr) 413 { 414 for (const auto &index : m_vector) 415 { 416 dwarf2_per_cu_data *result = index->lookup (addr); 417 if (result != nullptr) 418 return result; 419 } 420 return nullptr; 421 } 422 423 /* See cooked-index.h. */ 424 425 std::vector<addrmap *> 426 cooked_index_vector::get_addrmaps () 427 { 428 std::vector<addrmap *> result; 429 for (const auto &index : m_vector) 430 result.push_back (index->m_addrmap); 431 return result; 432 } 433 434 /* See cooked-index.h. */ 435 436 cooked_index_vector::range 437 cooked_index_vector::find (const std::string &name, bool completing) 438 { 439 std::vector<cooked_index::range> result_range; 440 result_range.reserve (m_vector.size ()); 441 for (auto &entry : m_vector) 442 result_range.push_back (entry->find (name, completing)); 443 return range (std::move (result_range)); 444 } 445 446 /* See cooked-index.h. */ 447 448 const cooked_index_entry * 449 cooked_index_vector::get_main () const 450 { 451 const cooked_index_entry *result = nullptr; 452 453 for (const auto &index : m_vector) 454 { 455 const cooked_index_entry *entry = index->get_main (); 456 /* Choose the first "main" we see. The choice among several is 457 arbitrary. See the comment by the sole caller to understand 458 the rationale for filtering by language. */ 459 if (entry != nullptr 460 && !language_requires_canonicalization (entry->per_cu->lang ())) 461 { 462 result = entry; 463 break; 464 } 465 } 466 467 return result; 468 } 469 470 void _initialize_cooked_index (); 471 void 472 _initialize_cooked_index () 473 { 474 #if GDB_SELF_TEST 475 selftests::register_test ("cooked_index_entry::compare", test_compare); 476 #endif 477 } 478