<commit_before>// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

use std::cmp::Ordering;

use config::lists::*;
use syntax::ast::{self, UseTreeKind};
use syntax::source_map::{self, BytePos, Span, DUMMY_SP};

use comment::combine_strs_with_missing_comments;
use config::{Edition, IndentStyle};
use lists::{definitive_tactic, itemize_list, write_list, ListFormatting, ListItem, Separator};
use rewrite::{Rewrite, RewriteContext};
use shape::Shape;
use source_map::SpanUtils;
use spanned::Spanned;
use utils::{is_same_visibility, mk_sp, rewrite_ident};
use visitor::FmtVisitor;

use std::borrow::Cow;
use std::fmt;

/// Returns a name imported by a `use` declaration. e.g. returns `Ordering`
/// for `std::cmp::Ordering` and `self` for `std::cmp::self`.
pub fn path_to_imported_ident(path: &ast::Path) -> ast::Ident {
    path.segments.last().unwrap().ident
}

impl<'a> FmtVisitor<'a> {
    pub fn format_import(&mut self, item: &ast::Item, tree: &ast::UseTree) {
        let span = item.span();
        let shape = self.shape();
        let rw = UseTree::from_ast(
            &self.get_context(),
            tree,
            None,
            Some(item.vis.clone()),
            Some(item.span.lo()),
            Some(item.attrs.clone()),
        ).rewrite_top_level(&self.get_context(), shape);
        match rw {
            Some(ref s) if s.is_empty() => {
                // Format up to last newline
                let prev_span = mk_sp(self.last_pos, source!(self, span).lo());
                let trimmed_snippet = self.snippet(prev_span).trim_right();
                let span_end = self.last_pos + BytePos(trimmed_snippet.len() as u32);
                self.format_missing(span_end);
                // We have an excessive newline from the removed import.
                if self.buffer.ends_with('\n') {
                    self.buffer.pop();
                    self.line_number -= 1;
                }
                self.last_pos = source!(self, span).hi();
            }
            Some(ref s) => {
                self.format_missing_with_indent(source!(self, span).lo());
                self.push_str(s);
                self.last_pos = source!(self, span).hi();
            }
            None => {
                self.format_missing_with_indent(source!(self, span).lo());
                self.format_missing(source!(self, span).hi());
            }
        }
    }
}

// Ordering of imports

// We order imports by translating to our own representation and then sorting.
// The Rust AST data structures are really bad for this. Rustfmt applies a bunch
// of normalisations to imports and since we want to sort based on the result
// of these (and to maintain idempotence) we must apply the same normalisations
// to the data structures for sorting.
//
// We sort `self` and `super` before other imports, then identifier imports,
// then glob imports, then lists of imports. We do not take aliases into account
// when ordering unless the imports are identical except for the alias (rare in
// practice).

// FIXME(#2531) - we should unify the comparison code here with the formatting
// code elsewhere since we are essentially string-ifying twice. Furthermore, by
// parsing to our own format on comparison, we repeat a lot of work when
// sorting.

// FIXME we do a lot of allocation to make our own representation.
#[derive(Clone, Eq, PartialEq)]
pub enum UseSegment {
    Ident(String, Option<String>),
    Slf(Option<String>),
    Super(Option<String>),
    Glob,
    List(Vec<UseTree>),
}

#[derive(Clone)]
pub struct UseTree {
    pub path: Vec<UseSegment>,
    pub span: Span,
    // Comment information within nested use tree.
    pub list_item: Option<ListItem>,
    // Additional fields for top level use items.
    // Should we have another struct for top-level use items rather than reusing this?
    visibility: Option<ast::Visibility>,
    attrs: Option<Vec<ast::Attribute>>,
}

impl PartialEq for UseTree {
    fn eq(&self, other: &UseTree) -> bool {
        self.path == other.path
    }
}
impl Eq for UseTree {}

