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 arena::DroplessArena;
  20 use serialize::{Decodable, Decoder, Encodable, Encoder};
  21 use std::fmt;
  22 use std::str;
  23 use std::cmp::{PartialEq, Ordering, PartialOrd, Ord};
  24 use std::hash::{Hash, Hasher};
  25
  26 #[derive(Copy, Clone, Eq)]
  27 pub struct Ident {
  28     pub name: Symbol,
  29     pub span: Span,
  30 }
  31
  32 impl Ident {
  33     #[inline]
  34     pub const fn new(name: Symbol, span: Span) -> Ident {
  35         Ident { name, span }
  36     }
  37     #[inline]
  38     pub const fn with_empty_ctxt(name: Symbol) -> Ident {
  39         Ident::new(name, DUMMY_SP)
  40     }
  41
  42     /// Maps an interned string to an identifier with an empty syntax context.
  43     pub fn from_interned_str(string: InternedString) -> Ident {
  44         Ident::with_empty_ctxt(string.as_symbol())
  45     }
  46
  47     /// Maps a string to an identifier with an empty syntax context.
  48     pub fn from_str(string: &str) -> Ident {
  49         Ident::with_empty_ctxt(Symbol::intern(string))
  50     }
  51
  52     /// Replace `lo` and `hi` with those from `span`, but keep hygiene context.
  53     pub fn with_span_pos(self, span: Span) -> Ident {
  54         Ident::new(self.name, span.with_ctxt(self.span.ctxt()))
  55     }
  56
  57     pub fn without_first_quote(self) -> Ident {
  58         Ident::new(Symbol::intern(self.name.as_str().trim_left_matches('\'')), self.span)
  59     }
  60
  61     pub fn modern(self) -> Ident {
  62         Ident::new(self.name, self.span.modern())
  63     }
  64
  65     pub fn gensym(self) -> Ident {
  66         Ident::new(self.name.gensymed(), self.span)
  67     }
  68 }
  69
  70 impl PartialEq for Ident {
  71     fn eq(&self, rhs: &Self) -> bool {
  72         self.name == rhs.name && self.span.ctxt() == rhs.span.ctxt()
  73     }
  74 }
  75
  76 impl Hash for Ident {
  77     fn hash<H: Hasher>(&self, state: &mut H) {
  78         self.name.hash(state);
  79         self.span.ctxt().hash(state);
  80     }
  81 }
  82
  83 impl fmt::Debug for Ident {
  84     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  85         write!(f, "{}{:?}", self.name, self.span.ctxt())
  86     }
  87 }
  88
  89 impl fmt::Display for Ident {
  90     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  91         fmt::Display::fmt(&self.name, f)
  92     }
  93 }
  94
  95 impl Encodable for Ident {
  96     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
  97         if self.span.ctxt().modern() == SyntaxContext::empty() {
  98             s.emit_str(&self.name.as_str())
  99         } else { // FIXME(jseyfried) intercrate hygiene
 100             let mut string = "#".to_owned();
 101             string.push_str(&self.name.as_str());
 102             s.emit_str(&string)
 103         }
 104     }
 105 }
 106
 107 impl Decodable for Ident {
 108     fn decode<D: Decoder>(d: &mut D) -> Result<Ident, D::Error> {
 109         let string = d.read_str()?;
 110         Ok(if !string.starts_with('#') {
 111             Ident::from_str(&string)
 112         } else { // FIXME(jseyfried) intercrate hygiene
 113             Ident::with_empty_ctxt(Symbol::gensym(&string[1..]))
 114         })
 115     }
 116 }
 117
 118 /// A symbol is an interned or gensymed string.
 119 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
 120 pub struct Symbol(u32);
 121
 122 // The interner is pointed to by a thread local value which is only set on the main thread
 123 // with parallelization is disabled. So we don't allow Symbol to transfer between threads
 124 // to avoid panics and other errors, even though it would be memory safe to do so.
 125 #[cfg(not(parallel_queries))]
 126 impl !Send for Symbol { }
 127 #[cfg(not(parallel_queries))]
 128 impl !Sync for Symbol { }
 129
 130 impl Symbol {
 131     /// Maps a string to its interned representation.
 132     pub fn intern(string: &str) -> Self {
 133         with_interner(|interner| interner.intern(string))
 134     }
 135
 136     pub fn interned(self) -> Self {
 137         with_interner(|interner| interner.interned(self))
 138     }
 139
 140     /// gensym's a new usize, using the current interner.
 141     pub fn gensym(string: &str) -> Self {
 142         with_interner(|interner| interner.gensym(string))
 143     }
 144
 145     pub fn gensymed(self) -> Self {
 146         with_interner(|interner| interner.gensymed(self))
 147     }
 148
 149     pub fn as_str(self) -> LocalInternedString {
 150         with_interner(|interner| unsafe {
 151             LocalInternedString {
 152                 string: ::std::mem::transmute::<&str, &str>(interner.get(self))
 153             }
 154         })
 155     }
 156
 157     pub fn as_interned_str(self) -> InternedString {
 158         with_interner(|interner| InternedString {
 159             symbol: interner.interned(self)
 160         })
 161     }
 162
 163     pub fn as_u32(self) -> u32 {
 164         self.0
 165     }
 166 }
 167
 168 impl fmt::Debug for Symbol {
 169     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 170         let is_gensymed = with_interner(|interner| interner.is_gensymed(*self));
 171         if is_gensymed {
 172             write!(f, "{}({})", self, self.0)
 173         } else {
 174             write!(f, "{}", self)
 175         }
 176     }
 177 }
 178
 179 impl fmt::Display for Symbol {
 180     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 181         fmt::Display::fmt(&self.as_str(), f)
 182     }
 183 }
 184
 185 impl Encodable for Symbol {
 186     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 187         s.emit_str(&self.as_str())
 188     }
 189 }
 190
 191 impl Decodable for Symbol {
 192     fn decode<D: Decoder>(d: &mut D) -> Result<Symbol, D::Error> {
 193         Ok(Symbol::intern(&d.read_str()?))
 194     }
 195 }
 196
 197 impl<T: ::std::ops::Deref<Target=str>> PartialEq<T> for Symbol {
 198     fn eq(&self, other: &T) -> bool {
 199         self.as_str() == other.deref()
 200     }
 201 }
 202
 203 // The &'static strs in this type actually point into the arena
 204 pub struct Interner {
 205     arena: DroplessArena,
 206     names: FxHashMap<&'static str, Symbol>,
 207     strings: Vec<&'static str>,
 208     gensyms: Vec<Symbol>,
 209 }
 210
 211 impl Interner {
 212     pub fn new() -> Self {
 213         Interner {
 214             arena: DroplessArena::new(),
 215             names: Default::default(),
 216             strings: Default::default(),
 217             gensyms: Default::default(),
 218         }
 219     }
 220
 221     fn prefill(init: &[&str]) -> Self {
 222         let mut this = Interner::new();
 223         for &string in init {
 224             if string == "" {
 225                 // We can't allocate empty strings in the arena, so handle this here
 226                 let name = Symbol(this.strings.len() as u32);
 227                 this.names.insert("", name);
 228                 this.strings.push("");
 229             } else {
 230                 this.intern(string);
 231             }
 232         }
 233         this
 234     }
 235
 236     pub fn intern(&mut self, string: &str) -> Symbol {
 237         if let Some(&name) = self.names.get(string) {
 238             return name;
 239         }
 240
 241         let name = Symbol(self.strings.len() as u32);
 242
 243         // from_utf8_unchecked is safe since we just allocated a &str which is known to be utf8
 244         let string: &str = unsafe {
 245             str::from_utf8_unchecked(self.arena.alloc_slice(string.as_bytes()))
 246         };
 247         // It is safe to extend the arena allocation to 'static because we only access
 248         // these while the arena is still alive
 249         let string: &'static str =  unsafe {
 250             &*(string as *const str)
 251         };
 252         self.strings.push(string);
 253         self.names.insert(string, name);
 254         name
 255     }
 256
 257     pub fn interned(&self, symbol: Symbol) -> Symbol {
 258         if (symbol.0 as usize) < self.strings.len() {
 259             symbol
 260         } else {
 261             self.interned(self.gensyms[(!0 - symbol.0) as usize])
 262         }
 263     }
 264
 265     fn gensym(&mut self, string: &str) -> Symbol {
 266         let symbol = self.intern(string);
 267         self.gensymed(symbol)
 268     }
 269
 270     fn gensymed(&mut self, symbol: Symbol) -> Symbol {
 271         self.gensyms.push(symbol);
 272         Symbol(!0 - self.gensyms.len() as u32 + 1)
 273     }
 274
 275     fn is_gensymed(&mut self, symbol: Symbol) -> bool {
 276         symbol.0 as usize >= self.strings.len()
 277     }
 278
 279     pub fn get(&self, symbol: Symbol) -> &str {
 280         match self.strings.get(symbol.0 as usize) {
 281             Some(string) => string,
 282             None => self.get(self.gensyms[(!0 - symbol.0) as usize]),
 283         }
 284     }
 285 }
 286
 287 // In this macro, there is the requirement that the name (the number) must be monotonically
 288 // increasing by one in the special identifiers, starting at 0; the same holds for the keywords,
 289 // except starting from the next number instead of zero.
 290 macro_rules! declare_keywords {(
 291     $( ($index: expr, $konst: ident, $string: expr) )*
 292 ) => {
 293     pub mod keywords {
 294         use super::{Symbol, Ident};
 295         #[derive(Clone, Copy, PartialEq, Eq)]
 296         pub struct Keyword {
 297             ident: Ident,
 298         }
 299         impl Keyword {
 300             #[inline] pub fn ident(self) -> Ident { self.ident }
 301             #[inline] pub fn name(self) -> Symbol { self.ident.name }
 302         }
 303         $(
 304             #[allow(non_upper_case_globals)]
 305             pub const $konst: Keyword = Keyword {
 306                 ident: Ident::with_empty_ctxt(super::Symbol($index))
 307             };
 308         )*
 309     }
 310
 311     impl Interner {
 312         pub fn fresh() -> Self {
 313             Interner::prefill(&[$($string,)*])
 314         }
 315     }
 316 }}
 317
 318 // NB: leaving holes in the ident table is bad! a different ident will get
 319 // interned with the id from the hole, but it will be between the min and max
 320 // of the reserved words, and thus tagged as "reserved".
 321 // After modifying this list adjust `is_special_ident`, `is_used_keyword`/`is_unused_keyword`,
 322 // this should be rarely necessary though if the keywords are kept in alphabetic order.
 323 declare_keywords! {
 324     // Special reserved identifiers used internally for elided lifetimes,
 325     // unnamed method parameters, crate root module, error recovery etc.
 326     (0,  Invalid,            "")
 327     (1,  CrateRoot,          "{{root}}")
 328     (2,  DollarCrate,        "$crate")
 329     (3,  Underscore,         "_")
 330
 331     // Keywords used in the language.
 332     (4,  As,                 "as")
 333     (5,  Box,                "box")
 334     (6,  Break,              "break")
 335     (7,  Const,              "const")
 336     (8,  Continue,           "continue")
 337     (9,  Crate,              "crate")
 338     (10, Else,               "else")
 339     (11, Enum,               "enum")
 340     (12, Extern,             "extern")
 341     (13, False,              "false")
 342     (14, Fn,                 "fn")
 343     (15, For,                "for")
 344     (16, If,                 "if")
 345     (17, Impl,               "impl")
 346     (18, In,                 "in")
 347     (19, Let,                "let")
 348     (20, Loop,               "loop")
 349     (21, Match,              "match")
 350     (22, Mod,                "mod")
 351     (23, Move,               "move")
 352     (24, Mut,                "mut")
 353     (25, Pub,                "pub")
 354     (26, Ref,                "ref")
 355     (27, Return,             "return")
 356     (28, SelfValue,          "self")
 357     (29, SelfType,           "Self")
 358     (30, Static,             "static")
 359     (31, Struct,             "struct")
 360     (32, Super,              "super")
 361     (33, Trait,              "trait")
 362     (34, True,               "true")
 363     (35, Type,               "type")
 364     (36, Unsafe,             "unsafe")
 365     (37, Use,                "use")
 366     (38, Where,              "where")
 367     (39, While,              "while")
 368
 369     // Keywords reserved for future use.
 370     (40, Abstract,           "abstract")
 371     (41, Alignof,            "alignof")
 372     (42, Become,             "become")
 373     (43, Do,                 "do")
 374     (44, Final,              "final")
 375     (45, Macro,              "macro")
 376     (46, Offsetof,           "offsetof")
 377     (47, Override,           "override")
 378     (48, Priv,               "priv")
 379     (49, Pure,               "pure")
 380     (50, Sizeof,             "sizeof")
 381     (51, Typeof,             "typeof")
 382     (52, Unsized,            "unsized")
 383     (53, Virtual,            "virtual")
 384     (54, Yield,              "yield")
 385
 386     // Special lifetime names
 387     (55, UnderscoreLifetime, "'_")
 388     (56, StaticLifetime,     "'static")
 389
 390     // Weak keywords, have special meaning only in specific contexts.
 391     (57, Auto,               "auto")
 392     (58, Catch,              "catch")
 393     (59, Default,            "default")
 394     (60, Dyn,                "dyn")
 395     (61, Union,              "union")
 396 }
 397
 398 // If an interner exists, return it. Otherwise, prepare a fresh one.
 399 #[inline]
 400 fn with_interner<T, F: FnOnce(&mut Interner) -> T>(f: F) -> T {
 401     GLOBALS.with(|globals| f(&mut *globals.symbol_interner.lock()))
 402 }
 403
 404 /// Represents a string stored in the interner. Because the interner outlives any thread
 405 /// which uses this type, we can safely treat `string` which points to interner data,
 406 /// as an immortal string, as long as this type never crosses between threads.
 407 // FIXME: Ensure that the interner outlives any thread which uses LocalInternedString,
 408 //        by creating a new thread right after constructing the interner
 409 #[derive(Clone, Copy, Hash, PartialOrd, Eq, Ord)]
 410 pub struct LocalInternedString {
 411     string: &'static str,
 412 }
 413
 414 impl LocalInternedString {
 415     pub fn as_interned_str(self) -> InternedString {
 416         InternedString {
 417             symbol: Symbol::intern(self.string)
 418         }
 419     }
 420 }
 421
 422 impl<U: ?Sized> ::std::convert::AsRef<U> for LocalInternedString
 423 where
 424     str: ::std::convert::AsRef<U>
 425 {
 426     fn as_ref(&self) -> &U {
 427         self.string.as_ref()
 428     }
 429 }
 430
 431 impl<T: ::std::ops::Deref<Target = str>> ::std::cmp::PartialEq<T> for LocalInternedString {
 432     fn eq(&self, other: &T) -> bool {
 433         self.string == other.deref()
 434     }
 435 }
 436
 437 impl ::std::cmp::PartialEq<LocalInternedString> for str {
 438     fn eq(&self, other: &LocalInternedString) -> bool {
 439         self == other.string
 440     }
 441 }
 442
 443 impl<'a> ::std::cmp::PartialEq<LocalInternedString> for &'a str {
 444     fn eq(&self, other: &LocalInternedString) -> bool {
 445         *self == other.string
 446     }
 447 }
 448
 449 impl ::std::cmp::PartialEq<LocalInternedString> for String {
 450     fn eq(&self, other: &LocalInternedString) -> bool {
 451         self == other.string
 452     }
 453 }
 454
 455 impl<'a> ::std::cmp::PartialEq<LocalInternedString> for &'a String {
 456     fn eq(&self, other: &LocalInternedString) -> bool {
 457         *self == other.string
 458     }
 459 }
 460
 461 impl !Send for LocalInternedString {}
 462 impl !Sync for LocalInternedString {}
 463
 464 impl ::std::ops::Deref for LocalInternedString {
 465     type Target = str;
 466     fn deref(&self) -> &str { self.string }
 467 }
 468
 469 impl fmt::Debug for LocalInternedString {
 470     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 471         fmt::Debug::fmt(self.string, f)
 472     }
 473 }
 474
 475 impl fmt::Display for LocalInternedString {
 476     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 477         fmt::Display::fmt(self.string, f)
 478     }
 479 }
 480
 481 impl Decodable for LocalInternedString {
 482     fn decode<D: Decoder>(d: &mut D) -> Result<LocalInternedString, D::Error> {
 483         Ok(Symbol::intern(&d.read_str()?).as_str())
 484     }
 485 }
 486
 487 impl Encodable for LocalInternedString {
 488     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 489         s.emit_str(self.string)
 490     }
 491 }
 492
 493 /// Represents a string stored in the string interner
 494 #[derive(Clone, Copy, Eq)]
 495 pub struct InternedString {
 496     symbol: Symbol,
 497 }
 498
 499 impl InternedString {
 500     pub fn with<F: FnOnce(&str) -> R, R>(self, f: F) -> R {
 501         let str = with_interner(|interner| {
 502             interner.get(self.symbol) as *const str
 503         });
 504         // This is safe because the interner keeps string alive until it is dropped.
 505         // We can access it because we know the interner is still alive since we use a
 506         // scoped thread local to access it, and it was alive at the begining of this scope
 507         unsafe { f(&*str) }
 508     }
 509
 510     pub fn as_symbol(self) -> Symbol {
 511         self.symbol
 512     }
 513
 514     pub fn as_str(self) -> LocalInternedString {
 515         self.symbol.as_str()
 516     }
 517 }
 518
 519 impl Hash for InternedString {
 520     fn hash<H: Hasher>(&self, state: &mut H) {
 521         self.with(|str| str.hash(state))
 522     }
 523 }
 524
 525 impl PartialOrd<InternedString> for InternedString {
 526     fn partial_cmp(&self, other: &InternedString) -> Option<Ordering> {
 527         if self.symbol == other.symbol {
 528             return Some(Ordering::Equal);
 529         }
 530         self.with(|self_str| other.with(|other_str| self_str.partial_cmp(&other_str)))
 531     }
 532 }
 533
 534 impl Ord for InternedString {
 535     fn cmp(&self, other: &InternedString) -> Ordering {
 536         if self.symbol == other.symbol {
 537             return Ordering::Equal;
 538         }
 539         self.with(|self_str| other.with(|other_str| self_str.cmp(&other_str)))
 540     }
 541 }
 542
 543 impl<T: ::std::ops::Deref<Target = str>> PartialEq<T> for InternedString {
 544     fn eq(&self, other: &T) -> bool {
 545         self.with(|string| string == other.deref())
 546     }
 547 }
 548
 549 impl PartialEq<InternedString> for InternedString {
 550     fn eq(&self, other: &InternedString) -> bool {
 551         self.symbol == other.symbol
 552     }
 553 }
 554
 555 impl PartialEq<InternedString> for str {
 556     fn eq(&self, other: &InternedString) -> bool {
 557         other.with(|string| self == string)
 558     }
 559 }
 560
 561 impl<'a> PartialEq<InternedString> for &'a str {
 562     fn eq(&self, other: &InternedString) -> bool {
 563         other.with(|string| *self == string)
 564     }
 565 }
 566
 567 impl PartialEq<InternedString> for String {
 568     fn eq(&self, other: &InternedString) -> bool {
 569         other.with(|string| self == string)
 570     }
 571 }
 572
 573 impl<'a> PartialEq<InternedString> for &'a String {
 574     fn eq(&self, other: &InternedString) -> bool {
 575         other.with(|string| *self == string)
 576     }
 577 }
 578
 579 impl ::std::convert::From<InternedString> for String {
 580     fn from(val: InternedString) -> String {
 581         val.as_symbol().to_string()
 582     }
 583 }
 584
 585 impl fmt::Debug for InternedString {
 586     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 587         self.with(|str| fmt::Debug::fmt(&str, f))
 588     }
 589 }
 590
 591 impl fmt::Display for InternedString {
 592     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 593         self.with(|str| fmt::Display::fmt(&str, f))
 594     }
 595 }
 596
 597 impl Decodable for InternedString {
 598     fn decode<D: Decoder>(d: &mut D) -> Result<InternedString, D::Error> {
 599         Ok(Symbol::intern(&d.read_str()?).as_interned_str())
 600     }
 601 }
 602
 603 impl Encodable for InternedString {
 604     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 605         self.with(|string| s.emit_str(string))
 606     }
 607 }
 608
 609 #[cfg(test)]
 610 mod tests {
 611     use super::*;
 612     use Globals;
 613
 614     #[test]
 615     fn interner_tests() {
 616         let mut i: Interner = Interner::new();
 617         // first one is zero:
 618         assert_eq!(i.intern("dog"), Symbol(0));
 619         // re-use gets the same entry:
 620         assert_eq!(i.intern("dog"), Symbol(0));
 621         // different string gets a different #:
 622         assert_eq!(i.intern("cat"), Symbol(1));
 623         assert_eq!(i.intern("cat"), Symbol(1));
 624         // dog is still at zero
 625         assert_eq!(i.intern("dog"), Symbol(0));
 626         assert_eq!(i.gensym("zebra"), Symbol(4294967295));
 627         // gensym of same string gets new number :
 628         assert_eq!(i.gensym("zebra"), Symbol(4294967294));
 629         // gensym of *existing* string gets new number:
 630         assert_eq!(i.gensym("dog"), Symbol(4294967293));
 631     }
 632
 633     #[test]
 634     fn without_first_quote_test() {
 635         GLOBALS.set(&Globals::new(), || {
 636             let i = Ident::from_str("'break");
 637             assert_eq!(i.without_first_quote().name, keywords::Break.name());
 638         });
 639     }
 640 }