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.
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.
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.
16 use hygiene::SyntaxContext;
17 use {Span, DUMMY_SP, GLOBALS};
19 use rustc_data_structures::fx::FxHashMap;
20 use arena::DroplessArena;
21 use serialize::{Decodable, Decoder, Encodable, Encoder};
24 use std::cmp::{PartialEq, Ordering, PartialOrd, Ord};
25 use std::hash::{Hash, Hasher};
27 #[derive(Copy, Clone, Eq)]
35 pub const fn new(name: Symbol, span: Span) -> Ident {
39 pub const fn with_empty_ctxt(name: Symbol) -> Ident {
40 Ident::new(name, DUMMY_SP)
43 /// Maps an interned string to an identifier with an empty syntax context.
44 pub fn from_interned_str(string: InternedString) -> Ident {
45 Ident::with_empty_ctxt(string.as_symbol())
48 /// Maps a string to an identifier with an empty syntax context.
49 pub fn from_str(string: &str) -> Ident {
50 Ident::with_empty_ctxt(Symbol::intern(string))
53 /// Replace `lo` and `hi` with those from `span`, but keep hygiene context.
54 pub fn with_span_pos(self, span: Span) -> Ident {
55 Ident::new(self.name, span.with_ctxt(self.span.ctxt()))
58 pub fn without_first_quote(self) -> Ident {
59 Ident::new(Symbol::intern(self.as_str().trim_left_matches('\'')), self.span)
62 pub fn modern(self) -> Ident {
63 Ident::new(self.name, self.span.modern())
66 pub fn gensym(self) -> Ident {
67 Ident::new(self.name.gensymed(), self.span)
70 pub fn as_str(self) -> LocalInternedString {
75 impl PartialEq for Ident {
76 fn eq(&self, rhs: &Self) -> bool {
77 self.name == rhs.name && self.span.ctxt() == rhs.span.ctxt()
82 fn hash<H: Hasher>(&self, state: &mut H) {
83 self.name.hash(state);
84 self.span.ctxt().hash(state);
88 impl fmt::Debug for Ident {
89 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
90 write!(f, "{}{:?}", self.name, self.span.ctxt())
94 impl fmt::Display for Ident {
95 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
96 fmt::Display::fmt(&self.name, f)
100 impl Encodable for Ident {
101 fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
102 if self.span.ctxt().modern() == SyntaxContext::empty() {
103 s.emit_str(&self.as_str())
104 } else { // FIXME(jseyfried) intercrate hygiene
105 let mut string = "#".to_owned();
106 string.push_str(&self.as_str());
112 impl Decodable for Ident {
113 fn decode<D: Decoder>(d: &mut D) -> Result<Ident, D::Error> {
114 let string = d.read_str()?;
115 Ok(if !string.starts_with('#') {
116 Ident::from_str(&string)
117 } else { // FIXME(jseyfried) intercrate hygiene
118 Ident::with_empty_ctxt(Symbol::gensym(&string[1..]))
123 /// A symbol is an interned or gensymed string.
124 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
125 pub struct Symbol(u32);
127 // The interner is pointed to by a thread local value which is only set on the main thread
128 // with parallelization is disabled. So we don't allow Symbol to transfer between threads
129 // to avoid panics and other errors, even though it would be memory safe to do so.
130 #[cfg(not(parallel_queries))]
131 impl !Send for Symbol { }
132 #[cfg(not(parallel_queries))]
133 impl !Sync for Symbol { }
136 /// Maps a string to its interned representation.
137 pub fn intern(string: &str) -> Self {
138 with_interner(|interner| interner.intern(string))
141 pub fn interned(self) -> Self {
142 with_interner(|interner| interner.interned(self))
145 /// gensym's a new usize, using the current interner.
146 pub fn gensym(string: &str) -> Self {
147 with_interner(|interner| interner.gensym(string))
150 pub fn gensymed(self) -> Self {
151 with_interner(|interner| interner.gensymed(self))
154 pub fn as_str(self) -> LocalInternedString {
155 with_interner(|interner| unsafe {
156 LocalInternedString {
157 string: ::std::mem::transmute::<&str, &str>(interner.get(self))
162 pub fn as_interned_str(self) -> InternedString {
163 with_interner(|interner| InternedString {
164 symbol: interner.interned(self)
168 pub fn as_u32(self) -> u32 {
173 impl fmt::Debug for Symbol {
174 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
175 let is_gensymed = with_interner(|interner| interner.is_gensymed(*self));
177 write!(f, "{}({})", self, self.0)
179 write!(f, "{}", self)
184 impl fmt::Display for Symbol {
185 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
186 fmt::Display::fmt(&self.as_str(), f)
190 impl Encodable for Symbol {
191 fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
192 s.emit_str(&self.as_str())
196 impl Decodable for Symbol {
197 fn decode<D: Decoder>(d: &mut D) -> Result<Symbol, D::Error> {
198 Ok(Symbol::intern(&d.read_str()?))
202 impl<T: ::std::ops::Deref<Target=str>> PartialEq<T> for Symbol {
203 fn eq(&self, other: &T) -> bool {
204 self.as_str() == other.deref()
208 // The &'static strs in this type actually point into the arena
209 pub struct Interner {
210 arena: DroplessArena,
211 names: FxHashMap<&'static str, Symbol>,
212 strings: Vec<&'static str>,
213 gensyms: Vec<Symbol>,
217 pub fn new() -> Self {
219 arena: DroplessArena::new(),
220 names: Default::default(),
221 strings: Default::default(),
222 gensyms: Default::default(),
226 fn prefill(init: &[&str]) -> Self {
227 let mut this = Interner::new();
228 for &string in init {
230 // We can't allocate empty strings in the arena, so handle this here
231 let name = Symbol(this.strings.len() as u32);
232 this.names.insert("", name);
233 this.strings.push("");
241 pub fn intern(&mut self, string: &str) -> Symbol {
242 if let Some(&name) = self.names.get(string) {
246 let name = Symbol(self.strings.len() as u32);
248 // from_utf8_unchecked is safe since we just allocated a &str which is known to be utf8
249 let string: &str = unsafe {
250 str::from_utf8_unchecked(self.arena.alloc_slice(string.as_bytes()))
252 // It is safe to extend the arena allocation to 'static because we only access
253 // these while the arena is still alive
254 let string: &'static str = unsafe {
255 &*(string as *const str)
257 self.strings.push(string);
258 self.names.insert(string, name);
262 pub fn interned(&self, symbol: Symbol) -> Symbol {
263 if (symbol.0 as usize) < self.strings.len() {
266 self.interned(self.gensyms[(!0 - symbol.0) as usize])
270 fn gensym(&mut self, string: &str) -> Symbol {
271 let symbol = self.intern(string);
272 self.gensymed(symbol)
275 fn gensymed(&mut self, symbol: Symbol) -> Symbol {
276 self.gensyms.push(symbol);
277 Symbol(!0 - self.gensyms.len() as u32 + 1)
280 fn is_gensymed(&mut self, symbol: Symbol) -> bool {
281 symbol.0 as usize >= self.strings.len()
284 pub fn get(&self, symbol: Symbol) -> &str {
285 match self.strings.get(symbol.0 as usize) {
286 Some(string) => string,
287 None => self.get(self.gensyms[(!0 - symbol.0) as usize]),
292 // In this macro, there is the requirement that the name (the number) must be monotonically
293 // increasing by one in the special identifiers, starting at 0; the same holds for the keywords,
294 // except starting from the next number instead of zero.
295 macro_rules! declare_keywords {(
296 $( ($index: expr, $konst: ident, $string: expr) )*
299 use super::{Symbol, Ident};
300 #[derive(Clone, Copy, PartialEq, Eq)]
305 #[inline] pub fn ident(self) -> Ident { self.ident }
306 #[inline] pub fn name(self) -> Symbol { self.ident.name }
309 #[allow(non_upper_case_globals)]
310 pub const $konst: Keyword = Keyword {
311 ident: Ident::with_empty_ctxt(super::Symbol($index))
315 impl ::std::str::FromStr for Keyword {
318 fn from_str(s: &str) -> Result<Self, ()> {
320 $($string => Ok($konst),)*
328 pub fn fresh() -> Self {
329 Interner::prefill(&[$($string,)*])
334 // NB: leaving holes in the ident table is bad! a different ident will get
335 // interned with the id from the hole, but it will be between the min and max
336 // of the reserved words, and thus tagged as "reserved".
337 // After modifying this list adjust `is_special`, `is_used_keyword`/`is_unused_keyword`,
338 // this should be rarely necessary though if the keywords are kept in alphabetic order.
340 // Special reserved identifiers used internally for elided lifetimes,
341 // unnamed method parameters, crate root module, error recovery etc.
343 (1, CrateRoot, "{{root}}")
344 (2, DollarCrate, "$crate")
347 // Keywords used in the language.
352 (8, Continue, "continue")
356 (12, Extern, "extern")
371 (27, Return, "return")
372 (28, SelfValue, "self")
373 (29, SelfType, "Self")
374 (30, Static, "static")
375 (31, Struct, "struct")
380 (36, Unsafe, "unsafe")
385 // Keywords reserved for future use.
386 (40, Abstract, "abstract")
387 (41, Become, "become")
391 (45, Override, "override")
393 (47, Typeof, "typeof")
394 (48, Unsized, "unsized")
395 (49, Virtual, "virtual")
398 // Edition-specific keywords reserved for future use.
399 (51, Async, "async") // >= 2018 Edition Only
401 // Special lifetime names
402 (52, UnderscoreLifetime, "'_")
403 (53, StaticLifetime, "'static")
405 // Weak keywords, have special meaning only in specific contexts.
408 (56, Default, "default")
414 fn is_unused_keyword_2018(self) -> bool {
415 self == keywords::Async.name()
420 // Returns true for reserved identifiers used internally for elided lifetimes,
421 // unnamed method parameters, crate root module, error recovery etc.
422 pub fn is_special(self) -> bool {
423 self.name <= keywords::Underscore.name()
426 /// Returns `true` if the token is a keyword used in the language.
427 pub fn is_used_keyword(self) -> bool {
428 self.name >= keywords::As.name() && self.name <= keywords::While.name()
431 /// Returns `true` if the token is a keyword reserved for possible future use.
432 pub fn is_unused_keyword(self) -> bool {
433 // Note: `span.edition()` is relatively expensive, don't call it unless necessary.
434 self.name >= keywords::Abstract.name() && self.name <= keywords::Yield.name() ||
435 self.name.is_unused_keyword_2018() && self.span.edition() == Edition::Edition2018
438 /// Returns `true` if the token is either a special identifier or a keyword.
439 pub fn is_reserved(self) -> bool {
440 self.is_special() || self.is_used_keyword() || self.is_unused_keyword()
443 /// A keyword or reserved identifier that can be used as a path segment.
444 pub fn is_path_segment_keyword(self) -> bool {
445 self.name == keywords::Super.name() ||
446 self.name == keywords::SelfValue.name() ||
447 self.name == keywords::SelfType.name() ||
448 self.name == keywords::Extern.name() ||
449 self.name == keywords::Crate.name() ||
450 self.name == keywords::CrateRoot.name() ||
451 self.name == keywords::DollarCrate.name()
454 // We see this identifier in a normal identifier position, like variable name or a type.
455 // How was it written originally? Did it use the raw form? Let's try to guess.
456 pub fn is_raw_guess(self) -> bool {
457 self.name != keywords::Invalid.name() &&
458 self.is_reserved() && !self.is_path_segment_keyword()
462 // If an interner exists, return it. Otherwise, prepare a fresh one.
464 fn with_interner<T, F: FnOnce(&mut Interner) -> T>(f: F) -> T {
465 GLOBALS.with(|globals| f(&mut *globals.symbol_interner.lock()))
468 /// Represents a string stored in the interner. Because the interner outlives any thread
469 /// which uses this type, we can safely treat `string` which points to interner data,
470 /// as an immortal string, as long as this type never crosses between threads.
471 // FIXME: Ensure that the interner outlives any thread which uses LocalInternedString,
472 // by creating a new thread right after constructing the interner
473 #[derive(Clone, Copy, Hash, PartialOrd, Eq, Ord)]
474 pub struct LocalInternedString {
475 string: &'static str,
478 impl LocalInternedString {
479 pub fn as_interned_str(self) -> InternedString {
481 symbol: Symbol::intern(self.string)
486 impl<U: ?Sized> ::std::convert::AsRef<U> for LocalInternedString
488 str: ::std::convert::AsRef<U>
490 fn as_ref(&self) -> &U {
495 impl<T: ::std::ops::Deref<Target = str>> ::std::cmp::PartialEq<T> for LocalInternedString {
496 fn eq(&self, other: &T) -> bool {
497 self.string == other.deref()
501 impl ::std::cmp::PartialEq<LocalInternedString> for str {
502 fn eq(&self, other: &LocalInternedString) -> bool {
507 impl<'a> ::std::cmp::PartialEq<LocalInternedString> for &'a str {
508 fn eq(&self, other: &LocalInternedString) -> bool {
509 *self == other.string
513 impl ::std::cmp::PartialEq<LocalInternedString> for String {
514 fn eq(&self, other: &LocalInternedString) -> bool {
519 impl<'a> ::std::cmp::PartialEq<LocalInternedString> for &'a String {
520 fn eq(&self, other: &LocalInternedString) -> bool {
521 *self == other.string
525 impl !Send for LocalInternedString {}
526 impl !Sync for LocalInternedString {}
528 impl ::std::ops::Deref for LocalInternedString {
530 fn deref(&self) -> &str { self.string }
533 impl fmt::Debug for LocalInternedString {
534 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
535 fmt::Debug::fmt(self.string, f)
539 impl fmt::Display for LocalInternedString {
540 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
541 fmt::Display::fmt(self.string, f)
545 impl Decodable for LocalInternedString {
546 fn decode<D: Decoder>(d: &mut D) -> Result<LocalInternedString, D::Error> {
547 Ok(Symbol::intern(&d.read_str()?).as_str())
551 impl Encodable for LocalInternedString {
552 fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
553 s.emit_str(self.string)
557 /// Represents a string stored in the string interner
558 #[derive(Clone, Copy, Eq)]
559 pub struct InternedString {
563 impl InternedString {
564 pub fn with<F: FnOnce(&str) -> R, R>(self, f: F) -> R {
565 let str = with_interner(|interner| {
566 interner.get(self.symbol) as *const str
568 // This is safe because the interner keeps string alive until it is dropped.
569 // We can access it because we know the interner is still alive since we use a
570 // scoped thread local to access it, and it was alive at the begining of this scope
574 pub fn as_symbol(self) -> Symbol {
578 pub fn as_str(self) -> LocalInternedString {
583 impl Hash for InternedString {
584 fn hash<H: Hasher>(&self, state: &mut H) {
585 self.with(|str| str.hash(state))
589 impl PartialOrd<InternedString> for InternedString {
590 fn partial_cmp(&self, other: &InternedString) -> Option<Ordering> {
591 if self.symbol == other.symbol {
592 return Some(Ordering::Equal);
594 self.with(|self_str| other.with(|other_str| self_str.partial_cmp(other_str)))
598 impl Ord for InternedString {
599 fn cmp(&self, other: &InternedString) -> Ordering {
600 if self.symbol == other.symbol {
601 return Ordering::Equal;
603 self.with(|self_str| other.with(|other_str| self_str.cmp(&other_str)))
607 impl<T: ::std::ops::Deref<Target = str>> PartialEq<T> for InternedString {
608 fn eq(&self, other: &T) -> bool {
609 self.with(|string| string == other.deref())
613 impl PartialEq<InternedString> for InternedString {
614 fn eq(&self, other: &InternedString) -> bool {
615 self.symbol == other.symbol
619 impl PartialEq<InternedString> for str {
620 fn eq(&self, other: &InternedString) -> bool {
621 other.with(|string| self == string)
625 impl<'a> PartialEq<InternedString> for &'a str {
626 fn eq(&self, other: &InternedString) -> bool {
627 other.with(|string| *self == string)
631 impl PartialEq<InternedString> for String {
632 fn eq(&self, other: &InternedString) -> bool {
633 other.with(|string| self == string)
637 impl<'a> PartialEq<InternedString> for &'a String {
638 fn eq(&self, other: &InternedString) -> bool {
639 other.with(|string| *self == string)
643 impl ::std::convert::From<InternedString> for String {
644 fn from(val: InternedString) -> String {
645 val.as_symbol().to_string()
649 impl fmt::Debug for InternedString {
650 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
651 self.with(|str| fmt::Debug::fmt(&str, f))
655 impl fmt::Display for InternedString {
656 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
657 self.with(|str| fmt::Display::fmt(&str, f))
661 impl Decodable for InternedString {
662 fn decode<D: Decoder>(d: &mut D) -> Result<InternedString, D::Error> {
663 Ok(Symbol::intern(&d.read_str()?).as_interned_str())
667 impl Encodable for InternedString {
668 fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
669 self.with(|string| s.emit_str(string))
679 fn interner_tests() {
680 let mut i: Interner = Interner::new();
681 // first one is zero:
682 assert_eq!(i.intern("dog"), Symbol(0));
683 // re-use gets the same entry:
684 assert_eq!(i.intern("dog"), Symbol(0));
685 // different string gets a different #:
686 assert_eq!(i.intern("cat"), Symbol(1));
687 assert_eq!(i.intern("cat"), Symbol(1));
688 // dog is still at zero
689 assert_eq!(i.intern("dog"), Symbol(0));
690 assert_eq!(i.gensym("zebra"), Symbol(4294967295));
691 // gensym of same string gets new number :
692 assert_eq!(i.gensym("zebra"), Symbol(4294967294));
693 // gensym of *existing* string gets new number:
694 assert_eq!(i.gensym("dog"), Symbol(4294967293));
698 fn without_first_quote_test() {
699 GLOBALS.set(&Globals::new(), || {
700 let i = Ident::from_str("'break");
701 assert_eq!(i.without_first_quote().name, keywords::Break.name());