1 /* Map logical line numbers to (source file, line number) pairs. 2 Copyright (C) 2001, 2003, 2004, 2007, 2008, 2009 3 Free Software Foundation, Inc. 4 5 This program is free software; you can redistribute it and/or modify it 6 under the terms of the GNU General Public License as published by the 7 Free Software Foundation; either version 3, or (at your option) any 8 later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program; see the file COPYING3. If not see 17 <http://www.gnu.org/licenses/>. 18 19 In other words, you are welcome to use, share and improve this program. 20 You are forbidden to forbid anyone else to use, share and improve 21 what you give them. Help stamp out software-hoarding! */ 22 23 #include "config.h" 24 #include "system.h" 25 #include "line-map.h" 26 27 static void trace_include (const struct line_maps *, const struct line_map *); 28 29 /* Initialize a line map set. */ 30 31 void 32 linemap_init (struct line_maps *set) 33 { 34 set->maps = NULL; 35 set->allocated = 0; 36 set->used = 0; 37 set->last_listed = -1; 38 set->trace_includes = false; 39 set->depth = 0; 40 set->cache = 0; 41 set->highest_location = RESERVED_LOCATION_COUNT - 1; 42 set->highest_line = RESERVED_LOCATION_COUNT - 1; 43 set->max_column_hint = 0; 44 set->reallocator = 0; 45 } 46 47 /* Check for and warn about line_maps entered but not exited. */ 48 49 void 50 linemap_check_files_exited (struct line_maps *set) 51 { 52 struct line_map *map; 53 /* Depending upon whether we are handling preprocessed input or 54 not, this can be a user error or an ICE. */ 55 for (map = &set->maps[set->used - 1]; ! MAIN_FILE_P (map); 56 map = INCLUDED_FROM (set, map)) 57 fprintf (stderr, "line-map.c: file \"%s\" entered but not left\n", 58 map->to_file); 59 } 60 61 /* Free a line map set. */ 62 63 void 64 linemap_free (struct line_maps *set) 65 { 66 if (set->maps) 67 { 68 linemap_check_files_exited (set); 69 70 free (set->maps); 71 } 72 } 73 74 /* Add a mapping of logical source line to physical source file and 75 line number. 76 77 The text pointed to by TO_FILE must have a lifetime 78 at least as long as the final call to lookup_line (). An empty 79 TO_FILE means standard input. If reason is LC_LEAVE, and 80 TO_FILE is NULL, then TO_FILE, TO_LINE and SYSP are given their 81 natural values considering the file we are returning to. 82 83 FROM_LINE should be monotonic increasing across calls to this 84 function. A call to this function can relocate the previous set of 85 maps, so any stored line_map pointers should not be used. */ 86 87 const struct line_map * 88 linemap_add (struct line_maps *set, enum lc_reason reason, 89 unsigned int sysp, const char *to_file, linenum_type to_line) 90 { 91 struct line_map *map; 92 source_location start_location = set->highest_location + 1; 93 94 if (set->used && start_location < set->maps[set->used - 1].start_location) 95 abort (); 96 97 if (set->used == set->allocated) 98 { 99 line_map_realloc reallocator 100 = set->reallocator ? set->reallocator : xrealloc; 101 set->allocated = 2 * set->allocated + 256; 102 set->maps 103 = (struct line_map *) (*reallocator) (set->maps, 104 set->allocated 105 * sizeof (struct line_map)); 106 memset (&set->maps[set->used], 0, ((set->allocated - set->used) 107 * sizeof (struct line_map))); 108 } 109 110 map = &set->maps[set->used]; 111 112 if (to_file && *to_file == '\0' && reason != LC_RENAME_VERBATIM) 113 to_file = "<stdin>"; 114 115 if (reason == LC_RENAME_VERBATIM) 116 reason = LC_RENAME; 117 118 /* If we don't keep our line maps consistent, we can easily 119 segfault. Don't rely on the client to do it for us. */ 120 if (set->depth == 0) 121 reason = LC_ENTER; 122 else if (reason == LC_LEAVE) 123 { 124 struct line_map *from; 125 bool error; 126 127 if (MAIN_FILE_P (map - 1)) 128 { 129 if (to_file == NULL) 130 { 131 set->depth--; 132 return NULL; 133 } 134 error = true; 135 reason = LC_RENAME; 136 from = map - 1; 137 } 138 else 139 { 140 from = INCLUDED_FROM (set, map - 1); 141 error = to_file && strcmp (from->to_file, to_file); 142 } 143 144 /* Depending upon whether we are handling preprocessed input or 145 not, this can be a user error or an ICE. */ 146 if (error) 147 fprintf (stderr, "line-map.c: file \"%s\" left but not entered\n", 148 to_file); 149 150 /* A TO_FILE of NULL is special - we use the natural values. */ 151 if (error || to_file == NULL) 152 { 153 to_file = from->to_file; 154 to_line = SOURCE_LINE (from, from[1].start_location); 155 sysp = from->sysp; 156 } 157 } 158 159 map->reason = reason; 160 map->sysp = sysp; 161 map->start_location = start_location; 162 map->to_file = to_file; 163 map->to_line = to_line; 164 set->cache = set->used++; 165 map->column_bits = 0; 166 set->highest_location = start_location; 167 set->highest_line = start_location; 168 set->max_column_hint = 0; 169 170 if (reason == LC_ENTER) 171 { 172 map->included_from = set->depth == 0 ? -1 : (int) (set->used - 2); 173 set->depth++; 174 if (set->trace_includes) 175 trace_include (set, map); 176 } 177 else if (reason == LC_RENAME) 178 map->included_from = map[-1].included_from; 179 else if (reason == LC_LEAVE) 180 { 181 set->depth--; 182 map->included_from = INCLUDED_FROM (set, map - 1)->included_from; 183 } 184 185 return map; 186 } 187 188 source_location 189 linemap_line_start (struct line_maps *set, linenum_type to_line, 190 unsigned int max_column_hint) 191 { 192 struct line_map *map = &set->maps[set->used - 1]; 193 source_location highest = set->highest_location; 194 source_location r; 195 linenum_type last_line = SOURCE_LINE (map, set->highest_line); 196 int line_delta = to_line - last_line; 197 bool add_map = false; 198 if (line_delta < 0 199 || (line_delta > 10 && line_delta * map->column_bits > 1000) 200 || (max_column_hint >= (1U << map->column_bits)) 201 || (max_column_hint <= 80 && map->column_bits >= 10)) 202 { 203 add_map = true; 204 } 205 else 206 max_column_hint = set->max_column_hint; 207 if (add_map) 208 { 209 int column_bits; 210 if (max_column_hint > 100000 || highest > 0xC0000000) 211 { 212 /* If the column number is ridiculous or we've allocated a huge 213 number of source_locations, give up on column numbers. */ 214 max_column_hint = 0; 215 if (highest >0xF0000000) 216 return 0; 217 column_bits = 0; 218 } 219 else 220 { 221 column_bits = 7; 222 while (max_column_hint >= (1U << column_bits)) 223 column_bits++; 224 max_column_hint = 1U << column_bits; 225 } 226 /* Allocate the new line_map. However, if the current map only has a 227 single line we can sometimes just increase its column_bits instead. */ 228 if (line_delta < 0 229 || last_line != map->to_line 230 || SOURCE_COLUMN (map, highest) >= (1U << column_bits)) 231 map = (struct line_map *) linemap_add (set, LC_RENAME, map->sysp, 232 map->to_file, to_line); 233 map->column_bits = column_bits; 234 r = map->start_location + ((to_line - map->to_line) << column_bits); 235 } 236 else 237 r = highest - SOURCE_COLUMN (map, highest) 238 + (line_delta << map->column_bits); 239 set->highest_line = r; 240 if (r > set->highest_location) 241 set->highest_location = r; 242 set->max_column_hint = max_column_hint; 243 return r; 244 } 245 246 source_location 247 linemap_position_for_column (struct line_maps *set, unsigned int to_column) 248 { 249 source_location r = set->highest_line; 250 if (to_column >= set->max_column_hint) 251 { 252 if (r >= 0xC000000 || to_column > 100000) 253 { 254 /* Running low on source_locations - disable column numbers. */ 255 return r; 256 } 257 else 258 { 259 struct line_map *map = &set->maps[set->used - 1]; 260 r = linemap_line_start (set, SOURCE_LINE (map, r), to_column + 50); 261 } 262 } 263 r = r + to_column; 264 if (r >= set->highest_location) 265 set->highest_location = r; 266 return r; 267 } 268 269 /* Given a logical line, returns the map from which the corresponding 270 (source file, line) pair can be deduced. Since the set is built 271 chronologically, the logical lines are monotonic increasing, and so 272 the list is sorted and we can use a binary search. */ 273 274 const struct line_map * 275 linemap_lookup (struct line_maps *set, source_location line) 276 { 277 unsigned int md, mn, mx; 278 const struct line_map *cached; 279 280 mn = set->cache; 281 mx = set->used; 282 283 cached = &set->maps[mn]; 284 /* We should get a segfault if no line_maps have been added yet. */ 285 if (line >= cached->start_location) 286 { 287 if (mn + 1 == mx || line < cached[1].start_location) 288 return cached; 289 } 290 else 291 { 292 mx = mn; 293 mn = 0; 294 } 295 296 while (mx - mn > 1) 297 { 298 md = (mn + mx) / 2; 299 if (set->maps[md].start_location > line) 300 mx = md; 301 else 302 mn = md; 303 } 304 305 set->cache = mn; 306 return &set->maps[mn]; 307 } 308 309 /* Print an include trace, for e.g. the -H option of the preprocessor. */ 310 311 static void 312 trace_include (const struct line_maps *set, const struct line_map *map) 313 { 314 unsigned int i = set->depth; 315 316 while (--i) 317 putc ('.', stderr); 318 fprintf (stderr, " %s\n", map->to_file); 319 } 320