holger-server-lib 0.6.9

//! Repo-name → backend dispatch table on the gRPC/HTTP hot path.
//!
//! An `ExposedEndpoint` fans out to many repos; every request must resolve the
//! repo name to its `RepositoryBackendTrait` before `fetch()`/`put()`. Rather
//! than a `HashMap` this uses a first-byte bucketed table: routes are sorted by
//! initial byte (then length), and `first_byte_index`/`first_byte_len` give the
//! `[start, len)` slice for a byte in O(1), so `lookup` scans only same-first-byte
//! names with exact `==` compare — no hashing, cache-friendly for the small,
//! fixed route sets the wiring engine attaches.
//!
//! Built once and immutable: `FastRoutes::new` is called after the graph is
//! wired, and the struct is `Clone` (cheap — `Arc` backends) but never mutated.
//! Gotcha: bucketing is purely on the first byte, and empty names fold into
//! byte 0 (`unwrap_or(0)`), so an empty-string route collides with anything else
//! keyed at index 0 — names are assumed non-empty and unique.

use std::sync::Arc;
use traits::RepositoryBackendTrait;


#[derive(Clone)]
pub struct FastRoute {
    pub name: String,
    // todo make Option
    pub backend: Arc<dyn RepositoryBackendTrait>,
}

#[derive(Clone)]
pub struct FastRoutes {
    pub routes: Vec<FastRoute>,
    pub first_byte_index: [usize; 256],
    pub first_byte_len: [usize; 256],
}

impl FastRoutes {
    pub fn new(routes: Vec<(String, Arc<dyn RepositoryBackendTrait>)>) -> Self {
        let mut routes_vec: Vec<FastRoute> = routes
            .into_iter()
            .map(|(name, backend)| FastRoute { name, backend })
            .collect();

        // Sort by first byte then length
        routes_vec.sort_by(|a, b| {
            let fa = a.name.as_bytes().first().copied().unwrap_or(0);
            let fb = b.name.as_bytes().first().copied().unwrap_or(0);
            fa.cmp(&fb).then(a.name.len().cmp(&b.name.len()))
        });

        let mut first_byte_index = [0usize; 256];
        let mut first_byte_len = [0usize; 256];

        // Build lookup table
        let mut i = 0usize;
        while i < routes_vec.len() {
            let byte = routes_vec[i].name.as_bytes().first().copied().unwrap_or(0);
            let start = i;
            while i < routes_vec.len()
                && routes_vec[i].name.as_bytes().first().copied().unwrap_or(0) == byte
            {
                i += 1;
            }
            first_byte_index[byte as usize] = start;
            first_byte_len[byte as usize] = i - start;
        }

        Self {
            routes: routes_vec,
            first_byte_index,
            first_byte_len,
        }
    }

    pub fn lookup(&self, name: &str) -> Option<&Arc<dyn RepositoryBackendTrait>> {
        let bytes = name.as_bytes();
        let first = bytes.first().copied().unwrap_or(0) as usize;

        let start = self.first_byte_index[first];
        let len = self.first_byte_len[first];
        if len == 0 {
            return None;
        }

        let bucket = &self.routes[start..start + len];
        for r in bucket {
            if r.name == name {
                return Some(&r.backend);
            }
        }
        None
    }

