#[derive(Debug, Clone, PartialEq, Eq)]
pub enum KnitError {
MissingOrigin(Vec<u8>),
BadDeltaHeader(Vec<u8>),
TruncatedDelta,
Gzip(String),
EmptyRecord,
HeaderFields(Vec<u8>),
HeaderCount(Vec<u8>),
LineCount { declared: usize, actual: usize },
BadEndMarker { expected: Vec<u8>, actual: Vec<u8> },
MissingTrailingNewline,
NetworkMissingKeyTerminator,
NetworkMissingParentsTerminator,
NetworkMissingNoEolByte,
BadIndexValue(Vec<u8>),
TooManyCompressionParents(usize),
UnexpectedVersion { wanted: Vec<u8>, got: Vec<u8> },
BadKnitHeader { path: String },
KndxCorrupt { line: Vec<u8>, detail: String },
Corrupt(String),
RevisionNotPresent(KnitKey),
ReadOnly,
NotImplemented(&'static str),
Retry(String),
Aborted(String),
ExistingContent(Vec<u8>),
BadSha1 {
key: KnitKey,
lines: Vec<Vec<u8>>,
actual: Vec<u8>,
expected: Vec<u8>,
},
}
impl std::fmt::Display for KnitError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
KnitError::MissingOrigin(l) => {
write!(f, "annotated knit line missing origin: {:?}", l)
}
KnitError::BadDeltaHeader(h) => write!(f, "bad delta header: {:?}", h),
KnitError::TruncatedDelta => write!(f, "delta truncated: too few lines"),
KnitError::Gzip(msg) => write!(f, "corrupt compressed record: {}", msg),
KnitError::EmptyRecord => write!(f, "empty knit record"),
KnitError::HeaderFields(h) => {
write!(f, "unexpected number of elements in record header: {:?}", h)
}
KnitError::HeaderCount(h) => {
write!(f, "record header line count is not an integer: {:?}", h)
}
KnitError::LineCount { declared, actual } => {
write!(
f,
"incorrect number of lines {} != {} in record",
actual, declared
)
}
KnitError::BadEndMarker { expected, actual } => write!(
f,
"unexpected version end line {:?}, wanted {:?}",
actual, expected
),
KnitError::MissingTrailingNewline => {
write!(f, "corrupt lines value: last line missing trailing newline")
}
KnitError::NetworkMissingKeyTerminator => {
write!(f, "knit network record key missing newline terminator")
}
KnitError::NetworkMissingParentsTerminator => {
write!(f, "knit network record parents missing newline terminator")
}
KnitError::NetworkMissingNoEolByte => {
write!(f, "knit network record missing noeol byte")
}
KnitError::BadIndexValue(v) => {
write!(f, "bad knit index value: {:?}", v)
}
KnitError::TooManyCompressionParents(n) => {
write!(f, "Too many compression parents: {}", n)
}
KnitError::UnexpectedVersion { wanted, got } => {
write!(f, "unexpected version, wanted {:?}, got {:?}", wanted, got)
}
KnitError::BadKnitHeader { path } => {
write!(f, "knit index file {} does not have a valid header", path)
}
KnitError::KndxCorrupt { line, detail } => {
write!(f, "kndx corrupt record {:?}: {}", line, detail)
}
KnitError::Corrupt(msg) => write!(f, "knit corrupt: {}", msg),
KnitError::RevisionNotPresent(key) => write!(f, "Revision not present: {:?}", key),
KnitError::ReadOnly => write!(f, "write attempted on read-only knit index"),
KnitError::NotImplemented(name) => write!(f, "{}", name),
KnitError::Retry(ctx) => write!(f, "pack listing changed, retry needed: {}", ctx),
KnitError::Aborted(ctx) => write!(f, "operation aborted: {}", ctx),
KnitError::ExistingContent(digest) => {
write!(f, "content already present: {:?}", digest)
}
KnitError::BadSha1 {
key,
actual,
expected,
..
} => write!(
f,
"sha1 mismatch for {:?}: got {:?}, expected {:?}",
key.last().map(Vec::as_slice).unwrap_or(&[]),
actual,
expected
),
}
}
}
impl std::error::Error for KnitError {}
#[derive(Debug)]
pub enum KndxLoadError {
Transport(crate::transport::TransportError),
Knit(KnitError),
}
impl std::fmt::Display for KndxLoadError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
KndxLoadError::Transport(e) => e.fmt(f),
KndxLoadError::Knit(e) => e.fmt(f),
}
}
}
impl std::error::Error for KndxLoadError {}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DeltaHunk<T> {
pub start: usize,
pub end: usize,
pub count: usize,
pub lines: Vec<T>,
}
pub type AnnotatedLine = (Vec<u8>, Vec<u8>);
pub fn parse_fulltext(lines: &[&[u8]]) -> Result<Vec<AnnotatedLine>, KnitError> {
lines.iter().map(|l| split_annotated(l)).collect()
}
pub fn lower_fulltext(content: &[(Vec<u8>, Vec<u8>)]) -> Vec<Vec<u8>> {
content
.iter()
.map(|(origin, text)| {
let mut out = Vec::with_capacity(origin.len() + 1 + text.len());
out.extend_from_slice(origin);
out.push(b' ');
out.extend_from_slice(text);
out
})
.collect()
}
pub fn parse_line_delta_annotated(
lines: &[&[u8]],
) -> Result<Vec<DeltaHunk<AnnotatedLine>>, KnitError> {
parse_line_delta_inner(lines, true).map(|hunks| {
hunks
.into_iter()
.map(|h| DeltaHunk {
start: h.start,
end: h.end,
count: h.count,
lines: h
.lines
.into_iter()
.map(|line| match line {
ParsedLine::Annotated(o, t) => (o, t),
ParsedLine::Plain(_) => unreachable!(),
})
.collect(),
})
.collect()
})
}
pub fn parse_line_delta_plain(lines: &[&[u8]]) -> Result<Vec<DeltaHunk<Vec<u8>>>, KnitError> {
parse_line_delta_inner(lines, false).map(|hunks| {
hunks
.into_iter()
.map(|h| DeltaHunk {
start: h.start,
end: h.end,
count: h.count,
lines: h
.lines
.into_iter()
.map(|line| match line {
ParsedLine::Plain(t) => t,
ParsedLine::Annotated(_, t) => t,
})
.collect(),
})
.collect()
})
}
pub fn lower_line_delta_annotated(delta: &[DeltaHunk<AnnotatedLine>]) -> Vec<Vec<u8>> {
let mut out = Vec::new();
for hunk in delta {
out.push(format!("{},{},{}\n", hunk.start, hunk.end, hunk.count).into_bytes());
for (origin, text) in &hunk.lines {
let mut line = Vec::with_capacity(origin.len() + 1 + text.len());
line.extend_from_slice(origin);
line.push(b' ');
line.extend_from_slice(text);
out.push(line);
}
}
out
}
pub fn parse_line_delta_raw(lines: &[&[u8]]) -> Result<Vec<DeltaHunk<Vec<u8>>>, KnitError> {
let mut out = Vec::new();
let mut i = 0;
while i < lines.len() {
let (start, end, count) = parse_delta_header(lines[i])?;
i += 1;
if i + count > lines.len() {
return Err(KnitError::TruncatedDelta);
}
let hunk_lines: Vec<Vec<u8>> = lines[i..i + count].iter().map(|l| l.to_vec()).collect();
i += count;
out.push(DeltaHunk {
start,
end,
count,
lines: hunk_lines,
});
}
Ok(out)
}
pub fn lower_line_delta_raw(delta: &[DeltaHunk<Vec<u8>>]) -> Vec<Vec<u8>> {
let mut out = Vec::new();
for hunk in delta {
out.push(format!("{},{},{}\n", hunk.start, hunk.end, hunk.count).into_bytes());
for line in &hunk.lines {
out.push(line.clone());
}
}
out
}
pub fn get_line_delta_blocks(
delta: &[(usize, usize, usize)],
source: &[&[u8]],
target: &[&[u8]],
) -> Vec<(usize, usize, usize)> {
let target_len = target.len();
let mut out = Vec::new();
let mut s_pos = 0usize;
let mut t_pos = 0usize;
for &(s_begin, s_end, t_len) in delta {
let true_n = s_begin - s_pos;
let mut n = true_n;
if n > 0 {
if source[s_pos + n - 1] != target[t_pos + n - 1] {
n -= 1;
}
if n > 0 {
out.push((s_pos, t_pos, n));
}
}
t_pos += t_len + true_n;
s_pos = s_end;
}
let mut n = target_len - t_pos;
if n > 0 {
if source[s_pos + n - 1] != target[t_pos + n - 1] {
n -= 1;
}
if n > 0 {
out.push((s_pos, t_pos, n));
}
}
out.push((s_pos + (target_len - t_pos), target_len, 0));
out
}
pub trait KnitContent {
type DeltaLine: Clone;
fn should_strip_eol(&self) -> bool;
fn set_should_strip_eol(&mut self, strip: bool);
fn apply_delta(&mut self, delta: &[DeltaHunk<Self::DeltaLine>], new_version_id: &[u8]);
fn text(&self) -> Vec<Vec<u8>>;
fn annotate(&self) -> Vec<AnnotatedLine>;
fn annotate_mut(&mut self) -> &mut Vec<AnnotatedLine> {
unimplemented!("annotate_mut is only supported for annotated content")
}
fn annotate_raw(&self) -> Vec<AnnotatedLine>;
fn delta_line_from_annotated(pair: &AnnotatedLine) -> Self::DeltaLine;
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct AnnotatedKnitContent {
pub lines: Vec<AnnotatedLine>,
should_strip_eol: bool,
}
impl AnnotatedKnitContent {
pub fn new(lines: Vec<AnnotatedLine>) -> Self {
Self {
lines,
should_strip_eol: false,
}
}
}
impl KnitContent for AnnotatedKnitContent {
type DeltaLine = AnnotatedLine;
fn should_strip_eol(&self) -> bool {
self.should_strip_eol
}
fn set_should_strip_eol(&mut self, strip: bool) {
self.should_strip_eol = strip;
}
fn apply_delta(&mut self, delta: &[DeltaHunk<AnnotatedLine>], _new_version_id: &[u8]) {
let mut offset: isize = 0;
for hunk in delta {
let start = (offset + hunk.start as isize) as usize;
let end = (offset + hunk.end as isize) as usize;
self.lines.splice(start..end, hunk.lines.iter().cloned());
offset += hunk.start as isize - hunk.end as isize + hunk.count as isize;
}
}
fn text(&self) -> Vec<Vec<u8>> {
let mut out: Vec<Vec<u8>> = self.lines.iter().map(|(_, t)| t.clone()).collect();
if self.should_strip_eol {
if let Some(last) = out.last_mut() {
if last.ends_with(b"\n") {
last.pop();
}
}
}
out
}
fn annotate(&self) -> Vec<AnnotatedLine> {
let mut out = self.lines.clone();
if self.should_strip_eol {
if let Some((_, last)) = out.last_mut() {
if last.ends_with(b"\n") {
last.pop();
}
}
}
out
}
fn annotate_mut(&mut self) -> &mut Vec<AnnotatedLine> {
&mut self.lines
}
fn annotate_raw(&self) -> Vec<AnnotatedLine> {
self.lines.clone()
}
fn delta_line_from_annotated(pair: &AnnotatedLine) -> Self::DeltaLine {
pair.clone()
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PlainKnitContent {
pub lines: Vec<Vec<u8>>,
pub version_id: Vec<u8>,
should_strip_eol: bool,
}
impl PlainKnitContent {
pub fn new(lines: Vec<Vec<u8>>, version_id: Vec<u8>) -> Self {
Self {
lines,
version_id,
should_strip_eol: false,
}
}
}
impl KnitContent for PlainKnitContent {
type DeltaLine = Vec<u8>;
fn should_strip_eol(&self) -> bool {
self.should_strip_eol
}
fn set_should_strip_eol(&mut self, strip: bool) {
self.should_strip_eol = strip;
}
fn apply_delta(&mut self, delta: &[DeltaHunk<Vec<u8>>], new_version_id: &[u8]) {
let mut offset: isize = 0;
for hunk in delta {
let start = (offset + hunk.start as isize) as usize;
let end = (offset + hunk.end as isize) as usize;
self.lines.splice(start..end, hunk.lines.iter().cloned());
offset += hunk.start as isize - hunk.end as isize + hunk.count as isize;
}
self.version_id = new_version_id.to_vec();
}
fn text(&self) -> Vec<Vec<u8>> {
let mut out = self.lines.clone();
if self.should_strip_eol {
if let Some(last) = out.last_mut() {
if last.ends_with(b"\n") {
last.pop();
}
}
}
out
}
fn annotate(&self) -> Vec<AnnotatedLine> {
let mut out: Vec<AnnotatedLine> = self
.lines
.iter()
.map(|l| (self.version_id.clone(), l.clone()))
.collect();
if self.should_strip_eol {
if let Some((_, last)) = out.last_mut() {
if last.ends_with(b"\n") {
last.pop();
}
}
}
out
}
fn annotate_raw(&self) -> Vec<AnnotatedLine> {
self.lines
.iter()
.map(|l| (self.version_id.clone(), l.clone()))
.collect()
}
fn delta_line_from_annotated(pair: &AnnotatedLine) -> Self::DeltaLine {
pair.1.clone()
}
}
pub trait KnitFactory {
type Content: KnitContent + Clone;
fn annotated(&self) -> bool;
fn parse_fulltext_content(
&self,
lines: &[&[u8]],
version_id: &[u8],
) -> Result<Self::Content, KnitError>;
fn parse_line_delta(
&self,
lines: &[&[u8]],
) -> Result<Vec<DeltaHunk<<Self::Content as KnitContent>::DeltaLine>>, KnitError>;
fn make(&self, lines: Vec<Vec<u8>>, version_id: Vec<u8>) -> Self::Content;
fn lower_fulltext(&self, content: &Self::Content) -> Vec<Vec<u8>>;
fn lower_line_delta(
&self,
delta: &[DeltaHunk<<Self::Content as KnitContent>::DeltaLine>],
) -> Vec<Vec<u8>>;
fn fulltext_payload_lines(&self, body_lines: &[Vec<u8>]) -> Result<Vec<Vec<u8>>, KnitError>;
fn linedelta_payload_lines(&self, body_lines: &[Vec<u8>]) -> Result<Vec<Vec<u8>>, KnitError>;
fn parse_record(
&self,
version_id: &[u8],
body_lines: &[&[u8]],
method: KnitMethod,
noeol: bool,
base_content: Option<&Self::Content>,
) -> Result<Self::Content, KnitError> {
let mut content = match method {
KnitMethod::Fulltext => self.parse_fulltext_content(body_lines, version_id)?,
KnitMethod::LineDelta => {
let base = base_content.ok_or_else(|| {
KnitError::BadIndexValue(b"line-delta record requires base content".to_vec())
})?;
let mut content = base.clone();
let delta = self.parse_line_delta(body_lines)?;
content.apply_delta(&delta, version_id);
content
}
KnitMethod::NoEol => {
return Err(KnitError::BadIndexValue(
b"NoEol is not a storage method; use Fulltext or LineDelta".to_vec(),
))
}
};
content.set_should_strip_eol(noeol);
Ok(content)
}
}
#[derive(Debug, Default, Clone, Copy)]
pub struct KnitAnnotateFactory;
impl KnitFactory for KnitAnnotateFactory {
type Content = AnnotatedKnitContent;
fn annotated(&self) -> bool {
true
}
fn parse_fulltext_content(
&self,
lines: &[&[u8]],
_version_id: &[u8],
) -> Result<Self::Content, KnitError> {
let pairs = parse_fulltext(lines)?;
Ok(AnnotatedKnitContent::new(pairs))
}
fn parse_line_delta(
&self,
lines: &[&[u8]],
) -> Result<Vec<DeltaHunk<AnnotatedLine>>, KnitError> {
parse_line_delta_annotated(lines)
}
fn make(&self, lines: Vec<Vec<u8>>, version_id: Vec<u8>) -> Self::Content {
AnnotatedKnitContent::new(
lines
.into_iter()
.map(|text| (version_id.clone(), text))
.collect(),
)
}
fn lower_fulltext(&self, content: &Self::Content) -> Vec<Vec<u8>> {
lower_fulltext(&content.lines)
}
fn lower_line_delta(&self, delta: &[DeltaHunk<AnnotatedLine>]) -> Vec<Vec<u8>> {
lower_line_delta_annotated(delta)
}
fn fulltext_payload_lines(&self, body_lines: &[Vec<u8>]) -> Result<Vec<Vec<u8>>, KnitError> {
let refs: Vec<&[u8]> = body_lines.iter().map(|l| l.as_slice()).collect();
let pairs = parse_fulltext(&refs)?;
Ok(pairs.into_iter().map(|(_, text)| text).collect())
}
fn linedelta_payload_lines(&self, body_lines: &[Vec<u8>]) -> Result<Vec<Vec<u8>>, KnitError> {
let refs: Vec<&[u8]> = body_lines.iter().map(|l| l.as_slice()).collect();
let hunks = parse_line_delta_annotated(&refs)?;
Ok(hunks
.into_iter()
.flat_map(|h| h.lines.into_iter().map(|(_, text)| text))
.collect())
}
}
#[derive(Debug, Default, Clone, Copy)]
pub struct KnitPlainFactory;
impl KnitFactory for KnitPlainFactory {
type Content = PlainKnitContent;
fn annotated(&self) -> bool {
false
}
fn parse_fulltext_content(
&self,
lines: &[&[u8]],
version_id: &[u8],
) -> Result<Self::Content, KnitError> {
let lines: Vec<Vec<u8>> = lines.iter().map(|l| l.to_vec()).collect();
Ok(PlainKnitContent::new(lines, version_id.to_vec()))
}
fn parse_line_delta(&self, lines: &[&[u8]]) -> Result<Vec<DeltaHunk<Vec<u8>>>, KnitError> {
parse_line_delta_raw(lines)
}
fn make(&self, lines: Vec<Vec<u8>>, version_id: Vec<u8>) -> Self::Content {
PlainKnitContent::new(lines, version_id)
}
fn lower_fulltext(&self, content: &Self::Content) -> Vec<Vec<u8>> {
content.lines.clone()
}
fn lower_line_delta(&self, delta: &[DeltaHunk<Vec<u8>>]) -> Vec<Vec<u8>> {
lower_line_delta_raw(delta)
}
fn fulltext_payload_lines(&self, body_lines: &[Vec<u8>]) -> Result<Vec<Vec<u8>>, KnitError> {
Ok(body_lines.to_vec())
}
fn linedelta_payload_lines(&self, body_lines: &[Vec<u8>]) -> Result<Vec<Vec<u8>>, KnitError> {
let refs: Vec<&[u8]> = body_lines.iter().map(|l| l.as_slice()).collect();
let hunks = parse_line_delta_raw(&refs)?;
Ok(hunks.into_iter().flat_map(|h| h.lines).collect())
}
}
enum ParsedLine {
Annotated(Vec<u8>, Vec<u8>),
Plain(Vec<u8>),
}
fn split_annotated(line: &[u8]) -> Result<(Vec<u8>, Vec<u8>), KnitError> {
let sp = line
.iter()
.position(|&b| b == b' ')
.ok_or_else(|| KnitError::MissingOrigin(line.to_vec()))?;
Ok((line[..sp].to_vec(), line[sp + 1..].to_vec()))
}
fn parse_line_delta_inner(
lines: &[&[u8]],
annotated: bool,
) -> Result<Vec<DeltaHunk<ParsedLine>>, KnitError> {
let mut out = Vec::new();
let mut i = 0;
while i < lines.len() {
let header = lines[i];
i += 1;
let (start, end, count) = parse_delta_header(header)?;
if i + count > lines.len() {
return Err(KnitError::TruncatedDelta);
}
let mut hunk_lines = Vec::with_capacity(count);
for raw in &lines[i..i + count] {
let (origin, text) = split_annotated(raw)?;
hunk_lines.push(if annotated {
ParsedLine::Annotated(origin, text)
} else {
ParsedLine::Plain(text)
});
}
i += count;
out.push(DeltaHunk {
start,
end,
count,
lines: hunk_lines,
});
}
Ok(out)
}
fn parse_delta_header(line: &[u8]) -> Result<(usize, usize, usize), KnitError> {
let trimmed = line.strip_suffix(b"\n").unwrap_or(line);
let mut parts = trimmed.split(|&b| b == b',');
let mut next = || -> Result<usize, KnitError> {
let part = parts
.next()
.ok_or_else(|| KnitError::BadDeltaHeader(line.to_vec()))?;
std::str::from_utf8(part)
.ok()
.and_then(|s| s.parse().ok())
.ok_or_else(|| KnitError::BadDeltaHeader(line.to_vec()))
};
let start = next()?;
let end = next()?;
let count = next()?;
if parts.next().is_some() {
return Err(KnitError::BadDeltaHeader(line.to_vec()));
}
Ok((start, end, count))
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct NetworkRecordHeader<'a> {
pub key: Vec<&'a [u8]>,
pub parents: Option<Vec<Vec<&'a [u8]>>>,
pub noeol: bool,
pub raw_record: &'a [u8],
}
pub fn parse_network_record_header(
bytes: &[u8],
start: usize,
) -> Result<NetworkRecordHeader<'_>, KnitError> {
let key_end = bytes[start..]
.iter()
.position(|&b| b == b'\n')
.map(|i| start + i)
.ok_or(KnitError::NetworkMissingKeyTerminator)?;
let key: Vec<&[u8]> = bytes[start..key_end].split(|&b| b == b'\x00').collect();
let parents_start = key_end + 1;
let parents_end = bytes[parents_start..]
.iter()
.position(|&b| b == b'\n')
.map(|i| parents_start + i)
.ok_or(KnitError::NetworkMissingParentsTerminator)?;
let parents_line = &bytes[parents_start..parents_end];
let parents = if parents_line == b"None:" {
None
} else {
Some(
parents_line
.split(|&b| b == b'\t')
.filter(|seg| !seg.is_empty())
.map(|seg| seg.split(|&b| b == b'\x00').collect::<Vec<&[u8]>>())
.collect(),
)
};
let noeol_pos = parents_end + 1;
if noeol_pos >= bytes.len() {
return Err(KnitError::NetworkMissingNoEolByte);
}
let noeol = bytes[noeol_pos] == b'N';
let raw_record = &bytes[noeol_pos + 1..];
Ok(NetworkRecordHeader {
key,
parents,
noeol,
raw_record,
})
}
pub const NO_PARENTS: Option<&[&[&[u8]]]> = None;
fn write_joined_key<Seg: AsRef<[u8]>>(out: &mut Vec<u8>, key: &[Seg]) {
for (i, segment) in key.iter().enumerate() {
if i > 0 {
out.push(b'\x00');
}
out.extend_from_slice(segment.as_ref());
}
}
pub fn build_network_record<Seg, PK>(
storage_kind: &[u8],
key: &[Seg],
parents: Option<&[PK]>,
noeol: bool,
raw_record: &[u8],
) -> Vec<u8>
where
Seg: AsRef<[u8]>,
PK: AsRef<[Seg]>,
{
let mut out = Vec::with_capacity(storage_kind.len() + raw_record.len() + 32);
out.extend_from_slice(storage_kind);
out.push(b'\n');
write_joined_key(&mut out, key);
out.push(b'\n');
match parents {
None => out.extend_from_slice(b"None:"),
Some(list) => {
for (i, parent) in list.iter().enumerate() {
if i > 0 {
out.push(b'\t');
}
write_joined_key(&mut out, parent.as_ref());
}
}
}
out.push(b'\n');
out.push(if noeol { b'N' } else { b' ' });
out.extend_from_slice(raw_record);
out
}
pub fn dictionary_compress_suffixes<S>(
suffixes: &[S],
lookup: &std::collections::HashMap<&[u8], u64>,
) -> Vec<u8>
where
S: AsRef<[u8]>,
{
if suffixes.is_empty() {
return Vec::new();
}
let mut out = Vec::new();
for (i, suffix) in suffixes.iter().enumerate() {
if i > 0 {
out.push(b' ');
}
let s = suffix.as_ref();
match lookup.get(s) {
Some(pos) => {
use std::io::Write;
write!(out, "{}", pos).unwrap();
}
None => {
out.push(b'.');
out.extend_from_slice(s);
}
}
}
out
}
pub fn format_kndx_record_line(
suffix: &[u8],
options: &[Vec<u8>],
pos: u64,
size: u64,
parent_refs: &[u8],
) -> Vec<u8> {
use std::io::Write;
let options_csv = options.join(b",".as_ref());
let mut line = Vec::with_capacity(
1 + suffix.len() + 1 + options_csv.len() + 1 + 20 + 1 + 20 + 1 + parent_refs.len() + 2,
);
line.push(b'\n');
line.extend_from_slice(suffix);
line.push(b' ');
line.extend_from_slice(&options_csv);
line.push(b' ');
write!(line, "{}", pos).unwrap();
line.push(b' ');
write!(line, "{}", size).unwrap();
line.push(b' ');
line.extend_from_slice(parent_refs);
line.extend_from_slice(b" :");
line
}
#[allow(clippy::type_complexity)]
pub fn split_keys_by_prefix<'a, K, Seg>(
keys: &'a [K],
) -> (Vec<(&'a [u8], Vec<&'a K>)>, Vec<&'a [u8]>)
where
K: AsRef<[Seg]> + 'a,
Seg: AsRef<[u8]> + 'a,
{
use std::collections::HashMap;
const EMPTY: &[u8] = b"";
let mut buckets: Vec<(&'a [u8], Vec<&'a K>)> = Vec::new();
let mut index: HashMap<&'a [u8], usize> = HashMap::new();
let mut prefix_order: Vec<&'a [u8]> = Vec::new();
for key in keys {
let segments: &'a [Seg] = key.as_ref();
let prefix: &'a [u8] = if segments.len() == 1 {
EMPTY
} else {
segments[0].as_ref()
};
match index.get(prefix) {
Some(&i) => buckets[i].1.push(key),
None => {
index.insert(prefix, buckets.len());
prefix_order.push(prefix);
buckets.push((prefix, vec![key]));
}
}
}
(buckets, prefix_order)
}
pub struct KnitDeltaClosureRecord<'a, Seg: AsRef<[u8]>> {
pub key: &'a [Seg],
pub parents: Option<&'a [&'a [Seg]]>,
pub method: &'a [u8],
pub noeol: bool,
pub next: Option<&'a [Seg]>,
pub record_bytes: &'a [u8],
}
pub fn build_knit_delta_closure_wire<EK, Seg>(
annotated: bool,
emit_keys: &[EK],
records: &[KnitDeltaClosureRecord<'_, Seg>],
) -> Vec<u8>
where
EK: AsRef<[Seg]>,
Seg: AsRef<[u8]>,
{
let body_estimate: usize = records.iter().map(|r| r.record_bytes.len() + 64).sum();
let mut out = Vec::with_capacity(64 + body_estimate);
out.extend_from_slice(b"knit-delta-closure\n");
if annotated {
out.extend_from_slice(b"annotated");
}
out.push(b'\n');
for (i, key) in emit_keys.iter().enumerate() {
if i > 0 {
out.push(b'\t');
}
write_joined_key(&mut out, key.as_ref());
}
out.push(b'\n');
for rec in records {
write_joined_key(&mut out, rec.key);
out.push(b'\n');
match rec.parents {
None => out.extend_from_slice(b"None:"),
Some(list) => {
for (i, parent) in list.iter().enumerate() {
if i > 0 {
out.push(b'\t');
}
write_joined_key(&mut out, parent);
}
}
}
out.push(b'\n');
out.extend_from_slice(rec.method);
out.push(b'\n');
out.push(if rec.noeol { b'T' } else { b'F' });
out.push(b'\n');
if let Some(next) = rec.next {
write_joined_key(&mut out, next);
}
out.push(b'\n');
out.extend_from_slice(rec.record_bytes.len().to_string().as_bytes());
out.push(b'\n');
out.extend_from_slice(rec.record_bytes);
}
out
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RecordHeader {
pub method: Vec<u8>,
pub version_id: Vec<u8>,
pub count: usize,
pub digest: Vec<u8>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RecordHeaderRef<'a> {
pub method: &'a [u8],
pub version_id: &'a [u8],
pub count: usize,
pub digest: &'a [u8],
}
impl RecordHeaderRef<'_> {
pub fn to_owned(&self) -> RecordHeader {
RecordHeader {
method: self.method.to_vec(),
version_id: self.version_id.to_vec(),
count: self.count,
digest: self.digest.to_vec(),
}
}
}
pub fn parse_header_line(line: &[u8]) -> Result<RecordHeaderRef<'_>, KnitError> {
let trimmed = line.strip_suffix(b"\n").unwrap_or(line);
let fields: Vec<&[u8]> = trimmed.split(|&b| b == b' ').collect();
if fields.len() != 4 {
return Err(KnitError::HeaderFields(line.to_vec()));
}
let count: usize = std::str::from_utf8(fields[2])
.ok()
.and_then(|s| s.parse().ok())
.ok_or_else(|| KnitError::HeaderCount(line.to_vec()))?;
Ok(RecordHeaderRef {
method: fields[0],
version_id: fields[1],
count,
digest: fields[3],
})
}
fn split_readlines(data: &[u8]) -> Vec<Vec<u8>> {
let mut out = Vec::new();
let mut start = 0;
for (i, &b) in data.iter().enumerate() {
if b == b'\n' {
out.push(data[start..=i].to_vec());
start = i + 1;
}
}
if start < data.len() {
out.push(data[start..].to_vec());
}
out
}
pub fn decode_record_gz(data: &[u8]) -> Result<Vec<u8>, KnitError> {
use flate2::read::GzDecoder;
use std::io::Read;
let mut decoder = GzDecoder::new(data);
let mut decompressed = Vec::new();
decoder
.read_to_end(&mut decompressed)
.map_err(|e| KnitError::Gzip(e.to_string()))?;
Ok(decompressed)
}
pub fn readlines(data: &[u8]) -> Vec<&[u8]> {
ReadLines::new(data).collect()
}
#[derive(Debug, Clone)]
pub struct ReadLines<'a> {
data: &'a [u8],
pos: usize,
}
impl<'a> ReadLines<'a> {
pub fn new(data: &'a [u8]) -> Self {
Self { data, pos: 0 }
}
}
impl<'a> Iterator for ReadLines<'a> {
type Item = &'a [u8];
fn next(&mut self) -> Option<Self::Item> {
if self.pos >= self.data.len() {
return None;
}
let start = self.pos;
match self.data[start..].iter().position(|&b| b == b'\n') {
Some(off) => {
let end = start + off + 1;
self.pos = end;
Some(&self.data[start..end])
}
None => {
self.pos = self.data.len();
Some(&self.data[start..])
}
}
}
}
pub fn parse_record_body_unchecked(
decompressed: &[u8],
) -> Result<(RecordHeaderRef<'_>, Vec<&[u8]>), KnitError> {
let mut lines = readlines(decompressed);
if lines.is_empty() {
return Err(KnitError::EmptyRecord);
}
let header_line = lines.remove(0);
let header = parse_header_line(header_line)?;
if lines.is_empty() {
return Err(KnitError::LineCount {
declared: header.count,
actual: 0,
});
}
let last_line = lines.pop().unwrap();
if lines.len() != header.count {
return Err(KnitError::LineCount {
declared: header.count,
actual: lines.len(),
});
}
let mut expected_end = b"end ".to_vec();
expected_end.extend_from_slice(header.version_id);
expected_end.push(b'\n');
if last_line != expected_end.as_slice() {
return Err(KnitError::BadEndMarker {
expected: expected_end,
actual: last_line.to_vec(),
});
}
Ok((header, lines))
}
pub fn parse_record_unchecked(data: &[u8]) -> Result<(RecordHeader, Vec<Vec<u8>>), KnitError> {
let decompressed = decode_record_gz(data)?;
let mut lines = split_readlines(&decompressed);
if lines.is_empty() {
return Err(KnitError::EmptyRecord);
}
let header_line = lines.remove(0);
let header = parse_header_line(&header_line)?.to_owned();
if lines.is_empty() {
return Err(KnitError::LineCount {
declared: header.count,
actual: 0,
});
}
let last_line = lines.pop().unwrap();
if lines.len() != header.count {
return Err(KnitError::LineCount {
declared: header.count,
actual: lines.len(),
});
}
let mut expected_end = b"end ".to_vec();
expected_end.extend_from_slice(&header.version_id);
expected_end.push(b'\n');
if last_line != expected_end {
return Err(KnitError::BadEndMarker {
expected: expected_end,
actual: last_line,
});
}
Ok((header, lines))
}
pub fn parse_record(
expected_version: &[u8],
data: &[u8],
) -> Result<(Vec<Vec<u8>>, Vec<u8>), KnitError> {
let (header, body) = parse_record_unchecked(data)?;
if header.version_id != expected_version {
return Err(KnitError::UnexpectedVersion {
wanted: expected_version.to_vec(),
got: header.version_id,
});
}
Ok((body, header.digest))
}
pub fn parse_record_header_only(data: &[u8]) -> Result<RecordHeader, KnitError> {
use flate2::read::GzDecoder;
use std::io::Read;
let mut decoder = GzDecoder::new(data);
let mut header_buf = Vec::with_capacity(64);
let mut byte = [0u8; 1];
loop {
match decoder
.read(&mut byte)
.map_err(|e| KnitError::Gzip(e.to_string()))?
{
0 => break,
_ => {
header_buf.push(byte[0]);
if byte[0] == b'\n' {
break;
}
}
}
}
if header_buf.is_empty() {
return Err(KnitError::EmptyRecord);
}
Ok(parse_header_line(&header_buf)?.to_owned())
}
pub fn record_to_data<P>(
version_id: &[u8],
digest: &[u8],
line_count: usize,
payload: &[P],
has_trailing_newline: bool,
) -> Result<(usize, Vec<Vec<u8>>), KnitError>
where
P: AsRef<[u8]>,
{
if !has_trailing_newline {
return Err(KnitError::MissingTrailingNewline);
}
let mut header = Vec::with_capacity(version_id.len() + digest.len() + 16);
header.extend_from_slice(b"version ");
header.extend_from_slice(version_id);
header.extend_from_slice(format!(" {} ", line_count).as_bytes());
header.extend_from_slice(digest);
header.push(b'\n');
let mut end = Vec::with_capacity(version_id.len() + 5);
end.extend_from_slice(b"end ");
end.extend_from_slice(version_id);
end.push(b'\n');
let mut chunks: Vec<&[u8]> = Vec::with_capacity(payload.len() + 2);
chunks.push(&header);
for p in payload {
chunks.push(p.as_ref());
}
chunks.push(&end);
let compressed = crate::tuned_gzip::chunks_to_gzip(chunks.into_iter());
let total: usize = compressed.iter().map(|c| c.len()).sum();
Ok((total, compressed))
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum KnitMethod {
Fulltext,
LineDelta,
NoEol,
}
impl KnitMethod {
pub fn as_str(self) -> &'static str {
match self {
KnitMethod::Fulltext => "fulltext",
KnitMethod::LineDelta => "line-delta",
KnitMethod::NoEol => "no-eol",
}
}
pub fn from_str(s: &str) -> Option<Self> {
match s {
"fulltext" => Some(KnitMethod::Fulltext),
"line-delta" => Some(KnitMethod::LineDelta),
"no-eol" => Some(KnitMethod::NoEol),
_ => None,
}
}
}
pub fn delta_closure_storage_kind(first: bool) -> &'static str {
if first {
"knit-delta-closure"
} else {
"knit-delta-closure-ref"
}
}
pub fn format_storage_kind(method: KnitMethod, annotated: bool) -> String {
let annotated_prefix = if annotated { "annotated-" } else { "" };
match method {
KnitMethod::LineDelta => format!("knit-{annotated_prefix}delta-gz"),
KnitMethod::Fulltext | KnitMethod::NoEol => format!("knit-{annotated_prefix}ft-gz"),
}
}
pub fn parse_storage_kind(storage_kind: &str) -> Option<(KnitMethod, bool)> {
if !storage_kind.starts_with("knit-") || !storage_kind.ends_with("-gz") {
return None;
}
let annotated = storage_kind.contains("annotated");
let method = if storage_kind.contains("ft") {
KnitMethod::Fulltext
} else {
KnitMethod::LineDelta
};
Some((method, annotated))
}
pub fn encode_graph_index_record(
noeol: bool,
pos: u64,
size: u64,
method: KnitMethod,
has_parents: bool,
has_deltas: bool,
parents: &[KnitKey],
) -> Result<(Vec<u8>, Vec<Vec<KnitKey>>), KnitError> {
if !has_deltas && method == KnitMethod::LineDelta {
return Err(KnitError::Corrupt(
"attempt to add line-delta in non-delta knit".to_string(),
));
}
if !has_parents && !parents.is_empty() {
return Err(KnitError::Corrupt(
"attempt to add node with parents in parentless index".to_string(),
));
}
let flag = if noeol { b'N' } else { b' ' };
let value = format!("{}{} {}", flag as char, pos, size).into_bytes();
let node_refs = if has_parents {
if has_deltas {
if method == KnitMethod::LineDelta {
let compression_parent = parents.first().cloned().unwrap_or_default();
vec![parents.to_vec(), vec![compression_parent]]
} else {
vec![parents.to_vec(), vec![]]
}
} else {
vec![parents.to_vec()]
}
} else {
vec![]
};
Ok((value, node_refs))
}
#[derive(Debug, Clone)]
pub struct AddRecordInput {
pub key: KnitKey,
pub options: Vec<u8>,
pub pos: u64,
pub size: u64,
pub parents: Vec<KnitKey>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PreparedAddRecord {
pub key: KnitKey,
pub value: Vec<u8>,
pub node_refs: Vec<Vec<KnitKey>>,
}
#[derive(Debug, Clone)]
pub struct ExistingAddRecord {
pub key: KnitKey,
pub value: Vec<u8>,
pub parents: Vec<KnitKey>,
}
pub fn prepare_dedup_records(
inputs: &[AddRecordInput],
has_parents: bool,
has_deltas: bool,
) -> Result<Vec<PreparedAddRecord>, KnitError> {
let mut out: Vec<PreparedAddRecord> = Vec::with_capacity(inputs.len());
for input in inputs {
let noeol = input
.options
.windows(b"no-eol".len())
.any(|w| w == b"no-eol");
let method = if input
.options
.windows(b"line-delta".len())
.any(|w| w == b"line-delta")
{
KnitMethod::LineDelta
} else {
KnitMethod::Fulltext
};
let (value, node_refs) = encode_graph_index_record(
noeol,
input.pos,
input.size,
method,
has_parents,
has_deltas,
&input.parents,
)?;
if let Some(existing) = out.iter_mut().find(|p| p.key == input.key) {
existing.value = value;
existing.node_refs = node_refs;
} else {
out.push(PreparedAddRecord {
key: input.key.clone(),
value,
node_refs,
});
}
}
Ok(out)
}
pub fn verify_dedup_records(
prepared: &[PreparedAddRecord],
existing: &[ExistingAddRecord],
) -> Result<std::collections::HashSet<KnitKey>, KnitError> {
let mut to_remove: std::collections::HashSet<KnitKey> = std::collections::HashSet::new();
for ex in existing {
let Some(new) = prepared.iter().find(|p| p.key == ex.key) else {
continue;
};
let existing_flag = ex.value.first().copied().unwrap_or(b' ');
let new_flag = new.value.first().copied().unwrap_or(b' ');
let new_parents: &[KnitKey] = new.node_refs.first().map(|v| v.as_slice()).unwrap_or(&[]);
if existing_flag != new_flag || ex.parents.as_slice() != new_parents {
return Err(KnitError::Corrupt(format!(
"inconsistent details in add_records: existing flag={:?} new flag={:?}",
existing_flag as char, new_flag as char,
)));
}
to_remove.insert(ex.key.clone());
}
Ok(to_remove)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct KnitIndexValue {
pub noeol: bool,
pub pos: u64,
pub size: u64,
}
pub fn parse_knit_index_value(value: &[u8]) -> Result<KnitIndexValue, KnitError> {
if value.is_empty() {
return Err(KnitError::BadIndexValue(value.to_vec()));
}
let noeol = value[0] == b'N';
let trimmed = &value[1..];
let mut parts = trimmed.splitn(2, |&b| b == b' ');
let pos_bytes = parts
.next()
.ok_or_else(|| KnitError::BadIndexValue(value.to_vec()))?;
let size_bytes = parts
.next()
.ok_or_else(|| KnitError::BadIndexValue(value.to_vec()))?;
let pos: u64 = std::str::from_utf8(pos_bytes)
.ok()
.and_then(|s| s.parse().ok())
.ok_or_else(|| KnitError::BadIndexValue(value.to_vec()))?;
let size: u64 = std::str::from_utf8(size_bytes)
.ok()
.and_then(|s| s.parse().ok())
.ok_or_else(|| KnitError::BadIndexValue(value.to_vec()))?;
Ok(KnitIndexValue { noeol, pos, size })
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct KnitBuildDetails {
pub pos: u64,
pub size: u64,
pub noeol: bool,
pub method: KnitMethod,
pub compression_parent: Option<usize>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ClosureBatch<K, P>
where
K: Eq + std::hash::Hash + Clone,
{
pub present: std::collections::HashMap<K, (Option<K>, P)>,
pub missing: std::collections::HashSet<K>,
}
#[allow(clippy::type_complexity)]
pub fn walk_compression_closure<K, P, F>(
initial_keys: impl IntoIterator<Item = K>,
allow_missing: bool,
mut lookup_batch: F,
) -> Result<std::collections::HashMap<K, P>, std::collections::HashSet<K>>
where
K: Eq + std::hash::Hash + Clone,
F: FnMut(&[K]) -> ClosureBatch<K, P>,
{
use std::collections::HashMap;
let mut result: HashMap<K, P> = HashMap::new();
let mut pending: Vec<K> = initial_keys.into_iter().collect();
while !pending.is_empty() {
let batch = lookup_batch(&pending);
if !batch.missing.is_empty() && !allow_missing {
return Err(batch.missing);
}
let mut next: Vec<K> = Vec::new();
for (key, (compression_parent, payload)) in batch.present {
if let Some(parent) = compression_parent.as_ref() {
if !result.contains_key(parent) && !next.contains(parent) {
next.push(parent.clone());
}
}
result.insert(key, payload);
}
pending = next;
}
Ok(result)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DeltaDecision {
UseDelta,
FulltextSmaller,
ChainTooLong,
MissingParent,
}
impl DeltaDecision {
pub fn should_use_delta(self) -> bool {
matches!(self, DeltaDecision::UseDelta)
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ChainStep<K> {
pub size: u64,
pub compression_parent: Option<K>,
}
pub fn should_use_delta<K, F>(initial_parent: K, max_chain: usize, mut get_step: F) -> DeltaDecision
where
F: FnMut(&K) -> Option<ChainStep<K>>,
{
let mut delta_size: u64 = 0;
let mut current = initial_parent;
for _ in 0..max_chain {
let step = match get_step(¤t) {
Some(s) => s,
None => return DeltaDecision::MissingParent,
};
match step.compression_parent {
None => {
return if step.size > delta_size {
DeltaDecision::UseDelta
} else {
DeltaDecision::FulltextSmaller
};
}
Some(next) => {
delta_size += step.size;
current = next;
}
}
}
DeltaDecision::ChainTooLong
}
pub fn decode_kndx_options<O: AsRef<[u8]>>(options: &[O]) -> Result<(KnitMethod, bool), KnitError> {
let mut method: Option<KnitMethod> = None;
let mut noeol = false;
for opt in options {
let o = opt.as_ref();
if o == b"fulltext" {
method = Some(KnitMethod::Fulltext);
} else if o == b"line-delta" {
method = Some(KnitMethod::LineDelta);
} else if o == b"no-eol" {
noeol = true;
}
}
let method = method.ok_or_else(|| {
KnitError::BadIndexValue(
options
.iter()
.flat_map(|o| {
let mut v = o.as_ref().to_vec();
v.push(b',');
v
})
.collect(),
)
})?;
Ok((method, noeol))
}
pub fn decode_knit_build_details(
value: &[u8],
has_deltas: bool,
compression_parent_count: usize,
) -> Result<KnitBuildDetails, KnitError> {
let parsed = parse_knit_index_value(value)?;
let compression_parent = if has_deltas {
match compression_parent_count {
0 => None,
1 => Some(0),
n => return Err(KnitError::TooManyCompressionParents(n)),
}
} else {
None
};
let method = if compression_parent.is_some() {
KnitMethod::LineDelta
} else {
KnitMethod::Fulltext
};
Ok(KnitBuildDetails {
pos: parsed.pos,
size: parsed.size,
noeol: parsed.noeol,
method,
compression_parent,
})
}
pub fn extract_annotated_fulltext_to_plain_lines(
raw_record: &[u8],
noeol: bool,
) -> Result<Vec<Vec<u8>>, KnitError> {
let decompressed = decode_record_gz(raw_record)?;
let (_header, body_lines) = parse_record_body_unchecked(&decompressed)?;
let annotated: Vec<AnnotatedLine> = parse_fulltext(&body_lines)?;
let mut lines: Vec<Vec<u8>> = annotated.into_iter().map(|(_, text)| text).collect();
if noeol {
if let Some(last) = lines.last_mut() {
if last.ends_with(b"\n") {
last.pop();
}
}
}
Ok(lines)
}
pub fn extract_plain_fulltext_lines(
raw_record: &[u8],
noeol: bool,
) -> Result<Vec<Vec<u8>>, KnitError> {
let decompressed = decode_record_gz(raw_record)?;
let (_header, body_lines) = parse_record_body_unchecked(&decompressed)?;
let mut lines: Vec<Vec<u8>> = body_lines.iter().map(|l| l.to_vec()).collect();
if noeol {
if let Some(last) = lines.last_mut() {
if last.ends_with(b"\n") {
last.pop();
}
}
}
Ok(lines)
}
pub fn apply_annotated_delta_to_plain_basis(
raw_record: &[u8],
basis_lines: Vec<Vec<u8>>,
version_id: &[u8],
noeol: bool,
) -> Result<Vec<Vec<u8>>, KnitError> {
let decompressed = decode_record_gz(raw_record)?;
let (_header, body_lines) = parse_record_body_unchecked(&decompressed)?;
let annotated_hunks = parse_line_delta_annotated(&body_lines)?;
let plain_hunks: Vec<DeltaHunk<Vec<u8>>> = annotated_hunks
.into_iter()
.map(|h| DeltaHunk {
start: h.start,
end: h.end,
count: h.count,
lines: h.lines.into_iter().map(|(_origin, text)| text).collect(),
})
.collect();
let mut content = PlainKnitContent::new(basis_lines, version_id.to_vec());
content.apply_delta(&plain_hunks, version_id);
content.set_should_strip_eol(noeol);
Ok(content.text())
}
pub fn apply_plain_delta_to_plain_basis(
raw_record: &[u8],
basis_lines: Vec<Vec<u8>>,
version_id: &[u8],
noeol: bool,
) -> Result<Vec<Vec<u8>>, KnitError> {
let decompressed = decode_record_gz(raw_record)?;
let (_header, body_lines) = parse_record_body_unchecked(&decompressed)?;
let plain_hunks = parse_line_delta_raw(&body_lines)?;
let mut content = PlainKnitContent::new(basis_lines, version_id.to_vec());
content.apply_delta(&plain_hunks, version_id);
content.set_should_strip_eol(noeol);
Ok(content.text())
}
fn apply_plain_delta_to_basis(
key: &KnitKey,
raw_record: &[u8],
noeol: bool,
basis_text: &[u8],
) -> Result<Vec<Vec<u8>>, KnitError> {
let version_id = key.last().map(Vec::as_slice).unwrap_or(&[]);
let mut basis_lines: Vec<Vec<u8>> =
crate::osutils::chunks_to_lines(std::iter::once(Ok::<_, std::io::Error>(
std::borrow::Cow::Borrowed(basis_text),
)))
.map(|r| r.unwrap().into_owned())
.collect();
let (delta_body, _sha1) = parse_record(version_id, raw_record)?;
let delta_refs: Vec<&[u8]> = delta_body.iter().map(|l| l.as_slice()).collect();
let hunks = parse_line_delta_raw(&delta_refs)?;
let mut offset: isize = 0;
for hunk in &hunks {
let start = (offset + hunk.start as isize) as usize;
let end = (offset + hunk.end as isize) as usize;
basis_lines.splice(start..end, hunk.lines.iter().cloned());
offset += hunk.start as isize - hunk.end as isize + hunk.count as isize;
}
if noeol {
if let Some(last) = basis_lines.last_mut() {
if last.ends_with(b"\n") {
last.pop();
}
}
}
Ok(basis_lines)
}
pub(crate) fn decode_plain_knit_to_lines<I, A, F>(
kvf: &KnitVersionedFiles<I, A, F>,
key: &KnitKey,
method: KnitMethod,
noeol: bool,
compression_parent: Option<&KnitKey>,
raw_record: &[u8],
) -> Result<Vec<Vec<u8>>, KnitError>
where
I: KnitIndex,
A: KnitAccess<F = I::F>,
F: KnitFactory,
{
if method == KnitMethod::Fulltext {
return extract_plain_fulltext_lines(raw_record, noeol);
}
let cp = compression_parent.ok_or_else(|| {
KnitError::Corrupt(format!("delta record {key:?} has no compression parent",))
})?;
let basis_text = kvf.get_text(cp)?;
apply_plain_delta_to_basis(key, raw_record, noeol, &basis_text)
}
pub(crate) fn decode_plain_knit_to_lines_with_fallbacks<I, A, F>(
kvf: &KnitVersionedFiles<I, A, F>,
key: &KnitKey,
method: KnitMethod,
noeol: bool,
compression_parent: Option<&KnitKey>,
raw_record: &[u8],
fallbacks: &[&dyn crate::versionedfile::VersionedFiles],
) -> Result<Vec<Vec<u8>>, KnitError>
where
I: KnitIndex,
A: KnitAccess<F = I::F>,
F: KnitFactory,
{
if method == KnitMethod::Fulltext {
return extract_plain_fulltext_lines(raw_record, noeol);
}
let cp = compression_parent.ok_or_else(|| {
KnitError::Corrupt(format!("delta record {key:?} has no compression parent",))
})?;
if let Ok(basis_text) = kvf.get_text(cp) {
return apply_plain_delta_to_basis(key, raw_record, noeol, &basis_text);
}
let cp_key = vf_key_from_knit(cp);
for fb in fallbacks {
let mut stream = fb.get_record_stream(std::slice::from_ref(&cp_key), "unordered", true)?;
let mut basis: Option<Box<dyn crate::versionedfile::ContentFactory>> = None;
for rec in stream.by_ref() {
let rec = rec?;
if rec.storage_kind() != "absent" {
basis = Some(rec);
break;
}
}
if let Some(basis) = basis {
let basis_bytes = basis.to_fulltext().into_owned();
return apply_plain_delta_to_basis(key, raw_record, noeol, &basis_bytes);
}
}
Err(KnitError::RevisionNotPresent(cp.clone()))
}
fn vf_key_from_knit(k: &KnitKey) -> crate::versionedfile::Key {
crate::versionedfile::Key::Fixed(k.clone())
}
pub fn recompress_annotated_to_unannotated_fulltext(
raw_record: &[u8],
) -> Result<Vec<u8>, KnitError> {
let decompressed = decode_record_gz(raw_record)?;
let (header, body_lines) = parse_record_body_unchecked(&decompressed)?;
let annotated: Vec<AnnotatedLine> = parse_fulltext(&body_lines)?;
let plain_lines: Vec<Vec<u8>> = annotated.into_iter().map(|(_, text)| text).collect();
let has_trailing_newline = plain_lines.last().is_none_or(|l| l.ends_with(b"\n"));
let (_, chunks) = record_to_data(
header.version_id,
header.digest,
plain_lines.len(),
&plain_lines,
has_trailing_newline,
)?;
Ok(chunks.into_iter().flatten().collect())
}
pub fn recompress_annotated_to_unannotated_delta(raw_record: &[u8]) -> Result<Vec<u8>, KnitError> {
let decompressed = decode_record_gz(raw_record)?;
let (header, body_lines) = parse_record_body_unchecked(&decompressed)?;
let plain_delta = parse_line_delta_plain(&body_lines)?;
let plain_bytes = lower_line_delta_raw(&plain_delta);
let has_trailing_newline = plain_bytes.last().is_none_or(|l| l.ends_with(b"\n"));
let (_, chunks) = record_to_data(
header.version_id,
header.digest,
plain_bytes.len(),
&plain_bytes,
has_trailing_newline,
)?;
Ok(chunks.into_iter().flatten().collect())
}
#[derive(Debug)]
pub struct KnitAdapterInput<'a> {
pub key: &'a [Vec<u8>],
pub raw_record: &'a [u8],
pub noeol: bool,
pub parents: Option<&'a [Vec<Vec<u8>>]>,
pub storage_kind: &'a str,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum KnitTextResult {
Bytes(Vec<u8>),
Lines(Vec<Vec<u8>>),
}
pub fn materialize_text(lines: Vec<Vec<u8>>, target_kind: &str) -> Option<KnitTextResult> {
match target_kind {
"fulltext" => Some(KnitTextResult::Bytes(lines.into_iter().flatten().collect())),
"chunked" | "lines" => Some(KnitTextResult::Lines(lines)),
_ => None,
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum KnitAdapterOutput {
RawBytes(Vec<u8>),
Text(KnitTextResult),
}
#[derive(Debug)]
pub enum AdapterError {
Unavailable {
source_storage_kind: String,
target_storage_kind: String,
},
BasisNotPresent(KnitKey),
Knit(KnitError),
}
impl std::fmt::Display for AdapterError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
AdapterError::Unavailable {
source_storage_kind,
target_storage_kind,
} => write!(
f,
"knit adapter cannot convert {source_storage_kind} to {target_storage_kind}",
),
AdapterError::BasisNotPresent(key) => {
write!(f, "basis record not present: {key:?}")
}
AdapterError::Knit(e) => write!(f, "{e}"),
}
}
}
impl std::error::Error for AdapterError {}
impl From<KnitError> for AdapterError {
fn from(e: KnitError) -> Self {
AdapterError::Knit(e)
}
}
pub trait BasisVfBridge {
fn get_basis_lines(&self, compression_parent: &[Vec<u8>])
-> Result<Vec<Vec<u8>>, AdapterError>;
}
pub trait KnitAdapter: Send + Sync + 'static {
fn keys(&self) -> &'static [(&'static str, &'static str)];
fn get_bytes(
&self,
input: &KnitAdapterInput<'_>,
target_storage_kind: &str,
basis: Option<&dyn BasisVfBridge>,
) -> Result<KnitAdapterOutput, AdapterError>;
}
fn unavailable(input: &KnitAdapterInput<'_>, target: &str) -> AdapterError {
AdapterError::Unavailable {
source_storage_kind: input.storage_kind.to_owned(),
target_storage_kind: target.to_owned(),
}
}
fn compression_parent<'a>(input: &'a KnitAdapterInput<'_>) -> Result<&'a [Vec<u8>], AdapterError> {
input
.parents
.and_then(|ps| ps.first())
.map(|p| p.as_slice())
.ok_or_else(|| {
AdapterError::Knit(KnitError::Corrupt(
"delta record missing compression parent".to_owned(),
))
})
}
fn version_id<'a>(input: &'a KnitAdapterInput<'_>) -> &'a [u8] {
input.key.last().map(|s| s.as_slice()).unwrap_or(b"")
}
pub struct FtAnnotatedToUnannotated;
impl KnitAdapter for FtAnnotatedToUnannotated {
fn keys(&self) -> &'static [(&'static str, &'static str)] {
&[("knit-annotated-ft-gz", "knit-ft-gz")]
}
fn get_bytes(
&self,
input: &KnitAdapterInput<'_>,
target_storage_kind: &str,
_basis: Option<&dyn BasisVfBridge>,
) -> Result<KnitAdapterOutput, AdapterError> {
if target_storage_kind != "knit-ft-gz" {
return Err(unavailable(input, target_storage_kind));
}
Ok(KnitAdapterOutput::RawBytes(
recompress_annotated_to_unannotated_fulltext(input.raw_record)?,
))
}
}
pub struct DeltaAnnotatedToUnannotated;
impl KnitAdapter for DeltaAnnotatedToUnannotated {
fn keys(&self) -> &'static [(&'static str, &'static str)] {
&[("knit-annotated-delta-gz", "knit-delta-gz")]
}
fn get_bytes(
&self,
input: &KnitAdapterInput<'_>,
target_storage_kind: &str,
_basis: Option<&dyn BasisVfBridge>,
) -> Result<KnitAdapterOutput, AdapterError> {
if target_storage_kind != "knit-delta-gz" {
return Err(unavailable(input, target_storage_kind));
}
Ok(KnitAdapterOutput::RawBytes(
recompress_annotated_to_unannotated_delta(input.raw_record)?,
))
}
}
pub struct FtAnnotatedToFullText;
impl KnitAdapter for FtAnnotatedToFullText {
fn keys(&self) -> &'static [(&'static str, &'static str)] {
&[
("knit-annotated-ft-gz", "fulltext"),
("knit-annotated-ft-gz", "chunked"),
("knit-annotated-ft-gz", "lines"),
]
}
fn get_bytes(
&self,
input: &KnitAdapterInput<'_>,
target_storage_kind: &str,
_basis: Option<&dyn BasisVfBridge>,
) -> Result<KnitAdapterOutput, AdapterError> {
if !matches!(target_storage_kind, "fulltext" | "chunked" | "lines") {
return Err(unavailable(input, target_storage_kind));
}
let lines = extract_annotated_fulltext_to_plain_lines(input.raw_record, input.noeol)?;
let result = materialize_text(lines, target_storage_kind)
.expect("target validated to be a text kind");
Ok(KnitAdapterOutput::Text(result))
}
}
pub struct FtPlainToFullText;
impl KnitAdapter for FtPlainToFullText {
fn keys(&self) -> &'static [(&'static str, &'static str)] {
&[
("knit-ft-gz", "fulltext"),
("knit-ft-gz", "chunked"),
("knit-ft-gz", "lines"),
]
}
fn get_bytes(
&self,
input: &KnitAdapterInput<'_>,
target_storage_kind: &str,
_basis: Option<&dyn BasisVfBridge>,
) -> Result<KnitAdapterOutput, AdapterError> {
if !matches!(target_storage_kind, "fulltext" | "chunked" | "lines") {
return Err(unavailable(input, target_storage_kind));
}
let lines = extract_plain_fulltext_lines(input.raw_record, input.noeol)?;
let result = materialize_text(lines, target_storage_kind)
.expect("target validated to be a text kind");
Ok(KnitAdapterOutput::Text(result))
}
}
pub struct DeltaAnnotatedToFullText;
impl KnitAdapter for DeltaAnnotatedToFullText {
fn keys(&self) -> &'static [(&'static str, &'static str)] {
&[
("knit-annotated-delta-gz", "fulltext"),
("knit-annotated-delta-gz", "chunked"),
("knit-annotated-delta-gz", "lines"),
]
}
fn get_bytes(
&self,
input: &KnitAdapterInput<'_>,
target_storage_kind: &str,
basis: Option<&dyn BasisVfBridge>,
) -> Result<KnitAdapterOutput, AdapterError> {
if !matches!(target_storage_kind, "fulltext" | "chunked" | "lines") {
return Err(unavailable(input, target_storage_kind));
}
let basis = basis.ok_or_else(|| {
AdapterError::Knit(KnitError::Corrupt(
"DeltaAnnotatedToFullText requires basis_vf".to_owned(),
))
})?;
let cp = compression_parent(input)?;
let basis_lines = basis.get_basis_lines(cp)?;
let lines = apply_annotated_delta_to_plain_basis(
input.raw_record,
basis_lines,
version_id(input),
input.noeol,
)?;
let result = materialize_text(lines, target_storage_kind)
.expect("target validated to be a text kind");
Ok(KnitAdapterOutput::Text(result))
}
}
pub struct DeltaPlainToFullText;
impl KnitAdapter for DeltaPlainToFullText {
fn keys(&self) -> &'static [(&'static str, &'static str)] {
&[
("knit-delta-gz", "fulltext"),
("knit-delta-gz", "chunked"),
("knit-delta-gz", "lines"),
]
}
fn get_bytes(
&self,
input: &KnitAdapterInput<'_>,
target_storage_kind: &str,
basis: Option<&dyn BasisVfBridge>,
) -> Result<KnitAdapterOutput, AdapterError> {
if !matches!(target_storage_kind, "fulltext" | "chunked" | "lines") {
return Err(unavailable(input, target_storage_kind));
}
let basis = basis.ok_or_else(|| {
AdapterError::Knit(KnitError::Corrupt(
"DeltaPlainToFullText requires basis_vf".to_owned(),
))
})?;
let cp = compression_parent(input)?;
let basis_lines = basis.get_basis_lines(cp)?;
let lines = apply_plain_delta_to_plain_basis(
input.raw_record,
basis_lines,
version_id(input),
input.noeol,
)?;
let result = materialize_text(lines, target_storage_kind)
.expect("target validated to be a text kind");
Ok(KnitAdapterOutput::Text(result))
}
}
pub struct AdapterEntry {
pub adapter: &'static dyn KnitAdapter,
}
inventory::collect!(AdapterEntry);
#[macro_export]
macro_rules! declare_adapter {
($adapter:path) => {
inventory::submit! {
$crate::knit::AdapterEntry {
adapter: &$adapter,
}
}
};
}
declare_adapter!(FtAnnotatedToUnannotated);
declare_adapter!(DeltaAnnotatedToUnannotated);
declare_adapter!(FtAnnotatedToFullText);
declare_adapter!(FtPlainToFullText);
declare_adapter!(DeltaAnnotatedToFullText);
declare_adapter!(DeltaPlainToFullText);
pub fn lookup_adapter(
source_storage_kind: &str,
target_storage_kind: &str,
) -> Option<&'static dyn KnitAdapter> {
for entry in inventory::iter::<AdapterEntry> {
for &(src, tgt) in entry.adapter.keys() {
if src == source_storage_kind && tgt == target_storage_kind {
return Some(entry.adapter);
}
}
}
None
}
pub type KnitKey = Vec<Vec<u8>>;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct KnitRecordDetails<F: FileRef = String> {
pub method: KnitMethod,
pub noeol: bool,
pub index_memo: KnitIndexMemo<F>,
pub compression_parent: Option<KnitKey>,
pub parents: Vec<KnitKey>,
}
pub trait FileRef:
Clone + Eq + std::hash::Hash + Ord + std::fmt::Debug + Send + Sync + 'static
{
fn placeholder() -> Self;
}
impl FileRef for String {
fn placeholder() -> Self {
String::new()
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct KnitIndexMemo<F: FileRef = String> {
pub file_ref: F,
pub offset: u64,
pub length: usize,
}
pub trait KnitIndex {
type F: FileRef;
fn get_build_details(
&self,
keys: &[KnitKey],
) -> Result<std::collections::HashMap<KnitKey, KnitRecordDetails<Self::F>>, KnitError>;
fn keys(&self) -> Result<Vec<KnitKey>, KnitError>;
fn get_parent_map(
&self,
keys: &[KnitKey],
) -> Result<std::collections::HashMap<KnitKey, Vec<KnitKey>>, KnitError>;
fn get_method(&self, key: &KnitKey) -> Result<KnitMethod, KnitError>;
fn get_total_build_size(
&self,
keys: &[KnitKey],
positions: &std::collections::HashMap<KnitKey, KnitRecordDetails<Self::F>>,
) -> usize;
fn sort_keys_by_io(
&self,
keys: &mut [KnitKey],
positions: &std::collections::HashMap<KnitKey, KnitRecordDetails<Self::F>>,
);
fn has_graph(&self) -> bool;
fn contains(&self, key: &KnitKey) -> Result<bool, KnitError>;
fn get_missing_compression_parents(&self) -> Result<Vec<KnitKey>, KnitError>;
fn check_write_ok(&self) -> Result<(), KnitError>;
fn add_records(
&self,
records: &[(
KnitKey,
Vec<KnitMethod>,
KnitIndexMemo<Self::F>,
Vec<KnitKey>,
)],
random_id: bool,
missing_compression_parents: bool,
) -> Result<(), KnitError>;
}
pub trait AddCallback {
fn call(
&mut self,
entries: &[(KnitKey, Vec<u8>, Vec<Vec<KnitKey>>)],
has_parents: bool,
) -> Result<(), KnitError>;
}
pub struct KnitGraphIndex<C> {
pub deltas: bool,
pub parents: bool,
pub add_callback: Option<C>,
pub missing_compression_parents: std::collections::HashSet<KnitKey>,
pub key_dependencies: Option<crate::versionedfile::KeyRefs<KnitKey>>,
}
impl<C: AddCallback> KnitGraphIndex<C> {
pub fn new(deltas: bool, parents: bool) -> Self {
Self {
deltas,
parents,
add_callback: None,
missing_compression_parents: std::collections::HashSet::new(),
key_dependencies: None,
}
}
pub fn set_add_callback(&mut self, callback: C) {
self.add_callback = Some(callback);
}
pub fn clear_add_callback(&mut self) {
self.add_callback = None;
}
pub fn enable_key_dependencies(&mut self, track_new_keys: bool) {
self.key_dependencies = Some(crate::versionedfile::KeyRefs::new(track_new_keys));
}
pub fn clear_key_dependencies(&mut self) {
if let Some(kd) = self.key_dependencies.as_mut() {
kd.clear();
}
}
pub fn add_key_dependencies(&mut self, key: KnitKey, parent_keys: Vec<KnitKey>) {
if let Some(kd) = self.key_dependencies.as_mut() {
kd.add_references(key, parent_keys);
}
}
pub fn add_missing_compression_parent(&mut self, key: KnitKey) {
self.missing_compression_parents.insert(key);
}
pub fn satisfy_refs_for_keys(&mut self, keys: impl IntoIterator<Item = KnitKey>) {
if let Some(kd) = self.key_dependencies.as_mut() {
kd.satisfy_refs_for_keys(keys);
}
}
pub fn unsatisfied_refs(&self) -> impl Iterator<Item = &KnitKey> {
self.key_dependencies
.iter()
.flat_map(|kd| kd.unsatisfied_refs())
}
pub fn referrers(&self) -> std::collections::HashSet<KnitKey> {
self.key_dependencies
.as_ref()
.map(|kd| kd.referrers())
.unwrap_or_default()
}
pub fn new_keys(&self) -> Option<&std::collections::HashSet<KnitKey>> {
self.key_dependencies.as_ref()?.new_keys()
}
pub fn update_missing_compression_parents(
&mut self,
new_missing: impl IntoIterator<Item = KnitKey>,
present_keys: &std::collections::HashSet<KnitKey>,
) {
for key in new_missing {
if !present_keys.contains(&key) {
self.missing_compression_parents.insert(key);
}
}
}
pub fn encode_and_dispatch<I>(
&mut self,
records: I,
missing_compression_parents_flag: bool,
) -> Result<(), KnitError>
where
I: IntoIterator<Item = (KnitKey, Vec<u8>, u64, u64, Vec<KnitKey>)>,
{
let Some(cb) = self.add_callback.as_mut() else {
return Err(KnitError::ReadOnly);
};
let mut entries: Vec<(KnitKey, Vec<u8>, Vec<Vec<KnitKey>>)> = Vec::new();
let mut new_compression_parents: std::collections::HashSet<KnitKey> =
std::collections::HashSet::new();
let mut key_dep_updates: Vec<(KnitKey, Vec<KnitKey>)> = Vec::new();
for (key, options_bytes, pos, size, parents) in records {
let noeol = options_bytes.windows(6).any(|w| w == b"no-eol");
let method = if options_bytes.windows(10).any(|w| w == b"line-delta") {
KnitMethod::LineDelta
} else {
KnitMethod::Fulltext
};
if missing_compression_parents_flag && method == KnitMethod::LineDelta {
if let Some(cp) = parents.first() {
new_compression_parents.insert(cp.clone());
}
}
let (value, node_refs) = encode_graph_index_record(
noeol,
pos,
size,
method,
self.parents,
self.deltas,
&parents,
)?;
if self.parents && self.key_dependencies.is_some() {
key_dep_updates.push((key.clone(), parents));
}
if let Some(existing) = entries.iter_mut().find(|(k, _, _)| k == &key) {
*existing = (key, value, node_refs);
} else {
entries.push((key, value, node_refs));
}
}
cb.call(&entries, self.parents)?;
for (key, parents) in key_dep_updates {
self.add_key_dependencies(key, parents);
}
let added_keys: std::collections::HashSet<&KnitKey> =
entries.iter().map(|(k, _, _)| k).collect();
if missing_compression_parents_flag {
new_compression_parents.retain(|k| !added_keys.contains(k));
self.missing_compression_parents
.extend(new_compression_parents);
}
self.missing_compression_parents
.retain(|k| !added_keys.contains(k));
Ok(())
}
}
pub trait KnitAccess {
type F: FileRef;
fn get_raw_record(&self, memo: &KnitIndexMemo<Self::F>) -> Result<Vec<u8>, KnitError>;
fn get_raw_records(&self, memos: &[KnitIndexMemo<Self::F>]) -> Result<Vec<Vec<u8>>, KnitError>;
fn add_raw_record(
&self,
key: &KnitKey,
size: usize,
data: Vec<Vec<u8>>,
) -> Result<KnitIndexMemo<Self::F>, KnitError>;
fn flush(&self) -> Result<(), KnitError>;
fn reload_or_raise(&self, err: KnitError) -> Result<(), KnitError>;
}
pub fn get_text<I, A, F>(
index: &I,
access: &A,
factory: &F,
key: &KnitKey,
) -> Result<Vec<u8>, KnitError>
where
I: KnitIndex,
A: KnitAccess<F = I::F>,
F: KnitFactory,
{
let content = get_content(index, access, factory, key)?;
let mut out = Vec::new();
for line in content.text() {
out.extend_from_slice(&line);
}
Ok(out)
}
pub fn get_content<I, A, F>(
index: &I,
access: &A,
factory: &F,
key: &KnitKey,
) -> Result<F::Content, KnitError>
where
I: KnitIndex,
A: KnitAccess<F = I::F>,
F: KnitFactory,
{
let chain = walk_compression_closure::<KnitKey, KnitRecordDetails<I::F>, _>(
std::iter::once(key.clone()),
false,
|batch| {
let lookup = match index.get_build_details(batch) {
Ok(m) => m,
Err(_) => {
return ClosureBatch {
present: Default::default(),
missing: batch.iter().cloned().collect(),
};
}
};
let mut present = std::collections::HashMap::new();
let mut missing = std::collections::HashSet::new();
for k in batch {
match lookup.get(k) {
Some(details) => {
present.insert(
k.clone(),
(details.compression_parent.clone(), details.clone()),
);
}
None => {
missing.insert(k.clone());
}
}
}
ClosureBatch { present, missing }
},
)
.map_err(|missing| {
let one = missing.into_iter().next().unwrap_or_else(|| key.clone());
KnitError::RevisionNotPresent(one)
})?;
let mut order: Vec<KnitKey> = Vec::new();
let mut cursor: Option<KnitKey> = Some(key.clone());
while let Some(k) = cursor {
let details = chain.get(&k).ok_or_else(|| {
KnitError::BadIndexValue(b"chain walk produced a key without details".to_vec())
})?;
cursor = details.compression_parent.clone();
order.push(k);
}
order.reverse();
let mut content: Option<F::Content> = None;
for chain_key in order {
let details = chain.get(&chain_key).ok_or_else(|| {
KnitError::BadIndexValue(b"chain walk produced a key without details".to_vec())
})?;
let raw = access.get_raw_record(&details.index_memo)?;
let decompressed = decode_record_gz(&raw)?;
let (_, body_lines) = parse_record_body_unchecked(&decompressed)?;
let next = factory.parse_record(
chain_key.last().map(|s| s.as_slice()).unwrap_or(&[]),
&body_lines,
details.method,
details.noeol,
content.as_ref(),
)?;
content = Some(next);
}
content.ok_or_else(|| KnitError::BadIndexValue(b"empty compression chain for key".to_vec()))
}
pub fn get_sha1s<I, A>(
index: &I,
access: &A,
keys: &[KnitKey],
) -> Result<std::collections::HashMap<KnitKey, Vec<u8>>, KnitError>
where
I: KnitIndex,
A: KnitAccess<F = I::F>,
{
let details_map = index.get_build_details(keys)?;
let mut out = std::collections::HashMap::new();
for key in keys {
let Some(details) = details_map.get(key) else {
continue;
};
let raw = access.get_raw_record(&details.index_memo)?;
let header = parse_record_header_only(&raw)?;
out.insert(key.clone(), header.digest);
}
Ok(out)
}
pub struct KndxIndex<T, M> {
transport: T,
mapper: M,
kndx_cache: std::sync::Mutex<std::collections::HashMap<Vec<Vec<u8>>, KndxPrefixCache>>,
}
#[derive(Debug, Default)]
pub struct KndxPrefixCache {
pub cache: std::collections::HashMap<Vec<u8>, KndxCacheEntry>,
pub history: Vec<Vec<u8>>,
}
#[derive(Debug, Clone)]
pub struct KndxCacheEntry {
pub version_id: Vec<u8>,
pub options: Vec<Vec<u8>>,
pub pos: u64,
pub size: usize,
pub parents: Vec<Vec<u8>>,
pub index: usize,
}
pub const KNDX_HEADER: &[u8] = b"# bzr knit index 8\n";
impl<T: crate::transport::Transport, M: crate::key_mapper::Mapper> KndxIndex<T, M> {
pub fn new(transport: T, mapper: M) -> Self {
Self {
transport,
mapper,
kndx_cache: std::sync::Mutex::new(std::collections::HashMap::new()),
}
}
pub fn prefix_of(key: &KnitKey) -> Vec<Vec<u8>> {
key[..key.len().saturating_sub(1)].iter().cloned().collect()
}
pub fn suffix_of(key: &KnitKey) -> Vec<u8> {
key.last().cloned().unwrap_or_default()
}
pub fn mapper(&self) -> &M {
&self.mapper
}
pub fn transport(&self) -> &T {
&self.transport
}
pub fn transport_mut(&mut self) -> &mut T {
&mut self.transport
}
pub fn kndx_cache(
&self,
) -> &std::sync::Mutex<std::collections::HashMap<Vec<Vec<u8>>, KndxPrefixCache>> {
&self.kndx_cache
}
pub fn prefix_path(&self, prefix: &[Vec<u8>]) -> String {
let refs: Vec<&[u8]> = prefix.iter().map(|s| s.as_slice()).collect();
self.mapper.map(&refs) + ".kndx"
}
pub fn load_prefix_shared(
&self,
prefix: Vec<Vec<u8>>,
) -> Result<(), crate::transport::TransportError> {
self.load_prefix_typed(prefix).map_err(|e| match e {
KndxLoadError::Transport(te) => te,
KndxLoadError::Knit(ke) => crate::transport::TransportError::Other(ke.to_string()),
})
}
pub fn load_prefix_typed(&self, prefix: Vec<Vec<u8>>) -> Result<(), KndxLoadError> {
if self.kndx_cache.lock().unwrap().contains_key(&prefix) {
return Ok(());
}
let path = self.prefix_path(&prefix);
let data = match self.transport.get_bytes(&path) {
Ok(d) => d,
Err(crate::transport::TransportError::NoSuchFile(_)) => {
self.kndx_cache
.lock()
.unwrap()
.insert(prefix, KndxPrefixCache::default());
if self.mapper.is_constant() {
self.transport
.put_file_non_atomic(&path, KNDX_HEADER, true)
.map_err(KndxLoadError::Transport)?;
}
return Ok(());
}
Err(te) => return Err(KndxLoadError::Transport(te)),
};
let pc = parse_kndx_data(&data).map_err(|e| match e {
KnitError::BadKnitHeader { .. } => {
KndxLoadError::Knit(KnitError::BadKnitHeader { path: path.clone() })
}
other => KndxLoadError::Knit(other),
})?;
self.kndx_cache.lock().unwrap().insert(prefix, pc);
Ok(())
}
fn build_details_from_cache(
&self,
keys: &[KnitKey],
) -> std::collections::HashMap<KnitKey, KnitRecordDetails> {
let cache = self.kndx_cache.lock().unwrap();
let mut result = std::collections::HashMap::new();
for key in keys {
let prefix = Self::prefix_of(key);
let suffix = Self::suffix_of(key);
let Some(pc) = cache.get(&prefix) else {
continue;
};
let Some(entry) = pc.cache.get(&suffix) else {
continue;
};
let (method, noeol) = decode_kndx_options(
&entry
.options
.iter()
.map(|o| o.as_slice())
.collect::<Vec<_>>(),
)
.unwrap_or((KnitMethod::Fulltext, false));
let parents: Vec<KnitKey> = entry
.parents
.iter()
.map(|p| {
let mut pk = prefix.clone();
pk.push(p.clone());
pk
})
.collect();
let compression_parent = if method == KnitMethod::LineDelta {
parents.first().cloned()
} else {
None
};
let knit_path = {
let refs: Vec<&[u8]> = prefix.iter().map(|s| s.as_slice()).collect();
self.mapper.map(&refs) + ".knit"
};
result.insert(
key.clone(),
KnitRecordDetails {
method,
noeol,
index_memo: KnitIndexMemo {
file_ref: knit_path,
offset: entry.pos,
length: entry.size,
},
compression_parent,
parents,
},
);
}
result
}
}
pub fn parse_kndx_data(data: &[u8]) -> Result<KndxPrefixCache, KnitError> {
if data.is_empty() {
return Ok(KndxPrefixCache::default());
}
if !data.starts_with(KNDX_HEADER) {
return Err(KnitError::BadKnitHeader {
path: "<kndx>".to_string(),
});
}
parse_kndx_body(&data[KNDX_HEADER.len()..])
}
pub fn parse_kndx_body(rest: &[u8]) -> Result<KndxPrefixCache, KnitError> {
let mut pc = KndxPrefixCache::default();
for line in rest.split(|&b| b == b'\n') {
let line = line.strip_prefix(b"\r").unwrap_or(line);
let line = if line.first() == Some(&b'\n') {
&line[1..]
} else {
line
};
let line = line.strip_prefix(b"\r").unwrap_or(line);
if line.is_empty() {
continue;
}
let Some(line) = line.strip_suffix(b" :") else {
continue;
};
let parts: Vec<&[u8]> = line.splitn(5, |&b| b == b' ').collect();
if parts.len() < 4 {
continue;
}
let version_id = parts[0].to_vec();
let options: Vec<Vec<u8>> = parts[1].split(|&b| b == b',').map(|o| o.to_vec()).collect();
let pos_str = std::str::from_utf8(parts[2]).map_err(|_| KnitError::KndxCorrupt {
line: line.to_vec(),
detail: format!("{:?} is not a valid integer", parts[2]),
})?;
let pos = pos_str.parse::<u64>().map_err(|_| KnitError::KndxCorrupt {
line: line.to_vec(),
detail: format!("{:?} is not a valid integer", pos_str),
})?;
let size_str = std::str::from_utf8(parts[3]).map_err(|_| KnitError::KndxCorrupt {
line: line.to_vec(),
detail: format!("{:?} is not a valid integer", parts[3]),
})?;
let size = size_str
.parse::<usize>()
.map_err(|_| KnitError::KndxCorrupt {
line: line.to_vec(),
detail: format!("{:?} is not a valid integer", size_str),
})?;
let parents_raw = if parts.len() > 4 {
parts[4]
} else {
b"" as &[u8]
};
let mut parents: Vec<Vec<u8>> = vec![];
for p in parents_raw.split(|&b| b == b' ').filter(|p| !p.is_empty()) {
if p.first() == Some(&b'.') {
parents.push(p[1..].to_vec());
} else {
let s = std::str::from_utf8(p).map_err(|_| KnitError::KndxCorrupt {
line: line.to_vec(),
detail: format!("{:?} is not a valid integer", p),
})?;
let idx: usize = s.parse().map_err(|_| KnitError::KndxCorrupt {
line: line.to_vec(),
detail: format!("{:?} is not a valid integer", s),
})?;
if idx >= pc.history.len() {
return Err(KnitError::KndxCorrupt {
line: line.to_vec(),
detail: format!(
"Parent index refers to a revision which does not exist yet. {} > {}",
idx,
pc.history.len()
),
});
}
parents.push(pc.history[idx].clone());
}
}
let index = if pc.cache.contains_key(&version_id) {
pc.cache[&version_id].index
} else {
let idx = pc.history.len();
pc.history.push(version_id.clone());
idx
};
pc.cache.insert(
version_id.clone(),
KndxCacheEntry {
version_id,
options,
pos,
size,
parents,
index,
},
);
}
Ok(pc)
}
impl<T: crate::transport::Transport, M: crate::key_mapper::Mapper> KnitIndex for KndxIndex<T, M> {
type F = String;
fn get_build_details(
&self,
keys: &[KnitKey],
) -> Result<std::collections::HashMap<KnitKey, KnitRecordDetails>, KnitError> {
let prefixes: std::collections::HashSet<Vec<Vec<u8>>> =
keys.iter().map(Self::prefix_of).collect();
for prefix in prefixes {
self.load_prefix_shared(prefix)
.map_err(|e| KnitError::BadIndexValue(e.to_string().into_bytes()))?;
}
Ok(self.build_details_from_cache(keys))
}
fn keys(&self) -> Result<Vec<KnitKey>, KnitError> {
let cache = self.kndx_cache.lock().unwrap();
let mut result = Vec::new();
for (prefix, pc) in cache.iter() {
for suffix in pc.cache.keys() {
let mut key = prefix.clone();
key.push(suffix.clone());
result.push(key);
}
}
Ok(result)
}
fn get_parent_map(
&self,
keys: &[KnitKey],
) -> Result<std::collections::HashMap<KnitKey, Vec<KnitKey>>, KnitError> {
let prefixes: std::collections::HashSet<Vec<Vec<u8>>> =
keys.iter().map(Self::prefix_of).collect();
for prefix in prefixes {
self.load_prefix_shared(prefix)
.map_err(|e| KnitError::BadIndexValue(e.to_string().into_bytes()))?;
}
let cache = self.kndx_cache.lock().unwrap();
let mut result = std::collections::HashMap::new();
for key in keys {
let prefix = Self::prefix_of(key);
let suffix = Self::suffix_of(key);
let Some(pc) = cache.get(&prefix) else {
continue;
};
let Some(entry) = pc.cache.get(&suffix) else {
continue;
};
let parents: Vec<KnitKey> = entry
.parents
.iter()
.map(|p| {
let mut pk = prefix.clone();
pk.push(p.clone());
pk
})
.collect();
result.insert(key.clone(), parents);
}
Ok(result)
}
fn get_method(&self, key: &KnitKey) -> Result<KnitMethod, KnitError> {
let prefix = Self::prefix_of(key);
let suffix = Self::suffix_of(key);
self.load_prefix_shared(prefix.clone())
.map_err(|e| KnitError::BadIndexValue(e.to_string().into_bytes()))?;
let cache = self.kndx_cache.lock().unwrap();
let pc = cache
.get(&prefix)
.ok_or_else(|| KnitError::BadIndexValue(b"prefix not loaded".to_vec()))?;
let entry = pc
.cache
.get(&suffix)
.ok_or_else(|| KnitError::Corrupt(format!("key not found: {:?}", key)))?;
let (method, _) = decode_kndx_options(
&entry
.options
.iter()
.map(|o| o.as_slice())
.collect::<Vec<_>>(),
)
.unwrap_or((KnitMethod::Fulltext, false));
Ok(method)
}
fn get_total_build_size(
&self,
keys: &[KnitKey],
positions: &std::collections::HashMap<KnitKey, KnitRecordDetails>,
) -> usize {
let mut total = 0usize;
let mut seen = std::collections::HashSet::new();
let mut queue: std::collections::VecDeque<&KnitKey> = keys.iter().collect();
while let Some(key) = queue.pop_front() {
if !seen.insert(key) {
continue;
}
if let Some(details) = positions.get(key) {
total += details.index_memo.length;
if let Some(ref cp) = details.compression_parent {
if positions.contains_key(cp) {
queue.push_back(cp);
}
}
}
}
total
}
fn sort_keys_by_io(
&self,
keys: &mut [KnitKey],
positions: &std::collections::HashMap<KnitKey, KnitRecordDetails>,
) {
keys.sort_by(|a, b| {
let a_memo = positions
.get(a)
.map(|d| (&d.index_memo.file_ref, d.index_memo.offset));
let b_memo = positions
.get(b)
.map(|d| (&d.index_memo.file_ref, d.index_memo.offset));
a_memo.cmp(&b_memo)
});
}
fn has_graph(&self) -> bool {
true
}
fn contains(&self, key: &KnitKey) -> Result<bool, KnitError> {
let prefix = Self::prefix_of(key);
let suffix = Self::suffix_of(key);
self.load_prefix_shared(prefix.clone())
.map_err(|e| KnitError::BadIndexValue(e.to_string().into_bytes()))?;
let cache = self.kndx_cache.lock().unwrap();
Ok(cache
.get(&prefix)
.map(|pc| pc.cache.contains_key(&suffix))
.unwrap_or(false))
}
fn get_missing_compression_parents(&self) -> Result<Vec<KnitKey>, KnitError> {
Err(KnitError::NotImplemented("get_missing_compression_parents"))
}
fn check_write_ok(&self) -> Result<(), KnitError> {
Ok(())
}
fn add_records(
&self,
records: &[(KnitKey, Vec<KnitMethod>, KnitIndexMemo, Vec<KnitKey>)],
_random_id: bool,
_missing_compression_parents: bool,
) -> Result<(), KnitError> {
let mut by_prefix: std::collections::HashMap<Vec<Vec<u8>>, Vec<_>> =
std::collections::HashMap::new();
for (key, methods, memo, parents) in records {
let prefix = Self::prefix_of(key);
by_prefix
.entry(prefix)
.or_default()
.push((key, methods, memo, parents));
}
for (prefix, entries) in by_prefix {
self.load_prefix_shared(prefix.clone())
.map_err(|e| KnitError::BadIndexValue(e.to_string().into_bytes()))?;
let path = self.prefix_path(&prefix);
let needs_header = !self
.transport
.has(&path)
.map_err(|e| KnitError::BadIndexValue(e.to_string().into_bytes()))?;
let mut cache = self.kndx_cache.lock().unwrap();
let pc = cache.entry(prefix.clone()).or_default();
let mut append_buf: Vec<u8> = Vec::new();
if needs_header {
append_buf.extend_from_slice(KNDX_HEADER);
}
for (key, methods, memo, parents) in entries {
let suffix = Self::suffix_of(key);
let options: Vec<Vec<u8>> = methods
.iter()
.map(|m| m.as_str().as_bytes().to_vec())
.collect();
let parent_suffixes: Vec<Vec<u8>> =
parents.iter().map(|p| Self::suffix_of(p)).collect();
let encoded_parents: Vec<Vec<u8>> = parent_suffixes
.iter()
.map(|p| match pc.cache.get(p) {
Some(e) => e.index.to_string().into_bytes(),
None => {
let mut v = vec![b'.'];
v.extend_from_slice(p);
v
}
})
.collect();
let idx = pc.history.len();
pc.history.push(suffix.clone());
pc.cache.insert(
suffix.clone(),
KndxCacheEntry {
version_id: suffix.clone(),
options: options.clone(),
pos: memo.offset,
size: memo.length,
parents: parent_suffixes.clone(),
index: idx,
},
);
append_buf.push(b'\n');
append_buf.extend_from_slice(&suffix);
append_buf.push(b' ');
let opts_joined: Vec<u8> = options.join(&b","[..]);
append_buf.extend_from_slice(&opts_joined);
append_buf.push(b' ');
append_buf.extend_from_slice(memo.offset.to_string().as_bytes());
append_buf.push(b' ');
append_buf.extend_from_slice(memo.length.to_string().as_bytes());
for p in &encoded_parents {
append_buf.push(b' ');
append_buf.extend_from_slice(p);
}
append_buf.extend_from_slice(b" :");
}
drop(cache);
append_creating_parent(&self.transport, &path, &append_buf)
.map_err(|e| KnitError::BadIndexValue(e.to_string().into_bytes()))?;
}
Ok(())
}
}
fn append_creating_parent<T: crate::transport::Transport>(
transport: &T,
path: &str,
data: &[u8],
) -> Result<u64, crate::transport::TransportError> {
match transport.append_bytes(path, data) {
Ok(off) => Ok(off),
Err(crate::transport::TransportError::NoSuchFile(_)) => {
let parent = path.rfind('/').map(|i| &path[..i]).unwrap_or("");
transport.mkdir(parent)?;
transport.append_bytes(path, data)
}
Err(e) => Err(e),
}
}
pub struct KnitKeyAccess<T, M> {
transport: T,
mapper: M,
}
impl<T: crate::transport::Transport, M: crate::key_mapper::Mapper> KnitKeyAccess<T, M> {
pub fn new(transport: T, mapper: M) -> Self {
Self { transport, mapper }
}
pub fn mapper(&self) -> &M {
&self.mapper
}
pub fn transport(&self) -> &T {
&self.transport
}
fn key_path(&self, key: &KnitKey) -> String {
let prefix = &key[..key.len().saturating_sub(1)];
let refs: Vec<&[u8]> = prefix.iter().map(|s| s.as_slice()).collect();
self.mapper.map(&refs) + ".knit"
}
pub fn add_raw_record_bytes(
&self,
key: KnitKey,
data: &[u8],
) -> Result<(KnitKey, u64, usize), crate::transport::TransportError> {
let path = self.key_path(&key);
let offset = append_creating_parent(&self.transport, &path, data)?;
Ok((key, offset, data.len()))
}
}
impl<T: crate::transport::Transport, M: crate::key_mapper::Mapper> KnitAccess
for KnitKeyAccess<T, M>
{
type F = String;
fn get_raw_record(&self, memo: &KnitIndexMemo) -> Result<Vec<u8>, KnitError> {
use crate::transport::ReadRange;
let ranges = [ReadRange {
offset: memo.offset,
length: memo.length,
}];
self.transport
.readv(&memo.file_ref, &ranges)
.map_err(|e| KnitError::BadIndexValue(e.to_string().into_bytes()))
.and_then(|mut v| {
v.pop()
.map(|r| r.bytes)
.ok_or_else(|| KnitError::BadIndexValue(b"readv returned no data".to_vec()))
})
}
fn get_raw_records(&self, memos: &[KnitIndexMemo]) -> Result<Vec<Vec<u8>>, KnitError> {
use crate::transport::ReadRange;
let mut by_path: std::collections::HashMap<&str, Vec<(usize, ReadRange)>> =
std::collections::HashMap::new();
for (i, memo) in memos.iter().enumerate() {
by_path.entry(&memo.file_ref).or_default().push((
i,
ReadRange {
offset: memo.offset,
length: memo.length,
},
));
}
let mut out = vec![Vec::new(); memos.len()];
for (path, indexed_ranges) in by_path {
let ranges: Vec<ReadRange> = indexed_ranges.iter().map(|(_, r)| r.clone()).collect();
let results = self
.transport
.readv(path, &ranges)
.map_err(|e| KnitError::BadIndexValue(e.to_string().into_bytes()))?;
for ((orig_idx, _), result) in indexed_ranges.into_iter().zip(results) {
out[orig_idx] = result.bytes;
}
}
Ok(out)
}
fn add_raw_record(
&self,
key: &KnitKey,
_size: usize,
data: Vec<Vec<u8>>,
) -> Result<KnitIndexMemo, KnitError> {
let path = self.key_path(key);
let flat: Vec<u8> = data.into_iter().flatten().collect();
let length = flat.len();
let offset = append_creating_parent(self.transport(), &path, &flat)
.map_err(|e| KnitError::BadIndexValue(e.to_string().into_bytes()))?;
Ok(KnitIndexMemo {
file_ref: path,
offset,
length,
})
}
fn flush(&self) -> Result<(), KnitError> {
Ok(())
}
fn reload_or_raise(&self, err: KnitError) -> Result<(), KnitError> {
Err(err)
}
}
pub struct KnitVersionedFiles<I, A, F> {
pub index: I,
pub access: A,
pub factory: F,
pub max_delta_chain: usize,
}
impl<I, A, F> KnitVersionedFiles<I, A, F>
where
I: KnitIndex,
A: KnitAccess<F = I::F>,
F: KnitFactory,
{
pub fn new(index: I, access: A, factory: F, max_delta_chain: usize) -> Self {
Self {
index,
access,
factory,
max_delta_chain,
}
}
pub fn index(&self) -> &I {
&self.index
}
fn with_retry<T>(&self, mut op: impl FnMut() -> Result<T, KnitError>) -> Result<T, KnitError> {
loop {
match op() {
Err(err @ KnitError::Retry(_)) => self.access.reload_or_raise(err)?,
other => return other,
}
}
}
pub fn keys(&self) -> Result<Vec<KnitKey>, KnitError> {
self.index.keys()
}
pub fn get_parent_map(
&self,
keys: &[KnitKey],
) -> Result<std::collections::HashMap<KnitKey, Vec<KnitKey>>, KnitError> {
self.index.get_parent_map(keys)
}
pub fn get_text(&self, key: &KnitKey) -> Result<Vec<u8>, KnitError> {
get_text(&self.index, &self.access, &self.factory, key)
}
pub fn get_sha1s(
&self,
keys: &[KnitKey],
) -> Result<std::collections::HashMap<KnitKey, Vec<u8>>, KnitError> {
get_sha1s(&self.index, &self.access, keys)
}
pub fn get_content(&self, key: &KnitKey) -> Result<F::Content, KnitError> {
get_content(&self.index, &self.access, &self.factory, key)
}
pub fn get_build_details(
&self,
keys: &[KnitKey],
) -> Result<std::collections::HashMap<KnitKey, KnitRecordDetails<I::F>>, KnitError> {
self.index.get_build_details(keys)
}
pub fn contains(&self, key: &KnitKey) -> Result<bool, KnitError> {
self.index.contains(key)
}
pub fn get_missing_compression_parent_keys(&self) -> Result<Vec<KnitKey>, KnitError> {
self.index.get_missing_compression_parents()
}
pub fn check_should_delta(&self, parent: &KnitKey) -> Result<bool, KnitError> {
if self.max_delta_chain == 0 {
return Ok(false);
}
let mut cursor = parent.clone();
let mut steps = 0usize;
let mut delta_size = 0u64;
loop {
let details_map = self
.index
.get_build_details(std::slice::from_ref(&cursor))?;
let Some(det) = details_map.get(&cursor) else {
return Ok(false);
};
if det.method == KnitMethod::Fulltext {
return Ok(delta_size < det.index_memo.length as u64 * 2 + 200);
}
delta_size += det.index_memo.length as u64;
steps += 1;
if steps >= self.max_delta_chain {
return Ok(false);
}
match det.compression_parent.clone() {
Some(cp) => cursor = cp,
None => return Ok(false),
}
}
}
pub fn add_lines(
&self,
key: KnitKey,
parents: Vec<KnitKey>,
lines: Vec<Vec<u8>>,
random_id: bool,
) -> Result<(Vec<u8>, usize), KnitError> {
use crate::osutils::sha::sha_string;
self.index.check_write_ok()?;
let line_bytes: Vec<u8> = lines.iter().flat_map(|l| l.iter().copied()).collect();
let digest = sha_string(&line_bytes).into_bytes();
let text_length = line_bytes.len();
let no_eol = !line_bytes.is_empty() && !line_bytes.ends_with(b"\n");
let version_id = key.last().cloned().unwrap_or_default();
let present_map = self.index.get_parent_map(&parents)?;
let use_delta = parents.first().is_some_and(|p| present_map.contains_key(p))
&& self.max_delta_chain > 0
&& self.check_should_delta(&parents[0])?;
let present_parents: Vec<KnitKey> = parents
.iter()
.filter(|p| present_map.contains_key(*p))
.cloned()
.collect();
let content_lines = if no_eol {
let mut l = lines.clone();
if let Some(last) = l.last_mut() {
last.push(b'\n');
}
l
} else {
lines
};
let (method, payload) = {
let mut content = self.factory.make(content_lines, version_id.clone());
if no_eol {
content.set_should_strip_eol(true);
}
let delta_opt = merge_annotations(
&self.index,
&self.access,
&self.factory,
&mut content,
&present_parents,
use_delta,
)?;
if let Some(delta) = delta_opt {
let serialised = self.factory.lower_line_delta(&delta);
(KnitMethod::LineDelta, serialised)
} else {
let serialised = self.factory.lower_fulltext(&content);
(KnitMethod::Fulltext, serialised)
}
};
let (size, chunks) = record_to_data(&version_id, &digest, payload.len(), &payload, true)?;
let memo = self.access.add_raw_record(&key, size, chunks)?;
let mut options = vec![method];
if no_eol {
options.push(KnitMethod::NoEol);
}
self.index
.add_records(&[(key, options, memo, parents)], random_id, false)?;
Ok((digest, text_length))
}
pub fn read_records_iter(
&self,
records: &[(KnitKey, KnitIndexMemo<I::F>)],
) -> Result<Vec<(KnitKey, F::Content, Vec<u8>)>, KnitError> {
if records.is_empty() {
return Ok(vec![]);
}
let mut sorted = records.to_vec();
sorted.sort_by(|a, b| (&a.1.file_ref, a.1.offset).cmp(&(&b.1.file_ref, b.1.offset)));
let memos: Vec<KnitIndexMemo<I::F>> = sorted.iter().map(|(_, m)| m.clone()).collect();
let raw_data = self.access.get_raw_records(&memos)?;
let mut out = Vec::with_capacity(sorted.len());
for ((key, _), raw) in sorted.into_iter().zip(raw_data) {
let version_id = key.last().cloned().unwrap_or_default();
let (body_lines, digest) = parse_record(&version_id, &raw)?;
let refs: Vec<&[u8]> = body_lines.iter().map(|l| l.as_slice()).collect();
let content = self.factory.parse_fulltext_content(&refs, &version_id)?;
out.push((key, content, digest));
}
Ok(out)
}
pub fn read_records_iter_unchecked(
&self,
records: &[(KnitKey, KnitIndexMemo<I::F>)],
) -> Result<Vec<(KnitKey, Vec<u8>)>, KnitError> {
if records.is_empty() {
return Ok(vec![]);
}
let memos: Vec<KnitIndexMemo<I::F>> = records.iter().map(|(_, m)| m.clone()).collect();
let raw_data = self.access.get_raw_records(&memos)?;
Ok(records
.iter()
.map(|(k, _)| k.clone())
.zip(raw_data)
.collect())
}
pub fn read_records_iter_raw(
&self,
records: &[(KnitKey, KnitIndexMemo<I::F>)],
) -> Result<Vec<(KnitKey, Vec<u8>, Vec<u8>)>, KnitError> {
let pairs = self.read_records_iter_unchecked(records)?;
let mut out = Vec::with_capacity(pairs.len());
for (key, raw) in pairs {
let header = parse_record_header_only(&raw)?;
out.push((key, raw, header.digest));
}
Ok(out)
}
pub fn iter_lines_added_or_present_in_keys(
&self,
keys: &[KnitKey],
) -> Result<Vec<(Vec<u8>, KnitKey)>, KnitError> {
self.with_retry(|| self.iter_lines_added_or_present_in_keys_once(keys))
}
fn iter_lines_added_or_present_in_keys_once(
&self,
keys: &[KnitKey],
) -> Result<Vec<(Vec<u8>, KnitKey)>, KnitError> {
if keys.is_empty() {
return Ok(vec![]);
}
let build_details = self.index.get_build_details(keys)?;
let key_records: Vec<(KnitKey, KnitIndexMemo<I::F>)> = build_details
.iter()
.filter(|(k, _)| keys.contains(k))
.map(|(k, det)| (k.clone(), det.index_memo.clone()))
.collect();
let memos: Vec<KnitIndexMemo<I::F>> = key_records.iter().map(|(_, m)| m.clone()).collect();
let raw_data = self.access.get_raw_records(&memos)?;
let mut out = Vec::new();
for ((key, _), raw) in key_records.iter().zip(raw_data) {
let version_id = key.last().cloned().unwrap_or_default();
let (body_lines, _digest) = parse_record(&version_id, &raw)?;
let details = &build_details[key];
match details.method {
KnitMethod::Fulltext => {
for line in self.factory.fulltext_payload_lines(&body_lines)? {
out.push((line, key.clone()));
}
}
KnitMethod::LineDelta => {
for line in self.factory.linedelta_payload_lines(&body_lines)? {
out.push((line, key.clone()));
}
}
KnitMethod::NoEol => {
return Err(KnitError::BadIndexValue(
b"NoEol is not a storage method".to_vec(),
));
}
}
}
Ok(out)
}
}
pub enum KnitStreamRecord {
NativeKnit {
key: KnitKey,
parents: Vec<KnitKey>,
method: KnitMethod,
noeol: bool,
compression_parent: Option<KnitKey>,
raw_record: Vec<u8>,
},
ConvertAnnotated {
key: KnitKey,
parents: Vec<KnitKey>,
method: KnitMethod,
noeol: bool,
compression_parent: Option<KnitKey>,
raw_record: Vec<u8>,
},
ConvertPlain {
key: KnitKey,
parents: Vec<KnitKey>,
method: KnitMethod,
noeol: bool,
compression_parent: Option<KnitKey>,
raw_record: Vec<u8>,
},
Lines {
key: KnitKey,
parents: Vec<KnitKey>,
lines: Vec<Vec<u8>>,
},
}
#[derive(Debug, Clone)]
pub struct DeltaClosureRawEntry {
pub raw_bytes: Vec<u8>,
pub method: KnitMethod,
pub noeol: bool,
pub next: Option<KnitKey>,
}
pub type DeltaClosureRawMap = std::collections::HashMap<KnitKey, DeltaClosureRawEntry>;
pub struct ParsedDeltaClosure {
pub annotated: bool,
pub keys: Vec<KnitKey>,
pub global_map: std::collections::HashMap<KnitKey, Option<Vec<KnitKey>>>,
pub raw_map: DeltaClosureRawMap,
}
pub fn parse_delta_closure_wire_bytes(
bytes: &[u8],
line_end: usize,
) -> Result<ParsedDeltaClosure, KnitError> {
let mut start = line_end;
let find_nl = |from: usize| -> Result<usize, KnitError> {
bytes[from..]
.iter()
.position(|&b| b == b'\n')
.map(|p| from + p)
.ok_or_else(|| KnitError::Corrupt("truncated delta-closure wire bytes".to_string()))
};
let parse_key_bytes =
|seg: &[u8]| -> KnitKey { seg.split(|&b| b == b'\x00').map(|s| s.to_vec()).collect() };
let nl = find_nl(start)?;
let annotated = &bytes[start..nl] == b"annotated";
start = nl + 1;
let nl = find_nl(start)?;
let keys_line = &bytes[start..nl];
start = nl + 1;
let keys: Vec<KnitKey> = keys_line
.split(|&b| b == b'\t')
.filter(|s| !s.is_empty())
.map(parse_key_bytes)
.collect();
let mut global_map = std::collections::HashMap::new();
let mut raw_map = DeltaClosureRawMap::new();
let end = bytes.len();
while start < end {
let nl = find_nl(start)?;
let key = parse_key_bytes(&bytes[start..nl]);
start = nl + 1;
let nl = find_nl(start)?;
let parents_line = &bytes[start..nl];
start = nl + 1;
let parents: Option<Vec<KnitKey>> = if parents_line == b"None:" {
None
} else {
Some(
parents_line
.split(|&b| b == b'\t')
.filter(|s| !s.is_empty())
.map(parse_key_bytes)
.collect(),
)
};
global_map.insert(key.clone(), parents);
let nl = find_nl(start)?;
let method_str = std::str::from_utf8(&bytes[start..nl])
.map_err(|_| KnitError::Corrupt("non-UTF8 method in delta-closure".to_string()))?;
let method = KnitMethod::from_str(method_str)
.ok_or_else(|| KnitError::Corrupt(format!("unknown method: {method_str}")))?;
start = nl + 1;
let nl = find_nl(start)?;
let noeol = bytes[start] == b'T';
start = nl + 1;
let nl = find_nl(start)?;
let next_line = &bytes[start..nl];
let next = if next_line.is_empty() {
None
} else {
Some(parse_key_bytes(next_line))
};
start = nl + 1;
let nl = find_nl(start)?;
let count_str = std::str::from_utf8(&bytes[start..nl])
.map_err(|_| KnitError::Corrupt("non-UTF8 byte count".to_string()))?;
let count: usize = count_str
.parse()
.map_err(|_| KnitError::Corrupt(format!("invalid byte count: {count_str}")))?;
start = nl + 1;
let raw_bytes = bytes[start..start + count].to_vec();
start += count;
raw_map.insert(
key,
DeltaClosureRawEntry {
raw_bytes,
method,
noeol,
next,
},
);
}
Ok(ParsedDeltaClosure {
annotated,
keys,
global_map,
raw_map,
})
}
pub fn reconstruct_text_from_raw_map<F: KnitFactory>(
factory: &F,
raw_map: &DeltaClosureRawMap,
key: &KnitKey,
) -> Result<(Vec<Vec<u8>>, Vec<u8>), KnitError> {
let mut chain: Vec<KnitKey> = Vec::new();
let mut cursor = key.clone();
loop {
let entry = raw_map.get(&cursor).ok_or_else(|| {
KnitError::Corrupt(format!("key {cursor:?} missing from raw record map"))
})?;
chain.push(cursor.clone());
match &entry.next {
None => break,
Some(next) => cursor = next.clone(),
}
}
let mut content: Option<F::Content> = None;
let mut last_digest = Vec::new();
for k in chain.iter().rev() {
let entry = &raw_map[k];
let version_id = k.last().cloned().unwrap_or_default();
let (body_lines, digest) = parse_record(&version_id, &entry.raw_bytes)?;
let refs: Vec<&[u8]> = body_lines.iter().map(|l| l.as_slice()).collect();
let new_content = factory.parse_record(
&version_id,
&refs,
entry.method.clone(),
entry.noeol,
content.as_ref(),
)?;
content = Some(new_content);
last_digest = digest;
}
let content = content.ok_or_else(|| KnitError::Corrupt("empty chain".to_string()))?;
Ok((
content.text().into_iter().map(|l| l.to_vec()).collect(),
last_digest,
))
}
pub fn build_delta_closure_wire_bytes(
annotated: bool,
emit_keys: &[KnitKey],
raw_map: &DeltaClosureRawMap,
global_map: &std::collections::HashMap<KnitKey, Option<Vec<KnitKey>>>,
) -> Vec<u8> {
let parent_slices: Vec<Option<Vec<&[Vec<u8>]>>> = raw_map
.iter()
.map(|(key, _)| {
global_map
.get(key)
.and_then(|p| p.as_ref())
.map(|ps| ps.iter().map(|p| p.as_slice()).collect())
})
.collect();
let emit_key_slices: Vec<&[Vec<u8>]> = emit_keys.iter().map(|k| k.as_slice()).collect();
let records: Vec<KnitDeltaClosureRecord<'_, Vec<u8>>> = raw_map
.iter()
.zip(parent_slices.iter())
.map(|((key, entry), parents_opt)| KnitDeltaClosureRecord {
key: key.as_slice(),
parents: parents_opt.as_deref(),
method: entry.method.as_str().as_bytes(),
noeol: entry.noeol,
next: entry.next.as_deref(),
record_bytes: &entry.raw_bytes,
})
.collect();
build_knit_delta_closure_wire(annotated, &emit_key_slices, &records)
}
#[derive(Debug, Clone)]
pub struct KnitContentFactory<F: FileRef = String> {
pub key: KnitKey,
pub parents: Option<Vec<KnitKey>>,
pub record_details: KnitRecordDetails<F>,
pub sha1: Option<Vec<u8>>,
pub raw_record: Vec<u8>,
pub annotated: bool,
}
impl<F: FileRef> KnitContentFactory<F> {
fn into_lines_inner(&self) -> Result<Vec<Vec<u8>>, KnitError> {
if self.raw_record.is_empty() {
return Err(KnitError::RevisionNotPresent(self.key.clone()));
}
let version_id = self.key.last().map(Vec::as_slice).unwrap_or(&[]);
let (body_lines, _digest) = parse_record(version_id, &self.raw_record)?;
let refs: Vec<&[u8]> = body_lines.iter().map(|l| l.as_slice()).collect();
if self.annotated {
let content = KnitAnnotateFactory.parse_record(
version_id,
&refs,
self.record_details.method.clone(),
self.record_details.noeol,
None,
)?;
Ok(content.text().into_iter().collect())
} else {
let content = KnitPlainFactory.parse_record(
version_id,
&refs,
self.record_details.method.clone(),
self.record_details.noeol,
None,
)?;
Ok(content.text().into_iter().collect())
}
}
fn into_fulltext_inner(&self) -> Result<Vec<u8>, KnitError> {
let lines = self.into_lines_inner()?;
Ok(lines.into_iter().flatten().collect())
}
}
impl<F: FileRef> crate::versionedfile::ContentFactory for KnitContentFactory<F> {
fn sha1(&self) -> Option<Vec<u8>> {
self.sha1.clone()
}
fn size(&self) -> Option<usize> {
None
}
fn key(&self) -> crate::versionedfile::Key {
crate::versionedfile::Key::Fixed(self.key.clone())
}
fn parents(&self) -> Option<Vec<crate::versionedfile::Key>> {
self.parents.as_ref().map(|ps| {
ps.iter()
.cloned()
.map(crate::versionedfile::Key::Fixed)
.collect()
})
}
fn storage_kind(&self) -> String {
if self.raw_record.is_empty() {
"absent".to_string()
} else {
let annotated_prefix = if self.annotated { "annotated-" } else { "" };
match self.record_details.method {
KnitMethod::LineDelta => format!("knit-{annotated_prefix}delta-gz"),
KnitMethod::Fulltext | KnitMethod::NoEol => {
format!("knit-{annotated_prefix}ft-gz")
}
}
}
}
fn to_fulltext<'a, 'b>(&'a self) -> std::borrow::Cow<'b, [u8]>
where
'a: 'b,
{
std::borrow::Cow::Owned(self.into_fulltext_inner().unwrap_or_default())
}
fn to_chunks<'a, 'b>(&'a self) -> Box<dyn Iterator<Item = std::borrow::Cow<'b, [u8]>> + 'b>
where
'a: 'b,
{
Box::new(std::iter::once(std::borrow::Cow::Owned(
self.into_fulltext_inner().unwrap_or_default(),
)))
}
fn to_lines<'a, 'b>(&'a self) -> Box<dyn Iterator<Item = std::borrow::Cow<'b, [u8]>> + 'b>
where
'a: 'b,
{
let lines = self.into_lines_inner().unwrap_or_default();
Box::new(lines.into_iter().map(std::borrow::Cow::Owned))
}
fn into_fulltext(self) -> Vec<u8> {
self.into_fulltext_inner().unwrap_or_default()
}
fn into_chunks(self) -> Box<dyn Iterator<Item = Vec<u8>>> {
Box::new(std::iter::once(
self.into_fulltext_inner().unwrap_or_default(),
))
}
fn map_key(&mut self, f: &dyn Fn(crate::versionedfile::Key) -> crate::versionedfile::Key) {
let new_key = f(crate::versionedfile::Key::Fixed(self.key.clone()));
self.key = match new_key {
crate::versionedfile::Key::Fixed(v)
| crate::versionedfile::Key::ContentAddressed(v) => v,
};
self.parents = self.parents.take().map(|ps| {
ps.into_iter()
.map(|p| match f(crate::versionedfile::Key::Fixed(p)) {
crate::versionedfile::Key::Fixed(v)
| crate::versionedfile::Key::ContentAddressed(v) => v,
})
.collect()
});
}
}
impl<I: KnitIndex, A: KnitAccess<F = I::F>, F: KnitFactory> KnitVersionedFiles<I, A, F> {
pub fn get_record_stream(
&self,
keys: &[KnitKey],
ordering: &str,
include_delta_closure: bool,
) -> Result<Vec<KnitContentFactory<I::F>>, KnitError> {
self.with_retry(|| self.get_record_stream_once(keys, ordering, include_delta_closure))
}
fn get_record_stream_once(
&self,
keys: &[KnitKey],
ordering: &str,
include_delta_closure: bool,
) -> Result<Vec<KnitContentFactory<I::F>>, KnitError> {
use std::collections::{HashMap, HashSet};
if keys.is_empty() {
return Ok(vec![]);
}
let positions: HashMap<KnitKey, KnitRecordDetails<I::F>> = if include_delta_closure {
let closure_result = walk_compression_closure::<KnitKey, KnitRecordDetails<I::F>, _>(
keys.iter().cloned(),
true,
|batch| {
let details = self.index.get_build_details(batch).unwrap_or_default();
let mut present = HashMap::new();
let mut missing = HashSet::new();
for k in batch {
if let Some(det) = details.get(k) {
present
.insert(k.clone(), (det.compression_parent.clone(), det.clone()));
} else {
missing.insert(k.clone());
}
}
ClosureBatch { present, missing }
},
);
closure_result.unwrap_or_default()
} else {
self.index.get_build_details(keys)?
};
let present_keys: Vec<KnitKey> = keys
.iter()
.filter(|k| positions.contains_key(*k))
.cloned()
.collect();
let absent_keys: Vec<KnitKey> = keys
.iter()
.filter(|k| !positions.contains_key(*k))
.cloned()
.collect();
let sorted_keys: Vec<KnitKey> = match ordering {
"topological" => {
let parent_map = self.index.get_parent_map(&present_keys)?;
let mut sorter = vcs_graph::tsort::TopoSorter::new(parent_map.into_iter());
sorter
.sorted()
.map_err(|e| KnitError::Corrupt(format!("topo_sort: {e:?}")))?
}
_ => {
let mut ks = present_keys.clone();
self.index.sort_keys_by_io(&mut ks, &positions);
ks
}
};
let memos: Vec<KnitIndexMemo<I::F>> = sorted_keys
.iter()
.map(|k| positions[k].index_memo.clone())
.collect();
let raw_records = self.access.get_raw_records(&memos)?;
let mut out: Vec<KnitContentFactory<I::F>> = Vec::with_capacity(keys.len());
for key in &absent_keys {
out.push(KnitContentFactory {
key: key.clone(),
parents: None,
record_details: KnitRecordDetails {
method: KnitMethod::Fulltext,
noeol: false,
index_memo: KnitIndexMemo {
file_ref: I::F::placeholder(),
offset: 0,
length: 0,
},
compression_parent: None,
parents: vec![],
},
sha1: None,
raw_record: vec![],
annotated: self.factory.annotated(),
});
}
for (key, raw) in sorted_keys.into_iter().zip(raw_records) {
let details = positions[&key].clone();
out.push(KnitContentFactory {
key,
parents: Some(details.parents.clone()),
record_details: details,
sha1: None,
raw_record: raw,
annotated: self.factory.annotated(),
});
}
Ok(out)
}
pub fn insert_record_stream(
&self,
stream: impl IntoIterator<Item = Result<KnitStreamRecord, KnitError>>,
) -> Result<(), KnitError> {
use std::collections::HashMap;
self.index.check_write_ok()?;
let mut buffered: HashMap<
KnitKey,
Vec<(KnitKey, Vec<KnitMethod>, KnitIndexMemo<I::F>, Vec<KnitKey>)>,
> = HashMap::new();
for item in stream {
let record = item?;
let (key, parents, method, noeol, compression_parent, raw_bytes) = match record {
KnitStreamRecord::NativeKnit {
key,
parents,
method,
noeol,
compression_parent,
raw_record,
} => (key, parents, method, noeol, compression_parent, raw_record),
KnitStreamRecord::ConvertAnnotated {
key,
parents,
method,
noeol,
compression_parent,
raw_record,
} => {
if method == KnitMethod::LineDelta && self.max_delta_chain == 0 {
let plain_delta = recompress_annotated_to_unannotated_delta(&raw_record)?;
let lines = decode_plain_knit_to_lines(
self,
&key,
KnitMethod::LineDelta,
noeol,
compression_parent.as_ref(),
&plain_delta,
)?;
self.access.flush()?;
self.add_lines(key.clone(), parents, lines, false)?;
let mut ready = vec![key];
while let Some(k) = ready.pop() {
if let Some(entries) = buffered.remove(&k) {
let new_keys: Vec<KnitKey> =
entries.iter().map(|(ek, _, _, _)| ek.clone()).collect();
self.index.add_records(&entries, false, false)?;
ready.extend(new_keys);
}
}
continue;
}
let converted = match method {
KnitMethod::LineDelta => {
recompress_annotated_to_unannotated_delta(&raw_record)?
}
_ => recompress_annotated_to_unannotated_fulltext(&raw_record)?,
};
(key, parents, method, noeol, compression_parent, converted)
}
KnitStreamRecord::ConvertPlain {
key,
parents,
method,
noeol,
compression_parent,
raw_record,
} => {
let lines = decode_plain_knit_to_lines(
self,
&key,
method,
noeol,
compression_parent.as_ref(),
&raw_record,
)?;
self.access.flush()?;
self.add_lines(key.clone(), parents, lines, false)?;
let mut ready = vec![key];
while let Some(k) = ready.pop() {
if let Some(entries) = buffered.remove(&k) {
let new_keys: Vec<KnitKey> =
entries.iter().map(|(ek, _, _, _)| ek.clone()).collect();
self.index.add_records(&entries, false, false)?;
ready.extend(new_keys);
}
}
continue;
}
KnitStreamRecord::Lines {
key,
parents,
lines,
} => {
self.access.flush()?;
self.add_lines(key.clone(), parents, lines, false)?;
let mut ready = vec![key];
while let Some(k) = ready.pop() {
if let Some(entries) = buffered.remove(&k) {
let new_keys: Vec<KnitKey> =
entries.iter().map(|(ek, _, _, _)| ek.clone()).collect();
self.index.add_records(&entries, false, false)?;
ready.extend(new_keys);
}
}
continue;
}
};
parse_record_header_only(&raw_bytes)?;
let size = raw_bytes.len();
let memo = self.access.add_raw_record(&key, size, vec![raw_bytes])?;
let mut options = vec![method];
if noeol {
options.push(KnitMethod::NoEol);
}
let entry = (key.clone(), options, memo, parents.to_vec());
let needs_buffer = compression_parent.as_ref().is_some_and(|cp| {
self.index
.get_parent_map(std::slice::from_ref(cp))
.map(|m| !m.contains_key(cp))
.unwrap_or(true)
});
if needs_buffer {
buffered
.entry(compression_parent.unwrap())
.or_default()
.push(entry);
} else {
self.index.add_records(&[entry], false, false)?;
let mut ready = vec![key];
while let Some(k) = ready.pop() {
if let Some(entries) = buffered.remove(&k) {
let new_keys: Vec<KnitKey> =
entries.iter().map(|(ek, _, _, _)| ek.clone()).collect();
self.index.add_records(&entries, false, false)?;
ready.extend(new_keys);
}
}
}
}
if !buffered.is_empty() {
let all_entries: Vec<_> = buffered.into_values().flatten().collect();
self.index.add_records(&all_entries, false, true)?;
}
Ok(())
}
pub fn get_record_stream_with_fallbacks(
&self,
keys: &[KnitKey],
ordering: &str,
include_delta_closure: bool,
fallbacks: &[&dyn crate::versionedfile::VersionedFiles],
) -> Result<Vec<Box<dyn crate::versionedfile::ContentFactory>>, KnitError> {
use crate::versionedfile::ContentFactory;
use std::collections::{HashMap, HashSet};
if keys.is_empty() {
return Ok(vec![]);
}
let mut global_map: HashMap<KnitKey, Vec<KnitKey>> = HashMap::new();
let mut missing: HashSet<KnitKey> = keys.iter().cloned().collect();
let local_map = self.index.get_parent_map(keys)?;
for (k, v) in &local_map {
global_map.insert(k.clone(), v.clone());
missing.remove(k);
}
for fallback in fallbacks {
if missing.is_empty() {
break;
}
let fb_keys: Vec<crate::versionedfile::Key> =
missing.iter().map(vf_key_from_knit).collect();
let fb_map = fallback.get_parent_map(&fb_keys)?;
for (k, v) in &fb_map {
let kk = knit_key_from_vf(k);
let parents = v.iter().map(knit_key_from_vf).collect();
global_map.insert(kk.clone(), parents);
missing.remove(&kk);
}
}
let absent_keys: Vec<KnitKey> = missing.into_iter().collect();
let present_keys: Vec<KnitKey> = if ordering == "topological" {
vcs_graph::tsort::TopoSorter::new(
global_map.iter().map(|(k, v)| (k.clone(), v.clone())),
)
.sorted()
.map_err(|e| KnitError::Corrupt(format!("topo_sort: {e:?}")))?
} else {
global_map.keys().cloned().collect()
};
let local_recs =
self.get_record_stream(&present_keys, "unordered", include_delta_closure)?;
let local_present: HashSet<KnitKey> = local_map.keys().cloned().collect();
let mut local_rec_map: HashMap<KnitKey, Box<dyn ContentFactory>> = local_recs
.into_iter()
.filter(|r| r.storage_kind() != "absent")
.map(|r| {
let key = match r.key() {
crate::versionedfile::Key::Fixed(v)
| crate::versionedfile::Key::ContentAddressed(v) => v,
};
(key, Box::new(r) as Box<dyn ContentFactory>)
})
.collect();
let mut fallback_rec_map: HashMap<KnitKey, Box<dyn ContentFactory>> = HashMap::new();
let mut fb_needed: Vec<KnitKey> = present_keys
.iter()
.filter(|k| !local_present.contains(*k))
.cloned()
.collect();
for fallback in fallbacks {
if fb_needed.is_empty() {
break;
}
let fb_keys: Vec<crate::versionedfile::Key> =
fb_needed.iter().map(vf_key_from_knit).collect();
let fb_recs = fallback.get_record_stream(&fb_keys, ordering, include_delta_closure)?;
let mut still_needed = Vec::new();
for rec in fb_recs {
let rec = rec?;
let rec_key = knit_key_from_vf(&rec.key());
if rec.storage_kind() == "absent" {
still_needed.push(rec_key);
} else {
fallback_rec_map.insert(rec_key, rec);
}
}
fb_needed = still_needed;
}
let mut out: Vec<Box<dyn ContentFactory>> = Vec::with_capacity(keys.len());
for key in &present_keys {
if let Some(rec) = local_rec_map.remove(key) {
out.push(rec);
} else if let Some(rec) = fallback_rec_map.remove(key) {
out.push(rec);
}
}
for key in absent_keys {
out.push(Box::new(crate::versionedfile::AbsentContentFactory::new(
vf_key_from_knit(&key),
)));
}
for key in fb_needed {
out.push(Box::new(crate::versionedfile::AbsentContentFactory::new(
vf_key_from_knit(&key),
)));
}
Ok(out)
}
pub fn insert_record_stream_with_fallbacks(
&self,
stream: impl IntoIterator<Item = Result<KnitStreamRecord, KnitError>>,
fallbacks: &[&dyn crate::versionedfile::VersionedFiles],
) -> Result<(), KnitError> {
use std::collections::HashMap;
self.index.check_write_ok()?;
let mut buffered: HashMap<
KnitKey,
Vec<(KnitKey, Vec<KnitMethod>, KnitIndexMemo<I::F>, Vec<KnitKey>)>,
> = HashMap::new();
for item in stream {
let record = item?;
let (key, parents, method, noeol, compression_parent, raw_bytes) = match record {
KnitStreamRecord::NativeKnit {
key,
parents,
method,
noeol,
compression_parent,
raw_record,
} => (key, parents, method, noeol, compression_parent, raw_record),
KnitStreamRecord::ConvertAnnotated {
key,
parents,
method,
noeol,
compression_parent,
raw_record,
} => {
if method == KnitMethod::LineDelta && self.max_delta_chain == 0 {
let plain_delta = recompress_annotated_to_unannotated_delta(&raw_record)?;
let lines = decode_plain_knit_to_lines_with_fallbacks(
self,
&key,
KnitMethod::LineDelta,
noeol,
compression_parent.as_ref(),
&plain_delta,
fallbacks,
)?;
self.access.flush()?;
self.add_lines(key.clone(), parents, lines, false)?;
let mut ready = vec![key];
while let Some(k) = ready.pop() {
if let Some(entries) = buffered.remove(&k) {
let new_keys: Vec<KnitKey> =
entries.iter().map(|(ek, _, _, _)| ek.clone()).collect();
self.index.add_records(&entries, false, false)?;
ready.extend(new_keys);
}
}
continue;
}
let converted = match method {
KnitMethod::LineDelta => {
recompress_annotated_to_unannotated_delta(&raw_record)?
}
_ => recompress_annotated_to_unannotated_fulltext(&raw_record)?,
};
(key, parents, method, noeol, compression_parent, converted)
}
KnitStreamRecord::ConvertPlain {
key,
parents,
method,
noeol,
compression_parent,
raw_record,
} => {
let lines = decode_plain_knit_to_lines_with_fallbacks(
self,
&key,
method,
noeol,
compression_parent.as_ref(),
&raw_record,
fallbacks,
)?;
self.access.flush()?;
self.add_lines(key.clone(), parents, lines, false)?;
let mut ready = vec![key];
while let Some(k) = ready.pop() {
if let Some(entries) = buffered.remove(&k) {
let new_keys: Vec<KnitKey> =
entries.iter().map(|(ek, _, _, _)| ek.clone()).collect();
self.index.add_records(&entries, false, false)?;
ready.extend(new_keys);
}
}
continue;
}
KnitStreamRecord::Lines {
key,
parents,
lines,
} => {
self.access.flush()?;
self.add_lines(key.clone(), parents, lines, false)?;
let mut ready = vec![key];
while let Some(k) = ready.pop() {
if let Some(entries) = buffered.remove(&k) {
let new_keys: Vec<KnitKey> =
entries.iter().map(|(ek, _, _, _)| ek.clone()).collect();
self.index.add_records(&entries, false, false)?;
ready.extend(new_keys);
}
}
continue;
}
};
parse_record_header_only(&raw_bytes)?;
let mut cp_fallback_idx: Option<usize> = None;
let store_directly = if let Some(cp) = compression_parent.as_ref() {
if fallbacks.is_empty() {
true
} else {
let in_local = self
.index
.get_parent_map(std::slice::from_ref(cp))
.map(|m| m.contains_key(cp))
.unwrap_or(false);
if in_local {
true
} else {
let cp_vf = vf_key_from_knit(cp);
let fb_idx = fallbacks.iter().position(|fb| {
fb.get_parent_map(std::slice::from_ref(&cp_vf))
.map(|m| !m.is_empty())
.unwrap_or(false)
});
cp_fallback_idx = fb_idx;
fb_idx.is_none()
}
}
} else {
true
};
if store_directly {
let size = raw_bytes.len();
let memo = self.access.add_raw_record(&key, size, vec![raw_bytes])?;
let mut options = vec![method];
if noeol {
options.push(KnitMethod::NoEol);
}
let entry = (key.clone(), options, memo, parents.to_vec());
let needs_buffer = compression_parent.as_ref().is_some_and(|cp| {
self.index
.get_parent_map(std::slice::from_ref(cp))
.map(|m| !m.contains_key(cp))
.unwrap_or(true)
});
if needs_buffer {
buffered
.entry(compression_parent.unwrap())
.or_default()
.push(entry);
} else {
self.index.add_records(&[entry], false, false)?;
let mut ready = vec![key];
while let Some(k) = ready.pop() {
if let Some(entries) = buffered.remove(&k) {
let new_keys: Vec<KnitKey> =
entries.iter().map(|(ek, _, _, _)| ek.clone()).collect();
self.index.add_records(&entries, false, false)?;
ready.extend(new_keys);
}
}
}
} else {
let cp = compression_parent.as_ref().unwrap();
self.access.flush()?;
let fb_idx =
cp_fallback_idx.expect("store_directly == false implies a fallback was found");
let fb = fallbacks[fb_idx];
let cp_vf = vf_key_from_knit(cp);
let mut basis_iter =
fb.get_record_stream(std::slice::from_ref(&cp_vf), "unordered", true)?;
let basis = loop {
match basis_iter.next() {
Some(Ok(rec)) => {
if rec.storage_kind() != "absent" {
break Some(rec);
}
}
Some(Err(e)) => return Err(e),
None => break None,
}
}
.ok_or_else(|| {
KnitError::Corrupt(format!(
"compression parent {cp:?} not found in fallback {fb_idx}",
))
})?;
let basis_bytes = basis.to_fulltext().into_owned();
let result_lines =
apply_plain_delta_to_basis(&key, &raw_bytes, noeol, &basis_bytes)?;
self.add_lines(key.clone(), parents, result_lines, false)?;
let mut ready = vec![key];
while let Some(k) = ready.pop() {
if let Some(entries) = buffered.remove(&k) {
let new_keys: Vec<KnitKey> =
entries.iter().map(|(ek, _, _, _)| ek.clone()).collect();
self.index.add_records(&entries, false, false)?;
ready.extend(new_keys);
}
}
}
}
if !buffered.is_empty() {
let all_entries: Vec<_> = buffered.into_values().flatten().collect();
self.index.add_records(&all_entries, false, true)?;
}
Ok(())
}
}
fn knit_key_from_vf(k: &crate::versionedfile::Key) -> KnitKey {
match k {
crate::versionedfile::Key::Fixed(v) | crate::versionedfile::Key::ContentAddressed(v) => {
v.clone()
}
}
}
pub(crate) fn merge_annotations<I, A, F>(
index: &I,
access: &A,
factory: &F,
content: &mut F::Content,
present_parents: &[KnitKey],
use_delta: bool,
) -> Result<Option<Vec<DeltaHunk<<F::Content as KnitContent>::DeltaLine>>>, KnitError>
where
I: KnitIndex,
A: KnitAccess<F = I::F>,
F: KnitFactory,
<F::Content as KnitContent>::DeltaLine: Clone,
{
if factory.annotated() {
for parent_key in present_parents {
let parent_content = get_content(index, access, factory, parent_key)?;
let parent_text: Vec<Vec<u8>> = parent_content.text();
let new_text: Vec<Vec<u8>> = content.text();
let mut matcher = patiencediff::SequenceMatcher::new(&parent_text, &new_text);
let opcodes = matcher.get_opcodes().to_vec();
let parent_annot_raw = parent_content.annotate_raw();
for op in &opcodes {
if let patiencediff::Opcode::Equal(a_start, a_end, b_start, b_end) = op {
let len = a_end - a_start;
let new_lines = content.annotate_mut();
for k in 0..len {
new_lines[b_start + k] = parent_annot_raw[a_start + k].clone();
}
let _ = b_end;
}
}
}
}
if use_delta {
let Some(first_parent) = present_parents.first() else {
return Ok(None);
};
let base = get_content(index, access, factory, first_parent)?;
let delta = compute_line_delta(&base, content);
Ok(Some(delta))
} else {
Ok(None)
}
}
fn compute_line_delta<C: KnitContent>(base: &C, new: &C) -> Vec<DeltaHunk<C::DeltaLine>>
where
C::DeltaLine: Clone,
{
let old_text = base.text();
let new_text = new.text();
let mut matcher = patiencediff::SequenceMatcher::new(&old_text, &new_text);
let opcodes = matcher.get_opcodes().to_vec();
let new_annot_raw = new.annotate_raw();
let mut hunks: Vec<DeltaHunk<C::DeltaLine>> = Vec::new();
for op in &opcodes {
if matches!(op, patiencediff::Opcode::Equal(..)) {
continue;
}
let hunk_new_lines: Vec<C::DeltaLine> = new_annot_raw[op.b_start()..op.b_end()]
.iter()
.map(C::delta_line_from_annotated)
.collect();
hunks.push(DeltaHunk {
start: op.a_start(),
end: op.a_end(),
count: op.b_end() - op.b_start(),
lines: hunk_new_lines,
});
}
hunks
}
pub type LineAnnotation = Vec<KnitKey>;
pub struct KnitAnnotator<I, A, F>
where
I: KnitIndex,
A: KnitAccess<F = I::F>,
F: KnitFactory,
{
index: I,
access: A,
factory: F,
parent_map: std::collections::HashMap<KnitKey, Vec<KnitKey>>,
text_cache: std::collections::HashMap<KnitKey, Vec<Vec<u8>>>,
num_needed_children: std::collections::HashMap<KnitKey, usize>,
annotations_cache: std::collections::HashMap<KnitKey, Vec<LineAnnotation>>,
all_build_details: std::collections::HashMap<KnitKey, KnitRecordDetails<I::F>>,
num_compression_children: std::collections::HashMap<KnitKey, usize>,
content_objects: std::collections::HashMap<KnitKey, F::Content>,
pending_deltas: std::collections::HashMap<
KnitKey,
Vec<(KnitKey, Vec<KnitKey>, Vec<u8>, KnitRecordDetails<I::F>)>,
>,
pending_annotation: std::collections::HashMap<KnitKey, Vec<(KnitKey, Vec<KnitKey>)>>,
matching_blocks: std::collections::HashMap<(KnitKey, KnitKey), Vec<(usize, usize, usize)>>,
}
impl<I, A, F> KnitAnnotator<I, A, F>
where
I: KnitIndex,
A: KnitAccess<F = I::F>,
F: KnitFactory,
F::Content: Clone,
{
pub fn new(index: I, access: A, factory: F) -> Self {
Self {
index,
access,
factory,
parent_map: Default::default(),
text_cache: Default::default(),
num_needed_children: Default::default(),
annotations_cache: Default::default(),
all_build_details: Default::default(),
num_compression_children: Default::default(),
content_objects: Default::default(),
pending_deltas: Default::default(),
pending_annotation: Default::default(),
matching_blocks: Default::default(),
}
}
pub fn access(&self) -> &A {
&self.access
}
pub fn seed_text(&mut self, key: KnitKey, parents: Vec<KnitKey>, lines: Vec<Vec<u8>>) {
self.parent_map.insert(key.clone(), parents);
self.text_cache.insert(key, lines);
}
fn get_build_graph(
&mut self,
key: &KnitKey,
) -> Result<(Vec<(KnitKey, KnitIndexMemo<I::F>)>, Vec<KnitKey>), KnitError> {
let mut pending: std::collections::HashSet<KnitKey> =
std::iter::once(key.clone()).collect();
let mut records: Vec<(KnitKey, KnitIndexMemo<I::F>)> = Vec::new();
let mut ann_keys: Vec<KnitKey> = Vec::new();
*self.num_needed_children.entry(key.clone()).or_insert(0) += 1;
while !pending.is_empty() {
let this_iteration: Vec<KnitKey> = pending.drain().collect();
let build_details = self.index.get_build_details(&this_iteration)?;
self.all_build_details.extend(build_details.clone());
pending = std::collections::HashSet::new();
for k in &this_iteration {
if let Some(details) = build_details.get(k) {
let parents = details.parents.clone();
self.parent_map.insert(k.clone(), parents.clone());
self.num_needed_children.entry(k.clone()).or_insert(0);
records.push((k.clone(), details.index_memo.clone()));
for pk in &parents {
if !self.all_build_details.contains_key(pk) {
pending.insert(pk.clone());
}
*self.num_needed_children.entry(pk.clone()).or_insert(0) += 1;
}
if let Some(ref cp) = details.compression_parent {
*self.num_compression_children.entry(cp.clone()).or_insert(0) += 1;
}
} else if self.parent_map.contains_key(k) && self.text_cache.contains_key(k) {
ann_keys.push(k.clone());
let parents = self.parent_map[k].clone();
for pk in &parents {
*self.num_needed_children.entry(pk.clone()).or_insert(0) += 1;
if !self.all_build_details.contains_key(pk) {
pending.insert(pk.clone());
}
}
} else {
return Err(KnitError::RevisionNotPresent(k.clone()));
}
}
}
records.reverse();
Ok((records, ann_keys))
}
fn parse_raw_record(
&self,
key: &KnitKey,
raw: &[u8],
method: KnitMethod,
noeol: bool,
base: Option<F::Content>,
) -> Result<F::Content, KnitError> {
let decompressed = decode_record_gz(raw)?;
let (_, body_lines) = parse_record_body_unchecked(&decompressed)?;
self.factory.parse_record(
key.last().map(|s| s.as_slice()).unwrap_or(&[]),
&body_lines,
method,
noeol,
base.as_ref(),
)
}
fn expand_record(
&mut self,
key: KnitKey,
parent_keys: Vec<KnitKey>,
compression_parent: Option<KnitKey>,
raw: Vec<u8>,
method: KnitMethod,
noeol: bool,
) -> Result<Option<Vec<Vec<u8>>>, KnitError> {
let content = if let Some(ref cp) = compression_parent {
if !self.content_objects.contains_key(cp) {
self.pending_deltas.entry(cp.clone()).or_default().push((
key,
parent_keys,
raw,
KnitRecordDetails {
method,
noeol,
index_memo: KnitIndexMemo {
file_ref: I::F::placeholder(),
offset: 0,
length: 0,
},
compression_parent: compression_parent.clone(),
parents: vec![],
},
));
return Ok(None);
}
let num = self.num_compression_children[cp];
let base_content = if num <= 1 {
self.num_compression_children.remove(cp);
self.content_objects.remove(cp).unwrap()
} else {
*self.num_compression_children.get_mut(cp).unwrap() -= 1;
self.content_objects[cp].clone()
};
let content = self.parse_raw_record(&key, &raw, method, noeol, Some(base_content))?;
if method == KnitMethod::LineDelta {
if let Some(parent_lines) = self.text_cache.get(cp).cloned() {
let lines = content.text();
let p_refs: Vec<&[u8]> = parent_lines.iter().map(|l| l.as_slice()).collect();
let l_refs: Vec<&[u8]> = lines.iter().map(|l| l.as_slice()).collect();
if let Ok(decompressed) = decode_record_gz(&raw) {
if let Ok((_, body_lines)) = parse_record_body_unchecked(&decompressed) {
if let Ok(hunks) = parse_line_delta_raw(
&body_lines.iter().copied().collect::<Vec<_>>(),
) {
let raw_hunks: Vec<(usize, usize, usize)> = hunks
.iter()
.map(|h| (h.start, h.end, h.lines.len()))
.collect();
let blocks = get_line_delta_blocks(&raw_hunks, &p_refs, &l_refs);
self.matching_blocks
.insert((key.clone(), cp.clone()), blocks);
}
}
}
}
}
content
} else {
self.parse_raw_record(&key, &raw, method, noeol, None)?
};
if self
.num_compression_children
.get(&key)
.copied()
.unwrap_or(0)
> 0
{
self.content_objects.insert(key.clone(), content.clone());
}
let lines = content.text();
self.text_cache.insert(key.clone(), lines.clone());
Ok(Some(lines))
}
fn check_ready_for_annotations(&mut self, key: &KnitKey, parent_keys: &[KnitKey]) -> bool {
for pk in parent_keys {
if !self.annotations_cache.contains_key(pk) {
self.pending_annotation
.entry(pk.clone())
.or_default()
.push((key.clone(), parent_keys.to_vec()));
return false;
}
}
true
}
fn process_pending(&mut self, key: &KnitKey) -> Result<Vec<KnitKey>, KnitError> {
let mut to_return: Vec<KnitKey> = Vec::new();
if let Some(children) = self.pending_deltas.remove(key) {
for (child_key, parent_keys, raw, details) in children {
self.expand_record(
child_key.clone(),
parent_keys.clone(),
Some(key.clone()),
raw,
details.method,
details.noeol,
)?;
if self.check_ready_for_annotations(&child_key, &parent_keys) {
to_return.push(child_key);
}
}
}
if let Some(children) = self.pending_annotation.remove(key) {
for (child_key, parent_keys) in children {
if self.check_ready_for_annotations(&child_key, &parent_keys) {
to_return.push(child_key);
}
}
}
Ok(to_return)
}
fn extract_and_annotate(
&mut self,
records: Vec<(KnitKey, KnitIndexMemo<I::F>)>,
) -> Result<(), KnitError> {
let memos: Vec<KnitIndexMemo<I::F>> = records.iter().map(|(_, m)| m.clone()).collect();
let raw_bytes = self.access.get_raw_records(&memos)?;
for ((key, _memo), raw) in records.into_iter().zip(raw_bytes.into_iter()) {
let details = self.all_build_details[&key].clone();
let lines = self.expand_record(
key.clone(),
details.parents.clone(),
details.compression_parent.clone(),
raw,
details.method,
details.noeol,
)?;
let Some(lines) = lines else { continue };
if self.check_ready_for_annotations(&key, &details.parents) {
self.annotate_one(&key, &lines);
}
let mut to_process = self.process_pending(&key)?;
while !to_process.is_empty() {
let this_batch = std::mem::take(&mut to_process);
for k in this_batch {
let lines = self.text_cache[&k].clone();
self.annotate_one(&k, &lines);
to_process.extend(self.process_pending(&k)?);
}
}
}
Ok(())
}
fn get_parent_annotations_and_matches(
&mut self,
key: &KnitKey,
text: &[Vec<u8>],
parent_key: &KnitKey,
) -> (Vec<LineAnnotation>, Vec<(usize, usize, usize)>) {
if let Some(blocks) = self
.matching_blocks
.remove(&(key.clone(), parent_key.clone()))
{
let parent_annotations = self.annotations_cache[parent_key].clone();
return (parent_annotations, blocks);
}
let parent_lines = self.text_cache[parent_key].clone();
let parent_annotations = self.annotations_cache[parent_key].clone();
let p_refs: Vec<&[u8]> = parent_lines.iter().map(|l| l.as_slice()).collect();
let t_refs: Vec<&[u8]> = text.iter().map(|l| l.as_slice()).collect();
let blocks = patiencediff::SequenceMatcher::new(&p_refs, &t_refs)
.get_matching_blocks()
.to_vec();
(parent_annotations, blocks)
}
fn record_annotation(
&mut self,
key: &KnitKey,
parent_keys: &[KnitKey],
annotations: Vec<LineAnnotation>,
) {
self.annotations_cache.insert(key.clone(), annotations);
for pk in parent_keys {
if let Some(n) = self.num_needed_children.get_mut(pk) {
*n -= 1;
if *n == 0 {
self.text_cache.remove(pk);
self.annotations_cache.remove(pk);
}
}
}
}
fn annotate_one(&mut self, key: &KnitKey, text: &[Vec<u8>]) {
let this_annotation: LineAnnotation = vec![key.clone()];
let mut annotations: Vec<LineAnnotation> = vec![this_annotation.clone(); text.len()];
let parent_keys = self.parent_map[key].clone();
if let Some(first_parent) = parent_keys.first() {
let (parent_annotations, blocks) =
self.get_parent_annotations_and_matches(key, text, first_parent);
for (parent_idx, lines_idx, match_len) in &blocks {
if *match_len == 0 {
continue;
}
annotations[*lines_idx..*lines_idx + *match_len]
.clone_from_slice(&parent_annotations[*parent_idx..*parent_idx + *match_len]);
}
for other_parent in parent_keys.iter().skip(1) {
let (parent_annotations, blocks) =
self.get_parent_annotations_and_matches(key, text, other_parent);
for (parent_idx, lines_idx, match_len) in &blocks {
if *match_len == 0 {
continue;
}
let ann_sub = annotations[*lines_idx..*lines_idx + *match_len].to_vec();
let par_sub = &parent_annotations[*parent_idx..*parent_idx + *match_len];
if ann_sub == par_sub {
continue;
}
for idx in 0..*match_len {
let ann = &ann_sub[idx];
let par_ann = &par_sub[idx];
let ann_idx = *lines_idx + idx;
if ann == par_ann || *ann == this_annotation {
annotations[ann_idx] = par_ann.clone();
} else {
let mut new_ann: std::collections::BTreeSet<KnitKey> =
ann.iter().cloned().collect();
new_ann.extend(par_ann.iter().cloned());
annotations[ann_idx] = new_ann.into_iter().collect();
}
}
}
}
}
self.record_annotation(key, &parent_keys.clone(), annotations);
}
pub fn add_special_text(
&mut self,
key: KnitKey,
parent_keys: Vec<KnitKey>,
lines: Vec<Vec<u8>>,
) {
self.parent_map.insert(key.clone(), parent_keys);
self.text_cache.insert(key, lines);
}
pub fn annotate(
&mut self,
key: &KnitKey,
) -> Result<(Vec<LineAnnotation>, Vec<Vec<u8>>), KnitError> {
let (records, ann_keys) = self.get_build_graph(key)?;
self.extract_and_annotate(records)?;
for ann_key in ann_keys {
let text = self.text_cache[&ann_key].clone();
self.annotate_one(&ann_key, &text);
}
let annotations = self
.annotations_cache
.get(key)
.cloned()
.ok_or_else(|| KnitError::RevisionNotPresent(key.clone()))?;
let lines = self.text_cache.get(key).cloned().unwrap_or_default();
Ok((annotations, lines))
}
pub fn annotate_seeded(
&mut self,
key: &KnitKey,
topological_order: &[KnitKey],
) -> Result<(Vec<LineAnnotation>, Vec<Vec<u8>>), KnitError> {
for k in topological_order {
let text = self
.text_cache
.get(k)
.cloned()
.ok_or_else(|| KnitError::Corrupt(format!("text not seeded: {:?}", k)))?;
self.annotate_one(k, &text);
}
let annotations = self
.annotations_cache
.get(key)
.cloned()
.ok_or_else(|| KnitError::RevisionNotPresent(key.clone()))?;
let lines = self.text_cache.get(key).cloned().unwrap_or_default();
Ok((annotations, lines))
}
pub fn annotate_flat_seeded(
&mut self,
key: &KnitKey,
topological_order: &[KnitKey],
) -> Result<Vec<(KnitKey, Vec<u8>)>, KnitError> {
let (annotations, lines) = self.annotate_seeded(key, topological_order)?;
self.heads_to_flat(annotations, lines)
}
fn heads_to_flat(
&self,
annotations: Vec<LineAnnotation>,
lines: Vec<Vec<u8>>,
) -> Result<Vec<(KnitKey, Vec<u8>)>, KnitError> {
let mut kg = vcs_graph::KnownGraph::new(
self.parent_map.iter().map(|(k, v)| (k.clone(), v.clone())),
false,
);
let out = annotations
.into_iter()
.zip(lines)
.map(|(annotation, line)| {
let head = if annotation.len() == 1 {
annotation.into_iter().next().unwrap()
} else {
let the_heads = kg.heads(annotation.iter().cloned());
if the_heads.len() == 1 {
the_heads.into_iter().next().unwrap()
} else {
let mut sorted: Vec<KnitKey> = the_heads.into_iter().collect();
sorted.sort();
sorted.into_iter().next().unwrap()
}
};
(head, line)
})
.collect();
Ok(out)
}
pub fn annotate_flat(&mut self, key: &KnitKey) -> Result<Vec<(KnitKey, Vec<u8>)>, KnitError> {
let (annotations, lines) = self.annotate(key)?;
self.heads_to_flat(annotations, lines)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::transport::Transport;
fn refs<'a>(v: &'a [Vec<u8>]) -> Vec<&'a [u8]> {
v.iter().map(|l| l.as_slice()).collect()
}
#[test]
fn pure_rust_full_record_read_pipeline() {
let pairs = vec![
(b"r1".to_vec(), b"hello\n".to_vec()),
(b"r1".to_vec(), b"world\n".to_vec()),
];
let body = lower_fulltext(&pairs);
let (_, chunks) = record_to_data(b"v", b"DD", body.len(), &body, true).unwrap();
let raw: Vec<u8> = chunks.into_iter().flatten().collect();
let decompressed = decode_record_gz(&raw).unwrap();
let (header, body_lines) = parse_record_body_unchecked(&decompressed).unwrap();
let factory = KnitAnnotateFactory;
let content = factory
.parse_record(
header.version_id,
&body_lines,
KnitMethod::Fulltext,
false,
None,
)
.unwrap();
assert_eq!(content.lines, pairs);
assert_eq!(
content.text(),
vec![b"hello\n".to_vec(), b"world\n".to_vec()]
);
}
#[test]
fn pure_rust_delta_chain_apply_pipeline() {
let parent_pairs = vec![
(b"r1".to_vec(), b"a\n".to_vec()),
(b"r1".to_vec(), b"b\n".to_vec()),
];
let parent_body = lower_fulltext(&parent_pairs);
let (_, p_chunks) =
record_to_data(b"r1", b"D1", parent_body.len(), &parent_body, true).unwrap();
let parent_raw: Vec<u8> = p_chunks.into_iter().flatten().collect();
let delta = vec![DeltaHunk {
start: 1,
end: 2,
count: 1,
lines: vec![(b"r2".to_vec(), b"B\n".to_vec())],
}];
let delta_body = lower_line_delta_annotated(&delta);
let (_, d_chunks) =
record_to_data(b"r2", b"D2", delta_body.len(), &delta_body, true).unwrap();
let delta_raw: Vec<u8> = d_chunks.into_iter().flatten().collect();
let factory = KnitAnnotateFactory;
let parent_decomp = decode_record_gz(&parent_raw).unwrap();
let (parent_header, parent_lines) = parse_record_body_unchecked(&parent_decomp).unwrap();
let parent_content = factory
.parse_record(
parent_header.version_id,
&parent_lines,
KnitMethod::Fulltext,
false,
None,
)
.unwrap();
let delta_decomp = decode_record_gz(&delta_raw).unwrap();
let (delta_header, delta_lines) = parse_record_body_unchecked(&delta_decomp).unwrap();
let target_content = factory
.parse_record(
delta_header.version_id,
&delta_lines,
KnitMethod::LineDelta,
false,
Some(&parent_content),
)
.unwrap();
assert_eq!(
target_content.text(),
vec![b"a\n".to_vec(), b"B\n".to_vec()]
);
}
#[derive(Default)]
struct MockKnit {
records: std::collections::HashMap<KnitKey, KnitRecordDetails>,
bytes: std::collections::HashMap<KnitIndexMemo, Vec<u8>>,
}
impl MockKnit {
fn add_record(&mut self, key: KnitKey, details: KnitRecordDetails, raw: Vec<u8>) {
self.bytes.insert(details.index_memo.clone(), raw);
self.records.insert(key, details);
}
}
impl KnitIndex for MockKnit {
type F = String;
fn get_build_details(
&self,
keys: &[KnitKey],
) -> Result<std::collections::HashMap<KnitKey, KnitRecordDetails>, KnitError> {
let mut out = std::collections::HashMap::new();
for k in keys {
if let Some(d) = self.records.get(k) {
out.insert(k.clone(), d.clone());
}
}
Ok(out)
}
fn keys(&self) -> Result<Vec<KnitKey>, KnitError> {
Ok(self.records.keys().cloned().collect())
}
fn get_parent_map(
&self,
keys: &[KnitKey],
) -> Result<std::collections::HashMap<KnitKey, Vec<KnitKey>>, KnitError> {
Ok(keys
.iter()
.filter_map(|k| self.records.get(k).map(|d| (k.clone(), d.parents.clone())))
.collect())
}
fn get_method(&self, key: &KnitKey) -> Result<KnitMethod, KnitError> {
self.records
.get(key)
.map(|d| d.method)
.ok_or_else(|| KnitError::Corrupt(format!("key not found: {:?}", key)))
}
fn get_total_build_size(
&self,
keys: &[KnitKey],
positions: &std::collections::HashMap<KnitKey, KnitRecordDetails>,
) -> usize {
keys.iter()
.filter_map(|k| positions.get(k))
.map(|d| d.index_memo.length)
.sum()
}
fn sort_keys_by_io(
&self,
keys: &mut [KnitKey],
positions: &std::collections::HashMap<KnitKey, KnitRecordDetails>,
) {
keys.sort_by(|a, b| {
let a_key = positions
.get(a)
.map(|d| (&d.index_memo.file_ref, d.index_memo.offset));
let b_key = positions
.get(b)
.map(|d| (&d.index_memo.file_ref, d.index_memo.offset));
a_key.cmp(&b_key)
});
}
fn has_graph(&self) -> bool {
true
}
fn contains(&self, key: &KnitKey) -> Result<bool, KnitError> {
Ok(self.records.contains_key(key))
}
fn get_missing_compression_parents(&self) -> Result<Vec<KnitKey>, KnitError> {
Ok(vec![])
}
fn check_write_ok(&self) -> Result<(), KnitError> {
Ok(())
}
fn add_records(
&self,
_records: &[(KnitKey, Vec<KnitMethod>, KnitIndexMemo, Vec<KnitKey>)],
_random_id: bool,
_missing_compression_parents: bool,
) -> Result<(), KnitError> {
Ok(())
}
}
impl KnitAccess for MockKnit {
type F = String;
fn get_raw_record(&self, memo: &KnitIndexMemo) -> Result<Vec<u8>, KnitError> {
self.bytes
.get(memo)
.cloned()
.ok_or_else(|| KnitError::BadIndexValue(memo.file_ref.as_bytes().to_vec()))
}
fn get_raw_records(&self, memos: &[KnitIndexMemo]) -> Result<Vec<Vec<u8>>, KnitError> {
memos.iter().map(|m| self.get_raw_record(m)).collect()
}
fn add_raw_record(
&self,
_key: &KnitKey,
_size: usize,
_data: Vec<Vec<u8>>,
) -> Result<KnitIndexMemo, KnitError> {
unimplemented!("MockKnit::add_raw_record")
}
fn flush(&self) -> Result<(), KnitError> {
Ok(())
}
fn reload_or_raise(&self, err: KnitError) -> Result<(), KnitError> {
Err(err)
}
}
fn build_fulltext_record(
version_id: &[u8],
annotated: &[AnnotatedLine],
) -> (Vec<u8>, KnitIndexMemo) {
let body = lower_fulltext(annotated);
let (_, chunks) = record_to_data(version_id, b"DIGEST", body.len(), &body, true).unwrap();
let raw: Vec<u8> = chunks.into_iter().flatten().collect();
let memo = KnitIndexMemo {
file_ref: format!("rec/{}", String::from_utf8_lossy(version_id)),
offset: 0,
length: raw.len(),
};
(raw, memo)
}
fn build_delta_record(
version_id: &[u8],
delta: &[DeltaHunk<AnnotatedLine>],
) -> (Vec<u8>, KnitIndexMemo) {
let body = lower_line_delta_annotated(delta);
let (_, chunks) = record_to_data(version_id, b"DIGEST", body.len(), &body, true).unwrap();
let raw: Vec<u8> = chunks.into_iter().flatten().collect();
let memo = KnitIndexMemo {
file_ref: format!("rec/{}", String::from_utf8_lossy(version_id)),
offset: 0,
length: raw.len(),
};
(raw, memo)
}
#[test]
fn get_text_returns_fulltext_record_via_traits() {
let mut knit = MockKnit::default();
let key: KnitKey = vec![b"file".to_vec(), b"v1".to_vec()];
let pairs = vec![
(b"v1".to_vec(), b"alpha\n".to_vec()),
(b"v1".to_vec(), b"beta\n".to_vec()),
];
let (raw, memo) = build_fulltext_record(b"v1", &pairs);
knit.add_record(
key.clone(),
KnitRecordDetails {
method: KnitMethod::Fulltext,
noeol: false,
index_memo: memo,
compression_parent: None,
parents: vec![],
},
raw,
);
let factory = KnitAnnotateFactory;
let text = get_text(&knit, &knit, &factory, &key).unwrap();
assert_eq!(text, b"alpha\nbeta\n".to_vec());
}
#[test]
fn get_text_walks_two_step_delta_chain_via_traits() {
let mut knit = MockKnit::default();
let parent_key: KnitKey = vec![b"file".to_vec(), b"v1".to_vec()];
let child_key: KnitKey = vec![b"file".to_vec(), b"v2".to_vec()];
let parent_pairs = vec![
(b"v1".to_vec(), b"a\n".to_vec()),
(b"v1".to_vec(), b"b\n".to_vec()),
];
let (parent_raw, parent_memo) = build_fulltext_record(b"v1", &parent_pairs);
knit.add_record(
parent_key.clone(),
KnitRecordDetails {
method: KnitMethod::Fulltext,
noeol: false,
index_memo: parent_memo,
compression_parent: None,
parents: vec![],
},
parent_raw,
);
let delta = vec![DeltaHunk {
start: 1,
end: 2,
count: 1,
lines: vec![(b"v2".to_vec(), b"B\n".to_vec())],
}];
let (delta_raw, delta_memo) = build_delta_record(b"v2", &delta);
knit.add_record(
child_key.clone(),
KnitRecordDetails {
method: KnitMethod::LineDelta,
noeol: false,
index_memo: delta_memo,
compression_parent: Some(parent_key.clone()),
parents: vec![parent_key.clone()],
},
delta_raw,
);
let factory = KnitAnnotateFactory;
let text = get_text(&knit, &knit, &factory, &child_key).unwrap();
assert_eq!(text, b"a\nB\n".to_vec());
}
#[test]
fn get_sha1s_returns_digests_without_parsing_bodies() {
let mut knit = MockKnit::default();
let key_a: KnitKey = vec![b"file".to_vec(), b"a".to_vec()];
let key_b: KnitKey = vec![b"file".to_vec(), b"b".to_vec()];
let pairs_a = vec![(b"a".to_vec(), b"hello\n".to_vec())];
let pairs_b = vec![(b"b".to_vec(), b"world\n".to_vec())];
let (raw_a, memo_a) = build_fulltext_record(b"a", &pairs_a);
let (raw_b, memo_b) = build_fulltext_record(b"b", &pairs_b);
knit.add_record(
key_a.clone(),
KnitRecordDetails {
method: KnitMethod::Fulltext,
noeol: false,
index_memo: memo_a,
compression_parent: None,
parents: vec![],
},
raw_a,
);
knit.add_record(
key_b.clone(),
KnitRecordDetails {
method: KnitMethod::Fulltext,
noeol: false,
index_memo: memo_b,
compression_parent: None,
parents: vec![],
},
raw_b,
);
let result = get_sha1s(&knit, &knit, &[key_a.clone(), key_b.clone()]).unwrap();
assert_eq!(result.len(), 2);
assert_eq!(result[&key_a], b"DIGEST");
assert_eq!(result[&key_b], b"DIGEST");
}
#[test]
fn get_sha1s_skips_missing_keys() {
let knit = MockKnit::default();
let key: KnitKey = vec![b"missing".to_vec()];
let result = get_sha1s(&knit, &knit, &[key]).unwrap();
assert!(result.is_empty());
}
#[test]
fn get_text_propagates_missing_key() {
let knit = MockKnit::default();
let key: KnitKey = vec![b"missing".to_vec()];
let factory = KnitAnnotateFactory;
assert!(get_text(&knit, &knit, &factory, &key).is_err());
}
#[test]
fn annotated_content_text_strips_origins() {
let content = AnnotatedKnitContent::new(vec![
(b"r1".to_vec(), b"first\n".to_vec()),
(b"r2".to_vec(), b"second\n".to_vec()),
]);
assert_eq!(
content.text(),
vec![b"first\n".to_vec(), b"second\n".to_vec()]
);
}
#[test]
fn annotated_content_text_honors_strip_eol() {
let mut content = AnnotatedKnitContent::new(vec![
(b"r1".to_vec(), b"first\n".to_vec()),
(b"r2".to_vec(), b"second\n".to_vec()),
]);
content.set_should_strip_eol(true);
assert_eq!(
content.text(),
vec![b"first\n".to_vec(), b"second".to_vec()]
);
let annotated = content.annotate();
assert_eq!(annotated.last().unwrap().1, b"second");
}
#[test]
fn annotated_content_apply_delta_splices_lines() {
let mut content = AnnotatedKnitContent::new(vec![
(b"r1".to_vec(), b"a\n".to_vec()),
(b"r1".to_vec(), b"b\n".to_vec()),
(b"r1".to_vec(), b"c\n".to_vec()),
(b"r1".to_vec(), b"d\n".to_vec()),
]);
let delta = vec![DeltaHunk {
start: 1,
end: 3,
count: 2,
lines: vec![
(b"r2".to_vec(), b"B\n".to_vec()),
(b"r2".to_vec(), b"C\n".to_vec()),
],
}];
content.apply_delta(&delta, b"r2");
let texts = content.text();
assert_eq!(
texts,
vec![
b"a\n".to_vec(),
b"B\n".to_vec(),
b"C\n".to_vec(),
b"d\n".to_vec(),
]
);
}
#[test]
fn plain_content_apply_delta_updates_version_id() {
let mut content =
PlainKnitContent::new(vec![b"a\n".to_vec(), b"b\n".to_vec()], b"r1".to_vec());
let delta = vec![DeltaHunk {
start: 0,
end: 0,
count: 1,
lines: vec![b"first\n".to_vec()],
}];
content.apply_delta(&delta, b"r2");
assert_eq!(content.version_id, b"r2");
assert_eq!(
content.text(),
vec![b"first\n".to_vec(), b"a\n".to_vec(), b"b\n".to_vec()]
);
}
#[test]
fn plain_content_annotate_uses_version_id() {
let content =
PlainKnitContent::new(vec![b"a\n".to_vec(), b"b\n".to_vec()], b"rev".to_vec());
let annotated = content.annotate();
assert_eq!(annotated.len(), 2);
assert_eq!(annotated[0].0, b"rev");
assert_eq!(annotated[0].1, b"a\n");
assert_eq!(annotated[1].0, b"rev");
}
#[test]
fn factory_parse_fulltext_round_trips_via_annotated_content() {
let pairs = vec![
(b"r1".to_vec(), b"alpha\n".to_vec()),
(b"r2".to_vec(), b"beta\n".to_vec()),
];
let body = lower_fulltext(&pairs);
let body_refs: Vec<&[u8]> = body.iter().map(|l| l.as_slice()).collect();
let factory = KnitAnnotateFactory;
let content = factory
.parse_record(b"v", &body_refs, KnitMethod::Fulltext, false, None)
.unwrap();
assert_eq!(content.lines, pairs);
assert!(!content.should_strip_eol());
}
#[test]
fn factory_parse_record_applies_delta_to_base() {
let base = AnnotatedKnitContent::new(vec![
(b"r1".to_vec(), b"a\n".to_vec()),
(b"r1".to_vec(), b"b\n".to_vec()),
]);
let body = vec![b"1,2,1\n".to_vec(), b"r2 B\n".to_vec()];
let body_refs: Vec<&[u8]> = body.iter().map(|l| l.as_slice()).collect();
let factory = KnitAnnotateFactory;
let content = factory
.parse_record(b"r2", &body_refs, KnitMethod::LineDelta, false, Some(&base))
.unwrap();
assert_eq!(content.text(), vec![b"a\n".to_vec(), b"B\n".to_vec()]);
}
#[test]
fn plain_factory_parses_line_delta_record() {
let base = PlainKnitContent::new(vec![b"a\n".to_vec(), b"b\n".to_vec()], b"r1".to_vec());
let body = vec![b"1,2,1\n".to_vec(), b"B\n".to_vec()];
let body_refs: Vec<&[u8]> = body.iter().map(|l| l.as_slice()).collect();
let factory = KnitPlainFactory;
let content = factory
.parse_record(b"r2", &body_refs, KnitMethod::LineDelta, false, Some(&base))
.unwrap();
assert_eq!(content.version_id, b"r2");
assert_eq!(content.text(), vec![b"a\n".to_vec(), b"B\n".to_vec()]);
}
#[test]
fn factory_line_delta_without_base_is_an_error() {
let factory = KnitAnnotateFactory;
let err = factory
.parse_record(b"v", &[], KnitMethod::LineDelta, false, None)
.unwrap_err();
assert!(matches!(err, KnitError::BadIndexValue(_)));
}
#[test]
fn plain_factory_parses_fulltext_into_plain_content() {
let factory = KnitPlainFactory;
let body = vec![b"alpha\n".to_vec(), b"beta\n".to_vec()];
let body_refs: Vec<&[u8]> = body.iter().map(|l| l.as_slice()).collect();
let content = factory
.parse_record(b"v", &body_refs, KnitMethod::Fulltext, true, None)
.unwrap();
assert_eq!(content.version_id, b"v");
assert!(content.should_strip_eol());
assert_eq!(content.text(), vec![b"alpha\n".to_vec(), b"beta".to_vec()]);
}
#[test]
fn fulltext_round_trip() {
let content: Vec<AnnotatedLine> = vec![
(b"rev1".to_vec(), b"first line\n".to_vec()),
(b"rev2".to_vec(), b"second line\n".to_vec()),
];
let bytes = lower_fulltext(&content);
assert_eq!(
bytes,
vec![
b"rev1 first line\n".to_vec(),
b"rev2 second line\n".to_vec(),
]
);
let parsed = parse_fulltext(&refs(&bytes)).unwrap();
assert_eq!(parsed, content);
}
#[test]
fn fulltext_rejects_missing_origin() {
let lines = vec![b"no-space-here".as_slice()];
assert!(matches!(
parse_fulltext(&lines),
Err(KnitError::MissingOrigin(_))
));
}
#[test]
fn delta_annotated_round_trip() {
let delta = vec![
DeltaHunk {
start: 0,
end: 1,
count: 2,
lines: vec![
(b"r1".to_vec(), b"alpha\n".to_vec()),
(b"r1".to_vec(), b"beta\n".to_vec()),
],
},
DeltaHunk {
start: 5,
end: 5,
count: 1,
lines: vec![(b"r2".to_vec(), b"gamma\n".to_vec())],
},
];
let bytes = lower_line_delta_annotated(&delta);
assert_eq!(
bytes,
vec![
b"0,1,2\n".to_vec(),
b"r1 alpha\n".to_vec(),
b"r1 beta\n".to_vec(),
b"5,5,1\n".to_vec(),
b"r2 gamma\n".to_vec(),
]
);
let parsed = parse_line_delta_annotated(&refs(&bytes)).unwrap();
assert_eq!(parsed, delta);
}
#[test]
fn delta_raw_round_trip() {
let delta = vec![
DeltaHunk {
start: 0,
end: 0,
count: 2,
lines: vec![b"one\n".to_vec(), b"two\n".to_vec()],
},
DeltaHunk {
start: 4,
end: 5,
count: 1,
lines: vec![b"three\n".to_vec()],
},
];
let bytes = lower_line_delta_raw(&delta);
assert_eq!(
bytes,
vec![
b"0,0,2\n".to_vec(),
b"one\n".to_vec(),
b"two\n".to_vec(),
b"4,5,1\n".to_vec(),
b"three\n".to_vec(),
]
);
let parsed = parse_line_delta_raw(&refs(&bytes)).unwrap();
assert_eq!(parsed, delta);
}
#[test]
fn delta_plain_strips_origin() {
let bytes: Vec<Vec<u8>> = vec![
b"0,1,2\n".to_vec(),
b"r1 alpha\n".to_vec(),
b"r1 beta\n".to_vec(),
];
let parsed = parse_line_delta_plain(&refs(&bytes)).unwrap();
assert_eq!(parsed.len(), 1);
assert_eq!(parsed[0].start, 0);
assert_eq!(parsed[0].end, 1);
assert_eq!(parsed[0].count, 2);
assert_eq!(
parsed[0].lines,
vec![b"alpha\n".to_vec(), b"beta\n".to_vec()]
);
}
#[test]
fn delta_rejects_bad_header() {
let bytes = vec![b"not,a,number\n".as_slice()];
assert!(matches!(
parse_line_delta_annotated(&bytes),
Err(KnitError::BadDeltaHeader(_))
));
}
#[test]
fn delta_rejects_truncated() {
let bytes = vec![b"0,0,3\n".as_slice(), b"r1 one\n".as_slice()];
assert_eq!(
parse_line_delta_annotated(&bytes),
Err(KnitError::TruncatedDelta)
);
}
fn lines_with_nl(text: &[u8]) -> Vec<Vec<u8>> {
text.split(|&b| b == b'\n')
.filter(|l| !l.is_empty())
.map(|l| {
let mut v = l.to_vec();
v.push(b'\n');
v
})
.collect()
}
#[test]
fn line_delta_blocks_equal_inputs() {
let source = lines_with_nl(b"a\nb\nc\n");
let target = source.clone();
let delta: Vec<(usize, usize, usize)> = vec![];
let blocks = get_line_delta_blocks(&delta, &refs(&source), &refs(&target));
assert_eq!(blocks, vec![(0, 0, 3), (3, 3, 0)]);
}
#[test]
fn line_delta_blocks_noeol_shrinks_trailing_run() {
let source: Vec<Vec<u8>> = vec![b"a\n".to_vec(), b"b\n".to_vec(), b"c".to_vec()];
let target: Vec<Vec<u8>> = vec![
b"a\n".to_vec(),
b"b\n".to_vec(),
b"c\n".to_vec(),
b"d\n".to_vec(),
];
let delta = vec![(2usize, 3usize, 2usize)];
let blocks = get_line_delta_blocks(&delta, &refs(&source), &refs(&target));
assert_eq!(blocks, vec![(0, 0, 2), (3, 4, 0)]);
}
#[test]
fn line_delta_blocks_replace_middle_line() {
let source = lines_with_nl(b"a\nb\nc\n");
let target = lines_with_nl(b"a\nX\nc\n");
let delta = vec![(1usize, 2usize, 1usize)];
let blocks = get_line_delta_blocks(&delta, &refs(&source), &refs(&target));
assert_eq!(blocks, vec![(0, 0, 1), (2, 2, 1), (3, 3, 0)]);
}
#[test]
fn network_header_no_parents_no_eol() {
let bytes = b"knit-ft-gz\nfile-id\x00rev\nNone:\nNDATA";
let header = parse_network_record_header(bytes, 11).unwrap();
assert_eq!(header.key, vec![b"file-id".as_slice(), b"rev".as_slice()]);
assert!(header.parents.is_none());
assert!(header.noeol);
assert_eq!(header.raw_record, b"DATA");
}
#[test]
fn network_header_with_parents_and_eol() {
let bytes = b"knit-delta-gz\nf\x00r\nf\x00p1\tf\x00p2\nYBODY";
let header = parse_network_record_header(bytes, 14).unwrap();
let parents = header.parents.unwrap();
assert_eq!(
parents,
vec![
vec![b"f".as_slice(), b"p1".as_slice()],
vec![b"f".as_slice(), b"p2".as_slice()],
]
);
assert!(!header.noeol);
assert_eq!(header.raw_record, b"BODY");
}
#[test]
fn network_header_empty_parents_list_is_some_empty() {
let bytes = b"knit-ft-gz\nk\n\nNX";
let header = parse_network_record_header(bytes, 11).unwrap();
assert_eq!(header.parents.unwrap().len(), 0);
assert_eq!(header.raw_record, b"X");
}
#[test]
fn split_keys_by_prefix_preserves_first_seen_order() {
let keys: Vec<Vec<Vec<u8>>> = vec![
vec![b"file-a".to_vec(), b"rev-1".to_vec()],
vec![b"file-b".to_vec(), b"rev-1".to_vec()],
vec![b"file-a".to_vec(), b"rev-2".to_vec()],
vec![b"lone-rev".to_vec()], vec![b"file-b".to_vec(), b"rev-2".to_vec()],
];
let (buckets, order) = split_keys_by_prefix(&keys);
assert_eq!(
order,
vec![b"file-a".to_vec(), b"file-b".to_vec(), Vec::<u8>::new()]
);
assert_eq!(buckets.len(), 3);
assert_eq!(buckets[0].0, b"file-a".to_vec());
assert_eq!(buckets[0].1.len(), 2);
assert_eq!(buckets[0].1[0], keys[0].as_slice());
assert_eq!(buckets[0].1[1], keys[2].as_slice());
assert_eq!(buckets[2].0, Vec::<u8>::new());
assert_eq!(buckets[2].1, vec![keys[3].as_slice()]);
}
#[test]
fn split_keys_by_prefix_empty_input() {
let keys: Vec<Vec<Vec<u8>>> = vec![];
let (buckets, order) = split_keys_by_prefix(&keys);
assert!(buckets.is_empty());
assert!(order.is_empty());
}
#[test]
fn knit_delta_closure_wire_matches_python_layout() {
let key1: &[&[u8]] = &[b"file", b"rev1"];
let key2: &[&[u8]] = &[b"rev2"];
let emit_keys: &[&[&[u8]]] = &[key1, key2];
let parent_a: &[&[u8]] = &[b"file", b"p0"];
let rec2_parents: &[&[&[u8]]] = &[parent_a];
let next2: &[&[u8]] = &[b"file", b"rev1"];
let records = [
KnitDeltaClosureRecord {
key: key1,
parents: None,
method: b"line-delta",
noeol: true,
next: None,
record_bytes: b"BODY-1",
},
KnitDeltaClosureRecord {
key: key2,
parents: Some(rec2_parents),
method: b"fulltext",
noeol: false,
next: Some(next2),
record_bytes: b"BODY-2",
},
];
let out = build_knit_delta_closure_wire(true, emit_keys, &records);
let mut expected: Vec<u8> = Vec::new();
expected.extend_from_slice(b"knit-delta-closure\n");
expected.extend_from_slice(b"annotated\n");
expected.extend_from_slice(b"file\x00rev1\trev2\n");
expected.extend_from_slice(b"file\x00rev1\n");
expected.extend_from_slice(b"None:\n");
expected.extend_from_slice(b"line-delta\n");
expected.extend_from_slice(b"T\n");
expected.extend_from_slice(b"\n"); expected.extend_from_slice(b"6\n"); expected.extend_from_slice(b"BODY-1");
expected.extend_from_slice(b"rev2\n");
expected.extend_from_slice(b"file\x00p0\n");
expected.extend_from_slice(b"fulltext\n");
expected.extend_from_slice(b"F\n");
expected.extend_from_slice(b"file\x00rev1\n");
expected.extend_from_slice(b"6\n");
expected.extend_from_slice(b"BODY-2");
assert_eq!(out, expected);
}
#[test]
fn knit_delta_closure_wire_unannotated_has_blank_flag_line() {
let emit_keys: &[&[&[u8]]] = &[];
let out = build_knit_delta_closure_wire(false, emit_keys, &[]);
assert_eq!(out, b"knit-delta-closure\n\n\n".to_vec());
}
#[test]
fn build_network_record_round_trips_none_parents() {
let key: &[&[u8]] = &[b"file-id", b"rev"];
let raw = build_network_record(b"knit-ft-gz", key, NO_PARENTS, true, b"DATA");
let line_end = b"knit-ft-gz\n".len();
let parsed = parse_network_record_header(&raw, line_end).unwrap();
assert_eq!(parsed.key, vec![&b"file-id"[..], &b"rev"[..]]);
assert!(parsed.parents.is_none());
assert!(parsed.noeol);
assert_eq!(parsed.raw_record, b"DATA");
}
#[test]
fn build_network_record_round_trips_with_parents_and_eol() {
let key: &[&[u8]] = &[b"f", b"r"];
let p1: &[&[u8]] = &[b"f", b"p1"];
let p2: &[&[u8]] = &[b"f", b"p2"];
let parents: &[&[&[u8]]] = &[p1, p2];
let raw = build_network_record(b"knit-delta-gz", key, Some(parents), false, b"BODY");
let line_end = b"knit-delta-gz\n".len();
let parsed = parse_network_record_header(&raw, line_end).unwrap();
assert_eq!(parsed.parents.unwrap().len(), 2);
assert!(!parsed.noeol);
assert_eq!(parsed.raw_record, b"BODY");
}
#[test]
fn build_network_record_single_key_segment() {
let key: &[&[u8]] = &[b"only"];
let raw = build_network_record(b"knit-ft-gz", key, NO_PARENTS, true, b"X");
assert_eq!(raw, b"knit-ft-gz\nonly\nNone:\nNX".to_vec());
}
#[test]
fn network_header_rejects_missing_noeol_byte() {
let bytes = b"knit-ft-gz\nk\nNone:\n";
let err = parse_network_record_header(bytes, 11).unwrap_err();
assert_eq!(err, KnitError::NetworkMissingNoEolByte);
}
fn build_record(version_id: &[u8], digest: &[u8], body: &[&[u8]]) -> Vec<u8> {
let mut header = Vec::new();
header.extend_from_slice(b"version ");
header.extend_from_slice(version_id);
header.extend_from_slice(format!(" {} ", body.len()).as_bytes());
header.extend_from_slice(digest);
header.push(b'\n');
let mut end = Vec::new();
end.extend_from_slice(b"end ");
end.extend_from_slice(version_id);
end.push(b'\n');
let mut chunks: Vec<&[u8]> = vec![&header];
chunks.extend_from_slice(body);
chunks.push(&end);
let gz = crate::tuned_gzip::chunks_to_gzip(chunks.iter().copied());
gz.into_iter().flatten().collect()
}
#[test]
fn parse_record_unchecked_round_trip() {
let body: &[&[u8]] = &[b"first line\n", b"second line\n"];
let raw = build_record(b"rev-1", b"DIGEST", body);
let (rec, contents) = parse_record_unchecked(&raw).unwrap();
assert_eq!(rec.method, b"version");
assert_eq!(rec.version_id, b"rev-1");
assert_eq!(rec.count, 2);
assert_eq!(rec.digest, b"DIGEST");
assert_eq!(
contents,
vec![b"first line\n".to_vec(), b"second line\n".to_vec()]
);
}
#[test]
fn parse_record_unchecked_zero_body() {
let raw = build_record(b"rev-0", b"DD", &[]);
let (rec, contents) = parse_record_unchecked(&raw).unwrap();
assert_eq!(rec.count, 0);
assert!(contents.is_empty());
}
#[test]
fn parse_record_unchecked_wrong_line_count() {
let mut header = b"version rev-x 5 DD\n".to_vec();
let body = b"only one\n".to_vec();
let end = b"end rev-x\n".to_vec();
let chunks: Vec<&[u8]> = vec![&header[..], &body[..], &end[..]];
let gz = crate::tuned_gzip::chunks_to_gzip(chunks.iter().copied());
let raw: Vec<u8> = gz.into_iter().flatten().collect();
let _ = &mut header;
let err = parse_record_unchecked(&raw).unwrap_err();
assert_eq!(
err,
KnitError::LineCount {
declared: 5,
actual: 1,
}
);
}
#[test]
fn parse_record_checks_version_match() {
let body: &[&[u8]] = &[b"a\n", b"b\n"];
let raw = build_record(b"rev-9", b"DIGEST", body);
let (lines, digest) = parse_record(b"rev-9", &raw).unwrap();
assert_eq!(lines, vec![b"a\n".to_vec(), b"b\n".to_vec()]);
assert_eq!(digest, b"DIGEST");
}
#[test]
fn parse_record_rejects_version_mismatch() {
let raw = build_record(b"got-this", b"DD", &[b"x\n"]);
let err = parse_record(b"wanted-that", &raw).unwrap_err();
assert_eq!(
err,
KnitError::UnexpectedVersion {
wanted: b"wanted-that".to_vec(),
got: b"got-this".to_vec(),
}
);
}
#[test]
fn parse_record_header_only_ignores_line_count_mismatch() {
let header = b"version rev-id-1 2 DIGEST\n".to_vec();
let body = b"foo\n".to_vec();
let end = b"end rev-id-1\n".to_vec();
let chunks: Vec<&[u8]> = vec![&header, &body, &end];
let gz = crate::tuned_gzip::chunks_to_gzip(chunks.into_iter());
let raw: Vec<u8> = gz.into_iter().flatten().collect();
assert!(parse_record_unchecked(&raw).is_err());
let rec = parse_record_header_only(&raw).unwrap();
assert_eq!(rec.version_id, b"rev-id-1");
assert_eq!(rec.count, 2);
assert_eq!(rec.digest, b"DIGEST");
}
#[test]
fn parse_record_unchecked_reports_gzip_errors_as_knit_error() {
let err = parse_record_unchecked(b"definitely not gzip").unwrap_err();
assert!(matches!(err, KnitError::Gzip(_)));
assert!(err.to_string().contains("corrupt compressed record"));
}
#[test]
fn readlines_iter_matches_collected_and_handles_unterminated_tail() {
let data = b"alpha\nbeta\ngamma";
let streamed: Vec<&[u8]> = ReadLines::new(data).collect();
assert_eq!(
streamed,
vec![&b"alpha\n"[..], &b"beta\n"[..], &b"gamma"[..]]
);
assert_eq!(streamed, readlines(data));
assert!(ReadLines::new(b"").next().is_none());
assert_eq!(readlines(b"just-one"), vec![&b"just-one"[..]]);
assert_eq!(readlines(b"\n"), vec![&b"\n"[..]]);
}
#[test]
fn parse_knit_index_value_handles_noeol_flag() {
let v = parse_knit_index_value(b"N123 4567").unwrap();
assert!(v.noeol);
assert_eq!(v.pos, 123);
assert_eq!(v.size, 4567);
let v = parse_knit_index_value(b" 5 10").unwrap();
assert!(!v.noeol);
assert_eq!(v.pos, 5);
assert_eq!(v.size, 10);
}
#[test]
fn parse_knit_index_value_rejects_garbage() {
assert_eq!(
parse_knit_index_value(b"").unwrap_err(),
KnitError::BadIndexValue(b"".to_vec())
);
assert_eq!(
parse_knit_index_value(b"Nfoo bar").unwrap_err(),
KnitError::BadIndexValue(b"Nfoo bar".to_vec())
);
assert_eq!(
parse_knit_index_value(b"N5").unwrap_err(),
KnitError::BadIndexValue(b"N5".to_vec())
);
}
fn batch_from_chain<'a>(
chain: &'a std::collections::HashMap<&'static str, Option<&'static str>>,
keys: &[&'static str],
) -> ClosureBatch<&'static str, &'static str> {
ClosureBatch {
present: keys
.iter()
.filter_map(|k| chain.get(k).map(|p| (*k, (*p, *k))))
.collect(),
missing: keys
.iter()
.filter(|k| !chain.contains_key(*k))
.copied()
.collect(),
}
}
#[test]
fn walk_compression_closure_follows_chain_until_fulltext() {
let chain: std::collections::HashMap<&'static str, Option<&'static str>> =
vec![("a", Some("b")), ("b", Some("c")), ("c", None)]
.into_iter()
.collect();
let result =
walk_compression_closure(vec!["a"], false, |batch| batch_from_chain(&chain, batch))
.unwrap();
let learned: std::collections::HashSet<&'static str> = result.keys().copied().collect();
let expected: std::collections::HashSet<&'static str> =
vec!["a", "b", "c"].into_iter().collect();
assert_eq!(learned, expected);
assert_eq!(result[&"a"], "a");
assert_eq!(result[&"c"], "c");
}
#[test]
fn walk_compression_closure_dedups_shared_parents() {
let chain: std::collections::HashMap<&'static str, Option<&'static str>> =
vec![("c1", Some("p")), ("c2", Some("p")), ("p", None)]
.into_iter()
.collect();
let mut batches: usize = 0;
let result = walk_compression_closure(vec!["c1", "c2"], false, |batch| {
batches += 1;
batch_from_chain(&chain, batch)
})
.unwrap();
assert_eq!(batches, 2);
let learned: std::collections::HashSet<&'static str> = result.keys().copied().collect();
let expected: std::collections::HashSet<&'static str> =
vec!["c1", "c2", "p"].into_iter().collect();
assert_eq!(learned, expected);
}
#[test]
fn walk_compression_closure_reports_missing_when_not_allowed() {
let err =
walk_compression_closure::<&'static str, &'static str, _>(vec!["x"], false, |_batch| {
ClosureBatch {
present: Default::default(),
missing: vec!["x"].into_iter().collect(),
}
})
.unwrap_err();
let expected: std::collections::HashSet<&'static str> = vec!["x"].into_iter().collect();
assert_eq!(err, expected);
}
#[test]
fn walk_compression_closure_skips_missing_when_allowed() {
let result = walk_compression_closure::<&'static str, &'static str, _>(
vec!["x", "y"],
true,
|batch| {
let mut present = std::collections::HashMap::new();
let mut missing = std::collections::HashSet::new();
for k in batch {
if *k == "y" {
present.insert(*k, (None, *k));
} else {
missing.insert(*k);
}
}
ClosureBatch { present, missing }
},
)
.unwrap();
let learned: std::collections::HashSet<&'static str> = result.keys().copied().collect();
let expected: std::collections::HashSet<&'static str> = vec!["y"].into_iter().collect();
assert_eq!(learned, expected);
}
#[test]
fn should_use_delta_finds_fulltext_and_picks_delta() {
let chain: std::collections::HashMap<&str, ChainStep<&'static str>> = vec![
(
"a",
ChainStep {
size: 10,
compression_parent: Some("b"),
},
),
(
"b",
ChainStep {
size: 10,
compression_parent: Some("c"),
},
),
(
"c",
ChainStep {
size: 100,
compression_parent: None,
},
),
]
.into_iter()
.collect();
let decision = should_use_delta("a", 5, |k| chain.get(k).cloned());
assert_eq!(decision, DeltaDecision::UseDelta);
assert!(decision.should_use_delta());
}
#[test]
fn should_use_delta_picks_fulltext_when_delta_chain_is_bigger() {
let chain: std::collections::HashMap<&str, ChainStep<&'static str>> = vec![
(
"a",
ChainStep {
size: 100,
compression_parent: Some("b"),
},
),
(
"b",
ChainStep {
size: 100,
compression_parent: Some("c"),
},
),
(
"c",
ChainStep {
size: 50,
compression_parent: None,
},
),
]
.into_iter()
.collect();
assert_eq!(
should_use_delta("a", 5, |k| chain.get(k).cloned()),
DeltaDecision::FulltextSmaller
);
}
#[test]
fn should_use_delta_chain_too_long() {
let decision = should_use_delta("a", 3, |_| {
Some(ChainStep {
size: 5,
compression_parent: Some("a"),
})
});
assert_eq!(decision, DeltaDecision::ChainTooLong);
}
#[test]
fn should_use_delta_missing_parent_falls_back_to_fulltext() {
let decision = should_use_delta("a", 5, |_| None);
assert_eq!(decision, DeltaDecision::MissingParent);
assert!(!decision.should_use_delta());
}
#[test]
fn decode_kndx_options_picks_method_and_noeol() {
let opts: &[&[u8]] = &[b"fulltext"];
assert_eq!(
decode_kndx_options(opts).unwrap(),
(KnitMethod::Fulltext, false)
);
let opts: &[&[u8]] = &[b"line-delta", b"no-eol"];
assert_eq!(
decode_kndx_options(opts).unwrap(),
(KnitMethod::LineDelta, true)
);
let opts: &[&[u8]] = &[b"no-eol", b"some-future-flag", b"fulltext"];
assert_eq!(
decode_kndx_options(opts).unwrap(),
(KnitMethod::Fulltext, true)
);
}
#[test]
fn decode_kndx_options_rejects_missing_method() {
let opts: &[&[u8]] = &[b"no-eol"];
assert!(matches!(
decode_kndx_options(opts).unwrap_err(),
KnitError::BadIndexValue(_)
));
}
#[test]
fn decode_knit_build_details_picks_method_from_parent_count() {
let d = decode_knit_build_details(b" 0 10", false, 5).unwrap();
assert_eq!(d.method, KnitMethod::Fulltext);
assert_eq!(d.compression_parent, None);
let d = decode_knit_build_details(b" 0 10", true, 0).unwrap();
assert_eq!(d.method, KnitMethod::Fulltext);
assert_eq!(d.compression_parent, None);
let d = decode_knit_build_details(b"N0 10", true, 1).unwrap();
assert_eq!(d.method, KnitMethod::LineDelta);
assert!(d.noeol);
assert_eq!(d.compression_parent, Some(0));
assert_eq!(
decode_knit_build_details(b" 0 10", true, 2).unwrap_err(),
KnitError::TooManyCompressionParents(2)
);
}
#[test]
fn extract_annotated_fulltext_strips_origins_and_honors_noeol() {
let annotated: Vec<AnnotatedLine> = vec![
(b"r1".to_vec(), b"hello\n".to_vec()),
(b"r2".to_vec(), b"world\n".to_vec()),
];
let body = lower_fulltext(&annotated);
let (_, chunks) = record_to_data(b"v", b"DD", body.len(), &body, true).unwrap();
let raw: Vec<u8> = chunks.into_iter().flatten().collect();
let with_eol = extract_annotated_fulltext_to_plain_lines(&raw, false).unwrap();
assert_eq!(with_eol, vec![b"hello\n".to_vec(), b"world\n".to_vec()]);
let no_eol = extract_annotated_fulltext_to_plain_lines(&raw, true).unwrap();
assert_eq!(no_eol, vec![b"hello\n".to_vec(), b"world".to_vec()]);
}
#[test]
fn extract_plain_fulltext_lines_passes_through_with_noeol_strip() {
let body = vec![b"alpha\n".to_vec(), b"beta\n".to_vec()];
let (_, chunks) = record_to_data(b"v", b"DD", body.len(), &body, true).unwrap();
let raw: Vec<u8> = chunks.into_iter().flatten().collect();
let plain = extract_plain_fulltext_lines(&raw, false).unwrap();
assert_eq!(plain, vec![b"alpha\n".to_vec(), b"beta\n".to_vec()]);
let stripped = extract_plain_fulltext_lines(&raw, true).unwrap();
assert_eq!(stripped, vec![b"alpha\n".to_vec(), b"beta".to_vec()]);
}
#[test]
fn recompress_annotated_to_unannotated_fulltext_strips_origins() {
let annotated: Vec<AnnotatedLine> = vec![
(b"rev1".to_vec(), b"alpha\n".to_vec()),
(b"rev2".to_vec(), b"beta\n".to_vec()),
];
let body = lower_fulltext(&annotated);
let (_, chunks) = record_to_data(b"rev-id", b"DIGEST", body.len(), &body, true).unwrap();
let raw: Vec<u8> = chunks.into_iter().flatten().collect();
let unannotated_raw = recompress_annotated_to_unannotated_fulltext(&raw).unwrap();
let (header, body_lines) = parse_record_unchecked(&unannotated_raw).unwrap();
assert_eq!(header.version_id, b"rev-id");
assert_eq!(header.digest, b"DIGEST");
assert_eq!(header.count, 2);
assert_eq!(body_lines, vec![b"alpha\n".to_vec(), b"beta\n".to_vec()]);
}
#[test]
fn recompress_annotated_to_unannotated_delta_strips_origins() {
let delta = vec![DeltaHunk {
start: 0,
end: 1,
count: 2,
lines: vec![
(b"r1".to_vec(), b"alpha\n".to_vec()),
(b"r2".to_vec(), b"beta\n".to_vec()),
],
}];
let body = lower_line_delta_annotated(&delta);
let (_, chunks) = record_to_data(b"rev-id", b"DD", body.len(), &body, true).unwrap();
let raw: Vec<u8> = chunks.into_iter().flatten().collect();
let unannotated_raw = recompress_annotated_to_unannotated_delta(&raw).unwrap();
let (header, body_lines) = parse_record_unchecked(&unannotated_raw).unwrap();
assert_eq!(header.version_id, b"rev-id");
assert_eq!(header.digest, b"DD");
assert_eq!(body_lines.len(), 3);
assert_eq!(body_lines[0], b"0,1,2\n".to_vec());
assert_eq!(body_lines[1], b"alpha\n".to_vec());
assert_eq!(body_lines[2], b"beta\n".to_vec());
}
#[test]
fn parse_record_body_unchecked_borrows_from_buffer() {
let mut body = Vec::new();
body.extend_from_slice(b"version rev-x 2 DIG\n");
body.extend_from_slice(b"alpha\n");
body.extend_from_slice(b"beta\n");
body.extend_from_slice(b"end rev-x\n");
let (header, lines) = parse_record_body_unchecked(&body).unwrap();
assert_eq!(header.method, b"version");
assert_eq!(header.version_id, b"rev-x");
assert_eq!(header.count, 2);
assert_eq!(header.digest, b"DIG");
assert_eq!(lines, vec![&b"alpha\n"[..], &b"beta\n"[..]]);
let body_range = body.as_ptr_range();
for line in &lines {
let start = line.as_ptr();
assert!(start >= body_range.start && start < body_range.end);
}
}
#[test]
fn record_to_data_round_trip_via_parse() {
let body: Vec<Vec<u8>> = vec![b"alpha\n".to_vec(), b"beta\n".to_vec()];
let (len, chunks) = record_to_data(b"rev-7", b"DIGEST", body.len(), &body, true).unwrap();
let raw: Vec<u8> = chunks.into_iter().flatten().collect();
assert_eq!(len, raw.len());
let (rec, contents) = parse_record_unchecked(&raw).unwrap();
assert_eq!(rec.version_id, b"rev-7");
assert_eq!(rec.count, 2);
assert_eq!(rec.digest, b"DIGEST");
assert_eq!(contents, body);
}
#[test]
fn record_to_data_rejects_missing_trailing_newline() {
let body: Vec<Vec<u8>> = vec![b"no-newline".to_vec()];
let err = record_to_data(b"rev", b"DD", 1, &body, false).unwrap_err();
assert_eq!(err, KnitError::MissingTrailingNewline);
}
#[test]
fn record_to_data_empty_body() {
let empty: Vec<Vec<u8>> = vec![];
let (_, chunks) = record_to_data(b"rev-0", b"DD", 0, &empty, true).unwrap();
let raw: Vec<u8> = chunks.into_iter().flatten().collect();
let (rec, contents) = parse_record_unchecked(&raw).unwrap();
assert_eq!(rec.count, 0);
assert!(contents.is_empty());
}
#[test]
fn parse_record_unchecked_bad_end_marker() {
let mut header = b"version rev-y 1 DD\n".to_vec();
let body = b"body\n".to_vec();
let end = b"end wrong-id\n".to_vec();
let chunks: Vec<&[u8]> = vec![&header[..], &body[..], &end[..]];
let gz = crate::tuned_gzip::chunks_to_gzip(chunks.iter().copied());
let raw: Vec<u8> = gz.into_iter().flatten().collect();
let _ = &mut header;
let err = parse_record_unchecked(&raw).unwrap_err();
assert_eq!(
err,
KnitError::BadEndMarker {
expected: b"end rev-y\n".to_vec(),
actual: b"end wrong-id\n".to_vec(),
}
);
}
#[test]
fn dictionary_compress_empty() {
let lookup = std::collections::HashMap::new();
let suffixes: Vec<&[u8]> = vec![];
assert_eq!(dictionary_compress_suffixes(&suffixes, &lookup), b"");
}
#[test]
fn dictionary_compress_all_cached() {
let mut lookup = std::collections::HashMap::new();
lookup.insert(&b"rev-a"[..], 0u64);
lookup.insert(&b"rev-b"[..], 3u64);
let suffixes: Vec<&[u8]> = vec![b"rev-a", b"rev-b"];
assert_eq!(dictionary_compress_suffixes(&suffixes, &lookup), b"0 3");
}
#[test]
fn dictionary_compress_mixed_and_fallback() {
let mut lookup = std::collections::HashMap::new();
lookup.insert(&b"rev-a"[..], 12u64);
let suffixes: Vec<&[u8]> = vec![b"rev-a", b"rev-ghost", b"rev-a"];
assert_eq!(
dictionary_compress_suffixes(&suffixes, &lookup),
b"12 .rev-ghost 12"
);
}
#[test]
fn format_kndx_record_line_basic() {
let options = vec![b"fulltext".to_vec(), b"no-eol".to_vec()];
let line = format_kndx_record_line(b"rev-1", &options, 0, 123, b"0 .rev-x");
assert_eq!(line, b"\nrev-1 fulltext,no-eol 0 123 0 .rev-x :");
}
#[test]
fn format_kndx_record_line_no_parents() {
let options = vec![b"line-delta".to_vec()];
let line = format_kndx_record_line(b"rev-2", &options, 17, 99, b"");
assert_eq!(line, b"\nrev-2 line-delta 17 99 :");
}
#[test]
fn parse_storage_kind_classifies_each_variant() {
assert_eq!(
parse_storage_kind("knit-ft-gz"),
Some((KnitMethod::Fulltext, false))
);
assert_eq!(
parse_storage_kind("knit-delta-gz"),
Some((KnitMethod::LineDelta, false))
);
assert_eq!(
parse_storage_kind("knit-annotated-ft-gz"),
Some((KnitMethod::Fulltext, true))
);
assert_eq!(
parse_storage_kind("knit-annotated-delta-gz"),
Some((KnitMethod::LineDelta, true))
);
}
#[test]
fn parse_storage_kind_rejects_non_knit() {
assert!(parse_storage_kind("groupcompress-block").is_none());
assert!(parse_storage_kind("knit-ft").is_none());
assert!(parse_storage_kind("").is_none());
}
#[test]
fn format_and_parse_storage_kind_roundtrip() {
for method in [KnitMethod::Fulltext, KnitMethod::LineDelta] {
for annotated in [false, true] {
let kind = format_storage_kind(method, annotated);
let parsed = parse_storage_kind(&kind).expect("valid kind");
assert_eq!(parsed, (method, annotated));
}
}
}
#[test]
fn annotated_content_text_returns_empty_for_empty_input() {
let content = AnnotatedKnitContent::new(vec![]);
assert!(content.text().is_empty());
}
#[test]
fn annotated_content_text_returns_text_part_of_pairs() {
let content = AnnotatedKnitContent::new(vec![
(b"origin1".to_vec(), b"text1".to_vec()),
(b"origin2".to_vec(), b"text2".to_vec()),
]);
assert_eq!(content.text(), vec![b"text1".to_vec(), b"text2".to_vec()]);
}
#[test]
fn annotated_content_clone_preserves_annotations() {
let content = AnnotatedKnitContent::new(vec![
(b"origin1".to_vec(), b"text1".to_vec()),
(b"origin2".to_vec(), b"text2".to_vec()),
]);
let copy = content.clone();
assert_eq!(copy.annotate(), content.annotate());
}
#[test]
fn annotated_content_annotate_returns_pairs_verbatim() {
let empty = AnnotatedKnitContent::new(vec![]);
assert!(empty.annotate().is_empty());
let content = AnnotatedKnitContent::new(vec![
(b"origin1".to_vec(), b"text1".to_vec()),
(b"origin2".to_vec(), b"text2".to_vec()),
]);
assert_eq!(
content.annotate(),
vec![
(b"origin1".to_vec(), b"text1".to_vec()),
(b"origin2".to_vec(), b"text2".to_vec()),
]
);
}
#[test]
fn materialize_text_fulltext_joins_lines() {
let r = materialize_text(vec![b"a\n".to_vec(), b"b\n".to_vec()], "fulltext").unwrap();
assert_eq!(r, KnitTextResult::Bytes(b"a\nb\n".to_vec()));
}
#[test]
fn materialize_text_chunked_returns_lines() {
let r = materialize_text(vec![b"a\n".to_vec(), b"b\n".to_vec()], "chunked").unwrap();
assert_eq!(
r,
KnitTextResult::Lines(vec![b"a\n".to_vec(), b"b\n".to_vec()])
);
}
#[test]
fn annotated_content_line_delta_keeps_annotations() {
let content1 = AnnotatedKnitContent::new(vec![
(Vec::new(), b"a".to_vec()),
(Vec::new(), b"b".to_vec()),
]);
let content2 = AnnotatedKnitContent::new(vec![
(Vec::new(), b"a".to_vec()),
(Vec::new(), b"a".to_vec()),
(Vec::new(), b"c".to_vec()),
]);
let delta = compute_line_delta(&content1, &content2);
assert_eq!(
delta,
vec![DeltaHunk {
start: 1,
end: 2,
count: 2,
lines: vec![(Vec::new(), b"a".to_vec()), (Vec::new(), b"c".to_vec()),],
}]
);
}
#[test]
fn plain_content_text_returns_lines_verbatim() {
let annotated = AnnotatedKnitContent::new(vec![
(Vec::new(), b"text1".to_vec()),
(Vec::new(), b"text2".to_vec()),
]);
let plain = PlainKnitContent::new(annotated.text(), b"bogus".to_vec());
assert_eq!(plain.text(), vec![b"text1".to_vec(), b"text2".to_vec()]);
}
#[test]
fn plain_content_annotate_uses_constructor_version_id() {
let empty = PlainKnitContent::new(vec![], b"bogus".to_vec());
assert!(empty.annotate().is_empty());
let content = PlainKnitContent::new(
vec![b"text1".to_vec(), b"text2".to_vec()],
b"bogus".to_vec(),
);
assert_eq!(
content.annotate(),
vec![
(b"bogus".to_vec(), b"text1".to_vec()),
(b"bogus".to_vec(), b"text2".to_vec()),
]
);
}
#[test]
fn plain_content_line_delta_uses_bare_text_lines() {
let content1 = PlainKnitContent::new(vec![b"a".to_vec(), b"b".to_vec()], b"v1".to_vec());
let content2 = PlainKnitContent::new(
vec![b"a".to_vec(), b"a".to_vec(), b"c".to_vec()],
b"v2".to_vec(),
);
let delta = compute_line_delta(&content1, &content2);
assert_eq!(
delta,
vec![DeltaHunk {
start: 1,
end: 2,
count: 2,
lines: vec![b"a".to_vec(), b"c".to_vec()],
}]
);
}
fn kndx_bytes(lines: &[&[u8]]) -> Vec<u8> {
let mut out = Vec::new();
out.extend_from_slice(KNDX_HEADER);
for line in lines {
out.push(b'\n');
out.extend_from_slice(line);
}
out
}
#[test]
fn parse_kndx_data_empty_input_yields_empty_cache() {
let pc = parse_kndx_data(b"").unwrap();
assert!(pc.cache.is_empty());
assert!(pc.history.is_empty());
}
#[test]
fn parse_kndx_data_rejects_corrupt_header() {
let err = parse_kndx_data(b"not a bzr knit index header\n").unwrap_err();
assert!(matches!(err, KnitError::BadKnitHeader { .. }));
}
#[test]
fn parse_kndx_data_ignores_corrupted_lines() {
let data = kndx_bytes(&[
b"corrupted",
b"corrupted options 0 1 .b .c ",
b"version options 0 1 :",
]);
let pc = parse_kndx_data(&data).unwrap();
assert_eq!(pc.cache.len(), 1);
assert!(pc.cache.contains_key(b"version".as_slice()));
}
#[test]
fn parse_kndx_data_short_line_is_skipped() {
let data = kndx_bytes(&[b"a option 0 10 :", b"b option 10 10 0"]);
let pc = parse_kndx_data(&data).unwrap();
assert_eq!(pc.cache.len(), 1);
assert!(pc.cache.contains_key(b"a".as_slice()));
}
#[test]
fn parse_kndx_data_resumes_after_incomplete_record() {
let data = kndx_bytes(&[
b"a option 0 10 :",
b"b option 10 10 0",
b"c option 20 10 0 :",
]);
let pc = parse_kndx_data(&data).unwrap();
let mut keys: Vec<Vec<u8>> = pc.cache.keys().cloned().collect();
keys.sort();
assert_eq!(keys, vec![b"a".to_vec(), b"c".to_vec()]);
}
#[test]
fn parse_kndx_data_trailing_characters_are_skipped() {
let data = kndx_bytes(&[
b"a option 0 10 :",
b"b option 10 10 0 :a",
b"c option 20 10 0 :",
]);
let pc = parse_kndx_data(&data).unwrap();
let mut keys: Vec<Vec<u8>> = pc.cache.keys().cloned().collect();
keys.sort();
assert_eq!(keys, vec![b"a".to_vec(), b"c".to_vec()]);
}
#[test]
fn parse_kndx_data_resolves_compressed_parents() {
let data = kndx_bytes(&[
b"a option 0 1 :",
b"b option 0 1 0 :",
b"c option 0 1 1 0 :",
]);
let pc = parse_kndx_data(&data).unwrap();
assert_eq!(pc.cache[&b"b".to_vec()].parents, vec![b"a".to_vec()]);
assert_eq!(
pc.cache[&b"c".to_vec()].parents,
vec![b"b".to_vec(), b"a".to_vec()]
);
}
#[test]
fn parse_kndx_data_duplicate_entries_keep_first_history_index() {
let data = kndx_bytes(&[
b"parent options 0 1 :",
b"version options1 0 1 0 :",
b"version options2 1 2 .other :",
b"version options3 3 4 0 .other :",
]);
let pc = parse_kndx_data(&data).unwrap();
assert_eq!(pc.cache.len(), 2);
assert_eq!(pc.history.len(), 2);
let ver = &pc.cache[&b"version".to_vec()];
assert_eq!(ver.index, 1);
assert_eq!(ver.pos, 3);
assert_eq!(ver.size, 4);
assert_eq!(ver.options, vec![b"options3".to_vec()]);
assert_eq!(ver.parents, vec![b"parent".to_vec(), b"other".to_vec()]);
}
#[test]
fn parse_kndx_data_rejects_impossible_parent_index() {
let data = kndx_bytes(&[b"a option 0 1 :", b"b option 0 1 4 :"]);
let err = parse_kndx_data(&data).unwrap_err();
assert!(matches!(err, KnitError::KndxCorrupt { .. }));
}
#[test]
fn parse_kndx_data_rejects_non_integer_parent_index() {
let data = kndx_bytes(&[b"a option 0 1 :", b"b option 0 1 :", b"c option 0 1 1v :"]);
let err = parse_kndx_data(&data).unwrap_err();
assert!(matches!(err, KnitError::KndxCorrupt { .. }));
}
#[test]
fn parse_kndx_data_rejects_corrupt_parent_in_list() {
let data = kndx_bytes(&[b"a option 0 1 :", b"b option 0 1 :", b"c option 0 1 1 v :"]);
let err = parse_kndx_data(&data).unwrap_err();
assert!(matches!(err, KnitError::KndxCorrupt { .. }));
}
#[test]
fn parse_kndx_data_rejects_invalid_position() {
let data = kndx_bytes(&[b"a option 1v 1 :"]);
let err = parse_kndx_data(&data).unwrap_err();
assert!(matches!(err, KnitError::KndxCorrupt { .. }));
}
#[test]
fn parse_kndx_data_rejects_invalid_size() {
let data = kndx_bytes(&[b"a option 1 1v :"]);
let err = parse_kndx_data(&data).unwrap_err();
assert!(matches!(err, KnitError::KndxCorrupt { .. }));
}
#[test]
fn parse_kndx_data_parses_position_and_size() {
let data = kndx_bytes(&[b"a option 0 1 :", b"b option 1 2 :"]);
let pc = parse_kndx_data(&data).unwrap();
let a = &pc.cache[&b"a".to_vec()];
let b = &pc.cache[&b"b".to_vec()];
assert_eq!((a.pos, a.size), (0, 1));
assert_eq!((b.pos, b.size), (1, 2));
}
#[test]
fn parse_kndx_data_preserves_options_list() {
let data = kndx_bytes(&[b"a opt1 0 1 :", b"b opt2,opt3 1 2 :"]);
let pc = parse_kndx_data(&data).unwrap();
assert_eq!(pc.cache[&b"a".to_vec()].options, vec![b"opt1".to_vec()]);
assert_eq!(
pc.cache[&b"b".to_vec()].options,
vec![b"opt2".to_vec(), b"opt3".to_vec()]
);
}
fn make_kndx_transport(
name: &str,
lines: &[&[u8]],
) -> crate::transport::testing::MemoryTransport {
let t = crate::transport::testing::MemoryTransport::new();
let data = kndx_bytes(lines);
t.put_file_non_atomic(&format!("{}.kndx", name), &data, true)
.unwrap();
t
}
fn make_kndx_index(
name: &str,
lines: &[&[u8]],
) -> KndxIndex<crate::transport::testing::MemoryTransport, crate::key_mapper::ConstantMapper>
{
let transport = make_kndx_transport(name, lines);
KndxIndex::new(
transport,
crate::key_mapper::ConstantMapper {
result: name.to_string(),
},
)
}
#[test]
fn kndx_index_get_parent_map_resolves_compressed_parents() {
let idx = make_kndx_index(
"filename",
&[
b"a option 0 1 :",
b"b option 1 2 0 .c :",
b"c option 1 2 1 0 .e :",
],
);
let key_a: KnitKey = vec![b"a".to_vec()];
let key_b: KnitKey = vec![b"b".to_vec()];
let key_c: KnitKey = vec![b"c".to_vec()];
let pm = idx
.get_parent_map(&[key_a.clone(), key_b.clone(), key_c.clone()])
.unwrap();
assert_eq!(pm[&key_a], Vec::<KnitKey>::new());
assert_eq!(pm[&key_b], vec![vec![b"a".to_vec()], vec![b"c".to_vec()],]);
assert_eq!(
pm[&key_c],
vec![
vec![b"b".to_vec()],
vec![b"a".to_vec()],
vec![b"e".to_vec()],
]
);
}
#[test]
fn kndx_index_get_method_returns_method_from_options() {
let idx = make_kndx_index(
"filename",
&[b"a fulltext,unknown 0 1 :", b"b unknown,line-delta 1 2 :"],
);
let key_a: KnitKey = vec![b"a".to_vec()];
let key_b: KnitKey = vec![b"b".to_vec()];
assert_eq!(idx.get_method(&key_a).unwrap(), KnitMethod::Fulltext);
assert_eq!(idx.get_method(&key_b).unwrap(), KnitMethod::LineDelta);
}
#[test]
fn kndx_index_add_records_writes_to_transport_and_updates_cache() {
let idx = make_kndx_index("filename", &[]);
let key: KnitKey = vec![b"a".to_vec()];
let memo = KnitIndexMemo {
file_ref: "filename.knit".to_string(),
offset: 0,
length: 1,
};
idx.add_records(
&[(key.clone(), vec![KnitMethod::Fulltext], memo, vec![])],
false,
false,
)
.unwrap();
assert!(idx.contains(&key).unwrap());
assert_eq!(idx.get_method(&key).unwrap(), KnitMethod::Fulltext);
let written = idx.transport().get_bytes("filename.kndx").unwrap();
assert!(
written.ends_with(b"\na fulltext 0 1 :"),
"kndx tail mismatch: {:?}",
String::from_utf8_lossy(&written)
);
}
#[test]
fn kndx_index_add_records_writes_ghost_parent_dotted() {
let idx = make_kndx_index("filename", &[]);
let memo = KnitIndexMemo {
file_ref: "filename.knit".to_string(),
offset: 0,
length: 1,
};
idx.add_records(
&[(
vec![b"version".to_vec()],
vec![KnitMethod::Fulltext],
memo,
vec![vec![b"ghost".to_vec()]],
)],
false,
false,
)
.unwrap();
let written = idx.transport().get_bytes("filename.kndx").unwrap();
assert!(
written.ends_with(b"\nversion fulltext 0 1 .ghost :"),
"kndx tail mismatch: {:?}",
String::from_utf8_lossy(&written)
);
}
#[test]
fn kndx_index_add_records_writes_known_parent_as_index() {
let idx = make_kndx_index("filename", &[]);
let memo = |off| KnitIndexMemo {
file_ref: "filename.knit".to_string(),
offset: off,
length: 1,
};
idx.add_records(
&[(
vec![b"a".to_vec()],
vec![KnitMethod::Fulltext],
memo(0),
vec![],
)],
false,
false,
)
.unwrap();
idx.add_records(
&[(
vec![b"b".to_vec()],
vec![KnitMethod::Fulltext],
memo(1),
vec![vec![b"a".to_vec()]],
)],
false,
false,
)
.unwrap();
let written = idx.transport().get_bytes("filename.kndx").unwrap();
assert!(
written.ends_with(b"\nb fulltext 1 1 0 :"),
"kndx tail mismatch: {:?}",
String::from_utf8_lossy(&written)
);
}
#[test]
fn kndx_index_load_prefix_typed_reports_bad_header() {
let transport = crate::transport::testing::MemoryTransport::new();
transport
.put_file_non_atomic("filename.kndx", b"not a bzr knit index header\n", true)
.unwrap();
let idx = KndxIndex::new(
transport,
crate::key_mapper::ConstantMapper {
result: "filename".to_string(),
},
);
let err = idx.load_prefix_typed(vec![]).unwrap_err();
assert!(matches!(
err,
KndxLoadError::Knit(KnitError::BadKnitHeader { .. })
));
}
fn fulltext_pos(path: &str, offset: u64, length: usize) -> KnitRecordDetails {
KnitRecordDetails {
method: KnitMethod::Fulltext,
noeol: false,
index_memo: KnitIndexMemo {
file_ref: path.to_string(),
offset,
length,
},
compression_parent: None,
parents: vec![],
}
}
fn delta_pos(
path: &str,
offset: u64,
length: usize,
compression_parent: KnitKey,
) -> KnitRecordDetails {
KnitRecordDetails {
method: KnitMethod::LineDelta,
noeol: false,
index_memo: KnitIndexMemo {
file_ref: path.to_string(),
offset,
length,
},
compression_parent: Some(compression_parent.clone()),
parents: vec![compression_parent],
}
}
#[test]
fn materialize_text_unknown_kind_returns_none() {
assert!(materialize_text(vec![b"a\n".to_vec()], "knit-ft-gz").is_none());
}
fn adapter_input<'a>(
key: &'a [Vec<u8>],
raw_record: &'a [u8],
noeol: bool,
parents: Option<&'a [Vec<Vec<u8>>]>,
storage_kind: &'a str,
) -> KnitAdapterInput<'a> {
KnitAdapterInput {
key,
raw_record,
noeol,
parents,
storage_kind,
}
}
fn fulltext_raw(version_id: &[u8], lines: &[&[u8]], _noeol: bool) -> Vec<u8> {
let pairs: Vec<AnnotatedLine> = lines
.iter()
.map(|l| (version_id.to_vec(), l.to_vec()))
.collect();
let body = lower_fulltext(&pairs);
let count = lines.len();
let has_tnl = lines.last().map(|l| l.ends_with(b"\n")).unwrap_or(true);
let (_, chunks) = record_to_data(version_id, b"DD", count, &body, has_tnl).unwrap();
chunks.into_iter().flatten().collect()
}
fn delta_raw_annotated(version_id: &[u8], hunks: &[DeltaHunk<AnnotatedLine>]) -> Vec<u8> {
let body = lower_line_delta_annotated(hunks);
let count = body.len();
let has_tnl = body.last().map(|l| l.ends_with(b"\n")).unwrap_or(true);
let (_, chunks) = record_to_data(version_id, b"DD", count, &body, has_tnl).unwrap();
chunks.into_iter().flatten().collect()
}
fn ann_key(id: &[u8]) -> KnitKey {
vec![id.to_vec()]
}
fn make_annotator() -> KnitAnnotator<MockKnit, MockKnit, KnitAnnotateFactory> {
KnitAnnotator::new(
MockKnit::default(),
MockKnit::default(),
KnitAnnotateFactory,
)
}
#[test]
fn annotator_special_text_merges_origins_from_two_parents() {
let mut ann = make_annotator();
let rev1 = ann_key(b"rev-1");
let rev2 = ann_key(b"rev-2");
let rev3 = ann_key(b"rev-3");
let spec = ann_key(b"special:");
ann.seed_text(rev1.clone(), vec![], vec![b"initial content\n".to_vec()]);
ann.seed_text(
rev2.clone(),
vec![rev1.clone()],
vec![
b"initial content\n".to_vec(),
b"common content\n".to_vec(),
b"content in 2\n".to_vec(),
],
);
ann.seed_text(
rev3.clone(),
vec![rev1.clone()],
vec![
b"initial content\n".to_vec(),
b"common content\n".to_vec(),
b"content in 3\n".to_vec(),
],
);
let spec_text = vec![
b"initial content\n".to_vec(),
b"common content\n".to_vec(),
b"content in 2\n".to_vec(),
b"content in 3\n".to_vec(),
];
ann.add_special_text(
spec.clone(),
vec![rev2.clone(), rev3.clone()],
spec_text.clone(),
);
let order = vec![rev1.clone(), rev2.clone(), rev3.clone(), spec.clone()];
let (annotations, lines) = ann.annotate_seeded(&spec, &order).unwrap();
assert_eq!(
annotations,
vec![
vec![rev1.clone()],
vec![rev2.clone(), rev3.clone()],
vec![rev2.clone()],
vec![rev3.clone()],
]
);
assert_eq!(lines, spec_text);
}
#[test]
fn annotator_expand_fulltext_caches_content_and_text() {
let mut ann = make_annotator();
let rev_key = ann_key(b"rev-id");
ann.num_compression_children.insert(rev_key.clone(), 1);
let raw = fulltext_raw(b"rev-id", &[b"line1\n", b"line2\n"], true);
let res = ann
.expand_record(
rev_key.clone(),
vec![ann_key(b"parent-id")],
None,
raw,
KnitMethod::Fulltext,
true,
)
.unwrap();
assert_eq!(res, Some(vec![b"line1\n".to_vec(), b"line2".to_vec()]));
assert!(ann.content_objects.contains_key(&rev_key));
assert_eq!(
ann.text_cache[&rev_key],
vec![b"line1\n".to_vec(), b"line2".to_vec()]
);
}
#[test]
fn annotator_expand_delta_queues_when_parent_unavailable() {
let mut ann = make_annotator();
let rev_key = ann_key(b"rev-id");
let parent_key = ann_key(b"parent-id");
let hunk = DeltaHunk {
start: 0,
end: 1,
count: 1,
lines: vec![(b"rev-id".to_vec(), b"new-line\n".to_vec())],
};
let raw = delta_raw_annotated(b"rev-id", &[hunk]);
let res = ann
.expand_record(
rev_key.clone(),
vec![parent_key.clone()],
Some(parent_key.clone()),
raw,
KnitMethod::LineDelta,
false,
)
.unwrap();
assert_eq!(res, None);
assert!(ann.pending_deltas.contains_key(&parent_key));
assert_eq!(ann.pending_deltas[&parent_key].len(), 1);
}
#[test]
fn annotator_expand_record_tracks_num_compression_children() {
let mut ann = make_annotator();
let rev_key = ann_key(b"rev-id");
let rev2_key = ann_key(b"rev2-id");
let parent_key = ann_key(b"parent-id");
ann.num_compression_children.insert(parent_key.clone(), 2);
let raw_parent = fulltext_raw(b"parent-id", &[b"line1\n", b"line2\n"], false);
ann.expand_record(
parent_key.clone(),
vec![],
None,
raw_parent,
KnitMethod::Fulltext,
false,
)
.unwrap();
let hunk = DeltaHunk {
start: 0,
end: 1,
count: 1,
lines: vec![(b"rev-id".to_vec(), b"new-line\n".to_vec())],
};
let raw_rev = delta_raw_annotated(b"rev-id", &[hunk.clone()]);
ann.expand_record(
rev_key.clone(),
vec![parent_key.clone()],
Some(parent_key.clone()),
raw_rev,
KnitMethod::LineDelta,
false,
)
.unwrap();
assert_eq!(ann.num_compression_children[&parent_key], 1);
let raw_rev2 = delta_raw_annotated(b"rev2-id", &[hunk]);
ann.expand_record(
rev2_key.clone(),
vec![parent_key.clone()],
Some(parent_key.clone()),
raw_rev2,
KnitMethod::LineDelta,
false,
)
.unwrap();
assert!(!ann.content_objects.contains_key(&parent_key));
assert!(!ann.num_compression_children.contains_key(&parent_key));
assert!(!ann.content_objects.contains_key(&rev_key));
assert!(!ann.content_objects.contains_key(&rev2_key));
}
#[test]
fn annotator_expand_delta_records_matching_blocks() {
let mut ann = make_annotator();
let rev_key = ann_key(b"rev-id");
let parent_key = ann_key(b"parent-id");
ann.num_compression_children.insert(parent_key.clone(), 2);
let raw_parent = fulltext_raw(b"parent-id", &[b"line1\n", b"line2\n", b"line3\n"], false);
ann.expand_record(
parent_key.clone(),
vec![],
None,
raw_parent,
KnitMethod::Fulltext,
false,
)
.unwrap();
let hunk_ann = DeltaHunk {
start: 0,
end: 1,
count: 1,
lines: vec![(b"rev-id".to_vec(), b"new-line\n".to_vec())],
};
let raw_rev = delta_raw_annotated(b"rev-id", &[hunk_ann]);
ann.expand_record(
rev_key.clone(),
vec![parent_key.clone()],
Some(parent_key.clone()),
raw_rev,
KnitMethod::LineDelta,
true,
)
.unwrap();
assert_eq!(
ann.matching_blocks[&(rev_key.clone(), parent_key.clone())],
vec![(1, 1, 1), (3, 3, 0)]
);
let rev2_key = ann_key(b"rev2-id");
let hunk_plain = DeltaHunk {
start: 0,
end: 1,
count: 1,
lines: vec![(b"rev2-id".to_vec(), b"new-line\n".to_vec())],
};
let raw_rev2 = delta_raw_annotated(b"rev2-id", &[hunk_plain]);
ann.expand_record(
rev2_key.clone(),
vec![parent_key.clone()],
Some(parent_key.clone()),
raw_rev2,
KnitMethod::LineDelta,
false,
)
.unwrap();
assert_eq!(
ann.matching_blocks[&(rev2_key.clone(), parent_key.clone())],
vec![(1, 1, 2), (3, 3, 0)]
);
}
#[test]
fn annotator_get_parent_annotations_uses_precomputed_blocks() {
let mut ann = make_annotator();
let rev_key = ann_key(b"rev-id");
let parent_key = ann_key(b"parent-id");
let parent_ann: Vec<LineAnnotation> = vec![vec![parent_key.clone()]; 3];
ann.annotations_cache
.insert(parent_key.clone(), parent_ann.clone());
ann.matching_blocks.insert(
(rev_key.clone(), parent_key.clone()),
vec![(0, 1, 1), (3, 3, 0)],
);
let text = vec![b"1\n".to_vec(), b"2\n".to_vec(), b"3\n".to_vec()];
let (par_ann, blocks) =
ann.get_parent_annotations_and_matches(&rev_key, &text, &parent_key);
assert_eq!(par_ann, parent_ann);
assert_eq!(blocks, vec![(0, 1, 1), (3, 3, 0)]);
assert!(ann.matching_blocks.is_empty());
}
#[test]
fn annotator_process_pending_drains_queues() {
let mut ann = make_annotator();
let rev_key = ann_key(b"rev-id");
let p1_key = ann_key(b"p1-id");
let p2_key = ann_key(b"p2-id");
ann.num_compression_children.insert(p1_key.clone(), 1);
let hunk = DeltaHunk {
start: 0,
end: 1,
count: 1,
lines: vec![(b"rev-id".to_vec(), b"new-line\n".to_vec())],
};
let raw_rev = delta_raw_annotated(b"rev-id", &[hunk]);
let res = ann
.expand_record(
rev_key.clone(),
vec![p1_key.clone(), p2_key.clone()],
Some(p1_key.clone()),
raw_rev,
KnitMethod::LineDelta,
false,
)
.unwrap();
assert_eq!(res, None);
assert!(ann.pending_annotation.is_empty());
let raw_p1 = fulltext_raw(b"p1-id", &[b"line1\n", b"line2\n"], false);
let res = ann
.expand_record(
p1_key.clone(),
vec![],
None,
raw_p1,
KnitMethod::Fulltext,
false,
)
.unwrap();
assert_eq!(res, Some(vec![b"line1\n".to_vec(), b"line2\n".to_vec()]));
ann.annotations_cache
.insert(p1_key.clone(), vec![vec![p1_key.clone()]; 2]);
let ready = ann.process_pending(&p1_key).unwrap();
assert_eq!(ready, Vec::<KnitKey>::new());
assert!(!ann.pending_deltas.contains_key(&p1_key));
assert!(ann.pending_annotation.contains_key(&p2_key));
assert_eq!(
ann.pending_annotation[&p2_key],
vec![(rev_key.clone(), vec![p1_key.clone(), p2_key.clone()])]
);
let raw_p2 = fulltext_raw(b"p2-id", &[], false);
ann.expand_record(
p2_key.clone(),
vec![],
None,
raw_p2,
KnitMethod::Fulltext,
false,
)
.unwrap();
ann.annotations_cache.insert(p2_key.clone(), vec![]);
let ready = ann.process_pending(&p2_key).unwrap();
assert_eq!(ready, vec![rev_key.clone()]);
assert!(ann.pending_annotation.is_empty());
assert!(ann.pending_deltas.is_empty());
}
struct StaticBasis {
lines: Vec<Vec<u8>>,
}
impl BasisVfBridge for StaticBasis {
fn get_basis_lines(
&self,
_compression_parent: &[Vec<u8>],
) -> Result<Vec<Vec<u8>>, AdapterError> {
Ok(self.lines.clone())
}
}
#[test]
fn kndx_index_total_build_size_walks_compression_chain() {
let idx = make_kndx_index("filename", &[]);
let key_a: KnitKey = vec![b"a".to_vec()];
let key_b: KnitKey = vec![b"b".to_vec()];
let key_c: KnitKey = vec![b"c".to_vec()];
let key_d: KnitKey = vec![b"d".to_vec()];
let mut positions = std::collections::HashMap::new();
positions.insert(key_a.clone(), fulltext_pos("p", 0, 100));
positions.insert(key_b.clone(), delta_pos("p", 100, 21, key_a.clone()));
positions.insert(key_c.clone(), delta_pos("p", 121, 35, key_b.clone()));
positions.insert(key_d.clone(), delta_pos("p", 156, 12, key_b.clone()));
assert_eq!(idx.get_total_build_size(&[key_a.clone()], &positions), 100);
assert_eq!(idx.get_total_build_size(&[key_b.clone()], &positions), 121);
assert_eq!(idx.get_total_build_size(&[key_c.clone()], &positions), 156);
assert_eq!(
idx.get_total_build_size(&[key_b.clone(), key_c.clone()], &positions),
156
);
assert_eq!(idx.get_total_build_size(&[key_d.clone()], &positions), 133);
assert_eq!(idx.get_total_build_size(&[key_c, key_d], &positions), 168);
}
#[test]
fn encode_graph_index_record_rejects_delta_in_non_delta_index() {
let err = encode_graph_index_record(false, 0, 10, KnitMethod::LineDelta, true, false, &[])
.unwrap_err();
assert!(matches!(err, KnitError::Corrupt(_)));
}
#[test]
fn encode_graph_index_record_rejects_parents_in_parentless_index() {
let err = encode_graph_index_record(
false,
0,
10,
KnitMethod::Fulltext,
false,
false,
&[vec![b"p".to_vec()]],
)
.unwrap_err();
assert!(matches!(err, KnitError::Corrupt(_)));
}
#[test]
fn encode_graph_index_record_fulltext_no_parents() {
let (value, refs) =
encode_graph_index_record(true, 123, 45, KnitMethod::Fulltext, true, true, &[])
.unwrap();
assert_eq!(value, b"N123 45");
assert_eq!(refs, vec![Vec::<KnitKey>::new(), Vec::<KnitKey>::new()]);
}
#[test]
fn encode_graph_index_record_line_delta_uses_first_parent_as_compression_parent() {
let parent_a: KnitKey = vec![b"file".to_vec(), b"a".to_vec()];
let parent_b: KnitKey = vec![b"file".to_vec(), b"b".to_vec()];
let (value, refs) = encode_graph_index_record(
false,
10,
20,
KnitMethod::LineDelta,
true,
true,
&[parent_a.clone(), parent_b.clone()],
)
.unwrap();
assert_eq!(value, b" 10 20");
assert_eq!(refs, vec![vec![parent_a.clone(), parent_b], vec![parent_a]]);
}
#[test]
fn encode_graph_index_record_parentless_index_has_single_refs_column() {
let (value, refs) =
encode_graph_index_record(false, 5, 7, KnitMethod::Fulltext, false, false, &[])
.unwrap();
assert_eq!(value, b" 5 7");
assert!(refs.is_empty());
}
#[test]
fn ft_annotated_to_unannotated_strips_origins() {
let raw = fulltext_raw(b"rev-id", &[b"line1\n", b"line2\n"], false);
let key = vec![b"rev-id".to_vec()];
let input = adapter_input(&key, &raw, false, None, "knit-annotated-ft-gz");
let out = FtAnnotatedToUnannotated
.get_bytes(&input, "knit-ft-gz", None)
.unwrap();
match out {
KnitAdapterOutput::RawBytes(bytes) => {
let plain_lines = extract_plain_fulltext_lines(&bytes, false).unwrap();
assert_eq!(plain_lines, vec![b"line1\n".to_vec(), b"line2\n".to_vec()]);
}
_ => panic!("expected RawBytes"),
}
}
#[test]
fn ft_annotated_to_unannotated_rejects_text_target() {
let raw = fulltext_raw(b"rev-id", &[b"x\n"], false);
let key = vec![b"rev-id".to_vec()];
let input = adapter_input(&key, &raw, false, None, "knit-annotated-ft-gz");
let err = FtAnnotatedToUnannotated
.get_bytes(&input, "fulltext", None)
.unwrap_err();
assert!(matches!(err, AdapterError::Unavailable { .. }));
}
#[test]
fn ft_annotated_to_fulltext_returns_joined() {
let raw = fulltext_raw(b"rev-id", &[b"a\n", b"b\n"], false);
let key = vec![b"rev-id".to_vec()];
let input = adapter_input(&key, &raw, false, None, "knit-annotated-ft-gz");
let out = FtAnnotatedToFullText
.get_bytes(&input, "fulltext", None)
.unwrap();
assert_eq!(
out,
KnitAdapterOutput::Text(KnitTextResult::Bytes(b"a\nb\n".to_vec()))
);
}
#[test]
fn ft_annotated_to_fulltext_returns_lines_for_chunked() {
let raw = fulltext_raw(b"rev-id", &[b"a\n", b"b\n"], false);
let key = vec![b"rev-id".to_vec()];
let input = adapter_input(&key, &raw, false, None, "knit-annotated-ft-gz");
let out = FtAnnotatedToFullText
.get_bytes(&input, "chunked", None)
.unwrap();
assert_eq!(
out,
KnitAdapterOutput::Text(KnitTextResult::Lines(vec![
b"a\n".to_vec(),
b"b\n".to_vec()
]))
);
}
#[test]
fn delta_annotated_to_fulltext_requires_basis() {
let raw = delta_raw_annotated(
b"rev-id",
&[DeltaHunk {
start: 0,
end: 0,
count: 1,
lines: vec![(b"rev-id".to_vec(), b"x\n".to_vec())],
}],
);
let key = vec![b"rev-id".to_vec()];
let parents = vec![vec![b"parent-id".to_vec()]];
let input = adapter_input(&key, &raw, false, Some(&parents), "knit-annotated-delta-gz");
let err = DeltaAnnotatedToFullText
.get_bytes(&input, "fulltext", None)
.unwrap_err();
assert!(matches!(err, AdapterError::Knit(KnitError::Corrupt(_))));
}
#[test]
fn lookup_adapter_finds_all_six_pairs() {
assert!(lookup_adapter("knit-annotated-ft-gz", "knit-ft-gz").is_some());
assert!(lookup_adapter("knit-annotated-delta-gz", "knit-delta-gz").is_some());
assert!(lookup_adapter("knit-annotated-ft-gz", "fulltext").is_some());
assert!(lookup_adapter("knit-ft-gz", "fulltext").is_some());
assert!(lookup_adapter("knit-annotated-delta-gz", "fulltext").is_some());
assert!(lookup_adapter("knit-delta-gz", "fulltext").is_some());
assert!(lookup_adapter("knit-ft-gz", "junk").is_none());
}
#[test]
fn delta_annotated_to_fulltext_applies_delta_with_basis() {
let raw = delta_raw_annotated(
b"child",
&[DeltaHunk {
start: 0,
end: 0,
count: 1,
lines: vec![(b"child".to_vec(), b"X\n".to_vec())],
}],
);
let key = vec![b"child".to_vec()];
let parents = vec![vec![b"parent".to_vec()]];
let input = adapter_input(&key, &raw, false, Some(&parents), "knit-annotated-delta-gz");
let basis = StaticBasis {
lines: vec![b"a\n".to_vec(), b"b\n".to_vec()],
};
let out = DeltaAnnotatedToFullText
.get_bytes(&input, "fulltext", Some(&basis))
.unwrap();
assert_eq!(
out,
KnitAdapterOutput::Text(KnitTextResult::Bytes(b"X\na\nb\n".to_vec()))
);
}
fn knit_key(s: &str) -> KnitKey {
vec![s.as_bytes().to_vec()]
}
#[test]
fn prepare_dedup_records_keeps_last_per_key() {
let inputs = vec![
AddRecordInput {
key: knit_key("a"),
options: b"fulltext".to_vec(),
pos: 0,
size: 10,
parents: vec![],
},
AddRecordInput {
key: knit_key("a"),
options: b"line-delta".to_vec(),
pos: 10,
size: 5,
parents: vec![knit_key("p")],
},
];
let prepared = prepare_dedup_records(&inputs, true, true).unwrap();
assert_eq!(prepared.len(), 1);
assert_eq!(prepared[0].key, knit_key("a"));
assert_eq!(prepared[0].value, b" 10 5");
}
#[test]
fn prepare_dedup_records_detects_no_eol() {
let inputs = vec![AddRecordInput {
key: knit_key("a"),
options: b"fulltext,no-eol".to_vec(),
pos: 0,
size: 7,
parents: vec![],
}];
let prepared = prepare_dedup_records(&inputs, true, false).unwrap();
assert_eq!(prepared[0].value, b"N0 7");
}
#[test]
fn verify_dedup_records_passes_consistent_entries() {
let prepared = vec![PreparedAddRecord {
key: knit_key("a"),
value: b" 0 10".to_vec(),
node_refs: vec![vec![knit_key("p")]],
}];
let existing = vec![ExistingAddRecord {
key: knit_key("a"),
value: b" 0 10".to_vec(),
parents: vec![knit_key("p")],
}];
let to_remove = verify_dedup_records(&prepared, &existing).unwrap();
assert!(to_remove.contains(&knit_key("a")));
}
#[test]
fn verify_dedup_records_rejects_mismatched_flag() {
let prepared = vec![PreparedAddRecord {
key: knit_key("a"),
value: b"N0 10".to_vec(),
node_refs: vec![vec![]],
}];
let existing = vec![ExistingAddRecord {
key: knit_key("a"),
value: b" 0 10".to_vec(),
parents: vec![],
}];
let err = verify_dedup_records(&prepared, &existing).unwrap_err();
assert!(matches!(err, KnitError::Corrupt(_)));
}
#[test]
fn verify_dedup_records_rejects_mismatched_parents() {
let prepared = vec![PreparedAddRecord {
key: knit_key("a"),
value: b" 0 10".to_vec(),
node_refs: vec![vec![knit_key("p")]],
}];
let existing = vec![ExistingAddRecord {
key: knit_key("a"),
value: b" 0 10".to_vec(),
parents: vec![knit_key("q")],
}];
let err = verify_dedup_records(&prepared, &existing).unwrap_err();
assert!(matches!(err, KnitError::Corrupt(_)));
}
#[derive(Default)]
struct CapturingCallback {
batches: std::rc::Rc<std::cell::RefCell<Vec<Vec<KnitKey>>>>,
}
impl AddCallback for CapturingCallback {
fn call(
&mut self,
entries: &[(KnitKey, Vec<u8>, Vec<Vec<KnitKey>>)],
_has_parents: bool,
) -> Result<(), KnitError> {
self.batches
.borrow_mut()
.push(entries.iter().map(|(k, _, _)| k.clone()).collect());
Ok(())
}
}
fn graph_index_with_capture() -> (
KnitGraphIndex<CapturingCallback>,
std::rc::Rc<std::cell::RefCell<Vec<Vec<KnitKey>>>>,
) {
let mut idx = KnitGraphIndex::new(true, true);
let batches = std::rc::Rc::new(std::cell::RefCell::new(Vec::new()));
idx.set_add_callback(CapturingCallback {
batches: batches.clone(),
});
(idx, batches)
}
#[test]
fn knit_graph_index_encode_and_dispatch_calls_back() {
let (mut idx, batches) = graph_index_with_capture();
idx.encode_and_dispatch(
vec![(knit_key("a"), b"fulltext".to_vec(), 0, 10, vec![])],
false,
)
.unwrap();
assert_eq!(batches.borrow().as_slice(), &[vec![knit_key("a")]]);
assert!(idx.missing_compression_parents.is_empty());
}
#[test]
fn knit_graph_index_read_only_without_callback_errors() {
let mut idx: KnitGraphIndex<CapturingCallback> = KnitGraphIndex::new(true, true);
let err = idx
.encode_and_dispatch(
vec![(knit_key("a"), b"fulltext".to_vec(), 0, 10, vec![])],
false,
)
.unwrap_err();
assert!(matches!(err, KnitError::ReadOnly));
}
#[test]
fn knit_graph_index_tracks_then_clears_missing_compression_parent() {
let (mut idx, _batches) = graph_index_with_capture();
idx.encode_and_dispatch(
vec![(
knit_key("child"),
b"line-delta".to_vec(),
0,
10,
vec![knit_key("base")],
)],
true,
)
.unwrap();
assert_eq!(
idx.missing_compression_parents,
std::iter::once(knit_key("base")).collect()
);
idx.encode_and_dispatch(
vec![(knit_key("base"), b"fulltext".to_vec(), 10, 10, vec![])],
true,
)
.unwrap();
assert!(idx.missing_compression_parents.is_empty());
}
#[test]
fn knit_graph_index_tracks_external_parent_refs() {
let (mut idx, _batches) = graph_index_with_capture();
idx.enable_key_dependencies(false);
idx.encode_and_dispatch(
vec![(
knit_key("a"),
b"fulltext".to_vec(),
0,
10,
vec![knit_key("missing")],
)],
false,
)
.unwrap();
let unsatisfied: std::collections::HashSet<KnitKey> =
idx.unsatisfied_refs().cloned().collect();
assert_eq!(unsatisfied, std::iter::once(knit_key("missing")).collect());
idx.satisfy_refs_for_keys(std::iter::once(knit_key("missing")));
assert_eq!(idx.unsatisfied_refs().count(), 0);
}
#[test]
fn knit_graph_index_update_missing_compression_parents_skips_present() {
let mut idx: KnitGraphIndex<CapturingCallback> = KnitGraphIndex::new(true, true);
let present: std::collections::HashSet<KnitKey> =
std::iter::once(knit_key("here")).collect();
idx.update_missing_compression_parents(vec![knit_key("here"), knit_key("gone")], &present);
assert_eq!(
idx.missing_compression_parents,
std::iter::once(knit_key("gone")).collect()
);
}
}