libcpp/line-map.c

   1 /* Map logical line numbers to (source file, line number) pairs.
   2    Copyright (C) 2001-2013 Free Software Foundation, Inc.
   3
   4 This program is free software; you can redistribute it and/or modify it
   5 under the terms of the GNU General Public License as published by the
   6 Free Software Foundation; either version 3, or (at your option) any
   7 later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; see the file COPYING3.  If not see
  16 <http://www.gnu.org/licenses/>.
  17
  18  In other words, you are welcome to use, share and improve this program.
  19  You are forbidden to forbid anyone else to use, share and improve
  20  what you give them.   Help stamp out software-hoarding!  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "line-map.h"
  25 #include "cpplib.h"
  26 #include "internal.h"
  27 #include "hashtab.h"
  28
  29 static void trace_include (const struct line_maps *, const struct line_map *);
  30 static const struct line_map * linemap_ordinary_map_lookup (struct line_maps *,
  31                                                             source_location);
  32 static const struct line_map* linemap_macro_map_lookup (struct line_maps *,
  33                                                         source_location);
  34 static source_location linemap_macro_map_loc_to_def_point
  35 (const struct line_map*, source_location);
  36 static source_location linemap_macro_map_loc_unwind_toward_spelling
  37 (const struct line_map*, source_location);
  38 static source_location linemap_macro_map_loc_to_exp_point
  39 (const struct line_map*, source_location);
  40 static source_location linemap_macro_loc_to_spelling_point
  41 (struct line_maps *, source_location, const struct line_map **);
  42 static source_location linemap_macro_loc_to_def_point (struct line_maps *,
  43                                                        source_location,
  44                                                        const struct line_map **);
  45 static source_location linemap_macro_loc_to_exp_point (struct line_maps *,
  46                                                        source_location,
  47                                                        const struct line_map **);
  48
  49 /* Counters defined in macro.c.  */
  50 extern unsigned num_expanded_macros_counter;
  51 extern unsigned num_macro_tokens_counter;
  52
  53 /* Hash function for location_adhoc_data hashtable.  */
  54
  55 static hashval_t
  56 location_adhoc_data_hash (const void *l)
  57 {
  58   const struct location_adhoc_data *lb =
  59       (const struct location_adhoc_data *) l;
  60   return (hashval_t) lb->locus + (size_t) lb->data;
  61 }
  62
  63 /* Compare function for location_adhoc_data hashtable.  */
  64
  65 static int
  66 location_adhoc_data_eq (const void *l1, const void *l2)
  67 {
  68   const struct location_adhoc_data *lb1 =
  69       (const struct location_adhoc_data *) l1;
  70   const struct location_adhoc_data *lb2 =
  71       (const struct location_adhoc_data *) l2;
  72   return lb1->locus == lb2->locus && lb1->data == lb2->data;
  73 }
  74
  75 /* Update the hashtable when location_adhoc_data is reallocated.  */
  76
  77 static int
  78 location_adhoc_data_update (void **slot, void *data)
  79 {
  80   *((char **) slot) += *((long long *) data);
  81   return 1;
  82 }
  83
  84 /* Rebuild the hash table from the location adhoc data.  */
  85
  86 void
  87 rebuild_location_adhoc_htab (struct line_maps *set)
  88 {
  89   unsigned i;
  90   set->location_adhoc_data_map.htab =
  91       htab_create (100, location_adhoc_data_hash, location_adhoc_data_eq, NULL);
  92   for (i = 0; i < set->location_adhoc_data_map.curr_loc; i++)
  93     htab_find_slot (set->location_adhoc_data_map.htab,
  94                     set->location_adhoc_data_map.data + i, INSERT);
  95 }
  96
  97 /* Combine LOCUS and DATA to a combined adhoc loc.  */
  98
  99 source_location
 100 get_combined_adhoc_loc (struct line_maps *set,
 101                         source_location locus, void *data)
 102 {
 103   struct location_adhoc_data lb;
 104   struct location_adhoc_data **slot;
 105
 106   linemap_assert (data);
 107
 108   if (IS_ADHOC_LOC (locus))
 109     locus =
 110         set->location_adhoc_data_map.data[locus & MAX_SOURCE_LOCATION].locus;
 111   if (locus == 0 && data == NULL)
 112     return 0;
 113   lb.locus = locus;
 114   lb.data = data;
 115   slot = (struct location_adhoc_data **)
 116       htab_find_slot (set->location_adhoc_data_map.htab, &lb, INSERT);
 117   if (*slot == NULL)
 118     {
 119       if (set->location_adhoc_data_map.curr_loc >=
 120           set->location_adhoc_data_map.allocated)
 121         {
 122           char *orig_data = (char *) set->location_adhoc_data_map.data;
 123           long long offset;
 124           /* Cast away extern "C" from the type of xrealloc.  */
 125           line_map_realloc reallocator = (set->reallocator
 126                                           ? set->reallocator
 127                                           : (line_map_realloc) xrealloc);
 128
 129           if (set->location_adhoc_data_map.allocated == 0)
 130             set->location_adhoc_data_map.allocated = 128;
 131           else
 132             set->location_adhoc_data_map.allocated *= 2;
 133           set->location_adhoc_data_map.data = (struct location_adhoc_data *)
 134               reallocator (set->location_adhoc_data_map.data,
 135                            set->location_adhoc_data_map.allocated
 136                            * sizeof (struct location_adhoc_data));
 137           offset = (char *) (set->location_adhoc_data_map.data) - orig_data;
 138           if (set->location_adhoc_data_map.allocated > 128)
 139             htab_traverse (set->location_adhoc_data_map.htab,
 140                            location_adhoc_data_update, &offset);
 141         }
 142       *slot = set->location_adhoc_data_map.data
 143               + set->location_adhoc_data_map.curr_loc;
 144       set->location_adhoc_data_map.data[
 145           set->location_adhoc_data_map.curr_loc++] = lb;
 146     }
 147   return ((*slot) - set->location_adhoc_data_map.data) | 0x80000000;
 148 }
 149
 150 /* Return the data for the adhoc loc.  */
 151
 152 void *
 153 get_data_from_adhoc_loc (struct line_maps *set, source_location loc)
 154 {
 155   linemap_assert (IS_ADHOC_LOC (loc));
 156   return set->location_adhoc_data_map.data[loc & MAX_SOURCE_LOCATION].data;
 157 }
 158
 159 /* Return the location for the adhoc loc.  */
 160
 161 source_location
 162 get_location_from_adhoc_loc (struct line_maps *set, source_location loc)
 163 {
 164   linemap_assert (IS_ADHOC_LOC (loc));
 165   return set->location_adhoc_data_map.data[loc & MAX_SOURCE_LOCATION].locus;
 166 }
 167
 168 /* Finalize the location_adhoc_data structure.  */
 169 void
 170 location_adhoc_data_fini (struct line_maps *set)
 171 {
 172   htab_delete (set->location_adhoc_data_map.htab);
 173 }
 174
 175 /* Initialize a line map set.  */
 176
 177 void
 178 linemap_init (struct line_maps *set)
 179 {
 180   memset (set, 0, sizeof (struct line_maps));
 181   set->highest_location = RESERVED_LOCATION_COUNT - 1;
 182   set->highest_line = RESERVED_LOCATION_COUNT - 1;
 183   set->location_adhoc_data_map.htab =
 184       htab_create (100, location_adhoc_data_hash, location_adhoc_data_eq, NULL);
 185 }
 186
 187 /* Check for and warn about line_maps entered but not exited.  */
 188
 189 void
 190 linemap_check_files_exited (struct line_maps *set)
 191 {
 192   struct line_map *map;
 193   /* Depending upon whether we are handling preprocessed input or
 194      not, this can be a user error or an ICE.  */
 195   for (map = LINEMAPS_LAST_ORDINARY_MAP (set);
 196        ! MAIN_FILE_P (map);
 197        map = INCLUDED_FROM (set, map))
 198     fprintf (stderr, "line-map.c: file \"%s\" entered but not left\n",
 199              ORDINARY_MAP_FILE_NAME (map));
 200 }
 201
 202 /* Create a new line map in the line map set SET, and return it.
 203    REASON is the reason of creating the map. It determines the type
 204    of map created (ordinary or macro map). Note that ordinary maps and
 205    macro maps are allocated in different memory location.  */
 206
 207 static struct line_map *
 208 new_linemap (struct line_maps *set,
 209              enum lc_reason reason)
 210 {
 211   /* Depending on this variable, a macro map would be allocated in a
 212      different memory location than an ordinary map.  */
 213   bool macro_map_p = (reason == LC_ENTER_MACRO);
 214   struct line_map *result;
 215
 216   if (LINEMAPS_USED (set, macro_map_p) == LINEMAPS_ALLOCATED (set, macro_map_p))
 217     {
 218       /* We ran out of allocated line maps. Let's allocate more.  */
 219       unsigned alloc_size;
 220
 221       /* Cast away extern "C" from the type of xrealloc.  */
 222       line_map_realloc reallocator = (set->reallocator
 223                                       ? set->reallocator
 224                                       : (line_map_realloc) xrealloc);
 225       line_map_round_alloc_size_func round_alloc_size =
 226         set->round_alloc_size;
 227
 228       /* We are going to execute some dance to try to reduce the
 229          overhead of the memory allocator, in case we are using the
 230          ggc-page.c one.
 231
 232          The actual size of memory we are going to get back from the
 233          allocator is the smallest power of 2 that is greater than the
 234          size we requested.  So let's consider that size then.  */
 235
 236       alloc_size =
 237         (2 * LINEMAPS_ALLOCATED (set, macro_map_p) +  256)
 238         * sizeof (struct line_map);
 239
 240       /* Get the actual size of memory that is going to be allocated
 241          by the allocator.  */
 242       alloc_size = round_alloc_size (alloc_size);
 243
 244       /* Now alloc_size contains the exact memory size we would get if
 245          we have asked for the initial alloc_size amount of memory.
 246          Let's get back to the number of macro map that amounts
 247          to.  */
 248       LINEMAPS_ALLOCATED (set, macro_map_p) =
 249         alloc_size / (sizeof (struct line_map));
 250
 251       /* And now let's really do the re-allocation.  */
 252       LINEMAPS_MAPS (set, macro_map_p) =
 253         (struct line_map *) (*reallocator)
 254         (LINEMAPS_MAPS (set, macro_map_p),
 255          (LINEMAPS_ALLOCATED (set, macro_map_p)
 256           * sizeof (struct line_map)));
 257
 258       result =
 259         &LINEMAPS_MAPS (set, macro_map_p)[LINEMAPS_USED (set, macro_map_p)];
 260       memset (result, 0,
 261               ((LINEMAPS_ALLOCATED (set, macro_map_p)
 262                 - LINEMAPS_USED (set, macro_map_p))
 263                * sizeof (struct line_map)));
 264     }
 265   else
 266     result =
 267       &LINEMAPS_MAPS (set, macro_map_p)[LINEMAPS_USED (set, macro_map_p)];
 268
 269   LINEMAPS_USED (set, macro_map_p)++;
 270
 271   result->reason = reason;
 272   return result;
 273 }
 274
 275 /* Add a mapping of logical source line to physical source file and
 276    line number.
 277
 278    The text pointed to by TO_FILE must have a lifetime
 279    at least as long as the final call to lookup_line ().  An empty
 280    TO_FILE means standard input.  If reason is LC_LEAVE, and
 281    TO_FILE is NULL, then TO_FILE, TO_LINE and SYSP are given their
 282    natural values considering the file we are returning to.
 283
 284    FROM_LINE should be monotonic increasing across calls to this
 285    function.  A call to this function can relocate the previous set of
 286    maps, so any stored line_map pointers should not be used.  */
 287
 288 const struct line_map *
 289 linemap_add (struct line_maps *set, enum lc_reason reason,
 290              unsigned int sysp, const char *to_file, linenum_type to_line)
 291 {
 292   struct line_map *map;
 293   source_location start_location = set->highest_location + 1;
 294
 295   linemap_assert (!(LINEMAPS_ORDINARY_USED (set)
 296                     && (start_location
 297                         < MAP_START_LOCATION (LINEMAPS_LAST_ORDINARY_MAP (set)))));
 298
 299   /* When we enter the file for the first time reason cannot be
 300      LC_RENAME.  */
 301   linemap_assert (!(set->depth == 0 && reason == LC_RENAME));
 302
 303   /* If we are leaving the main file, return a NULL map.  */
 304   if (reason == LC_LEAVE
 305       && MAIN_FILE_P (LINEMAPS_LAST_ORDINARY_MAP (set))
 306       && to_file == NULL)
 307     {
 308       set->depth--;
 309       return NULL;
 310     }
 311
 312   map = new_linemap (set, reason);
 313
 314   if (to_file && *to_file == '\0' && reason != LC_RENAME_VERBATIM)
 315     to_file = "<stdin>";
 316
 317   if (reason == LC_RENAME_VERBATIM)
 318     reason = LC_RENAME;
 319
 320   if (reason == LC_LEAVE)
 321     {
 322       /* When we are just leaving an "included" file, and jump to the next
 323          location inside the "includer" right after the #include
 324          "included", this variable points the map in use right before the
 325          #include "included", inside the same "includer" file.  */
 326       struct line_map *from;
 327       bool error;
 328
 329       if (MAIN_FILE_P (map - 1))
 330         {
 331           /* So this _should_ means we are leaving the main file --
 332              effectively ending the compilation unit. But to_file not
 333              being NULL means the caller thinks we are leaving to
 334              another file. This is an erroneous behaviour but we'll
 335              try to recover from it. Let's pretend we are not leaving
 336              the main file.  */
 337           error = true;
 338           reason = LC_RENAME;
 339           from = map - 1;
 340         }
 341       else
 342         {
 343           /* (MAP - 1) points to the map we are leaving. The
 344              map from which (MAP - 1) got included should be the map
 345              that comes right before MAP in the same file.  */
 346           from = INCLUDED_FROM (set, map - 1);
 347           error = to_file && filename_cmp (ORDINARY_MAP_FILE_NAME (from),
 348                                            to_file);
 349         }
 350
 351       /* Depending upon whether we are handling preprocessed input or
 352          not, this can be a user error or an ICE.  */
 353       if (error)
 354         fprintf (stderr, "line-map.c: file \"%s\" left but not entered\n",
 355                  to_file);
 356
 357       /* A TO_FILE of NULL is special - we use the natural values.  */
 358       if (error || to_file == NULL)
 359         {
 360           to_file = ORDINARY_MAP_FILE_NAME (from);
 361           to_line = SOURCE_LINE (from, from[1].start_location);
 362           sysp = ORDINARY_MAP_IN_SYSTEM_HEADER_P (from);
 363         }
 364     }
 365
 366   linemap_assert (reason != LC_ENTER_MACRO);
 367   ORDINARY_MAP_IN_SYSTEM_HEADER_P (map) = sysp;
 368   MAP_START_LOCATION (map) = start_location;
 369   ORDINARY_MAP_FILE_NAME (map) = to_file;
 370   ORDINARY_MAP_STARTING_LINE_NUMBER (map) = to_line;
 371   LINEMAPS_ORDINARY_CACHE (set) = LINEMAPS_ORDINARY_USED (set) - 1;
 372   ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) = 0;
 373   set->highest_location = start_location;
 374   set->highest_line = start_location;
 375   set->max_column_hint = 0;
 376
 377   if (reason == LC_ENTER)
 378     {
 379       ORDINARY_MAP_INCLUDER_FILE_INDEX (map) =
 380         set->depth == 0 ? -1 : (int) (LINEMAPS_ORDINARY_USED (set) - 2);
 381       set->depth++;
 382       if (set->trace_includes)
 383         trace_include (set, map);
 384     }
 385   else if (reason == LC_RENAME)
 386     ORDINARY_MAP_INCLUDER_FILE_INDEX (map) =
 387       ORDINARY_MAP_INCLUDER_FILE_INDEX (&map[-1]);
 388   else if (reason == LC_LEAVE)
 389     {
 390       set->depth--;
 391       ORDINARY_MAP_INCLUDER_FILE_INDEX (map) =
 392         ORDINARY_MAP_INCLUDER_FILE_INDEX (INCLUDED_FROM (set, map - 1));
 393     }
 394
 395   return map;
 396 }
 397
 398 /* Returns TRUE if the line table set tracks token locations across
 399    macro expansion, FALSE otherwise.  */
 400
 401 bool
 402 linemap_tracks_macro_expansion_locs_p (struct line_maps *set)
 403 {
 404   return LINEMAPS_MACRO_MAPS (set) != NULL;
 405 }
 406
 407 /* Create a macro map.  A macro map encodes source locations of tokens
 408    that are part of a macro replacement-list, at a macro expansion
 409    point.  See the extensive comments of struct line_map and struct
 410    line_map_macro, in line-map.h.
 411
 412    This map shall be created when the macro is expanded.  The map
 413    encodes the source location of the expansion point of the macro as
 414    well as the "original" source location of each token that is part
 415    of the macro replacement-list.  If a macro is defined but never
 416    expanded, it has no macro map.  SET is the set of maps the macro
 417    map should be part of.  MACRO_NODE is the macro which the new macro
 418    map should encode source locations for.  EXPANSION is the location
 419    of the expansion point of MACRO. For function-like macros
 420    invocations, it's best to make it point to the closing parenthesis
 421    of the macro, rather than the the location of the first character
 422    of the macro.  NUM_TOKENS is the number of tokens that are part of
 423    the replacement-list of MACRO.
 424
 425    Note that when we run out of the integer space available for source
 426    locations, this function returns NULL.  In that case, callers of
 427    this function cannot encode {line,column} pairs into locations of
 428    macro tokens anymore.  */
 429
 430 const struct line_map *
 431 linemap_enter_macro (struct line_maps *set, struct cpp_hashnode *macro_node,
 432                      source_location expansion, unsigned int num_tokens)
 433 {
 434   struct line_map *map;
 435   source_location start_location;
 436   /* Cast away extern "C" from the type of xrealloc.  */
 437   line_map_realloc reallocator = (set->reallocator
 438                                   ? set->reallocator
 439                                   : (line_map_realloc) xrealloc);
 440
 441   start_location = LINEMAPS_MACRO_LOWEST_LOCATION (set) - num_tokens;
 442
 443   if (start_location <= set->highest_line
 444       || start_location > LINEMAPS_MACRO_LOWEST_LOCATION (set))
 445     /* We ran out of macro map space.   */
 446     return NULL;
 447
 448   map = new_linemap (set, LC_ENTER_MACRO);
 449
 450   MAP_START_LOCATION (map) = start_location;
 451   MACRO_MAP_MACRO (map) = macro_node;
 452   MACRO_MAP_NUM_MACRO_TOKENS (map) = num_tokens;
 453   MACRO_MAP_LOCATIONS (map)
 454     = (source_location*) reallocator (NULL,
 455                                       2 * num_tokens
 456                                       * sizeof (source_location));
 457   MACRO_MAP_EXPANSION_POINT_LOCATION (map) = expansion;
 458   memset (MACRO_MAP_LOCATIONS (map), 0,
 459           num_tokens * sizeof (source_location));
 460
 461   LINEMAPS_MACRO_CACHE (set) = LINEMAPS_MACRO_USED (set) - 1;
 462
 463   return map;
 464 }
 465
 466 /* Create and return a virtual location for a token that is part of a
 467    macro expansion-list at a macro expansion point.  See the comment
 468    inside struct line_map_macro to see what an expansion-list exactly
 469    is.
 470
 471    A call to this function must come after a call to
 472    linemap_enter_macro.
 473
 474    MAP is the map into which the source location is created.  TOKEN_NO
 475    is the index of the token in the macro replacement-list, starting
 476    at number 0.
 477
 478    ORIG_LOC is the location of the token outside of this macro
 479    expansion.  If the token comes originally from the macro
 480    definition, it is the locus in the macro definition; otherwise it
 481    is a location in the context of the caller of this macro expansion
 482    (which is a virtual location or a source location if the caller is
 483    itself a macro expansion or not).
 484
 485    MACRO_DEFINITION_LOC is the location in the macro definition,
 486    either of the token itself or of a macro parameter that it
 487    replaces.  */
 488
 489 source_location
 490 linemap_add_macro_token (const struct line_map *map,
 491                          unsigned int token_no,
 492                          source_location orig_loc,
 493                          source_location orig_parm_replacement_loc)
 494 {
 495   source_location result;
 496
 497   linemap_assert (linemap_macro_expansion_map_p (map));
 498   linemap_assert (token_no < MACRO_MAP_NUM_MACRO_TOKENS (map));
 499
 500   MACRO_MAP_LOCATIONS (map)[2 * token_no] = orig_loc;
 501   MACRO_MAP_LOCATIONS (map)[2 * token_no + 1] = orig_parm_replacement_loc;
 502
 503   result = MAP_START_LOCATION (map) + token_no;
 504   return result;
 505 }
 506
 507 /* Return a source_location for the start (i.e. column==0) of
 508    (physical) line TO_LINE in the current source file (as in the
 509    most recent linemap_add).   MAX_COLUMN_HINT is the highest column
 510    number we expect to use in this line (but it does not change
 511    the highest_location).  */
 512
 513 source_location
 514 linemap_line_start (struct line_maps *set, linenum_type to_line,
 515                     unsigned int max_column_hint)
 516 {
 517   struct line_map *map = LINEMAPS_LAST_ORDINARY_MAP (set);
 518   source_location highest = set->highest_location;
 519   source_location r;
 520   linenum_type last_line =
 521     SOURCE_LINE (map, set->highest_line);
 522   int line_delta = to_line - last_line;
 523   bool add_map = false;
 524
 525   if (line_delta < 0
 526       || (line_delta > 10
 527           && line_delta * ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) > 1000)
 528       || (max_column_hint >= (1U << ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map)))
 529       || (max_column_hint <= 80
 530           && ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) >= 10))
 531     {
 532       add_map = true;
 533     }
 534   else
 535     max_column_hint = set->max_column_hint;
 536   if (add_map)
 537     {
 538       int column_bits;
 539       if (max_column_hint > 100000 || highest > 0x60000000)
 540         {
 541           /* If the column number is ridiculous or we've allocated a huge
 542              number of source_locations, give up on column numbers. */
 543           max_column_hint = 0;
 544           if (highest >0x70000000)
 545             return 0;
 546           column_bits = 0;
 547         }
 548       else
 549         {
 550           column_bits = 7;
 551           while (max_column_hint >= (1U << column_bits))
 552             column_bits++;
 553           max_column_hint = 1U << column_bits;
 554         }
 555       /* Allocate the new line_map.  However, if the current map only has a
 556          single line we can sometimes just increase its column_bits instead. */
 557       if (line_delta < 0
 558           || last_line != ORDINARY_MAP_STARTING_LINE_NUMBER (map)
 559           || SOURCE_COLUMN (map, highest) >= (1U << column_bits))
 560         map = (struct line_map *) linemap_add (set, LC_RENAME,
 561                                                ORDINARY_MAP_IN_SYSTEM_HEADER_P
 562                                                (map),
 563                                                ORDINARY_MAP_FILE_NAME (map),
 564                                                to_line);
 565       ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map) = column_bits;
 566       r = (MAP_START_LOCATION (map)
 567            + ((to_line - ORDINARY_MAP_STARTING_LINE_NUMBER (map))
 568               << column_bits));
 569     }
 570   else
 571     r = highest - SOURCE_COLUMN (map, highest)
 572       + (line_delta << ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map));
 573
 574   /* Locations of ordinary tokens are always lower than locations of
 575      macro tokens.  */
 576   if (r >= LINEMAPS_MACRO_LOWEST_LOCATION (set))
 577     return 0;
 578
 579   set->highest_line = r;
 580   if (r > set->highest_location)
 581     set->highest_location = r;
 582   set->max_column_hint = max_column_hint;
 583   return r;
 584 }
 585
 586 /* Encode and return a source_location from a column number. The
 587    source line considered is the last source line used to call
 588    linemap_line_start, i.e, the last source line which a location was
 589    encoded from.  */
 590
 591 source_location
 592 linemap_position_for_column (struct line_maps *set, unsigned int to_column)
 593 {
 594   source_location r = set->highest_line;
 595
 596   linemap_assert
 597     (!linemap_macro_expansion_map_p (LINEMAPS_LAST_ORDINARY_MAP (set)));
 598
 599   if (to_column >= set->max_column_hint)
 600     {
 601       if (r >= 0xC000000 || to_column > 100000)
 602         {
 603           /* Running low on source_locations - disable column numbers.  */
 604           return r;
 605         }
 606       else
 607         {
 608           struct line_map *map = LINEMAPS_LAST_ORDINARY_MAP (set);
 609           r = linemap_line_start (set, SOURCE_LINE (map, r), to_column + 50);
 610         }
 611     }
 612   r = r + to_column;
 613   if (r >= set->highest_location)
 614     set->highest_location = r;
 615   return r;
 616 }
 617
 618 /* Encode and return a source location from a given line and
 619    column.  */
 620
 621 source_location
 622 linemap_position_for_line_and_column (struct line_map *map,
 623                                       linenum_type line,
 624                                       unsigned column)
 625 {
 626   linemap_assert (ORDINARY_MAP_STARTING_LINE_NUMBER (map) <= line);
 627
 628   return (MAP_START_LOCATION (map)
 629           + ((line - ORDINARY_MAP_STARTING_LINE_NUMBER (map))
 630              << ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map))
 631           + (column & ((1 << ORDINARY_MAP_NUMBER_OF_COLUMN_BITS (map)) - 1)));
 632 }
 633
 634 /* Given a virtual source location yielded by a map (either an
 635    ordinary or a macro map), returns that map.  */
 636
 637 const struct line_map*
 638 linemap_lookup (struct line_maps *set, source_location line)
 639 {
 640   if (IS_ADHOC_LOC (line))
 641     line = set->location_adhoc_data_map.data[line & MAX_SOURCE_LOCATION].locus;
 642   if (linemap_location_from_macro_expansion_p (set, line))
 643     return linemap_macro_map_lookup (set, line);
 644   return linemap_ordinary_map_lookup (set, line);
 645 }
 646
 647 /* Given a source location yielded by an ordinary map, returns that
 648    map.  Since the set is built chronologically, the logical lines are
 649    monotonic increasing, and so the list is sorted and we can use a
 650    binary search.  */
 651
 652 static const struct line_map *
 653 linemap_ordinary_map_lookup (struct line_maps *set, source_location line)
 654 {
 655   unsigned int md, mn, mx;
 656   const struct line_map *cached, *result;
 657
 658   if (IS_ADHOC_LOC (line))
 659     line = set->location_adhoc_data_map.data[line & MAX_SOURCE_LOCATION].locus;
 660
 661   if (set ==  NULL || line < RESERVED_LOCATION_COUNT)
 662     return NULL;
 663
 664   mn = LINEMAPS_ORDINARY_CACHE (set);
 665   mx = LINEMAPS_ORDINARY_USED (set);
 666
 667   cached = LINEMAPS_ORDINARY_MAP_AT (set, mn);
 668   /* We should get a segfault if no line_maps have been added yet.  */
 669   if (line >= MAP_START_LOCATION (cached))
 670     {
 671       if (mn + 1 == mx || line < MAP_START_LOCATION (&cached[1]))
 672         return cached;
 673     }
 674   else
 675     {
 676       mx = mn;
 677       mn = 0;
 678     }
 679
 680   while (mx - mn > 1)
 681     {
 682       md = (mn + mx) / 2;
 683       if (MAP_START_LOCATION (LINEMAPS_ORDINARY_MAP_AT (set, md)) > line)
 684         mx = md;
 685       else
 686         mn = md;
 687     }
 688
 689   LINEMAPS_ORDINARY_CACHE (set) = mn;
 690   result = LINEMAPS_ORDINARY_MAP_AT (set, mn);
 691   linemap_assert (line >= MAP_START_LOCATION (result));
 692   return result;
 693 }
 694
 695 /* Given a source location yielded by a macro map, returns that map.
 696    Since the set is built chronologically, the logical lines are
 697    monotonic decreasing, and so the list is sorted and we can use a
 698    binary search.  */
 699
 700 static const struct line_map*
 701 linemap_macro_map_lookup (struct line_maps *set, source_location line)
 702 {
 703   unsigned int md, mn, mx;
 704   const struct line_map *cached, *result;
 705
 706   if (IS_ADHOC_LOC (line))
 707     line = set->location_adhoc_data_map.data[line & MAX_SOURCE_LOCATION].locus;
 708
 709   linemap_assert (line >= LINEMAPS_MACRO_LOWEST_LOCATION (set));
 710
 711   if (set ==  NULL)
 712     return NULL;
 713
 714   mn = LINEMAPS_MACRO_CACHE (set);
 715   mx = LINEMAPS_MACRO_USED (set);
 716   cached = LINEMAPS_MACRO_MAP_AT (set, mn);
 717
 718   if (line >= MAP_START_LOCATION (cached))
 719     {
 720       if (mn == 0 || line < MAP_START_LOCATION (&cached[-1]))
 721         return cached;
 722       mx = mn - 1;
 723       mn = 0;
 724     }
 725
 726   while (mn < mx)
 727     {
 728       md = (mx + mn) / 2;
 729       if (MAP_START_LOCATION (LINEMAPS_MACRO_MAP_AT (set, md)) > line)
 730         mn = md + 1;
 731       else
 732         mx = md;
 733     }
 734
 735   LINEMAPS_MACRO_CACHE (set) = mx;
 736   result = LINEMAPS_MACRO_MAP_AT (set, LINEMAPS_MACRO_CACHE (set));
 737   linemap_assert (MAP_START_LOCATION (result) <= line);
 738
 739   return result;
 740 }
 741
 742 /* Return TRUE if MAP encodes locations coming from a macro
 743    replacement-list at macro expansion point.  */
 744
 745 bool
 746 linemap_macro_expansion_map_p (const struct line_map *map)
 747 {
 748   if (!map)
 749     return false;
 750   return (map->reason == LC_ENTER_MACRO);
 751 }
 752
 753 /* If LOCATION is the locus of a token in a replacement-list of a
 754    macro expansion return the location of the macro expansion point.
 755
 756    Read the comments of struct line_map and struct line_map_macro in
 757    line-map.h to understand what a macro expansion point is.  */
 758
 759 static source_location
 760 linemap_macro_map_loc_to_exp_point (const struct line_map *map,
 761                                     source_location location ATTRIBUTE_UNUSED)
 762 {
 763   linemap_assert (linemap_macro_expansion_map_p (map)
 764                   && location >= MAP_START_LOCATION (map));
 765
 766   /* Make sure LOCATION is correct.  */
 767   linemap_assert ((location - MAP_START_LOCATION (map))
 768                   <  MACRO_MAP_NUM_MACRO_TOKENS (map));
 769
 770   return MACRO_MAP_EXPANSION_POINT_LOCATION (map);
 771 }
 772
 773 /* If LOCATION is the source location of a token that belongs to a
 774    macro replacement-list -- as part of a macro expansion -- then
 775    return the location of the token at the definition point of the
 776    macro.  Otherwise, return LOCATION.  SET is the set of maps
 777    location come from.  ORIGINAL_MAP is an output parm. If non NULL,
 778    the function sets *ORIGINAL_MAP to the ordinary (non-macro) map the
 779    returned location comes from.  */
 780
 781 source_location
 782 linemap_macro_map_loc_to_def_point (const struct line_map *map,
 783                                     source_location location)
 784 {
 785   unsigned token_no;
 786
 787   linemap_assert (linemap_macro_expansion_map_p (map)
 788                   && location >= MAP_START_LOCATION (map));
 789   linemap_assert (location >= RESERVED_LOCATION_COUNT);
 790
 791   token_no = location - MAP_START_LOCATION (map);
 792   linemap_assert (token_no < MACRO_MAP_NUM_MACRO_TOKENS (map));
 793
 794   location = MACRO_MAP_LOCATIONS (map)[2 * token_no + 1];
 795
 796   return location;
 797 }
 798
 799 /* If LOCATION is the locus of a token that is an argument of a
 800    function-like macro M and appears in the expansion of M, return the
 801    locus of that argument in the context of the caller of M.
 802
 803    In other words, this returns the xI location presented in the
 804    comments of line_map_macro above.  */
 805 source_location
 806 linemap_macro_map_loc_unwind_toward_spelling (const struct line_map* map,
 807                                               source_location location)
 808 {
 809   unsigned token_no;
 810
 811   linemap_assert (linemap_macro_expansion_map_p (map)
 812                   && location >= MAP_START_LOCATION (map));
 813   linemap_assert (location >= RESERVED_LOCATION_COUNT);
 814
 815   token_no = location - MAP_START_LOCATION (map);
 816   linemap_assert (token_no < MACRO_MAP_NUM_MACRO_TOKENS (map));
 817
 818   location = MACRO_MAP_LOCATIONS (map)[2 * token_no];
 819
 820   return location;
 821 }
 822
 823 /* Return the source line number corresponding to source location
 824    LOCATION.  SET is the line map set LOCATION comes from.  If
 825    LOCATION is the source location of token that is part of the
 826    replacement-list of a macro expansion return the line number of the
 827    macro expansion point.  */
 828
 829 int
 830 linemap_get_expansion_line (struct line_maps *set,
 831                             source_location location)
 832 {
 833   const struct line_map *map = NULL;
 834
 835   if (IS_ADHOC_LOC (location))
 836     location = set->location_adhoc_data_map.data[
 837         location & MAX_SOURCE_LOCATION].locus;
 838
 839   if (location < RESERVED_LOCATION_COUNT)
 840     return 0;
 841
 842   location =
 843     linemap_macro_loc_to_exp_point (set, location, &map);
 844
 845   return SOURCE_LINE (map, location);
 846 }
 847
 848 /* Return the path of the file corresponding to source code location
 849    LOCATION.
 850
 851    If LOCATION is the source location of token that is part of the
 852    replacement-list of a macro expansion return the file path of the
 853    macro expansion point.
 854
 855    SET is the line map set LOCATION comes from.  */
 856
 857 const char*
 858 linemap_get_expansion_filename (struct line_maps *set,
 859                                 source_location location)
 860 {
 861   const struct line_map *map = NULL;
 862
 863   if (IS_ADHOC_LOC (location))
 864     location = set->location_adhoc_data_map.data[
 865         location & MAX_SOURCE_LOCATION].locus;
 866
 867   if (location < RESERVED_LOCATION_COUNT)
 868     return NULL;
 869
 870   location =
 871     linemap_macro_loc_to_exp_point (set, location, &map);
 872
 873   return LINEMAP_FILE (map);
 874 }
 875
 876 /* Return the name of the macro associated to MACRO_MAP.  */
 877
 878 const char*
 879 linemap_map_get_macro_name (const struct line_map* macro_map)
 880 {
 881   linemap_assert (macro_map && linemap_macro_expansion_map_p (macro_map));
 882   return (const char*) NODE_NAME (MACRO_MAP_MACRO (macro_map));
 883 }
 884
 885 /* Return a positive value if LOCATION is the locus of a token that is
 886    located in a system header, O otherwise. It returns 1 if LOCATION
 887    is the locus of a token that is located in a system header, and 2
 888    if LOCATION is the locus of a token located in a C system header
 889    that therefore needs to be extern "C" protected in C++.
 890
 891    Note that this function returns 1 if LOCATION belongs to a token
 892    that is part of a macro replacement-list defined in a system
 893    header, but expanded in a non-system file.  */
 894
 895 int
 896 linemap_location_in_system_header_p (struct line_maps *set,
 897                                      source_location location)
 898 {
 899   const struct line_map *map = NULL;
 900
 901   if (IS_ADHOC_LOC (location))
 902     location = set->location_adhoc_data_map.data[
 903         location & MAX_SOURCE_LOCATION].locus;
 904
 905   if (location < RESERVED_LOCATION_COUNT)
 906     return false;
 907
 908   /* Let's look at where the token for LOCATION comes from.  */
 909   while (true)
 910     {
 911       map = linemap_lookup (set, location);
 912       if (map != NULL)
 913         {
 914           if (!linemap_macro_expansion_map_p (map))
 915             /* It's a normal token.  */
 916             return LINEMAP_SYSP (map);
 917           else
 918             {
 919               /* It's a token resulting from a macro expansion.  */
 920               source_location loc =
 921                 linemap_macro_map_loc_unwind_toward_spelling (map, location);
 922               if (loc < RESERVED_LOCATION_COUNT)
 923                 /* This token might come from a built-in macro.  Let's
 924                    look at where that macro got expanded.  */
 925                 location = linemap_macro_map_loc_to_exp_point (map, location);
 926               else
 927                 location = loc;
 928             }
 929         }
 930       else
 931         break;
 932     }
 933   return false;
 934 }
 935
 936 /* Return TRUE if LOCATION is a source code location of a token coming
 937    from a macro replacement-list at a macro expansion point, FALSE
 938    otherwise.  */
 939
 940 bool
 941 linemap_location_from_macro_expansion_p (struct line_maps *set,
 942                                          source_location location)
 943 {
 944   if (IS_ADHOC_LOC (location))
 945     location = set->location_adhoc_data_map.data[
 946         location & MAX_SOURCE_LOCATION].locus;
 947
 948   linemap_assert (location <= MAX_SOURCE_LOCATION
 949                   && (set->highest_location
 950                       < LINEMAPS_MACRO_LOWEST_LOCATION (set)));
 951   if (set == NULL)
 952     return false;
 953   return (location > set->highest_location);
 954 }
 955
 956 /* Given two virtual locations *LOC0 and *LOC1, return the first
 957    common macro map in their macro expansion histories.  Return NULL
 958    if no common macro was found.  *LOC0 (resp. *LOC1) is set to the
 959    virtual location of the token inside the resulting macro.  */
 960
 961 static const struct line_map*
 962 first_map_in_common_1 (struct line_maps *set,
 963                        source_location *loc0,
 964                        source_location *loc1)
 965 {
 966   source_location l0 = *loc0, l1 = *loc1;
 967   const struct line_map *map0 = linemap_lookup (set, l0),
 968     *map1 = linemap_lookup (set, l1);
 969
 970   while (linemap_macro_expansion_map_p (map0)
 971          && linemap_macro_expansion_map_p (map1)
 972          && (map0 != map1))
 973     {
 974       if (MAP_START_LOCATION (map0) < MAP_START_LOCATION (map1))
 975         {
 976           l0 = linemap_macro_map_loc_to_exp_point (map0, l0);
 977           map0 = linemap_lookup (set, l0);
 978         }
 979       else
 980         {
 981           l1 = linemap_macro_map_loc_to_exp_point (map1, l1);
 982           map1 = linemap_lookup (set, l1);
 983         }
 984     }
 985
 986   if (map0 == map1)
 987     {
 988       *loc0 = l0;
 989       *loc1 = l1;
 990       return map0;
 991     }
 992   return NULL;
 993 }
 994
 995 /* Given two virtual locations LOC0 and LOC1, return the first common
 996    macro map in their macro expansion histories.  Return NULL if no
 997    common macro was found.  *RES_LOC0 (resp. *RES_LOC1) is set to the
 998    virtual location of the token inside the resulting macro, upon
 999    return of a non-NULL result.  */
