Merge commit 'c4416f20dcaec5d93077f72470e83e150fb923b1' into sync-rustfmt

10 files changed, 245 insertions, 195 deletions

diff --git a/src/cargo-fmt/main.rs b/src/cargo-fmt/main.rs
index 55fd75f6de9..9031d29b45f 100644
--- a/src/cargo-fmt/main.rs
+++ b/src/cargo-fmt/main.rs
@@ -14,7 +14,7 @@ use std::path::{Path, PathBuf};
 use std::process::Command;
 use std::str;
 
-use clap::{CommandFactory, Parser};
+use clap::{AppSettings, CommandFactory, Parser};
 
 #[path = "test/mod.rs"]
 #[cfg(test)]
@@ -22,6 +22,7 @@ mod cargo_fmt_tests;
 
 #[derive(Parser)]
 #[clap(
+    global_setting(AppSettings::NoAutoVersion),
     bin_name = "cargo fmt",
     about = "This utility formats all bin and lib files of \
              the current crate using rustfmt."
diff --git a/src/comment.rs b/src/comment.rs
index eb195b1f762..4d565afc1e0 100644
--- a/src/comment.rs
+++ b/src/comment.rs
@@ -730,6 +730,10 @@ impl<'a> CommentRewrite<'a> {
                     {
                         let mut config = self.fmt.config.clone();
                         config.set().wrap_comments(false);
+                        let comment_max_width = config
+                            .doc_comment_code_block_width()
+                            .min(config.max_width());
+                        config.set().max_width(comment_max_width);
                         if let Some(s) =
                             crate::format_code_block(&self.code_block_buffer, &config, false)
                         {
diff --git a/src/config/mod.rs b/src/config/mod.rs
index a5169528187..f49c18d3a46 100644
--- a/src/config/mod.rs
+++ b/src/config/mod.rs
@@ -57,6 +57,8 @@ create_config! {
     // Comments. macros, and strings
     wrap_comments: bool, false, false, "Break comments to fit on the line";
     format_code_in_doc_comments: bool, false, false, "Format the code snippet in doc comments.";
+    doc_comment_code_block_width: usize, 100, false, "Maximum width for code snippets in doc \
+        comments. No effect unless format_code_in_doc_comments = true";
     comment_width: usize, 80, false,
         "Maximum length of comments. No effect unless wrap_comments = true";
     normalize_comments: bool, false, false, "Convert /* */ comments to // comments where possible";
@@ -532,6 +534,7 @@ chain_width = 60
 single_line_if_else_max_width = 50
 wrap_comments = false
 format_code_in_doc_comments = false
+doc_comment_code_block_width = 100
 comment_width = 80
 normalize_comments = false
 normalize_doc_attributes = false
diff --git a/src/expr.rs b/src/expr.rs
index 4ccf1ca70c9..e4cc93026f1 100644
--- a/src/expr.rs
+++ b/src/expr.rs
@@ -1,6 +1,5 @@
 use std::borrow::Cow;
 use std::cmp::min;
-use std::collections::HashMap;
 
 use itertools::Itertools;
 use rustc_ast::token::{Delimiter, LitKind};
@@ -23,7 +22,7 @@ use crate::macros::{rewrite_macro, MacroPosition};
 use crate::matches::rewrite_match;
 use crate::overflow::{self, IntoOverflowableItem, OverflowableItem};
 use crate::pairs::{rewrite_all_pairs, rewrite_pair, PairParts};
-use crate::rewrite::{QueryId, Rewrite, RewriteContext};
+use crate::rewrite::{Rewrite, RewriteContext};
 use crate::shape::{Indent, Shape};
 use crate::source_map::{LineRangeUtils, SpanUtils};
 use crate::spanned::Spanned;
@@ -55,54 +54,6 @@ pub(crate) fn format_expr(
     context: &RewriteContext<'_>,
     shape: Shape,
 ) -> Option<String> {
-    // when max_width is tight, we should check all possible formattings, in order to find
-    // if we can fit expression in the limit. Doing it recursively takes exponential time
-    // relative to input size, and people hit it with rustfmt takes minutes in #4476 #4867 #5128
-    // By memoization of format_expr function, we format each pair of expression and shape
-    // only once, so worst case execution time becomes O(n*max_width^3).
-    if context.inside_macro() || context.is_macro_def {
-        // span ids are not unique in macros, so we don't memoize result of them.
-        return format_expr_inner(expr, expr_type, context, shape);
-    }
-    let clean;
-    let query_id = QueryId {
-        shape,
-        span: expr.span,
-    };
-    if let Some(map) = context.memoize.take() {
-        if let Some(r) = map.get(&query_id) {
-            let r = r.clone();
-            context.memoize.set(Some(map)); // restore map in the memoize cell for other users
-            return r;
-        }
-        context.memoize.set(Some(map));
-        clean = false;
-    } else {
-        context.memoize.set(Some(HashMap::default()));
-        clean = true; // We got None, so we are the top level called function. When
-        // this function finishes, no one is interested in what is in the map, because
-        // all of them are sub expressions of this top level expression, and this is
-        // done. So we should clean up memoize map to save some memory.
-    }
-
-    let r = format_expr_inner(expr, expr_type, context, shape);
-    if clean {
-        context.memoize.set(None);
-    } else {
-        if let Some(mut map) = context.memoize.take() {
-            map.insert(query_id, r.clone()); // insert the result in the memoize map
-            context.memoize.set(Some(map)); // so it won't be computed again
-        }
-    }
-    r
-}
-
-fn format_expr_inner(
-    expr: &ast::Expr,
-    expr_type: ExprType,
-    context: &RewriteContext<'_>,
-    shape: Shape,
-) -> Option<String> {
     skip_out_of_file_lines_range!(context, expr.span);
 
     if contains_skip(&*expr.attrs) {
diff --git a/src/formatting.rs b/src/formatting.rs
index e644ea50eff..1dfd8a514f0 100644
--- a/src/formatting.rs
+++ b/src/formatting.rs
@@ -2,7 +2,6 @@
 
 use std::collections::HashMap;
 use std::io::{self, Write};
-use std::rc::Rc;
 use std::time::{Duration, Instant};
 
 use rustc_ast::ast;
@@ -203,7 +202,6 @@ impl<'a, T: FormatHandler + 'a> FormatContext<'a, T> {
             self.config,
             &snippet_provider,
             self.report.clone(),
-            Rc::default(),
         );
         visitor.skip_context.update_with_attrs(&self.krate.attrs);
         visitor.is_macro_def = is_macro_def;
diff --git a/src/imports.rs b/src/imports.rs
index 559ed3917db..8d41c881589 100644
--- a/src/imports.rs
+++ b/src/imports.rs
@@ -15,7 +15,7 @@ use rustc_span::{
 use crate::comment::combine_strs_with_missing_comments;
 use crate::config::lists::*;
 use crate::config::ImportGranularity;
-use crate::config::{Edition, IndentStyle};
+use crate::config::{Edition, IndentStyle, Version};
 use crate::lists::{
     definitive_tactic, itemize_list, write_list, ListFormatting, ListItem, Separator,
 };
@@ -92,7 +92,7 @@ impl<'a> FmtVisitor<'a> {
 
 // FIXME we do a lot of allocation to make our own representation.
 #[derive(Clone, Eq, Hash, PartialEq)]
-pub(crate) enum UseSegment {
+pub(crate) enum UseSegmentKind {
     Ident(String, Option<String>),
     Slf(Option<String>),
     Super(Option<String>),
@@ -101,6 +101,12 @@ pub(crate) enum UseSegment {
     List(Vec<UseTree>),
 }
 
+#[derive(Clone, Eq, PartialEq)]
+pub(crate) struct UseSegment {
+    pub(crate) kind: UseSegmentKind,
+    pub(crate) version: Version,
+}
+
 #[derive(Clone)]
 pub(crate) struct UseTree {
     pub(crate) path: Vec<UseSegment>,
@@ -134,34 +140,38 @@ impl Spanned for UseTree {
 impl UseSegment {
     // Clone a version of self with any top-level alias removed.
     fn remove_alias(&self) -> UseSegment {
-        match *self {
-            UseSegment::Ident(ref s, _) => UseSegment::Ident(s.clone(), None),
-            UseSegment::Slf(_) => UseSegment::Slf(None),
-            UseSegment::Super(_) => UseSegment::Super(None),
-            UseSegment::Crate(_) => UseSegment::Crate(None),
-            _ => self.clone(),
+        let kind = match self.kind {
+            UseSegmentKind::Ident(ref s, _) => UseSegmentKind::Ident(s.clone(), None),
+            UseSegmentKind::Slf(_) => UseSegmentKind::Slf(None),
+            UseSegmentKind::Super(_) => UseSegmentKind::Super(None),
+            UseSegmentKind::Crate(_) => UseSegmentKind::Crate(None),
+            _ => return self.clone(),
+        };
+        UseSegment {
+            kind,
+            version: self.version,
         }
     }
 
     // Check if self == other with their aliases removed.
     fn equal_except_alias(&self, other: &Self) -> bool {
-        match (self, other) {
-            (UseSegment::Ident(ref s1, _), UseSegment::Ident(ref s2, _)) => s1 == s2,
-            (UseSegment::Slf(_), UseSegment::Slf(_))
-            | (UseSegment::Super(_), UseSegment::Super(_))
-            | (UseSegment::Crate(_), UseSegment::Crate(_))
-            | (UseSegment::Glob, UseSegment::Glob) => true,
-            (UseSegment::List(ref list1), UseSegment::List(ref list2)) => list1 == list2,
+        match (&self.kind, &other.kind) {
+            (UseSegmentKind::Ident(ref s1, _), UseSegmentKind::Ident(ref s2, _)) => s1 == s2,
+            (UseSegmentKind::Slf(_), UseSegmentKind::Slf(_))
+            | (UseSegmentKind::Super(_), UseSegmentKind::Super(_))
+            | (UseSegmentKind::Crate(_), UseSegmentKind::Crate(_))
+            | (UseSegmentKind::Glob, UseSegmentKind::Glob) => true,
+            (UseSegmentKind::List(ref list1), UseSegmentKind::List(ref list2)) => list1 == list2,
             _ => false,
         }
     }
 
     fn get_alias(&self) -> Option<&str> {
-        match self {
-            UseSegment::Ident(_, a)
-            | UseSegment::Slf(a)
-            | UseSegment::Super(a)
-            | UseSegment::Crate(a) => a.as_deref(),
+        match &self.kind {
+            UseSegmentKind::Ident(_, a)
+            | UseSegmentKind::Slf(a)
+            | UseSegmentKind::Super(a)
+            | UseSegmentKind::Crate(a) => a.as_deref(),
             _ => None,
         }
     }
@@ -175,19 +185,24 @@ impl UseSegment {
         if name.is_empty() || name == "{{root}}" {
             return None;
         }
-        Some(match name {
-            "self" => UseSegment::Slf(None),
-            "super" => UseSegment::Super(None),
-            "crate" => UseSegment::Crate(None),
+        let kind = match name {
+            "self" => UseSegmentKind::Slf(None),
+            "super" => UseSegmentKind::Super(None),
+            "crate" => UseSegmentKind::Crate(None),
             _ => {
                 let mod_sep = if modsep { "::" } else { "" };
-                UseSegment::Ident(format!("{}{}", mod_sep, name), None)
+                UseSegmentKind::Ident(format!("{}{}", mod_sep, name), None)
             }
+        };
+
+        Some(UseSegment {
+            kind,
+            version: context.config.version(),
         })
     }
 
     fn contains_comment(&self) -> bool {
-        if let UseSegment::List(list) = self {
+        if let UseSegmentKind::List(list) = &self.kind {
             list.iter().any(|subtree| subtree.contains_comment())
         } else {
             false
@@ -254,20 +269,38 @@ impl fmt::Debug for UseTree {
 
 impl fmt::Debug for UseSegment {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        fmt::Display::fmt(self, f)
+        fmt::Display::fmt(&self.kind, f)
     }
 }
 
 impl fmt::Display for UseSegment {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Display::fmt(&self.kind, f)
+    }
+}
+
+impl Hash for UseSegment {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.kind.hash(state);
+    }
+}
+
+impl fmt::Debug for UseSegmentKind {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Display::fmt(self, f)
+    }
+}
+
+impl fmt::Display for UseSegmentKind {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match *self {
-            UseSegment::Glob => write!(f, "*"),
-            UseSegment::Ident(ref s, Some(ref alias)) => write!(f, "{} as {}", s, alias),
-            UseSegment::Ident(ref s, None) => write!(f, "{}", s),
-            UseSegment::Slf(..) => write!(f, "self"),
-            UseSegment::Super(..) => write!(f, "super"),
-            UseSegment::Crate(..) => write!(f, "crate"),
-            UseSegment::List(ref list) => {
+            UseSegmentKind::Glob => write!(f, "*"),
+            UseSegmentKind::Ident(ref s, Some(ref alias)) => write!(f, "{} as {}", s, alias),
+            UseSegmentKind::Ident(ref s, None) => write!(f, "{}", s),
+            UseSegmentKind::Slf(..) => write!(f, "self"),
+            UseSegmentKind::Super(..) => write!(f, "super"),
+            UseSegmentKind::Crate(..) => write!(f, "crate"),
+            UseSegmentKind::List(ref list) => {
                 write!(f, "{{")?;
                 for (i, item) in list.iter().enumerate() {
                     if i != 0 {
@@ -411,13 +444,19 @@ impl UseTree {
             }
         }
 
+        let version = context.config.version();
+
         match a.kind {
             UseTreeKind::Glob => {
                 // in case of a global path and the glob starts at the root, e.g., "::*"
                 if a.prefix.segments.len() == 1 && leading_modsep {
-                    result.path.push(UseSegment::Ident("".to_owned(), None));
+                    let kind = UseSegmentKind::Ident("".to_owned(), None);
+                    result.path.push(UseSegment { kind, version });
                 }
-                result.path.push(UseSegment::Glob);
+                result.path.push(UseSegment {
+                    kind: UseSegmentKind::Glob,
+                    version,
+                });
             }
             UseTreeKind::Nested(ref list) => {
                 // Extract comments between nested use items.
@@ -438,16 +477,18 @@ impl UseTree {
                 // in case of a global path and the nested list starts at the root,
                 // e.g., "::{foo, bar}"
                 if a.prefix.segments.len() == 1 && leading_modsep {
-                    result.path.push(UseSegment::Ident("".to_owned(), None));
+                    let kind = UseSegmentKind::Ident("".to_owned(), None);
+                    result.path.push(UseSegment { kind, version });
                 }
-                result.path.push(UseSegment::List(
+                let kind = UseSegmentKind::List(
                     list.iter()
                         .zip(items)
                         .map(|(t, list_item)| {
                             Self::from_ast(context, &t.0, Some(list_item), None, None, None)
                         })
                         .collect(),
-                ));
+                );
+                result.path.push(UseSegment { kind, version });
             }
             UseTreeKind::Simple(ref rename, ..) => {
                 // If the path has leading double colons and is composed of only 2 segments, then we
@@ -469,13 +510,15 @@ impl UseTree {
                         Some(rewrite_ident(context, ident).to_owned())
                     }
                 });
-                let segment = match name.as_ref() {
-                    "self" => UseSegment::Slf(alias),
-                    "super" => UseSegment::Super(alias),
-                    "crate" => UseSegment::Crate(alias),
-                    _ => UseSegment::Ident(name, alias),
+                let kind = match name.as_ref() {
+                    "self" => UseSegmentKind::Slf(alias),
+                    "super" => UseSegmentKind::Super(alias),
+                    "crate" => UseSegmentKind::Crate(alias),
+                    _ => UseSegmentKind::Ident(name, alias),
                 };
 
+                let segment = UseSegment { kind, version };
+
                 // `name` is already in result.
                 result.path.pop();
                 result.path.push(segment);
@@ -492,13 +535,13 @@ impl UseTree {
         let mut aliased_self = false;
 
         // Remove foo::{} or self without attributes.
-        match last {
+        match last.kind {
             _ if self.attrs.is_some() => (),
-            UseSegment::List(ref list) if list.is_empty() => {
+            UseSegmentKind::List(ref list) if list.is_empty() => {
                 self.path = vec![];
                 return self;
             }
-            UseSegment::Slf(None) if self.path.is_empty() && self.visibility.is_some() => {
+            UseSegmentKind::Slf(None) if self.path.is_empty() && self.visibility.is_some() => {
                 self.path = vec![];
                 return self;
             }
@@ -506,15 +549,19 @@ impl UseTree {
         }
 
         // Normalise foo::self -> foo.
-        if let UseSegment::Slf(None) = last {
+        if let UseSegmentKind::Slf(None) = last.kind {
             if !self.path.is_empty() {
                 return self;
             }
         }
 
         // Normalise foo::self as bar -> foo as bar.
-        if let UseSegment::Slf(_) = last {
-            if let Some(UseSegment::Ident(_, None)) = self.path.last() {
+        if let UseSegmentKind::Slf(_) = last.kind {
+            if let Some(UseSegment {
+                kind: UseSegmentKind::Ident(_, None),
+                ..
+            }) = self.path.last()
+            {
                 aliased_self = true;
             }
         }
@@ -522,9 +569,12 @@ impl UseTree {
         let mut done = false;
         if aliased_self {
             match self.path.last_mut() {
-                Some(UseSegment::Ident(_, ref mut old_rename)) => {
+                Some(UseSegment {
+                    kind: UseSegmentKind::Ident(_, ref mut old_rename),
+                    ..
+                }) => {
                     assert!(old_rename.is_none());
-                    if let UseSegment::Slf(Some(rename)) = last.clone() {
+                    if let UseSegmentKind::Slf(Some(rename)) = last.clone().kind {
                         *old_rename = Some(rename);
                         done = true;
                     }
@@ -538,15 +588,15 @@ impl UseTree {
         }
 
         // Normalise foo::{bar} -> foo::bar
-        if let UseSegment::List(ref list) = last {
+        if let UseSegmentKind::List(ref list) = last.kind {
             if list.len() == 1 && list[0].to_string() != "self" {
                 normalize_sole_list = true;
             }
         }
 
         if normalize_sole_list {
-            match last {
-                UseSegment::List(list) => {
+            match last.kind {
+                UseSegmentKind::List(list) => {
                     for seg in &list[0].path {
                         self.path.push(seg.clone());
                     }
@@ -557,10 +607,13 @@ impl UseTree {
         }
 
         // Recursively normalize elements of a list use (including sorting the list).
-        if let UseSegment::List(list) = last {
+        if let UseSegmentKind::List(list) = last.kind {
             let mut list = list.into_iter().map(UseTree::normalize).collect::<Vec<_>>();
             list.sort();
-            last = UseSegment::List(list);
+            last = UseSegment {
+                kind: UseSegmentKind::List(list),
+                version: last.version,
+            };
         }
 
         self.path.push(last);
@@ -620,10 +673,10 @@ impl UseTree {
         if self.path.is_empty() || self.contains_comment() {
             return vec![self];
         }
-        match self.path.clone().last().unwrap() {
-            UseSegment::List(list) => {
+        match &self.path.clone().last().unwrap().kind {
+            UseSegmentKind::List(list) => {
                 if list.len() == 1 && list[0].path.len() == 1 {
-                    if let UseSegment::Slf(..) = list[0].path[0] {
+                    if let UseSegmentKind::Slf(..) = list[0].path[0].kind {
                         return vec![self];
                     };
                 }
@@ -671,12 +724,15 @@ impl UseTree {
 
     /// If this tree ends in `::self`, rewrite it to `::{self}`.
     fn nest_trailing_self(mut self) -> UseTree {
-        if let Some(UseSegment::Slf(..)) = self.path.last() {
+        if let Some(UseSegment {
+            kind: UseSegmentKind::Slf(..),
+            ..
+        }) = self.path.last()
+        {
             let self_segment = self.path.pop().unwrap();
-            self.path.push(UseSegment::List(vec![UseTree::from_path(
-                vec![self_segment],
-                DUMMY_SP,
-            )]));
+            let version = self_segment.version;
+            let kind = UseSegmentKind::List(vec![UseTree::from_path(vec![self_segment], DUMMY_SP)]);
+            self.path.push(UseSegment { kind, version });
         }
         self
     }
@@ -692,7 +748,8 @@ fn merge_rest(
         return None;
     }
     if a.len() != len && b.len() != len {
-        if let UseSegment::List(ref list) = a[len] {
+        let version = a[len].version;
+        if let UseSegmentKind::List(ref list) = a[len].kind {
             let mut list = list.clone();
             merge_use_trees_inner(
                 &mut list,
@@ -700,7 +757,8 @@ fn merge_rest(
                 merge_by,
             );
             let mut new_path = b[..len].to_vec();
-            new_path.push(UseSegment::List(list));
+            let kind = UseSegmentKind::List(list);
+            new_path.push(UseSegment { kind, version });
             return Some(new_path);
         }
     } else if len == 1 {
@@ -709,15 +767,28 @@ fn merge_rest(
         } else {
             (&b[0], &a[1..])
         };
+        let kind = UseSegmentKind::Slf(common.get_alias().map(ToString::to_string));
+        let version = a[0].version;
         let mut list = vec![UseTree::from_path(
-            vec![UseSegment::Slf(common.get_alias().map(ToString::to_string))],
+            vec![UseSegment { kind, version }],
             DUMMY_SP,
         )];
         match rest {
-            [UseSegment::List(rest_list)] => list.extend(rest_list.clone()),
+            [
+                UseSegment {
+                    kind: UseSegmentKind::List(rest_list),
+                    ..
+                },
+            ] => list.extend(rest_list.clone()),
             _ => list.push(UseTree::from_path(rest.to_vec(), DUMMY_SP)),
         }
-        return Some(vec![b[0].clone(), UseSegment::List(list)]);
+        return Some(vec![
+            b[0].clone(),
+            UseSegment {
+                kind: UseSegmentKind::List(list),
+                version,
+            },
+        ]);
     } else {
         len -= 1;
     }
@@ -727,7 +798,9 @@ fn merge_rest(
     ];
     list.sort();
     let mut new_path = b[..len].to_vec();
-    new_path.push(UseSegment::List(list));
+    let kind = UseSegmentKind::List(list);
+    let version = a[0].version;
+    new_path.push(UseSegment { kind, version });
     Some(new_path)
 }
 
@@ -805,19 +878,33 @@ impl PartialOrd for UseTree {
 }
 impl Ord for UseSegment {
     fn cmp(&self, other: &UseSegment) -> Ordering {
-        use self::UseSegment::*;
+        use self::UseSegmentKind::*;
 
         fn is_upper_snake_case(s: &str) -> bool {
             s.chars()
                 .all(|c| c.is_uppercase() || c == '_' || c.is_numeric())
         }
 
-        match (self, other) {
-            (&Slf(ref a), &Slf(ref b))
-            | (&Super(ref a), &Super(ref b))
-            | (&Crate(ref a), &Crate(ref b)) => a.cmp(b),
-            (&Glob, &Glob) => Ordering::Equal,
-            (&Ident(ref ia, ref aa), &Ident(ref ib, ref ab)) => {
+        match (&self.kind, &other.kind) {
+            (Slf(ref a), Slf(ref b))
+            | (Super(ref a), Super(ref b))
+            | (Crate(ref a), Crate(ref b)) => match (a, b) {
+                (Some(sa), Some(sb)) => {
+                    if self.version == Version::Two {
+                        sa.trim_start_matches("r#").cmp(sb.trim_start_matches("r#"))
+                    } else {
+                        a.cmp(b)
+                    }
+                }
+                (_, _) => a.cmp(b),
+            },
+            (Glob, Glob) => Ordering::Equal,
+            (Ident(ref pia, ref aa), Ident(ref pib, ref ab)) => {
+                let (ia, ib) = if self.version == Version::Two {
+                    (pia.trim_start_matches("r#"), pib.trim_start_matches("r#"))
+                } else {
+                    (pia.as_str(), pib.as_str())
+                };
                 // snake_case < CamelCase < UPPER_SNAKE_CASE
                 if ia.starts_with(char::is_uppercase) && ib.starts_with(char::is_lowercase) {
                     return Ordering::Greater;
@@ -835,15 +922,21 @@ impl Ord for UseSegment {
                 if ident_ord != Ordering::Equal {
                     return ident_ord;
                 }
-                if aa.is_none() && ab.is_some() {
-                    return Ordering::Less;
-                }
-                if aa.is_some() && ab.is_none() {
-                    return Ordering::Greater;
+                match (aa, ab) {
+                    (None, Some(_)) => Ordering::Less,
+                    (Some(_), None) => Ordering::Greater,
+                    (Some(aas), Some(abs)) => {
+                        if self.version == Version::Two {
+                            aas.trim_start_matches("r#")
+                                .cmp(abs.trim_start_matches("r#"))
+                        } else {
+                            aas.cmp(abs)
+                        }
+                    }
+                    (None, None) => Ordering::Equal,
                 }
-                aa.cmp(ab)
             }
-            (&List(ref a), &List(ref b)) => {
+            (List(ref a), List(ref b)) => {
                 for (a, b) in a.iter().zip(b.iter()) {
                     let ord = a.cmp(b);
                     if ord != Ordering::Equal {
@@ -853,16 +946,16 @@ impl Ord for UseSegment {
 
                 a.len().cmp(&b.len())
             }
-            (&Slf(_), _) => Ordering::Less,
-            (_, &Slf(_)) => Ordering::Greater,
-            (&Super(_), _) => Ordering::Less,
-            (_, &Super(_)) => Ordering::Greater,
-            (&Crate(_), _) => Ordering::Less,
-            (_, &Crate(_)) => Ordering::Greater,
-            (&Ident(..), _) => Ordering::Less,
-            (_, &Ident(..)) => Ordering::Greater,
-            (&Glob, _) => Ordering::Less,
-            (_, &Glob) => Ordering::Greater,
+            (Slf(_), _) => Ordering::Less,
+            (_, Slf(_)) => Ordering::Greater,
+            (Super(_), _) => Ordering::Less,
+            (_, Super(_)) => Ordering::Greater,
+            (Crate(_), _) => Ordering::Less,
+            (_, Crate(_)) => Ordering::Greater,
+            (Ident(..), _) => Ordering::Less,
+            (_, Ident(..)) => Ordering::Greater,
+            (Glob, _) => Ordering::Less,
+            (_, Glob) => Ordering::Greater,
         }
     }
 }
@@ -906,7 +999,7 @@ fn rewrite_nested_use_tree(
     }
     let has_nested_list = use_tree_list.iter().any(|use_segment| {
         use_segment.path.last().map_or(false, |last_segment| {
-            matches!(last_segment, UseSegment::List(..))
+            matches!(last_segment.kind, UseSegmentKind::List(..))
         })
     });
 
@@ -957,17 +1050,19 @@ fn rewrite_nested_use_tree(
 
 impl Rewrite for UseSegment {
     fn rewrite(&self, context: &RewriteContext<'_>, shape: Shape) -> Option<String> {
-        Some(match self {
-            UseSegment::Ident(ref ident, Some(ref rename)) => format!("{} as {}", ident, rename),
-            UseSegment::Ident(ref ident, None) => ident.clone(),
-            UseSegment::Slf(Some(ref rename)) => format!("self as {}", rename),
-            UseSegment::Slf(None) => "self".to_owned(),
-            UseSegment::Super(Some(ref rename)) => format!("super as {}", rename),
-            UseSegment::Super(None) => "super".to_owned(),
-            UseSegment::Crate(Some(ref rename)) => format!("crate as {}", rename),
-            UseSegment::Crate(None) => "crate".to_owned(),
-            UseSegment::Glob => "*".to_owned(),
-            UseSegment::List(ref use_tree_list) => rewrite_nested_use_tree(
+        Some(match self.kind {
+            UseSegmentKind::Ident(ref ident, Some(ref rename)) => {
+                format!("{} as {}", ident, rename)
+            }
+            UseSegmentKind::Ident(ref ident, None) => ident.clone(),
+            UseSegmentKind::Slf(Some(ref rename)) => format!("self as {}", rename),
+            UseSegmentKind::Slf(None) => "self".to_owned(),
+            UseSegmentKind::Super(Some(ref rename)) => format!("super as {}", rename),
+            UseSegmentKind::Super(None) => "super".to_owned(),
+            UseSegmentKind::Crate(Some(ref rename)) => format!("crate as {}", rename),
+            UseSegmentKind::Crate(None) => "crate".to_owned(),
+            UseSegmentKind::Glob => "*".to_owned(),
+            UseSegmentKind::List(ref use_tree_list) => rewrite_nested_use_tree(
                 context,
                 use_tree_list,
                 // 1 = "{" and "}"
@@ -1016,6 +1111,7 @@ mod test {
 
         struct Parser<'a> {
             input: Peekable<Chars<'a>>,
+            version: Version,
         }
 
         impl<'a> Parser<'a> {
@@ -1028,34 +1124,40 @@ mod test {
             }
 
             fn push_segment(
+                &self,
                 result: &mut Vec<UseSegment>,
                 buf: &mut String,
                 alias_buf: &mut Option<String>,
             ) {
+                let version = self.version;
                 if !buf.is_empty() {
                     let mut alias = None;
                     swap(alias_buf, &mut alias);
 
                     match buf.as_ref() {
                         "self" => {
-                            result.push(UseSegment::Slf(alias));
+                            let kind = UseSegmentKind::Slf(alias);
+                            result.push(UseSegment { kind, version });
                             *buf = String::new();
                             *alias_buf = None;
                         }
                         "super" => {
-                            result.push(UseSegment::Super(alias));
+                            let kind = UseSegmentKind::Super(alias);
+                            result.push(UseSegment { kind, version });
                             *buf = String::new();
                             *alias_buf = None;
                         }
                         "crate" => {
-                            result.push(UseSegment::Crate(alias));
+                            let kind = UseSegmentKind::Crate(alias);
+                            result.push(UseSegment { kind, version });
                             *buf = String::new();
                             *alias_buf = None;
                         }
                         _ => {
                             let mut name = String::new();
                             swap(buf, &mut name);
-                            result.push(UseSegment::Ident(name, alias));
+                            let kind = UseSegmentKind::Ident(name, alias);
+                            result.push(UseSegment { kind, version });
                         }
                     }
                 }
@@ -1070,21 +1172,29 @@ mod test {
                         '{' => {
                             assert!(buf.is_empty());
                             self.bump();
-                            result.push(UseSegment::List(self.parse_list()));
+                            let kind = UseSegmentKind::List(self.parse_list());
+                            result.push(UseSegment {
+                                kind,
+                                version: self.version,
+                            });
                             self.eat('}');
                         }
                         '*' => {
                             assert!(buf.is_empty());
                             self.bump();
-                            result.push(UseSegment::Glob);
+                            let kind = UseSegmentKind::Glob;
+                            result.push(UseSegment {
+                                kind,
+                                version: self.version,
+                            });
                         }
                         ':' => {
                             self.bump();
                             self.eat(':');
-                            Self::push_segment(&mut result, &mut buf, &mut alias_buf);
+                            self.push_segment(&mut result, &mut buf, &mut alias_buf);
                         }
                         '}' | ',' => {
-                            Self::push_segment(&mut result, &mut buf, &mut alias_buf);
+                            self.push_segment(&mut result, &mut buf, &mut alias_buf);
                             return UseTree {
                                 path: result,
                                 span: DUMMY_SP,
@@ -1110,7 +1220,7 @@ mod test {
                         }
                     }
                 }
-                Self::push_segment(&mut result, &mut buf, &mut alias_buf);
+                self.push_segment(&mut result, &mut buf, &mut alias_buf);
                 UseTree {
                     path: result,
                     span: DUMMY_SP,
@@ -1136,6 +1246,7 @@ mod test {
 
         let mut parser = Parser {
             input: s.chars().peekable(),
+            version: Version::One,
         };
         parser.parse_in_list()
     }
diff --git a/src/reorder.rs b/src/reorder.rs
index 8ae297de25b..9e4a668aa49 100644
--- a/src/reorder.rs
+++ b/src/reorder.rs
@@ -12,7 +12,7 @@ use rustc_ast::ast;
 use rustc_span::{symbol::sym, Span};
 
 use crate::config::{Config, GroupImportsTactic};
-use crate::imports::{normalize_use_trees_with_granularity, UseSegment, UseTree};
+use crate::imports::{normalize_use_trees_with_granularity, UseSegmentKind, UseTree};
 use crate::items::{is_mod_decl, rewrite_extern_crate, rewrite_mod};
 use crate::lists::{itemize_list, write_list, ListFormatting, ListItem};
 use crate::rewrite::RewriteContext;
@@ -182,16 +182,16 @@ fn group_imports(uts: Vec<UseTree>) -> Vec<Vec<UseTree>> {
             external_imports.push(ut);
             continue;
         }
-        match &ut.path[0] {
-            UseSegment::Ident(id, _) => match id.as_ref() {
+        match &ut.path[0].kind {
+            UseSegmentKind::Ident(id, _) => match id.as_ref() {
                 "std" | "alloc" | "core" => std_imports.push(ut),
                 _ => external_imports.push(ut),
             },
-            UseSegment::Slf(_) | UseSegment::Super(_) | UseSegment::Crate(_) => {
+            UseSegmentKind::Slf(_) | UseSegmentKind::Super(_) | UseSegmentKind::Crate(_) => {
                 local_imports.push(ut)
             }
             // These are probably illegal here
-            UseSegment::Glob | UseSegment::List(_) => external_imports.push(ut),
+            UseSegmentKind::Glob | UseSegmentKind::List(_) => external_imports.push(ut),
         }
     }
 
diff --git a/src/rewrite.rs b/src/rewrite.rs
index f97df70cc6a..4a3bd129d16 100644
--- a/src/rewrite.rs
+++ b/src/rewrite.rs
@@ -12,7 +12,6 @@ use crate::shape::Shape;
 use crate::skip::SkipContext;
 use crate::visitor::SnippetProvider;
 use crate::FormatReport;
-use rustc_data_structures::stable_map::FxHashMap;
 
 pub(crate) trait Rewrite {
     /// Rewrite self into shape.
@@ -25,22 +24,10 @@ impl<T: Rewrite> Rewrite for ptr::P<T> {
     }
 }
 
-#[derive(Clone, PartialEq, Eq, Hash)]
-pub(crate) struct QueryId {
-    pub(crate) shape: Shape,
-    pub(crate) span: Span,
-}
-
-// We use Option<HashMap> instead of HashMap, because in case of `None`
-// the function clean the memoize map, but it doesn't clean when
-// there is `Some(empty)`, so they are different.
-pub(crate) type Memoize = Rc<Cell<Option<FxHashMap<QueryId, Option<String>>>>>;
-
 #[derive(Clone)]
 pub(crate) struct RewriteContext<'a> {
     pub(crate) parse_sess: &'a ParseSess,
     pub(crate) config: &'a Config,
-    pub(crate) memoize: Memoize,
     pub(crate) inside_macro: Rc<Cell<bool>>,
     // Force block indent style even if we are using visual indent style.
     pub(crate) use_block: Cell<bool>,
diff --git a/src/shape.rs b/src/shape.rs
index b3f785a9470..4376fd12b52 100644
--- a/src/shape.rs
+++ b/src/shape.rs
@@ -4,7 +4,7 @@ use std::ops::{Add, Sub};
 
 use crate::Config;
 
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Copy, Clone, Debug)]
 pub(crate) struct Indent {
     // Width of the block indent, in characters. Must be a multiple of
     // Config::tab_spaces.
@@ -139,7 +139,7 @@ impl Sub<usize> for Indent {
 // 8096 is close enough to infinite for rustfmt.
 const INFINITE_SHAPE_WIDTH: usize = 8096;
 
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Copy, Clone, Debug)]
 pub(crate) struct Shape {
     pub(crate) width: usize,
     // The current indentation of code.
diff --git a/src/visitor.rs b/src/visitor.rs
index 3ff56d52f92..9a0e0752c12 100644
--- a/src/visitor.rs
+++ b/src/visitor.rs
@@ -17,7 +17,7 @@ use crate::items::{
 use crate::macros::{macro_style, rewrite_macro, rewrite_macro_def, MacroPosition};
 use crate::modules::Module;
 use crate::parse::session::ParseSess;
-use crate::rewrite::{Memoize, Rewrite, RewriteContext};
+use crate::rewrite::{Rewrite, RewriteContext};
 use crate::shape::{Indent, Shape};
 use crate::skip::{is_skip_attr, SkipContext};
 use crate::source_map::{LineRangeUtils, SpanUtils};
@@ -71,7 +71,6 @@ impl SnippetProvider {
 
 pub(crate) struct FmtVisitor<'a> {
     parent_context: Option<&'a RewriteContext<'a>>,
-    pub(crate) memoize: Memoize,
     pub(crate) parse_sess: &'a ParseSess,
     pub(crate) buffer: String,
     pub(crate) last_pos: BytePos,
@@ -759,7 +758,6 @@ impl<'b, 'a: 'b> FmtVisitor<'a> {
             ctx.config,
             ctx.snippet_provider,
             ctx.report.clone(),
-            ctx.memoize.clone(),
         );
         visitor.skip_context.update(ctx.skip_context.clone());
         visitor.set_parent_context(ctx);
@@ -771,12 +769,10 @@ impl<'b, 'a: 'b> FmtVisitor<'a> {
         config: &'a Config,
         snippet_provider: &'a SnippetProvider,
         report: FormatReport,
-        memoize: Memoize,
     ) -> FmtVisitor<'a> {
         FmtVisitor {
             parent_context: None,
             parse_sess: parse_session,
-            memoize,
             buffer: String::with_capacity(snippet_provider.big_snippet.len() * 2),
             last_pos: BytePos(0),
             block_indent: Indent::empty(),
@@ -999,7 +995,6 @@ impl<'b, 'a: 'b> FmtVisitor<'a> {
         RewriteContext {
             parse_sess: self.parse_sess,
             config: self.config,
-            memoize: self.memoize.clone(),
             inside_macro: Rc::new(Cell::new(false)),
             use_block: Cell::new(false),
             is_if_else_block: Cell::new(false),