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  	// print map entries in sorted order
   319  	var nodes []Node
   320  	for node := range cmap {
   321  		nodes = append(nodes, node)
   322  	}
   323  	sort.Sort(byInterval(nodes))
   324  
   325  	var buf bytes.Buffer
   326  	fmt.Fprintln(&buf, "CommentMap {")
   327  	for _, node := range nodes {
   328  		comment := cmap[node]
   329  		// print name of identifiers; print node type for other nodes
   330  		var s string
   331  		if ident, ok := node.(*Ident); ok {
   332  			s = ident.Name
   333  		} else {
   334  			s = fmt.Sprintf("%T", node)
   335  		}
   336  		fmt.Fprintf(&buf, "\t%p  %20s:  %s\n", node, s, summary(comment))
   337  	}
   338  	fmt.Fprintln(&buf, "}")
   339  	return buf.String()
   340  }
   341
View as plain text