gix_ref/store/packed/
find.rs

1use gix_object::bstr::{BStr, BString};
2
3use crate::{FullNameRef, PartialNameRef, store_impl::packed};
4
5/// packed-refs specific functionality
6impl packed::Buffer {
7    /// Find a reference with the given `name` and return it.
8    ///
9    /// Note that it will look it up verbatim and does not deal with namespaces or special prefixes like
10    /// `main-worktree/` or `worktrees/<name>/`, as this is left to the caller.
11    pub fn try_find<'a, Name, E>(&self, name: Name) -> Result<Option<packed::Reference<'_>>, Error>
12    where
13        Name: TryInto<&'a PartialNameRef, Error = E>,
14        Error: From<E>,
15    {
16        let name = name.try_into()?;
17        let mut buf = BString::default();
18        for inbetween in &["", "tags", "heads", "remotes"] {
19            let (name, was_absolute) = if name.looks_like_full_name(false) {
20                let name = FullNameRef::new_unchecked(name.as_bstr());
21                let name = match transform_full_name_for_lookup(name) {
22                    None => return Ok(None),
23                    Some(name) => name,
24                };
25                (name, true)
26            } else {
27                let full_name = name.construct_full_name_ref(inbetween, &mut buf, false);
28                (full_name, false)
29            };
30            match self.try_find_full_name(name)? {
31                Some(r) => return Ok(Some(r)),
32                None if was_absolute => return Ok(None),
33                None => continue,
34            }
35        }
36        Ok(None)
37    }
38
39    pub(crate) fn try_find_full_name(&self, name: &FullNameRef) -> Result<Option<packed::Reference<'_>>, Error> {
40        match self.binary_search_by(name.as_bstr()) {
41            Ok(line_start) => {
42                let mut input = &self.as_ref()[line_start..];
43                Ok(Some(
44                    packed::decode::reference(&mut input, self.object_hash).map_err(|_| Error::Parse)?,
45                ))
46            }
47            Err((parse_failure, _)) => {
48                if parse_failure {
49                    Err(Error::Parse)
50                } else {
51                    Ok(None)
52                }
53            }
54        }
55    }
56
57    /// Find a reference with the given `name` and return it.
58    pub fn find<'a, Name, E>(&self, name: Name) -> Result<packed::Reference<'_>, existing::Error>
59    where
60        Name: TryInto<&'a PartialNameRef, Error = E>,
61        Error: From<E>,
62    {
63        match self.try_find(name) {
64            Ok(Some(r)) => Ok(r),
65            Ok(None) => Err(existing::Error::NotFound),
66            Err(err) => Err(existing::Error::Find(err)),
67        }
68    }
69
70    /// Perform a binary search where `Ok(pos)` is the beginning of the line that matches `name` perfectly and `Err(pos)`
71    /// is the beginning of the line at which `name` could be inserted to still be in sort order.
72    pub(in crate::store_impl::packed) fn binary_search_by(&self, full_name: &BStr) -> Result<usize, (bool, usize)> {
73        let a = self.as_ref();
74        let mut encountered_parse_failure = false;
75        a.binary_search_by_key(&full_name.as_ref(), |b: &u8| {
76            let ofs = std::ptr::from_ref::<u8>(b) as usize - a.as_ptr() as usize;
77            let line = packed::decode::record_at_offset(a, ofs);
78            // The binary search only needs the name bytes for ordered
79            // comparison; skip ref-name and hex-hash validation here and let
80            // the final match site re-parse the record via `decode::reference`
81            // (which validates fully). This saves the `log₂(n)` per-query.
82            match packed::decode::name_at_record_start(line, self.object_hash) {
83                Some(name) => name,
84                None => {
85                    encountered_parse_failure = true;
86                    &[]
87                }
88            }
89        })
90        .map(|pos| packed::decode::record_start_at_offset(a, pos))
91        .map_err(|pos| {
92            (
93                encountered_parse_failure,
94                packed::decode::record_start_at_offset(a, pos),
95            )
96        })
97    }
98}
99
100mod error {
101    use std::convert::Infallible;
102
103    /// The error returned by [`find()`][super::packed::Buffer::find()]
104    #[derive(Debug, thiserror::Error)]
105    #[allow(missing_docs)]
106    pub enum Error {
107        #[error("The ref name or path is not a valid ref name")]
108        RefnameValidation(#[from] crate::name::Error),
109        #[error("The reference could not be parsed")]
110        Parse,
111    }
112
113    impl From<Infallible> for Error {
114        fn from(_: Infallible) -> Self {
115            unreachable!("this impl is needed to allow passing a known valid partial path as parameter")
116        }
117    }
118}
119pub use error::Error;
120
121///
122pub mod existing {
123
124    /// The error returned by [`find_existing()`][super::packed::Buffer::find()]
125    #[derive(Debug, thiserror::Error)]
126    #[allow(missing_docs)]
127    pub enum Error {
128        #[error("The find operation failed")]
129        Find(#[from] super::Error),
130        #[error("The reference did not exist even though that was expected")]
131        NotFound,
132    }
133}
134
135pub(crate) fn transform_full_name_for_lookup(name: &FullNameRef) -> Option<&FullNameRef> {
136    match name.category_and_short_name() {
137        Some((c, sn)) => {
138            use crate::Category::*;
139            Some(match c {
140                MainRef | LinkedRef { .. } => FullNameRef::new_unchecked(sn),
141                Tag | RemoteBranch | LocalBranch | Bisect | Rewritten | Note => name,
142                MainPseudoRef | PseudoRef | LinkedPseudoRef { .. } | WorktreePrivate => return None,
143            })
144        }
145        None => Some(name),
146    }
147}
gix_ref/store/packed/find.rs

gix_ref/store/packed/
find.rs
