Radish alpha
h
heartwood
rad:z3gqcJUoA1n9HaHKufZs5FCSGazv5
Radicle Heartwood Protocol & Stack
Radicle
Git
Patches › 4288b0ec
radicle: reverse lookup for AliasStore
Merged fintohaps opened 1 year ago

Provide functionality to lookup the NodeIds associated with a given Alias.

The use for this functionality is to allow callers to use aliases as shorthands for NodeIds, but still refer to the exact identifier.

The implementation allows for searching using the LIKE '%<pattern>%' queries in sqlite, so searches do not have to be exact matches.

Activity Changes +289 -3
4 files changed +289 -3 3dba4fbc → 6940ac42
modified radicle/src/node.rs
@@ -13,7 +13,7 @@ pub mod routing;
pub mod seed;

pub mod timestamp;
- 
use std::collections::{BTreeSet, HashMap, HashSet, VecDeque};
+ 
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};

use std::io::{BufRead, BufReader};

use std::marker::PhantomData;

use std::ops::{ControlFlow, Deref};
@@ -388,6 +388,27 @@ impl TryFrom<String> for Alias {
    }

}
+ 
impl TryFrom<&sqlite::Value> for Alias {
+ 
    type Error = sqlite::Error;
+
+ 
    fn try_from(value: &sqlite::Value) -> Result<Self, Self::Error> {
+ 
        match value {
+ 
            sqlite::Value::String(s) => Self::from_str(s).map_err(|e| sqlite::Error {
+ 
                code: None,
+ 
                message: Some(e.to_string()),
+ 
            }),
+ 
            _ => Err(sqlite::Error {
+ 
                code: None,
+ 
                message: Some(format!(
+ 
                    "sql: invalid type {:?} for alias, expected {:?}",
+ 
                    value.kind(),
+ 
                    sqlite::Type::String
+ 
                )),
+ 
            }),
+ 
        }
+ 
    }
+ 
}
+ 


/// Options passed to the "connect" node command.

#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]

