// Copyright 2012 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 (
	
	
	
	
)

type byPos []*CommentGroup

func ( byPos) () int           { return len() }
func ( byPos) (,  int) bool { return [].Pos() < [].Pos() }
func ( byPos) (,  int)      { [], [] = [], [] }

// sortComments sorts the list of comment groups in source order.
//
func sortComments( []*CommentGroup) {
	// TODO(gri): Does it make sense to check for sorted-ness
	//            first (because we know that sorted-ness is
	//            very likely)?
	if  := byPos(); !sort.IsSorted() {
		sort.Sort()
	}
}

// A CommentMap maps an AST node to a list of comment groups
// associated with it. See NewCommentMap for a description of
// the association.
//
type CommentMap map[Node][]*CommentGroup

func ( CommentMap) ( Node,  *CommentGroup) {
	 := []
	if len() == 0 {
		 = []*CommentGroup{}
	} else {
		 = append(, )
	}
	[] = 
}

type byInterval []Node

func ( byInterval) () int { return len() }
func ( byInterval) (,  int) bool {
	,  := [].Pos(), [].Pos()
	return  <  ||  ==  && [].End() > [].End()
}
func ( byInterval) (,  int) { [], [] = [], [] }

// nodeList returns the list of nodes of the AST n in source order.
//
func nodeList( Node) []Node {
	var  []Node
	Inspect(, func( Node) bool {
		// don't collect comments
		switch .(type) {
		case nil, *CommentGroup, *Comment:
			return false
		}
		 = append(, )
		return true
	})
	// Note: The current implementation assumes that Inspect traverses the
	//       AST in depth-first and thus _source_ order. If AST traversal
	//       does not follow source order, the sorting call below will be
	//       required.
	// sort.Sort(byInterval(list))
	return 
}

// A commentListReader helps iterating through a list of comment groups.
//
type commentListReader struct {
	fset     *token.FileSet
	list     []*CommentGroup
	index    int
	comment  *CommentGroup  // comment group at current index
	pos, end token.Position // source interval of comment group at current index
}

func ( *commentListReader) () bool {
	return .index >= len(.list)
}

func ( *commentListReader) () {
	if !.eol() {
		.comment = .list[.index]
		.pos = .fset.Position(.comment.Pos())
		.end = .fset.Position(.comment.End())
		.index++
	}
}

// A nodeStack keeps track of nested nodes.
// A node lower on the stack lexically contains the nodes higher on the stack.
//
type nodeStack []Node

// push pops all nodes that appear lexically before n
// and then pushes n on the stack.
//
func ( *nodeStack) ( Node) {
	.pop(.Pos())
	* = append((*), )
}

// pop pops all nodes that appear lexically before pos
// (i.e., whose lexical extent has ended before or at pos).
// It returns the last node popped.
//
func ( *nodeStack) ( token.Pos) ( Node) {
	 := len(*)
	for  > 0 && (*)[-1].End() <=  {
		 = (*)[-1]
		--
	}
	* = (*)[0:]
	return 
}

