internal/buffer/line_array.go

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