pub struct ConnectOptions {
@@ -1361,12 +1382,109 @@ impl Handle for Node {
pub trait AliasStore {

    /// Returns alias of a `NodeId`.

    fn alias(&self, nid: &NodeId) -> Option<Alias>;
+
+ 
    /// Return all the [`NodeId`]s that match the `alias`.
+ 
    ///
+ 
    /// Note that the implementation may choose to allow the alias to be a
+ 
    /// substring for more dynamic queries, thus a `BTreeMap` is returned to return
+ 
    /// the full [`Alias`] and matching [`NodeId`]s.
+ 
    fn reverse_lookup(&self, alias: &Alias) -> BTreeMap<Alias, BTreeSet<NodeId>>;

}



impl AliasStore for HashMap<NodeId, Alias> {

    fn alias(&self, nid: &NodeId) -> Option<Alias> {

        self.get(nid).map(ToOwned::to_owned)

    }
+
+ 
    fn reverse_lookup(&self, needle: &Alias) -> BTreeMap<Alias, BTreeSet<NodeId>> {
+ 
        self.iter()
+ 
            .fold(BTreeMap::new(), |mut result, (node, alias)| {
+ 
                if alias.contains(needle.as_str()) {
+ 
                    let nodes = result.entry(alias.clone()).or_default();
+ 
                    nodes.insert(*node);
+ 
                }
+ 
                result
+ 
            })
+ 
    }
+ 
}
+
+ 
#[cfg(test)]
+ 
pub(crate) mod properties {
+ 
    use std::collections::BTreeSet;
+
+ 
    use crate::node::{Alias, NodeId};
+ 
    use crate::test::arbitrary;
+
+ 
    use super::AliasStore;
+
+ 
    pub struct AliasInput {
+ 
        short: (Alias, BTreeSet<NodeId>),
+ 
        long: (Alias, BTreeSet<NodeId>),
+ 
    }
+
+ 
    impl AliasInput {
+ 
        pub fn new() -> Self {
+ 
            let short = arbitrary::gen::<Alias>(0);
+ 
            let long = {
+ 
                // Ensure we have a second, unique alias
+ 
                let mut a = short.to_string();
+ 
                a.push_str(arbitrary::gen::<Alias>(1).as_str());
+ 
                Alias::new(a)
+ 
            };
+ 
            Self {
+ 
                short: (short, arbitrary::vec::<NodeId>(3).into_iter().collect()),
+ 
                long: (long, arbitrary::vec::<NodeId>(2).into_iter().collect()),
+ 
            }
+ 
        }
+
+ 
        pub fn short(&self) -> &(Alias, BTreeSet<NodeId>) {
+ 
            &self.short
+ 
        }
+
+ 
        pub fn long(&self) -> &(Alias, BTreeSet<NodeId>) {
+ 
            &self.long
+ 
        }
+ 
    }
+
+ 
    /// Given the `AliasInput` ensure that the lookup of `NodeId`s for two
+ 
    /// aliases works as intended.
+ 
    ///
+ 
    /// The `short` alias is a prefix of the `long` alias, so when looking up
+ 
    /// the `short` alias, both sets of results will return. For the `long`
+ 
    /// alias, only its results will return.
+ 
    ///
+ 
    /// It is also expected that the lookup is case insensitive.
+ 
    pub fn test_reverse_lookup(store: &impl AliasStore, AliasInput { short, long }: AliasInput) {
+ 
        let (short, short_ids) = short;
+ 
        let (long, long_ids) = long;
+ 
        let first = store.reverse_lookup(&short);
+ 
        // We get back the results for `short`
+ 
        assert_eq!(first.get(&short), Some(&short_ids),);
+ 
        // We also get back the results for `long` since `short` is a prefix of it
+ 
        assert_eq!(first.get(&long), Some(&long_ids));
+
+ 
        let second = store.reverse_lookup(&long);
+ 
        // We do not get back a result for `short` since it is only a suffix of `long`
+ 
        assert_eq!(second.get(&short), None);
+ 
        assert_eq!(second.get(&long), Some(&long_ids));
+
+ 
        let mixed_case = Alias::new(
+ 
            short
+ 
                .as_str()
+ 
                .chars()
+ 
                .enumerate()
+ 
                .map(|(i, c)| {
+ 
                    if i % 2 == 0 {
+ 
                        c.to_ascii_uppercase()
+ 
                    } else {
+ 
                        c.to_ascii_lowercase()
+ 
                    }
+ 
                })
+ 
                .collect::<String>(),
+ 
        );
+ 
        let upper = store.reverse_lookup(&mixed_case);
+ 
        assert!(upper.contains_key(&short));
+ 
    }

}



#[cfg(test)]
modified radicle/src/node/address/store.rs
@@ -1,3 +1,4 @@
+ 
use std::collections::{BTreeMap, BTreeSet};

use std::net::IpAddr;

use std::num::TryFromIntError;

use std::str::FromStr;
@@ -20,6 +21,8 @@ pub enum Error {
    Internal(#[from] sql::Error),

    #[error("alias error: {0}")]

    InvalidAlias(#[from] AliasError),
+ 
    #[error("node id error: {0}")]
+ 
    Node(#[from] crypto::PublicKeyError),

    #[error("integer conversion error: {0}")]

    TryFromInt(#[from] TryFromIntError),

    /// No rows returned in query result.
@@ -94,6 +97,14 @@ pub trait Store {
    ) -> Result<(), Error>;

}
+ 
pub trait StoreExt {
+ 
    type NodeAlias<'a>: Iterator<Item = Result<(NodeId, Alias), Error>> + 'a
+ 
    where
+ 
        Self: 'a;
+
+ 
    fn nodes_by_alias<'a>(&'a self, alias: &Alias) -> Result<Self::NodeAlias<'a>, Error>;
+ 
}
+ 


impl Store for Database {

    fn get(&self, node: &NodeId) -> Result<Option<Node>, Error> {

        let mut stmt = self.db.prepare(
@@ -413,9 +424,51 @@ impl Store for Database {
    }

}
+ 
pub struct NodeAliasIter<'a> {
+ 
    inner: sql::CursorWithOwnership<'a>,
+ 
}
+
+ 
impl<'a> NodeAliasIter<'a> {
+ 
    fn parse_row(row: sql::Row) -> Result<(NodeId, Alias), Error> {
+ 
        let nid = row.try_read::<NodeId, _>("id")?;
+ 
        let alias = row.try_read::<&str, _>("alias")?.parse()?;
+ 
        Ok((nid, alias))
+ 
    }
+ 
}
+
+ 
impl<'a> Iterator for NodeAliasIter<'a> {
+ 
    type Item = Result<(NodeId, Alias), Error>;
+
+ 
    fn next(&mut self) -> Option<Self::Item> {
+ 
        let row = self.inner.next()?;
+ 
        Some(row.map_err(Error::from).and_then(Self::parse_row))
+ 
    }
+ 
}
+
+ 
impl StoreExt for Database {
+ 
    type NodeAlias<'a> = NodeAliasIter<'a>
+ 
    where
+ 
        Self: 'a;
+
+ 
    fn nodes_by_alias<'a>(&'a self, alias: &Alias) -> Result<Self::NodeAlias<'a>, Error> {
+ 
        let mut stmt = self.db.prepare(
+ 
            "SELECT id, alias
+ 
             FROM nodes
+ 
             WHERE UPPER(alias) LIKE ?",
+ 
        )?;
+ 
        stmt.bind((
+ 
            1,
+ 
            sql::Value::String(format!("%{}%", alias.as_str().to_uppercase())),
+ 
        ))?;
+ 
        Ok(NodeAliasIter {
+ 
            inner: stmt.into_iter(),
+ 
        })
+ 
    }
+ 
}
+ 


impl<T> AliasStore for T

where
- 
    T: Store,
+ 
    T: Store + StoreExt,

{

    /// Retrieve `alias` of given node.

    /// Calls `Self::get` under the hood.
@@ -424,6 +477,18 @@ where
            .map(|node| node.map(|n| n.alias))

            .unwrap_or(None)

    }
+
+ 
    fn reverse_lookup(&self, alias: &Alias) -> BTreeMap<Alias, BTreeSet<NodeId>> {
+ 
        let Ok(iter) = self.nodes_by_alias(alias) else {
+ 
            return BTreeMap::new();
+ 
        };
+ 
        iter.flatten()
+ 
            .fold(BTreeMap::new(), |mut result, (node, alias)| {
+ 
                let nodes = result.entry(alias).or_default();
+ 
                nodes.insert(node);
+ 
                result
+ 
            })
+ 
    }

}



impl TryFrom<&sql::Value> for Source {
@@ -904,4 +969,28 @@ mod test {
        assert!(db.is_ip_banned(ip1.into()).unwrap());

        assert!(db.is_ip_banned(ip2.into()).unwrap());

    }
+
+ 
    #[test]
+ 
    fn test_node_aliases() {
+ 
        let mut db = Database::memory().unwrap();
+ 
        let input = node::properties::AliasInput::new();
+ 
        let (short, short_ids) = input.short();
+ 
        let (long, long_ids) = input.long();
+ 
        let features = node::Features::SEED;
+ 
        let agent = UserAgent::default();
+ 
        let timestamp = Timestamp::from(LocalTime::now());
+ 
        let ka = arbitrary::gen::<KnownAddress>(1);
+
+ 
        for id in short_ids {
+ 
            db.insert(id, 1, features, short, 16, &agent, timestamp, [ka.clone()])
+ 
                .unwrap();
+ 
        }
+
+ 
        for id in long_ids {
+ 
            db.insert(id, 1, features, long, 16, &agent, timestamp, [ka.clone()])
+ 
                .unwrap();
+ 
        }
+
+ 
        node::properties::test_reverse_lookup(&db, input)
+ 
    }

}
modified radicle/src/node/policy/store.rs
@@ -1,4 +1,5 @@
#![allow(clippy::type_complexity)]
+ 
use std::collections::{BTreeMap, BTreeSet};

use std::marker::PhantomData;

use std::path::Path;

use std::{fmt, io, ops::Not as _, str::FromStr, time};
@@ -341,6 +342,38 @@ impl<T> Store<T> {
        }

        Ok(Box::new(entries.into_iter()))

    }
+
+ 
    pub fn nodes_by_alias<'a>(&'a self, alias: &Alias) -> Result<NodeAliasIter<'a>, Error> {
+ 
        let mut stmt = self
+ 
            .db
+ 
            .prepare("SELECT id, alias FROM `following` WHERE UPPER(alias) LIKE ?")?;
+ 
        let query = format!("%{}%", alias.as_str().to_uppercase());
+ 
        stmt.bind((1, sql::Value::String(query)))?;
+ 
        Ok(NodeAliasIter {
+ 
            inner: stmt.into_iter(),
+ 
        })
+ 
    }
