src/tools/rustfmt/src/reorder.rs

   1 //! Reorder items.
   2 //!
   3 //! `mod`, `extern crate` and `use` declarations are reordered in alphabetical
   4 //! order. Trait items are reordered in pre-determined order (associated types
   5 //! and constants comes before methods).
   6
   7 // FIXME(#2455): Reorder trait items.
   8
   9 use std::cmp::{Ord, Ordering};
  10
  11 use rustc_ast::ast;
  12 use rustc_span::{symbol::sym, Span};
  13
  14 use crate::config::{Config, GroupImportsTactic, ImportGranularity};
  15 use crate::imports::{flatten_use_trees, merge_use_trees, SharedPrefix, UseSegment, UseTree};
  16 use crate::items::{is_mod_decl, rewrite_extern_crate, rewrite_mod};
  17 use crate::lists::{itemize_list, write_list, ListFormatting, ListItem};
  18 use crate::rewrite::RewriteContext;
  19 use crate::shape::Shape;
  20 use crate::source_map::LineRangeUtils;
  21 use crate::spanned::Spanned;
  22 use crate::utils::{contains_skip, mk_sp};
  23 use crate::visitor::FmtVisitor;
  24
  25 /// Choose the ordering between the given two items.
  26 fn compare_items(a: &ast::Item, b: &ast::Item) -> Ordering {
  27     match (&a.kind, &b.kind) {
  28         (&ast::ItemKind::Mod(..), &ast::ItemKind::Mod(..)) => {
  29             a.ident.as_str().cmp(b.ident.as_str())
  30         }
  31         (&ast::ItemKind::ExternCrate(ref a_name), &ast::ItemKind::ExternCrate(ref b_name)) => {
  32             // `extern crate foo as bar;`
  33             //               ^^^ Comparing this.
  34             let a_orig_name = a_name.unwrap_or(a.ident.name);
  35             let b_orig_name = b_name.unwrap_or(b.ident.name);
  36             let result = a_orig_name.as_str().cmp(b_orig_name.as_str());
  37             if result != Ordering::Equal {
  38                 return result;
  39             }
  40
  41             // `extern crate foo as bar;`
  42             //                      ^^^ Comparing this.
  43             match (a_name, b_name) {
  44                 (Some(..), None) => Ordering::Greater,
  45                 (None, Some(..)) => Ordering::Less,
  46                 (None, None) => Ordering::Equal,
  47                 (Some(..), Some(..)) => a.ident.as_str().cmp(b.ident.as_str()),
  48             }
  49         }
  50         _ => unreachable!(),
  51     }
  52 }
  53
  54 fn wrap_reorderable_items(
  55     context: &RewriteContext<'_>,
  56     list_items: &[ListItem],
  57     shape: Shape,
  58 ) -> Option<String> {
  59     let fmt = ListFormatting::new(shape, context.config)
  60         .separator("")
  61         .align_comments(false);
  62     write_list(list_items, &fmt)
  63 }
  64
  65 fn rewrite_reorderable_item(
  66     context: &RewriteContext<'_>,
  67     item: &ast::Item,
  68     shape: Shape,
  69 ) -> Option<String> {
  70     match item.kind {
  71         ast::ItemKind::ExternCrate(..) => rewrite_extern_crate(context, item, shape),
  72         ast::ItemKind::Mod(..) => rewrite_mod(context, item, shape),
  73         _ => None,
  74     }
  75 }
  76
  77 /// Rewrite a list of items with reordering and/or regrouping. Every item
  78 /// in `items` must have the same `ast::ItemKind`. Whether reordering, regrouping,
  79 /// or both are done is determined from the `context`.
  80 fn rewrite_reorderable_or_regroupable_items(
  81     context: &RewriteContext<'_>,
  82     reorderable_items: &[&ast::Item],
  83     shape: Shape,
  84     span: Span,
  85 ) -> Option<String> {
  86     match reorderable_items[0].kind {
  87         // FIXME: Remove duplicated code.
  88         ast::ItemKind::Use(..) => {
  89             let mut normalized_items: Vec<_> = reorderable_items
  90                 .iter()
  91                 .filter_map(|item| UseTree::from_ast_with_normalization(context, item))
  92                 .collect();
  93             let cloned = normalized_items.clone();
  94             // Add comments before merging.
  95             let list_items = itemize_list(
  96                 context.snippet_provider,
  97                 cloned.iter(),
  98                 "",
  99                 ";",
 100                 |item| item.span().lo(),
 101                 |item| item.span().hi(),
 102                 |_item| Some("".to_owned()),
 103                 span.lo(),
 104                 span.hi(),
 105                 false,
 106             );
 107             for (item, list_item) in normalized_items.iter_mut().zip(list_items) {
 108                 item.list_item = Some(list_item.clone());
 109             }
 110             normalized_items = match context.config.imports_granularity() {
 111                 ImportGranularity::Crate => merge_use_trees(normalized_items, SharedPrefix::Crate),
 112                 ImportGranularity::Module => {
 113                     merge_use_trees(normalized_items, SharedPrefix::Module)
 114                 }
 115                 ImportGranularity::Item => flatten_use_trees(normalized_items),
 116                 ImportGranularity::One => merge_use_trees(normalized_items, SharedPrefix::One),
 117                 ImportGranularity::Preserve => normalized_items,
 118             };
 119
 120             let mut regrouped_items = match context.config.group_imports() {
 121                 GroupImportsTactic::Preserve | GroupImportsTactic::One => {
 122                     vec![normalized_items]
 123                 }
 124                 GroupImportsTactic::StdExternalCrate => group_imports(normalized_items),
 125             };
 126
 127             if context.config.reorder_imports() {
 128                 regrouped_items.iter_mut().for_each(|items| items.sort())
 129             }
 130
 131             // 4 = "use ", 1 = ";"
 132             let nested_shape = shape.offset_left(4)?.sub_width(1)?;
 133             let item_vec: Vec<_> = regrouped_items
 134                 .into_iter()
 135                 .filter(|use_group| !use_group.is_empty())
 136                 .map(|use_group| {
 137                     let item_vec: Vec<_> = use_group
 138                         .into_iter()
 139                         .map(|use_tree| ListItem {
 140                             item: use_tree.rewrite_top_level(context, nested_shape),
 141                             ..use_tree.list_item.unwrap_or_else(ListItem::empty)
 142                         })
 143                         .collect();
 144                     wrap_reorderable_items(context, &item_vec, nested_shape)
 145                 })
 146                 .collect::<Option<Vec<_>>>()?;
 147
 148             let join_string = format!("\n\n{}", shape.indent.to_string(context.config));
 149             Some(item_vec.join(&join_string))
 150         }
 151         _ => {
 152             let list_items = itemize_list(
 153                 context.snippet_provider,
 154                 reorderable_items.iter(),
 155                 "",
 156                 ";",
 157                 |item| item.span().lo(),
 158                 |item| item.span().hi(),
 159                 |item| rewrite_reorderable_item(context, item, shape),
 160                 span.lo(),
 161                 span.hi(),
 162                 false,
 163             );
 164
 165             let mut item_pair_vec: Vec<_> = list_items.zip(reorderable_items.iter()).collect();
 166             item_pair_vec.sort_by(|a, b| compare_items(a.1, b.1));
 167             let item_vec: Vec<_> = item_pair_vec.into_iter().map(|pair| pair.0).collect();
 168
 169             wrap_reorderable_items(context, &item_vec, shape)
 170         }
 171     }
 172 }
 173
 174 fn contains_macro_use_attr(item: &ast::Item) -> bool {
 175     crate::attr::contains_name(&item.attrs, sym::macro_use)
 176 }
 177
 178 /// Divides imports into three groups, corresponding to standard, external
 179 /// and local imports. Sorts each subgroup.
 180 fn group_imports(uts: Vec<UseTree>) -> Vec<Vec<UseTree>> {
 181     let mut std_imports = Vec::new();
 182     let mut external_imports = Vec::new();
 183     let mut local_imports = Vec::new();
 184
 185     for ut in uts.into_iter() {
 186         if ut.path.is_empty() {
 187             external_imports.push(ut);
 188             continue;
 189         }
 190         match &ut.path[0] {
 191             UseSegment::Ident(id, _) => match id.as_ref() {
 192                 "std" | "alloc" | "core" => std_imports.push(ut),
 193                 _ => external_imports.push(ut),
 194             },
 195             UseSegment::Slf(_) | UseSegment::Super(_) | UseSegment::Crate(_) => {
 196                 local_imports.push(ut)
 197             }
 198             // These are probably illegal here
 199             UseSegment::Glob | UseSegment::List(_) => external_imports.push(ut),
 200         }
 201     }
 202
 203     vec![std_imports, external_imports, local_imports]
 204 }
 205
 206 /// A simplified version of `ast::ItemKind`.
 207 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
 208 enum ReorderableItemKind {
 209     ExternCrate,
 210     Mod,
 211     Use,
 212     /// An item that cannot be reordered. Either has an unreorderable item kind
 213     /// or an `macro_use` attribute.
 214     Other,
 215 }
 216
 217 impl ReorderableItemKind {
 218     fn from(item: &ast::Item) -> Self {
 219         match item.kind {
 220             _ if contains_macro_use_attr(item) | contains_skip(&item.attrs) => {
 221                 ReorderableItemKind::Other
 222             }
 223             ast::ItemKind::ExternCrate(..) => ReorderableItemKind::ExternCrate,
 224             ast::ItemKind::Mod(..) if is_mod_decl(item) => ReorderableItemKind::Mod,
 225             ast::ItemKind::Use(..) => ReorderableItemKind::Use,
 226             _ => ReorderableItemKind::Other,
 227         }
 228     }
 229
 230     fn is_same_item_kind(self, item: &ast::Item) -> bool {
 231         ReorderableItemKind::from(item) == self
 232     }
 233
 234     fn is_reorderable(self, config: &Config) -> bool {
 235         match self {
 236             ReorderableItemKind::ExternCrate => config.reorder_imports(),
 237             ReorderableItemKind::Mod => config.reorder_modules(),
 238             ReorderableItemKind::Use => config.reorder_imports(),
 239             ReorderableItemKind::Other => false,
 240         }
 241     }
 242
 243     fn is_regroupable(self, config: &Config) -> bool {
 244         match self {
 245             ReorderableItemKind::ExternCrate
 246             | ReorderableItemKind::Mod
 247             | ReorderableItemKind::Other => false,
 248             ReorderableItemKind::Use => config.group_imports() != GroupImportsTactic::Preserve,
 249         }
 250     }
 251
 252     fn in_group(self, config: &Config) -> bool {
 253         match self {
 254             ReorderableItemKind::ExternCrate | ReorderableItemKind::Mod => true,
 255             ReorderableItemKind::Use => config.group_imports() == GroupImportsTactic::Preserve,
 256             ReorderableItemKind::Other => false,
 257         }
 258     }
 259 }
 260
 261 impl<'b, 'a: 'b> FmtVisitor<'a> {
 262     /// Format items with the same item kind and reorder them, regroup them, or
 263     /// both. If `in_group` is `true`, then the items separated by an empty line
 264     /// will not be reordered together.
 265     fn walk_reorderable_or_regroupable_items(
 266         &mut self,
 267         items: &[&ast::Item],
 268         item_kind: ReorderableItemKind,
 269         in_group: bool,
 270     ) -> usize {
 271         let mut last = self.parse_sess.lookup_line_range(items[0].span());
 272         let item_length = items
 273             .iter()
 274             .take_while(|ppi| {
 275                 item_kind.is_same_item_kind(&***ppi)
 276                     && (!in_group || {
 277                         let current = self.parse_sess.lookup_line_range(ppi.span());
 278                         let in_same_group = current.lo < last.hi + 2;
 279                         last = current;
 280                         in_same_group
 281                     })
 282             })
 283             .count();
 284         let items = &items[..item_length];
 285
 286         let at_least_one_in_file_lines = items
 287             .iter()
 288             .any(|item| !out_of_file_lines_range!(self, item.span));
 289
 290         if at_least_one_in_file_lines && !items.is_empty() {
 291             let lo = items.first().unwrap().span().lo();
 292             let hi = items.last().unwrap().span().hi();
 293             let span = mk_sp(lo, hi);
 294             let rw = rewrite_reorderable_or_regroupable_items(
 295                 &self.get_context(),
 296                 items,
 297                 self.shape(),
 298                 span,
 299             );
 300             self.push_rewrite(span, rw);
 301         } else {
 302             for item in items {
 303                 self.push_rewrite(item.span, None);
 304             }
 305         }
 306
 307         item_length
 308     }
 309
 310     /// Visits and format the given items. Items are reordered If they are
 311     /// consecutive and reorderable.
 312     pub(crate) fn visit_items_with_reordering(&mut self, mut items: &[&ast::Item]) {
 313         while !items.is_empty() {
 314             // If the next item is a `use`, `extern crate` or `mod`, then extract it and any
 315             // subsequent items that have the same item kind to be reordered within
 316             // `walk_reorderable_items`. Otherwise, just format the next item for output.
 317             let item_kind = ReorderableItemKind::from(items[0]);
 318             if item_kind.is_reorderable(self.config) || item_kind.is_regroupable(self.config) {
 319                 let visited_items_num = self.walk_reorderable_or_regroupable_items(
 320                     items,
 321                     item_kind,
 322                     item_kind.in_group(self.config),
 323                 );
 324                 let (_, rest) = items.split_at(visited_items_num);
 325                 items = rest;
 326             } else {
 327                 // Reaching here means items were not reordered. There must be at least
 328                 // one item left in `items`, so calling `unwrap()` here is safe.
 329                 let (item, rest) = items.split_first().unwrap();
 330                 self.visit_item(item);
 331                 items = rest;
 332             }
 333         }
 334     }
 335 }