1000
1001 static const struct line_map*
1002 first_map_in_common (struct line_maps *set,
1003                      source_location loc0,
1004                      source_location loc1,
1005                      source_location  *res_loc0,
1006                      source_location  *res_loc1)
1007 {
1008   *res_loc0 = loc0;
1009   *res_loc1 = loc1;
1010
1011   return first_map_in_common_1 (set, res_loc0, res_loc1);
1012 }
1013
1014 /* Return a positive value if PRE denotes the location of a token that
1015    comes before the token of POST, 0 if PRE denotes the location of
1016    the same token as the token for POST, and a negative value
1017    otherwise.  */
1018
1019 int
1020 linemap_compare_locations (struct line_maps *set,
1021                            source_location  pre,
1022                            source_location post)
1023 {
1024   bool pre_virtual_p, post_virtual_p;
1025   source_location l0 = pre, l1 = post;
1026
1027   if (l0 == l1)
1028     return 0;
1029
1030   if ((pre_virtual_p = linemap_location_from_macro_expansion_p (set, l0)))
1031     l0 = linemap_resolve_location (set, l0,
1032                                    LRK_MACRO_EXPANSION_POINT,
1033                                    NULL);
1034
1035   if ((post_virtual_p = linemap_location_from_macro_expansion_p (set, l1)))
1036     l1 = linemap_resolve_location (set, l1,
1037                                    LRK_MACRO_EXPANSION_POINT,
1038                                    NULL);
1039
1040   if (l0 == l1
1041       && pre_virtual_p
1042       && post_virtual_p)
1043     {
1044       /* So pre and post represent two tokens that are present in a
1045          same macro expansion.  Let's see if the token for pre was
1046          before the token for post in that expansion.  */
1047       unsigned i0, i1;
1048       const struct line_map *map =
1049         first_map_in_common (set, pre, post, &l0, &l1);
1050
1051       if (map == NULL)
1052         /* This should not be possible.  */
1053         abort ();
1054
1055       i0 = l0 - MAP_START_LOCATION (map);
1056       i1 = l1 - MAP_START_LOCATION (map);
1057       return i1 - i0;
1058     }
1059
1060   return l1 - l0;
1061 }
1062
1063 /* Print an include trace, for e.g. the -H option of the preprocessor.  */
1064
1065 static void
1066 trace_include (const struct line_maps *set, const struct line_map *map)
1067 {
1068   unsigned int i = set->depth;
1069
1070   while (--i)
1071     putc ('.', stderr);
1072
1073   fprintf (stderr, " %s\n", ORDINARY_MAP_FILE_NAME (map));
1074 }
1075
1076 /* Return the spelling location of the token wherever it comes from,
1077    whether part of a macro definition or not.
1078
1079    This is a subroutine for linemap_resolve_location.  */
1080
1081 static source_location
1082 linemap_macro_loc_to_spelling_point (struct line_maps *set,
1083                                      source_location location,
1084                                      const struct line_map **original_map)
1085 {
1086   struct line_map *map;
1087
1088   if (IS_ADHOC_LOC (location))
1089     location = set->location_adhoc_data_map.data[
1090         location & MAX_SOURCE_LOCATION].locus;
1091
1092   linemap_assert (set && location >= RESERVED_LOCATION_COUNT);
1093
1094   while (true)
1095     {
1096       map = (struct line_map*) linemap_lookup (set, location);
1097       if (!linemap_macro_expansion_map_p (map))
1098         break;
1099
1100       location =
1101         linemap_macro_map_loc_unwind_toward_spelling (map, location);
1102     }
1103
1104   if (original_map)
1105     *original_map = map;
1106   return location;
1107 }
1108
1109 /* If LOCATION is the source location of a token that belongs to a
1110    macro replacement-list -- as part of a macro expansion -- then
1111    return the location of the token at the definition point of the
1112    macro.  Otherwise, return LOCATION.  SET is the set of maps
1113    location come from.  ORIGINAL_MAP is an output parm. If non NULL,
1114    the function sets *ORIGINAL_MAP to the ordinary (non-macro) map the
1115    returned location comes from.
1116
1117    This is a subroutine of linemap_resolve_location.  */
1118
1119 static source_location
1120 linemap_macro_loc_to_def_point (struct line_maps *set,
1121                                 source_location location,
1122                                 const struct line_map **original_map)
1123 {
1124   struct line_map *map;
1125
1126   if (IS_ADHOC_LOC (location))
1127     location = set->location_adhoc_data_map.data[
1128         location & MAX_SOURCE_LOCATION].locus;
1129
1130   linemap_assert (set && location >= RESERVED_LOCATION_COUNT);
1131
1132   while (true)
1133     {
1134       map = (struct line_map*) linemap_lookup (set, location);
1135       if (!linemap_macro_expansion_map_p (map))
1136         break;
1137
1138       location =
1139         linemap_macro_map_loc_to_def_point (map, location);
1140     }
1141
1142   if (original_map)
1143     *original_map = map;
1144   return location;
1145 }
1146
1147 /* If LOCATION is the source location of a token that belongs to a
1148    macro replacement-list -- at a macro expansion point -- then return
1149    the location of the topmost expansion point of the macro.  We say
1150    topmost because if we are in the context of a nested macro
1151    expansion, the function returns the source location of the first
1152    macro expansion that triggered the nested expansions.
1153
1154    Otherwise, return LOCATION.  SET is the set of maps location come
1155    from.  ORIGINAL_MAP is an output parm. If non NULL, the function
1156    sets *ORIGINAL_MAP to the ordinary (non-macro) map the returned
1157    location comes from.
1158
1159    This is a subroutine of linemap_resolve_location.  */
1160
1161 static source_location
1162 linemap_macro_loc_to_exp_point (struct line_maps *set,
1163                                 source_location location,
1164                                 const struct line_map **original_map)
1165 {
1166   struct line_map *map;
1167
1168   if (IS_ADHOC_LOC (location))
1169     location = set->location_adhoc_data_map.data[
1170         location & MAX_SOURCE_LOCATION].locus;
1171
1172   linemap_assert (set && location >= RESERVED_LOCATION_COUNT);
1173
1174   while (true)
1175     {
1176       map = (struct line_map*) linemap_lookup (set, location);
1177       if (!linemap_macro_expansion_map_p (map))
1178         break;
1179       location = linemap_macro_map_loc_to_exp_point (map, location);
1180     }
1181
1182   if (original_map)
1183     *original_map = map;
1184   return location;
1185 }
1186
1187 /* Resolve a virtual location into either a spelling location, an
1188    expansion point location or a token argument replacement point
1189    location.  Return the map that encodes the virtual location as well
1190    as the resolved location.
1191
1192    If LOC is *NOT* the location of a token resulting from the
1193    expansion of a macro, then the parameter LRK (which stands for
1194    Location Resolution Kind) is ignored and the resulting location
1195    just equals the one given in argument.
1196
1197    Now if LOC *IS* the location of a token resulting from the
1198    expansion of a macro, this is what happens.
1199
1200    * If LRK is set to LRK_MACRO_EXPANSION_POINT
1201    -------------------------------
1202
1203    The virtual location is resolved to the first macro expansion point
1204    that led to this macro expansion.
1205
1206    * If LRK is set to LRK_SPELLING_LOCATION
1207    -------------------------------------
1208
1209    The virtual location is resolved to the locus where the token has
1210    been spelled in the source.   This can follow through all the macro
1211    expansions that led to the token.
1212
1213    * If LRK is set to LRK_MACRO_DEFINITION_LOCATION
1214    --------------------------------------
1215
1216    The virtual location is resolved to the locus of the token in the
1217    context of the macro definition.
1218
1219    If LOC is the locus of a token that is an argument of a
1220    function-like macro [replacing a parameter in the replacement list
1221    of the macro] the virtual location is resolved to the locus of the
1222    parameter that is replaced, in the context of the definition of the
1223    macro.
1224
1225    If LOC is the locus of a token that is not an argument of a
1226    function-like macro, then the function behaves as if LRK was set to
1227    LRK_SPELLING_LOCATION.
1228
1229    If LOC_MAP is not NULL, *LOC_MAP is set to the map encoding the
1230    returned location.  Note that if the returned location wasn't originally
1231    encoded by a map, the *MAP is set to NULL.  This can happen if LOC
1232    resolves to a location reserved for the client code, like
1233    UNKNOWN_LOCATION or BUILTINS_LOCATION in GCC.  */
1234
1235 source_location
1236 linemap_resolve_location (struct line_maps *set,
1237                           source_location loc,
1238                           enum location_resolution_kind lrk,
1239                           const struct line_map **map)
1240 {
1241   if (IS_ADHOC_LOC (loc))
1242     loc = set->location_adhoc_data_map.data[loc & MAX_SOURCE_LOCATION].locus;
1243
1244   if (loc < RESERVED_LOCATION_COUNT)
1245     {
1246       /* A reserved location wasn't encoded in a map.  Let's return a
1247          NULL map here, just like what linemap_ordinary_map_lookup
1248          does.  */
1249       if (map)
1250         *map = NULL;
1251       return loc;
1252     }
1253
1254   switch (lrk)
1255     {
1256     case LRK_MACRO_EXPANSION_POINT:
1257       loc = linemap_macro_loc_to_exp_point (set, loc, map);
1258       break;
1259     case LRK_SPELLING_LOCATION:
1260       loc = linemap_macro_loc_to_spelling_point (set, loc, map);
1261       break;
1262     case LRK_MACRO_DEFINITION_LOCATION:
1263       loc = linemap_macro_loc_to_def_point (set, loc, map);
1264       break;
1265     default:
1266       abort ();
1267     }
1268   return loc;
1269 }
1270
1271 /*
1272    Suppose that LOC is the virtual location of a token T coming from
1273    the expansion of a macro M.  This function then steps up to get the
1274    location L of the point where M got expanded.  If L is a spelling
1275    location inside a macro expansion M', then this function returns
1276    the locus of the point where M' was expanded.  Said otherwise, this
1277    function returns the location of T in the context that triggered
1278    the expansion of M.
1279
1280    *LOC_MAP must be set to the map of LOC.  This function then sets it
1281    to the map of the returned location.  */
1282
1283 source_location
1284 linemap_unwind_toward_expansion (struct line_maps *set,
1285                                  source_location loc,
1286                                  const struct line_map **map)
1287 {
1288   source_location resolved_location;
1289   const struct line_map *resolved_map;
1290
1291   if (IS_ADHOC_LOC (loc))
1292     loc = set->location_adhoc_data_map.data[loc & MAX_SOURCE_LOCATION].locus;
1293
1294   resolved_location =
1295     linemap_macro_map_loc_unwind_toward_spelling (*map, loc);
1296   resolved_map = linemap_lookup (set, resolved_location);
1297
1298   if (!linemap_macro_expansion_map_p (resolved_map))
1299     {
1300       resolved_location = linemap_macro_map_loc_to_exp_point (*map, loc);
1301       resolved_map = linemap_lookup (set, resolved_location);
1302     }
1303
1304   *map = resolved_map;
1305   return resolved_location;
1306 }
1307
1308 /* If LOC is the virtual location of a token coming from the expansion
1309    of a macro M and if its spelling location is reserved (e.g, a
1310    location for a built-in token), then this function unwinds (using
1311    linemap_unwind_toward_expansion) the location until a location that
1312    is not reserved and is not in a system header is reached.  In other
1313    words, this unwinds the reserved location until a location that is
1314    in real source code is reached.
1315
1316    Otherwise, if the spelling location for LOC is not reserved or if
1317    LOC doesn't come from the expansion of a macro, the function
1318    returns LOC as is and *MAP is not touched.
1319
1320    *MAP is set to the map of the returned location if the later is
1321    different from LOC.  */
1322 source_location
1323 linemap_unwind_to_first_non_reserved_loc (struct line_maps *set,
1324                                           source_location loc,
1325                                           const struct line_map **map)
1326 {
1327   source_location resolved_loc;
1328   const struct line_map *map0 = NULL, *map1 = NULL;
1329
1330   if (IS_ADHOC_LOC (loc))
1331     loc = set->location_adhoc_data_map.data[loc & MAX_SOURCE_LOCATION].locus;
1332
1333   map0 = linemap_lookup (set, loc);
1334   if (!linemap_macro_expansion_map_p (map0))
1335     return loc;
1336
1337   resolved_loc = linemap_resolve_location (set, loc,
1338                                            LRK_SPELLING_LOCATION,
1339                                            &map1);
1340
1341   if (resolved_loc >= RESERVED_LOCATION_COUNT
1342       && !LINEMAP_SYSP (map1))
1343     return loc;
1344
1345   while (linemap_macro_expansion_map_p (map0)
1346          && (resolved_loc < RESERVED_LOCATION_COUNT
1347              || LINEMAP_SYSP (map1)))
1348     {
1349       loc = linemap_unwind_toward_expansion (set, loc, &map0);
1350       resolved_loc = linemap_resolve_location (set, loc,
1351                                                LRK_SPELLING_LOCATION,
1352                                                &map1);
1353     }
1354
1355   if (map != NULL)
1356     *map = map0;
1357   return loc;
1358 }
1359
1360 /* Expand source code location LOC and return a user readable source
1361    code location.  LOC must be a spelling (non-virtual) location.  If
1362    it's a location < RESERVED_LOCATION_COUNT a zeroed expanded source
1363    location is returned.  */
1364
1365 expanded_location
1366 linemap_expand_location (struct line_maps *set,
1367                          const struct line_map *map,
1368                          source_location loc)
1369
1370 {
1371   expanded_location xloc;
1372
1373   memset (&xloc, 0, sizeof (xloc));
1374   if (IS_ADHOC_LOC (loc))
1375     {
1376       loc = set->location_adhoc_data_map.data[loc & MAX_SOURCE_LOCATION].locus;
1377       xloc.data = set->location_adhoc_data_map.data[
1378           loc & MAX_SOURCE_LOCATION].data;
1379     }
1380
1381   if (loc < RESERVED_LOCATION_COUNT)
1382     /* The location for this token wasn't generated from a line map.
1383        It was probably a location for a builtin token, chosen by some
1384        client code.  Let's not try to expand the location in that
1385        case.  */;
1386   else if (map == NULL)
1387     /* We shouldn't be getting a NULL map with a location that is not
1388        reserved by the client code.  */
1389     abort ();
1390   else
1391     {
1392       /* MAP must be an ordinary map and LOC must be non-virtual,
1393          encoded into this map, obviously; the accessors used on MAP
1394          below ensure it is ordinary.  Let's just assert the
1395          non-virtualness of LOC here.  */
1396       if (linemap_location_from_macro_expansion_p (set, loc))
1397         abort ();
1398
1399       xloc.file = LINEMAP_FILE (map);
1400       xloc.line = SOURCE_LINE (map, loc);
1401       xloc.column = SOURCE_COLUMN (map, loc);
1402       xloc.sysp = LINEMAP_SYSP (map) != 0;
1403     }
1404
1405   return xloc;
1406 }
1407
1408
1409 /* Dump line map at index IX in line table SET to STREAM.  If STREAM
1410    is NULL, use stderr.  IS_MACRO is true if the caller wants to
1411    dump a macro map, false otherwise.  */
1412
1413 void
1414 linemap_dump (FILE *stream, struct line_maps *set, unsigned ix, bool is_macro)
1415 {
1416   const char *lc_reasons_v[LC_ENTER_MACRO + 1]
1417       = { "LC_ENTER", "LC_LEAVE", "LC_RENAME", "LC_RENAME_VERBATIM",
1418           "LC_ENTER_MACRO" };
1419   const char *reason;
1420   struct line_map *map;
1421
1422   if (stream == NULL)
1423     stream = stderr;
1424
1425   if (!is_macro)
1426     map = LINEMAPS_ORDINARY_MAP_AT (set, ix);
1427   else
1428     map = LINEMAPS_MACRO_MAP_AT (set, ix);
1429
1430   reason = (map->reason <= LC_ENTER_MACRO) ? lc_reasons_v[map->reason] : "???";
1431
1432   fprintf (stream, "Map #%u [%p] - LOC: %u - REASON: %s - SYSP: %s\n",
1433            ix, (void *) map, map->start_location, reason,
1434            (!is_macro && ORDINARY_MAP_IN_SYSTEM_HEADER_P (map)) ? "yes" : "no");
1435   if (!is_macro)
1436     {
1437       unsigned includer_ix;
1438       struct line_map *includer_map;
1439
1440       includer_ix = ORDINARY_MAP_INCLUDER_FILE_INDEX (map);
1441       includer_map = includer_ix < LINEMAPS_ORDINARY_USED (set)
1442                      ? LINEMAPS_ORDINARY_MAP_AT (set, includer_ix)
1443                      : NULL;
1444
1445       fprintf (stream, "File: %s:%d\n", ORDINARY_MAP_FILE_NAME (map),
1446                ORDINARY_MAP_STARTING_LINE_NUMBER (map));
1447       fprintf (stream, "Included from: [%d] %s\n", includer_ix,
1448                includer_map ? ORDINARY_MAP_FILE_NAME (includer_map) : "None");
1449     }
1450   else
1451     fprintf (stream, "Macro: %s (%u tokens)\n",
1452              linemap_map_get_macro_name (map),
1453              MACRO_MAP_NUM_MACRO_TOKENS (map));
1454
1455   fprintf (stream, "\n");
1456 }
1457
1458
1459 /* Dump debugging information about source location LOC into the file
1460    stream STREAM. SET is the line map set LOC comes from.  */
1461
1462 void
1463 linemap_dump_location (struct line_maps *set,
1464                        source_location loc,
1465                        FILE *stream)
1466 {
1467   const struct line_map *map;
1468   source_location location;
1469   const char *path = "", *from = "";
1470   int l = -1, c = -1, s = -1, e = -1;
1471
1472   if (IS_ADHOC_LOC (loc))
1473     loc = set->location_adhoc_data_map.data[loc & MAX_SOURCE_LOCATION].locus;
1474
1475   if (loc == 0)
1476     return;
1477
1478   location =
1479     linemap_resolve_location (set, loc, LRK_MACRO_DEFINITION_LOCATION, &map);
1480
1481   if (map == NULL)
1482     /* Only reserved locations can be tolerated in this case.  */
1483     linemap_assert (location < RESERVED_LOCATION_COUNT);
1484   else
1485     {
1486       path = LINEMAP_FILE (map);
1487       l = SOURCE_LINE (map, location);
1488       c = SOURCE_COLUMN (map, location);
1489       s = LINEMAP_SYSP (map) != 0;
1490       e = location != loc;
1491       if (e)
1492         from = "N/A";
1493       else
1494         from = (INCLUDED_FROM (set, map))
1495           ? LINEMAP_FILE (INCLUDED_FROM (set, map))
1496           : "<NULL>";
1497     }
1498
1499   /* P: path, L: line, C: column, S: in-system-header, M: map address,
1500      E: macro expansion?, LOC: original location, R: resolved location   */
1501   fprintf (stream, "{P:%s;F:%s;L:%d;C:%d;S:%d;M:%p;E:%d,LOC:%d,R:%d}",
1502            path, from, l, c, s, (void*)map, e, loc, location);
1503 }
1504
1505 /* Compute and return statistics about the memory consumption of some
1506    parts of the line table SET.  */
1507
1508 void
1509 linemap_get_statistics (struct line_maps *set,
1510                         struct linemap_stats *s)
1511 {
1512   long ordinary_maps_allocated_size, ordinary_maps_used_size,
1513     macro_maps_allocated_size, macro_maps_used_size,
1514     macro_maps_locations_size = 0, duplicated_macro_maps_locations_size = 0;
1515
1516   struct line_map *cur_map;
1517
1518   ordinary_maps_allocated_size =
1519     LINEMAPS_ORDINARY_ALLOCATED (set) * sizeof (struct line_map);
1520
1521   ordinary_maps_used_size =
1522     LINEMAPS_ORDINARY_USED (set) * sizeof (struct line_map);
1523
1524   macro_maps_allocated_size =
1525     LINEMAPS_MACRO_ALLOCATED (set) * sizeof (struct line_map);
1526
1527   for (cur_map = LINEMAPS_MACRO_MAPS (set);
1528        cur_map && cur_map <= LINEMAPS_LAST_MACRO_MAP (set);
1529        ++cur_map)
1530     {
1531       unsigned i;
1532
1533       linemap_assert (linemap_macro_expansion_map_p (cur_map));
1534
1535       macro_maps_locations_size +=
1536         2 * MACRO_MAP_NUM_MACRO_TOKENS (cur_map) * sizeof (source_location);
1537
1538       for (i = 0; i < 2 * MACRO_MAP_NUM_MACRO_TOKENS (cur_map); i += 2)
1539         {
1540           if (MACRO_MAP_LOCATIONS (cur_map)[i] ==
1541               MACRO_MAP_LOCATIONS (cur_map)[i + 1])
1542             duplicated_macro_maps_locations_size +=
1543               sizeof (source_location);
1544         }
1545     }
1546
1547   macro_maps_used_size =
1548     LINEMAPS_MACRO_USED (set) * sizeof (struct line_map);
1549
1550   s->num_ordinary_maps_allocated = LINEMAPS_ORDINARY_ALLOCATED (set);
1551   s->num_ordinary_maps_used = LINEMAPS_ORDINARY_USED (set);
1552   s->ordinary_maps_allocated_size = ordinary_maps_allocated_size;
1553   s->ordinary_maps_used_size = ordinary_maps_used_size;
1554   s->num_expanded_macros = num_expanded_macros_counter;
1555   s->num_macro_tokens = num_macro_tokens_counter;
1556   s->num_macro_maps_used = LINEMAPS_MACRO_USED (set);
1557   s->macro_maps_allocated_size = macro_maps_allocated_size;
1558   s->macro_maps_locations_size = macro_maps_locations_size;
1559   s->macro_maps_used_size = macro_maps_used_size;
1560   s->duplicated_macro_maps_locations_size =
1561     duplicated_macro_maps_locations_size;
1562 }
1563
1564
1565 /* Dump line table SET to STREAM.  If STREAM is NULL, stderr is used.
1566    NUM_ORDINARY specifies how many ordinary maps to dump.  NUM_MACRO
1567    specifies how many macro maps to dump.  */
1568
1569 void
1570 line_table_dump (FILE *stream, struct line_maps *set, unsigned int num_ordinary,
1571                  unsigned int num_macro)
1572 {
1573   unsigned int i;
1574
1575   if (set == NULL)
1576     return;
1577
1578   if (stream == NULL)
1579     stream = stderr;
1580
1581   fprintf (stream, "# of ordinary maps:  %d\n", LINEMAPS_ORDINARY_USED (set));
1582   fprintf (stream, "# of macro maps:     %d\n", LINEMAPS_MACRO_USED (set));
1583   fprintf (stream, "Include stack depth: %d\n", set->depth);
1584   fprintf (stream, "Highest location:    %u\n", set->highest_location);
1585
1586   if (num_ordinary)
1587     {
1588       fprintf (stream, "\nOrdinary line maps\n");
1589       for (i = 0; i < num_ordinary && i < LINEMAPS_ORDINARY_USED (set); i++)
1590         linemap_dump (stream, set, i, false);
1591       fprintf (stream, "\n");
1592     }
1593
1594   if (num_macro)
1595     {
1596       fprintf (stream, "\nMacro line maps\n");
1597       for (i = 0; i < num_macro && i < LINEMAPS_MACRO_USED (set); i++)
1598         linemap_dump (stream, set, i, true);
1599       fprintf (stream, "\n");
1600     }
1601 }