+ 
}
+
+ 
pub struct NodeAliasIter<'a> {
+ 
    inner: sql::CursorWithOwnership<'a>,
+ 
}
+
+ 
impl<'a> NodeAliasIter<'a> {
+ 
    fn parse_row(row: sql::Row) -> Result<(NodeId, Alias), Error> {
+ 
        let nid = row.try_read::<NodeId, _>("id")?;
+ 
        let alias = row.try_read::<Alias, _>("alias")?;
+ 
        Ok((nid, alias))
+ 
    }
+ 
}
+
+ 
impl<'a> Iterator for NodeAliasIter<'a> {
+ 
    type Item = Result<(NodeId, Alias), Error>;
+
+ 
    fn next(&mut self) -> Option<Self::Item> {
+ 
        let row = self.inner.next()?;
+ 
        Some(row.map_err(Error::from).and_then(Self::parse_row))
+ 
    }

}



impl<T> AliasStore for Store<T> {
@@ -351,12 +384,24 @@ impl<T> AliasStore for Store<T> {
            .map(|node| node.and_then(|n| n.alias))

            .unwrap_or(None)

    }
+
+ 
    fn reverse_lookup(&self, alias: &Alias) -> BTreeMap<Alias, BTreeSet<NodeId>> {
+ 
        let Ok(iter) = self.nodes_by_alias(alias) else {
+ 
            return BTreeMap::new();
+ 
        };
+ 
        iter.flatten()
+ 
            .fold(BTreeMap::new(), |mut result, (node, alias)| {
+ 
                let nodes = result.entry(alias).or_default();
+ 
                nodes.insert(node);
+ 
                result
+ 
            })
+ 
    }

}



