Feature request: preserve source line numbers in AST nodes

[lvh]

Summary

It would be helpful if the parsed AST nodes included source line number information from the original markdown text.

Use case

When building linting tools that check markdown structure (e.g., heading hierarchy validation), error messages are much more useful when they can reference the specific line number:

Line 15: H1 not allowed in blog posts: 'Introduction'

vs just:

H1 not allowed in blog posts: 'Introduction'

Current behavior

The AST nodes only contain content, not source positions:

(require '[nextjournal.markdown :as md])
(md/parse "## Heading\n\nParagraph")
;; => {:content [{:type :heading, :heading-level 2, :content [...], :attrs {...}}
;;               {:type :paragraph, :content [...]}], ...}

Proposed behavior

Include source position information, perhaps as metadata or additional keys:

{:type :heading
 :heading-level 2
 :content [...]
 :attrs {...}
 :source {:line 1 :column 0}}  ;; or similar

Notes

The underlying commonmark-java parser does track source spans (SourceSpans), so this information is available during parsing but currently discarded.

[jackrusher]

+1. This would be a great improvement to the library.

[borkdude]

Seems good to me too.

The underlying commonmark-java parser does track source spans

Hopefully the underlying JS library does too. I can have a look at this in new year if nobody else beats me to it.

[borkdude]

I made a PR here which you could try: #66
It adds locations to every node. Tests fail because of this difference. Before proceeding.

Locations are added with the following function:

(defn node->loc [^Node node]
  (when-let [spans (.getSourceSpans node)]
    (when-not (.isEmpty spans)
      (let [^SourceSpan first-span (first spans)
            ^SourceSpan last-span (last spans)]
        {:line (.getLineIndex first-span)
         :column (.getColumnIndex first-span)
         :end-line (.getLineIndex last-span)
         :end-column (+ (.getColumnIndex last-span) (.getLength last-span))}))))

I have to see if there is a performance difference compared to not doing this. If there isn't a significant difference, I don't see a reason not to add this extra information.

I have yet to see if the CLJS implementation also supports this. If not, should we still add it to the CLJ implementation? I think that would be ok.

@zampino Any objections to the current approach?

[borkdude]

Without source spans:

user=> (do (time (dotimes [i 10000] (md/parse (slurp "README.md")))) nil)
"Elapsed time: 1705.666625 msecs"

With source spans:

user=> (do (time (dotimes [i 10000] (md/parse (slurp "README.md")))) nil)
"Elapsed time: 1917.5215 msecs"

That's a 10% slowdown. Maybe significant enough to make this optional?

[borkdude]

What's pretty nice is the addition of :input-index and :length here so you can use (subs s input-index (+ input-index length)) to get the original string back of the node (and potentially show it or replace it with something else). It starting to look a bit like rewrite-clj this way.

(defn node->loc [^Node node]
  (when-let [spans (.getSourceSpans node)]
    (when-not (.isEmpty spans)
      (let [^SourceSpan first-span (first spans)
            ^SourceSpan last-span (last spans)]
        {:input-index (.getInputIndex first-span)
         :length (apply + (map #(.getLength ^Node %) spans))
         :line (.getLineIndex first-span)
         :column (.getColumnIndex first-span)
         :end-line (.getLineIndex last-span)
         :end-column (+ (.getColumnIndex last-span) (.getLength last-span))}))))

[mk]

For now you merged the location info onto the node, right? Unsure if we should nest it under a :loc key or similar. Might make access slightly less convenient but could make it clearer that it's about location info.

Also wonder about the naming of :input-index and :line, :column, :end-line, :end-column which also indices but don't have that in the name?

[borkdude]

Adding this to a separate entry also crossed my mind. I'd choose for :location.

:input-index is different from the others since it contains the index into the string (which you can e.g. use with (subs s input-dex ...), whereas the others represent the line and column of the document Agreed that this could have a better name... perhaps :offset`

Another option would be to just datafy the source-span and add that. This would be the most unopinionated option. You can calculate everything you need from that yourself (like in the node->loc function).

:source-spans [{:input-index ... :line :column :length}]