]> git.lizzy.rs Git - rust.git/blob - src/libsyntax_pos/symbol.rs
Rollup merge of #62453 - zackmdavis:single_path, r=estebank
[rust.git] / src / libsyntax_pos / symbol.rs
1 //! An "interner" is a data structure that associates values with usize tags and
2 //! allows bidirectional lookup; i.e., given a value, one can easily find the
3 //! type, and vice versa.
4
5 use arena::DroplessArena;
6 use rustc_data_structures::fx::FxHashMap;
7 use rustc_data_structures::indexed_vec::Idx;
8 use rustc_data_structures::newtype_index;
9 use rustc_macros::symbols;
10 use serialize::{Decodable, Decoder, Encodable, Encoder};
11
12 use std::cmp::{PartialEq, Ordering, PartialOrd, Ord};
13 use std::fmt;
14 use std::hash::{Hash, Hasher};
15 use std::str;
16
17 use crate::hygiene::SyntaxContext;
18 use crate::{Span, DUMMY_SP, GLOBALS};
19
20 symbols! {
21     // After modifying this list adjust `is_special`, `is_used_keyword`/`is_unused_keyword`,
22     // this should be rarely necessary though if the keywords are kept in alphabetic order.
23     Keywords {
24         // Special reserved identifiers used internally for elided lifetimes,
25         // unnamed method parameters, crate root module, error recovery etc.
26         Invalid:            "",
27         PathRoot:           "{{root}}",
28         DollarCrate:        "$crate",
29         Underscore:         "_",
30
31         // Keywords that are used in stable Rust.
32         As:                 "as",
33         Break:              "break",
34         Const:              "const",
35         Continue:           "continue",
36         Crate:              "crate",
37         Else:               "else",
38         Enum:               "enum",
39         Extern:             "extern",
40         False:              "false",
41         Fn:                 "fn",
42         For:                "for",
43         If:                 "if",
44         Impl:               "impl",
45         In:                 "in",
46         Let:                "let",
47         Loop:               "loop",
48         Match:              "match",
49         Mod:                "mod",
50         Move:               "move",
51         Mut:                "mut",
52         Pub:                "pub",
53         Ref:                "ref",
54         Return:             "return",
55         SelfLower:          "self",
56         SelfUpper:          "Self",
57         Static:             "static",
58         Struct:             "struct",
59         Super:              "super",
60         Trait:              "trait",
61         True:               "true",
62         Type:               "type",
63         Unsafe:             "unsafe",
64         Use:                "use",
65         Where:              "where",
66         While:              "while",
67
68         // Keywords that are used in unstable Rust or reserved for future use.
69         Abstract:           "abstract",
70         Become:             "become",
71         Box:                "box",
72         Do:                 "do",
73         Final:              "final",
74         Macro:              "macro",
75         Override:           "override",
76         Priv:               "priv",
77         Typeof:             "typeof",
78         Unsized:            "unsized",
79         Virtual:            "virtual",
80         Yield:              "yield",
81
82         // Edition-specific keywords that are used in stable Rust.
83         Dyn:                "dyn", // >= 2018 Edition only
84
85         // Edition-specific keywords that are used in unstable Rust or reserved for future use.
86         Async:              "async", // >= 2018 Edition only
87         Await:              "await", // >= 2018 Edition only
88         Try:                "try", // >= 2018 Edition only
89
90         // Special lifetime names
91         UnderscoreLifetime: "'_",
92         StaticLifetime:     "'static",
93
94         // Weak keywords, have special meaning only in specific contexts.
95         Auto:               "auto",
96         Catch:              "catch",
97         Default:            "default",
98         Existential:        "existential",
99         Union:              "union",
100     }
101
102     // Symbols that can be referred to with syntax_pos::sym::*. The symbol is
103     // the stringified identifier unless otherwise specified (e.g.
104     // `proc_dash_macro` represents "proc-macro").
105     //
106     // As well as the symbols listed, there are symbols for the the strings
107     // "0", "1", ..., "9", which are accessible via `sym::integer`.
108     Symbols {
109         aarch64_target_feature,
110         abi,
111         abi_amdgpu_kernel,
112         abi_msp430_interrupt,
113         abi_ptx,
114         abi_sysv64,
115         abi_thiscall,
116         abi_unadjusted,
117         abi_vectorcall,
118         abi_x86_interrupt,
119         aborts,
120         advanced_slice_patterns,
121         adx_target_feature,
122         alias,
123         align,
124         alignstack,
125         all,
126         allocator,
127         allocator_internals,
128         alloc_error_handler,
129         allow,
130         allowed,
131         allow_fail,
132         allow_internal_unsafe,
133         allow_internal_unstable,
134         allow_internal_unstable_backcompat_hack,
135         always,
136         and,
137         any,
138         arbitrary_enum_discriminant,
139         arbitrary_self_types,
140         Arguments,
141         ArgumentV1,
142         arm_target_feature,
143         asm,
144         assert,
145         associated_consts,
146         associated_type_bounds,
147         associated_type_defaults,
148         associated_types,
149         async_await,
150         async_closure,
151         attr,
152         attributes,
153         attr_literals,
154         augmented_assignments,
155         automatically_derived,
156         avx512_target_feature,
157         await_macro,
158         begin_panic,
159         bench,
160         bin,
161         bind_by_move_pattern_guards,
162         block,
163         bool,
164         borrowck_graphviz_postflow,
165         borrowck_graphviz_preflow,
166         box_patterns,
167         box_syntax,
168         braced_empty_structs,
169         C,
170         cdylib,
171         cfg,
172         cfg_attr,
173         cfg_attr_multi,
174         cfg_doctest,
175         cfg_target_feature,
176         cfg_target_has_atomic,
177         cfg_target_thread_local,
178         cfg_target_vendor,
179         char,
180         clippy,
181         clone,
182         Clone,
183         clone_closures,
184         clone_from,
185         closure_to_fn_coercion,
186         cmp,
187         cmpxchg16b_target_feature,
188         cold,
189         column,
190         compile_error,
191         compiler_builtins,
192         concat,
193         concat_idents,
194         conservative_impl_trait,
195         console,
196         const_compare_raw_pointers,
197         const_constructor,
198         const_fn,
199         const_fn_union,
200         const_generics,
201         const_indexing,
202         const_let,
203         const_panic,
204         const_raw_ptr_deref,
205         const_raw_ptr_to_usize_cast,
206         const_transmute,
207         contents,
208         context,
209         convert,
210         Copy,
211         copy_closures,
212         core,
213         core_intrinsics,
214         crate_id,
215         crate_in_paths,
216         crate_local,
217         crate_name,
218         crate_type,
219         crate_visibility_modifier,
220         custom_attribute,
221         custom_derive,
222         custom_inner_attributes,
223         custom_test_frameworks,
224         c_variadic,
225         Debug,
226         declare_lint_pass,
227         decl_macro,
228         Decodable,
229         Default,
230         default_lib_allocator,
231         default_type_parameter_fallback,
232         default_type_params,
233         deny,
234         deprecated,
235         deref,
236         deref_mut,
237         derive,
238         direct,
239         doc,
240         doc_alias,
241         doc_cfg,
242         doc_keyword,
243         doc_masked,
244         doc_spotlight,
245         doctest,
246         document_private_items,
247         dotdoteq_in_patterns,
248         dotdot_in_tuple_patterns,
249         double_braced_crate: "{{crate}}",
250         double_braced_impl: "{{impl}}",
251         double_braced_misc: "{{misc}}",
252         double_braced_closure: "{{closure}}",
253         double_braced_constructor: "{{constructor}}",
254         double_braced_constant: "{{constant}}",
255         double_braced_opaque: "{{opaque}}",
256         dropck_eyepatch,
257         dropck_parametricity,
258         drop_types_in_const,
259         dylib,
260         dyn_trait,
261         eh_personality,
262         eh_unwind_resume,
263         enable,
264         Encodable,
265         env,
266         eq,
267         err,
268         Err,
269         Eq,
270         Equal,
271         except,
272         exclusive_range_pattern,
273         exhaustive_integer_patterns,
274         exhaustive_patterns,
275         existential_type,
276         expected,
277         export_name,
278         expr,
279         extern_absolute_paths,
280         external_doc,
281         extern_crate_item_prelude,
282         extern_crate_self,
283         extern_in_paths,
284         extern_prelude,
285         extern_types,
286         f16c_target_feature,
287         f32,
288         f64,
289         feature,
290         ffi_returns_twice,
291         field,
292         field_init_shorthand,
293         file,
294         fmt,
295         fmt_internals,
296         fn_must_use,
297         forbid,
298         format_args,
299         format_args_nl,
300         from,
301         From,
302         from_desugaring,
303         from_error,
304         from_generator,
305         from_method,
306         from_ok,
307         from_usize,
308         fundamental,
309         future,
310         Future,
311         FxHashSet,
312         FxHashMap,
313         gen_future,
314         generators,
315         generic_associated_types,
316         generic_param_attrs,
317         global_allocator,
318         global_asm,
319         globs,
320         hash,
321         Hash,
322         HashSet,
323         HashMap,
324         hexagon_target_feature,
325         hidden,
326         homogeneous_aggregate,
327         html_favicon_url,
328         html_logo_url,
329         html_no_source,
330         html_playground_url,
331         html_root_url,
332         i128,
333         i128_type,
334         i16,
335         i32,
336         i64,
337         i8,
338         ident,
339         if_let,
340         if_while_or_patterns,
341         ignore,
342         impl_header_lifetime_elision,
343         impl_lint_pass,
344         impl_trait_in_bindings,
345         import_shadowing,
346         index,
347         index_mut,
348         in_band_lifetimes,
349         include,
350         include_bytes,
351         include_str,
352         inclusive_range_syntax,
353         infer_outlives_requirements,
354         infer_static_outlives_requirements,
355         inline,
356         intel,
357         into_iter,
358         IntoIterator,
359         into_result,
360         intrinsics,
361         irrefutable_let_patterns,
362         isize,
363         issue,
364         issue_5723_bootstrap,
365         issue_tracker_base_url,
366         item,
367         item_like_imports,
368         iter,
369         Iterator,
370         keyword,
371         kind,
372         label,
373         label_break_value,
374         lang,
375         lang_items,
376         let_chains,
377         lhs,
378         lib,
379         lifetime,
380         line,
381         link,
382         linkage,
383         link_args,
384         link_cfg,
385         link_llvm_intrinsics,
386         link_name,
387         link_section,
388         LintPass,
389         lint_reasons,
390         literal,
391         local_inner_macros,
392         log_syntax,
393         loop_break_value,
394         macro_at_most_once_rep,
395         macro_escape,
396         macro_export,
397         macro_lifetime_matcher,
398         macro_literal_matcher,
399         macro_reexport,
400         macro_rules,
401         macros_in_extern,
402         macro_use,
403         macro_vis_matcher,
404         main,
405         managed_boxes,
406         marker,
407         marker_trait_attr,
408         masked,
409         match_beginning_vert,
410         match_default_bindings,
411         may_dangle,
412         member_constraints,
413         message,
414         meta,
415         min_const_fn,
416         min_const_unsafe_fn,
417         mips_target_feature,
418         mmx_target_feature,
419         module,
420         module_path,
421         more_struct_aliases,
422         movbe_target_feature,
423         must_use,
424         naked,
425         naked_functions,
426         name,
427         needs_allocator,
428         needs_panic_runtime,
429         negate_unsigned,
430         never,
431         never_type,
432         new,
433         next,
434         __next,
435         nll,
436         no_builtins,
437         no_core,
438         no_crate_inject,
439         no_debug,
440         no_default_passes,
441         no_implicit_prelude,
442         no_inline,
443         no_link,
444         no_main,
445         no_mangle,
446         non_ascii_idents,
447         None,
448         non_exhaustive,
449         non_modrs_mods,
450         no_stack_check,
451         no_start,
452         no_std,
453         not,
454         note,
455         Ok,
456         omit_gdb_pretty_printer_section,
457         on,
458         on_unimplemented,
459         oom,
460         ops,
461         optimize,
462         optimize_attribute,
463         optin_builtin_traits,
464         option,
465         Option,
466         option_env,
467         opt_out_copy,
468         or,
469         Ord,
470         Ordering,
471         Output,
472         overlapping_marker_traits,
473         packed,
474         panic,
475         panic_handler,
476         panic_impl,
477         panic_implementation,
478         panic_runtime,
479         parent_trait,
480         partial_cmp,
481         param_attrs,
482         PartialEq,
483         PartialOrd,
484         passes,
485         pat,
486         path,
487         pattern_parentheses,
488         Pending,
489         pin,
490         Pin,
491         pinned,
492         platform_intrinsics,
493         plugin,
494         plugin_registrar,
495         plugins,
496         Poll,
497         poll_with_tls_context,
498         powerpc_target_feature,
499         precise_pointer_size_matching,
500         prelude,
501         prelude_import,
502         primitive,
503         proc_dash_macro: "proc-macro",
504         proc_macro,
505         proc_macro_attribute,
506         proc_macro_def_site,
507         proc_macro_derive,
508         proc_macro_expr,
509         proc_macro_gen,
510         proc_macro_hygiene,
511         proc_macro_internals,
512         proc_macro_mod,
513         proc_macro_non_items,
514         proc_macro_path_invoc,
515         profiler_runtime,
516         pub_restricted,
517         pushpop_unsafe,
518         quad_precision_float,
519         question_mark,
520         quote,
521         Range,
522         RangeFrom,
523         RangeFull,
524         RangeInclusive,
525         RangeTo,
526         RangeToInclusive,
527         raw_identifiers,
528         Ready,
529         reason,
530         recursion_limit,
531         reexport_test_harness_main,
532         reflect,
533         relaxed_adts,
534         repr,
535         repr128,
536         repr_align,
537         repr_align_enum,
538         repr_packed,
539         repr_simd,
540         repr_transparent,
541         re_rebalance_coherence,
542         result,
543         Result,
544         Return,
545         rhs,
546         rlib,
547         rt,
548         rtm_target_feature,
549         rust,
550         rust_2015_preview,
551         rust_2018_preview,
552         rust_begin_unwind,
553         rustc,
554         RustcDecodable,
555         RustcEncodable,
556         rustc_allocator,
557         rustc_allocator_nounwind,
558         rustc_allow_const_fn_ptr,
559         rustc_args_required_const,
560         rustc_attrs,
561         rustc_builtin_macro,
562         rustc_clean,
563         rustc_const_unstable,
564         rustc_conversion_suggestion,
565         rustc_copy_clone_marker,
566         rustc_def_path,
567         rustc_deprecated,
568         rustc_diagnostic_macros,
569         rustc_dirty,
570         rustc_dummy,
571         rustc_dump_env_program_clauses,
572         rustc_dump_program_clauses,
573         rustc_dump_user_substs,
574         rustc_error,
575         rustc_expected_cgu_reuse,
576         rustc_if_this_changed,
577         rustc_inherit_overflow_checks,
578         rustc_layout,
579         rustc_layout_scalar_valid_range_end,
580         rustc_layout_scalar_valid_range_start,
581         rustc_macro_transparency,
582         rustc_mir,
583         rustc_nonnull_optimization_guaranteed,
584         rustc_object_lifetime_default,
585         rustc_on_unimplemented,
586         rustc_outlives,
587         rustc_paren_sugar,
588         rustc_partition_codegened,
589         rustc_partition_reused,
590         rustc_peek,
591         rustc_peek_definite_init,
592         rustc_peek_maybe_init,
593         rustc_peek_maybe_uninit,
594         rustc_private,
595         rustc_proc_macro_decls,
596         rustc_promotable,
597         rustc_regions,
598         rustc_stable,
599         rustc_std_internal_symbol,
600         rustc_symbol_name,
601         rustc_synthetic,
602         rustc_test_marker,
603         rustc_then_this_would_need,
604         rustc_variance,
605         rustdoc,
606         rust_eh_personality,
607         rust_eh_unwind_resume,
608         rust_oom,
609         __rust_unstable_column,
610         rvalue_static_promotion,
611         sanitizer_runtime,
612         _Self,
613         self_in_typedefs,
614         self_struct_ctor,
615         should_panic,
616         simd,
617         simd_ffi,
618         since,
619         size,
620         slice_patterns,
621         slicing_syntax,
622         Some,
623         specialization,
624         speed,
625         spotlight,
626         sse4a_target_feature,
627         stable,
628         staged_api,
629         start,
630         static_in_const,
631         staticlib,
632         static_nobundle,
633         static_recursion,
634         std,
635         std_inject,
636         str,
637         stringify,
638         stmt,
639         stmt_expr_attributes,
640         stop_after_dataflow,
641         struct_field_attributes,
642         struct_inherit,
643         structural_match,
644         struct_variant,
645         sty,
646         suggestion,
647         target_feature,
648         target_has_atomic,
649         target_thread_local,
650         task,
651         tbm_target_feature,
652         termination_trait,
653         termination_trait_test,
654         test,
655         test_2018_feature,
656         test_accepted_feature,
657         test_case,
658         test_removed_feature,
659         test_runner,
660         then_with,
661         thread_local,
662         tool_attributes,
663         tool_lints,
664         trace_macros,
665         trait_alias,
666         transmute,
667         transparent,
668         transparent_enums,
669         transparent_unions,
670         trivial_bounds,
671         Try,
672         try_blocks,
673         try_trait,
674         tt,
675         tuple_indexing,
676         Ty,
677         ty,
678         TyCtxt,
679         TyKind,
680         type_alias_enum_variants,
681         type_ascription,
682         type_length_limit,
683         type_macros,
684         u128,
685         u16,
686         u32,
687         u64,
688         u8,
689         unboxed_closures,
690         underscore_const_names,
691         underscore_imports,
692         underscore_lifetimes,
693         uniform_paths,
694         universal_impl_trait,
695         unmarked_api,
696         unreachable_code,
697         unrestricted_attribute_tokens,
698         unsafe_destructor_blind_to_params,
699         unsafe_no_drop_flag,
700         unsized_locals,
701         unsized_tuple_coercion,
702         unstable,
703         untagged_unions,
704         unwind,
705         unwind_attributes,
706         unwrap_or,
707         used,
708         use_extern_macros,
709         use_nested_groups,
710         usize,
711         v1,
712         val,
713         vec,
714         Vec,
715         vis,
716         visible_private_types,
717         volatile,
718         warn,
719         warn_directory_ownership,
720         wasm_import_module,
721         wasm_target_feature,
722         while_let,
723         windows,
724         windows_subsystem,
725         Yield,
726     }
727 }
728
729 #[derive(Copy, Clone, Eq)]
730 pub struct Ident {
731     pub name: Symbol,
732     pub span: Span,
733 }
734
735 impl Ident {
736     #[inline]
737     /// Constructs a new identifier from a symbol and a span.
738     pub const fn new(name: Symbol, span: Span) -> Ident {
739         Ident { name, span }
740     }
741
742     /// Constructs a new identifier with an empty syntax context.
743     #[inline]
744     pub const fn with_empty_ctxt(name: Symbol) -> Ident {
745         Ident::new(name, DUMMY_SP)
746     }
747
748     #[inline]
749     pub fn invalid() -> Ident {
750         Ident::with_empty_ctxt(kw::Invalid)
751     }
752
753     /// Maps an interned string to an identifier with an empty syntax context.
754     pub fn from_interned_str(string: InternedString) -> Ident {
755         Ident::with_empty_ctxt(string.as_symbol())
756     }
757
758     /// Maps a string to an identifier with an empty span.
759     pub fn from_str(string: &str) -> Ident {
760         Ident::with_empty_ctxt(Symbol::intern(string))
761     }
762
763     /// Maps a string and a span to an identifier.
764     pub fn from_str_and_span(string: &str, span: Span) -> Ident {
765         Ident::new(Symbol::intern(string), span)
766     }
767
768     /// Replaces `lo` and `hi` with those from `span`, but keep hygiene context.
769     pub fn with_span_pos(self, span: Span) -> Ident {
770         Ident::new(self.name, span.with_ctxt(self.span.ctxt()))
771     }
772
773     pub fn without_first_quote(self) -> Ident {
774         Ident::new(Symbol::intern(self.as_str().trim_start_matches('\'')), self.span)
775     }
776
777     /// "Normalize" ident for use in comparisons using "item hygiene".
778     /// Identifiers with same string value become same if they came from the same "modern" macro
779     /// (e.g., `macro` item, but not `macro_rules` item) and stay different if they came from
780     /// different "modern" macros.
781     /// Technically, this operation strips all non-opaque marks from ident's syntactic context.
782     pub fn modern(self) -> Ident {
783         Ident::new(self.name, self.span.modern())
784     }
785
786     /// "Normalize" ident for use in comparisons using "local variable hygiene".
787     /// Identifiers with same string value become same if they came from the same non-transparent
788     /// macro (e.g., `macro` or `macro_rules!` items) and stay different if they came from different
789     /// non-transparent macros.
790     /// Technically, this operation strips all transparent marks from ident's syntactic context.
791     pub fn modern_and_legacy(self) -> Ident {
792         Ident::new(self.name, self.span.modern_and_legacy())
793     }
794
795     /// Transforms an identifier into one with the same name, but gensymed.
796     pub fn gensym(self) -> Ident {
797         let name = with_interner(|interner| interner.gensymed(self.name));
798         Ident::new(name, self.span)
799     }
800
801     /// Transforms an underscore identifier into one with the same name, but
802     /// gensymed. Leaves non-underscore identifiers unchanged.
803     pub fn gensym_if_underscore(self) -> Ident {
804         if self.name == kw::Underscore { self.gensym() } else { self }
805     }
806
807     // WARNING: this function is deprecated and will be removed in the future.
808     pub fn is_gensymed(self) -> bool {
809         with_interner(|interner| interner.is_gensymed(self.name))
810     }
811
812     pub fn as_str(self) -> LocalInternedString {
813         self.name.as_str()
814     }
815
816     pub fn as_interned_str(self) -> InternedString {
817         self.name.as_interned_str()
818     }
819 }
820
821 impl PartialEq for Ident {
822     fn eq(&self, rhs: &Self) -> bool {
823         self.name == rhs.name && self.span.ctxt() == rhs.span.ctxt()
824     }
825 }
826
827 impl Hash for Ident {
828     fn hash<H: Hasher>(&self, state: &mut H) {
829         self.name.hash(state);
830         self.span.ctxt().hash(state);
831     }
832 }
833
834 impl fmt::Debug for Ident {
835     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
836         write!(f, "{}{:?}", self.name, self.span.ctxt())
837     }
838 }
839
840 impl fmt::Display for Ident {
841     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
842         fmt::Display::fmt(&self.name, f)
843     }
844 }
845
846 impl Encodable for Ident {
847     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
848         if self.span.ctxt().modern() == SyntaxContext::empty() {
849             s.emit_str(&self.as_str())
850         } else { // FIXME(jseyfried): intercrate hygiene
851             let mut string = "#".to_owned();
852             string.push_str(&self.as_str());
853             s.emit_str(&string)
854         }
855     }
856 }
857
858 impl Decodable for Ident {
859     fn decode<D: Decoder>(d: &mut D) -> Result<Ident, D::Error> {
860         let string = d.read_str()?;
861         Ok(if !string.starts_with('#') {
862             Ident::from_str(&string)
863         } else { // FIXME(jseyfried): intercrate hygiene
864             Ident::from_str(&string[1..]).gensym()
865         })
866     }
867 }
868
869 /// A symbol is an interned or gensymed string. A gensym is a symbol that is
870 /// never equal to any other symbol.
871 ///
872 /// Conceptually, a gensym can be thought of as a normal symbol with an
873 /// invisible unique suffix. Gensyms are useful when creating new identifiers
874 /// that must not match any existing identifiers, e.g. during macro expansion
875 /// and syntax desugaring. Because gensyms should always be identifiers, all
876 /// gensym operations are on `Ident` rather than `Symbol`. (Indeed, in the
877 /// future the gensym-ness may be moved from `Symbol` to hygiene data.)
878 ///
879 /// Examples:
880 /// ```
881 /// assert_eq!(Ident::from_str("x"), Ident::from_str("x"))
882 /// assert_ne!(Ident::from_str("x").gensym(), Ident::from_str("x"))
883 /// assert_ne!(Ident::from_str("x").gensym(), Ident::from_str("x").gensym())
884 /// ```
885 /// Internally, a symbol is implemented as an index, and all operations
886 /// (including hashing, equality, and ordering) operate on that index. The use
887 /// of `newtype_index!` means that `Option<Symbol>` only takes up 4 bytes,
888 /// because `newtype_index!` reserves the last 256 values for tagging purposes.
889 ///
890 /// Note that `Symbol` cannot directly be a `newtype_index!` because it
891 /// implements `fmt::Debug`, `Encodable`, and `Decodable` in special ways.
892 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
893 pub struct Symbol(SymbolIndex);
894
895 newtype_index! {
896     pub struct SymbolIndex { .. }
897 }
898
899 impl Symbol {
900     const fn new(n: u32) -> Self {
901         Symbol(SymbolIndex::from_u32_const(n))
902     }
903
904     /// Maps a string to its interned representation.
905     pub fn intern(string: &str) -> Self {
906         with_interner(|interner| interner.intern(string))
907     }
908
909     pub fn as_str(self) -> LocalInternedString {
910         with_interner(|interner| unsafe {
911             LocalInternedString {
912                 string: std::mem::transmute::<&str, &str>(interner.get(self))
913             }
914         })
915     }
916
917     pub fn as_interned_str(self) -> InternedString {
918         with_interner(|interner| InternedString {
919             symbol: interner.interned(self)
920         })
921     }
922
923     pub fn as_u32(self) -> u32 {
924         self.0.as_u32()
925     }
926 }
927
928 impl fmt::Debug for Symbol {
929     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
930         let is_gensymed = with_interner(|interner| interner.is_gensymed(*self));
931         if is_gensymed {
932             write!(f, "{}({:?})", self, self.0)
933         } else {
934             write!(f, "{}", self)
935         }
936     }
937 }
938
939 impl fmt::Display for Symbol {
940     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
941         fmt::Display::fmt(&self.as_str(), f)
942     }
943 }
944
945 impl Encodable for Symbol {
946     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
947         s.emit_str(&self.as_str())
948     }
949 }
950
951 impl Decodable for Symbol {
952     fn decode<D: Decoder>(d: &mut D) -> Result<Symbol, D::Error> {
953         Ok(Symbol::intern(&d.read_str()?))
954     }
955 }
956
957 // The `&'static str`s in this type actually point into the arena.
958 //
959 // Note that normal symbols are indexed upward from 0, and gensyms are indexed
960 // downward from SymbolIndex::MAX_AS_U32.
961 #[derive(Default)]
962 pub struct Interner {
963     arena: DroplessArena,
964     names: FxHashMap<&'static str, Symbol>,
965     strings: Vec<&'static str>,
966     gensyms: Vec<Symbol>,
967 }
968
969 impl Interner {
970     fn prefill(init: &[&'static str]) -> Self {
971         Interner {
972             strings: init.into(),
973             names: init.iter().copied().zip((0..).map(Symbol::new)).collect(),
974             ..Default::default()
975         }
976     }
977
978     pub fn intern(&mut self, string: &str) -> Symbol {
979         if let Some(&name) = self.names.get(string) {
980             return name;
981         }
982
983         let name = Symbol::new(self.strings.len() as u32);
984
985         // `from_utf8_unchecked` is safe since we just allocated a `&str` which is known to be
986         // UTF-8.
987         let string: &str = unsafe {
988             str::from_utf8_unchecked(self.arena.alloc_slice(string.as_bytes()))
989         };
990         // It is safe to extend the arena allocation to `'static` because we only access
991         // these while the arena is still alive.
992         let string: &'static str =  unsafe {
993             &*(string as *const str)
994         };
995         self.strings.push(string);
996         self.names.insert(string, name);
997         name
998     }
999
1000     fn interned(&self, symbol: Symbol) -> Symbol {
1001         if (symbol.0.as_usize()) < self.strings.len() {
1002             symbol
1003         } else {
1004             self.gensyms[(SymbolIndex::MAX_AS_U32 - symbol.0.as_u32()) as usize]
1005         }
1006     }
1007
1008     fn gensymed(&mut self, symbol: Symbol) -> Symbol {
1009         self.gensyms.push(symbol);
1010         Symbol::new(SymbolIndex::MAX_AS_U32 - self.gensyms.len() as u32 + 1)
1011     }
1012
1013     fn is_gensymed(&mut self, symbol: Symbol) -> bool {
1014         symbol.0.as_usize() >= self.strings.len()
1015     }
1016
1017     // Get the symbol as a string. `Symbol::as_str()` should be used in
1018     // preference to this function.
1019     pub fn get(&self, symbol: Symbol) -> &str {
1020         match self.strings.get(symbol.0.as_usize()) {
1021             Some(string) => string,
1022             None => {
1023                 let symbol = self.gensyms[(SymbolIndex::MAX_AS_U32 - symbol.0.as_u32()) as usize];
1024                 self.strings[symbol.0.as_usize()]
1025             }
1026         }
1027     }
1028 }
1029
1030 // This module has a very short name because it's used a lot.
1031 pub mod kw {
1032     use super::Symbol;
1033     keywords!();
1034 }
1035
1036 // This module has a very short name because it's used a lot.
1037 pub mod sym {
1038     use std::convert::TryInto;
1039     use super::Symbol;
1040
1041     symbols!();
1042
1043     // Get the symbol for an integer. The first few non-negative integers each
1044     // have a static symbol and therefore are fast.
1045     pub fn integer<N: TryInto<usize> + Copy + ToString>(n: N) -> Symbol {
1046         if let Result::Ok(idx) = n.try_into() {
1047             if let Option::Some(&sym) = digits_array.get(idx) {
1048                 return sym;
1049             }
1050         }
1051         Symbol::intern(&n.to_string())
1052     }
1053 }
1054
1055 impl Symbol {
1056     fn is_used_keyword_2018(self) -> bool {
1057         self == kw::Dyn
1058     }
1059
1060     fn is_unused_keyword_2018(self) -> bool {
1061         self >= kw::Async && self <= kw::Try
1062     }
1063
1064     /// Used for sanity checking rustdoc keyword sections.
1065     pub fn is_doc_keyword(self) -> bool {
1066         self <= kw::Union
1067     }
1068
1069     /// A keyword or reserved identifier that can be used as a path segment.
1070     pub fn is_path_segment_keyword(self) -> bool {
1071         self == kw::Super ||
1072         self == kw::SelfLower ||
1073         self == kw::SelfUpper ||
1074         self == kw::Crate ||
1075         self == kw::PathRoot ||
1076         self == kw::DollarCrate
1077     }
1078
1079     /// This symbol can be a raw identifier.
1080     pub fn can_be_raw(self) -> bool {
1081         self != kw::Invalid && self != kw::Underscore && !self.is_path_segment_keyword()
1082     }
1083 }
1084
1085 impl Ident {
1086     // Returns `true` for reserved identifiers used internally for elided lifetimes,
1087     // unnamed method parameters, crate root module, error recovery etc.
1088     pub fn is_special(self) -> bool {
1089         self.name <= kw::Underscore
1090     }
1091
1092     /// Returns `true` if the token is a keyword used in the language.
1093     pub fn is_used_keyword(self) -> bool {
1094         // Note: `span.edition()` is relatively expensive, don't call it unless necessary.
1095         self.name >= kw::As && self.name <= kw::While ||
1096         self.name.is_used_keyword_2018() && self.span.rust_2018()
1097     }
1098
1099     /// Returns `true` if the token is a keyword reserved for possible future use.
1100     pub fn is_unused_keyword(self) -> bool {
1101         // Note: `span.edition()` is relatively expensive, don't call it unless necessary.
1102         self.name >= kw::Abstract && self.name <= kw::Yield ||
1103         self.name.is_unused_keyword_2018() && self.span.rust_2018()
1104     }
1105
1106     /// Returns `true` if the token is either a special identifier or a keyword.
1107     pub fn is_reserved(self) -> bool {
1108         self.is_special() || self.is_used_keyword() || self.is_unused_keyword()
1109     }
1110
1111     /// A keyword or reserved identifier that can be used as a path segment.
1112     pub fn is_path_segment_keyword(self) -> bool {
1113         self.name.is_path_segment_keyword()
1114     }
1115
1116     /// We see this identifier in a normal identifier position, like variable name or a type.
1117     /// How was it written originally? Did it use the raw form? Let's try to guess.
1118     pub fn is_raw_guess(self) -> bool {
1119         self.name.can_be_raw() && self.is_reserved()
1120     }
1121 }
1122
1123 // If an interner exists, return it. Otherwise, prepare a fresh one.
1124 #[inline]
1125 fn with_interner<T, F: FnOnce(&mut Interner) -> T>(f: F) -> T {
1126     GLOBALS.with(|globals| f(&mut *globals.symbol_interner.lock()))
1127 }
1128
1129 /// An alternative to `Symbol` and `InternedString`, useful when the chars
1130 /// within the symbol need to be accessed. It is best used for temporary
1131 /// values.
1132 ///
1133 /// Because the interner outlives any thread which uses this type, we can
1134 /// safely treat `string` which points to interner data, as an immortal string,
1135 /// as long as this type never crosses between threads.
1136 //
1137 // FIXME: ensure that the interner outlives any thread which uses
1138 // `LocalInternedString`, by creating a new thread right after constructing the
1139 // interner.
1140 #[derive(Clone, Copy, Hash, PartialOrd, Eq, Ord)]
1141 pub struct LocalInternedString {
1142     string: &'static str,
1143 }
1144
1145 impl LocalInternedString {
1146     /// Maps a string to its interned representation.
1147     pub fn intern(string: &str) -> Self {
1148         let string = with_interner(|interner| {
1149             let symbol = interner.intern(string);
1150             interner.strings[symbol.0.as_usize()]
1151         });
1152         LocalInternedString {
1153             string: unsafe { std::mem::transmute::<&str, &str>(string) }
1154         }
1155     }
1156
1157     pub fn as_interned_str(self) -> InternedString {
1158         InternedString {
1159             symbol: Symbol::intern(self.string)
1160         }
1161     }
1162
1163     #[inline]
1164     pub fn get(&self) -> &str {
1165         // This returns a valid string since we ensure that `self` outlives the interner
1166         // by creating the interner on a thread which outlives threads which can access it.
1167         // This type cannot move to a thread which outlives the interner since it does
1168         // not implement Send.
1169         self.string
1170     }
1171 }
1172
1173 impl<U: ?Sized> std::convert::AsRef<U> for LocalInternedString
1174 where
1175     str: std::convert::AsRef<U>
1176 {
1177     #[inline]
1178     fn as_ref(&self) -> &U {
1179         self.string.as_ref()
1180     }
1181 }
1182
1183 impl<T: std::ops::Deref<Target = str>> std::cmp::PartialEq<T> for LocalInternedString {
1184     fn eq(&self, other: &T) -> bool {
1185         self.string == other.deref()
1186     }
1187 }
1188
1189 impl std::cmp::PartialEq<LocalInternedString> for str {
1190     fn eq(&self, other: &LocalInternedString) -> bool {
1191         self == other.string
1192     }
1193 }
1194
1195 impl<'a> std::cmp::PartialEq<LocalInternedString> for &'a str {
1196     fn eq(&self, other: &LocalInternedString) -> bool {
1197         *self == other.string
1198     }
1199 }
1200
1201 impl std::cmp::PartialEq<LocalInternedString> for String {
1202     fn eq(&self, other: &LocalInternedString) -> bool {
1203         self == other.string
1204     }
1205 }
1206
1207 impl<'a> std::cmp::PartialEq<LocalInternedString> for &'a String {
1208     fn eq(&self, other: &LocalInternedString) -> bool {
1209         *self == other.string
1210     }
1211 }
1212
1213 impl !Send for LocalInternedString {}
1214 impl !Sync for LocalInternedString {}
1215
1216 impl std::ops::Deref for LocalInternedString {
1217     type Target = str;
1218     #[inline]
1219     fn deref(&self) -> &str { self.string }
1220 }
1221
1222 impl fmt::Debug for LocalInternedString {
1223     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1224         fmt::Debug::fmt(self.string, f)
1225     }
1226 }
1227
1228 impl fmt::Display for LocalInternedString {
1229     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1230         fmt::Display::fmt(self.string, f)
1231     }
1232 }
1233
1234 impl Decodable for LocalInternedString {
1235     fn decode<D: Decoder>(d: &mut D) -> Result<LocalInternedString, D::Error> {
1236         Ok(LocalInternedString::intern(&d.read_str()?))
1237     }
1238 }
1239
1240 impl Encodable for LocalInternedString {
1241     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
1242         s.emit_str(self.string)
1243     }
1244 }
1245
1246 /// An alternative to `Symbol` that is focused on string contents. It has two
1247 /// main differences to `Symbol`.
1248 ///
1249 /// First, its implementations of `Hash`, `PartialOrd` and `Ord` work with the
1250 /// string chars rather than the symbol integer. This is useful when hash
1251 /// stability is required across compile sessions, or a guaranteed sort
1252 /// ordering is required.
1253 ///
1254 /// Second, gensym-ness is irrelevant. E.g.:
1255 /// ```
1256 /// assert_ne!(Symbol::gensym("x"), Symbol::gensym("x"))
1257 /// assert_eq!(Symbol::gensym("x").as_interned_str(), Symbol::gensym("x").as_interned_str())
1258 /// ```
1259 #[derive(Clone, Copy, PartialEq, Eq)]
1260 pub struct InternedString {
1261     symbol: Symbol,
1262 }
1263
1264 impl InternedString {
1265     /// Maps a string to its interned representation.
1266     pub fn intern(string: &str) -> Self {
1267         InternedString {
1268             symbol: Symbol::intern(string)
1269         }
1270     }
1271
1272     pub fn with<F: FnOnce(&str) -> R, R>(self, f: F) -> R {
1273         let str = with_interner(|interner| {
1274             interner.get(self.symbol) as *const str
1275         });
1276         // This is safe because the interner keeps string alive until it is dropped.
1277         // We can access it because we know the interner is still alive since we use a
1278         // scoped thread local to access it, and it was alive at the beginning of this scope
1279         unsafe { f(&*str) }
1280     }
1281
1282     fn with2<F: FnOnce(&str, &str) -> R, R>(self, other: &InternedString, f: F) -> R {
1283         let (self_str, other_str) = with_interner(|interner| {
1284             (interner.get(self.symbol) as *const str,
1285              interner.get(other.symbol) as *const str)
1286         });
1287         // This is safe for the same reason that `with` is safe.
1288         unsafe { f(&*self_str, &*other_str) }
1289     }
1290
1291     pub fn as_symbol(self) -> Symbol {
1292         self.symbol
1293     }
1294
1295     pub fn as_str(self) -> LocalInternedString {
1296         self.symbol.as_str()
1297     }
1298 }
1299
1300 impl Hash for InternedString {
1301     fn hash<H: Hasher>(&self, state: &mut H) {
1302         self.with(|str| str.hash(state))
1303     }
1304 }
1305
1306 impl PartialOrd<InternedString> for InternedString {
1307     fn partial_cmp(&self, other: &InternedString) -> Option<Ordering> {
1308         if self.symbol == other.symbol {
1309             return Some(Ordering::Equal);
1310         }
1311         self.with2(other, |self_str, other_str| self_str.partial_cmp(other_str))
1312     }
1313 }
1314
1315 impl Ord for InternedString {
1316     fn cmp(&self, other: &InternedString) -> Ordering {
1317         if self.symbol == other.symbol {
1318             return Ordering::Equal;
1319         }
1320         self.with2(other, |self_str, other_str| self_str.cmp(other_str))
1321     }
1322 }
1323
1324 impl fmt::Debug for InternedString {
1325     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1326         self.with(|str| fmt::Debug::fmt(&str, f))
1327     }
1328 }
1329
1330 impl fmt::Display for InternedString {
1331     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1332         self.with(|str| fmt::Display::fmt(&str, f))
1333     }
1334 }
1335
1336 impl Decodable for InternedString {
1337     fn decode<D: Decoder>(d: &mut D) -> Result<InternedString, D::Error> {
1338         Ok(InternedString::intern(&d.read_str()?))
1339     }
1340 }
1341
1342 impl Encodable for InternedString {
1343     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
1344         self.with(|string| s.emit_str(string))
1345     }
1346 }
1347
1348 #[cfg(test)]
1349 mod tests {
1350     use super::*;
1351     use crate::Globals;
1352     use crate::edition;
1353
1354     #[test]
1355     fn interner_tests() {
1356         let mut i: Interner = Interner::default();
1357         // first one is zero:
1358         assert_eq!(i.intern("dog"), Symbol::new(0));
1359         // re-use gets the same entry:
1360         assert_eq!(i.intern("dog"), Symbol::new(0));
1361         // different string gets a different #:
1362         assert_eq!(i.intern("cat"), Symbol::new(1));
1363         assert_eq!(i.intern("cat"), Symbol::new(1));
1364         // dog is still at zero
1365         assert_eq!(i.intern("dog"), Symbol::new(0));
1366         let z = i.intern("zebra");
1367         assert_eq!(i.gensymed(z), Symbol::new(SymbolIndex::MAX_AS_U32));
1368         // gensym of same string gets new number:
1369         assert_eq!(i.gensymed(z), Symbol::new(SymbolIndex::MAX_AS_U32 - 1));
1370         // gensym of *existing* string gets new number:
1371         let d = i.intern("dog");
1372         assert_eq!(i.gensymed(d), Symbol::new(SymbolIndex::MAX_AS_U32 - 2));
1373     }
1374
1375     #[test]
1376     fn without_first_quote_test() {
1377         GLOBALS.set(&Globals::new(edition::DEFAULT_EDITION), || {
1378             let i = Ident::from_str("'break");
1379             assert_eq!(i.without_first_quote().name, kw::Break);
1380         });
1381     }
1382 }