Skip to main content

folderbase_core/
query.rs

1//! Bounded, metadata-only query projection for one Folderbase Root.
2//!
3//! Live query never owns filesystem traversal. It projects the exact
4//! [`crate::CapturePlan`] produced by [`crate::FolderbaseVersionStore`].
5
6use 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
43/// A root-bound handle for read-only query and explicit disposable-index work.
44pub 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/// One bounded query request.
65#[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    /// Construct one live query with a page limit from 1 through 1000.
111    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/// Source observation from which a query row was projected.
125#[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/// Filesystem kind exposed by query 0.1.
133#[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/// Lifecycle exposed by query 0.1.
143#[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/// How the selected observation was evaluated.
151#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
152#[serde(rename_all = "snake_case")]
153pub enum QueryExecution {
154    BoundedScan,
155    PrivateIndex,
156}
157
158/// One query row.
159#[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/// Optional type attached to an explainable exclusion.
291#[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/// One path omitted from ordinary query rows.
304#[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/// Page metadata for a query result.
325#[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/// One successful query page.
349#[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/// Read-only state of the disposable private query index.
363#[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/// Result of inspecting the private index without changing it.
372#[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/// Result of explicitly replacing the disposable private index.
410#[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/// Read-only explanation of one normalized query plan.
447#[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/// Typed failures from query/index Core operations.
534#[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    /// Open one exact Folderbase Root without writing state.
557    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    /// Run one bounded query against a newly observed scope.
664    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    /// Explain one query using the same normalized request and observation.
743    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    /// Inspect disposable-index freshness without writing state.
801    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    /// Explicitly replace the exact disposable query-index namespace.
830    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}