jj_lib/
op_store.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::collections::BTreeMap;
19use std::collections::HashMap;
20use std::collections::HashSet;
21use std::fmt::Debug;
22use std::iter;
23use std::time::SystemTime;
24
25use itertools::Itertools as _;
26use once_cell::sync::Lazy;
27use thiserror::Error;
28
29use crate::backend::CommitId;
30use crate::backend::MillisSinceEpoch;
31use crate::backend::Timestamp;
32use crate::content_hash::ContentHash;
33use crate::merge::Merge;
34use crate::object_id::id_type;
35use crate::object_id::HexPrefix;
36use crate::object_id::ObjectId as _;
37use crate::object_id::PrefixResolution;
38use crate::ref_name::GitRefNameBuf;
39use crate::ref_name::RefName;
40use crate::ref_name::RefNameBuf;
41use crate::ref_name::RemoteName;
42use crate::ref_name::RemoteNameBuf;
43use crate::ref_name::RemoteRefSymbol;
44use crate::ref_name::WorkspaceNameBuf;
45
46id_type!(pub ViewId { hex() });
47id_type!(pub OperationId { hex() });
48
49#[derive(ContentHash, PartialEq, Eq, Hash, Clone, Debug)]
50pub struct RefTarget {
51    merge: Merge<Option<CommitId>>,
52}
53
54impl Default for RefTarget {
55    fn default() -> Self {
56        Self::absent()
57    }
58}
59
60impl RefTarget {
61    /// Creates non-conflicting target pointing to no commit.
62    pub fn absent() -> Self {
63        Self::from_merge(Merge::absent())
64    }
65
66    /// Returns non-conflicting target pointing to no commit.
67    ///
68    /// This will typically be used in place of `None` returned by map lookup.
69    pub fn absent_ref() -> &'static Self {
70        static TARGET: Lazy<RefTarget> = Lazy::new(RefTarget::absent);
71        &TARGET
72    }
73
74    /// Creates non-conflicting target that optionally points to a commit.
75    pub fn resolved(maybe_id: Option<CommitId>) -> Self {
76        Self::from_merge(Merge::resolved(maybe_id))
77    }
78
79    /// Creates non-conflicting target pointing to a commit.
80    pub fn normal(id: CommitId) -> Self {
81        Self::from_merge(Merge::normal(id))
82    }
83
84    /// Creates target from removed/added ids.
85    pub fn from_legacy_form(
86        removed_ids: impl IntoIterator<Item = CommitId>,
87        added_ids: impl IntoIterator<Item = CommitId>,
88    ) -> Self {
89        Self::from_merge(Merge::from_legacy_form(removed_ids, added_ids))
90    }
91
92    pub fn from_merge(merge: Merge<Option<CommitId>>) -> Self {
93        RefTarget { merge }
94    }
95
96    /// Returns the underlying value if this target is non-conflicting.
97    pub fn as_resolved(&self) -> Option<&Option<CommitId>> {
98        self.merge.as_resolved()
99    }
100
101    /// Returns id if this target is non-conflicting and points to a commit.
102    pub fn as_normal(&self) -> Option<&CommitId> {
103        self.merge.as_normal()
104    }
105
106    /// Returns true if this target points to no commit.
107    pub fn is_absent(&self) -> bool {
108        self.merge.is_absent()
109    }
110
111    /// Returns true if this target points to any commit. Conflicting target is
112    /// always "present" as it should have at least one commit id.
113    pub fn is_present(&self) -> bool {
114        self.merge.is_present()
115    }
116
117    /// Whether this target has conflicts.
118    pub fn has_conflict(&self) -> bool {
119        !self.merge.is_resolved()
120    }
121
122    pub fn removed_ids(&self) -> impl Iterator<Item = &CommitId> {
123        self.merge.removes().flatten()
124    }
125
126    pub fn added_ids(&self) -> impl Iterator<Item = &CommitId> {
127        self.merge.adds().flatten()
128    }
129
130    pub fn as_merge(&self) -> &Merge<Option<CommitId>> {
131        &self.merge
132    }
133}
134
135/// Remote bookmark or tag.
136#[derive(ContentHash, Clone, Debug, Eq, Hash, PartialEq)]
137pub struct RemoteRef {
138    pub target: RefTarget,
139    pub state: RemoteRefState,
140}
141
142impl RemoteRef {
143    /// Creates remote ref pointing to no commit.
144    pub fn absent() -> Self {
145        RemoteRef {
146            target: RefTarget::absent(),
147            state: RemoteRefState::New,
148        }
149    }
150
151    /// Returns remote ref pointing to no commit.
152    ///
153    /// This will typically be used in place of `None` returned by map lookup.
154    pub fn absent_ref() -> &'static Self {
155        static TARGET: Lazy<RemoteRef> = Lazy::new(RemoteRef::absent);
156        &TARGET
157    }
158
159    /// Returns true if the target points to no commit.
160    pub fn is_absent(&self) -> bool {
161        self.target.is_absent()
162    }
163
164    /// Returns true if the target points to any commit.
165    pub fn is_present(&self) -> bool {
166        self.target.is_present()
167    }
168
169    /// Returns true if the ref is supposed to be merged in to the local ref.
170    pub fn is_tracked(&self) -> bool {
171        self.state == RemoteRefState::Tracked
172    }
173
174    /// Target that should have been merged in to the local ref.
175    ///
176    /// Use this as the base or known target when merging new remote ref in to
177    /// local or pushing local ref to remote.
178    pub fn tracked_target(&self) -> &RefTarget {
179        if self.is_tracked() {
180            &self.target
181        } else {
182            RefTarget::absent_ref()
183        }
184    }
185}
186
187/// Whether the ref is tracked or not.
188#[derive(ContentHash, Clone, Copy, Debug, Eq, Hash, PartialEq)]
189pub enum RemoteRefState {
190    /// Remote ref is not merged in to the local ref.
191    New,
192    /// Remote ref has been merged in to the local ref. Incoming ref will be
193    /// merged, too.
194    Tracked,
195}
196
197/// Helper to strip redundant `Option<T>` from `RefTarget` lookup result.
198pub trait RefTargetOptionExt {
199    type Value;
200
201    fn flatten(self) -> Self::Value;
202}
203
204impl RefTargetOptionExt for Option<RefTarget> {
205    type Value = RefTarget;
206
207    fn flatten(self) -> Self::Value {
208        self.unwrap_or_else(RefTarget::absent)
209    }
210}
211
212impl<'a> RefTargetOptionExt for Option<&'a RefTarget> {
213    type Value = &'a RefTarget;
214
215    fn flatten(self) -> Self::Value {
216        self.unwrap_or_else(|| RefTarget::absent_ref())
217    }
218}
219
220impl RefTargetOptionExt for Option<RemoteRef> {
221    type Value = RemoteRef;
222
223    fn flatten(self) -> Self::Value {
224        self.unwrap_or_else(RemoteRef::absent)
225    }
226}
227
228impl<'a> RefTargetOptionExt for Option<&'a RemoteRef> {
229    type Value = &'a RemoteRef;
230
231    fn flatten(self) -> Self::Value {
232        self.unwrap_or_else(|| RemoteRef::absent_ref())
233    }
234}
235
236/// Local and remote bookmarks of the same bookmark name.
237#[derive(PartialEq, Eq, Clone, Debug)]
238pub struct BookmarkTarget<'a> {
239    /// The commit the bookmark points to locally.
240    pub local_target: &'a RefTarget,
241    /// `(remote_name, remote_ref)` pairs in lexicographical order.
242    pub remote_refs: Vec<(&'a RemoteName, &'a RemoteRef)>,
243}
244
245/// Represents the way the repo looks at a given time, just like how a Tree
246/// object represents how the file system looks at a given time.
247#[derive(ContentHash, PartialEq, Eq, Clone, Debug)]
248pub struct View {
249    /// All head commits
250    pub head_ids: HashSet<CommitId>,
251    pub local_bookmarks: BTreeMap<RefNameBuf, RefTarget>,
252    pub tags: BTreeMap<RefNameBuf, RefTarget>,
253    pub remote_views: BTreeMap<RemoteNameBuf, RemoteView>,
254    pub git_refs: BTreeMap<GitRefNameBuf, RefTarget>,
255    /// The commit the Git HEAD points to.
256    // TODO: Support multiple Git worktrees?
257    // TODO: Do we want to store the current bookmark name too?
258    pub git_head: RefTarget,
259    // The commit that *should be* checked out in the workspace. Note that the working copy
260    // (.jj/working_copy/) has the source of truth about which commit *is* checked out (to be
261    // precise: the commit to which we most recently completed an update to).
262    pub wc_commit_ids: BTreeMap<WorkspaceNameBuf, CommitId>,
263}
264
265impl View {
266    /// Creates new truly empty view.
267    ///
268    /// The caller should add at least one commit ID to `head_ids`. The other
269    /// fields may be empty.
270    pub fn empty() -> Self {
271        View {
272            head_ids: HashSet::new(),
273            local_bookmarks: BTreeMap::new(),
274            tags: BTreeMap::new(),
275            remote_views: BTreeMap::new(),
276            git_refs: BTreeMap::new(),
277            git_head: RefTarget::absent(),
278            wc_commit_ids: BTreeMap::new(),
279        }
280    }
281
282    /// Creates new (mostly empty) view containing the given commit as the head.
283    pub fn make_root(root_commit_id: CommitId) -> Self {
284        View {
285            head_ids: HashSet::from([root_commit_id]),
286            local_bookmarks: BTreeMap::new(),
287            tags: BTreeMap::new(),
288            remote_views: BTreeMap::new(),
289            git_refs: BTreeMap::new(),
290            git_head: RefTarget::absent(),
291            wc_commit_ids: BTreeMap::new(),
292        }
293    }
294}
295
296/// Represents the state of the remote repo.
297#[derive(ContentHash, Clone, Debug, Default, Eq, PartialEq)]
298pub struct RemoteView {
299    // TODO: Do we need to support tombstones for remote bookmarks? For example, if the bookmark
300    // has been deleted locally and you pull from a remote, maybe it should make a difference
301    // whether the bookmark is known to have existed on the remote. We may not want to resurrect
302    // the bookmark if the bookmark's state on the remote was just not known.
303    pub bookmarks: BTreeMap<RefNameBuf, RemoteRef>,
304    // TODO: pub tags: BTreeMap<RefNameBuf, RemoteRef>,
305}
306
307/// Iterates pair of local and remote bookmarks by bookmark name.
308pub(crate) fn merge_join_bookmark_views<'a>(
309    local_bookmarks: &'a BTreeMap<RefNameBuf, RefTarget>,
310    remote_views: &'a BTreeMap<RemoteNameBuf, RemoteView>,
311) -> impl Iterator<Item = (&'a RefName, BookmarkTarget<'a>)> {
312    let mut local_bookmarks_iter = local_bookmarks
313        .iter()
314        .map(|(bookmark_name, target)| (&**bookmark_name, target))
315        .peekable();
316    let mut remote_bookmarks_iter = flatten_remote_bookmarks(remote_views).peekable();
317
318    iter::from_fn(move || {
319        // Pick earlier bookmark name
320        let (bookmark_name, local_target) = if let Some((symbol, _)) = remote_bookmarks_iter.peek()
321        {
322            local_bookmarks_iter
323                .next_if(|&(local_bookmark_name, _)| local_bookmark_name <= symbol.name)
324                .unwrap_or((symbol.name, RefTarget::absent_ref()))
325        } else {
326            local_bookmarks_iter.next()?
327        };
328        let remote_refs = remote_bookmarks_iter
329            .peeking_take_while(|(symbol, _)| symbol.name == bookmark_name)
330            .map(|(symbol, remote_ref)| (symbol.remote, remote_ref))
331            .collect();
332        let bookmark_target = BookmarkTarget {
333            local_target,
334            remote_refs,
335        };
336        Some((bookmark_name, bookmark_target))
337    })
338}
339
340/// Iterates bookmark `(symbol, remote_ref)`s in lexicographical order.
341pub(crate) fn flatten_remote_bookmarks(
342    remote_views: &BTreeMap<RemoteNameBuf, RemoteView>,
343) -> impl Iterator<Item = (RemoteRefSymbol<'_>, &RemoteRef)> {
344    remote_views
345        .iter()
346        .map(|(remote, remote_view)| {
347            remote_view
348                .bookmarks
349                .iter()
350                .map(move |(name, remote_ref)| (name.to_remote_symbol(remote), remote_ref))
351        })
352        .kmerge_by(|(symbol1, _), (symbol2, _)| symbol1 < symbol2)
353}
354
355/// Represents an operation (transaction) on the repo view, just like how a
356/// Commit object represents an operation on the tree.
357///
358/// Operations and views are not meant to be exchanged between repos or users;
359/// they represent local state and history.
360///
361/// The operation history will almost always be linear. It will only have
362/// forks when parallel operations occurred. The parent is determined when
363/// the transaction starts. When the transaction commits, a lock will be
364/// taken and it will be checked that the current head of the operation
365/// graph is unchanged. If the current head has changed, there has been
366/// concurrent operation.
367#[derive(ContentHash, PartialEq, Eq, Clone, Debug)]
368pub struct Operation {
369    pub view_id: ViewId,
370    pub parents: Vec<OperationId>,
371    pub metadata: OperationMetadata,
372}
373
374impl Operation {
375    pub fn make_root(root_view_id: ViewId) -> Operation {
376        let timestamp = Timestamp {
377            timestamp: MillisSinceEpoch(0),
378            tz_offset: 0,
379        };
380        let metadata = OperationMetadata {
381            start_time: timestamp,
382            end_time: timestamp,
383            description: "".to_string(),
384            hostname: "".to_string(),
385            username: "".to_string(),
386            is_snapshot: false,
387            tags: HashMap::new(),
388        };
389        Operation {
390            view_id: root_view_id,
391            parents: vec![],
392            metadata,
393        }
394    }
395}
396
397#[derive(ContentHash, PartialEq, Eq, Clone, Debug)]
398pub struct OperationMetadata {
399    pub start_time: Timestamp,
400    pub end_time: Timestamp,
401    // Whatever is useful to the user, such as exact command line call
402    pub description: String,
403    pub hostname: String,
404    pub username: String,
405    /// Whether this operation represents a pure snapshotting of the working
406    /// copy.
407    pub is_snapshot: bool,
408    pub tags: HashMap<String, String>,
409}
410
411/// Data to be loaded into the root operation/view.
412#[derive(Clone, Debug)]
413pub struct RootOperationData {
414    /// The root commit ID, which should exist in the root view.
415    pub root_commit_id: CommitId,
416}
417
418#[derive(Debug, Error)]
419pub enum OpStoreError {
420    #[error("Object {hash} of type {object_type} not found")]
421    ObjectNotFound {
422        object_type: String,
423        hash: String,
424        source: Box<dyn std::error::Error + Send + Sync>,
425    },
426    #[error("Error when reading object {hash} of type {object_type}")]
427    ReadObject {
428        object_type: String,
429        hash: String,
430        source: Box<dyn std::error::Error + Send + Sync>,
431    },
432    #[error("Could not write object of type {object_type}")]
433    WriteObject {
434        object_type: &'static str,
435        source: Box<dyn std::error::Error + Send + Sync>,
436    },
437    #[error(transparent)]
438    Other(Box<dyn std::error::Error + Send + Sync>),
439}
440
441pub type OpStoreResult<T> = Result<T, OpStoreError>;
442
443pub trait OpStore: Send + Sync + Debug {
444    fn as_any(&self) -> &dyn Any;
445
446    fn name(&self) -> &str;
447
448    fn root_operation_id(&self) -> &OperationId;
449
450    fn read_view(&self, id: &ViewId) -> OpStoreResult<View>;
451
452    fn write_view(&self, contents: &View) -> OpStoreResult<ViewId>;
453
454    fn read_operation(&self, id: &OperationId) -> OpStoreResult<Operation>;
455
456    fn write_operation(&self, contents: &Operation) -> OpStoreResult<OperationId>;
457
458    /// Resolves an unambiguous operation ID prefix.
459    fn resolve_operation_id_prefix(
460        &self,
461        prefix: &HexPrefix,
462    ) -> OpStoreResult<PrefixResolution<OperationId>>;
463
464    /// Prunes unreachable operations and views.
465    ///
466    /// All operations and views reachable from the `head_ids` won't be
467    /// removed. In addition to that, objects created after `keep_newer` will be
468    /// preserved. This mitigates a risk of deleting new heads created
469    /// concurrently by another process.
470    // TODO: return stats?
471    fn gc(&self, head_ids: &[OperationId], keep_newer: SystemTime) -> OpStoreResult<()>;
472}
473
474#[cfg(test)]
475mod tests {
476    use maplit::btreemap;
477
478    use super::*;
479
480    #[test]
481    fn test_merge_join_bookmark_views() {
482        let remote_ref = |target: &RefTarget| RemoteRef {
483            target: target.clone(),
484            state: RemoteRefState::Tracked, // doesn't matter
485        };
486        let local_bookmark1_target = RefTarget::normal(CommitId::from_hex("111111"));
487        let local_bookmark2_target = RefTarget::normal(CommitId::from_hex("222222"));
488        let git_bookmark1_remote_ref = remote_ref(&RefTarget::normal(CommitId::from_hex("333333")));
489        let git_bookmark2_remote_ref = remote_ref(&RefTarget::normal(CommitId::from_hex("444444")));
490        let remote1_bookmark1_remote_ref =
491            remote_ref(&RefTarget::normal(CommitId::from_hex("555555")));
492        let remote2_bookmark2_remote_ref =
493            remote_ref(&RefTarget::normal(CommitId::from_hex("666666")));
494
495        let local_bookmarks = btreemap! {
496            "bookmark1".into() => local_bookmark1_target.clone(),
497            "bookmark2".into() => local_bookmark2_target.clone(),
498        };
499        let remote_views = btreemap! {
500            "git".into() => RemoteView {
501                bookmarks: btreemap! {
502                    "bookmark1".into() => git_bookmark1_remote_ref.clone(),
503                    "bookmark2".into() => git_bookmark2_remote_ref.clone(),
504                },
505            },
506            "remote1".into() => RemoteView {
507                bookmarks: btreemap! {
508                    "bookmark1".into() => remote1_bookmark1_remote_ref.clone(),
509                },
510            },
511            "remote2".into() => RemoteView {
512                bookmarks: btreemap! {
513                    "bookmark2".into() => remote2_bookmark2_remote_ref.clone(),
514                },
515            },
516        };
517        assert_eq!(
518            merge_join_bookmark_views(&local_bookmarks, &remote_views).collect_vec(),
519            vec![
520                (
521                    "bookmark1".as_ref(),
522                    BookmarkTarget {
523                        local_target: &local_bookmark1_target,
524                        remote_refs: vec![
525                            ("git".as_ref(), &git_bookmark1_remote_ref),
526                            ("remote1".as_ref(), &remote1_bookmark1_remote_ref),
527                        ],
528                    },
529                ),
530                (
531                    "bookmark2".as_ref(),
532                    BookmarkTarget {
533                        local_target: &local_bookmark2_target.clone(),
534                        remote_refs: vec![
535                            ("git".as_ref(), &git_bookmark2_remote_ref),
536                            ("remote2".as_ref(), &remote2_bookmark2_remote_ref),
537                        ],
538                    },
539                ),
540            ],
541        );
542
543        // Local only
544        let local_bookmarks = btreemap! {
545            "bookmark1".into() => local_bookmark1_target.clone(),
546        };
547        let remote_views = btreemap! {};
548        assert_eq!(
549            merge_join_bookmark_views(&local_bookmarks, &remote_views).collect_vec(),
550            vec![(
551                "bookmark1".as_ref(),
552                BookmarkTarget {
553                    local_target: &local_bookmark1_target,
554                    remote_refs: vec![],
555                },
556            )],
557        );
558
559        // Remote only
560        let local_bookmarks = btreemap! {};
561        let remote_views = btreemap! {
562            "remote1".into() => RemoteView {
563                bookmarks: btreemap! {
564                    "bookmark1".into() => remote1_bookmark1_remote_ref.clone(),
565                },
566            },
567        };
568        assert_eq!(
569            merge_join_bookmark_views(&local_bookmarks, &remote_views).collect_vec(),
570            vec![(
571                "bookmark1".as_ref(),
572                BookmarkTarget {
573                    local_target: RefTarget::absent_ref(),
574                    remote_refs: vec![("remote1".as_ref(), &remote1_bookmark1_remote_ref)],
575                },
576            )],
577        );
578    }
579}
jj_lib/op_store.rs

jj_lib/
op_store.rs
