// Copyright 2011 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package ast

import (
	
	
	
	
)

// SortImports sorts runs of consecutive import lines in import blocks in f.
// It also removes duplicate imports when it is possible to do so without data loss.
func ( *token.FileSet,  *File) {
	for ,  := range .Decls {
		,  := .(*GenDecl)
		if ! || .Tok != token.IMPORT {
			// Not an import declaration, so we're done.
			// Imports are always first.
			break
		}

		if !.Lparen.IsValid() {
			// Not a block: sorted by default.
			continue
		}

		// Identify and sort runs of specs on successive lines.
		 := 0
		 := .Specs[:0]
		for ,  := range .Specs {
			if  >  && lineAt(, .Pos()) > 1+lineAt(, .Specs[-1].End()) {
				// j begins a new run. End this one.
				 = append(, sortSpecs(, , .Specs[:])...)
				 = 
			}
		}
		 = append(, sortSpecs(, , .Specs[:])...)
		.Specs = 

		// Deduping can leave a blank line before the rparen; clean that up.
		if len(.Specs) > 0 {
			 := .Specs[len(.Specs)-1]
			 := lineAt(, .Pos())
			 := lineAt(, .Rparen)
			for  > +1 {
				--
				.File(.Rparen).MergeLine()
			}
		}
	}
}

func lineAt( *token.FileSet,  token.Pos) int {
	return .PositionFor(, false).Line
}

func importPath( Spec) string {
	,  := strconv.Unquote(.(*ImportSpec).Path.Value)
	if  == nil {
		return 
	}
	return ""
}

func importName( Spec) string {
	 := .(*ImportSpec).Name
	if  == nil {
		return ""
	}
	return .Name
}

func importComment( Spec) string {
	 := .(*ImportSpec).Comment
	if  == nil {
		return ""
	}
	return .Text()
}

// collapse indicates whether prev may be removed, leaving only next.
func collapse(,  Spec) bool {
	if importPath() != importPath() || importName() != importName() {
		return false
	}
	return .(*ImportSpec).Comment == nil
}

type posSpan struct {
	Start token.Pos
	End   token.Pos
}

type cgPos struct {
	left bool // true if comment is to the left of the spec, false otherwise.
	cg   *CommentGroup
}

func sortSpecs( *token.FileSet,  *File,  []Spec) []Spec {
	// Can't short-circuit here even if specs are already sorted,
	// since they might yet need deduplication.
	// A lone import, however, may be safely ignored.
	if len() <= 1 {
		return 
	}

	// Record positions for specs.
	 := make([]posSpan, len())
	for ,  := range  {
		[] = posSpan{.Pos(), .End()}
	}

	// Identify comments in this range.
	 := [0].Start
	 := [len()-1].End
	 := .File().LineStart(lineAt(, ))
	 := lineAt(, )
	 := .File()
	var  token.Pos
	if  == .LineCount() {
		 = 
	} else {
		 = .LineStart( + 1) // beginning of next line
	}
	 := len(.Comments)
	 := -1
	for ,  := range .Comments {
		if .End() >=  {
			break
		}
		// g.End() < end
		if  <= .Pos() {
			// comment is within the range [beg, end[ of import declarations
			if  <  {
				 = 
			}
			if  >  {
				 = 
			}
		}
	}

	var  []*CommentGroup
	if  >= 0 {
		 = .Comments[ : +1]
	}

	// Assign each comment to the import spec on the same line.
	 := map[*ImportSpec][]cgPos{}
	 := 0
	for ,  := range  {
		for +1 < len() && [+1].Start <= .Pos() {
			++
		}
		var  bool
		// A block comment can appear before the first import spec.
		if  == 0 && [].Start > .Pos() {
			 = true
		} else if +1 < len() && // Or it can appear on the left of an import spec.
			lineAt(, [].Start)+1 == lineAt(, .Pos()) {
			++
			 = true
		}
		 := [].(*ImportSpec)
		[] = append([], cgPos{left: , cg: })
	}

	// Sort the import specs by import path.
	// Remove duplicates, when possible without data loss.
	// Reassign the import paths to have the same position sequence.
	// Reassign each comment to the spec on the same line.
	// Sort the comments by new position.
	slices.SortFunc(, func(,  Spec) int {
		 := importPath()
		 := importPath()
		 := cmp.Compare(, )
		if  != 0 {
			return 
		}
		 := importName()
		 := importName()
		 = cmp.Compare(, )
		if  != 0 {
			return 
		}
		return cmp.Compare(importComment(), importComment())
	})

	// Dedup. Thanks to our sorting, we can just consider
	// adjacent pairs of imports.
	 := [:0]
	for ,  := range  {
		if  == len()-1 || !collapse(, [+1]) {
			 = append(, )
		} else {
			 := .Pos()
			.File().MergeLine(lineAt(, ))
		}
	}
	 = 

	// Fix up comment positions
	for ,  := range  {
		 := .(*ImportSpec)
		if .Name != nil {
			.Name.NamePos = [].Start
		}
		.Path.ValuePos = [].Start
		.EndPos = [].End
		for ,  := range [] {
			for ,  := range .cg.List {
				if .left {
					.Slash = [].Start - 1
				} else {
					// An import spec can have both block comment and a line comment
					// to its right. In that case, both of them will have the same pos.
					// But while formatting the AST, the line comment gets moved to
					// after the block comment.
					.Slash = [].End
				}
			}
		}
	}

	slices.SortFunc(, func(,  *CommentGroup) int {
		return cmp.Compare(.Pos(), .Pos())
	})

	return 
}