libgo/go/go/token/position.go

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