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 complaint (&symfile_complaints
,
449 "both `%s' and `%s' allegedly #included at %s:%d", included
,
450 (*link
)->filename
, source
->filename
, line
);
452 /* Now, choose a new, unoccupied line number for this
453 #inclusion, after the alleged #inclusion line. */
454 while (*link
&& line
== (*link
)->included_at_line
)
456 /* This line number is taken, so try the next line. */
458 link
= &(*link
)->next_included
;
462 /* At this point, we know that LINE is an unused line number, and
463 *LINK points to the entry an #inclusion at that line should
465 new = new_source_file (source
->table
, included
);
466 new->included_by
= source
;
467 new->included_at_line
= line
;
468 new->next_included
= *link
;
475 struct macro_source_file
*
476 macro_lookup_inclusion (struct macro_source_file
*source
, const char *name
)
478 /* Is SOURCE itself named NAME? */
479 if (strcmp (name
, source
->filename
) == 0)
482 /* The filename in the source structure is probably a full path, but
483 NAME could be just the final component of the name. */
485 int name_len
= strlen (name
);
486 int src_name_len
= strlen (source
->filename
);
488 /* We do mean < here, and not <=; if the lengths are the same,
489 then the strcmp above should have triggered, and we need to
490 check for a slash here. */
491 if (name_len
< src_name_len
492 && source
->filename
[src_name_len
- name_len
- 1] == '/'
493 && strcmp (name
, source
->filename
+ src_name_len
- name_len
) == 0)
497 /* It's not us. Try all our children, and return the lowest. */
499 struct macro_source_file
*child
;
500 struct macro_source_file
*best
= NULL
;
503 for (child
= source
->includes
; child
; child
= child
->next_included
)
505 struct macro_source_file
*result
506 = macro_lookup_inclusion (child
, name
);
510 int result_depth
= inclusion_depth (result
);
512 if (! best
|| result_depth
< best_depth
)
515 best_depth
= result_depth
;
526 /* Registering and looking up macro definitions. */
529 /* Construct a definition for a macro in table T. Cache all strings,
530 and the macro_definition structure itself, in T's bcache. */
531 static struct macro_definition
*
532 new_macro_definition (struct macro_table
*t
,
533 enum macro_kind kind
,
534 int argc
, const char **argv
,
535 const char *replacement
)
537 struct macro_definition
*d
= macro_alloc (sizeof (*d
), t
);
539 memset (d
, 0, sizeof (*d
));
542 d
->replacement
= macro_bcache_str (t
, replacement
);
544 if (kind
== macro_function_like
)
547 const char **cached_argv
;
548 int cached_argv_size
= argc
* sizeof (*cached_argv
);
550 /* Bcache all the arguments. */
551 cached_argv
= alloca (cached_argv_size
);
552 for (i
= 0; i
< argc
; i
++)
553 cached_argv
[i
] = macro_bcache_str (t
, argv
[i
]);
555 /* Now bcache the array of argument pointers itself. */
556 d
->argv
= macro_bcache (t
, cached_argv
, cached_argv_size
);
560 /* We don't bcache the entire definition structure because it's got
561 a pointer to the macro table in it; since each compilation unit
562 has its own macro table, you'd only get bcache hits for identical
563 definitions within a compilation unit, which seems unlikely.
565 "So, why do macro definitions have pointers to their macro tables
566 at all?" Well, when the splay tree library wants to free a
567 node's value, it calls the value freeing function with nothing
568 but the value itself. It makes the (apparently reasonable)
569 assumption that the value carries enough information to free
570 itself. But not all macro tables have bcaches, so not all macro
571 definitions would be bcached. There's no way to tell whether a
572 given definition is bcached without knowing which table the
573 definition belongs to. ... blah. The thing's only sixteen
574 bytes anyway, and we can still bcache the name, args, and
575 definition, so we just don't bother bcaching the definition
581 /* Free a macro definition. */
583 macro_tree_delete_value (void *untyped_definition
)
585 struct macro_definition
*d
= (struct macro_definition
*) untyped_definition
;
586 struct macro_table
*t
= d
->table
;
588 if (d
->kind
== macro_function_like
)
592 for (i
= 0; i
< d
->argc
; i
++)
593 macro_bcache_free (t
, (char *) d
->argv
[i
]);
594 macro_bcache_free (t
, (char **) d
->argv
);
597 macro_bcache_free (t
, (char *) d
->replacement
);
602 /* Find the splay tree node for the definition of NAME at LINE in
603 SOURCE, or zero if there is none. */
604 static splay_tree_node
605 find_definition (const char *name
,
606 struct macro_source_file
*file
,
609 struct macro_table
*t
= file
->table
;
612 /* Construct a macro_key object, just for the query. */
613 struct macro_key query
;
616 query
.start_file
= file
;
617 query
.start_line
= line
;
618 query
.end_file
= NULL
;
620 n
= splay_tree_lookup (t
->definitions
, (splay_tree_key
) &query
);
623 /* It's okay for us to do two queries like this: the real work
624 of the searching is done when we splay, and splaying the tree
625 a second time at the same key is a constant time operation.
626 If this still bugs you, you could always just extend the
627 splay tree library with a predecessor-or-equal operation, and
629 splay_tree_node pred
= splay_tree_predecessor (t
->definitions
,
630 (splay_tree_key
) &query
);
634 /* Make sure this predecessor actually has the right name.
635 We just want to search within a given name's definitions. */
636 struct macro_key
*found
= (struct macro_key
*) pred
->key
;
638 if (strcmp (found
->name
, name
) == 0)
645 struct macro_key
*found
= (struct macro_key
*) n
->key
;
647 /* Okay, so this definition has the right name, and its scope
648 begins before the given source location. But does its scope
649 end after the given source location? */
650 if (compare_locations (file
, line
, found
->end_file
, found
->end_line
) < 0)
660 /* If NAME already has a definition in scope at LINE in SOURCE, return
661 the key. If the old definition is different from the definition
662 given by KIND, ARGC, ARGV, and REPLACEMENT, complain, too.
663 Otherwise, return zero. (ARGC and ARGV are meaningless unless KIND
664 is `macro_function_like'.) */
665 static struct macro_key
*
666 check_for_redefinition (struct macro_source_file
*source
, int line
,
667 const char *name
, enum macro_kind kind
,
668 int argc
, const char **argv
,
669 const char *replacement
)
671 splay_tree_node n
= find_definition (name
, source
, line
);
675 struct macro_key
*found_key
= (struct macro_key
*) n
->key
;
676 struct macro_definition
*found_def
677 = (struct macro_definition
*) n
->value
;
680 /* Is this definition the same as the existing one?
681 According to the standard, this comparison needs to be done
682 on lists of tokens, not byte-by-byte, as we do here. But
683 that's too hard for us at the moment, and comparing
684 byte-by-byte will only yield false negatives (i.e., extra
685 warning messages), not false positives (i.e., unnoticed
686 definition changes). */
687 if (kind
!= found_def
->kind
)
689 else if (strcmp (replacement
, found_def
->replacement
))
691 else if (kind
== macro_function_like
)
693 if (argc
!= found_def
->argc
)
699 for (i
= 0; i
< argc
; i
++)
700 if (strcmp (argv
[i
], found_def
->argv
[i
]))
707 complaint (&symfile_complaints
,
708 "macro `%s' redefined at %s:%d; original definition at %s:%d",
709 name
, source
->filename
, line
,
710 found_key
->start_file
->filename
, found_key
->start_line
);
721 macro_define_object (struct macro_source_file
*source
, int line
,
722 const char *name
, const char *replacement
)
724 struct macro_table
*t
= source
->table
;
726 struct macro_definition
*d
;
728 k
= check_for_redefinition (source
, line
,
729 name
, macro_object_like
,
733 /* If we're redefining a symbol, and the existing key would be
734 identical to our new key, then the splay_tree_insert function
735 will try to delete the old definition. When the definition is
736 living on an obstack, this isn't a happy thing.
738 Since this only happens in the presence of questionable debug
739 info, we just ignore all definitions after the first. The only
740 case I know of where this arises is in GCC's output for
741 predefined macros, and all the definitions are the same in that
743 if (k
&& ! key_compare (k
, name
, source
, line
))
746 k
= new_macro_key (t
, name
, source
, line
);
747 d
= new_macro_definition (t
, macro_object_like
, 0, 0, replacement
);
748 splay_tree_insert (t
->definitions
, (splay_tree_key
) k
, (splay_tree_value
) d
);
753 macro_define_function (struct macro_source_file
*source
, int line
,
754 const char *name
, int argc
, const char **argv
,
755 const char *replacement
)
757 struct macro_table
*t
= source
->table
;
759 struct macro_definition
*d
;
761 k
= check_for_redefinition (source
, line
,
762 name
, macro_function_like
,
766 /* See comments about duplicate keys in macro_define_object. */
767 if (k
&& ! key_compare (k
, name
, source
, line
))
770 /* We should also check here that all the argument names in ARGV are
773 k
= new_macro_key (t
, name
, source
, line
);
774 d
= new_macro_definition (t
, macro_function_like
, argc
, argv
, replacement
);
775 splay_tree_insert (t
->definitions
, (splay_tree_key
) k
, (splay_tree_value
) d
);
780 macro_undef (struct macro_source_file
*source
, int line
,
783 splay_tree_node n
= find_definition (name
, source
, line
);
787 /* This function is the only place a macro's end-of-scope
788 location gets set to anything other than "end of the
789 compilation unit" (i.e., end_file is zero). So if this macro
790 already has its end-of-scope set, then we're probably seeing
791 a second #undefinition for the same #definition. */
792 struct macro_key
*key
= (struct macro_key
*) n
->key
;
796 complaint (&symfile_complaints
,
797 "macro '%s' is #undefined twice, at %s:%d and %s:%d", name
,
798 source
->filename
, line
, key
->end_file
->filename
,
802 /* Whatever the case, wipe out the old ending point, and
803 make this the ending point. */
804 key
->end_file
= source
;
805 key
->end_line
= line
;
809 /* According to the ISO C standard, an #undef for a symbol that
810 has no macro definition in scope is ignored. So we should
813 complaint (&symfile_complaints
,
814 "no definition for macro `%s' in scope to #undef at %s:%d",
815 name
, source
->filename
, line
);
821 struct macro_definition
*
822 macro_lookup_definition (struct macro_source_file
*source
,
823 int line
, const char *name
)
825 splay_tree_node n
= find_definition (name
, source
, line
);
828 return (struct macro_definition
*) n
->value
;
834 struct macro_source_file
*
835 macro_definition_location (struct macro_source_file
*source
,
838 int *definition_line
)
840 splay_tree_node n
= find_definition (name
, source
, line
);
844 struct macro_key
*key
= (struct macro_key
*) n
->key
;
845 *definition_line
= key
->start_line
;
846 return key
->start_file
;
854 /* Creating and freeing macro tables. */
858 new_macro_table (struct obstack
*obstack
,
861 struct macro_table
*t
;
863 /* First, get storage for the `struct macro_table' itself. */
865 t
= obstack_alloc (obstack
, sizeof (*t
));
867 t
= xmalloc (sizeof (*t
));
869 memset (t
, 0, sizeof (*t
));
870 t
->obstack
= obstack
;
872 t
->main_source
= NULL
;
873 t
->definitions
= (splay_tree_new_with_allocator
875 ((splay_tree_delete_key_fn
) macro_tree_delete_key
),
876 ((splay_tree_delete_value_fn
) macro_tree_delete_value
),
877 ((splay_tree_allocate_fn
) macro_alloc
),
878 ((splay_tree_deallocate_fn
) macro_free
),
886 free_macro_table (struct macro_table
*table
)
888 /* Free the source file tree. */
889 free_macro_source_file (table
->main_source
);
891 /* Free the table of macro definitions. */
892 splay_tree_delete (table
->definitions
);