namespace/lib.rs
1//! A namespace looks like `abc::def::ghi`.
2//!
3//! Namespaces are more subtle than one would naively assume. For namespaces to be genuinely
4//! extensible, they cannot know anything beyond their scope. This means that they don't have an
5//! absolute index. They can be positioned relative to another namespace only by a 'sliding'
6//! match. This matching can potentially be ambiguous, so if multiple matches occur an error is
7//! returned. Namespaces can never be empty.
8
9use std::cmp::Ordering;
10use std::fmt;
11use std::ops::Index;
12
13// Separator
14// The separator length is fixed at 2.
15
16const SEP1: char = ':';
17const SEP2: char = ':';
18
19#[derive(Debug, PartialEq)]
20pub enum NSErr {
21 Parse(String, usize),
22 NoMatch,
23 NoRemainder,
24 MultipleMatch,
25 Remove,
26 OutOfBounds,
27}
28
29impl fmt::Display for NSErr {
30 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
31 match self {
32 NSErr::Parse(s, pos) => write!(f, "Could not parse \"{}\" at position {}.", s, pos),
33 NSErr::NoMatch => write!(f, "No match."),
34 NSErr::MultipleMatch => write!(f, "Multiple matches."),
35 NSErr::Remove => write!(f, "Removed too many segments."),
36 NSErr::NoRemainder => write!(f, "No remainder."),
37 NSErr::OutOfBounds => write!(f, "Index out of bounds."),
38 }
39 }
40}
41
42
43// Parser state.
44enum PS {
45 SegmentStart,
46 Segment,
47 Separator,
48}
49
50// To work with a Namespace we can use an iterator of of `Slice`s into `s`.
51// These are generated by the `Iterator`'s `next()` function.
52//
53/// `Namespace` cannot be empty. It always contains at least one segment.
54///
55#[derive(Clone, Hash)]
56pub struct Namespace {
57 // Contains the string passed in by new() with separators removed.
58 pub s: String,
59
60 // Contains usize pointers into the Vec representation of s.
61 pub segments: Vec<usize>,
62}
63
64impl Namespace {
65
66 /// ```
67 /// let ns = Namespace::new("a::b::c").unwrap();
68 /// ```
69 ///
70 pub fn new(s: &str) -> Result<Self, NSErr> {
71 let mut parser_state = PS::SegmentStart;
72 let mut leftpos = 0usize;
73 let mut segments: Vec<usize> = Vec::new();
74
75 for (pos, ch) in s.char_indices() {
76 match (&parser_state, ch) {
77
78 (_, '\n') => {
79 return Err(NSErr::Parse(s.to_string(), pos))
80 },
81
82 (PS::SegmentStart, SEP1) => {
83 return Err(NSErr::Parse(s.to_string(), pos))
84 },
85
86 // Required if SEP2 != SEP1
87 //
88 // (PS::SegmentStart, SEP2) => {
89 // return Err(NSErr::Parse(s.to_string(), pos))
90 // },
91
92 (PS::SegmentStart, ch) => {
93 if ch.is_whitespace() {
94 return Err(NSErr::Parse(s.to_string(), pos));
95 } else {
96 leftpos = pos;
97 parser_state = PS::Segment;
98 }
99 },
100
101 // First ':' in separator.
102 (PS::Segment, SEP1) => {
103 parser_state = PS::Separator;
104 },
105
106 (PS::Segment, _) => {},
107
108 // Second ':' in separator.
109 (PS::Separator, SEP2) => {
110 segments.push(leftpos);
111 leftpos = pos + 1;
112 parser_state = PS::SegmentStart;
113 },
114
115 (PS::Separator, _) => {
116 return Err(NSErr::Parse(s.to_string(), pos))
117 },
118 }
119 }
120 // Save last segment.
121 match parser_state {
122 PS::Segment => { segments.push(leftpos) },
123 _ => { return Err(NSErr::Parse(s.to_string(), s.len())) },
124 };
125 Ok(Namespace {
126 s: s.to_string(),
127 segments: segments,
128 })
129 }
130
131
132 /// Returns the number of segments.
133 ///
134 pub fn len(&self) -> usize {
135 self.segments.len()
136 }
137
138 /// Appends a new namespace to the end of `Self`. For example,
139 ///
140 /// ```
141 /// let ns1 = Namespace::new("a::b").unwrap();
142 /// let ns2 = Namespace::new("b::c").unwrap();
143 /// let ns = ns1.append(&ns2);
144 ///
145 /// assert!(ns, "a::b::b::c");
146 /// ```
147 pub fn append(&self, other: &Namespace) -> Namespace {
148
149 // Append strings.
150 let mut s = self.s.clone();
151 s.push(SEP1);
152 s.push(SEP2);
153 s.push_str(&other.s);
154
155 let mut segs = self.segments.clone();
156 for n in other.segments.clone().iter() {
157 segs.push(n + self.s.len() + 2)
158 }
159
160 Namespace {
161 s: s,
162 segments: segs,
163 }
164 }
165
166 /// Appends a new namespace at index. Returns an error if the `n > self.len()`.
167 ///
168 /// ```rust
169 /// let ns1 = Namespace::new("a::b::c").unwrap();
170 /// let ns2 = Namespace::new("d").unwrap();
171 /// assert_eq!(ns1.append_at(&ns2, 1), "a::d");
172 /// ```
173 pub fn append_at(&self, other: &Namespace, n: usize) -> Result<Namespace, NSErr> {
174 if n > self.len() {
175 Err(NSErr::OutOfBounds)
176 } else if n == 0 {
177 Ok(other.clone())
178 } else {
179 Ok(self.truncate(n).unwrap().append(other))
180 }
181 }
182
183 /// Remove `n` segments from the right-hand side of `Self`. Namespaces cannot be empty so
184 /// returns an error if all segments are removed.
185 ///
186 /// ```rust
187 /// assert_eq!(
188 /// Namespace::new("a::b::c").unwrap()
189 /// .remove(2)
190 /// .unwrap()
191 /// .to_string(),
192 /// "a"
193 /// );
194 /// ```
195 ///
196 pub fn remove(&self, n: usize) -> Result<Namespace, NSErr> {
197 if n == 0 {
198 // No-op.
199 Ok(self.clone())
200 } else if n < self.len() {
201 let segs = self.len() - 1 - n;
202 Ok(Namespace {
203 s: self.s[0..(self.segments[segs + 1] - 2)].to_string(),
204 segments: self.segments[0..=segs].to_vec(),
205 })
206 } else {
207 Err(NSErr::Remove)
208 }
209 }
210
211 /// Truncate the namespace to the first `n` segments. In other words truncate to length `n`.
212 /// Returns an error if `n > self.len()`.
213 ///
214 pub fn truncate(&self, n: usize) -> Result<Namespace, NSErr> {
215 let out = self.clone();
216 if n == 0 || n > self.len() {
217 Err(NSErr::OutOfBounds)
218 } else {
219 out.remove(self.len() - n)
220 }
221 }
222
223 /// Tries to find a sliding match. Returns the index of the position in self aligned to the
224 /// first segment of other. Note that this value can be negative. If there are no matches
225 /// returns an empty `Vec`.
226 ///
227 /// ```rust
228 /// let ns1 = Namespace::new("a::b::c").unwrap();
229 /// let ns2 = Namespace::new("c::d").unwrap();
230 /// assert_eq!(
231 /// ns1.sliding_match(&ns),
232 /// vec!(2)
233 /// );
234 /// ```
235 ///
236 pub fn sliding_match(&self, other: &Namespace) -> Vec<isize> {
237 let slen = self.len() as isize;
238 let olen = other.len() as isize;
239
240 let mut v: Vec<isize> = Vec::with_capacity(slen.max(olen) as usize);
241
242 for offset in (0 - olen + 1)..slen {
243 if self.offset_match(other, offset) { v.push(offset) }
244 };
245 v
246 }
247
248 /// The offset is the index of the position in self aligned to the first segment of other.
249 /// Returns true if all aligned segments match.
250 ///
251 pub fn offset_match(&self, other: &Namespace, offset: isize) -> bool {
252 // ls rs
253 // v v
254 // self [ ]
255 // other [ ]
256 // ^ ^
257 // lo ro
258 let ls = 0;
259 let rs = self.len() as isize;
260 let lo = offset;
261 let ro = other.len() as isize + offset;
262
263 for i in ls.max(lo)..rs.min(ro) {
264 if self[i as usize] != other[(i - offset) as usize] { return false }
265 };
266 true
267 }
268
269 #[test]
270 fn test_sliding_match() {
271 let ns = Namespace::new("a::b::c").unwrap();
272
273 let other = Namespace::new("c::b::a").unwrap();
274 assert_eq!(
275 ns.sliding_match(&other)[1],
276 2
277 );
278
279 let other = Namespace::new("a").unwrap();
280 assert_eq!(
281 ns.sliding_match(&other)[0],
282 0
283 );
284
285 let other = Namespace::new("a::b::c").unwrap();
286 assert_eq!(
287 ns.sliding_match(&other)[0],
288 0
289 );
290
291 let other = Namespace::new("x::y").unwrap();
292 assert!(
293 ns.sliding_match(&other).is_empty()
294 );
295 }
296
297 /// Returns the remainder of `other`. If there is no match, multiple matches or no remainder,
298 /// returns an error.
299 ///
300 /// ```rust
301 /// let ns1 = Namespace::new("a::b::c").unwrap();
302 /// let ns2 = Namespace::new("c::d::e").unwrap();
303 /// assert_eq!(
304 /// ns.remainder(&ns2).unwrap().to_string(),
305 /// "d::e"
306 /// );
307 /// ```
308 pub fn remainder(&self, other: &Namespace) -> Result<Namespace, NSErr> {
309 let offset = check_unique(&self.sliding_match(&other))?;
310
311 // The only valid condition is:
312 //
313 // offset
314 // | other.len()
315 // v |
316 // self: [ ] v
317 // other: [ ]
318 // ^
319 // |
320 // rem_ix
321 //
322 if offset + other.len() as isize > self.len() as isize {
323 let rem_ix = self.len() - offset as usize;
324 Ok(
325 Namespace {
326 s: String::from(&other.s[other.segments[rem_ix]..]),
327 segments: other.segments[rem_ix..].to_vec(),
328 }
329 )
330 } else {
331 Err(NSErr::NoRemainder)
332 }
333 }
334
335 /// If there is a unique sliding_match, returns `self` appended with the the remainder of
336 /// `other`, otherwise returns an error.
337 ///
338 /// ```rust
339 /// let ns = Namespace::new("a::b").unwrap();
340 /// let other = Namespace::new("b::c").unwrap();
341 /// ns.sliding_join(&other);
342 /// assert_eq!(
343 /// ns.sliding_join(&other).unwrap().to_string(),
344 /// "a::b::c",
345 /// );
346 /// ```
347 ///
348 pub fn sliding_join(&self, other: &Namespace) -> Result<Namespace, NSErr> {
349 let ns = self.clone();
350 Ok(ns.append(&self.remainder(other)?))
351 }
352
353 pub fn iter(&self) -> NamespaceIter {
354 NamespaceIter {
355 ns: &self,
356 index: 0usize,
357 }
358 }
359}
360
361impl Index<usize> for Namespace {
362 type Output = str;
363
364 fn index(&self, n: usize) -> &Self::Output {
365 match n.cmp(&(self.segments.len() - 1)) {
366 Ordering::Less => &self.s[self.segments[n]..self.segments[n + 1] - 2],
367 Ordering::Equal => &self.s[self.segments[n]..],
368 Ordering::Greater => panic!("Index on Namespace out of bounds."),
369 }
370 }
371}
372
373#[test]
374fn test_index_1() {
375 let ns = Namespace::new("a::bc::d").unwrap();
376 assert_eq!(
377 ns[0],
378 "a"
379 );
380}
381
382pub struct NamespaceIter<'a> {
383 ns: &'a Namespace,
384 index: usize,
385}
386
387// Think implement a whole lot of functions<&Segment> for Namespace.
388
389impl<'a> Iterator for NamespaceIter<'a> {
390 type Item = &'a str;
391
392 fn next(&mut self) -> Option<Self::Item> {
393 let i = self.index;
394 self.index += 1;
395
396 if i < self.ns.len() {
397 Some(&self.ns[i])
398 } else {
399 None
400 }
401 }
402}
403
404impl fmt::Display for Namespace {
405 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
406 write!(f, "{}", self.s)
407 }
408}
409
410impl fmt::Debug for Namespace {
411 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
412 write!(f, "{}", self.to_string())
413 }
414}
415
416// If namespaces are not the same length returns false
417impl PartialEq for Namespace {
418 fn eq(&self, other: &Namespace) -> bool {
419 self.s == other.s
420 }
421}
422
423impl Eq for Namespace {}
424
425// Supplement to slide_match() which checks that there is only one match, otherwise returns an
426// error.
427fn check_unique(v: &Vec<isize>) -> Result<isize, NSErr> {
428 match v.len() {
429 0 => Err(NSErr::NoMatch),
430 1 => Ok(v[0]),
431 _ => Err(NSErr::MultipleMatch),
432 }
433}
434