...
Run Format

Source file src/go/token/position.go

Documentation: go/token

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

View as plain text