1	/* Map (unsigned int) keys to (source file, line, column) triples.
2	Copyright (C) 2001-2024 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 line_maps *, const line_map_ordinary *);
30	static const line_map_ordinary * linemap_ordinary_map_lookup (const line_maps *,
31	location_t);
32	static const line_map_macro* linemap_macro_map_lookup (const line_maps *,
33	location_t);
34	static location_t linemap_macro_map_loc_to_def_point
35	(const line_map_macro *, location_t);
36	static location_t linemap_macro_map_loc_to_exp_point
37	(const line_map_macro *, location_t);
38	static location_t linemap_macro_loc_to_spelling_point
39	(const line_maps *, location_t, const line_map_ordinary **);
40	static location_t linemap_macro_loc_to_def_point (const line_maps *,
41	location_t,
42	const line_map_ordinary **);
43	static location_t linemap_macro_loc_to_exp_point (const line_maps *,
44	location_t,
45	const line_map_ordinary **);
46
47	/* Counters defined in macro.cc. */
48	extern unsigned num_expanded_macros_counter;
49	extern unsigned num_macro_tokens_counter;
50
51	/* Destructor for class line_maps.
52	Ensure non-GC-managed memory is released. */
53
54	line_maps::~line_maps ()
55	{
56	if (m_location_adhoc_data_map.htab)
57	htab_delete (m_location_adhoc_data_map.htab);
58	}
59
60	/* Hash function for location_adhoc_data hashtable. */
61
62	static hashval_t
63	location_adhoc_data_hash (const void *l)
64	{
65	const struct location_adhoc_data *lb =
66	(const struct location_adhoc_data *) l;
67	return ((hashval_t) lb->locus
68	+ (hashval_t) lb->src_range.m_start
69	+ (hashval_t) lb->src_range.m_finish
70	+ (size_t) lb->data
71	+ lb->discriminator);
72	}
73
74	/* Compare function for location_adhoc_data hashtable. */
75
76	static int
77	location_adhoc_data_eq (const void *l1, const void *l2)
78	{
79	const struct location_adhoc_data *lb1 =
80	(const struct location_adhoc_data *) l1;
81	const struct location_adhoc_data *lb2 =
82	(const struct location_adhoc_data *) l2;
83	return (lb1->locus == lb2->locus
84	&& lb1->src_range.m_start == lb2->src_range.m_start
85	&& lb1->src_range.m_finish == lb2->src_range.m_finish
86	&& lb1->data == lb2->data
87	&& lb1->discriminator == lb2->discriminator);
88	}
89
90	/* Update the hashtable when location_adhoc_data_map::data is reallocated.
91	The param is an array of two pointers, the previous value of the data
92	pointer, and then the new value. The pointers stored in the hash map
93	are then rebased to be relative to the new data pointer instead of the
94	old one. */
95
96	static int
97	location_adhoc_data_update (void **slot_v, void *param_v)
98	{
99	const auto slot = reinterpret_cast<location_adhoc_data **> (slot_v);
100	const auto param = static_cast<location_adhoc_data **> (param_v);
101	*slot = (*slot - param[0]) + param[1];
102	return 1;
103	}
104
105	/* The adhoc data hash table is not part of the GGC infrastructure, so it was
106	not initialized when SET was reconstructed from PCH; take care of that by
107	rebuilding it from scratch. */
108
109	void
110	rebuild_location_adhoc_htab (line_maps *set)
111	{
112	set->m_location_adhoc_data_map.htab =
113	htab_create (100, location_adhoc_data_hash, location_adhoc_data_eq, NULL);
114	for (auto p = set->m_location_adhoc_data_map.data,
115	end = p + set->m_location_adhoc_data_map.curr_loc;
116	p != end; ++p)
117	{
118	const auto slot = reinterpret_cast<location_adhoc_data **>
119	(htab_find_slot (set->m_location_adhoc_data_map.htab, p, INSERT));
120	*slot = p;
121	}
122	}
123
124	/* Helper function for get_combined_adhoc_loc.
125	Can the given LOCUS + SRC_RANGE and DATA pointer be stored compactly
126	within a location_t, without needing to use an ad-hoc location. */
127
128	bool
129	line_maps::can_be_stored_compactly_p (location_t locus,
130	source_range src_range,
131	void *data,
132	unsigned discriminator) const
133	{
134	/* If there's an ad-hoc pointer, we can't store it directly in the
135	location_t, we need the lookaside. */
136	if (data)
137	return false;
138
139	if (discriminator != 0)
140	return false;
141
142	/* We only store ranges that begin at the locus and that are sufficiently
143	"sane". */
144	if (src_range.m_start != locus)
145	return false;
146
147	if (src_range.m_finish < src_range.m_start)
148	return false;
149
150	if (src_range.m_start < RESERVED_LOCATION_COUNT)
151	return false;
152
153	if (locus >= LINE_MAP_MAX_LOCATION_WITH_PACKED_RANGES)
154	return false;
155
156	/* All 3 locations must be within ordinary maps, typically, the same
157	ordinary map. */
158	location_t lowest_macro_loc = LINEMAPS_MACRO_LOWEST_LOCATION (set: this);
159	if (locus >= lowest_macro_loc)
160	return false;
161	if (src_range.m_start >= lowest_macro_loc)
162	return false;
163	if (src_range.m_finish >= lowest_macro_loc)
164	return false;
165
166	/* Passed all tests. */
167	return true;
168	}
169
170	/* Combine LOCUS and DATA to a combined adhoc loc. */
171
172	location_t
173	line_maps::get_or_create_combined_loc (location_t locus,
174	source_range src_range,
175	void *data,
176	unsigned discriminator)
177	{
178	struct location_adhoc_data lb;
179	struct location_adhoc_data **slot;
180
181	if (IS_ADHOC_LOC (loc: locus))
182	locus = get_location_from_adhoc_loc (this, locus);
183	if (locus == 0 && data == NULL)
184	return 0;
185
186	/* Any ordinary locations ought to be "pure" at this point: no
187	compressed ranges. */
188	linemap_assert (locus < RESERVED_LOCATION_COUNT
189	|| locus >= LINE_MAP_MAX_LOCATION_WITH_PACKED_RANGES
190	|| locus >= LINEMAPS_MACRO_LOWEST_LOCATION (this)
191	|| pure_location_p (locus));
192
193	/* Consider short-range optimization. */
194	if (can_be_stored_compactly_p (locus, src_range, data, discriminator))
195	{
196	/* The low bits ought to be clear. */
197	linemap_assert (pure_location_p (locus));
198	const line_map *map = linemap_lookup (this, locus);
199	const line_map_ordinary *ordmap = linemap_check_ordinary (map);
200	unsigned int int_diff = src_range.m_finish - src_range.m_start;
201	unsigned int col_diff = (int_diff >> ordmap->m_range_bits);
202	if (col_diff < (1U << ordmap->m_range_bits))
203	{
204	location_t packed = locus | col_diff;
205	m_num_optimized_ranges++;
206	return packed;
207	}
208	}
209
210	/* We can also compactly store locations
211	when locus == start == finish (and data is NULL). */
212	if (locus == src_range.m_start
213	&& locus == src_range.m_finish
214	&& !data && discriminator == 0)
215	return locus;
216
217	if (!data && discriminator == 0)
218	m_num_unoptimized_ranges++;
219
220	lb.locus = locus;
221	lb.src_range = src_range;
222	lb.data = data;
223	lb.discriminator = discriminator;
224	slot = (struct location_adhoc_data **)
225	htab_find_slot (m_location_adhoc_data_map.htab, &lb, INSERT);
226	if (*slot == NULL)
227	{
228	if (m_location_adhoc_data_map.curr_loc >=
229	m_location_adhoc_data_map.allocated)
230	{
231	const auto orig_data = m_location_adhoc_data_map.data;
232	/* Cast away extern "C" from the type of xrealloc. */
233	line_map_realloc reallocator = (m_reallocator
234	? m_reallocator
235	: (line_map_realloc) xrealloc);
236
237	if (m_location_adhoc_data_map.allocated == 0)
238	m_location_adhoc_data_map.allocated = 128;
239	else
240	m_location_adhoc_data_map.allocated *= 2;
241	m_location_adhoc_data_map.data = (struct location_adhoc_data *)
242	reallocator (m_location_adhoc_data_map.data,
243	m_location_adhoc_data_map.allocated
244	* sizeof (struct location_adhoc_data));
245	if (m_location_adhoc_data_map.allocated > 128)
246	{
247	location_adhoc_data *param[2]
248	= {orig_data, m_location_adhoc_data_map.data};
249	htab_traverse (m_location_adhoc_data_map.htab,
250	location_adhoc_data_update, param);
251	}
252	}
253	*slot = m_location_adhoc_data_map.data
254	+ m_location_adhoc_data_map.curr_loc;
255	m_location_adhoc_data_map.data[m_location_adhoc_data_map.curr_loc++]
256	= lb;
257	}
258	return ((*slot) - m_location_adhoc_data_map.data) | 0x80000000;
259	}
260
261	/* Construct a location with caret at CARET, ranging from START to
262	FINISH.
263
264	For example, consider:
265
266	11111111112
267	12345678901234567890
268	522
269	523 return foo + bar;
270	~~~~^~~~~
271	524
272
273	The location's caret is at the "+", line 523 column 15, but starts
274	earlier, at the "f" of "foo" at column 11. The finish is at the "r"
275	of "bar" at column 19. */
276
277	location_t
278	line_maps::make_location (location_t caret, location_t start, location_t finish)
279	{
280	location_t pure_loc = get_pure_location (loc: caret);
281	source_range src_range;
282	src_range.m_start = get_start (loc: start);
283	src_range.m_finish = get_finish (loc: finish);
284	location_t combined_loc = get_or_create_combined_loc (locus: pure_loc,
285	src_range,
286	data: nullptr,
287	discriminator: 0);
288	return combined_loc;
289	}
290
291	/* Return the data for the adhoc loc. */
292
293	void *
294	get_data_from_adhoc_loc (const line_maps *set, location_t loc)
295	{
296	linemap_assert (IS_ADHOC_LOC (loc));
297	return set->m_location_adhoc_data_map.data[loc & MAX_LOCATION_T].data;
298	}
299
300	unsigned
301	get_discriminator_from_adhoc_loc (const line_maps *set, location_t loc)
302	{
303	linemap_assert (IS_ADHOC_LOC (loc));
304	return set->m_location_adhoc_data_map.data[loc & MAX_LOCATION_T].discriminator;
305	}
306
307	/* Return the location for the adhoc loc. */
308
309	location_t
310	get_location_from_adhoc_loc (const line_maps *set, location_t loc)
311	{
312	linemap_assert (IS_ADHOC_LOC (loc));
313	return set->m_location_adhoc_data_map.data[loc & MAX_LOCATION_T].locus;
314	}
315
316	/* Return the source_range for adhoc location LOC. */
317
318	source_range
319	line_maps::get_range_from_adhoc_loc (location_t loc) const
320	{
321	linemap_assert (IS_ADHOC_LOC (loc));
322	return m_location_adhoc_data_map.data[loc & MAX_LOCATION_T].src_range;
323	}
324
325	/* Get the source_range of location LOC, either from the ad-hoc
326	lookaside table, or embedded inside LOC itself. */
327
328	source_range
329	line_maps::get_range_from_loc (location_t loc) const
330	{
331	if (IS_ADHOC_LOC (loc))
332	return get_range_from_adhoc_loc (loc);
333
334	/* For ordinary maps, extract packed range. */
335	if (loc >= RESERVED_LOCATION_COUNT
336	&& loc < LINEMAPS_MACRO_LOWEST_LOCATION (set: this)
337	&& loc <= LINE_MAP_MAX_LOCATION_WITH_PACKED_RANGES)
338	{
339	const line_map *map = linemap_lookup (this, loc);
340	const line_map_ordinary *ordmap = linemap_check_ordinary (map);
341	source_range result;
342	int offset = loc & ((1 << ordmap->m_range_bits) - 1);
343	result.m_start = loc - offset;
344	result.m_finish = result.m_start + (offset << ordmap->m_range_bits);
345	return result;
346	}
347
348	return source_range::from_location (loc);
349	}
350
351	source_range
352	get_range_from_loc (const line_maps *set,
353	location_t loc)
354	{
355	return set->get_range_from_loc (loc);
356	}
357
358	unsigned
359	get_discriminator_from_loc (const line_maps *set,
360	location_t loc)
361	{
362	if (IS_ADHOC_LOC (loc))
363	return get_discriminator_from_adhoc_loc (set, loc);
364	return 0;
365	}
366
367	/* Get whether location LOC is a "pure" location, or
368	whether it is an ad-hoc location, or embeds range information. */
369
370	bool
371	line_maps::pure_location_p (location_t loc) const
372	{
373	if (IS_ADHOC_LOC (loc))
374	return false;
375
376	const line_map *map = linemap_lookup (this, loc);
377	if (map == NULL)
378	return true;
379	const line_map_ordinary *ordmap = linemap_check_ordinary (map);
380
381	if (loc & ((1U << ordmap->m_range_bits) - 1))
382	return false;
383
384	return true;
385	}
386
387	bool
388	pure_location_p (const line_maps *set, location_t loc)
389	{
390	return set->pure_location_p (loc);
391	}
392
393	/* Given location LOC within SET, strip away any packed range information
394	or ad-hoc information. */
395
396	location_t
397	line_maps::get_pure_location (location_t loc) const
398	{
399	if (IS_ADHOC_LOC (loc))
400	loc = get_location_from_adhoc_loc (set: this, loc);
401
402	if (loc >= LINEMAPS_MACRO_LOWEST_LOCATION (set: this))
403	return loc;
404
405	if (loc < RESERVED_LOCATION_COUNT)
406	return loc;
407
408	const line_map *map = linemap_lookup (this, loc);
409	const line_map_ordinary *ordmap = linemap_check_ordinary (map);
410
411	return loc & ~((1 << ordmap->m_range_bits) - 1);
412	}
413
414	location_t
415	get_pure_location (const line_maps *set, location_t loc)
416	{
417	return set->get_pure_location (loc);
418	}
419
420	/* Initialize a line map set. */
421
422	void
423	linemap_init (line_maps *set,
424	location_t builtin_location)
425	{
426	#if __GNUC__ == 4 && __GNUC_MINOR__ == 2 && !defined (__clang__)
427	/* PR33916, needed to fix PR82939. */
428	memset (set, 0, sizeof (line_maps));
429	#else
430	new (set) line_maps();
431	#endif
432	/* Set default reallocator (used for initial alloc too). */
433	set->m_reallocator = xrealloc;
434	set->highest_location = RESERVED_LOCATION_COUNT - 1;
435	set->highest_line = RESERVED_LOCATION_COUNT - 1;
436	set->m_location_adhoc_data_map.htab =
437	htab_create (100, location_adhoc_data_hash, location_adhoc_data_eq, NULL);
438	set->builtin_location = builtin_location;
439	}
440
441	/* Return the ordinary line map from whence MAP was included. Returns
442	NULL if MAP was not an include. */
443
444	const line_map_ordinary *
445	linemap_included_from_linemap (const line_maps *set, const line_map_ordinary *map)
446	{
447	return linemap_ordinary_map_lookup (set, linemap_included_from (ord_map: map));
448	}
449
450	/* Check for and warn about line_maps entered but not exited. */
451
452	void
453	linemap_check_files_exited (const line_maps *set)
454	{
455	/* Depending upon whether we are handling preprocessed input or
456	not, this can be a user error or an ICE. */
457	for (const line_map_ordinary *map = LINEMAPS_LAST_ORDINARY_MAP (set);
458	! MAIN_FILE_P (ord_map: map);
459	map = linemap_included_from_linemap (set, map))
460	fprintf (stderr, format: "line-map.cc: file \"%s\" entered but not left\n",
461	ORDINARY_MAP_FILE_NAME (ord_map: map));
462	}
463
464	/* Create NUM zero-initialized maps of type MACRO_P. */
465
466	line_map *
467	line_map_new_raw (line_maps *set, bool macro_p, unsigned num)
468	{
469	unsigned num_maps_allocated = LINEMAPS_ALLOCATED (set, map_kind: macro_p);
470	unsigned num_maps_used = LINEMAPS_USED (set, map_kind: macro_p);
471
472	if (num > num_maps_allocated - num_maps_used)
473	{
474	/* We need more space! */
475	if (!num_maps_allocated)
476	num_maps_allocated = 128;
477	if (num_maps_allocated < num_maps_used + num)
478	num_maps_allocated = num_maps_used + num;
479	num_maps_allocated *= 2;
480
481	size_t size_of_a_map;
482	void *buffer;
483	if (macro_p)
484	{
485	size_of_a_map = sizeof (line_map_macro);
486	buffer = set->info_macro.maps;
487	}
488	else
489	{
490	size_of_a_map = sizeof (line_map_ordinary);
491	buffer = set->info_ordinary.maps;
492	}
493
494	/* We are going to execute some dance to try to reduce the
495	overhead of the memory allocator, in case we are using the
496	ggc-page.cc one.
497
498	The actual size of memory we are going to get back from the
499	allocator may well be larger than what we ask for. Use this
500	hook to find what that size is. */
501	size_t alloc_size
502	= set->m_round_alloc_size (num_maps_allocated * size_of_a_map);
503
504	/* Now alloc_size contains the exact memory size we would get if
505	we have asked for the initial alloc_size amount of memory.
506	Let's get back to the number of map that amounts to. */
507	unsigned num_maps = alloc_size / size_of_a_map;
508	buffer = set->m_reallocator (buffer, num_maps * size_of_a_map);
509	memset (s: (char *)buffer + num_maps_used * size_of_a_map, c: 0,
510	n: (num_maps - num_maps_used) * size_of_a_map);
511	if (macro_p)
512	set->info_macro.maps = (line_map_macro *)buffer;
513	else
514	set->info_ordinary.maps = (line_map_ordinary *)buffer;
515	LINEMAPS_ALLOCATED (set, map_kind: macro_p) = num_maps;
516	}
517
518	line_map *result = (macro_p ? (line_map *)&set->info_macro.maps[num_maps_used]
519	: (line_map *)&set->info_ordinary.maps[num_maps_used]);
520	LINEMAPS_USED (set, map_kind: macro_p) += num;
521
522	return result;
523	}
524
525	/* Create a new line map in the line map set SET, and return it.
526	REASON is the reason of creating the map. It determines the type
527	of map created (ordinary or macro map). Note that ordinary maps and
528	macro maps are allocated in different memory location. */
529
530	static struct line_map *
531	new_linemap (line_maps *set, location_t start_location)
532	{
533	line_map *result = line_map_new_raw (set,
534	macro_p: start_location >= LINE_MAP_MAX_LOCATION,
535	num: 1);
536
537	result->start_location = start_location;
538
539	return result;
540	}
541
542	/* Return the location of the last source line within an ordinary
543	map. */
544	inline location_t
545	LAST_SOURCE_LINE_LOCATION (const line_map_ordinary *map)
546	{
547	return (((map[1].start_location - 1
548	- map->start_location)
549	& ~((1 << map->m_column_and_range_bits) - 1))
550	+ map->start_location);
551	}
552
553	/* Add a mapping of logical source line to physical source file and
554	line number.
555
556	The text pointed to by TO_FILE must have a lifetime
557	at least as long as the final call to lookup_line (). An empty
558	TO_FILE means standard input. If reason is LC_LEAVE, and
559	TO_FILE is NULL, then TO_FILE, TO_LINE and SYSP are given their
560	natural values considering the file we are returning to.
561
562	FROM_LINE should be monotonic increasing across calls to this
563	function. A call to this function can relocate the previous set of
564	maps, so any stored line_map pointers should not be used. */
565
566	const struct line_map *
567	linemap_add (line_maps *set, enum lc_reason reason,
568	unsigned int sysp, const char *to_file, linenum_type to_line)
569	{
570	/* Generate a start_location above the current highest_location.
571	If possible, make the low range bits be zero. */
572	location_t start_location = set->highest_location + 1;
573	unsigned range_bits = 0;
574	if (start_location < LINE_MAP_MAX_LOCATION_WITH_COLS)
575	range_bits = set->default_range_bits;
576	start_location += (1 << range_bits) - 1;
577	start_location &= ~((1 << range_bits) - 1);
578
579	linemap_assert (!LINEMAPS_ORDINARY_USED (set)
580	|| (start_location
581	>= MAP_START_LOCATION (LINEMAPS_LAST_ORDINARY_MAP (set))));
582
583	/* When we enter the file for the first time reason cannot be
584	LC_RENAME. */
585	linemap_assert (!(set->depth == 0 && reason == LC_RENAME));
586
587	/* If we are leaving the main file, return a NULL map. */
588	if (reason == LC_LEAVE
589	&& MAIN_FILE_P (ord_map: LINEMAPS_LAST_ORDINARY_MAP (set))
590	&& to_file == NULL)
591	{
592	set->depth--;
593	return NULL;
594	}
595
596	linemap_assert (reason != LC_ENTER_MACRO);
597
598	if (start_location >= LINE_MAP_MAX_LOCATION)
599	/* We ran out of line map space. */
600	start_location = 0;
601
602	line_map_ordinary *map
603	= linemap_check_ordinary (map: new_linemap (set, start_location));
604	map->reason = reason;
605
606	if (to_file && *to_file == '\0' && reason != LC_RENAME_VERBATIM)
607	to_file = "<stdin>";
608
609	if (reason == LC_RENAME_VERBATIM)
610	reason = LC_RENAME;
611
612	const line_map_ordinary *from = NULL;
613	if (reason == LC_LEAVE)
614	{
615	/* When we are just leaving an "included" file, and jump to the next
616	location inside the "includer" right after the #include
617	"included", this variable points the map in use right before the
618	#include "included", inside the same "includer" file. */
619
620	linemap_assert (!MAIN_FILE_P (map - 1));
621	/* (MAP - 1) points to the map we are leaving. The
622	map from which (MAP - 1) got included should be the map
623	that comes right before MAP in the same file. */
624	from = linemap_included_from_linemap (set, map: map - 1);
625
626	/* A TO_FILE of NULL is special - we use the natural values. */
627	if (to_file == NULL)
628	{
629	to_file = ORDINARY_MAP_FILE_NAME (ord_map: from);
630	to_line = SOURCE_LINE (ord_map: from, loc: from[1].start_location);
631	sysp = ORDINARY_MAP_IN_SYSTEM_HEADER_P (ord_map: from);
632	}
633	else
634	linemap_assert (filename_cmp (ORDINARY_MAP_FILE_NAME (from),
635	to_file) == 0);
636	}
637
638	map->sysp = sysp;
639	map->to_file = to_file;
640	map->to_line = to_line;
641	set->info_ordinary.m_cache = LINEMAPS_ORDINARY_USED (set) - 1;
642	/* Do not store range_bits here. That's readjusted in
643	linemap_line_start. */
644	map->m_range_bits = map->m_column_and_range_bits = 0;
645	set->highest_location = start_location;
646	set->highest_line = start_location;
647	set->max_column_hint = 0;
648
649	/* This assertion is placed after set->highest_location has
650	been updated, since the latter affects
651	linemap_location_from_macro_expansion_p, which ultimately affects
652	pure_location_p. */
653	linemap_assert (pure_location_p (set, start_location));
654
655	if (reason == LC_ENTER)
656	{
657	if (set->depth == 0)
658	map->included_from = 0;
659	else
660	/* The location of the end of the just-closed map. */
661	map->included_from
662	= (((map[0].start_location - 1 - map[-1].start_location)
663	& ~((1 << map[-1].m_column_and_range_bits) - 1))
664	+ map[-1].start_location);
665	set->depth++;
666	if (set->trace_includes)
667	trace_include (set, map);
668	}
669	else if (reason == LC_RENAME)
670	map->included_from = linemap_included_from (ord_map: &map[-1]);
671	else if (reason == LC_LEAVE)
672	{
673	set->depth--;
674	map->included_from = linemap_included_from (ord_map: from);
675	}
676
677	return map;
678	}
679
680	/* Create a location for a module NAME imported at FROM. */
681
682	location_t
683	linemap_module_loc (line_maps *set, location_t from, const char *name)
684	{
685	const line_map_ordinary *map
686	= linemap_check_ordinary (map: linemap_add (set, reason: LC_MODULE, sysp: false, to_file: name, to_line: 0));
687	const_cast <line_map_ordinary *> (map)->included_from = from;
688
689	location_t loc = linemap_line_start (set, to_line: 0, max_column_hint: 0);
690
691	return loc;
692	}
693
694	/* The linemap containing LOC is being reparented to be
695	imported/included from ADOPTOR. This can happen when an
696	indirectly imported module is then directly imported, or when
697	partitions are involved. */
698
699	void
700	linemap_module_reparent (line_maps *set, location_t loc, location_t adoptor)
701	{
702	const line_map_ordinary *map = linemap_ordinary_map_lookup (set, loc);
703	const_cast<line_map_ordinary *> (map)->included_from = adoptor;
704	}
705
706	/* A linemap at LWM-1 was interrupted to insert module locations & imports.
707	Append a new map, continuing the interrupted one. Return the start location
708	of the new map, or 0 if failed (because we ran out of locations. */
709
710	unsigned
711	linemap_module_restore (line_maps *set, unsigned lwm)
712	{
713	linemap_assert (lwm);
714
715	const line_map_ordinary *pre_map
716	= linemap_check_ordinary (map: LINEMAPS_MAP_AT (set, map_kind: false, index: lwm - 1));
717	unsigned src_line = SOURCE_LINE (ord_map: pre_map, loc: LAST_SOURCE_LINE_LOCATION (map: pre_map));
718	location_t inc_at = pre_map->included_from;
719	if (const line_map_ordinary *post_map
720	= (linemap_check_ordinary
721	(map: linemap_add (set, reason: LC_RENAME_VERBATIM,
722	sysp: ORDINARY_MAP_IN_SYSTEM_HEADER_P (ord_map: pre_map),
723	to_file: ORDINARY_MAP_FILE_NAME (ord_map: pre_map), to_line: src_line))))
724	{
725	/* linemap_add will think we were included from the same as the preceeding
726	map. */
727	const_cast <line_map_ordinary *> (post_map)->included_from = inc_at;
728
729	return post_map->start_location;
730	}
731
732	return 0;
733	}
734
735	/* Returns TRUE if the line table set tracks token locations across
736	macro expansion, FALSE otherwise. */
737
738	bool
739	linemap_tracks_macro_expansion_locs_p (const line_maps *set)
740	{
741	return set->info_macro.maps != nullptr;
742	}
743
744	/* Create a macro map. A macro map encodes source locations of tokens
745	that are part of a macro replacement-list, at a macro expansion
746	point. See the extensive comments of struct line_map and struct
747	line_map_macro, in line-map.h.
748
749	This map shall be created when the macro is expanded. The map
750	encodes the source location of the expansion point of the macro as
751	well as the "original" source location of each token that is part
752	of the macro replacement-list. If a macro is defined but never
753	expanded, it has no macro map. SET is the set of maps the macro
754	map should be part of. MACRO_NODE is the macro which the new macro
755	map should encode source locations for. EXPANSION is the location
756	of the expansion point of MACRO. For function-like macros
757	invocations, it's best to make it point to the closing parenthesis
758	of the macro, rather than the the location of the first character
759	of the macro. NUM_TOKENS is the number of tokens that are part of
760	the replacement-list of MACRO.
761
762	Note that when we run out of the integer space available for source
763	locations, this function returns NULL. In that case, callers of
764	this function cannot encode {line,column} pairs into locations of
765	macro tokens anymore. */
766
767	const line_map_macro *
768	linemap_enter_macro (class line_maps *set, struct cpp_hashnode *macro_node,
769	location_t expansion, unsigned int num_tokens)
770	{
771	location_t start_location
772	= LINEMAPS_MACRO_LOWEST_LOCATION (set) - num_tokens;
773
774	if (start_location < LINE_MAP_MAX_LOCATION)
775	/* We ran out of macro map space. */
776	return NULL;
777
778	line_map_macro *map = linemap_check_macro (map: new_linemap (set, start_location));
779
780	map->macro = macro_node;
781	map->n_tokens = num_tokens;
782	map->macro_locations
783	= (location_t*) set->m_reallocator (nullptr,
784	2 * num_tokens * sizeof (location_t));
785	map->m_expansion = expansion;
786	memset (s: MACRO_MAP_LOCATIONS (macro_map: map), c: 0,
787	n: 2 * num_tokens * sizeof (location_t));
788
789	set->info_macro.m_cache = LINEMAPS_MACRO_USED (set) - 1;
790
791	return map;
792	}
793
794	/* Create and return a virtual location for a token that is part of a
795	macro expansion-list at a macro expansion point. See the comment
796	inside struct line_map_macro to see what an expansion-list exactly
797	is.
798
799	A call to this function must come after a call to
800	linemap_enter_macro.
801
802	MAP is the map into which the source location is created. TOKEN_NO
803	is the index of the token in the macro replacement-list, starting
804	at number 0.
805
806	ORIG_LOC is the location of the token outside of this macro
807	expansion. If the token comes originally from the macro
808	definition, it is the locus in the macro definition; otherwise it
809	is a location in the context of the caller of this macro expansion
810	(which is a virtual location or a source location if the caller is
811	itself a macro expansion or not).
812
813	ORIG_PARM_REPLACEMENT_LOC is the location in the macro definition,
814	either of the token itself or of a macro parameter that it
815	replaces. */
816
817	location_t
818	linemap_add_macro_token (const line_map_macro *map,
819	unsigned int token_no,
820	location_t orig_loc,
821	location_t orig_parm_replacement_loc)
822	{
823	location_t result;
824
825	linemap_assert (linemap_macro_expansion_map_p (map));
826	linemap_assert (token_no < MACRO_MAP_NUM_MACRO_TOKENS (map));
827
828	MACRO_MAP_LOCATIONS (macro_map: map)[2 * token_no] = orig_loc;
829	MACRO_MAP_LOCATIONS (macro_map: map)[2 * token_no + 1] = orig_parm_replacement_loc;
830
831	result = MAP_START_LOCATION (map) + token_no;
832	return result;
833	}
834
835	/* Return a location_t for the start (i.e. column==0) of
836	(physical) line TO_LINE in the current source file (as in the
837	most recent linemap_add). MAX_COLUMN_HINT is the highest column
838	number we expect to use in this line (but it does not change
839	the highest_location). */
840
841	location_t
842	linemap_line_start (line_maps *set, linenum_type to_line,
843	unsigned int max_column_hint)
844	{
845	line_map_ordinary *map = LINEMAPS_LAST_ORDINARY_MAP (set);
846	location_t highest = set->highest_location;
847	location_t r;
848	linenum_type last_line =
849	SOURCE_LINE (ord_map: map, loc: set->highest_line);
850	int line_delta = to_line - last_line;
851	bool add_map = false;
852	linemap_assert (map->m_column_and_range_bits >= map->m_range_bits);
853	int effective_column_bits = map->m_column_and_range_bits - map->m_range_bits;
854
855	if (line_delta < 0
856	|| (line_delta > 10
857	&& line_delta * map->m_column_and_range_bits > 1000)
858	|| (max_column_hint >= (1U << effective_column_bits))
859	|| (max_column_hint <= 80 && effective_column_bits >= 10)
860	|| (highest > LINE_MAP_MAX_LOCATION_WITH_PACKED_RANGES
861	&& map->m_range_bits > 0)
862	|| (highest > LINE_MAP_MAX_LOCATION_WITH_COLS
863	&& (set->max_column_hint || highest >= LINE_MAP_MAX_LOCATION)))
864	add_map = true;
865	else
866	max_column_hint = set->max_column_hint;
867	if (add_map)
868	{
869	int column_bits;
870	int range_bits;
871	if (max_column_hint > LINE_MAP_MAX_COLUMN_NUMBER
872	|| highest > LINE_MAP_MAX_LOCATION_WITH_COLS)
873	{
874	/* If the column number is ridiculous or we've allocated a huge
875	number of location_ts, give up on column numbers
876	(and on packed ranges). */
877	max_column_hint = 1;
878	column_bits = 0;
879	range_bits = 0;
880	if (highest >= LINE_MAP_MAX_LOCATION)
881	goto overflowed;
882	}
883	else
884	{
885	column_bits = 7;
886	if (highest <= LINE_MAP_MAX_LOCATION_WITH_PACKED_RANGES)
887	range_bits = set->default_range_bits;
888	else
889	range_bits = 0;
890	while (max_column_hint >= (1U << column_bits))
891	column_bits++;
892	max_column_hint = 1U << column_bits;
893	column_bits += range_bits;
894	}
895
896	/* Allocate the new line_map. However, if the current map only has a
897	single line we can sometimes just increase its column_bits instead. */
898	if (line_delta < 0
899	|| last_line != ORDINARY_MAP_STARTING_LINE_NUMBER (ord_map: map)
900	|| SOURCE_COLUMN (ord_map: map, loc: highest) >= (1U << (column_bits - range_bits))
901	|| ( /* We can't reuse the map if the line offset is sufficiently
902	large to cause overflow when computing location_t values. */
903	(to_line - ORDINARY_MAP_STARTING_LINE_NUMBER (ord_map: map))
904	>= (((uint64_t) 1)
905	<< (CHAR_BIT * sizeof (linenum_type) - column_bits)))
906	|| range_bits < map->m_range_bits)
907	map = linemap_check_ordinary
908	(map: const_cast <line_map *>
909	(linemap_add (set, reason: LC_RENAME,
910	sysp: ORDINARY_MAP_IN_SYSTEM_HEADER_P (ord_map: map),
911	to_file: ORDINARY_MAP_FILE_NAME (ord_map: map),
912	to_line)));
913	map->m_column_and_range_bits = column_bits;
914	map->m_range_bits = range_bits;
915	r = (MAP_START_LOCATION (map)
916	+ ((to_line - ORDINARY_MAP_STARTING_LINE_NUMBER (ord_map: map))
917	<< column_bits));
918	}
919	else
920	r = set->highest_line + (line_delta << map->m_column_and_range_bits);
921
922	/* Locations of ordinary tokens are always lower than locations of
923	macro tokens. */
924	if (r >= LINE_MAP_MAX_LOCATION)
925	{
926	overflowed:
927	/* Remember we overflowed. */
928	set->highest_line = set->highest_location = LINE_MAP_MAX_LOCATION - 1;
929	/* No column numbers! */
930	set->max_column_hint = 1;
931	return 0;
932	}
933
934	set->highest_line = r;
935	if (r > set->highest_location)
936	set->highest_location = r;
937	set->max_column_hint = max_column_hint;
938
939	/* At this point, we expect one of:
940	(a) the normal case: a "pure" location with 0 range bits, or
941	(b) we've gone past LINE_MAP_MAX_LOCATION_WITH_COLS so can't track
942	columns anymore (or ranges), or
943	(c) we're in a region with a column hint exceeding
944	LINE_MAP_MAX_COLUMN_NUMBER, so column-tracking is off,
945	with column_bits == 0. */
946	linemap_assert (pure_location_p (set, r)
947	|| r >= LINE_MAP_MAX_LOCATION_WITH_COLS
948	|| map->m_column_and_range_bits == 0);
949	linemap_assert (SOURCE_LINE (map, r) == to_line);
950	return r;
951	}
952
953	/* Encode and return a location_t from a column number. The
954	source line considered is the last source line used to call
955	linemap_line_start, i.e, the last source line which a location was
956	encoded from. */
957
958	location_t
959	linemap_position_for_column (line_maps *set, unsigned int to_column)
960	{
961	location_t r = set->highest_line;
962
963	linemap_assert
964	(!linemap_macro_expansion_map_p (LINEMAPS_LAST_ORDINARY_MAP (set)));
965
966	if (to_column >= set->max_column_hint)
967	{
968	if (r > LINE_MAP_MAX_LOCATION_WITH_COLS
969	|| to_column > LINE_MAP_MAX_COLUMN_NUMBER)
970	{
971	/* Running low on location_ts - disable column numbers. */
972	return r;
973	}
974	else
975	{
976	/* Otherwise, attempt to start a new line that can hold TO_COLUMN,
977	with some space to spare. This may or may not lead to a new
978	linemap being created. */
979	line_map_ordinary *map = LINEMAPS_LAST_ORDINARY_MAP (set);
980	r = linemap_line_start (set, to_line: SOURCE_LINE (ord_map: map, loc: r), max_column_hint: to_column + 50);
981	map = LINEMAPS_LAST_ORDINARY_MAP (set);
982	if (map->m_column_and_range_bits == 0)
983	{
984	/* ...then the linemap has column-tracking disabled,
985	presumably due to exceeding either
986	LINE_MAP_MAX_LOCATION_WITH_COLS (overall) or
987	LINE_MAP_MAX_COLUMN_NUMBER (within this line).
988	Return the start of the linemap, which encodes column 0, for
989	the whole line. */
990	return r;
991	}
992	}
993	}
994	line_map_ordinary *map = LINEMAPS_LAST_ORDINARY_MAP (set);
995	r = r + (to_column << map->m_range_bits);
996	if (r >= set->highest_location)
997	set->highest_location = r;
998	return r;
999	}
1000
1001	/* Encode and return a source location from a given line and
1002	column. */
1003
1004	location_t
1005	linemap_position_for_line_and_column (line_maps *set,
1006	const line_map_ordinary *ord_map,
1007	linenum_type line,
1008	unsigned column)
1009	{
1010	linemap_assert (ORDINARY_MAP_STARTING_LINE_NUMBER (ord_map) <= line);
1011
1012	location_t r = MAP_START_LOCATION (map: ord_map);
1013	r += ((line - ORDINARY_MAP_STARTING_LINE_NUMBER (ord_map))
1014	<< ord_map->m_column_and_range_bits);
1015	if (r <= LINE_MAP_MAX_LOCATION_WITH_COLS)
1016	r += ((column & ((1 << ord_map->m_column_and_range_bits) - 1))
1017	<< ord_map->m_range_bits);
1018	location_t upper_limit = LINEMAPS_MACRO_LOWEST_LOCATION (set);
1019	if (r >= upper_limit)
1020	r = upper_limit - 1;
1021	if (r > set->highest_location)
1022	set->highest_location = r;
1023	return r;
1024	}
1025
1026	/* Encode and return a location_t starting from location LOC and
1027	shifting it by COLUMN_OFFSET columns. This function does not support
1028	virtual locations. */
1029
1030	location_t
1031	linemap_position_for_loc_and_offset (line_maps *set,
1032	location_t loc,
1033	unsigned int column_offset)
1034	{
1035	const line_map_ordinary * map = NULL;
1036
1037	if (IS_ADHOC_LOC (loc))
1038	loc = get_location_from_adhoc_loc (set, loc);
1039
1040	/* This function does not support virtual locations yet. */
1041	if (linemap_location_from_macro_expansion_p (set, loc))
1042	return loc;
1043
1044	if (column_offset == 0
1045	/* Adding an offset to a reserved location (like
1046	UNKNOWN_LOCATION for the C/C++ FEs) does not really make
1047	sense. So let's leave the location intact in that case. */
1048	|| loc < RESERVED_LOCATION_COUNT)
1049	return loc;
1050
1051	/* We find the real location and shift it. */
1052	loc = linemap_resolve_location (set, loc, lrk: LRK_SPELLING_LOCATION, loc_map: &map);
1053	/* The new location (loc + offset) should be higher than the first
1054	location encoded by MAP. This can fail if the line information
1055	is messed up because of line directives (see PR66415). */
1056	if (MAP_START_LOCATION (map) >= loc + (column_offset << map->m_range_bits))
1057	return loc;
1058
1059	linenum_type line = SOURCE_LINE (ord_map: map, loc);
1060	unsigned int column = SOURCE_COLUMN (ord_map: map, loc);
1061
1062	/* If MAP is not the last line map of its set, then the new location
1063	(loc + offset) should be less than the first location encoded by
1064	the next line map of the set. Otherwise, we try to encode the
1065	location in the next map. */
1066	for (; map != LINEMAPS_LAST_ORDINARY_MAP (set)
1067	&& (loc + (column_offset << map->m_range_bits)
1068	>= MAP_START_LOCATION (map: map + 1)); map++)
1069	/* If the next map is a different file, or starts in a higher line, we
1070	cannot encode the location there. */
1071	if ((map + 1)->reason != LC_RENAME
1072	|| line < ORDINARY_MAP_STARTING_LINE_NUMBER (ord_map: map + 1)
1073	|| 0 != strcmp (s1: LINEMAP_FILE (ord_map: map + 1), s2: LINEMAP_FILE (ord_map: map)))
1074	return loc;
1075
1076	column += column_offset;
1077
1078	/* Bail out if the column is not representable within the existing
1079	linemap. */
1080	if (column >= (1u << (map->m_column_and_range_bits - map->m_range_bits)))
1081	return loc;
1082
1083	location_t r =
1084	linemap_position_for_line_and_column (set, ord_map: map, line, column);
1085	if (linemap_assert_fails (r <= set->highest_location)
1086	|| linemap_assert_fails (map == linemap_lookup (set, r)))
1087	return loc;
1088
1089	return r;
1090	}
1091
1092	/* Given a virtual source location yielded by a map (either an
1093	ordinary or a macro map), returns that map. */
1094
1095	const struct line_map*
1096	linemap_lookup (const line_maps *set, location_t line)
1097	{
1098	if (IS_ADHOC_LOC (loc: line))
1099	line = get_location_from_adhoc_loc (set, loc: line);
1100	if (linemap_location_from_macro_expansion_p (set, line))
1101	return linemap_macro_map_lookup (set, line);
1102	return linemap_ordinary_map_lookup (set, line);
1103	}
1104
1105	/* Given a source location yielded by an ordinary map, returns that
1106	map. Since the set is built chronologically, the logical lines are
1107	monotonic increasing, and so the list is sorted and we can use a
1108	binary search. */
1109
1110	static const line_map_ordinary *
1111	linemap_ordinary_map_lookup (const line_maps *set, location_t line)
1112	{
1113	if (IS_ADHOC_LOC (loc: line))
1114	line = get_location_from_adhoc_loc (set, loc: line);
1115
1116	if (set == NULL || line < RESERVED_LOCATION_COUNT)
1117	return NULL;
1118
1119	unsigned mn = set->info_ordinary.m_cache;
1120	unsigned mx = LINEMAPS_ORDINARY_USED (set);
1121
1122	const line_map_ordinary *cached = LINEMAPS_ORDINARY_MAP_AT (set, index: mn);
1123	/* We should get a segfault if no line_maps have been added yet. */
1124	if (line >= MAP_START_LOCATION (map: cached))
1125	{
1126	if (mn + 1 == mx || line < MAP_START_LOCATION (map: &cached[1]))
1127	return cached;
1128	}
1129	else
1130	{
1131	mx = mn;
1132	mn = 0;
1133	}
1134
1135	while (mx - mn > 1)
1136	{
1137	unsigned md = (mn + mx) / 2;
1138	if (MAP_START_LOCATION (map: LINEMAPS_ORDINARY_MAP_AT (set, index: md)) > line)
1139	mx = md;
1140	else
1141	mn = md;
1142	}
1143
1144	set->info_ordinary.m_cache = mn;
1145	const line_map_ordinary *result = LINEMAPS_ORDINARY_MAP_AT (set, index: mn);
1146	linemap_assert (line >= MAP_START_LOCATION (result));
1147	return result;
1148	}
1149
1150	/* Given a source location yielded by a macro map, returns that map.
1151	Since the set is built chronologically, the logical lines are
1152	monotonic decreasing, and so the list is sorted and we can use a
1153	binary search. */
1154
1155	static const line_map_macro *
1156	linemap_macro_map_lookup (const line_maps *set, location_t line)
1157	{
1158	if (IS_ADHOC_LOC (loc: line))
1159	line = get_location_from_adhoc_loc (set, loc: line);
1160
1161	linemap_assert (line >= LINEMAPS_MACRO_LOWEST_LOCATION (set));
1162
1163	if (set == NULL)
1164	return NULL;
1165
1166	unsigned ix = linemap_lookup_macro_index (set, line);
1167	const struct line_map_macro *result = LINEMAPS_MACRO_MAP_AT (set, index: ix);
1168	linemap_assert (MAP_START_LOCATION (result) <= line);
1169
1170	return result;
1171	}
1172
1173	unsigned
1174	linemap_lookup_macro_index (const line_maps *set, location_t line)
1175	{
1176	unsigned mn = set->info_macro.m_cache;
1177	unsigned mx = LINEMAPS_MACRO_USED (set);
1178	const struct line_map_macro *cached = LINEMAPS_MACRO_MAP_AT (set, index: mn);
1179
1180	if (line >= MAP_START_LOCATION (map: cached))
1181	{
1182	if (line < (MAP_START_LOCATION (map: cached)
1183	+ MACRO_MAP_NUM_MACRO_TOKENS (macro_map: cached)))
1184	return mn;
1185	mx = mn - 1;
1186	mn = 0;
1187	}
1188
1189	while (mn < mx)
1190	{
1191	unsigned md = (mx + mn) / 2;
1192	if (MAP_START_LOCATION (map: LINEMAPS_MACRO_MAP_AT (set, index: md)) > line)
1193	mn = md + 1;
1194	else
1195	mx = md;
1196	}
1197
1198	set->info_macro.m_cache = mx;
1199	return mx;
1200	}
1201
1202	/* Return TRUE if MAP encodes locations coming from a macro
1203	replacement-list at macro expansion point. */
1204
1205	bool
1206	linemap_macro_expansion_map_p (const struct line_map *map)
1207	{
1208	return map && !MAP_ORDINARY_P (map);
1209	}
1210
1211	/* If LOCATION is the locus of a token in a replacement-list of a
1212	macro expansion return the location of the macro expansion point.
1213
1214	Read the comments of struct line_map and struct line_map_macro in
1215	line-map.h to understand what a macro expansion point is. */
1216
1217	static location_t
1218	linemap_macro_map_loc_to_exp_point (const line_map_macro *map,
1219	location_t location ATTRIBUTE_UNUSED)
1220	{
1221	linemap_assert (linemap_macro_expansion_map_p (map)
1222	&& location >= MAP_START_LOCATION (map));
1223
1224	/* Make sure LOCATION is correct. */
1225	linemap_assert ((location - MAP_START_LOCATION (map))
1226	< MACRO_MAP_NUM_MACRO_TOKENS (map));
1227
1228	return map->get_expansion_point_location ();
1229	}
1230
1231	/* LOCATION is the source location of a token that belongs to a macro
1232	replacement-list as part of the macro expansion denoted by MAP.
1233
1234	Return the location of the token at the definition point of the
1235	macro. */
1236
1237	static location_t
1238	linemap_macro_map_loc_to_def_point (const line_map_macro *map,
1239	location_t location)
1240	{
1241	unsigned token_no;
1242
1243	linemap_assert (linemap_macro_expansion_map_p (map)
1244	&& location >= MAP_START_LOCATION (map));
1245	linemap_assert (location >= RESERVED_LOCATION_COUNT);
1246
1247	token_no = location - MAP_START_LOCATION (map);
1248	linemap_assert (token_no < MACRO_MAP_NUM_MACRO_TOKENS (map));
1249
1250	location = MACRO_MAP_LOCATIONS (macro_map: map)[2 * token_no + 1];
1251
1252	return location;
1253	}
1254
1255	/* If LOCATION is the locus of a token that is an argument of a
1256	function-like macro M and appears in the expansion of M, return the
1257	locus of that argument in the context of the caller of M.
1258
1259	In other words, this returns the xI location presented in the
1260	comments of line_map_macro above. */
1261	location_t
1262	linemap_macro_map_loc_unwind_toward_spelling (const line_maps *set,
1263	const line_map_macro* map,
1264	location_t location)
1265	{
1266	unsigned token_no;
1267
1268	if (IS_ADHOC_LOC (loc: location))
1269	location = get_location_from_adhoc_loc (set, loc: location);
1270
1271	linemap_assert (linemap_macro_expansion_map_p (map)
1272	&& location >= MAP_START_LOCATION (map));
1273	linemap_assert (location >= RESERVED_LOCATION_COUNT);
1274	linemap_assert (!IS_ADHOC_LOC (location));
1275
1276	token_no = location - MAP_START_LOCATION (map);
1277	linemap_assert (token_no < MACRO_MAP_NUM_MACRO_TOKENS (map));
1278
1279	location = MACRO_MAP_LOCATIONS (macro_map: map)[2 * token_no];
1280
1281	return location;
1282	}
1283
1284	/* Return the source line number corresponding to source location
1285	LOCATION. SET is the line map set LOCATION comes from. If
1286	LOCATION is the source location of token that is part of the
1287	replacement-list of a macro expansion return the line number of the
1288	macro expansion point. */
1289
1290	int
1291	linemap_get_expansion_line (const line_maps *set,
1292	location_t location)
1293	{
1294	const line_map_ordinary *map = NULL;
1295
1296	if (IS_ADHOC_LOC (loc: location))
1297	location = get_location_from_adhoc_loc (set, loc: location);
1298
1299	if (location < RESERVED_LOCATION_COUNT)
1300	return 0;
1301
1302	location =
1303	linemap_macro_loc_to_exp_point (set, location, &map);
1304
1305	return SOURCE_LINE (ord_map: map, loc: location);
1306	}
1307
1308	/* Return the path of the file corresponding to source code location
1309	LOCATION.
1310
1311	If LOCATION is the source location of token that is part of the
1312	replacement-list of a macro expansion return the file path of the
1313	macro expansion point.
1314
1315	SET is the line map set LOCATION comes from. */
1316
1317	const char*
1318	linemap_get_expansion_filename (const line_maps *set,
1319	location_t location)
1320	{
1321	const struct line_map_ordinary *map = NULL;
1322
1323	if (IS_ADHOC_LOC (loc: location))
1324	location = get_location_from_adhoc_loc (set, loc: location);
1325
1326	if (location < RESERVED_LOCATION_COUNT)
1327	return NULL;
1328
1329	linemap_macro_loc_to_exp_point (set, location, &map);
1330
1331	return LINEMAP_FILE (ord_map: map);
1332	}
1333
1334	/* Return the name of the macro associated to MACRO_MAP. */
1335
1336	const char*
1337	linemap_map_get_macro_name (const line_map_macro *macro_map)
1338	{
1339	linemap_assert (macro_map && linemap_macro_expansion_map_p (macro_map));
1340	return (const char*) NODE_NAME (MACRO_MAP_MACRO (macro_map));
1341	}
1342
1343	/* Return a positive value if LOCATION is the locus of a token that is
1344	located in a system header, O otherwise. It returns 1 if LOCATION
1345	is the locus of a token that is located in a system header, and 2
1346	if LOCATION is the locus of a token located in a C system header
1347	that therefore needs to be extern "C" protected in C++.
1348
1349	Note that this function returns 1 if LOCATION belongs to a token
1350	that is part of a macro replacement-list defined in a system
1351	header, but expanded in a non-system file. */
1352
1353	int
1354	linemap_location_in_system_header_p (const line_maps *set,
1355	location_t location)
1356	{
1357	const struct line_map *map = NULL;
1358
1359	if (IS_ADHOC_LOC (loc: location))
1360	location = get_location_from_adhoc_loc (set, loc: location);
1361
1362	if (location < RESERVED_LOCATION_COUNT)
1363	return false;
1364
1365	/* Let's look at where the token for LOCATION comes from. */
1366	while (true)
1367	{
1368	map = linemap_lookup (set, line: location);
1369	if (map != NULL)
1370	{
1371	if (!linemap_macro_expansion_map_p (map))
1372	/* It's a normal token. */
1373	return LINEMAP_SYSP (ord_map: linemap_check_ordinary (map));
1374	else
1375	{
1376	const line_map_macro *macro_map = linemap_check_macro (map);
1377
1378	/* It's a token resulting from a macro expansion. */
1379	location_t loc =
1380	linemap_macro_map_loc_unwind_toward_spelling (set, map: macro_map, location);
1381	if (loc < RESERVED_LOCATION_COUNT)
1382	/* This token might come from a built-in macro. Let's
1383	look at where that macro got expanded. */
1384	location = linemap_macro_map_loc_to_exp_point (map: macro_map, location);
1385	else
1386	location = loc;
1387	}
1388	}
1389	else
1390	break;
1391	}
1392	return false;
1393	}
1394
1395	/* Return TRUE if LOCATION is a source code location of a token that is part of
1396	a macro expansion, FALSE otherwise. */
1397
1398	bool
1399	linemap_location_from_macro_expansion_p (const class line_maps *set,
1400	location_t location)
1401	{
1402	if (IS_ADHOC_LOC (loc: location))
1403	location = get_location_from_adhoc_loc (set, loc: location);
1404
1405	return location >= LINEMAPS_MACRO_LOWEST_LOCATION (set);
1406	}
1407
1408	/* Given two virtual locations *LOC0 and *LOC1, return the first
1409	common macro map in their macro expansion histories. Return NULL
1410	if no common macro was found. *LOC0 (resp. *LOC1) is set to the
1411	virtual location of the token inside the resulting macro. */
1412
1413	static const struct line_map*
1414	first_map_in_common_1 (const line_maps *set,
1415	location_t *loc0,
1416	location_t *loc1)
1417	{
1418	location_t l0 = *loc0, l1 = *loc1;
1419	const struct line_map *map0 = linemap_lookup (set, line: l0);
1420	if (IS_ADHOC_LOC (loc: l0))
1421	l0 = get_location_from_adhoc_loc (set, loc: l0);
1422
1423	const struct line_map *map1 = linemap_lookup (set, line: l1);
1424	if (IS_ADHOC_LOC (loc: l1))
1425	l1 = get_location_from_adhoc_loc (set, loc: l1);
1426
1427	while (linemap_macro_expansion_map_p (map: map0)
1428	&& linemap_macro_expansion_map_p (map: map1)
1429	&& (map0 != map1))
1430	{
1431	if (MAP_START_LOCATION (map: map0) < MAP_START_LOCATION (map: map1))
1432	{
1433	l0 = linemap_macro_map_loc_to_exp_point (map: linemap_check_macro (map: map0),
1434	location: l0);
1435	map0 = linemap_lookup (set, line: l0);
1436	}
1437	else
1438	{
1439	l1 = linemap_macro_map_loc_to_exp_point (map: linemap_check_macro (map: map1),
1440	location: l1);
1441	map1 = linemap_lookup (set, line: l1);
1442	}
1443	}
1444
1445	if (map0 == map1)
1446	{
1447	*loc0 = l0;
1448	*loc1 = l1;
1449	return map0;
1450	}
1451	return NULL;
1452	}
1453
1454	/* Given two virtual locations LOC0 and LOC1, return the first common
1455	macro map in their macro expansion histories. Return NULL if no
1456	common macro was found. *RES_LOC0 (resp. *RES_LOC1) is set to the
1457	virtual location of the token inside the resulting macro, upon
1458	return of a non-NULL result. */
1459
1460	const struct line_map*
1461	first_map_in_common (const line_maps *set,
1462	location_t loc0,
1463	location_t loc1,
1464	location_t *res_loc0,
1465	location_t *res_loc1)
1466	{
1467	*res_loc0 = loc0;
1468	*res_loc1 = loc1;
1469
1470	return first_map_in_common_1 (set, loc0: res_loc0, loc1: res_loc1);
1471	}
1472
1473	/* Return a positive value if PRE denotes the location of a token that
1474	comes before the token of POST, 0 if PRE denotes the location of
1475	the same token as the token for POST, and a negative value
1476	otherwise. */
1477
1478	int
1479	linemap_compare_locations (const line_maps *set,
1480	location_t pre,
1481	location_t post)
1482	{
1483	bool pre_virtual_p, post_virtual_p;
1484	location_t l0 = pre, l1 = post;
1485
1486	if (IS_ADHOC_LOC (loc: l0))
1487	l0 = get_location_from_adhoc_loc (set, loc: l0);
1488	if (IS_ADHOC_LOC (loc: l1))
1489	l1 = get_location_from_adhoc_loc (set, loc: l1);
1490
1491	if (l0 == l1)
1492	return 0;
1493
1494	if ((pre_virtual_p = linemap_location_from_macro_expansion_p (set, location: l0)))
1495	l0 = linemap_resolve_location (set, loc: l0,
1496	lrk: LRK_MACRO_EXPANSION_POINT,
1497	NULL);
1498
1499	if ((post_virtual_p = linemap_location_from_macro_expansion_p (set, location: l1)))
1500	l1 = linemap_resolve_location (set, loc: l1,
1501	lrk: LRK_MACRO_EXPANSION_POINT,
1502	NULL);
1503
1504	if (l0 == l1
1505	&& pre_virtual_p
1506	&& post_virtual_p)
1507	{
1508	/* So pre and post represent two tokens that are present in a
1509	same macro expansion. Let's see if the token for pre was
1510	before the token for post in that expansion. */
1511	const struct line_map *map =
1512	first_map_in_common (set, loc0: pre, loc1: post, res_loc0: &l0, res_loc1: &l1);
1513
1514	if (map == NULL)
1515	/* This should not be possible while we have column information, but if
1516	we don't, the tokens could be from separate macro expansions on the
1517	same line. */
1518	gcc_assert (l0 > LINE_MAP_MAX_LOCATION_WITH_COLS);
1519	else
1520	{
1521	unsigned i0 = l0 - MAP_START_LOCATION (map);
1522	unsigned i1 = l1 - MAP_START_LOCATION (map);
1523	return i1 - i0;
1524	}
1525	}
1526
1527	if (IS_ADHOC_LOC (loc: l0))
1528	l0 = get_location_from_adhoc_loc (set, loc: l0);
1529	if (IS_ADHOC_LOC (loc: l1))
1530	l1 = get_location_from_adhoc_loc (set, loc: l1);
1531
1532	return l1 - l0;
1533	}
1534
1535	/* Print an include trace, for e.g. the -H option of the preprocessor. */
1536
1537	static void
1538	trace_include (const class line_maps *set, const line_map_ordinary *map)
1539	{
1540	unsigned int i = set->depth;
1541
1542	while (--i)
1543	putc ('.', stderr);
1544
1545	fprintf (stderr, format: " %s\n", ORDINARY_MAP_FILE_NAME (ord_map: map));
1546	}
1547
1548	/* Return the spelling location of the token wherever it comes from,
1549	whether part of a macro definition or not.
1550
1551	This is a subroutine for linemap_resolve_location. */
1552
1553	static location_t
1554	linemap_macro_loc_to_spelling_point (const line_maps *set,
1555	location_t location,
1556	const line_map_ordinary **original_map)
1557	{
1558	linemap_assert (set && location >= RESERVED_LOCATION_COUNT);
1559
1560	while (true)
1561	{
1562	const struct line_map *map = linemap_lookup (set, line: location);
1563	if (!map || MAP_ORDINARY_P (map))
1564	{
1565	if (original_map)
1566	*original_map = (const line_map_ordinary *)map;
1567	break;
1568	}
1569
1570	location = linemap_macro_map_loc_unwind_toward_spelling
1571	(set, map: linemap_check_macro (map), location);
1572	}
1573
1574	return location;
1575	}
1576
1577	/* If LOCATION is the source location of a token that belongs to a
1578	macro replacement-list -- as part of a macro expansion -- then
1579	return the location of the token at the definition point of the
1580	macro. Otherwise, return LOCATION. SET is the set of maps
1581	location come from. ORIGINAL_MAP is an output parm. If non NULL,
1582	the function sets *ORIGINAL_MAP to the ordinary (non-macro) map the
1583	returned location comes from.
1584
1585	This is a subroutine of linemap_resolve_location. */
1586
1587	static location_t
1588	linemap_macro_loc_to_def_point (const line_maps *set,
1589	location_t location,
1590	const line_map_ordinary **original_map)
1591	{
1592	linemap_assert (set && location >= RESERVED_LOCATION_COUNT);
1593
1594	for (;;)
1595	{
1596	location_t caret_loc = location;
1597	if (IS_ADHOC_LOC (loc: caret_loc))
1598	caret_loc = get_location_from_adhoc_loc (set, loc: caret_loc);
1599
1600	const line_map *map = linemap_lookup (set, line: caret_loc);
1601	if (!map || MAP_ORDINARY_P (map))
1602	{
1603	if (original_map)
1604	*original_map = (const line_map_ordinary *)map;
1605	break;
1606	}
1607
1608	location = linemap_macro_map_loc_to_def_point
1609	(map: linemap_check_macro (map), location: caret_loc);
1610	}
1611
1612	return location;
1613	}
1614
1615	/* If LOCATION is the source location of a token that belongs to a
1616	macro replacement-list -- at a macro expansion point -- then return
1617	the location of the topmost expansion point of the macro. We say
1618	topmost because if we are in the context of a nested macro
1619	expansion, the function returns the source location of the first
1620	macro expansion that triggered the nested expansions.
1621
1622	Otherwise, return LOCATION. SET is the set of maps location come
1623	from. ORIGINAL_MAP is an output parm. If non NULL, the function
1624	sets *ORIGINAL_MAP to the ordinary (non-macro) map the returned
1625	location comes from.
1626
1627	This is a subroutine of linemap_resolve_location. */
1628
1629	static location_t
1630	linemap_macro_loc_to_exp_point (const line_maps *set,
1631	location_t location,
1632	const line_map_ordinary **original_map)
1633	{
1634	struct line_map *map;
1635
1636	if (IS_ADHOC_LOC (loc: location))
1637	location = get_location_from_adhoc_loc (set, loc: location);
1638
1639	linemap_assert (set && location >= RESERVED_LOCATION_COUNT);
1640
1641	while (true)
1642	{
1643	map = const_cast <line_map *> (linemap_lookup (set, line: location));
1644	if (!linemap_macro_expansion_map_p (map))
1645	break;
1646	location = linemap_macro_map_loc_to_exp_point (map: linemap_check_macro (map),
1647	location);
1648	}
1649
1650	if (original_map)
1651	*original_map = linemap_check_ordinary (map);
1652	return location;
1653	}
1654
1655	/* Resolve a virtual location into either a spelling location, an
1656	expansion point location or a token argument replacement point
1657	location. Return the map that encodes the virtual location as well
1658	as the resolved location.
1659
1660	If LOC is *NOT* the location of a token resulting from the
1661	expansion of a macro, then the parameter LRK (which stands for
1662	Location Resolution Kind) is ignored and the resulting location
1663	just equals the one given in argument.
1664
1665	Now if LOC *IS* the location of a token resulting from the
1666	expansion of a macro, this is what happens.
1667
1668	* If LRK is set to LRK_MACRO_EXPANSION_POINT
1669	-------------------------------
1670
1671	The virtual location is resolved to the first macro expansion point
1672	that led to this macro expansion.
1673
1674	* If LRK is set to LRK_SPELLING_LOCATION
1675	-------------------------------------
1676
1677	The virtual location is resolved to the locus where the token has
1678	been spelled in the source. This can follow through all the macro
1679	expansions that led to the token.
1680
1681	* If LRK is set to LRK_MACRO_DEFINITION_LOCATION
1682	--------------------------------------
1683
1684	The virtual location is resolved to the locus of the token in the
1685	context of the macro definition.
1686
1687	If LOC is the locus of a token that is an argument of a
1688	function-like macro [replacing a parameter in the replacement list
1689	of the macro] the virtual location is resolved to the locus of the
1690	parameter that is replaced, in the context of the definition of the
1691	macro.
1692
1693	If LOC is the locus of a token that is not an argument of a
1694	function-like macro, then the function behaves as if LRK was set to
1695	LRK_SPELLING_LOCATION.
1696
1697	If MAP is not NULL, *MAP is set to the map encoding the
1698	returned location. Note that if the returned location wasn't originally
1699	encoded by a map, then *MAP is set to NULL. This can happen if LOC
1700	resolves to a location reserved for the client code, like
1701	UNKNOWN_LOCATION or BUILTINS_LOCATION in GCC. */
1702
1703	location_t
1704	linemap_resolve_location (const line_maps *set,
1705	location_t loc,
1706	enum location_resolution_kind lrk,
1707	const line_map_ordinary **map)
1708	{
1709	location_t locus = loc;
1710	if (IS_ADHOC_LOC (loc))
1711	locus = get_location_from_adhoc_loc (set, loc);
1712
1713	if (locus < RESERVED_LOCATION_COUNT)
1714	{
1715	/* A reserved location wasn't encoded in a map. Let's return a
1716	NULL map here, just like what linemap_ordinary_map_lookup
1717	does. */
1718	if (map)
1719	*map = NULL;
1720	return loc;
1721	}
1722
1723	switch (lrk)
1724	{
1725	case LRK_MACRO_EXPANSION_POINT:
1726	loc = linemap_macro_loc_to_exp_point (set, location: loc, original_map: map);
1727	break;
1728	case LRK_SPELLING_LOCATION:
1729	loc = linemap_macro_loc_to_spelling_point (set, location: loc, original_map: map);
1730	break;
1731	case LRK_MACRO_DEFINITION_LOCATION:
1732	loc = linemap_macro_loc_to_def_point (set, location: loc, original_map: map);
1733	break;
1734	default:
1735	abort ();
1736	}
1737	return loc;
1738	}
1739
1740	/* TRUE if LOCATION is a source code location of a token that is part of the
1741	definition of a macro, FALSE otherwise. */
1742
1743	bool
1744	linemap_location_from_macro_definition_p (const line_maps *set,
1745	location_t loc)
1746	{
1747	if (IS_ADHOC_LOC (loc))
1748	loc = get_location_from_adhoc_loc (set, loc);
1749
1750	if (!linemap_location_from_macro_expansion_p (set, location: loc))
1751	return false;
1752
1753	while (true)
1754	{
1755	const struct line_map_macro *map
1756	= linemap_check_macro (map: linemap_lookup (set, line: loc));
1757
1758	location_t s_loc
1759	= linemap_macro_map_loc_unwind_toward_spelling (set, map, location: loc);
1760	if (linemap_location_from_macro_expansion_p (set, location: s_loc))
1761	loc = s_loc;
1762	else
1763	{
1764	location_t def_loc
1765	= linemap_macro_map_loc_to_def_point (map, location: loc);
1766	return s_loc == def_loc;
1767	}
1768	}
1769	}
1770
1771	/*
1772	Suppose that LOC is the virtual location of a token T coming from
1773	the expansion of a macro M. This function then steps up to get the
1774	location L of the point where M got expanded. If L is a spelling
1775	location inside a macro expansion M', then this function returns
1776	the locus of the point where M' was expanded. Said otherwise, this
1777	function returns the location of T in the context that triggered
1778	the expansion of M.
1779
1780	*LOC_MAP must be set to the map of LOC. This function then sets it
1781	to the map of the returned location. */
1782
1783	location_t
1784	linemap_unwind_toward_expansion (const line_maps *set,
1785	location_t loc,
1786	const struct line_map **map)
1787	{
1788	location_t resolved_location;
1789	const line_map_macro *macro_map = linemap_check_macro (map: *map);
1790	const struct line_map *resolved_map;
1791
1792	if (IS_ADHOC_LOC (loc))
1793	loc = get_location_from_adhoc_loc (set, loc);
1794
1795	resolved_location =
1796	linemap_macro_map_loc_unwind_toward_spelling (set, map: macro_map, location: loc);
1797	resolved_map = linemap_lookup (set, line: resolved_location);
1798
1799	if (!linemap_macro_expansion_map_p (map: resolved_map))
1800	{
1801	resolved_location = linemap_macro_map_loc_to_exp_point (map: macro_map, location: loc);
1802	resolved_map = linemap_lookup (set, line: resolved_location);
1803	}
1804
1805	*map = resolved_map;
1806	return resolved_location;
1807	}
1808
1809	/* If LOC is the virtual location of a token coming from the expansion
1810	of a macro M and if its spelling location is reserved (e.g, a
1811	location for a built-in token), then this function unwinds (using
1812	linemap_unwind_toward_expansion) the location until a location that
1813	is not reserved and is not in a system header is reached. In other
1814	words, this unwinds the reserved location until a location that is
1815	in real source code is reached.
1816
1817	Otherwise, if the spelling location for LOC is not reserved or if
1818	LOC doesn't come from the expansion of a macro, the function
1819	returns LOC as is and *MAP is not touched.
1820
1821	*MAP is set to the map of the returned location if the later is
1822	different from LOC. */
1823	location_t
1824	linemap_unwind_to_first_non_reserved_loc (const line_maps *set,
1825	location_t loc,
1826	const struct line_map **map)
1827	{
1828	location_t resolved_loc;
1829	const struct line_map *map0 = NULL;
1830	const line_map_ordinary *map1 = NULL;
1831
1832	if (IS_ADHOC_LOC (loc))
1833	loc = get_location_from_adhoc_loc (set, loc);
1834
1835	map0 = linemap_lookup (set, line: loc);
1836	if (!linemap_macro_expansion_map_p (map: map0))
1837	return loc;
1838
1839	resolved_loc = linemap_resolve_location (set, loc,
1840	lrk: LRK_SPELLING_LOCATION,
1841	map: &map1);
1842
1843	if (resolved_loc >= RESERVED_LOCATION_COUNT
1844	&& !LINEMAP_SYSP (ord_map: map1))
1845	return loc;
1846
1847	while (linemap_macro_expansion_map_p (map: map0)
1848	&& (resolved_loc < RESERVED_LOCATION_COUNT
1849	|| LINEMAP_SYSP (ord_map: map1)))
1850	{
1851	loc = linemap_unwind_toward_expansion (set, loc, map: &map0);
1852	resolved_loc = linemap_resolve_location (set, loc,
1853	lrk: LRK_SPELLING_LOCATION,
1854	map: &map1);
1855	}
1856
1857	if (map != NULL)
1858	*map = map0;
1859	return loc;
1860	}
1861
1862	/* Expand source code location LOC and return a user readable source
1863	code location. LOC must be a spelling (non-virtual) location. If
1864	it's a location < RESERVED_LOCATION_COUNT a zeroed expanded source
1865	location is returned. */
1866
1867	expanded_location
1868	linemap_expand_location (const line_maps *set,
1869	const struct line_map *map,
1870	location_t loc)
1871
1872	{
1873	expanded_location xloc;
1874
1875	memset (s: &xloc, c: 0, n: sizeof (xloc));
1876	if (IS_ADHOC_LOC (loc))
1877	{
1878	xloc.data = get_data_from_adhoc_loc (set, loc);
1879	loc = get_location_from_adhoc_loc (set, loc);
1880	}
1881
1882	if (loc < RESERVED_LOCATION_COUNT)
1883	/* The location for this token wasn't generated from a line map.
1884	It was probably a location for a builtin token, chosen by some
1885	client code. Let's not try to expand the location in that
1886	case. */;
1887	else if (map == NULL)
1888	/* We shouldn't be getting a NULL map with a location that is not
1889	reserved by the client code. */
1890	abort ();
1891	else
1892	{
1893	/* MAP must be an ordinary map and LOC must be non-virtual,
1894	encoded into this map, obviously; the accessors used on MAP
1895	below ensure it is ordinary. Let's just assert the
1896	non-virtualness of LOC here. */
1897	if (linemap_location_from_macro_expansion_p (set, location: loc))
1898	abort ();
1899
1900	const line_map_ordinary *ord_map = linemap_check_ordinary (map);
1901
1902	xloc.file = LINEMAP_FILE (ord_map);
1903	xloc.line = SOURCE_LINE (ord_map, loc);
1904	xloc.column = SOURCE_COLUMN (ord_map, loc);
1905	xloc.sysp = LINEMAP_SYSP (ord_map) != 0;
1906	}
1907
1908	return xloc;
1909	}
1910
1911
1912	/* Dump line map at index IX in line table SET to STREAM. If STREAM
1913	is NULL, use stderr. IS_MACRO is true if the caller wants to
1914	dump a macro map, false otherwise. */
1915
1916	void
1917	linemap_dump (FILE *stream, const line_maps *set, unsigned ix, bool is_macro)
1918	{
1919	const char *const lc_reasons_v[LC_HWM]
1920	= { "LC_ENTER", "LC_LEAVE", "LC_RENAME", "LC_RENAME_VERBATIM",
1921	"LC_ENTER_MACRO", "LC_MODULE" };
1922	const line_map *map;
1923	unsigned reason;
1924
1925	if (stream == NULL)
1926	stream = stderr;
1927
1928	if (!is_macro)
1929	{
1930	map = LINEMAPS_ORDINARY_MAP_AT (set, index: ix);
1931	reason = linemap_check_ordinary (map)->reason;
1932	}
1933	else
1934	{
1935	map = LINEMAPS_MACRO_MAP_AT (set, index: ix);
1936	reason = LC_ENTER_MACRO;
1937	}
1938
1939	fprintf (stream: stream, format: "Map #%u [%p] - LOC: %u - REASON: %s - SYSP: %s\n",
1940	ix, (void *) map, map->start_location,
1941	reason < LC_HWM ? lc_reasons_v[reason] : "???",
1942	((!is_macro
1943	&& ORDINARY_MAP_IN_SYSTEM_HEADER_P (ord_map: linemap_check_ordinary (map)))
1944	? "yes" : "no"));
1945	if (!is_macro)
1946	{
1947	const line_map_ordinary *ord_map = linemap_check_ordinary (map);
1948	const line_map_ordinary *includer_map
1949	= linemap_included_from_linemap (set, map: ord_map);
1950
1951	fprintf (stream: stream, format: "File: %s:%d\n", ORDINARY_MAP_FILE_NAME (ord_map),
1952	ORDINARY_MAP_STARTING_LINE_NUMBER (ord_map));
1953	fprintf (stream: stream, format: "Included from: [%d] %s\n",
1954	includer_map ? int (includer_map - set->info_ordinary.maps) : -1,
1955	includer_map ? ORDINARY_MAP_FILE_NAME (ord_map: includer_map) : "None");
1956	}
1957	else
1958	{
1959	const line_map_macro *macro_map = linemap_check_macro (map);
1960	fprintf (stream: stream, format: "Macro: %s (%u tokens)\n",
1961	linemap_map_get_macro_name (macro_map),
1962	MACRO_MAP_NUM_MACRO_TOKENS (macro_map));
1963	}
1964
1965	fprintf (stream: stream, format: "\n");
1966	}
1967
1968
1969	/* Dump debugging information about source location LOC into the file
1970	stream STREAM. SET is the line map set LOC comes from. */
1971
1972	void
1973	linemap_dump_location (const line_maps *set,
1974	location_t loc,
1975	FILE *stream)
1976	{
1977	const line_map_ordinary *map;
1978	location_t location;
1979	const char *path = "", *from = "";
1980	int l = -1, c = -1, s = -1, e = -1;
1981
1982	if (IS_ADHOC_LOC (loc))
1983	loc = get_location_from_adhoc_loc (set, loc);
1984
1985	if (loc == 0)
1986	return;
1987
1988	location =
1989	linemap_resolve_location (set, loc, lrk: LRK_MACRO_DEFINITION_LOCATION, map: &map);
1990
1991	if (map == NULL)
1992	/* Only reserved locations can be tolerated in this case. */
1993	linemap_assert (location < RESERVED_LOCATION_COUNT);
1994	else
1995	{
1996	path = LINEMAP_FILE (ord_map: map);
1997	l = SOURCE_LINE (ord_map: map, loc: location);
1998	c = SOURCE_COLUMN (ord_map: map, loc: location);
1999	s = LINEMAP_SYSP (ord_map: map) != 0;
2000	e = location != loc;
2001	if (e)
2002	from = "N/A";
2003	else
2004	{
2005	const line_map_ordinary *from_map
2006	= linemap_included_from_linemap (set, map);
2007	from = from_map ? LINEMAP_FILE (ord_map: from_map) : "<NULL>";
2008	}
2009	}
2010
2011	/* P: path, L: line, C: column, S: in-system-header, M: map address,
2012	E: macro expansion?, LOC: original location, R: resolved location */
2013	fprintf (stream: stream, format: "{P:%s;F:%s;L:%d;C:%d;S:%d;M:%p;E:%d,LOC:%d,R:%d}",
2014	path, from, l, c, s, (void*)map, e, loc, location);
2015	}
2016
2017	/* Return the highest location emitted for a given file for which
2018	there is a line map in SET. FILE_NAME is the file name to
2019	consider. If the function returns TRUE, *LOC is set to the highest
2020	location emitted for that file. */
2021
2022	bool
2023	linemap_get_file_highest_location (const line_maps *set,
2024	const char *file_name,
2025	location_t *loc)
2026	{
2027	/* If the set is empty or no ordinary map has been created then
2028	there is no file to look for ... */
2029	if (set == NULL || set->info_ordinary.used == 0)
2030	return false;
2031
2032	/* Now look for the last ordinary map created for FILE_NAME. */
2033	int i;
2034	for (i = set->info_ordinary.used - 1; i >= 0; --i)
2035	{
2036	const char *fname = set->info_ordinary.maps[i].to_file;
2037	if (fname && !filename_cmp (s1: fname, s2: file_name))
2038	break;
2039	}
2040
2041	if (i < 0)
2042	return false;
2043
2044	/* The highest location for a given map is either the starting
2045	location of the next map minus one, or -- if the map is the
2046	latest one -- the highest location of the set. */
2047	location_t result;
2048	if (i == (int) set->info_ordinary.used - 1)
2049	result = set->highest_location;
2050	else
2051	result = set->info_ordinary.maps[i + 1].start_location - 1;
2052
2053	*loc = result;
2054	return true;
2055	}
2056
2057	/* Compute and return statistics about the memory consumption of some
2058	parts of the line table SET. */
2059
2060	void
2061	linemap_get_statistics (const line_maps *set,
2062	struct linemap_stats *s)
2063	{
2064	long ordinary_maps_allocated_size, ordinary_maps_used_size,
2065	macro_maps_allocated_size, macro_maps_used_size,
2066	macro_maps_locations_size = 0, duplicated_macro_maps_locations_size = 0;
2067
2068	const line_map_macro *cur_map;
2069
2070	ordinary_maps_allocated_size =
2071	LINEMAPS_ORDINARY_ALLOCATED (set) * sizeof (struct line_map_ordinary);
2072
2073	ordinary_maps_used_size =
2074	LINEMAPS_ORDINARY_USED (set) * sizeof (struct line_map_ordinary);
2075
2076	macro_maps_allocated_size =
2077	LINEMAPS_MACRO_ALLOCATED (set) * sizeof (struct line_map_macro);
2078
2079	for (cur_map = set->info_macro.maps;
2080	cur_map && cur_map <= LINEMAPS_LAST_MACRO_MAP (set);
2081	++cur_map)
2082	{
2083	unsigned i;
2084
2085	linemap_assert (linemap_macro_expansion_map_p (cur_map));
2086
2087	macro_maps_locations_size +=
2088	2 * MACRO_MAP_NUM_MACRO_TOKENS (macro_map: cur_map) * sizeof (location_t);
2089
2090	for (i = 0; i < 2 * MACRO_MAP_NUM_MACRO_TOKENS (macro_map: cur_map); i += 2)
2091	{
2092	if (MACRO_MAP_LOCATIONS (macro_map: cur_map)[i] ==
2093	MACRO_MAP_LOCATIONS (macro_map: cur_map)[i + 1])
2094	duplicated_macro_maps_locations_size +=
2095	sizeof (location_t);
2096	}
2097	}
2098
2099	macro_maps_used_size =
2100	LINEMAPS_MACRO_USED (set) * sizeof (struct line_map_macro);
2101
2102	s->num_ordinary_maps_allocated = LINEMAPS_ORDINARY_ALLOCATED (set);
2103	s->num_ordinary_maps_used = LINEMAPS_ORDINARY_USED (set);
2104	s->ordinary_maps_allocated_size = ordinary_maps_allocated_size;
2105	s->ordinary_maps_used_size = ordinary_maps_used_size;
2106	s->num_expanded_macros = num_expanded_macros_counter;
2107	s->num_macro_tokens = num_macro_tokens_counter;
2108	s->num_macro_maps_used = LINEMAPS_MACRO_USED (set);
2109	s->macro_maps_allocated_size = macro_maps_allocated_size;
2110	s->macro_maps_locations_size = macro_maps_locations_size;
2111	s->macro_maps_used_size = macro_maps_used_size;
2112	s->duplicated_macro_maps_locations_size =
2113	duplicated_macro_maps_locations_size;
2114	s->adhoc_table_size = (set->m_location_adhoc_data_map.allocated
2115	* sizeof (struct location_adhoc_data));
2116	s->adhoc_table_entries_used = set->m_location_adhoc_data_map.curr_loc;
2117	}
2118
2119
2120	/* Dump line table SET to STREAM. If STREAM is NULL, stderr is used.
2121	NUM_ORDINARY specifies how many ordinary maps to dump. NUM_MACRO
2122	specifies how many macro maps to dump. */
2123
2124	void
2125	line_table_dump (FILE *stream, const line_maps *set, unsigned int num_ordinary,
2126	unsigned int num_macro)
2127	{
2128	unsigned int i;
2129
2130	if (set == NULL)
2131	return;
2132
2133	if (stream == NULL)
2134	stream = stderr;
2135
2136	fprintf (stream: stream, format: "# of ordinary maps: %d\n", LINEMAPS_ORDINARY_USED (set));
2137	fprintf (stream: stream, format: "# of macro maps: %d\n", LINEMAPS_MACRO_USED (set));
2138	fprintf (stream: stream, format: "Include stack depth: %d\n", set->depth);
2139	fprintf (stream: stream, format: "Highest location: %u\n", set->highest_location);
2140
2141	if (num_ordinary)
2142	{
2143	fprintf (stream: stream, format: "\nOrdinary line maps\n");
2144	for (i = 0; i < num_ordinary && i < LINEMAPS_ORDINARY_USED (set); i++)
2145	linemap_dump (stream, set, ix: i, is_macro: false);
2146	fprintf (stream: stream, format: "\n");
2147	}
2148
2149	if (num_macro)
2150	{
2151	fprintf (stream: stream, format: "\nMacro line maps\n");
2152	for (i = 0; i < num_macro && i < LINEMAPS_MACRO_USED (set); i++)
2153	linemap_dump (stream, set, ix: i, is_macro: true);
2154	fprintf (stream: stream, format: "\n");
2155	}
2156	}
2157
2158	/* class rich_location. */
2159
2160	/* Construct a rich_location with location LOC as its initial range. */
2161
2162	rich_location::rich_location (line_maps *set, location_t loc,
2163	const range_label *label) :
2164	m_line_table (set),
2165	m_ranges (),
2166	m_column_override (0),
2167	m_have_expanded_location (false),
2168	m_seen_impossible_fixit (false),
2169	m_fixits_cannot_be_auto_applied (false),
2170	m_escape_on_output (false),
2171	m_fixit_hints (),
2172	m_path (NULL)
2173	{
2174	add_range (loc, range_display_kind: SHOW_RANGE_WITH_CARET, label);
2175	}
2176
2177	/* The destructor for class rich_location. */
2178
2179	rich_location::~rich_location ()
2180	{
2181	for (unsigned int i = 0; i < m_fixit_hints.count (); i++)
2182	delete get_fixit_hint (idx: i);
2183	}
2184
2185	/* Get location IDX within this rich_location. */
2186
2187	location_t
2188	rich_location::get_loc (unsigned int idx) const
2189	{
2190	const location_range *locrange = get_range (idx);
2191	return locrange->m_loc;
2192	}
2193
2194	/* Get range IDX within this rich_location. */
2195
2196	const location_range *
2197	rich_location::get_range (unsigned int idx) const
2198	{
2199	return &m_ranges[idx];
2200	}
2201
2202	/* Mutable access to range IDX within this rich_location. */
2203
2204	location_range *
2205	rich_location::get_range (unsigned int idx)
2206	{
2207	return &m_ranges[idx];
2208	}
2209
2210	/* Expand location IDX within this rich_location. */
2211	/* Get an expanded_location for this rich_location's primary
2212	location. */
2213
2214	expanded_location
2215	rich_location::get_expanded_location (unsigned int idx) const
2216	{
2217	if (idx == 0)
2218	{
2219	/* Cache the expansion of the primary location. */
2220	if (!m_have_expanded_location)
2221	{
2222	m_expanded_location
2223	= linemap_client_expand_location_to_spelling_point
2224	(m_line_table, get_loc (idx: 0), LOCATION_ASPECT_CARET);
2225	if (m_column_override)
2226	m_expanded_location.column = m_column_override;
2227	m_have_expanded_location = true;
2228	}
2229
2230	return m_expanded_location;
2231	}
2232	else
2233	return linemap_client_expand_location_to_spelling_point
2234	(m_line_table, get_loc (idx), LOCATION_ASPECT_CARET);
2235	}
2236
2237	/* Set the column of the primary location, with 0 meaning
2238	"don't override it". */
2239
2240	void
2241	rich_location::override_column (int column)
2242	{
2243	m_column_override = column;
2244	m_have_expanded_location = false;
2245	}
2246
2247	/* Add the given range. */
2248
2249	void
2250	rich_location::add_range (location_t loc,
2251	enum range_display_kind range_display_kind,
2252	const range_label *label)
2253	{
2254	location_range range;
2255	range.m_loc = loc;
2256	range.m_range_display_kind = range_display_kind;
2257	range.m_label = label;
2258	m_ranges.push (value: range);
2259	}
2260
2261	/* Add or overwrite the location given by IDX, setting its location to LOC,
2262	and setting its m_range_display_kind to RANGE_DISPLAY_KIND.
2263
2264	It must either overwrite an existing location, or add one *exactly* on
2265	the end of the array.
2266
2267	This is primarily for use by gcc when implementing diagnostic format
2268	decoders e.g.
2269	- the "+" in the C/C++ frontends, for handling format codes like "%q+D"
2270	(which writes the source location of a tree back into location 0 of
2271	the rich_location), and
2272	- the "%C" and "%L" format codes in the Fortran frontend. */
2273
2274	void
2275	rich_location::set_range (unsigned int idx, location_t loc,
2276	enum range_display_kind range_display_kind)
2277	{
2278	/* We can either overwrite an existing range, or add one exactly
2279	on the end of the array. */
2280	linemap_assert (idx <= m_ranges.count ());
2281
2282	if (idx == m_ranges.count ())
2283	add_range (loc, range_display_kind);
2284	else
2285	{
2286	location_range *locrange = get_range (idx);
2287	locrange->m_loc = loc;
2288	locrange->m_range_display_kind = range_display_kind;
2289	}
2290
2291	if (idx == 0)
2292	/* Mark any cached value here as dirty. */
2293	m_have_expanded_location = false;
2294	}
2295
2296	/* Methods for adding insertion fix-it hints. */
2297
2298	/* Add a fixit-hint, suggesting insertion of NEW_CONTENT
2299	immediately before the primary range's start location. */
2300
2301	void
2302	rich_location::add_fixit_insert_before (const char *new_content)
2303	{
2304	add_fixit_insert_before (where: get_loc (), new_content);
2305	}
2306
2307	/* Add a fixit-hint, suggesting insertion of NEW_CONTENT
2308	immediately before the start of WHERE. */
2309
2310	void
2311	rich_location::add_fixit_insert_before (location_t where,
2312	const char *new_content)
2313	{
2314	location_t start = get_range_from_loc (set: m_line_table, loc: where).m_start;
2315	maybe_add_fixit (start, next_loc: start, new_content);
2316	}
2317
2318	/* Add a fixit-hint, suggesting insertion of NEW_CONTENT
2319	immediately after the primary range's end-point. */
2320
2321	void
2322	rich_location::add_fixit_insert_after (const char *new_content)
2323	{
2324	add_fixit_insert_after (where: get_loc (), new_content);
2325	}
2326
2327	/* Add a fixit-hint, suggesting insertion of NEW_CONTENT
2328	immediately after the end-point of WHERE. */
2329
2330	void
2331	rich_location::add_fixit_insert_after (location_t where,
2332	const char *new_content)
2333	{
2334	location_t finish = get_range_from_loc (set: m_line_table, loc: where).m_finish;
2335	location_t next_loc
2336	= linemap_position_for_loc_and_offset (set: m_line_table, loc: finish, column_offset: 1);
2337
2338	/* linemap_position_for_loc_and_offset can fail, if so, it returns
2339	its input value. */
2340	if (next_loc == finish)
2341	{
2342	stop_supporting_fixits ();
2343	return;
2344	}
2345
2346	maybe_add_fixit (start: next_loc, next_loc, new_content);
2347	}
2348
2349	/* Methods for adding removal fix-it hints. */
2350
2351	/* Add a fixit-hint, suggesting removal of the content covered
2352	by range 0. */
2353
2354	void
2355	rich_location::add_fixit_remove ()
2356	{
2357	add_fixit_remove (where: get_loc ());
2358	}
2359
2360	/* Add a fixit-hint, suggesting removal of the content between
2361	the start and finish of WHERE. */
2362
2363	void
2364	rich_location::add_fixit_remove (location_t where)
2365	{
2366	source_range range = get_range_from_loc (set: m_line_table, loc: where);
2367	add_fixit_remove (src_range: range);
2368	}
2369
2370	/* Add a fixit-hint, suggesting removal of the content at
2371	SRC_RANGE. */
2372
2373	void
2374	rich_location::add_fixit_remove (source_range src_range)
2375	{
2376	add_fixit_replace (src_range, new_content: "");
2377	}
2378
2379	/* Add a fixit-hint, suggesting replacement of the content covered
2380	by range 0 with NEW_CONTENT. */
2381
2382	void
2383	rich_location::add_fixit_replace (const char *new_content)
2384	{
2385	add_fixit_replace (where: get_loc (), new_content);
2386	}
2387
2388	/* Methods for adding "replace" fix-it hints. */
2389
2390	/* Add a fixit-hint, suggesting replacement of the content between
2391	the start and finish of WHERE with NEW_CONTENT. */
2392
2393	void
2394	rich_location::add_fixit_replace (location_t where,
2395	const char *new_content)
2396	{
2397	source_range range = get_range_from_loc (set: m_line_table, loc: where);
2398	add_fixit_replace (src_range: range, new_content);
2399	}
2400
2401	/* Add a fixit-hint, suggesting replacement of the content at
2402	SRC_RANGE with NEW_CONTENT. */
2403
2404	void
2405	rich_location::add_fixit_replace (source_range src_range,
2406	const char *new_content)
2407	{
2408	location_t start = get_pure_location (set: m_line_table, loc: src_range.m_start);
2409	location_t finish = get_pure_location (set: m_line_table, loc: src_range.m_finish);
2410
2411	/* Fix-it hints use half-closed ranges, so attempt to offset the endpoint. */
2412	location_t next_loc
2413	= linemap_position_for_loc_and_offset (set: m_line_table, loc: finish, column_offset: 1);
2414	/* linemap_position_for_loc_and_offset can fail, if so, it returns
2415	its input value. */
2416	if (next_loc == finish)
2417	{
2418	stop_supporting_fixits ();
2419	return;
2420	}
2421	finish = next_loc;
2422
2423	maybe_add_fixit (start, next_loc: finish, new_content);
2424	}
2425
2426	/* Get the last fix-it hint within this rich_location, or NULL if none. */
2427
2428	fixit_hint *
2429	rich_location::get_last_fixit_hint () const
2430	{
2431	if (m_fixit_hints.count () > 0)
2432	return get_fixit_hint (idx: m_fixit_hints.count () - 1);
2433	else
2434	return NULL;
2435	}
2436
2437	/* If WHERE is an "awkward" location, then mark this rich_location as not
2438	supporting fixits, purging any thay were already added, and return true.
2439
2440	Otherwise (the common case), return false. */
2441
2442	bool
2443	rich_location::reject_impossible_fixit (location_t where)
2444	{
2445	/* Fix-its within a rich_location should either all be suggested, or
2446	none of them should be suggested.
2447	Once we've rejected a fixit, we reject any more, even those
2448	with reasonable locations. */
2449	if (m_seen_impossible_fixit)
2450	return true;
2451
2452	if (where <= LINE_MAP_MAX_LOCATION_WITH_COLS)
2453	/* WHERE is a reasonable location for a fix-it; don't reject it. */
2454	return false;
2455
2456	/* Otherwise we have an attempt to add a fix-it with an "awkward"
2457	location: either one that we can't obtain column information
2458	for (within an ordinary map), or one within a macro expansion. */
2459	stop_supporting_fixits ();
2460	return true;
2461	}
2462
2463	/* Mark this rich_location as not supporting fixits, purging any that were
2464	already added. */
2465
2466	void
2467	rich_location::stop_supporting_fixits ()
2468	{
2469	m_seen_impossible_fixit = true;
2470
2471	/* Purge the rich_location of any fix-its that were already added. */
2472	for (unsigned int i = 0; i < m_fixit_hints.count (); i++)
2473	delete get_fixit_hint (idx: i);
2474	m_fixit_hints.truncate (len: 0);
2475	}
2476
2477	/* Add HINT to the fix-it hints in this rich_location,
2478	consolidating into the prior fixit if possible. */
2479
2480	void
2481	rich_location::maybe_add_fixit (location_t start,
2482	location_t next_loc,
2483	const char *new_content)
2484	{
2485	if (reject_impossible_fixit (where: start))
2486	return;
2487	if (reject_impossible_fixit (where: next_loc))
2488	return;
2489
2490	/* Only allow fix-it hints that affect a single line in one file.
2491	Compare the end-points. */
2492	expanded_location exploc_start
2493	= linemap_client_expand_location_to_spelling_point (m_line_table,
2494	start,
2495	LOCATION_ASPECT_START);
2496	expanded_location exploc_next_loc
2497	= linemap_client_expand_location_to_spelling_point (m_line_table,
2498	next_loc,
2499	LOCATION_ASPECT_START);
2500	/* They must be within the same file... */
2501	if (exploc_start.file != exploc_next_loc.file)
2502	{
2503	stop_supporting_fixits ();
2504	return;
2505	}
2506	/* ...and on the same line. */
2507	if (exploc_start.line != exploc_next_loc.line)
2508	{
2509	stop_supporting_fixits ();
2510	return;
2511	}
2512	/* The columns must be in the correct order. This can fail if the
2513	endpoints straddle the boundary for which the linemap can represent
2514	columns (PR c/82050). */
2515	if (exploc_start.column > exploc_next_loc.column)
2516	{
2517	stop_supporting_fixits ();
2518	return;
2519	}
2520	/* If we have very long lines, tokens will eventually fall back to
2521	having column == 0.
2522	We can't handle fix-it hints that use such locations. */
2523	if (exploc_start.column == 0 || exploc_next_loc.column == 0)
2524	{
2525	stop_supporting_fixits ();
2526	return;
2527	}
2528
2529	const char *newline = strchr (s: new_content, c: '\n');
2530	if (newline)
2531	{
2532	/* For now, we can only support insertion of whole lines
2533	i.e. starts at start of line, and the newline is at the end of
2534	the insertion point. */
2535
2536	/* It must be an insertion, not a replacement/deletion. */
2537	if (start != next_loc)
2538	{
2539	stop_supporting_fixits ();
2540	return;
2541	}
2542
2543	/* The insertion must be at the start of a line. */
2544	if (exploc_start.column != 1)
2545	{
2546	stop_supporting_fixits ();
2547	return;
2548	}
2549
2550	/* The newline must be at end of NEW_CONTENT.
2551	We could eventually split up fix-its at newlines if we wanted
2552	to allow more generality (e.g. to allow adding multiple lines
2553	with one add_fixit call. */
2554	if (newline[1] != '\0')
2555	{
2556	stop_supporting_fixits ();
2557	return;
2558	}
2559	}
2560
2561	/* Consolidate neighboring fixits.
2562	Don't consolidate into newline-insertion fixits. */
2563	fixit_hint *prev = get_last_fixit_hint ();
2564	if (prev && !prev->ends_with_newline_p ())
2565	if (prev->maybe_append (start, next_loc, new_content))
2566	return;
2567
2568	m_fixit_hints.push (value: new fixit_hint (start, next_loc, new_content));
2569	}
2570
2571	/* class fixit_hint. */
2572
2573	fixit_hint::fixit_hint (location_t start,
2574	location_t next_loc,
2575	const char *new_content)
2576	: m_start (start),
2577	m_next_loc (next_loc),
2578	m_bytes (xstrdup (new_content)),
2579	m_len (strlen (s: new_content))
2580	{
2581	}
2582
2583	/* Does this fix-it hint affect the given line? */
2584
2585	bool
2586	fixit_hint::affects_line_p (const line_maps *set,
2587	const char *file,
2588	int line) const
2589	{
2590	expanded_location exploc_start
2591	= linemap_client_expand_location_to_spelling_point (set,
2592	m_start,
2593	LOCATION_ASPECT_START);
2594	if (file != exploc_start.file)
2595	return false;
2596	if (line < exploc_start.line)
2597	return false;
2598	expanded_location exploc_next_loc
2599	= linemap_client_expand_location_to_spelling_point (set,
2600	m_next_loc,
2601	LOCATION_ASPECT_START);
2602	if (file != exploc_next_loc.file)
2603	return false;
2604	if (line > exploc_next_loc.line)
2605	return false;
2606	return true;
2607	}
2608
2609	/* Method for consolidating fix-it hints, for use by
2610	rich_location::maybe_add_fixit.
2611	If possible, merge a pending fix-it hint with the given params
2612	into this one and return true.
2613	Otherwise return false. */
2614
2615	bool
2616	fixit_hint::maybe_append (location_t start,
2617	location_t next_loc,
2618	const char *new_content)
2619	{
2620	/* For consolidation to be possible, START must be at this hint's
2621	m_next_loc. */
2622	if (start != m_next_loc)
2623	return false;
2624
2625	/* If so, we have neighboring replacements; merge them. */
2626	m_next_loc = next_loc;
2627	size_t extra_len = strlen (s: new_content);
2628	m_bytes = (char *)xrealloc (m_bytes, m_len + extra_len + 1);
2629	memcpy (dest: m_bytes + m_len, src: new_content, n: extra_len);
2630	m_len += extra_len;
2631	m_bytes[m_len] = '\0';
2632	return true;
2633	}
2634
2635	/* Return true iff this hint's content ends with a newline. */
2636
2637	bool
2638	fixit_hint::ends_with_newline_p () const
2639	{
2640	if (m_len == 0)
2641	return false;
2642	return m_bytes[m_len - 1] == '\n';
2643	}
2644