#[cfg(test)]

#[allow(clippy::unwrap_used)]

mod test {
- 
    use crate::assert_matches;
+ 
    use crate::{assert_matches, node};



    use super::*;

    use crate::test::arbitrary;
@@ -478,4 +523,22 @@ mod test {
            Policy::Block

        );

    }
+
+ 
    #[test]
+ 
    fn test_node_aliases() {
+ 
        let mut db = Store::open(":memory:").unwrap();
+ 
        let input = node::properties::AliasInput::new();
+ 
        let (short, short_ids) = input.short();
+ 
        let (long, long_ids) = input.long();
+
+ 
        for id in short_ids {
+ 
            db.follow(id, Some(short.as_str())).unwrap();
+ 
        }
+
+ 
        for id in long_ids {
+ 
            db.follow(id, Some(long.as_str())).unwrap();
+ 
        }
+
+ 
        node::properties::test_reverse_lookup(&db, input)
+ 
    }

}
modified radicle/src/profile.rs
@@ -14,6 +14,7 @@
pub mod config;

pub use config::{Config, ConfigError, ConfigPath, RawConfig};
+ 
use std::collections::{BTreeMap, BTreeSet};

use std::path::{Path, PathBuf};

use std::{fs, io};
@@ -409,6 +410,10 @@ impl AliasStore for Profile {
    fn alias(&self, nid: &NodeId) -> Option<Alias> {

        self.aliases().alias(nid)

    }
+
+ 
    fn reverse_lookup(&self, alias: &Alias) -> BTreeMap<Alias, BTreeSet<NodeId>> {
+ 
        self.aliases().reverse_lookup(alias)
+ 
    }

}



/// Holds multiple alias stores, and will try
@@ -427,6 +432,17 @@ impl AliasStore for Aliases {
            .and_then(|db| db.alias(nid))

            .or_else(|| self.db.as_ref().and_then(|db| db.alias(nid)))

    }
+
+ 
    fn reverse_lookup(&self, alias: &Alias) -> BTreeMap<Alias, BTreeSet<NodeId>> {
+ 
        let mut nodes = BTreeMap::new();
+ 
        if let Some(db) = self.policies.as_ref() {
+ 
            nodes.extend(db.reverse_lookup(alias));
+ 
        }
+ 
        if let Some(db) = self.db.as_ref() {
+ 
            nodes.extend(db.reverse_lookup(alias));
+ 
        }
+ 
        nodes
+ 
    }

}



/// Get the path to the radicle home folder.