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.
15 use hygiene::SyntaxContext;
16 use {Span, DUMMY_SP, GLOBALS};
18 use rustc_data_structures::fx::FxHashMap;
19 use serialize::{Decodable, Decoder, Encodable, Encoder};
21 use std::hash::{Hash, Hasher};
23 #[derive(Copy, Clone, Eq)]
31 pub const fn new(name: Symbol, span: Span) -> Ident {
35 pub const fn with_empty_ctxt(name: Symbol) -> Ident {
36 Ident::new(name, DUMMY_SP)
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))
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()))
49 pub fn without_first_quote(self) -> Ident {
50 Ident::new(Symbol::intern(self.name.as_str().trim_left_matches('\'')), self.span)
53 pub fn modern(self) -> Ident {
54 Ident::new(self.name, self.span.modern())
57 pub fn gensym(self) -> Ident {
58 Ident::new(self.name.gensymed(), self.span)
62 impl PartialEq for Ident {
63 fn eq(&self, rhs: &Self) -> bool {
64 self.name == rhs.name && self.span.ctxt() == rhs.span.ctxt()
69 fn hash<H: Hasher>(&self, state: &mut H) {
70 self.name.hash(state);
71 self.span.ctxt().hash(state);
75 impl fmt::Debug for Ident {
76 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
77 write!(f, "{}{:?}", self.name, self.span.ctxt())
81 impl fmt::Display for Ident {
82 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
83 fmt::Display::fmt(&self.name, f)
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());
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..]))
110 /// A symbol is an interned or gensymed string.
111 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
112 pub struct Symbol(u32);
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 { }
123 /// Maps a string to its interned representation.
124 pub fn intern(string: &str) -> Self {
125 with_interner(|interner| interner.intern(string))
128 pub fn interned(self) -> Self {
129 with_interner(|interner| interner.interned(self))
132 /// gensym's a new usize, using the current interner.
133 pub fn gensym(string: &str) -> Self {
134 with_interner(|interner| interner.gensym(string))
137 pub fn gensymed(self) -> Self {
138 with_interner(|interner| interner.gensymed(self))
141 pub fn as_str(self) -> InternedString {
142 with_interner(|interner| unsafe {
144 string: ::std::mem::transmute::<&str, &str>(interner.get(self))
149 pub fn as_u32(self) -> u32 {
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));
158 write!(f, "{}({})", self, self.0)
160 write!(f, "{}", self)
165 impl fmt::Display for Symbol {
166 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
167 fmt::Display::fmt(&self.as_str(), f)
171 impl Encodable for Symbol {
172 fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
173 s.emit_str(&self.as_str())
177 impl Decodable for Symbol {
178 fn decode<D: Decoder>(d: &mut D) -> Result<Symbol, D::Error> {
179 Ok(Symbol::intern(&d.read_str()?))
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()
190 pub struct Interner {
191 names: FxHashMap<Box<str>, Symbol>,
192 strings: Vec<Box<str>>,
193 gensyms: Vec<Symbol>,
197 pub fn new() -> Self {
201 fn prefill(init: &[&str]) -> Self {
202 let mut this = Interner::new();
203 for &string in init {
209 pub fn intern(&mut self, string: &str) -> Symbol {
210 if let Some(&name) = self.names.get(string) {
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);
221 pub fn interned(&self, symbol: Symbol) -> Symbol {
222 if (symbol.0 as usize) < self.strings.len() {
225 self.interned(self.gensyms[(!0 - symbol.0) as usize])
229 fn gensym(&mut self, string: &str) -> Symbol {
230 let symbol = self.intern(string);
231 self.gensymed(symbol)
234 fn gensymed(&mut self, symbol: Symbol) -> Symbol {
235 self.gensyms.push(symbol);
236 Symbol(!0 - self.gensyms.len() as u32 + 1)
239 fn is_gensymed(&mut self, symbol: Symbol) -> bool {
240 symbol.0 as usize >= self.strings.len()
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]),
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) )*
258 use super::{Symbol, Ident};
259 #[derive(Clone, Copy, PartialEq, Eq)]
264 #[inline] pub fn ident(self) -> Ident { self.ident }
265 #[inline] pub fn name(self) -> Symbol { self.ident.name }
268 #[allow(non_upper_case_globals)]
269 pub const $konst: Keyword = Keyword {
270 ident: Ident::with_empty_ctxt(super::Symbol($index))
276 pub fn fresh() -> Self {
277 Interner::prefill(&[$($string,)*])
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.
288 // Special reserved identifiers used internally for elided lifetimes,
289 // unnamed method parameters, crate root module, error recovery etc.
291 (1, CrateRoot, "{{root}}")
292 (2, DollarCrate, "$crate")
295 // Keywords used in the language.
300 (8, Continue, "continue")
304 (12, Extern, "extern")
319 (27, Return, "return")
320 (28, SelfValue, "self")
321 (29, SelfType, "Self")
322 (30, Static, "static")
323 (31, Struct, "struct")
328 (36, Unsafe, "unsafe")
333 // Keywords reserved for future use.
334 (40, Abstract, "abstract")
335 (41, Alignof, "alignof")
336 (42, Become, "become")
340 (46, Offsetof, "offsetof")
341 (47, Override, "override")
344 (50, Sizeof, "sizeof")
345 (51, Typeof, "typeof")
346 (52, Unsized, "unsized")
347 (53, Virtual, "virtual")
350 // Special lifetime names
351 (55, UnderscoreLifetime, "'_")
352 (56, StaticLifetime, "'static")
354 // Weak keywords, have special meaning only in specific contexts.
357 (59, Default, "default")
362 // If an interner exists, return it. Otherwise, prepare a fresh one.
364 fn with_interner<T, F: FnOnce(&mut Interner) -> T>(f: F) -> T {
365 GLOBALS.with(|globals| f(&mut *globals.symbol_interner.lock()))
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.
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
377 #[derive(Clone, Copy, Hash, PartialOrd, Eq, Ord)]
378 pub struct InternedString {
379 string: &'static str,
382 impl<U: ?Sized> ::std::convert::AsRef<U> for InternedString where str: ::std::convert::AsRef<U> {
383 fn as_ref(&self) -> &U {
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()
394 impl ::std::cmp::PartialEq<InternedString> for str {
395 fn eq(&self, other: &InternedString) -> bool {
400 impl<'a> ::std::cmp::PartialEq<InternedString> for &'a str {
401 fn eq(&self, other: &InternedString) -> bool {
402 *self == other.string
406 impl ::std::cmp::PartialEq<InternedString> for String {
407 fn eq(&self, other: &InternedString) -> bool {
412 impl<'a> ::std::cmp::PartialEq<InternedString> for &'a String {
413 fn eq(&self, other: &InternedString) -> bool {
414 *self == other.string
418 impl !Send for InternedString { }
420 impl ::std::ops::Deref for InternedString {
422 fn deref(&self) -> &str { self.string }
425 impl fmt::Debug for InternedString {
426 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
427 fmt::Debug::fmt(self.string, f)
431 impl fmt::Display for InternedString {
432 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
433 fmt::Display::fmt(self.string, f)
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())
443 impl Encodable for InternedString {
444 fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
445 s.emit_str(self.string)
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));
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());