Debian Codegraph @

bgzf/reader.go

raw
1 // Copyright ©2012 The bíogo Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package bgzf
6
7 import (
8 "bufio"
9 "bytes"
10 "compress/flate"
11 "compress/gzip"
12 "io"
13 "runtime"
14 "sync"
15 )
16
17 // countReader wraps flate.Reader, adding support for querying current offset.
18 type countReader struct {
19 // Underlying Reader.
20 fr flate.Reader
21
22 // Offset within the underlying reader.
23 off int64
24 }
25
26 // newCountReader returns a new countReader.
27 func newCountReader(r io.Reader) *countReader {
28 switch r := r.(type) {
29 case *countReader:
30 panic("bgzf: illegal use of internal type")
31 case flate.Reader:
32 return &countReader{fr: r}
33 default:
34 return &countReader{fr: bufio.NewReader(r)}
35 }
36 }
37
38 // Read is required to satisfy flate.Reader.
39 func (r *countReader) Read(p []byte) (int, error) {
40 n, err := r.fr.Read(p)
41 r.off += int64(n)
42 return n, err
43 }
44
45 // ReadByte is required to satisfy flate.Reader.
46 func (r *countReader) ReadByte() (byte, error) {
47 b, err := r.fr.ReadByte()
48 if err == nil {
49 r.off++
50 }
51 return b, err
52 }
53
54 // offset returns the current offset in the underlying reader.
55 func (r *countReader) offset() int64 { return r.off }
56
57 // seek moves the countReader to the specified offset using rs as the
58 // underlying reader.
59 func (r *countReader) seek(rs io.ReadSeeker, off int64) error {
60 _, err := rs.Seek(off, 0)
61 if err != nil {
62 return err
63 }
64
65 type reseter interface {
66 Reset(io.Reader)
67 }
68 switch cr := r.fr.(type) {
69 case reseter:
70 cr.Reset(rs)
71 default:
72 r.fr = newCountReader(rs)
73 }
74 r.off = off
75
76 return nil
77 }
78
79 // buffer is a flate.Reader used by a decompressor to store read-ahead data.
80 type buffer struct {
81 // Buffered compressed data from read ahead.
82 off int // Current position in buffered data.
83 size int // Total size of buffered data.
84 data [MaxBlockSize]byte
85 }
86
87 // Read provides the flate.Decompressor Read method.
88 func (r *buffer) Read(b []byte) (int, error) {
89 if r.off >= r.size {
90 return 0, io.EOF
91 }
92 if n := r.size - r.off; len(b) > n {
93 b = b[:n]
94 }
95 n := copy(b, r.data[r.off:])
96 r.off += n
97 return n, nil
98 }
99
100 // ReadByte provides the flate.Decompressor ReadByte method.
101 func (r *buffer) ReadByte() (byte, error) {
102 if r.off == r.size {
103 return 0, io.EOF
104 }
105 b := r.data[r.off]
106 r.off++
107 return b, nil
108 }
109
110 // reset makes the buffer available to store data.
111 func (r *buffer) reset() { r.size = 0 }
112
113 // hasData returns whether the buffer has any data buffered.
114 func (r *buffer) hasData() bool { return r.size != 0 }
115
116 // readLimited reads n bytes into the buffer from the given source.
117 func (r *buffer) readLimited(n int, src *countReader) error {
118 if r.hasData() {
119 panic("bgzf: read into non-empty buffer")
120 }
121 r.off = 0
122 var err error
123 r.size, err = io.ReadFull(src, r.data[:n])
124 return err
125 }
126
127 // equals returns a boolean indicating the equality between
128 // the buffered data and the given byte slice.
129 func (r *buffer) equals(b []byte) bool { return bytes.Equal(r.data[:r.size], b) }
130
131 // decompressor is a gzip member decompressor worker.
132 type decompressor struct {
133 owner *Reader
134
135 gz gzip.Reader
136
137 cr *countReader
138
139 // Current block size.
140 blockSize int
141
142 // Buffered compressed data from read ahead.
143 buf buffer
144
145 // Decompressed data.
146 wg sync.WaitGroup
147 blk Block
148
149 err error
150 }
151
152 // Read provides the Read method for the decompressor's gzip.Reader.
153 func (d *decompressor) Read(b []byte) (int, error) {
154 if d.buf.hasData() {
155 return d.buf.Read(b)
156 }
157 return d.cr.Read(b)
158 }
159
160 // ReadByte provides the ReadByte method for the decompressor's gzip.Reader.
161 func (d *decompressor) ReadByte() (byte, error) {
162 if d.buf.hasData() {
163 return d.buf.ReadByte()
164 }
165 return d.cr.ReadByte()
166 }
167
168 // lazyBlock conditionally creates a ready to use Block.
169 func (d *decompressor) lazyBlock() {
170 if d.blk == nil {
171 if w, ok := d.owner.cache.(Wrapper); ok {
172 d.blk = w.Wrap(&block{owner: d.owner})
173 } else {
174 d.blk = &block{owner: d.owner}
175 }
176 return
177 }
178 if !d.blk.ownedBy(d.owner) {
179 d.blk.setOwner(d.owner)
180 }
181 }
182
183 // acquireHead gains the read head from the decompressor's owner.
184 func (d *decompressor) acquireHead() {
185 d.wg.Add(1)
186 d.cr = <-d.owner.head
187 }
188
189 // releaseHead releases the read head back to the decompressor's owner.
190 func (d *decompressor) releaseHead() {
191 d.owner.head <- d.cr
192 d.cr = nil // Defensively zero the reader.
193 }
194
195 // wait waits for the current member to be decompressed or fail, and returns
196 // the resulting error state.
197 func (d *decompressor) wait() (Block, error) {
198 d.wg.Wait()
199 blk := d.blk
200 d.blk = nil
201 return blk, d.err
202 }
203
204 // using sets the Block for the decompressor to work with.
205 func (d *decompressor) using(b Block) *decompressor { d.blk = b; return d }
206
207 // nextBlockAt makes the decompressor ready for reading decompressed data
208 // from its Block. It checks if there is a cached Block for the nextBase,
209 // otherwise it seeks to the correct location if decompressor is not
210 // correctly positioned, and then reads the compressed data and fills
211 // the decompressed Block.
212 // After nextBlockAt returns without error, the decompressor's Block
213 // holds a valid gzip.Header and base offset.
214 func (d *decompressor) nextBlockAt(off int64, rs io.ReadSeeker) *decompressor {
215 d.err = nil
216 for {
217 exists, next := d.owner.cacheHasBlockFor(off)
218 if !exists {
219 break
220 }
221 off = next
222 }
223
224 d.lazyBlock()
225
226 d.acquireHead()
227 defer d.releaseHead()
228
229 if d.cr.offset() != off {
230 if rs == nil {
231 // It should not be possible for the expected next block base
232 // to be out of register with the count reader unless Seek
233 // has been called, so we know the base reader must be an
234 // io.ReadSeeker.
235 var ok bool
236 rs, ok = d.owner.r.(io.ReadSeeker)
237 if !ok {
238 panic("bgzf: unexpected offset without seek")
239 }
240 }
241 d.err = d.cr.seek(rs, off)
242 if d.err != nil {
243 d.wg.Done()
244 return d
245 }
246 }
247
248 d.blk.setBase(d.cr.offset())
249 d.err = d.readMember()
250 if d.err != nil {
251 d.wg.Done()
252 return d
253 }
254 d.blk.setHeader(d.gz.Header)
255 d.gz.Header = gzip.Header{} // Prevent retention of header field in next use.
256
257 // Decompress data into the decompressor's Block.
258 go func() {
259 d.err = d.blk.readFrom(&d.gz)
260 d.wg.Done()
261 }()
262
263 return d
264 }
265
266 // expectedMemberSize returns the size of the BGZF conformant gzip member.
267 // It returns -1 if no BGZF block size field is found.
268 func expectedMemberSize(h gzip.Header) int {
269 i := bytes.Index(h.Extra, bgzfExtraPrefix)
270 if i < 0 || i+5 >= len(h.Extra) {
271 return -1
272 }
273 return (int(h.Extra[i+4]) | int(h.Extra[i+5])<<8) + 1
274 }
275
276 // readMember buffers the gzip member starting the current decompressor offset.
277 func (d *decompressor) readMember() error {
278 // Set the decompressor to Read from the underlying flate.Reader
279 // and mark the starting offset from which the underlying reader
280 // was used.
281 d.buf.reset()
282 mark := d.cr.offset()
283
284 err := d.gz.Reset(d)
285 if err != nil {
286 d.blockSize = -1
287 return err
288 }
289
290 d.blockSize = expectedMemberSize(d.gz.Header)
291 if d.blockSize < 0 {
292 return ErrNoBlockSize
293 }
294 skipped := int(d.cr.offset() - mark)
295 need := d.blockSize - skipped
296 if need == 0 {
297 return io.EOF
298 } else if need < 0 {
299 return ErrCorrupt
300 }
301
302 // Read compressed data into the decompressor buffer until the
303 // underlying flate.Reader is positioned at the end of the gzip
304 // member in which the readMember call was made.
305 return d.buf.readLimited(need, d.cr)
306 }
307
308 // Offset is a BGZF virtual offset.
309 type Offset struct {
310 File int64
311 Block uint16
312 }
313
314 // Chunk is a region of a BGZF file.
315 type Chunk struct {
316 Begin Offset
317 End Offset
318 }
319
320 // Reader implements BGZF blocked gzip decompression.
321 type Reader struct {
322 gzip.Header
323 r io.Reader
324
325 // head serialises access to the underlying
326 // io.Reader.
327 head chan *countReader
328
329 // lastChunk is the virtual file offset
330 // interval of the last successful read
331 // or seek operation.
332 lastChunk Chunk
333
334 // Blocked specifies the behaviour of the
335 // Reader at the end of a BGZF member.
336 // If the Reader is Blocked, a Read that
337 // reaches the end of a BGZF block will
338 // return io.EOF. This error is not sticky,
339 // so a subsequent Read will progress to
340 // the next block if it is available.
341 Blocked bool
342
343 // Non-concurrent work decompressor.
344 dec *decompressor
345
346 // Concurrent work fields.
347 waiting chan *decompressor
348 working chan *decompressor
349 control chan int64
350 done chan struct{}
351
352 current Block
353
354 // cache is the Reader block cache. If Cache is not nil,
355 // the cache is queried for blocks before an attempt to
356 // read from the underlying io.Reader.
357 mu sync.RWMutex
358 cache Cache
359
360 err error
361 }
362
363 // NewReader returns a new BGZF reader.
364 //
365 // The number of concurrent read decompressors is specified by rd. If rd
366 // is 0, GOMAXPROCS concurrent will be created. If rd is 1, blocks will
367 // be read synchronously without readahead. The returned Reader should
368 // be closed after use to avoid leaking resources.
369 func NewReader(r io.Reader, rd int) (*Reader, error) {
370 if rd == 0 {
371 rd = runtime.GOMAXPROCS(0)
372 }
373 bg := &Reader{
374 r: r,
375
376 head: make(chan *countReader, 1),
377 }
378 bg.head <- newCountReader(r)
379
380 // Make work loop control structures.
381 if rd > 1 {
382 bg.waiting = make(chan *decompressor, rd)
383 bg.working = make(chan *decompressor, rd)
384 bg.control = make(chan int64, 1)
385 bg.done = make(chan struct{})
386 for ; rd > 1; rd-- {
387 bg.waiting <- &decompressor{owner: bg}
388 }
389 }
390
391 // Read the first block now so we can fail before
392 // the first Read call if there is a problem.
393 bg.dec = &decompressor{owner: bg}
394 blk, err := bg.dec.nextBlockAt(0, nil).wait()
395 if err != nil {
396 return nil, err
397 }
398 bg.current = blk
399 bg.Header = bg.current.header()
400
401 // Set up work loop if rd was > 1.
402 if bg.control != nil {
403 bg.waiting <- bg.dec
404 bg.dec = nil
405 next := blk.NextBase()
406 go func() {
407 defer func() {
408 bg.mu.Lock()
409 bg.cache = nil
410 bg.mu.Unlock()
411 close(bg.done)
412 }()
413 for dec := range bg.waiting {
414 var open bool
415 if next < 0 {
416 next, open = <-bg.control
417 if !open {
418 return
419 }
420 } else {
421 select {
422 case next, open = <-bg.control:
423 if !open {
424 return
425 }
426 default:
427 }
428 }
429 dec.nextBlockAt(next, nil)
430 next = dec.blk.NextBase()
431 bg.working <- dec
432 }
433 }()
434 }
435
436 return bg, nil
437 }
438
439 // SetCache sets the cache to be used by the Reader.
440 func (bg *Reader) SetCache(c Cache) {
441 bg.mu.Lock()
442 bg.cache = c
443 bg.mu.Unlock()
444 }
445
446 // Seek performs a seek operation to the given virtual offset.
447 func (bg *Reader) Seek(off Offset) error {
448 rs, ok := bg.r.(io.ReadSeeker)
449 if !ok {
450 return ErrNotASeeker
451 }
452
453 if off.File != bg.current.Base() || !bg.current.hasData() {
454 ok := bg.cacheSwap(off.File)
455 if !ok {
456 var dec *decompressor
457 if bg.dec != nil {
458 dec = bg.dec
459 } else {
460 select {
461 case dec = <-bg.waiting:
462 case dec = <-bg.working:
463 blk, err := dec.wait()
464 if err == nil {
465 bg.keep(blk)
466 if blk.Base() == off.File {
467 // This decompressor had the block we
468 // wanted.
469 bg.current = blk
470 bg.control <- bg.current.NextBase()
471 bg.waiting <- dec
472 dec = nil
473 }
474 }
475 }
476 }
477 if dec != nil {
478 // Synchronously decompress the requested block using
479 // the selected decompressor. Not necessary if that
480 // decompressor had the block ready, as determined
481 // above.
482 bg.current, bg.err = dec.
483 using(bg.current).
484 nextBlockAt(off.File, rs).
485 wait()
486 if bg.dec == nil {
487 select {
488 case <-bg.control:
489 default:
490 }
491 bg.control <- bg.current.NextBase()
492 bg.waiting <- dec
493 }
494 bg.Header = bg.current.header()
495 if bg.err != nil {
496 return bg.err
497 }
498 }
499 }
500 }
501
502 bg.err = bg.current.seek(int64(off.Block))
503 if bg.err == nil {
504 bg.lastChunk = Chunk{Begin: off, End: off}
505 }
506
507 return bg.err
508 }
509
510 // LastChunk returns the region of the BGZF file read by the last
511 // successful read operation or the resulting virtual offset of
512 // the last successful seek operation.
513 func (bg *Reader) LastChunk() Chunk { return bg.lastChunk }
514
515 // BlockLen returns the number of bytes remaining to be read from the
516 // current BGZF block.
517 func (bg *Reader) BlockLen() int { return bg.current.len() }
518
519 // Close closes the reader and releases resources.
520 func (bg *Reader) Close() error {
521 if bg.control != nil {
522 close(bg.control)
523 close(bg.waiting)
524 <-bg.done
525 }
526 if bg.err == io.EOF {
527 return nil
528 }
529 return bg.err
530 }
531
532 // Read implements the io.Reader interface.
533 func (bg *Reader) Read(p []byte) (int, error) {
534 if bg.err != nil {
535 return 0, bg.err
536 }
537
538 // Discard leading empty blocks. This is an indexing
539 // optimisation to avoid retaining useless members
540 // in a BAI/CSI.
541 for bg.current.len() == 0 {
542 bg.err = bg.nextBlock()
543 if bg.err != nil {
544 return 0, bg.err
545 }
546 }
547
548 bg.lastChunk.Begin = bg.current.txOffset()
549
550 var n int
551 for n < len(p) && bg.err == nil {
552 var _n int
553 _n, bg.err = bg.current.Read(p[n:])
554 n += _n
555 if bg.err == io.EOF {
556 if n == len(p) {
557 bg.err = nil
558 break
559 }
560
561 if bg.Blocked {
562 bg.err = nil
563 bg.lastChunk.End = bg.current.txOffset()
564 return n, io.EOF
565 }
566
567 bg.err = bg.nextBlock()
568 if bg.err != nil {
569 break
570 }
571 }
572 }
573
574 bg.lastChunk.End = bg.current.txOffset()
575 return n, bg.err
576 }
577
578 // ReadByte implements the io.ByteReader interface.
579 func (bg *Reader) ReadByte() (byte, error) {
580 if bg.err != nil {
581 return 0, bg.err
582 }
583
584 // Discard leading empty blocks. This is an indexing
585 // optimisation to avoid retaining useless members
586 // in a BAI/CSI.
587 for bg.current.len() == 0 {
588 bg.err = bg.nextBlock()
589 if bg.err != nil {
590 return 0, bg.err
591 }
592 }
593
594 bg.lastChunk.Begin = bg.current.txOffset()
595
596 var b byte
597 b, bg.err = bg.current.ReadByte()
598 if bg.err == io.EOF {
599 if bg.Blocked {
600 bg.err = nil
601 bg.lastChunk.End = bg.current.txOffset()
602 return b, io.EOF
603 }
604
605 bg.err = bg.nextBlock()
606 }
607
608 bg.lastChunk.End = bg.current.txOffset()
609 return b, bg.err
610 }
611
612 // nextBlock swaps the current decompressed block for the next
613 // in the stream. If the block is available from the cache
614 // no additional work is done, otherwise a decompressor is
615 // used or waited on.
616 func (bg *Reader) nextBlock() error {
617 base := bg.current.NextBase()
618 ok := bg.cacheSwap(base)
619 if ok {
620 bg.Header = bg.current.header()
621 return nil
622 }
623
624 var err error
625 if bg.dec != nil {
626 bg.dec.using(bg.current).nextBlockAt(base, nil)
627 bg.current, err = bg.dec.wait()
628 } else {
629 var ok bool
630 for i := 0; i < cap(bg.working); i++ {
631 dec := <-bg.working
632 bg.current, err = dec.wait()
633 bg.waiting <- dec
634 if bg.current.Base() == base {
635 ok = true
636 break
637 }
638 if err == nil {
639 bg.keep(bg.current)
640 bg.current = nil
641 }
642 }
643 if !ok {
644 panic("bgzf: unexpected block")
645 }
646 }
647 if err != nil {
648 return err
649 }
650
651 // Only set header if there was no error.
652 h := bg.current.header()
653 if bg.current.isMagicBlock() {
654 // TODO(kortschak): Do this more carefully. It may be that
655 // someone actually has extra data in this field that we are
656 // clobbering.
657 bg.Header.Extra = h.Extra
658 } else {
659 bg.Header = h
660 }
661
662 return nil
663 }
664
665 // cacheSwap attempts to swap the current Block for a cached Block
666 // for the given base offset. It returns true if successful.
667 func (bg *Reader) cacheSwap(base int64) bool {
668 bg.mu.RLock()
669 defer bg.mu.RUnlock()
670 if bg.cache == nil {
671 return false
672 }
673
674 blk, err := bg.cachedBlockFor(base)
675 if err != nil {
676 return false
677 }
678 if blk != nil {
679 // TODO(kortschak): Under some conditions, e.g. FIFO
680 // cache we will be discarding a non-nil evicted Block.
681 // Consider retaining these in a sync.Pool.
682 bg.cachePut(bg.current)
683 bg.current = blk
684 return true
685 }
686 var retained bool
687 bg.current, retained = bg.cachePut(bg.current)
688 if retained {
689 bg.current = nil
690 }
691 return false
692 }
693
694 // cacheHasBlockFor returns whether the Reader's cache has a block
695 // for the given base offset. If the requested Block exists, the base
696 // offset of the following Block is returned.
697 func (bg *Reader) cacheHasBlockFor(base int64) (exists bool, next int64) {
698 bg.mu.RLock()
699 defer bg.mu.RUnlock()
700 if bg.cache == nil {
701 return false, -1
702 }
703 return bg.cache.Peek(base)
704 }
705
706 // cachedBlockFor returns a non-nil Block if the Reader has access to a
707 // cache and the cache holds the block with the given base and the
708 // correct owner, otherwise it returns nil. If the Block's owner is not
709 // correct, or the Block cannot seek to the start of its data, a non-nil
710 // error is returned.
711 func (bg *Reader) cachedBlockFor(base int64) (Block, error) {
712 blk := bg.cache.Get(base)
713 if blk != nil {
714 if !blk.ownedBy(bg) {
715 return nil, ErrContaminatedCache
716 }
717 err := blk.seek(0)
718 if err != nil {
719 return nil, err
720 }
721 }
722 return blk, nil
723 }
724
725 // cachePut puts the given Block into the cache if it exists, it returns
726 // the Block that was evicted or b if it was not retained, and whether
727 // the Block was retained by the cache.
728 func (bg *Reader) cachePut(b Block) (evicted Block, retained bool) {
729 if b == nil || !b.hasData() {
730 return b, false
731 }
732 return bg.cache.Put(b)
733 }
734
735 // keep puts the given Block into the cache if it exists.
736 func (bg *Reader) keep(b Block) {
737 if b == nil || !b.hasData() {
738 return
739 }
740 bg.mu.RLock()
741 defer bg.mu.RUnlock()
742 if bg.cache != nil {
743 bg.cache.Put(b)
744 }
745 }
746
747 // Begin returns a Tx that starts at the current virtual offset.
748 func (bg *Reader) Begin() Tx { return Tx{begin: bg.lastChunk.Begin, r: bg} }
749
750 // Tx represents a multi-read transaction.
751 type Tx struct {
752 begin Offset
753 r *Reader
754 }
755
756 // End returns the Chunk spanning the transaction. After return the Tx is
757 // no longer valid.
758 func (t *Tx) End() Chunk {
759 c := Chunk{Begin: t.begin, End: t.r.lastChunk.End}
760 t.r = nil
761 return c
762 }