1 /* C preprocessor macro tables for GDB.
2 Copyright 2002 Free Software Foundation, Inc.
3 Contributed by Red Hat, Inc.
5 This file is part of GDB.
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 2 of the License, or
10 (at your option) any later version.
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.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
23 #include "gdb_obstack.h"
24 #include "splay-tree.h"
29 #include "gdb_assert.h"
31 #include "complaints.h"
34 /* The macro table structure. */
38 /* The obstack this table's data should be allocated in, or zero if
39 we should use xmalloc. */
40 struct obstack *obstack;
42 /* The bcache we should use to hold macro names, argument names, and
43 definitions, or zero if we should use xmalloc. */
44 struct bcache *bcache;
46 /* The main source file for this compilation unit --- the one whose
47 name was given to the compiler. This is the root of the
48 #inclusion tree; everything else is #included from here. */
49 struct macro_source_file *main_source;
51 /* The table of macro definitions. This is a splay tree (an ordered
52 binary tree that stays balanced, effectively), sorted by macro
53 name. Where a macro gets defined more than once (presumably with
54 an #undefinition in between), we sort the definitions by the
55 order they would appear in the preprocessor's output. That is,
56 if `a.c' #includes `m.h' and then #includes `n.h', and both
57 header files #define X (with an #undef somewhere in between),
58 then the definition from `m.h' appears in our splay tree before
61 The splay tree's keys are `struct macro_key' pointers;
62 the values are `struct macro_definition' pointers.
64 The splay tree, its nodes, and the keys and values are allocated
65 in obstack, if it's non-zero, or with xmalloc otherwise. The
66 macro names, argument names, argument name arrays, and definition
67 strings are all allocated in bcache, if non-zero, or with xmalloc
69 splay_tree definitions;
74 /* Allocation and freeing functions. */
76 /* Allocate SIZE bytes of memory appropriately for the macro table T.
77 This just checks whether T has an obstack, or whether its pieces
78 should be allocated with xmalloc. */
80 macro_alloc (int size, struct macro_table *t)
83 return obstack_alloc (t->obstack, size);
85 return xmalloc (size);
90 macro_free (void *object, struct macro_table *t)
92 gdb_assert (! t->obstack);
97 /* If the macro table T has a bcache, then cache the LEN bytes at ADDR
98 there, and return the cached copy. Otherwise, just xmalloc a copy
99 of the bytes, and return a pointer to that. */
101 macro_bcache (struct macro_table *t, const void *addr, int len)
104 return bcache (addr, len, t->bcache);
107 void *copy = xmalloc (len);
108 memcpy (copy, addr, len);
114 /* If the macro table T has a bcache, cache the null-terminated string
115 S there, and return a pointer to the cached copy. Otherwise,
116 xmalloc a copy and return that. */
118 macro_bcache_str (struct macro_table *t, const char *s)
120 return (char *) macro_bcache (t, s, strlen (s) + 1);
124 /* Free a possibly bcached object OBJ. That is, if the macro table T
125 has a bcache, it's an error; otherwise, xfree OBJ. */
127 macro_bcache_free (struct macro_table *t, void *obj)
129 gdb_assert (! t->bcache);
135 /* Macro tree keys, w/their comparison, allocation, and freeing functions. */
137 /* A key in the splay tree. */
140 /* The table we're in. We only need this in order to free it, since
141 the splay tree library's key and value freeing functions require
142 that the key or value contain all the information needed to free
144 struct macro_table *table;
146 /* The name of the macro. This is in the table's bcache, if it has
150 /* The source file and line number where the definition's scope
151 begins. This is also the line of the definition itself. */
152 struct macro_source_file *start_file;
155 /* The first source file and line after the definition's scope.
156 (That is, the scope does not include this endpoint.) If end_file
157 is zero, then the definition extends to the end of the
159 struct macro_source_file *end_file;
164 /* Return the #inclusion depth of the source file FILE. This is the
165 number of #inclusions it took to reach this file. For the main
166 source file, the #inclusion depth is zero; for a file it #includes
167 directly, the depth would be one; and so on. */
169 inclusion_depth (struct macro_source_file *file)
173 for (depth = 0; file->included_by; depth++)
174 file = file->included_by;
180 /* Compare two source locations (from the same compilation unit).
181 This is part of the comparison function for the tree of
184 LINE1 and LINE2 are line numbers in the source files FILE1 and
185 FILE2. Return a value:
186 - less than zero if {LINE,FILE}1 comes before {LINE,FILE}2,
187 - greater than zero if {LINE,FILE}1 comes after {LINE,FILE}2, or
188 - zero if they are equal.
190 When the two locations are in different source files --- perhaps
191 one is in a header, while another is in the main source file --- we
192 order them by where they would appear in the fully pre-processed
193 sources, where all the #included files have been substituted into
196 compare_locations (struct macro_source_file *file1, int line1,
197 struct macro_source_file *file2, int line2)
199 /* We want to treat positions in an #included file as coming *after*
200 the line containing the #include, but *before* the line after the
201 include. As we walk up the #inclusion tree toward the main
202 source file, we update fileX and lineX as we go; includedX
203 indicates whether the original position was from the #included
208 /* If a file is zero, that means "end of compilation unit." Handle
220 /* If the two files are not the same, find their common ancestor in
221 the #inclusion tree. */
224 /* If one file is deeper than the other, walk up the #inclusion
225 chain until the two files are at least at the same *depth*.
226 Then, walk up both files in synchrony until they're the same
227 file. That file is the common ancestor. */
228 int depth1 = inclusion_depth (file1);
229 int depth2 = inclusion_depth (file2);
231 /* Only one of these while loops will ever execute in any given
233 while (depth1 > depth2)
235 line1 = file1->included_at_line;
236 file1 = file1->included_by;
240 while (depth2 > depth1)
242 line2 = file2->included_at_line;
243 file2 = file2->included_by;
248 /* Now both file1 and file2 are at the same depth. Walk toward
249 the root of the tree until we find where the branches meet. */
250 while (file1 != file2)
252 line1 = file1->included_at_line;
253 file1 = file1->included_by;
254 /* At this point, we know that the case the includedX flags
255 are trying to deal with won't come up, but we'll just
256 maintain them anyway. */
259 line2 = file2->included_at_line;
260 file2 = file2->included_by;
263 /* Sanity check. If file1 and file2 are really from the
264 same compilation unit, then they should both be part of
265 the same tree, and this shouldn't happen. */
266 gdb_assert (file1 && file2);
270 /* Now we've got two line numbers in the same file. */
273 /* They can't both be from #included files. Then we shouldn't
274 have walked up this far. */
275 gdb_assert (! included1 || ! included2);
277 /* Any #included position comes after a non-#included position
278 with the same line number in the #including file. */
287 return line1 - line2;
291 /* Compare a macro key KEY against NAME, the source file FILE, and
294 Sort definitions by name; for two definitions with the same name,
295 place the one whose definition comes earlier before the one whose
296 definition comes later.
298 Return -1, 0, or 1 if key comes before, is identical to, or comes
299 after NAME, FILE, and LINE. */
301 key_compare (struct macro_key *key,
302 const char *name, struct macro_source_file *file, int line)
304 int names = strcmp (key->name, name);
308 return compare_locations (key->start_file, key->start_line,
313 /* The macro tree comparison function, typed for the splay tree
314 library's happiness. */
316 macro_tree_compare (splay_tree_key untyped_key1,
317 splay_tree_key untyped_key2)
319 struct macro_key *key1 = (struct macro_key *) untyped_key1;
320 struct macro_key *key2 = (struct macro_key *) untyped_key2;
322 return key_compare (key1, key2->name, key2->start_file, key2->start_line);
326 /* Construct a new macro key node for a macro in table T whose name is
327 NAME, and whose scope starts at LINE in FILE; register the name in
329 static struct macro_key *
330 new_macro_key (struct macro_table *t,
332 struct macro_source_file *file,
335 struct macro_key *k = macro_alloc (sizeof (*k), t);
337 memset (k, 0, sizeof (*k));
339 k->name = macro_bcache_str (t, name);
340 k->start_file = file;
341 k->start_line = line;
349 macro_tree_delete_key (void *untyped_key)
351 struct macro_key *key = (struct macro_key *) untyped_key;
353 macro_bcache_free (key->table, (char *) key->name);
354 macro_free (key, key->table);
359 /* Building and querying the tree of #included files. */
362 /* Allocate and initialize a new source file structure. */
363 static struct macro_source_file *
364 new_source_file (struct macro_table *t,
365 const char *filename)
367 /* Get space for the source file structure itself. */
368 struct macro_source_file *f = macro_alloc (sizeof (*f), t);
370 memset (f, 0, sizeof (*f));
372 f->filename = macro_bcache_str (t, filename);
379 /* Free a source file, and all the source files it #included. */
381 free_macro_source_file (struct macro_source_file *src)
383 struct macro_source_file *child, *next_child;
385 /* Free this file's children. */
386 for (child = src->includes; child; child = next_child)
388 next_child = child->next_included;
389 free_macro_source_file (child);
392 macro_bcache_free (src->table, (char *) src->filename);
393 macro_free (src, src->table);
397 struct macro_source_file *
398 macro_set_main (struct macro_table *t,
399 const char *filename)
401 /* You can't change a table's main source file. What would that do
403 gdb_assert (! t->main_source);
405 t->main_source = new_source_file (t, filename);
407 return t->main_source;
411 struct macro_source_file *
412 macro_main (struct macro_table *t)
414 gdb_assert (t->main_source);
416 return t->main_source;
420 struct macro_source_file *
421 macro_include (struct macro_source_file *source,
423 const char *included)
425 struct macro_source_file *new;
426 struct macro_source_file **link;
428 /* Find the right position in SOURCE's `includes' list for the new
429 file. Scan until we find the first file we shouldn't follow ---
430 which is therefore the file we should directly precede --- or
431 reach the end of the list. */
432 for (link = &source->includes;
433 *link && line < (*link)->included_at_line;
434 link = &(*link)->next_included)
437 /* Did we find another file already #included at the same line as
439 if (*link && line == (*link)->included_at_line)
441 /* This means the compiler is emitting bogus debug info. (GCC
442 circa March 2002 did this.) It also means that the splay
443 tree ordering function, macro_tree_compare, will abort,
444 because it can't tell which #inclusion came first. But GDB
445 should tolerate bad debug info. So:
448 static struct deprecated_complaint bogus_inclusion_line = {
449 "both `%s' and `%s' allegedly #included at %s:%d", 0, 0
452 complain (&bogus_inclusion_line,
453 included, (*link)->filename, source->filename, line);
455 /* Now, choose a new, unoccupied line number for this
456 #inclusion, after the alleged #inclusion line. */
457 while (*link && line == (*link)->included_at_line)
459 /* This line number is taken, so try the next line. */
461 link = &(*link)->next_included;
465 /* At this point, we know that LINE is an unused line number, and
466 *LINK points to the entry an #inclusion at that line should
468 new = new_source_file (source->table, included);
469 new->included_by = source;
470 new->included_at_line = line;
471 new->next_included = *link;
478 struct macro_source_file *
479 macro_lookup_inclusion (struct macro_source_file *source, const char *name)
481 /* Is SOURCE itself named NAME? */
482 if (strcmp (name, source->filename) == 0)
485 /* The filename in the source structure is probably a full path, but
486 NAME could be just the final component of the name. */
488 int name_len = strlen (name);
489 int src_name_len = strlen (source->filename);
491 /* We do mean < here, and not <=; if the lengths are the same,
492 then the strcmp above should have triggered, and we need to
493 check for a slash here. */
494 if (name_len < src_name_len
495 && source->filename[src_name_len - name_len - 1] == '/'
496 && strcmp (name, source->filename + src_name_len - name_len) == 0)
500 /* It's not us. Try all our children, and return the lowest. */
502 struct macro_source_file *child;
503 struct macro_source_file *best = NULL;
506 for (child = source->includes; child; child = child->next_included)
508 struct macro_source_file *result
509 = macro_lookup_inclusion (child, name);
513 int result_depth = inclusion_depth (result);
515 if (! best || result_depth < best_depth)
518 best_depth = result_depth;
529 /* Registering and looking up macro definitions. */
532 /* Construct a definition for a macro in table T. Cache all strings,
533 and the macro_definition structure itself, in T's bcache. */
534 static struct macro_definition *
535 new_macro_definition (struct macro_table *t,
536 enum macro_kind kind,
537 int argc, const char **argv,
538 const char *replacement)
540 struct macro_definition *d = macro_alloc (sizeof (*d), t);
542 memset (d, 0, sizeof (*d));
545 d->replacement = macro_bcache_str (t, replacement);
547 if (kind == macro_function_like)
550 const char **cached_argv;
551 int cached_argv_size = argc * sizeof (*cached_argv);
553 /* Bcache all the arguments. */
554 cached_argv = alloca (cached_argv_size);
555 for (i = 0; i < argc; i++)
556 cached_argv[i] = macro_bcache_str (t, argv[i]);
558 /* Now bcache the array of argument pointers itself. */
559 d->argv = macro_bcache (t, cached_argv, cached_argv_size);
563 /* We don't bcache the entire definition structure because it's got
564 a pointer to the macro table in it; since each compilation unit
565 has its own macro table, you'd only get bcache hits for identical
566 definitions within a compilation unit, which seems unlikely.
568 "So, why do macro definitions have pointers to their macro tables
569 at all?" Well, when the splay tree library wants to free a
570 node's value, it calls the value freeing function with nothing
571 but the value itself. It makes the (apparently reasonable)
572 assumption that the value carries enough information to free
573 itself. But not all macro tables have bcaches, so not all macro
574 definitions would be bcached. There's no way to tell whether a
575 given definition is bcached without knowing which table the
576 definition belongs to. ... blah. The thing's only sixteen
577 bytes anyway, and we can still bcache the name, args, and
578 definition, so we just don't bother bcaching the definition
584 /* Free a macro definition. */
586 macro_tree_delete_value (void *untyped_definition)
588 struct macro_definition *d = (struct macro_definition *) untyped_definition;
589 struct macro_table *t = d->table;
591 if (d->kind == macro_function_like)
595 for (i = 0; i < d->argc; i++)
596 macro_bcache_free (t, (char *) d->argv[i]);
597 macro_bcache_free (t, (char **) d->argv);
600 macro_bcache_free (t, (char *) d->replacement);
605 /* Find the splay tree node for the definition of NAME at LINE in
606 SOURCE, or zero if there is none. */
607 static splay_tree_node
608 find_definition (const char *name,
609 struct macro_source_file *file,
612 struct macro_table *t = file->table;
615 /* Construct a macro_key object, just for the query. */
616 struct macro_key query;
619 query.start_file = file;
620 query.start_line = line;
621 query.end_file = NULL;
623 n = splay_tree_lookup (t->definitions, (splay_tree_key) &query);
626 /* It's okay for us to do two queries like this: the real work
627 of the searching is done when we splay, and splaying the tree
628 a second time at the same key is a constant time operation.
629 If this still bugs you, you could always just extend the
630 splay tree library with a predecessor-or-equal operation, and
632 splay_tree_node pred = splay_tree_predecessor (t->definitions,
633 (splay_tree_key) &query);
637 /* Make sure this predecessor actually has the right name.
638 We just want to search within a given name's definitions. */
639 struct macro_key *found = (struct macro_key *) pred->key;
641 if (strcmp (found->name, name) == 0)
648 struct macro_key *found = (struct macro_key *) n->key;
650 /* Okay, so this definition has the right name, and its scope
651 begins before the given source location. But does its scope
652 end after the given source location? */
653 if (compare_locations (file, line, found->end_file, found->end_line) < 0)
663 /* If NAME already has a definition in scope at LINE in SOURCE, return
664 the key. If the old definition is different from the definition
665 given by KIND, ARGC, ARGV, and REPLACEMENT, complain, too.
666 Otherwise, return zero. (ARGC and ARGV are meaningless unless KIND
667 is `macro_function_like'.) */
668 static struct macro_key *
669 check_for_redefinition (struct macro_source_file *source, int line,
670 const char *name, enum macro_kind kind,
671 int argc, const char **argv,
672 const char *replacement)
674 splay_tree_node n = find_definition (name, source, line);
678 struct macro_key *found_key = (struct macro_key *) n->key;
679 struct macro_definition *found_def
680 = (struct macro_definition *) n->value;
683 /* Is this definition the same as the existing one?
684 According to the standard, this comparison needs to be done
685 on lists of tokens, not byte-by-byte, as we do here. But
686 that's too hard for us at the moment, and comparing
687 byte-by-byte will only yield false negatives (i.e., extra
688 warning messages), not false positives (i.e., unnoticed
689 definition changes). */
690 if (kind != found_def->kind)
692 else if (strcmp (replacement, found_def->replacement))
694 else if (kind == macro_function_like)
696 if (argc != found_def->argc)
702 for (i = 0; i < argc; i++)
703 if (strcmp (argv[i], found_def->argv[i]))
710 static struct deprecated_complaint macro_redefined = {
711 "macro `%s' redefined at %s:%d; original definition at %s:%d",
714 complain (¯o_redefined,
716 source->filename, line,
717 found_key->start_file->filename,
718 found_key->start_line);
729 macro_define_object (struct macro_source_file *source, int line,
730 const char *name, const char *replacement)
732 struct macro_table *t = source->table;
734 struct macro_definition *d;
736 k = check_for_redefinition (source, line,
737 name, macro_object_like,
741 /* If we're redefining a symbol, and the existing key would be
742 identical to our new key, then the splay_tree_insert function
743 will try to delete the old definition. When the definition is
744 living on an obstack, this isn't a happy thing.
746 Since this only happens in the presence of questionable debug
747 info, we just ignore all definitions after the first. The only
748 case I know of where this arises is in GCC's output for
749 predefined macros, and all the definitions are the same in that
751 if (k && ! key_compare (k, name, source, line))
754 k = new_macro_key (t, name, source, line);
755 d = new_macro_definition (t, macro_object_like, 0, 0, replacement);
756 splay_tree_insert (t->definitions, (splay_tree_key) k, (splay_tree_value) d);
761 macro_define_function (struct macro_source_file *source, int line,
762 const char *name, int argc, const char **argv,
763 const char *replacement)
765 struct macro_table *t = source->table;
767 struct macro_definition *d;
769 k = check_for_redefinition (source, line,
770 name, macro_function_like,
774 /* See comments about duplicate keys in macro_define_object. */
775 if (k && ! key_compare (k, name, source, line))
778 /* We should also check here that all the argument names in ARGV are
781 k = new_macro_key (t, name, source, line);
782 d = new_macro_definition (t, macro_function_like, argc, argv, replacement);
783 splay_tree_insert (t->definitions, (splay_tree_key) k, (splay_tree_value) d);
788 macro_undef (struct macro_source_file *source, int line,
791 splay_tree_node n = find_definition (name, source, line);
795 /* This function is the only place a macro's end-of-scope
796 location gets set to anything other than "end of the
797 compilation unit" (i.e., end_file is zero). So if this macro
798 already has its end-of-scope set, then we're probably seeing
799 a second #undefinition for the same #definition. */
800 struct macro_key *key = (struct macro_key *) n->key;
804 static struct deprecated_complaint double_undef = {
805 "macro '%s' is #undefined twice, at %s:%d and %s:%d",
808 complain (&double_undef, name, source->filename, line,
809 key->end_file->filename, key->end_line);
812 /* Whatever the case, wipe out the old ending point, and
813 make this the ending point. */
814 key->end_file = source;
815 key->end_line = line;
819 /* According to the ISO C standard, an #undef for a symbol that
820 has no macro definition in scope is ignored. So we should
823 static struct deprecated_complaint no_macro_to_undefine = {
824 "no definition for macro `%s' in scope to #undef at %s:%d",
827 complain (&no_macro_to_undefine, name, source->filename, line);
833 struct macro_definition *
834 macro_lookup_definition (struct macro_source_file *source,
835 int line, const char *name)
837 splay_tree_node n = find_definition (name, source, line);
840 return (struct macro_definition *) n->value;
846 struct macro_source_file *
847 macro_definition_location (struct macro_source_file *source,
850 int *definition_line)
852 splay_tree_node n = find_definition (name, source, line);
856 struct macro_key *key = (struct macro_key *) n->key;
857 *definition_line = key->start_line;
858 return key->start_file;
866 /* Creating and freeing macro tables. */
870 new_macro_table (struct obstack *obstack,
873 struct macro_table *t;
875 /* First, get storage for the `struct macro_table' itself. */
877 t = obstack_alloc (obstack, sizeof (*t));
879 t = xmalloc (sizeof (*t));
881 memset (t, 0, sizeof (*t));
882 t->obstack = obstack;
884 t->main_source = NULL;
885 t->definitions = (splay_tree_new_with_allocator
887 ((splay_tree_delete_key_fn) macro_tree_delete_key),
888 ((splay_tree_delete_value_fn) macro_tree_delete_value),
889 ((splay_tree_allocate_fn) macro_alloc),
890 ((splay_tree_deallocate_fn) macro_free),
898 free_macro_table (struct macro_table *table)
900 /* Free the source file tree. */
901 free_macro_source_file (table->main_source);
903 /* Free the table of macro definitions. */
904 splay_tree_delete (table->definitions);