code review 6281044: go/ast: comment map implementation

go/ast: comment map implementation

A comment map associates comments with AST nodes
and permits correct updating of the AST's comment
list when the AST is manipulated.

[gri, 2012-06-04 23:51:02]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://code.google.com/p/go

[gri, 2012-06-05 17:13:04]

hold off on this one - there's some issues with it
- gri

On Mon, Jun 4, 2012 at 4:51 PM,  <gri@golang.org> wrote:
> Reviewers: golang-dev_googlegroups.com,
>
> Message:
> Hello golang-dev@googlegroups.com,
>
> I'd like you to review this change to
> https://code.google.com/p/go
>
>
> Description:
> go/ast: comment map implementation
>
> A comment map associates comments with AST nodes
> and permits correct updating of the AST's comment
> list when the AST is manipulated.
>
> Please review this at http://codereview.appspot.com/6281044/
>
> Affected files:
>  A src/pkg/go/ast/commentmap.go
>  A src/pkg/go/ast/commentmap_test.go
>
>

[gri, 2012-06-07 01:23:25]

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2012-06-07 03:26:43]

This is new API, but we can still tweak it until it is released, probably in Go
1.1.

I am curious about the future uses of the CommentMap. It seems like it does not
have enough information to be used in gofmt, for example. What are the plans?

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go
File src/pkg/go/ast/commentmap.go (right):

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:12: // byPos implements sort.Interface
These are fairly formulaic. I'd drop them, or change them to say something
specific to the type, like

// byPos implements sort.Interface, comparing by source position.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:19: // SortComments sorts the list of comment
groups in source order.
Does this need to be public API?

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:30: // A CommentMap maps AST nodes to the list of
comment groups
Please use singular where possible, to be more precise:

// A CommentMap maps an AST node to a list of comment groups
// associated with it.

