use super::*;
fn naive_count_match_length(src: &[u8], left: usize, right: usize) -> usize {
let max_len = src
.len()
.saturating_sub(right)
.min(src.len().saturating_sub(left));
let mut matched = 0usize;
while matched < max_len && src[left + matched] == src[right + matched] {
matched += 1;
}
matched
}
#[test]
fn word_at_a_time_match_count_matches_naive_for_overlapping_positions() {
let mut src = Vec::with_capacity(96);
while src.len() < 96 {
src.extend_from_slice(b"abc123abcXYZabc123abcxy");
}
src.truncate(96);
src[31] = b'Q';
src[63] = b'R';
src[95] = b'S';
for left in 0..src.len() {
for right in 0..src.len() {
assert_eq!(
count_match_length(&src, left, right),
naive_count_match_length(&src, left, right),
"left={left} right={right}",
);
}
}
}
#[test]
fn word_at_a_time_match_count_handles_tail_mismatches_on_word_boundaries() {
let src = b"01234567012345670123456001234567";
assert_eq!(count_match_length(src, 0, 8), 15);
assert_eq!(count_match_length(src, 0, 16), 7);
assert_eq!(count_match_length(src, 8, 24), 8);
}
#[test]
fn plans_matches_from_an_external_prefix() {
let prefix =
b"GET /v2/customers/10000/orders?status=open&limit=50\n{\"customer_id\":10000,\"status\":\"open\"}\n";
let src = b"GET /v2/customers/10000/orders?status=open&limit=50\n{\"customer_id\":10000,\"status\":\"open\"}\n";
let plan = plan_sequences_with_params_and_prefix(
src,
prefix,
RepeatOffsets::default(),
MatchFinderParameters::default(),
)
.unwrap();
assert!(!plan.sequences.is_empty());
assert_eq!(plan.literals.len(), 0);
}
#[test]
fn external_prefix_matcher_supports_cross_boundary_candidates() {
let prefix = b"xxab";
let src = b"ababababzz";
let plan = plan_sequences_with_params_and_prefix(
src,
prefix,
RepeatOffsets::default(),
MatchFinderParameters::default(),
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, 2);
assert!(plan.sequences[0].match_length >= 8);
}
#[test]
fn uses_the_segmented_matcher_for_a_later_non_empty_prefix_slot() {
let prefix = b"xxab";
let src = b"ababababzz";
let plan = plan_sequences_with_params_and_prefixes(
src,
&[b"", prefix],
RepeatOffsets::default(),
MatchFinderParameters::default(),
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, 2);
}
#[test]
fn segmented_prefix_chain_supports_cross_segment_candidates() {
let src = b"ababababzz";
let plan = plan_sequences_with_params_and_prefixes(
src,
&[b"xx", b"ab"],
RepeatOffsets::default(),
MatchFinderParameters::default(),
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, 2);
assert!(plan.sequences[0].match_length >= 8);
}
#[test]
fn binary_tree_segmented_prefix_planner_finds_dictionary_matches() {
let src = b"ababababzz";
let plan = plan_sequences_for_block(
src,
&[b"xx", b"ab"],
RepeatOffsets::default(),
MatchFinderParameters {
parser_strategy: ParserStrategy::BinaryTreeLazy2,
search_depth: 8,
dictionary_search_depth: 8,
..MatchFinderParameters::default()
},
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, 2);
assert!(plan.sequences[0].match_length >= 8);
}
#[test]
fn btopt_segmented_prefix_planner_finds_dictionary_matches() {
let src = b"customer=0012|region=us-east|tier=gold|invoice=42";
let prefixes: [&[u8]; 2] = [b"customer=0012|", b"region=us-east|tier=gold|"];
let plan = plan_sequences_for_block(
src,
&prefixes,
RepeatOffsets::default(),
MatchFinderParameters {
parser_strategy: ParserStrategy::BinaryTreeOpt,
search_depth: 12,
dictionary_search_depth: 12,
good_enough_match_length: 32,
..MatchFinderParameters::default()
},
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert!(raw_offset >= prefixes.iter().map(|prefix| prefix.len()).sum::<usize>() as u32);
}
#[test]
fn no_prefix_planner_keeps_finding_repeated_sequences() {
let src = b"pattern-0123456789-pattern-0123456789-pattern-0123456789";
let plan = plan_sequences_with_params(
src,
RepeatOffsets::default(),
MatchFinderParameters::default(),
)
.unwrap();
assert!(!plan.sequences.is_empty());
}
#[test]
fn reusable_sequence_plan_keeps_allocated_buffers() {
let large = b"pattern-0123456789-pattern-0123456789-pattern-0123456789-pattern-0123456789";
let small = b"pattern-0123456789-pattern-0123456789";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::Fast,
fast_search_step: 2,
..MatchFinderParameters::default()
};
let mut plan = SequencePlan::default();
plan_sequences_for_block_into(&mut plan, large, &[&[]], RepeatOffsets::default(), params)
.unwrap();
assert!(!plan.sequences.is_empty());
let literals_ptr = plan.literals.as_ptr();
let sequences_ptr = plan.sequences.as_ptr();
let literals_capacity = plan.literals.capacity();
let sequences_capacity = plan.sequences.capacity();
plan_sequences_for_block_into(&mut plan, small, &[&[]], RepeatOffsets::default(), params)
.unwrap();
assert_eq!(plan.literals.as_ptr(), literals_ptr);
assert_eq!(plan.sequences.as_ptr(), sequences_ptr);
assert_eq!(plan.literals.capacity(), literals_capacity);
assert_eq!(plan.sequences.capacity(), sequences_capacity);
assert!(!plan.sequences.is_empty());
}
#[test]
fn contiguous_block_state_reuses_prior_block_history() {
let block = b"pattern-0123456789-pattern-0123456789";
let mut src = Vec::new();
src.extend_from_slice(block);
src.extend_from_slice(block);
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::Fast,
fast_search_step: 2,
..MatchFinderParameters::default()
};
let mut state = ContiguousBlockMatchState::new(src.len(), params);
let first = plan_sequences_for_contiguous_block(
&src[..block.len()],
0,
RepeatOffsets::default(),
params,
128 * 1024,
&mut state,
)
.unwrap();
let second = plan_sequences_for_contiguous_block(
&src,
block.len(),
first.repeat_offsets,
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!second.sequences.is_empty());
assert!(second.literals.len() < block.len());
}
#[test]
fn greedy_row_contiguous_block_keeps_rep1_before_searching_regular_candidates() {
let src = b"abcde12345abcde12345TAILTAILTAIL";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::GreedyRow,
search_log: 5,
min_match: 5,
lazy_search_depth: 0,
..MatchFinderParameters::default()
};
let mut state = ContiguousBlockMatchState::new(src.len(), params);
state.insert_range(src, 0, 10);
let plan = plan_sequences_for_contiguous_block(
src,
10,
RepeatOffsets::from_values([10, 64, 8]),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
assert_eq!(plan.sequences[0].literal_length, 1);
assert_eq!(plan.sequences[0].match_length, 9);
assert!(
!plan
.trace_row_searches
.iter()
.any(|search| search.pos == 10),
"GreedyRow should store the baseline rep1 without a regular row search"
);
let mut repeat_offsets = RepeatOffsets::from_values([10, 64, 8]);
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, 10);
}
#[test]
fn greedy_row_contiguous_block_codes_regular_store_as_rep2_when_raw_offset_matches_rep2() {
let src = b"Zabcde123450abcde12345TAILTAILTAIL";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::GreedyRow,
search_log: 5,
min_match: 5,
lazy_search_depth: 0,
..MatchFinderParameters::default()
};
let mut state = ContiguousBlockMatchState::new(src.len(), params);
state.insert_range(src, 0, 11);
let plan = plan_sequences_for_contiguous_block(
src,
11,
RepeatOffsets::from_values([20, 11, 8]),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
assert_eq!(plan.sequences[0].literal_length, 1);
assert_eq!(plan.sequences[0].match_length, 10);
assert_eq!(plan.sequences[0].offset_value, 2);
assert_ne!(plan.sequences[0].offset_value, explicit_offbase(11));
let mut repeat_offsets = RepeatOffsets::from_values([20, 11, 8]);
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, 11);
assert_eq!(repeat_offsets.values()[0], 11);
}
#[test]
fn row_collect_match_indices_group_width_one_keeps_rotated_order_and_low_limit_break() {
let context = RowHashContext {
total_hash_bits: 0,
row_entries: 16,
row_mask: 15,
group_width: 1,
};
let location = RowHashLocation {
rel_row: 0,
tag: 0xAB,
head_index: 7,
head_grouped: 7,
insert_index: row_next_insert_index(7, context.row_mask),
};
let mut row = [0u32; 16];
let mut tag_row = [0u8; 16];
tag_row[0] = location.head_index as u8;
for (slot, index) in [(7usize, 100u32), (9, 90), (15, 80), (1, 70)] {
tag_row[slot] = location.tag;
row[slot] = index;
}
let mut match_positions = [0usize; ROW_HASH_MAX_ENTRIES];
let mut match_buffer = [NO_POS; ROW_HASH_MAX_ENTRIES];
let (num_matches, attempts_left) = row_collect_match_indices(
&row,
&tag_row,
location,
context,
85,
200,
8,
Some(&mut match_positions),
&mut match_buffer,
core::ptr::null(),
);
assert_eq!(num_matches, 2);
assert_eq!(attempts_left, 6);
assert_eq!(&match_positions[..num_matches], &[7, 9]);
assert_eq!(&match_buffer[..num_matches], &[100u32, 90]);
let mut match_positions = [0usize; ROW_HASH_MAX_ENTRIES];
let mut match_buffer = [NO_POS; ROW_HASH_MAX_ENTRIES];
let (num_matches, _) = row_collect_match_indices(
&row,
&tag_row,
location,
context,
85,
95,
8,
Some(&mut match_positions),
&mut match_buffer,
core::ptr::null(),
);
assert_eq!(
num_matches, 1,
"an entry at or beyond search_pos is not a match"
);
assert_eq!(&match_buffer[..num_matches], &[90u32]);
}
#[test]
fn prefixed_block_state_reuses_prior_source_history() {
let prefix = b"dictionary-only-prefix";
let block = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ012345";
let mut src = Vec::new();
src.extend_from_slice(block);
src.extend_from_slice(block);
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::Fast,
fast_search_step: 2,
..MatchFinderParameters::default()
};
let mut state = PrefixedBlockMatchState::new(prefix, src.len(), params);
let first = plan_sequences_for_prefixed_contiguous_block(
prefix,
&src[..block.len()],
0,
RepeatOffsets::default(),
params,
128 * 1024,
&mut state,
)
.unwrap();
let second = plan_sequences_for_prefixed_contiguous_block(
prefix,
&src,
block.len(),
first.repeat_offsets,
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!second.sequences.is_empty());
let mut repeat_offsets = first.repeat_offsets;
let raw_offset = repeat_offsets.resolve(&second.sequences[0]).unwrap();
assert_eq!(raw_offset, block.len() as u32);
}
#[test]
fn generic_planner_extends_source_matches_back_to_the_anchor() {
let src = b"x!abcdefghijklmnopx!abcdefghijklmnop";
let plan = plan_sequences_with_params(
src,
RepeatOffsets::default(),
MatchFinderParameters::default(),
)
.unwrap();
assert!(!plan.sequences.is_empty());
assert_eq!(plan.literals, b"x!abcdefghijklmnop");
assert_eq!(plan.sequences[0].literal_length, 18);
assert_eq!(plan.sequences[0].match_length, 18);
}
#[test]
fn generic_prefix_planner_extends_dictionary_matches_back_to_the_anchor() {
let prefix = b"abcXYZ";
let src = b"abcXYZrest";
let plan = plan_sequences_with_params_and_prefix(
src,
prefix,
RepeatOffsets::default(),
MatchFinderParameters::default(),
)
.unwrap();
assert!(!plan.sequences.is_empty());
assert_eq!(plan.literals, b"rest");
assert_eq!(plan.sequences[0].literal_length, 0);
assert_eq!(plan.sequences[0].match_length, 6);
}
#[test]
fn lazy_family_chains_immediate_rep2_after_storing_a_match() {
let src = b"abcdWXYZabcdWXYZWXYZWXYZWXYZWXYZ";
for (strategy, lazy_search_depth) in [
(ParserStrategy::Greedy, 0),
(ParserStrategy::Lazy, 1),
(ParserStrategy::Lazy2, 2),
(ParserStrategy::BinaryTreeLazy2, 2),
] {
let plan = plan_sequences_for_block(
src,
&[&[]],
RepeatOffsets::from_values([4, 64, 8]),
MatchFinderParameters {
parser_strategy: strategy,
lazy_search_depth,
..MatchFinderParameters::default()
},
)
.unwrap();
assert!(
plan.sequences.len() >= 2,
"expected an immediate rep2 chain for {strategy:?}"
);
let mut repeat_offsets = RepeatOffsets::from_values([4, 64, 8]);
let first_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
let second_offset = repeat_offsets.resolve(&plan.sequences[1]).unwrap();
assert_eq!(first_offset, 8, "unexpected first offset for {strategy:?}");
assert_eq!(second_offset, 4, "expected rep2 chain for {strategy:?}");
assert_eq!(plan.sequences[1].literal_length, 0);
}
}
#[test]
fn lazy_family_row_contiguous_blocks_chain_immediate_rep2_after_storing_a_match() {
let src = b"abcdWXYZabcdWXYZWXYZWXYZWXYZWXYZ";
for (strategy, lazy_search_depth) in [
(ParserStrategy::GreedyRow, 0),
(ParserStrategy::LazyRow, 1),
(ParserStrategy::Lazy2Row, 2),
] {
let params = MatchFinderParameters {
parser_strategy: strategy,
lazy_search_depth,
..MatchFinderParameters::default()
};
let mut state = ContiguousBlockMatchState::new(src.len(), params);
state.insert_range(src, 0, 8);
let plan = plan_sequences_for_contiguous_block(
src,
8,
RepeatOffsets::from_values([4, 64, 8]),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(
plan.sequences.len() >= 2,
"expected an immediate rep2 chain for {strategy:?}"
);
let mut repeat_offsets = RepeatOffsets::from_values([4, 64, 8]);
let first_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
let second_offset = repeat_offsets.resolve(&plan.sequences[1]).unwrap();
assert_eq!(first_offset, 8, "unexpected first offset for {strategy:?}");
assert_eq!(second_offset, 4, "expected rep2 chain for {strategy:?}");
assert_eq!(plan.sequences[1].literal_length, 0);
}
}
#[test]
fn lazy_family_prefix_path_chains_immediate_rep2_after_storing_a_match() {
let prefix = b"abcdWXYZ";
let src = b"abcdWXYZWXYZWXYZWXYZWXYZ";
for (strategy, lazy_search_depth) in [
(ParserStrategy::Greedy, 0),
(ParserStrategy::Lazy, 1),
(ParserStrategy::Lazy2, 2),
(ParserStrategy::GreedyRow, 0),
(ParserStrategy::LazyRow, 1),
(ParserStrategy::Lazy2Row, 2),
(ParserStrategy::BinaryTreeLazy2, 2),
] {
let plan = plan_sequences_for_block(
src,
&[prefix],
RepeatOffsets::from_values([4, 64, 8]),
MatchFinderParameters {
parser_strategy: strategy,
lazy_search_depth,
..MatchFinderParameters::default()
},
)
.unwrap();
assert!(
plan.sequences.len() >= 2,
"expected an immediate rep2 chain with prefix history for {strategy:?}"
);
let mut repeat_offsets = RepeatOffsets::from_values([4, 64, 8]);
let first_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
let second_offset = repeat_offsets.resolve(&plan.sequences[1]).unwrap();
assert_eq!(first_offset, prefix.len() as u32);
assert_eq!(second_offset, 4, "expected rep2 chain for {strategy:?}");
assert_eq!(plan.sequences[0].literal_length, 0);
assert_eq!(plan.sequences[1].literal_length, 0);
}
}
#[test]
fn prepared_fast_and_double_fast_dict_tables_preserve_zero_index_matches() {
let prefix = b"abcdWXYZabcdWXYZ";
for strategy in [ParserStrategy::Fast, ParserStrategy::DoubleFast] {
let params = MatchFinderParameters {
parser_strategy: strategy,
fast_search_step: 2,
secondary_hash_bits: 16,
..MatchFinderParameters::default()
};
let prepared = build_prepared_dictionary_match_state(prefix, params)
.expect("prepared dictionary state must build");
match prepared {
PreparedDictionaryMatchState::Fast(ref prepared) => {
assert_eq!(prepared.candidate_at(prefix, 0), Some(0));
}
PreparedDictionaryMatchState::DoubleFast(ref prepared) => {
assert_eq!(prepared.long_candidate_at(prefix, 0), Some(0));
assert_eq!(prepared.short_candidate_at(prefix, 0), Some(0));
}
_ => panic!("unexpected prepared dictionary state for {strategy:?}"),
}
}
}
#[test]
fn prepared_row_dict_state_uses_dictionary_boundary_offsets() {
let prefix = b"customer=0012|region=us-east|tier=gold|";
let src = b"customer=0012|region=us-east|tier=gold|invoice=42";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::GreedyRow,
search_log: 5,
min_match: 5,
..MatchFinderParameters::default()
};
let prepared = build_prepared_dictionary_match_state(prefix, params)
.expect("prepared row dictionary state must build");
let mut state = PrefixedBlockMatchState::new_with_prepared_match_state(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
Some(&prepared),
);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
0,
RepeatOffsets::default(),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, prefix.len() as u32);
}
#[test]
fn prepared_chain_dict_state_uses_dictionary_boundary_offsets() {
let prefix = b"customer=0012|region=us-east|tier=gold|";
let src = b"customer=0012|region=us-east|tier=gold|invoice=42";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::Greedy,
search_log: 5,
min_match: 5,
..MatchFinderParameters::default()
};
let prepared = build_prepared_dictionary_match_state(prefix, params)
.expect("prepared chain dictionary state must build");
let mut state = PrefixedBlockMatchState::new_with_prepared_match_state(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
Some(&prepared),
);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
0,
RepeatOffsets::default(),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, prefix.len() as u32);
}
#[test]
fn row_dict_match_state_prefers_longer_dict_match_over_shorter_source_match() {
let prefix = b"ABCDEFGHIJ";
let src = b"ABCDE12345ABCDEFGHIJabcdefgh";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::LazyRow,
search_log: 5,
min_match: 5,
..MatchFinderParameters::default()
};
let mut prefix_finder =
RowHashFinder::new(params.hash_bits, params.search_log, params.min_match);
prefix_finder.hash_salt = 0;
prefix_finder.insert_prefix(prefix);
let mut src_finder = RowHashFinder::new(params.hash_bits, params.search_log, params.min_match);
src_finder.insert_range(src, 0, 10);
let mut trace_first_row_contest = None;
let mut trace_row_searches = Vec::new();
let (candidate, source) = best_row_dict_match_state_regular_match_core::<true, false>(
prefix,
src,
10,
params,
0,
0,
&prefix_finder,
&mut src_finder,
false,
&mut trace_first_row_contest,
&mut trace_row_searches,
None,
)
.unwrap();
assert_eq!(source, SequenceTraceMatchSource::Dict);
assert_eq!(candidate.length, prefix.len());
assert_eq!(candidate.offset, prefix.len() + 10);
if let Some(contest) = trace_first_row_contest {
assert_eq!(contest.winner, SequenceTraceMatchSource::Dict);
assert!(contest.dict_length > contest.source_length);
}
}
#[test]
fn row_dict_match_state_keeps_source_match_when_source_candidate_is_valid() {
let prefix = b"mnopabcdWXYZ";
let src = b"abcdWXYZuvabcdWXYZtailtailtail";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::GreedyRow,
search_log: 5,
min_match: 5,
..MatchFinderParameters::default()
};
let mut state = PrefixedBlockMatchState::new_with_mode(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
);
state.insert_range(src, 0, 10);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
10,
RepeatOffsets::default(),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, 10);
assert_eq!(
plan.trace_match_sources.first().copied(),
Some(SequenceTraceMatchSource::Source)
);
if let Some(contest) = plan.trace_first_row_contest {
assert_eq!(contest.winner, SequenceTraceMatchSource::Source);
assert!(contest.source_length >= contest.dict_length);
}
assert!(
!plan
.trace_match_sources
.contains(&SequenceTraceMatchSource::Prefix)
);
}
#[test]
fn row_dict_match_state_tied_lengths_keep_source_match() {
let prefix = b"ABCDEFGHIJ";
let src = b"ABCDEFGHIJABCDEFGHIJtailtailtail";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::GreedyRow,
search_log: 5,
min_match: 5,
..MatchFinderParameters::default()
};
let mut state = PrefixedBlockMatchState::new_with_mode(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
);
state.insert_range(src, 0, 10);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
10,
RepeatOffsets::default(),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, 10);
assert_eq!(
plan.trace_match_sources.first().copied(),
Some(SequenceTraceMatchSource::Source)
);
if let Some(contest) = plan.trace_first_row_contest {
assert_eq!(contest.winner, SequenceTraceMatchSource::Source);
assert_eq!(contest.source_length, contest.dict_length);
}
}
#[test]
fn row_dict_match_state_catch_up_respects_prefix_low() {
let prefix = b"ABCDWXYZQRST";
let src = b"ABCDWXYZQRSTabcdefghijklmnop";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::GreedyRow,
search_log: 5,
min_match: 4,
..MatchFinderParameters::default()
};
let plan_within_window = {
let mut state = PrefixedBlockMatchState::new_with_mode(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
);
plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
0,
RepeatOffsets::default(),
params,
8 + src.len(),
&mut state,
)
.unwrap()
};
assert!(!plan_within_window.sequences.is_empty());
assert_eq!(plan_within_window.sequences[0].literal_length, 0);
assert_eq!(plan_within_window.sequences[0].match_length, 12);
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets
.resolve(&plan_within_window.sequences[0])
.unwrap();
assert_eq!(raw_offset, 12);
assert_eq!(
plan_within_window.trace_match_sources.first().copied(),
Some(SequenceTraceMatchSource::Dict)
);
let plan_past_window = {
let mut state = PrefixedBlockMatchState::new_with_mode(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
);
plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
0,
RepeatOffsets::default(),
params,
8,
&mut state,
)
.unwrap()
};
assert!(
plan_past_window.sequences.is_empty(),
"an 8-byte window cannot reach a match 12 bytes back, but took {:?}",
plan_past_window.sequences,
);
}
#[test]
fn prepared_row_dict_state_use_rep1_across_dictionary_boundary() {
let prefix = b"abcdefghij";
let src = b"ZabcdefghijTAILTAIL";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::GreedyRow,
search_log: 5,
min_match: 5,
..MatchFinderParameters::default()
};
let prepared = build_prepared_dictionary_match_state(prefix, params)
.expect("prepared row dictionary state must build");
let mut state = PrefixedBlockMatchState::new_with_prepared_match_state(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
Some(&prepared),
);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
0,
RepeatOffsets::from_values([prefix.len() as u32 + 1, 4, 8]),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
assert_eq!(plan.sequences[0].literal_length, 1);
let mut repeat_offsets = RepeatOffsets::from_values([prefix.len() as u32 + 1, 4, 8]);
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, prefix.len() as u32 + 1);
assert_eq!(
plan.trace_match_sources.first().copied(),
Some(SequenceTraceMatchSource::Rep)
);
assert!(
!plan
.trace_match_sources
.contains(&SequenceTraceMatchSource::Prefix)
);
}
#[test]
fn prepared_row_dict_state_chain_rep2_across_dictionary_boundary() {
let prefix = b"abcdefghABCDEFGH";
let src = b"abcdefghABCDEFGHEFGHEFGHTAILTAIL";
for (strategy, lazy_search_depth) in [
(ParserStrategy::GreedyRow, 0),
(ParserStrategy::LazyRow, 1),
(ParserStrategy::Lazy2Row, 2),
] {
let params = MatchFinderParameters {
parser_strategy: strategy,
search_log: 5,
min_match: 5,
lazy_search_depth,
..MatchFinderParameters::default()
};
let prepared = build_prepared_dictionary_match_state(prefix, params)
.expect("prepared row dictionary state must build");
let mut state = PrefixedBlockMatchState::new_with_prepared_match_state(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
Some(&prepared),
);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
0,
RepeatOffsets::from_values([4, 64, 8]),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(
plan.sequences.len() >= 2,
"expected a regular dict match followed by a rep2 chain for {strategy:?}"
);
assert_eq!(
plan.sequences[0].offset_value,
prefix.len() as u32 + 3,
"expected the first regular match to stay explicit for {strategy:?}"
);
assert_eq!(
plan.sequences[1].offset_value, 1,
"expected the immediate rep2 chain to encode as rep1 for {strategy:?}"
);
let mut repeat_offsets = RepeatOffsets::from_values([4, 64, 8]);
let first_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
let second_offset = repeat_offsets.resolve(&plan.sequences[1]).unwrap();
assert_eq!(first_offset, prefix.len() as u32, "for {strategy:?}");
assert_eq!(second_offset, 4, "for {strategy:?}");
assert_eq!(
plan.trace_match_sources.first().copied(),
Some(SequenceTraceMatchSource::Dict),
"for {strategy:?}"
);
assert_eq!(
plan.trace_match_sources.get(1).copied(),
Some(SequenceTraceMatchSource::Rep),
"for {strategy:?}"
);
assert!(
!plan
.trace_match_sources
.contains(&SequenceTraceMatchSource::Prefix)
);
}
}
#[test]
fn exact_offset_store_keeps_zero_literal_regular_matches_explicit() {
let src = b"abcdabcd";
let mut plan = SequencePlan::default();
let mut anchor = 0usize;
let mut repeat_offsets = RepeatOffsets::from_values([8, 4, 16]);
let raw_offset = store_lazy_sequence_with_offset_value_and_source(
&mut plan,
src,
&mut anchor,
&mut repeat_offsets,
0,
explicit_offbase(4),
4,
SequenceTraceMatchSource::Dict,
)
.unwrap();
assert_eq!(raw_offset, 4);
assert_eq!(plan.sequences.len(), 1);
assert_eq!(plan.sequences[0].literal_length, 0);
assert_eq!(plan.sequences[0].offset_value, 7);
assert_eq!(repeat_offsets.values(), [4, 8, 4]);
}
#[test]
fn chain_dict_match_state_prefers_longer_dict_match_over_shorter_source_match() {
let prefix = b"ABCDEFGHIJ";
let src = b"ABCDE12345ABCDEFGHIJabcdefgh";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::Lazy,
search_log: 5,
min_match: 5,
..MatchFinderParameters::default()
};
let prefix_refs = [prefix.as_slice()];
let prefix_chain = PrefixChain::new(&prefix_refs).unwrap().unwrap();
let mut prefix_finder = MatchFinder::with_chain_log(
prefix.len(),
params.hash_bits,
params.chain_log,
params.min_match,
);
prefix_finder.insert_prefix_chain(prefix_chain, &[]);
let mut src_finder = MatchFinder::with_chain_log(
src.len(),
params.hash_bits,
params.chain_log,
params.min_match,
);
src_finder.insert_range(src, 0, 10);
let search = best_chain_dict_match_state_regular_match(
prefix_chain,
src,
10,
params,
0,
0,
&prefix_finder,
&mut src_finder,
false,
None,
);
let candidate = search.candidate.unwrap();
let source = search.source;
assert_eq!(source, SequenceTraceMatchSource::Dict);
assert_eq!(candidate.length, prefix.len());
assert_eq!(candidate.offset, prefix.len() + 10);
}
#[test]
fn chain_ext_dict_regular_search_uses_unified_prefix_chain_finder() {
let prefix = b"ABCDEFGHIJ";
let src = b"ABCDE12345ABCDEFGHIJabcdefgh";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::Lazy,
search_log: 5,
min_match: 5,
..MatchFinderParameters::default()
};
let prefix_refs = [prefix.as_slice()];
let prefix_chain = PrefixChain::new(&prefix_refs).unwrap().unwrap();
let mut finder = MatchFinder::with_chain_log(
prefix.len(),
params.hash_bits,
params.chain_log,
params.min_match,
);
finder.insert_prefix_chain(prefix_chain, &[]);
let search = best_chain_ext_dict_regular_match(
prefix_chain,
src,
10,
params,
0,
0,
&mut finder,
false,
None,
);
let candidate = search.candidate.unwrap();
assert_eq!(search.source, SequenceTraceMatchSource::Prefix);
assert_eq!(candidate.length, prefix.len());
assert_eq!(candidate.offset, prefix.len() + 10);
}
#[test]
fn prepared_chain_ext_dict_state_reuses_prepared_prefix_tables() {
let prefix = vec![b'a'; 16];
let src = vec![b'a'; 8];
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::Lazy,
..MatchFinderParameters::default()
};
let prepared = build_prepared_dictionary_match_state(&prefix, params)
.expect("prepared chain dictionary state should build");
let state = PrefixedBlockMatchState::new_with_prepared_match_state(
&prefix,
src.len(),
params,
PrefixMatchMode::ExtDict,
Some(&prepared),
);
let PrefixedBlockMatchStateInner::Chain {
prefix_finder,
mut src_finder,
mode,
..
} = state.inner
else {
panic!("expected chain extdict state");
};
assert_eq!(mode, PrefixMatchMode::ExtDict);
assert_eq!(src_finder.next_to_update, prefix_finder.next_to_update);
assert_eq!(
src_finder.insert_and_find_first_index_ext_dict(prefix.len(), &src, 0, false),
Some(7)
);
}
#[test]
fn chain_extdict_lazy_family_reserves_last_8_bytes_as_literals() {
let prefix = b"abcdefghi";
let src = b"abcdefghifghiXYZ";
for (strategy, lazy_search_depth) in [
(ParserStrategy::Greedy, 0),
(ParserStrategy::Lazy, 1),
(ParserStrategy::Lazy2, 2),
] {
let params = MatchFinderParameters {
parser_strategy: strategy,
lazy_search_depth,
..MatchFinderParameters::default()
};
let mut state = PrefixedBlockMatchState::new_with_mode(
prefix,
src.len(),
params,
PrefixMatchMode::ExtDict,
);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
0,
RepeatOffsets::default(),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert_eq!(
plan.sequences.len(),
1,
"expected the final 7 bytes to remain literals for {strategy:?}"
);
assert_eq!(plan.literals, b"fghiXYZ");
assert_eq!(plan.sequences[0].literal_length, 0);
assert_eq!(plan.sequences[0].match_length, prefix.len() as u32);
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, prefix.len() as u32);
assert_eq!(
plan.trace_match_sources.first().copied(),
Some(SequenceTraceMatchSource::Prefix)
);
}
}
#[test]
fn prepared_fast_and_double_fast_dict_state_use_rep1_across_dictionary_boundary() {
let prefix = b"abcdefghij";
let src = b"ZabcdefghijTAIL";
for strategy in [ParserStrategy::Fast, ParserStrategy::DoubleFast] {
let params = MatchFinderParameters {
parser_strategy: strategy,
fast_search_step: 2,
secondary_hash_bits: 16,
..MatchFinderParameters::default()
};
let prepared = build_prepared_dictionary_match_state(prefix, params)
.expect("prepared dictionary state must build");
let mut state = PrefixedBlockMatchState::new_with_prepared_match_state(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
Some(&prepared),
);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
0,
RepeatOffsets::from_values([prefix.len() as u32 + 1, 4, 8]),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
assert_eq!(plan.sequences[0].literal_length, 1);
let mut repeat_offsets = RepeatOffsets::from_values([prefix.len() as u32 + 1, 4, 8]);
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, prefix.len() as u32 + 1);
assert_eq!(
plan.trace_match_sources.first().copied(),
Some(SequenceTraceMatchSource::Rep)
);
assert!(
!plan
.trace_match_sources
.contains(&SequenceTraceMatchSource::Prefix),
"dictMatchState should not trace prefix-origin matches for {strategy:?}"
);
}
}
#[test]
fn prepared_fast_and_double_fast_dict_state_chain_rep2_across_dictionary_boundary() {
let prefix = b"abcdWXYZabcdWXYZ";
let src = b"abcdWXYZabcdWXYZWXYZWXYZ";
for strategy in [ParserStrategy::Fast, ParserStrategy::DoubleFast] {
let params = MatchFinderParameters {
parser_strategy: strategy,
fast_search_step: 2,
secondary_hash_bits: 16,
..MatchFinderParameters::default()
};
let prepared = build_prepared_dictionary_match_state(prefix, params)
.expect("prepared dictionary state must build");
let mut state = PrefixedBlockMatchState::new_with_prepared_match_state(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
Some(&prepared),
);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
0,
RepeatOffsets::from_values([4, 64, 8]),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(
plan.sequences.len() >= 2,
"expected an immediate rep2 chain for {strategy:?}"
);
let mut repeat_offsets = RepeatOffsets::from_values([4, 64, 8]);
let first_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
let second_offset = repeat_offsets.resolve(&plan.sequences[1]).unwrap();
assert_eq!(first_offset, prefix.len() as u32);
assert_eq!(second_offset, 4, "expected rep2 chain for {strategy:?}");
assert!(
!plan
.trace_match_sources
.contains(&SequenceTraceMatchSource::Prefix),
"dictMatchState should not trace prefix-origin matches for {strategy:?}"
);
}
}
#[test]
fn fast_dict_match_state_keeps_source_match_when_source_candidate_is_valid() {
let prefix = b"ZZZZabcdWXYZ";
let src = b"abcdqrstabcdWXYZtail";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::Fast,
fast_search_step: 2,
..MatchFinderParameters::default()
};
let mut state = PrefixedBlockMatchState::new_with_mode(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
);
state.insert_range(src, 0, 8);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
8,
RepeatOffsets::default(),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, 8);
assert_eq!(
plan.trace_match_sources.first().copied(),
Some(SequenceTraceMatchSource::Source)
);
assert!(
!plan
.trace_match_sources
.contains(&SequenceTraceMatchSource::Prefix)
);
}
#[test]
fn double_fast_dict_match_state_keeps_source_long_match_when_source_candidate_is_valid() {
let prefix = b"mnopabcdWXYZ";
let src = b"abcdWXYZuvabcdWXYZtail";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::DoubleFast,
fast_search_step: 2,
secondary_hash_bits: 16,
..MatchFinderParameters::default()
};
let mut state = PrefixedBlockMatchState::new_with_mode(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
);
state.insert_range(src, 0, 10);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
10,
RepeatOffsets::default(),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, 10);
assert_eq!(
plan.trace_match_sources.first().copied(),
Some(SequenceTraceMatchSource::Source)
);
assert!(
!plan
.trace_match_sources
.contains(&SequenceTraceMatchSource::Prefix)
);
}
#[test]
fn double_fast_dict_match_state_prefers_ip_plus_one_dict_long_probe() {
let prefix = b"abcdefghij";
let src = b"0abcqrstuv0abcdefghijTAIL";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::DoubleFast,
fast_search_step: 2,
secondary_hash_bits: 16,
..MatchFinderParameters::default()
};
let mut state = PrefixedBlockMatchState::new_with_mode(
prefix,
src.len(),
params,
PrefixMatchMode::DictMatchState,
);
state.insert_range(src, 0, 10);
let plan = plan_sequences_for_prefixed_contiguous_block(
prefix,
src,
10,
RepeatOffsets::default(),
params,
128 * 1024,
&mut state,
)
.unwrap();
assert!(!plan.sequences.is_empty());
assert_eq!(plan.sequences[0].literal_length, 1);
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert_eq!(raw_offset, prefix.len() as u32 + 11);
assert_eq!(
plan.trace_match_sources.first().copied(),
Some(SequenceTraceMatchSource::Dict)
);
assert!(
!plan
.trace_match_sources
.contains(&SequenceTraceMatchSource::Prefix)
);
}
#[test]
fn double_fast_planner_keeps_finding_repeated_sequences() {
let src = b"pattern-0123456789-pattern-0123456789-pattern-0123456789";
let plan = plan_sequences_for_block(
src,
&[&[]],
RepeatOffsets::default(),
MatchFinderParameters {
parser_strategy: ParserStrategy::DoubleFast,
secondary_hash_bits: 16,
..MatchFinderParameters::default()
},
)
.unwrap();
assert!(!plan.sequences.is_empty());
}
#[test]
fn fast_planner_keeps_finding_repeated_sequences() {
let src = b"pattern-0123456789-pattern-0123456789-pattern-0123456789";
let plan = plan_sequences_for_block(
src,
&[&[]],
RepeatOffsets::default(),
MatchFinderParameters {
parser_strategy: ParserStrategy::Fast,
fast_search_step: 2,
..MatchFinderParameters::default()
},
)
.unwrap();
assert!(!plan.sequences.is_empty());
}
#[test]
fn double_fast_prefix_planner_finds_dictionary_matches() {
let prefix = b"customer=0012|region=us-east|tier=gold|";
let src = b"customer=0012|region=us-east|tier=gold|invoice=42";
let plan = plan_sequences_for_block(
src,
&[prefix],
RepeatOffsets::default(),
MatchFinderParameters {
parser_strategy: ParserStrategy::DoubleFast,
secondary_hash_bits: 16,
..MatchFinderParameters::default()
},
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert!(raw_offset >= prefix.len() as u32);
}
#[test]
fn fast_prefix_planner_finds_dictionary_matches() {
let prefix = b"customer=0012|region=us-east|tier=gold|";
let src = b"customer=0012|region=us-east|tier=gold|invoice=42";
let plan = plan_sequences_for_block(
src,
&[prefix],
RepeatOffsets::default(),
MatchFinderParameters {
parser_strategy: ParserStrategy::Fast,
fast_search_step: 2,
..MatchFinderParameters::default()
},
)
.unwrap();
assert!(!plan.sequences.is_empty());
let mut repeat_offsets = RepeatOffsets::default();
let raw_offset = repeat_offsets.resolve(&plan.sequences[0]).unwrap();
assert!(raw_offset >= prefix.len() as u32);
}
#[test]
fn fast_prefix_matcher_rejects_tail_positions_shorter_than_its_threshold() {
let prefix = b"prefix-wxyz";
let src = b"tailwxyz";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::Fast,
min_match_length_after_literals: 6,
..MatchFinderParameters::default()
};
let mut prefix_finder = FastFinder::new(params.hash_bits, params.min_match);
prefix_finder.insert_prefix(prefix);
let mut src_finder = FastFinder::new(params.hash_bits, params.min_match);
let found = fast_best_match_with_prefix(
prefix,
src,
4,
0,
&prefix_finder,
&mut src_finder,
params,
0,
0,
);
assert!(found.is_none());
}
#[test]
fn lazy_match_scoring_accounts_for_skipped_literals() {
assert!(
should_take_lazy_match_with_skip(
MatchCandidate {
offset: 64,
length: 8,
},
0,
MatchCandidate {
offset: 8,
length: 10,
},
1,
RepeatOffsets::default().values(),
0,
),
"a one-byte skip should win when it gains enough match length"
);
assert!(
!should_take_lazy_match_with_skip(
MatchCandidate {
offset: 8,
length: 10,
},
0,
MatchCandidate {
offset: 4,
length: 11,
},
2,
RepeatOffsets::default().values(),
0,
),
"a two-byte skip should not win when it only buys one extra byte"
);
}
#[test]
fn source_penalty_can_keep_a_better_prefix_match() {
let repeat_offsets = RepeatOffsets::default().values();
let mut chosen = None;
for prefix_length in 8..24 {
for source_length in 4..24 {
let prefix = MatchCandidate {
offset: 96,
length: prefix_length,
};
let source = MatchCandidate {
offset: 4,
length: source_length,
};
let prefix_score = estimated_match_score_bits(prefix, repeat_offsets, 1);
let source_score = estimated_match_score_bits(source, repeat_offsets, 1);
if source_score > prefix_score && source_score - 16 < prefix_score {
chosen = Some((prefix, source));
break;
}
}
if chosen.is_some() {
break;
}
}
let (prefix, source) = chosen.expect("expected a score pair that the source penalty flips");
assert_eq!(
choose_better_match_with_adjustment(Some(prefix), Some(source), repeat_offsets, 1, -16,),
Some(prefix)
);
}
#[test]
fn lazy_matching_checks_repeat_offset_one_ahead_before_stopping() {
let src = vec![b'a'; 80];
let params = MatchFinderParameters {
lazy_search_depth: 2,
good_enough_match_length: 32,
..MatchFinderParameters::default()
};
let mut finder = MatchFinder::new(src.len(), params.hash_bits, params.min_match);
let decision = find_lazy_match_skip_without_prefix(
&src,
0,
0,
RepeatOffsets::default().values(),
MatchCandidate {
offset: 64,
length: 32,
},
params,
&mut finder,
MatchFloor::fixed(0),
);
assert_eq!(decision.skip, 1);
assert_eq!(decision.inserted, 1);
}
#[test]
fn prefix_lazy_matching_checks_repeat_offset_one_ahead_before_stopping() {
let prefix = vec![b'a'; 64];
let src = vec![b'a'; 80];
let params = MatchFinderParameters {
lazy_search_depth: 2,
good_enough_match_length: 32,
..MatchFinderParameters::default()
};
let prefix_refs = [prefix.as_slice()];
let prefix_chain = PrefixChain::new(&prefix_refs).unwrap().unwrap();
let prefix_finder = MatchFinder::new(prefix_chain.len(), params.hash_bits, params.min_match);
let mut src_finder = MatchFinder::new(src.len(), params.hash_bits, params.min_match);
let decision = find_lazy_match_skip_with_prefix_chain(
prefix_chain,
&src,
0,
0,
RepeatOffsets::default().values(),
MatchCandidate {
offset: 64,
length: 32,
},
params,
PrefixedMatchFloor::fixed(0, 0),
PrefixMatchMode::ExtDict,
&prefix_finder,
&mut src_finder,
);
assert_eq!(decision.skip, 1);
assert_eq!(decision.inserted, 1);
}
#[test]
fn prefix_match_search_keeps_looking_past_good_enough_candidates() {
let src = {
let mut src = b"ABCD".to_vec();
src.extend(vec![b'x'; 60]);
src
};
let mut prefix = src.clone();
prefix.push(b'!');
prefix.extend_from_slice(&src[..48]);
prefix.push(b'?');
prefix.extend_from_slice(&src[..32]);
let params = MatchFinderParameters {
dictionary_search_depth: 8,
good_enough_match_length: 32,
source_score_penalty_with_prefix: 32,
..MatchFinderParameters::default()
};
let prefix_refs = [prefix.as_slice()];
let prefix_chain = PrefixChain::new(&prefix_refs).unwrap().unwrap();
let mut prefix_finder =
MatchFinder::new(prefix_chain.len(), params.hash_bits, params.min_match);
let slot = hash_at(&src, 0, params.hash_bits);
prefix_finder.heads[slot] = (src.len() + 50) as u32;
prefix_finder.previous[src.len() + 50] = (src.len() + 1) as u32;
prefix_finder.previous[src.len() + 1] = 0u32;
let candidate = prefix_finder
.find_prefix_chain_match(prefix_chain, &src, 0, params, 0, 0)
.expect("expected a dictionary candidate");
assert_eq!(candidate.length, src.len());
}
#[test]
fn incompressible_skip_matches_upstream_shape() {
let params = MatchFinderParameters::default();
assert_eq!(skip_after_no_match(0, 0, params), 1);
assert_eq!(skip_after_no_match(0, 255, params), 1);
assert_eq!(skip_after_no_match(0, 256, params), 2);
assert_eq!(skip_after_no_match(0, 1024, params), 5);
}
#[test]
fn chain_match_finder_lazy_skipping_only_inserts_one_position_per_search() {
let src = vec![b'a'; 32];
let mut eager = MatchFinder::with_chain_log(src.len(), 10, 10, 4);
assert_eq!(eager.insert_and_find_first_index(&src, 8, false), Some(7));
assert_eq!(eager.next_to_update, 8);
let mut lazy = MatchFinder::with_chain_log(src.len(), 10, 10, 4);
assert_eq!(lazy.insert_and_find_first_index(&src, 8, true), Some(0));
assert_eq!(lazy.next_to_update, 8);
assert_eq!(lazy.insert_and_find_first_index(&src, 9, true), Some(8));
assert_eq!(lazy.next_to_update, 9);
}
#[test]
fn chain_extdict_match_finder_lazy_skipping_only_inserts_one_position_per_search() {
let prefix = vec![b'a'; 32];
let src = vec![b'a'; 32];
let prefix_refs = [prefix.as_slice()];
let prefix_chain = PrefixChain::new(&prefix_refs).unwrap().unwrap();
let mut eager = MatchFinder::with_chain_log(prefix.len(), 10, 10, 4);
eager.insert_prefix_chain(prefix_chain, &[]);
assert!(
eager
.insert_and_find_first_index_ext_dict(prefix.len(), &src, 8, false)
.is_some()
);
assert_eq!(eager.next_to_update, prefix.len() + 8);
let mut lazy = MatchFinder::with_chain_log(prefix.len(), 10, 10, 4);
lazy.insert_prefix_chain(prefix_chain, &[]);
assert!(
lazy.insert_and_find_first_index_ext_dict(prefix.len(), &src, 8, true)
.is_some()
);
assert_eq!(lazy.next_to_update, prefix.len() + 8);
assert!(
lazy.insert_and_find_first_index_ext_dict(prefix.len(), &src, 9, true)
.is_some()
);
assert_eq!(lazy.next_to_update, prefix.len() + 9);
}
#[test]
fn row_hash_finder_lazy_skipping_only_inserts_current_position_on_search() {
let src = vec![b'a'; 32];
let limit = row_search_limit(src.len());
let mut eager = RowHashFinder::new(10, 6, 4);
eager.refill_hash_cache::<4>(&src, limit);
let eager_attempts = eager.search_attempt_budget(6);
let (eager_candidate, _, _) =
eager.find_source_match_with_budget(&src, 8, 0, false, eager_attempts, false, None);
assert!(eager_candidate.is_some());
assert_eq!(eager.next_to_update, 9);
let mut lazy = RowHashFinder::new(10, 6, 4);
lazy.refill_hash_cache::<4>(&src, limit);
let lazy_attempts = lazy.search_attempt_budget(6);
let (first_candidate, _, _) =
lazy.find_source_match_with_budget(&src, 8, 0, true, lazy_attempts, false, None);
assert!(first_candidate.is_none());
assert_eq!(lazy.next_to_update, 9);
let (second_candidate, _, _) =
lazy.find_source_match_with_budget(&src, 9, 0, true, lazy_attempts, false, None);
assert_eq!(
second_candidate,
Some(MatchCandidate {
offset: 1,
length: 23
})
);
assert_eq!(lazy.next_to_update, 10);
}
#[test]
fn row_hash_finder_large_gap_update_matches_upstream_head_and_tail_ranges() {
let mut src = Vec::with_capacity(640);
while src.len() < 640 {
src.extend_from_slice(b"abcde12345vwxyz67890ABCDE54321");
}
src.truncate(640);
let mut actual = RowHashFinder::new(16, 6, 4);
let context = actual.row_context();
let limit = row_search_limit(src.len());
let target = 480;
assert!(target < limit);
actual.refill_hash_cache::<4>(&src, limit);
actual.update_internal_with_context::<4>(&src, target, true, context);
let mut expected = RowHashFinder::new(16, 6, 4);
expected.insert_range(&src, 0, 96);
expected.insert_range(&src, target - 32, target);
assert_eq!(actual.next_to_update, target);
assert_eq!(actual.hash_table, expected.hash_table);
assert_eq!(actual.tag_table, expected.tag_table);
}
#[test]
fn row_hash_finder_untraced_search_matches_traced_result_and_state() {
let src = b"abcde12345abcde12345abcde12345abcde12345uvwxyz";
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::LazyRow,
search_log: 5,
min_match: 5,
..MatchFinderParameters::default()
};
let pos = 20;
let limit = row_search_limit(src.len());
assert!(pos < limit);
let mut traced = RowHashFinder::new(params.hash_bits, params.search_log, params.min_match);
traced.insert_range(src, 0, pos);
traced.refill_hash_cache::<5>(src, limit);
let mut untraced = traced.clone();
let attempts = traced.search_attempt_budget(params.search_log);
let (traced_candidate, traced_attempts_left, traced_trace) =
traced.find_source_match_with_budget(src, pos, 0, false, attempts, true, None);
let (untraced_candidate, untraced_attempts_left, untraced_trace) =
untraced.find_source_match_with_budget(src, pos, 0, false, attempts, false, None);
assert_eq!(untraced_candidate, traced_candidate);
assert_eq!(untraced_attempts_left, traced_attempts_left);
assert_eq!(untraced_trace, RowMatchBufferTrace::default());
assert!(traced_trace.num_matches > 0);
assert_eq!(untraced.next_to_update, traced.next_to_update);
assert_eq!(untraced.hash_table, traced.hash_table);
assert_eq!(untraced.tag_table, traced.tag_table);
}
#[test]
fn chain_match_finder_hashes_with_min_match_length() {
let src = b"ABCDx123ABCDy123ABCDx123".to_vec();
let mut min4 = MatchFinder::with_chain_log(src.len(), 20, 10, 4);
min4.insert_range(&src, 0, 8);
assert_eq!(min4.insert_and_find_first_index(&src, 8, false), Some(0));
let mut min5 = MatchFinder::with_chain_log(src.len(), 20, 10, 5);
min5.insert_range(&src, 0, 8);
assert_eq!(min5.insert_and_find_first_index(&src, 8, false), None);
}
#[test]
fn prepared_chain_dictionary_tables_stop_at_hash_read_tail() {
let prefix = vec![b'a'; 16];
let src = vec![b'a'; 8];
let prefix_refs = [prefix.as_slice()];
let prefix_chain = PrefixChain::new(&prefix_refs).unwrap().unwrap();
let mut generic = MatchFinder::with_chain_log(prefix.len(), 10, 10, 4);
generic.insert_prefix_chain(prefix_chain, &[]);
let mut cdict = MatchFinder::with_chain_log(prefix.len(), 10, 10, 4);
cdict.insert_prefix_chain_for_cdict(prefix_chain);
assert_eq!(generic.lookup_prefix_chain(prefix_chain, &src, 0), Some(12));
assert_eq!(cdict.lookup_prefix_chain(prefix_chain, &src, 0), Some(7));
assert_eq!(cdict.next_to_update, prefix.len());
}
#[test]
fn match_finders_preserve_configured_hash_bits_up_to_twenty() {
let fast = FastFinder::new(20, MIN_MATCH as u32);
assert_eq!(fast.hash_bits, 20);
assert_eq!(fast.heads.len(), 1usize << 20);
let double_fast = DoubleFastFinder::new(20, 19, MIN_MATCH as u32);
assert_eq!(double_fast.long_hash_bits, 20);
assert_eq!(double_fast.short_hash_bits, 19);
assert_eq!(double_fast.long_entries.len(), 1usize << 20);
assert_eq!(double_fast.short_heads.len(), 1usize << 19);
let chain = MatchFinder::new(128 * 1024, 19, 4);
assert_eq!(chain.hash_bits, 19);
assert_eq!(chain.heads.len(), 1usize << 19);
let binary_tree = BinaryTreeFinder::new(20, 16, 4);
assert_eq!(binary_tree.hash_bits, 20);
assert_eq!(binary_tree.heads.len(), 1usize << 20);
}
#[test]
fn only_positions_with_a_whole_hash_key_are_insertable() {
for len in 0..MIN_MATCH {
assert_eq!(hash_insert_end(len), 0, "a {len}-byte buffer has no key");
}
assert_eq!(hash_insert_end(MIN_MATCH), 1);
for len in MIN_MATCH..64 {
assert_eq!(
hash_insert_end(len),
len - MIN_MATCH + 1,
"last insertable position in {len} bytes is {}",
len - MIN_MATCH,
);
}
}
#[test]
fn the_fixed_width_literal_copy_needs_room_in_the_source_too() {
let src = vec![0u8; 64];
let roomy_destination = 1 << 20;
assert!(wildcopy_literals_fits(&src, 8, 8, 8, roomy_destination));
for literals_end in (src.len() - WILDCOPY_OVERLENGTH + 1)..=src.len() {
assert!(
!wildcopy_literals_fits(&src, literals_end, 4, 4, roomy_destination),
"a run ending at {literals_end} of {} is inside the overshoot",
src.len(),
);
}
assert!(!wildcopy_literals_fits(&src, 8, 8, 8, 8));
assert!(!wildcopy_literals_fits(&src, 17, 17, 17, roomy_destination));
}
#[test]
fn traced_and_untraced_lazy_planners_agree_on_the_same_block() {
const HOSTS: [&str; 6] = ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot"];
const STATUSES: [&str; 4] = ["ok", "warn", "error", "timeout"];
let mut src = Vec::with_capacity(48 * 1024);
let mut rng = 0x2545_F491_4F6C_DD1Du64;
let mut next = move || {
rng ^= rng << 13;
rng ^= rng >> 7;
rng ^= rng << 17;
rng
};
let mut id = 1000u64;
while src.len() < 48 * 1024 {
let value = next();
id += value % 7;
src.extend_from_slice(
format!(
"{{\"id\":{id},\"host\":\"{}-node-{:02}\",\"status\":\"{}\",\"latency_ms\":{},\"region\":\"us-{}-{}\"}}\n",
HOSTS[(value >> 3) as usize % HOSTS.len()],
(value >> 11) % 32,
STATUSES[(value >> 17) as usize % STATUSES.len()],
(value >> 23) % 500,
if value & 1 == 0 { "east" } else { "west" },
(value >> 29) % 4,
)
.as_bytes(),
);
}
const STRATEGIES: [(ParserStrategy, usize); 7] = [
(ParserStrategy::Greedy, 0),
(ParserStrategy::Lazy, 1),
(ParserStrategy::Lazy2, 2),
(ParserStrategy::GreedyRow, 0),
(ParserStrategy::LazyRow, 1),
(ParserStrategy::Lazy2Row, 2),
(ParserStrategy::BinaryTreeLazy2, 2),
];
for (parser_strategy, lazy_search_depth) in STRATEGIES {
let params = MatchFinderParameters {
parser_strategy,
hash_bits: 17,
chain_log: 17,
search_log: 4,
min_match: 5,
search_depth: 16,
lazy_search_depth,
good_enough_match_length: 8,
window_log: 20,
..MatchFinderParameters::default()
};
let mut untraced = SequencePlan::default();
untraced.disable_tracing();
plan_sequences_for_block_into(&mut untraced, &src, &[], RepeatOffsets::default(), params)
.unwrap();
assert!(!untraced.tracing_enabled());
let mut traced = SequencePlan::default();
traced.enable_tracing();
plan_sequences_for_block_into(&mut traced, &src, &[], RepeatOffsets::default(), params)
.unwrap();
assert!(traced.tracing_enabled());
assert_eq!(
traced.sequences, untraced.sequences,
"{parser_strategy:?}: traced and untraced planners disagree on sequences",
);
assert_eq!(
traced.literals, untraced.literals,
"{parser_strategy:?}: traced and untraced planners disagree on literals",
);
assert_eq!(
traced.repeat_offsets.values(),
untraced.repeat_offsets.values(),
"{parser_strategy:?}: traced and untraced planners disagree on repeat offsets",
);
}
}
#[test]
fn binary_tree_compares_a_match_older_than_the_children_roll_buffer() {
const CHAIN_LOG: u32 = 6;
const REPEAT: &[u8] = b"Zq7-mixed run of bytes with no inner echo 9876543210";
const GAP: usize = 200;
let mut src = Vec::from(REPEAT);
let mut state = 0x9e37_79b9u32;
while src.len() < REPEAT.len() + GAP {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
src.extend_from_slice(&state.to_le_bytes());
}
let second_copy = src.len();
src.extend_from_slice(REPEAT);
let mut finder = BinaryTreeFinder::new(16, CHAIN_LOG, 4);
assert!(
second_copy > finder.bt_mask,
"the match at offset {second_copy} has to sit outside the {}-slot roll buffer \
or the bug cannot show",
finder.bt_mask
);
let mut matches = Vec::new();
for pos in 0..=second_copy {
finder.insert_and_collect_matches(&mut matches, &src, pos, 32, 0, MIN_MATCH);
}
let found = matches
.iter()
.copied()
.find(|candidate| candidate.offset == second_copy)
.unwrap_or_else(|| panic!("no candidate at offset {second_copy}; collected {matches:?}"));
assert_eq!(
found.length,
REPEAT.len(),
"the whole repeated run should match, not a prefix of it"
);
}
#[test]
fn limited_update_bounds_the_catch_up_only_once_the_lag_is_long() {
assert_eq!(limited_update_after_long_match(1_000, 1_000), 1_000);
assert_eq!(limited_update_after_long_match(1_000, 1_384), 1_000);
assert_eq!(limited_update_after_long_match(1_000, 1_385), 1_384);
assert_eq!(limited_update_after_long_match(1_000, 1_500), 1_384);
assert_eq!(limited_update_after_long_match(1_000, 1_576), 1_384);
assert_eq!(limited_update_after_long_match(1_000, 200_000), 199_808);
assert_eq!(limited_update_after_long_match(200_000, 1_000), 200_000);
}
fn shift_fixture(len: usize) -> Vec<u8> {
let mut src = Vec::with_capacity(len);
let mut counter = 0u32;
while src.len() < len {
src.extend_from_slice(b"id=");
src.extend_from_slice(counter.to_string().as_bytes());
src.extend_from_slice(b",name=widget,qty=");
src.extend_from_slice((counter % 97).to_string().as_bytes());
src.push(b'\n');
counter += 1;
}
src.truncate(len);
src
}
#[test]
fn shifting_the_fast_table_matches_a_fill_of_the_retained_bytes() {
let src = shift_fixture(64 * 1024);
for delta in [1usize, 7, 4096, 32 * 1024, 63 * 1024] {
let mut shifted = FastFinder::new(14, 4);
shifted.insert_range(&src, 0, src.len());
shifted.shift_positions(delta);
let mut rebuilt = FastFinder::new(14, 4);
rebuilt.insert_range(&src[delta..], 0, src.len() - delta);
assert_eq!(shifted.heads, rebuilt.heads, "delta={delta}");
}
}
#[test]
fn shifting_the_double_fast_tables_matches_a_fill_of_the_retained_bytes() {
let src = shift_fixture(64 * 1024);
for delta in [1usize, 7, 4096, 32 * 1024, 63 * 1024] {
let mut shifted = DoubleFastFinder::new(14, 13, 4);
shifted.insert_range(&src, 0, src.len());
shifted.shift_positions(delta);
let mut rebuilt = DoubleFastFinder::new(14, 13, 4);
rebuilt.insert_range(&src[delta..], 0, src.len() - delta);
assert_eq!(shifted.long_entries, rebuilt.long_entries, "delta={delta}");
assert_eq!(shifted.short_heads, rebuilt.short_heads, "delta={delta}");
}
}
#[test]
fn the_long_table_files_source_positions_past_sixteen_mib() {
const PAST_CEILING: usize = (1 << 24) + 4096;
let mut src = vec![0u8; PAST_CEILING + 8];
src[PAST_CEILING..PAST_CEILING + 8].copy_from_slice(b"long tag");
let mut finder = DoubleFastFinder::new(12, 12, 4);
finder.insert_src_long_position(&src, PAST_CEILING);
let hash = hash_long_at(&src, PAST_CEILING, finder.long_hash_bits);
let entry = finder.long_entries[tagged_index(hash)];
assert_eq!(
long_entry_pos(entry),
PAST_CEILING as u32,
"the filed position must survive at full width"
);
assert!(
long_entry_tag_matches(entry, hash),
"and the tag must sit below it without taking any of its range"
);
}
#[test]
fn shifting_the_row_table_rebases_every_live_entry() {
let src = shift_fixture(64 * 1024);
for delta in [1usize, 7, 4096, 32 * 1024] {
let mut finder = RowHashFinder::new(14, 4, 4);
finder.insert_range(&src, 0, src.len());
let before = finder.hash_table.clone();
let next_to_update_before = finder.next_to_update;
finder.shift_positions(delta);
assert_eq!(
finder.next_to_update,
next_to_update_before - delta,
"delta={delta}"
);
assert!(next_to_update_before > delta, "fixture must span the shift");
let mut live = 0usize;
for (slot, (&old, &new)) in before.iter().zip(finder.hash_table.iter()).enumerate() {
if (old as usize) < delta {
assert_eq!(new, 0, "slot {slot} should have emptied, delta={delta}");
} else {
assert_eq!(
new as usize,
old as usize - delta,
"slot {slot}, delta={delta}"
);
live += 1;
}
}
assert!(
live > before.len() / 4,
"only {live} of {} entries survived a {delta}-byte shift",
before.len()
);
}
}
#[test]
fn a_reaching_floor_rises_with_the_position() {
let floor = MatchFloor::reaching(1_000, 4_096);
assert_eq!(floor.at(0), 1_000);
assert_eq!(floor.at(5_000), 1_000);
assert_eq!(floor.at(5_096), 1_000);
assert_eq!(floor.at(5_097), 1_001);
assert_eq!(floor.at(10_000), 5_904);
for pos in [0usize, 1, 999, 1_000, 5_096, 5_097, 100_000] {
assert!(floor.at(pos) <= pos.max(1_000));
}
}
#[test]
fn a_fixed_floor_does_not_move() {
let floor = MatchFloor::fixed(700);
for pos in [0usize, 1, 700, 701, usize::MAX] {
assert_eq!(floor.at(pos), 700, "fixed floor moved at {pos}");
}
assert_eq!(MatchFloor::fixed(0).at(usize::MAX), 0);
}
#[test]
fn a_prefixed_floor_splits_at_the_prefix_boundary() {
const PREFIX_LEN: usize = 1_125;
let floor = PrefixedMatchFloor::reaching(PREFIX_LEN, MatchFloor::reaching(PREFIX_LEN, 2_048));
assert_eq!(floor.at(0), (PREFIX_LEN, 0));
assert_eq!(floor.at(2_048), (PREFIX_LEN, 0));
assert_eq!(floor.at(2_049), (PREFIX_LEN, 1));
assert_eq!(floor.at(4_105), (PREFIX_LEN, 2_057));
let live = PrefixedMatchFloor::reaching(PREFIX_LEN, MatchFloor::reaching(0, 2_048));
assert_eq!(live.at(0), (0, 0));
assert_eq!(live.at(900), (0, 0));
assert_eq!(live.at(924), (1, 0));
assert_eq!(live.at(2_048), (PREFIX_LEN, 0));
let fixed = PrefixedMatchFloor::fixed(400, 12);
for pos in [0usize, 1, 4_105, usize::MAX] {
assert_eq!(
fixed.at(pos),
(400, 12),
"fixed prefixed floor moved at {pos}"
);
}
}
#[test]
fn retired_floors_agree_in_both_coordinate_spaces() {
const PREFIX_LEN: usize = 1_125;
const MAX_HISTORY: usize = 2_048;
let prefix = vec![0u8; PREFIX_LEN];
let mut retired_blocks = 0usize;
for block_start in [0usize, 1_024, 2_048, 4_096, 16_384] {
let block_end = block_start + 1_024;
let floors = prefixed_block_floors(&prefix, block_start, block_end, MAX_HISTORY, 0);
if !floors.prefix_retired {
continue;
}
retired_blocks += 1;
let contiguous = MatchFloor::reaching(block_start.saturating_sub(MAX_HISTORY), MAX_HISTORY);
for pos in block_start..block_end {
let (prefix_low, source_low) = floors.match_floor.at(pos);
assert_eq!(
prefix_low, PREFIX_LEN,
"a retired block left part of the prefix reachable at {pos}",
);
assert_eq!(
source_low,
contiguous.at(pos),
"the two coordinate spaces disagreed at {pos} of the block at {block_start}",
);
}
}
assert!(
retired_blocks >= 2,
"only {retired_blocks} of the block starts retired the prefix",
);
}
#[test]
fn the_prefix_leaves_the_window_only_once_the_block_passes_it() {
const PREFIX_LEN: usize = 1_125;
const HISTORY: usize = 2_048;
let (prefix_low, source_low) = prefixed_window_lows(PREFIX_LEN, 0, HISTORY - 1, HISTORY, 0);
assert_eq!(prefix_low, 0);
assert_eq!(source_low, 0);
let (prefix_low, _) = prefixed_window_lows(PREFIX_LEN, 0, HISTORY - 1, HISTORY, 2);
assert_eq!(prefix_low, 2);
let (prefix_low, source_low) = prefixed_window_lows(PREFIX_LEN, 0, HISTORY, HISTORY, 0);
assert_eq!(prefix_low, 0);
assert_eq!(source_low, 0);
let (prefix_low, source_low) = prefixed_window_lows(PREFIX_LEN, 0, HISTORY + 1, HISTORY, 0);
assert_eq!(prefix_low, PREFIX_LEN);
assert_eq!(source_low, 0);
let (prefix_low, source_low) = prefixed_window_lows(PREFIX_LEN, 64, HISTORY + 1, HISTORY, 0);
assert_eq!(prefix_low, PREFIX_LEN);
assert_eq!(source_low, 1);
let (_, source_low) = prefixed_window_lows(PREFIX_LEN, 4_096, 131_072, HISTORY, 0);
assert_eq!(source_low, 4_096);
}
fn imperfectly_periodic_records(len: usize) -> Vec<u8> {
let mut out = Vec::with_capacity(len + 128);
let mut counter = 1u32;
while out.len() < len {
counter = counter.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
out.extend_from_slice(b"{\"id\":");
out.extend_from_slice((counter % 100_000).to_string().as_bytes());
out.extend_from_slice(b",\"region\":\"us-east-1\",\"tier\":\"gold\",\"amount\":");
out.extend_from_slice((counter % 997).to_string().as_bytes());
out.extend_from_slice(b"}\n");
}
out.truncate(len);
out
}
#[test]
fn retired_fast_prefix_matches_the_plain_parser() {
const MAX_HISTORY: usize = 16 * 1024;
const BLOCK_SIZE: usize = 4 * 1024;
let prefix = imperfectly_periodic_records(1_024);
let src = imperfectly_periodic_records(32 * 1024);
let params = MatchFinderParameters {
parser_strategy: ParserStrategy::Fast,
..MatchFinderParameters::default()
};
let mut dispatched = PrefixedBlockMatchState::new_with_mode(
&prefix,
src.len(),
params,
PrefixMatchMode::ExtDict,
);
let mut forced = dispatched.clone();
let mut dispatched_offsets = RepeatOffsets::default();
let mut forced_offsets = RepeatOffsets::default();
let (mut retired_blocks, mut live_blocks, mut sequences) = (0usize, 0usize, 0usize);
let mut block_start = 0usize;
while block_start < src.len() {
let block_end = (block_start + BLOCK_SIZE).min(src.len());
let floors = prefixed_block_floors(
&prefix,
block_start,
block_end,
MAX_HISTORY,
params.prefix_low_limit,
);
if floors.prefix_retired {
retired_blocks += 1;
} else {
live_blocks += 1;
}
let mut dispatched_plan = SequencePlan::default();
plan_sequences_for_prefixed_contiguous_block_into(
&mut dispatched_plan,
&prefix,
&src[..block_end],
block_start,
dispatched_offsets,
params,
MAX_HISTORY,
&mut dispatched,
)
.unwrap();
let mut forced_plan = SequencePlan::default();
let PrefixedBlockMatchStateInner::Fast {
prefix_finder,
src_finder,
mode,
prepared,
} = &mut forced.inner
else {
panic!("the Fast strategy must build a Fast match state");
};
plan_sequences_fast_with_prefix_from_into(
&mut forced_plan,
&src[..block_end],
block_start,
&prefix,
forced_offsets,
params,
floors.prefix_low,
floors.source_low,
prefix_finder.as_deref(),
src_finder,
*mode,
prepared.as_deref(),
)
.unwrap();
let divergence = dispatched_plan
.sequences
.iter()
.zip(forced_plan.sequences.iter())
.position(|(dispatched, forced)| dispatched != forced);
assert!(
divergence.is_none() && dispatched_plan.sequences.len() == forced_plan.sequences.len(),
"sequences diverged in the block at {block_start} (retired={}) at index {divergence:?} \
of {}/{}: {:?} against {:?}",
floors.prefix_retired,
dispatched_plan.sequences.len(),
forced_plan.sequences.len(),
divergence.map(|at| dispatched_plan.sequences[at]),
divergence.map(|at| forced_plan.sequences[at]),
);
assert!(
dispatched_plan.literals == forced_plan.literals,
"literals diverged in the block at {block_start}: {} bytes against {}",
dispatched_plan.literals.len(),
forced_plan.literals.len(),
);
assert_eq!(
dispatched_plan.repeat_offsets, forced_plan.repeat_offsets,
"repeat offsets diverged in the block at {block_start}",
);
sequences += dispatched_plan.sequences.len();
dispatched_offsets = dispatched_plan.repeat_offsets;
forced_offsets = forced_plan.repeat_offsets;
block_start = block_end;
}
assert!(
retired_blocks >= 2,
"the body never passed the window: {retired_blocks} retired blocks",
);
assert!(
live_blocks >= 2,
"the prefix retired immediately: {live_blocks} live blocks",
);
assert!(
sequences > 100,
"the parse found almost nothing: {sequences}"
);
let (
PrefixedBlockMatchStateInner::Fast {
src_finder: dispatched_finder,
..
},
PrefixedBlockMatchStateInner::Fast {
src_finder: forced_finder,
..
},
) = (&dispatched.inner, &forced.inner)
else {
panic!("the Fast strategy must build a Fast match state");
};
let differing = dispatched_finder
.heads
.iter()
.zip(forced_finder.heads.iter())
.filter(|(dispatched, forced)| dispatched != forced)
.count();
assert_eq!(
differing,
0,
"the two routes filed different positions in {differing} of {} hash slots",
dispatched_finder.heads.len(),
);
}
#[test]
fn the_prefix_table_is_built_exactly_when_a_parse_reads_it() {
let prefix = b"abcdefghABCDEFGHabcdefghABCDEFGH";
let src = b"abcdefghABCDEFGHEFGHEFGHTAILTAIL";
for strategy in [ParserStrategy::Fast, ParserStrategy::DoubleFast] {
let params = MatchFinderParameters {
parser_strategy: strategy,
min_match: 4,
..MatchFinderParameters::default()
};
for mode in [PrefixMatchMode::ExtDict, PrefixMatchMode::DictMatchState] {
for cached in [false, true] {
let prepared =
cached.then(|| build_prepared_dictionary_match_state(prefix, params).unwrap());
let state = PrefixedBlockMatchState::new_with_prepared_match_state(
prefix,
src.len(),
params,
mode,
prepared.as_ref(),
);
let (prefix_finder_built, prepared_present) = match &state.inner {
PrefixedBlockMatchStateInner::Fast {
prefix_finder,
prepared,
..
} => (prefix_finder.is_some(), prepared.is_some()),
PrefixedBlockMatchStateInner::DoubleFast {
prefix_finder,
prepared,
..
} => (prefix_finder.is_some(), prepared.is_some()),
_ => panic!("{strategy:?} must build its own kind of match state"),
};
let ext_dict = mode == PrefixMatchMode::ExtDict;
assert_eq!(
prefix_finder_built, ext_dict,
"{strategy:?}/{mode:?}/cached={cached}: the prefix table should be \
built for ext-dict mode and only for ext-dict mode",
);
assert!(
ext_dict || prepared_present,
"{strategy:?}/{mode:?}/cached={cached}: dropping the prefix table is \
only safe while dict-match-state always carries prepared tables",
);
}
}
}
}
#[test]
#[cfg_attr(target_family = "wasm", ignore = "panic = abort on wasm")]
fn a_dict_match_state_parse_without_prepared_tables_says_so() {
let prefix = b"abcdefghABCDEFGHabcdefghABCDEFGH";
let src = b"abcdefghABCDEFGHEFGHEFGHTAILTAIL";
for strategy in [ParserStrategy::Fast, ParserStrategy::DoubleFast] {
let params = MatchFinderParameters {
parser_strategy: strategy,
min_match: 4,
..MatchFinderParameters::default()
};
let mut plan = SequencePlan::default();
let payload = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
match strategy {
ParserStrategy::Fast => {
let mut src_finder = FastFinder::new(params.hash_bits, params.min_match);
plan_sequences_fast_with_prefix_from_into(
&mut plan,
src,
0,
prefix,
RepeatOffsets::default(),
params,
0,
0,
None,
&mut src_finder,
PrefixMatchMode::DictMatchState,
None,
)
}
_ => {
let mut src_finder = DoubleFastFinder::new(
params.hash_bits,
params.secondary_hash_bits,
params.min_match,
);
plan_sequences_double_fast_with_prefix_from_into(
&mut plan,
src,
0,
prefix,
RepeatOffsets::default(),
params,
0,
0,
None,
&mut src_finder,
PrefixMatchMode::DictMatchState,
None,
)
}
}
.unwrap();
}))
.expect_err("{strategy:?} parsed a dict-match-state block with no prepared tables");
let message = payload
.downcast_ref::<String>()
.map(String::as_str)
.or_else(|| payload.downcast_ref::<&str>().copied())
.unwrap_or_default();
assert!(
message.contains("must have been given prepared tables"),
"{strategy:?} panicked, but not on the missing tables: {message}",
);
}
}
#[test]
fn only_the_tagged_strategies_gate_reuse_on_the_entry_width() {
const BELOW: usize = PACKED_TAGGED_POSITION_LIMIT;
const ABOVE: usize = PACKED_TAGGED_POSITION_LIMIT + 1;
for strategy in [
ParserStrategy::Fast,
ParserStrategy::DoubleFast,
ParserStrategy::Greedy,
ParserStrategy::Lazy,
ParserStrategy::Lazy2,
ParserStrategy::GreedyRow,
ParserStrategy::LazyRow,
ParserStrategy::Lazy2Row,
ParserStrategy::BinaryTreeLazy2,
ParserStrategy::BinaryTreeOpt,
ParserStrategy::BinaryTreeUltra,
ParserStrategy::BinaryTreeUltra2,
] {
let params = MatchFinderParameters {
parser_strategy: strategy,
..MatchFinderParameters::default()
};
let tagged = matches!(strategy, ParserStrategy::Fast | ParserStrategy::DoubleFast);
for limit in [BELOW, ABOVE] {
let mut state =
ContiguousBlockMatchState::new_with_position_limit(limit, limit, params);
assert!(
state.reset_if_compatible(params, limit),
"{strategy:?} refused reuse at an unchanged position limit of {limit}",
);
}
let mut state = ContiguousBlockMatchState::new_with_position_limit(BELOW, BELOW, params);
assert_eq!(
state.reset_if_compatible(params, ABOVE),
!tagged,
"{strategy:?} reuse across the 16 MiB boundary",
);
let mut state = ContiguousBlockMatchState::new_with_position_limit(ABOVE, ABOVE, params);
assert_eq!(
state.reset_if_compatible(params, BELOW),
!tagged,
"{strategy:?} reuse back across the 16 MiB boundary",
);
}
}