Accelerate lookup_symbol_aux_objfile 85x
[external/binutils.git] / gdb / block.c
1 /* Block-related functions for the GNU debugger, GDB.
2
3    Copyright (C) 2003-2014 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 "block.h"
22 #include "symtab.h"
23 #include "symfile.h"
24 #include "gdb_obstack.h"
25 #include "cp-support.h"
26 #include "addrmap.h"
27 #include "gdbtypes.h"
28
29 /* This is used by struct block to store namespace-related info for
30    C++ files, namely using declarations and the current namespace in
31    scope.  */
32
33 struct block_namespace_info
34 {
35   const char *scope;
36   struct using_direct *using;
37 };
38
39 static void block_initialize_namespace (struct block *block,
40                                         struct obstack *obstack);
41
42 /* Return Nonzero if block a is lexically nested within block b,
43    or if a and b have the same pc range.
44    Return zero otherwise.  */
45
46 int
47 contained_in (const struct block *a, const struct block *b)
48 {
49   if (!a || !b)
50     return 0;
51
52   do
53     {
54       if (a == b)
55         return 1;
56       /* If A is a function block, then A cannot be contained in B,
57          except if A was inlined.  */
58       if (BLOCK_FUNCTION (a) != NULL && !block_inlined_p (a))
59         return 0;
60       a = BLOCK_SUPERBLOCK (a);
61     }
62   while (a != NULL);
63
64   return 0;
65 }
66
67
68 /* Return the symbol for the function which contains a specified
69    lexical block, described by a struct block BL.  The return value
70    will not be an inlined function; the containing function will be
71    returned instead.  */
72
73 struct symbol *
74 block_linkage_function (const struct block *bl)
75 {
76   while ((BLOCK_FUNCTION (bl) == NULL || block_inlined_p (bl))
77          && BLOCK_SUPERBLOCK (bl) != NULL)
78     bl = BLOCK_SUPERBLOCK (bl);
79
80   return BLOCK_FUNCTION (bl);
81 }
82
83 /* Return the symbol for the function which contains a specified
84    block, described by a struct block BL.  The return value will be
85    the closest enclosing function, which might be an inline
86    function.  */
87
88 struct symbol *
89 block_containing_function (const struct block *bl)
90 {
91   while (BLOCK_FUNCTION (bl) == NULL && BLOCK_SUPERBLOCK (bl) != NULL)
92     bl = BLOCK_SUPERBLOCK (bl);
93
94   return BLOCK_FUNCTION (bl);
95 }
96
97 /* Return one if BL represents an inlined function.  */
98
99 int
100 block_inlined_p (const struct block *bl)
101 {
102   return BLOCK_FUNCTION (bl) != NULL && SYMBOL_INLINED (BLOCK_FUNCTION (bl));
103 }
104
105 /* A helper function that checks whether PC is in the blockvector BL.
106    It returns the containing block if there is one, or else NULL.  */
107
108 static struct block *
109 find_block_in_blockvector (const struct blockvector *bl, CORE_ADDR pc)
110 {
111   struct block *b;
112   int bot, top, half;
113
114   /* If we have an addrmap mapping code addresses to blocks, then use
115      that.  */
116   if (BLOCKVECTOR_MAP (bl))
117     return addrmap_find (BLOCKVECTOR_MAP (bl), pc);
118
119   /* Otherwise, use binary search to find the last block that starts
120      before PC.
121      Note: GLOBAL_BLOCK is block 0, STATIC_BLOCK is block 1.
122      They both have the same START,END values.
123      Historically this code would choose STATIC_BLOCK over GLOBAL_BLOCK but the
124      fact that this choice was made was subtle, now we make it explicit.  */
125   gdb_assert (BLOCKVECTOR_NBLOCKS (bl) >= 2);
126   bot = STATIC_BLOCK;
127   top = BLOCKVECTOR_NBLOCKS (bl);
128
129   while (top - bot > 1)
130     {
131       half = (top - bot + 1) >> 1;
132       b = BLOCKVECTOR_BLOCK (bl, bot + half);
133       if (BLOCK_START (b) <= pc)
134         bot += half;
135       else
136         top = bot + half;
137     }
138
139   /* Now search backward for a block that ends after PC.  */
140
141   while (bot >= STATIC_BLOCK)
142     {
143       b = BLOCKVECTOR_BLOCK (bl, bot);
144       if (BLOCK_END (b) > pc)
145         return b;
146       bot--;
147     }
148
149   return NULL;
150 }
151
152 /* Return the blockvector immediately containing the innermost lexical
153    block containing the specified pc value and section, or 0 if there
154    is none.  PBLOCK is a pointer to the block.  If PBLOCK is NULL, we
155    don't pass this information back to the caller.  */
156
157 const struct blockvector *
158 blockvector_for_pc_sect (CORE_ADDR pc, struct obj_section *section,
159                          const struct block **pblock,
160                          struct compunit_symtab *cust)
161 {
162   const struct blockvector *bl;
163   struct block *b;
164
165   if (cust == NULL)
166     {
167       /* First search all symtabs for one whose file contains our pc */
168       cust = find_pc_sect_compunit_symtab (pc, section);
169       if (cust == NULL)
170         return 0;
171     }
172
173   bl = COMPUNIT_BLOCKVECTOR (cust);
174
175   /* Then search that symtab for the smallest block that wins.  */
176   b = find_block_in_blockvector (bl, pc);
177   if (b == NULL)
178     return NULL;
179
180   if (pblock)
181     *pblock = b;
182   return bl;
183 }
184
185 /* Return true if the blockvector BV contains PC, false otherwise.  */
186
187 int
188 blockvector_contains_pc (const struct blockvector *bv, CORE_ADDR pc)
189 {
190   return find_block_in_blockvector (bv, pc) != NULL;
191 }
192
193 /* Return call_site for specified PC in GDBARCH.  PC must match exactly, it
194    must be the next instruction after call (or after tail call jump).  Throw
195    NO_ENTRY_VALUE_ERROR otherwise.  This function never returns NULL.  */
196
197 struct call_site *
198 call_site_for_pc (struct gdbarch *gdbarch, CORE_ADDR pc)
199 {
200   struct compunit_symtab *cust;
201   void **slot = NULL;
202
203   /* -1 as tail call PC can be already after the compilation unit range.  */
204   cust = find_pc_compunit_symtab (pc - 1);
205
206   if (cust != NULL && COMPUNIT_CALL_SITE_HTAB (cust) != NULL)
207     slot = htab_find_slot (COMPUNIT_CALL_SITE_HTAB (cust), &pc, NO_INSERT);
208
209   if (slot == NULL)
210     {
211       struct bound_minimal_symbol msym = lookup_minimal_symbol_by_pc (pc);
212
213       /* DW_TAG_gnu_call_site will be missing just if GCC could not determine
214          the call target.  */
215       throw_error (NO_ENTRY_VALUE_ERROR,
216                    _("DW_OP_GNU_entry_value resolving cannot find "
217                      "DW_TAG_GNU_call_site %s in %s"),
218                    paddress (gdbarch, pc),
219                    (msym.minsym == NULL ? "???"
220                     : MSYMBOL_PRINT_NAME (msym.minsym)));
221     }
222
223   return *slot;
224 }
225
226 /* Return the blockvector immediately containing the innermost lexical block
227    containing the specified pc value, or 0 if there is none.
228    Backward compatibility, no section.  */
229
230 const struct blockvector *
231 blockvector_for_pc (CORE_ADDR pc, const struct block **pblock)
232 {
233   return blockvector_for_pc_sect (pc, find_pc_mapped_section (pc),
234                                   pblock, NULL);
235 }
236
237 /* Return the innermost lexical block containing the specified pc value
238    in the specified section, or 0 if there is none.  */
239
240 const struct block *
241 block_for_pc_sect (CORE_ADDR pc, struct obj_section *section)
242 {
243   const struct blockvector *bl;
244   const struct block *b;
245
246   bl = blockvector_for_pc_sect (pc, section, &b, NULL);
247   if (bl)
248     return b;
249   return 0;
250 }
251
252 /* Return the innermost lexical block containing the specified pc value,
253    or 0 if there is none.  Backward compatibility, no section.  */
254
255 const struct block *
256 block_for_pc (CORE_ADDR pc)
257 {
258   return block_for_pc_sect (pc, find_pc_mapped_section (pc));
259 }
260
261 /* Now come some functions designed to deal with C++ namespace issues.
262    The accessors are safe to use even in the non-C++ case.  */
263
264 /* This returns the namespace that BLOCK is enclosed in, or "" if it
265    isn't enclosed in a namespace at all.  This travels the chain of
266    superblocks looking for a scope, if necessary.  */
267
268 const char *
269 block_scope (const struct block *block)
270 {
271   for (; block != NULL; block = BLOCK_SUPERBLOCK (block))
272     {
273       if (BLOCK_NAMESPACE (block) != NULL
274           && BLOCK_NAMESPACE (block)->scope != NULL)
275         return BLOCK_NAMESPACE (block)->scope;
276     }
277
278   return "";
279 }
280
281 /* Set BLOCK's scope member to SCOPE; if needed, allocate memory via
282    OBSTACK.  (It won't make a copy of SCOPE, however, so that already
283    has to be allocated correctly.)  */
284
285 void
286 block_set_scope (struct block *block, const char *scope,
287                  struct obstack *obstack)
288 {
289   block_initialize_namespace (block, obstack);
290
291   BLOCK_NAMESPACE (block)->scope = scope;
292 }
293
294 /* This returns the using directives list associated with BLOCK, if
295    any.  */
296
297 struct using_direct *
298 block_using (const struct block *block)
299 {
300   if (block == NULL || BLOCK_NAMESPACE (block) == NULL)
301     return NULL;
302   else
303     return BLOCK_NAMESPACE (block)->using;
304 }
305
306 /* Set BLOCK's using member to USING; if needed, allocate memory via
307    OBSTACK.  (It won't make a copy of USING, however, so that already
308    has to be allocated correctly.)  */
309
310 void
311 block_set_using (struct block *block,
312                  struct using_direct *using,
313                  struct obstack *obstack)
314 {
315   block_initialize_namespace (block, obstack);
316
317   BLOCK_NAMESPACE (block)->using = using;
318 }
319
320 /* If BLOCK_NAMESPACE (block) is NULL, allocate it via OBSTACK and
321    ititialize its members to zero.  */
322
323 static void
324 block_initialize_namespace (struct block *block, struct obstack *obstack)
325 {
326   if (BLOCK_NAMESPACE (block) == NULL)
327     {
328       BLOCK_NAMESPACE (block)
329         = obstack_alloc (obstack, sizeof (struct block_namespace_info));
330       BLOCK_NAMESPACE (block)->scope = NULL;
331       BLOCK_NAMESPACE (block)->using = NULL;
332     }
333 }
334
335 /* Return the static block associated to BLOCK.  Return NULL if block
336    is NULL or if block is a global block.  */
337
338 const struct block *
339 block_static_block (const struct block *block)
340 {
341   if (block == NULL || BLOCK_SUPERBLOCK (block) == NULL)
342     return NULL;
343
344   while (BLOCK_SUPERBLOCK (BLOCK_SUPERBLOCK (block)) != NULL)
345     block = BLOCK_SUPERBLOCK (block);
346
347   return block;
348 }
349
350 /* Return the static block associated to BLOCK.  Return NULL if block
351    is NULL.  */
352
353 const struct block *
354 block_global_block (const struct block *block)
355 {
356   if (block == NULL)
357     return NULL;
358
359   while (BLOCK_SUPERBLOCK (block) != NULL)
360     block = BLOCK_SUPERBLOCK (block);
361
362   return block;
363 }
364
365 /* Allocate a block on OBSTACK, and initialize its elements to
366    zero/NULL.  This is useful for creating "dummy" blocks that don't
367    correspond to actual source files.
368
369    Warning: it sets the block's BLOCK_DICT to NULL, which isn't a
370    valid value.  If you really don't want the block to have a
371    dictionary, then you should subsequently set its BLOCK_DICT to
372    dict_create_linear (obstack, NULL).  */
373
374 struct block *
375 allocate_block (struct obstack *obstack)
376 {
377   struct block *bl = OBSTACK_ZALLOC (obstack, struct block);
378
379   return bl;
380 }
381
382 /* Allocate a global block.  */
383
384 struct block *
385 allocate_global_block (struct obstack *obstack)
386 {
387   struct global_block *bl = OBSTACK_ZALLOC (obstack, struct global_block);
388
389   return &bl->block;
390 }
391
392 /* Set the compunit of the global block.  */
393
394 void
395 set_block_compunit_symtab (struct block *block, struct compunit_symtab *cu)
396 {
397   struct global_block *gb;
398
399   gdb_assert (BLOCK_SUPERBLOCK (block) == NULL);
400   gb = (struct global_block *) block;
401   gdb_assert (gb->compunit_symtab == NULL);
402   gb->compunit_symtab = cu;
403 }
404
405 /* Return the compunit of the global block.  */
406
407 static struct compunit_symtab *
408 get_block_compunit_symtab (const struct block *block)
409 {
410   struct global_block *gb;
411
412   gdb_assert (BLOCK_SUPERBLOCK (block) == NULL);
413   gb = (struct global_block *) block;
414   gdb_assert (gb->compunit_symtab != NULL);
415   return gb->compunit_symtab;
416 }
417
418 \f
419
420 /* Initialize a block iterator, either to iterate over a single block,
421    or, for static and global blocks, all the included symtabs as
422    well.  */
423
424 static void
425 initialize_block_iterator (const struct block *block,
426                            struct block_iterator *iter)
427 {
428   enum block_enum which;
429   struct compunit_symtab *cu;
430
431   iter->idx = -1;
432
433   if (BLOCK_SUPERBLOCK (block) == NULL)
434     {
435       which = GLOBAL_BLOCK;
436       cu = get_block_compunit_symtab (block);
437     }
438   else if (BLOCK_SUPERBLOCK (BLOCK_SUPERBLOCK (block)) == NULL)
439     {
440       which = STATIC_BLOCK;
441       cu = get_block_compunit_symtab (BLOCK_SUPERBLOCK (block));
442     }
443   else
444     {
445       iter->d.block = block;
446       /* A signal value meaning that we're iterating over a single
447          block.  */
448       iter->which = FIRST_LOCAL_BLOCK;
449       return;
450     }
451
452   /* If this is an included symtab, find the canonical includer and
453      use it instead.  */
454   while (cu->user != NULL)
455     cu = cu->user;
456
457   /* Putting this check here simplifies the logic of the iterator
458      functions.  If there are no included symtabs, we only need to
459      search a single block, so we might as well just do that
460      directly.  */
461   if (cu->includes == NULL)
462     {
463       iter->d.block = block;
464       /* A signal value meaning that we're iterating over a single
465          block.  */
466       iter->which = FIRST_LOCAL_BLOCK;
467     }
468   else
469     {
470       iter->d.compunit_symtab = cu;
471       iter->which = which;
472     }
473 }
474
475 /* A helper function that finds the current compunit over whose static
476    or global block we should iterate.  */
477
478 static struct compunit_symtab *
479 find_iterator_compunit_symtab (struct block_iterator *iterator)
480 {
481   if (iterator->idx == -1)
482     return iterator->d.compunit_symtab;
483   return iterator->d.compunit_symtab->includes[iterator->idx];
484 }
485
486 /* Perform a single step for a plain block iterator, iterating across
487    symbol tables as needed.  Returns the next symbol, or NULL when
488    iteration is complete.  */
489
490 static struct symbol *
491 block_iterator_step (struct block_iterator *iterator, int first)
492 {
493   struct symbol *sym;
494
495   gdb_assert (iterator->which != FIRST_LOCAL_BLOCK);
496
497   while (1)
498     {
499       if (first)
500         {
501           struct compunit_symtab *cust
502             = find_iterator_compunit_symtab (iterator);
503           const struct block *block;
504
505           /* Iteration is complete.  */
506           if (cust == NULL)
507             return  NULL;
508
509           block = BLOCKVECTOR_BLOCK (COMPUNIT_BLOCKVECTOR (cust),
510                                      iterator->which);
511           sym = dict_iterator_first (BLOCK_DICT (block), &iterator->dict_iter);
512         }
513       else
514         sym = dict_iterator_next (&iterator->dict_iter);
515
516       if (sym != NULL)
517         return sym;
518
519       /* We have finished iterating the appropriate block of one
520          symtab.  Now advance to the next symtab and begin iteration
521          there.  */
522       ++iterator->idx;
523       first = 1;
524     }
525 }
526
527 /* See block.h.  */
528
529 struct symbol *
530 block_iterator_first (const struct block *block,
531                       struct block_iterator *iterator)
532 {
533   initialize_block_iterator (block, iterator);
534
535   if (iterator->which == FIRST_LOCAL_BLOCK)
536     return dict_iterator_first (block->dict, &iterator->dict_iter);
537
538   return block_iterator_step (iterator, 1);
539 }
540
541 /* See block.h.  */
542
543 struct symbol *
544 block_iterator_next (struct block_iterator *iterator)
545 {
546   if (iterator->which == FIRST_LOCAL_BLOCK)
547     return dict_iterator_next (&iterator->dict_iter);
548
549   return block_iterator_step (iterator, 0);
550 }
551
552 /* Perform a single step for a "name" block iterator, iterating across
553    symbol tables as needed.  Returns the next symbol, or NULL when
554    iteration is complete.  */
555
556 static struct symbol *
557 block_iter_name_step (struct block_iterator *iterator, const char *name,
558                       int first)
559 {
560   struct symbol *sym;
561
562   gdb_assert (iterator->which != FIRST_LOCAL_BLOCK);
563
564   while (1)
565     {
566       if (first)
567         {
568           struct compunit_symtab *cust
569             = find_iterator_compunit_symtab (iterator);
570           const struct block *block;
571
572           /* Iteration is complete.  */
573           if (cust == NULL)
574             return  NULL;
575
576           block = BLOCKVECTOR_BLOCK (COMPUNIT_BLOCKVECTOR (cust),
577                                      iterator->which);
578           sym = dict_iter_name_first (BLOCK_DICT (block), name,
579                                       &iterator->dict_iter);
580         }
581       else
582         sym = dict_iter_name_next (name, &iterator->dict_iter);
583
584       if (sym != NULL)
585         return sym;
586
587       /* We have finished iterating the appropriate block of one
588          symtab.  Now advance to the next symtab and begin iteration
589          there.  */
590       ++iterator->idx;
591       first = 1;
592     }
593 }
594
595 /* See block.h.  */
596
597 struct symbol *
598 block_iter_name_first (const struct block *block,
599                        const char *name,
600                        struct block_iterator *iterator)
601 {
602   initialize_block_iterator (block, iterator);
603
604   if (iterator->which == FIRST_LOCAL_BLOCK)
605     return dict_iter_name_first (block->dict, name, &iterator->dict_iter);
606
607   return block_iter_name_step (iterator, name, 1);
608 }
609
610 /* See block.h.  */
611
612 struct symbol *
613 block_iter_name_next (const char *name, struct block_iterator *iterator)
614 {
615   if (iterator->which == FIRST_LOCAL_BLOCK)
616     return dict_iter_name_next (name, &iterator->dict_iter);
617
618   return block_iter_name_step (iterator, name, 0);
619 }
620
621 /* Perform a single step for a "match" block iterator, iterating
622    across symbol tables as needed.  Returns the next symbol, or NULL
623    when iteration is complete.  */
624
625 static struct symbol *
626 block_iter_match_step (struct block_iterator *iterator,
627                        const char *name,
628                        symbol_compare_ftype *compare,
629                        int first)
630 {
631   struct symbol *sym;
632
633   gdb_assert (iterator->which != FIRST_LOCAL_BLOCK);
634
635   while (1)
636     {
637       if (first)
638         {
639           struct compunit_symtab *cust
640             = find_iterator_compunit_symtab (iterator);
641           const struct block *block;
642
643           /* Iteration is complete.  */
644           if (cust == NULL)
645             return  NULL;
646
647           block = BLOCKVECTOR_BLOCK (COMPUNIT_BLOCKVECTOR (cust),
648                                      iterator->which);
649           sym = dict_iter_match_first (BLOCK_DICT (block), name,
650                                        compare, &iterator->dict_iter);
651         }
652       else
653         sym = dict_iter_match_next (name, compare, &iterator->dict_iter);
654
655       if (sym != NULL)
656         return sym;
657
658       /* We have finished iterating the appropriate block of one
659          symtab.  Now advance to the next symtab and begin iteration
660          there.  */
661       ++iterator->idx;
662       first = 1;
663     }
664 }
665
666 /* See block.h.  */
667
668 struct symbol *
669 block_iter_match_first (const struct block *block,
670                         const char *name,
671                         symbol_compare_ftype *compare,
672                         struct block_iterator *iterator)
673 {
674   initialize_block_iterator (block, iterator);
675
676   if (iterator->which == FIRST_LOCAL_BLOCK)
677     return dict_iter_match_first (block->dict, name, compare,
678                                   &iterator->dict_iter);
679
680   return block_iter_match_step (iterator, name, compare, 1);
681 }
682
683 /* See block.h.  */
684
685 struct symbol *
686 block_iter_match_next (const char *name,
687                        symbol_compare_ftype *compare,
688                        struct block_iterator *iterator)
689 {
690   if (iterator->which == FIRST_LOCAL_BLOCK)
691     return dict_iter_match_next (name, compare, &iterator->dict_iter);
692
693   return block_iter_match_step (iterator, name, compare, 0);
694 }
695
696 /* See block.h.
697
698    Note that if NAME is the demangled form of a C++ symbol, we will fail
699    to find a match during the binary search of the non-encoded names, but
700    for now we don't worry about the slight inefficiency of looking for
701    a match we'll never find, since it will go pretty quick.  Once the
702    binary search terminates, we drop through and do a straight linear
703    search on the symbols.  Each symbol which is marked as being a ObjC/C++
704    symbol (language_cplus or language_objc set) has both the encoded and
705    non-encoded names tested for a match.  */
706
707 struct symbol *
708 block_lookup_symbol (const struct block *block, const char *name,
709                      const domain_enum domain)
710 {
711   struct block_iterator iter;
712   struct symbol *sym;
713
714   if (!BLOCK_FUNCTION (block))
715     {
716       ALL_BLOCK_SYMBOLS_WITH_NAME (block, name, iter, sym)
717         {
718           if (symbol_matches_domain (SYMBOL_LANGUAGE (sym),
719                                      SYMBOL_DOMAIN (sym), domain))
720             return sym;
721         }
722       return NULL;
723     }
724   else
725     {
726       /* Note that parameter symbols do not always show up last in the
727          list; this loop makes sure to take anything else other than
728          parameter symbols first; it only uses parameter symbols as a
729          last resort.  Note that this only takes up extra computation
730          time on a match.  */
731
732       struct symbol *sym_found = NULL;
733
734       ALL_BLOCK_SYMBOLS_WITH_NAME (block, name, iter, sym)
735         {
736           if (symbol_matches_domain (SYMBOL_LANGUAGE (sym),
737                                      SYMBOL_DOMAIN (sym), domain))
738             {
739               sym_found = sym;
740               if (!SYMBOL_IS_ARGUMENT (sym))
741                 {
742                   break;
743                 }
744             }
745         }
746       return (sym_found);       /* Will be NULL if not found.  */
747     }
748 }
749
750 /* See block.h.  */
751
752 struct symbol *
753 block_lookup_symbol_primary (const struct block *block, const char *name,
754                              const domain_enum domain)
755 {
756   struct symbol *sym;
757   struct dict_iterator dict_iter;
758
759   /* Verify BLOCK is STATIC_BLOCK or GLOBAL_BLOCK.  */
760   gdb_assert (BLOCK_SUPERBLOCK (block) == NULL
761               || BLOCK_SUPERBLOCK (BLOCK_SUPERBLOCK (block)) == NULL);
762
763   for (sym = dict_iter_name_first (block->dict, name, &dict_iter);
764        sym != NULL;
765        sym = dict_iter_name_next (name, &dict_iter))
766     {
767       if (symbol_matches_domain (SYMBOL_LANGUAGE (sym),
768                                  SYMBOL_DOMAIN (sym), domain))
769         return sym;
770     }
771
772   return NULL;
773 }