Skip to main content

drive/query/
document_history_drive_query.rs

1//! A page of a document's retained revisions with its lifecycle, read from
2//! the per-type composite-keyed history tree.
3
4use crate::drive::document::paths::{
5    contract_document_type_path_vec, DOCUMENT_HISTORY_TREE_KEY, DOCUMENT_LIFECYCLE_TREE_KEY,
6};
7use crate::drive::document::MAX_DOCUMENT_HISTORY_FETCH_LIMIT;
8use crate::drive::Drive;
9use crate::error::drive::DriveError;
10use crate::error::query::QuerySyntaxError;
11use crate::error::Error;
12use crate::verify::RootHash;
13use dpp::data_contract::document_type::{DocumentPropertyType, DocumentTypeRef};
14use dpp::document::lifecycle::DocumentLifecycleRecord;
15use dpp::document::serialization_traits::DocumentPlatformConversionMethodsV0;
16use dpp::document::{Document, DocumentV0Getters};
17use dpp::serialization::PlatformDeserializableUntrusted;
18use dpp::version::PlatformVersion;
19#[cfg(feature = "server")]
20use grovedb::TransactionArg;
21use grovedb::{Element, PathQuery, Query, SizedQuery};
22
23/// The highest revision a revision filter can address. Revision `n` is read at
24/// the zero-based offset `n - 1` of the document's history tree, and GroveDB
25/// offsets are `u16`.
26pub const MAX_DOCUMENT_HISTORY_REVISION_FILTER: u64 = u16::MAX as u64 + 1;
27
28/// Exactly one lower bound or revision position for a history page.
29#[derive(Debug, Clone, PartialEq, Eq)]
30#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
31pub enum DocumentHistoryFilter {
32    /// Inclusive time bound for the first page.
33    StartAtTime(u64),
34    /// Exclusive composite cursor for subsequent pages.
35    StartAfter {
36        /// Timestamp of the last entry received.
37        time_ms: u64,
38        /// History sequence of the last entry received.
39        revision: u64,
40    },
41    /// Inclusive retained revision position.
42    StartAtRevision(u64),
43    /// One retained revision position.
44    Revision(u64),
45}
46
47/// A page of one historical document's retained revisions.
48#[derive(Debug, Clone, PartialEq, Eq)]
49pub struct DocumentHistoryDriveQuery {
50    /// Contract identifier.
51    pub contract_id: [u8; 32],
52    /// Document type name.
53    pub document_type_name: String,
54    /// Document identifier.
55    pub document_id: [u8; 32],
56    /// Page filter.
57    pub filter: DocumentHistoryFilter,
58    /// Page length, at most ten.
59    pub limit: Option<u16>,
60}
61
62/// Lifecycle states supported by live-pointer storage.
63#[derive(Debug, Clone, Copy, PartialEq, Eq)]
64pub enum DocumentHistoryState {
65    /// A current document is present.
66    Active,
67    /// Neither a current document nor a retained history exists.
68    Absent,
69    /// The document has been deleted; its revisions are still retained.
70    Deleted,
71    /// An authorized erasure has started and has not finished.
72    Erasing,
73}
74
75/// Authenticated lifecycle timestamps independent of the requested page.
76#[derive(Debug, Clone, PartialEq, Eq, Default)]
77pub struct DocumentHistoryLifecycleTimes {
78    /// Block time the document was deleted at, zero while it is active.
79    pub deleted_at_ms: u64,
80    /// Block time an authorized erasure started at, zero while none has.
81    pub erasing_started_at_ms: u64,
82    /// Timestamp of the newest revision retained when the erasure started.
83    pub erasing_from_time_ms: u64,
84    /// History sequence of the newest revision retained when the erasure
85    /// started.
86    pub erasing_from_revision: u64,
87}
88
89/// Authenticated history metadata independent of the requested page.
90#[derive(Debug, Clone, PartialEq, Eq)]
91pub struct DocumentHistoryLifecycle {
92    /// Current lifecycle state.
93    pub state: DocumentHistoryState,
94    /// Count authenticated by the per-document count-tree element.
95    pub remaining_revisions: u64,
96    /// Times recorded by the lifecycle record, all zero unless one exists.
97    pub times: DocumentHistoryLifecycleTimes,
98}
99
100/// One retained edit, including its complete pagination cursor.
101#[derive(Debug, Clone, PartialEq)]
102pub struct DocumentHistoryEntry {
103    /// Block timestamp in milliseconds.
104    pub time_ms: u64,
105    /// History sequence, equal to the document revision when present.
106    pub revision: u64,
107    /// Document body at this revision.
108    pub document: Document,
109}
110
111/// The result of a history query: a page and the lifecycle of the whole
112/// history.
113#[derive(Debug, Clone, PartialEq)]
114pub struct DocumentHistoryDriveQueryExecutionResult {
115    /// Ordered retained revisions in this page.
116    pub entries: Vec<DocumentHistoryEntry>,
117    /// Metadata for the whole history. Drive always returns it, including empty pages.
118    pub lifecycle: Option<DocumentHistoryLifecycle>,
119}
120
121pub(crate) fn invalid(message: &str) -> Error {
122    Error::Query(QuerySyntaxError::Unsupported(message.to_owned()))
123}
124
125pub(crate) fn corrupt(message: &'static str) -> Error {
126    Error::Drive(DriveError::CorruptedDocumentPath(message))
127}
128
129impl DocumentHistoryDriveQuery {
130    /// Validates the filter without accessing state.
131    pub fn validate(&self) -> Result<(), Error> {
132        if !(1..=MAX_DOCUMENT_HISTORY_FETCH_LIMIT)
133            .contains(&self.limit.unwrap_or(MAX_DOCUMENT_HISTORY_FETCH_LIMIT))
134        {
135            return Err(invalid("history limit must be between one and ten"));
136        }
137        match self.filter {
138            DocumentHistoryFilter::StartAtTime(time)
139            | DocumentHistoryFilter::StartAfter { time_ms: time, .. }
140                if time >= (1u64 << 63) =>
141            {
142                Err(invalid("history time must be below 2^63"))
143            }
144            DocumentHistoryFilter::StartAfter { revision: 0, .. } => {
145                Err(invalid("history cursor revision must be positive"))
146            }
147            DocumentHistoryFilter::StartAtRevision(revision)
148            | DocumentHistoryFilter::Revision(revision)
149                if !(1..=MAX_DOCUMENT_HISTORY_REVISION_FILTER).contains(&revision) =>
150            {
151                Err(invalid("history revision must be between one and 65536"))
152            }
153            DocumentHistoryFilter::Revision(_) if self.limit.is_some_and(|limit| limit != 1) => {
154                Err(invalid("single revision queries require limit one"))
155            }
156            _ => Ok(()),
157        }
158    }
159
160    /// The page and its lifecycle in the per-type composite-keyed history tree.
161    pub fn construct_path_query(
162        &self,
163        platform_version: &PlatformVersion,
164    ) -> Result<PathQuery, Error> {
165        match platform_version
166            .drive
167            .methods
168            .document
169            .query
170            .fetch_document_history_query
171        {
172            1 => self.merged_path_query(platform_version),
173            version => Err(Error::Drive(DriveError::UnknownVersionMismatch {
174                method: "DocumentHistoryDriveQuery::construct_path_query".to_string(),
175                known_versions: vec![1],
176                received: version,
177            })),
178        }
179    }
180
181    fn merged_path_query(&self, version: &PlatformVersion) -> Result<PathQuery, Error> {
182        let page = Drive::fetch_document_history_drive_query_v1(self)?;
183        let mut leaf = page.query.query;
184        leaf.limit = page.query.limit;
185        leaf.offset = page.query.offset;
186        let mut queries = [0, 1]
187            .map(|branch| {
188                let mut path =
189                    contract_document_type_path_vec(&self.contract_id, &self.document_type_name);
190                path.push(vec![branch]);
191                let mut query = Query::new();
192                query.insert_key(self.document_id.to_vec());
193                PathQuery::new(path, SizedQuery::new(query, None, None))
194            })
195            .to_vec();
196        let mut path = contract_document_type_path_vec(&self.contract_id, &self.document_type_name);
197        path.push(vec![DOCUMENT_HISTORY_TREE_KEY]);
198        let mut history = Query::new_single_key(self.document_id.to_vec());
199        history.add_parent_tree_on_subquery = true;
200        history.set_subquery(leaf);
201        queries.push(PathQuery::new_unsized(path, history));
202        // Only the page leaf is limited. Exact siblings and their selecting
203        // ancestors must stay unlimited so omission authenticates absence.
204        Ok(PathQuery::merge(
205            queries.iter().collect(),
206            &version.drive.grove_version,
207        )?)
208    }
209
210    pub(crate) fn decode_result(
211        &self,
212        rows: Vec<grovedb::query_result_type::PathKeyOptionalElementTrio>,
213        document_type: DocumentTypeRef,
214        version: &PlatformVersion,
215    ) -> Result<DocumentHistoryDriveQueryExecutionResult, Error> {
216        let mut entry_path =
217            contract_document_type_path_vec(&self.contract_id, &self.document_type_name);
218        entry_path.push(vec![DOCUMENT_HISTORY_TREE_KEY]);
219        entry_path.push(self.document_id.to_vec());
220        let mut metadata = vec![];
221        let mut entries = vec![];
222        for (path, key, element) in rows {
223            if path == entry_path {
224                entries.push((
225                    key,
226                    element.ok_or_else(|| corrupt("history entry contains an absent element"))?,
227                ));
228            } else {
229                metadata.push((path, key, element));
230            }
231        }
232        let (lifecycle, record) = self.lifecycle(metadata, document_type, version)?;
233        let limit = if matches!(self.filter, DocumentHistoryFilter::Revision(_)) {
234            1
235        } else {
236            self.limit.unwrap_or(MAX_DOCUMENT_HISTORY_FETCH_LIMIT)
237        } as u64;
238        let maximum = lifecycle.remaining_revisions.min(limit);
239        if let DocumentHistoryFilter::Revision(revision)
240        | DocumentHistoryFilter::StartAtRevision(revision) = self.filter
241        {
242            if entries.len() as u64
243                != lifecycle
244                    .remaining_revisions
245                    .saturating_sub(revision - 1)
246                    .min(limit)
247            {
248                return Err(corrupt(
249                    "history page length disagrees with its revision count",
250                ));
251            }
252        } else if entries.len() as u64 > maximum {
253            return Err(corrupt("history page exceeds its limit or revision count"));
254        }
255        let entries = self.decode_entries(entries, document_type, version)?;
256        if let Some(record) = record {
257            if entries.iter().any(|entry| {
258                entry.time_ms > record.deleted_at_ms() || entry.revision > record.latest_revision()
259            }) {
260                return Err(corrupt(
261                    "retained revision is newer than its deletion record",
262                ));
263            }
264        }
265        Ok(DocumentHistoryDriveQueryExecutionResult {
266            entries,
267            lifecycle: Some(lifecycle),
268        })
269    }
270
271    pub(crate) fn lifecycle(
272        &self,
273        metadata: Vec<grovedb::query_result_type::PathKeyOptionalElementTrio>,
274        document_type: DocumentTypeRef,
275        version: &PlatformVersion,
276    ) -> Result<(DocumentHistoryLifecycle, Option<DocumentLifecycleRecord>), Error> {
277        let mut primary =
278            contract_document_type_path_vec(&self.contract_id, &self.document_type_name);
279        primary.push(vec![0]);
280        let mut history = primary.clone();
281        history[4] = vec![DOCUMENT_HISTORY_TREE_KEY];
282        let mut lifecycle = primary.clone();
283        lifecycle[4] = vec![DOCUMENT_LIFECYCLE_TREE_KEY];
284        let mut active = false;
285        let mut latest_revision = None;
286        let mut count = None;
287        let mut record = None;
288        for (path, key, element) in metadata {
289            let element =
290                element.ok_or_else(|| corrupt("history metadata contains an absent element"))?;
291            if key != self.document_id {
292                return Err(corrupt("history metadata key does not match the document"));
293            }
294            if path == lifecycle {
295                let Element::Item(bytes, _) = element else {
296                    return Err(corrupt("a lifecycle record is not an item"));
297                };
298                if record
299                    .replace(DocumentLifecycleRecord::deserialize_from_bytes_untrusted(
300                        &bytes,
301                    )?)
302                    .is_some()
303                {
304                    return Err(corrupt("duplicate lifecycle record"));
305                }
306            } else if path == primary {
307                let bytes = match element {
308                    Element::Item(bytes, _) | Element::ItemWithSumItem(bytes, _, _) => bytes,
309                    _ => {
310                        return Err(corrupt(
311                            "history current pointer did not resolve to a document",
312                        ))
313                    }
314                };
315                let document = Document::from_bytes(&bytes, document_type, version)?;
316                if document.id().as_slice() != self.document_id {
317                    return Err(corrupt(
318                        "history current document id does not match the query",
319                    ));
320                }
321                latest_revision = Some(document.revision().unwrap_or(1));
322                if active {
323                    return Err(corrupt("duplicate history current pointer"));
324                }
325                active = true;
326            } else if path == history {
327                let Element::ProvableCountTree(_, revisions, _) = element else {
328                    return Err(corrupt("history metadata is not a provable count tree"));
329                };
330                if count.replace(revisions).is_some() {
331                    return Err(corrupt("duplicate history metadata"));
332                }
333            } else {
334                return Err(corrupt(
335                    "unexpected lifecycle record or history metadata path",
336                ));
337            }
338        }
339        if active && record.is_some() {
340            return Err(corrupt(
341                "a current document cannot also carry a lifecycle record",
342            ));
343        }
344        if active && count.unwrap_or_default() == 0
345            || !active && record.is_none() && count.unwrap_or_default() > 0
346        {
347            return Err(corrupt("current document and retained history disagree"));
348        }
349        if record.is_some() && count == Some(0) {
350            return Err(corrupt("an empty history tree must not remain in storage"));
351        }
352        if record.is_some() && count.unwrap_or_default() == 0 {
353            return Err(corrupt("a lifecycle record survives its retained history"));
354        }
355        if let Some(record) = record {
356            let remaining = count.unwrap_or_default();
357            if !record.is_coherent()
358                || if record.is_erasing() {
359                    remaining >= record.revision_count()
360                } else {
361                    remaining != record.revision_count()
362                }
363            {
364                return Err(corrupt(
365                    "lifecycle record disagrees with its retained history",
366                ));
367            }
368        }
369        // A by-revision read maps the revision onto a position, which only
370        // holds while the retained revisions number one through the latest
371        // without a gap. A current document says so through its revision; a
372        // deleted one through what its record kept from the moment of
373        // deletion, since an erase only ever removes the newest revisions and
374        // so cannot open a gap afterwards.
375        if matches!(
376            self.filter,
377            DocumentHistoryFilter::Revision(_) | DocumentHistoryFilter::StartAtRevision(_)
378        ) {
379            let gapped = match (active, &record) {
380                (true, _) => latest_revision != count,
381                (false, Some(record)) => !record.revisions_are_contiguous(),
382                (false, None) => false,
383            };
384            if gapped {
385                return Err(invalid(
386                    "retained history contains a revision gap; use time pagination",
387                ));
388            }
389        }
390        let state = match (active, &record) {
391            (true, _) => DocumentHistoryState::Active,
392            (false, Some(record)) if record.is_erasing() => DocumentHistoryState::Erasing,
393            (false, Some(_)) => DocumentHistoryState::Deleted,
394            // Retained history with no record and no pointer was rejected as
395            // inconsistent above, so nothing is left here but an unused id.
396            (false, None) => DocumentHistoryState::Absent,
397        };
398        let times = record
399            .map(|record| DocumentHistoryLifecycleTimes {
400                deleted_at_ms: record.deleted_at_ms(),
401                erasing_started_at_ms: record.erasing_started_at_ms(),
402                erasing_from_time_ms: record.erasing_from_time_ms(),
403                erasing_from_revision: record.erasing_from_revision(),
404            })
405            .unwrap_or_default();
406        Ok((
407            DocumentHistoryLifecycle {
408                state,
409                remaining_revisions: count.unwrap_or_default(),
410                times,
411            },
412            record,
413        ))
414    }
415
416    pub(crate) fn decode_entries(
417        &self,
418        entries: Vec<(Vec<u8>, Element)>,
419        document_type: DocumentTypeRef,
420        version: &PlatformVersion,
421    ) -> Result<Vec<DocumentHistoryEntry>, Error> {
422        entries
423            .into_iter()
424            .enumerate()
425            .map(|(position, (key, element))| {
426                if key.len() != 16 {
427                    return Err(corrupt(
428                        "history revision keys must contain exactly sixteen bytes",
429                    ));
430                }
431                let time_ms = DocumentPropertyType::decode_date_timestamp(&key[..8])
432                    .ok_or_else(|| corrupt("invalid history timestamp"))?;
433                let revision = DocumentPropertyType::decode_date_timestamp(&key[8..])
434                    .ok_or_else(|| corrupt("invalid history revision"))?;
435                if time_ms >= (1u64 << 63) || revision == 0 {
436                    return Err(corrupt(
437                        "history key contains an invalid timestamp or revision",
438                    ));
439                }
440                let Element::Item(bytes, _) = element else {
441                    return Err(corrupt("history revision is not a plain item"));
442                };
443                let document = Document::from_bytes(&bytes, document_type, version)?;
444                if document.id().as_slice() != self.document_id
445                    || document.revision().unwrap_or(1) != revision
446                {
447                    return Err(corrupt("history revision does not match its key"));
448                }
449                if let DocumentHistoryFilter::StartAtRevision(requested)
450                | DocumentHistoryFilter::Revision(requested) = self.filter
451                {
452                    if revision != requested + position as u64 {
453                        return Err(invalid(
454                            "retained history contains a revision gap; use time pagination",
455                        ));
456                    }
457                }
458                Ok(DocumentHistoryEntry {
459                    time_ms,
460                    revision,
461                    document,
462                })
463            })
464            .collect()
465    }
466
467    /// Fetches the page from the per-type composite-keyed history tree.
468    #[cfg(feature = "server")]
469    pub fn execute_no_proof(
470        &self,
471        drive: &Drive,
472        document_type: DocumentTypeRef,
473        transaction: TransactionArg,
474        platform_version: &PlatformVersion,
475    ) -> Result<DocumentHistoryDriveQueryExecutionResult, Error> {
476        drive.fetch_document_history(self, document_type, transaction, platform_version)
477    }
478
479    /// Proves the page from the per-type composite-keyed history tree.
480    #[cfg(feature = "server")]
481    pub fn execute_with_proof(
482        &self,
483        drive: &Drive,
484        document_type: DocumentTypeRef,
485        transaction: TransactionArg,
486        platform_version: &PlatformVersion,
487    ) -> Result<Vec<u8>, Error> {
488        drive.prove_document_history(self, document_type, transaction, platform_version)
489    }
490
491    /// Verifies a proof produced by [`Self::execute_with_proof`].
492    pub fn verify_document_history_proof(
493        &self,
494        proof: &[u8],
495        document_type: DocumentTypeRef,
496        platform_version: &PlatformVersion,
497    ) -> Result<(RootHash, DocumentHistoryDriveQueryExecutionResult), Error> {
498        Drive::verify_document_history(self, proof, document_type, platform_version)
499    }
500}
501
502#[cfg(test)]
503#[path = "document_history_drive_query_tests.rs"]
504mod decode_tests;