impl Spanned for UseTree {
    fn span(&self) -> Span {
        let lo = if let Some(ref attrs) = self.attrs {
            attrs.iter().next().map_or(self.span.lo(), |a| a.span.lo())
        } else {
            self.span.lo()
        };
        mk_sp(lo, self.span.hi())
    }
}

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),
            _ => self.clone(),
        }
    }

    fn from_path_segment(
        context: &RewriteContext,
        path_seg: &ast::PathSegment,
        modsep: bool,
    ) -> Option<UseSegment> {
        let name = rewrite_ident(context, path_seg.ident);
        if name.is_empty() || name == "{{root}}" {
            return None;
        }
        Some(match name {
            "self" => UseSegment::Slf(None),
            "super" => UseSegment::Super(None),
            _ => {
                let mod_sep = if modsep { "::" } else { "" };
                UseSegment::Ident(format!("{}{}", mod_sep, name), None)
            }
        })
    }
}

pub fn merge_use_trees(use_trees: Vec<UseTree>) -> Vec<UseTree> {
    let mut result = Vec::with_capacity(use_trees.len());
    for use_tree in use_trees {
        if use_tree.has_comment() || use_tree.attrs.is_some() {
            result.push(use_tree);
            continue;
        }

        for flattened in use_tree.flatten() {
            merge_use_trees_inner(&mut result, flattened);
        }
    }
    result
}

fn merge_use_trees_inner(trees: &mut Vec<UseTree>, use_tree: UseTree) {
    for tree in trees.iter_mut() {
        if tree.share_prefix(&use_tree) {
            tree.merge(use_tree);
            return;
        }
    }

    trees.push(use_tree);
}

impl fmt::Debug for UseTree {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Display::fmt(self, f)
    }
}

impl fmt::Debug for UseSegment {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Display::fmt(self, f)
    }
}

impl fmt::Display for UseSegment {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            UseSegment::Glob => write!(f, "*"),
            UseSegment::Ident(ref s, _) => write!(f, "{}", s),
            UseSegment::Slf(..) => write!(f, "self"),
            UseSegment::Super(..) => write!(f, "super"),
            UseSegment::List(ref list) => {
                write!(f, "{{")?;
                for (i, item) in list.iter().enumerate() {
                    let is_last = i == list.len() - 1;
                    write!(f, "{}", item)?;
                    if !is_last {
                        write!(f, ", ")?;
                    }
                }
                write!(f, "}}")
            }
        }
    }
}
impl fmt::Display for UseTree {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for (i, segment) in self.path.iter().enumerate() {
            let is_last = i == self.path.len() - 1;
            write!(f, "{}", segment)?;
            if !is_last {
                write!(f, "::")?;
            }
        }
        write!(f, "")
    }
}

impl UseTree {
    // Rewrite use tree with `use ` and a trailing `;`.
    pub fn rewrite_top_level(&self, context: &RewriteContext, shape: Shape) -> Option<String> {
        let vis = self.visibility.as_ref().map_or(Cow::from(""), |vis| {
            ::utils::format_visibility(context, &vis)
        });
        let use_str = self
            .rewrite(context, shape.offset_left(vis.len())?)
            .map(|s| {
                if s.is_empty() {
                    s.to_owned()
                } else {
                    format!("{}use {};", vis, s)
                }
            })?;
        if let Some(ref attrs) = self.attrs {
            let attr_str = attrs.rewrite(context, shape)?;
            let lo = attrs.last().as_ref()?.span().hi();
            let hi = self.span.lo();
            let span = mk_sp(lo, hi);
            combine_strs_with_missing_comments(context, &attr_str, &use_str, span, shape, false)
        } else {
            Some(use_str)
        }
    }

    // FIXME: Use correct span?
    // The given span is essentially incorrect, since we are reconstructing
    // use statements. This should not be a problem, though, since we have
    // already tried to extract comment and observed that there are no comment
    // around the given use item, and the span will not be used afterward.
    fn from_path(path: Vec<UseSegment>, span: Span) -> UseTree {
        UseTree {
            path,
            span,
            list_item: None,
            visibility: None,
            attrs: None,
        }
    }

