fr_trie/
lib.rs

1//! A generic fuzzy compressed radix trie implementation.
2
3pub mod trie;
4pub mod key;
5pub mod node;
6pub mod matcher;
7pub mod iterator;
8pub mod glob;
9
10#[cfg(test)]
11mod tests {
12    use crate::trie::Trie;
13    use crate::glob::GlobMatcher;
14    use crate::glob::acl::{AclTrie, Acl, Permissions};
15
16    #[test]
17    fn functional_test() {
18
19        let mut trie = Trie::new();
20        let a = String::from("a");
21        let aa = String::from("aa");
22        let aaaa = String::from("aaaa");
23        let aabb = String::from("aabb");
24        let aacc = String::from("aacc");
25        let z = String::from("z");
26
27        trie.insert(z.clone(), z.clone());
28        trie.insert(aaaa.clone(), aaaa.clone());
29        trie.insert(aabb.clone(), aabb.clone());
30        trie.insert(aacc.clone(), aacc.clone());
31        trie.insert(a.clone(), a.clone());
32
33        trie.foreach(|tup| {
34            let indent= String::from_utf8(vec![b' '; tup.0 *3]).unwrap();
35            println!("{} {:?} = {:?}", indent, tup.1, tup.2);
36        });
37
38        trie.insert(aa.clone(), aa.clone());
39
40        trie.foreach(|tup| {
41            let indent= String::from_utf8(vec![b' '; tup.0 *3]).unwrap();
42            println!("{} {:?} = {:?}", indent, tup.1, tup.2);
43        });
44
45        assert_eq!(trie.get::<GlobMatcher>(&a).unwrap(), a);
46        assert_eq!(trie.get::<GlobMatcher>(&aaaa).unwrap(), aaaa);
47        assert_eq!(trie.get::<GlobMatcher>(&aabb).unwrap(), aabb);
48        assert_eq!(trie.get::<GlobMatcher>(&aacc).unwrap(), aacc);
49        assert_eq!(trie.get::<GlobMatcher>(&z).unwrap(), z);
50
51        let mut trie = AclTrie::new();
52
53        trie.insert(Acl::new("de"), Permissions::READ);
54        trie.insert(Acl::new("df"), Permissions::READ);
55
56        trie.insert(Acl::new("a"), Permissions::READ);
57        trie.insert(Acl::new("z"), Permissions::READ);
58        trie.insert(Acl::new("b"), Permissions::WRITE);
59        let x = trie.get::<GlobMatcher>(&Acl::new("b"));
60        assert_eq!(Permissions::WRITE, x.unwrap());
61
62        trie.insert(Acl::new("b"), Permissions::OWNER);
63        trie.insert(Acl::new("ab"), Permissions::READ);
64        trie.insert(Acl::new("aaa0a"), Permissions::READ);
65        trie.insert(Acl::new("aaa0b"), Permissions::READ);
66        trie.insert(Acl::new("ac"), Permissions::READ);
67        trie.insert(Acl::new("j1*"), Permissions::WRITE);
68        trie.insert(Acl::new("j0*t"), Permissions::all());
69        let x = trie.get::<GlobMatcher>(&Acl::new("j01t"));
70        assert_eq!(Permissions::all(), x.unwrap());
71        let x = trie.get::<GlobMatcher>(&Acl::new("j1zz"));
72        assert_eq!(Permissions::WRITE, x.unwrap());
73
74        let x = trie.get::<GlobMatcher>(&Acl::new("b"));
75        assert_eq!(Permissions::OWNER, x.unwrap());
76        trie.insert(Acl::new("be"), Permissions::READ);
77        trie.insert(Acl::new("bf"), Permissions::READ);
78
79        let x = trie.get::<GlobMatcher>(&Acl::new("b"));
80        assert_eq!(Permissions::OWNER, x.unwrap());
81
82        trie.insert(Acl::new("ba"), Permissions::READ);
83        trie.insert(Acl::new("aaaab"), Permissions::WRITE);
84
85        trie.foreach(|tup| -> () {
86            let indent= String::from_utf8(vec![b' '; tup.0 *3]).unwrap();
87            println!("{} {} = {:?}", indent, tup.1, tup.2);
88        });
89
90        let x = trie.get::<GlobMatcher>(&Acl::new("aaaab"));
91        assert_eq!(Permissions::WRITE, x.unwrap());
92
93        let x = trie.get::<GlobMatcher>(&Acl::new("aaaabb"));
94        assert!(x.is_none());
95
96        let mut trie = AclTrie::new();
97        trie.insert(Acl::new("abc"), Permissions::WRITE);
98        trie.insert(Acl::new("a*"), Permissions::READ);
99        trie.insert(Acl::new("ax*"), Permissions::CREATE);
100
101        let x = trie.get_merge::<GlobMatcher>(&Acl::new("axy"));
102        assert!(x.is_some());
103        assert_eq!(Permissions::READ | Permissions::CREATE, x.unwrap());
104
105        let mut trie = AclTrie::new();
106        trie.insert(Acl::new("/path/*"), Permissions::READ);
107        trie.insert(Acl::new("/path/to/resource"), Permissions::WRITE);
108
109        // Multiget example 1
110        let result = trie.get_merge::<GlobMatcher>(&Acl::new("/path/to/anything"));
111        if let Some(value) = result {
112            if value == Permissions::READ {
113                println!("Expecting /path/* wilcard key is accessed");
114            }
115        }
116
117        // Multiget example 2
118        let result = trie.get_merge::<GlobMatcher>(&Acl::new("/path/to/resource"));
119        if let Some(value) = result {
120            if value == (Permissions::READ | Permissions::WRITE) {
121                println!("Expecting both /path/* wilcard key and /path/to/resource is accessed");
122            }
123        }
124
125        // Dump trie structure
126        trie.foreach(|tup| {
127            let indent= String::from_utf8(vec![b' '; tup.0 *3]).unwrap();
128            println!("{} {} = {:?}", indent, tup.1, tup.2);
129        });
130    }
131
132    #[test]
133    fn bugfix_test() {
134
135        let mut trie = AclTrie::new();
136        trie.insert(Acl::new("/path/*"), Permissions::READ);
137        trie.insert(Acl::new("/path/to/resource"), Permissions::WRITE);
138
139        let x = trie.get_merge::<GlobMatcher>(&Acl::new("/path/other"));
140        assert!(x.is_some());
141        assert_eq!(Permissions::READ, x.unwrap());
142
143        let x = trie.get_merge::<GlobMatcher>(&Acl::new("/path/to/resourc"));
144        assert!(x.is_some());
145        assert_eq!(Permissions::READ, x.unwrap());
146
147        let x = trie.get_merge::<GlobMatcher>(&Acl::new("/path/to/resource"));
148        assert!(x.is_some());
149        assert_eq!(Permissions::READ | Permissions::WRITE, x.unwrap());
150
151        let mut trie = AclTrie::new();
152        trie.insert(Acl::new("abc"), Permissions::WRITE);
153        trie.insert(Acl::new("a*"), Permissions::READ);
154
155        let x = trie.get::<GlobMatcher>(&Acl::new("ax"));
156        assert!(x.is_some());
157        assert_eq!(Permissions::READ, x.unwrap());
158
159        let mut trie = AclTrie::new();
160        trie.insert(Acl::new("abc"), Permissions::WRITE);
161        trie.insert(Acl::new("a*"), Permissions::READ);
162
163        let x = trie.get::<GlobMatcher>(&Acl::new("a/x"));
164        assert!(x.is_some());
165        assert_eq!(Permissions::READ, x.unwrap());
166    }
167
168    #[test]
169    fn serde_test() {
170        let mut trie = AclTrie::new();
171        trie.insert(Acl::new("aaaa"), Permissions::empty());
172        trie.insert(Acl::new("aaaa"), Permissions::all());
173        trie.insert(Acl::new("aabb"), Permissions::READ);
174        trie.insert(Acl::new("t"), Permissions::READ);
175        assert!(trie.get::<GlobMatcher>(&Acl::new("a")).is_none());
176        assert!(trie.get::<GlobMatcher>(&Acl::new("z")).is_none());
177        assert!(trie.get::<GlobMatcher>(&Acl::new("aaaaaaaaaa")).is_none());
178
179        let serialized_string = serde_json::ser::to_string_pretty(&trie).unwrap();
180        let other_trie = serde_json::de::from_str::<AclTrie>(&serialized_string).unwrap();
181        match other_trie.get::<GlobMatcher>(&Acl::new("aaaa")) {
182            None => assert!(false, "key not found after deserialization"),
183            Some(result) => {
184                assert_eq!(result, Permissions::all());
185            }
186        }
187        let serialized_bytes = bincode::serialize(&other_trie).unwrap();
188        let another_trie = bincode::deserialize::<AclTrie>(&serialized_bytes).unwrap();
189        assert!(another_trie.get::<GlobMatcher>(&Acl::new("aabbcc")).is_none());
190    }
191}
fr_trie/lib.rs

fr_trie/
lib.rs
