coap_server/app/
path_matcher.rs

1use std::collections::hash_map::Values;
2use std::collections::HashMap;
3
4/// Lookup mechanism that uses inexact matching of input paths by finding the most specific
5/// match and returning that instead.  See [`PathMatcher::lookup`] for more information.
6#[derive(Debug)]
7pub struct PathMatcher<V> {
8    map: HashMap<Vec<String>, V>,
9}
10
11impl<V> FromIterator<(Vec<String>, V)> for PathMatcher<V> {
12    fn from_iter<I: IntoIterator<Item = (Vec<String>, V)>>(iter: I) -> Self {
13        Self {
14            map: HashMap::from_iter(iter),
15        }
16    }
17}
18
19impl<V> PathMatcher<V> {
20    pub fn new_empty() -> Self {
21        Self {
22            map: HashMap::default(),
23        }
24    }
25
26    /// Convert canonical path strings into the more efficient PathMatcher variation.  Input paths
27    /// are expected to be in the form of "/foo/bar".
28    pub fn from_path_strings(src: HashMap<String, V>) -> Self {
29        let iter = src.into_iter().map(|(k, v)| (key_from_path(&k), v));
30        Self::from_iter(iter)
31    }
32
33    /// Finds the most specific matched result based on the provided input path.  Does not
34    /// require an exact match of input path!  See [`MatchedResult`] for more information.
35    pub fn lookup(&self, path: &[String]) -> Option<MatchedResult<V>> {
36        for search_depth in (0..path.len() + 1).rev() {
37            let search_path = &path[0..search_depth];
38            if let Some(value) = self.map.get(search_path) {
39                return Some(MatchedResult {
40                    value,
41                    matched_index: search_depth,
42                });
43            }
44        }
45        None
46    }
47
48    /// Identical to `lookup` except that it doesn't stop once the most specific match has been
49    /// found, but rather returns all potential matches.  For example, if the input path is
50    /// "/foo/bar", and the matcher contains "/foo", "/foo/bar", "/baz", the result will be
51    /// matched results for "/foo" and "/foo/bar".
52    pub fn match_all(&self, path: &[String]) -> Vec<MatchedResult<V>> {
53        let mut result = Vec::new();
54        for search_depth in (0..path.len() + 1).rev() {
55            let search_path = &path[0..search_depth];
56            if let Some(value) = self.map.get(search_path) {
57                result.push(MatchedResult {
58                    value,
59                    matched_index: search_depth,
60                });
61            }
62        }
63        result
64    }
65
66    pub fn insert(&mut self, key: Vec<String>, value: V) -> Option<V> {
67        self.map.insert(key, value)
68    }
69
70    pub fn remove(&mut self, key: &[String]) -> Option<V> {
71        self.map.remove(key)
72    }
73
74    pub fn values(&self) -> Values<'_, Vec<String>, V> {
75        self.map.values()
76    }
77
78    pub fn lookup_exact(&self, path: &[String]) -> Option<&V> {
79        self.map.get(path)
80    }
81}
82
83pub fn key_from_path(path: &str) -> Vec<String> {
84    path.split('/')
85        .filter(|s| !s.is_empty())
86        .map(|s| s.to_string())
87        .collect()
88}
89
90/// Looked up value but also the index at which the match occurred so that the caller can determine
91/// how much of the input path was unmatched and considered "dangling".  For example, the input
92/// path could be `["foo","bar"]` but the match was for `["foo"]`.  The `matched_index` would be 1
93/// such that `&input[matched_index..]` would yield `["bar"]`.
94pub struct MatchedResult<'a, V> {
95    pub value: &'a V,
96    pub matched_index: usize,
97}
98
99#[cfg(test)]
100mod tests {
101    use crate::app::path_matcher::PathMatcher;
102
103    #[test]
104    fn test_unambiguous_exact_match() {
105        let matcher = new_matcher(["/a/b/c", "/a/b/d"]);
106        assert_exact_match(&matcher, "/a/b/c");
107        assert_exact_match(&matcher, "/a/b/d");
108    }
109
110    #[test]
111    fn test_ambiguous_match() {
112        let matcher = new_matcher(["/a/b/c", "/a/b/d"]);
113        assert_no_match(&matcher, "/a/b");
114    }
115
116    #[test]
117    fn test_inexact_match() {
118        let matcher = new_matcher(["/a/b/c"]);
119        assert_prefix_match(&matcher, "/a/b/c/d", "/a/b/c", "d");
120    }
121
122    fn new_matcher<const N: usize>(paths: [&str; N]) -> PathMatcher<String> {
123        let path_kv_pairs = paths.into_iter().map(|path| {
124            let key = path_to_vec(path);
125            let value = path.to_string();
126            (key, value)
127        });
128
129        PathMatcher::from_iter(path_kv_pairs)
130    }
131
132    fn assert_no_match(matcher: &PathMatcher<String>, path: &str) {
133        let paths = path_to_vec(path);
134        assert!(matcher.lookup(&paths).is_none());
135    }
136
137    fn assert_exact_match(matcher: &PathMatcher<String>, path: &str) {
138        assert_prefix_match(matcher, path, path, "");
139    }
140
141    fn assert_prefix_match(
142        matcher: &PathMatcher<String>,
143        path: &str,
144        expected_value: &str,
145        expected_suffix: &str,
146    ) {
147        let paths = path_to_vec(path);
148
149        let result = matcher.lookup(&paths);
150        let matched = result.unwrap_or_else(|| panic!("Expected {expected_value}"));
151        assert_eq!(matched.value, expected_value);
152
153        let actual_suffix = &paths[matched.matched_index..];
154        assert_eq!(actual_suffix, &path_to_vec(expected_suffix));
155    }
156
157    fn path_to_vec(path: &str) -> Vec<String> {
158        if path.is_empty() {
159            return vec![];
160        }
161        path.split('/').map(|p| p.to_string()).collect()
162    }
163}
coap_server/app/path_matcher.rs

coap_server/app/
path_matcher.rs
