frithu 0.1.0

use std::collections;
use std::rc;

#[derive(Clone, Debug, Default, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct StringCache(collections::BTreeSet<rc::Rc<str>>);

impl StringCache {
    pub fn new() -> StringCache {
        StringCache::default()
    }

    pub fn get_or_intern<S: Into<String>>(&mut self, query: S) -> rc::Rc<str> {
        let candidate_string = query.into();
        let candidate: rc::Rc<str> = candidate_string.into();

        if let Some(existing) = self.0.get(&candidate) {
            return existing.clone();
        }

        self.0.insert(candidate.clone());
        candidate
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn interning() {
        let mut cache = StringCache::new();

        // Create a string and intern it.
        let mut string1 = String::new();
        string1.push_str("a");
        string1.push_str("bc");

        // Create an equal string in a different way, so hopefully it will
        // have a different memory location and won't be optimized into
        // re-using string1.
        let mut string2 = String::new();
        string2.push_str("ab");
        string2.push_str("c");

        assert_ne!(
            &string1 as *const _ as usize,
            &string2 as *const _ as usize,
        );

        // Cache the two strings; they *should* be different.
        let ref1 = cache.get_or_intern(string1);
        let ref2 = cache.get_or_intern(string2);

        // Get the underlying pointers to make sure both refs are pointing
        // at the same memory location.
        let ptr1 = ref1.as_ptr() as usize;
        let ptr2 = ref2.as_ptr() as usize;

        assert_eq!(ptr1, ptr2);

        let ref3 = cache.get_or_intern("def");
        let ptr3 = ref3.as_ptr() as usize;

        // This new string should *not* be the same as the previous two.
        assert_ne!(ptr1, ptr3);
    }
}