| 1 |
use alloc::{vec, vec::Vec}; |
| 2 |
|
| 3 |
/// The default buffer capacity that we use for the stream buffer. |
| 4 |
const DEFAULT_BUFFER_CAPACITY: usize = 64 * (1 << 10); // 64 KB |
| 5 |
|
| 6 |
/// A fairly simple roll buffer for supporting stream searches. |
| 7 |
/// |
| 8 |
/// This buffer acts as a temporary place to store a fixed amount of data when |
| 9 |
/// reading from a stream. Its central purpose is to allow "rolling" some |
| 10 |
/// suffix of the data to the beginning of the buffer before refilling it with |
| 11 |
/// more data from the stream. For example, let's say we are trying to match |
| 12 |
/// "foobar" on a stream. When we report the match, we'd like to not only |
| 13 |
/// report the correct offsets at which the match occurs, but also the matching |
| 14 |
/// bytes themselves. So let's say our stream is a file with the following |
| 15 |
/// contents: `test test foobar test test`. Now assume that we happen to read |
| 16 |
/// the aforementioned file in two chunks: `test test foo` and `bar test test`. |
| 17 |
/// Naively, it would not be possible to report a single contiguous `foobar` |
| 18 |
/// match, but this roll buffer allows us to do that. Namely, after the second |
| 19 |
/// read, the contents of the buffer should be `st foobar test test`, where the |
| 20 |
/// search should ultimately resume immediately after `foo`. (The prefix `st ` |
| 21 |
/// is included because the roll buffer saves N bytes at the end of the buffer, |
| 22 |
/// where N is the maximum possible length of a match.) |
| 23 |
/// |
| 24 |
/// A lot of the logic for dealing with this is unfortunately split out between |
| 25 |
/// this roll buffer and the `StreamChunkIter`. |
| 26 |
/// |
| 27 |
/// Note also that this buffer is not actually required to just report matches. |
| 28 |
/// Because a `Match` is just some offsets. But it *is* required for supporting |
| 29 |
/// things like `try_stream_replace_all` because that needs some mechanism for |
| 30 |
/// knowing which bytes in the stream correspond to a match and which don't. So |
| 31 |
/// when a match occurs across two `read` calls, *something* needs to retain |
| 32 |
/// the bytes from the previous `read` call because you don't know before the |
| 33 |
/// second read call whether a match exists or not. |
| 34 |
#[derive(Debug)] |
| 35 |
pub(crate) struct Buffer { |
| 36 |
/// The raw buffer contents. This has a fixed size and never increases. |
| 37 |
buf: Vec<u8>, |
| 38 |
/// The minimum size of the buffer, which is equivalent to the maximum |
| 39 |
/// possible length of a match. This corresponds to the amount that we |
| 40 |
/// roll |
| 41 |
min: usize, |
| 42 |
/// The end of the contents of this buffer. |
| 43 |
end: usize, |
| 44 |
} |
| 45 |
|
| 46 |
impl Buffer { |
| 47 |
/// Create a new buffer for stream searching. The minimum buffer length |
| 48 |
/// given should be the size of the maximum possible match length. |
| 49 |
pub(crate) fn new(min_buffer_len: usize) -> Buffer { |
| 50 |
let min = core::cmp::max(1, min_buffer_len); |
| 51 |
// The minimum buffer amount is also the amount that we roll our |
| 52 |
// buffer in order to support incremental searching. To this end, |
| 53 |
// our actual capacity needs to be at least 1 byte bigger than our |
| 54 |
// minimum amount, otherwise we won't have any overlap. In actuality, |
| 55 |
// we want our buffer to be a bit bigger than that for performance |
| 56 |
// reasons, so we set a lower bound of `8 * min`. |
| 57 |
// |
| 58 |
// TODO: It would be good to find a way to test the streaming |
| 59 |
// implementation with the minimal buffer size. For now, we just |
| 60 |
// uncomment out the next line and comment out the subsequent line. |
| 61 |
// let capacity = 1 + min; |
| 62 |
let capacity = core::cmp::max(min * 8, DEFAULT_BUFFER_CAPACITY); |
| 63 |
Buffer { buf: vec![0; capacity], min, end: 0 } |
| 64 |
} |
| 65 |
|
| 66 |
/// Return the contents of this buffer. |
| 67 |
#[inline] |
| 68 |
pub(crate) fn buffer(&self) -> &[u8] { |
| 69 |
&self.buf[..self.end] |
| 70 |
} |
| 71 |
|
| 72 |
/// Return the minimum size of the buffer. The only way a buffer may be |
| 73 |
/// smaller than this is if the stream itself contains less than the |
| 74 |
/// minimum buffer amount. |
| 75 |
#[inline] |
| 76 |
pub(crate) fn min_buffer_len(&self) -> usize { |
| 77 |
self.min |
| 78 |
} |
| 79 |
|
| 80 |
/// Return all free capacity in this buffer. |
| 81 |
fn free_buffer(&mut self) -> &mut [u8] { |
| 82 |
&mut self.buf[self.end..] |
| 83 |
} |
| 84 |
|
| 85 |
/// Refill the contents of this buffer by reading as much as possible into |
| 86 |
/// this buffer's free capacity. If no more bytes could be read, then this |
| 87 |
/// returns false. Otherwise, this reads until it has filled the buffer |
| 88 |
/// past the minimum amount. |
| 89 |
pub(crate) fn fill<R: std::io::Read>( |
| 90 |
&mut self, |
| 91 |
mut rdr: R, |
| 92 |
) -> std::io::Result<bool> { |
| 93 |
let mut readany = false; |
| 94 |
loop { |
| 95 |
let readlen = rdr.read(self.free_buffer())?; |
| 96 |
if readlen == 0 { |
| 97 |
return Ok(readany); |
| 98 |
} |
| 99 |
readany = true; |
| 100 |
self.end += readlen; |
| 101 |
if self.buffer().len() >= self.min { |
| 102 |
return Ok(true); |
| 103 |
} |
| 104 |
} |
| 105 |
} |
| 106 |
|
| 107 |
/// Roll the contents of the buffer so that the suffix of this buffer is |
| 108 |
/// moved to the front and all other contents are dropped. The size of the |
| 109 |
/// suffix corresponds precisely to the minimum buffer length. |
| 110 |
/// |
| 111 |
/// This should only be called when the entire contents of this buffer have |
| 112 |
/// been searched. |
| 113 |
pub(crate) fn roll(&mut self) { |
| 114 |
let roll_start = self |
| 115 |
.end |
| 116 |
.checked_sub(self.min) |
| 117 |
.expect("buffer capacity should be bigger than minimum amount"); |
| 118 |
let roll_end = roll_start + self.min; |
| 119 |
|
| 120 |
assert!(roll_end <= self.end); |
| 121 |
self.buf.copy_within(roll_start..roll_end, 0); |
| 122 |
self.end = self.min; |
| 123 |
} |
| 124 |
} |