internal/buffer/line_array.go

   1 package buffer
   2
   3 import (
   4         "bufio"
   5         "io"
   6         "sync"
   7         "unicode/utf8"
   8
   9         "github.com/zyedidia/micro/pkg/highlight"
  10 )
  11
  12 // Finds the byte index of the nth rune in a byte slice
  13 func runeToByteIndex(n int, txt []byte) int {
  14         if n == 0 {
  15                 return 0
  16         }
  17
  18         count := 0
  19         i := 0
  20         for len(txt) > 0 {
  21                 _, size := utf8.DecodeRune(txt)
  22
  23                 txt = txt[size:]
  24                 count += size
  25                 i++
  26
  27                 if i == n {
  28                         break
  29                 }
  30         }
  31         return count
  32 }
  33
  34 // A Line contains the data in bytes as well as a highlight state, match
  35 // and a flag for whether the highlighting needs to be updated
  36 type Line struct {
  37         data []byte
  38
  39         state       highlight.State
  40         match       highlight.LineMatch
  41         rehighlight bool
  42         lock        sync.Mutex
  43 }
  44
  45 const (
  46         // Line ending file formats
  47         FFAuto = 0 // Autodetect format
  48         FFUnix = 1 // LF line endings (unix style '\n')
  49         FFDos  = 2 // CRLF line endings (dos style '\r\n')
  50 )
  51
  52 type FileFormat byte
  53
  54 // A LineArray simply stores and array of lines and makes it easy to insert
  55 // and delete in it
  56 type LineArray struct {
  57         lines    []Line
  58         Endings  FileFormat
  59         initsize uint64
  60 }
  61
  62 // Append efficiently appends lines together
  63 // It allocates an additional 10000 lines if the original estimate
  64 // is incorrect
  65 func Append(slice []Line, data ...Line) []Line {
  66         l := len(slice)
  67         if l+len(data) > cap(slice) { // reallocate
  68                 newSlice := make([]Line, (l+len(data))+10000)
  69                 copy(newSlice, slice)
  70                 slice = newSlice
  71         }
  72         slice = slice[0 : l+len(data)]
  73         for i, c := range data {
  74                 slice[l+i] = c
  75         }
  76         return slice
  77 }
  78
  79 // NewLineArray returns a new line array from an array of bytes
  80 func NewLineArray(size uint64, endings FileFormat, reader io.Reader) *LineArray {
  81         la := new(LineArray)
  82
  83         la.lines = make([]Line, 0, 1000)
  84         la.initsize = size
  85
  86         br := bufio.NewReader(reader)
  87         var loaded int
  88
  89         n := 0
  90         for {
  91                 data, err := br.ReadBytes('\n')
  92                 // Detect the line ending by checking to see if there is a '\r' char
  93                 // before the '\n'
  94                 // Even if the file format is set to DOS, the '\r' is removed so
  95                 // that all lines end with '\n'
  96                 dlen := len(data)
  97                 if dlen > 1 && data[dlen-2] == '\r' {
  98                         data = append(data[:dlen-2], '\n')
  99                         if endings == FFAuto {
 100                                 la.Endings = FFDos
 101                         }
 102                         dlen = len(data)
 103                 } else if dlen > 0 {
 104                         if endings == FFAuto {
 105                                 la.Endings = FFUnix
 106                         }
 107                 }
 108
 109                 // If we are loading a large file (greater than 1000) we use the file
 110                 // size and the length of the first 1000 lines to try to estimate
 111                 // how many lines will need to be allocated for the rest of the file
 112                 // We add an extra 10000 to the original estimate to be safe and give
 113                 // plenty of room for expansion
 114                 if n >= 1000 && loaded >= 0 {
 115                         totalLinesNum := int(float64(size) * (float64(n) / float64(loaded)))
 116                         newSlice := make([]Line, len(la.lines), totalLinesNum+10000)
 117                         copy(newSlice, la.lines)
 118                         la.lines = newSlice
 119                         loaded = -1
 120                 }
 121
 122                 // Counter for the number of bytes in the first 1000 lines
 123                 if loaded >= 0 {
 124                         loaded += dlen
 125                 }
 126
 127                 if err != nil {
 128                         if err == io.EOF {
 129                                 la.lines = Append(la.lines, Line{
 130                                         data:        data[:],
 131                                         state:       nil,
 132                                         match:       nil,
 133                                         rehighlight: false,
 134                                 })
 135                         }
 136                         // Last line was read
 137                         break
 138                 } else {
 139                         la.lines = Append(la.lines, Line{
 140                                 data:        data[:dlen-1],
 141                                 state:       nil,
 142                                 match:       nil,
 143                                 rehighlight: false,
 144                         })
 145                 }
 146                 n++
 147         }
 148
 149         return la
 150 }
 151
 152 // Bytes returns the string that should be written to disk when
 153 // the line array is saved
 154 func (la *LineArray) Bytes() []byte {
 155         str := make([]byte, 0, la.initsize+1000) // initsize should provide a good estimate
 156         for i, l := range la.lines {
 157                 str = append(str, l.data...)
 158                 if i != len(la.lines)-1 {
 159                         if la.Endings == FFDos {
 160                                 str = append(str, '\r')
 161                         }
 162                         str = append(str, '\n')
 163                 }
 164         }
 165         return str
 166 }
 167
 168 // newlineBelow adds a newline below the given line number
 169 func (la *LineArray) newlineBelow(y int) {
 170         la.lines = append(la.lines, Line{
 171                 data:        []byte{' '},
 172                 state:       nil,
 173                 match:       nil,
 174                 rehighlight: false,
 175         })
 176         copy(la.lines[y+2:], la.lines[y+1:])
 177         la.lines[y+1] = Line{
 178                 data:        []byte{},
 179                 state:       la.lines[y].state,
 180                 match:       nil,
 181                 rehighlight: false,
 182         }
 183 }
 184
 185 // Inserts a byte array at a given location
 186 func (la *LineArray) insert(pos Loc, value []byte) {
 187         x, y := runeToByteIndex(pos.X, la.lines[pos.Y].data), pos.Y
 188         for i := 0; i < len(value); i++ {
 189                 if value[i] == '\n' {
 190                         la.split(Loc{x, y})
 191                         x = 0
 192                         y++
 193                         continue
 194                 }
 195                 la.insertByte(Loc{x, y}, value[i])
 196                 x++
 197         }
 198 }
 199
 200 // InsertByte inserts a byte at a given location
 201 func (la *LineArray) insertByte(pos Loc, value byte) {
 202         la.lines[pos.Y].data = append(la.lines[pos.Y].data, 0)
 203         copy(la.lines[pos.Y].data[pos.X+1:], la.lines[pos.Y].data[pos.X:])
 204         la.lines[pos.Y].data[pos.X] = value
 205 }
 206
 207 // joinLines joins the two lines a and b
 208 func (la *LineArray) joinLines(a, b int) {
 209         la.insert(Loc{len(la.lines[a].data), a}, la.lines[b].data)
 210         la.deleteLine(b)
 211 }
 212
 213 // split splits a line at a given position
 214 func (la *LineArray) split(pos Loc) {
 215         la.newlineBelow(pos.Y)
 216         la.insert(Loc{0, pos.Y + 1}, la.lines[pos.Y].data[pos.X:])
 217         la.lines[pos.Y+1].state = la.lines[pos.Y].state
 218         la.lines[pos.Y].state = nil
 219         la.lines[pos.Y].match = nil
 220         la.lines[pos.Y+1].match = nil
 221         la.lines[pos.Y].rehighlight = true
 222         la.deleteToEnd(Loc{pos.X, pos.Y})
 223 }
 224
 225 // removes from start to end
 226 func (la *LineArray) remove(start, end Loc) []byte {
 227         sub := la.Substr(start, end)
 228         startX := runeToByteIndex(start.X, la.lines[start.Y].data)
 229         endX := runeToByteIndex(end.X, la.lines[end.Y].data)
 230         if start.Y == end.Y {
 231                 la.lines[start.Y].data = append(la.lines[start.Y].data[:startX], la.lines[start.Y].data[endX:]...)
 232         } else {
 233                 for i := start.Y + 1; i <= end.Y-1; i++ {
 234                         la.deleteLine(start.Y + 1)
 235                 }
 236                 la.deleteToEnd(Loc{startX, start.Y})
 237                 la.deleteFromStart(Loc{endX - 1, start.Y + 1})
 238                 la.joinLines(start.Y, start.Y+1)
 239         }
 240         return sub
 241 }
 242
 243 // deleteToEnd deletes from the end of a line to the position
 244 func (la *LineArray) deleteToEnd(pos Loc) {
 245         la.lines[pos.Y].data = la.lines[pos.Y].data[:pos.X]
 246 }
 247
 248 // deleteFromStart deletes from the start of a line to the position
 249 func (la *LineArray) deleteFromStart(pos Loc) {
 250         la.lines[pos.Y].data = la.lines[pos.Y].data[pos.X+1:]
 251 }
 252
 253 // deleteLine deletes the line number
 254 func (la *LineArray) deleteLine(y int) {
 255         la.lines = la.lines[:y+copy(la.lines[y:], la.lines[y+1:])]
 256 }
 257
 258 // DeleteByte deletes the byte at a position
 259 func (la *LineArray) deleteByte(pos Loc) {
 260         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:])]
 261 }
 262
 263 // Substr returns the string representation between two locations
 264 func (la *LineArray) Substr(start, end Loc) []byte {
 265         startX := runeToByteIndex(start.X, la.lines[start.Y].data)
 266         endX := runeToByteIndex(end.X, la.lines[end.Y].data)
 267         if start.Y == end.Y {
 268                 src := la.lines[start.Y].data[startX:endX]
 269                 dest := make([]byte, len(src))
 270                 copy(dest, src)
 271                 return dest
 272         }
 273         str := make([]byte, 0, len(la.lines[start.Y+1].data)*(end.Y-start.Y))
 274         str = append(str, la.lines[start.Y].data[startX:]...)
 275         str = append(str, '\n')
 276         for i := start.Y + 1; i <= end.Y-1; i++ {
 277                 str = append(str, la.lines[i].data...)
 278                 str = append(str, '\n')
 279         }
 280         str = append(str, la.lines[end.Y].data[:endX]...)
 281         return str
 282 }
 283
 284 // LinesNum returns the number of lines in the buffer
 285 func (la *LineArray) LinesNum() int {
 286         return len(la.lines)
 287 }
 288
 289 // Start returns the start of the buffer
 290 func (la *LineArray) Start() Loc {
 291         return Loc{0, 0}
 292 }
 293
 294 // End returns the location of the last character in the buffer
 295 func (la *LineArray) End() Loc {
 296         numlines := len(la.lines)
 297         return Loc{utf8.RuneCount(la.lines[numlines-1].data), numlines - 1}
 298 }
 299
 300 // LineBytes returns line n as an array of bytes
 301 func (la *LineArray) LineBytes(n int) []byte {
 302         if n >= len(la.lines) || n < 0 {
 303                 return []byte{}
 304         }
 305         return la.lines[n].data
 306 }
 307
 308 // State gets the highlight state for the given line number
 309 func (la *LineArray) State(lineN int) highlight.State {
 310         la.lines[lineN].lock.Lock()
 311         defer la.lines[lineN].lock.Unlock()
 312         return la.lines[lineN].state
 313 }
 314
 315 // SetState sets the highlight state at the given line number
 316 func (la *LineArray) SetState(lineN int, s highlight.State) {
 317         la.lines[lineN].lock.Lock()
 318         defer la.lines[lineN].lock.Unlock()
 319         la.lines[lineN].state = s
 320 }
 321
 322 // SetMatch sets the match at the given line number
 323 func (la *LineArray) SetMatch(lineN int, m highlight.LineMatch) {
 324         la.lines[lineN].lock.Lock()
 325         defer la.lines[lineN].lock.Unlock()
 326         la.lines[lineN].match = m
 327 }
 328
 329 // Match retrieves the match for the given line number
 330 func (la *LineArray) Match(lineN int) highlight.LineMatch {
 331         la.lines[lineN].lock.Lock()
 332         defer la.lines[lineN].lock.Unlock()
 333         return la.lines[lineN].match
 334 }
 335
 336 func (la *LineArray) Rehighlight(lineN int) bool {
 337         la.lines[lineN].lock.Lock()
 338         defer la.lines[lineN].lock.Unlock()
 339         return la.lines[lineN].rehighlight
 340 }
 341
 342 func (la *LineArray) SetRehighlight(lineN int, on bool) {
 343         la.lines[lineN].lock.Lock()
 344         defer la.lines[lineN].lock.Unlock()
 345         la.lines[lineN].rehighlight = on
 346 }