master
1package gitdiff
2
3import (
4 "errors"
5 "io"
6)
7
8const (
9 byteBufferSize = 32 * 1024 // from io.Copy
10 lineBufferSize = 32
11 indexBufferSize = 1024
12)
13
14// LineReaderAt is the interface that wraps the ReadLinesAt method.
15//
16// ReadLinesAt reads len(lines) into lines starting at line offset. It returns
17// the number of lines read (0 <= n <= len(lines)) and any error encountered.
18// Line numbers are zero-indexed.
19//
20// If n < len(lines), ReadLinesAt returns a non-nil error explaining why more
21// lines were not returned.
22//
23// Lines read by ReadLinesAt include the newline character. The last line does
24// not have a final newline character if the input ends without one.
25type LineReaderAt interface {
26 ReadLinesAt(lines [][]byte, offset int64) (n int, err error)
27}
28
29type lineReaderAt struct {
30 r io.ReaderAt
31 index []int64
32 eof bool
33}
34
35func (r *lineReaderAt) ReadLinesAt(lines [][]byte, offset int64) (n int, err error) {
36 if offset < 0 {
37 return 0, errors.New("ReadLinesAt: negative offset")
38 }
39 if len(lines) == 0 {
40 return 0, nil
41 }
42
43 count := len(lines)
44 startLine := offset
45 endLine := startLine + int64(count)
46
47 if endLine > int64(len(r.index)) && !r.eof {
48 if err := r.indexTo(endLine); err != nil {
49 return 0, err
50 }
51 }
52 if startLine >= int64(len(r.index)) {
53 return 0, io.EOF
54 }
55
56 buf, byteOffset, err := r.readBytes(startLine, int64(count))
57 if err != nil {
58 return 0, err
59 }
60
61 for n = 0; n < count && startLine+int64(n) < int64(len(r.index)); n++ {
62 lineno := startLine + int64(n)
63 start, end := int64(0), r.index[lineno]-byteOffset
64 if lineno > 0 {
65 start = r.index[lineno-1] - byteOffset
66 }
67 lines[n] = buf[start:end]
68 }
69
70 if n < count {
71 return n, io.EOF
72 }
73 return n, nil
74}
75
76// indexTo reads data and computes the line index until there is information
77// for line or a read returns io.EOF. It returns an error if and only if there
78// is an error reading data.
79func (r *lineReaderAt) indexTo(line int64) error {
80 var buf [indexBufferSize]byte
81
82 offset := r.lastOffset()
83 for int64(len(r.index)) < line {
84 n, err := r.r.ReadAt(buf[:], offset)
85 if err != nil && err != io.EOF {
86 return err
87 }
88 for _, b := range buf[:n] {
89 offset++
90 if b == '\n' {
91 r.index = append(r.index, offset)
92 }
93 }
94 if err == io.EOF {
95 if offset > r.lastOffset() {
96 r.index = append(r.index, offset)
97 }
98 r.eof = true
99 break
100 }
101 }
102 return nil
103}
104
105func (r *lineReaderAt) lastOffset() int64 {
106 if n := len(r.index); n > 0 {
107 return r.index[n-1]
108 }
109 return 0
110}
111
112// readBytes reads the bytes of the n lines starting at line and returns the
113// bytes and the offset of the first byte in the underlying source.
114func (r *lineReaderAt) readBytes(line, n int64) (b []byte, offset int64, err error) {
115 indexLen := int64(len(r.index))
116
117 var size int64
118 if line > indexLen {
119 offset = r.index[indexLen-1]
120 } else if line > 0 {
121 offset = r.index[line-1]
122 }
123 if n > 0 {
124 if line+n > indexLen {
125 size = r.index[indexLen-1] - offset
126 } else {
127 size = r.index[line+n-1] - offset
128 }
129 }
130
131 b = make([]byte, size)
132 if _, err := r.r.ReadAt(b, offset); err != nil {
133 if err == io.EOF {
134 err = errors.New("ReadLinesAt: corrupt line index or changed source data")
135 }
136 return nil, 0, err
137 }
138 return b, offset, nil
139}
140
141func isLen(r io.ReaderAt, n int64) (bool, error) {
142 off := n - 1
143 if off < 0 {
144 off = 0
145 }
146
147 var b [2]byte
148 nr, err := r.ReadAt(b[:], off)
149 if err == io.EOF {
150 return (n == 0 && nr == 0) || (n > 0 && nr == 1), nil
151 }
152 return false, err
153}
154
155// copyFrom writes bytes starting from offset off in src to dst stopping at the
156// end of src or at the first error. copyFrom returns the number of bytes
157// written and any error.
158func copyFrom(dst io.Writer, src io.ReaderAt, off int64) (written int64, err error) {
159 buf := make([]byte, byteBufferSize)
160 for {
161 nr, rerr := src.ReadAt(buf, off)
162 if nr > 0 {
163 nw, werr := dst.Write(buf[0:nr])
164 if nw > 0 {
165 written += int64(nw)
166 }
167 if werr != nil {
168 err = werr
169 break
170 }
171 if nr != nw {
172 err = io.ErrShortWrite
173 break
174 }
175 off += int64(nr)
176 }
177 if rerr != nil {
178 if rerr != io.EOF {
179 err = rerr
180 }
181 break
182 }
183 }
184 return written, err
185}
186
187// copyLinesFrom writes lines starting from line off in src to dst stopping at
188// the end of src or at the first error. copyLinesFrom returns the number of
189// lines written and any error.
190func copyLinesFrom(dst io.Writer, src LineReaderAt, off int64) (written int64, err error) {
191 buf := make([][]byte, lineBufferSize)
192ReadLoop:
193 for {
194 nr, rerr := src.ReadLinesAt(buf, off)
195 if nr > 0 {
196 for _, line := range buf[0:nr] {
197 nw, werr := dst.Write(line)
198 if nw > 0 {
199 written++
200 }
201 if werr != nil {
202 err = werr
203 break ReadLoop
204 }
205 if len(line) != nw {
206 err = io.ErrShortWrite
207 break ReadLoop
208 }
209 }
210 off += int64(nr)
211 }
212 if rerr != nil {
213 if rerr != io.EOF {
214 err = rerr
215 }
216 break
217 }
218 }
219 return written, err
220}