cmd/micro/buffer/line_array.go

   1 package buffer
   2
   3 import (
   4         "bufio"
   5         "io"
   6         "unicode/utf8"
   7
   8         "github.com/zyedidia/micro/cmd/micro/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                 } else if dlen > 0 {
 101                         if endings == FFAuto {
 102                                 la.endings = FFUnix
 103                         }
 104                 }
 105
 106                 // If we are loading a large file (greater than 1000) we use the file
 107                 // size and the length of the first 1000 lines to try to estimate
 108                 // how many lines will need to be allocated for the rest of the file
 109                 // We add an extra 10000 to the original estimate to be safe and give
 110                 // plenty of room for expansion
 111                 if n >= 1000 && loaded >= 0 {
 112                         totalLinesNum := int(float64(size) * (float64(n) / float64(loaded)))
 113                         newSlice := make([]Line, len(la.lines), totalLinesNum+10000)
 114                         copy(newSlice, la.lines)
 115                         la.lines = newSlice
 116                         loaded = -1
 117                 }
 118
 119                 // Counter for the number of bytes in the first 1000 lines
 120                 if loaded >= 0 {
 121                         loaded += dlen
 122                 }
 123
 124                 if err != nil {
 125                         if err == io.EOF {
 126                                 la.lines = Append(la.lines, Line{data[:], nil, nil, false})
 127                         }
 128                         // Last line was read
 129                         break
 130                 } else {
 131                         la.lines = Append(la.lines, Line{data[:dlen-1], nil, nil, false})
 132                 }
 133                 n++
 134         }
 135
 136         return la
 137 }
 138
 139 // Bytes returns the string that should be written to disk when
 140 // the line array is saved
 141 func (la *LineArray) Bytes() []byte {
 142         str := make([]byte, 0, la.initsize+1000) // initsize should provide a good estimate
 143         for i, l := range la.lines {
 144                 str = append(str, l.data...)
 145                 if i != len(la.lines)-1 {
 146                         if la.endings == FFDos {
 147                                 str = append(str, '\r')
 148                         }
 149                         str = append(str, '\n')
 150                 }
 151         }
 152         return str
 153 }
 154
 155 // newlineBelow adds a newline below the given line number
 156 func (la *LineArray) newlineBelow(y int) {
 157         la.lines = append(la.lines, Line{[]byte{' '}, nil, nil, false})
 158         copy(la.lines[y+2:], la.lines[y+1:])
 159         la.lines[y+1] = Line{[]byte{}, la.lines[y].state, nil, false}
 160 }
 161
 162 // Inserts a byte array at a given location
 163 func (la *LineArray) insert(pos Loc, value []byte) {
 164         x, y := runeToByteIndex(pos.X, la.lines[pos.Y].data), pos.Y
 165         for i := 0; i < len(value); i++ {
 166                 if value[i] == '\n' {
 167                         la.split(Loc{x, y})
 168                         x = 0
 169                         y++
 170                         continue
 171                 }
 172                 la.insertByte(Loc{x, y}, value[i])
 173                 x++
 174         }
 175 }
 176
 177 // InsertByte inserts a byte at a given location
 178 func (la *LineArray) insertByte(pos Loc, value byte) {
 179         la.lines[pos.Y].data = append(la.lines[pos.Y].data, 0)
 180         copy(la.lines[pos.Y].data[pos.X+1:], la.lines[pos.Y].data[pos.X:])
 181         la.lines[pos.Y].data[pos.X] = value
 182 }
 183
 184 // joinLines joins the two lines a and b
 185 func (la *LineArray) joinLines(a, b int) {
 186         la.insert(Loc{len(la.lines[a].data), a}, la.lines[b].data)
 187         la.deleteLine(b)
 188 }
 189
 190 // split splits a line at a given position
 191 func (la *LineArray) split(pos Loc) {
 192         la.newlineBelow(pos.Y)
 193         la.insert(Loc{0, pos.Y + 1}, la.lines[pos.Y].data[pos.X:])
 194         la.lines[pos.Y+1].state = la.lines[pos.Y].state
 195         la.lines[pos.Y].state = nil
 196         la.lines[pos.Y].match = nil
 197         la.lines[pos.Y+1].match = nil
 198         la.lines[pos.Y].rehighlight = true
 199         la.deleteToEnd(Loc{pos.X, pos.Y})
 200 }
 201
 202 // removes from start to end
 203 func (la *LineArray) remove(start, end Loc) []byte {
 204         sub := la.Substr(start, end)
 205         startX := runeToByteIndex(start.X, la.lines[start.Y].data)
 206         endX := runeToByteIndex(end.X, la.lines[end.Y].data)
 207         if start.Y == end.Y {
 208                 la.lines[start.Y].data = append(la.lines[start.Y].data[:startX], la.lines[start.Y].data[endX:]...)
 209         } else {
 210                 for i := start.Y + 1; i <= end.Y-1; i++ {
 211                         la.deleteLine(start.Y + 1)
 212                 }
 213                 la.deleteToEnd(Loc{startX, start.Y})
 214                 la.deleteFromStart(Loc{endX - 1, start.Y + 1})
 215                 la.joinLines(start.Y, start.Y+1)
 216         }
 217         return sub
 218 }
 219
 220 // deleteToEnd deletes from the end of a line to the position
 221 func (la *LineArray) deleteToEnd(pos Loc) {
 222         la.lines[pos.Y].data = la.lines[pos.Y].data[:pos.X]
 223 }
 224
 225 // deleteFromStart deletes from the start of a line to the position
 226 func (la *LineArray) deleteFromStart(pos Loc) {
 227         la.lines[pos.Y].data = la.lines[pos.Y].data[pos.X+1:]
 228 }
 229
 230 // deleteLine deletes the line number
 231 func (la *LineArray) deleteLine(y int) {
 232         la.lines = la.lines[:y+copy(la.lines[y:], la.lines[y+1:])]
 233 }
 234
 235 // DeleteByte deletes the byte at a position
 236 func (la *LineArray) deleteByte(pos Loc) {
 237         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:])]
 238 }
 239
 240 // Substr returns the string representation between two locations
 241 func (la *LineArray) Substr(start, end Loc) []byte {
 242         startX := runeToByteIndex(start.X, la.lines[start.Y].data)
 243         endX := runeToByteIndex(end.X, la.lines[end.Y].data)
 244         if start.Y == end.Y {
 245                 return la.lines[start.Y].data[startX:endX]
 246         }
 247         str := make([]byte, 0, len(la.lines[start.Y+1].data)*(end.Y-start.Y))
 248         str = append(str, la.lines[start.Y].data[startX:]...)
 249         str = append(str, '\n')
 250         for i := start.Y + 1; i <= end.Y-1; i++ {
 251                 str = append(str, la.lines[i].data...)
 252                 str = append(str, '\n')
 253         }
 254         str = append(str, la.lines[end.Y].data[:endX]...)
 255         return str
 256 }
 257
 258 // State gets the highlight state for the given line number
 259 func (la *LineArray) State(lineN int) highlight.State {
 260         return la.lines[lineN].state
 261 }
 262
 263 // SetState sets the highlight state at the given line number
 264 func (la *LineArray) SetState(lineN int, s highlight.State) {
 265         la.lines[lineN].state = s
 266 }
 267
 268 // SetMatch sets the match at the given line number
 269 func (la *LineArray) SetMatch(lineN int, m highlight.LineMatch) {
 270         la.lines[lineN].match = m
 271 }
 272
 273 // Match retrieves the match for the given line number
 274 func (la *LineArray) Match(lineN int) highlight.LineMatch {
 275         return la.lines[lineN].match
 276 }
 277
 278 func (la *LineArray) Rehighlight(lineN int) bool {
 279         return la.lines[lineN].rehighlight
 280 }
 281
 282 func (la *LineArray) SetRehighlight(lineN int, on bool) {
 283         la.lines[lineN].rehighlight = on
 284 }