jj_lib/
op_walk.rs

1// Copyright 2020-2023 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//! Utility for operation id resolution and traversal.
16
17use std::cmp::Ordering;
18use std::collections::HashMap;
19use std::collections::HashSet;
20use std::slice;
21use std::sync::Arc;
22
23use itertools::Itertools as _;
24use thiserror::Error;
25
26use crate::dag_walk;
27use crate::object_id::HexPrefix;
28use crate::object_id::PrefixResolution;
29use crate::op_heads_store;
30use crate::op_heads_store::OpHeadResolutionError;
31use crate::op_heads_store::OpHeadsStore;
32use crate::op_heads_store::OpHeadsStoreError;
33use crate::op_store::OpStore;
34use crate::op_store::OpStoreError;
35use crate::op_store::OpStoreResult;
36use crate::op_store::OperationId;
37use crate::operation::Operation;
38use crate::repo::ReadonlyRepo;
39use crate::repo::Repo as _;
40use crate::repo::RepoLoader;
41
42/// Error that may occur during evaluation of operation set expression.
43#[derive(Debug, Error)]
44pub enum OpsetEvaluationError {
45    /// Failed to resolve operation set expression.
46    #[error(transparent)]
47    OpsetResolution(#[from] OpsetResolutionError),
48    /// Failed to read op heads.
49    #[error(transparent)]
50    OpHeadsStore(#[from] OpHeadsStoreError),
51    /// Failed to resolve the current operation heads.
52    #[error(transparent)]
53    OpHeadResolution(#[from] OpHeadResolutionError),
54    /// Failed to access operation object.
55    #[error(transparent)]
56    OpStore(#[from] OpStoreError),
57}
58
59/// Error that may occur during parsing and resolution of operation set
60/// expression.
61#[derive(Debug, Error)]
62pub enum OpsetResolutionError {
63    // TODO: Maybe empty/multiple operations should be allowed, and rejected by
64    // caller as needed.
65    /// Expression resolved to multiple operations.
66    #[error(r#"The "{expr}" expression resolved to more than one operation"#)]
67    MultipleOperations {
68        /// Source expression.
69        expr: String,
70        /// Matched operation ids.
71        candidates: Vec<OperationId>,
72    },
73    /// Expression resolved to no operations.
74    #[error(r#"The "{0}" expression resolved to no operations"#)]
75    EmptyOperations(String),
76    /// Invalid symbol as an operation ID.
77    #[error(r#"Operation ID "{0}" is not a valid hexadecimal prefix"#)]
78    InvalidIdPrefix(String),
79    /// Operation ID not found.
80    #[error(r#"No operation ID matching "{0}""#)]
81    NoSuchOperation(String),
82    /// Operation ID prefix matches multiple operations.
83    #[error(r#"Operation ID prefix "{0}" is ambiguous"#)]
84    AmbiguousIdPrefix(String),
85}
86
87/// Resolves operation set expression without loading a repo.
88pub fn resolve_op_for_load(
89    repo_loader: &RepoLoader,
90    op_str: &str,
91) -> Result<Operation, OpsetEvaluationError> {
92    let op_store = repo_loader.op_store();
93    let op_heads_store = repo_loader.op_heads_store().as_ref();
94    let get_current_op = || {
95        op_heads_store::resolve_op_heads(op_heads_store, op_store, |op_heads| {
96            Err(OpsetResolutionError::MultipleOperations {
97                expr: "@".to_owned(),
98                candidates: op_heads.iter().map(|op| op.id().clone()).collect(),
99            }
100            .into())
101        })
102    };
103    let get_head_ops = || get_current_head_ops(op_store, op_heads_store);
104    resolve_single_op(op_store, get_current_op, get_head_ops, op_str)
105}
106
107/// Resolves operation set expression against the loaded repo.
108///
109/// The "@" symbol will be resolved to the operation the repo was loaded at.
110pub fn resolve_op_with_repo(
111    repo: &ReadonlyRepo,
112    op_str: &str,
113) -> Result<Operation, OpsetEvaluationError> {
114    resolve_op_at(repo.op_store(), slice::from_ref(repo.operation()), op_str)
115}
116
117/// Resolves operation set expression at the given head operations.
118pub fn resolve_op_at(
119    op_store: &Arc<dyn OpStore>,
120    head_ops: &[Operation],
121    op_str: &str,
122) -> Result<Operation, OpsetEvaluationError> {
123    let get_current_op = || match head_ops {
124        [head_op] => Ok(head_op.clone()),
125        [] => Err(OpsetResolutionError::EmptyOperations("@".to_owned()).into()),
126        _ => Err(OpsetResolutionError::MultipleOperations {
127            expr: "@".to_owned(),
128            candidates: head_ops.iter().map(|op| op.id().clone()).collect(),
129        }
130        .into()),
131    };
132    let get_head_ops = || Ok(head_ops.to_vec());
133    resolve_single_op(op_store, get_current_op, get_head_ops, op_str)
134}
135
136/// Resolves operation set expression with the given "@" symbol resolution
137/// callbacks.
138fn resolve_single_op(
139    op_store: &Arc<dyn OpStore>,
140    get_current_op: impl FnOnce() -> Result<Operation, OpsetEvaluationError>,
141    get_head_ops: impl FnOnce() -> Result<Vec<Operation>, OpsetEvaluationError>,
142    op_str: &str,
143) -> Result<Operation, OpsetEvaluationError> {
144    let op_symbol = op_str.trim_end_matches(['-', '+']);
145    let op_postfix = &op_str[op_symbol.len()..];
146    let head_ops = op_postfix.contains('+').then(get_head_ops).transpose()?;
147    let mut operation = match op_symbol {
148        "@" => get_current_op(),
149        s => resolve_single_op_from_store(op_store, s),
150    }?;
151    for (i, c) in op_postfix.chars().enumerate() {
152        let mut neighbor_ops = match c {
153            '-' => operation.parents().try_collect()?,
154            '+' => find_child_ops(head_ops.as_ref().unwrap(), operation.id())?,
155            _ => unreachable!(),
156        };
157        operation = match neighbor_ops.len() {
158            // Since there is no hint provided for `EmptyOperations` in
159            // `opset_resolution_error_hint()` (there would be no useful hint for the
160            // user to take action on anyway), we don't have to worry about op ids being
161            // incoherent with the op set expression shown to the user, unlike for the
162            // `MultipleOperations` variant.
163            //
164            // The full op set expression is guaranteed to be empty in this case,
165            // because ancestors/descendants of an empty operation are empty.
166            0 => Err(OpsetResolutionError::EmptyOperations(op_str.to_owned()))?,
167            1 => neighbor_ops.pop().unwrap(),
168            // Returns the exact subexpression that resolves to multiple operations,
169            // rather than the full expression provided by the user.
170            _ => Err(OpsetResolutionError::MultipleOperations {
171                expr: op_str[..=op_symbol.len() + i].to_owned(),
172                candidates: neighbor_ops.iter().map(|op| op.id().clone()).collect(),
173            })?,
174        };
175    }
176    Ok(operation)
177}
178
179fn resolve_single_op_from_store(
180    op_store: &Arc<dyn OpStore>,
181    op_str: &str,
182) -> Result<Operation, OpsetEvaluationError> {
183    if op_str.is_empty() {
184        return Err(OpsetResolutionError::InvalidIdPrefix(op_str.to_owned()).into());
185    }
186    let prefix = HexPrefix::new(op_str)
187        .ok_or_else(|| OpsetResolutionError::InvalidIdPrefix(op_str.to_owned()))?;
188    match op_store.resolve_operation_id_prefix(&prefix)? {
189        PrefixResolution::NoMatch => {
190            Err(OpsetResolutionError::NoSuchOperation(op_str.to_owned()).into())
191        }
192        PrefixResolution::SingleMatch(op_id) => {
193            let data = op_store.read_operation(&op_id)?;
194            Ok(Operation::new(op_store.clone(), op_id, data))
195        }
196        PrefixResolution::AmbiguousMatch => {
197            Err(OpsetResolutionError::AmbiguousIdPrefix(op_str.to_owned()).into())
198        }
199    }
200}
201
202/// Loads the current head operations. The returned operations may contain
203/// redundant ones which are ancestors of the other heads.
204pub fn get_current_head_ops(
205    op_store: &Arc<dyn OpStore>,
206    op_heads_store: &dyn OpHeadsStore,
207) -> Result<Vec<Operation>, OpsetEvaluationError> {
208    let mut head_ops: Vec<_> = op_heads_store
209        .get_op_heads()?
210        .into_iter()
211        .map(|id| -> OpStoreResult<Operation> {
212            let data = op_store.read_operation(&id)?;
213            Ok(Operation::new(op_store.clone(), id, data))
214        })
215        .try_collect()?;
216    // To stabilize output, sort in the same order as resolve_op_heads()
217    head_ops.sort_by_key(|op| op.metadata().end_time.timestamp);
218    Ok(head_ops)
219}
220
221/// Looks up children of the `root_op_id` by traversing from the `head_ops`.
222///
223/// This will be slow if the `root_op_id` is far away (or unreachable) from the
224/// `head_ops`.
225fn find_child_ops(
226    head_ops: &[Operation],
227    root_op_id: &OperationId,
228) -> OpStoreResult<Vec<Operation>> {
229    walk_ancestors(head_ops)
230        .take_while(|res| res.as_ref().map_or(true, |op| op.id() != root_op_id))
231        .filter_ok(|op| op.parent_ids().iter().any(|id| id == root_op_id))
232        .try_collect()
233}
234
235#[derive(Clone, Debug, Eq, Hash, PartialEq)]
236struct OperationByEndTime(Operation);
237
238impl Ord for OperationByEndTime {
239    fn cmp(&self, other: &Self) -> Ordering {
240        let self_end_time = &self.0.metadata().end_time;
241        let other_end_time = &other.0.metadata().end_time;
242        self_end_time
243            .cmp(other_end_time)
244            .then_with(|| self.0.cmp(&other.0)) // to comply with Eq
245    }
246}
247
248impl PartialOrd for OperationByEndTime {
249    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
250        Some(self.cmp(other))
251    }
252}
253
254/// Walks `head_ops` and their ancestors in reverse topological order.
255pub fn walk_ancestors(
256    head_ops: &[Operation],
257) -> impl Iterator<Item = OpStoreResult<Operation>> + use<> {
258    // Emit the latest head first to stabilize the order.
259    let mut head_ops = head_ops
260        .iter()
261        .cloned()
262        .map(OperationByEndTime)
263        .collect_vec();
264    head_ops.sort_unstable_by(|op1, op2| op1.cmp(op2).reverse());
265    // Lazily load operations based on timestamp-based heuristic. This works so long
266    // as the operation history is mostly linear.
267    dag_walk::topo_order_reverse_lazy_ok(
268        head_ops.into_iter().map(Ok),
269        |OperationByEndTime(op)| op.id().clone(),
270        |OperationByEndTime(op)| op.parents().map_ok(OperationByEndTime).collect_vec(),
271    )
272    .map_ok(|OperationByEndTime(op)| op)
273}
274
275/// Stats about `reparent_range()`.
276#[derive(Clone, Debug, Eq, PartialEq)]
277pub struct ReparentStats {
278    /// New head operation ids in order of the old `head_ops`.
279    pub new_head_ids: Vec<OperationId>,
280    /// The number of rewritten operations.
281    pub rewritten_count: usize,
282    /// The number of ancestor operations that become unreachable from the
283    /// rewritten heads.
284    pub unreachable_count: usize,
285}
286
287/// Reparents the operation range `root_ops..head_ops` onto the `dest_op`.
288///
289/// Returns the new head operation ids as well as some stats. If the old
290/// operation heads are remapped to the new heads, the operations within the
291/// range `dest_op..root_ops` become unreachable.
292///
293/// If the source operation range `root_ops..head_ops` was empty, the
294/// `new_head_ids` will be `[dest_op.id()]`, meaning the `dest_op` is the head.
295// TODO: Find better place to host this function. It might be an OpStore method.
296pub fn reparent_range(
297    op_store: &dyn OpStore,
298    root_ops: &[Operation],
299    head_ops: &[Operation],
300    dest_op: &Operation,
301) -> OpStoreResult<ReparentStats> {
302    // Calculate ::root_ops to exclude them from the source range and count the
303    // number of operations that become unreachable.
304    let mut unwanted_ids: HashSet<_> = walk_ancestors(root_ops)
305        .map_ok(|op| op.id().clone())
306        .try_collect()?;
307    let ops_to_reparent: Vec<_> = walk_ancestors(head_ops)
308        .filter_ok(|op| !unwanted_ids.contains(op.id()))
309        .try_collect()?;
310    for op in walk_ancestors(slice::from_ref(dest_op)) {
311        unwanted_ids.remove(op?.id());
312    }
313    let unreachable_ids = unwanted_ids;
314
315    assert!(
316        ops_to_reparent
317            .last()
318            .is_none_or(|op| op.id() != op_store.root_operation_id()),
319        "root operation cannot be rewritten"
320    );
321    let mut rewritten_ids = HashMap::new();
322    for old_op in ops_to_reparent.into_iter().rev() {
323        let mut data = old_op.store_operation().clone();
324        let mut dest_once = Some(dest_op.id());
325        data.parents = data
326            .parents
327            .iter()
328            .filter_map(|id| rewritten_ids.get(id).or_else(|| dest_once.take()))
329            .cloned()
330            .collect();
331        let new_id = op_store.write_operation(&data)?;
332        rewritten_ids.insert(old_op.id().clone(), new_id);
333    }
334
335    let mut dest_once = Some(dest_op.id());
336    let new_head_ids = head_ops
337        .iter()
338        .filter_map(|op| rewritten_ids.get(op.id()).or_else(|| dest_once.take()))
339        .cloned()
340        .collect();
341    Ok(ReparentStats {
342        new_head_ids,
343        rewritten_count: rewritten_ids.len(),
344        unreachable_count: unreachable_ids.len(),
345    })
346}
jj_lib/op_walk.rs

jj_lib/
op_walk.rs
