1 /* Map (unsigned int) keys to (source file, line, column) triples. 2 Copyright (C) 2001-2018 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 #ifndef LIBCPP_LINE_MAP_H 23 #define LIBCPP_LINE_MAP_H 24 25 #ifndef GTY 26 #define GTY(x) /* nothing */ 27 #endif 28 29 /* Both gcc and emacs number source *lines* starting at 1, but 30 they have differing conventions for *columns*. 31 32 GCC uses a 1-based convention for source columns, 33 whereas Emacs's M-x column-number-mode uses a 0-based convention. 34 35 For example, an error in the initial, left-hand 36 column of source line 3 is reported by GCC as: 37 38 some-file.c:3:1: error: ...etc... 39 40 On navigating to the location of that error in Emacs 41 (e.g. via "next-error"), 42 the locus is reported in the Mode Line 43 (assuming M-x column-number-mode) as: 44 45 some-file.c 10% (3, 0) 46 47 i.e. "3:1:" in GCC corresponds to "(3, 0)" in Emacs. */ 48 49 /* The type of line numbers. */ 50 typedef unsigned int linenum_type; 51 52 /* A function for for use by qsort for comparing line numbers. */ 53 54 inline int compare (linenum_type lhs, linenum_type rhs) 55 { 56 /* Avoid truncation issues by using long long for the comparison, 57 and only consider the sign of the result. */ 58 long long diff = (long long)lhs - (long long)rhs; 59 if (diff) 60 return diff > 0 ? 1 : -1; 61 return 0; 62 } 63 64 /* Reason for creating a new line map with linemap_add. LC_ENTER is 65 when including a new file, e.g. a #include directive in C. 66 LC_LEAVE is when reaching a file's end. LC_RENAME is when a file 67 name or line number changes for neither of the above reasons 68 (e.g. a #line directive in C); LC_RENAME_VERBATIM is like LC_RENAME 69 but a filename of "" is not specially interpreted as standard 70 input. LC_ENTER_MACRO is when a macro expansion is about to start. */ 71 enum lc_reason 72 { 73 LC_ENTER = 0, 74 LC_LEAVE, 75 LC_RENAME, 76 LC_RENAME_VERBATIM, 77 LC_ENTER_MACRO 78 /* FIXME: add support for stringize and paste. */ 79 }; 80 81 /* The typedef "source_location" is a key within the location database, 82 identifying a source location or macro expansion, along with range 83 information, and (optionally) a pointer for use by gcc. 84 85 This key only has meaning in relation to a line_maps instance. Within 86 gcc there is a single line_maps instance: "line_table", declared in 87 gcc/input.h and defined in gcc/input.c. 88 89 The values of the keys are intended to be internal to libcpp, 90 but for ease-of-understanding the implementation, they are currently 91 assigned as follows: 92 93 Actual | Value | Meaning 94 -----------+-------------------------------+------------------------------- 95 0x00000000 | UNKNOWN_LOCATION (gcc/input.h)| Unknown/invalid location. 96 -----------+-------------------------------+------------------------------- 97 0x00000001 | BUILTINS_LOCATION | The location for declarations 98 | (gcc/input.h) | in "<built-in>" 99 -----------+-------------------------------+------------------------------- 100 0x00000002 | RESERVED_LOCATION_COUNT | The first location to be 101 | (also | handed out, and the 102 | ordmap[0]->start_location) | first line in ordmap 0 103 -----------+-------------------------------+------------------------------- 104 | ordmap[1]->start_location | First line in ordmap 1 105 | ordmap[1]->start_location+32 | First column in that line 106 | (assuming range_bits == 5) | 107 | ordmap[1]->start_location+64 | 2nd column in that line 108 | ordmap[1]->start_location+4096| Second line in ordmap 1 109 | (assuming column_bits == 12) 110 | 111 | Subsequent lines are offset by (1 << column_bits), 112 | e.g. 4096 for 12 bits, with a column value of 0 representing 113 | "the whole line". 114 | 115 | Within a line, the low "range_bits" (typically 5) are used for 116 | storing short ranges, so that there's an offset of 117 | (1 << range_bits) between individual columns within a line, 118 | typically 32. 119 | The low range_bits store the offset of the end point from the 120 | start point, and the start point is found by masking away 121 | the range bits. 122 | 123 | For example: 124 | ordmap[1]->start_location+64 "2nd column in that line" 125 | above means a caret at that location, with a range 126 | starting and finishing at the same place (the range bits 127 | are 0), a range of length 1. 128 | 129 | By contrast: 130 | ordmap[1]->start_location+68 131 | has range bits 0x4, meaning a caret with a range starting at 132 | that location, but with endpoint 4 columns further on: a range 133 | of length 5. 134 | 135 | Ranges that have caret != start, or have an endpoint too 136 | far away to fit in range_bits are instead stored as ad-hoc 137 | locations. Hence for range_bits == 5 we can compactly store 138 | tokens of length <= 32 without needing to use the ad-hoc 139 | table. 140 | 141 | This packing scheme means we effectively have 142 | (column_bits - range_bits) 143 | of bits for the columns, typically (12 - 5) = 7, for 128 144 | columns; longer line widths are accomodated by starting a 145 | new ordmap with a higher column_bits. 146 | 147 | ordmap[2]->start_location-1 | Final location in ordmap 1 148 -----------+-------------------------------+------------------------------- 149 | ordmap[2]->start_location | First line in ordmap 2 150 | ordmap[3]->start_location-1 | Final location in ordmap 2 151 -----------+-------------------------------+------------------------------- 152 | | (etc) 153 -----------+-------------------------------+------------------------------- 154 | ordmap[n-1]->start_location | First line in final ord map 155 | | (etc) 156 | set->highest_location - 1 | Final location in that ordmap 157 -----------+-------------------------------+------------------------------- 158 | set->highest_location | Location of the where the next 159 | | ordinary linemap would start 160 -----------+-------------------------------+------------------------------- 161 | | 162 | VVVVVVVVVVVVVVVVVVVVVVVVVVV 163 | Ordinary maps grow this way 164 | 165 | (unallocated integers) 166 | 167 0x60000000 | LINE_MAP_MAX_LOCATION_WITH_COLS 168 | Beyond this point, ordinary linemaps have 0 bits per column: 169 | each increment of the value corresponds to a new source line. 170 | 171 0x70000000 | LINE_MAP_MAX_SOURCE_LOCATION 172 | Beyond the point, we give up on ordinary maps; attempts to 173 | create locations in them lead to UNKNOWN_LOCATION (0). 174 | 175 | (unallocated integers) 176 | 177 | Macro maps grow this way 178 | ^^^^^^^^^^^^^^^^^^^^^^^^ 179 | | 180 -----------+-------------------------------+------------------------------- 181 | LINEMAPS_MACRO_LOWEST_LOCATION| Locations within macro maps 182 | macromap[m-1]->start_location | Start of last macro map 183 | | 184 -----------+-------------------------------+------------------------------- 185 | macromap[m-2]->start_location | Start of penultimate macro map 186 -----------+-------------------------------+------------------------------- 187 | macromap[1]->start_location | Start of macro map 1 188 -----------+-------------------------------+------------------------------- 189 | macromap[0]->start_location | Start of macro map 0 190 0x7fffffff | MAX_SOURCE_LOCATION | Also used as a mask for 191 | | accessing the ad-hoc data table 192 -----------+-------------------------------+------------------------------- 193 0x80000000 | Start of ad-hoc values; the lower 31 bits are used as an index 194 ... | into the line_table->location_adhoc_data_map.data array. 195 0xffffffff | UINT_MAX | 196 -----------+-------------------------------+------------------------------- 197 198 Examples of location encoding. 199 200 Packed ranges 201 ============= 202 203 Consider encoding the location of a token "foo", seen underlined here 204 on line 523, within an ordinary line_map that starts at line 500: 205 206 11111111112 207 12345678901234567890 208 522 209 523 return foo + bar; 210 ^~~ 211 524 212 213 The location's caret and start are both at line 523, column 11; the 214 location's finish is on the same line, at column 13 (an offset of 2 215 columns, for length 3). 216 217 Line 523 is offset 23 from the starting line of the ordinary line_map. 218 219 caret == start, and the offset of the finish fits within 5 bits, so 220 this can be stored as a packed range. 221 222 This is encoded as: 223 ordmap->start 224 + (line_offset << ordmap->m_column_and_range_bits) 225 + (column << ordmap->m_range_bits) 226 + (range_offset); 227 i.e. (for line offset 23, column 11, range offset 2): 228 ordmap->start 229 + (23 << 12) 230 + (11 << 5) 231 + 2; 232 i.e.: 233 ordmap->start + 0x17162 234 assuming that the line_map uses the default of 7 bits for columns and 235 5 bits for packed range (giving 12 bits for m_column_and_range_bits). 236 237 238 "Pure" locations 239 ================ 240 241 These are a special case of the above, where 242 caret == start == finish 243 They are stored as packed ranges with offset == 0. 244 For example, the location of the "f" of "foo" could be stored 245 as above, but with range offset 0, giving: 246 ordmap->start 247 + (23 << 12) 248 + (11 << 5) 249 + 0; 250 i.e.: 251 ordmap->start + 0x17160 252 253 254 Unoptimized ranges 255 ================== 256 257 Consider encoding the location of the binary expression 258 below: 259 260 11111111112 261 12345678901234567890 262 522 263 523 return foo + bar; 264 ~~~~^~~~~ 265 524 266 267 The location's caret is at the "+", line 523 column 15, but starts 268 earlier, at the "f" of "foo" at column 11. The finish is at the "r" 269 of "bar" at column 19. 270 271 This can't be stored as a packed range since start != caret. 272 Hence it is stored as an ad-hoc location e.g. 0x80000003. 273 274 Stripping off the top bit gives us an index into the ad-hoc 275 lookaside table: 276 277 line_table->location_adhoc_data_map.data[0x3] 278 279 from which the caret, start and finish can be looked up, 280 encoded as "pure" locations: 281 282 start == ordmap->start + (23 << 12) + (11 << 5) 283 == ordmap->start + 0x17160 (as above; the "f" of "foo") 284 285 caret == ordmap->start + (23 << 12) + (15 << 5) 286 == ordmap->start + 0x171e0 287 288 finish == ordmap->start + (23 << 12) + (19 << 5) 289 == ordmap->start + 0x17260 290 291 To further see how source_location works in practice, see the 292 worked example in libcpp/location-example.txt. */ 293 typedef unsigned int source_location; 294 295 /* Do not track column numbers higher than this one. As a result, the 296 range of column_bits is [12, 18] (or 0 if column numbers are 297 disabled). */ 298 const unsigned int LINE_MAP_MAX_COLUMN_NUMBER = (1U << 12); 299 300 /* Do not pack ranges if locations get higher than this. 301 If you change this, update: 302 gcc.dg/plugin/location-overflow-test-*.c. */ 303 const source_location LINE_MAP_MAX_LOCATION_WITH_PACKED_RANGES = 0x50000000; 304 305 /* Do not track column numbers if locations get higher than this. 306 If you change this, update: 307 gcc.dg/plugin/location-overflow-test-*.c. */ 308 const source_location LINE_MAP_MAX_LOCATION_WITH_COLS = 0x60000000; 309 310 /* A range of source locations. 311 312 Ranges are closed: 313 m_start is the first location within the range, 314 m_finish is the last location within the range. 315 316 We may need a more compact way to store these, but for now, 317 let's do it the simple way, as a pair. */ 318 struct GTY(()) source_range 319 { 320 source_location m_start; 321 source_location m_finish; 322 323 /* We avoid using constructors, since various structs that 324 don't yet have constructors will embed instances of 325 source_range. */ 326 327 /* Make a source_range from a source_location. */ 328 static source_range from_location (source_location loc) 329 { 330 source_range result; 331 result.m_start = loc; 332 result.m_finish = loc; 333 return result; 334 } 335 336 /* Make a source_range from a pair of source_location. */ 337 static source_range from_locations (source_location start, 338 source_location finish) 339 { 340 source_range result; 341 result.m_start = start; 342 result.m_finish = finish; 343 return result; 344 } 345 }; 346 347 /* Memory allocation function typedef. Works like xrealloc. */ 348 typedef void *(*line_map_realloc) (void *, size_t); 349 350 /* Memory allocator function that returns the actual allocated size, 351 for a given requested allocation. */ 352 typedef size_t (*line_map_round_alloc_size_func) (size_t); 353 354 /* A line_map encodes a sequence of locations. 355 There are two kinds of maps. Ordinary maps and macro expansion 356 maps, a.k.a macro maps. 357 358 A macro map encodes source locations of tokens that are part of a 359 macro replacement-list, at a macro expansion point. E.g, in: 360 361 #define PLUS(A,B) A + B 362 363 No macro map is going to be created there, because we are not at a 364 macro expansion point. We are at a macro /definition/ point. So the 365 locations of the tokens of the macro replacement-list (i.e, A + B) 366 will be locations in an ordinary map, not a macro map. 367 368 On the other hand, if we later do: 369 370 int a = PLUS (1,2); 371 372 The invocation of PLUS here is a macro expansion. So we are at a 373 macro expansion point. The preprocessor expands PLUS (1,2) and 374 replaces it with the tokens of its replacement-list: 1 + 2. A macro 375 map is going to be created to hold (or rather to map, haha ...) the 376 locations of the tokens 1, + and 2. The macro map also records the 377 location of the expansion point of PLUS. That location is mapped in 378 the map that is active right before the location of the invocation 379 of PLUS. */ 380 struct GTY((tag ("0"), desc ("%h.reason == LC_ENTER_MACRO ? 2 : 1"))) line_map { 381 source_location start_location; 382 383 /* The reason for creation of this line map. */ 384 ENUM_BITFIELD (lc_reason) reason : CHAR_BIT; 385 }; 386 387 /* An ordinary line map encodes physical source locations. Those 388 physical source locations are called "spelling locations". 389 390 Physical source file TO_FILE at line TO_LINE at column 0 is represented 391 by the logical START_LOCATION. TO_LINE+L at column C is represented by 392 START_LOCATION+(L*(1<<m_column_and_range_bits))+(C*1<<m_range_bits), as 393 long as C<(1<<effective range bits), and the result_location is less than 394 the next line_map's start_location. 395 (The top line is line 1 and the leftmost column is column 1; line/column 0 396 means "entire file/line" or "unknown line/column" or "not applicable".) 397 398 The highest possible source location is MAX_SOURCE_LOCATION. */ 399 struct GTY((tag ("1"))) line_map_ordinary : public line_map { 400 const char *to_file; 401 linenum_type to_line; 402 403 /* An index into the set that gives the line mapping at whose end 404 the current one was included. File(s) at the bottom of the 405 include stack have this set to -1. */ 406 int included_from; 407 408 /* SYSP is one for a system header, two for a C system header file 409 that therefore needs to be extern "C" protected in C++, and zero 410 otherwise. This field isn't really needed now that it's in 411 cpp_buffer. */ 412 unsigned char sysp; 413 414 /* Number of the low-order source_location bits used for column numbers 415 and ranges. */ 416 unsigned int m_column_and_range_bits : 8; 417 418 /* Number of the low-order "column" bits used for storing short ranges 419 inline, rather than in the ad-hoc table. 420 MSB LSB 421 31 0 422 +-------------------------+-------------------------------------------+ 423 | |<---map->column_and_range_bits (e.g. 12)-->| 424 +-------------------------+-----------------------+-------------------+ 425 | | column_and_range_bits | map->range_bits | 426 | | - range_bits | | 427 +-------------------------+-----------------------+-------------------+ 428 | row bits | effective column bits | short range bits | 429 | | (e.g. 7) | (e.g. 5) | 430 +-------------------------+-----------------------+-------------------+ */ 431 unsigned int m_range_bits : 8; 432 }; 433 434 /* This is the highest possible source location encoded within an 435 ordinary or macro map. */ 436 const source_location MAX_SOURCE_LOCATION = 0x7FFFFFFF; 437 438 struct cpp_hashnode; 439 440 /* A macro line map encodes location of tokens coming from a macro 441 expansion. 442 443 The offset from START_LOCATION is used to index into 444 MACRO_LOCATIONS; this holds the original location of the token. */ 445 struct GTY((tag ("2"))) line_map_macro : public line_map { 446 /* The cpp macro which expansion gave birth to this macro map. */ 447 struct cpp_hashnode * GTY ((nested_ptr (union tree_node, 448 "%h ? CPP_HASHNODE (GCC_IDENT_TO_HT_IDENT (%h)) : NULL", 449 "%h ? HT_IDENT_TO_GCC_IDENT (HT_NODE (%h)) : NULL"))) 450 macro; 451 452 /* The number of tokens inside the replacement-list of MACRO. */ 453 unsigned int n_tokens; 454 455 /* This array of location is actually an array of pairs of 456 locations. The elements inside it thus look like: 457 458 x0,y0, x1,y1, x2,y2, ...., xn,yn. 459 460 where n == n_tokens; 461 462 Remember that these xI,yI are collected when libcpp is about to 463 expand a given macro. 464 465 yI is the location in the macro definition, either of the token 466 itself or of a macro parameter that it replaces. 467 468 Imagine this: 469 470 #define PLUS(A, B) A + B <--- #1 471 472 int a = PLUS (1,2); <--- #2 473 474 There is a macro map for the expansion of PLUS in #2. PLUS is 475 expanded into its expansion-list. The expansion-list is the 476 replacement-list of PLUS where the macro parameters are replaced 477 with their arguments. So the replacement-list of PLUS is made of 478 the tokens: 479 480 A, +, B 481 482 and the expansion-list is made of the tokens: 483 484 1, +, 2 485 486 Let's consider the case of token "+". Its y1 [yI for I == 1] is 487 its spelling location in #1. 488 489 y0 (thus for token "1") is the spelling location of A in #1. 490 491 And y2 (of token "2") is the spelling location of B in #1. 492 493 When the token is /not/ an argument for a macro, xI is the same 494 location as yI. Otherwise, xI is the location of the token 495 outside this macro expansion. If this macro was expanded from 496 another macro expansion, xI is a virtual location representing 497 the token in that macro expansion; otherwise, it is the spelling 498 location of the token. 499 500 Note that a virtual location is a location returned by 501 linemap_add_macro_token. It encodes the relevant locations (x,y 502 pairs) of that token across the macro expansions from which it 503 (the token) might come from. 504 505 In the example above x1 (for token "+") is going to be the same 506 as y1. x0 is the spelling location for the argument token "1", 507 and x2 is the spelling location for the argument token "2". */ 508 source_location * GTY((atomic)) macro_locations; 509 510 /* This is the location of the expansion point of the current macro 511 map. It's the location of the macro name. That location is held 512 by the map that was current right before the current one. It 513 could have been either a macro or an ordinary map, depending on 514 if we are in a nested expansion context not. */ 515 source_location expansion; 516 }; 517 518 #if CHECKING_P && (GCC_VERSION >= 2007) 519 520 /* Assertion macro to be used in line-map code. */ 521 #define linemap_assert(EXPR) \ 522 do { \ 523 if (! (EXPR)) \ 524 abort (); \ 525 } while (0) 526 527 /* Assert that becomes a conditional expression when checking is disabled at 528 compilation time. Use this for conditions that should not happen but if 529 they happen, it is better to handle them gracefully rather than crash 530 randomly later. 531 Usage: 532 533 if (linemap_assert_fails(EXPR)) handle_error(); */ 534 #define linemap_assert_fails(EXPR) __extension__ \ 535 ({linemap_assert (EXPR); false;}) 536 537 #else 538 /* Include EXPR, so that unused variable warnings do not occur. */ 539 #define linemap_assert(EXPR) ((void)(0 && (EXPR))) 540 #define linemap_assert_fails(EXPR) (! (EXPR)) 541 #endif 542 543 /* Return TRUE if MAP encodes locations coming from a macro 544 replacement-list at macro expansion point. */ 545 bool 546 linemap_macro_expansion_map_p (const struct line_map *); 547 548 /* Assert that MAP encodes locations of tokens that are not part of 549 the replacement-list of a macro expansion, downcasting from 550 line_map * to line_map_ordinary *. */ 551 552 inline line_map_ordinary * 553 linemap_check_ordinary (struct line_map *map) 554 { 555 linemap_assert (!linemap_macro_expansion_map_p (map)); 556 return (line_map_ordinary *)map; 557 } 558 559 /* Assert that MAP encodes locations of tokens that are not part of 560 the replacement-list of a macro expansion, downcasting from 561 const line_map * to const line_map_ordinary *. */ 562 563 inline const line_map_ordinary * 564 linemap_check_ordinary (const struct line_map *map) 565 { 566 linemap_assert (!linemap_macro_expansion_map_p (map)); 567 return (const line_map_ordinary *)map; 568 } 569 570 /* Assert that MAP is a macro expansion and downcast to the appropriate 571 subclass. */ 572 573 inline line_map_macro *linemap_check_macro (line_map *map) 574 { 575 linemap_assert (linemap_macro_expansion_map_p (map)); 576 return (line_map_macro *)map; 577 } 578 579 /* Assert that MAP is a macro expansion and downcast to the appropriate 580 subclass. */ 581 582 inline const line_map_macro * 583 linemap_check_macro (const line_map *map) 584 { 585 linemap_assert (linemap_macro_expansion_map_p (map)); 586 return (const line_map_macro *)map; 587 } 588 589 /* Read the start location of MAP. */ 590 591 inline source_location 592 MAP_START_LOCATION (const line_map *map) 593 { 594 return map->start_location; 595 } 596 597 /* Get the starting line number of ordinary map MAP. */ 598 599 inline linenum_type 600 ORDINARY_MAP_STARTING_LINE_NUMBER (const line_map_ordinary *ord_map) 601 { 602 return ord_map->to_line; 603 } 604 605 /* Get the index of the ordinary map at whose end 606 ordinary map MAP was included. 607 608 File(s) at the bottom of the include stack have this set. */ 609 610 inline int 611 ORDINARY_MAP_INCLUDER_FILE_INDEX (const line_map_ordinary *ord_map) 612 { 613 return ord_map->included_from; 614 } 615 616 /* Return a positive value if map encodes locations from a system 617 header, 0 otherwise. Returns 1 if ordinary map MAP encodes locations 618 in a system header and 2 if it encodes locations in a C system header 619 that therefore needs to be extern "C" protected in C++. */ 620 621 inline unsigned char 622 ORDINARY_MAP_IN_SYSTEM_HEADER_P (const line_map_ordinary *ord_map) 623 { 624 return ord_map->sysp; 625 } 626 627 /* Get the filename of ordinary map MAP. */ 628 629 inline const char * 630 ORDINARY_MAP_FILE_NAME (const line_map_ordinary *ord_map) 631 { 632 return ord_map->to_file; 633 } 634 635 /* Get the cpp macro whose expansion gave birth to macro map MAP. */ 636 637 inline cpp_hashnode * 638 MACRO_MAP_MACRO (const line_map_macro *macro_map) 639 { 640 return macro_map->macro; 641 } 642 643 /* Get the number of tokens inside the replacement-list of the macro 644 that led to macro map MAP. */ 645 646 inline unsigned int 647 MACRO_MAP_NUM_MACRO_TOKENS (const line_map_macro *macro_map) 648 { 649 return macro_map->n_tokens; 650 } 651 652 /* Get the array of pairs of locations within macro map MAP. 653 See the declaration of line_map_macro for more information. */ 654 655 inline source_location * 656 MACRO_MAP_LOCATIONS (const line_map_macro *macro_map) 657 { 658 return macro_map->macro_locations; 659 } 660 661 /* Get the location of the expansion point of the macro map MAP. */ 662 663 inline source_location 664 MACRO_MAP_EXPANSION_POINT_LOCATION (const line_map_macro *macro_map) 665 { 666 return macro_map->expansion; 667 } 668 669 /* The abstraction of a set of location maps. There can be several 670 types of location maps. This abstraction contains the attributes 671 that are independent from the type of the map. 672 673 Essentially this is just a vector of T_linemap_subclass, 674 which can only ever grow in size. */ 675 676 struct GTY(()) maps_info_ordinary { 677 /* This array contains the "ordinary" line maps, for all 678 events other than macro expansion 679 (e.g. when a new preprocessing unit starts or ends). */ 680 line_map_ordinary * GTY ((length ("%h.used"))) maps; 681 682 /* The total number of allocated maps. */ 683 unsigned int allocated; 684 685 /* The number of elements used in maps. This number is smaller 686 or equal to ALLOCATED. */ 687 unsigned int used; 688 689 unsigned int cache; 690 }; 691 692 struct GTY(()) maps_info_macro { 693 /* This array contains the macro line maps. 694 A macro line map is created whenever a macro expansion occurs. */ 695 line_map_macro * GTY ((length ("%h.used"))) maps; 696 697 /* The total number of allocated maps. */ 698 unsigned int allocated; 699 700 /* The number of elements used in maps. This number is smaller 701 or equal to ALLOCATED. */ 702 unsigned int used; 703 704 unsigned int cache; 705 }; 706 707 /* Data structure to associate a source_range together with an arbitrary 708 data pointer with a source location. */ 709 struct GTY(()) location_adhoc_data { 710 source_location locus; 711 source_range src_range; 712 void * GTY((skip)) data; 713 }; 714 715 struct htab; 716 717 /* The following data structure encodes a location with some adhoc data 718 and maps it to a new unsigned integer (called an adhoc location) 719 that replaces the original location to represent the mapping. 720 721 The new adhoc_loc uses the highest bit as the enabling bit, i.e. if the 722 highest bit is 1, then the number is adhoc_loc. Otherwise, it serves as 723 the original location. Once identified as the adhoc_loc, the lower 31 724 bits of the integer is used to index the location_adhoc_data array, 725 in which the locus and associated data is stored. */ 726 727 struct GTY(()) location_adhoc_data_map { 728 struct htab * GTY((skip)) htab; 729 source_location curr_loc; 730 unsigned int allocated; 731 struct location_adhoc_data GTY((length ("%h.allocated"))) *data; 732 }; 733 734 /* A set of chronological line_map structures. */ 735 struct GTY(()) line_maps { 736 737 ~line_maps (); 738 739 maps_info_ordinary info_ordinary; 740 741 maps_info_macro info_macro; 742 743 /* Depth of the include stack, including the current file. */ 744 unsigned int depth; 745 746 /* If true, prints an include trace a la -H. */ 747 bool trace_includes; 748 749 /* Highest source_location "given out". */ 750 source_location highest_location; 751 752 /* Start of line of highest source_location "given out". */ 753 source_location highest_line; 754 755 /* The maximum column number we can quickly allocate. Higher numbers 756 may require allocating a new line_map. */ 757 unsigned int max_column_hint; 758 759 /* If non-null, the allocator to use when resizing 'maps'. If null, 760 xrealloc is used. */ 761 line_map_realloc reallocator; 762 763 /* The allocators' function used to know the actual size it 764 allocated, for a certain allocation size requested. */ 765 line_map_round_alloc_size_func round_alloc_size; 766 767 struct location_adhoc_data_map location_adhoc_data_map; 768 769 /* The special location value that is used as spelling location for 770 built-in tokens. */ 771 source_location builtin_location; 772 773 /* True if we've seen a #line or # 44 "file" directive. */ 774 bool seen_line_directive; 775 776 /* The default value of range_bits in ordinary line maps. */ 777 unsigned int default_range_bits; 778 779 unsigned int num_optimized_ranges; 780 unsigned int num_unoptimized_ranges; 781 }; 782 783 /* Returns the number of allocated maps so far. MAP_KIND shall be TRUE 784 if we are interested in macro maps, FALSE otherwise. */ 785 inline unsigned int 786 LINEMAPS_ALLOCATED (const line_maps *set, bool map_kind) 787 { 788 if (map_kind) 789 return set->info_macro.allocated; 790 else 791 return set->info_ordinary.allocated; 792 } 793 794 /* As above, but by reference (e.g. as an lvalue). */ 795 796 inline unsigned int & 797 LINEMAPS_ALLOCATED (line_maps *set, bool map_kind) 798 { 799 if (map_kind) 800 return set->info_macro.allocated; 801 else 802 return set->info_ordinary.allocated; 803 } 804 805 /* Returns the number of used maps so far. MAP_KIND shall be TRUE if 806 we are interested in macro maps, FALSE otherwise.*/ 807 inline unsigned int 808 LINEMAPS_USED (const line_maps *set, bool map_kind) 809 { 810 if (map_kind) 811 return set->info_macro.used; 812 else 813 return set->info_ordinary.used; 814 } 815 816 /* As above, but by reference (e.g. as an lvalue). */ 817 818 inline unsigned int & 819 LINEMAPS_USED (line_maps *set, bool map_kind) 820 { 821 if (map_kind) 822 return set->info_macro.used; 823 else 824 return set->info_ordinary.used; 825 } 826 827 /* Returns the index of the last map that was looked up with 828 linemap_lookup. MAP_KIND shall be TRUE if we are interested in 829 macro maps, FALSE otherwise. */ 830 inline unsigned int 831 LINEMAPS_CACHE (const line_maps *set, bool map_kind) 832 { 833 if (map_kind) 834 return set->info_macro.cache; 835 else 836 return set->info_ordinary.cache; 837 } 838 839 /* As above, but by reference (e.g. as an lvalue). */ 840 841 inline unsigned int & 842 LINEMAPS_CACHE (line_maps *set, bool map_kind) 843 { 844 if (map_kind) 845 return set->info_macro.cache; 846 else 847 return set->info_ordinary.cache; 848 } 849 850 /* Return the map at a given index. */ 851 inline line_map * 852 LINEMAPS_MAP_AT (const line_maps *set, bool map_kind, int index) 853 { 854 if (map_kind) 855 return &set->info_macro.maps[index]; 856 else 857 return &set->info_ordinary.maps[index]; 858 } 859 860 /* Returns the last map used in the line table SET. MAP_KIND 861 shall be TRUE if we are interested in macro maps, FALSE 862 otherwise.*/ 863 inline line_map * 864 LINEMAPS_LAST_MAP (const line_maps *set, bool map_kind) 865 { 866 return LINEMAPS_MAP_AT (set, map_kind, 867 LINEMAPS_USED (set, map_kind) - 1); 868 } 869 870 /* Returns the last map that was allocated in the line table SET. 871 MAP_KIND shall be TRUE if we are interested in macro maps, FALSE 872 otherwise.*/ 873 inline line_map * 874 LINEMAPS_LAST_ALLOCATED_MAP (const line_maps *set, bool map_kind) 875 { 876 return LINEMAPS_MAP_AT (set, map_kind, 877 LINEMAPS_ALLOCATED (set, map_kind) - 1); 878 } 879 880 /* Returns a pointer to the memory region where ordinary maps are 881 allocated in the line table SET. */ 882 inline line_map_ordinary * 883 LINEMAPS_ORDINARY_MAPS (const line_maps *set) 884 { 885 return set->info_ordinary.maps; 886 } 887 888 /* Returns the INDEXth ordinary map. */ 889 inline line_map_ordinary * 890 LINEMAPS_ORDINARY_MAP_AT (const line_maps *set, int index) 891 { 892 linemap_assert (index >= 0); 893 linemap_assert ((unsigned int)index < set->info_ordinary.used); 894 return &set->info_ordinary.maps[index]; 895 } 896 897 /* Return the number of ordinary maps allocated in the line table 898 SET. */ 899 inline unsigned int 900 LINEMAPS_ORDINARY_ALLOCATED (const line_maps *set) 901 { 902 return LINEMAPS_ALLOCATED (set, false); 903 } 904 905 /* Return the number of ordinary maps used in the line table SET. */ 906 inline unsigned int 907 LINEMAPS_ORDINARY_USED (const line_maps *set) 908 { 909 return LINEMAPS_USED (set, false); 910 } 911 912 /* Return the index of the last ordinary map that was looked up with 913 linemap_lookup. */ 914 inline unsigned int 915 LINEMAPS_ORDINARY_CACHE (const line_maps *set) 916 { 917 return LINEMAPS_CACHE (set, false); 918 } 919 920 /* As above, but by reference (e.g. as an lvalue). */ 921 922 inline unsigned int & 923 LINEMAPS_ORDINARY_CACHE (line_maps *set) 924 { 925 return LINEMAPS_CACHE (set, false); 926 } 927 928 /* Returns a pointer to the last ordinary map used in the line table 929 SET. */ 930 inline line_map_ordinary * 931 LINEMAPS_LAST_ORDINARY_MAP (const line_maps *set) 932 { 933 return (line_map_ordinary *)LINEMAPS_LAST_MAP (set, false); 934 } 935 936 /* Returns a pointer to the last ordinary map allocated the line table 937 SET. */ 938 inline line_map_ordinary * 939 LINEMAPS_LAST_ALLOCATED_ORDINARY_MAP (const line_maps *set) 940 { 941 return (line_map_ordinary *)LINEMAPS_LAST_ALLOCATED_MAP (set, false); 942 } 943 944 /* Returns a pointer to the beginning of the region where macro maps 945 are allocated. */ 946 inline line_map_macro * 947 LINEMAPS_MACRO_MAPS (const line_maps *set) 948 { 949 return set->info_macro.maps; 950 } 951 952 /* Returns the INDEXth macro map. */ 953 inline line_map_macro * 954 LINEMAPS_MACRO_MAP_AT (const line_maps *set, int index) 955 { 956 linemap_assert (index >= 0); 957 linemap_assert ((unsigned int)index < set->info_macro.used); 958 return &set->info_macro.maps[index]; 959 } 960 961 /* Returns the number of macro maps that were allocated in the line 962 table SET. */ 963 inline unsigned int 964 LINEMAPS_MACRO_ALLOCATED (const line_maps *set) 965 { 966 return LINEMAPS_ALLOCATED (set, true); 967 } 968 969 /* Returns the number of macro maps used in the line table SET. */ 970 inline unsigned int 971 LINEMAPS_MACRO_USED (const line_maps *set) 972 { 973 return LINEMAPS_USED (set, true); 974 } 975 976 /* Returns the index of the last macro map looked up with 977 linemap_lookup. */ 978 inline unsigned int 979 LINEMAPS_MACRO_CACHE (const line_maps *set) 980 { 981 return LINEMAPS_CACHE (set, true); 982 } 983 984 /* As above, but by reference (e.g. as an lvalue). */ 985 986 inline unsigned int & 987 LINEMAPS_MACRO_CACHE (line_maps *set) 988 { 989 return LINEMAPS_CACHE (set, true); 990 } 991 992 /* Returns the last macro map used in the line table SET. */ 993 inline line_map_macro * 994 LINEMAPS_LAST_MACRO_MAP (const line_maps *set) 995 { 996 return (line_map_macro *)LINEMAPS_LAST_MAP (set, true); 997 } 998 999 /* Returns the lowest location [of a token resulting from macro 1000 expansion] encoded in this line table. */ 1001 inline source_location 1002 LINEMAPS_MACRO_LOWEST_LOCATION (const line_maps *set) 1003 { 1004 return LINEMAPS_MACRO_USED (set) 1005 ? MAP_START_LOCATION (LINEMAPS_LAST_MACRO_MAP (set)) 1006 : MAX_SOURCE_LOCATION; 1007 } 1008 1009 /* Returns the last macro map allocated in the line table SET. */ 1010 inline line_map_macro * 1011 LINEMAPS_LAST_ALLOCATED_MACRO_MAP (const line_maps *set) 1012 { 1013 return (line_map_macro *)LINEMAPS_LAST_ALLOCATED_MAP (set, true); 1014 } 1015 1016 extern source_location get_combined_adhoc_loc (struct line_maps *, 1017 source_location, 1018 source_range, 1019 void *); 1020 extern void *get_data_from_adhoc_loc (struct line_maps *, source_location); 1021 extern source_location get_location_from_adhoc_loc (struct line_maps *, 1022 source_location); 1023 1024 extern source_range get_range_from_loc (line_maps *set, source_location loc); 1025 1026 /* Get whether location LOC is an ad-hoc location. */ 1027 1028 inline bool 1029 IS_ADHOC_LOC (source_location loc) 1030 { 1031 return (loc & MAX_SOURCE_LOCATION) != loc; 1032 } 1033 1034 /* Get whether location LOC is a "pure" location, or 1035 whether it is an ad-hoc location, or embeds range information. */ 1036 1037 bool 1038 pure_location_p (line_maps *set, source_location loc); 1039 1040 /* Given location LOC within SET, strip away any packed range information 1041 or ad-hoc information. */ 1042 1043 extern source_location get_pure_location (line_maps *set, 1044 source_location loc); 1045 1046 /* Combine LOC and BLOCK, giving a combined adhoc location. */ 1047 1048 inline source_location 1049 COMBINE_LOCATION_DATA (struct line_maps *set, 1050 source_location loc, 1051 source_range src_range, 1052 void *block) 1053 { 1054 return get_combined_adhoc_loc (set, loc, src_range, block); 1055 } 1056 1057 extern void rebuild_location_adhoc_htab (struct line_maps *); 1058 1059 /* Initialize a line map set. SET is the line map set to initialize 1060 and BUILTIN_LOCATION is the special location value to be used as 1061 spelling location for built-in tokens. This BUILTIN_LOCATION has 1062 to be strictly less than RESERVED_LOCATION_COUNT. */ 1063 extern void linemap_init (struct line_maps *set, 1064 source_location builtin_location); 1065 1066 /* Check for and warn about line_maps entered but not exited. */ 1067 1068 extern void linemap_check_files_exited (struct line_maps *); 1069 1070 /* Return a source_location for the start (i.e. column==0) of 1071 (physical) line TO_LINE in the current source file (as in the 1072 most recent linemap_add). MAX_COLUMN_HINT is the highest column 1073 number we expect to use in this line (but it does not change 1074 the highest_location). */ 1075 1076 extern source_location linemap_line_start 1077 (struct line_maps *set, linenum_type to_line, unsigned int max_column_hint); 1078 1079 /* Add a mapping of logical source line to physical source file and 1080 line number. This function creates an "ordinary map", which is a 1081 map that records locations of tokens that are not part of macro 1082 replacement-lists present at a macro expansion point. 1083 1084 The text pointed to by TO_FILE must have a lifetime 1085 at least as long as the lifetime of SET. An empty 1086 TO_FILE means standard input. If reason is LC_LEAVE, and 1087 TO_FILE is NULL, then TO_FILE, TO_LINE and SYSP are given their 1088 natural values considering the file we are returning to. 1089 1090 A call to this function can relocate the previous set of 1091 maps, so any stored line_map pointers should not be used. */ 1092 extern const struct line_map *linemap_add 1093 (struct line_maps *, enum lc_reason, unsigned int sysp, 1094 const char *to_file, linenum_type to_line); 1095 1096 /* Given a logical source location, returns the map which the 1097 corresponding (source file, line, column) triplet can be deduced 1098 from. Since the set is built chronologically, the logical lines are 1099 monotonic increasing, and so the list is sorted and we can use a 1100 binary search. If no line map have been allocated yet, this 1101 function returns NULL. */ 1102 extern const struct line_map *linemap_lookup 1103 (struct line_maps *, source_location); 1104 1105 /* Returns TRUE if the line table set tracks token locations across 1106 macro expansion, FALSE otherwise. */ 1107 bool linemap_tracks_macro_expansion_locs_p (struct line_maps *); 1108 1109 /* Return the name of the macro associated to MACRO_MAP. */ 1110 const char* linemap_map_get_macro_name (const line_map_macro *); 1111 1112 /* Return a positive value if LOCATION is the locus of a token that is 1113 located in a system header, O otherwise. It returns 1 if LOCATION 1114 is the locus of a token that is located in a system header, and 2 1115 if LOCATION is the locus of a token located in a C system header 1116 that therefore needs to be extern "C" protected in C++. 1117 1118 Note that this function returns 1 if LOCATION belongs to a token 1119 that is part of a macro replacement-list defined in a system 1120 header, but expanded in a non-system file. */ 1121 int linemap_location_in_system_header_p (struct line_maps *, 1122 source_location); 1123 1124 /* Return TRUE if LOCATION is a source code location of a token that is part of 1125 a macro expansion, FALSE otherwise. */ 1126 bool linemap_location_from_macro_expansion_p (const struct line_maps *, 1127 source_location); 1128 1129 /* TRUE if LOCATION is a source code location of a token that is part of the 1130 definition of a macro, FALSE otherwise. */ 1131 bool linemap_location_from_macro_definition_p (struct line_maps *, 1132 source_location); 1133 1134 /* With the precondition that LOCATION is the locus of a token that is 1135 an argument of a function-like macro MACRO_MAP and appears in the 1136 expansion of MACRO_MAP, return the locus of that argument in the 1137 context of the caller of MACRO_MAP. */ 1138 1139 extern source_location linemap_macro_map_loc_unwind_toward_spelling 1140 (line_maps *set, const line_map_macro *macro_map, source_location location); 1141 1142 /* source_location values from 0 to RESERVED_LOCATION_COUNT-1 will 1143 be reserved for libcpp user as special values, no token from libcpp 1144 will contain any of those locations. */ 1145 const source_location RESERVED_LOCATION_COUNT = 2; 1146 1147 /* Converts a map and a source_location to source line. */ 1148 inline linenum_type 1149 SOURCE_LINE (const line_map_ordinary *ord_map, source_location loc) 1150 { 1151 return ((loc - ord_map->start_location) 1152 >> ord_map->m_column_and_range_bits) + ord_map->to_line; 1153 } 1154 1155 /* Convert a map and source_location to source column number. */ 1156 inline linenum_type 1157 SOURCE_COLUMN (const line_map_ordinary *ord_map, source_location loc) 1158 { 1159 return ((loc - ord_map->start_location) 1160 & ((1 << ord_map->m_column_and_range_bits) - 1)) >> ord_map->m_range_bits; 1161 } 1162 1163 /* Return the location of the last source line within an ordinary 1164 map. */ 1165 inline source_location 1166 LAST_SOURCE_LINE_LOCATION (const line_map_ordinary *map) 1167 { 1168 return (((map[1].start_location - 1 1169 - map->start_location) 1170 & ~((1 << map->m_column_and_range_bits) - 1)) 1171 + map->start_location); 1172 } 1173 1174 /* Returns the last source line number within an ordinary map. This 1175 is the (last) line of the #include, or other directive, that caused 1176 a map change. */ 1177 inline linenum_type 1178 LAST_SOURCE_LINE (const line_map_ordinary *map) 1179 { 1180 return SOURCE_LINE (map, LAST_SOURCE_LINE_LOCATION (map)); 1181 } 1182 1183 /* Return the last column number within an ordinary map. */ 1184 1185 inline linenum_type 1186 LAST_SOURCE_COLUMN (const line_map_ordinary *map) 1187 { 1188 return SOURCE_COLUMN (map, LAST_SOURCE_LINE_LOCATION (map)); 1189 } 1190 1191 /* Returns the map a given map was included from, or NULL if the map 1192 belongs to the main file, i.e, a file that wasn't included by 1193 another one. */ 1194 inline line_map_ordinary * 1195 INCLUDED_FROM (struct line_maps *set, const line_map_ordinary *ord_map) 1196 { 1197 return ((ord_map->included_from == -1) 1198 ? NULL 1199 : LINEMAPS_ORDINARY_MAP_AT (set, ord_map->included_from)); 1200 } 1201 1202 /* True if the map is at the bottom of the include stack. */ 1203 1204 inline bool 1205 MAIN_FILE_P (const line_map_ordinary *ord_map) 1206 { 1207 return ord_map->included_from < 0; 1208 } 1209 1210 /* Encode and return a source_location from a column number. The 1211 source line considered is the last source line used to call 1212 linemap_line_start, i.e, the last source line which a location was 1213 encoded from. */ 1214 extern source_location 1215 linemap_position_for_column (struct line_maps *, unsigned int); 1216 1217 /* Encode and return a source location from a given line and 1218 column. */ 1219 source_location 1220 linemap_position_for_line_and_column (line_maps *set, 1221 const line_map_ordinary *, 1222 linenum_type, unsigned int); 1223 1224 /* Encode and return a source_location starting from location LOC and 1225 shifting it by OFFSET columns. This function does not support 1226 virtual locations. */ 1227 source_location 1228 linemap_position_for_loc_and_offset (struct line_maps *set, 1229 source_location loc, 1230 unsigned int offset); 1231 1232 /* Return the file this map is for. */ 1233 inline const char * 1234 LINEMAP_FILE (const line_map_ordinary *ord_map) 1235 { 1236 return ord_map->to_file; 1237 } 1238 1239 /* Return the line number this map started encoding location from. */ 1240 inline linenum_type 1241 LINEMAP_LINE (const line_map_ordinary *ord_map) 1242 { 1243 return ord_map->to_line; 1244 } 1245 1246 /* Return a positive value if map encodes locations from a system 1247 header, 0 otherwise. Returns 1 if MAP encodes locations in a 1248 system header and 2 if it encodes locations in a C system header 1249 that therefore needs to be extern "C" protected in C++. */ 1250 inline unsigned char 1251 LINEMAP_SYSP (const line_map_ordinary *ord_map) 1252 { 1253 return ord_map->sysp; 1254 } 1255 1256 /* Return a positive value if PRE denotes the location of a token that 1257 comes before the token of POST, 0 if PRE denotes the location of 1258 the same token as the token for POST, and a negative value 1259 otherwise. */ 1260 int linemap_compare_locations (struct line_maps *set, 1261 source_location pre, 1262 source_location post); 1263 1264 /* Return TRUE if LOC_A denotes the location a token that comes 1265 topogically before the token denoted by location LOC_B, or if they 1266 are equal. */ 1267 inline bool 1268 linemap_location_before_p (struct line_maps *set, 1269 source_location loc_a, 1270 source_location loc_b) 1271 { 1272 return linemap_compare_locations (set, loc_a, loc_b) >= 0; 1273 } 1274 1275 typedef struct 1276 { 1277 /* The name of the source file involved. */ 1278 const char *file; 1279 1280 /* The line-location in the source file. */ 1281 int line; 1282 1283 int column; 1284 1285 void *data; 1286 1287 /* In a system header?. */ 1288 bool sysp; 1289 } expanded_location; 1290 1291 /* A location within a rich_location: a caret&range, with 1292 the caret potentially flagged for display. */ 1293 1294 struct location_range 1295 { 1296 source_location m_loc; 1297 1298 /* Should a caret be drawn for this range? Typically this is 1299 true for the 0th range, and false for subsequent ranges, 1300 but the Fortran frontend overrides this for rendering things like: 1301 1302 x = x + y 1303 1 2 1304 Error: Shapes for operands at (1) and (2) are not conformable 1305 1306 where "1" and "2" are notionally carets. */ 1307 bool m_show_caret_p; 1308 }; 1309 1310 /* A partially-embedded vec for use within rich_location for storing 1311 ranges and fix-it hints. 1312 1313 Elements [0..NUM_EMBEDDED) are allocated within m_embed, after 1314 that they are within the dynamically-allocated m_extra. 1315 1316 This allows for static allocation in the common case, whilst 1317 supporting the rarer case of an arbitrary number of elements. 1318 1319 Dynamic allocation is not performed unless it's needed. */ 1320 1321 template <typename T, int NUM_EMBEDDED> 1322 class semi_embedded_vec 1323 { 1324 public: 1325 semi_embedded_vec (); 1326 ~semi_embedded_vec (); 1327 1328 unsigned int count () const { return m_num; } 1329 T& operator[] (int idx); 1330 const T& operator[] (int idx) const; 1331 1332 void push (const T&); 1333 void truncate (int len); 1334 1335 private: 1336 int m_num; 1337 T m_embedded[NUM_EMBEDDED]; 1338 int m_alloc; 1339 T *m_extra; 1340 }; 1341 1342 /* Constructor for semi_embedded_vec. In particular, no dynamic allocation 1343 is done. */ 1344 1345 template <typename T, int NUM_EMBEDDED> 1346 semi_embedded_vec<T, NUM_EMBEDDED>::semi_embedded_vec () 1347 : m_num (0), m_alloc (0), m_extra (NULL) 1348 { 1349 } 1350 1351 /* semi_embedded_vec's dtor. Release any dynamically-allocated memory. */ 1352 1353 template <typename T, int NUM_EMBEDDED> 1354 semi_embedded_vec<T, NUM_EMBEDDED>::~semi_embedded_vec () 1355 { 1356 XDELETEVEC (m_extra); 1357 } 1358 1359 /* Look up element IDX, mutably. */ 1360 1361 template <typename T, int NUM_EMBEDDED> 1362 T& 1363 semi_embedded_vec<T, NUM_EMBEDDED>::operator[] (int idx) 1364 { 1365 linemap_assert (idx < m_num); 1366 if (idx < NUM_EMBEDDED) 1367 return m_embedded[idx]; 1368 else 1369 { 1370 linemap_assert (m_extra != NULL); 1371 return m_extra[idx - NUM_EMBEDDED]; 1372 } 1373 } 1374 1375 /* Look up element IDX (const). */ 1376 1377 template <typename T, int NUM_EMBEDDED> 1378 const T& 1379 semi_embedded_vec<T, NUM_EMBEDDED>::operator[] (int idx) const 1380 { 1381 linemap_assert (idx < m_num); 1382 if (idx < NUM_EMBEDDED) 1383 return m_embedded[idx]; 1384 else 1385 { 1386 linemap_assert (m_extra != NULL); 1387 return m_extra[idx - NUM_EMBEDDED]; 1388 } 1389 } 1390 1391 /* Append VALUE to the end of the semi_embedded_vec. */ 1392 1393 template <typename T, int NUM_EMBEDDED> 1394 void 1395 semi_embedded_vec<T, NUM_EMBEDDED>::push (const T& value) 1396 { 1397 int idx = m_num++; 1398 if (idx < NUM_EMBEDDED) 1399 m_embedded[idx] = value; 1400 else 1401 { 1402 /* Offset "idx" to be an index within m_extra. */ 1403 idx -= NUM_EMBEDDED; 1404 if (NULL == m_extra) 1405 { 1406 linemap_assert (m_alloc == 0); 1407 m_alloc = 16; 1408 m_extra = XNEWVEC (T, m_alloc); 1409 } 1410 else if (idx >= m_alloc) 1411 { 1412 linemap_assert (m_alloc > 0); 1413 m_alloc *= 2; 1414 m_extra = XRESIZEVEC (T, m_extra, m_alloc); 1415 } 1416 linemap_assert (m_extra); 1417 linemap_assert (idx < m_alloc); 1418 m_extra[idx] = value; 1419 } 1420 } 1421 1422 /* Truncate to length LEN. No deallocation is performed. */ 1423 1424 template <typename T, int NUM_EMBEDDED> 1425 void 1426 semi_embedded_vec<T, NUM_EMBEDDED>::truncate (int len) 1427 { 1428 linemap_assert (len <= m_num); 1429 m_num = len; 1430 } 1431 1432 class fixit_hint; 1433 1434 /* A "rich" source code location, for use when printing diagnostics. 1435 A rich_location has one or more carets&ranges, where the carets 1436 are optional. These are referred to as "ranges" from here. 1437 Typically the zeroth range has a caret; other ranges sometimes 1438 have carets. 1439 1440 The "primary" location of a rich_location is the caret of range 0, 1441 used for determining the line/column when printing diagnostic 1442 text, such as: 1443 1444 some-file.c:3:1: error: ...etc... 1445 1446 Additional ranges may be added to help the user identify other 1447 pertinent clauses in a diagnostic. 1448 1449 rich_location instances are intended to be allocated on the stack 1450 when generating diagnostics, and to be short-lived. 1451 1452 Examples of rich locations 1453 -------------------------- 1454 1455 Example A 1456 ********* 1457 int i = "foo"; 1458 ^ 1459 This "rich" location is simply a single range (range 0), with 1460 caret = start = finish at the given point. 1461 1462 Example B 1463 ********* 1464 a = (foo && bar) 1465 ~~~~~^~~~~~~ 1466 This rich location has a single range (range 0), with the caret 1467 at the first "&", and the start/finish at the parentheses. 1468 Compare with example C below. 1469 1470 Example C 1471 ********* 1472 a = (foo && bar) 1473 ~~~ ^~ ~~~ 1474 This rich location has three ranges: 1475 - Range 0 has its caret and start location at the first "&" and 1476 end at the second "&. 1477 - Range 1 has its start and finish at the "f" and "o" of "foo"; 1478 the caret is not flagged for display, but is perhaps at the "f" 1479 of "foo". 1480 - Similarly, range 2 has its start and finish at the "b" and "r" of 1481 "bar"; the caret is not flagged for display, but is perhaps at the 1482 "b" of "bar". 1483 Compare with example B above. 1484 1485 Example D (Fortran frontend) 1486 **************************** 1487 x = x + y 1488 1 2 1489 This rich location has range 0 at "1", and range 1 at "2". 1490 Both are flagged for caret display. Both ranges have start/finish 1491 equal to their caret point. The frontend overrides the diagnostic 1492 context's default caret character for these ranges. 1493 1494 Example E 1495 ********* 1496 printf ("arg0: %i arg1: %s arg2: %i", 1497 ^~ 1498 100, 101, 102); 1499 ~~~ 1500 This rich location has two ranges: 1501 - range 0 is at the "%s" with start = caret = "%" and finish at 1502 the "s". 1503 - range 1 has start/finish covering the "101" and is not flagged for 1504 caret printing; it is perhaps at the start of "101". 1505 1506 1507 Fix-it hints 1508 ------------ 1509 1510 Rich locations can also contain "fix-it hints", giving suggestions 1511 for the user on how to edit their code to fix a problem. These 1512 can be expressed as insertions, replacements, and removals of text. 1513 The edits by default are relative to the zeroth range within the 1514 rich_location, but optionally they can be expressed relative to 1515 other locations (using various overloaded methods of the form 1516 rich_location::add_fixit_*). 1517 1518 For example: 1519 1520 Example F: fix-it hint: insert_before 1521 ************************************* 1522 ptr = arr[0]; 1523 ^~~~~~ 1524 & 1525 This rich location has a single range (range 0) covering "arr[0]", 1526 with the caret at the start. The rich location has a single 1527 insertion fix-it hint, inserted before range 0, added via 1528 richloc.add_fixit_insert_before ("&"); 1529 1530 Example G: multiple fix-it hints: insert_before and insert_after 1531 **************************************************************** 1532 #define FN(ARG0, ARG1, ARG2) fn(ARG0, ARG1, ARG2) 1533 ^~~~ ^~~~ ^~~~ 1534 ( ) ( ) ( ) 1535 This rich location has three ranges, covering "arg0", "arg1", 1536 and "arg2", all with caret-printing enabled. 1537 The rich location has 6 insertion fix-it hints: each arg 1538 has a pair of insertion fix-it hints, suggesting wrapping 1539 them with parentheses: one a '(' inserted before, 1540 the other a ')' inserted after, added via 1541 richloc.add_fixit_insert_before (LOC, "("); 1542 and 1543 richloc.add_fixit_insert_after (LOC, ")"); 1544 1545 Example H: fix-it hint: removal 1546 ******************************* 1547 struct s {int i};; 1548 ^ 1549 - 1550 This rich location has a single range at the stray trailing 1551 semicolon, along with a single removal fix-it hint, covering 1552 the same range, added via: 1553 richloc.add_fixit_remove (); 1554 1555 Example I: fix-it hint: replace 1556 ******************************* 1557 c = s.colour; 1558 ^~~~~~ 1559 color 1560 This rich location has a single range (range 0) covering "colour", 1561 and a single "replace" fix-it hint, covering the same range, 1562 added via 1563 richloc.add_fixit_replace ("color"); 1564 1565 Adding a fix-it hint can fail: for example, attempts to insert content 1566 at the transition between two line maps may fail due to there being no 1567 source_location (aka location_t) value to express the new location. 1568 1569 Attempts to add a fix-it hint within a macro expansion will fail. 1570 1571 There is only limited support for newline characters in fix-it hints: 1572 only hints with newlines which insert an entire new line are permitted, 1573 inserting at the start of a line, and finishing with a newline 1574 (with no interior newline characters). Other attempts to add 1575 fix-it hints containing newline characters will fail. 1576 Similarly, attempts to delete or replace a range *affecting* multiple 1577 lines will fail. 1578 1579 The rich_location API handles these failures gracefully, so that 1580 diagnostics can attempt to add fix-it hints without each needing 1581 extensive checking. 1582 1583 Fix-it hints within a rich_location are "atomic": if any hints can't 1584 be applied, none of them will be (tracked by the m_seen_impossible_fixit 1585 flag), and no fix-its hints will be displayed for that rich_location. 1586 This implies that diagnostic messages need to be worded in such a way 1587 that they make sense whether or not the fix-it hints are displayed, 1588 or that richloc.seen_impossible_fixit_p () should be checked before 1589 issuing the diagnostics. */ 1590 1591 class rich_location 1592 { 1593 public: 1594 /* Constructors. */ 1595 1596 /* Constructing from a location. */ 1597 rich_location (line_maps *set, source_location loc); 1598 1599 /* Destructor. */ 1600 ~rich_location (); 1601 1602 /* Accessors. */ 1603 source_location get_loc () const { return get_loc (0); } 1604 source_location get_loc (unsigned int idx) const; 1605 1606 void 1607 add_range (source_location loc, bool show_caret_p); 1608 1609 void 1610 set_range (line_maps *set, unsigned int idx, source_location loc, 1611 bool show_caret_p); 1612 1613 unsigned int get_num_locations () const { return m_ranges.count (); } 1614 1615 const location_range *get_range (unsigned int idx) const; 1616 location_range *get_range (unsigned int idx); 1617 1618 expanded_location get_expanded_location (unsigned int idx); 1619 1620 void 1621 override_column (int column); 1622 1623 /* Fix-it hints. */ 1624 1625 /* Methods for adding insertion fix-it hints. */ 1626 1627 /* Suggest inserting NEW_CONTENT immediately before the primary 1628 range's start. */ 1629 void 1630 add_fixit_insert_before (const char *new_content); 1631 1632 /* Suggest inserting NEW_CONTENT immediately before the start of WHERE. */ 1633 void 1634 add_fixit_insert_before (source_location where, 1635 const char *new_content); 1636 1637 /* Suggest inserting NEW_CONTENT immediately after the end of the primary 1638 range. */ 1639 void 1640 add_fixit_insert_after (const char *new_content); 1641 1642 /* Suggest inserting NEW_CONTENT immediately after the end of WHERE. */ 1643 void 1644 add_fixit_insert_after (source_location where, 1645 const char *new_content); 1646 1647 /* Methods for adding removal fix-it hints. */ 1648 1649 /* Suggest removing the content covered by range 0. */ 1650 void 1651 add_fixit_remove (); 1652 1653 /* Suggest removing the content covered between the start and finish 1654 of WHERE. */ 1655 void 1656 add_fixit_remove (source_location where); 1657 1658 /* Suggest removing the content covered by SRC_RANGE. */ 1659 void 1660 add_fixit_remove (source_range src_range); 1661 1662 /* Methods for adding "replace" fix-it hints. */ 1663 1664 /* Suggest replacing the content covered by range 0 with NEW_CONTENT. */ 1665 void 1666 add_fixit_replace (const char *new_content); 1667 1668 /* Suggest replacing the content between the start and finish of 1669 WHERE with NEW_CONTENT. */ 1670 void 1671 add_fixit_replace (source_location where, 1672 const char *new_content); 1673 1674 /* Suggest replacing the content covered by SRC_RANGE with 1675 NEW_CONTENT. */ 1676 void 1677 add_fixit_replace (source_range src_range, 1678 const char *new_content); 1679 1680 unsigned int get_num_fixit_hints () const { return m_fixit_hints.count (); } 1681 fixit_hint *get_fixit_hint (int idx) const { return m_fixit_hints[idx]; } 1682 fixit_hint *get_last_fixit_hint () const; 1683 bool seen_impossible_fixit_p () const { return m_seen_impossible_fixit; } 1684 1685 /* Set this if the fix-it hints are not suitable to be 1686 automatically applied. 1687 1688 For example, if you are suggesting more than one 1689 mutually exclusive solution to a problem, then 1690 it doesn't make sense to apply all of the solutions; 1691 manual intervention is required. 1692 1693 If set, then the fix-it hints in the rich_location will 1694 be printed, but will not be added to generated patches, 1695 or affect the modified version of the file. */ 1696 void fixits_cannot_be_auto_applied () 1697 { 1698 m_fixits_cannot_be_auto_applied = true; 1699 } 1700 1701 bool fixits_can_be_auto_applied_p () const 1702 { 1703 return !m_fixits_cannot_be_auto_applied; 1704 } 1705 1706 private: 1707 bool reject_impossible_fixit (source_location where); 1708 void stop_supporting_fixits (); 1709 void maybe_add_fixit (source_location start, 1710 source_location next_loc, 1711 const char *new_content); 1712 1713 public: 1714 static const int STATICALLY_ALLOCATED_RANGES = 3; 1715 1716 protected: 1717 line_maps *m_line_table; 1718 semi_embedded_vec <location_range, STATICALLY_ALLOCATED_RANGES> m_ranges; 1719 1720 int m_column_override; 1721 1722 bool m_have_expanded_location; 1723 expanded_location m_expanded_location; 1724 1725 static const int MAX_STATIC_FIXIT_HINTS = 2; 1726 semi_embedded_vec <fixit_hint *, MAX_STATIC_FIXIT_HINTS> m_fixit_hints; 1727 1728 bool m_seen_impossible_fixit; 1729 bool m_fixits_cannot_be_auto_applied; 1730 }; 1731 1732 /* A fix-it hint: a suggested insertion, replacement, or deletion of text. 1733 We handle these three types of edit with one class, by representing 1734 them as replacement of a half-open range: 1735 [start, next_loc) 1736 Insertions have start == next_loc: "replace" the empty string at the 1737 start location with the new string. 1738 Deletions are replacement with the empty string. 1739 1740 There is only limited support for newline characters in fix-it hints 1741 as noted above in the comment for class rich_location. 1742 A fixit_hint instance can have at most one newline character; if 1743 present, the newline character must be the final character of 1744 the content (preventing e.g. fix-its that split a pre-existing line). */ 1745 1746 class fixit_hint 1747 { 1748 public: 1749 fixit_hint (source_location start, 1750 source_location next_loc, 1751 const char *new_content); 1752 ~fixit_hint () { free (m_bytes); } 1753 1754 bool affects_line_p (const char *file, int line) const; 1755 source_location get_start_loc () const { return m_start; } 1756 source_location get_next_loc () const { return m_next_loc; } 1757 bool maybe_append (source_location start, 1758 source_location next_loc, 1759 const char *new_content); 1760 1761 const char *get_string () const { return m_bytes; } 1762 size_t get_length () const { return m_len; } 1763 1764 bool insertion_p () const { return m_start == m_next_loc; } 1765 1766 bool ends_with_newline_p () const; 1767 1768 private: 1769 /* We don't use source_range here since, unlike most places, 1770 this is a half-open/half-closed range: 1771 [start, next_loc) 1772 so that we can support insertion via start == next_loc. */ 1773 source_location m_start; 1774 source_location m_next_loc; 1775 char *m_bytes; 1776 size_t m_len; 1777 }; 1778 1779 1780 /* This is enum is used by the function linemap_resolve_location 1781 below. The meaning of the values is explained in the comment of 1782 that function. */ 1783 enum location_resolution_kind 1784 { 1785 LRK_MACRO_EXPANSION_POINT, 1786 LRK_SPELLING_LOCATION, 1787 LRK_MACRO_DEFINITION_LOCATION 1788 }; 1789 1790 /* Resolve a virtual location into either a spelling location, an 1791 expansion point location or a token argument replacement point 1792 location. Return the map that encodes the virtual location as well 1793 as the resolved location. 1794 1795 If LOC is *NOT* the location of a token resulting from the 1796 expansion of a macro, then the parameter LRK (which stands for 1797 Location Resolution Kind) is ignored and the resulting location 1798 just equals the one given in argument. 1799 1800 Now if LOC *IS* the location of a token resulting from the 1801 expansion of a macro, this is what happens. 1802 1803 * If LRK is set to LRK_MACRO_EXPANSION_POINT 1804 ------------------------------- 1805 1806 The virtual location is resolved to the first macro expansion point 1807 that led to this macro expansion. 1808 1809 * If LRK is set to LRK_SPELLING_LOCATION 1810 ------------------------------------- 1811 1812 The virtual location is resolved to the locus where the token has 1813 been spelled in the source. This can follow through all the macro 1814 expansions that led to the token. 1815 1816 * If LRK is set to LRK_MACRO_DEFINITION_LOCATION 1817 -------------------------------------- 1818 1819 The virtual location is resolved to the locus of the token in the 1820 context of the macro definition. 1821 1822 If LOC is the locus of a token that is an argument of a 1823 function-like macro [replacing a parameter in the replacement list 1824 of the macro] the virtual location is resolved to the locus of the 1825 parameter that is replaced, in the context of the definition of the 1826 macro. 1827 1828 If LOC is the locus of a token that is not an argument of a 1829 function-like macro, then the function behaves as if LRK was set to 1830 LRK_SPELLING_LOCATION. 1831 1832 If LOC_MAP is not NULL, *LOC_MAP is set to the map encoding the 1833 returned location. Note that if the returned location wasn't originally 1834 encoded by a map, the *MAP is set to NULL. This can happen if LOC 1835 resolves to a location reserved for the client code, like 1836 UNKNOWN_LOCATION or BUILTINS_LOCATION in GCC. */ 1837 1838 source_location linemap_resolve_location (struct line_maps *, 1839 source_location loc, 1840 enum location_resolution_kind lrk, 1841 const line_map_ordinary **loc_map); 1842 1843 /* Suppose that LOC is the virtual location of a token coming from the 1844 expansion of a macro M. This function then steps up to get the 1845 location L of the point where M got expanded. If L is a spelling 1846 location inside a macro expansion M', then this function returns 1847 the point where M' was expanded. LOC_MAP is an output parameter. 1848 When non-NULL, *LOC_MAP is set to the map of the returned 1849 location. */ 1850 source_location linemap_unwind_toward_expansion (struct line_maps *, 1851 source_location loc, 1852 const struct line_map **loc_map); 1853 1854 /* If LOC is the virtual location of a token coming from the expansion 1855 of a macro M and if its spelling location is reserved (e.g, a 1856 location for a built-in token), then this function unwinds (using 1857 linemap_unwind_toward_expansion) the location until a location that 1858 is not reserved and is not in a system header is reached. In other 1859 words, this unwinds the reserved location until a location that is 1860 in real source code is reached. 1861 1862 Otherwise, if the spelling location for LOC is not reserved or if 1863 LOC doesn't come from the expansion of a macro, the function 1864 returns LOC as is and *MAP is not touched. 1865 1866 *MAP is set to the map of the returned location if the later is 1867 different from LOC. */ 1868 source_location linemap_unwind_to_first_non_reserved_loc (struct line_maps *, 1869 source_location loc, 1870 const struct line_map **map); 1871 1872 /* Expand source code location LOC and return a user readable source 1873 code location. LOC must be a spelling (non-virtual) location. If 1874 it's a location < RESERVED_LOCATION_COUNT a zeroed expanded source 1875 location is returned. */ 1876 expanded_location linemap_expand_location (struct line_maps *, 1877 const struct line_map *, 1878 source_location loc); 1879 1880 /* Statistics about maps allocation and usage as returned by 1881 linemap_get_statistics. */ 1882 struct linemap_stats 1883 { 1884 long num_ordinary_maps_allocated; 1885 long num_ordinary_maps_used; 1886 long ordinary_maps_allocated_size; 1887 long ordinary_maps_used_size; 1888 long num_expanded_macros; 1889 long num_macro_tokens; 1890 long num_macro_maps_used; 1891 long macro_maps_allocated_size; 1892 long macro_maps_used_size; 1893 long macro_maps_locations_size; 1894 long duplicated_macro_maps_locations_size; 1895 long adhoc_table_size; 1896 long adhoc_table_entries_used; 1897 }; 1898 1899 /* Return the highest location emitted for a given file for which 1900 there is a line map in SET. FILE_NAME is the file name to 1901 consider. If the function returns TRUE, *LOC is set to the highest 1902 location emitted for that file. */ 1903 bool linemap_get_file_highest_location (struct line_maps * set, 1904 const char *file_name, 1905 source_location *loc); 1906 1907 /* Compute and return statistics about the memory consumption of some 1908 parts of the line table SET. */ 1909 void linemap_get_statistics (struct line_maps *, struct linemap_stats *); 1910 1911 /* Dump debugging information about source location LOC into the file 1912 stream STREAM. SET is the line map set LOC comes from. */ 1913 void linemap_dump_location (struct line_maps *, source_location, FILE *); 1914 1915 /* Dump line map at index IX in line table SET to STREAM. If STREAM 1916 is NULL, use stderr. IS_MACRO is true if the caller wants to 1917 dump a macro map, false otherwise. */ 1918 void linemap_dump (FILE *, struct line_maps *, unsigned, bool); 1919 1920 /* Dump line table SET to STREAM. If STREAM is NULL, stderr is used. 1921 NUM_ORDINARY specifies how many ordinary maps to dump. NUM_MACRO 1922 specifies how many macro maps to dump. */ 1923 void line_table_dump (FILE *, struct line_maps *, unsigned int, unsigned int); 1924 1925 /* An enum for distinguishing the various parts within a source_location. */ 1926 1927 enum location_aspect 1928 { 1929 LOCATION_ASPECT_CARET, 1930 LOCATION_ASPECT_START, 1931 LOCATION_ASPECT_FINISH 1932 }; 1933 1934 /* The rich_location class requires a way to expand source_location instances. 1935 We would directly use expand_location_to_spelling_point, which is 1936 implemented in gcc/input.c, but we also need to use it for rich_location 1937 within genmatch.c. 1938 Hence we require client code of libcpp to implement the following 1939 symbol. */ 1940 extern expanded_location 1941 linemap_client_expand_location_to_spelling_point (source_location, 1942 enum location_aspect); 1943 1944 #endif /* !LIBCPP_LINE_MAP_H */ 1945