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