<p>I'm currently working on a protobuf parser and I'm trying to preserve the comments in the AST. However, there many non-trivial cases and I was wondering if there was an already existing algorithm/data structure for this kind of problem.</p>
<p>Here is an example of most of the possible comments:</p>
<pre class="lang-protobuf prettyprint-override"><code>message Comments {
  int32 foo = 1;  // Comment attached to foo.
  // Comment attached to bar.
  int32 bar = 2;

  string baz = 3;
  // Comment attached to baz.
  // Another line attached to baz.

  // Comment attached to moo.
  //
  // Another line attached to moo.
  double moo = 4;

  // Detached comment for corge. This is not leading or trailing comments
  // to moo or corge because there are blank lines separating it from
  // both.

  // Detached comment for corge paragraph 2.

  string corge = 5;
  /* Block comment attached
   * to corge. */
  /* Block comment attached to
   * grault. */
  int32 grault = 6;

  optional int32 another = 7;
  // attached to funny, not trailing comment for another
  optional int32 funny = 8;

  // ignored detached comments.
}
</code></pre>
<p>Note that this is important for my AST to determine leading comments (just before a statement), leading detached comments (look at the comments before corge, they are detached because separated by blank newlines), and trailing comments (just after statements).</p>
<h2>Edit</h2>
<p>As it was not clear, I want to mention that I'm writing a parser by hand and I also wrote a lexer that provides tokens for comment and spaces.</p>

<abstract-syntax-tree><comments>
Preserving Comments in AST
CC BY-SA 4.0
2023-07-11T12:46:38.430Z
thanks for editing, do you have parsing functions like parseField() or parseVariable() that you call from e.g. parseMessage()? or do you have a callback that is called on each token, that you pass down to some state machine? can you tell us more about your current strategy and how it makes it difficult to parse comments etc. ?
coredump
CC BY-SA 4.0
2023-07-12T02:45:43.100Z
I have parseField and parseMessage functions. I'm afraid the rest is a little bit specific to Protobuf but basically, I need to record locations of each message and field in the code. These locations are the start and end of each construct in the language. Now, because I'm currently only doing 1 pass, It is hard to know if a comment is leading, trailing or detached. Hope that clarifies a little.
Clément Jean
<blockquote>
<p>However, there many non-trivial cases and I was wondering if there was an already existing algorithm/data structure for this kind of problem.</p>
</blockquote>
<p>Yes there is, but you are absolutely correct that there are a lot of cases to consider and there is no one slam-dunk-obviously-correct algorithm.</p>
<p>Roslyn -- the C# and VB compilers we designed in the early 2010s -- uses &quot;full fidelity parsing&quot; -- that is, every character in the original source code is assigned a unique location in the lex and parse, whether that character is whitespace, comment or program text proper. The reason for this was primarily to facilitate <em>refactoring engines</em> and code formatters. That is, when you highlight the call to Bar and click &quot;create explanatory variable&quot;:</p>
<pre><code>Foo(/* blah is known to be frobby */ Bar(blah), Baz(qux));
</code></pre>
<p>then we would probably like the refactoring tool to produce something like:</p>
<pre><code>var bar = /* blah is known to be frobby */ Bar(blah); 
Foo(bar, Baz(qux));
</code></pre>
<p>And not</p>
<pre><code>var bar = Bar(blah); 
Foo(/* blah is known to be frobby */ bar, Baz(qux));
</code></pre>
<p>And similarly there are situations where you want to know the spacing so as to preserve it or modify it according to rules in your code formatter, or warning pass, or whatever.</p>
<p>The way we did this was: every node in the parse tree knows the exact location in the token stream of the tokens, and every token has three parts: the &quot;leading trivia list&quot;, the token itself, and the &quot;trailing trivia list&quot;. &quot;Trivia&quot; is comments, spaces, tabs, newlines and so on.</p>
<p>Your question then is essentially what algorithm do we use to decide what trivia is &quot;leading&quot; of the <em>next</em> token instead of &quot;trailing&quot; of the <em>previous</em> token, and we just tried a whole bunch of different options until we found one that worked most of the time. If I recall correctly -- and this was over ten years ago so maybe don't trust me on this -- the simple solution we arrived at was trivia usually belongs to the token which follows it, so most trivia is leading trivia. The special case is trivia following the last token on a line is trailing trivia of that token.</p>
<p>That simple approach is likely not sophisticated enough for your use cases.</p>

