internal/buffer/line_array.go

   1 package buffer
   2
   3 import (
   4         "bufio"
   5         "bytes"
   6         "io"
   7         "sync"
   8
   9         "github.com/zyedidia/micro/v2/internal/util"
  10         "github.com/zyedidia/micro/v2/pkg/highlight"
  11 )
  12
  13 // Finds the byte index of the nth rune in a byte slice
  14 func runeToByteIndex(n int, txt []byte) int {
  15         if n == 0 {
  16                 return 0
  17         }
  18
  19         count := 0
  20         i := 0
  21         for len(txt) > 0 {
  22                 _, _, size := util.DecodeCharacter(txt)
  23
  24                 txt = txt[size:]
  25                 count += size
  26                 i++
  27
  28                 if i == n {
  29                         break
  30                 }
  31         }
  32         return count
  33 }
  34
  35 // A searchState contains the search match info for a single line
  36 type searchState struct {
  37         search     string
  38         useRegex   bool
  39         ignorecase bool
  40         match      [][2]int
  41         done       bool
  42 }
  43
  44 // A Line contains the data in bytes as well as a highlight state, match
  45 // and a flag for whether the highlighting needs to be updated
  46 type Line struct {
  47         data []byte
  48
  49         state       highlight.State
  50         match       highlight.LineMatch
  51         rehighlight bool
  52         lock        sync.Mutex
  53
  54         // The search states for the line, used for highlighting of search matches,
  55         // separately from the syntax highlighting.
  56         // A map is used because the line array may be shared between multiple buffers
  57         // (multiple instances of the same file opened in different edit panes)
  58         // which have distinct searches, so in the general case there are multiple
  59         // searches per a line, one search per a Buffer containing this line.
  60         search map[*Buffer]*searchState
  61 }
  62
  63 const (
  64         // Line ending file formats
  65         FFAuto = 0 // Autodetect format
  66         FFUnix = 1 // LF line endings (unix style '\n')
  67         FFDos  = 2 // CRLF line endings (dos style '\r\n')
  68 )
  69
  70 type FileFormat byte
  71
  72 // A LineArray simply stores and array of lines and makes it easy to insert
  73 // and delete in it
  74 type LineArray struct {
  75         lines    []Line
  76         Endings  FileFormat
  77         initsize uint64
  78 }
  79
  80 // Append efficiently appends lines together
  81 // It allocates an additional 10000 lines if the original estimate
  82 // is incorrect
  83 func Append(slice []Line, data ...Line) []Line {
  84         l := len(slice)
  85         if l+len(data) > cap(slice) { // reallocate
  86                 newSlice := make([]Line, (l+len(data))+10000)
  87                 copy(newSlice, slice)
  88                 slice = newSlice
  89         }
  90         slice = slice[0 : l+len(data)]
  91         for i, c := range data {
  92                 slice[l+i] = c
  93         }
  94         return slice
  95 }
  96
  97 // NewLineArray returns a new line array from an array of bytes
  98 func NewLineArray(size uint64, endings FileFormat, reader io.Reader) *LineArray {
  99         la := new(LineArray)
 100
 101         la.lines = make([]Line, 0, 1000)
 102         la.initsize = size
 103
 104         br := bufio.NewReader(reader)
 105         var loaded int
 106
 107         la.Endings = endings
 108
 109         n := 0
 110         for {
 111                 data, err := br.ReadBytes('\n')
 112                 // Detect the line ending by checking to see if there is a '\r' char
 113                 // before the '\n'
 114                 // Even if the file format is set to DOS, the '\r' is removed so
 115                 // that all lines end with '\n'
 116                 dlen := len(data)
 117                 if dlen > 1 && data[dlen-2] == '\r' {
 118                         data = append(data[:dlen-2], '\n')
 119                         if endings == FFAuto {
 120                                 la.Endings = FFDos
 121                         }
 122                         dlen = len(data)
 123                 } else if dlen > 0 {
 124                         if endings == FFAuto {
 125                                 la.Endings = FFUnix
 126                         }
 127                 }
 128
 129                 // If we are loading a large file (greater than 1000) we use the file
 130                 // size and the length of the first 1000 lines to try to estimate
 131                 // how many lines will need to be allocated for the rest of the file
 132                 // We add an extra 10000 to the original estimate to be safe and give
 133                 // plenty of room for expansion
 134                 if n >= 1000 && loaded >= 0 {
 135                         totalLinesNum := int(float64(size) * (float64(n) / float64(loaded)))
 136                         newSlice := make([]Line, len(la.lines), totalLinesNum+10000)
 137                         copy(newSlice, la.lines)
 138                         la.lines = newSlice
 139                         loaded = -1
 140                 }
 141
 142                 // Counter for the number of bytes in the first 1000 lines
 143                 if loaded >= 0 {
 144                         loaded += dlen
 145                 }
 146
 147                 if err != nil {
 148                         if err == io.EOF {
 149                                 la.lines = Append(la.lines, Line{
 150                                         data:        data,
 151                                         state:       nil,
 152                                         match:       nil,
 153                                         rehighlight: false,
 154                                 })
 155                         }
 156                         // Last line was read
 157                         break
 158                 } else {
 159                         la.lines = Append(la.lines, Line{
 160                                 data:        data[:dlen-1],
 161                                 state:       nil,
 162                                 match:       nil,
 163                                 rehighlight: false,
 164                         })
 165                 }
 166                 n++
 167         }
 168
 169         return la
 170 }
 171
 172 // Bytes returns the string that should be written to disk when
 173 // the line array is saved
 174 func (la *LineArray) Bytes() []byte {
 175         b := new(bytes.Buffer)
 176         // initsize should provide a good estimate
 177         b.Grow(int(la.initsize + 4096))
 178         for i, l := range la.lines {
 179                 b.Write(l.data)
 180                 if i != len(la.lines)-1 {
 181                         if la.Endings == FFDos {
 182                                 b.WriteByte('\r')
 183                         }
 184                         b.WriteByte('\n')
 185                 }
 186         }
 187         return b.Bytes()
 188 }
 189
 190 // newlineBelow adds a newline below the given line number
 191 func (la *LineArray) newlineBelow(y int) {
 192         la.lines = append(la.lines, Line{
 193                 data:        []byte{' '},
 194                 state:       nil,
 195                 match:       nil,
 196                 rehighlight: false,
 197         })
 198         copy(la.lines[y+2:], la.lines[y+1:])
 199         la.lines[y+1] = Line{
 200                 data:        []byte{},
 201                 state:       la.lines[y].state,
 202                 match:       nil,
 203                 rehighlight: false,
 204         }
 205 }
 206
 207 // Inserts a byte array at a given location
 208 func (la *LineArray) insert(pos Loc, value []byte) {
 209         x, y := runeToByteIndex(pos.X, la.lines[pos.Y].data), pos.Y
 210         for i := 0; i < len(value); i++ {
 211                 if value[i] == '\n' || (value[i] == '\r' && i < len(value)-1 && value[i+1] == '\n') {
 212                         la.split(Loc{x, y})
 213                         x = 0
 214                         y++
 215
 216                         if value[i] == '\r' {
 217                                 i++
 218                         }
 219
 220                         continue
 221                 }
 222                 la.insertByte(Loc{x, y}, value[i])
 223                 x++
 224         }
 225 }
 226
 227 // InsertByte inserts a byte at a given location
 228 func (la *LineArray) insertByte(pos Loc, value byte) {
 229         la.lines[pos.Y].data = append(la.lines[pos.Y].data, 0)
 230         copy(la.lines[pos.Y].data[pos.X+1:], la.lines[pos.Y].data[pos.X:])
 231         la.lines[pos.Y].data[pos.X] = value
 232 }
 233
 234 // joinLines joins the two lines a and b
 235 func (la *LineArray) joinLines(a, b int) {
 236         la.insert(Loc{len(la.lines[a].data), a}, la.lines[b].data)
 237         la.deleteLine(b)
 238 }
 239
 240 // split splits a line at a given position
 241 func (la *LineArray) split(pos Loc) {
 242         la.newlineBelow(pos.Y)
 243         la.insert(Loc{0, pos.Y + 1}, la.lines[pos.Y].data[pos.X:])
 244         la.lines[pos.Y+1].state = la.lines[pos.Y].state
 245         la.lines[pos.Y].state = nil
 246         la.lines[pos.Y].match = nil
 247         la.lines[pos.Y+1].match = nil
 248         la.lines[pos.Y].rehighlight = true
 249         la.deleteToEnd(Loc{pos.X, pos.Y})
 250 }
 251
 252 // removes from start to end
 253 func (la *LineArray) remove(start, end Loc) []byte {
 254         sub := la.Substr(start, end)
 255         startX := runeToByteIndex(start.X, la.lines[start.Y].data)
 256         endX := runeToByteIndex(end.X, la.lines[end.Y].data)
 257         if start.Y == end.Y {
 258                 la.lines[start.Y].data = append(la.lines[start.Y].data[:startX], la.lines[start.Y].data[endX:]...)
 259         } else {
 260                 la.deleteLines(start.Y+1, end.Y-1)
 261                 la.deleteToEnd(Loc{startX, start.Y})
 262                 la.deleteFromStart(Loc{endX - 1, start.Y + 1})
 263                 la.joinLines(start.Y, start.Y+1)
 264         }
 265         return sub
 266 }
 267
 268 // deleteToEnd deletes from the end of a line to the position
 269 func (la *LineArray) deleteToEnd(pos Loc) {
 270         la.lines[pos.Y].data = la.lines[pos.Y].data[:pos.X]
 271 }
 272
 273 // deleteFromStart deletes from the start of a line to the position
 274 func (la *LineArray) deleteFromStart(pos Loc) {
 275         la.lines[pos.Y].data = la.lines[pos.Y].data[pos.X+1:]
 276 }
 277
 278 // deleteLine deletes the line number
 279 func (la *LineArray) deleteLine(y int) {
 280         la.lines = la.lines[:y+copy(la.lines[y:], la.lines[y+1:])]
 281 }
 282
 283 func (la *LineArray) deleteLines(y1, y2 int) {
 284         la.lines = la.lines[:y1+copy(la.lines[y1:], la.lines[y2+1:])]
 285 }
 286
 287 // DeleteByte deletes the byte at a position
 288 func (la *LineArray) deleteByte(pos Loc) {
 289         la.lines[pos.Y].data = la.lines[pos.Y].data[:pos.X+copy(la.lines[pos.Y].data[pos.X:], la.lines[pos.Y].data[pos.X+1:])]
 290 }
 291
 292 // Substr returns the string representation between two locations
 293 func (la *LineArray) Substr(start, end Loc) []byte {
 294         startX := runeToByteIndex(start.X, la.lines[start.Y].data)
 295         endX := runeToByteIndex(end.X, la.lines[end.Y].data)
 296         if start.Y == end.Y {
 297                 src := la.lines[start.Y].data[startX:endX]
 298                 dest := make([]byte, len(src))
 299                 copy(dest, src)
 300                 return dest
 301         }
 302         str := make([]byte, 0, len(la.lines[start.Y+1].data)*(end.Y-start.Y))
 303         str = append(str, la.lines[start.Y].data[startX:]...)
 304         str = append(str, '\n')
 305         for i := start.Y + 1; i <= end.Y-1; i++ {
 306                 str = append(str, la.lines[i].data...)
 307                 str = append(str, '\n')
 308         }
 309         str = append(str, la.lines[end.Y].data[:endX]...)
 310         return str
 311 }
 312
 313 // LinesNum returns the number of lines in the buffer
 314 func (la *LineArray) LinesNum() int {
 315         return len(la.lines)
 316 }
 317
 318 // Start returns the start of the buffer
 319 func (la *LineArray) Start() Loc {
 320         return Loc{0, 0}
 321 }
 322
 323 // End returns the location of the last character in the buffer
 324 func (la *LineArray) End() Loc {
 325         numlines := len(la.lines)
 326         return Loc{util.CharacterCount(la.lines[numlines-1].data), numlines - 1}
 327 }
 328
 329 // LineBytes returns line n as an array of bytes
 330 func (la *LineArray) LineBytes(n int) []byte {
 331         if n >= len(la.lines) || n < 0 {
 332                 return []byte{}
 333         }
 334         return la.lines[n].data
 335 }
 336
 337 // State gets the highlight state for the given line number
 338 func (la *LineArray) State(lineN int) highlight.State {
 339         la.lines[lineN].lock.Lock()
 340         defer la.lines[lineN].lock.Unlock()
 341         return la.lines[lineN].state
 342 }
 343
 344 // SetState sets the highlight state at the given line number
 345 func (la *LineArray) SetState(lineN int, s highlight.State) {
 346         la.lines[lineN].lock.Lock()
 347         defer la.lines[lineN].lock.Unlock()
 348         la.lines[lineN].state = s
 349 }
 350
 351 // SetMatch sets the match at the given line number
 352 func (la *LineArray) SetMatch(lineN int, m highlight.LineMatch) {
 353         la.lines[lineN].lock.Lock()
 354         defer la.lines[lineN].lock.Unlock()
 355         la.lines[lineN].match = m
 356 }
 357
 358 // Match retrieves the match for the given line number
 359 func (la *LineArray) Match(lineN int) highlight.LineMatch {
 360         la.lines[lineN].lock.Lock()
 361         defer la.lines[lineN].lock.Unlock()
 362         return la.lines[lineN].match
 363 }
 364
 365 func (la *LineArray) Rehighlight(lineN int) bool {
 366         la.lines[lineN].lock.Lock()
 367         defer la.lines[lineN].lock.Unlock()
 368         return la.lines[lineN].rehighlight
 369 }
 370
 371 func (la *LineArray) SetRehighlight(lineN int, on bool) {
 372         la.lines[lineN].lock.Lock()
 373         defer la.lines[lineN].lock.Unlock()
 374         la.lines[lineN].rehighlight = on
 375 }
 376
 377 // SearchMatch returns true if the location `pos` is within a match
 378 // of the last search for the buffer `b`.
 379 // It is used for efficient highlighting of search matches (separately
 380 // from the syntax highlighting).
 381 // SearchMatch searches for the matches if it is called first time
 382 // for the given line or if the line was modified. Otherwise the
 383 // previously found matches are used.
 384 //
 385 // The buffer `b` needs to be passed because the line array may be shared
 386 // between multiple buffers (multiple instances of the same file opened
 387 // in different edit panes) which have distinct searches, so SearchMatch
 388 // needs to know which search to match against.
 389 func (la *LineArray) SearchMatch(b *Buffer, pos Loc) bool {
 390         if b.LastSearch == "" {
 391                 return false
 392         }
 393
 394         lineN := pos.Y
 395         if la.lines[lineN].search == nil {
 396                 la.lines[lineN].search = make(map[*Buffer]*searchState)
 397         }
 398         s, ok := la.lines[lineN].search[b]
 399         if !ok {
 400                 // Note: here is a small harmless leak: when the buffer `b` is closed,
 401                 // `s` is not deleted from the map. It means that the buffer
 402                 // will not be garbage-collected until the line array is garbage-collected,
 403                 // i.e. until all the buffers sharing this file are closed.
 404                 s = new(searchState)
 405                 la.lines[lineN].search[b] = s
 406         }
 407         if !ok || s.search != b.LastSearch || s.useRegex != b.LastSearchRegex ||
 408                 s.ignorecase != b.Settings["ignorecase"].(bool) {
 409                 s.search = b.LastSearch
 410                 s.useRegex = b.LastSearchRegex
 411                 s.ignorecase = b.Settings["ignorecase"].(bool)
 412                 s.done = false
 413         }
 414
 415         if !s.done {
 416                 s.match = nil
 417                 start := Loc{0, lineN}
 418                 end := Loc{util.CharacterCount(la.lines[lineN].data), lineN}
 419                 for start.X < end.X {
 420                         m, found, _ := b.FindNext(b.LastSearch, start, end, start, true, b.LastSearchRegex)
 421                         if !found {
 422                                 break
 423                         }
 424                         s.match = append(s.match, [2]int{m[0].X, m[1].X})
 425
 426                         start.X = m[1].X
 427                         if m[1].X == m[0].X {
 428                                 start.X = m[1].X + 1
 429                         }
 430                 }
 431
 432                 s.done = true
 433         }
 434
 435         for _, m := range s.match {
 436                 if pos.X >= m[0] && pos.X < m[1] {
 437                         return true
 438                 }
 439         }
 440         return false
 441 }
 442
 443 // invalidateSearchMatches marks search matches for the given line as outdated.
 444 // It is called when the line is modified.
 445 func (la *LineArray) invalidateSearchMatches(lineN int) {
 446         if la.lines[lineN].search != nil {
 447                 for _, s := range la.lines[lineN].search {
 448                         s.done = false
 449                 }
 450         }
 451 }