    pub fn all_repos(&self) -> Vec<(String, Arc<dyn RepositoryBackendTrait>)> {
        self.routes.iter().map(|r| (r.name.clone(), r.backend.clone())).collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use traits::{ArtifactEntry, ArtifactFormat, ArtifactId};

    /// A backend that only knows its own name — enough to prove `lookup` resolves
    /// a repo name to the RIGHT backend (we assert on `backend.name()`).
    struct NamedRepo(&'static str);

    #[async_trait::async_trait]
    impl RepositoryBackendTrait for NamedRepo {
        fn name(&self) -> &str {
            self.0
        }
        fn format(&self) -> ArtifactFormat {
            ArtifactFormat::Raw
        }
        fn is_writable(&self) -> bool {
            false
        }
        fn fetch(&self, _id: &ArtifactId) -> anyhow::Result<Option<Vec<u8>>> {
            Ok(None)
        }
        fn put(&self, _id: &ArtifactId, _data: &[u8]) -> anyhow::Result<()> {
            anyhow::bail!("read-only")
        }
        fn list(&self, _f: Option<&str>, _l: usize) -> anyhow::Result<Vec<ArtifactEntry>> {
            Ok(Vec::new())
        }
        fn handle_http2_request(
            &self,
            _m: &str,
            _s: &str,
            _b: &[u8],
        ) -> anyhow::Result<(u16, Vec<(String, String)>, Vec<u8>)> {
            Ok((404, Vec::new(), Vec::new()))
        }
    }

    fn route(name: &'static str) -> (String, Arc<dyn RepositoryBackendTrait>) {
        (name.to_string(), Arc::new(NamedRepo(name)) as Arc<dyn RepositoryBackendTrait>)
    }

    #[test]
    fn lookup_resolves_every_registered_name_to_its_own_backend() {
        // Deliberately unsorted input; several share a first byte ('r', 'm').
        let fr = FastRoutes::new(vec![
            route("rust"),
            route("maven"),
            route("rust-proxy"),
            route("mirror"),
            route("pip"),
        ]);
        for name in ["rust", "maven", "rust-proxy", "mirror", "pip"] {
            let backend = fr.lookup(name).unwrap_or_else(|| panic!("{name} not found"));
            assert_eq!(backend.name(), name, "lookup returned the WRONG backend for {name}");
        }
    }

    #[test]
    fn same_first_byte_siblings_do_not_alias_and_lengths_are_covered() {
        // 'r' bucket holds three names of different lengths — the paginator sorts
        // by (first_byte, len), so this exercises the length tiebreak + exact `==`.
        let fr = FastRoutes::new(vec![route("r"), route("rust"), route("rust-proxy")]);
        assert_eq!(fr.lookup("r").unwrap().name(), "r");
        assert_eq!(fr.lookup("rust").unwrap().name(), "rust");
        assert_eq!(fr.lookup("rust-proxy").unwrap().name(), "rust-proxy");
        // A name in the same bucket that was never registered must miss, not alias
        // onto a sibling sharing the first byte.
        assert!(fr.lookup("ruby").is_none(), "unregistered same-first-byte name misses");
        assert!(fr.lookup("rustacean").is_none());
    }

    #[test]
    fn lookup_misses_return_none() {
        let fr = FastRoutes::new(vec![route("maven"), route("pip")]);
        // A first byte with zero routes ('z') short-circuits on first_byte_len==0.
        assert!(fr.lookup("zzz").is_none(), "unpopulated first byte → None");
        // A populated first byte ('m') but a name not in the bucket.
        assert!(fr.lookup("mirror").is_none());
        // The empty string folds to byte 0, which has no routes here.
        assert!(fr.lookup("").is_none());
    }

    #[test]
    fn empty_route_table_looks_up_nothing() {
        let fr = FastRoutes::new(Vec::new());
        assert!(fr.lookup("anything").is_none());
        assert!(fr.all_repos().is_empty());
    }

    #[test]
    fn all_repos_returns_every_registered_route() {
        let fr = FastRoutes::new(vec![route("a"), route("b"), route("c")]);
        let mut names: Vec<String> = fr.all_repos().into_iter().map(|(n, _)| n).collect();
        names.sort();
        assert_eq!(names, vec!["a".to_string(), "b".into(), "c".into()]);
    }

    #[test]
    fn high_byte_names_bucket_correctly() {
        // Non-ASCII first byte (>127) must still bucket into the 256-wide table
        // without indexing out of range.
        let fr = FastRoutes::new(vec![route("æther"), route("rust")]);
        assert_eq!(fr.lookup("æther").unwrap().name(), "æther");
        assert_eq!(fr.lookup("rust").unwrap().name(), "rust");
        assert!(fr.lookup("ähnlich").is_none());
    }
}