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