Support position on zippers created without position tracking

[mainej]

Problem/Opportunity
Per its docstring, rewrite-clj.zip/position throws if zloc was created without position tracking. Because of this, several other functions can't be used with untracked zippers.

Proposed Solution
In zippers created without position tracking, the nodes have position information in their metadata (:row (meta (z/node zloc))). On untracked zippers, rewrite-clj.zip/position could return that node metadata.

Of course, if a user edits an untracked zipper, the node position metadata can become outdated, a problem that the tracked zippers avoid. So, perhaps edited untracked zippers should throw if position is invoked on their zlocs. Or perhaps there could be configuration for whether this throws, emits a warning, or ignores the danger.

Alternative Solutions
clojure-lsp, a (grateful) consumer of rewrite-clj, has worked around the limitations of position by identifying functions that rely on it, duplicating, and rewriting them to use node metadata. (clojure-lsp doesn't use position tracking for performance reasons.)

A safer but more complicated solution could retroactively "repair" the positions of edited untracked zippers, only after position is called. This would maintain the performance characteristics of untracked zippers until the moment that it's determined that they should have been tracked, at the cost of additional time spent recursively repairing a node and its predecessors.

Action
I'd be willing to be involved to any extent—design, coding and/or maintenance—but with my limited understanding of rewrite-clj and its consumers, I realize that the full breadth of this change could be way beyond my scope of knowledge.

[lread]

Hey, thanks for the thoughtful issue @mainej!
Awesome to get feedback from real-world use!

clojure-lsp doesn't use position tracking for performance reasons.

I've never done any perf testing on position tracking zippers.
I fully assume they'd be slower, but I do wonder by how much.
I'm curious, have you folks done some real testing?

A safer but more complicated solution could retroactively "repair" the positions of edited untracked zippers...

Do you mean automatically upgrading an untracked zipper to a position tracked zipper?
My gut feeling about being automatically helpful is that it can sometimes be more confusing/annoying than helpful. But I am happy to be wrong.

[mainej]

I fully assume they'd be slower, but I do wonder by how much. I'm curious, have you folks done some real testing?

It's a good question, and to the best of my knowledge, the answer is "no." I've been doing a lot of benchmarking in clojure-lsp lately, but haven't tested this specifically. I'd be willing to research a bit, but would have to think about how to frame the question... there are a lot of parameters—zipper size, number and breadth of edits, amount of navigation you expect to do before and after editing, etc.

Do you mean automatically upgrading an untracked zipper to a position tracked zipper?

Either that or leaving it untracked, but fixing metadata by finding the first edited node and working forward from there. I haven't thought through that idea very carefully, and as you said, being automatically helpful isn't always desirable. That's why I prefer the idea of using metadata blindly, or at least until the zipper is edited.

[lread]

This just might give me the kick in the pants to do a performance comparison.
I have been curious for a long time.

I mean, what if we find the position tracking zipper is real zippy (or zippy enough)?

[mainej]

zippy

I see what you did there. :) Yeah, if they have similar performance, all the better. You're probably aware of this already, but for high-level comparison of algorithms, criterium is a handy tool. If you need to dig into which parts of an algorithm are taking the most time, I've been having good luck with clj-async-profiler. See, for example, here.

[lread]

All tips appreciated, much thanks!

[mainej]

This is also probably obvious, but larger files will be more interesting. I've been using analyzer.clj in clj-kondo, but clojure.core is good too.

[lread]

I went hunting a while back for larger sources and found this big puppy.

[mainej]

Uh, yeah. That'll do. Yikes.

[lread]

So, in #172 we've found that the current position tracking zipper is significantly slower than the non-position tracking zipper.

But we must ask ourselves the crux of the problem we are trying to solve for this issue.
Is it that we want an untracked zipper that returns positions where those positions can be stale?
Or is it that we want a position tracking zipper that is fast enough to use with clojure-lsp?

I'm guessing it is the latter. Am I right?

[lread]

Fun historical before-my-time fact: rewrite-clj once used the fast-zip lib.

[mainej]

we want a position tracking zipper that is fast enough to use with clojure-lsp

If we can get that, we'd certainly take it. And if we could always construct tracked zippers, then this issue is moot.

That said, I know of only one place in clojure-lsp where we'd really like the position after editing. Otherwise, we're almost always interested in the position prior to any edits. And for that, node metadata works fine.

So, at least for our case, I think we'd take potentially stale positions over a fully optimized tracked zipper if the former were a lot easier. But, like I said, we're able to work around this easily enough, so if you'd rather pursue fast tracked zippers, that'd be great too.

[lread]

Thanks so much @mainej, that helps!

[mainej]

rewrite-clj once used the fast-zip lib.

That is some deep history!