gix_ref/store/packed/
find.rs

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

gix_ref/store/packed/
find.rs
