1 // Copyright 2018 The CUE Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 package token 16 17 import ( 18 "fmt" 19 "sort" 20 "sync" 21 ) 22 23 // ----------------------------------------------------------------------------- 24 // Positions 25 26 // Position describes an arbitrary source position 27 // including the file, line, and column location. 28 // A Position is valid if the line number is > 0. 29 type Position struct { 30 Filename string // filename, if any 31 Offset int // offset, starting at 0 32 Line int // line number, starting at 1 33 Column int // column number, starting at 1 (byte count) 34 // RelPos Pos // relative position information 35 } 36 37 // IsValid reports whether the position is valid. 38 func (pos *Position) IsValid() bool { return pos.Line > 0 } 39 40 // String returns a string in one of several forms: 41 // 42 // file:line:column valid position with file name 43 // line:column valid position without file name 44 // file invalid position with file name 45 // - invalid position without file name 46 func (pos Position) String() string { 47 s := pos.Filename 48 if pos.IsValid() { 49 if s != "" { 50 s += ":" 51 } 52 s += fmt.Sprintf("%d:%d", pos.Line, pos.Column) 53 } 54 if s == "" { 55 s = "-" 56 } 57 return s 58 } 59 60 // Pos is a compact encoding of a source position within a file, as well as 61 // relative positioning information. It can be converted into a Position for a 62 // more convenient, but much larger, representation. 63 type Pos struct { 64 file *File 65 offset int 66 } 67 68 // File returns the file that contains the position p or nil if there is no 69 // such file (for instance for p == NoPos). 70 func (p Pos) File() *File { 71 if p.index() == 0 { 72 return nil 73 } 74 return p.file 75 } 76 77 func (p Pos) Line() int { 78 if p.file == nil { 79 return 0 80 } 81 return p.Position().Line 82 } 83 84 func (p Pos) Column() int { 85 if p.file == nil { 86 return 0 87 } 88 return p.Position().Column 89 } 90 91 func (p Pos) Filename() string { 92 if p.file == nil { 93 return "" 94 } 95 return p.Position().Filename 96 } 97 98 func (p Pos) Position() Position { 99 if p.file == nil { 100 return Position{} 101 } 102 return p.file.Position(p) 103 } 104 105 func (p Pos) String() string { 106 return p.Position().String() 107 } 108 109 // NoPos is the zero value for Pos; there is no file and line information 110 // associated with it, and NoPos().IsValid() is false. NoPos is always 111 // smaller than any other Pos value. The corresponding Position value 112 // for NoPos is the zero value for Position. 113 var NoPos = Pos{} 114 115 // RelPos indicates the relative position of token to the previous token. 116 type RelPos int 117 118 const ( 119 // NoRelPos indicates no relative position is specified. 120 NoRelPos RelPos = iota 121 122 // Elided indicates that the token for which this position is defined is 123 // not rendered at all. 124 Elided 125 126 // NoSpace indicates there is no whitespace after this token. 127 NoSpace 128 129 // Blank means there is horizontal space after this token. 130 Blank 131 132 // Newline means there is a single newline after this token. 133 Newline 134 135 // NewSection means there are two or more newlines after this token. 136 NewSection 137 138 relMask = 0xf 139 relShift = 4 140 ) 141 142 var relNames = []string{ 143 "invalid", "elided", "nospace", "blank", "newline", "section", 144 } 145 146 func (p RelPos) String() string { return relNames[p] } 147 148 func (p RelPos) Pos() Pos { 149 return Pos{nil, int(p)} 150 } 151 152 // HasRelPos repors whether p has a relative position. 153 func (p Pos) HasRelPos() bool { 154 return p.offset&relMask != 0 155 156 } 157 158 func (p Pos) Before(q Pos) bool { 159 return p.file == q.file && p.Offset() < q.Offset() 160 } 161 162 // Offset reports the byte offset relative to the file. 163 func (p Pos) Offset() int { 164 return p.Position().Offset 165 } 166 167 // Add creates a new position relative to the p offset by n. 168 func (p Pos) Add(n int) Pos { 169 return Pos{p.file, p.offset + toPos(index(n))} 170 } 171 172 // IsValid reports whether the position is valid. 173 func (p Pos) IsValid() bool { 174 return p != NoPos 175 } 176 177 // IsNewline reports whether the relative information suggests this node should 178 // be printed on a new lien. 179 func (p Pos) IsNewline() bool { 180 return p.RelPos() >= Newline 181 } 182 183 func (p Pos) WithRel(rel RelPos) Pos { 184 return Pos{p.file, p.offset&^relMask | int(rel)} 185 } 186 187 func (p Pos) RelPos() RelPos { 188 return RelPos(p.offset & relMask) 189 } 190 191 func (p Pos) index() index { 192 return index(p.offset) >> relShift 193 } 194 195 func toPos(x index) int { 196 return (int(x) << relShift) 197 } 198 199 // ----------------------------------------------------------------------------- 200 // File 201 202 // index represents an offset into the file. 203 // It's 1-based rather than zero-based so that 204 // we can distinguish the zero Pos from a Pos that 205 // just has a zero offset. 206 type index int 207 208 // A File has a name, size, and line offset table. 209 type File struct { 210 mutex sync.RWMutex 211 name string // file name as provided to AddFile 212 // base is deprecated and stored only so that [File.Base] 213 // can continue to return the same value passed to [NewFile]. 214 base index 215 size index // file size as provided to AddFile 216 217 // lines and infos are protected by set.mutex 218 lines []index // lines contains the offset of the first character for each line (the first entry is always 0) 219 infos []lineInfo 220 } 221 222 // NewFile returns a new file with the given OS file name. The size provides the 223 // size of the whole file. 224 // 225 // The second argument is deprecated. It has no effect. 226 func NewFile(filename string, deprecatedBase, size int) *File { 227 if deprecatedBase < 0 { 228 deprecatedBase = 1 229 } 230 return &File{sync.RWMutex{}, filename, index(deprecatedBase), index(size), []index{0}, nil} 231 } 232 233 // Name returns the file name of file f as registered with AddFile. 234 func (f *File) Name() string { 235 return f.name 236 } 237 238 // Base returns the base offset of file f as passed to NewFile. 239 // 240 // Deprecated: this method just returns the (deprecated) second argument passed to NewFile. 241 func (f *File) Base() int { 242 return int(f.base) 243 } 244 245 // Size returns the size of file f as passed to NewFile. 246 func (f *File) Size() int { 247 return int(f.size) 248 } 249 250 // LineCount returns the number of lines in file f. 251 func (f *File) LineCount() int { 252 f.mutex.RLock() 253 n := len(f.lines) 254 f.mutex.RUnlock() 255 return n 256 } 257 258 // AddLine adds the line offset for a new line. 259 // The line offset must be larger than the offset for the previous line 260 // and smaller than the file size; otherwise the line offset is ignored. 261 func (f *File) AddLine(offset int) { 262 x := index(offset) 263 f.mutex.Lock() 264 if i := len(f.lines); (i == 0 || f.lines[i-1] < x) && x < f.size { 265 f.lines = append(f.lines, x) 266 } 267 f.mutex.Unlock() 268 } 269 270 // MergeLine merges a line with the following line. It is akin to replacing 271 // the newline character at the end of the line with a space (to not change the 272 // remaining offsets). To obtain the line number, consult e.g. Position.Line. 273 // MergeLine will panic if given an invalid line number. 274 func (f *File) MergeLine(line int) { 275 if line <= 0 { 276 panic("illegal line number (line numbering starts at 1)") 277 } 278 f.mutex.Lock() 279 defer f.mutex.Unlock() 280 if line >= len(f.lines) { 281 panic("illegal line number") 282 } 283 // To merge the line numbered <line> with the line numbered <line+1>, 284 // we need to remove the entry in lines corresponding to the line 285 // numbered <line+1>. The entry in lines corresponding to the line 286 // numbered <line+1> is located at index <line>, since indices in lines 287 // are 0-based and line numbers are 1-based. 288 copy(f.lines[line:], f.lines[line+1:]) 289 f.lines = f.lines[:len(f.lines)-1] 290 } 291 292 // SetLines sets the line offsets for a file and reports whether it succeeded. 293 // The line offsets are the offsets of the first character of each line; 294 // for instance for the content "ab\nc\n" the line offsets are {0, 3}. 295 // An empty file has an empty line offset table. 296 // Each line offset must be larger than the offset for the previous line 297 // and smaller than the file size; otherwise SetLines fails and returns 298 // false. 299 // Callers must not mutate the provided slice after SetLines returns. 300 func (f *File) SetLines(lines []int) bool { 301 // verify validity of lines table 302 size := f.size 303 for i, offset := range lines { 304 if i > 0 && offset <= lines[i-1] || size <= index(offset) { 305 return false 306 } 307 } 308 309 // set lines table 310 f.mutex.Lock() 311 f.lines = f.lines[:0] 312 for _, l := range lines { 313 f.lines = append(f.lines, index(l)) 314 } 315 f.mutex.Unlock() 316 return true 317 } 318 319 // SetLinesForContent sets the line offsets for the given file content. 320 // It ignores position-altering //line comments. 321 func (f *File) SetLinesForContent(content []byte) { 322 var lines []index 323 line := index(0) 324 for offset, b := range content { 325 if line >= 0 { 326 lines = append(lines, line) 327 } 328 line = -1 329 if b == '\n' { 330 line = index(offset) + 1 331 } 332 } 333 334 // set lines table 335 f.mutex.Lock() 336 f.lines = lines 337 f.mutex.Unlock() 338 } 339 340 // A lineInfo object describes alternative file and line number 341 // information (such as provided via a //line comment in a .go 342 // file) for a given file offset. 343 type lineInfo struct { 344 // fields are exported to make them accessible to gob 345 Offset int 346 Filename string 347 Line int 348 } 349 350 // AddLineInfo adds alternative file and line number information for 351 // a given file offset. The offset must be larger than the offset for 352 // the previously added alternative line info and smaller than the 353 // file size; otherwise the information is ignored. 354 // 355 // AddLineInfo is typically used to register alternative position 356 // information for //line filename:line comments in source files. 357 func (f *File) AddLineInfo(offset int, filename string, line int) { 358 x := index(offset) 359 f.mutex.Lock() 360 if i := len(f.infos); i == 0 || index(f.infos[i-1].Offset) < x && x < f.size { 361 f.infos = append(f.infos, lineInfo{offset, filename, line}) 362 } 363 f.mutex.Unlock() 364 } 365 366 // Pos returns the Pos value for the given file offset; 367 // the offset must be <= f.Size(). 368 // f.Pos(f.Offset(p)) == p. 369 func (f *File) Pos(offset int, rel RelPos) Pos { 370 if index(offset) > f.size { 371 panic("illegal file offset") 372 } 373 return Pos{f, toPos(1+index(offset)) + int(rel)} 374 } 375 376 // Offset returns the offset for the given file position p; 377 // p must be a valid Pos value in that file. 378 // f.Offset(f.Pos(offset)) == offset. 379 func (f *File) Offset(p Pos) int { 380 x := p.index() 381 if x < 1 || x > 1+index(f.size) { 382 panic("illegal Pos value") 383 } 384 return int(x - 1) 385 } 386 387 // Line returns the line number for the given file position p; 388 // p must be a Pos value in that file or NoPos. 389 func (f *File) Line(p Pos) int { 390 return f.Position(p).Line 391 } 392 393 func searchLineInfos(a []lineInfo, x int) int { 394 return sort.Search(len(a), func(i int) bool { return a[i].Offset > x }) - 1 395 } 396 397 // unpack returns the filename and line and column number for a file offset. 398 // If adjusted is set, unpack will return the filename and line information 399 // possibly adjusted by //line comments; otherwise those comments are ignored. 400 func (f *File) unpack(offset index, adjusted bool) (filename string, line, column int) { 401 filename = f.name 402 if i := searchInts(f.lines, offset); i >= 0 { 403 line, column = int(i+1), int(offset-f.lines[i]+1) 404 } 405 if adjusted && len(f.infos) > 0 { 406 // almost no files have extra line infos 407 if i := searchLineInfos(f.infos, int(offset)); i >= 0 { 408 alt := &f.infos[i] 409 filename = alt.Filename 410 if i := searchInts(f.lines, index(alt.Offset)); i >= 0 { 411 line += alt.Line - i - 1 412 } 413 } 414 } 415 return 416 } 417 418 func (f *File) position(p Pos, adjusted bool) (pos Position) { 419 offset := p.index() - 1 420 pos.Offset = int(offset) 421 pos.Filename, pos.Line, pos.Column = f.unpack(offset, adjusted) 422 return 423 } 424 425 // PositionFor returns the Position value for the given file position p. 426 // If adjusted is set, the position may be adjusted by position-altering 427 // //line comments; otherwise those comments are ignored. 428 // p must be a Pos value in f or NoPos. 429 func (f *File) PositionFor(p Pos, adjusted bool) (pos Position) { 430 x := p.index() 431 if p != NoPos { 432 if x < 1 || x > 1+f.size { 433 panic("illegal Pos value") 434 } 435 pos = f.position(p, adjusted) 436 } 437 return 438 } 439 440 // Position returns the Position value for the given file position p. 441 // Calling f.Position(p) is equivalent to calling f.PositionFor(p, true). 442 func (f *File) Position(p Pos) (pos Position) { 443 return f.PositionFor(p, true) 444 } 445 446 // ----------------------------------------------------------------------------- 447 // Helper functions 448 449 func searchInts(a []index, x index) int { 450 // This function body is a manually inlined version of: 451 // 452 // return sort.Search(len(a), func(i int) bool { return a[i] > x }) - 1 453 // 454 // With better compiler optimizations, this may not be needed in the 455 // future, but at the moment this change improves the go/printer 456 // benchmark performance by ~30%. This has a direct impact on the 457 // speed of gofmt and thus seems worthwhile (2011-04-29). 458 // TODO(gri): Remove this when compilers have caught up. 459 i, j := 0, len(a) 460 for i < j { 461 h := i + (j-i)/2 // avoid overflow when computing h 462 // i ≤ h < j 463 if a[h] <= x { 464 i = h + 1 465 } else { 466 j = h 467 } 468 } 469 return i - 1 470 } 471