CC BY-SA 4.0
2023-07-13T07:37:01.883Z
2023-07-13T07:37:01.883Z
Eric Lippert
<p>In your case you may want to add tokens in your lexer for comments and whitespace (e.g. <code>empty-line</code>, <code>block-comment</code>, <code>line-comment</code>) which retains most of the original formatting.</p>
<p>Then if you define a grammar you explicitly say that a <code>field</code> in protobuf is either an <code>actual-field</code> followed possibly by a <code>line-comment</code> (without <code>empty-line</code>) or a list of <code>comment</code> non-terminals followed by an <code>actual-field</code>.</p>
<p>This requires that you explicitly specify all the places where comments can happen, which is different from some possible implementation where the lexer just skips over comment sections.</p>

CC BY-SA 4.0
2023-07-11T07:48:40.127Z
2023-07-11T07:54:07.317Z
2023-07-11T07:54:07.317Z
coredump
CC BY-SA 4.0
2023-07-11T08:41:24.577Z
Forgot to mention that I already have such token for comment and spaces. I'm mostly looking for an algorithm to distinguish between these different comments.
Clément Jean
CC BY-SA 4.0
2023-07-11T09:02:11.630Z
So what is not clear to me now is how you process your tokens, do you write a parser by hand or do you have a parser generator based on a grammar ? Maybe you can edit the question to add more details about that part :)
coredump
<p>Usually, you'd put comment-like tokens in a different category and link them to the adjacent <em>real</em> tokens. In your case, you might also need to add them to a global list so that you can distinguish between consumed comments and ones that have not been consumed. The consumption would happen in the parse rule either by consuming all comments before or after your anchor token. Based on your example, I guess that you will end up with looking in both directions and a complex rule on what to consume based on token kind and begin and end locations.</p>
<p>For input languages of code generators, it might not be correct to treat comments as comments. I have an example from a similar project for a serialization code generator that is also hand-written: <a href="https://github.com/serialization/ogss/blob/master/src/main/scala/ogss/frontend/skill/FileParser.scala" rel="nofollow noreferrer">https://github.com/serialization/ogss/blob/master/src/main/scala/ogss/frontend/skill/FileParser.scala</a></p>

CC BY-SA 4.0
2023-07-12T07:11:12.190Z
2023-07-12T07:11:12.190Z
feldentm
# Preserving Comments in AST
Posted by: username_0 on 2023-07-11
I'm currently working on a protobuf parser and I'm trying to preserve the comments in the AST. However, there many non-trivial cases and I was wondering if there was an already existing algorithm/data structure for this kind of problem.
Here is an example of most of the possible comments:
message Comments {
  int32 foo = 1;  // Comment attached to foo.
  // Comment attached to bar.
  int32 bar = 2;

  string baz = 3;
  // Comment attached to baz.
  // Another line attached to baz.

  // Comment attached to moo.
  //
  // Another line attached to moo.
  double moo = 4;

  // Detached comment for corge. This is not leading or trailing comments
  // to moo or corge because there are blank lines separating it from
  // both.

  // Detached comment for corge paragraph 2.

  string corge = 5;
  /* Block comment attached
   * to corge. */
  /* Block comment attached to
   * grault. */
  int32 grault = 6;

  optional int32 another = 7;
  // attached to funny, not trailing comment for another
  optional int32 funny = 8;

  // ignored detached comments.
}

