jj_lib/
backend.rs

1// Copyright 2020 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![allow(missing_docs)]
16
17use std::any::Any;
18use std::fmt::Debug;
19use std::pin::Pin;
20use std::slice;
21use std::time::SystemTime;
22
23use async_trait::async_trait;
24use chrono::TimeZone as _;
25use futures::stream::BoxStream;
26use thiserror::Error;
27use tokio::io::AsyncRead;
28
29use crate::content_hash::ContentHash;
30use crate::hex_util;
31use crate::index::Index;
32use crate::merge::Merge;
33use crate::object_id::ObjectId as _;
34use crate::object_id::id_type;
35use crate::repo_path::RepoPath;
36use crate::repo_path::RepoPathBuf;
37use crate::repo_path::RepoPathComponent;
38use crate::repo_path::RepoPathComponentBuf;
39use crate::signing::SignResult;
40
41id_type!(
42    /// Identifier for a [`Commit`] based on its content. When a commit is
43    /// rewritten, its `CommitId` changes.
44    pub CommitId { hex() }
45);
46id_type!(
47    /// Stable identifier for a [`Commit`]. Unlike the `CommitId`, the `ChangeId`
48    /// follows the commit and is not updated when the commit is rewritten.
49    pub ChangeId { reverse_hex() }
50);
51id_type!(pub TreeId { hex() });
52id_type!(pub FileId { hex() });
53id_type!(pub SymlinkId { hex() });
54id_type!(pub ConflictId { hex() });
55id_type!(pub CopyId { hex() });
56
57impl ChangeId {
58    /// Parses the given "reverse" hex string into a `ChangeId`.
59    pub fn try_from_reverse_hex(hex: impl AsRef<[u8]>) -> Option<Self> {
60        hex_util::decode_reverse_hex(hex).map(Self)
61    }
62
63    /// Returns the hex string representation of this ID, which uses `z-k`
64    /// "digits" instead of `0-9a-f`.
65    pub fn reverse_hex(&self) -> String {
66        hex_util::encode_reverse_hex(&self.0)
67    }
68}
69
70impl CopyId {
71    /// Returns a placeholder copy id to be used when we don't have a real copy
72    /// id yet.
73    // TODO: Delete this
74    pub fn placeholder() -> Self {
75        Self::new(vec![])
76    }
77}
78
79#[derive(Debug, Error)]
80#[error("Out-of-range date")]
81pub struct TimestampOutOfRange;
82
83#[derive(ContentHash, Debug, PartialEq, Eq, Clone, Copy, PartialOrd, Ord)]
84pub struct MillisSinceEpoch(pub i64);
85
86#[derive(ContentHash, Debug, PartialEq, Eq, Clone, Copy, PartialOrd, Ord)]
87pub struct Timestamp {
88    pub timestamp: MillisSinceEpoch,
89    // time zone offset in minutes
90    pub tz_offset: i32,
91}
92
93impl Timestamp {
94    pub fn now() -> Self {
95        Self::from_datetime(chrono::offset::Local::now())
96    }
97
98    pub fn from_datetime<Tz: chrono::TimeZone<Offset = chrono::offset::FixedOffset>>(
99        datetime: chrono::DateTime<Tz>,
100    ) -> Self {
101        Self {
102            timestamp: MillisSinceEpoch(datetime.timestamp_millis()),
103            tz_offset: datetime.offset().local_minus_utc() / 60,
104        }
105    }
106
107    pub fn to_datetime(
108        &self,
109    ) -> Result<chrono::DateTime<chrono::FixedOffset>, TimestampOutOfRange> {
110        let utc = match chrono::Utc.timestamp_opt(
111            self.timestamp.0.div_euclid(1000),
112            (self.timestamp.0.rem_euclid(1000)) as u32 * 1000000,
113        ) {
114            chrono::LocalResult::None => {
115                return Err(TimestampOutOfRange);
116            }
117            chrono::LocalResult::Single(x) => x,
118            chrono::LocalResult::Ambiguous(y, _z) => y,
119        };
120
121        Ok(utc.with_timezone(
122            &chrono::FixedOffset::east_opt(self.tz_offset * 60)
123                .unwrap_or_else(|| chrono::FixedOffset::east_opt(0).unwrap()),
124        ))
125    }
126}
127
128impl serde::Serialize for Timestamp {
129    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
130    where
131        S: serde::Serializer,
132    {
133        // TODO: test is_human_readable() to use raw format?
134        let t = self.to_datetime().map_err(serde::ser::Error::custom)?;
135        t.serialize(serializer)
136    }
137}
138
139/// Represents a [`Commit`] signature.
140#[derive(ContentHash, Debug, PartialEq, Eq, Clone, serde::Serialize)]
141pub struct Signature {
142    pub name: String,
143    pub email: String,
144    pub timestamp: Timestamp,
145}
146
147/// Represents a cryptographically signed [`Commit`] signature.
148#[derive(ContentHash, Debug, PartialEq, Eq, Clone)]
149pub struct SecureSig {
150    pub data: Vec<u8>,
151    pub sig: Vec<u8>,
152}
153
154pub type SigningFn<'a> = dyn FnMut(&[u8]) -> SignResult<Vec<u8>> + Send + 'a;
155
156/// Identifies a single legacy tree, which may have path-level conflicts, or a
157/// merge of multiple trees, where the individual trees do not have conflicts.
158// TODO(#1624): Delete this type at some point in the future, when we decide to drop
159// support for conflicts in older repos, or maybe after we have provided an upgrade
160// mechanism.
161#[derive(ContentHash, Debug, Clone)]
162pub enum MergedTreeId {
163    /// The tree id of a legacy tree
164    Legacy(TreeId),
165    /// The tree id(s) of a merge tree
166    Merge(Merge<TreeId>),
167}
168
169impl PartialEq for MergedTreeId {
170    /// Overridden to make conflict-free trees be considered equal even if their
171    /// `MergedTreeId` variant is different.
172    fn eq(&self, other: &Self) -> bool {
173        self.to_merge() == other.to_merge()
174    }
175}
176
177impl Eq for MergedTreeId {}
178
179impl MergedTreeId {
180    /// Create a resolved `MergedTreeId` from a single regular tree.
181    pub fn resolved(tree_id: TreeId) -> Self {
182        Self::Merge(Merge::resolved(tree_id))
183    }
184
185    /// Return this id as `Merge<TreeId>`
186    pub fn to_merge(&self) -> Merge<TreeId> {
187        match self {
188            Self::Legacy(tree_id) => Merge::resolved(tree_id.clone()),
189            Self::Merge(tree_ids) => tree_ids.clone(),
190        }
191    }
192}
193
194#[derive(ContentHash, Debug, PartialEq, Eq, Clone, serde::Serialize)]
195pub struct Commit {
196    pub parents: Vec<CommitId>,
197    // TODO: delete commit.predecessors when we can assume that most commits are
198    // tracked by op.commit_predecessors. (in jj 0.42 or so?)
199    #[serde(skip)] // deprecated
200    pub predecessors: Vec<CommitId>,
201    #[serde(skip)] // TODO: should be exposed?
202    pub root_tree: MergedTreeId,
203    pub change_id: ChangeId,
204    pub description: String,
205    pub author: Signature,
206    pub committer: Signature,
207    #[serde(skip)] // raw data wouldn't be useful
208    pub secure_sig: Option<SecureSig>,
209}
210
211#[derive(ContentHash, Debug, PartialEq, Eq, Clone)]
212pub struct ConflictTerm {
213    pub value: TreeValue,
214}
215
216#[derive(ContentHash, Debug, PartialEq, Eq, Clone)]
217pub struct Conflict {
218    // A conflict is represented by a list of positive and negative states that need to be applied.
219    // In a simple 3-way merge of B and C with merge base A, the conflict will be { add: [B, C],
220    // remove: [A] }. Also note that a conflict of the form { add: [A], remove: [] } is the
221    // same as non-conflict A.
222    pub removes: Vec<ConflictTerm>,
223    pub adds: Vec<ConflictTerm>,
224}
225
226/// An individual copy event, from file A -> B.
227#[derive(Debug, PartialEq, Eq, Clone)]
228pub struct CopyRecord {
229    /// The destination of the copy, B.
230    pub target: RepoPathBuf,
231    /// The CommitId where the copy took place.
232    pub target_commit: CommitId,
233    /// The source path a target was copied from.
234    ///
235    /// It is not required that the source path is different than the target
236    /// path. A custom backend may choose to represent 'rollbacks' as copies
237    /// from a file unto itself, from a specific prior commit.
238    pub source: RepoPathBuf,
239    pub source_file: FileId,
240    /// The source commit the target was copied from. Backends may use this
241    /// field to implement 'integration' logic, where a source may be
242    /// periodically merged into a target, similar to a branch, but the
243    /// branching occurs at the file level rather than the repository level. It
244    /// also follows naturally that any copy source targeted to a specific
245    /// commit should avoid copy propagation on rebasing, which is desirable
246    /// for 'fork' style copies.
247    ///
248    /// It is required that the commit id is an ancestor of the commit with
249    /// which this copy source is associated.
250    pub source_commit: CommitId,
251}
252
253/// Describes the copy history of a file. The copy object is unchanged when a
254/// file is modified.
255#[derive(ContentHash, Debug, PartialEq, Eq, Clone, PartialOrd, Ord)]
256pub struct CopyHistory {
257    /// The file's current path.
258    pub current_path: RepoPathBuf,
259    /// IDs of the files that became the current incarnation of this file.
260    ///
261    /// A newly created file has no parents. A regular copy or rename has one
262    /// parent. A merge of multiple files has multiple parents.
263    pub parents: Vec<CopyId>,
264    /// An optional piece of data to give the Copy object a different ID. May be
265    /// randomly generated. This allows a commit to say that a file was replaced
266    /// by a new incarnation of it, indicating a logically distinct file
267    /// taking the place of the previous file at the path.
268    pub salt: Vec<u8>,
269}
270
271/// Error that may occur during backend initialization.
272#[derive(Debug, Error)]
273#[error(transparent)]
274pub struct BackendInitError(pub Box<dyn std::error::Error + Send + Sync>);
275
276/// Error that may occur during backend loading.
277#[derive(Debug, Error)]
278#[error(transparent)]
279pub struct BackendLoadError(pub Box<dyn std::error::Error + Send + Sync>);
280
281/// Commit-backend error that may occur after the backend is loaded.
282#[derive(Debug, Error)]
283pub enum BackendError {
284    #[error(
285        "Invalid hash length for object of type {object_type} (expected {expected} bytes, got \
286         {actual} bytes): {hash}"
287    )]
288    InvalidHashLength {
289        expected: usize,
290        actual: usize,
291        object_type: String,
292        hash: String,
293    },
294    #[error("Invalid UTF-8 for object {hash} of type {object_type}")]
295    InvalidUtf8 {
296        object_type: String,
297        hash: String,
298        source: std::str::Utf8Error,
299    },
300    #[error("Object {hash} of type {object_type} not found")]
301    ObjectNotFound {
302        object_type: String,
303        hash: String,
304        source: Box<dyn std::error::Error + Send + Sync>,
305    },
306    #[error("Error when reading object {hash} of type {object_type}")]
307    ReadObject {
308        object_type: String,
309        hash: String,
310        source: Box<dyn std::error::Error + Send + Sync>,
311    },
312    #[error("Access denied to read object {hash} of type {object_type}")]
313    ReadAccessDenied {
314        object_type: String,
315        hash: String,
316        source: Box<dyn std::error::Error + Send + Sync>,
317    },
318    #[error(
319        "Error when reading file content for file {path} with id {id}",
320        path = path.as_internal_file_string()
321    )]
322    ReadFile {
323        path: RepoPathBuf,
324        id: FileId,
325        source: Box<dyn std::error::Error + Send + Sync>,
326    },
327    #[error("Could not write object of type {object_type}")]
328    WriteObject {
329        object_type: &'static str,
330        source: Box<dyn std::error::Error + Send + Sync>,
331    },
332    #[error(transparent)]
333    Other(Box<dyn std::error::Error + Send + Sync>),
334    /// A valid operation attempted, but failed because it isn't supported by
335    /// the particular backend.
336    #[error("{0}")]
337    Unsupported(String),
338}
339
340pub type BackendResult<T> = Result<T, BackendError>;
341
342#[derive(ContentHash, Debug, PartialEq, Eq, Clone, Hash)]
343pub enum TreeValue {
344    // TODO: When there's a CopyId here, the copy object's path must match
345    // the path identified by the tree.
346    File {
347        id: FileId,
348        executable: bool,
349        copy_id: CopyId,
350    },
351    Symlink(SymlinkId),
352    Tree(TreeId),
353    GitSubmodule(CommitId),
354    Conflict(ConflictId),
355}
356
357impl TreeValue {
358    pub fn hex(&self) -> String {
359        match self {
360            Self::File { id, .. } => id.hex(),
361            Self::Symlink(id) => id.hex(),
362            Self::Tree(id) => id.hex(),
363            Self::GitSubmodule(id) => id.hex(),
364            Self::Conflict(id) => id.hex(),
365        }
366    }
367}
368
369#[derive(Debug, PartialEq, Eq, Clone)]
370pub struct TreeEntry<'a> {
371    name: &'a RepoPathComponent,
372    value: &'a TreeValue,
373}
374
375impl<'a> TreeEntry<'a> {
376    pub fn new(name: &'a RepoPathComponent, value: &'a TreeValue) -> Self {
377        Self { name, value }
378    }
379
380    pub fn name(&self) -> &'a RepoPathComponent {
381        self.name
382    }
383
384    pub fn value(&self) -> &'a TreeValue {
385        self.value
386    }
387}
388
389pub struct TreeEntriesNonRecursiveIterator<'a> {
390    iter: slice::Iter<'a, (RepoPathComponentBuf, TreeValue)>,
391}
392
393impl<'a> Iterator for TreeEntriesNonRecursiveIterator<'a> {
394    type Item = TreeEntry<'a>;
395
396    fn next(&mut self) -> Option<Self::Item> {
397        self.iter
398            .next()
399            .map(|(name, value)| TreeEntry { name, value })
400    }
401}
402
403#[derive(ContentHash, Default, PartialEq, Eq, Debug, Clone)]
404pub struct Tree {
405    entries: Vec<(RepoPathComponentBuf, TreeValue)>,
406}
407
408impl Tree {
409    pub fn from_sorted_entries(entries: Vec<(RepoPathComponentBuf, TreeValue)>) -> Self {
410        debug_assert!(entries.is_sorted_by(|(a, _), (b, _)| a < b));
411        Self { entries }
412    }
413
414    pub fn is_empty(&self) -> bool {
415        self.entries.is_empty()
416    }
417
418    pub fn names(&self) -> impl Iterator<Item = &RepoPathComponent> {
419        self.entries.iter().map(|(name, _)| name.as_ref())
420    }
421
422    pub fn entries(&self) -> TreeEntriesNonRecursiveIterator<'_> {
423        TreeEntriesNonRecursiveIterator {
424            iter: self.entries.iter(),
425        }
426    }
427
428    pub fn entry(&self, name: &RepoPathComponent) -> Option<TreeEntry<'_>> {
429        let index = self
430            .entries
431            .binary_search_by_key(&name, |(name, _)| name)
432            .ok()?;
433        let (name, value) = &self.entries[index];
434        Some(TreeEntry { name, value })
435    }
436
437    pub fn value(&self, name: &RepoPathComponent) -> Option<&TreeValue> {
438        self.entry(name).map(|entry| entry.value)
439    }
440}
441
442pub fn make_root_commit(root_change_id: ChangeId, empty_tree_id: TreeId) -> Commit {
443    let timestamp = Timestamp {
444        timestamp: MillisSinceEpoch(0),
445        tz_offset: 0,
446    };
447    let signature = Signature {
448        name: String::new(),
449        email: String::new(),
450        timestamp,
451    };
452    Commit {
453        parents: vec![],
454        predecessors: vec![],
455        root_tree: MergedTreeId::resolved(empty_tree_id),
456        change_id: root_change_id,
457        description: String::new(),
458        author: signature.clone(),
459        committer: signature,
460        secure_sig: None,
461    }
462}
463
464/// Defines the interface for commit backends.
465#[async_trait]
466pub trait Backend: Send + Sync + Debug {
467    fn as_any(&self) -> &dyn Any;
468
469    /// A unique name that identifies this backend. Written to
470    /// `.jj/repo/store/type` when the repo is created.
471    fn name(&self) -> &str;
472
473    /// The length of commit IDs in bytes.
474    fn commit_id_length(&self) -> usize;
475
476    /// The length of change IDs in bytes.
477    fn change_id_length(&self) -> usize;
478
479    fn root_commit_id(&self) -> &CommitId;
480
481    fn root_change_id(&self) -> &ChangeId;
482
483    fn empty_tree_id(&self) -> &TreeId;
484
485    /// An estimate of how many concurrent requests this backend handles well. A
486    /// local backend like the Git backend (at until it supports partial clones)
487    /// may want to set this to 1. A cloud-backed backend may want to set it to
488    /// 100 or so.
489    ///
490    /// It is not guaranteed that at most this number of concurrent requests are
491    /// sent.
492    fn concurrency(&self) -> usize;
493
494    async fn read_file(
495        &self,
496        path: &RepoPath,
497        id: &FileId,
498    ) -> BackendResult<Pin<Box<dyn AsyncRead + Send>>>;
499
500    async fn write_file(
501        &self,
502        path: &RepoPath,
503        contents: &mut (dyn AsyncRead + Send + Unpin),
504    ) -> BackendResult<FileId>;
505
506    async fn read_symlink(&self, path: &RepoPath, id: &SymlinkId) -> BackendResult<String>;
507
508    async fn write_symlink(&self, path: &RepoPath, target: &str) -> BackendResult<SymlinkId>;
509
510    /// Read the specified `CopyHistory` object.
511    ///
512    /// Backends that don't support copy tracking may return
513    /// `BackendError::Unsupported`.
514    async fn read_copy(&self, id: &CopyId) -> BackendResult<CopyHistory>;
515
516    /// Write the `CopyHistory` object and return its ID.
517    ///
518    /// Backends that don't support copy tracking may return
519    /// `BackendError::Unsupported`.
520    async fn write_copy(&self, copy: &CopyHistory) -> BackendResult<CopyId>;
521
522    /// Find all copy histories that are related to the specified one. This is
523    /// defined as those that are ancestors of the given specified one, plus
524    /// their descendants. Children must be returned before parents.
525    ///
526    /// It is valid (but wasteful) to include other copy histories, such as
527    /// siblings, or even completely unrelated copy histories.
528    ///
529    /// Backends that don't support copy tracking may return
530    /// `BackendError::Unsupported`.
531    async fn get_related_copies(&self, copy_id: &CopyId) -> BackendResult<Vec<CopyHistory>>;
532
533    async fn read_tree(&self, path: &RepoPath, id: &TreeId) -> BackendResult<Tree>;
534
535    async fn write_tree(&self, path: &RepoPath, contents: &Tree) -> BackendResult<TreeId>;
536
537    // Not async because it would force `MergedTree::value()` to be async. We don't
538    // need this to be async anyway because it's only used by legacy repos.
539    fn read_conflict(&self, path: &RepoPath, id: &ConflictId) -> BackendResult<Conflict>;
540
541    fn write_conflict(&self, path: &RepoPath, contents: &Conflict) -> BackendResult<ConflictId>;
542
543    async fn read_commit(&self, id: &CommitId) -> BackendResult<Commit>;
544
545    /// Writes a commit and returns its ID and the commit itself. The commit
546    /// should contain the data that was actually written, which may differ
547    /// from the data passed in. For example, the backend may change the
548    /// committer name to an authenticated user's name, or the backend's
549    /// timestamps may have less precision than the millisecond precision in
550    /// `Commit`.
551    ///
552    /// The `sign_with` parameter could contain a function to cryptographically
553    /// sign some binary representation of the commit.
554    /// If the backend supports it, it could call it and store the result in
555    /// an implementation specific fashion, and both `read_commit` and the
556    /// return of `write_commit` should read it back as the `secure_sig`
557    /// field.
558    async fn write_commit(
559        &self,
560        contents: Commit,
561        sign_with: Option<&mut SigningFn>,
562    ) -> BackendResult<(CommitId, Commit)>;
563
564    /// Get copy records for the dag range `root..head`.  If `paths` is None
565    /// include all paths, otherwise restrict to only `paths`.
566    ///
567    /// The exact order these are returned is unspecified, but it is guaranteed
568    /// to be reverse-topological. That is, for any two copy records with
569    /// different commit ids A and B, if A is an ancestor of B, A is streamed
570    /// after B.
571    ///
572    /// Streaming by design to better support large backends which may have very
573    /// large single-file histories. This also allows more iterative algorithms
574    /// like blame/annotate to short-circuit after a point without wasting
575    /// unnecessary resources.
576    fn get_copy_records(
577        &self,
578        paths: Option<&[RepoPathBuf]>,
579        root: &CommitId,
580        head: &CommitId,
581    ) -> BackendResult<BoxStream<'_, BackendResult<CopyRecord>>>;
582
583    /// Perform garbage collection.
584    ///
585    /// All commits found in the `index` won't be removed. In addition to that,
586    /// objects created after `keep_newer` will be preserved. This mitigates a
587    /// risk of deleting new commits created concurrently by another process.
588    fn gc(&self, index: &dyn Index, keep_newer: SystemTime) -> BackendResult<()>;
589}
jj_lib/backend.rs

jj_lib/
backend.rs
