just playing with tangled
ilyagr.bsky.social
1// Copyright 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#![allow(missing_docs)]
16
17use std::cmp::{Ordering, Reverse};
18use std::collections::{BinaryHeap, HashSet};
19use std::fmt;
20use std::iter::Peekable;
21use std::ops::Range;
22use std::sync::Arc;
23
24use itertools::Itertools;
25
26use crate::backend::{ChangeId, CommitId, MillisSinceEpoch};
27use crate::default_index_store::{
28 CompositeIndex, IndexEntry, IndexEntryByPosition, IndexPosition, RevWalk,
29};
30use crate::default_revset_graph_iterator::RevsetGraphIterator;
31use crate::id_prefix::{IdIndex, IdIndexSource, IdIndexSourceEntry};
32use crate::index::{HexPrefix, Index, PrefixResolution};
33use crate::matchers::{EverythingMatcher, Matcher, PrefixMatcher, Visit};
34use crate::repo_path::RepoPath;
35use crate::revset::{
36 ChangeIdIndex, ResolvedExpression, ResolvedPredicateExpression, Revset, RevsetEvaluationError,
37 RevsetFilterPredicate, GENERATION_RANGE_FULL,
38};
39use crate::revset_graph::RevsetGraphEdge;
40use crate::rewrite;
41use crate::store::Store;
42
43trait ToPredicateFn: fmt::Debug {
44 /// Creates function that tests if the given entry is included in the set.
45 ///
46 /// The predicate function is evaluated in order of `RevsetIterator`.
47 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_>;
48}
49
50impl<T: ToPredicateFn + ?Sized> ToPredicateFn for Box<T> {
51 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_> {
52 <T as ToPredicateFn>::to_predicate_fn(self)
53 }
54}
55
56trait InternalRevset<'index>: fmt::Debug + ToPredicateFn {
57 // All revsets currently iterate in order of descending index position
58 fn iter(&self) -> Box<dyn Iterator<Item = IndexEntry<'index>> + '_>;
59
60 fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>
61 where
62 Self: 'a;
63}
64
65pub struct RevsetImpl<'index> {
66 inner: Box<dyn InternalRevset<'index> + 'index>,
67 index: CompositeIndex<'index>,
68}
69
70impl<'index> RevsetImpl<'index> {
71 fn new(
72 revset: Box<dyn InternalRevset<'index> + 'index>,
73 index: CompositeIndex<'index>,
74 ) -> Self {
75 Self {
76 inner: revset,
77 index,
78 }
79 }
80
81 pub fn iter_graph_impl(&self) -> RevsetGraphIterator<'_, 'index> {
82 RevsetGraphIterator::new(self.index, self.inner.iter())
83 }
84}
85
86impl fmt::Debug for RevsetImpl<'_> {
87 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88 f.debug_struct("RevsetImpl")
89 .field("inner", &self.inner)
90 .finish_non_exhaustive()
91 }
92}
93
94impl<'index> Revset<'index> for RevsetImpl<'index> {
95 fn iter(&self) -> Box<dyn Iterator<Item = CommitId> + '_> {
96 Box::new(self.inner.iter().map(|index_entry| index_entry.commit_id()))
97 }
98
99 fn commit_change_ids(&self) -> Box<dyn Iterator<Item = (CommitId, ChangeId)> + '_> {
100 Box::new(
101 self.inner
102 .iter()
103 .map(|index_entry| (index_entry.commit_id(), index_entry.change_id())),
104 )
105 }
106
107 fn iter_graph(&self) -> Box<dyn Iterator<Item = (CommitId, Vec<RevsetGraphEdge>)> + '_> {
108 Box::new(self.iter_graph_impl())
109 }
110
111 fn change_id_index(&self) -> Box<dyn ChangeIdIndex + 'index> {
112 // TODO: Create a persistent lookup from change id to commit ids.
113 let mut pos_by_change = IdIndex::builder();
114 for entry in self.inner.iter() {
115 pos_by_change.insert(&entry.change_id(), entry.position());
116 }
117 Box::new(ChangeIdIndexImpl {
118 index: self.index,
119 pos_by_change: pos_by_change.build(),
120 })
121 }
122
123 fn is_empty(&self) -> bool {
124 self.iter().next().is_none()
125 }
126
127 fn count(&self) -> usize {
128 self.inner.iter().count()
129 }
130}
131
132struct ChangeIdIndexImpl<'index> {
133 index: CompositeIndex<'index>,
134 pos_by_change: IdIndex<ChangeId, IndexPosition, 4>,
135}
136
137impl ChangeIdIndex for ChangeIdIndexImpl<'_> {
138 fn resolve_prefix(&self, prefix: &HexPrefix) -> PrefixResolution<Vec<CommitId>> {
139 self.pos_by_change
140 .resolve_prefix_with(self.index, prefix, |entry| entry.commit_id())
141 .map(|(_, commit_ids)| commit_ids)
142 }
143
144 fn shortest_unique_prefix_len(&self, change_id: &ChangeId) -> usize {
145 self.pos_by_change
146 .shortest_unique_prefix_len(self.index, change_id)
147 }
148}
149
150impl<'index> IdIndexSource<IndexPosition> for CompositeIndex<'index> {
151 type Entry = IndexEntry<'index>;
152
153 fn entry_at(&self, pointer: &IndexPosition) -> Self::Entry {
154 self.entry_by_pos(*pointer)
155 }
156}
157
158impl IdIndexSourceEntry<ChangeId> for IndexEntry<'_> {
159 fn to_key(&self) -> ChangeId {
160 self.change_id()
161 }
162}
163
164#[derive(Debug)]
165struct EagerRevset<'index> {
166 index_entries: Vec<IndexEntry<'index>>,
167}
168
169impl EagerRevset<'static> {
170 pub const fn empty() -> Self {
171 EagerRevset {
172 index_entries: Vec::new(),
173 }
174 }
175}
176
177impl<'index> InternalRevset<'index> for EagerRevset<'index> {
178 fn iter(&self) -> Box<dyn Iterator<Item = IndexEntry<'index>> + '_> {
179 Box::new(self.index_entries.iter().cloned())
180 }
181
182 fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>
183 where
184 Self: 'a,
185 {
186 self
187 }
188}
189
190impl ToPredicateFn for EagerRevset<'_> {
191 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_> {
192 predicate_fn_from_iter(self.iter())
193 }
194}
195
196struct RevWalkRevset<T> {
197 walk: T,
198}
199
200impl<T> fmt::Debug for RevWalkRevset<T> {
201 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
202 f.debug_struct("RevWalkRevset").finish_non_exhaustive()
203 }
204}
205
206impl<'index, T> InternalRevset<'index> for RevWalkRevset<T>
207where
208 T: Iterator<Item = IndexEntry<'index>> + Clone,
209{
210 fn iter(&self) -> Box<dyn Iterator<Item = IndexEntry<'index>> + '_> {
211 Box::new(self.walk.clone())
212 }
213
214 fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>
215 where
216 Self: 'a,
217 {
218 self
219 }
220}
221
222impl<'index, T> ToPredicateFn for RevWalkRevset<T>
223where
224 T: Iterator<Item = IndexEntry<'index>> + Clone,
225{
226 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_> {
227 predicate_fn_from_iter(self.walk.clone())
228 }
229}
230
231fn predicate_fn_from_iter<'index, 'iter>(
232 iter: impl Iterator<Item = IndexEntry<'index>> + 'iter,
233) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + 'iter> {
234 let mut iter = iter.fuse().peekable();
235 Box::new(move |entry| {
236 while iter.next_if(|e| e.position() > entry.position()).is_some() {
237 continue;
238 }
239 iter.next_if(|e| e.position() == entry.position()).is_some()
240 })
241}
242
243#[derive(Debug)]
244struct FilterRevset<'index, P> {
245 candidates: Box<dyn InternalRevset<'index> + 'index>,
246 predicate: P,
247}
248
249impl<'index, P: ToPredicateFn> InternalRevset<'index> for FilterRevset<'index, P> {
250 fn iter(&self) -> Box<dyn Iterator<Item = IndexEntry<'index>> + '_> {
251 let p = self.predicate.to_predicate_fn();
252 Box::new(self.candidates.iter().filter(p))
253 }
254
255 fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>
256 where
257 Self: 'a,
258 {
259 self
260 }
261}
262
263impl<P: ToPredicateFn> ToPredicateFn for FilterRevset<'_, P> {
264 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_> {
265 let mut p1 = self.candidates.to_predicate_fn();
266 let mut p2 = self.predicate.to_predicate_fn();
267 Box::new(move |entry| p1(entry) && p2(entry))
268 }
269}
270
271#[derive(Debug)]
272struct NotInPredicate<S>(S);
273
274impl<S: ToPredicateFn> ToPredicateFn for NotInPredicate<S> {
275 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_> {
276 let mut p = self.0.to_predicate_fn();
277 Box::new(move |entry| !p(entry))
278 }
279}
280
281#[derive(Debug)]
282struct UnionRevset<'index> {
283 set1: Box<dyn InternalRevset<'index> + 'index>,
284 set2: Box<dyn InternalRevset<'index> + 'index>,
285}
286
287impl<'index> InternalRevset<'index> for UnionRevset<'index> {
288 fn iter(&self) -> Box<dyn Iterator<Item = IndexEntry<'index>> + '_> {
289 Box::new(UnionRevsetIterator {
290 iter1: self.set1.iter().peekable(),
291 iter2: self.set2.iter().peekable(),
292 })
293 }
294
295 fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>
296 where
297 Self: 'a,
298 {
299 self
300 }
301}
302
303impl ToPredicateFn for UnionRevset<'_> {
304 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_> {
305 let mut p1 = self.set1.to_predicate_fn();
306 let mut p2 = self.set2.to_predicate_fn();
307 Box::new(move |entry| p1(entry) || p2(entry))
308 }
309}
310
311#[derive(Debug)]
312struct UnionPredicate<S1, S2> {
313 set1: S1,
314 set2: S2,
315}
316
317impl<S1, S2> ToPredicateFn for UnionPredicate<S1, S2>
318where
319 S1: ToPredicateFn,
320 S2: ToPredicateFn,
321{
322 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_> {
323 let mut p1 = self.set1.to_predicate_fn();
324 let mut p2 = self.set2.to_predicate_fn();
325 Box::new(move |entry| p1(entry) || p2(entry))
326 }
327}
328
329struct UnionRevsetIterator<
330 'index,
331 I1: Iterator<Item = IndexEntry<'index>>,
332 I2: Iterator<Item = IndexEntry<'index>>,
333> {
334 iter1: Peekable<I1>,
335 iter2: Peekable<I2>,
336}
337
338impl<'index, I1: Iterator<Item = IndexEntry<'index>>, I2: Iterator<Item = IndexEntry<'index>>>
339 Iterator for UnionRevsetIterator<'index, I1, I2>
340{
341 type Item = IndexEntry<'index>;
342
343 fn next(&mut self) -> Option<Self::Item> {
344 match (self.iter1.peek(), self.iter2.peek()) {
345 (None, _) => self.iter2.next(),
346 (_, None) => self.iter1.next(),
347 (Some(entry1), Some(entry2)) => match entry1.position().cmp(&entry2.position()) {
348 Ordering::Less => self.iter2.next(),
349 Ordering::Equal => {
350 self.iter1.next();
351 self.iter2.next()
352 }
353 Ordering::Greater => self.iter1.next(),
354 },
355 }
356 }
357}
358
359#[derive(Debug)]
360struct IntersectionRevset<'index> {
361 set1: Box<dyn InternalRevset<'index> + 'index>,
362 set2: Box<dyn InternalRevset<'index> + 'index>,
363}
364
365impl<'index> InternalRevset<'index> for IntersectionRevset<'index> {
366 fn iter(&self) -> Box<dyn Iterator<Item = IndexEntry<'index>> + '_> {
367 Box::new(IntersectionRevsetIterator {
368 iter1: self.set1.iter().peekable(),
369 iter2: self.set2.iter().peekable(),
370 })
371 }
372
373 fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>
374 where
375 Self: 'a,
376 {
377 self
378 }
379}
380
381impl ToPredicateFn for IntersectionRevset<'_> {
382 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_> {
383 let mut p1 = self.set1.to_predicate_fn();
384 let mut p2 = self.set2.to_predicate_fn();
385 Box::new(move |entry| p1(entry) && p2(entry))
386 }
387}
388
389struct IntersectionRevsetIterator<
390 'index,
391 I1: Iterator<Item = IndexEntry<'index>>,
392 I2: Iterator<Item = IndexEntry<'index>>,
393> {
394 iter1: Peekable<I1>,
395 iter2: Peekable<I2>,
396}
397
398impl<'index, I1: Iterator<Item = IndexEntry<'index>>, I2: Iterator<Item = IndexEntry<'index>>>
399 Iterator for IntersectionRevsetIterator<'index, I1, I2>
400{
401 type Item = IndexEntry<'index>;
402
403 fn next(&mut self) -> Option<Self::Item> {
404 loop {
405 match (self.iter1.peek(), self.iter2.peek()) {
406 (None, _) => {
407 return None;
408 }
409 (_, None) => {
410 return None;
411 }
412 (Some(entry1), Some(entry2)) => match entry1.position().cmp(&entry2.position()) {
413 Ordering::Less => {
414 self.iter2.next();
415 }
416 Ordering::Equal => {
417 self.iter1.next();
418 return self.iter2.next();
419 }
420 Ordering::Greater => {
421 self.iter1.next();
422 }
423 },
424 }
425 }
426 }
427}
428
429#[derive(Debug)]
430struct DifferenceRevset<'index> {
431 // The minuend (what to subtract from)
432 set1: Box<dyn InternalRevset<'index> + 'index>,
433 // The subtrahend (what to subtract)
434 set2: Box<dyn InternalRevset<'index> + 'index>,
435}
436
437impl<'index> InternalRevset<'index> for DifferenceRevset<'index> {
438 fn iter(&self) -> Box<dyn Iterator<Item = IndexEntry<'index>> + '_> {
439 Box::new(DifferenceRevsetIterator {
440 iter1: self.set1.iter().peekable(),
441 iter2: self.set2.iter().peekable(),
442 })
443 }
444
445 fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>
446 where
447 Self: 'a,
448 {
449 self
450 }
451}
452
453impl ToPredicateFn for DifferenceRevset<'_> {
454 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_> {
455 let mut p1 = self.set1.to_predicate_fn();
456 let mut p2 = self.set2.to_predicate_fn();
457 Box::new(move |entry| p1(entry) && !p2(entry))
458 }
459}
460
461struct DifferenceRevsetIterator<
462 'index,
463 I1: Iterator<Item = IndexEntry<'index>>,
464 I2: Iterator<Item = IndexEntry<'index>>,
465> {
466 iter1: Peekable<I1>,
467 iter2: Peekable<I2>,
468}
469
470impl<'index, I1: Iterator<Item = IndexEntry<'index>>, I2: Iterator<Item = IndexEntry<'index>>>
471 Iterator for DifferenceRevsetIterator<'index, I1, I2>
472{
473 type Item = IndexEntry<'index>;
474
475 fn next(&mut self) -> Option<Self::Item> {
476 loop {
477 match (self.iter1.peek(), self.iter2.peek()) {
478 (None, _) => {
479 return None;
480 }
481 (_, None) => {
482 return self.iter1.next();
483 }
484 (Some(entry1), Some(entry2)) => match entry1.position().cmp(&entry2.position()) {
485 Ordering::Less => {
486 self.iter2.next();
487 }
488 Ordering::Equal => {
489 self.iter2.next();
490 self.iter1.next();
491 }
492 Ordering::Greater => {
493 return self.iter1.next();
494 }
495 },
496 }
497 }
498 }
499}
500
501pub fn evaluate<'index>(
502 expression: &ResolvedExpression,
503 store: &Arc<Store>,
504 index: CompositeIndex<'index>,
505) -> Result<RevsetImpl<'index>, RevsetEvaluationError> {
506 let context = EvaluationContext {
507 store: store.clone(),
508 index,
509 };
510 let internal_revset = context.evaluate(expression)?;
511 Ok(RevsetImpl::new(internal_revset, index))
512}
513
514struct EvaluationContext<'index> {
515 store: Arc<Store>,
516 index: CompositeIndex<'index>,
517}
518
519fn to_u32_generation_range(range: &Range<u64>) -> Result<Range<u32>, RevsetEvaluationError> {
520 let start = range.start.try_into().map_err(|_| {
521 RevsetEvaluationError::Other(format!(
522 "Lower bound of generation ({}) is too large",
523 range.start
524 ))
525 })?;
526 let end = range.end.try_into().unwrap_or(u32::MAX);
527 Ok(start..end)
528}
529
530impl<'index> EvaluationContext<'index> {
531 fn evaluate(
532 &self,
533 expression: &ResolvedExpression,
534 ) -> Result<Box<dyn InternalRevset<'index> + 'index>, RevsetEvaluationError> {
535 match expression {
536 ResolvedExpression::Commits(commit_ids) => {
537 Ok(Box::new(self.revset_for_commit_ids(commit_ids)))
538 }
539 ResolvedExpression::Ancestors { heads, generation } => {
540 let head_set = self.evaluate(heads)?;
541 let walk = self.walk_ancestors(&*head_set);
542 if generation == &GENERATION_RANGE_FULL {
543 Ok(Box::new(RevWalkRevset { walk }))
544 } else {
545 let walk = walk.filter_by_generation(to_u32_generation_range(generation)?);
546 Ok(Box::new(RevWalkRevset { walk }))
547 }
548 }
549 ResolvedExpression::Range {
550 roots,
551 heads,
552 generation,
553 } => {
554 let root_set = self.evaluate(roots)?;
555 let root_positions = root_set.iter().map(|entry| entry.position()).collect_vec();
556 let head_set = self.evaluate(heads)?;
557 let head_positions = head_set.iter().map(|entry| entry.position()).collect_vec();
558 let walk = self.index.walk_revs(&head_positions, &root_positions);
559 if generation == &GENERATION_RANGE_FULL {
560 Ok(Box::new(RevWalkRevset { walk }))
561 } else {
562 let walk = walk.filter_by_generation(to_u32_generation_range(generation)?);
563 Ok(Box::new(RevWalkRevset { walk }))
564 }
565 }
566 ResolvedExpression::DagRange {
567 roots,
568 heads,
569 generation_from_roots,
570 } => {
571 let root_set = self.evaluate(roots)?;
572 let head_set = self.evaluate(heads)?;
573 if generation_from_roots == &(1..2) {
574 Ok(Box::new(self.walk_children(&*root_set, &*head_set)))
575 } else if generation_from_roots == &GENERATION_RANGE_FULL {
576 let (dag_range_set, _) = self.collect_dag_range(&*root_set, &*head_set);
577 Ok(Box::new(dag_range_set))
578 } else {
579 // For small generation range, it might be better to build a reachable map
580 // with generation bit set, which can be calculated incrementally from roots:
581 // reachable[pos] = (reachable[parent_pos] | ...) << 1
582 let root_positions =
583 root_set.iter().map(|entry| entry.position()).collect_vec();
584 let walk = self
585 .walk_ancestors(&*head_set)
586 .descendants_filtered_by_generation(
587 &root_positions,
588 to_u32_generation_range(generation_from_roots)?,
589 );
590 let mut index_entries = walk.collect_vec();
591 index_entries.reverse();
592 Ok(Box::new(EagerRevset { index_entries }))
593 }
594 }
595 ResolvedExpression::Heads(candidates) => {
596 let candidate_set = self.evaluate(candidates)?;
597 let candidate_ids = candidate_set
598 .iter()
599 .map(|entry| entry.commit_id())
600 .collect_vec();
601 Ok(Box::new(self.revset_for_commit_ids(
602 &self.index.heads(&mut candidate_ids.iter()),
603 )))
604 }
605 ResolvedExpression::Roots(candidates) => {
606 let candidate_set = EagerRevset {
607 index_entries: self.evaluate(candidates)?.iter().collect(),
608 };
609 let (_, filled) = self.collect_dag_range(&candidate_set, &candidate_set);
610 let mut index_entries = vec![];
611 for candidate in candidate_set.iter() {
612 if !candidate
613 .parent_positions()
614 .iter()
615 .any(|parent| filled.contains(parent))
616 {
617 index_entries.push(candidate);
618 }
619 }
620 Ok(Box::new(EagerRevset { index_entries }))
621 }
622 ResolvedExpression::Latest { candidates, count } => {
623 let candidate_set = self.evaluate(candidates)?;
624 Ok(Box::new(
625 self.take_latest_revset(candidate_set.as_ref(), *count),
626 ))
627 }
628 ResolvedExpression::Union(expression1, expression2) => {
629 let set1 = self.evaluate(expression1)?;
630 let set2 = self.evaluate(expression2)?;
631 Ok(Box::new(UnionRevset { set1, set2 }))
632 }
633 ResolvedExpression::FilterWithin {
634 candidates,
635 predicate,
636 } => Ok(Box::new(FilterRevset {
637 candidates: self.evaluate(candidates)?,
638 predicate: self.evaluate_predicate(predicate)?,
639 })),
640 ResolvedExpression::Intersection(expression1, expression2) => {
641 let set1 = self.evaluate(expression1)?;
642 let set2 = self.evaluate(expression2)?;
643 Ok(Box::new(IntersectionRevset { set1, set2 }))
644 }
645 ResolvedExpression::Difference(expression1, expression2) => {
646 let set1 = self.evaluate(expression1)?;
647 let set2 = self.evaluate(expression2)?;
648 Ok(Box::new(DifferenceRevset { set1, set2 }))
649 }
650 }
651 }
652
653 fn evaluate_predicate(
654 &self,
655 expression: &ResolvedPredicateExpression,
656 ) -> Result<Box<dyn ToPredicateFn + 'index>, RevsetEvaluationError> {
657 match expression {
658 ResolvedPredicateExpression::Filter(predicate) => Ok(build_predicate_fn(
659 self.store.clone(),
660 self.index,
661 predicate,
662 )),
663 ResolvedPredicateExpression::Set(expression) => {
664 Ok(self.evaluate(expression)?.into_predicate())
665 }
666 ResolvedPredicateExpression::NotIn(complement) => {
667 let set = self.evaluate_predicate(complement)?;
668 Ok(Box::new(NotInPredicate(set)))
669 }
670 ResolvedPredicateExpression::Union(expression1, expression2) => {
671 let set1 = self.evaluate_predicate(expression1)?;
672 let set2 = self.evaluate_predicate(expression2)?;
673 Ok(Box::new(UnionPredicate { set1, set2 }))
674 }
675 }
676 }
677
678 fn walk_ancestors<'a, S>(&self, head_set: &S) -> RevWalk<'index>
679 where
680 S: InternalRevset<'a> + ?Sized,
681 {
682 let head_positions = head_set.iter().map(|entry| entry.position()).collect_vec();
683 self.index.walk_revs(&head_positions, &[])
684 }
685
686 fn walk_children<'a, 'b, S, T>(
687 &self,
688 root_set: &S,
689 head_set: &T,
690 ) -> impl InternalRevset<'index> + 'index
691 where
692 S: InternalRevset<'a> + ?Sized,
693 T: InternalRevset<'b> + ?Sized,
694 {
695 let root_positions = root_set.iter().map(|entry| entry.position()).collect_vec();
696 let walk = self
697 .walk_ancestors(head_set)
698 .take_until_roots(&root_positions);
699 let root_positions: HashSet<_> = root_positions.into_iter().collect();
700 let candidates = Box::new(RevWalkRevset { walk });
701 let predicate = PurePredicateFn(move |entry: &IndexEntry| {
702 entry
703 .parent_positions()
704 .iter()
705 .any(|parent_pos| root_positions.contains(parent_pos))
706 });
707 // TODO: Suppose heads include all visible heads, ToPredicateFn version can be
708 // optimized to only test the predicate()
709 FilterRevset {
710 candidates,
711 predicate,
712 }
713 }
714
715 /// Calculates `root_set::head_set`.
716 fn collect_dag_range<'a, 'b, S, T>(
717 &self,
718 root_set: &S,
719 head_set: &T,
720 ) -> (EagerRevset<'index>, HashSet<IndexPosition>)
721 where
722 S: InternalRevset<'a> + ?Sized,
723 T: InternalRevset<'b> + ?Sized,
724 {
725 let root_positions = root_set.iter().map(|entry| entry.position()).collect_vec();
726 let walk = self
727 .walk_ancestors(head_set)
728 .take_until_roots(&root_positions);
729 let root_positions: HashSet<_> = root_positions.into_iter().collect();
730 let mut reachable_positions = HashSet::new();
731 let mut index_entries = vec![];
732 for candidate in walk.collect_vec().into_iter().rev() {
733 if root_positions.contains(&candidate.position())
734 || candidate
735 .parent_positions()
736 .iter()
737 .any(|parent_pos| reachable_positions.contains(parent_pos))
738 {
739 reachable_positions.insert(candidate.position());
740 index_entries.push(candidate);
741 }
742 }
743 index_entries.reverse();
744 (EagerRevset { index_entries }, reachable_positions)
745 }
746
747 fn revset_for_commit_ids(&self, commit_ids: &[CommitId]) -> EagerRevset<'index> {
748 let mut index_entries = vec![];
749 for id in commit_ids {
750 index_entries.push(self.index.entry_by_id(id).unwrap());
751 }
752 index_entries.sort_unstable_by_key(|b| Reverse(b.position()));
753 index_entries.dedup();
754 EagerRevset { index_entries }
755 }
756
757 fn take_latest_revset(
758 &self,
759 candidate_set: &dyn InternalRevset<'index>,
760 count: usize,
761 ) -> EagerRevset<'index> {
762 if count == 0 {
763 return EagerRevset::empty();
764 }
765
766 #[derive(Clone, Eq, Ord, PartialEq, PartialOrd)]
767 struct Item<'a> {
768 timestamp: MillisSinceEpoch,
769 entry: IndexEntryByPosition<'a>, // tie-breaker
770 }
771
772 let make_rev_item = |entry: IndexEntry<'index>| {
773 let commit = self.store.get_commit(&entry.commit_id()).unwrap();
774 Reverse(Item {
775 timestamp: commit.committer().timestamp.timestamp.clone(),
776 entry: IndexEntryByPosition(entry),
777 })
778 };
779
780 // Maintain min-heap containing the latest (greatest) count items. For small
781 // count and large candidate set, this is probably cheaper than building vec
782 // and applying selection algorithm.
783 let mut candidate_iter = candidate_set.iter().map(make_rev_item).fuse();
784 let mut latest_items = BinaryHeap::from_iter(candidate_iter.by_ref().take(count));
785 for item in candidate_iter {
786 let mut earliest = latest_items.peek_mut().unwrap();
787 if earliest.0 < item.0 {
788 *earliest = item;
789 }
790 }
791
792 assert!(latest_items.len() <= count);
793 let mut index_entries = latest_items
794 .into_iter()
795 .map(|item| item.0.entry.0)
796 .collect_vec();
797 index_entries.sort_unstable_by_key(|b| Reverse(b.position()));
798 EagerRevset { index_entries }
799 }
800}
801
802struct PurePredicateFn<F>(F);
803
804impl<F> fmt::Debug for PurePredicateFn<F> {
805 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
806 f.debug_struct("PurePredicateFn").finish_non_exhaustive()
807 }
808}
809
810impl<F: Fn(&IndexEntry<'_>) -> bool> ToPredicateFn for PurePredicateFn<F> {
811 fn to_predicate_fn(&self) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + '_> {
812 Box::new(&self.0)
813 }
814}
815
816fn pure_predicate_fn<'index>(
817 f: impl Fn(&IndexEntry<'_>) -> bool + 'index,
818) -> Box<dyn ToPredicateFn + 'index> {
819 Box::new(PurePredicateFn(f))
820}
821
822fn build_predicate_fn<'index>(
823 store: Arc<Store>,
824 index: CompositeIndex<'index>,
825 predicate: &RevsetFilterPredicate,
826) -> Box<dyn ToPredicateFn + 'index> {
827 match predicate {
828 RevsetFilterPredicate::ParentCount(parent_count_range) => {
829 let parent_count_range = parent_count_range.clone();
830 pure_predicate_fn(move |entry| parent_count_range.contains(&entry.num_parents()))
831 }
832 RevsetFilterPredicate::Description(needle) => {
833 let needle = needle.clone();
834 pure_predicate_fn(move |entry| {
835 store
836 .get_commit(&entry.commit_id())
837 .unwrap()
838 .description()
839 .contains(needle.as_str())
840 })
841 }
842 RevsetFilterPredicate::Author(needle) => {
843 let needle = needle.clone();
844 // TODO: Make these functions that take a needle to search for accept some
845 // syntax for specifying whether it's a regex and whether it's
846 // case-sensitive.
847 pure_predicate_fn(move |entry| {
848 let commit = store.get_commit(&entry.commit_id()).unwrap();
849 commit.author().name.contains(needle.as_str())
850 || commit.author().email.contains(needle.as_str())
851 })
852 }
853 RevsetFilterPredicate::Committer(needle) => {
854 let needle = needle.clone();
855 pure_predicate_fn(move |entry| {
856 let commit = store.get_commit(&entry.commit_id()).unwrap();
857 commit.committer().name.contains(needle.as_str())
858 || commit.committer().email.contains(needle.as_str())
859 })
860 }
861 RevsetFilterPredicate::File(paths) => {
862 // TODO: Add support for globs and other formats
863 let matcher: Box<dyn Matcher> = if let Some(paths) = paths {
864 Box::new(PrefixMatcher::new(paths))
865 } else {
866 Box::new(EverythingMatcher)
867 };
868 pure_predicate_fn(move |entry| {
869 has_diff_from_parent(&store, index, entry, matcher.as_ref())
870 })
871 }
872 RevsetFilterPredicate::HasConflict => pure_predicate_fn(move |entry| {
873 let commit = store.get_commit(&entry.commit_id()).unwrap();
874 commit.merged_tree().unwrap().has_conflict()
875 }),
876 }
877}
878
879fn has_diff_from_parent(
880 store: &Arc<Store>,
881 index: CompositeIndex<'_>,
882 entry: &IndexEntry<'_>,
883 matcher: &dyn Matcher,
884) -> bool {
885 let commit = store.get_commit(&entry.commit_id()).unwrap();
886 let parents = commit.parents();
887 if let [parent] = parents.as_slice() {
888 // Fast path: no need to load the root tree
889 let unchanged = commit.tree_id() == parent.tree_id();
890 if matcher.visit(&RepoPath::root()) == Visit::AllRecursively {
891 return !unchanged;
892 } else if unchanged {
893 return false;
894 }
895 }
896 let from_tree = rewrite::merge_commit_trees_without_repo(store, &index, &parents).unwrap();
897 let to_tree = commit.tree();
898 from_tree.diff(&to_tree, matcher).next().is_some()
899}
900
901#[cfg(test)]
902mod tests {
903 use super::*;
904 use crate::backend::{ChangeId, CommitId, ObjectId};
905 use crate::default_index_store::MutableIndexImpl;
906
907 /// Generator of unique 16-byte ChangeId excluding root id
908 fn change_id_generator() -> impl FnMut() -> ChangeId {
909 let mut iter = (1_u128..).map(|n| ChangeId::new(n.to_le_bytes().into()));
910 move || iter.next().unwrap()
911 }
912
913 #[test]
914 fn test_revset_combinator() {
915 let mut new_change_id = change_id_generator();
916 let mut index = MutableIndexImpl::full(3, 16);
917 let id_0 = CommitId::from_hex("000000");
918 let id_1 = CommitId::from_hex("111111");
919 let id_2 = CommitId::from_hex("222222");
920 let id_3 = CommitId::from_hex("333333");
921 let id_4 = CommitId::from_hex("444444");
922 index.add_commit_data(id_0.clone(), new_change_id(), &[]);
923 index.add_commit_data(id_1.clone(), new_change_id(), &[id_0.clone()]);
924 index.add_commit_data(id_2.clone(), new_change_id(), &[id_1.clone()]);
925 index.add_commit_data(id_3.clone(), new_change_id(), &[id_2.clone()]);
926 index.add_commit_data(id_4.clone(), new_change_id(), &[id_3.clone()]);
927
928 let get_entry = |id: &CommitId| index.as_composite().entry_by_id(id).unwrap();
929 let make_entries = |ids: &[&CommitId]| ids.iter().map(|id| get_entry(id)).collect_vec();
930 let make_set = |ids: &[&CommitId]| -> Box<dyn InternalRevset> {
931 let index_entries = make_entries(ids);
932 Box::new(EagerRevset { index_entries })
933 };
934
935 let set = make_set(&[&id_4, &id_3, &id_2, &id_0]);
936 let mut p = set.to_predicate_fn();
937 assert!(p(&get_entry(&id_4)));
938 assert!(p(&get_entry(&id_3)));
939 assert!(p(&get_entry(&id_2)));
940 assert!(!p(&get_entry(&id_1)));
941 assert!(p(&get_entry(&id_0)));
942 // Uninteresting entries can be skipped
943 let mut p = set.to_predicate_fn();
944 assert!(p(&get_entry(&id_3)));
945 assert!(!p(&get_entry(&id_1)));
946 assert!(p(&get_entry(&id_0)));
947
948 let set = FilterRevset {
949 candidates: make_set(&[&id_4, &id_2, &id_0]),
950 predicate: pure_predicate_fn(|entry| entry.commit_id() != id_4),
951 };
952 assert_eq!(set.iter().collect_vec(), make_entries(&[&id_2, &id_0]));
953 let mut p = set.to_predicate_fn();
954 assert!(!p(&get_entry(&id_4)));
955 assert!(!p(&get_entry(&id_3)));
956 assert!(p(&get_entry(&id_2)));
957 assert!(!p(&get_entry(&id_1)));
958 assert!(p(&get_entry(&id_0)));
959
960 // Intersection by FilterRevset
961 let set = FilterRevset {
962 candidates: make_set(&[&id_4, &id_2, &id_0]),
963 predicate: make_set(&[&id_3, &id_2, &id_1]),
964 };
965 assert_eq!(set.iter().collect_vec(), make_entries(&[&id_2]));
966 let mut p = set.to_predicate_fn();
967 assert!(!p(&get_entry(&id_4)));
968 assert!(!p(&get_entry(&id_3)));
969 assert!(p(&get_entry(&id_2)));
970 assert!(!p(&get_entry(&id_1)));
971 assert!(!p(&get_entry(&id_0)));
972
973 let set = UnionRevset {
974 set1: make_set(&[&id_4, &id_2]),
975 set2: make_set(&[&id_3, &id_2, &id_1]),
976 };
977 assert_eq!(
978 set.iter().collect_vec(),
979 make_entries(&[&id_4, &id_3, &id_2, &id_1])
980 );
981 let mut p = set.to_predicate_fn();
982 assert!(p(&get_entry(&id_4)));
983 assert!(p(&get_entry(&id_3)));
984 assert!(p(&get_entry(&id_2)));
985 assert!(p(&get_entry(&id_1)));
986 assert!(!p(&get_entry(&id_0)));
987
988 let set = IntersectionRevset {
989 set1: make_set(&[&id_4, &id_2, &id_0]),
990 set2: make_set(&[&id_3, &id_2, &id_1]),
991 };
992 assert_eq!(set.iter().collect_vec(), make_entries(&[&id_2]));
993 let mut p = set.to_predicate_fn();
994 assert!(!p(&get_entry(&id_4)));
995 assert!(!p(&get_entry(&id_3)));
996 assert!(p(&get_entry(&id_2)));
997 assert!(!p(&get_entry(&id_1)));
998 assert!(!p(&get_entry(&id_0)));
999
1000 let set = DifferenceRevset {
1001 set1: make_set(&[&id_4, &id_2, &id_0]),
1002 set2: make_set(&[&id_3, &id_2, &id_1]),
1003 };
1004 assert_eq!(set.iter().collect_vec(), make_entries(&[&id_4, &id_0]));
1005 let mut p = set.to_predicate_fn();
1006 assert!(p(&get_entry(&id_4)));
1007 assert!(!p(&get_entry(&id_3)));
1008 assert!(!p(&get_entry(&id_2)));
1009 assert!(!p(&get_entry(&id_1)));
1010 assert!(p(&get_entry(&id_0)));
1011 }
1012}