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.
13 // -----------------------------------------------------------------------------
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.
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)
27 // IsValid reports whether the position is valid.
28 func (pos
*Position
) IsValid() bool { return pos
.Line
> 0 }
30 // String returns a string in one of several forms:
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
37 func (pos Position
) String() string {
43 s
+= fmt
.Sprintf("%d:%d", pos
.Line
, pos
.Column
)
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.
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
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).
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.
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.
80 // IsValid reports whether the position is valid.
81 func (p Pos
) IsValid() bool {
85 // -----------------------------------------------------------------------------
88 // A File is a handle for a file belonging to a FileSet.
89 // A File has a name, size, and line offset table.
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
97 // lines and infos are protected by mutex
99 lines
[]int // lines contains the offset of the first character for each line (the first entry is always 0)
103 // Name returns the file name of file f as registered with AddFile.
104 func (f
*File
) Name() string {
108 // Base returns the base offset of file f as registered with AddFile.
109 func (f
*File
) Base() int {
113 // Size returns the size of file f as registered with AddFile.
114 func (f
*File
) Size() int {
118 // LineCount returns the number of lines in file f.
119 func (f
*File
) LineCount() int {
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.
130 func (f
*File
) AddLine(offset
int) {
132 if i
:= len(f
.lines
); (i
== 0 || f
.lines
[i
-1] < offset
) && offset
< f
.size
{
133 f
.lines
= append(f
.lines
, offset
)
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.
143 func (f
*File
) MergeLine(line
int) {
145 panic("illegal line number (line numbering starts at 1)")
148 defer f
.mutex
.Unlock()
149 if line
>= len(f
.lines
) {
150 panic("illegal line number")
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]
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
168 // Callers must not mutate the provided slice after SetLines returns.
170 func (f
*File
) SetLines(lines
[]int) bool {
171 // verify validity of lines table
173 for i
, offset
:= range lines
{
174 if i
> 0 && offset
<= lines
[i
-1] || size
<= offset
{
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) {
191 for offset
, b
:= range content
{
193 lines
= append(lines
, line
)
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
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.
222 // AddLineInfo is typically used to register alternative position
223 // information for //line filename:line comments in source files.
225 func (f
*File
) AddLineInfo(offset
int, filename
string, line
int) {
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
})
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.
237 func (f
*File
) Pos(offset
int) Pos
{
239 panic("illegal file offset")
241 return Pos(f
.base
+ offset
)
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.
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")
252 return int(p
) - f
.base
255 // Line returns the line number for the given file position p;
256 // p must be a Pos value in that file or NoPos.
258 func (f
*File
) Line(p Pos
) int {
259 return f
.Position(p
).Line
262 func searchLineInfos(a
[]lineInfo
, x
int) int {
263 return sort
.Search(len(a
), func(i
int) bool { return a
[i
].Offset
> x
}) - 1
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.
270 func (f
*File
) unpack(offset
int, adjusted
bool) (filename
string, line
, column
int) {
272 defer f
.mutex
.Unlock()
274 if i
:= searchInts(f
.lines
, offset
); i
>= 0 {
275 line
, column
= i
+1, offset
-f
.lines
[i
]+1
277 if adjusted
&& len(f
.infos
) > 0 {
278 // almost no files have extra line infos
279 if i
:= searchLineInfos(f
.infos
, offset
); i
>= 0 {
281 filename
= alt
.Filename
282 if i
:= searchInts(f
.lines
, alt
.Offset
); i
>= 0 {
283 line
+= alt
.Line
- i
- 1
290 func (f
*File
) position(p Pos
, adjusted
bool) (pos Position
) {
291 offset
:= int(p
) - f
.base
293 pos
.Filename
, pos
.Line
, pos
.Column
= f
.unpack(offset
, adjusted
)
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.
302 func (f
*File
) PositionFor(p Pos
, adjusted
bool) (pos Position
) {
304 if int(p
) < f
.base ||
int(p
) > f
.base
+f
.size
{
305 panic("illegal Pos value")
307 pos
= f
.position(p
, adjusted
)
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).
315 func (f
*File
) Position(p Pos
) (pos Position
) {
316 return f
.PositionFor(p
, true)
319 // -----------------------------------------------------------------------------
322 // A FileSet represents a set of source files.
323 // Methods of file sets are synchronized; multiple goroutines
324 // may invoke them concurrently.
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
333 // NewFileSet creates a new file set.
334 func NewFileSet() *FileSet
{
336 base
: 1, // 0 == NoPos
340 // Base returns the minimum base offset that must be provided to
341 // AddFile when adding the next file.
343 func (s
*FileSet
) Base() int {
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.
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:
361 // int(p) = base + offs
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.
367 func (s
*FileSet
) AddFile(filename
string, base
, size
int) *File
{
369 defer s
.mutex
.Unlock()
373 if base
< s
.base || size
< 0 {
374 panic("illegal base or size")
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
380 panic("token.Pos offset overflow (> 2G of source code in file set)")
382 // add the file to the file set
384 s
.files
= append(s
.files
, f
)
389 // Iterate calls f for the files in the file set in the order they were added
390 // until f returns false.
392 func (s
*FileSet
) Iterate(f
func(*File
) bool) {
396 if i
< len(s
.files
) {
400 if file
== nil ||
!f(file
) {
406 func searchFiles(a
[]*File
, x
int) int {
407 return sort
.Search(len(a
), func(i
int) bool { return a
[i
].base
> x
}) - 1
410 func (s
*FileSet
) file(p Pos
) *File
{
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
{
417 // p is not in last file - search all files
418 if i
:= searchFiles(s
.files
, int(p
)); i
>= 0 {
420 // f.base <= int(p) by definition of searchFiles
421 if int(p
) <= f
.base
+f
.size
{
424 s
.last
= f
// race is ok - s.last is only a cache
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.
437 func (s
*FileSet
) File(p Pos
) (f
*File
) {
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.
449 func (s
*FileSet
) PositionFor(p Pos
, adjusted
bool) (pos Position
) {
451 if f
:= s
.file(p
); f
!= nil {
452 return f
.position(p
, adjusted
)
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).
461 func (s
*FileSet
) Position(p Pos
) (pos Position
) {
462 return s
.PositionFor(p
, true)
465 // -----------------------------------------------------------------------------
468 func searchInts(a
[]int, x
int) int {
469 // This function body is a manually inlined version of:
471 // return sort.Search(len(a), func(i int) bool { return a[i] > x }) - 1
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.
480 h
:= i
+ (j
-i
)/2 // avoid overflow when computing h