I would also appreciate a sentence or two more explaining the relationship, like
"These are the comments preceding that statement." or something. I don't
understand how the map distinguishes a preceding block comment from a following
end-of-line comment.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:58: list := make([]Node, 0, 64) // 64 seems like a
good initial capacity
Any particular reason? I would think append would be in charge of that decision.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:65: panic("internal error: should not be
reachable")
Is there harm in returning false? Might avoid panics later.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:131: // and the comments are taken from f.Comments.
Like above, it would be nice to make clear how block comments vs end-of-line
comments are handled.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:141: clist := make([]*CommentGroup,
len(f.Comments))
maybe comments and nodes instead of clist and nlist? The types make clear that
they are lists.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:147: // create node list in lexcial order
lexical

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:152: var p Node               // previous node
var ( ...?

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:181: // TODO(gri) try to simplify the logic below
One way to simplify would be to pop nodes from the stack until the top of stack
holds a node that cannot match the comment, and then use the node before that
(the one most recently popped). I wonder if the stack is even necessary. Perhaps
it would work to do the depth-first pre-order traversal here instead:

comments = ... sorted by order
Inspect(f, func(n Node) bool {
    switch n.(type) {
    case nil, *CommentGroup, *Comment:
        return false
    }

    for len(comments) > 0 && comments[0].Line <= n.Line {
       cmap[n] = append(cmap[n], comments[0])
       comments = comments[1:]
    }
})

 
This would have different semantics than the current code but would be very easy
to explain: each comment is assigned to the first node that starts on the same
line or a later line in the source.

// comment1
if x { // comment2
} // comment3
// comment4

f()

in this case comment1 and comment2 would be assigned to the if, while comment3
and comment4 would be associated with f. I think the comment3 and comment4 cases
are pretty rare.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:234: // create a map of all nodes
I wonder if it would save noticeable memory to copy cmap instead:

missing := map[Node]bool{}
for n := range cmap { missing[n] = true }
Inspect( ... delete(missing, n) ... )
... if missing[n] { delete(cmap, n) } ...

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:248: // List returns the list of comment groups
given a comment map.
s/given a/in the/

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap_te...
File src/pkg/go/ast/commentmap_test.go (right):

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap_te...
src/pkg/go/ast/commentmap_test.go:5: // To avoid cyclic dependencies, this file
is in a separate package.
This confused me on first reading.
"avoid a cyclic dependency with go/parser"?

[gri, 2012-06-07 18:59:22]

PTAL.

The current plan is to use comment maps to augment the AST filtering code which
is not dealing with comments correctly. Those changes should be completely
internal.

A longer-term plan could be to use comment maps instead of comment lists (it
seems a better representation in retrospect). For one, one could extend tha map
with more information about the comment positioning (before, next, after, a
node), and then use this in the go/printer directly. It may simplify its logic
dramatically. But for a good job one would have to experiment a little bit.

One option might be to not expose comment maps at all for now (keep it
completely inside AST and just fix the filtering and related issue 3454) and
export it once we are happy with it.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go
File src/pkg/go/ast/commentmap.go (right):

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:12: // byPos implements sort.Interface
On 2012/06/07 03:26:43, rsc wrote:
> These are fairly formulaic. I'd drop them, or change them to say something
> specific to the type, like
> 
> // byPos implements sort.Interface, comparing by source position.

Done.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:19: // SortComments sorts the list of comment
groups in source order.
On 2012/06/07 03:26:43, rsc wrote:
> Does this need to be public API?

I was debating this myself. Changed. We can always add it later if necessary.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:30: // A CommentMap maps AST nodes to the list of
comment groups
On 2012/06/07 03:26:43, rsc wrote:
> Please use singular where possible, to be more precise:
> 
> // A CommentMap maps an AST node to a list of comment groups
> // associated with it.
> 
> I would also appreciate a sentence or two more explaining the relationship,
like
> "These are the comments preceding that statement." or something. I don't
> understand how the map distinguishes a preceding block comment from a
following
> end-of-line comment.
> 

Done.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:58: list := make([]Node, 0, 64) // 64 seems like a
good initial capacity
On 2012/06/07 03:26:43, rsc wrote:
> Any particular reason? I would think append would be in charge of that
decision.

Done.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:65: panic("internal error: should not be
reachable")
On 2012/06/07 03:26:43, rsc wrote:
> Is there harm in returning false? Might avoid panics later.

if reached, it does indicate a misunderstanding of the traversal or the AST. but
it's fine to ignore it.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:131: // and the comments are taken from f.Comments.
On 2012/06/07 03:26:43, rsc wrote:
> Like above, it would be nice to make clear how block comments vs end-of-line
> comments are handled.

Done.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:141: clist := make([]*CommentGroup,
len(f.Comments))
On 2012/06/07 03:26:43, rsc wrote:
> maybe comments and nodes instead of clist and nlist? The types make clear that
> they are lists.
> 

Done.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:147: // create node list in lexcial order
On 2012/06/07 03:26:43, rsc wrote:
> lexical

Done.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:152: var p Node               // previous node
On 2012/06/07 03:26:43, rsc wrote:
> var ( ...?

Done.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:181: // TODO(gri) try to simplify the logic below
I think the stack is not needed and one could use the recursion directly. I am
fine with making this change eventually, but first I'd like to gain some more
experience with this. The change would be completely internal.

On 2012/06/07 03:26:43, rsc wrote:
> One way to simplify would be to pop nodes from the stack until the top of
stack
> holds a node that cannot match the comment, and then use the node before that
> (the one most recently popped). I wonder if the stack is even necessary.
Perhaps
> it would work to do the depth-first pre-order traversal here instead:
> 
> comments = ... sorted by order
> Inspect(f, func(n Node) bool {
>     switch n.(type) {
>     case nil, *CommentGroup, *Comment:
>         return false
>     }
> 
>     for len(comments) > 0 && comments[0].Line <= n.Line {
>        cmap[n] = append(cmap[n], comments[0])
>        comments = comments[1:]
>     }
> })
> 
>  
> This would have different semantics than the current code but would be very
easy
> to explain: each comment is assigned to the first node that starts on the same
> line or a later line in the source.
> 
> // comment1
> if x { // comment2
> } // comment3
> // comment4
> 
> f()
> 
> in this case comment1 and comment2 would be assigned to the if, while comment3
> and comment4 would be associated with f. I think the comment3 and comment4
cases
> are pretty rare.

I sometimes have a block/statement ending in a comment (on the next line)
stating the invariants I know after that block, followed by an empty line. It's
not complicated to handle in the existing code, and I am reasonably confident it
works correctly. I prefer to make changes here later.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:234: // create a map of all nodes
On 2012/06/07 03:26:43, rsc wrote:
> I wonder if it would save noticeable memory to copy cmap instead:
> 
> missing := map[Node]bool{}
> for n := range cmap { missing[n] = true }
> Inspect( ... delete(missing, n) ... )
> ... if missing[n] { delete(cmap, n) } ...
> 

good idea. done.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap.go...
src/pkg/go/ast/commentmap.go:248: // List returns the list of comment groups
given a comment map.
On 2012/06/07 03:26:43, rsc wrote:
> s/given a/in the/

Done.

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap_te...
File src/pkg/go/ast/commentmap_test.go (right):

http://codereview.appspot.com/6281044/diff/15002/src/pkg/go/ast/commentmap_te...
src/pkg/go/ast/commentmap_test.go:5: // To avoid cyclic dependencies, this file
is in a separate package.
On 2012/06/07 03:26:43, rsc wrote:
> This confused me on first reading.
> "avoid a cyclic dependency with go/parser"?
> 

Done.

[rsc, 2012-06-07 19:09:41]

LGTM

[gri, 2012-06-07 23:44:11]

PTAL.

Changed Update function (now called Filter).
- gri

On Thu, Jun 7, 2012 at 12:09 PM,  <rsc@golang.org> wrote:
> LGTM
>
>
> http://codereview.appspot.com/6281044/

[rsc, 2012-06-13 19:09:30]

LGTM

[gri, 2012-06-13 20:32:45]

*** Submitted as http://code.google.com/p/go/source/detail?r=5da2d3663cf1 ***

go/ast: comment map implementation

A comment map associates comments with AST nodes
and permits correct updating of the AST's comment
list when the AST is manipulated.

R=rsc
CC=golang-dev
http://codereview.appspot.com/6281044