diff options
Diffstat (limited to 'src/pkg/go/token')
| -rw-r--r-- | src/pkg/go/token/Makefile | 3 | ||||
| -rw-r--r-- | src/pkg/go/token/position.go | 409 | ||||
| -rw-r--r-- | src/pkg/go/token/position_test.go | 158 | ||||
| -rw-r--r-- | src/pkg/go/token/token.go | 41 |
4 files changed, 570 insertions, 41 deletions
diff --git a/src/pkg/go/token/Makefile b/src/pkg/go/token/Makefile index 629196c5d..4a4e64dc8 100644 --- a/src/pkg/go/token/Makefile +++ b/src/pkg/go/token/Makefile @@ -2,10 +2,11 @@ # Use of this source code is governed by a BSD-style # license that can be found in the LICENSE file. -include ../../../Make.$(GOARCH) +include ../../../Make.inc TARG=go/token GOFILES=\ + position.go\ token.go\ include ../../../Make.pkg diff --git a/src/pkg/go/token/position.go b/src/pkg/go/token/position.go new file mode 100644 index 000000000..0044a0ed7 --- /dev/null +++ b/src/pkg/go/token/position.go @@ -0,0 +1,409 @@ +// Copyright 2010 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// TODO(gri) consider making this a separate package outside the go directory. + +package token + +import ( + "fmt" + "sort" + "sync" +) + + +// Position describes an arbitrary source position +// including the file, line, and column location. +// A Position is valid if the line number is > 0. +// +type Position struct { + Filename string // filename, if any + Offset int // offset, starting at 0 + Line int // line number, starting at 1 + Column int // column number, starting at 1 (character count) +} + + +// IsValid returns true if the position is valid. +func (pos *Position) IsValid() bool { return pos.Line > 0 } + + +// String returns a string in one of several forms: +// +// file:line:column valid position with file name +// line:column valid position without file name +// file invalid position with file name +// - invalid position without file name +// +func (pos Position) String() string { + s := pos.Filename + if pos.IsValid() { + if s != "" { + s += ":" + } + s += fmt.Sprintf("%d:%d", pos.Line, pos.Column) + } + if s == "" { + s = "-" + } + return s +} + + +// Pos is a compact encoding of a source position within a file set. +// It can be converted into a Position for a more convenient, but much +// larger, representation. +// +// The Pos value for a given file is a number in the range [base, base+size], +// where base and size are specified when adding the file to the file set via +// AddFile. +// +// To create the Pos value for a specific source offset, first add +// the respective file to the current file set (via FileSet.AddFile) +// and then call File.Pos(offset) for that file. Given a Pos value p +// for a specific file set fset, the corresponding Position value is +// obtained by calling fset.Position(p). +// +// Pos values can be compared directly with the usual comparison operators: +// If two Pos values p and q are in the same file, comparing p and q is +// equivalent to comparing the respective source file offsets. If p and q +// are in different files, p < q is true if the file implied by p was added +// to the respective file set before the file implied by q. +// +type Pos int + + +// The zero value for Pos is NoPos; there is no file and line information +// associated with it, and NoPos().IsValid() is false. NoPos is always +// smaller than any other Pos value. The corresponding Position value +// for NoPos is the zero value for Position. +// +const NoPos Pos = 0 + + +// IsValid returns true if the position is valid. +func (p Pos) IsValid() bool { + return p != NoPos +} + + +func searchFiles(a []*File, x int) int { + return sort.Search(len(a), func(i int) bool { return a[i].base > x }) - 1 +} + + +func (s *FileSet) file(p Pos) *File { + if i := searchFiles(s.files, int(p)); i >= 0 { + f := s.files[i] + // f.base <= int(p) by definition of searchFiles + if int(p) <= f.base+f.size { + return f + } + } + return nil +} + + +// File returns the file which contains the position p. +// If no such file is found (for instance for p == NoPos), +// the result is nil. +// +func (s *FileSet) File(p Pos) (f *File) { + if p != NoPos { + s.mutex.RLock() + f = s.file(p) + s.mutex.RUnlock() + } + return +} + + +func (f *File) position(p Pos) (pos Position) { + offset := int(p) - f.base + pos.Offset = offset + pos.Filename, pos.Line, pos.Column = f.info(offset) + return +} + + +// Position converts a Pos in the fileset into a general Position. +func (s *FileSet) Position(p Pos) (pos Position) { + if p != NoPos { + // TODO(gri) consider optimizing the case where p + // is in the last file addded, or perhaps + // looked at - will eliminate one level + // of search + s.mutex.RLock() + if f := s.file(p); f != nil { + pos = f.position(p) + } + s.mutex.RUnlock() + } + return +} + + +type lineInfo struct { + offset int + filename string + line int +} + + +// AddLineInfo adds alternative file and line number information for +// a given file offset. The offset must be larger than the offset for +// the previously added alternative line info and not larger than the +// file size; otherwise the information is ignored. +// +// AddLineInfo is typically used to register alternative position +// information for //line filename:line comments in source files. +// +func (f *File) AddLineInfo(offset int, filename string, line int) { + f.set.mutex.Lock() + if i := len(f.infos); i == 0 || f.infos[i-1].offset < offset && offset <= f.size { + f.infos = append(f.infos, lineInfo{offset, filename, line}) + } + f.set.mutex.Unlock() +} + + +// A File is a handle for a file belonging to a FileSet. +// A File has a name, size, and line offset table. +// +type File struct { + set *FileSet + name string // file name as provided to AddFile + base int // Pos value range for this file is [base...base+size] + size int // file size as provided to AddFile + + // lines and infos are protected by set.mutex + lines []int + infos []lineInfo +} + + +// Name returns the file name of file f as registered with AddFile. +func (f *File) Name() string { + return f.name +} + + +// Base returns the base offset of file f as registered with AddFile. +func (f *File) Base() int { + return f.base +} + + +// Size returns the size of file f as registered with AddFile. +func (f *File) Size() int { + return f.size +} + + +// LineCount returns the number of lines in file f. +func (f *File) LineCount() int { + f.set.mutex.RLock() + n := len(f.lines) + f.set.mutex.RUnlock() + return n +} + + +// AddLine adds the line offset for a new line. +// The line offset must be larger than the offset for the previous line +// and not larger than the file size; otherwise the line offset is ignored. +// +func (f *File) AddLine(offset int) { + f.set.mutex.Lock() + if i := len(f.lines); (i == 0 || f.lines[i-1] < offset) && offset <= f.size { + f.lines = append(f.lines, offset) + } + f.set.mutex.Unlock() +} + + +// SetLines sets all line offsets for a file and returns true if successful. +// Each line offset must be larger than the offset for the previous line +// and not larger than the file size; otherwise the SetLines fails and returns +// false. +// +func (f *File) SetLines(lines []int) bool { + // verify validity of lines table + size := f.size + for i, offset := range lines { + if i > 0 && offset <= lines[i-1] || size < offset { + return false + } + } + + // set lines table + f.set.mutex.Lock() + f.lines = lines + f.set.mutex.Unlock() + return true +} + + +// Pos returns the Pos value for the given file offset; +// the offset must be <= f.Size(). +// f.Pos(f.Offset(p)) == p. +// +func (f *File) Pos(offset int) Pos { + if offset > f.size { + panic("illegal file offset") + } + return Pos(f.base + offset) +} + + +// Offset returns the offset for the given file position p; +// p must be a valid Pos value in that file. +// f.Offset(f.Pos(offset)) == offset. +// +func (f *File) Offset(p Pos) int { + if int(p) < f.base || int(p) > f.base+f.size { + panic("illegal Pos value") + } + return int(p) - f.base +} + + +// Line returns the line number for the given file position p; +// p must be a Pos value in that file or NoPos. +// +func (f *File) Line(p Pos) int { + // TODO(gri) this can be implemented much more efficiently + return f.Position(p).Line +} + + +// Position returns the Position value for the given file position p; +// p must be a Pos value in that file or NoPos. +// +func (f *File) Position(p Pos) (pos Position) { + if p != NoPos { + if int(p) < f.base || int(p) > f.base+f.size { + panic("illegal Pos value") + } + pos = f.position(p) + } + return +} + + +func searchUints(a []int, x int) int { + return sort.Search(len(a), func(i int) bool { return a[i] > x }) - 1 +} + + +func searchLineInfos(a []lineInfo, x int) int { + return sort.Search(len(a), func(i int) bool { return a[i].offset > x }) - 1 +} + + +// info returns the file name, line, and column number for a file offset. +func (f *File) info(offset int) (filename string, line, column int) { + filename = f.name + if i := searchUints(f.lines, offset); i >= 0 { + line, column = i+1, offset-f.lines[i]+1 + } + if i := searchLineInfos(f.infos, offset); i >= 0 { + alt := &f.infos[i] + filename = alt.filename + if i := searchUints(f.lines, alt.offset); i >= 0 { + line += alt.line - i - 1 + } + } + return +} + + +// A FileSet represents a set of source files. +// Methods of file sets are synchronized; multiple goroutines +// may invoke them concurrently. +// +type FileSet struct { + mutex sync.RWMutex // protects the file set + base int // base offset for the next file + files []*File // list of files in the order added to the set + index map[*File]int // file -> files index for quick lookup +} + + +// NewFileSet creates a new file set. +func NewFileSet() *FileSet { + s := new(FileSet) + s.base = 1 // 0 == NoPos + s.index = make(map[*File]int) + return s +} + + +// Base returns the minimum base offset that must be provided to +// AddFile when adding the next file. +// +func (s *FileSet) Base() int { + s.mutex.RLock() + b := s.base + s.mutex.RUnlock() + return b + +} + + +// AddFile adds a new file with a given filename, base offset, and file size +// to the file set s and returns the file. Multiple files may have the same +// name. The base offset must not be smaller than the FileSet's Base(), and +// size must not be negative. +// +// Adding the file will set the file set's Base() value to base + size + 1 +// as the minimum base value for the next file. The following relationship +// exists between a Pos value p for a given file offset offs: +// +// int(p) = base + offs +// +// with offs in the range [0, size] and thus p in the range [base, base+size]. +// For convenience, File.Pos may be used to create file-specific position +// values from a file offset. +// +func (s *FileSet) AddFile(filename string, base, size int) *File { + s.mutex.Lock() + defer s.mutex.Unlock() + if base < s.base || size < 0 { + panic("illegal base or size") + } + // base >= s.base && size >= 0 + f := &File{s, filename, base, size, []int{0}, nil} + base += size + 1 // +1 because EOF also has a position + if base < 0 { + panic("token.Pos offset overflow (> 2G of source code in file set)") + } + // add the file to the file set + s.base = base + s.index[f] = len(s.files) + s.files = append(s.files, f) + return f +} + + +// Files returns the files added to the file set. +func (s *FileSet) Files() <-chan *File { + ch := make(chan *File) + go func() { + for i := 0; ; i++ { + var f *File + s.mutex.RLock() + if i < len(s.files) { + f = s.files[i] + } + s.mutex.RUnlock() + if f == nil { + break + } + ch <- f + } + close(ch) + }() + return ch +} diff --git a/src/pkg/go/token/position_test.go b/src/pkg/go/token/position_test.go new file mode 100644 index 000000000..1cffcc3c2 --- /dev/null +++ b/src/pkg/go/token/position_test.go @@ -0,0 +1,158 @@ +// Copyright 2010 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package token + +import ( + "fmt" + "testing" +) + + +func checkPos(t *testing.T, msg string, p, q Position) { + if p.Filename != q.Filename { + t.Errorf("%s: expected filename = %q; got %q", msg, q.Filename, p.Filename) + } + if p.Offset != q.Offset { + t.Errorf("%s: expected offset = %d; got %d", msg, q.Offset, p.Offset) + } + if p.Line != q.Line { + t.Errorf("%s: expected line = %d; got %d", msg, q.Line, p.Line) + } + if p.Column != q.Column { + t.Errorf("%s: expected column = %d; got %d", msg, q.Column, p.Column) + } +} + + +func TestNoPos(t *testing.T) { + if NoPos.IsValid() { + t.Errorf("NoPos should not be valid") + } + var fset *FileSet + checkPos(t, "nil NoPos", fset.Position(NoPos), Position{}) + fset = NewFileSet() + checkPos(t, "fset NoPos", fset.Position(NoPos), Position{}) +} + + +var tests = []struct { + filename string + size int + lines []int +}{ + {"a", 0, []int{}}, + {"b", 5, []int{0}}, + {"c", 10, []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}, + {"d", 100, []int{0, 5, 10, 20, 30, 70, 71, 72, 80, 85, 90, 99}}, + {"e", 777, []int{0, 80, 100, 120, 130, 180, 267, 455, 500, 567, 620}}, +} + + +func linecol(lines []int, offs int) (int, int) { + prevLineOffs := 0 + for line, lineOffs := range lines { + if offs < lineOffs { + return line, offs - prevLineOffs + 1 + } + prevLineOffs = lineOffs + } + return len(lines), offs - prevLineOffs + 1 +} + + +func verifyPositions(t *testing.T, fset *FileSet, f *File, lines []int) { + for offs := 0; offs < f.Size(); offs++ { + p := f.Pos(offs) + offs2 := f.Offset(p) + if offs2 != offs { + t.Errorf("%s, Offset: expected offset %d; got %d", f.Name(), offs, offs2) + } + line, col := linecol(lines, offs) + msg := fmt.Sprintf("%s (offs = %d, p = %d)", f.Name(), offs, p) + checkPos(t, msg, f.Position(f.Pos(offs)), Position{f.Name(), offs, line, col}) + checkPos(t, msg, fset.Position(p), Position{f.Name(), offs, line, col}) + } +} + + +func TestPositions(t *testing.T) { + const delta = 7 // a non-zero base offset increment + fset := NewFileSet() + for _, test := range tests { + // add file and verify name and size + f := fset.AddFile(test.filename, fset.Base()+delta, test.size) + if f.Name() != test.filename { + t.Errorf("expected filename %q; got %q", test.filename, f.Name()) + } + if f.Size() != test.size { + t.Errorf("%s: expected file size %d; got %d", f.Name(), test.size, f.Size()) + } + if fset.File(f.Pos(0)) != f { + t.Errorf("%s: f.Pos(0) was not found in f", f.Name()) + } + + // add lines individually and verify all positions + for i, offset := range test.lines { + f.AddLine(offset) + if f.LineCount() != i+1 { + t.Errorf("%s, AddLine: expected line count %d; got %d", f.Name(), i+1, f.LineCount()) + } + // adding the same offset again should be ignored + f.AddLine(offset) + if f.LineCount() != i+1 { + t.Errorf("%s, AddLine: expected unchanged line count %d; got %d", f.Name(), i+1, f.LineCount()) + } + verifyPositions(t, fset, f, test.lines[0:i+1]) + } + + // add lines at once and verify all positions + ok := f.SetLines(test.lines) + if !ok { + t.Errorf("%s: SetLines failed", f.Name()) + } + if f.LineCount() != len(test.lines) { + t.Errorf("%s, SetLines: expected line count %d; got %d", f.Name(), len(test.lines), f.LineCount()) + } + verifyPositions(t, fset, f, test.lines) + } +} + + +func TestLineInfo(t *testing.T) { + fset := NewFileSet() + f := fset.AddFile("foo", fset.Base(), 500) + lines := []int{0, 42, 77, 100, 210, 220, 277, 300, 333, 401} + // add lines individually and provide alternative line information + for _, offs := range lines { + f.AddLine(offs) + f.AddLineInfo(offs, "bar", 42) + } + // verify positions for all offsets + for offs := 0; offs <= f.Size(); offs++ { + p := f.Pos(offs) + _, col := linecol(lines, offs) + msg := fmt.Sprintf("%s (offs = %d, p = %d)", f.Name(), offs, p) + checkPos(t, msg, f.Position(f.Pos(offs)), Position{"bar", offs, 42, col}) + checkPos(t, msg, fset.Position(p), Position{"bar", offs, 42, col}) + } +} + + +func TestFiles(t *testing.T) { + fset := NewFileSet() + for i, test := range tests { + fset.AddFile(test.filename, fset.Base(), test.size) + j := 0 + for g := range fset.Files() { + if g.Name() != tests[j].filename { + t.Errorf("expected filename = %s; got %s", tests[j].filename, g.Name()) + } + j++ + } + if j != i+1 { + t.Errorf("expected %d files; got %d", i+1, j) + } + } +} diff --git a/src/pkg/go/token/token.go b/src/pkg/go/token/token.go index 70c2501e9..1bd81c1b1 100644 --- a/src/pkg/go/token/token.go +++ b/src/pkg/go/token/token.go @@ -8,10 +8,7 @@ // package token -import ( - "fmt" - "strconv" -) +import "strconv" // Token is the set of lexical tokens of the Go programming language. @@ -321,39 +318,3 @@ func (tok Token) IsOperator() bool { return operator_beg < tok && tok < operator // returns false otherwise. // func (tok Token) IsKeyword() bool { return keyword_beg < tok && tok < keyword_end } - - -// Token source positions are represented by a Position value. -// A Position is valid if the line number is > 0. -// -type Position struct { - Filename string // filename, if any - Offset int // byte offset, starting at 0 - Line int // line number, starting at 1 - Column int // column number, starting at 1 (character count) -} - - -// Pos is an accessor method for anonymous Position fields. -// It returns its receiver. -// -func (pos *Position) Pos() Position { return *pos } - - -// IsValid returns true if the position is valid. -func (pos *Position) IsValid() bool { return pos.Line > 0 } - - -func (pos Position) String() string { - s := pos.Filename - if pos.IsValid() { - if s != "" { - s += ":" - } - s += fmt.Sprintf("%d:%d", pos.Line, pos.Column) - } - if s == "" { - s = "???" - } - return s -} |