/* Map (unsigned int) keys to (source file, line, column) triples.   Copyright (C) 2001-2026 Free Software Foundation, Inc. This program is free software; you can redistribute it and/or modify itunder the terms of the GNU General Public License as published by theFree Software Foundation; either version 3, or (at your option) anylater version. This program is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See theGNU General Public License for more details. You should have received a copy of the GNU General Public Licensealong with this program; see the file COPYING3.  If not see<http://www.gnu.org/licenses/>.  In other words, you are welcome to use, share and improve this program. You are forbidden to forbid anyone else to use, share and improve what you give them.   Help stamp out software-hoarding!  */ #ifndef LIBCPP_LINE_MAP_H#define LIBCPP_LINE_MAP_H #include <utility> #ifndef GTY#define GTY(x) /* nothing */#endif /* Both gcc and emacs number source *lines* starting at 1, but   they have differing conventions for *columns*.    GCC uses a 1-based convention for source columns,   whereas Emacs's M-x column-number-mode uses a 0-based convention.    For example, an error in the initial, left-hand   column of source line 3 is reported by GCC as:       some-file.c:3:1: error: ...etc...    On navigating to the location of that error in Emacs   (e.g. via "next-error"),   the locus is reported in the Mode Line   (assuming M-x column-number-mode) as:      some-file.c   10%   (3, 0)    i.e. "3:1:" in GCC corresponds to "(3, 0)" in Emacs.  */ /* The type of line numbers.  */typedef unsigned int linenum_type; /* A type for doing arithmetic on line numbers.  */typedef long long linenum_arith_t; /* A function for for use by qsort for comparing line numbers.  */ inline int compare (linenum_type lhs, linenum_type rhs){  /* Avoid truncation issues by using linenum_arith_t for the comparison,     and only consider the sign of the result.  */  linenum_arith_t diff = (linenum_arith_t)lhs - (linenum_arith_t)rhs;  if (diff)    return diff > 0 ? 1 : -1;  return 0;} /* Reason for creating a new line map with linemap_add.  */enum lc_reason{  LC_ENTER = 0,		/* Begin #include.  */  LC_LEAVE,		/* Return to including file.  */  LC_RENAME,		/* Other reason for name change.  */  LC_RENAME_VERBATIM,	/* Likewise, but "" != stdin.  */  LC_ENTER_MACRO,	/* Begin macro expansion.  */  LC_MODULE,		/* A (C++) Module.  */  /* FIXME: add support for stringize and paste.  */  LC_HWM /* High Water Mark.  */}; /* The typedef "location_t" is a key within the location database,   identifying a source location or macro expansion, along with range   information, and (optionally) a pointer for use by gcc.    This key only has meaning in relation to a line_maps instance.  Within   gcc there is a single line_maps instance: "line_table", declared in   gcc/input.h and defined in gcc/input.cc.    The values of the keys are intended to be internal to libcpp, but for   ease-of-understanding the implementation, they are currently assigned as   follows in the case of 32-bit location_t:   Actual     | Value                         | Meaning  -----------+-------------------------------+-------------------------------  0x00000000 | UNKNOWN_LOCATION (gcc/input.h)| Unknown/invalid location.  -----------+-------------------------------+-------------------------------  0x00000001 | BUILTINS_LOCATION             | The location for declarations             |   (gcc/input.h)               | in "<built-in>"  -----------+-------------------------------+-------------------------------  0x00000002 | RESERVED_LOCATION_COUNT       | The first location to be             | (also                         | handed out, and the             |  ordmap[0]->start_location)   | first line in ordmap 0  -----------+-------------------------------+-------------------------------             | ordmap[1]->start_location     | First line in ordmap 1             | ordmap[1]->start_location+32  | First column in that line             |   (assuming range_bits == 5)  |             | ordmap[1]->start_location+64  | 2nd column in that line             | ordmap[1]->start_location+4096| Second line in ordmap 1             |   (assuming column_bits == 12)             |             |   Subsequent lines are offset by (1 << column_bits),             |   e.g. 4096 for 12 bits, with a column value of 0 representing             |   "the whole line".             |             |   Within a line, the low "range_bits" (typically 5) are used for             |   storing short ranges, so that there's an offset of             |     (1 << range_bits) between individual columns within a line,             |   typically 32.             |   The low range_bits store the offset of the end point from the             |   start point, and the start point is found by masking away             |   the range bits.             |             |   For example:             |      ordmap[1]->start_location+64    "2nd column in that line"             |   above means a caret at that location, with a range             |   starting and finishing at the same place (the range bits             |   are 0), a range of length 1.             |             |   By contrast:             |      ordmap[1]->start_location+68             |   has range bits 0x4, meaning a caret with a range starting at             |   that location, but with endpoint 4 columns further on: a range             |   of length 5.             |             |   Ranges that have caret != start, or have an endpoint too             |   far away to fit in range_bits are instead stored as ad-hoc             |   locations.  Hence for range_bits == 5 we can compactly store             |   tokens of length <= 32 without needing to use the ad-hoc             |   table.             |             |   This packing scheme means we effectively have             |     (column_bits - range_bits)             |   of bits for the columns, typically (12 - 5) = 7, for 128             |   columns; longer line widths are accomodated by starting a             |   new ordmap with a higher column_bits.             |             | ordmap[2]->start_location-1   | Final location in ordmap 1  -----------+-------------------------------+-------------------------------             | ordmap[2]->start_location     | First line in ordmap 2             | ordmap[3]->start_location-1   | Final location in ordmap 2  -----------+-------------------------------+-------------------------------             |                               | (etc)  -----------+-------------------------------+-------------------------------             | ordmap[n-1]->start_location   | First line in final ord map             |                               | (etc)             | set->highest_location - 1     | Final location in that ordmap  -----------+-------------------------------+-------------------------------             | set->highest_location         | Location of the where the next             |                               | ordinary linemap would start  -----------+-------------------------------+-------------------------------             |                               |             |                  VVVVVVVVVVVVVVVVVVVVVVVVVVV             |                  Ordinary maps grow this way             |             |                    (unallocated integers)             |  0x60000000 | LINE_MAP_MAX_LOCATION_WITH_COLS             |   Beyond this point, ordinary linemaps have 0 bits per column:             |   each increment of the value corresponds to a new source line.             |  0x70000000 | LINE_MAP_MAX_LOCATION             |   Beyond the point, we give up on ordinary maps; attempts to             |   create locations in them lead to UNKNOWN_LOCATION (0).             |             |                    (unallocated integers)             |             |                   Macro maps grow this way             |                   ^^^^^^^^^^^^^^^^^^^^^^^^             |                               |  -----------+-------------------------------+-------------------------------             | LINEMAPS_MACRO_LOWEST_LOCATION| Locations within macro maps             | macromap[m-1]->start_location | Start of last macro map             |                               |  -----------+-------------------------------+-------------------------------             | macromap[m-2]->start_location | Start of penultimate macro map  -----------+-------------------------------+-------------------------------             | macromap[1]->start_location   | Start of macro map 1  -----------+-------------------------------+-------------------------------             | macromap[0]->start_location   | Start of macro map 0  0x7fffffff | MAX_LOCATION_T                | Also used as a mask for             |                               | accessing the ad-hoc data table  -----------+-------------------------------+-------------------------------  0x80000000 | Start of ad-hoc values; the lower 31 bits are used as an index  ...        | into the line_table->location_adhoc_data_map.data array.  0xffffffff | UINT_MAX                      |  -----------+-------------------------------+-------------------------------    Examples of location encoding.    Packed ranges   =============    Consider encoding the location of a token "foo", seen underlined here   on line 523, within an ordinary line_map that starts at line 500:                  11111111112        12345678901234567890     522     523   return foo + bar;                  ^~~     524    The location's caret and start are both at line 523, column 11; the   location's finish is on the same line, at column 13 (an offset of 2   columns, for length 3).    Line 523 is offset 23 from the starting line of the ordinary line_map.    caret == start, and the offset of the finish fits within 5 bits, so   this can be stored as a packed range.    This is encoded as:      ordmap->start         + (line_offset << ordmap->m_column_and_range_bits)         + (column << ordmap->m_range_bits)         + (range_offset);   i.e. (for line offset 23, column 11, range offset 2):      ordmap->start         + (23 << 12)         + (11 << 5)         + 2;   i.e.:      ordmap->start + 0x17162   assuming that the line_map uses the default of 7 bits for columns and   5 bits for packed range (giving 12 bits for m_column_and_range_bits).     "Pure" locations   ================    These are a special case of the above, where      caret == start == finish   They are stored as packed ranges with offset == 0.   For example, the location of the "f" of "foo" could be stored   as above, but with range offset 0, giving:      ordmap->start         + (23 << 12)         + (11 << 5)         + 0;   i.e.:      ordmap->start + 0x17160     Unoptimized ranges   ==================    Consider encoding the location of the binary expression   below:                  11111111112        12345678901234567890     522     523   return foo + bar;                  ~~~~^~~~~     524    The location's caret is at the "+", line 523 column 15, but starts   earlier, at the "f" of "foo" at column 11.  The finish is at the "r"   of "bar" at column 19.    This can't be stored as a packed range since start != caret.   Hence it is stored as an ad-hoc location e.g. 0x80000003.    Stripping off the top bit gives us an index into the ad-hoc   lookaside table:      line_table->location_adhoc_data_map.data[0x3]    from which the caret, start and finish can be looked up,   encoded as "pure" locations:      start  == ordmap->start + (23 << 12) + (11 << 5)            == ordmap->start + 0x17160  (as above; the "f" of "foo")      caret  == ordmap->start + (23 << 12) + (15 << 5)            == ordmap->start + 0x171e0      finish == ordmap->start + (23 << 12) + (19 << 5)            == ordmap->start + 0x17260    To further see how location_t works in practice, see the   worked example in libcpp/location-example.txt.  */ /* A 64-bit type to represent a location.  We only use 63 of the 64 bits, so   that two location_t can be safely subtracted and stored in an int64_t.  */typedef uint64_t location_t;typedef int64_t location_diff_t; /* Sometimes we need a type that has the same size as location_t but that does   not represent a location.  This typedef provides more clarity in those   cases.  */typedef location_t line_map_uint_t; /* Do not track column numbers higher than this one.  As a result, the   range of column_bits is [12, 18] (or 0 if column numbers are   disabled).  */const unsigned int LINE_MAP_MAX_COLUMN_NUMBER = (1U << 31) - 1; /* Do not pack ranges if locations get higher than this.   If you change this, update:     gcc.dg/plugin/location-overflow-test-*.c.  */const location_t LINE_MAP_MAX_LOCATION_WITH_PACKED_RANGES  = location_t (0x50000000) << 31; /* Do not track column numbers if locations get higher than this.   If you change this, update:     gcc.dg/plugin/location-overflow-test-*.c.  */const location_t LINE_MAP_MAX_LOCATION_WITH_COLS  = location_t (0x60000000) << 31; /* Highest possible source location encoded within an ordinary map.  Higher   values up to MAX_LOCATION_T represent macro virtual locations.  */const location_t LINE_MAP_MAX_LOCATION = location_t (0x70000000) << 31; /* This is the highest possible source location encoded within an   ordinary or macro map.  */const location_t MAX_LOCATION_T = location_t (-1) >> 2; /* This is the number of range bits suggested to enable, if range tracking is   desired.  */const int line_map_suggested_range_bits = 7; /* A range of source locations.    Ranges are closed:   m_start is the first location within the range,   m_finish is the last location within the range.    We may need a more compact way to store these, but for now,   let's do it the simple way, as a pair.  */struct GTY(()) source_range{  location_t m_start;  location_t m_finish;   /* We avoid using constructors, since various structs that     don't yet have constructors will embed instances of     source_range.  */   /* Make a source_range from a location_t.  */  static source_range from_location (location_t loc)  {    source_range result;    result.m_start = loc;    result.m_finish = loc;    return result;  }   /* Make a source_range from a pair of location_t.  */  static source_range from_locations (location_t start,				      location_t finish)  {    source_range result;    result.m_start = start;    result.m_finish = finish;    return result;  }}; /* Memory allocation function typedef.  Works like xrealloc.  */typedef void *(*line_map_realloc) (void *, size_t); /* Memory allocator function that returns the actual allocated size,   for a given requested allocation.  */typedef size_t (*line_map_round_alloc_size_func) (size_t); /* A line_map encodes a sequence of locations.   There are two kinds of maps. Ordinary maps and macro expansion   maps, a.k.a macro maps.    A macro map encodes source locations of tokens that are part of a   macro replacement-list, at a macro expansion point. E.g, in:             #define PLUS(A,B) A + B    No macro map is going to be created there, because we are not at a   macro expansion point. We are at a macro /definition/ point. So the   locations of the tokens of the macro replacement-list (i.e, A + B)   will be locations in an ordinary map, not a macro map.    On the other hand, if we later do:         int a = PLUS (1,2);    The invocation of PLUS here is a macro expansion. So we are at a   macro expansion point. The preprocessor expands PLUS (1,2) and   replaces it with the tokens of its replacement-list: 1 + 2. A macro   map is going to be created to hold (or rather to map, haha ...) the   locations of the tokens 1, + and 2. The macro map also records the   location of the expansion point of PLUS. That location is mapped in   the map that is active right before the location of the invocation   of PLUS.  */ /* This contains GTY mark-up to support precompiled headers.   line_map is an abstract class, only derived objects exist.  */struct GTY((tag ("0"), desc ("MAP_ORDINARY_P (&%h) ? 1 : 2"))) line_map {  location_t start_location;   /* Size is 8 bytes; alignment 4 or 8 depending on the arch.  */}; /* An ordinary line map encodes physical source locations. Those   physical source locations are called "spelling locations".    Physical source file TO_FILE at line TO_LINE at column 0 is represented   by the logical START_LOCATION.  TO_LINE+L at column C is represented by   START_LOCATION+(L*(1<<m_column_and_range_bits))+(C*1<<m_range_bits), as   long as C<(1<<effective range bits), and the result_location is less than   the next line_map's start_location.   (The top line is line 1 and the leftmost column is column 1; line/column 0   means "entire file/line" or "unknown line/column" or "not applicable".)    The highest possible source location is MAX_LOCATION_T.  */struct GTY((tag ("1"))) line_map_ordinary : public line_map {  /* Base class is 8 bytes.  */   /* 4 bytes of integers, each 1 byte for easy extraction/insertion.  */   /* The reason for creation of this line map.  */  ENUM_BITFIELD (lc_reason) reason : 8;   /* SYSP is one for a system header, two for a C system header file     that therefore needs to be extern "C" protected in C++, and zero     otherwise.  This field isn't really needed now that it's in     cpp_buffer.  */  unsigned char sysp;   /* Number of the low-order location_t bits used for column numbers     and ranges.  */  unsigned int m_column_and_range_bits : 8;   /* Number of the low-order "column" bits used for storing short ranges     inline, rather than in the ad-hoc table.     MSB                                                                 LSB     31                                                                    0     +-------------------------+-------------------------------------------+     |                         |<---map->column_and_range_bits (e.g. 12)-->|     +-------------------------+-----------------------+-------------------+     |                         | column_and_range_bits | map->range_bits   |     |                         |   - range_bits        |                   |     +-------------------------+-----------------------+-------------------+     | row bits                | effective column bits | short range bits  |     |                         |    (e.g. 7)           |   (e.g. 5)        |     +-------------------------+-----------------------+-------------------+ */  unsigned int m_range_bits : 8;   /* 32-bit int even in 64-bit mode.  */  linenum_type to_line;   /* Location from whence this line map was included.  For regular     #includes, this location will be the last location of a map.  For     outermost file, this is 0.  For modules it could be anywhere     within a map.  */  location_t included_from;   /* Pointer alignment boundary, whether 32-bit or 64-bit mode.  */  const char *to_file;   /* Size is 28 (32) bytes for 32-bit (64-bit) arch.  */}; struct cpp_hashnode; /* A macro line map encodes location of tokens coming from a macro   expansion.    The offset from START_LOCATION is used to index into   MACRO_LOCATIONS; this holds the original location of the token.  */struct GTY((tag ("2"))) line_map_macro : public line_map {   /* Get the location of the expansion point of this macro map.  */   location_t  get_expansion_point_location () const  {    return m_expansion;  }   /* Base is 8 bytes.  */   /* The number of tokens inside the replacement-list of MACRO.  */  unsigned int n_tokens;   /* Pointer alignment boundary.  */   /* The cpp macro whose expansion gave birth to this macro map.  */  struct cpp_hashnode *    GTY ((nested_ptr (union tree_node,		      "%h ? CPP_HASHNODE (GCC_IDENT_TO_HT_IDENT (%h)) : NULL",

Lines 1–500 of 1486. Load more