ketos/
rc_vec.rs

1//! Implements a reference-counted `Vec` supporting efficient subslicing.
2
3use std::borrow::Cow;
4use std::cmp::Ordering;
5use std::ffi::OsStr;
6use std::fmt;
7use std::ops;
8use std::path::Path;
9use std::rc::Rc;
10use std::slice::Iter;
11
12// A duplicate of `collections::range::RangeArgument`, which is unstable.
13/// Argument for functions accepting a range
14pub trait RangeArgument<T> {
15    /// Returns start value
16    fn start(&self) -> Option<&T> { None }
17    /// Returns end value
18    fn end(&self) -> Option<&T> { None }
19}
20
21impl<T> RangeArgument<T> for ops::RangeFull {}
22impl<T> RangeArgument<T> for ops::Range<T> {
23    fn start(&self) -> Option<&T> { Some(&self.start) }
24    fn end(&self) -> Option<&T> { Some(&self.end) }
25}
26impl<T> RangeArgument<T> for ops::RangeFrom<T> {
27    fn start(&self) -> Option<&T> { Some(&self.start) }
28}
29impl<T> RangeArgument<T> for ops::RangeTo<T> {
30    fn end(&self) -> Option<&T> { Some(&self.end) }
31}
32
33/// Represents a reference-counted view into a `String`.
34/// Subslices may be created which will share the underlying data buffer.
35#[derive(Clone)]
36pub struct RcString {
37    data: Rc<String>,
38    start: usize,
39    end: usize,
40}
41
42impl RcString {
43    /// Constructs a new `RcString` from a `String`.
44    pub fn new(data: String) -> RcString {
45        let n = data.len();
46
47        RcString{
48            data: Rc::new(data),
49            start: 0,
50            end: n,
51        }
52    }
53
54    /// Returns whether the visible slice is empty.
55    pub fn is_empty(&self) -> bool {
56        self.start == self.end
57    }
58
59    /// Returns the length of the visible slice.
60    pub fn len(&self) -> usize {
61        self.end - self.start
62    }
63
64    /// Returns a subslice of the `RcString`.
65    pub fn slice<R: RangeArgument<usize>>(&self, range: R) -> RcString {
66        let start = range.start().map_or(0, |v| *v);
67        let end = range.end().map_or(self.len(), |v| *v);
68
69        let a = self.start + start;
70        let b = self.start + end;
71
72        if a > self.end {
73            panic!("RcString slice out of bounds; start is {} but length is {}",
74                start, self.len());
75        }
76
77        if b > self.end {
78            panic!("RcString slice out of bounds; end is {} but length is {}",
79                end, self.len());
80        }
81
82        if !self.data.is_char_boundary(a) || !self.data.is_char_boundary(b) {
83            panic!("index {} and/or {} in RcString `{}` do not lie on \
84                character boundary", a, b, &self[..]);
85        }
86
87        RcString{
88            data: self.data.clone(),
89            start: a,
90            end: b,
91        }
92    }
93
94    /// Consumes the `RcString` and returns a `String`.
95    pub fn into_string(self) -> String {
96        match Rc::try_unwrap(self.data) {
97            Ok(mut s) => {
98                let _ = s.drain(self.end..);
99                let _ = s.drain(..self.start);
100                s
101            }
102            Err(data) => data[self.start..self.end].to_owned()
103        }
104    }
105
106    /// Pushes a `char` to the end of the contained `String`.
107    pub fn push(&mut self, ch: char) {
108        self.make_mut().push(ch);
109        self.end += ch.len_utf8();
110    }
111
112    /// Pushes a `&str` to the end of the contained `String`.
113    pub fn push_str(&mut self, s: &str) {
114        self.make_mut().push_str(s);
115        self.end += s.len();
116    }
117
118    fn make_mut(&mut self) -> &mut String {
119        let s = Rc::make_mut(&mut self.data);
120
121        let _ = s.drain(self.end..);
122        let _ = s.drain(..self.start);
123        let n = s.len();
124
125        self.start = 0;
126        self.end = n;
127
128        s
129    }
130}
131
132impl AsRef<str> for RcString {
133    fn as_ref(&self) -> &str {
134        &self.data[self.start..self.end]
135    }
136}
137
138impl AsRef<[u8]> for RcString {
139    fn as_ref(&self) -> &[u8] {
140        AsRef::<str>::as_ref(self).as_ref()
141    }
142}
143
144impl AsRef<Path> for RcString {
145    fn as_ref(&self) -> &Path {
146        AsRef::<str>::as_ref(self).as_ref()
147    }
148}
149
150impl AsRef<OsStr> for RcString {
151    fn as_ref(&self) -> &OsStr {
152        AsRef::<str>::as_ref(self).as_ref()
153    }
154}
155
156impl ops::Deref for RcString {
157    type Target = str;
158
159    fn deref(&self) -> &str {
160        self.as_ref()
161    }
162}
163
164impl ops::DerefMut for RcString {
165    fn deref_mut(&mut self) -> &mut str {
166        self.make_mut()
167    }
168}
169
170impl fmt::Debug for RcString {
171    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
172        fmt::Debug::fmt(&self[..], f)
173    }
174}
175
176impl fmt::Display for RcString {
177    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
178        fmt::Display::fmt(&self[..], f)
179    }
180}
181
182macro_rules! impl_eq_str {
183    ( $lhs:ty, $rhs:ty ) => {
184        impl<'a> PartialEq<$rhs> for $lhs {
185            fn eq(&self, rhs: &$rhs) -> bool { self[..] == rhs[..] }
186        }
187    }
188}
189
190impl_eq_str!{ RcString, RcString }
191impl_eq_str!{ RcString, String }
192impl_eq_str!{ RcString, str }
193impl_eq_str!{ RcString, &'a str }
194impl_eq_str!{ RcString, Cow<'a, str> }
195
196impl Eq for RcString {}
197
198impl PartialOrd for RcString {
199    fn partial_cmp(&self, rhs: &RcString) -> Option<Ordering> { self[..].partial_cmp(&rhs[..]) }
200
201    fn lt(&self, rhs: &RcString) -> bool { self[..] < rhs[..] }
202    fn le(&self, rhs: &RcString) -> bool { self[..] <= rhs[..] }
203    fn gt(&self, rhs: &RcString) -> bool { self[..] > rhs[..] }
204    fn ge(&self, rhs: &RcString) -> bool { self[..] >= rhs[..] }
205}
206
207impl Ord for RcString {
208    fn cmp(&self, rhs: &RcString) -> Ordering { self[..].cmp(&rhs[..]) }
209}
210
211impl<'a> From<&'a str> for RcString {
212    fn from(s: &str) -> RcString {
213        RcString::new(s.to_owned())
214    }
215}
216
217impl From<String> for RcString {
218    fn from(s: String) -> RcString {
219        RcString::new(s)
220    }
221}
222
223/// Represents a reference-counted view into a `Vec`.
224/// Subslices may be created which will share the underlying data buffer.
225#[derive(Clone)]
226pub struct RcVec<T> {
227    data: Rc<Vec<T>>,
228    start: usize,
229    end: usize,
230}
231
232impl<T> RcVec<T> {
233    /// Constructs a new `RcVec` from a `Vec`.
234    pub fn new(data: Vec<T>) -> RcVec<T> {
235        let n = data.len();
236
237        RcVec{
238            data: Rc::new(data),
239            start: 0,
240            end: n,
241        }
242    }
243
244    /// Returns whether the `RcVec` is empty.
245    pub fn is_empty(&self) -> bool {
246        self.start == self.end
247    }
248
249    /// Returns the number of elements visible to the `RcVec`.
250    pub fn len(&self) -> usize {
251        self.end - self.start
252    }
253
254    /// Returns a subslice of the `RcVec`, with the range being relative
255    /// to this slice's boundaries.
256    pub fn slice<R: RangeArgument<usize>>(&self, range: R) -> RcVec<T> {
257        let start = range.start().map_or(0, |v| *v);
258        let end = range.end().map_or(self.len(), |v| *v);
259
260        let a = self.start + start;
261        let b = self.start + end;
262
263        if a > self.end {
264            panic!("RcVec slice out of bounds; start is {} but length is {}",
265                start, self.len());
266        }
267
268        if b > self.end {
269            panic!("RcVec slice out of bounds; end is {} but length is {}",
270                end, self.len());
271        }
272
273        RcVec{
274            data: self.data.clone(),
275            start: a,
276            end: b,
277        }
278    }
279}
280
281impl<T: Clone> RcVec<T> {
282    /// Consumes the `RcVec` and returns the contained `Vec`.
283    /// This will clone the contained values unless the data was uniquely held.
284    pub fn into_vec(self) -> Vec<T> {
285        match Rc::try_unwrap(self.data) {
286            Ok(mut v) => {
287                let _ = v.drain(self.end..);
288                let _ = v.drain(..self.start);
289                v
290            }
291            Err(data) => data[self.start..self.end].to_vec()
292        }
293    }
294
295    /// Makes wrapped data unique and returns a mutable reference,
296    /// after adjusting `start` and `end` fields.
297    ///
298    /// # Note
299    ///
300    /// If the length of the `Vec` is modified, the `end` field of `RcVec`
301    /// must be adjusted manually. That's why this method is private.
302    fn make_mut(&mut self) -> &mut Vec<T> {
303        let v = Rc::make_mut(&mut self.data);
304
305        let _ = v.drain(self.end..);
306        let _ = v.drain(..self.start);
307        let n = v.len();
308
309        self.start = 0;
310        self.end = n;
311
312        v
313    }
314
315    /// Pushes a value into the contained `Vec`.
316    pub fn push(&mut self, t: T) {
317        self.make_mut().push(t);
318        self.end += 1;
319    }
320}
321
322impl<T> AsRef<[T]> for RcVec<T> {
323    fn as_ref(&self) -> &[T] {
324        &self.data[self.start..self.end]
325    }
326}
327
328impl<T> ops::Deref for RcVec<T> {
329    type Target = [T];
330
331    fn deref(&self) -> &[T] {
332        self.as_ref()
333    }
334}
335
336impl<T: Clone> ops::DerefMut for RcVec<T> {
337    fn deref_mut(&mut self) -> &mut [T] {
338        self.make_mut()
339    }
340}
341
342impl<T: fmt::Debug> fmt::Debug for RcVec<T> {
343    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
344        fmt::Debug::fmt(&self[..], f)
345    }
346}
347
348impl<T: Clone> Extend<T> for RcVec<T> {
349    fn extend<I>(&mut self, iterable: I) where I: IntoIterator<Item=T> {
350        self.make_mut().extend(iterable);
351        self.end = self.data.len();
352    }
353}
354
355impl<'a, T: Clone> Extend<&'a T> for RcVec<T> where T: Copy + 'a {
356    fn extend<I>(&mut self, iterable: I) where I: IntoIterator<Item=&'a T> {
357        self.make_mut().extend(iterable);
358        self.end = self.data.len();
359    }
360}
361
362impl<'a, T> IntoIterator for &'a RcVec<T> {
363    type Item = &'a T;
364    type IntoIter = Iter<'a, T>;
365
366    fn into_iter(self) -> Iter<'a, T> {
367        self.iter()
368    }
369}
370
371macro_rules! impl_eq_vec {
372    ( $lhs:ty, $rhs:ty ) => {
373        impl<'a, A, B> PartialEq<$rhs> for $lhs where A: PartialEq<B> {
374            fn eq(&self, rhs: &$rhs) -> bool { self[..] == rhs[..] }
375        }
376    }
377}
378
379macro_rules! impl_eq_array {
380    ( $( $n:expr )+ ) => {
381        $(
382            impl<A, B> PartialEq<[B; $n]> for RcVec<A> where A: PartialEq<B> {
383                fn eq(&self, rhs: &[B; $n]) -> bool { self[..] == rhs[..] }
384            }
385
386            impl<'a, A, B> PartialEq<&'a [B; $n]> for RcVec<A> where A: PartialEq<B> {
387                fn eq(&self, rhs: &&'a [B; $n]) -> bool { self[..] == rhs[..] }
388            }
389        )+
390    }
391}
392
393impl_eq_vec!{ RcVec<A>, RcVec<B> }
394impl_eq_vec!{ RcVec<A>, Vec<B> }
395impl_eq_vec!{ RcVec<A>, [B] }
396impl_eq_vec!{ RcVec<A>, &'a [B] }
397
398impl_eq_array!{
399    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
400    17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
401}
402
403impl<T: Eq> Eq for RcVec<T> {}
404
405impl<T: PartialOrd> PartialOrd for RcVec<T> {
406    fn partial_cmp(&self, rhs: &RcVec<T>) -> Option<Ordering> { self[..].partial_cmp(&rhs[..]) }
407
408    fn lt(&self, rhs: &RcVec<T>) -> bool { self[..] < rhs[..] }
409    fn le(&self, rhs: &RcVec<T>) -> bool { self[..] <= rhs[..] }
410    fn gt(&self, rhs: &RcVec<T>) -> bool { self[..] > rhs[..] }
411    fn ge(&self, rhs: &RcVec<T>) -> bool { self[..] >= rhs[..] }
412}
413
414impl<T: Ord> Ord for RcVec<T> {
415    fn cmp(&self, rhs: &RcVec<T>) -> Ordering { self[..].cmp(&rhs[..]) }
416}
417
418impl<T> From<Vec<T>> for RcVec<T> {
419    fn from(v: Vec<T>) -> RcVec<T> {
420        RcVec::new(v)
421    }
422}
423
424#[cfg(test)]
425mod test {
426    use super::{RcString, RcVec};
427
428    #[test]
429    fn test_rc_string() {
430        let a = RcString::from("foobar");
431        let mut b = a.slice(1..4);
432        let mut c = a.clone();
433
434        assert_eq!(a.data.as_ptr(), b.data.as_ptr());
435        assert_eq!(a, "foobar");
436        assert_eq!(b, "oob");
437        assert_eq!(b.is_empty(), false);
438        assert_eq!(b.len(), 3);
439
440        b.push('x');
441        assert_eq!(b, "oobx");
442
443        c.push_str("lol");
444        assert_eq!(c.into_string(), "foobarlol");
445    }
446
447    #[test]
448    #[should_panic]
449    fn test_rc_string_error() {
450        let a = RcString::from("foo\u{2022}");
451        let _b = a.slice(2..4);
452    }
453
454    #[test]
455    fn test_rc_vec() {
456        let a = RcVec::new(vec![1, 2, 3]);
457        let mut b = a.slice(1..3);
458        let mut c = a.clone();
459
460        assert_eq!(a.data.as_ptr(), b.data.as_ptr());
461        assert_eq!(a, [1, 2, 3]);
462        assert_eq!(b, [2, 3]);
463        assert_eq!(b.is_empty(), false);
464        assert_eq!(b.len(), 2);
465
466        b.push(4);
467        assert_eq!(b, [2, 3, 4]);
468
469        c.extend(&[4, 5, 6]);
470        assert_eq!(c.into_vec(), [1, 2, 3, 4, 5, 6]);
471    }
472}
ketos/rc_vec.rs

ketos/
rc_vec.rs