    pub fn from_ast_with_normalization(
        context: &RewriteContext,
        item: &ast::Item,
    ) -> Option<UseTree> {
        match item.node {
            ast::ItemKind::Use(ref use_tree) => Some(
                UseTree::from_ast(
                    context,
                    use_tree,
                    None,
                    Some(item.vis.clone()),
                    Some(item.span.lo()),
                    if item.attrs.is_empty() {
                        None
                    } else {
                        Some(item.attrs.clone())
                    },
                ).normalize(),
            ),
            _ => None,
        }
    }

    fn from_ast(
        context: &RewriteContext,
        a: &ast::UseTree,
        list_item: Option<ListItem>,
        visibility: Option<ast::Visibility>,
        opt_lo: Option<BytePos>,
        attrs: Option<Vec<ast::Attribute>>,
    ) -> UseTree {
        let span = if let Some(lo) = opt_lo {
            mk_sp(lo, a.span.hi())
        } else {
            a.span
        };
        let mut result = UseTree {
            path: vec![],
            span,
            list_item,
            visibility,
            attrs,
        };

        let leading_modsep = if context.config.edition() == Edition::Edition2018 {
            if a.prefix.to_string().len() > 2 && a.prefix.to_string().starts_with("::") {
                true
            } else {
                false
            }
        } else {
            false
        };
        for p in &a.prefix.segments {
            if let Some(use_segment) = UseSegment::from_path_segment(context, p, leading_modsep) {
                result.path.push(use_segment);
            }
        }
        match a.kind {
            UseTreeKind::Glob => {
                result.path.push(UseSegment::Glob);
            }
            UseTreeKind::Nested(ref list) => {
                // Extract comments between nested use items.
                // This needs to be done before sorting use items.
                let items: Vec<_> = itemize_list(
                    context.snippet_provider,<commit_msg>Fixed overly complicated code as requested in the code review<commit_after>// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

use std::cmp::Ordering;

use config::lists::*;
use syntax::ast::{self, UseTreeKind};
use syntax::source_map::{self, BytePos, Span, DUMMY_SP};

use comment::combine_strs_with_missing_comments;
use config::{Edition, IndentStyle};
use lists::{definitive_tactic, itemize_list, write_list, ListFormatting, ListItem, Separator};
use rewrite::{Rewrite, RewriteContext};
use shape::Shape;
use source_map::SpanUtils;
use spanned::Spanned;
use utils::{is_same_visibility, mk_sp, rewrite_ident};
use visitor::FmtVisitor;

use std::borrow::Cow;
use std::fmt;

/// Returns a name imported by a `use` declaration. e.g. returns `Ordering`
/// for `std::cmp::Ordering` and `self` for `std::cmp::self`.
pub fn path_to_imported_ident(path: &ast::Path) -> ast::Ident {
    path.segments.last().unwrap().ident
}

impl<'a> FmtVisitor<'a> {
    pub fn format_import(&mut self, item: &ast::Item, tree: &ast::UseTree) {
        let span = item.span();
        let shape = self.shape();
        let rw = UseTree::from_ast(
            &self.get_context(),
            tree,
            None,
            Some(item.vis.clone()),
            Some(item.span.lo()),
            Some(item.attrs.clone()),
        ).rewrite_top_level(&self.get_context(), shape);
        match rw {
            Some(ref s) if s.is_empty() => {
                // Format up to last newline
                let prev_span = mk_sp(self.last_pos, source!(self, span).lo());
                let trimmed_snippet = self.snippet(prev_span).trim_right();
                let span_end = self.last_pos + BytePos(trimmed_snippet.len() as u32);
                self.format_missing(span_end);
                // We have an excessive newline from the removed import.
                if self.buffer.ends_with('\n') {
                    self.buffer.pop();
                    self.line_number -= 1;
                }
                self.last_pos = source!(self, span).hi();
            }
            Some(ref s) => {
                self.format_missing_with_indent(source!(self, span).lo());
                self.push_str(s);
                self.last_pos = source!(self, span).hi();
            }
            None => {
                self.format_missing_with_indent(source!(self, span).lo());
                self.format_missing(source!(self, span).hi());
            }
        }
    }
}

// Ordering of imports

// We order imports by translating to our own representation and then sorting.
// The Rust AST data structures are really bad for this. Rustfmt applies a bunch
// of normalisations to imports and since we want to sort based on the result
// of these (and to maintain idempotence) we must apply the same normalisations
// to the data structures for sorting.
//
// We sort `self` and `super` before other imports, then identifier imports,
// then glob imports, then lists of imports. We do not take aliases into account
// when ordering unless the imports are identical except for the alias (rare in
// practice).

// FIXME(#2531) - we should unify the comparison code here with the formatting
// code elsewhere since we are essentially string-ifying twice. Furthermore, by
// parsing to our own format on comparison, we repeat a lot of work when
// sorting.

// FIXME we do a lot of allocation to make our own representation.
#[derive(Clone, Eq, PartialEq)]
pub enum UseSegment {
    Ident(String, Option<String>),
    Slf(Option<String>),
    Super(Option<String>),
    Glob,
    List(Vec<UseTree>),
}

#[derive(Clone)]
pub struct UseTree {
    pub path: Vec<UseSegment>,
    pub span: Span,
    // Comment information within nested use tree.
    pub list_item: Option<ListItem>,
    // Additional fields for top level use items.
    // Should we have another struct for top-level use items rather than reusing this?
    visibility: Option<ast::Visibility>,
    attrs: Option<Vec<ast::Attribute>>,
}

impl PartialEq for UseTree {
    fn eq(&self, other: &UseTree) -> bool {
        self.path == other.path
    }
}
impl Eq for UseTree {}

impl Spanned for UseTree {
    fn span(&self) -> Span {
        let lo = if let Some(ref attrs) = self.attrs {
            attrs.iter().next().map_or(self.span.lo(), |a| a.span.lo())
        } else {
            self.span.lo()
        };
        mk_sp(lo, self.span.hi())
    }
}

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),
            _ => self.clone(),
        }
    }

    fn from_path_segment(
        context: &RewriteContext,
        path_seg: &ast::PathSegment,
        modsep: bool,
    ) -> Option<UseSegment> {
        let name = rewrite_ident(context, path_seg.ident);
        if name.is_empty() || name == "{{root}}" {
            return None;
        }
        Some(match name {
            "self" => UseSegment::Slf(None),
            "super" => UseSegment::Super(None),
            _ => {
                let mod_sep = if modsep { "::" } else { "" };
                UseSegment::Ident(format!("{}{}", mod_sep, name), None)
            }
        })
    }
}

pub fn merge_use_trees(use_trees: Vec<UseTree>) -> Vec<UseTree> {
    let mut result = Vec::with_capacity(use_trees.len());
    for use_tree in use_trees {
        if use_tree.has_comment() || use_tree.attrs.is_some() {
            result.push(use_tree);
            continue;
        }

        for flattened in use_tree.flatten() {
            merge_use_trees_inner(&mut result, flattened);
        }
    }
    result
}

fn merge_use_trees_inner(trees: &mut Vec<UseTree>, use_tree: UseTree) {
    for tree in trees.iter_mut() {
        if tree.share_prefix(&use_tree) {
            tree.merge(use_tree);
            return;
        }
    }

    trees.push(use_tree);
}

impl fmt::Debug for UseTree {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Display::fmt(self, f)
    }
}

