1 // Copyright 2010 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package token 6 7 import ( 8 "fmt" 9 "sort" 10 "sync" 11 ) 12 13 // ----------------------------------------------------------------------------- 14 // Positions 15 16 // Position describes an arbitrary source position 17 // including the file, line, and column location. 18 // A Position is valid if the line number is > 0. 19 // 20 type Position struct { 21 Filename string // filename, if any 22 Offset int // offset, starting at 0 23 Line int // line number, starting at 1 24 Column int // column number, starting at 1 (byte count) 25 } 26 27 // IsValid reports whether the position is valid. 28 func (pos *Position) IsValid() bool { return pos.Line > 0 } 29 30 // String returns a string in one of several forms: 31 // 32 // file:line:column valid position with file name 33 // file:line valid position with file name but no column (column == 0) 34 // line:column valid position without file name 35 // line valid position without file name and no column (column == 0) 36 // file invalid position with file name 37 // - invalid position without file name 38 // 39 func (pos Position) String() string { 40 s := pos.Filename 41 if pos.IsValid() { 42 if s != "" { 43 s += ":" 44 } 45 s += fmt.Sprintf("%d", pos.Line) 46 if pos.Column != 0 { 47 s += fmt.Sprintf(":%d", pos.Column) 48 } 49 } 50 if s == "" { 51 s = "-" 52 } 53 return s 54 } 55 56 // Pos is a compact encoding of a source position within a file set. 57 // It can be converted into a Position for a more convenient, but much 58 // larger, representation. 59 // 60 // The Pos value for a given file is a number in the range [base, base+size], 61 // where base and size are specified when adding the file to the file set via 62 // AddFile. 63 // 64 // To create the Pos value for a specific source offset (measured in bytes), 65 // first add the respective file to the current file set using FileSet.AddFile 66 // and then call File.Pos(offset) for that file. Given a Pos value p 67 // for a specific file set fset, the corresponding Position value is 68 // obtained by calling fset.Position(p). 69 // 70 // Pos values can be compared directly with the usual comparison operators: 71 // If two Pos values p and q are in the same file, comparing p and q is 72 // equivalent to comparing the respective source file offsets. If p and q 73 // are in different files, p < q is true if the file implied by p was added 74 // to the respective file set before the file implied by q. 75 // 76 type Pos int 77 78 // The zero value for Pos is NoPos; there is no file and line information 79 // associated with it, and NoPos.IsValid() is false. NoPos is always 80 // smaller than any other Pos value. The corresponding Position value 81 // for NoPos is the zero value for Position. 82 // 83 const NoPos Pos = 0 84 85 // IsValid reports whether the position is valid. 86 func (p Pos) IsValid() bool { 87 return p != NoPos 88 } 89 90 // ----------------------------------------------------------------------------- 91 // File 92 93 // A File is a handle for a file belonging to a FileSet. 94 // A File has a name, size, and line offset table. 95 // 96 type File struct { 97 set *FileSet 98 name string // file name as provided to AddFile 99 base int // Pos value range for this file is [base...base+size] 100 size int // file size as provided to AddFile 101 102 // lines and infos are protected by mutex 103 mutex sync.Mutex 104 lines []int // lines contains the offset of the first character for each line (the first entry is always 0) 105 infos []lineInfo 106 } 107 108 // Name returns the file name of file f as registered with AddFile. 109 func (f *File) Name() string { 110 return f.name 111 } 112 113 // Base returns the base offset of file f as registered with AddFile. 114 func (f *File) Base() int { 115 return f.base 116 } 117 118 // Size returns the size of file f as registered with AddFile. 119 func (f *File) Size() int { 120 return f.size 121 } 122 123 // LineCount returns the number of lines in file f. 124 func (f *File) LineCount() int { 125 f.mutex.Lock() 126 n := len(f.lines) 127 f.mutex.Unlock() 128 return n 129 } 130 131 // AddLine adds the line offset for a new line. 132 // The line offset must be larger than the offset for the previous line 133 // and smaller than the file size; otherwise the line offset is ignored. 134 // 135 func (f *File) AddLine(offset int) { 136 f.mutex.Lock() 137 if i := len(f.lines); (i == 0 || f.lines[i-1] < offset) && offset < f.size { 138 f.lines = append(f.lines, offset) 139 } 140 f.mutex.Unlock() 141 } 142 143 // MergeLine merges a line with the following line. It is akin to replacing 144 // the newline character at the end of the line with a space (to not change the 145 // remaining offsets). To obtain the line number, consult e.g. Position.Line. 146 // MergeLine will panic if given an invalid line number. 147 // 148 func (f *File) MergeLine(line int) { 149 if line < 1 { 150 panic("illegal line number (line numbering starts at 1)") 151 } 152 f.mutex.Lock() 153 defer f.mutex.Unlock() 154 if line >= len(f.lines) { 155 panic("illegal line number") 156 } 157 // To merge the line numbered <line> with the line numbered <line+1>, 158 // we need to remove the entry in lines corresponding to the line 159 // numbered <line+1>. The entry in lines corresponding to the line 160 // numbered <line+1> is located at index <line>, since indices in lines 161 // are 0-based and line numbers are 1-based. 162 copy(f.lines[line:], f.lines[line+1:]) 163 f.lines = f.lines[:len(f.lines)-1] 164 } 165 166 // SetLines sets the line offsets for a file and reports whether it succeeded. 167 // The line offsets are the offsets of the first character of each line; 168 // for instance for the content "ab\nc\n" the line offsets are {0, 3}. 169 // An empty file has an empty line offset table. 170 // Each line offset must be larger than the offset for the previous line 171 // and smaller than the file size; otherwise SetLines fails and returns 172 // false. 173 // Callers must not mutate the provided slice after SetLines returns. 174 // 175 func (f *File) SetLines(lines []int) bool { 176 // verify validity of lines table 177 size := f.size 178 for i, offset := range lines { 179 if i > 0 && offset <= lines[i-1] || size <= offset { 180 return false 181 } 182 } 183 184 // set lines table 185 f.mutex.Lock() 186 f.lines = lines 187 f.mutex.Unlock() 188 return true 189 } 190 191 // SetLinesForContent sets the line offsets for the given file content. 192 // It ignores position-altering //line comments. 193 func (f *File) SetLinesForContent(content []byte) { 194 var lines []int 195 line := 0 196 for offset, b := range content { 197 if line >= 0 { 198 lines = append(lines, line) 199 } 200 line = -1 201 if b == '\n' { 202 line = offset + 1 203 } 204 } 205 206 // set lines table 207 f.mutex.Lock() 208 f.lines = lines 209 f.mutex.Unlock() 210 } 211 212 // LineStart returns the Pos value of the start of the specified line. 213 // It ignores any alternative positions set using AddLineColumnInfo. 214 // LineStart panics if the 1-based line number is invalid. 215 func (f *File) LineStart(line int) Pos { 216 if line < 1 { 217 panic("illegal line number (line numbering starts at 1)") 218 } 219 f.mutex.Lock() 220 defer f.mutex.Unlock() 221 if line > len(f.lines) { 222 panic("illegal line number") 223 } 224 return Pos(f.base + f.lines[line-1]) 225 } 226 227 // A lineInfo object describes alternative file, line, and column 228 // number information (such as provided via a //line directive) 229 // for a given file offset. 230 type lineInfo struct { 231 // fields are exported to make them accessible to gob 232 Offset int 233 Filename string 234 Line, Column int 235 } 236 237 // AddLineInfo is like AddLineColumnInfo with a column = 1 argument. 238 // It is here for backward-compatibility for code prior to Go 1.11. 239 // 240 func (f *File) AddLineInfo(offset int, filename string, line int) { 241 f.AddLineColumnInfo(offset, filename, line, 1) 242 } 243 244 // AddLineColumnInfo adds alternative file, line, and column number 245 // information for a given file offset. The offset must be larger 246 // than the offset for the previously added alternative line info 247 // and smaller than the file size; otherwise the information is 248 // ignored. 249 // 250 // AddLineColumnInfo is typically used to register alternative position 251 // information for line directives such as //line filename:line:column. 252 // 253 func (f *File) AddLineColumnInfo(offset int, filename string, line, column int) { 254 f.mutex.Lock() 255 if i := len(f.infos); i == 0 || f.infos[i-1].Offset < offset && offset < f.size { 256 f.infos = append(f.infos, lineInfo{offset, filename, line, column}) 257 } 258 f.mutex.Unlock() 259 } 260 261 // Pos returns the Pos value for the given file offset; 262 // the offset must be <= f.Size(). 263 // f.Pos(f.Offset(p)) == p. 264 // 265 func (f *File) Pos(offset int) Pos { 266 if offset > f.size { 267 panic("illegal file offset") 268 } 269 return Pos(f.base + offset) 270 } 271 272 // Offset returns the offset for the given file position p; 273 // p must be a valid Pos value in that file. 274 // f.Offset(f.Pos(offset)) == offset. 275 // 276 func (f *File) Offset(p Pos) int { 277 if int(p) < f.base || int(p) > f.base+f.size { 278 panic("illegal Pos value") 279 } 280 return int(p) - f.base 281 } 282 283 // Line returns the line number for the given file position p; 284 // p must be a Pos value in that file or NoPos. 285 // 286 func (f *File) Line(p Pos) int { 287 return f.Position(p).Line 288 } 289 290 func searchLineInfos(a []lineInfo, x int) int { 291 return sort.Search(len(a), func(i int) bool { return a[i].Offset > x }) - 1 292 } 293 294 // unpack returns the filename and line and column number for a file offset. 295 // If adjusted is set, unpack will return the filename and line information 296 // possibly adjusted by //line comments; otherwise those comments are ignored. 297 // 298 func (f *File) unpack(offset int, adjusted bool) (filename string, line, column int) { 299 f.mutex.Lock() 300 defer f.mutex.Unlock() 301 filename = f.name 302 if i := searchInts(f.lines, offset); i >= 0 { 303 line, column = i+1, offset-f.lines[i]+1 304 } 305 if adjusted && len(f.infos) > 0 { 306 // few files have extra line infos 307 if i := searchLineInfos(f.infos, offset); i >= 0 { 308 alt := &f.infos[i] 309 filename = alt.Filename 310 if i := searchInts(f.lines, alt.Offset); i >= 0 { 311 // i+1 is the line at which the alternative position was recorded 312 d := line - (i + 1) // line distance from alternative position base 313 line = alt.Line + d 314 if alt.Column == 0 { 315 // alternative column is unknown => relative column is unknown 316 // (the current specification for line directives requires 317 // this to apply until the next PosBase/line directive, 318 // not just until the new newline) 319 column = 0 320 } else if d == 0 { 321 // the alternative position base is on the current line 322 // => column is relative to alternative column 323 column = alt.Column + (offset - alt.Offset) 324 } 325 } 326 } 327 } 328 return 329 } 330 331 func (f *File) position(p Pos, adjusted bool) (pos Position) { 332 offset := int(p) - f.base 333 pos.Offset = offset 334 pos.Filename, pos.Line, pos.Column = f.unpack(offset, adjusted) 335 return 336 } 337 338 // PositionFor returns the Position value for the given file position p. 339 // If adjusted is set, the position may be adjusted by position-altering 340 // //line comments; otherwise those comments are ignored. 341 // p must be a Pos value in f or NoPos. 342 // 343 func (f *File) PositionFor(p Pos, adjusted bool) (pos Position) { 344 if p != NoPos { 345 if int(p) < f.base || int(p) > f.base+f.size { 346 panic("illegal Pos value") 347 } 348 pos = f.position(p, adjusted) 349 } 350 return 351 } 352 353 // Position returns the Position value for the given file position p. 354 // Calling f.Position(p) is equivalent to calling f.PositionFor(p, true). 355 // 356 func (f *File) Position(p Pos) (pos Position) { 357 return f.PositionFor(p, true) 358 } 359 360 // ----------------------------------------------------------------------------- 361 // FileSet 362 363 // A FileSet represents a set of source files. 364 // Methods of file sets are synchronized; multiple goroutines 365 // may invoke them concurrently. 366 // 367 type FileSet struct { 368 mutex sync.RWMutex // protects the file set 369 base int // base offset for the next file 370 files []*File // list of files in the order added to the set 371 last *File // cache of last file looked up 372 } 373 374 // NewFileSet creates a new file set. 375 func NewFileSet() *FileSet { 376 return &FileSet{ 377 base: 1, // 0 == NoPos 378 } 379 } 380 381 // Base returns the minimum base offset that must be provided to 382 // AddFile when adding the next file. 383 // 384 func (s *FileSet) Base() int { 385 s.mutex.RLock() 386 b := s.base 387 s.mutex.RUnlock() 388 return b 389 390 } 391 392 // AddFile adds a new file with a given filename, base offset, and file size 393 // to the file set s and returns the file. Multiple files may have the same 394 // name. The base offset must not be smaller than the FileSet's Base(), and 395 // size must not be negative. As a special case, if a negative base is provided, 396 // the current value of the FileSet's Base() is used instead. 397 // 398 // Adding the file will set the file set's Base() value to base + size + 1 399 // as the minimum base value for the next file. The following relationship 400 // exists between a Pos value p for a given file offset offs: 401 // 402 // int(p) = base + offs 403 // 404 // with offs in the range [0, size] and thus p in the range [base, base+size]. 405 // For convenience, File.Pos may be used to create file-specific position 406 // values from a file offset. 407 // 408 func (s *FileSet) AddFile(filename string, base, size int) *File { 409 s.mutex.Lock() 410 defer s.mutex.Unlock() 411 if base < 0 { 412 base = s.base 413 } 414 if base < s.base || size < 0 { 415 panic("illegal base or size") 416 } 417 // base >= s.base && size >= 0 418 f := &File{set: s, name: filename, base: base, size: size, lines: []int{0}} 419 base += size + 1 // +1 because EOF also has a position 420 if base < 0 { 421 panic("token.Pos offset overflow (> 2G of source code in file set)") 422 } 423 // add the file to the file set 424 s.base = base 425 s.files = append(s.files, f) 426 s.last = f 427 return f 428 } 429 430 // Iterate calls f for the files in the file set in the order they were added 431 // until f returns false. 432 // 433 func (s *FileSet) Iterate(f func(*File) bool) { 434 for i := 0; ; i++ { 435 var file *File 436 s.mutex.RLock() 437 if i < len(s.files) { 438 file = s.files[i] 439 } 440 s.mutex.RUnlock() 441 if file == nil || !f(file) { 442 break 443 } 444 } 445 } 446 447 func searchFiles(a []*File, x int) int { 448 return sort.Search(len(a), func(i int) bool { return a[i].base > x }) - 1 449 } 450 451 func (s *FileSet) file(p Pos) *File { 452 s.mutex.RLock() 453 // common case: p is in last file 454 if f := s.last; f != nil && f.base <= int(p) && int(p) <= f.base+f.size { 455 s.mutex.RUnlock() 456 return f 457 } 458 // p is not in last file - search all files 459 if i := searchFiles(s.files, int(p)); i >= 0 { 460 f := s.files[i] 461 // f.base <= int(p) by definition of searchFiles 462 if int(p) <= f.base+f.size { 463 s.mutex.RUnlock() 464 s.mutex.Lock() 465 s.last = f // race is ok - s.last is only a cache 466 s.mutex.Unlock() 467 return f 468 } 469 } 470 s.mutex.RUnlock() 471 return nil 472 } 473 474 // File returns the file that contains the position p. 475 // If no such file is found (for instance for p == NoPos), 476 // the result is nil. 477 // 478 func (s *FileSet) File(p Pos) (f *File) { 479 if p != NoPos { 480 f = s.file(p) 481 } 482 return 483 } 484 485 // PositionFor converts a Pos p in the fileset into a Position value. 486 // If adjusted is set, the position may be adjusted by position-altering 487 // //line comments; otherwise those comments are ignored. 488 // p must be a Pos value in s or NoPos. 489 // 490 func (s *FileSet) PositionFor(p Pos, adjusted bool) (pos Position) { 491 if p != NoPos { 492 if f := s.file(p); f != nil { 493 return f.position(p, adjusted) 494 } 495 } 496 return 497 } 498 499 // Position converts a Pos p in the fileset into a Position value. 500 // Calling s.Position(p) is equivalent to calling s.PositionFor(p, true). 501 // 502 func (s *FileSet) Position(p Pos) (pos Position) { 503 return s.PositionFor(p, true) 504 } 505 506 // ----------------------------------------------------------------------------- 507 // Helper functions 508 509 func searchInts(a []int, x int) int { 510 // This function body is a manually inlined version of: 511 // 512 // return sort.Search(len(a), func(i int) bool { return a[i] > x }) - 1 513 // 514 // With better compiler optimizations, this may not be needed in the 515 // future, but at the moment this change improves the go/printer 516 // benchmark performance by ~30%. This has a direct impact on the 517 // speed of gofmt and thus seems worthwhile (2011-04-29). 518 // TODO(gri): Remove this when compilers have caught up. 519 i, j := 0, len(a) 520 for i < j { 521 h := i + (j-i)/2 // avoid overflow when computing h 522 // i ≤ h < j 523 if a[h] <= x { 524 i = h + 1 525 } else { 526 j = h 527 } 528 } 529 return i - 1 530 } 531