jj_lib/
tree.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::fmt::Debug;
18use std::fmt::Error;
19use std::fmt::Formatter;
20use std::hash::Hash;
21use std::hash::Hasher;
22use std::sync::Arc;
23
24use itertools::Itertools as _;
25use tokio::io::AsyncReadExt as _;
26use tracing::instrument;
27
28use crate::backend;
29use crate::backend::BackendError;
30use crate::backend::BackendResult;
31use crate::backend::ConflictId;
32use crate::backend::TreeEntriesNonRecursiveIterator;
33use crate::backend::TreeId;
34use crate::backend::TreeValue;
35use crate::files;
36use crate::matchers::EverythingMatcher;
37use crate::matchers::Matcher;
38use crate::merge::MergedTreeVal;
39use crate::object_id::ObjectId as _;
40use crate::repo_path::RepoPath;
41use crate::repo_path::RepoPathBuf;
42use crate::repo_path::RepoPathComponent;
43use crate::store::Store;
44
45#[derive(Clone)]
46pub struct Tree {
47    store: Arc<Store>,
48    dir: RepoPathBuf,
49    id: TreeId,
50    data: Arc<backend::Tree>,
51}
52
53impl Debug for Tree {
54    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
55        f.debug_struct("Tree")
56            .field("dir", &self.dir)
57            .field("id", &self.id)
58            .finish()
59    }
60}
61
62impl PartialEq for Tree {
63    fn eq(&self, other: &Self) -> bool {
64        self.id == other.id && self.dir == other.dir
65    }
66}
67
68impl Eq for Tree {}
69
70impl Hash for Tree {
71    fn hash<H: Hasher>(&self, state: &mut H) {
72        self.dir.hash(state);
73        self.id.hash(state);
74    }
75}
76
77impl Tree {
78    pub fn new(store: Arc<Store>, dir: RepoPathBuf, id: TreeId, data: Arc<backend::Tree>) -> Self {
79        Tree {
80            store,
81            dir,
82            id,
83            data,
84        }
85    }
86
87    pub fn empty(store: Arc<Store>, dir: RepoPathBuf) -> Self {
88        let id = store.empty_tree_id().clone();
89        Tree {
90            store,
91            dir,
92            id,
93            data: Arc::new(backend::Tree::default()),
94        }
95    }
96
97    pub fn store(&self) -> &Arc<Store> {
98        &self.store
99    }
100
101    pub fn dir(&self) -> &RepoPath {
102        &self.dir
103    }
104
105    pub fn id(&self) -> &TreeId {
106        &self.id
107    }
108
109    pub fn data(&self) -> &backend::Tree {
110        &self.data
111    }
112
113    pub fn entries_non_recursive(&self) -> TreeEntriesNonRecursiveIterator<'_> {
114        self.data.entries()
115    }
116
117    pub fn entries_matching<'matcher>(
118        &self,
119        matcher: &'matcher dyn Matcher,
120    ) -> TreeEntriesIterator<'matcher> {
121        TreeEntriesIterator::new(self.clone(), matcher)
122    }
123
124    pub fn value(&self, basename: &RepoPathComponent) -> Option<&TreeValue> {
125        self.data.value(basename)
126    }
127
128    pub fn path_value(&self, path: &RepoPath) -> BackendResult<Option<TreeValue>> {
129        assert_eq!(self.dir(), RepoPath::root());
130        match path.split() {
131            Some((dir, basename)) => {
132                let tree = self.sub_tree_recursive(dir)?;
133                Ok(tree.and_then(|tree| tree.data.value(basename).cloned()))
134            }
135            None => Ok(Some(TreeValue::Tree(self.id.clone()))),
136        }
137    }
138
139    pub fn sub_tree(&self, name: &RepoPathComponent) -> BackendResult<Option<Tree>> {
140        if let Some(sub_tree) = self.data.value(name) {
141            match sub_tree {
142                TreeValue::Tree(sub_tree_id) => {
143                    let subdir = self.dir.join(name);
144                    let sub_tree = self.store.get_tree(subdir, sub_tree_id)?;
145                    Ok(Some(sub_tree))
146                }
147                _ => Ok(None),
148            }
149        } else {
150            Ok(None)
151        }
152    }
153
154    fn known_sub_tree(&self, subdir: RepoPathBuf, id: &TreeId) -> Tree {
155        self.store.get_tree(subdir, id).unwrap()
156    }
157
158    /// Look up the tree at the given path.
159    pub fn sub_tree_recursive(&self, path: &RepoPath) -> BackendResult<Option<Tree>> {
160        let mut current_tree = self.clone();
161        for name in path.components() {
162            match current_tree.sub_tree(name)? {
163                None => {
164                    return Ok(None);
165                }
166                Some(sub_tree) => {
167                    current_tree = sub_tree;
168                }
169            }
170        }
171        // TODO: It would be nice to be able to return a reference here, but
172        // then we would have to figure out how to share Tree instances
173        // across threads.
174        Ok(Some(current_tree))
175    }
176
177    pub fn conflicts_matching(&self, matcher: &dyn Matcher) -> Vec<(RepoPathBuf, ConflictId)> {
178        let mut conflicts = vec![];
179        for (name, value) in self.entries_matching(matcher) {
180            if let TreeValue::Conflict(id) = value {
181                conflicts.push((name.clone(), id.clone()));
182            }
183        }
184        conflicts
185    }
186
187    #[instrument]
188    pub fn conflicts(&self) -> Vec<(RepoPathBuf, ConflictId)> {
189        self.conflicts_matching(&EverythingMatcher)
190    }
191
192    pub fn has_conflict(&self) -> bool {
193        !self.conflicts().is_empty()
194    }
195}
196
197pub struct TreeEntriesIterator<'matcher> {
198    stack: Vec<TreeEntriesDirItem>,
199    matcher: &'matcher dyn Matcher,
200}
201
202struct TreeEntriesDirItem {
203    tree: Tree,
204    entries: Vec<(RepoPathBuf, TreeValue)>,
205}
206
207impl From<Tree> for TreeEntriesDirItem {
208    fn from(tree: Tree) -> Self {
209        let mut entries = tree
210            .entries_non_recursive()
211            .map(|entry| (tree.dir().join(entry.name()), entry.value().clone()))
212            .collect_vec();
213        entries.reverse();
214        Self { tree, entries }
215    }
216}
217
218impl<'matcher> TreeEntriesIterator<'matcher> {
219    fn new(tree: Tree, matcher: &'matcher dyn Matcher) -> Self {
220        // TODO: Restrict walk according to Matcher::visit()
221        Self {
222            stack: vec![TreeEntriesDirItem::from(tree)],
223            matcher,
224        }
225    }
226}
227
228impl Iterator for TreeEntriesIterator<'_> {
229    type Item = (RepoPathBuf, TreeValue);
230
231    fn next(&mut self) -> Option<Self::Item> {
232        while let Some(top) = self.stack.last_mut() {
233            if let Some((path, value)) = top.entries.pop() {
234                match value {
235                    TreeValue::Tree(id) => {
236                        // TODO: Handle the other cases (specific files and trees)
237                        if self.matcher.visit(&path).is_nothing() {
238                            continue;
239                        }
240                        let subtree = top.tree.known_sub_tree(path, &id);
241                        self.stack.push(TreeEntriesDirItem::from(subtree));
242                    }
243                    value => {
244                        if self.matcher.matches(&path) {
245                            return Some((path, value));
246                        }
247                    }
248                };
249            } else {
250                self.stack.pop();
251            }
252        }
253        None
254    }
255}
256
257/// Resolves file-level conflict by merging content hunks.
258///
259/// The input `conflict` is supposed to be simplified. It shouldn't contain
260/// non-file values that cancel each other.
261pub async fn try_resolve_file_conflict(
262    store: &Store,
263    filename: &RepoPath,
264    conflict: &MergedTreeVal<'_>,
265) -> BackendResult<Option<TreeValue>> {
266    // If there are any non-file or any missing parts in the conflict, we can't
267    // merge it. We check early so we don't waste time reading file contents if
268    // we can't merge them anyway. At the same time we determine whether the
269    // resulting file should be executable.
270    let Ok(file_id_conflict) = conflict.try_map(|term| match term {
271        Some(TreeValue::File {
272            id,
273            executable: _,
274            copy_id: _,
275        }) => Ok(id),
276        _ => Err(()),
277    }) else {
278        return Ok(None);
279    };
280    let Ok(executable_conflict) = conflict.try_map(|term| match term {
281        Some(TreeValue::File {
282            id: _,
283            executable,
284            copy_id: _,
285        }) => Ok(executable),
286        _ => Err(()),
287    }) else {
288        return Ok(None);
289    };
290    let Ok(copy_id_conflict) = conflict.try_map(|term| match term {
291        Some(TreeValue::File {
292            id: _,
293            executable: _,
294            copy_id,
295        }) => Ok(copy_id),
296        _ => Err(()),
297    }) else {
298        return Ok(None);
299    };
300    let Some(&&executable) = executable_conflict.resolve_trivial() else {
301        // We're unable to determine whether the result should be executable
302        return Ok(None);
303    };
304    let Some(&copy_id) = copy_id_conflict.resolve_trivial() else {
305        // We're unable to determine the file's copy ID
306        return Ok(None);
307    };
308    if let Some(&resolved_file_id) = file_id_conflict.resolve_trivial() {
309        // Don't bother reading the file contents if the conflict can be trivially
310        // resolved.
311        return Ok(Some(TreeValue::File {
312            id: resolved_file_id.clone(),
313            executable,
314            copy_id: copy_id.clone(),
315        }));
316    }
317
318    // While the input conflict should be simplified by caller, it might contain
319    // terms which only differ in executable bits. Simplify the conflict further
320    // for two reasons:
321    // 1. Avoid reading unchanged file contents
322    // 2. The simplified conflict can sometimes be resolved when the unsimplfied one
323    //    cannot
324    let file_id_conflict = file_id_conflict.simplify();
325
326    let contents = file_id_conflict
327        .try_map_async(|file_id| async {
328            let mut content = vec![];
329            let mut reader = store.read_file(filename, file_id).await?;
330            reader
331                .read_to_end(&mut content)
332                .await
333                .map_err(|err| BackendError::ReadObject {
334                    object_type: file_id.object_type(),
335                    hash: file_id.hex(),
336                    source: err.into(),
337                })?;
338            BackendResult::Ok(content)
339        })
340        .await?;
341    if let Some(merged_content) = files::try_merge(&contents) {
342        let id = store
343            .write_file(filename, &mut merged_content.as_slice())
344            .await?;
345        Ok(Some(TreeValue::File {
346            id,
347            executable,
348            copy_id: copy_id.clone(),
349        }))
350    } else {
351        Ok(None)
352    }
353}
jj_lib/tree.rs

jj_lib/
tree.rs
