src/libsyntax_pos/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 hygiene::SyntaxContext;
  16 use {Span, DUMMY_SP, GLOBALS};
  17
  18 use rustc_data_structures::fx::FxHashMap;
  19 use serialize::{Decodable, Decoder, Encodable, Encoder};
  20 use std::fmt;
  21 use std::hash::{Hash, Hasher};
  22
  23 #[derive(Copy, Clone, Eq)]
  24 pub struct Ident {
  25     pub name: Symbol,
  26     pub span: Span,
  27 }
  28
  29 impl Ident {
  30     #[inline]
  31     pub const fn new(name: Symbol, span: Span) -> Ident {
  32         Ident { name, span }
  33     }
  34     #[inline]
  35     pub const fn with_empty_ctxt(name: Symbol) -> Ident {
  36         Ident::new(name, DUMMY_SP)
  37     }
  38
  39     /// Maps a string to an identifier with an empty syntax context.
  40     pub fn from_str(string: &str) -> Ident {
  41         Ident::with_empty_ctxt(Symbol::intern(string))
  42     }
  43
  44     /// Replace `lo` and `hi` with those from `span`, but keep hygiene context.
  45     pub fn with_span_pos(self, span: Span) -> Ident {
  46         Ident::new(self.name, span.with_ctxt(self.span.ctxt()))
  47     }
  48
  49     pub fn without_first_quote(self) -> Ident {
  50         Ident::new(Symbol::intern(self.name.as_str().trim_left_matches('\'')), self.span)
  51     }
  52
  53     pub fn modern(self) -> Ident {
  54         Ident::new(self.name, self.span.modern())
  55     }
  56
  57     pub fn gensym(self) -> Ident {
  58         Ident::new(self.name.gensymed(), self.span)
  59     }
  60 }
  61
  62 impl PartialEq for Ident {
  63     fn eq(&self, rhs: &Self) -> bool {
  64         self.name == rhs.name && self.span.ctxt() == rhs.span.ctxt()
  65     }
  66 }
  67
  68 impl Hash for Ident {
  69     fn hash<H: Hasher>(&self, state: &mut H) {
  70         self.name.hash(state);
  71         self.span.ctxt().hash(state);
  72     }
  73 }
  74
  75 impl fmt::Debug for Ident {
  76     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  77         write!(f, "{}{:?}", self.name, self.span.ctxt())
  78     }
  79 }
  80
  81 impl fmt::Display for Ident {
  82     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  83         fmt::Display::fmt(&self.name, f)
  84     }
  85 }
  86
  87 impl Encodable for Ident {
  88     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
  89         if self.span.ctxt().modern() == SyntaxContext::empty() {
  90             s.emit_str(&self.name.as_str())
  91         } else { // FIXME(jseyfried) intercrate hygiene
  92             let mut string = "#".to_owned();
  93             string.push_str(&self.name.as_str());
  94             s.emit_str(&string)
  95         }
  96     }
  97 }
  98
  99 impl Decodable for Ident {
 100     fn decode<D: Decoder>(d: &mut D) -> Result<Ident, D::Error> {
 101         let string = d.read_str()?;
 102         Ok(if !string.starts_with('#') {
 103             Ident::from_str(&string)
 104         } else { // FIXME(jseyfried) intercrate hygiene
 105             Ident::with_empty_ctxt(Symbol::gensym(&string[1..]))
 106         })
 107     }
 108 }
 109
 110 /// A symbol is an interned or gensymed string.
 111 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 112 pub struct Symbol(u32);
 113
 114 // The interner is pointed to by a thread local value which is only set on the main thread
 115 // with parallelization is disabled. So we don't allow Symbol to transfer between threads
 116 // to avoid panics and other errors, even though it would be memory safe to do so.
 117 #[cfg(not(parallel_queries))]
 118 impl !Send for Symbol { }
 119 #[cfg(not(parallel_queries))]
 120 impl !Sync for Symbol { }
 121
 122 impl Symbol {
 123     /// Maps a string to its interned representation.
 124     pub fn intern(string: &str) -> Self {
 125         with_interner(|interner| interner.intern(string))
 126     }
 127
 128     pub fn interned(self) -> Self {
 129         with_interner(|interner| interner.interned(self))
 130     }
 131
 132     /// gensym's a new usize, using the current interner.
 133     pub fn gensym(string: &str) -> Self {
 134         with_interner(|interner| interner.gensym(string))
 135     }
 136
 137     pub fn gensymed(self) -> Self {
 138         with_interner(|interner| interner.gensymed(self))
 139     }
 140
 141     pub fn as_str(self) -> InternedString {
 142         with_interner(|interner| unsafe {
 143             InternedString {
 144                 string: ::std::mem::transmute::<&str, &str>(interner.get(self))
 145             }
 146         })
 147     }
 148
 149     pub fn as_u32(self) -> u32 {
 150         self.0
 151     }
 152 }
 153
 154 impl fmt::Debug for Symbol {
 155     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 156         let is_gensymed = with_interner(|interner| interner.is_gensymed(*self));
 157         if is_gensymed {
 158             write!(f, "{}({})", self, self.0)
 159         } else {
 160             write!(f, "{}", self)
 161         }
 162     }
 163 }
 164
 165 impl fmt::Display for Symbol {
 166     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 167         fmt::Display::fmt(&self.as_str(), f)
 168     }
 169 }
 170
 171 impl Encodable for Symbol {
 172     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 173         s.emit_str(&self.as_str())
 174     }
 175 }
 176
 177 impl Decodable for Symbol {
 178     fn decode<D: Decoder>(d: &mut D) -> Result<Symbol, D::Error> {
 179         Ok(Symbol::intern(&d.read_str()?))
 180     }
 181 }
 182
 183 impl<T: ::std::ops::Deref<Target=str>> PartialEq<T> for Symbol {
 184     fn eq(&self, other: &T) -> bool {
 185         self.as_str() == other.deref()
 186     }
 187 }
 188
 189 #[derive(Default)]
 190 pub struct Interner {
 191     names: FxHashMap<Box<str>, Symbol>,
 192     strings: Vec<Box<str>>,
 193     gensyms: Vec<Symbol>,
 194 }
 195
 196 impl Interner {
 197     pub fn new() -> Self {
 198         Interner::default()
 199     }
 200
 201     fn prefill(init: &[&str]) -> Self {
 202         let mut this = Interner::new();
 203         for &string in init {
 204             this.intern(string);
 205         }
 206         this
 207     }
 208
 209     pub fn intern(&mut self, string: &str) -> Symbol {
 210         if let Some(&name) = self.names.get(string) {
 211             return name;
 212         }
 213
 214         let name = Symbol(self.strings.len() as u32);
 215         let string = string.to_string().into_boxed_str();
 216         self.strings.push(string.clone());
 217         self.names.insert(string, name);
 218         name
 219     }
 220
 221     pub fn interned(&self, symbol: Symbol) -> Symbol {
 222         if (symbol.0 as usize) < self.strings.len() {
 223             symbol
 224         } else {
 225             self.interned(self.gensyms[(!0 - symbol.0) as usize])
 226         }
 227     }
 228
 229     fn gensym(&mut self, string: &str) -> Symbol {
 230         let symbol = self.intern(string);
 231         self.gensymed(symbol)
 232     }
 233
 234     fn gensymed(&mut self, symbol: Symbol) -> Symbol {
 235         self.gensyms.push(symbol);
 236         Symbol(!0 - self.gensyms.len() as u32 + 1)
 237     }
 238
 239     fn is_gensymed(&mut self, symbol: Symbol) -> bool {
 240         symbol.0 as usize >= self.strings.len()
 241     }
 242
 243     pub fn get(&self, symbol: Symbol) -> &str {
 244         match self.strings.get(symbol.0 as usize) {
 245             Some(ref string) => string,
 246             None => self.get(self.gensyms[(!0 - symbol.0) as usize]),
 247         }
 248     }
 249 }
 250
 251 // In this macro, there is the requirement that the name (the number) must be monotonically
 252 // increasing by one in the special identifiers, starting at 0; the same holds for the keywords,
 253 // except starting from the next number instead of zero.
 254 macro_rules! declare_keywords {(
 255     $( ($index: expr, $konst: ident, $string: expr) )*
 256 ) => {
 257     pub mod keywords {
 258         use super::{Symbol, Ident};
 259         #[derive(Clone, Copy, PartialEq, Eq)]
 260         pub struct Keyword {
 261             ident: Ident,
 262         }
 263         impl Keyword {
 264             #[inline] pub fn ident(self) -> Ident { self.ident }
 265             #[inline] pub fn name(self) -> Symbol { self.ident.name }
 266         }
 267         $(
 268             #[allow(non_upper_case_globals)]
 269             pub const $konst: Keyword = Keyword {
 270                 ident: Ident::with_empty_ctxt(super::Symbol($index))
 271             };
 272         )*
 273     }
 274
 275     impl Interner {
 276         pub fn fresh() -> Self {
 277             Interner::prefill(&[$($string,)*])
 278         }
 279     }
 280 }}
 281
 282 // NB: leaving holes in the ident table is bad! a different ident will get
 283 // interned with the id from the hole, but it will be between the min and max
 284 // of the reserved words, and thus tagged as "reserved".
 285 // After modifying this list adjust `is_special_ident`, `is_used_keyword`/`is_unused_keyword`,
 286 // this should be rarely necessary though if the keywords are kept in alphabetic order.
 287 declare_keywords! {
 288     // Special reserved identifiers used internally for elided lifetimes,
 289     // unnamed method parameters, crate root module, error recovery etc.
 290     (0,  Invalid,            "")
 291     (1,  CrateRoot,          "{{root}}")
 292     (2,  DollarCrate,        "$crate")
 293     (3,  Underscore,         "_")
 294
 295     // Keywords used in the language.
 296     (4,  As,                 "as")
 297     (5,  Box,                "box")
 298     (6,  Break,              "break")
 299     (7,  Const,              "const")
 300     (8,  Continue,           "continue")
 301     (9,  Crate,              "crate")
 302     (10, Else,               "else")
 303     (11, Enum,               "enum")
 304     (12, Extern,             "extern")
 305     (13, False,              "false")
 306     (14, Fn,                 "fn")
 307     (15, For,                "for")
 308     (16, If,                 "if")
 309     (17, Impl,               "impl")
 310     (18, In,                 "in")
 311     (19, Let,                "let")
 312     (20, Loop,               "loop")
 313     (21, Match,              "match")
 314     (22, Mod,                "mod")
 315     (23, Move,               "move")
 316     (24, Mut,                "mut")
 317     (25, Pub,                "pub")
 318     (26, Ref,                "ref")
 319     (27, Return,             "return")
 320     (28, SelfValue,          "self")
 321     (29, SelfType,           "Self")
 322     (30, Static,             "static")
 323     (31, Struct,             "struct")
 324     (32, Super,              "super")
 325     (33, Trait,              "trait")
 326     (34, True,               "true")
 327     (35, Type,               "type")
 328     (36, Unsafe,             "unsafe")
 329     (37, Use,                "use")
 330     (38, Where,              "where")
 331     (39, While,              "while")
 332
 333     // Keywords reserved for future use.
 334     (40, Abstract,           "abstract")
 335     (41, Alignof,            "alignof")
 336     (42, Become,             "become")
 337     (43, Do,                 "do")
 338     (44, Final,              "final")
 339     (45, Macro,              "macro")
 340     (46, Offsetof,           "offsetof")
 341     (47, Override,           "override")
 342     (48, Priv,               "priv")
 343     (49, Pure,               "pure")
 344     (50, Sizeof,             "sizeof")
 345     (51, Typeof,             "typeof")
 346     (52, Unsized,            "unsized")
 347     (53, Virtual,            "virtual")
 348     (54, Yield,              "yield")
 349
 350     // Special lifetime names
 351     (55, UnderscoreLifetime, "'_")
 352     (56, StaticLifetime,     "'static")
 353
 354     // Weak keywords, have special meaning only in specific contexts.
 355     (57, Auto,               "auto")
 356     (58, Catch,              "catch")
 357     (59, Default,            "default")
 358     (60, Dyn,                "dyn")
 359     (61, Union,              "union")
 360 }
 361
 362 // If an interner exists, return it. Otherwise, prepare a fresh one.
 363 #[inline]
 364 fn with_interner<T, F: FnOnce(&mut Interner) -> T>(f: F) -> T {
 365     GLOBALS.with(|globals| f(&mut *globals.symbol_interner.lock()))
 366 }
 367
 368 /// Represents a string stored in the thread-local interner. Because the
 369 /// interner lives for the life of the thread, this can be safely treated as an
 370 /// immortal string, as long as it never crosses between threads.
 371 ///
 372 /// FIXME(pcwalton): You must be careful about what you do in the destructors
 373 /// of objects stored in TLS, because they may run after the interner is
 374 /// destroyed. In particular, they must not access string contents. This can
 375 /// be fixed in the future by just leaking all strings until thread death
 376 /// somehow.
 377 #[derive(Clone, Copy, Hash, PartialOrd, Eq, Ord)]
 378 pub struct InternedString {
 379     string: &'static str,
 380 }
 381
 382 impl<U: ?Sized> ::std::convert::AsRef<U> for InternedString where str: ::std::convert::AsRef<U> {
 383     fn as_ref(&self) -> &U {
 384         self.string.as_ref()
 385     }
 386 }
 387
 388 impl<T: ::std::ops::Deref<Target = str>> ::std::cmp::PartialEq<T> for InternedString {
 389     fn eq(&self, other: &T) -> bool {
 390         self.string == other.deref()
 391     }
 392 }
 393
 394 impl ::std::cmp::PartialEq<InternedString> for str {
 395     fn eq(&self, other: &InternedString) -> bool {
 396         self == other.string
 397     }
 398 }
 399
 400 impl<'a> ::std::cmp::PartialEq<InternedString> for &'a str {
 401     fn eq(&self, other: &InternedString) -> bool {
 402         *self == other.string
 403     }
 404 }
 405
 406 impl ::std::cmp::PartialEq<InternedString> for String {
 407     fn eq(&self, other: &InternedString) -> bool {
 408         self == other.string
 409     }
 410 }
 411
 412 impl<'a> ::std::cmp::PartialEq<InternedString> for &'a String {
 413     fn eq(&self, other: &InternedString) -> bool {
 414         *self == other.string
 415     }
 416 }
 417
 418 impl !Send for InternedString { }
 419
 420 impl ::std::ops::Deref for InternedString {
 421     type Target = str;
 422     fn deref(&self) -> &str { self.string }
 423 }
 424
 425 impl fmt::Debug for InternedString {
 426     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 427         fmt::Debug::fmt(self.string, f)
 428     }
 429 }
 430
 431 impl fmt::Display for InternedString {
 432     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 433         fmt::Display::fmt(self.string, f)
 434     }
 435 }
 436
 437 impl Decodable for InternedString {
 438     fn decode<D: Decoder>(d: &mut D) -> Result<InternedString, D::Error> {
 439         Ok(Symbol::intern(&d.read_str()?).as_str())
 440     }
 441 }
 442
 443 impl Encodable for InternedString {
 444     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 445         s.emit_str(self.string)
 446     }
 447 }
 448
 449 #[cfg(test)]
 450 mod tests {
 451     use super::*;
 452     use Globals;
 453
 454     #[test]
 455     fn interner_tests() {
 456         let mut i: Interner = Interner::new();
 457         // first one is zero:
 458         assert_eq!(i.intern("dog"), Symbol(0));
 459         // re-use gets the same entry:
 460         assert_eq!(i.intern("dog"), Symbol(0));
 461         // different string gets a different #:
 462         assert_eq!(i.intern("cat"), Symbol(1));
 463         assert_eq!(i.intern("cat"), Symbol(1));
 464         // dog is still at zero
 465         assert_eq!(i.intern("dog"), Symbol(0));
 466         assert_eq!(i.gensym("zebra"), Symbol(4294967295));
 467         // gensym of same string gets new number :
 468         assert_eq!(i.gensym("zebra"), Symbol(4294967294));
 469         // gensym of *existing* string gets new number:
 470         assert_eq!(i.gensym("dog"), Symbol(4294967293));
 471     }
 472
 473     #[test]
 474     fn without_first_quote_test() {
 475         GLOBALS.set(&Globals::new(), || {
 476             let i = Ident::from_str("'break");
 477             assert_eq!(i.without_first_quote().name, keywords::Break.name());
 478         });
 479     }
 480 }