GDB (xrefs)
Loading...
Searching...
No Matches
cooked-index.c
Go to the documentation of this file.
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
33bool
35{
36 return (lang == language_ada
37 || lang == language_c
38 || lang == language_cplus);
39}
40
41/* See cooked-index.h. */
42
43int
44cooked_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
84namespace {
85
86void
87test_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
156const char *
157cooked_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
189void
190cooked_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
203const cooked_index_entry *
204cooked_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
223void
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
234gdb::unique_xmalloc_ptr<char>
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
276void
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
377cooked_index::find (const std::string &name, bool completing)
378{
379 wait ();
380
381 cooked_index_entry::comparison_mode mode = (completing
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
403 : m_vector (std::move (vec))
404{
405 for (auto &idx : m_vector)
406 idx->finalize ();
407}
408
409/* See cooked-index.h. */
410
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
425std::vector<addrmap *>
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
437cooked_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
448const cooked_index_entry *
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
461 {
462 result = entry;
463 break;
464 }
465 }
466
467 return result;
468}
469
471void
473{
474#if GDB_SELF_TEST
475 selftests::register_test ("cooked_index_entry::compare", test_compare);
476#endif
477}
const char *const name
Definition: aarch64-tdep.c:67
void xfree(void *)
std::string ada_decode(const char *encoded, bool wrap, bool operators)
Definition: ada-lang.c:1310
void * xcalloc(size_t number, size_t size)
Definition: alloc.c:85
constexpr char c2[]
Definition: 2.cc:24
constexpr char c1[]
Definition: 2.cc:23
gdb::unique_xmalloc_ptr< char > c_canonicalize_name(const char *name)
Definition: c-lang.c:733
std::vector< addrmap * > get_addrmaps()
Definition: cooked-index.c:426
dwarf2_per_cu_data * lookup(CORE_ADDR addr)
Definition: cooked-index.c:412
const cooked_index_entry * get_main() const
Definition: cooked-index.c:449
std::vector< std::unique_ptr< cooked_index > > vec_type
Definition: cooked-index.h:364
range find(const std::string &name, bool completing)
Definition: cooked-index.c:437
cooked_index_vector(vec_type &&vec)
Definition: cooked-index.c:402
range_chain< cooked_index::range > range
Definition: cooked-index.h:389
gdb::unique_xmalloc_ptr< char > handle_gnat_encoded_entry(cooked_index_entry *entry, htab_t gnat_entries)
Definition: cooked-index.c:235
cooked_index_entry * create(sect_offset die_offset, enum dwarf_tag tag, cooked_index_flag flags, const char *name, const cooked_index_entry *parent_entry, dwarf2_per_cu_data *per_cu)
Definition: cooked-index.h:313
std::vector< gdb::unique_xmalloc_ptr< char > > m_names
Definition: cooked-index.h:346
void finalize()
Definition: cooked-index.c:224
cooked_index_entry * m_main
Definition: cooked-index.h:341
gdb::future< void > m_future
Definition: cooked-index.h:350
iterator_range< std::vector< cooked_index_entry * >::iterator > range
Definition: cooked-index.h:280
range find(const std::string &name, bool completing)
Definition: cooked-index.c:377
const cooked_index_entry * add(sect_offset die_offset, enum dwarf_tag tag, cooked_index_flag flags, const char *name, const cooked_index_entry *parent_entry, dwarf2_per_cu_data *per_cu)
Definition: cooked-index.c:204
std::vector< cooked_index_entry * > m_entries
Definition: cooked-index.h:339
void do_finalize()
Definition: cooked-index.c:277
bool language_requires_canonicalization(enum language lang)
Definition: cooked-index.c:34
void _initialize_cooked_index()
Definition: cooked-index.c:472
bool language_requires_canonicalization(enum language lang)
Definition: cooked-index.c:34
@ IS_LINKAGE
Definition: cooked-index.h:50
@ IS_MAIN
Definition: cooked-index.h:44
gdb::unique_xmalloc_ptr< char > cp_canonicalize_string(const char *string)
Definition: cp-support.c:626
language
Definition: defs.h:211
@ language_ada
Definition: defs.h:226
@ language_cplus
Definition: defs.h:216
@ language_go
Definition: defs.h:218
@ language_rust
Definition: defs.h:224
@ language_c
Definition: defs.h:214
@ language_d
Definition: defs.h:217
mach_port_t kern_return_t mach_port_t mach_msg_type_name_t msgportsPoly mach_port_t kern_return_t pid_t pid mach_port_t kern_return_t mach_port_t task mach_port_t kern_return_t int flags
Definition: gnu-nat.c:1862
uint32_t dwarf5_djb_hash(const char *str_)
Definition: index-common.c:45
Definition: aarch64.h:50
std::vector< gdb::string_view > split_name(const char *name, split_style style)
Definition: split-name.c:27
Definition: cooked-index.h:72
dwarf2_per_cu_data * per_cu
Definition: cooked-index.h:225
void write_scope(struct obstack *storage, const char *sep, bool for_name) const
Definition: cooked-index.c:190
sect_offset die_offset
Definition: cooked-index.h:219
comparison_mode
Definition: cooked-index.h:159
@ SORT
Definition: cooked-index.h:161
@ COMPLETE
Definition: cooked-index.h:162
@ MATCH
Definition: cooked-index.h:160
const char * canonical
Definition: cooked-index.h:213
static int compare(const char *stra, const char *strb, comparison_mode mode)
Definition: cooked-index.c:44
const char * name
Definition: cooked-index.h:210
const char * full_name(struct obstack *storage, bool for_main=false) const
Definition: cooked-index.c:157
const cooked_index_entry * parent_entry
Definition: cooked-index.h:223
cooked_index_flag flags
Definition: cooked-index.h:217
enum language lang(bool strict_p=true) const
Definition: read.h:352