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

jj_lib/
tree.rs
