Source file src/go/ast/commentmap.go

     1	// Copyright 2012 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	package ast
     6	
     7	import (
     8		"bytes"
     9		"fmt"
    10		"go/token"
    11		"sort"
    12	)
    13	
    14	type byPos []*CommentGroup
    15	
    16	func (a byPos) Len() int           { return len(a) }
    17	func (a byPos) Less(i, j int) bool { return a[i].Pos() < a[j].Pos() }
    18	func (a byPos) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
    19	
    20	// sortComments sorts the list of comment groups in source order.
    21	//
    22	func sortComments(list []*CommentGroup) {
    23		// TODO(gri): Does it make sense to check for sorted-ness
    24		//            first (because we know that sorted-ness is
    25		//            very likely)?
    26		if orderedList := byPos(list); !sort.IsSorted(orderedList) {
    27			sort.Sort(orderedList)
    28		}
    29	}
    30	
    31	// A CommentMap maps an AST node to a list of comment groups
    32	// associated with it. See NewCommentMap for a description of
    33	// the association.
    34	//
    35	type CommentMap map[Node][]*CommentGroup
    36	
    37	func (cmap CommentMap) addComment(n Node, c *CommentGroup) {
    38		list := cmap[n]
    39		if len(list) == 0 {
    40			list = []*CommentGroup{c}
    41		} else {
    42			list = append(list, c)
    43		}
    44		cmap[n] = list
    45	}
    46	
    47	type byInterval []Node
    48	
    49	func (a byInterval) Len() int { return len(a) }
    50	func (a byInterval) Less(i, j int) bool {
    51		pi, pj := a[i].Pos(), a[j].Pos()
    52		return pi < pj || pi == pj && a[i].End() > a[j].End()
    53	}
    54	func (a byInterval) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
    55	
    56	// nodeList returns the list of nodes of the AST n in source order.
    57	//
    58	func nodeList(n Node) []Node {
    59		var list []Node
    60		Inspect(n, func(n Node) bool {
    61			// don't collect comments
    62			switch n.(type) {
    63			case nil, *CommentGroup, *Comment:
    64				return false
    65			}
    66			list = append(list, n)
    67			return true
    68		})
    69		// Note: The current implementation assumes that Inspect traverses the
    70		//       AST in depth-first and thus _source_ order. If AST traversal
    71		//       does not follow source order, the sorting call below will be
    72		//       required.
    73		// sort.Sort(byInterval(list))
    74		return list
    75	}
    76	
    77	// A commentListReader helps iterating through a list of comment groups.
    78	//
    79	type commentListReader struct {
    80		fset     *token.FileSet
    81		list     []*CommentGroup
    82		index    int
    83		comment  *CommentGroup  // comment group at current index
    84		pos, end token.Position // source interval of comment group at current index
    85	}
    86	
    87	func (r *commentListReader) eol() bool {
    88		return r.index >= len(r.list)
    89	}
    90	
    91	func (r *commentListReader) next() {
    92		if !r.eol() {
    93			r.comment = r.list[r.index]
    94			r.pos = r.fset.Position(r.comment.Pos())
    95			r.end = r.fset.Position(r.comment.End())
    96			r.index++
    97		}
    98	}
    99	
   100	// A nodeStack keeps track of nested nodes.
   101	// A node lower on the stack lexically contains the nodes higher on the stack.
   102	//
   103	type nodeStack []Node
   104	
   105	// push pops all nodes that appear lexically before n
   106	// and then pushes n on the stack.
   107	//
   108	func (s *nodeStack) push(n Node) {
   109		s.pop(n.Pos())
   110		*s = append((*s), n)
   111	}
   112	
   113	// pop pops all nodes that appear lexically before pos
   114	// (i.e., whose lexical extent has ended before or at pos).
   115	// It returns the last node popped.
   116	//
   117	func (s *nodeStack) pop(pos token.Pos) (top Node) {
   118		i := len(*s)
   119		for i > 0 && (*s)[i-1].End() <= pos {
   120			top = (*s)[i-1]
   121			i--
   122		}
   123		*s = (*s)[0:i]
   124		return top
   125	}
   126	
   127	// NewCommentMap creates a new comment map by associating comment groups
   128	// of the comments list with the nodes of the AST specified by node.
   129	//
   130	// A comment group g is associated with a node n if:
   131	//
   132	//   - g starts on the same line as n ends
   133	//   - g starts on the line immediately following n, and there is
   134	//     at least one empty line after g and before the next node
   135	//   - g starts before n and is not associated to the node before n
   136	//     via the previous rules
   137	//
   138	// NewCommentMap tries to associate a comment group to the "largest"
   139	// node possible: For instance, if the comment is a line comment
   140	// trailing an assignment, the comment is associated with the entire
   141	// assignment rather than just the last operand in the assignment.
   142	//
   143	func NewCommentMap(fset *token.FileSet, node Node, comments []*CommentGroup) CommentMap {
   144		if len(comments) == 0 {
   145			return nil // no comments to map
   146		}
   147	
   148		cmap := make(CommentMap)
   149	
   150		// set up comment reader r
   151		tmp := make([]*CommentGroup, len(comments))
   152		copy(tmp, comments) // don't change incoming comments
   153		sortComments(tmp)
   154		r := commentListReader{fset: fset, list: tmp} // !r.eol() because len(comments) > 0
   155		r.next()
   156	
   157		// create node list in lexical order
   158		nodes := nodeList(node)
   159		nodes = append(nodes, nil) // append sentinel
   160	
   161		// set up iteration variables
   162		var (
   163			p     Node           // previous node
   164			pend  token.Position // end of p
   165			pg    Node           // previous node group (enclosing nodes of "importance")
   166			pgend token.Position // end of pg
   167			stack nodeStack      // stack of node groups
   168		)
   169	
   170		for _, q := range nodes {
   171			var qpos token.Position
   172			if q != nil {
   173				qpos = fset.Position(q.Pos()) // current node position
   174			} else {
   175				// set fake sentinel position to infinity so that
   176				// all comments get processed before the sentinel
   177				const infinity = 1 << 30
   178				qpos.Offset = infinity
   179				qpos.Line = infinity
   180			}
   181	
   182			// process comments before current node
   183			for r.end.Offset <= qpos.Offset {
   184				// determine recent node group
   185				if top := stack.pop(r.comment.Pos()); top != nil {
   186					pg = top
   187					pgend = fset.Position(pg.End())
   188				}
   189				// Try to associate a comment first with a node group
   190				// (i.e., a node of "importance" such as a declaration);
   191				// if that fails, try to associate it with the most recent
   192				// node.
   193				// TODO(gri) try to simplify the logic below
   194				var assoc Node
   195				switch {
   196				case pg != nil &&
   197					(pgend.Line == r.pos.Line ||
   198						pgend.Line+1 == r.pos.Line && r.end.Line+1 < qpos.Line):
   199					// 1) comment starts on same line as previous node group ends, or
   200					// 2) comment starts on the line immediately after the
   201					//    previous node group and there is an empty line before
   202					//    the current node
   203					// => associate comment with previous node group
   204					assoc = pg
   205				case p != nil &&
   206					(pend.Line == r.pos.Line ||
   207						pend.Line+1 == r.pos.Line && r.end.Line+1 < qpos.Line ||
   208						q == nil):
   209					// same rules apply as above for p rather than pg,
   210					// but also associate with p if we are at the end (q == nil)
   211					assoc = p
   212				default:
   213					// otherwise, associate comment with current node
   214					if q == nil {
   215						// we can only reach here if there was no p
   216						// which would imply that there were no nodes
   217						panic("internal error: no comments should be associated with sentinel")
   218					}
   219					assoc = q
   220				}
   221				cmap.addComment(assoc, r.comment)
   222				if r.eol() {
   223					return cmap
   224				}
   225				r.next()
   226			}
   227	
   228			// update previous node
   229			p = q
   230			pend = fset.Position(p.End())
   231	
   232			// update previous node group if we see an "important" node
   233			switch q.(type) {
   234			case *File, *Field, Decl, Spec, Stmt:
   235				stack.push(q)
   236			}
   237		}
   238	
   239		return cmap
   240	}
   241	
   242	// Update replaces an old node in the comment map with the new node
   243	// and returns the new node. Comments that were associated with the
   244	// old node are associated with the new node.
   245	//
   246	func (cmap CommentMap) Update(old, new Node) Node {
   247		if list := cmap[old]; len(list) > 0 {
   248			delete(cmap, old)
   249			cmap[new] = append(cmap[new], list...)
   250		}
   251		return new
   252	}
   253	
   254	// Filter returns a new comment map consisting of only those
   255	// entries of cmap for which a corresponding node exists in
   256	// the AST specified by node.
   257	//
   258	func (cmap CommentMap) Filter(node Node) CommentMap {
   259		umap := make(CommentMap)
   260		Inspect(node, func(n Node) bool {
   261			if g := cmap[n]; len(g) > 0 {
   262				umap[n] = g
   263			}
   264			return true
   265		})
   266		return umap
   267	}
   268	
   269	// Comments returns the list of comment groups in the comment map.
   270	// The result is sorted in source order.
   271	//
   272	func (cmap CommentMap) Comments() []*CommentGroup {
   273		list := make([]*CommentGroup, 0, len(cmap))
   274		for _, e := range cmap {
   275			list = append(list, e...)
   276		}
   277		sortComments(list)
   278		return list
   279	}
   280	
   281	func summary(list []*CommentGroup) string {
   282		const maxLen = 40
   283		var buf bytes.Buffer
   284	
   285		// collect comments text
   286	loop:
   287		for _, group := range list {
   288			// Note: CommentGroup.Text() does too much work for what we
   289			//       need and would only replace this innermost loop.
   290			//       Just do it explicitly.
   291			for _, comment := range group.List {
   292				if buf.Len() >= maxLen {
   293					break loop
   294				}
   295				buf.WriteString(comment.Text)
   296			}
   297		}
   298	
   299		// truncate if too long
   300		if buf.Len() > maxLen {
   301			buf.Truncate(maxLen - 3)
   302			buf.WriteString("...")
   303		}
   304	
   305		// replace any invisibles with blanks
   306		bytes := buf.Bytes()
   307		for i, b := range bytes {
   308			switch b {
   309			case '\t', '\n', '\r':
   310				bytes[i] = ' '
   311			}
   312		}
   313	
   314		return string(bytes)
   315	}
   316	
   317	func (cmap CommentMap) String() string {
   318		var buf bytes.Buffer
   319		fmt.Fprintln(&buf, "CommentMap {")
   320		for node, comment := range cmap {
   321			// print name of identifiers; print node type for other nodes
   322			var s string
   323			if ident, ok := node.(*Ident); ok {
   324				s = ident.Name
   325			} else {
   326				s = fmt.Sprintf("%T", node)
   327			}
   328			fmt.Fprintf(&buf, "\t%p  %20s:  %s\n", node, s, summary(comment))
   329		}
   330		fmt.Fprintln(&buf, "}")
   331		return buf.String()
   332	}
   333	

View as plain text