1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
use std::collections::{HashMap, HashSet};
use std::path::PathBuf;
use std::sync::Arc;
use crate::tokenizer::build_all;
use crate::IndexError;
use super::{OverlayDoc, OverlayView};
/// Wrap a freshly-built posting map's `Vec` lists in `Arc` for the overlay's
/// COW-shared gram index. Used by the full-rebuild paths, which build into a
/// plain `Vec` map first (no per-push `Arc::make_mut` overhead) and share only
/// at the end.
fn wrap_arc(map: HashMap<u64, Vec<u32>>) -> HashMap<u64, Arc<Vec<u32>>> {
map.into_iter().map(|(k, v)| (k, Arc::new(v))).collect()
}
impl OverlayView {
/// Build an overlay from a set of dirty files.
///
/// # Caller contract: content must be pre-normalized
///
/// `dirty_files` content is stored as-is and returned by the resolver for
/// verification. Callers MUST call `normalize_encoding` before building the
/// overlay so that UTF-16 / BOM content is transcoded to UTF-8. `commit_batch`
/// in `index/mod.rs` satisfies this contract. Direct callers (e.g., tests)
/// using raw byte literals are exempt because ASCII source is already valid UTF-8.
///
/// `base_doc_count` is the total doc count across all base segments.
/// Overlay doc_ids start at `base_doc_count` to stay disjoint.
/// `dirty_files` maps repo-relative path to file content.
pub fn build(
base_doc_count: u32,
dirty_files: Vec<(PathBuf, Arc<[u8]>)>,
) -> Result<Self, IndexError> {
let mut gram_index: HashMap<u64, Vec<u32>> = HashMap::new();
let overlay_docs = dirty_files.len();
let mut docs = Vec::with_capacity(dirty_files.len());
let mut next_id = base_doc_count;
for (path, content) in dirty_files {
let doc_id = Self::next_doc_id(&mut next_id, base_doc_count, overlay_docs)?;
let grams = build_all(&content);
for &gram_hash in &grams {
gram_index.entry(gram_hash).or_default().push(doc_id);
}
docs.push(OverlayDoc {
doc_id,
path,
content,
grams,
});
}
// Sort posting lists for consistent intersection behavior.
for ids in gram_index.values_mut() {
ids.sort_unstable();
ids.dedup();
}
let doc_id_map = docs
.iter()
.enumerate()
.map(|(i, d)| (d.doc_id, i))
.collect();
Ok(OverlayView {
gram_index: wrap_arc(gram_index),
docs,
doc_id_map,
next_doc_id: next_id,
base_doc_count,
})
}
/// Build an overlay incrementally, reusing docs from the previous overlay
/// for files that haven't changed since the last commit.
///
/// Only `new_files` are read from disk and tokenized fresh. Unchanged docs
/// from `old_overlay` are carried forward with `Arc::clone` on content
/// (refcount bump, no data copy). All docs are re-indexed with new doc_ids
/// since the ID space starts at `base_doc_count`.
///
/// Fast path: when `base_doc_count == old_overlay.base_doc_count`, overlay
/// doc_ids for unchanged files are stable and the delta path is used instead
/// of a full rebuild.
pub fn build_incremental(
base_doc_count: u32,
old_overlay: &OverlayView,
new_files: Vec<(PathBuf, Arc<[u8]>)>,
newly_changed: &HashSet<PathBuf>,
removed_paths: &HashSet<PathBuf>,
) -> Result<Self, IndexError> {
// Fast path: base has not grown since the last commit.
// Overlay doc_ids for unchanged files are stable; use delta update.
if base_doc_count == old_overlay.base_doc_count {
return Self::build_incremental_delta(
base_doc_count,
old_overlay,
new_files,
newly_changed,
removed_paths,
);
}
let mut gram_index: HashMap<u64, Vec<u32>> = HashMap::new();
let overlay_docs =
(old_overlay.docs.len() + new_files.len()).saturating_sub(newly_changed.len());
let mut docs = Vec::new();
let mut next_id = base_doc_count;
// Reuse old overlay docs that are unchanged.
for old_doc in &old_overlay.docs {
if removed_paths.contains(&old_doc.path) {
continue;
}
if newly_changed.contains(&old_doc.path) {
continue; // replaced by new version below
}
let doc_id = Self::next_doc_id(&mut next_id, base_doc_count, overlay_docs)?;
// Reuse cached grams instead of re-tokenizing.
for &gram_hash in &old_doc.grams {
gram_index.entry(gram_hash).or_default().push(doc_id);
}
docs.push(OverlayDoc {
doc_id,
path: old_doc.path.clone(),
content: Arc::clone(&old_doc.content),
grams: old_doc.grams.clone(),
});
}
// Add newly changed/added files (freshly read from disk).
for (path, content) in new_files {
let doc_id = Self::next_doc_id(&mut next_id, base_doc_count, overlay_docs)?;
let grams = build_all(&content);
for &gram_hash in &grams {
gram_index.entry(gram_hash).or_default().push(doc_id);
}
docs.push(OverlayDoc {
doc_id,
path,
content,
grams,
});
}
for ids in gram_index.values_mut() {
ids.sort_unstable();
ids.dedup();
}
let doc_id_map = docs
.iter()
.enumerate()
.map(|(i, d)| (d.doc_id, i))
.collect();
Ok(OverlayView {
gram_index: wrap_arc(gram_index),
docs,
doc_id_map,
next_doc_id: next_id,
base_doc_count,
})
}
/// Allocate the next overlay doc_id, advancing `next_id` by 1.
#[inline]
fn next_doc_id(
next_id: &mut u32,
base_doc_count: u32,
overlay_docs: usize,
) -> Result<u32, IndexError> {
let id = *next_id;
*next_id = next_id.checked_add(1).ok_or(IndexError::DocIdOverflow {
base_doc_count,
overlay_docs,
})?;
Ok(id)
}
/// Delta path: base_doc_count is unchanged, so overlay doc_ids for unchanged
/// files are stable. Clone the old gram_index, remove stale entries for
/// changed/deleted files using their cached grams, append new doc_ids for
/// new/changed files. New doc_ids are always > all existing ids so posting
/// lists remain sorted after push.
fn build_incremental_delta(
base_doc_count: u32,
old_overlay: &OverlayView,
new_files: Vec<(PathBuf, Arc<[u8]>)>,
newly_changed: &HashSet<PathBuf>,
removed_paths: &HashSet<PathBuf>,
) -> Result<Self, IndexError> {
// Clone old gram_index: with Arc-shared posting lists this is a map of
// refcount bumps, not a deep copy of every Vec. Only the lists actually
// mutated below are deep-copied, via Arc::make_mut (copy-on-write), so
// the per-commit cost is O(changed-file grams), not O(total grams).
let mut gram_index = old_overlay.gram_index.clone();
let overlay_docs =
(old_overlay.docs.len() + new_files.len()).saturating_sub(newly_changed.len());
for old_doc in &old_overlay.docs {
if removed_paths.contains(&old_doc.path) || newly_changed.contains(&old_doc.path) {
for &gram_hash in &old_doc.grams {
if let Some(list) = gram_index.get_mut(&gram_hash) {
Arc::make_mut(list).retain(|&id| id != old_doc.doc_id);
}
}
}
}
// Drop posting lists that became empty after removal.
gram_index.retain(|_, list| !list.is_empty());
// Carry forward unchanged docs with their existing (stable) doc_ids.
let mut docs: Vec<OverlayDoc> = old_overlay
.docs
.iter()
.filter(|d| !removed_paths.contains(&d.path) && !newly_changed.contains(&d.path))
.cloned()
.collect();
// New/changed files get fresh doc_ids starting from next_doc_id.
let mut next_id = old_overlay.next_doc_id;
for (path, content) in new_files {
let doc_id = Self::next_doc_id(&mut next_id, base_doc_count, overlay_docs)?;
let grams = build_all(&content);
for &gram_hash in &grams {
Arc::make_mut(gram_index.entry(gram_hash).or_default()).push(doc_id);
}
docs.push(OverlayDoc {
doc_id,
path,
content,
grams,
});
}
// Sorted-order invariant: new doc_ids > all existing, so push() keeps
// lists sorted; the windows check is a read (no Arc::make_mut), so
// already-sorted lists carried forward stay Arc-shared. make_mut only
// fires on the rare list that is actually out of order.
for ids in gram_index.values_mut() {
if ids.windows(2).any(|w| w[0] >= w[1]) {
let list = Arc::make_mut(ids);
list.sort_unstable();
list.dedup();
}
}
let doc_id_map = docs
.iter()
.enumerate()
.map(|(i, d)| (d.doc_id, i))
.collect();
Ok(OverlayView {
gram_index,
docs,
doc_id_map,
next_doc_id: next_id,
base_doc_count,
})
}
}