Skip to main content

grit_lib/diff/
pickaxe.rs

1//! Pickaxe filters (`-S` / `-G`) for revision walks and diffs.
2//!
3//! `-S` keeps commits where the number of occurrences of a string (or ERE pattern with
4//! `--pickaxe-regex`) differs between a file's pre- and post-image compared to the first
5//! parent. `-G` keeps commits where added or removed lines match a regex (Git line-level diff).
6//! Merge commits are omitted unless combined merge diffs are requested (matches default `git log`).
7
8use std::collections::HashMap;
9use std::sync::Arc;
10
11use crate::config::ConfigSet;
12use crate::diff::core::diff_trees_for_pathspecs;
13use crate::diff::posix_ere::PosixEre;
14use crate::diff::structured::SideBytes;
15use crate::diff::{
16    detect_renames_with_policy, renames_from_config, DetectRenamesOptions, DiffEntry, DiffStatus,
17    RenameDetection,
18};
19use crate::error::{Error, Result};
20use crate::objects::{parse_commit, FileMode, ObjectId};
21use crate::parallel::ThreadPolicy;
22use crate::repo::Repository;
23
24/// Rename pairing a pickaxe applies to added and deleted paths before matching them.
25#[derive(Debug, Clone, Copy)]
26pub(crate) struct PickaxeRenames<'a> {
27    /// Similarity percent, or `None` when renames are not detected.
28    threshold: Option<u32>,
29    /// Source of `diff.renameLimit` and rename-scoring thread settings.
30    config: &'a ConfigSet,
31}
32
33impl<'a> PickaxeRenames<'a> {
34    pub fn new(detection: RenameDetection, config: &'a ConfigSet) -> Self {
35        Self {
36            threshold: detection.threshold_percent(),
37            config,
38        }
39    }
40
41    /// Git's `log` default: `diff.renames` from `config`, at the default similarity.
42    pub fn from_config(config: &'a ConfigSet) -> Self {
43        Self::new(renames_from_config(config), config)
44    }
45
46    pub fn config(&self) -> &'a ConfigSet {
47        self.config
48    }
49}
50
51/// Which pickaxe mode is active (`-S` or `-G`).
52#[derive(Debug, Clone)]
53pub enum PickaxeKind {
54    /// Occurrence count change (`git log -S` / `git diff -S`).
55    Occurrences {
56        /// Needle string when not using [`Pickaxe::pickaxe_regex`].
57        needle: String,
58    },
59    /// Line-level regex on added/removed lines (`git log -G`).
60    LineGrep,
61}
62
63/// Compiled pickaxe filter for [`crate::rev_list::rev_list`].
64#[derive(Debug, Clone)]
65pub struct Pickaxe {
66    kind: PickaxeKind,
67    ignore_case: bool,
68    /// When true with [`PickaxeKind::Occurrences`], interpret the needle as ERE (`--pickaxe-regex`).
69    pickaxe_regex: bool,
70    /// POSIX extended regex (`REG_EXTENDED | REG_NEWLINE`) for `-G` and `-S --pickaxe-regex`.
71    ere: Option<PosixEre>,
72}
73
74impl Pickaxe {
75    /// `-S` / occurrence-count pickaxe (literal string unless [`Self::pickaxe_regex`]).
76    #[must_use]
77    pub fn occurrences(needle: impl Into<String>) -> Self {
78        Self {
79            kind: PickaxeKind::Occurrences {
80                needle: needle.into(),
81            },
82            ignore_case: false,
83            pickaxe_regex: false,
84            ere: None,
85        }
86    }
87
88    /// `-G` / line-level regex pickaxe (Git `REG_EXTENDED | REG_NEWLINE`).
89    ///
90    /// # Errors
91    ///
92    /// Returns [`PickaxeError::InvalidPattern`] when the pattern does not compile.
93    pub fn line_grep(pattern: &str, ignore_case: bool) -> std::result::Result<Self, PickaxeError> {
94        let ere = compile_pickaxe_ere(pattern, ignore_case)?;
95        Ok(Self {
96            kind: PickaxeKind::LineGrep,
97            ignore_case,
98            pickaxe_regex: false,
99            ere: Some(ere),
100        })
101    }
102
103    /// Case-insensitive matching (Git `-i` / `--regexp-ignore-case`).
104    #[must_use]
105    pub fn ignore_case(mut self, on: bool) -> Self {
106        self.ignore_case = on;
107        self
108    }
109
110    /// Treat `-S` needle as an ERE (`--pickaxe-regex`; only valid with occurrence mode).
111    #[must_use]
112    pub fn pickaxe_regex(mut self, on: bool) -> Self {
113        self.pickaxe_regex = on;
114        self
115    }
116
117    /// Finalize a pickaxe built with [`Self::occurrences`] (compiles ERE when requested).
118    ///
119    /// # Errors
120    ///
121    /// Returns [`PickaxeError::InvalidPattern`] when `--pickaxe-regex` is set and the needle
122    /// does not compile as ERE.
123    pub fn build(mut self) -> std::result::Result<Self, PickaxeError> {
124        if self.pickaxe_regex {
125            let PickaxeKind::Occurrences { ref needle } = self.kind else {
126                return Err(PickaxeError::InvalidPattern {
127                    pattern: String::new(),
128                    detail: "--pickaxe-regex cannot be used with -G".into(),
129                });
130            };
131            self.ere = Some(compile_pickaxe_ere(needle, self.ignore_case)?);
132        }
133        Ok(self)
134    }
135
136    /// Whether this filter requires per-commit tree diffs.
137    #[must_use]
138    pub fn is_active(&self) -> bool {
139        true
140    }
141
142    /// Shared handle for [`crate::rev_list::RevListOptions`].
143    #[must_use]
144    pub fn into_shared(self) -> Arc<Self> {
145        Arc::new(self)
146    }
147
148    /// Returns true when `commit` would be kept by `git log` with this pickaxe vs its first parent.
149    ///
150    /// Matches Git's order of work: the tree diff is limited to `paths` first, then deleted and
151    /// added paths are paired as renames per `renames`, and only then is each file pair tested.
152    /// A rename whose old and new file hold the same number of matches (`-S`), or whose diff
153    /// changes no matching line (`-G`), is therefore not a change. A file moved into the
154    /// pathspec from outside it is an addition, since its old path was never diffed.
155    ///
156    /// Merge commits are skipped (Git default without combined merge diffs). Non-merge commits
157    /// compare to the first parent only. Binary files are skipped for `-G`; `-S` searches binary
158    /// blobs.
159    ///
160    /// # Parameters
161    ///
162    /// - `paths` — repository-relative pathspecs limiting the diff; empty means the whole tree.
163    /// - `renames` — rename pairing; callers following Git use
164    ///   [`renames_from_config`] (`diff.renames`).
165    /// # Errors
166    ///
167    /// Propagates object read and diff errors.
168    pub fn matches_commit(
169        &self,
170        repo: &Repository,
171        commit_oid: ObjectId,
172        paths: &[String],
173        renames: RenameDetection,
174    ) -> Result<bool> {
175        let config = repo.config().snapshot()?;
176        let data = repo.odb().read(&commit_oid)?.data;
177        let commit = parse_commit(&data)?;
178        let parent_ctx = crate::shallow::EffectiveCommitParents::load(repo);
179        let effective_parents = parent_ctx.for_commit(commit_oid, &commit.parents);
180        if effective_parents.len() > 1 {
181            return Ok(false);
182        }
183        let parent_tree = if let Some(&parent_oid) = effective_parents.first() {
184            let parent_data = repo.odb().read(&parent_oid)?.data;
185            let parent = parse_commit(&parent_data)?;
186            if parent.tree == commit.tree {
187                return Ok(false);
188            }
189            Some(parent.tree)
190        } else {
191            None
192        };
193        let renames = PickaxeRenames::new(renames, config.as_ref());
194        self.matches_trees(
195            repo,
196            parent_tree.as_ref(),
197            &commit.tree,
198            paths,
199            renames,
200            &mut HashMap::new(),
201        )
202    }
203
204    /// Pickaxe match using pre-resolved parent and commit trees (avoids re-reading commits).
205    ///
206    /// `parent_tree` is `None` for root commits. Merge commits must be filtered out by the caller.
207    /// `blob_occurrence_cache` memoizes literal `-S` counts per blob across calls.
208    pub(crate) fn matches_trees(
209        &self,
210        repo: &Repository,
211        parent_tree: Option<&ObjectId>,
212        commit_tree: &ObjectId,
213        paths: &[String],
214        renames: PickaxeRenames<'_>,
215        blob_occurrence_cache: &mut HashMap<ObjectId, usize>,
216    ) -> Result<bool> {
217        let diff_options = crate::diff::DiffOptions::from_config(renames.config());
218        let odb = repo.odb();
219        let pathspec_matcher = if paths.is_empty() {
220            None
221        } else {
222            Some(repo.pathspec_matcher(paths)?)
223        };
224        let entries = diff_trees_for_pathspecs(
225            odb,
226            parent_tree,
227            Some(commit_tree),
228            paths,
229            pathspec_matcher.as_ref(),
230        )?;
231        // Rename pairing only ever combines an added path with a deleted one, so every other
232        // entry can be tested (and can end the search) before paying for it.
233        let mut unpaired = Vec::new();
234        for entry in entries {
235            if matches!(entry.status, DiffStatus::Added | DiffStatus::Deleted) {
236                unpaired.push(entry);
237            } else if self.changed_filepair_matches(
238                odb,
239                &entry,
240                &diff_options,
241                blob_occurrence_cache,
242            )? {
243                return Ok(true);
244            }
245        }
246        if unpaired.is_empty() {
247            return Ok(false);
248        }
249        // Any pair or lone side that matches has a side that matches on its own.
250        let mut any_side_matches = false;
251        for entry in &unpaired {
252            if self.side_may_match(odb, entry, blob_occurrence_cache)? {
253                any_side_matches = true;
254                break;
255            }
256        }
257        if !any_side_matches {
258            return Ok(false);
259        }
260        let pairs = match renames.threshold {
261            Some(threshold) => {
262                detect_renames_with_policy(
263                    odb,
264                    None,
265                    unpaired,
266                    threshold,
267                    renames.config,
268                    &ThreadPolicy::default(),
269                    None,
270                    DetectRenamesOptions::default(),
271                )?
272                .entries
273            }
274            None => unpaired,
275        };
276        for entry in &pairs {
277            if self.changed_filepair_matches(odb, entry, &diff_options, blob_occurrence_cache)? {
278                return Ok(true);
279            }
280        }
281        Ok(false)
282    }
283
284    fn changed_filepair_matches(
285        &self,
286        odb: &crate::odb::Odb,
287        entry: &DiffEntry,
288        diff_options: &crate::diff::DiffOptions,
289        blob_occurrence_cache: &mut HashMap<ObjectId, usize>,
290    ) -> Result<bool> {
291        if entry.old_oid == entry.new_oid && entry.old_mode == entry.new_mode {
292            return Ok(false);
293        }
294        self.filepair_matches(odb, entry, diff_options, blob_occurrence_cache)
295    }
296
297    /// Whether the one present side of an added or deleted `entry` holds a match by itself.
298    fn side_may_match(
299        &self,
300        odb: &crate::odb::Odb,
301        entry: &DiffEntry,
302        blob_occurrence_cache: &mut HashMap<ObjectId, usize>,
303    ) -> Result<bool> {
304        let (oid, mode) = if entry.status == DiffStatus::Deleted {
305            (&entry.old_oid, entry.old_mode)
306        } else {
307            (&entry.new_oid, entry.new_mode)
308        };
309        match &self.kind {
310            PickaxeKind::Occurrences { .. } => {
311                Ok(self.occurrences_in(odb, oid, mode, blob_occurrence_cache)? > 0)
312            }
313            PickaxeKind::LineGrep => {
314                let (bytes, binary) = blob_side(odb, mode, oid)?;
315                let Some(regex) = self.ere.as_ref().filter(|_| !binary) else {
316                    return Ok(false);
317                };
318                Ok(regex.is_match(&bytes.data))
319            }
320        }
321    }
322
323    fn filepair_matches(
324        &self,
325        odb: &crate::odb::Odb,
326        entry: &DiffEntry,
327        diff_options: &crate::diff::DiffOptions,
328        blob_occurrence_cache: &mut HashMap<ObjectId, usize>,
329    ) -> Result<bool> {
330        match &self.kind {
331            PickaxeKind::Occurrences { .. } => {
332                let old = self.occurrences_in(
333                    odb,
334                    &entry.old_oid,
335                    entry.old_mode,
336                    blob_occurrence_cache,
337                )?;
338                let new = self.occurrences_in(
339                    odb,
340                    &entry.new_oid,
341                    entry.new_mode,
342                    blob_occurrence_cache,
343                )?;
344                Ok(old != new)
345            }
346            PickaxeKind::LineGrep => {
347                let (old_bytes, old_bin) = blob_side(odb, entry.old_mode, &entry.old_oid)?;
348                let (new_bytes, new_bin) = blob_side(odb, entry.new_mode, &entry.new_oid)?;
349                if old_bin || new_bin {
350                    return Ok(false);
351                }
352                let Some(regex) = self.ere.as_ref() else {
353                    return Ok(false);
354                };
355                // Under REG_NEWLINE a match within one line is also a match within its whole
356                // blob, so a pair where neither side matches has no matching changed line.
357                if !regex.is_match(&old_bytes.data) && !regex.is_match(&new_bytes.data) {
358                    return Ok(false);
359                }
360                Ok(line_grep_match(
361                    &String::from_utf8_lossy(&old_bytes.data),
362                    &String::from_utf8_lossy(&new_bytes.data),
363                    regex,
364                    diff_options,
365                ))
366            }
367        }
368    }
369
370    /// `-S` match count in one side of a file pair, memoized per blob in `cache`.
371    ///
372    /// The cache is only valid for this pickaxe: counts depend on the needle and its flags.
373    fn occurrences_in(
374        &self,
375        odb: &crate::odb::Odb,
376        oid: &ObjectId,
377        mode: FileMode,
378        cache: &mut HashMap<ObjectId, usize>,
379    ) -> Result<usize> {
380        let PickaxeKind::Occurrences { needle } = &self.kind else {
381            return Ok(0);
382        };
383        if mode.is_absent() || *oid == ObjectId::zero() {
384            return Ok(0);
385        }
386        let count_in =
387            |bytes: &[u8]| count_occurrences(bytes, needle, self.ignore_case, self.ere.as_ref());
388        if mode == FileMode::GITLINK {
389            let (bytes, _) = blob_side(odb, mode, oid)?;
390            return Ok(count_in(bytes.data.as_slice()));
391        }
392        if let Some(&count) = cache.get(oid) {
393            return Ok(count);
394        }
395        let count = count_in(&odb.read(oid)?.data);
396        cache.insert(*oid, count);
397        Ok(count)
398    }
399}
400
401/// Invalid pickaxe pattern.
402#[derive(Debug, thiserror::Error)]
403#[non_exhaustive]
404pub enum PickaxeError {
405    /// Pattern compilation failed.
406    #[error("invalid pickaxe pattern `{pattern}`: {detail}")]
407    InvalidPattern {
408        /// Original pattern text.
409        pattern: String,
410        /// Underlying error message.
411        detail: String,
412    },
413}
414
415impl From<PickaxeError> for Error {
416    fn from(value: PickaxeError) -> Self {
417        Error::Diff(crate::error::DiffError::Pickaxe(value))
418    }
419}
420
421/// Git `regcomp(..., REG_EXTENDED | REG_NEWLINE)` for pickaxe patterns.
422fn compile_pickaxe_ere(
423    pattern: &str,
424    ignore_case: bool,
425) -> std::result::Result<PosixEre, PickaxeError> {
426    PosixEre::compile(pattern, ignore_case).map_err(|detail| PickaxeError::InvalidPattern {
427        pattern: pattern.to_owned(),
428        detail,
429    })
430}
431
432fn count_occurrences(
433    haystack: &[u8],
434    needle: &str,
435    ignore_case: bool,
436    ere: Option<&PosixEre>,
437) -> usize {
438    if haystack.is_empty() {
439        return 0;
440    }
441    if let Some(re) = ere {
442        return re.count_nonoverlapping(haystack);
443    }
444    if ignore_case {
445        let h = String::from_utf8_lossy(haystack).to_lowercase();
446        let n = needle.to_lowercase();
447        return count_substr(h.as_bytes(), n.as_bytes());
448    }
449    count_substr(haystack, needle.as_bytes())
450}
451
452fn count_substr(haystack: &[u8], needle: &[u8]) -> usize {
453    if needle.is_empty() {
454        return 0;
455    }
456    memchr::memmem::find_iter(haystack, needle).count()
457}
458
459fn blob_side(odb: &crate::odb::Odb, mode: FileMode, oid: &ObjectId) -> Result<(SideBytes, bool)> {
460    if mode == FileMode::GITLINK {
461        let line = if *oid == ObjectId::zero() {
462            String::new()
463        } else {
464            format!("Subproject commit {}\n", oid.to_hex())
465        };
466        return Ok((SideBytes::from_bytes(line.into_bytes()), false));
467    }
468    if mode.is_absent() || *oid == ObjectId::zero() {
469        return Ok((SideBytes::from_bytes(Vec::new()), false));
470    }
471    let data = odb.read(oid)?.data;
472    let binary = data.iter().take(8000).any(|&b| b == 0);
473    Ok((SideBytes::from_bytes(data), binary))
474}
475
476fn line_grep_match(
477    old_text: &str,
478    new_text: &str,
479    regex: &PosixEre,
480    diff_options: &crate::diff::DiffOptions,
481) -> bool {
482    use crate::diff::core::compacted_line_ops_for_options;
483    use crate::diff::unified_emit::LineSide;
484    use similar::DiffOp;
485
486    let before = LineSide::from_text(old_text);
487    let after = LineSide::from_text(new_text);
488    let old_lines: Vec<&str> = before.lines().map(|l| l.body).collect();
489    let new_lines: Vec<&str> = after.lines().map(|l| l.body).collect();
490    for op in compacted_line_ops_for_options(old_text, new_text, diff_options) {
491        match op {
492            DiffOp::Equal { .. } => {}
493            DiffOp::Delete {
494                old_index, old_len, ..
495            } => {
496                for line in &old_lines[old_index..old_index + old_len] {
497                    if regex.is_match(line.as_bytes()) {
498                        return true;
499                    }
500                }
501            }
502            DiffOp::Insert {
503                new_index, new_len, ..
504            } => {
505                for line in &new_lines[new_index..new_index + new_len] {
506                    if regex.is_match(line.as_bytes()) {
507                        return true;
508                    }
509                }
510            }
511            DiffOp::Replace {
512                old_index,
513                old_len,
514                new_index,
515                new_len,
516                ..
517            } => {
518                for line in &old_lines[old_index..old_index + old_len] {
519                    if regex.is_match(line.as_bytes()) {
520                        return true;
521                    }
522                }
523                for line in &new_lines[new_index..new_index + new_len] {
524                    if regex.is_match(line.as_bytes()) {
525                        return true;
526                    }
527                }
528            }
529        }
530    }
531    false
532}
533
534#[cfg(test)]
535mod tests {
536    use super::*;
537
538    #[test]
539    fn literal_counts_do_not_overlap() {
540        assert_eq!(count_occurrences(b"aaaa", "aa", false, None), 2);
541        assert_eq!(count_occurrences(b"aaa", "aa", false, None), 1);
542        assert_eq!(count_occurrences(b"abcabc", "abc", false, None), 2);
543        assert_eq!(count_occurrences(b"abc", "", false, None), 0);
544        assert_eq!(count_occurrences(b"", "a", false, None), 0);
545    }
546
547    #[test]
548    fn ignore_case_counts_fold_both_sides() {
549        assert_eq!(count_occurrences(b"Needle NEEDLE", "needle", true, None), 2);
550        assert_eq!(
551            count_occurrences(b"Needle NEEDLE", "needle", false, None),
552            0
553        );
554    }
555}