impl fmt::Debug for UseSegment {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Display::fmt(self, f)
    }
}

impl fmt::Display for UseSegment {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            UseSegment::Glob => write!(f, "*"),
            UseSegment::Ident(ref s, _) => write!(f, "{}", s),
            UseSegment::Slf(..) => write!(f, "self"),
            UseSegment::Super(..) => write!(f, "super"),
            UseSegment::List(ref list) => {
                write!(f, "{{")?;
                for (i, item) in list.iter().enumerate() {
                    let is_last = i == list.len() - 1;
                    write!(f, "{}", item)?;
                    if !is_last {
                        write!(f, ", ")?;
                    }
                }
                write!(f, "}}")
            }
        }
    }
}
impl fmt::Display for UseTree {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for (i, segment) in self.path.iter().enumerate() {
            let is_last = i == self.path.len() - 1;
            write!(f, "{}", segment)?;
            if !is_last {
                write!(f, "::")?;
            }
        }
        write!(f, "")
    }
}

impl UseTree {
    // Rewrite use tree with `use ` and a trailing `;`.
    pub fn rewrite_top_level(&self, context: &RewriteContext, shape: Shape) -> Option<String> {
        let vis = self.visibility.as_ref().map_or(Cow::from(""), |vis| {
            ::utils::format_visibility(context, &vis)
        });
        let use_str = self
            .rewrite(context, shape.offset_left(vis.len())?)
            .map(|s| {
                if s.is_empty() {
                    s.to_owned()
                } else {
                    format!("{}use {};", vis, s)
                }
            })?;
        if let Some(ref attrs) = self.attrs {
            let attr_str = attrs.rewrite(context, shape)?;
            let lo = attrs.last().as_ref()?.span().hi();
            let hi = self.span.lo();
            let span = mk_sp(lo, hi);
            combine_strs_with_missing_comments(context, &attr_str, &use_str, span, shape, false)
        } else {
            Some(use_str)
        }
    }

