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::diff::posix_ere::PosixEre;
12use crate::diff::structured::SideBytes;
13use crate::diff::{diff_trees, DiffEntry};
14use crate::error::{Error, Result};
15use crate::objects::{parse_commit, ObjectId};
16use crate::pathspec::matches_pathspec_list;
17use crate::repo::Repository;
18
19/// Which pickaxe mode is active (`-S` or `-G`).
20#[derive(Debug, Clone)]
21pub enum PickaxeKind {
22    /// Occurrence count change (`git log -S` / `git diff -S`).
23    Occurrences {
24        /// Needle string when not using [`Pickaxe::pickaxe_regex`].
25        needle: String,
26    },
27    /// Line-level regex on added/removed lines (`git log -G`).
28    LineGrep,
29}
30
31/// Compiled pickaxe filter for [`crate::rev_list::rev_list`].
32#[derive(Debug, Clone)]
33pub struct Pickaxe {
34    kind: PickaxeKind,
35    ignore_case: bool,
36    /// When true with [`PickaxeKind::Occurrences`], interpret the needle as ERE (`--pickaxe-regex`).
37    pickaxe_regex: bool,
38    /// POSIX extended regex (`REG_EXTENDED | REG_NEWLINE`) for `-G` and `-S --pickaxe-regex`.
39    ere: Option<PosixEre>,
40}
41
42impl Pickaxe {
43    /// `-S` / occurrence-count pickaxe (literal string unless [`Self::pickaxe_regex`]).
44    #[must_use]
45    pub fn occurrences(needle: impl Into<String>) -> Self {
46        Self {
47            kind: PickaxeKind::Occurrences {
48                needle: needle.into(),
49            },
50            ignore_case: false,
51            pickaxe_regex: false,
52            ere: None,
53        }
54    }
55
56    /// `-G` / line-level regex pickaxe (Git `REG_EXTENDED | REG_NEWLINE`).
57    ///
58    /// # Errors
59    ///
60    /// Returns [`PickaxeError::InvalidPattern`] when the pattern does not compile.
61    pub fn line_grep(pattern: &str, ignore_case: bool) -> std::result::Result<Self, PickaxeError> {
62        let ere = compile_pickaxe_ere(pattern, ignore_case)?;
63        Ok(Self {
64            kind: PickaxeKind::LineGrep,
65            ignore_case,
66            pickaxe_regex: false,
67            ere: Some(ere),
68        })
69    }
70
71    /// Case-insensitive matching (Git `-i` / `--regexp-ignore-case`).
72    #[must_use]
73    pub fn ignore_case(mut self, on: bool) -> Self {
74        self.ignore_case = on;
75        self
76    }
77
78    /// Treat `-S` needle as an ERE (`--pickaxe-regex`; only valid with occurrence mode).
79    #[must_use]
80    pub fn pickaxe_regex(mut self, on: bool) -> Self {
81        self.pickaxe_regex = on;
82        self
83    }
84
85    /// Finalize a pickaxe built with [`Self::occurrences`] (compiles ERE when requested).
86    ///
87    /// # Errors
88    ///
89    /// Returns [`PickaxeError::InvalidPattern`] when `--pickaxe-regex` is set and the needle
90    /// does not compile as ERE.
91    pub fn build(mut self) -> std::result::Result<Self, PickaxeError> {
92        if self.pickaxe_regex {
93            let PickaxeKind::Occurrences { ref needle } = self.kind else {
94                return Err(PickaxeError::InvalidPattern {
95                    pattern: String::new(),
96                    detail: "--pickaxe-regex cannot be used with -G".into(),
97                });
98            };
99            self.ere = Some(compile_pickaxe_ere(needle, self.ignore_case)?);
100        }
101        Ok(self)
102    }
103
104    /// Whether this filter requires per-commit tree diffs.
105    #[must_use]
106    pub fn is_active(&self) -> bool {
107        true
108    }
109
110    /// Shared handle for [`crate::rev_list::RevListOptions`].
111    #[must_use]
112    pub fn into_shared(self) -> Arc<Self> {
113        Arc::new(self)
114    }
115
116    /// Returns true when `commit` would be kept by `git log` with this pickaxe vs its first parent.
117    ///
118    /// Merge commits are skipped (Git default without combined merge diffs). Non-merge commits
119    /// compare to the first parent only. Pathspecs limit which tree entries are considered.
120    /// Binary files are skipped for `-G`; `-S` searches binary blobs.
121    ///
122    /// # Errors
123    ///
124    /// Propagates object read and diff errors.
125    pub fn matches_commit(
126        &self,
127        repo: &Repository,
128        commit_oid: ObjectId,
129        paths: &[String],
130    ) -> Result<bool> {
131        let data = repo.odb().read(&commit_oid)?.data;
132        let commit = parse_commit(&data)?;
133        if commit.parents.len() > 1 {
134            return Ok(false);
135        }
136        let parent_tree = if let Some(&parent_oid) = commit.parents.first() {
137            let parent_data = repo.odb().read(&parent_oid)?.data;
138            let parent = parse_commit(&parent_data)?;
139            if parent.tree == commit.tree {
140                return Ok(false);
141            }
142            Some(parent.tree)
143        } else {
144            None
145        };
146        self.matches_trees(repo, parent_tree.as_ref(), &commit.tree, paths, None)
147    }
148
149    /// Pickaxe match using pre-resolved parent and commit trees (avoids re-reading commits).
150    ///
151    /// `parent_tree` is `None` for root commits. Merge commits must be filtered out by the caller.
152    pub(crate) fn matches_trees(
153        &self,
154        repo: &Repository,
155        parent_tree: Option<&ObjectId>,
156        commit_tree: &ObjectId,
157        paths: &[String],
158        mut blob_occurrence_cache: Option<&mut HashMap<ObjectId, usize>>,
159    ) -> Result<bool> {
160        let entries = diff_trees(repo.odb(), parent_tree, Some(commit_tree), "")?;
161        let odb = repo.odb();
162        for entry in entries {
163            if !entry_matches_pathspecs(&entry, paths) {
164                continue;
165            }
166            if entry.old_oid == entry.new_oid && entry.old_mode == entry.new_mode {
167                continue;
168            }
169            if self.filepair_matches(odb, &entry, &mut blob_occurrence_cache)? {
170                return Ok(true);
171            }
172        }
173        Ok(false)
174    }
175
176    fn filepair_matches(
177        &self,
178        odb: &crate::odb::Odb,
179        entry: &DiffEntry,
180        blob_occurrence_cache: &mut Option<&mut HashMap<ObjectId, usize>>,
181    ) -> Result<bool> {
182        match &self.kind {
183            PickaxeKind::Occurrences { needle } => {
184                let c1 = blob_occurrence_count(
185                    odb,
186                    &entry.old_oid,
187                    entry.old_mode.as_str(),
188                    needle,
189                    self.ignore_case,
190                    self.ere.as_ref(),
191                    blob_occurrence_cache.as_deref_mut(),
192                )?;
193                let c2 = blob_occurrence_count(
194                    odb,
195                    &entry.new_oid,
196                    entry.new_mode.as_str(),
197                    needle,
198                    self.ignore_case,
199                    self.ere.as_ref(),
200                    blob_occurrence_cache.as_deref_mut(),
201                )?;
202                Ok(c1 != c2)
203            }
204            PickaxeKind::LineGrep => {
205                let (old_bytes, old_bin) = blob_side(odb, entry.old_mode.as_str(), &entry.old_oid)?;
206                let (new_bytes, new_bin) = blob_side(odb, entry.new_mode.as_str(), &entry.new_oid)?;
207                if old_bin || new_bin {
208                    return Ok(false);
209                }
210                let Some(regex) = self.ere.as_ref() else {
211                    return Ok(false);
212                };
213                Ok(line_grep_match(
214                    old_bytes.text().as_str(),
215                    new_bytes.text().as_str(),
216                    regex,
217                ))
218            }
219        }
220    }
221}
222
223fn blob_occurrence_count(
224    odb: &crate::odb::Odb,
225    oid: &ObjectId,
226    mode: &str,
227    needle: &str,
228    ignore_case: bool,
229    ere: Option<&PosixEre>,
230    cache: Option<&mut HashMap<ObjectId, usize>>,
231) -> Result<usize> {
232    if mode == "000000" || *oid == ObjectId::zero() {
233        return Ok(0);
234    }
235    if mode == "160000" {
236        let (bytes, _) = blob_side(odb, mode, oid)?;
237        return Ok(count_occurrences(
238            bytes.data.as_slice(),
239            needle,
240            ignore_case,
241            ere,
242        ));
243    }
244    if let Some(cache) = cache {
245        if ere.is_none() && !ignore_case {
246            if let Some(&count) = cache.get(oid) {
247                return Ok(count);
248            }
249            let data = odb.read(oid)?.data;
250            let count = count_occurrences(&data, needle, false, None);
251            cache.insert(*oid, count);
252            return Ok(count);
253        }
254    }
255    let (bytes, _) = blob_side(odb, mode, oid)?;
256    Ok(count_occurrences(
257        bytes.data.as_slice(),
258        needle,
259        ignore_case,
260        ere,
261    ))
262}
263
264/// Invalid pickaxe pattern.
265#[derive(Debug, thiserror::Error)]
266pub enum PickaxeError {
267    /// Pattern compilation failed.
268    #[error("invalid pickaxe pattern `{pattern}`: {detail}")]
269    InvalidPattern {
270        /// Original pattern text.
271        pattern: String,
272        /// Underlying error message.
273        detail: String,
274    },
275}
276
277impl From<PickaxeError> for Error {
278    fn from(value: PickaxeError) -> Self {
279        match value {
280            PickaxeError::InvalidPattern { pattern, detail } => {
281                Error::Message(format!("invalid pickaxe pattern `{pattern}`: {detail}"))
282            }
283        }
284    }
285}
286
287/// Git `regcomp(..., REG_EXTENDED | REG_NEWLINE)` for pickaxe patterns.
288fn compile_pickaxe_ere(
289    pattern: &str,
290    ignore_case: bool,
291) -> std::result::Result<PosixEre, PickaxeError> {
292    PosixEre::compile(pattern, ignore_case).map_err(|detail| PickaxeError::InvalidPattern {
293        pattern: pattern.to_owned(),
294        detail,
295    })
296}
297
298fn entry_matches_pathspecs(entry: &DiffEntry, paths: &[String]) -> bool {
299    if paths.is_empty() {
300        return true;
301    }
302    let path = entry.path();
303    if path.is_empty() {
304        return false;
305    }
306    matches_pathspec_list(path, paths)
307}
308
309fn count_occurrences(
310    haystack: &[u8],
311    needle: &str,
312    ignore_case: bool,
313    ere: Option<&PosixEre>,
314) -> usize {
315    if haystack.is_empty() {
316        return 0;
317    }
318    if let Some(re) = ere {
319        return re.count_nonoverlapping(haystack);
320    }
321    if ignore_case {
322        let h = String::from_utf8_lossy(haystack).to_lowercase();
323        let n = needle.to_lowercase();
324        return count_substr(h.as_bytes(), n.as_bytes());
325    }
326    count_substr(haystack, needle.as_bytes())
327}
328
329fn count_substr(haystack: &[u8], needle: &[u8]) -> usize {
330    if needle.is_empty() {
331        return 0;
332    }
333    let mut count = 0usize;
334    let mut start = 0usize;
335    while start + needle.len() <= haystack.len() {
336        if haystack[start..].starts_with(needle) {
337            count += 1;
338            start += needle.len();
339        } else {
340            start += 1;
341        }
342    }
343    count
344}
345
346fn blob_side(odb: &crate::odb::Odb, mode: &str, oid: &ObjectId) -> Result<(SideBytes, bool)> {
347    if mode == "160000" {
348        let line = if *oid == ObjectId::zero() {
349            String::new()
350        } else {
351            format!("Subproject commit {}\n", oid.to_hex())
352        };
353        return Ok((SideBytes::from_bytes(line.into_bytes()), false));
354    }
355    if mode == "000000" || *oid == ObjectId::zero() {
356        return Ok((SideBytes::from_bytes(Vec::new()), false));
357    }
358    let data = odb.read(oid)?.data;
359    let binary = data.iter().take(8000).any(|&b| b == 0);
360    Ok((SideBytes::from_bytes(data), binary))
361}
362
363fn line_grep_match(old_text: &str, new_text: &str, regex: &PosixEre) -> bool {
364    use similar::{ChangeTag, TextDiff};
365    let diff = TextDiff::from_lines(old_text, new_text);
366    for change in diff.iter_all_changes() {
367        let line = change.value();
368        let check = match change.tag() {
369            ChangeTag::Delete | ChangeTag::Insert => line.as_bytes(),
370            ChangeTag::Equal => continue,
371        };
372        if regex.is_match(check) {
373            return true;
374        }
375    }
376    false
377}
grit_lib/diff/pickaxe.rs

grit_lib/diff/
pickaxe.rs
