1use std::{
7 cmp::Ordering,
8 collections::{BTreeMap, BTreeSet},
9 path::{Path, PathBuf},
10};
11
12use serde::{Deserialize, Serialize};
13use sha2::{Digest, Sha256};
14use unicode_casefold::UnicodeCaseFold;
15use unicode_normalization::UnicodeNormalization;
16use uuid::Uuid;
17
18use crate::{
19 CaptureEntryKind, CaptureExclusionKind, CaptureExclusionReason, CaptureIgnoredPath,
20 CapturePlan, CapturePlanEntry, CapturePlanExclusion, FolderbaseCaptureError, FolderbaseError,
21 FolderbaseVersionStore,
22 folderbase_state::FolderbaseState,
23 folderbase_version::{
24 DeletedKind, ExclusionKind, FolderbaseVersion, MAX_ENCODED_VERSION_BYTES, PathBindingKind,
25 validate_capture_path, validate_capture_version_id,
26 },
27};
28
29const QUERY_REQUEST_FORMAT: &str = "folderbase-query-request-v1";
30const MAX_PAGE_LIMIT: usize = 1_000;
31const MAX_RETURNED_EXCLUSIONS: usize = 1_000;
32const MAX_INDEX_BYTES: u64 = 64 * 1024 * 1024;
33const MAX_INDEX_RECORDS: usize = 16_384;
34const INDEX_ROOT: &str = ".folderbase/local/query-index-v1";
35const INDEX_RECORD: &str = ".folderbase/local/query-index-v1/index.json";
36const INDEX_FORMAT: &str = "folderbase-query-private-index-v1";
37#[cfg(test)]
38thread_local! {
39 static LIVE_RESULT_ROW_MATERIALIZATIONS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
40 static LIVE_RESULT_EXCLUSION_MATERIALIZATIONS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
41}
42
43pub struct FolderbaseQueryEngine {
45 root: PathBuf,
46 opening_root_instance_sha256: String,
47 store: FolderbaseVersionStore,
48 state: FolderbaseState,
49}
50
51impl std::fmt::Debug for FolderbaseQueryEngine {
52 fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
53 formatter
54 .debug_struct("FolderbaseQueryEngine")
55 .field("root", &self.root)
56 .field(
57 "opening_root_instance_sha256",
58 &self.opening_root_instance_sha256,
59 )
60 .finish_non_exhaustive()
61 }
62}
63
64#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
66#[serde(deny_unknown_fields)]
67pub struct QueryRequest {
68 format: String,
69 scope: QueryScope,
70 #[serde(default)]
71 filters: QueryFilters,
72 page: QueryPage,
73}
74
75#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
76#[serde(tag = "kind", rename_all = "snake_case", deny_unknown_fields)]
77enum QueryScope {
78 Live,
79 Historical { folderbase_version_id: String },
80}
81
82#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
83#[serde(deny_unknown_fields)]
84struct QueryFilters {
85 #[serde(default)]
86 paths: Vec<String>,
87 #[serde(default)]
88 path_prefixes: Vec<String>,
89 #[serde(default)]
90 kinds: Vec<QueryEntryKind>,
91 #[serde(default)]
92 lifecycles: Vec<QueryLifecycle>,
93 #[serde(default)]
94 object_ids: Vec<String>,
95 #[serde(default)]
96 object_version_ids: Vec<String>,
97 minimum_bytes: Option<u64>,
98 maximum_bytes: Option<u64>,
99}
100
101#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
102#[serde(deny_unknown_fields)]
103struct QueryPage {
104 limit: usize,
105 #[serde(default)]
106 cursor: Option<String>,
107}
108
109impl QueryRequest {
110 pub fn live(limit: usize) -> Self {
112 Self {
113 format: QUERY_REQUEST_FORMAT.to_owned(),
114 scope: QueryScope::Live,
115 filters: QueryFilters::default(),
116 page: QueryPage {
117 limit,
118 cursor: None,
119 },
120 }
121 }
122}
123
124#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
126#[serde(rename_all = "snake_case")]
127pub enum QuerySource {
128 CapturePlan,
129 FolderbaseVersion,
130}
131
132#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
134#[serde(rename_all = "snake_case")]
135pub enum QueryEntryKind {
136 Directory,
137 NestedFolderbase,
138 RegularFile,
139 Symlink,
140}
141
142#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
144#[serde(rename_all = "snake_case")]
145pub enum QueryLifecycle {
146 Deleted,
147 Live,
148}
149
150#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
152#[serde(rename_all = "snake_case")]
153pub enum QueryExecution {
154 BoundedScan,
155 PrivateIndex,
156}
157
158#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
160#[serde(deny_unknown_fields)]
161pub struct QueryEntry {
162 path: String,
163 kind: QueryEntryKind,
164 lifecycle: QueryLifecycle,
165 bytes: Option<u64>,
166 executable: Option<bool>,
167 symlink_target: Option<String>,
168 object_id: Option<String>,
169 object_version_id: Option<String>,
170 folderbase_version_id: Option<String>,
171 source: QuerySource,
172 boundary_reason: Option<String>,
173}
174
175impl QueryEntry {
176 pub fn path(&self) -> &str {
177 &self.path
178 }
179 pub fn kind(&self) -> QueryEntryKind {
180 self.kind
181 }
182 pub fn lifecycle(&self) -> QueryLifecycle {
183 self.lifecycle
184 }
185 pub fn bytes(&self) -> Option<u64> {
186 self.bytes
187 }
188 pub fn executable(&self) -> Option<bool> {
189 self.executable
190 }
191 pub fn symlink_target(&self) -> Option<&str> {
192 self.symlink_target.as_deref()
193 }
194 pub fn object_id(&self) -> Option<&str> {
195 self.object_id.as_deref()
196 }
197 pub fn object_version_id(&self) -> Option<&str> {
198 self.object_version_id.as_deref()
199 }
200 pub fn folderbase_version_id(&self) -> Option<&str> {
201 self.folderbase_version_id.as_deref()
202 }
203 pub fn source(&self) -> QuerySource {
204 self.source
205 }
206 pub fn boundary_reason(&self) -> Option<&str> {
207 self.boundary_reason.as_deref()
208 }
209
210 fn row_key(&self) -> QueryRowKey {
211 QueryRowKey {
212 path: self.path.clone(),
213 lifecycle: self.lifecycle,
214 kind: self.kind,
215 object_id: self.object_id.clone(),
216 object_version_id: self.object_version_id.clone(),
217 folderbase_version_id: self.folderbase_version_id.clone(),
218 source: self.source,
219 boundary_reason: self.boundary_reason.clone(),
220 }
221 }
222}
223
224#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
225#[serde(deny_unknown_fields)]
226struct QueryRowKey {
227 path: String,
228 lifecycle: QueryLifecycle,
229 kind: QueryEntryKind,
230 object_id: Option<String>,
231 object_version_id: Option<String>,
232 folderbase_version_id: Option<String>,
233 source: QuerySource,
234 boundary_reason: Option<String>,
235}
236
237impl QueryRowKey {
238 fn compare(&self, other: &Self) -> Ordering {
239 self.path
240 .as_bytes()
241 .cmp(other.path.as_bytes())
242 .then_with(|| lifecycle_rank(self.lifecycle).cmp(&lifecycle_rank(other.lifecycle)))
243 .then_with(|| kind_rank(self.kind).cmp(&kind_rank(other.kind)))
244 .then_with(|| compare_optional_bytes(&self.object_id, &other.object_id))
245 .then_with(|| compare_optional_bytes(&self.object_version_id, &other.object_version_id))
246 .then_with(|| {
247 compare_optional_bytes(&self.folderbase_version_id, &other.folderbase_version_id)
248 })
249 .then_with(|| source_rank(self.source).cmp(&source_rank(other.source)))
250 .then_with(|| compare_optional_bytes(&self.boundary_reason, &other.boundary_reason))
251 }
252}
253
254fn lifecycle_rank(lifecycle: QueryLifecycle) -> u8 {
255 match lifecycle {
256 QueryLifecycle::Live => 0,
257 QueryLifecycle::Deleted => 1,
258 }
259}
260
261fn kind_rank(kind: QueryEntryKind) -> u8 {
262 match kind {
263 QueryEntryKind::Directory => 0,
264 QueryEntryKind::RegularFile => 1,
265 QueryEntryKind::Symlink => 2,
266 QueryEntryKind::NestedFolderbase => 3,
267 }
268}
269
270fn source_rank(source: QuerySource) -> u8 {
271 match source {
272 QuerySource::CapturePlan => 0,
273 QuerySource::FolderbaseVersion => 1,
274 }
275}
276
277fn compare_optional_bytes(left: &Option<String>, right: &Option<String>) -> Ordering {
278 match (left, right) {
279 (None, None) => Ordering::Equal,
280 (None, Some(_)) => Ordering::Less,
281 (Some(_), None) => Ordering::Greater,
282 (Some(left), Some(right)) => left.as_bytes().cmp(right.as_bytes()),
283 }
284}
285
286fn compare_entries(left: &QueryEntry, right: &QueryEntry) -> Ordering {
287 left.row_key().compare(&right.row_key())
288}
289
290#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
292#[serde(rename_all = "snake_case")]
293pub enum QueryExclusionKind {
294 BlockDevice,
295 CharacterDevice,
296 Fifo,
297 HardLink,
298 NestedFolderbase,
299 OtherSpecial,
300 Socket,
301}
302
303#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
305#[serde(deny_unknown_fields)]
306pub struct QueryExclusion {
307 path: String,
308 reason: String,
309 kind: Option<QueryExclusionKind>,
310}
311
312impl QueryExclusion {
313 pub fn path(&self) -> &str {
314 &self.path
315 }
316 pub fn reason(&self) -> &str {
317 &self.reason
318 }
319 pub fn kind(&self) -> Option<QueryExclusionKind> {
320 self.kind
321 }
322}
323
324#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
326pub struct QueryPageResult {
327 limit: usize,
328 returned: usize,
329 has_more: bool,
330 next_cursor: Option<String>,
331}
332
333impl QueryPageResult {
334 pub fn limit(&self) -> usize {
335 self.limit
336 }
337 pub fn returned(&self) -> usize {
338 self.returned
339 }
340 pub fn has_more(&self) -> bool {
341 self.has_more
342 }
343 pub fn next_cursor(&self) -> Option<&str> {
344 self.next_cursor.as_deref()
345 }
346}
347
348#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
350pub struct QueryResult {
351 root: PathBuf,
352 folderbase_id: String,
353 request_sha256: String,
354 observation_generation: String,
355 execution: QueryExecution,
356 entries: Vec<QueryEntry>,
357 exclusions: Vec<QueryExclusion>,
358 exclusions_truncated: bool,
359 page: QueryPageResult,
360}
361
362#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
364#[serde(rename_all = "snake_case")]
365pub enum QueryIndexState {
366 Absent,
367 Fresh,
368 Stale,
369}
370
371#[derive(Debug, Clone, PartialEq, Eq)]
373pub struct QueryIndexStatus {
374 root: PathBuf,
375 folderbase_id: String,
376 state: QueryIndexState,
377 generation: Option<String>,
378 observed_generation: String,
379 records: usize,
380}
381
382impl QueryIndexStatus {
383 pub fn root(&self) -> &Path {
384 &self.root
385 }
386 pub fn folderbase_id(&self) -> &str {
387 &self.folderbase_id
388 }
389 pub fn state(&self) -> QueryIndexState {
390 self.state
391 }
392 pub fn generation(&self) -> Option<&str> {
393 self.generation.as_deref()
394 }
395 pub fn observed_generation(&self) -> &str {
396 &self.observed_generation
397 }
398 pub fn records(&self) -> usize {
399 self.records
400 }
401 pub fn storage_path(&self) -> &'static str {
402 INDEX_ROOT
403 }
404 pub fn disposable(&self) -> bool {
405 true
406 }
407}
408
409#[derive(Debug, Clone, PartialEq, Eq)]
411pub struct QueryIndexRebuildResult {
412 root: PathBuf,
413 folderbase_id: String,
414 generation: String,
415 records: usize,
416 exclusions: usize,
417}
418
419impl QueryIndexRebuildResult {
420 pub fn root(&self) -> &Path {
421 &self.root
422 }
423 pub fn folderbase_id(&self) -> &str {
424 &self.folderbase_id
425 }
426 pub fn generation(&self) -> &str {
427 &self.generation
428 }
429 pub fn records(&self) -> usize {
430 self.records
431 }
432 pub fn exclusions(&self) -> usize {
433 self.exclusions
434 }
435 pub fn storage_path(&self) -> &'static str {
436 INDEX_ROOT
437 }
438 pub fn portable_files_changed(&self) -> bool {
439 false
440 }
441 pub fn ordinary_files_changed(&self) -> bool {
442 false
443 }
444}
445
446#[derive(Debug, Clone, PartialEq, Eq)]
448pub struct QueryExplain {
449 root: PathBuf,
450 folderbase_id: String,
451 request_sha256: String,
452 observation_generation: String,
453 normalized_request: serde_json::Value,
454 scope_source: QuerySource,
455 index_strategy: QueryExecution,
456 matched: usize,
457 excluded: Vec<QueryExclusion>,
458 excluded_truncated: bool,
459}
460
461impl QueryExplain {
462 pub fn root(&self) -> &Path {
463 &self.root
464 }
465 pub fn folderbase_id(&self) -> &str {
466 &self.folderbase_id
467 }
468 pub fn request_sha256(&self) -> &str {
469 &self.request_sha256
470 }
471 pub fn observation_generation(&self) -> &str {
472 &self.observation_generation
473 }
474 pub fn normalized_request(&self) -> &serde_json::Value {
475 &self.normalized_request
476 }
477 pub fn scope_source(&self) -> QuerySource {
478 self.scope_source
479 }
480 pub fn ordering(&self) -> &'static str {
481 "query_row_key_v1"
482 }
483 pub fn filter_algebra(&self) -> &'static str {
484 "families_and_values_or"
485 }
486 pub fn ordinary_content_access(&self) -> &'static str {
487 "metadata_only"
488 }
489 pub fn index_strategy(&self) -> QueryExecution {
490 self.index_strategy
491 }
492 pub fn matched(&self) -> usize {
493 self.matched
494 }
495 pub fn excluded(&self) -> &[QueryExclusion] {
496 &self.excluded
497 }
498 pub fn excluded_truncated(&self) -> bool {
499 self.excluded_truncated
500 }
501}
502
503impl QueryResult {
504 pub fn root(&self) -> &Path {
505 &self.root
506 }
507 pub fn folderbase_id(&self) -> &str {
508 &self.folderbase_id
509 }
510 pub fn request_sha256(&self) -> &str {
511 &self.request_sha256
512 }
513 pub fn observation_generation(&self) -> &str {
514 &self.observation_generation
515 }
516 pub fn execution(&self) -> QueryExecution {
517 self.execution
518 }
519 pub fn entries(&self) -> &[QueryEntry] {
520 &self.entries
521 }
522 pub fn exclusions(&self) -> &[QueryExclusion] {
523 &self.exclusions
524 }
525 pub fn exclusions_truncated(&self) -> bool {
526 self.exclusions_truncated
527 }
528 pub fn page(&self) -> &QueryPageResult {
529 &self.page
530 }
531}
532
533#[derive(Debug, thiserror::Error)]
535#[non_exhaustive]
536pub enum QueryError {
537 #[error("invalid query request: {0}")]
538 InvalidQueryRequest(String),
539 #[error("invalid query cursor")]
540 InvalidQueryCursor,
541 #[error("the query observation changed; retry without a cursor")]
542 QuerySnapshotChanged,
543 #[error("the opened Folderbase root authority changed")]
544 RootAuthorityChanged,
545 #[error("query index rebuild failed: {0}")]
546 IndexRebuildFailed(String),
547 #[error("the exact historical Folderbase Version is missing: {version_id}")]
548 ScopeVersionMissing { version_id: String },
549 #[error("the exact historical Folderbase Version is invalid: {version_id}: {message}")]
550 ScopeVersionInvalid { version_id: String, message: String },
551 #[error(transparent)]
552 Capture(#[from] FolderbaseCaptureError),
553}
554
555impl FolderbaseQueryEngine {
556 pub fn open(root: impl AsRef<Path>) -> Result<Self, QueryError> {
558 let store = FolderbaseVersionStore::open_for_query(root)?;
559 let state = FolderbaseState::open_existing(&store.root_attestation.root)
560 .map_err(|_| QueryError::RootAuthorityChanged)?;
561 state
562 .verify_root_identity(store.root_physical_identity())
563 .map_err(|_| QueryError::RootAuthorityChanged)?;
564 Ok(Self {
565 root: store.root_attestation.root.clone(),
566 opening_root_instance_sha256: store.root_attestation.root_instance_sha256.clone(),
567 store,
568 state,
569 })
570 }
571
572 fn ensure_root_authority(&self) -> Result<(), QueryError> {
573 self.state
574 .verify_root_identity(self.store.root_physical_identity())
575 .map_err(|_| QueryError::RootAuthorityChanged)
576 }
577
578 fn ensure_observation_authority(
579 &self,
580 observation: &QueryObservation,
581 ) -> Result<(), QueryError> {
582 if observation.root_instance_sha256 != self.opening_root_instance_sha256 {
583 return Err(QueryError::RootAuthorityChanged);
584 }
585 self.ensure_root_authority()
586 }
587
588 fn prepare_continuation(
589 &self,
590 request: &QueryRequest,
591 normalized: &NormalizedRequest<'_>,
592 ) -> Result<(String, Option<QueryCursorPayload>), QueryError> {
593 let request_sha256 = request_sha256(normalized)?;
594 let cursor = request
595 .page
596 .cursor
597 .as_deref()
598 .map(decode_cursor)
599 .transpose()?;
600 if cursor.as_ref().is_some_and(|cursor| {
601 cursor.root_instance_sha256 != self.opening_root_instance_sha256
602 || cursor.request_sha256 != request_sha256
603 }) {
604 return Err(QueryError::InvalidQueryCursor);
605 }
606 Ok((request_sha256, cursor))
607 }
608
609 fn observe_live_query_for_continuation<G>(
610 &self,
611 after_live_observation: impl FnOnce() -> G,
612 has_cursor: bool,
613 ) -> Result<(QueryObservation, QueryExecution), QueryError> {
614 match self.observe_live_query_with_after_observation(after_live_observation) {
615 Ok(observation) => Ok(observation),
616 Err(QueryError::Capture(error))
617 if has_cursor && error.proves_query_observation_changed() =>
618 {
619 Err(QueryError::QuerySnapshotChanged)
620 }
621 Err(error) => Err(error),
622 }
623 }
624
625 fn observe_live_query_with_after_observation<G>(
626 &self,
627 after_observation: impl FnOnce() -> G,
628 ) -> Result<(QueryObservation, QueryExecution), QueryError> {
629 let state = observe_live_state(&self.store, &self.state)?;
630 if state.plan.root_instance_sha256() != self.opening_root_instance_sha256 {
631 return Err(QueryError::RootAuthorityChanged);
632 }
633 let observation_guard = after_observation();
634 let index = read_index(&self.state, &state);
635 let selected = if index.state == QueryIndexState::Fresh {
636 let record = index.record.expect("fresh index has a verified record");
637 (
638 state.observation_with(record.entries, record.exclusions),
639 QueryExecution::PrivateIndex,
640 )
641 } else {
642 (
643 project_live_observation(&state),
644 QueryExecution::BoundedScan,
645 )
646 };
647 drop(observation_guard);
648 self.ensure_observation_authority(&selected.0)?;
649 Ok(selected)
650 }
651
652 fn observe_historical_query_with_after_root_check<G>(
653 &self,
654 version_id: &str,
655 after_root_check: impl FnOnce() -> G,
656 ) -> Result<QueryObservation, QueryError> {
657 let root_guard = after_root_check();
658 let observation = observe_historical(&self.store, &self.state, version_id);
659 drop(root_guard);
660 observation
661 }
662
663 pub fn run(&self, request: &QueryRequest) -> Result<QueryResult, QueryError> {
665 self.run_with_observation_hooks(request, || (), || ())
666 }
667
668 fn run_with_observation_hooks<LiveGuard, HistoricalGuard>(
669 &self,
670 request: &QueryRequest,
671 after_live_observation: impl FnOnce() -> LiveGuard,
672 after_historical_root_check: impl FnOnce() -> HistoricalGuard,
673 ) -> Result<QueryResult, QueryError> {
674 self.ensure_root_authority()?;
675 let normalized = normalize_request(request)?;
676 let (request_sha256, cursor) = self.prepare_continuation(request, &normalized)?;
677 let (mut observation, execution) = match &request.scope {
678 QueryScope::Live => {
679 self.observe_live_query_for_continuation(after_live_observation, cursor.is_some())?
680 }
681 QueryScope::Historical {
682 folderbase_version_id,
683 } => (
684 self.observe_historical_query_with_after_root_check(
685 folderbase_version_id,
686 after_historical_root_check,
687 )?,
688 QueryExecution::BoundedScan,
689 ),
690 };
691 self.ensure_observation_authority(&observation)?;
692 let exclusions_truncated = observation.exclusions.len() > MAX_RETURNED_EXCLUSIONS;
693 observation.exclusions.truncate(MAX_RETURNED_EXCLUSIONS);
694 let after_row_key = if let Some(cursor) = cursor {
695 if cursor.observation_generation != observation.generation {
696 return Err(QueryError::QuerySnapshotChanged);
697 }
698 Some(cursor.last_row_key)
699 } else {
700 None
701 };
702 let entries = observation
703 .entries
704 .into_iter()
705 .filter(|entry| normalized.filters.applies(entry))
706 .filter(|entry| {
707 after_row_key
708 .as_ref()
709 .is_none_or(|row_key| entry.row_key().compare(row_key) == Ordering::Greater)
710 })
711 .collect::<Vec<_>>();
712 let returned = entries.len().min(normalized.limit);
713 let has_more = returned < entries.len();
714 let next_cursor = has_more
715 .then(|| {
716 encode_cursor(&QueryCursorPayload {
717 root_instance_sha256: observation.root_instance_sha256.clone(),
718 request_sha256: request_sha256.clone(),
719 observation_generation: observation.generation.clone(),
720 last_row_key: entries[returned - 1].row_key(),
721 })
722 })
723 .transpose()?;
724 Ok(QueryResult {
725 root: observation.root,
726 folderbase_id: observation.folderbase_id,
727 request_sha256,
728 observation_generation: observation.generation,
729 execution,
730 entries: entries.into_iter().take(returned).collect(),
731 exclusions: observation.exclusions,
732 exclusions_truncated,
733 page: QueryPageResult {
734 limit: normalized.limit,
735 returned,
736 has_more,
737 next_cursor,
738 },
739 })
740 }
741
742 pub fn explain(&self, request: &QueryRequest) -> Result<QueryExplain, QueryError> {
744 self.explain_with_after_live_observation(request, || ())
745 }
746
747 fn explain_with_after_live_observation<G>(
748 &self,
749 request: &QueryRequest,
750 after_live_observation: impl FnOnce() -> G,
751 ) -> Result<QueryExplain, QueryError> {
752 self.ensure_root_authority()?;
753 let normalized = normalize_request(request)?;
754 let (request_sha256, cursor) = self.prepare_continuation(request, &normalized)?;
755 let live = matches!(&request.scope, QueryScope::Live);
756 let (mut observation, index_strategy) = match &request.scope {
757 QueryScope::Live => {
758 self.observe_live_query_for_continuation(after_live_observation, cursor.is_some())?
759 }
760 QueryScope::Historical {
761 folderbase_version_id,
762 } => (
763 observe_historical(&self.store, &self.state, folderbase_version_id)?,
764 QueryExecution::BoundedScan,
765 ),
766 };
767 self.ensure_observation_authority(&observation)?;
768 if let Some(cursor) = cursor
769 && cursor.observation_generation != observation.generation
770 {
771 return Err(QueryError::QuerySnapshotChanged);
772 }
773 let matched = observation
774 .entries
775 .iter()
776 .filter(|entry| normalized.filters.applies(entry))
777 .count();
778 let normalized_request = serde_json::to_value(&normalized.value)
779 .map_err(|error| QueryError::InvalidQueryRequest(error.to_string()))?;
780 let excluded_truncated = observation.exclusions.len() > MAX_RETURNED_EXCLUSIONS;
781 observation.exclusions.truncate(MAX_RETURNED_EXCLUSIONS);
782 Ok(QueryExplain {
783 root: observation.root,
784 folderbase_id: observation.folderbase_id,
785 request_sha256,
786 observation_generation: observation.generation,
787 normalized_request,
788 scope_source: if live {
789 QuerySource::CapturePlan
790 } else {
791 QuerySource::FolderbaseVersion
792 },
793 index_strategy,
794 matched,
795 excluded: observation.exclusions,
796 excluded_truncated,
797 })
798 }
799
800 pub fn index_status(&self) -> Result<QueryIndexStatus, QueryError> {
802 self.index_status_with_after_observation(|| ())
803 }
804
805 fn index_status_with_after_observation<G>(
806 &self,
807 after_observation: impl FnOnce() -> G,
808 ) -> Result<QueryIndexStatus, QueryError> {
809 self.ensure_root_authority()?;
810 let observation = observe_live_state(&self.store, &self.state)?;
811 if observation.plan.root_instance_sha256() != self.opening_root_instance_sha256 {
812 return Err(QueryError::RootAuthorityChanged);
813 }
814 self.ensure_root_authority()?;
815 let observation_guard = after_observation();
816 let index = read_index(&self.state, &observation);
817 drop(observation_guard);
818 self.ensure_root_authority()?;
819 Ok(QueryIndexStatus {
820 root: observation.plan.root().to_path_buf(),
821 folderbase_id: observation.plan.folderbase_id().to_owned(),
822 state: index.state,
823 generation: index.generation,
824 observed_generation: observation.generation,
825 records: index.records,
826 })
827 }
828
829 pub fn rebuild_index(&self) -> Result<QueryIndexRebuildResult, QueryError> {
831 self.rebuild_index_with_before_publish(|| Ok(()))
832 }
833
834 fn rebuild_index_with_before_publish(
835 &self,
836 before_publish: impl FnOnce() -> std::io::Result<()>,
837 ) -> Result<QueryIndexRebuildResult, QueryError> {
838 self.rebuild_index_with_hooks(|| (), before_publish)
839 }
840
841 fn rebuild_index_with_hooks<G>(
842 &self,
843 after_observation: impl FnOnce() -> G,
844 before_publish: impl FnOnce() -> std::io::Result<()>,
845 ) -> Result<QueryIndexRebuildResult, QueryError> {
846 self.ensure_root_authority()?;
847 let live_state = observe_live_state(&self.store, &self.state)?;
848 let observation = project_live_observation(&live_state);
849 self.ensure_observation_authority(&observation)?;
850 if observation.entries.len() + observation.exclusions.len() > MAX_INDEX_RECORDS {
851 return Err(QueryError::IndexRebuildFailed(
852 "derived record count exceeds the private-index bound".to_owned(),
853 ));
854 }
855 let mut record = PrivateIndexRecord {
856 format: INDEX_FORMAT.to_owned(),
857 generation: observation.generation.clone(),
858 root_instance_sha256: observation.root_instance_sha256.clone(),
859 folderbase_id: observation.folderbase_id.clone(),
860 projection_sha256: live_projection_sha256(&live_state),
861 content_sha256: String::new(),
862 entries: observation.entries.clone(),
863 exclusions: observation.exclusions.clone(),
864 };
865 record.content_sha256 = private_index_content_sha256(&record)
866 .map_err(|error| QueryError::IndexRebuildFailed(error.to_string()))?;
867 let encoded = serde_json::to_vec(&record)
868 .map_err(|error| QueryError::IndexRebuildFailed(error.to_string()))?;
869 if encoded.len() as u64 > MAX_INDEX_BYTES {
870 return Err(QueryError::IndexRebuildFailed(
871 "derived index exceeds 64 MiB".to_owned(),
872 ));
873 }
874 self.ensure_root_authority()?;
875 let observation_guard = after_observation();
876 let publication: Result<IndexRead, QueryError> = (|| {
877 if let Err(first) = self.state.ensure_private_dir(Path::new(INDEX_ROOT)) {
878 self.state
879 .remove_private_leaf_durable(Path::new(INDEX_ROOT))
880 .map_err(|error| QueryError::IndexRebuildFailed(error.to_string()))?;
881 self.state
882 .ensure_private_dir(Path::new(INDEX_ROOT))
883 .map_err(|error| {
884 QueryError::IndexRebuildFailed(format!("{first}; recovery failed: {error}"))
885 })?;
886 }
887 self.state
888 .sanitize_private_single_file_namespace(
889 Path::new(INDEX_ROOT),
890 Path::new("index.json").as_os_str(),
891 )
892 .map_err(|error| QueryError::IndexRebuildFailed(error.to_string()))?;
893 self.state
894 .replace_with_before_publish(Path::new(INDEX_RECORD), &encoded, before_publish)
895 .map_err(|error| QueryError::IndexRebuildFailed(error.to_string()))?;
896 Ok(read_index(&self.state, &live_state))
897 })();
898 drop(observation_guard);
899 let verified = publication?;
900 self.ensure_observation_authority(&observation)?;
901 if verified.state != QueryIndexState::Fresh {
902 return Err(QueryError::IndexRebuildFailed(
903 "published index did not verify against its observation".to_owned(),
904 ));
905 }
906 Ok(QueryIndexRebuildResult {
907 root: observation.root,
908 folderbase_id: observation.folderbase_id,
909 generation: observation.generation,
910 records: observation.entries.len(),
911 exclusions: observation.exclusions.len(),
912 })
913 }
914}
915
916#[derive(Serialize)]
917struct NormalizedQueryRequest<'a> {
918 format: &'static str,
919 scope: NormalizedQueryScope<'a>,
920 filters: NormalizedQueryFilters,
921 page: NormalizedQueryPage,
922}
923
924#[derive(Serialize)]
925#[serde(tag = "kind", rename_all = "snake_case")]
926enum NormalizedQueryScope<'a> {
927 Live,
928 Historical { folderbase_version_id: &'a str },
929}
930
931#[derive(Serialize)]
932struct NormalizedQueryFilters {
933 paths: Vec<String>,
934 path_prefixes: Vec<String>,
935 kinds: Vec<QueryEntryKind>,
936 lifecycles: Vec<QueryLifecycle>,
937 object_ids: Vec<String>,
938 object_version_ids: Vec<String>,
939 minimum_bytes: Option<u64>,
940 maximum_bytes: Option<u64>,
941}
942
943impl NormalizedQueryFilters {
944 fn applies(&self, entry: &QueryEntry) -> bool {
945 (self.paths.is_empty() || self.paths.iter().any(|path| path == &entry.path))
946 && (self.path_prefixes.is_empty()
947 || self.path_prefixes.iter().any(|prefix| {
948 entry.path == *prefix || entry.path.starts_with(&format!("{prefix}/"))
949 }))
950 && (self.kinds.is_empty() || self.kinds.contains(&entry.kind))
951 && (self.lifecycles.is_empty() || self.lifecycles.contains(&entry.lifecycle))
952 && (self.object_ids.is_empty()
953 || entry
954 .object_id
955 .as_ref()
956 .is_some_and(|value| self.object_ids.contains(value)))
957 && (self.object_version_ids.is_empty()
958 || entry
959 .object_version_id
960 .as_ref()
961 .is_some_and(|value| self.object_version_ids.contains(value)))
962 && self
963 .minimum_bytes
964 .is_none_or(|minimum| entry.bytes.is_some_and(|bytes| bytes >= minimum))
965 && self
966 .maximum_bytes
967 .is_none_or(|maximum| entry.bytes.is_some_and(|bytes| bytes <= maximum))
968 }
969}
970
971#[derive(Serialize)]
972struct NormalizedQueryPage {
973 limit: usize,
974}
975
976struct NormalizedRequest<'a> {
977 value: NormalizedQueryRequest<'a>,
978 filters: NormalizedQueryFilters,
979 limit: usize,
980}
981
982fn normalize_request(request: &QueryRequest) -> Result<NormalizedRequest<'_>, QueryError> {
983 if request.format != QUERY_REQUEST_FORMAT {
984 return Err(QueryError::InvalidQueryRequest(
985 "unsupported request format".to_owned(),
986 ));
987 }
988 if !(1..=MAX_PAGE_LIMIT).contains(&request.page.limit) {
989 return Err(QueryError::InvalidQueryRequest(
990 "page limit must be from 1 through 1000".to_owned(),
991 ));
992 }
993 let scope = match &request.scope {
994 QueryScope::Live => NormalizedQueryScope::Live,
995 QueryScope::Historical {
996 folderbase_version_id,
997 } => {
998 validate_capture_version_id(folderbase_version_id)
999 .map_err(|error| QueryError::InvalidQueryRequest(error.to_string()))?;
1000 NormalizedQueryScope::Historical {
1001 folderbase_version_id,
1002 }
1003 }
1004 };
1005 validate_filter_bounds(&request.filters)?;
1006 let paths = normalize_paths(&request.filters.paths, "paths")?;
1007 let path_prefixes = normalize_paths(&request.filters.path_prefixes, "path_prefixes")?;
1008 let kinds = normalize_set(&request.filters.kinds);
1009 let lifecycles = normalize_set(&request.filters.lifecycles);
1010 let object_ids = normalize_identifiers(&request.filters.object_ids, "obj_", "object_ids")?;
1011 let object_version_ids = normalize_identifiers(
1012 &request.filters.object_version_ids,
1013 "version_",
1014 "object_version_ids",
1015 )?;
1016 let filters = NormalizedQueryFilters {
1017 paths,
1018 path_prefixes,
1019 kinds,
1020 lifecycles,
1021 object_ids,
1022 object_version_ids,
1023 minimum_bytes: request.filters.minimum_bytes,
1024 maximum_bytes: request.filters.maximum_bytes,
1025 };
1026 let value = NormalizedQueryRequest {
1027 format: QUERY_REQUEST_FORMAT,
1028 scope,
1029 filters: NormalizedQueryFilters {
1030 paths: filters.paths.clone(),
1031 path_prefixes: filters.path_prefixes.clone(),
1032 kinds: filters.kinds.clone(),
1033 lifecycles: filters.lifecycles.clone(),
1034 object_ids: filters.object_ids.clone(),
1035 object_version_ids: filters.object_version_ids.clone(),
1036 minimum_bytes: filters.minimum_bytes,
1037 maximum_bytes: filters.maximum_bytes,
1038 },
1039 page: NormalizedQueryPage {
1040 limit: request.page.limit,
1041 },
1042 };
1043 Ok(NormalizedRequest {
1044 value,
1045 filters,
1046 limit: request.page.limit,
1047 })
1048}
1049
1050fn validate_filter_bounds(filters: &QueryFilters) -> Result<(), QueryError> {
1051 for (length, maximum, label) in [
1052 (filters.paths.len(), 256, "paths"),
1053 (filters.path_prefixes.len(), 256, "path_prefixes"),
1054 (filters.kinds.len(), 4, "kinds"),
1055 (filters.lifecycles.len(), 2, "lifecycles"),
1056 (filters.object_ids.len(), 256, "object_ids"),
1057 (filters.object_version_ids.len(), 256, "object_version_ids"),
1058 ] {
1059 if length > maximum {
1060 return Err(QueryError::InvalidQueryRequest(format!(
1061 "{label} exceeds its bounded item limit"
1062 )));
1063 }
1064 }
1065 if filters.minimum_bytes > filters.maximum_bytes && filters.maximum_bytes.is_some() {
1066 return Err(QueryError::InvalidQueryRequest(
1067 "minimum_bytes must not exceed maximum_bytes".to_owned(),
1068 ));
1069 }
1070 if filters
1071 .minimum_bytes
1072 .into_iter()
1073 .chain(filters.maximum_bytes)
1074 .any(|bytes| bytes > 1_099_511_627_776)
1075 {
1076 return Err(QueryError::InvalidQueryRequest(
1077 "byte filter exceeds 1 TiB".to_owned(),
1078 ));
1079 }
1080 Ok(())
1081}
1082
1083fn normalize_paths(values: &[String], label: &str) -> Result<Vec<String>, QueryError> {
1084 let mut exact = BTreeSet::new();
1085 let mut nfc = BTreeMap::new();
1086 let mut folded = BTreeMap::new();
1087 for path in values {
1088 validate_capture_path(path)
1089 .map_err(|error| QueryError::InvalidQueryRequest(error.to_string()))?;
1090 let nfc_key = path.nfc().collect::<String>();
1091 let folded_key = nfc_key
1092 .case_fold()
1093 .collect::<String>()
1094 .nfc()
1095 .collect::<String>();
1096 for (index, key) in [(&mut nfc, nfc_key), (&mut folded, folded_key)] {
1097 if index
1098 .insert(key, path.as_str())
1099 .is_some_and(|existing| existing != path)
1100 {
1101 return Err(QueryError::InvalidQueryRequest(format!(
1102 "{label} contains a portable-path collision"
1103 )));
1104 }
1105 }
1106 exact.insert(path.clone());
1107 }
1108 Ok(exact.into_iter().collect())
1109}
1110
1111fn normalize_identifiers(
1112 values: &[String],
1113 prefix: &str,
1114 label: &str,
1115) -> Result<Vec<String>, QueryError> {
1116 let mut normalized = BTreeSet::new();
1117 for value in values {
1118 let uuid = value.strip_prefix(prefix).ok_or_else(|| {
1119 QueryError::InvalidQueryRequest(format!("{label} contains the wrong namespace"))
1120 })?;
1121 let parsed = Uuid::parse_str(uuid).map_err(|_| {
1122 QueryError::InvalidQueryRequest(format!("{label} contains an invalid UUID"))
1123 })?;
1124 if parsed.hyphenated().to_string() != uuid
1125 || !(1..=8).contains(&(parsed.as_bytes()[6] >> 4))
1126 || parsed.as_bytes()[8] & 0xc0 != 0x80
1127 {
1128 return Err(QueryError::InvalidQueryRequest(format!(
1129 "{label} contains an unsupported UUID"
1130 )));
1131 }
1132 normalized.insert(value.clone());
1133 }
1134 Ok(normalized.into_iter().collect())
1135}
1136
1137fn normalize_set<T: Ord + Copy>(values: &[T]) -> Vec<T> {
1138 values
1139 .iter()
1140 .copied()
1141 .collect::<BTreeSet<_>>()
1142 .into_iter()
1143 .collect()
1144}
1145
1146struct QueryObservation {
1147 root: PathBuf,
1148 root_instance_sha256: String,
1149 folderbase_id: String,
1150 generation: String,
1151 entries: Vec<QueryEntry>,
1152 exclusions: Vec<QueryExclusion>,
1153}
1154
1155struct LiveObservationState {
1156 plan: CapturePlan,
1157 identity: LiveIdentityProjection,
1158 generation: String,
1159}
1160
1161impl LiveObservationState {
1162 fn observation_with(
1163 &self,
1164 entries: Vec<QueryEntry>,
1165 exclusions: Vec<QueryExclusion>,
1166 ) -> QueryObservation {
1167 QueryObservation {
1168 root: self.plan.root().to_path_buf(),
1169 root_instance_sha256: self.plan.root_instance_sha256().to_owned(),
1170 folderbase_id: self.plan.folderbase_id().to_owned(),
1171 generation: self.generation.clone(),
1172 entries,
1173 exclusions,
1174 }
1175 }
1176}
1177
1178#[derive(Debug, Serialize, Deserialize)]
1179#[serde(deny_unknown_fields)]
1180struct PrivateIndexRecord {
1181 format: String,
1182 generation: String,
1183 root_instance_sha256: String,
1184 folderbase_id: String,
1185 projection_sha256: String,
1186 content_sha256: String,
1187 entries: Vec<QueryEntry>,
1188 exclusions: Vec<QueryExclusion>,
1189}
1190
1191fn private_index_content_sha256(record: &PrivateIndexRecord) -> Result<String, serde_json::Error> {
1192 #[derive(Serialize)]
1193 struct Content<'a> {
1194 format: &'a str,
1195 generation: &'a str,
1196 root_instance_sha256: &'a str,
1197 folderbase_id: &'a str,
1198 projection_sha256: &'a str,
1199 entries: &'a [QueryEntry],
1200 exclusions: &'a [QueryExclusion],
1201 }
1202 let content = Content {
1203 format: &record.format,
1204 generation: &record.generation,
1205 root_instance_sha256: &record.root_instance_sha256,
1206 folderbase_id: &record.folderbase_id,
1207 projection_sha256: &record.projection_sha256,
1208 entries: &record.entries,
1209 exclusions: &record.exclusions,
1210 };
1211 let mut digest = Sha256::new();
1212 digest.update(b"folderbase-query-private-index-content-v1\0");
1213 serde_json::to_writer(ProjectionDigestWriter(&mut digest), &content)?;
1214 Ok(format!("{:x}", digest.finalize()))
1215}
1216
1217fn private_index_projection_sha256(record: &PrivateIndexRecord) -> String {
1218 let mut digest = Sha256::new();
1219 digest.update(b"folderbase-query-live-projection-v1\0");
1220 for entry in &record.entries {
1221 update_projection_digest(&mut digest, b'E', entry);
1222 }
1223 for exclusion in &record.exclusions {
1224 update_projection_digest(&mut digest, b'X', exclusion);
1225 }
1226 format!("{:x}", digest.finalize())
1227}
1228
1229fn update_projection_digest<T: Serialize>(digest: &mut Sha256, tag: u8, value: &T) {
1230 let mut length = ProjectionLengthWriter::default();
1231 serde_json::to_writer(&mut length, value)
1232 .expect("typed query projections serialize to a counting writer");
1233 digest.update([tag]);
1234 digest.update(length.bytes.to_be_bytes());
1235 serde_json::to_writer(ProjectionDigestWriter(digest), value)
1236 .expect("typed query projections serialize to a digest writer");
1237}
1238
1239#[derive(Default)]
1240struct ProjectionLengthWriter {
1241 bytes: u64,
1242}
1243
1244impl std::io::Write for ProjectionLengthWriter {
1245 fn write(&mut self, bytes: &[u8]) -> std::io::Result<usize> {
1246 self.bytes = self
1247 .bytes
1248 .checked_add(bytes.len() as u64)
1249 .expect("bounded query projection length fits u64");
1250 Ok(bytes.len())
1251 }
1252
1253 fn flush(&mut self) -> std::io::Result<()> {
1254 Ok(())
1255 }
1256}
1257
1258struct ProjectionDigestWriter<'a>(&'a mut Sha256);
1259
1260impl std::io::Write for ProjectionDigestWriter<'_> {
1261 fn write(&mut self, bytes: &[u8]) -> std::io::Result<usize> {
1262 self.0.update(bytes);
1263 Ok(bytes.len())
1264 }
1265
1266 fn flush(&mut self) -> std::io::Result<()> {
1267 Ok(())
1268 }
1269}
1270
1271struct IndexRead {
1272 state: QueryIndexState,
1273 generation: Option<String>,
1274 records: usize,
1275 record: Option<PrivateIndexRecord>,
1276}
1277
1278impl IndexRead {
1279 fn absent() -> Self {
1280 Self {
1281 state: QueryIndexState::Absent,
1282 generation: None,
1283 records: 0,
1284 record: None,
1285 }
1286 }
1287
1288 fn stale(generation: Option<String>, records: usize) -> Self {
1289 Self {
1290 state: QueryIndexState::Stale,
1291 generation,
1292 records,
1293 record: None,
1294 }
1295 }
1296}
1297
1298fn read_index(state: &FolderbaseState, observation: &LiveObservationState) -> IndexRead {
1299 let encoded = match state.read_bounded_if_present(Path::new(INDEX_RECORD), MAX_INDEX_BYTES) {
1300 Ok(Some(encoded)) => encoded,
1301 Ok(None) => return IndexRead::absent(),
1302 Err(_) => return IndexRead::stale(None, 0),
1303 };
1304 let record: PrivateIndexRecord = match serde_json::from_slice(&encoded) {
1305 Ok(record) => record,
1306 Err(_) => return IndexRead::stale(None, 0),
1307 };
1308 let generation = is_sha256(&record.generation).then(|| record.generation.clone());
1309 let records = record.entries.len();
1310 let bounded = record.entries.len() + record.exclusions.len() <= MAX_INDEX_RECORDS;
1311 let ordered = record
1312 .entries
1313 .windows(2)
1314 .all(|pair| compare_entries(&pair[0], &pair[1]) == Ordering::Less)
1315 && record
1316 .exclusions
1317 .windows(2)
1318 .all(|pair| pair[0].path.as_bytes() < pair[1].path.as_bytes());
1319 let paths_valid = record
1320 .entries
1321 .iter()
1322 .all(|entry| validate_capture_path(&entry.path).is_ok())
1323 && record
1324 .exclusions
1325 .iter()
1326 .all(|entry| validate_capture_path(&entry.path).is_ok());
1327 let content_valid = is_sha256(&record.content_sha256)
1328 && private_index_content_sha256(&record).ok().as_deref()
1329 == Some(record.content_sha256.as_str());
1330 let projection_valid = is_sha256(&record.projection_sha256)
1331 && private_index_projection_sha256(&record) == record.projection_sha256
1332 && live_projection_sha256(observation) == record.projection_sha256;
1333 let equivalent = record.format == INDEX_FORMAT
1334 && record.generation == observation.generation
1335 && record.root_instance_sha256 == observation.plan.root_instance_sha256()
1336 && record.folderbase_id == observation.plan.folderbase_id();
1337 if bounded && ordered && paths_valid && content_valid && projection_valid && equivalent {
1338 IndexRead {
1339 state: QueryIndexState::Fresh,
1340 generation,
1341 records,
1342 record: Some(record),
1343 }
1344 } else {
1345 IndexRead::stale(generation, records.min(MAX_INDEX_RECORDS))
1346 }
1347}
1348
1349fn observe_live_state(
1350 store: &FolderbaseVersionStore,
1351 state: &FolderbaseState,
1352) -> Result<LiveObservationState, QueryError> {
1353 let plan = store.plan_capture()?;
1354 let identity = resolve_live_identity(&plan, state);
1355 let generation = live_observation_generation(&plan, &identity)?;
1356 Ok(LiveObservationState {
1357 plan,
1358 identity,
1359 generation,
1360 })
1361}
1362
1363fn project_live_observation(state: &LiveObservationState) -> QueryObservation {
1364 let mut entries = project_live_entries(&state.plan);
1365 if let Some(version) = state.identity.version.as_ref() {
1366 for entry in &mut entries {
1367 let Some(binding) = version.lookup_binding(&entry.path) else {
1368 continue;
1369 };
1370 let compatible = matches!(
1371 (entry.kind, binding.kind()),
1372 (QueryEntryKind::Directory, PathBindingKind::Directory)
1373 | (QueryEntryKind::RegularFile, PathBindingKind::RegularFile)
1374 | (QueryEntryKind::Symlink, PathBindingKind::Symlink)
1375 );
1376 if compatible {
1377 entry.object_id = Some(binding.object_id().to_owned());
1378 entry.object_version_id = binding.object_version_id().map(str::to_owned);
1379 }
1380 }
1381 }
1382 state.observation_with(entries, project_live_exclusions(&state.plan))
1383}
1384
1385struct LiveIdentityProjection {
1386 state: &'static str,
1387 canonical_digest: Option<String>,
1388 version: Option<FolderbaseVersion>,
1389}
1390
1391fn resolve_live_identity(plan: &CapturePlan, state: &FolderbaseState) -> LiveIdentityProjection {
1392 let Some(head) = plan.current_local_head() else {
1393 return LiveIdentityProjection {
1394 state: "absent",
1395 canonical_digest: None,
1396 version: None,
1397 };
1398 };
1399 let Ok(version) = read_historical_version(state, head.version_id()) else {
1400 return LiveIdentityProjection {
1401 state: "unresolved",
1402 canonical_digest: None,
1403 version: None,
1404 };
1405 };
1406 let Ok(canonical_digest) = version.canonical_digest() else {
1407 return LiveIdentityProjection {
1408 state: "unresolved",
1409 canonical_digest: None,
1410 version: None,
1411 };
1412 };
1413 if version.folderbase_id() != plan.folderbase_id() || canonical_digest != head.version_sha256()
1414 {
1415 return LiveIdentityProjection {
1416 state: "unresolved",
1417 canonical_digest: None,
1418 version: None,
1419 };
1420 }
1421 LiveIdentityProjection {
1422 state: "verified",
1423 canonical_digest: Some(canonical_digest),
1424 version: Some(version),
1425 }
1426}
1427
1428fn observe_historical(
1429 store: &FolderbaseVersionStore,
1430 state: &FolderbaseState,
1431 version_id: &str,
1432) -> Result<QueryObservation, QueryError> {
1433 let attestation = &store.root_attestation;
1434 let version = read_historical_version(state, version_id)?;
1435 if version.version_id() != version_id || version.folderbase_id() != attestation.folderbase_id {
1436 return Err(QueryError::ScopeVersionInvalid {
1437 version_id: version_id.to_owned(),
1438 message: "Version identity does not bind the requested Folderbase".to_owned(),
1439 });
1440 }
1441 let canonical_digest =
1442 version
1443 .canonical_digest()
1444 .map_err(|error| QueryError::ScopeVersionInvalid {
1445 version_id: version_id.to_owned(),
1446 message: error.to_string(),
1447 })?;
1448 let mut entries = version
1449 .bindings()
1450 .iter()
1451 .map(|binding| QueryEntry {
1452 path: binding.path().to_owned(),
1453 kind: query_binding_kind(binding.kind()),
1454 lifecycle: QueryLifecycle::Live,
1455 bytes: binding.bytes(),
1456 executable: binding.executable(),
1457 symlink_target: binding.symlink_target().map(str::to_owned),
1458 object_id: Some(binding.object_id().to_owned()),
1459 object_version_id: binding.object_version_id().map(str::to_owned),
1460 folderbase_version_id: Some(version_id.to_owned()),
1461 source: QuerySource::FolderbaseVersion,
1462 boundary_reason: None,
1463 })
1464 .collect::<Vec<_>>();
1465 entries.extend(version.tombstones().iter().map(|tombstone| QueryEntry {
1466 path: tombstone.path().to_owned(),
1467 kind: match tombstone.deleted_kind() {
1468 DeletedKind::Directory => QueryEntryKind::Directory,
1469 DeletedKind::RegularFile => QueryEntryKind::RegularFile,
1470 DeletedKind::Symlink => QueryEntryKind::Symlink,
1471 },
1472 lifecycle: QueryLifecycle::Deleted,
1473 bytes: None,
1474 executable: None,
1475 symlink_target: None,
1476 object_id: Some(tombstone.object_id().to_owned()),
1477 object_version_id: tombstone.last_object_version_id().map(str::to_owned),
1478 folderbase_version_id: Some(version_id.to_owned()),
1479 source: QuerySource::FolderbaseVersion,
1480 boundary_reason: None,
1481 }));
1482 entries.extend(
1483 version
1484 .exclusions()
1485 .iter()
1486 .filter(|exclusion| exclusion.kind() == ExclusionKind::NestedFolderbase)
1487 .map(|exclusion| QueryEntry {
1488 path: exclusion.path().to_owned(),
1489 kind: QueryEntryKind::NestedFolderbase,
1490 lifecycle: QueryLifecycle::Live,
1491 bytes: None,
1492 executable: None,
1493 symlink_target: None,
1494 object_id: None,
1495 object_version_id: None,
1496 folderbase_version_id: Some(version_id.to_owned()),
1497 source: QuerySource::FolderbaseVersion,
1498 boundary_reason: Some("nested-folderbase-boundary".to_owned()),
1499 }),
1500 );
1501 entries.sort_by(compare_entries);
1502 let exclusions = version
1503 .exclusions()
1504 .iter()
1505 .map(|exclusion| QueryExclusion {
1506 path: exclusion.path().to_owned(),
1507 reason: match exclusion.kind() {
1508 ExclusionKind::NestedFolderbase => "nested-folderbase-boundary",
1509 _ => "unsupported-v1",
1510 }
1511 .to_owned(),
1512 kind: Some(query_version_exclusion_kind(exclusion.kind())),
1513 })
1514 .collect();
1515 let mut digest = Sha256::new();
1516 digest.update(b"folderbase-query-historical-observation-v1\0");
1517 digest.update(attestation.root_instance_sha256.as_bytes());
1518 digest.update(version_id.as_bytes());
1519 digest.update(canonical_digest.as_bytes());
1520 Ok(QueryObservation {
1521 root: attestation.root.clone(),
1522 root_instance_sha256: attestation.root_instance_sha256.clone(),
1523 folderbase_id: attestation.folderbase_id.clone(),
1524 generation: format!("{:x}", digest.finalize()),
1525 entries,
1526 exclusions,
1527 })
1528}
1529
1530#[derive(Serialize, Deserialize)]
1531#[serde(deny_unknown_fields)]
1532struct QueryCursorPayload {
1533 root_instance_sha256: String,
1534 request_sha256: String,
1535 observation_generation: String,
1536 last_row_key: QueryRowKey,
1537}
1538
1539fn encode_cursor(payload: &QueryCursorPayload) -> Result<String, QueryError> {
1540 let bytes = serde_json::to_vec(payload).map_err(|_| QueryError::InvalidQueryCursor)?;
1541 let mut checksum = Sha256::new();
1542 checksum.update(b"folderbase-query-cursor-v1\0");
1543 checksum.update(&bytes);
1544 let mut encoded = String::with_capacity(5 + bytes.len() * 2 + 64);
1545 encoded.push_str("fbq1_");
1546 append_hex(&mut encoded, &bytes);
1547 append_hex(&mut encoded, &checksum.finalize());
1548 if encoded.len() > 8_192 {
1549 return Err(QueryError::InvalidQueryCursor);
1550 }
1551 Ok(encoded)
1552}
1553
1554fn decode_cursor(cursor: &str) -> Result<QueryCursorPayload, QueryError> {
1555 let encoded = cursor
1556 .strip_prefix("fbq1_")
1557 .ok_or(QueryError::InvalidQueryCursor)?;
1558 if cursor.len() > 8_192 || encoded.len() < 66 || encoded.len() % 2 != 0 {
1559 return Err(QueryError::InvalidQueryCursor);
1560 }
1561 let (payload, checksum) = encoded.split_at(encoded.len() - 64);
1562 let bytes = decode_hex(payload)?;
1563 let expected = decode_hex(checksum)?;
1564 let mut digest = Sha256::new();
1565 digest.update(b"folderbase-query-cursor-v1\0");
1566 digest.update(&bytes);
1567 if digest.finalize().as_slice() != expected {
1568 return Err(QueryError::InvalidQueryCursor);
1569 }
1570 let payload: QueryCursorPayload =
1571 serde_json::from_slice(&bytes).map_err(|_| QueryError::InvalidQueryCursor)?;
1572 if !is_sha256(&payload.root_instance_sha256)
1573 || !is_sha256(&payload.request_sha256)
1574 || !is_sha256(&payload.observation_generation)
1575 || validate_capture_path(&payload.last_row_key.path).is_err()
1576 {
1577 return Err(QueryError::InvalidQueryCursor);
1578 }
1579 Ok(payload)
1580}
1581
1582fn append_hex(output: &mut String, bytes: &[u8]) {
1583 const HEX: &[u8; 16] = b"0123456789abcdef";
1584 for byte in bytes {
1585 output.push(char::from(HEX[(byte >> 4) as usize]));
1586 output.push(char::from(HEX[(byte & 0xf) as usize]));
1587 }
1588}
1589
1590fn decode_hex(encoded: &str) -> Result<Vec<u8>, QueryError> {
1591 encoded
1592 .as_bytes()
1593 .chunks_exact(2)
1594 .map(|pair| {
1595 let high = hex_nibble(pair[0]).ok_or(QueryError::InvalidQueryCursor)?;
1596 let low = hex_nibble(pair[1]).ok_or(QueryError::InvalidQueryCursor)?;
1597 Ok((high << 4) | low)
1598 })
1599 .collect()
1600}
1601
1602fn hex_nibble(byte: u8) -> Option<u8> {
1603 match byte {
1604 b'0'..=b'9' => Some(byte - b'0'),
1605 b'a'..=b'f' => Some(byte - b'a' + 10),
1606 _ => None,
1607 }
1608}
1609
1610fn is_sha256(value: &str) -> bool {
1611 value.len() == 64
1612 && value
1613 .bytes()
1614 .all(|byte| byte.is_ascii_digit() || (b'a'..=b'f').contains(&byte))
1615}
1616
1617fn read_historical_version(
1618 state: &FolderbaseState,
1619 version_id: &str,
1620) -> Result<FolderbaseVersion, QueryError> {
1621 validate_capture_version_id(version_id)
1622 .map_err(|error| QueryError::InvalidQueryRequest(error.to_string()))?;
1623 let relative = Path::new(".folderbase/versions/folderbase").join(format!("{version_id}.json"));
1624 let encoded = match state.read_bounded(&relative, MAX_ENCODED_VERSION_BYTES) {
1625 Ok(Some(encoded)) => encoded,
1626 Ok(None) => {
1627 return Err(QueryError::ScopeVersionMissing {
1628 version_id: version_id.to_owned(),
1629 });
1630 }
1631 Err(FolderbaseError::Io { ref source, .. })
1632 if source.kind() == std::io::ErrorKind::NotFound =>
1633 {
1634 return Err(QueryError::ScopeVersionMissing {
1635 version_id: version_id.to_owned(),
1636 });
1637 }
1638 Err(error) => {
1639 return Err(QueryError::ScopeVersionInvalid {
1640 version_id: version_id.to_owned(),
1641 message: error.to_string(),
1642 });
1643 }
1644 };
1645 FolderbaseVersion::decode_bounded(encoded.as_slice()).map_err(|error| {
1646 QueryError::ScopeVersionInvalid {
1647 version_id: version_id.to_owned(),
1648 message: error.to_string(),
1649 }
1650 })
1651}
1652
1653fn query_binding_kind(kind: PathBindingKind) -> QueryEntryKind {
1654 match kind {
1655 PathBindingKind::Directory => QueryEntryKind::Directory,
1656 PathBindingKind::RegularFile => QueryEntryKind::RegularFile,
1657 PathBindingKind::Symlink => QueryEntryKind::Symlink,
1658 }
1659}
1660
1661fn query_version_exclusion_kind(kind: ExclusionKind) -> QueryExclusionKind {
1662 match kind {
1663 ExclusionKind::NestedFolderbase => QueryExclusionKind::NestedFolderbase,
1664 ExclusionKind::HardLink => QueryExclusionKind::HardLink,
1665 ExclusionKind::Fifo => QueryExclusionKind::Fifo,
1666 ExclusionKind::Socket => QueryExclusionKind::Socket,
1667 ExclusionKind::BlockDevice => QueryExclusionKind::BlockDevice,
1668 ExclusionKind::CharacterDevice => QueryExclusionKind::CharacterDevice,
1669 ExclusionKind::OtherSpecial => QueryExclusionKind::OtherSpecial,
1670 }
1671}
1672
1673fn query_capture_kind(kind: CaptureEntryKind) -> QueryEntryKind {
1674 match kind {
1675 CaptureEntryKind::Directory => QueryEntryKind::Directory,
1676 CaptureEntryKind::RegularFile => QueryEntryKind::RegularFile,
1677 CaptureEntryKind::Symlink => QueryEntryKind::Symlink,
1678 }
1679}
1680
1681fn query_capture_exclusion_kind(kind: CaptureExclusionKind) -> QueryExclusionKind {
1682 match kind {
1683 CaptureExclusionKind::NestedFolderbase => QueryExclusionKind::NestedFolderbase,
1684 CaptureExclusionKind::HardLink => QueryExclusionKind::HardLink,
1685 CaptureExclusionKind::Fifo => QueryExclusionKind::Fifo,
1686 CaptureExclusionKind::Socket => QueryExclusionKind::Socket,
1687 CaptureExclusionKind::BlockDevice => QueryExclusionKind::BlockDevice,
1688 CaptureExclusionKind::CharacterDevice => QueryExclusionKind::CharacterDevice,
1689 CaptureExclusionKind::OtherSpecial => QueryExclusionKind::OtherSpecial,
1690 }
1691}
1692
1693fn query_capture_exclusion_reason(reason: CaptureExclusionReason) -> &'static str {
1694 match reason {
1695 CaptureExclusionReason::NestedFolderbaseBoundary => "nested-folderbase-boundary",
1696 CaptureExclusionReason::UnsupportedV1 => "unsupported-v1",
1697 }
1698}
1699
1700fn live_capture_entry(entry: &CapturePlanEntry) -> QueryEntry {
1701 #[cfg(test)]
1702 LIVE_RESULT_ROW_MATERIALIZATIONS.with(|count| count.set(count.get() + 1));
1703 QueryEntry {
1704 path: entry.path().to_owned(),
1705 kind: query_capture_kind(entry.kind()),
1706 lifecycle: QueryLifecycle::Live,
1707 bytes: entry.bytes(),
1708 executable: entry.executable(),
1709 symlink_target: entry.symlink_target().map(str::to_owned),
1710 object_id: None,
1711 object_version_id: None,
1712 folderbase_version_id: None,
1713 source: QuerySource::CapturePlan,
1714 boundary_reason: None,
1715 }
1716}
1717
1718fn live_boundary_entry(exclusion: &CapturePlanExclusion) -> QueryEntry {
1719 #[cfg(test)]
1720 LIVE_RESULT_ROW_MATERIALIZATIONS.with(|count| count.set(count.get() + 1));
1721 QueryEntry {
1722 path: exclusion.path().to_owned(),
1723 kind: QueryEntryKind::NestedFolderbase,
1724 lifecycle: QueryLifecycle::Live,
1725 bytes: None,
1726 executable: None,
1727 symlink_target: None,
1728 object_id: None,
1729 object_version_id: None,
1730 folderbase_version_id: None,
1731 source: QuerySource::CapturePlan,
1732 boundary_reason: Some("nested-folderbase-boundary".to_owned()),
1733 }
1734}
1735
1736fn live_identity_fields<'a>(
1737 state: &'a LiveObservationState,
1738 path: &str,
1739 kind: QueryEntryKind,
1740) -> (Option<&'a str>, Option<&'a str>) {
1741 let Some(version) = state.identity.version.as_ref() else {
1742 return (None, None);
1743 };
1744 let Some(binding) = version.lookup_binding(path) else {
1745 return (None, None);
1746 };
1747 let compatible = matches!(
1748 (kind, binding.kind()),
1749 (QueryEntryKind::Directory, PathBindingKind::Directory)
1750 | (QueryEntryKind::RegularFile, PathBindingKind::RegularFile)
1751 | (QueryEntryKind::Symlink, PathBindingKind::Symlink)
1752 );
1753 if compatible {
1754 (Some(binding.object_id()), binding.object_version_id())
1755 } else {
1756 (None, None)
1757 }
1758}
1759
1760fn live_ignored_exclusion(ignored: &CaptureIgnoredPath) -> QueryExclusion {
1761 #[cfg(test)]
1762 LIVE_RESULT_EXCLUSION_MATERIALIZATIONS.with(|count| count.set(count.get() + 1));
1763 QueryExclusion {
1764 path: ignored.path().to_owned(),
1765 reason: "capture-ignore-policy".to_owned(),
1766 kind: None,
1767 }
1768}
1769
1770fn live_plan_exclusion(exclusion: &CapturePlanExclusion) -> QueryExclusion {
1771 #[cfg(test)]
1772 LIVE_RESULT_EXCLUSION_MATERIALIZATIONS.with(|count| count.set(count.get() + 1));
1773 QueryExclusion {
1774 path: exclusion.path().to_owned(),
1775 reason: query_capture_exclusion_reason(exclusion.reason()).to_owned(),
1776 kind: Some(query_capture_exclusion_kind(exclusion.kind())),
1777 }
1778}
1779
1780#[derive(Serialize)]
1781struct BorrowedLiveEntry<'a> {
1782 path: &'a str,
1783 kind: QueryEntryKind,
1784 lifecycle: QueryLifecycle,
1785 bytes: Option<u64>,
1786 executable: Option<bool>,
1787 symlink_target: Option<&'a str>,
1788 object_id: Option<&'a str>,
1789 object_version_id: Option<&'a str>,
1790 folderbase_version_id: Option<&'a str>,
1791 source: QuerySource,
1792 boundary_reason: Option<&'a str>,
1793}
1794
1795impl<'a> BorrowedLiveEntry<'a> {
1796 fn capture(state: &'a LiveObservationState, entry: &'a CapturePlanEntry) -> Self {
1797 let kind = query_capture_kind(entry.kind());
1798 let (object_id, object_version_id) = live_identity_fields(state, entry.path(), kind);
1799 Self {
1800 path: entry.path(),
1801 kind,
1802 lifecycle: QueryLifecycle::Live,
1803 bytes: entry.bytes(),
1804 executable: entry.executable(),
1805 symlink_target: entry.symlink_target(),
1806 object_id,
1807 object_version_id,
1808 folderbase_version_id: None,
1809 source: QuerySource::CapturePlan,
1810 boundary_reason: None,
1811 }
1812 }
1813
1814 fn boundary(exclusion: &'a CapturePlanExclusion) -> Self {
1815 Self {
1816 path: exclusion.path(),
1817 kind: QueryEntryKind::NestedFolderbase,
1818 lifecycle: QueryLifecycle::Live,
1819 bytes: None,
1820 executable: None,
1821 symlink_target: None,
1822 object_id: None,
1823 object_version_id: None,
1824 folderbase_version_id: None,
1825 source: QuerySource::CapturePlan,
1826 boundary_reason: Some("nested-folderbase-boundary"),
1827 }
1828 }
1829}
1830
1831#[derive(Serialize)]
1832struct BorrowedLiveExclusion<'a> {
1833 path: &'a str,
1834 reason: &'static str,
1835 kind: Option<QueryExclusionKind>,
1836}
1837
1838impl<'a> BorrowedLiveExclusion<'a> {
1839 fn ignored(ignored: &'a CaptureIgnoredPath) -> Self {
1840 Self {
1841 path: ignored.path(),
1842 reason: "capture-ignore-policy",
1843 kind: None,
1844 }
1845 }
1846
1847 fn plan(exclusion: &'a CapturePlanExclusion) -> Self {
1848 Self {
1849 path: exclusion.path(),
1850 reason: query_capture_exclusion_reason(exclusion.reason()),
1851 kind: Some(query_capture_exclusion_kind(exclusion.kind())),
1852 }
1853 }
1854}
1855
1856fn live_projection_sha256(state: &LiveObservationState) -> String {
1857 let mut digest = Sha256::new();
1858 digest.update(b"folderbase-query-live-projection-v1\0");
1859 let mut entries = state.plan.entries().iter().peekable();
1860 let mut boundaries = state
1861 .plan
1862 .exclusions()
1863 .iter()
1864 .filter(|exclusion| exclusion.kind() == CaptureExclusionKind::NestedFolderbase)
1865 .peekable();
1866 while entries.peek().is_some() || boundaries.peek().is_some() {
1867 let take_entry = match (entries.peek(), boundaries.peek()) {
1868 (Some(entry), Some(boundary)) => entry.path().as_bytes() <= boundary.path().as_bytes(),
1869 (Some(_), None) => true,
1870 (None, Some(_)) => false,
1871 (None, None) => unreachable!(),
1872 };
1873 let entry = if take_entry {
1874 BorrowedLiveEntry::capture(state, entries.next().expect("peeked entry"))
1875 } else {
1876 BorrowedLiveEntry::boundary(boundaries.next().expect("peeked boundary"))
1877 };
1878 update_projection_digest(&mut digest, b'E', &entry);
1879 }
1880
1881 let mut ignored = state.plan.ignored_paths().iter().peekable();
1882 let mut exclusions = state.plan.exclusions().iter().peekable();
1883 while ignored.peek().is_some() || exclusions.peek().is_some() {
1884 let take_ignored = match (ignored.peek(), exclusions.peek()) {
1885 (Some(ignored), Some(exclusion)) => {
1886 ignored.path().as_bytes() <= exclusion.path().as_bytes()
1887 }
1888 (Some(_), None) => true,
1889 (None, Some(_)) => false,
1890 (None, None) => unreachable!(),
1891 };
1892 let exclusion = if take_ignored {
1893 BorrowedLiveExclusion::ignored(ignored.next().expect("peeked ignored path"))
1894 } else {
1895 BorrowedLiveExclusion::plan(exclusions.next().expect("peeked exclusion"))
1896 };
1897 update_projection_digest(&mut digest, b'X', &exclusion);
1898 }
1899 format!("{:x}", digest.finalize())
1900}
1901
1902fn project_live_entries(plan: &CapturePlan) -> Vec<QueryEntry> {
1903 let mut entries = plan
1904 .entries()
1905 .iter()
1906 .map(live_capture_entry)
1907 .collect::<Vec<_>>();
1908 entries.extend(
1909 plan.exclusions()
1910 .iter()
1911 .filter(|exclusion| exclusion.kind() == CaptureExclusionKind::NestedFolderbase)
1912 .map(live_boundary_entry),
1913 );
1914 entries.sort_by(compare_entries);
1915 entries
1916}
1917
1918fn project_live_exclusions(plan: &CapturePlan) -> Vec<QueryExclusion> {
1919 let mut exclusions = plan
1920 .ignored_paths()
1921 .iter()
1922 .map(live_ignored_exclusion)
1923 .collect::<Vec<_>>();
1924 exclusions.extend(plan.exclusions().iter().map(live_plan_exclusion));
1925 exclusions.sort_by(|left, right| left.path.as_bytes().cmp(right.path.as_bytes()));
1926 exclusions
1927}
1928
1929fn request_sha256(request: &NormalizedRequest<'_>) -> Result<String, QueryError> {
1930 let bytes = serde_json::to_vec(&request.value)
1931 .map_err(|error| QueryError::InvalidQueryRequest(error.to_string()))?;
1932 let mut digest = Sha256::new();
1933 digest.update(b"folderbase-query-request-v1\0");
1934 digest.update(bytes);
1935 Ok(format!("{:x}", digest.finalize()))
1936}
1937
1938fn live_observation_generation(
1939 plan: &CapturePlan,
1940 identity: &LiveIdentityProjection,
1941) -> Result<String, QueryError> {
1942 #[derive(Serialize)]
1943 struct ObservationEntry<'a> {
1944 path: &'a str,
1945 kind: CaptureEntryKind,
1946 bytes: Option<u64>,
1947 executable: Option<bool>,
1948 symlink_target: Option<&'a str>,
1949 metadata: &'a crate::folderbase_capture::CaptureMetadataFingerprint,
1950 }
1951
1952 #[derive(Serialize)]
1953 struct Observation<'a> {
1954 root_instance_sha256: &'a str,
1955 folderbase_id: &'a str,
1956 root_manifest_sha256: &'a str,
1957 root_manifest_bytes: u64,
1958 root_manifest_observed: &'a crate::folderbase_capture::CaptureMetadataFingerprint,
1959 ignore_policy_sha256: &'a str,
1960 local_head: Option<(
1961 &'a str,
1962 &'a str,
1963 &'a str,
1964 &'a str,
1965 &'a crate::folderbase_capture::CaptureMetadataFingerprint,
1966 )>,
1967 identity_projection: (&'a str, Option<&'a str>),
1968 entries: Vec<ObservationEntry<'a>>,
1969 exclusions: Vec<(&'a str, CaptureExclusionKind, CaptureExclusionReason)>,
1970 ignored_paths: Vec<&'a str>,
1971 }
1972 let local_head = plan.current_local_head().map(|head| {
1973 (
1974 head.version_id(),
1975 head.version_sha256(),
1976 head.authority().sha256(),
1977 head.encoded_sha256(),
1978 head.observed(),
1979 )
1980 });
1981 let observation = Observation {
1982 root_instance_sha256: plan.root_instance_sha256(),
1983 folderbase_id: plan.folderbase_id(),
1984 root_manifest_sha256: plan.root_manifest_sha256(),
1985 root_manifest_bytes: plan.root_manifest_bytes(),
1986 root_manifest_observed: plan.root_manifest_observed(),
1987 ignore_policy_sha256: plan.ignore_policy_sha256(),
1988 local_head,
1989 identity_projection: (identity.state, identity.canonical_digest.as_deref()),
1990 entries: plan
1991 .entries()
1992 .iter()
1993 .map(|entry| ObservationEntry {
1994 path: entry.path(),
1995 kind: entry.kind(),
1996 bytes: entry.bytes(),
1997 executable: entry.executable(),
1998 symlink_target: entry.symlink_target(),
1999 metadata: entry.observed(),
2000 })
2001 .collect(),
2002 exclusions: plan
2003 .exclusions()
2004 .iter()
2005 .map(|exclusion| (exclusion.path(), exclusion.kind(), exclusion.reason()))
2006 .collect(),
2007 ignored_paths: plan
2008 .ignored_paths()
2009 .iter()
2010 .map(|path| path.path())
2011 .collect(),
2012 };
2013 let bytes = serde_json::to_vec(&observation)
2014 .map_err(|error| QueryError::InvalidQueryRequest(error.to_string()))?;
2015 let mut digest = Sha256::new();
2016 digest.update(b"folderbase-query-live-observation-v1\0");
2017 digest.update(bytes);
2018 Ok(format!("{:x}", digest.finalize()))
2019}
2020
2021#[cfg(test)]
2022mod tests {
2023 use std::{
2024 fs, io,
2025 path::{Path, PathBuf},
2026 };
2027
2028 use tempfile::tempdir;
2029
2030 use super::{
2031 FolderbaseQueryEngine, INDEX_RECORD, LIVE_RESULT_EXCLUSION_MATERIALIZATIONS,
2032 LIVE_RESULT_ROW_MATERIALIZATIONS, PrivateIndexRecord, QueryError, QueryExecution,
2033 QueryIndexState, QueryRequest, private_index_content_sha256,
2034 private_index_projection_sha256,
2035 };
2036
2037 const MANIFEST: &[u8] = br#"{
2038 "$schema": "https://folderbase.ai/protocol/0.5/folderbase.schema.json",
2039 "protocol_version": "0.5.0",
2040 "folderbase": {
2041 "id": "folderbase_019f9b75-4f42-7f65-a012-2bfecdd8c473",
2042 "name": "Query failure fixture",
2043 "kind": "project",
2044 "status": "active",
2045 "created_at": "2026-08-04T00:00:00Z"
2046 },
2047 "adapters": [],
2048 "policies": {
2049 "availability": "keep_local",
2050 "structural_changes": "approve",
2051 "archive": "manual",
2052 "cloud_sync": "disabled",
2053 "capture_ignore": {"format": "folderbase-capture-ignore-v1", "rules": []}
2054 }
2055 }"#;
2056
2057 const MISSING_VERSION_ID: &str = "fbversion_019f0000-0000-7000-8000-000000000099";
2058
2059 struct AmbientRootSwap {
2060 visible: PathBuf,
2061 detached: PathBuf,
2062 replacement: PathBuf,
2063 }
2064
2065 impl AmbientRootSwap {
2066 fn activate(visible: &Path, replacement: &Path) -> Self {
2067 let detached = visible.with_file_name("detached-opening-root");
2068 fs::rename(visible, &detached).expect("detach opening root");
2069 fs::rename(replacement, visible).expect("install replacement root");
2070 Self {
2071 visible: visible.to_path_buf(),
2072 detached,
2073 replacement: replacement.to_path_buf(),
2074 }
2075 }
2076 }
2077
2078 impl Drop for AmbientRootSwap {
2079 fn drop(&mut self) {
2080 fs::rename(&self.visible, &self.replacement).expect("remove replacement root");
2081 fs::rename(&self.detached, &self.visible).expect("restore opening root");
2082 }
2083 }
2084
2085 fn initialize_root(root: &Path, ordinary_name: &str) {
2086 fs::create_dir(root).expect("Folderbase root");
2087 fs::create_dir(root.join(".folderbase")).expect("state");
2088 fs::write(root.join(".folderbase/manifest.json"), MANIFEST).expect("manifest");
2089 fs::write(root.join(ordinary_name), b"content\n").expect("ordinary file");
2090 }
2091
2092 #[test]
2093 fn fresh_index_validation_materializes_no_expected_result_rows() {
2094 const REPRESENTATIVE_ROWS: usize = 512;
2095
2096 let root = tempdir().expect("temporary Folderbase");
2097 fs::create_dir(root.path().join(".folderbase")).expect("state");
2098 fs::write(root.path().join(".folderbase/manifest.json"), MANIFEST).expect("manifest");
2099 for index in 0..REPRESENTATIVE_ROWS {
2100 fs::write(
2101 root.path().join(format!("ordinary-{index:04}.md")),
2102 b"ordinary\n",
2103 )
2104 .expect("ordinary file");
2105 }
2106 fs::create_dir_all(root.path().join("nested/.folderbase")).expect("nested state");
2107 fs::write(
2108 root.path().join("nested/.folderbase/manifest.json"),
2109 b"opaque nested manifest\n",
2110 )
2111 .expect("nested manifest");
2112 let engine = FolderbaseQueryEngine::open(root.path()).expect("query engine");
2113 engine.rebuild_index().expect("fresh index");
2114
2115 LIVE_RESULT_ROW_MATERIALIZATIONS.with(|count| count.set(0));
2116 LIVE_RESULT_EXCLUSION_MATERIALIZATIONS.with(|count| count.set(0));
2117 let indexed = engine.run(&QueryRequest::live(10)).expect("indexed query");
2118 assert_eq!(indexed.execution(), QueryExecution::PrivateIndex);
2119 let status = engine.index_status().expect("status");
2120 assert_eq!(status.state(), QueryIndexState::Fresh);
2121 assert_eq!(status.records(), REPRESENTATIVE_ROWS + 1);
2122 assert_eq!(
2123 engine
2124 .explain(&QueryRequest::live(10))
2125 .expect("indexed explain")
2126 .index_strategy(),
2127 QueryExecution::PrivateIndex
2128 );
2129 LIVE_RESULT_ROW_MATERIALIZATIONS.with(|count| assert_eq!(count.get(), 0));
2130 LIVE_RESULT_EXCLUSION_MATERIALIZATIONS.with(|count| assert_eq!(count.get(), 0));
2131
2132 fs::write(root.path().join("second.md"), b"second\n").expect("stale index");
2133 let scanned = engine.run(&QueryRequest::live(10)).expect("fallback query");
2134 assert_eq!(scanned.execution(), QueryExecution::BoundedScan);
2135 LIVE_RESULT_ROW_MATERIALIZATIONS.with(|count| assert!(count.get() > 0));
2136 LIVE_RESULT_EXCLUSION_MATERIALIZATIONS.with(|count| assert!(count.get() > 0));
2137 }
2138
2139 #[test]
2140 fn a_coherently_rehashed_forged_index_never_supplies_query_rows() {
2141 let root = tempdir().expect("temporary Folderbase");
2142 fs::create_dir(root.path().join(".folderbase")).expect("state");
2143 fs::write(root.path().join(".folderbase/manifest.json"), MANIFEST).expect("manifest");
2144 fs::write(root.path().join("ordinary.md"), b"ordinary\n").expect("ordinary file");
2145 let engine = FolderbaseQueryEngine::open(root.path()).expect("query engine");
2146 engine.rebuild_index().expect("fresh index");
2147
2148 let mut record: PrivateIndexRecord =
2149 serde_json::from_slice(&fs::read(root.path().join(INDEX_RECORD)).expect("index bytes"))
2150 .expect("private index record");
2151 record.entries[0].bytes = Some(999_999);
2152 record.projection_sha256 = private_index_projection_sha256(&record);
2153 record.content_sha256 = private_index_content_sha256(&record).expect("coherent forgery");
2154 fs::write(
2155 root.path().join(INDEX_RECORD),
2156 serde_json::to_vec(&record).expect("forged index bytes"),
2157 )
2158 .expect("replace private index");
2159
2160 let result = engine.run(&QueryRequest::live(10)).expect("safe fallback");
2161 assert_eq!(result.execution(), QueryExecution::BoundedScan);
2162 assert_eq!(result.entries()[0].bytes(), Some(9));
2163 }
2164
2165 #[test]
2166 fn cursor_continuation_reports_snapshot_change_before_parsing_a_changed_local_head() {
2167 let root = tempdir().expect("temporary Folderbase");
2168 fs::create_dir(root.path().join(".folderbase")).expect("state");
2169 fs::write(root.path().join(".folderbase/manifest.json"), MANIFEST).expect("manifest");
2170 fs::write(root.path().join("alpha.md"), b"alpha\n").expect("first ordinary file");
2171 fs::write(root.path().join("beta.md"), b"beta\n").expect("second ordinary file");
2172 let engine = FolderbaseQueryEngine::open(root.path()).expect("query engine");
2173 let mut request = QueryRequest::live(1);
2174 let first = engine.run(&request).expect("first page");
2175 request.page.cursor = Some(
2176 first
2177 .page()
2178 .next_cursor()
2179 .expect("first page cursor")
2180 .to_owned(),
2181 );
2182 fs::create_dir_all(root.path().join(".folderbase/local")).expect("local state");
2183 fs::write(
2184 root.path().join(".folderbase/local/head.json"),
2185 b"{\"format\":\"changed-and-invalid-local-head\"}\n",
2186 )
2187 .expect("changed Local Head");
2188 drop(engine);
2189 let engine = FolderbaseQueryEngine::open(root.path())
2190 .expect("query engine defers Local Head parsing until the request is known");
2191
2192 assert!(matches!(
2193 engine.run(&request),
2194 Err(QueryError::QuerySnapshotChanged)
2195 ));
2196 assert!(matches!(
2197 engine.explain(&request),
2198 Err(QueryError::QuerySnapshotChanged)
2199 ));
2200 }
2201
2202 #[test]
2203 fn cursor_validation_precedes_live_state_parsing_for_run_and_explain() {
2204 fn assert_invalid_cursor(engine: &FolderbaseQueryEngine, request: &QueryRequest) {
2205 assert!(matches!(
2206 engine.run(request),
2207 Err(QueryError::InvalidQueryCursor)
2208 ));
2209 assert!(matches!(
2210 engine.explain(request),
2211 Err(QueryError::InvalidQueryCursor)
2212 ));
2213 }
2214
2215 let owner = tempdir().expect("root owner");
2216 let first_root = owner.path().join("first");
2217 let second_root = owner.path().join("second");
2218 initialize_root(&first_root, "alpha.md");
2219 fs::write(first_root.join("beta.md"), b"beta\n").expect("second ordinary file");
2220 initialize_root(&second_root, "other.md");
2221
2222 let first_engine = FolderbaseQueryEngine::open(&first_root).expect("first query engine");
2223 let first_page = first_engine
2224 .run(&QueryRequest::live(1))
2225 .expect("first page");
2226 let valid_cursor = first_page
2227 .page()
2228 .next_cursor()
2229 .expect("first page cursor")
2230 .to_owned();
2231 drop(first_engine);
2232
2233 for root in [&first_root, &second_root] {
2234 fs::create_dir_all(root.join(".folderbase/local")).expect("local state");
2235 fs::write(
2236 root.join(".folderbase/local/head.json"),
2237 b"{\"format\":\"changed-and-invalid-local-head\"}\n",
2238 )
2239 .expect("changed Local Head");
2240 }
2241
2242 let first_engine = FolderbaseQueryEngine::open(&first_root)
2243 .expect("first query engine defers Local Head parsing");
2244 let second_engine = FolderbaseQueryEngine::open(&second_root)
2245 .expect("second query engine defers Local Head parsing");
2246
2247 let mut malformed = QueryRequest::live(1);
2248 malformed.page.cursor = Some("not-a-query-cursor".to_owned());
2249 assert_invalid_cursor(&first_engine, &malformed);
2250
2251 let mut cross_request = QueryRequest::live(2);
2252 cross_request.page.cursor = Some(valid_cursor.clone());
2253 assert_invalid_cursor(&first_engine, &cross_request);
2254
2255 let mut cross_root = QueryRequest::live(1);
2256 cross_root.page.cursor = Some(valid_cursor);
2257 assert_invalid_cursor(&second_engine, &cross_root);
2258 }
2259
2260 #[test]
2261 fn query_engine_retains_opening_root_and_state_capabilities() {
2262 let root = tempdir().expect("temporary Folderbase");
2263 fs::create_dir(root.path().join(".folderbase")).expect("state");
2264 fs::write(root.path().join(".folderbase/manifest.json"), MANIFEST).expect("manifest");
2265 let engine = FolderbaseQueryEngine::open(root.path()).expect("query engine");
2266
2267 engine
2268 .state
2269 .verify_root_identity(engine.store.root_physical_identity())
2270 .expect("retained capabilities name one opening root");
2271 }
2272
2273 #[test]
2274 fn ambient_root_aba_never_redirects_query_index_reads_or_writes() {
2275 let owner = tempdir().expect("root owner");
2276 let visible = owner.path().join("workspace");
2277 let replacement = owner.path().join("replacement");
2278 initialize_root(&visible, "opening.md");
2279 initialize_root(&replacement, "replacement.md");
2280 let engine = FolderbaseQueryEngine::open(&visible).expect("query engine");
2281 engine.rebuild_index().expect("opening-root index");
2282
2283 let result = engine
2284 .run_with_observation_hooks(
2285 &QueryRequest::live(10),
2286 || AmbientRootSwap::activate(&visible, &replacement),
2287 || (),
2288 )
2289 .expect("retained indexed query");
2290 assert_eq!(result.execution(), QueryExecution::PrivateIndex);
2291 assert_eq!(result.entries()[0].path(), "opening.md");
2292
2293 let explanation = engine
2294 .explain_with_after_live_observation(&QueryRequest::live(10), || {
2295 AmbientRootSwap::activate(&visible, &replacement)
2296 })
2297 .expect("retained indexed explanation");
2298 assert_eq!(explanation.index_strategy(), QueryExecution::PrivateIndex);
2299
2300 let status = engine
2301 .index_status_with_after_observation(|| {
2302 AmbientRootSwap::activate(&visible, &replacement)
2303 })
2304 .expect("retained indexed status");
2305 assert_eq!(status.state(), QueryIndexState::Fresh);
2306
2307 fs::remove_file(visible.join(INDEX_RECORD)).expect("remove opening-root index");
2308 engine
2309 .rebuild_index_with_hooks(
2310 || AmbientRootSwap::activate(&visible, &replacement),
2311 || Ok(()),
2312 )
2313 .expect("retained index rebuild");
2314 assert!(visible.join(INDEX_RECORD).is_file());
2315 assert!(!replacement.join(INDEX_RECORD).exists());
2316 }
2317
2318 #[test]
2319 fn ambient_root_aba_preserves_historical_missing_taxonomy() {
2320 let owner = tempdir().expect("root owner");
2321 let visible = owner.path().join("workspace");
2322 let replacement = owner.path().join("replacement");
2323 initialize_root(&visible, "opening.md");
2324 initialize_root(&replacement, "replacement.md");
2325 let replacement_version = replacement
2326 .join(".folderbase/versions/folderbase")
2327 .join(format!("{MISSING_VERSION_ID}.json"));
2328 fs::create_dir_all(replacement_version.parent().expect("version parent"))
2329 .expect("replacement version directory");
2330 fs::write(&replacement_version, b"invalid historical version\n")
2331 .expect("invalid replacement version");
2332 let engine = FolderbaseQueryEngine::open(&visible).expect("query engine");
2333 let request: QueryRequest = serde_json::from_value(serde_json::json!({
2334 "format": "folderbase-query-request-v1",
2335 "scope": {
2336 "kind": "historical",
2337 "folderbase_version_id": MISSING_VERSION_ID
2338 },
2339 "page": {"limit": 10}
2340 }))
2341 .expect("historical request");
2342
2343 let error = engine
2344 .run_with_observation_hooks(
2345 &request,
2346 || (),
2347 || AmbientRootSwap::activate(&visible, &replacement),
2348 )
2349 .expect_err("opening root has no historical version");
2350 assert!(matches!(
2351 error,
2352 QueryError::ScopeVersionMissing { version_id } if version_id == MISSING_VERSION_ID
2353 ));
2354 }
2355
2356 #[test]
2357 fn failure_before_index_publication_preserves_the_previous_generation() {
2358 let root = tempdir().expect("temporary Folderbase");
2359 fs::create_dir(root.path().join(".folderbase")).expect("state");
2360 fs::write(root.path().join(".folderbase/manifest.json"), MANIFEST).expect("manifest");
2361 fs::write(root.path().join("ordinary.md"), b"ordinary\n").expect("ordinary file");
2362 let engine = FolderbaseQueryEngine::open(root.path()).expect("query engine");
2363 engine.rebuild_index().expect("initial index");
2364 let before = fs::read(root.path().join(INDEX_RECORD)).expect("initial bytes");
2365
2366 let failure = engine
2367 .rebuild_index_with_before_publish(|| {
2368 Err(io::Error::other("injected pre-publication failure"))
2369 })
2370 .expect_err("injected rebuild failure");
2371 assert!(
2372 failure
2373 .to_string()
2374 .contains("injected pre-publication failure")
2375 );
2376 assert_eq!(fs::read(root.path().join(INDEX_RECORD)).unwrap(), before);
2377 assert_eq!(
2378 engine.index_status().unwrap().state(),
2379 QueryIndexState::Fresh
2380 );
2381 }
2382}