Skip to main content

grit_lib/refs/
listing.rs

1//! Shared ref listing: namespace selection, glob patterns, sort keys, and limits.
2//!
3//! Used by branch/tag list, `for-each-ref`-style queries, and in-memory remote ref
4//! lists.
5//!
6//! - **Local lists** (`query_refs`, `query_listings_from_pairs`): patterns follow
7//!   `git for-each-ref` / `git branch --list` on the **short** ref name (suffix after
8//!   `refs/heads/`, `refs/tags/`, etc.), and a trailing `/` selects a directory prefix.
9//! - **Remote advertisements** ([`pattern_matches_ls_remote_pattern`]): patterns follow
10//!   `git ls-remote` tail-match rules on the **full** ref name (`main` matches
11//!   `refs/heads/main`; `refs/tags/v1*` also matches `refs/tags/v1^{}`).
12//!
13//! ```rust
14//! use grit_lib::refs::listing::{RefNamespace, RefQuery, RefQueryOptions, SortKey};
15//! use grit_lib::repo::{InitOptions, Repository};
16//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
17//! let dir = tempfile::tempdir()?;
18//! let (repo, _) = Repository::init(dir.path(), &InitOptions::default())?;
19//! let query = RefQuery {
20//!     namespaces: vec![RefNamespace::Heads],
21//!     ..RefQuery::default()
22//! };
23//! let _branches = repo.references().query(&query, &RefQueryOptions::default())?;
24//! # Ok(())
25//! # }
26//! ```
27
28use std::cmp::Ordering;
29use std::collections::BTreeMap;
30use std::ops::ControlFlow;
31
32use crate::ident::committer_unix_seconds_for_ordering_bytes;
33use crate::objects::{ObjectId, ObjectKind};
34use crate::odb::Odb;
35use crate::refs::query_reachability::{self, ReachRow};
36use crate::refs::store::{RefEntry, RefNameRef, RefStore};
37use crate::refs::version_sort::compare_refname_versions;
38use crate::refs::PackedRefPeels;
39use crate::repo::Repository;
40use crate::wildmatch::{wildmatch, WM_CASEFOLD};
41
42/// Which ref namespace to include in a [`RefQuery`].
43#[derive(Debug, Clone, PartialEq, Eq)]
44pub enum RefNamespace {
45    /// `refs/heads/*`
46    Heads,
47    /// `refs/remotes/*`
48    Remotes,
49    /// `refs/tags/*`
50    Tags,
51    /// Any ref whose full name starts with this prefix (for example `refs/notes/`).
52    Custom(String),
53}
54
55impl RefNamespace {
56    fn prefix(&self) -> &str {
57        match self {
58            Self::Heads => "refs/heads/",
59            Self::Remotes => "refs/remotes/",
60            Self::Tags => "refs/tags/",
61            Self::Custom(p) => p.as_str(),
62        }
63    }
64}
65
66/// Primary sort key for [`RefQuery`].
67#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
68pub enum SortKey {
69    /// Full ref name (`refname`), byte order.
70    #[default]
71    Name,
72    /// `version:refname` — [`compare_version_names`] on the full ref name, then refname tie-break.
73    Version,
74    /// `creatordate` — tagger or committer epoch from object headers.
75    Date,
76}
77
78/// Sort direction and key for ref listing.
79#[derive(Debug, Clone, Copy, PartialEq, Eq)]
80pub struct RefSort {
81    /// Which field to sort by.
82    pub key: SortKey,
83    /// When true, reverse the primary ordering (Git `--reverse` / leading `-` on `--sort`).
84    pub reverse: bool,
85}
86
87impl Default for RefSort {
88    fn default() -> Self {
89        Self {
90            key: SortKey::Name,
91            reverse: false,
92        }
93    }
94}
95
96/// Filters and ordering for a ref listing query.
97#[derive(Debug, Clone, PartialEq, Eq, Default)]
98pub struct RefQuery {
99    /// Namespaces to scan (union). When empty, defaults to [`RefNamespace::Heads`].
100    pub namespaces: Vec<RefNamespace>,
101    /// Glob patterns matched against the short ref name; empty means no pattern filter.
102    pub patterns: Vec<String>,
103    /// Sort key and direction.
104    pub sort: RefSort,
105    /// Maximum number of refs to return after sorting (`None` = unlimited).
106    pub limit: Option<usize>,
107    /// Keep refs whose peeled commit contains every listed commit (`--contains`).
108    pub contains: Vec<ObjectId>,
109    /// Exclude refs whose peeled commit contains any listed commit (`--no-contains`).
110    pub no_contains: Vec<ObjectId>,
111    /// Keep branch tips merged into every listed commit (`--merged`).
112    pub merged: Vec<ObjectId>,
113    /// Exclude branch tips merged into any listed commit (`--no-merged`).
114    pub no_merged: Vec<ObjectId>,
115    /// Keep refs whose oid or tag peel chain matches any listed object (`--points-at`).
116    pub points_at: Vec<ObjectId>,
117}
118
119/// Class of ref for display and JSON (`head`, `remote`, `tag`, …).
120#[derive(Debug, Clone, Copy, PartialEq, Eq)]
121pub enum RefKind {
122    /// Local branch (`refs/heads/`).
123    Head,
124    /// Remote-tracking branch (`refs/remotes/`).
125    Remote,
126    /// Tag (`refs/tags/`).
127    Tag,
128    /// Any other ref namespace.
129    Other,
130}
131
132/// One ref returned from [`References::query`](super::handle::References::query) or
133/// [`query_listings_from_pairs`].
134#[derive(Debug, Clone, PartialEq, Eq)]
135pub struct RefListing {
136    /// Full ref name (for example `refs/tags/v1.0`).
137    pub full_name: String,
138    /// Short name within its namespace (for example `v1.0` for tags).
139    pub short_name: String,
140    /// Object id stored at the ref (annotated tag object id for annotated tags).
141    pub oid: ObjectId,
142    /// Peeled object id when the ref store or ODB provides one (often a commit).
143    pub peeled: Option<ObjectId>,
144    /// Ref classification derived from `full_name`.
145    pub kind: RefKind,
146}
147
148/// Extra inputs for pattern matching and version sort (explicit config, no env reads).
149#[derive(Debug, Clone, Default)]
150pub struct RefQueryOptions {
151    /// `versionsort.suffix` values in priority order (Git multi-valued config).
152    pub versionsort_suffixes: Vec<String>,
153    /// When true, patterns use [`WM_CASEFOLD`] like `core.ignorecase`.
154    pub ignore_case: bool,
155}
156
157type QueryResult<T> = crate::error::Result<T>;
158
159#[derive(Clone)]
160struct CollectedRef {
161    full_name: String,
162    short_name: String,
163    oid: ObjectId,
164    peeled: Option<ObjectId>,
165    kind: RefKind,
166    creator_date: i64,
167}
168
169/// Classify `full_name` into a [`RefKind`].
170#[must_use]
171pub fn ref_kind_from_name(full_name: &str) -> RefKind {
172    if full_name.starts_with("refs/heads/") {
173        RefKind::Head
174    } else if full_name.starts_with("refs/remotes/") {
175        RefKind::Remote
176    } else if full_name.starts_with("refs/tags/") {
177        RefKind::Tag
178    } else {
179        RefKind::Other
180    }
181}
182
183/// Strip the namespace prefix for `full_name` given the query namespace used to collect it.
184#[must_use]
185pub fn short_name_in_namespace(full_name: &str, namespace: &RefNamespace) -> String {
186    let prefix = namespace.prefix();
187    full_name
188        .strip_prefix(prefix)
189        .unwrap_or(full_name)
190        .to_owned()
191}
192
193/// Whether `full_ref_name` matches `pattern` using `git ls-remote` tail-match rules.
194#[must_use]
195pub fn pattern_matches_ls_remote_pattern(full_ref_name: &str, pattern: &str) -> bool {
196    if pattern.is_empty() {
197        return false;
198    }
199    let path = format!("/{full_ref_name}");
200    let full = format!("*/{pattern}");
201    ls_remote_glob_match(&full, &path)
202}
203
204/// Returns `true` when `full_ref_name` matches one of `patterns`.
205///
206/// An empty `patterns` slice means no pattern filter (all ref names pass). An explicit
207/// empty-string pattern (`patterns == [""]`) matches nothing, like `git ls-remote`.
208#[must_use]
209pub fn patterns_match_ls_remote(full_ref_name: &str, patterns: &[String]) -> bool {
210    if patterns.is_empty() {
211        return true;
212    }
213    patterns
214        .iter()
215        .any(|p| pattern_matches_ls_remote_pattern(full_ref_name, p))
216}
217
218fn ls_remote_glob_match(pattern: &str, text: &str) -> bool {
219    let pat: Vec<char> = pattern.chars().collect();
220    let txt: Vec<char> = text.chars().collect();
221    let (mut pi, mut ti) = (0, 0);
222    let (mut star_pi, mut star_ti) = (usize::MAX, 0);
223    while ti < txt.len() {
224        if pi < pat.len() && (pat[pi] == '?' || pat[pi] == txt[ti]) {
225            pi += 1;
226            ti += 1;
227        } else if pi < pat.len() && pat[pi] == '*' {
228            star_pi = pi;
229            star_ti = ti;
230            pi += 1;
231        } else if star_pi != usize::MAX {
232            pi = star_pi + 1;
233            star_ti += 1;
234            ti = star_ti;
235        } else {
236            return false;
237        }
238    }
239    while pi < pat.len() && pat[pi] == '*' {
240        pi += 1;
241    }
242    pi == pat.len()
243}
244
245/// Whether `short_name` matches `pattern` (Git `for-each-ref` / branch list rules).
246#[must_use]
247pub fn pattern_matches_short_name(short_name: &str, pattern: &str, ignore_case: bool) -> bool {
248    if pattern.is_empty() {
249        return true;
250    }
251    let mut flags = 0u32;
252    if ignore_case {
253        flags |= WM_CASEFOLD;
254    }
255
256    if pattern.ends_with('/') {
257        let base = pattern.trim_end_matches('/');
258        if ascii_eq(short_name, base, ignore_case)
259            || ascii_starts_with(short_name, pattern, ignore_case)
260        {
261            return true;
262        }
263    }
264
265    if wildmatch(pattern.as_bytes(), short_name.as_bytes(), flags) {
266        return true;
267    }
268
269    // Literal prefix without glob metacharacters (Git `match_name_as_path` on short names).
270    if !pattern.contains(['*', '?', '[', '\\']) {
271        if ascii_eq(short_name, pattern, ignore_case) {
272            return true;
273        }
274        if ascii_starts_with_path_segment(short_name, pattern, ignore_case) {
275            return true;
276        }
277    }
278    false
279}
280
281fn ascii_eq(left: &str, right: &str, ignore_case: bool) -> bool {
282    ascii_eq_bytes(left.as_bytes(), right.as_bytes(), ignore_case)
283}
284
285fn ascii_eq_bytes(left: &[u8], right: &[u8], ignore_case: bool) -> bool {
286    if !ignore_case {
287        return left == right;
288    }
289    left.len() == right.len()
290        && left
291            .iter()
292            .zip(right.iter())
293            .all(|(a, b)| a.eq_ignore_ascii_case(b))
294}
295
296fn ascii_starts_with(name: &str, prefix: &str, ignore_case: bool) -> bool {
297    ascii_starts_with_bytes(name.as_bytes(), prefix.as_bytes(), ignore_case)
298}
299
300fn ascii_starts_with_bytes(name: &[u8], prefix: &[u8], ignore_case: bool) -> bool {
301    if name.len() < prefix.len() {
302        return false;
303    }
304    if !ignore_case {
305        return name.starts_with(prefix);
306    }
307    name[..prefix.len()]
308        .iter()
309        .zip(prefix.iter())
310        .all(|(a, b)| a.eq_ignore_ascii_case(b))
311}
312
313fn ascii_starts_with_path_segment(name: &str, pattern: &str, ignore_case: bool) -> bool {
314    let name = name.as_bytes();
315    let pattern = pattern.as_bytes();
316    if name.len() < pattern.len() + 1 || name[pattern.len()] != b'/' {
317        return false;
318    }
319    ascii_starts_with_bytes(name, pattern, ignore_case)
320}
321
322/// Compare two ref names using Git's `version:refname` / `versioncmp` ordering.
323///
324/// `versionsort_suffixes` is the configured `versionsort.suffix` list (may be empty).
325#[must_use]
326pub fn compare_version_names(a: &str, b: &str, versionsort_suffixes: &[String]) -> Ordering {
327    compare_refname_versions(a, b, versionsort_suffixes)
328}
329
330/// Extract the epoch from a Git identity line (`Name <email> <epoch> <tz>`).
331#[must_use]
332pub fn epoch_from_identity(ident: &str) -> i64 {
333    let parts: Vec<&str> = ident.rsplitn(3, ' ').collect();
334    if parts.len() >= 2 {
335        parts[1].parse().unwrap_or(0)
336    } else {
337        0
338    }
339}
340
341/// Creator date for a ref target: tagger date for tag objects, committer date for commits.
342///
343/// Reads only the object header region (stops at the first blank line). Returns `0` when
344/// unknown.
345#[must_use]
346pub fn creator_date_from_bytes(kind: ObjectKind, data: &[u8]) -> i64 {
347    let header = object_header_bytes(data);
348    match kind {
349        ObjectKind::Tag => {
350            if let Some(line) = find_header_value(header, b"tagger") {
351                committer_unix_seconds_for_ordering_bytes(line)
352            } else {
353                0
354            }
355        }
356        ObjectKind::Commit => {
357            if let Some(line) = find_header_value(header, b"committer") {
358                committer_unix_seconds_for_ordering_bytes(line)
359            } else {
360                0
361            }
362        }
363        _ => 0,
364    }
365}
366
367/// Creator date for `oid` in `odb` (see [`creator_date_from_bytes`]).
368///
369/// # Errors
370///
371/// Propagates object read failures.
372pub fn creator_date(odb: &Odb, oid: &ObjectId) -> crate::error::Result<i64> {
373    let obj = odb.read(oid)?;
374    Ok(creator_date_from_bytes(obj.kind, &obj.data))
375}
376
377/// Run `query` over an in-memory iterator of `(full_name, oid)` pairs.
378///
379/// `peeled` is optional per entry; pass `None` when unknown. For creator-date sort,
380/// `odb` must be `Some`.
381///
382/// # Errors
383///
384/// Returns [`RefError::QueryNeedsObjectDatabase`](crate::error::RefError::QueryNeedsObjectDatabase)
385/// when sort key is [`SortKey::Date`] and `odb` is `None`, and propagates ref store and object
386/// read errors.
387pub fn query_listings_from_pairs<I>(
388    entries: I,
389    query: &RefQuery,
390    options: &RefQueryOptions,
391    odb: Option<&Odb>,
392) -> QueryResult<Vec<RefListing>>
393where
394    I: IntoIterator<Item = (String, ObjectId, Option<ObjectId>)>,
395{
396    let namespaces = effective_namespaces(query);
397    let mut collected = BTreeMap::new();
398    for (full_name, oid, peeled) in entries {
399        if !namespaces
400            .iter()
401            .any(|ns| full_name.starts_with(ns.prefix()))
402        {
403            continue;
404        }
405        let short_name = short_name_for_query(&full_name, &namespaces);
406        if !patterns_match(&short_name, &query.patterns, options.ignore_case) {
407            continue;
408        }
409        let kind = ref_kind_from_name(&full_name);
410        collected.entry(full_name.clone()).or_insert(CollectedRef {
411            full_name,
412            short_name,
413            oid,
414            peeled,
415            kind,
416            creator_date: 0,
417        });
418    }
419    finish_query(
420        collected.into_values().collect(),
421        query,
422        options,
423        odb,
424        None,
425        PeelTips::Always,
426    )
427}
428
429/// Collect refs from `store` under each namespace in `query`, then filter, sort, and limit.
430///
431/// # Errors
432///
433/// Propagates ref-store and object-read failures.
434pub fn query_listings_on_store(
435    store: &dyn RefStore,
436    query: &RefQuery,
437    options: &RefQueryOptions,
438    odb: Option<&Odb>,
439) -> QueryResult<Vec<RefListing>> {
440    let namespaces = effective_namespaces(query);
441    let mut collected = Vec::new();
442    for ns in &namespaces {
443        let prefix = ns.prefix();
444        store.for_each_ref(prefix, &mut |entry: &RefEntry| {
445            insert_collected_ref(&mut collected, entry, store, &namespaces, query, options);
446            ControlFlow::Continue(())
447        })?;
448    }
449    finish_query(
450        dedup_collected(collected),
451        query,
452        options,
453        odb,
454        None,
455        PeelTips::Always,
456    )
457}
458
459/// Whether [`finish_query`] fills [`RefListing::peeled`] for refs the store did not peel.
460#[derive(Debug, Clone, Copy, PartialEq, Eq)]
461pub(crate) enum PeelTips {
462    /// Peel every listed ref (reads each tip's object header unless `packed-refs` says).
463    Always,
464    /// Peel only when a reachability or `points_at` filter needs it; otherwise listings carry
465    /// whatever peel the ref store reported.
466    WhenFiltering,
467}
468
469/// Query refs on `repo` (respects linked-worktree visibility and injected ref stores).
470///
471/// Finite, name-ordered `contains` queries without other reachability or object filters
472/// evaluate tips in result order and stop after `limit` matches. Ancestry results are
473/// shared across evaluated tips. Targets are validated even when the limit is zero.
474/// Unlimited queries, other sorts, and combined filters use a shared batch walk.
475///
476/// # Errors
477///
478/// Propagates ref-store and object-read failures.
479pub(crate) fn query_refs(
480    repo: &Repository,
481    query: &RefQuery,
482    options: &RefQueryOptions,
483) -> QueryResult<Vec<RefListing>> {
484    query_refs_peeling(repo, query, options, PeelTips::Always)
485}
486
487/// [`query_refs`] for callers that do not read [`RefListing::peeled`], which spares an
488/// object read per listed ref when no filter needs peeled tips.
489///
490/// # Errors
491///
492/// Same as [`query_refs`].
493pub(crate) fn query_refs_peeling(
494    repo: &Repository,
495    query: &RefQuery,
496    options: &RefQueryOptions,
497    peel: PeelTips,
498) -> QueryResult<Vec<RefListing>> {
499    let git_dir = repo.git_dir();
500    let store = repo.ref_store();
501    let namespaces = effective_namespaces(query);
502    let linked_worktree = crate::worktree_ref::is_linked_worktree_git_dir(git_dir);
503    let early_limit = early_ref_collection_limit(query, options);
504    let mut collected = Vec::new();
505    for ns in &namespaces {
506        let prefix = ns.prefix();
507        store.for_each_ref(prefix, &mut |entry: &RefEntry| {
508            if linked_worktree
509                && !crate::worktree_ref::ref_visible_from_worktree(git_dir, entry.name.as_str())
510            {
511                return ControlFlow::Continue(());
512            }
513            insert_collected_ref(&mut collected, entry, store, &namespaces, query, options);
514            if early_limit.is_some_and(|limit| collected.len() >= limit) {
515                return ControlFlow::Break(());
516            }
517            ControlFlow::Continue(())
518        })?;
519        if early_limit.is_some_and(|limit| collected.len() >= limit) {
520            break;
521        }
522    }
523    finish_query(
524        dedup_collected(collected),
525        query,
526        options,
527        Some(repo.odb()),
528        Some(repo),
529        peel,
530    )
531}
532
533/// Sort `collected` by full name and keep the first entry for each name.
534///
535/// Stores list each prefix in name order, so for a single namespace this is a linear pass.
536fn dedup_collected(mut collected: Vec<CollectedRef>) -> Vec<CollectedRef> {
537    collected.sort_by(|a, b| a.full_name.cmp(&b.full_name));
538    collected.dedup_by(|later, first| later.full_name == first.full_name);
539    collected
540}
541
542fn insert_collected_ref(
543    collected: &mut Vec<CollectedRef>,
544    entry: &RefEntry,
545    store: &dyn RefStore,
546    namespaces: &[RefNamespace],
547    query: &RefQuery,
548    options: &RefQueryOptions,
549) {
550    let resolved = entry
551        .peeled
552        .or_else(|| match &entry.value {
553            crate::refs::store::RawRef::Direct(oid) => Some(*oid),
554            crate::refs::store::RawRef::Symbolic(target) => {
555                store.resolve(RefNameRef::from_trusted(target)).ok()
556            }
557        })
558        .or_else(|| {
559            store
560                .resolve(RefNameRef::from_trusted(entry.name.as_str()))
561                .ok()
562        });
563    let Some(resolved) = resolved else {
564        return;
565    };
566    let short_name = short_name_for_query(entry.name.as_str(), namespaces);
567    if !patterns_match(&short_name, &query.patterns, options.ignore_case) {
568        return;
569    }
570    let direct_oid = match &entry.value {
571        crate::refs::store::RawRef::Direct(oid) => *oid,
572        crate::refs::store::RawRef::Symbolic(_) => resolved,
573    };
574    let peeled = match &entry.value {
575        crate::refs::store::RawRef::Direct(_) => entry.peeled,
576        crate::refs::store::RawRef::Symbolic(_) => None,
577    };
578    let kind = ref_kind_from_name(entry.name.as_str());
579    collected.push(CollectedRef {
580        full_name: entry.name.as_str().to_owned(),
581        short_name,
582        oid: direct_oid,
583        peeled,
584        kind,
585        creator_date: 0,
586    });
587}
588
589fn effective_namespaces(query: &RefQuery) -> Vec<RefNamespace> {
590    if query.namespaces.is_empty() {
591        vec![RefNamespace::Heads]
592    } else {
593        query.namespaces.clone()
594    }
595}
596
597fn short_name_for_query(full_name: &str, namespaces: &[RefNamespace]) -> String {
598    let mut best = 0usize;
599    for ns in namespaces {
600        let prefix = ns.prefix();
601        if full_name.starts_with(prefix) && prefix.len() > best {
602            best = prefix.len();
603        }
604    }
605    if best > 0 {
606        full_name[best..].to_owned()
607    } else {
608        short_name_for_kind(full_name, ref_kind_from_name(full_name))
609    }
610}
611
612fn short_name_for_kind(full_name: &str, kind: RefKind) -> String {
613    match kind {
614        RefKind::Head => full_name.strip_prefix("refs/heads/").unwrap_or(full_name),
615        RefKind::Remote => full_name.strip_prefix("refs/remotes/").unwrap_or(full_name),
616        RefKind::Tag => full_name.strip_prefix("refs/tags/").unwrap_or(full_name),
617        RefKind::Other => full_name.strip_prefix("refs/").unwrap_or(full_name),
618    }
619    .to_owned()
620}
621
622fn patterns_match(short_name: &str, patterns: &[String], ignore_case: bool) -> bool {
623    if patterns.is_empty() {
624        return true;
625    }
626    patterns
627        .iter()
628        .any(|p| pattern_matches_short_name(short_name, p, ignore_case))
629}
630
631fn query_has_reachability(query: &RefQuery) -> bool {
632    !query.contains.is_empty()
633        || !query.no_contains.is_empty()
634        || !query.merged.is_empty()
635        || !query.no_merged.is_empty()
636        || !query.points_at.is_empty()
637}
638
639/// When refs arrive in name order from the store, stop collecting once enough match.
640fn early_ref_collection_limit(query: &RefQuery, options: &RefQueryOptions) -> Option<usize> {
641    let limit = query.limit?;
642    if query.sort.key != SortKey::Name || query.sort.reverse {
643        return None;
644    }
645    if !query.patterns.is_empty() || options.ignore_case {
646        return None;
647    }
648    if query_has_reachability(query) {
649        return None;
650    }
651    if effective_namespaces(query).len() != 1 {
652        return None;
653    }
654    Some(limit)
655}
656
657fn finish_query(
658    mut collected: Vec<CollectedRef>,
659    query: &RefQuery,
660    options: &RefQueryOptions,
661    odb: Option<&Odb>,
662    repo: Option<&Repository>,
663    peel: PeelTips,
664) -> QueryResult<Vec<RefListing>> {
665    if query_has_reachability(query) {
666        // Filtering peels the tips it judges, so only the refs it keeps without having
667        // peeled them are peeled afterwards; each tip's header is read once.
668        let repo = repo.ok_or(crate::error::RefError::QueryNeedsObjectDatabase)?;
669        let packed = packed_peels_for(repo, &collected);
670        let mut rows: Vec<ReachRow> = collected
671            .iter()
672            .map(|c| ReachRow {
673                oid: c.oid,
674                peeled: c
675                    .peeled
676                    .map(Some)
677                    .or_else(|| packed.as_ref().and_then(|p| p.peeled(&c.full_name, &c.oid))),
678            })
679            .collect();
680        let keep = query_reachability::filter_listings_by_reachability(repo, query, &mut rows)?;
681        let mut verdicts = keep.into_iter().zip(rows);
682        collected.retain_mut(|entry| {
683            let Some((keep, row)) = verdicts.next() else {
684                return false;
685            };
686            if keep {
687                match row.peeled {
688                    Some(peeled) => entry.peeled = peeled,
689                    None => fill_peeled(repo.odb(), None, entry),
690                }
691            }
692            keep
693        });
694    } else if let Some(odb) = odb.filter(|_| peel == PeelTips::Always) {
695        let packed = repo.and_then(|r| packed_peels_for(r, &collected));
696        for entry in &mut collected {
697            fill_peeled(odb, packed.as_ref(), entry);
698        }
699    }
700    if matches!(query.sort.key, SortKey::Date) {
701        let odb = odb.ok_or(crate::error::RefError::QueryNeedsObjectDatabase)?;
702        for entry in &mut collected {
703            entry.creator_date = creator_date(odb, &entry.oid).unwrap_or(0);
704        }
705    }
706    let suffixes = &options.versionsort_suffixes;
707    collected.sort_by(|a, b| {
708        let primary = compare_entries(a, b, query.sort.key, suffixes);
709        let primary = if query.sort.reverse {
710            primary.reverse()
711        } else {
712            primary
713        };
714        if primary != Ordering::Equal {
715            return primary;
716        }
717        a.full_name.cmp(&b.full_name)
718    });
719    if let Some(limit) = query.limit {
720        collected.truncate(limit);
721    }
722    Ok(collected
723        .into_iter()
724        .map(|c| RefListing {
725            full_name: c.full_name,
726            short_name: c.short_name,
727            oid: c.oid,
728            peeled: c.peeled,
729            kind: c.kind,
730        })
731        .collect())
732}
733
734/// Fewest refs to peel for which indexing `packed-refs` beats reading each object header.
735///
736/// Loading the peel lines indexes the whole file, which in a repository with many packed
737/// refs costs more than a handful of object-header reads.
738pub(crate) const PACKED_PEELS_MIN_REFS: usize = 64;
739
740/// `packed-refs` peel lines for `collected`, when enough refs lack a peel to pay for them.
741///
742/// A malformed `packed-refs` only loses the shortcut; peeling falls back to the objects.
743fn packed_peels_for(repo: &Repository, collected: &[CollectedRef]) -> Option<PackedRefPeels> {
744    let to_peel = collected.iter().filter(|c| c.peeled.is_none()).count();
745    if to_peel < PACKED_PEELS_MIN_REFS {
746        return None;
747    }
748    PackedRefPeels::for_store(repo.ref_store(), repo.git_dir()).ok()
749}
750
751/// Set `entry.peeled` for annotated tags, preferring `packed-refs` peel lines over
752/// reading the tag object.
753fn fill_peeled(odb: &Odb, packed: Option<&PackedRefPeels>, entry: &mut CollectedRef) {
754    if entry.peeled.is_some() {
755        return;
756    }
757    if let Some(known) = packed.and_then(|p| p.peeled(&entry.full_name, &entry.oid)) {
758        entry.peeled = known;
759        return;
760    }
761    entry.peeled = odb.peel_tag_target(entry.oid).ok().flatten();
762}
763
764fn compare_entries(
765    a: &CollectedRef,
766    b: &CollectedRef,
767    key: SortKey,
768    suffixes: &[String],
769) -> Ordering {
770    match key {
771        SortKey::Name => a.full_name.cmp(&b.full_name),
772        SortKey::Version => compare_version_names(&a.full_name, &b.full_name, suffixes),
773        SortKey::Date => a.creator_date.cmp(&b.creator_date),
774    }
775}
776
777fn object_header_bytes(data: &[u8]) -> &[u8] {
778    if let Some(pos) = data.windows(2).position(|w| w == b"\n\n") {
779        &data[..pos]
780    } else {
781        data
782    }
783}
784
785fn find_header_value<'a>(header: &'a [u8], name: &[u8]) -> Option<&'a [u8]> {
786    let mut idx = 0;
787    while idx < header.len() {
788        let line_end = header[idx..]
789            .iter()
790            .position(|&b| b == b'\n')
791            .map(|p| idx + p)
792            .unwrap_or(header.len());
793        let line = &header[idx..line_end];
794        if line.is_empty() {
795            break;
796        }
797        if line.len() > name.len() + 1 && line.starts_with(name) && line[name.len()] == b' ' {
798            return Some(&line[name.len() + 1..]);
799        }
800        idx = line_end.saturating_add(1);
801    }
802    None
803}
804
805/// Build [`RefQueryOptions`] from repository config (`versionsort.suffix`, `core.ignorecase`).
806///
807/// # Errors
808///
809/// Propagates config load failures from [`Repository::config`](crate::repo::Repository::config).
810pub fn ref_query_options_for_repo(repo: &Repository) -> crate::error::Result<RefQueryOptions> {
811    let config = repo.config().snapshot()?;
812    let versionsort_suffixes = config.values_all("versionsort.suffix");
813    let ignore_case = config.ignore_case();
814    Ok(RefQueryOptions {
815        versionsort_suffixes,
816        ignore_case,
817    })
818}
819
820#[cfg(test)]
821mod tests {
822    #![allow(clippy::unwrap_used)]
823
824    use super::*;
825
826    #[test]
827    fn version_order_matches_git_tag_examples() {
828        assert_eq!(
829            compare_version_names("refs/tags/foo1.3", "refs/tags/foo1.10", &[]),
830            Ordering::Less
831        );
832        assert_eq!(
833            compare_version_names("refs/tags/foo1.10", "refs/tags/foo1.6", &[]),
834            Ordering::Greater
835        );
836    }
837
838    #[test]
839    fn pattern_prefix_slash_and_glob() {
840        assert!(pattern_matches_short_name("feature/x", "feature/", false));
841        assert!(pattern_matches_short_name("v1.9", "v1.*", false));
842        assert!(pattern_matches_short_name("release-rc1", "*rc*", false));
843        assert!(!pattern_matches_short_name("other", "feature/", false));
844    }
845
846    #[test]
847    fn versionsort_suffix_orders_prerelease() {
848        let suffixes = vec!["-rc".to_owned()];
849        assert_eq!(
850            compare_version_names("v1.0", "v1.0-rc1", &suffixes),
851            Ordering::Greater
852        );
853    }
854
855    #[test]
856    fn utf8_names_with_suffix_config_do_not_panic_in_compare() {
857        let suffixes = vec!["x".to_owned()];
858        let _ = compare_version_names("refs/tags/vα1", "refs/tags/vα2", &suffixes);
859    }
860
861    #[test]
862    fn ignore_case_prefix_directory_match() {
863        assert!(pattern_matches_short_name("Feature/x", "feature/", true));
864    }
865
866    #[test]
867    fn ignore_case_prefix_does_not_panic_on_utf8_short_names() {
868        assert!(!pattern_matches_short_name("€x", "a", true));
869    }
870
871    #[test]
872    fn ls_remote_empty_string_pattern_matches_nothing() {
873        assert!(!pattern_matches_ls_remote_pattern("refs/heads/main", ""));
874        assert!(!patterns_match_ls_remote(
875            "refs/heads/main",
876            &[String::new()]
877        ));
878        assert!(patterns_match_ls_remote("refs/heads/main", &[]));
879    }
880
881    #[test]
882    fn ls_remote_pattern_tail_component() {
883        assert!(pattern_matches_ls_remote_pattern("refs/heads/main", "main"));
884        assert!(!pattern_matches_ls_remote_pattern(
885            "refs/heads/topic",
886            "main"
887        ));
888        assert!(pattern_matches_ls_remote_pattern(
889            "refs/tags/v1^{}",
890            "refs/tags/v1*"
891        ));
892        assert!(!pattern_matches_ls_remote_pattern("refs/tags/v1^{}", "v1"));
893    }
894
895    #[test]
896    fn peel_tips_skips_peeling_only_without_filters() {
897        use crate::objects::{serialize_commit, serialize_tag, CommitData, ObjectKind, TagData};
898
899        let dir = tempfile::tempdir().unwrap();
900        let repo = crate::repo::init_repository(
901            dir.path(),
902            false,
903            "main",
904            None,
905            crate::RefStorageFormat::Files,
906        )
907        .unwrap();
908        let tree = repo.odb().write(ObjectKind::Tree, b"").unwrap();
909        let commit = repo
910            .odb()
911            .write(
912                ObjectKind::Commit,
913                &serialize_commit(&CommitData {
914                    tree,
915                    parents: Vec::new(),
916                    author: "T <t@example.com> 1 +0000".into(),
917                    committer: "T <t@example.com> 1 +0000".into(),
918                    author_raw: Vec::new(),
919                    committer_raw: Vec::new(),
920                    encoding: None,
921                    message: "m\n".into(),
922                    raw_message: None,
923                    extra_headers: Vec::new(),
924                }),
925            )
926            .unwrap();
927        let tag = repo
928            .odb()
929            .write(
930                ObjectKind::Tag,
931                &serialize_tag(&TagData {
932                    object: commit,
933                    object_type: "commit".into(),
934                    tag: "t".into(),
935                    tagger: Some("T <t@example.com> 1 +0000".into()),
936                    extra_headers: Vec::new(),
937                    message: "t\n".into(),
938                    raw_message: None,
939                }),
940            )
941            .unwrap();
942        crate::refs::write_ref(repo.git_dir(), "refs/heads/main", &commit).unwrap();
943        crate::refs::write_ref(repo.git_dir(), "refs/tags/tagged", &tag).unwrap();
944
945        let options = RefQueryOptions::default();
946        let peeled = |query: &RefQuery, peel: PeelTips| -> Vec<(String, Option<ObjectId>)> {
947            query_refs_peeling(&repo, query, &options, peel)
948                .unwrap()
949                .into_iter()
950                .map(|l| (l.short_name, l.peeled))
951                .collect()
952        };
953        let all = RefQuery {
954            namespaces: vec![RefNamespace::Heads, RefNamespace::Tags],
955            ..RefQuery::default()
956        };
957        let both_peeled = vec![
958            ("main".to_owned(), None),
959            ("tagged".to_owned(), Some(commit)),
960        ];
961        assert_eq!(peeled(&all, PeelTips::Always), both_peeled);
962        assert_eq!(
963            query_refs(&repo, &all, &options)
964                .unwrap()
965                .into_iter()
966                .map(|l| (l.short_name, l.peeled))
967                .collect::<Vec<_>>(),
968            both_peeled
969        );
970        assert_eq!(
971            peeled(&all, PeelTips::WhenFiltering),
972            vec![("main".to_owned(), None), ("tagged".to_owned(), None)]
973        );
974
975        let points_at = RefQuery {
976            points_at: vec![commit],
977            ..all.clone()
978        };
979        assert_eq!(peeled(&points_at, PeelTips::WhenFiltering), both_peeled);
980        let contains = RefQuery {
981            contains: vec![commit],
982            ..all.clone()
983        };
984        assert_eq!(peeled(&contains, PeelTips::WhenFiltering), both_peeled);
985    }
986
987    #[test]
988    fn limit_one_with_multiple_namespaces_uses_global_name_order() {
989        let dir = tempfile::tempdir().unwrap();
990        let repo = crate::repo::init_repository(
991            dir.path(),
992            false,
993            "main",
994            None,
995            crate::RefStorageFormat::Files,
996        )
997        .unwrap();
998        let tree = repo
999            .odb()
1000            .write(crate::objects::ObjectKind::Tree, b"")
1001            .unwrap();
1002        let commit = repo
1003            .odb()
1004            .write(
1005                crate::objects::ObjectKind::Commit,
1006                &crate::objects::serialize_commit(&crate::objects::CommitData {
1007                    tree,
1008                    parents: Vec::new(),
1009                    author: "T <t@example.com> 1 +0000".into(),
1010                    committer: "T <t@example.com> 1 +0000".into(),
1011                    author_raw: Vec::new(),
1012                    committer_raw: Vec::new(),
1013                    encoding: None,
1014                    message: "m\n".into(),
1015                    raw_message: None,
1016                    extra_headers: Vec::new(),
1017                }),
1018            )
1019            .unwrap();
1020        crate::refs::write_ref(repo.git_dir(), "refs/heads/a", &commit).unwrap();
1021        crate::refs::write_ref(repo.git_dir(), "refs/tags/z", &commit).unwrap();
1022
1023        let query = RefQuery {
1024            namespaces: vec![RefNamespace::Tags, RefNamespace::Heads],
1025            limit: Some(1),
1026            sort: RefSort {
1027                key: SortKey::Name,
1028                reverse: false,
1029            },
1030            ..RefQuery::default()
1031        };
1032        let names: Vec<String> = query_refs(&repo, &query, &RefQueryOptions::default())
1033            .unwrap()
1034            .into_iter()
1035            .map(|l| l.full_name)
1036            .collect();
1037        assert_eq!(names, vec!["refs/heads/a".to_owned()]);
1038    }
1039}