Note that this is important for my AST to determine leading comments (just before a statement), leading detached comments (look at the comments before corge, they are detached because separated by blank newlines), and trailing comments (just after statements).
Edit
As it was not clear, I want to mention that I'm writing a parser by hand and I also wrote a lexer that provides tokens for comment and spaces.
**Tags:** abstract-syntax-tree comments
> **Comments:**
> **username_1**: thanks for editing, do you have parsing functions like parseField() or parseVariable() that you call from e.g. parseMessage()? or do you have a callback that is called on each token, that you pass down to some state machine? can you tell us more about your current strategy and how it makes it difficult to parse comments etc. ?  
> **username_0**: I have parseField and parseMessage functions. I'm afraid the rest is a little bit specific to Protobuf but basically, I need to record locations of each message and field in the code. These locations are the start and end of each construct in the language. Now, because I'm currently only doing 1 pass, It is hard to know if a comment is leading, trailing or detached. Hope that clarifies a little.  
---
## 3 answers
### Answer by username_2 on 2023-07-13. Score: 12
However, there many non-trivial cases and I was wondering if there was an already existing algorithm/data structure for this kind of problem.

Yes there is, but you are absolutely correct that there are a lot of cases to consider and there is no one slam-dunk-obviously-correct algorithm.
Roslyn -- the C# and VB compilers we designed in the early 2010s -- uses "full fidelity parsing" -- that is, every character in the original source code is assigned a unique location in the lex and parse, whether that character is whitespace, comment or program text proper. The reason for this was primarily to facilitate refactoring engines and code formatters. That is, when you highlight the call to Bar and click "create explanatory variable":
Foo(/* blah is known to be frobby */ Bar(blah), Baz(qux));

then we would probably like the refactoring tool to produce something like:
var bar = /* blah is known to be frobby */ Bar(blah); 
Foo(bar, Baz(qux));

And not
var bar = Bar(blah); 
Foo(/* blah is known to be frobby */ bar, Baz(qux));

And similarly there are situations where you want to know the spacing so as to preserve it or modify it according to rules in your code formatter, or warning pass, or whatever.
The way we did this was: every node in the parse tree knows the exact location in the token stream of the tokens, and every token has three parts: the "leading trivia list", the token itself, and the "trailing trivia list". "Trivia" is comments, spaces, tabs, newlines and so on.
Your question then is essentially what algorithm do we use to decide what trivia is "leading" of the next token instead of "trailing" of the previous token, and we just tried a whole bunch of different options until we found one that worked most of the time. If I recall correctly -- and this was over ten years ago so maybe don't trust me on this -- the simple solution we arrived at was trivia usually belongs to the token which follows it, so most trivia is leading trivia. The special case is trivia following the last token on a line is trailing trivia of that token.
That simple approach is likely not sophisticated enough for your use cases.
---
### Answer by username_1 on 2023-07-11. Score: 4
In your case you may want to add tokens in your lexer for comments and whitespace (e.g. `empty-line`, `block-comment`, `line-comment`) which retains most of the original formatting.

Then if you define a grammar you explicitly say that a `field` in protobuf is either an `actual-field` followed possibly by a `line-comment` (without `empty-line`) or a list of `comment` non-terminals followed by an `actual-field`.

This requires that you explicitly specify all the places where comments can happen, which is different from some possible implementation where the lexer just skips over comment sections.
> **Comments:**
> **username_0** (2023-07-11): Forgot to mention that I already have such token for comment and spaces. I'm mostly looking for an algorithm to distinguish between these different comments.  
> **username_1** (2023-07-11): So what is not clear to me now is how you process your tokens, do you write a parser by hand or do you have a parser generator based on a grammar ? Maybe you can edit the question to add more details about that part :)  
---
### Answer by username_3 on 2023-07-12. Score: 3
Usually, you'd put comment-like tokens in a different category and link them to the adjacent *real* tokens. In your case, you might also need to add them to a global list so that you can distinguish between consumed comments and ones that have not been consumed. The consumption would happen in the parse rule either by consuming all comments before or after your anchor token. Based on your example, I guess that you will end up with looking in both directions and a complex rule on what to consume based on token kind and begin and end locations.

For input languages of code generators, it might not be correct to treat comments as comments. I have an example from a similar project for a serialization code generator that is also hand-written: <https://github.com/serialization/ogss/blob/master/src/main/scala/ogss/frontend/skill/FileParser.scala>
---