    // FIXME: Use correct span?
    // The given span is essentially incorrect, since we are reconstructing
    // use statements. This should not be a problem, though, since we have
    // already tried to extract comment and observed that there are no comment
    // around the given use item, and the span will not be used afterward.
    fn from_path(path: Vec<UseSegment>, span: Span) -> UseTree {
        UseTree {
            path,
            span,
            list_item: None,
            visibility: None,
            attrs: None,
        }
    }

    pub fn from_ast_with_normalization(
        context: &RewriteContext,
        item: &ast::Item,
    ) -> Option<UseTree> {
        match item.node {
            ast::ItemKind::Use(ref use_tree) => Some(
                UseTree::from_ast(
                    context,
                    use_tree,
                    None,
                    Some(item.vis.clone()),
                    Some(item.span.lo()),
                    if item.attrs.is_empty() {
                        None
                    } else {
                        Some(item.attrs.clone())
                    },
                ).normalize(),
            ),
            _ => None,
        }
    }

    fn from_ast(
        context: &RewriteContext,
        a: &ast::UseTree,
        list_item: Option<ListItem>,
        visibility: Option<ast::Visibility>,
        opt_lo: Option<BytePos>,
        attrs: Option<Vec<ast::Attribute>>,
    ) -> UseTree {
        let span = if let Some(lo) = opt_lo {
            mk_sp(lo, a.span.hi())
        } else {
            a.span
        };
        let mut result = UseTree {
            path: vec![],
            span,
            list_item,
            visibility,
            attrs,
        };

        let leading_modsep = context.config.edition() == Edition::Edition2018
            && a.prefix.to_string().len() > 2
            && a.prefix.to_string().starts_with("::");

        for p in &a.prefix.segments {
            if let Some(use_segment) = UseSegment::from_path_segment(context, p, leading_modsep) {
                result.path.push(use_segment);
            }
        }
        match a.kind {
            UseTreeKind::Glob => {
                result.path.push(UseSegment::Glob);
            }
            UseTreeKind::Nested(ref list) => {
                // Extract comments between nested use items.
                // This needs to be done before sorting use items.
                let items: Vec<_> = itemize_list(
                    context.snippet_provider,
{'fraction_non_alphanumeric': 0.13198058337342022, 'fraction_numerical': 0.0019241702016005598, 'mean_word_length': 1.887738350801869, 'pattern_counts': {'":': 6, '<': 55, '<?xml version=': 0, '>': 123, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1301803', 'n_tokens_mistral': 6802, 'n_tokens_neox': 6636, 'n_words': 1759}