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