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