1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use std::cmp::Ordering;
14 use syntax::ast::{self, UseTreeKind};
15 use syntax::codemap::{BytePos, Span};
17 use codemap::SpanUtils;
18 use config::IndentStyle;
19 use lists::{definitive_tactic, itemize_list, write_list, ListFormatting, ListItem, Separator};
20 use rewrite::{Rewrite, RewriteContext};
24 use visitor::FmtVisitor;
28 /// Returns a name imported by a `use` declaration. e.g. returns `Ordering`
29 /// for `std::cmp::Ordering` and `self` for `std::cmp::self`.
30 pub fn path_to_imported_ident(path: &ast::Path) -> ast::Ident {
31 path.segments.last().unwrap().identifier
34 impl<'a> FmtVisitor<'a> {
35 pub fn format_import(&mut self, item: &ast::Item, tree: &ast::UseTree) {
37 let shape = self.shape();
38 let rw = UseTree::from_ast(
42 Some(item.vis.clone()),
44 Some(item.attrs.clone()),
45 ).rewrite_top_level(&self.get_context(), shape);
47 Some(ref s) if s.is_empty() => {
48 // Format up to last newline
49 let prev_span = mk_sp(self.last_pos, source!(self, span).lo());
50 let trimmed_snippet = self.snippet(prev_span).trim_right();
51 let span_end = self.last_pos + BytePos(trimmed_snippet.len() as u32);
52 self.format_missing(span_end);
53 // We have an excessive newline from the removed import.
54 if self.buffer.ends_with('\n') {
56 self.line_number -= 1;
58 self.last_pos = source!(self, span).hi();
61 self.format_missing_with_indent(source!(self, span).lo());
63 self.last_pos = source!(self, span).hi();
66 self.format_missing_with_indent(source!(self, span).lo());
67 self.format_missing(source!(self, span).hi());
73 // Ordering of imports
75 // We order imports by translating to our own representation and then sorting.
76 // The Rust AST data structures are really bad for this. Rustfmt applies a bunch
77 // of normalisations to imports and since we want to sort based on the result
78 // of these (and to maintain idempotence) we must apply the same normalisations
79 // to the data structures for sorting.
81 // We sort `self` and `super` before other imports, then identifier imports,
82 // then glob imports, then lists of imports. We do not take aliases into account
83 // when ordering unless the imports are identical except for the alias (rare in
86 // FIXME(#2531) - we should unify the comparison code here with the formatting
87 // code elsewhere since we are essentially string-ifying twice. Furthermore, by
88 // parsing to our own format on comparison, we repeat a lot of work when
91 // FIXME we do a lot of allocation to make our own representation.
92 #[derive(Debug, Clone, Eq, PartialEq)]
94 Ident(String, Option<String>),
96 Super(Option<String>),
101 #[derive(Debug, Clone)]
103 pub path: Vec<UseSegment>,
105 // Comment information within nested use tree.
106 list_item: Option<ListItem>,
107 // Additional fields for top level use items.
108 // Should we have another struct for top-level use items rather than reusing this?
109 visibility: Option<ast::Visibility>,
110 attrs: Option<Vec<ast::Attribute>>,
113 impl PartialEq for UseTree {
114 fn eq(&self, other: &UseTree) -> bool {
115 self.path == other.path
118 impl Eq for UseTree {}
121 // Clone a version of self with any top-level alias removed.
122 fn remove_alias(&self) -> UseSegment {
124 UseSegment::Ident(ref s, _) => UseSegment::Ident(s.clone(), None),
125 UseSegment::Slf(_) => UseSegment::Slf(None),
126 UseSegment::Super(_) => UseSegment::Super(None),
131 fn from_path_segment(path_seg: &ast::PathSegment) -> Option<UseSegment> {
132 let name = path_seg.identifier.name.as_str();
133 if name == "{{root}}" {
136 Some(if name == "self" {
137 UseSegment::Slf(None)
138 } else if name == "super" {
139 UseSegment::Super(None)
141 UseSegment::Ident((*name).to_owned(), None)
147 // Rewrite use tree with `use ` and a trailing `;`.
148 pub fn rewrite_top_level(&self, context: &RewriteContext, shape: Shape) -> Option<String> {
149 let mut result = String::with_capacity(256);
150 if let Some(ref attrs) = self.attrs {
151 result.push_str(&attrs.rewrite(context, shape)?);
152 if !result.is_empty() {
153 result.push_str(&shape.indent.to_string_with_newline(context.config));
157 let vis = self.visibility
159 .map_or(Cow::from(""), |vis| ::utils::format_visibility(&vis));
160 result.push_str(&self.rewrite(context, shape.offset_left(vis.len())?)
165 format!("{}use {};", vis, s)
171 pub fn from_ast_with_normalization(
172 context: &RewriteContext,
174 ) -> Option<UseTree> {
176 ast::ItemKind::Use(ref use_tree) => Some(
181 Some(item.vis.clone()),
182 Some(item.span().lo()),
183 if item.attrs.is_empty() {
186 Some(item.attrs.clone())
188 ).normalize(context.config.reorder_imported_names()),
195 context: &RewriteContext,
197 list_item: Option<ListItem>,
198 visibility: Option<ast::Visibility>,
199 opt_lo: Option<BytePos>,
200 attrs: Option<Vec<ast::Attribute>>,
202 let span = if let Some(lo) = opt_lo {
203 mk_sp(lo, a.span.hi())
207 let mut result = UseTree {
214 for p in &a.prefix.segments {
215 if let Some(use_segment) = UseSegment::from_path_segment(p) {
216 result.path.push(use_segment);
220 UseTreeKind::Glob => {
221 result.path.push(UseSegment::Glob);
223 UseTreeKind::Nested(ref list) => {
224 // Extract comments between nested use items.
225 // This needs to be done before sorting use items.
226 let items: Vec<_> = itemize_list(
227 context.snippet_provider,
228 list.iter().map(|(tree, _)| tree),
231 |tree| tree.span.lo(),
232 |tree| tree.span.hi(),
233 |_| Some("".to_owned()), // We only need comments for now.
234 context.snippet_provider.span_after(a.span, "{"),
238 result.path.push(UseSegment::List(
240 .zip(items.into_iter())
241 .map(|(t, list_item)| {
242 Self::from_ast(context, &t.0, Some(list_item), None, None, None)
247 UseTreeKind::Simple(ref rename) => {
248 let mut name = (*path_to_imported_ident(&a.prefix).name.as_str()).to_owned();
249 let alias = rename.and_then(|ident| {
250 if ident == path_to_imported_ident(&a.prefix) {
253 Some(ident.to_string())
257 let segment = if &name == "self" {
258 UseSegment::Slf(alias)
259 } else if &name == "super" {
260 UseSegment::Super(alias)
262 UseSegment::Ident(name, alias)
265 // `name` is already in result.
267 result.path.push(segment);
273 // Do the adjustments that rustfmt does elsewhere to use paths.
274 pub fn normalize(mut self, do_sort: bool) -> UseTree {
275 let mut last = self.path.pop().expect("Empty use tree?");
276 // Hack around borrow checker.
277 let mut normalize_sole_list = false;
278 let mut aliased_self = false;
280 // Remove foo::{} or self without attributes.
282 _ if self.attrs.is_some() => (),
283 UseSegment::List(ref list) if list.is_empty() => {
287 UseSegment::Slf(None) if self.path.is_empty() && self.visibility.is_some() => {
294 // Normalise foo::self -> foo.
295 if let UseSegment::Slf(None) = last {
296 if self.path.len() > 0 {
301 // Normalise foo::self as bar -> foo as bar.
302 if let UseSegment::Slf(_) = last {
303 match self.path.last() {
305 Some(UseSegment::Ident(_, None)) => {
313 match self.path.last() {
314 Some(UseSegment::Ident(_, ref mut old_rename)) => {
315 assert!(old_rename.is_none());
316 if let UseSegment::Slf(Some(rename)) = last {
317 *old_rename = Some(rename);
325 // Normalise foo::{bar} -> foo::bar
326 if let UseSegment::List(ref list) = last {
328 normalize_sole_list = true;
332 if normalize_sole_list {
334 UseSegment::List(list) => {
335 for seg in &list[0].path {
336 self.path.push(seg.clone());
338 return self.normalize(do_sort);
344 // Recursively normalize elements of a list use (including sorting the list).
345 if let UseSegment::List(list) = last {
346 let mut list = list.into_iter()
347 .map(|ut| ut.normalize(do_sort))
348 .collect::<Vec<_>>();
352 last = UseSegment::List(list);
355 self.path.push(last);
360 impl PartialOrd for UseSegment {
361 fn partial_cmp(&self, other: &UseSegment) -> Option<Ordering> {
362 Some(self.cmp(other))
365 impl PartialOrd for UseTree {
366 fn partial_cmp(&self, other: &UseTree) -> Option<Ordering> {
367 Some(self.cmp(other))
370 impl Ord for UseSegment {
371 fn cmp(&self, other: &UseSegment) -> Ordering {
372 use self::UseSegment::*;
374 fn is_upper_snake_case(s: &str) -> bool {
375 s.chars().all(|c| c.is_uppercase() || c == '_')
378 match (self, other) {
379 (&Slf(ref a), &Slf(ref b)) | (&Super(ref a), &Super(ref b)) => a.cmp(b),
380 (&Glob, &Glob) => Ordering::Equal,
381 (&Ident(ref ia, ref aa), &Ident(ref ib, ref ab)) => {
382 // snake_case < CamelCase < UPPER_SNAKE_CASE
383 if ia.starts_with(char::is_uppercase) && ib.starts_with(char::is_lowercase) {
384 return Ordering::Greater;
386 if ia.starts_with(char::is_lowercase) && ib.starts_with(char::is_uppercase) {
387 return Ordering::Less;
389 if is_upper_snake_case(ia) && !is_upper_snake_case(ib) {
390 return Ordering::Greater;
392 if !is_upper_snake_case(ia) && is_upper_snake_case(ib) {
393 return Ordering::Less;
395 let ident_ord = ia.cmp(ib);
396 if ident_ord != Ordering::Equal {
399 if aa.is_none() && ab.is_some() {
400 return Ordering::Less;
402 if aa.is_some() && ab.is_none() {
403 return Ordering::Greater;
407 (&List(ref a), &List(ref b)) => {
408 for (a, b) in a.iter().zip(b.iter()) {
410 if ord != Ordering::Equal {
415 a.len().cmp(&b.len())
417 (&Slf(_), _) => Ordering::Less,
418 (_, &Slf(_)) => Ordering::Greater,
419 (&Super(_), _) => Ordering::Less,
420 (_, &Super(_)) => Ordering::Greater,
421 (&Ident(..), _) => Ordering::Less,
422 (_, &Ident(..)) => Ordering::Greater,
423 (&Glob, _) => Ordering::Less,
424 (_, &Glob) => Ordering::Greater,
428 impl Ord for UseTree {
429 fn cmp(&self, other: &UseTree) -> Ordering {
430 for (a, b) in self.path.iter().zip(other.path.iter()) {
432 // The comparison without aliases is a hack to avoid situations like
433 // comparing `a::b` to `a as c` - where the latter should be ordered
434 // first since it is shorter.
435 if ord != Ordering::Equal && a.remove_alias().cmp(&b.remove_alias()) != Ordering::Equal
441 self.path.len().cmp(&other.path.len())
445 fn rewrite_nested_use_tree(
446 context: &RewriteContext,
447 use_tree_list: &[UseTree],
449 ) -> Option<String> {
450 let mut list_items = Vec::with_capacity(use_tree_list.len());
451 let nested_shape = match context.config.imports_indent() {
452 IndentStyle::Block => shape
453 .block_indent(context.config.tab_spaces())
454 .with_max_width(context.config)
456 IndentStyle::Visual => shape.visual_indent(0),
458 for use_tree in use_tree_list {
459 let mut list_item = use_tree.list_item.clone()?;
460 list_item.item = use_tree.rewrite(context, nested_shape);
461 list_items.push(list_item);
463 let tactic = if use_tree_list.iter().any(|use_segment| {
467 .map_or(false, |last_segment| match last_segment {
468 UseSegment::List(..) => true,
472 DefinitiveListTactic::Vertical
476 context.config.imports_layout(),
478 shape.width.checked_sub(2).unwrap_or(0),
481 let ends_with_newline = context.config.imports_indent() == IndentStyle::Block
482 && tactic != DefinitiveListTactic::Horizontal;
483 let fmt = ListFormatting {
486 trailing_separator: if ends_with_newline {
487 context.config.trailing_comma()
489 SeparatorTactic::Never
491 separator_place: SeparatorPlace::Back,
494 preserve_newline: true,
495 config: context.config,
498 let list_str = write_list(&list_items, &fmt)?;
500 let result = if (list_str.contains('\n') || list_str.len() > remaining_width)
501 && context.config.imports_indent() == IndentStyle::Block
505 nested_shape.indent.to_string(context.config),
507 shape.indent.to_string(context.config)
510 format!("{{{}}}", list_str)
516 impl Rewrite for UseSegment {
517 fn rewrite(&self, context: &RewriteContext, shape: Shape) -> Option<String> {
519 UseSegment::Ident(ref ident, Some(ref rename)) => format!("{} as {}", ident, rename),
520 UseSegment::Ident(ref ident, None) => ident.clone(),
521 UseSegment::Slf(Some(ref rename)) => format!("self as {}", rename),
522 UseSegment::Slf(None) => "self".to_owned(),
523 UseSegment::Super(Some(ref rename)) => format!("super as {}", rename),
524 UseSegment::Super(None) => "super".to_owned(),
525 UseSegment::Glob => "*".to_owned(),
526 UseSegment::List(ref use_tree_list) => rewrite_nested_use_tree(
530 shape.offset_left(1)?.sub_width(1)?,
536 impl Rewrite for UseTree {
537 // This does NOT format attributes and visibility or add a trailing `;`.
538 fn rewrite(&self, context: &RewriteContext, mut shape: Shape) -> Option<String> {
539 let mut result = String::with_capacity(256);
540 let mut iter = self.path.iter().peekable();
541 while let Some(ref segment) = iter.next() {
542 let segment_str = segment.rewrite(context, shape)?;
543 result.push_str(&segment_str);
544 if iter.peek().is_some() {
545 result.push_str("::");
547 shape = shape.offset_left(2 + segment_str.len())?;
557 use syntax::codemap::DUMMY_SP;
559 // Parse the path part of an import. This parser is not robust and is only
560 // suitable for use in a test harness.
561 fn parse_use_tree(s: &str) -> UseTree {
562 use std::iter::Peekable;
567 input: Peekable<Chars<'a>>,
570 impl<'a> Parser<'a> {
572 self.input.next().unwrap();
574 fn eat(&mut self, c: char) {
575 assert!(self.input.next().unwrap() == c);
578 result: &mut Vec<UseSegment>,
580 alias_buf: &mut Option<String>,
583 let mut alias = None;
584 swap(alias_buf, &mut alias);
586 result.push(UseSegment::Slf(alias));
587 *buf = String::new();
589 } else if buf == "super" {
590 result.push(UseSegment::Super(alias));
591 *buf = String::new();
594 let mut name = String::new();
595 swap(buf, &mut name);
596 result.push(UseSegment::Ident(name, alias));
600 fn parse_in_list(&mut self) -> UseTree {
601 let mut result = vec![];
602 let mut buf = String::new();
603 let mut alias_buf = None;
604 while let Some(&c) = self.input.peek() {
607 assert!(buf.is_empty());
609 result.push(UseSegment::List(self.parse_list()));
613 assert!(buf.is_empty());
615 result.push(UseSegment::Glob);
620 Self::push_segment(&mut result, &mut buf, &mut alias_buf);
623 Self::push_segment(&mut result, &mut buf, &mut alias_buf);
637 alias_buf = Some(String::new());
641 if let Some(ref mut buf) = alias_buf {
649 Self::push_segment(&mut result, &mut buf, &mut alias_buf);
659 fn parse_list(&mut self) -> Vec<UseTree> {
660 let mut result = vec![];
662 match self.input.peek().unwrap() {
663 ',' | ' ' => self.bump(),
667 _ => result.push(self.parse_in_list()),
673 let mut parser = Parser {
674 input: s.chars().peekable(),
676 parser.parse_in_list()
680 fn test_use_tree_normalize() {
682 parse_use_tree("a::self").normalize(true),
686 parse_use_tree("a::self as foo").normalize(true),
687 parse_use_tree("a as foo")
690 parse_use_tree("a::{self}").normalize(true),
694 parse_use_tree("a::{b}").normalize(true),
695 parse_use_tree("a::b")
698 parse_use_tree("a::{b, c::self}").normalize(true),
699 parse_use_tree("a::{b, c}")
702 parse_use_tree("a::{b as bar, c::self}").normalize(true),
703 parse_use_tree("a::{b as bar, c}")
708 fn test_use_tree_ord() {
709 assert!(parse_use_tree("a").normalize(true) < parse_use_tree("aa").normalize(true));
710 assert!(parse_use_tree("a").normalize(true) < parse_use_tree("a::a").normalize(true));
711 assert!(parse_use_tree("a").normalize(true) < parse_use_tree("*").normalize(true));
712 assert!(parse_use_tree("a").normalize(true) < parse_use_tree("{a, b}").normalize(true));
713 assert!(parse_use_tree("*").normalize(true) < parse_use_tree("{a, b}").normalize(true));
716 parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, dddddddd}").normalize(true)
717 < parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, ddddddddd}").normalize(true)
720 parse_use_tree("serde::de::{Deserialize}").normalize(true)
721 < parse_use_tree("serde_json").normalize(true)
724 parse_use_tree("a::b::c").normalize(true) < parse_use_tree("a::b::*").normalize(true)
727 parse_use_tree("foo::{Bar, Baz}").normalize(true)
728 < parse_use_tree("{Bar, Baz}").normalize(true)
732 parse_use_tree("foo::{self as bar}").normalize(true)
733 < parse_use_tree("foo::{qux as bar}").normalize(true)
736 parse_use_tree("foo::{qux as bar}").normalize(true)
737 < parse_use_tree("foo::{baz, qux as bar}").normalize(true)
740 parse_use_tree("foo::{self as bar, baz}").normalize(true)
741 < parse_use_tree("foo::{baz, qux as bar}").normalize(true)
744 assert!(parse_use_tree("foo").normalize(true) < parse_use_tree("Foo").normalize(true));
745 assert!(parse_use_tree("foo").normalize(true) < parse_use_tree("foo::Bar").normalize(true));
748 parse_use_tree("std::cmp::{d, c, b, a}").normalize(true)
749 < parse_use_tree("std::cmp::{b, e, g, f}").normalize(true)