An approach to parsing Org files: a state-machine inside of rg?

[jdtsmith]

Thanks for dropping by r/emacs recently. I wonder if I could indulge you with a day-dream about rg parsing org files (one of our favorite kind of files around there).

The basic org structure is simple:

* top-level
Some text.
** Next level
Lots more interesting text.
*** Low level
You know, text.
** Back to intermediate level
And some content.
* Another top-level
Even more...

It's easy for rg to chew through files like these (which can be 10^5 lines or more) very quickly. But one thing it's missing (and I've tried) is a means to accumulate the containing heading state. E.g. if I searched for the word interesting, I'd love some rg capability that could return me:

* top-level>Next level
L123: Lots more interesting text.
...

or similar. This of course would require some simple state machine living inside of the rg process that can keep track of nested heading state. But I thought, perhaps this is possible via some sort of hidden extension capability or other means?

What's the craz-o-meter reading here?

[meedstrom]

For reference, my "state machine" is a list updated each time it lands upon a new heading. Just a data point showing it works to do things this way.

              ;; CRUMBS is a list that can look like
              ;;    ((3 "Heading" "id1234" ("noexport" "work" "urgent"))
              ;;     (2 "Another heading" "id6532" ("work"))
              ;;     (... ... ... ...))
              ;; if the previous heading looked like
              ;;    *** Heading  :noexport:work:urgent:
              ;;       :PROPERTIES:
              ;;       :ID: id1234
              ;;       :END:
              ;; It lets us track context so we know the outline path to the
              ;; current entry and what tags it should be able to inherit.
              ;; Update the list.
              (cl-loop until (> LEVEL (or (caar CRUMBS) 0))
                       do (pop CRUMBS)
                       finally do
                       (push (list LEVEL TITLE ID HERITABLE-TAGS)
                             CRUMBS))

Another piece of state you might want is the top-level setting #+todo: or #+seq_todo: or #+typ_todo:, which controls whether e.g. TODO and DONE count as todo-keywords, or if the possibilities are something else entirely, like NEXT/WAITING/DEFERRED/...

A thornier issue might be that it's not uncommon to want to your search to skip some areas, like between a #+begin_src org and #+end_src. That would be useful in many kinds of files IMO, not just Org.

@jdtsmith I wonder if you had in mind a more programmatic use, or if nested heading would also be useful for on-the-spot interactive search?

[BurntSushi]

Thanks for the question!

I don't see any obvious way of doing what you want easily with ripgrep. The closest thing ripgrep has to something like this are the --before-context and --after-context flags, but they only accept fixed integer values.

The only structure in files that ripgrep understands is lines. That is partially why it (and other tools, like GNU grep) can be as fast as they are. It is a feature that ripgrep doesn't try to understand anything more, because that winds up making the pre-processing step before searching very expensive. In contrasts, lines are a very lightweight structure that ripgrep can actually mostly "ignore" up-front, and then patch back together later.

[meedstrom]

how about if you cached which lines are under which headings?

so ripgrep finds that line 28001 says "magenta orangutans contrast well with cheetos", then you check what org knows about what is around line 28001.

[meedstrom]

and here I'm thinking org would also actually cache the whole body text under each heading, so you could easily do a second search of the matched bodies only, for where "bacon" is not on the same line.

[jdtsmith]

how about if you cached which lines are under which headings

Good idea. This could work! (If you can keep the cache fresh.) Then ripgrep could be used as-is, as a fast add-on to something which mostly caches headings (with line numbers), tags, deadlines, perhaps properties. Queries of the metadata would proceed from the cache, and full-text queries would use ripgrep and a quick line bracket find. Very interesting...

[meedstrom]

I could fairly easily extend org-node, I think, it has most of that stuff in place.

[meedstrom]

Basically done but let's take the discussion to meedstrom/org-node#86 so as to not spam our host :)