git_ref/store/packed/
find.rs

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

git_ref/store/packed/
find.rs
