gix_ref/store/packed/
find.rs

1use gix_object::bstr::{BStr, BString, ByteSlice};
2
3use crate::{store_impl::packed, FullNameRef, PartialNameRef};
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.hash_kind).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 search_start_of_record = |ofs: usize| {
75            a[..ofs]
76                .rfind(b"\n")
77                .and_then(|pos| {
78                    let candidate = pos + 1;
79                    a.get(candidate).and_then(|b| {
80                        if *b == b'^' {
81                            a[..pos].rfind(b"\n").map(|pos| pos + 1)
82                        } else {
83                            Some(candidate)
84                        }
85                    })
86                })
87                .unwrap_or(0)
88        };
89        let mut encountered_parse_failure = false;
90        a.binary_search_by_key(&full_name.as_ref(), |b: &u8| {
91            let ofs = std::ptr::from_ref::<u8>(b) as usize - a.as_ptr() as usize;
92            let mut line = &a[search_start_of_record(ofs)..];
93            packed::decode::reference(&mut line, self.hash_kind)
94                .map(|r| r.name.as_bstr().as_bytes())
95                .inspect_err(|_err| {
96                    encountered_parse_failure = true;
97                })
98                .unwrap_or(&[])
99        })
100        .map(search_start_of_record)
101        .map_err(|pos| (encountered_parse_failure, search_start_of_record(pos)))
102    }
103}
104
105mod error {
106    use std::convert::Infallible;
107
108    /// The error returned by [`find()`][super::packed::Buffer::find()]
109    #[derive(Debug, thiserror::Error)]
110    #[allow(missing_docs)]
111    pub enum Error {
112        #[error("The ref name or path is not a valid ref name")]
113        RefnameValidation(#[from] crate::name::Error),
114        #[error("The reference could not be parsed")]
115        Parse,
116    }
117
118    impl From<Infallible> for Error {
119        fn from(_: Infallible) -> Self {
120            unreachable!("this impl is needed to allow passing a known valid partial path as parameter")
121        }
122    }
123}
124pub use error::Error;
125
126///
127pub mod existing {
128
129    /// The error returned by [`find_existing()`][super::packed::Buffer::find()]
130    #[derive(Debug, thiserror::Error)]
131    #[allow(missing_docs)]
132    pub enum Error {
133        #[error("The find operation failed")]
134        Find(#[from] super::Error),
135        #[error("The reference did not exist even though that was expected")]
136        NotFound,
137    }
138}
139
140pub(crate) fn transform_full_name_for_lookup(name: &FullNameRef) -> Option<&FullNameRef> {
141    match name.category_and_short_name() {
142        Some((c, sn)) => {
143            use crate::Category::*;
144            Some(match c {
145                MainRef | LinkedRef { .. } => FullNameRef::new_unchecked(sn),
146                Tag | RemoteBranch | LocalBranch | Bisect | Rewritten | Note => name,
147                MainPseudoRef | PseudoRef | LinkedPseudoRef { .. } | WorktreePrivate => return None,
148            })
149        }
150        None => Some(name),
151    }
152}
gix_ref/store/packed/find.rs

gix_ref/store/packed/
find.rs
