src/libsyntax/symbol.rs

   1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! An "interner" is a data structure that associates values with usize tags and
  12 //! allows bidirectional lookup; i.e. given a value, one can easily find the
  13 //! type, and vice versa.
  14
  15 use serialize::{Decodable, Decoder, Encodable, Encoder};
  16 use std::cell::RefCell;
  17 use std::collections::HashMap;
  18 use std::fmt;
  19
  20 /// A symbol is an interned or gensymed string.
  21 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
  22 pub struct Symbol(u32);
  23
  24 // The interner in thread-local, so `Symbol` shouldn't move between threads.
  25 impl !Send for Symbol { }
  26
  27 impl Symbol {
  28     /// Maps a string to its interned representation.
  29     pub fn intern(string: &str) -> Self {
  30         with_interner(|interner| interner.intern(string))
  31     }
  32
  33     /// gensym's a new usize, using the current interner.
  34     pub fn gensym(string: &str) -> Self {
  35         with_interner(|interner| interner.gensym(string))
  36     }
  37
  38     pub fn as_str(self) -> InternedString {
  39         with_interner(|interner| unsafe {
  40             InternedString {
  41                 string: ::std::mem::transmute::<&str, &str>(interner.get(self))
  42             }
  43         })
  44     }
  45
  46     pub fn as_u32(self) -> u32 {
  47         self.0
  48     }
  49 }
  50
  51 impl fmt::Debug for Symbol {
  52     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  53         write!(f, "{}({})", self, self.0)
  54     }
  55 }
  56
  57 impl fmt::Display for Symbol {
  58     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  59         fmt::Display::fmt(&self.as_str(), f)
  60     }
  61 }
  62
  63 impl Encodable for Symbol {
  64     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
  65         s.emit_str(&self.as_str())
  66     }
  67 }
  68
  69 impl Decodable for Symbol {
  70     fn decode<D: Decoder>(d: &mut D) -> Result<Symbol, D::Error> {
  71         Ok(Symbol::intern(&d.read_str()?))
  72     }
  73 }
  74
  75 impl<'a> PartialEq<&'a str> for Symbol {
  76     fn eq(&self, other: &&str) -> bool {
  77         *self.as_str() == **other
  78     }
  79 }
  80
  81 #[derive(Default)]
  82 pub struct Interner {
  83     names: HashMap<Box<str>, Symbol>,
  84     strings: Vec<Box<str>>,
  85 }
  86
  87 impl Interner {
  88     pub fn new() -> Self {
  89         Interner::default()
  90     }
  91
  92     fn prefill(init: &[&str]) -> Self {
  93         let mut this = Interner::new();
  94         for &string in init {
  95             this.intern(string);
  96         }
  97         this
  98     }
  99
 100     pub fn intern(&mut self, string: &str) -> Symbol {
 101         if let Some(&name) = self.names.get(string) {
 102             return name;
 103         }
 104
 105         let name = Symbol(self.strings.len() as u32);
 106         let string = string.to_string().into_boxed_str();
 107         self.strings.push(string.clone());
 108         self.names.insert(string, name);
 109         name
 110     }
 111
 112     fn gensym(&mut self, string: &str) -> Symbol {
 113         let gensym = Symbol(self.strings.len() as u32);
 114         // leave out of `names` to avoid colliding
 115         self.strings.push(string.to_string().into_boxed_str());
 116         gensym
 117     }
 118
 119     pub fn get(&self, name: Symbol) -> &str {
 120         &self.strings[name.0 as usize]
 121     }
 122 }
 123
 124 // In this macro, there is the requirement that the name (the number) must be monotonically
 125 // increasing by one in the special identifiers, starting at 0; the same holds for the keywords,
 126 // except starting from the next number instead of zero.
 127 macro_rules! declare_keywords {(
 128     $( ($index: expr, $konst: ident, $string: expr) )*
 129 ) => {
 130     pub mod keywords {
 131         use ast;
 132         #[derive(Clone, Copy, PartialEq, Eq)]
 133         pub struct Keyword {
 134             ident: ast::Ident,
 135         }
 136         impl Keyword {
 137             #[inline] pub fn ident(self) -> ast::Ident { self.ident }
 138             #[inline] pub fn name(self) -> ast::Name { self.ident.name }
 139         }
 140         $(
 141             #[allow(non_upper_case_globals)]
 142             pub const $konst: Keyword = Keyword {
 143                 ident: ast::Ident::with_empty_ctxt(ast::Name($index))
 144             };
 145         )*
 146     }
 147
 148     impl Interner {
 149         fn fresh() -> Self {
 150             Interner::prefill(&[$($string,)*])
 151         }
 152     }
 153 }}
 154
 155 // NB: leaving holes in the ident table is bad! a different ident will get
 156 // interned with the id from the hole, but it will be between the min and max
 157 // of the reserved words, and thus tagged as "reserved".
 158 // After modifying this list adjust `is_strict_keyword`/`is_reserved_keyword`,
 159 // this should be rarely necessary though if the keywords are kept in alphabetic order.
 160 declare_keywords! {
 161     // Invalid identifier
 162     (0,  Invalid,        "")
 163
 164     // Strict keywords used in the language.
 165     (1,  As,             "as")
 166     (2,  Box,            "box")
 167     (3,  Break,          "break")
 168     (4,  Const,          "const")
 169     (5,  Continue,       "continue")
 170     (6,  Crate,          "crate")
 171     (7,  Else,           "else")
 172     (8,  Enum,           "enum")
 173     (9,  Extern,         "extern")
 174     (10, False,          "false")
 175     (11, Fn,             "fn")
 176     (12, For,            "for")
 177     (13, If,             "if")
 178     (14, Impl,           "impl")
 179     (15, In,             "in")
 180     (16, Let,            "let")
 181     (17, Loop,           "loop")
 182     (18, Match,          "match")
 183     (19, Mod,            "mod")
 184     (20, Move,           "move")
 185     (21, Mut,            "mut")
 186     (22, Pub,            "pub")
 187     (23, Ref,            "ref")
 188     (24, Return,         "return")
 189     (25, SelfValue,      "self")
 190     (26, SelfType,       "Self")
 191     (27, Static,         "static")
 192     (28, Struct,         "struct")
 193     (29, Super,          "super")
 194     (30, Trait,          "trait")
 195     (31, True,           "true")
 196     (32, Type,           "type")
 197     (33, Unsafe,         "unsafe")
 198     (34, Use,            "use")
 199     (35, Where,          "where")
 200     (36, While,          "while")
 201
 202     // Keywords reserved for future use.
 203     (37, Abstract,       "abstract")
 204     (38, Alignof,        "alignof")
 205     (39, Become,         "become")
 206     (40, Do,             "do")
 207     (41, Final,          "final")
 208     (42, Macro,          "macro")
 209     (43, Offsetof,       "offsetof")
 210     (44, Override,       "override")
 211     (45, Priv,           "priv")
 212     (46, Proc,           "proc")
 213     (47, Pure,           "pure")
 214     (48, Sizeof,         "sizeof")
 215     (49, Typeof,         "typeof")
 216     (50, Unsized,        "unsized")
 217     (51, Virtual,        "virtual")
 218     (52, Yield,          "yield")
 219
 220     // Weak keywords, have special meaning only in specific contexts.
 221     (53, Default,        "default")
 222     (54, StaticLifetime, "'static")
 223     (55, Union,          "union")
 224 }
 225
 226 // If an interner exists in TLS, return it. Otherwise, prepare a fresh one.
 227 fn with_interner<T, F: FnOnce(&mut Interner) -> T>(f: F) -> T {
 228     thread_local!(static INTERNER: RefCell<Interner> = {
 229         RefCell::new(Interner::fresh())
 230     });
 231     INTERNER.with(|interner| f(&mut *interner.borrow_mut()))
 232 }
 233
 234 /// Represents a string stored in the thread-local interner. Because the
 235 /// interner lives for the life of the thread, this can be safely treated as an
 236 /// immortal string, as long as it never crosses between threads.
 237 ///
 238 /// FIXME(pcwalton): You must be careful about what you do in the destructors
 239 /// of objects stored in TLS, because they may run after the interner is
 240 /// destroyed. In particular, they must not access string contents. This can
 241 /// be fixed in the future by just leaking all strings until thread death
 242 /// somehow.
 243 #[derive(Clone, PartialEq, Hash, PartialOrd, Eq, Ord)]
 244 pub struct InternedString {
 245     string: &'static str,
 246 }
 247
 248 impl !Send for InternedString { }
 249
 250 impl ::std::ops::Deref for InternedString {
 251     type Target = str;
 252     fn deref(&self) -> &str { self.string }
 253 }
 254
 255 impl fmt::Debug for InternedString {
 256     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 257         fmt::Debug::fmt(self.string, f)
 258     }
 259 }
 260
 261 impl fmt::Display for InternedString {
 262     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 263         fmt::Display::fmt(self.string, f)
 264     }
 265 }
 266
 267 impl Decodable for InternedString {
 268     fn decode<D: Decoder>(d: &mut D) -> Result<InternedString, D::Error> {
 269         Ok(Symbol::intern(&d.read_str()?).as_str())
 270     }
 271 }
 272
 273 impl Encodable for InternedString {
 274     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 275         s.emit_str(self.string)
 276     }
 277 }
 278
 279 #[cfg(test)]
 280 mod tests {
 281     use super::*;
 282     use ast::Name;
 283
 284     #[test]
 285     fn interner_tests() {
 286         let mut i: Interner = Interner::new();
 287         // first one is zero:
 288         assert_eq!(i.intern("dog"), Name(0));
 289         // re-use gets the same entry:
 290         assert_eq!(i.intern ("dog"), Name(0));
 291         // different string gets a different #:
 292         assert_eq!(i.intern("cat"), Name(1));
 293         assert_eq!(i.intern("cat"), Name(1));
 294         // dog is still at zero
 295         assert_eq!(i.intern("dog"), Name(0));
 296         // gensym gets 3
 297         assert_eq!(i.gensym("zebra"), Name(2));
 298         // gensym of same string gets new number :
 299         assert_eq!(i.gensym("zebra"), Name(3));
 300         // gensym of *existing* string gets new number:
 301         assert_eq!(i.gensym("dog"), Name(4));
 302     }
 303 }