// NewCommentMap creates a new comment map by associating comment groups
// of the comments list with the nodes of the AST specified by node.
//
// A comment group g is associated with a node n if:
//
//   - g starts on the same line as n ends
//   - g starts on the line immediately following n, and there is
//     at least one empty line after g and before the next node
//   - g starts before n and is not associated to the node before n
//     via the previous rules
//
// NewCommentMap tries to associate a comment group to the "largest"
// node possible: For instance, if the comment is a line comment
// trailing an assignment, the comment is associated with the entire
// assignment rather than just the last operand in the assignment.
//
func ( *token.FileSet,  Node,  []*CommentGroup) CommentMap {
	if len() == 0 {
		return nil // no comments to map
	}

	 := make(CommentMap)

	// set up comment reader r
	 := make([]*CommentGroup, len())
	copy(, ) // don't change incoming comments
	sortComments()
	 := commentListReader{fset: , list: } // !r.eol() because len(comments) > 0
	.next()

	// create node list in lexical order
	 := nodeList()
	 = append(, nil) // append sentinel

	// set up iteration variables
	var (
		     Node           // previous node
		  token.Position // end of p
		    Node           // previous node group (enclosing nodes of "importance")
		 token.Position // end of pg
		 nodeStack      // stack of node groups
	)

	for ,  := range  {
		var  token.Position
		if  != nil {
			 = .Position(.Pos()) // current node position
		} else {
			// set fake sentinel position to infinity so that
			// all comments get processed before the sentinel
			const  = 1 << 30
			.Offset = 
			.Line = 
		}

		// process comments before current node
		for .end.Offset <= .Offset {
			// determine recent node group
			if  := .pop(.comment.Pos());  != nil {
				 = 
				 = .Position(.End())
			}
			// Try to associate a comment first with a node group
			// (i.e., a node of "importance" such as a declaration);
			// if that fails, try to associate it with the most recent
			// node.
			// TODO(gri) try to simplify the logic below
			var  Node
			switch {
			case  != nil &&
				(.Line == .pos.Line ||
					.Line+1 == .pos.Line && .end.Line+1 < .Line):
				// 1) comment starts on same line as previous node group ends, or
				// 2) comment starts on the line immediately after the
				//    previous node group and there is an empty line before
				//    the current node
				// => associate comment with previous node group
				 = 
			case  != nil &&
				(.Line == .pos.Line ||
					.Line+1 == .pos.Line && .end.Line+1 < .Line ||
					 == nil):
				// same rules apply as above for p rather than pg,
				// but also associate with p if we are at the end (q == nil)
				 = 
			default:
				// otherwise, associate comment with current node
				if  == nil {
					// we can only reach here if there was no p
					// which would imply that there were no nodes
					panic("internal error: no comments should be associated with sentinel")
				}
				 = 
			}
			.addComment(, .comment)
			if .eol() {
				return 
			}
			.next()
		}

		// update previous node
		 = 
		 = .Position(.End())

		// update previous node group if we see an "important" node
		switch .(type) {
		case *File, *Field, Decl, Spec, Stmt:
			.push()
		}
	}

	return 
}

// Update replaces an old node in the comment map with the new node
// and returns the new node. Comments that were associated with the
// old node are associated with the new node.
//
func ( CommentMap) (,  Node) Node {
	if  := []; len() > 0 {
		delete(, )
		[] = append([], ...)
	}
	return 
}

// Filter returns a new comment map consisting of only those
// entries of cmap for which a corresponding node exists in
// the AST specified by node.
//
func ( CommentMap) ( Node) CommentMap {
	 := make(CommentMap)
	Inspect(, func( Node) bool {
		if  := []; len() > 0 {
			[] = 
		}
		return true
	})
	return 
}

// Comments returns the list of comment groups in the comment map.
// The result is sorted in source order.
//
func ( CommentMap) () []*CommentGroup {
	 := make([]*CommentGroup, 0, len())
	for ,  := range  {
		 = append(, ...)
	}
	sortComments()
	return 
}

func summary( []*CommentGroup) string {
	const  = 40
	var  bytes.Buffer

	// collect comments text
:
	for ,  := range  {
		// Note: CommentGroup.Text() does too much work for what we
		//       need and would only replace this innermost loop.
		//       Just do it explicitly.
		for ,  := range .List {
			if .Len() >=  {
				break 
			}
			.WriteString(.Text)
		}
	}

	// truncate if too long
	if .Len() >  {
		.Truncate( - 3)
		.WriteString("...")
	}

	// replace any invisibles with blanks
	 := .Bytes()
	for ,  := range  {
		switch  {
		case '\t', '\n', '\r':
			[] = ' '
		}
	}

	return string()
}

func ( CommentMap) () string {
	var  bytes.Buffer
	fmt.Fprintln(&, "CommentMap {")
	for ,  := range  {
		// print name of identifiers; print node type for other nodes
		var  string
		if ,  := .(*Ident);  {
			 = .Name
		} else {
			 = fmt.Sprintf("%T", )
		}
		fmt.Fprintf(&, "\t%p  %20s:  %s\n", , , summary())
	}
	fmt.Fprintln(&, "}")
	return .String()
}