1 /* C preprocessor macro tables for GDB.
2 Copyright (C) 2002, 2007 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 3 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, see <http://www.gnu.org/licenses/>. */
21 #include "gdb_obstack.h"
22 #include "splay-tree.h"
27 #include "gdb_assert.h"
29 #include "complaints.h"
32 /* The macro table structure. */
36 /* The obstack this table's data should be allocated in, or zero if
37 we should use xmalloc. */
38 struct obstack
*obstack
;
40 /* The bcache we should use to hold macro names, argument names, and
41 definitions, or zero if we should use xmalloc. */
42 struct bcache
*bcache
;
44 /* The main source file for this compilation unit --- the one whose
45 name was given to the compiler. This is the root of the
46 #inclusion tree; everything else is #included from here. */
47 struct macro_source_file
*main_source
;
49 /* The table of macro definitions. This is a splay tree (an ordered
50 binary tree that stays balanced, effectively), sorted by macro
51 name. Where a macro gets defined more than once (presumably with
52 an #undefinition in between), we sort the definitions by the
53 order they would appear in the preprocessor's output. That is,
54 if `a.c' #includes `m.h' and then #includes `n.h', and both
55 header files #define X (with an #undef somewhere in between),
56 then the definition from `m.h' appears in our splay tree before
59 The splay tree's keys are `struct macro_key' pointers;
60 the values are `struct macro_definition' pointers.
62 The splay tree, its nodes, and the keys and values are allocated
63 in obstack, if it's non-zero, or with xmalloc otherwise. The
64 macro names, argument names, argument name arrays, and definition
65 strings are all allocated in bcache, if non-zero, or with xmalloc
67 splay_tree definitions
;
72 /* Allocation and freeing functions. */
74 /* Allocate SIZE bytes of memory appropriately for the macro table T.
75 This just checks whether T has an obstack, or whether its pieces
76 should be allocated with xmalloc. */
78 macro_alloc (int size
, struct macro_table
*t
)
81 return obstack_alloc (t
->obstack
, size
);
83 return xmalloc (size
);
88 macro_free (void *object
, struct macro_table
*t
)
90 gdb_assert (! t
->obstack
);
95 /* If the macro table T has a bcache, then cache the LEN bytes at ADDR
96 there, and return the cached copy. Otherwise, just xmalloc a copy
97 of the bytes, and return a pointer to that. */
99 macro_bcache (struct macro_table
*t
, const void *addr
, int len
)
102 return bcache (addr
, len
, t
->bcache
);
105 void *copy
= xmalloc (len
);
106 memcpy (copy
, addr
, len
);
112 /* If the macro table T has a bcache, cache the null-terminated string
113 S there, and return a pointer to the cached copy. Otherwise,
114 xmalloc a copy and return that. */
116 macro_bcache_str (struct macro_table
*t
, const char *s
)
118 return (char *) macro_bcache (t
, s
, strlen (s
) + 1);
122 /* Free a possibly bcached object OBJ. That is, if the macro table T
123 has a bcache, it's an error; otherwise, xfree OBJ. */
125 macro_bcache_free (struct macro_table
*t
, void *obj
)
127 gdb_assert (! t
->bcache
);
133 /* Macro tree keys, w/their comparison, allocation, and freeing functions. */
135 /* A key in the splay tree. */
138 /* The table we're in. We only need this in order to free it, since
139 the splay tree library's key and value freeing functions require
140 that the key or value contain all the information needed to free
142 struct macro_table
*table
;
144 /* The name of the macro. This is in the table's bcache, if it has
148 /* The source file and line number where the definition's scope
149 begins. This is also the line of the definition itself. */
150 struct macro_source_file
*start_file
;
153 /* The first source file and line after the definition's scope.
154 (That is, the scope does not include this endpoint.) If end_file
155 is zero, then the definition extends to the end of the
157 struct macro_source_file
*end_file
;
162 /* Return the #inclusion depth of the source file FILE. This is the
163 number of #inclusions it took to reach this file. For the main
164 source file, the #inclusion depth is zero; for a file it #includes
165 directly, the depth would be one; and so on. */
167 inclusion_depth (struct macro_source_file
*file
)
171 for (depth
= 0; file
->included_by
; depth
++)
172 file
= file
->included_by
;
178 /* Compare two source locations (from the same compilation unit).
179 This is part of the comparison function for the tree of
182 LINE1 and LINE2 are line numbers in the source files FILE1 and
183 FILE2. Return a value:
184 - less than zero if {LINE,FILE}1 comes before {LINE,FILE}2,
185 - greater than zero if {LINE,FILE}1 comes after {LINE,FILE}2, or
186 - zero if they are equal.
188 When the two locations are in different source files --- perhaps
189 one is in a header, while another is in the main source file --- we
190 order them by where they would appear in the fully pre-processed
191 sources, where all the #included files have been substituted into
194 compare_locations (struct macro_source_file
*file1
, int line1
,
195 struct macro_source_file
*file2
, int line2
)
197 /* We want to treat positions in an #included file as coming *after*
198 the line containing the #include, but *before* the line after the
199 include. As we walk up the #inclusion tree toward the main
200 source file, we update fileX and lineX as we go; includedX
201 indicates whether the original position was from the #included
206 /* If a file is zero, that means "end of compilation unit." Handle
218 /* If the two files are not the same, find their common ancestor in
219 the #inclusion tree. */
222 /* If one file is deeper than the other, walk up the #inclusion
223 chain until the two files are at least at the same *depth*.
224 Then, walk up both files in synchrony until they're the same
225 file. That file is the common ancestor. */
226 int depth1
= inclusion_depth (file1
);
227 int depth2
= inclusion_depth (file2
);
229 /* Only one of these while loops will ever execute in any given
231 while (depth1
> depth2
)
233 line1
= file1
->included_at_line
;
234 file1
= file1
->included_by
;
238 while (depth2
> depth1
)
240 line2
= file2
->included_at_line
;
241 file2
= file2
->included_by
;
246 /* Now both file1 and file2 are at the same depth. Walk toward
247 the root of the tree until we find where the branches meet. */
248 while (file1
!= file2
)
250 line1
= file1
->included_at_line
;
251 file1
= file1
->included_by
;
252 /* At this point, we know that the case the includedX flags
253 are trying to deal with won't come up, but we'll just
254 maintain them anyway. */
257 line2
= file2
->included_at_line
;
258 file2
= file2
->included_by
;
261 /* Sanity check. If file1 and file2 are really from the
262 same compilation unit, then they should both be part of
263 the same tree, and this shouldn't happen. */
264 gdb_assert (file1
&& file2
);
268 /* Now we've got two line numbers in the same file. */
271 /* They can't both be from #included files. Then we shouldn't
272 have walked up this far. */
273 gdb_assert (! included1
|| ! included2
);
275 /* Any #included position comes after a non-#included position
276 with the same line number in the #including file. */
285 return line1
- line2
;
289 /* Compare a macro key KEY against NAME, the source file FILE, and
292 Sort definitions by name; for two definitions with the same name,
293 place the one whose definition comes earlier before the one whose
294 definition comes later.
296 Return -1, 0, or 1 if key comes before, is identical to, or comes
297 after NAME, FILE, and LINE. */
299 key_compare (struct macro_key
*key
,
300 const char *name
, struct macro_source_file
*file
, int line
)
302 int names
= strcmp (key
->name
, name
);
306 return compare_locations (key
->start_file
, key
->start_line
,
311 /* The macro tree comparison function, typed for the splay tree
312 library's happiness. */
314 macro_tree_compare (splay_tree_key untyped_key1
,
315 splay_tree_key untyped_key2
)
317 struct macro_key
*key1
= (struct macro_key
*) untyped_key1
;
318 struct macro_key
*key2
= (struct macro_key
*) untyped_key2
;
320 return key_compare (key1
, key2
->name
, key2
->start_file
, key2
->start_line
);
324 /* Construct a new macro key node for a macro in table T whose name is
325 NAME, and whose scope starts at LINE in FILE; register the name in
327 static struct macro_key
*
328 new_macro_key (struct macro_table
*t
,
330 struct macro_source_file
*file
,
333 struct macro_key
*k
= macro_alloc (sizeof (*k
), t
);
335 memset (k
, 0, sizeof (*k
));
337 k
->name
= macro_bcache_str (t
, name
);
338 k
->start_file
= file
;
339 k
->start_line
= line
;
347 macro_tree_delete_key (void *untyped_key
)
349 struct macro_key
*key
= (struct macro_key
*) untyped_key
;
351 macro_bcache_free (key
->table
, (char *) key
->name
);
352 macro_free (key
, key
->table
);
357 /* Building and querying the tree of #included files. */
360 /* Allocate and initialize a new source file structure. */
361 static struct macro_source_file
*
362 new_source_file (struct macro_table
*t
,
363 const char *filename
)
365 /* Get space for the source file structure itself. */
366 struct macro_source_file
*f
= macro_alloc (sizeof (*f
), t
);
368 memset (f
, 0, sizeof (*f
));
370 f
->filename
= macro_bcache_str (t
, filename
);
377 /* Free a source file, and all the source files it #included. */
379 free_macro_source_file (struct macro_source_file
*src
)
381 struct macro_source_file
*child
, *next_child
;
383 /* Free this file's children. */
384 for (child
= src
->includes
; child
; child
= next_child
)
386 next_child
= child
->next_included
;
387 free_macro_source_file (child
);
390 macro_bcache_free (src
->table
, (char *) src
->filename
);
391 macro_free (src
, src
->table
);
395 struct macro_source_file
*
396 macro_set_main (struct macro_table
*t
,
397 const char *filename
)
399 /* You can't change a table's main source file. What would that do
401 gdb_assert (! t
->main_source
);
403 t
->main_source
= new_source_file (t
, filename
);
405 return t
->main_source
;
409 struct macro_source_file
*
410 macro_main (struct macro_table
*t
)
412 gdb_assert (t
->main_source
);
414 return t
->main_source
;
418 struct macro_source_file
*
419 macro_include (struct macro_source_file
*source
,
421 const char *included
)
423 struct macro_source_file
*new;
424 struct macro_source_file
**link
;
426 /* Find the right position in SOURCE's `includes' list for the new
427 file. Skip inclusions at earlier lines, until we find one at the
428 same line or later --- or until the end of the list. */
429 for (link
= &source
->includes
;
430 *link
&& (*link
)->included_at_line
< line
;
431 link
= &(*link
)->next_included
)
434 /* Did we find another file already #included at the same line as
436 if (*link
&& line
== (*link
)->included_at_line
)
438 /* This means the compiler is emitting bogus debug info. (GCC
439 circa March 2002 did this.) It also means that the splay
440 tree ordering function, macro_tree_compare, will abort,
441 because it can't tell which #inclusion came first. But GDB
442 should tolerate bad debug info. So:
445 complaint (&symfile_complaints
,
446 _("both `%s' and `%s' allegedly #included at %s:%d"), included
,
447 (*link
)->filename
, source
->filename
, line
);
449 /* Now, choose a new, unoccupied line number for this
450 #inclusion, after the alleged #inclusion line. */
451 while (*link
&& line
== (*link
)->included_at_line
)
453 /* This line number is taken, so try the next line. */
455 link
= &(*link
)->next_included
;
459 /* At this point, we know that LINE is an unused line number, and
460 *LINK points to the entry an #inclusion at that line should
462 new = new_source_file (source
->table
, included
);
463 new->included_by
= source
;
464 new->included_at_line
= line
;
465 new->next_included
= *link
;
472 struct macro_source_file
*
473 macro_lookup_inclusion (struct macro_source_file
*source
, const char *name
)
475 /* Is SOURCE itself named NAME? */
476 if (strcmp (name
, source
->filename
) == 0)
479 /* The filename in the source structure is probably a full path, but
480 NAME could be just the final component of the name. */
482 int name_len
= strlen (name
);
483 int src_name_len
= strlen (source
->filename
);
485 /* We do mean < here, and not <=; if the lengths are the same,
486 then the strcmp above should have triggered, and we need to
487 check for a slash here. */
488 if (name_len
< src_name_len
489 && source
->filename
[src_name_len
- name_len
- 1] == '/'
490 && strcmp (name
, source
->filename
+ src_name_len
- name_len
) == 0)
494 /* It's not us. Try all our children, and return the lowest. */
496 struct macro_source_file
*child
;
497 struct macro_source_file
*best
= NULL
;
500 for (child
= source
->includes
; child
; child
= child
->next_included
)
502 struct macro_source_file
*result
503 = macro_lookup_inclusion (child
, name
);
507 int result_depth
= inclusion_depth (result
);
509 if (! best
|| result_depth
< best_depth
)
512 best_depth
= result_depth
;
523 /* Registering and looking up macro definitions. */
526 /* Construct a definition for a macro in table T. Cache all strings,
527 and the macro_definition structure itself, in T's bcache. */
528 static struct macro_definition
*
529 new_macro_definition (struct macro_table
*t
,
530 enum macro_kind kind
,
531 int argc
, const char **argv
,
532 const char *replacement
)
534 struct macro_definition
*d
= macro_alloc (sizeof (*d
), t
);
536 memset (d
, 0, sizeof (*d
));
539 d
->replacement
= macro_bcache_str (t
, replacement
);
541 if (kind
== macro_function_like
)
544 const char **cached_argv
;
545 int cached_argv_size
= argc
* sizeof (*cached_argv
);
547 /* Bcache all the arguments. */
548 cached_argv
= alloca (cached_argv_size
);
549 for (i
= 0; i
< argc
; i
++)
550 cached_argv
[i
] = macro_bcache_str (t
, argv
[i
]);
552 /* Now bcache the array of argument pointers itself. */
553 d
->argv
= macro_bcache (t
, cached_argv
, cached_argv_size
);
557 /* We don't bcache the entire definition structure because it's got
558 a pointer to the macro table in it; since each compilation unit
559 has its own macro table, you'd only get bcache hits for identical
560 definitions within a compilation unit, which seems unlikely.
562 "So, why do macro definitions have pointers to their macro tables
563 at all?" Well, when the splay tree library wants to free a
564 node's value, it calls the value freeing function with nothing
565 but the value itself. It makes the (apparently reasonable)
566 assumption that the value carries enough information to free
567 itself. But not all macro tables have bcaches, so not all macro
568 definitions would be bcached. There's no way to tell whether a
569 given definition is bcached without knowing which table the
570 definition belongs to. ... blah. The thing's only sixteen
571 bytes anyway, and we can still bcache the name, args, and
572 definition, so we just don't bother bcaching the definition
578 /* Free a macro definition. */
580 macro_tree_delete_value (void *untyped_definition
)
582 struct macro_definition
*d
= (struct macro_definition
*) untyped_definition
;
583 struct macro_table
*t
= d
->table
;
585 if (d
->kind
== macro_function_like
)
589 for (i
= 0; i
< d
->argc
; i
++)
590 macro_bcache_free (t
, (char *) d
->argv
[i
]);
591 macro_bcache_free (t
, (char **) d
->argv
);
594 macro_bcache_free (t
, (char *) d
->replacement
);
599 /* Find the splay tree node for the definition of NAME at LINE in
600 SOURCE, or zero if there is none. */
601 static splay_tree_node
602 find_definition (const char *name
,
603 struct macro_source_file
*file
,
606 struct macro_table
*t
= file
->table
;
609 /* Construct a macro_key object, just for the query. */
610 struct macro_key query
;
613 query
.start_file
= file
;
614 query
.start_line
= line
;
615 query
.end_file
= NULL
;
617 n
= splay_tree_lookup (t
->definitions
, (splay_tree_key
) &query
);
620 /* It's okay for us to do two queries like this: the real work
621 of the searching is done when we splay, and splaying the tree
622 a second time at the same key is a constant time operation.
623 If this still bugs you, you could always just extend the
624 splay tree library with a predecessor-or-equal operation, and
626 splay_tree_node pred
= splay_tree_predecessor (t
->definitions
,
627 (splay_tree_key
) &query
);
631 /* Make sure this predecessor actually has the right name.
632 We just want to search within a given name's definitions. */
633 struct macro_key
*found
= (struct macro_key
*) pred
->key
;
635 if (strcmp (found
->name
, name
) == 0)
642 struct macro_key
*found
= (struct macro_key
*) n
->key
;
644 /* Okay, so this definition has the right name, and its scope
645 begins before the given source location. But does its scope
646 end after the given source location? */
647 if (compare_locations (file
, line
, found
->end_file
, found
->end_line
) < 0)
657 /* If NAME already has a definition in scope at LINE in SOURCE, return
658 the key. If the old definition is different from the definition
659 given by KIND, ARGC, ARGV, and REPLACEMENT, complain, too.
660 Otherwise, return zero. (ARGC and ARGV are meaningless unless KIND
661 is `macro_function_like'.) */
662 static struct macro_key
*
663 check_for_redefinition (struct macro_source_file
*source
, int line
,
664 const char *name
, enum macro_kind kind
,
665 int argc
, const char **argv
,
666 const char *replacement
)
668 splay_tree_node n
= find_definition (name
, source
, line
);
672 struct macro_key
*found_key
= (struct macro_key
*) n
->key
;
673 struct macro_definition
*found_def
674 = (struct macro_definition
*) n
->value
;
677 /* Is this definition the same as the existing one?
678 According to the standard, this comparison needs to be done
679 on lists of tokens, not byte-by-byte, as we do here. But
680 that's too hard for us at the moment, and comparing
681 byte-by-byte will only yield false negatives (i.e., extra
682 warning messages), not false positives (i.e., unnoticed
683 definition changes). */
684 if (kind
!= found_def
->kind
)
686 else if (strcmp (replacement
, found_def
->replacement
))
688 else if (kind
== macro_function_like
)
690 if (argc
!= found_def
->argc
)
696 for (i
= 0; i
< argc
; i
++)
697 if (strcmp (argv
[i
], found_def
->argv
[i
]))
704 complaint (&symfile_complaints
,
705 _("macro `%s' redefined at %s:%d; original definition at %s:%d"),
706 name
, source
->filename
, line
,
707 found_key
->start_file
->filename
, found_key
->start_line
);
718 macro_define_object (struct macro_source_file
*source
, int line
,
719 const char *name
, const char *replacement
)
721 struct macro_table
*t
= source
->table
;
723 struct macro_definition
*d
;
725 k
= check_for_redefinition (source
, line
,
726 name
, macro_object_like
,
730 /* If we're redefining a symbol, and the existing key would be
731 identical to our new key, then the splay_tree_insert function
732 will try to delete the old definition. When the definition is
733 living on an obstack, this isn't a happy thing.
735 Since this only happens in the presence of questionable debug
736 info, we just ignore all definitions after the first. The only
737 case I know of where this arises is in GCC's output for
738 predefined macros, and all the definitions are the same in that
740 if (k
&& ! key_compare (k
, name
, source
, line
))
743 k
= new_macro_key (t
, name
, source
, line
);
744 d
= new_macro_definition (t
, macro_object_like
, 0, 0, replacement
);
745 splay_tree_insert (t
->definitions
, (splay_tree_key
) k
, (splay_tree_value
) d
);
750 macro_define_function (struct macro_source_file
*source
, int line
,
751 const char *name
, int argc
, const char **argv
,
752 const char *replacement
)
754 struct macro_table
*t
= source
->table
;
756 struct macro_definition
*d
;
758 k
= check_for_redefinition (source
, line
,
759 name
, macro_function_like
,
763 /* See comments about duplicate keys in macro_define_object. */
764 if (k
&& ! key_compare (k
, name
, source
, line
))
767 /* We should also check here that all the argument names in ARGV are
770 k
= new_macro_key (t
, name
, source
, line
);
771 d
= new_macro_definition (t
, macro_function_like
, argc
, argv
, replacement
);
772 splay_tree_insert (t
->definitions
, (splay_tree_key
) k
, (splay_tree_value
) d
);
777 macro_undef (struct macro_source_file
*source
, int line
,
780 splay_tree_node n
= find_definition (name
, source
, line
);
784 /* This function is the only place a macro's end-of-scope
785 location gets set to anything other than "end of the
786 compilation unit" (i.e., end_file is zero). So if this macro
787 already has its end-of-scope set, then we're probably seeing
788 a second #undefinition for the same #definition. */
789 struct macro_key
*key
= (struct macro_key
*) n
->key
;
793 complaint (&symfile_complaints
,
794 _("macro '%s' is #undefined twice, at %s:%d and %s:%d"), name
,
795 source
->filename
, line
, key
->end_file
->filename
,
799 /* Whatever the case, wipe out the old ending point, and
800 make this the ending point. */
801 key
->end_file
= source
;
802 key
->end_line
= line
;
806 /* According to the ISO C standard, an #undef for a symbol that
807 has no macro definition in scope is ignored. So we should
810 complaint (&symfile_complaints
,
811 _("no definition for macro `%s' in scope to #undef at %s:%d"),
812 name
, source
->filename
, line
);
818 struct macro_definition
*
819 macro_lookup_definition (struct macro_source_file
*source
,
820 int line
, const char *name
)
822 splay_tree_node n
= find_definition (name
, source
, line
);
825 return (struct macro_definition
*) n
->value
;
831 struct macro_source_file
*
832 macro_definition_location (struct macro_source_file
*source
,
835 int *definition_line
)
837 splay_tree_node n
= find_definition (name
, source
, line
);
841 struct macro_key
*key
= (struct macro_key
*) n
->key
;
842 *definition_line
= key
->start_line
;
843 return key
->start_file
;
851 /* Creating and freeing macro tables. */
855 new_macro_table (struct obstack
*obstack
,
858 struct macro_table
*t
;
860 /* First, get storage for the `struct macro_table' itself. */
862 t
= obstack_alloc (obstack
, sizeof (*t
));
864 t
= xmalloc (sizeof (*t
));
866 memset (t
, 0, sizeof (*t
));
867 t
->obstack
= obstack
;
869 t
->main_source
= NULL
;
870 t
->definitions
= (splay_tree_new_with_allocator
872 ((splay_tree_delete_key_fn
) macro_tree_delete_key
),
873 ((splay_tree_delete_value_fn
) macro_tree_delete_value
),
874 ((splay_tree_allocate_fn
) macro_alloc
),
875 ((splay_tree_deallocate_fn
) macro_free
),
883 free_macro_table (struct macro_table
*table
)
885 /* Free the source file tree. */
886 free_macro_source_file (table
->main_source
);
888 /* Free the table of macro definitions. */
889 splay_tree_delete (table
->definitions
);