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 <= 0 { 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 // A lineInfo object describes alternative file, line, and column 213 // number information (such as provided via a //line directive) 214 // for a given file offset. 215 type lineInfo struct { 216 // fields are exported to make them accessible to gob 217 Offset int 218 Filename string 219 Line, Column int 220 } 221 222 // AddLineInfo is like AddLineColumnInfo with a column = 1 argument. 223 // It is here for backward-compatibility for code prior to Go 1.11. 224 // 225 func (f *File) AddLineInfo(offset int, filename string, line int) { 226 f.AddLineColumnInfo(offset, filename, line, 1) 227 } 228 229 // AddLineColumnInfo adds alternative file, line, and column number 230 // information for a given file offset. The offset must be larger 231 // than the offset for the previously added alternative line info 232 // and smaller than the file size; otherwise the information is 233 // ignored. 234 // 235 // AddLineColumnInfo is typically used to register alternative position 236 // information for line directives such as //line filename:line:column. 237 // 238 func (f *File) AddLineColumnInfo(offset int, filename string, line, column int) { 239 f.mutex.Lock() 240 if i := len(f.infos); i == 0 || f.infos[i-1].Offset < offset && offset < f.size { 241 f.infos = append(f.infos, lineInfo{offset, filename, line, column}) 242 } 243 f.mutex.Unlock() 244 } 245 246 // Pos returns the Pos value for the given file offset; 247 // the offset must be <= f.Size(). 248 // f.Pos(f.Offset(p)) == p. 249 // 250 func (f *File) Pos(offset int) Pos { 251 if offset > f.size { 252 panic("illegal file offset") 253 } 254 return Pos(f.base + offset) 255 } 256 257 // Offset returns the offset for the given file position p; 258 // p must be a valid Pos value in that file. 259 // f.Offset(f.Pos(offset)) == offset. 260 // 261 func (f *File) Offset(p Pos) int { 262 if int(p) < f.base || int(p) > f.base+f.size { 263 panic("illegal Pos value") 264 } 265 return int(p) - f.base 266 } 267 268 // Line returns the line number for the given file position p; 269 // p must be a Pos value in that file or NoPos. 270 // 271 func (f *File) Line(p Pos) int { 272 return f.Position(p).Line 273 } 274 275 func searchLineInfos(a []lineInfo, x int) int { 276 return sort.Search(len(a), func(i int) bool { return a[i].Offset > x }) - 1 277 } 278 279 // unpack returns the filename and line and column number for a file offset. 280 // If adjusted is set, unpack will return the filename and line information 281 // possibly adjusted by //line comments; otherwise those comments are ignored. 282 // 283 func (f *File) unpack(offset int, adjusted bool) (filename string, line, column int) { 284 f.mutex.Lock() 285 defer f.mutex.Unlock() 286 filename = f.name 287 if i := searchInts(f.lines, offset); i >= 0 { 288 line, column = i+1, offset-f.lines[i]+1 289 } 290 if adjusted && len(f.infos) > 0 { 291 // few files have extra line infos 292 if i := searchLineInfos(f.infos, offset); i >= 0 { 293 alt := &f.infos[i] 294 filename = alt.Filename 295 if i := searchInts(f.lines, alt.Offset); i >= 0 { 296 // i+1 is the line at which the alternative position was recorded 297 d := line - (i + 1) // line distance from alternative position base 298 line = alt.Line + d 299 if alt.Column == 0 { 300 // alternative column is unknown => relative column is unknown 301 // (the current specification for line directives requires 302 // this to apply until the next PosBase/line directive, 303 // not just until the new newline) 304 column = 0 305 } else if d == 0 { 306 // the alternative position base is on the current line 307 // => column is relative to alternative column 308 column = alt.Column + (offset - alt.Offset) 309 } 310 } 311 } 312 } 313 return 314 } 315 316 func (f *File) position(p Pos, adjusted bool) (pos Position) { 317 offset := int(p) - f.base 318 pos.Offset = offset 319 pos.Filename, pos.Line, pos.Column = f.unpack(offset, adjusted) 320 return 321 } 322 323 // PositionFor returns the Position value for the given file position p. 324 // If adjusted is set, the position may be adjusted by position-altering 325 // //line comments; otherwise those comments are ignored. 326 // p must be a Pos value in f or NoPos. 327 // 328 func (f *File) PositionFor(p Pos, adjusted bool) (pos Position) { 329 if p != NoPos { 330 if int(p) < f.base || int(p) > f.base+f.size { 331 panic("illegal Pos value") 332 } 333 pos = f.position(p, adjusted) 334 } 335 return 336 } 337 338 // Position returns the Position value for the given file position p. 339 // Calling f.Position(p) is equivalent to calling f.PositionFor(p, true). 340 // 341 func (f *File) Position(p Pos) (pos Position) { 342 return f.PositionFor(p, true) 343 } 344 345 // ----------------------------------------------------------------------------- 346 // FileSet 347 348 // A FileSet represents a set of source files. 349 // Methods of file sets are synchronized; multiple goroutines 350 // may invoke them concurrently. 351 // 352 type FileSet struct { 353 mutex sync.RWMutex // protects the file set 354 base int // base offset for the next file 355 files []*File // list of files in the order added to the set 356 last *File // cache of last file looked up 357 } 358 359 // NewFileSet creates a new file set. 360 func NewFileSet() *FileSet { 361 return &FileSet{ 362 base: 1, // 0 == NoPos 363 } 364 } 365 366 // Base returns the minimum base offset that must be provided to 367 // AddFile when adding the next file. 368 // 369 func (s *FileSet) Base() int { 370 s.mutex.RLock() 371 b := s.base 372 s.mutex.RUnlock() 373 return b 374 375 } 376 377 // AddFile adds a new file with a given filename, base offset, and file size 378 // to the file set s and returns the file. Multiple files may have the same 379 // name. The base offset must not be smaller than the FileSet's Base(), and 380 // size must not be negative. As a special case, if a negative base is provided, 381 // the current value of the FileSet's Base() is used instead. 382 // 383 // Adding the file will set the file set's Base() value to base + size + 1 384 // as the minimum base value for the next file. The following relationship 385 // exists between a Pos value p for a given file offset offs: 386 // 387 // int(p) = base + offs 388 // 389 // with offs in the range [0, size] and thus p in the range [base, base+size]. 390 // For convenience, File.Pos may be used to create file-specific position 391 // values from a file offset. 392 // 393 func (s *FileSet) AddFile(filename string, base, size int) *File { 394 s.mutex.Lock() 395 defer s.mutex.Unlock() 396 if base < 0 { 397 base = s.base 398 } 399 if base < s.base || size < 0 { 400 panic("illegal base or size") 401 } 402 // base >= s.base && size >= 0 403 f := &File{set: s, name: filename, base: base, size: size, lines: []int{0}} 404 base += size + 1 // +1 because EOF also has a position 405 if base < 0 { 406 panic("token.Pos offset overflow (> 2G of source code in file set)") 407 } 408 // add the file to the file set 409 s.base = base 410 s.files = append(s.files, f) 411 s.last = f 412 return f 413 } 414 415 // Iterate calls f for the files in the file set in the order they were added 416 // until f returns false. 417 // 418 func (s *FileSet) Iterate(f func(*File) bool) { 419 for i := 0; ; i++ { 420 var file *File 421 s.mutex.RLock() 422 if i < len(s.files) { 423 file = s.files[i] 424 } 425 s.mutex.RUnlock() 426 if file == nil || !f(file) { 427 break 428 } 429 } 430 } 431 432 func searchFiles(a []*File, x int) int { 433 return sort.Search(len(a), func(i int) bool { return a[i].base > x }) - 1 434 } 435 436 func (s *FileSet) file(p Pos) *File { 437 s.mutex.RLock() 438 // common case: p is in last file 439 if f := s.last; f != nil && f.base <= int(p) && int(p) <= f.base+f.size { 440 s.mutex.RUnlock() 441 return f 442 } 443 // p is not in last file - search all files 444 if i := searchFiles(s.files, int(p)); i >= 0 { 445 f := s.files[i] 446 // f.base <= int(p) by definition of searchFiles 447 if int(p) <= f.base+f.size { 448 s.mutex.RUnlock() 449 s.mutex.Lock() 450 s.last = f // race is ok - s.last is only a cache 451 s.mutex.Unlock() 452 return f 453 } 454 } 455 s.mutex.RUnlock() 456 return nil 457 } 458 459 // File returns the file that contains the position p. 460 // If no such file is found (for instance for p == NoPos), 461 // the result is nil. 462 // 463 func (s *FileSet) File(p Pos) (f *File) { 464 if p != NoPos { 465 f = s.file(p) 466 } 467 return 468 } 469 470 // PositionFor converts a Pos p in the fileset into a Position value. 471 // If adjusted is set, the position may be adjusted by position-altering 472 // //line comments; otherwise those comments are ignored. 473 // p must be a Pos value in s or NoPos. 474 // 475 func (s *FileSet) PositionFor(p Pos, adjusted bool) (pos Position) { 476 if p != NoPos { 477 if f := s.file(p); f != nil { 478 return f.position(p, adjusted) 479 } 480 } 481 return 482 } 483 484 // Position converts a Pos p in the fileset into a Position value. 485 // Calling s.Position(p) is equivalent to calling s.PositionFor(p, true). 486 // 487 func (s *FileSet) Position(p Pos) (pos Position) { 488 return s.PositionFor(p, true) 489 } 490 491 // ----------------------------------------------------------------------------- 492 // Helper functions 493 494 func searchInts(a []int, x int) int { 495 // This function body is a manually inlined version of: 496 // 497 // return sort.Search(len(a), func(i int) bool { return a[i] > x }) - 1 498 // 499 // With better compiler optimizations, this may not be needed in the 500 // future, but at the moment this change improves the go/printer 501 // benchmark performance by ~30%. This has a direct impact on the 502 // speed of gofmt and thus seems worthwhile (2011-04-29). 503 // TODO(gri): Remove this when compilers have caught up. 504 i, j := 0, len(a) 505 for i < j { 506 h := i + (j-i)/2 // avoid overflow when computing h 507 // i ≤ h < j 508 if a[h] <= x { 509 i = h + 1 510 } else { 511 j = h 512 } 513 } 514 return i - 1 515 } 516