Do not return `nil` zipper

[mrkam2]

Problem/Opportunity
Movement functions return nil upon reaching the end of the movement. This possibility requires to always break the flow of manipulations with checks since for code that makes changes it is impossible to keep the accumulated changes.

Proposed Solution
Instead of returning nil, we could introduce a concept of a zipper that doesn't have a current node, but still has a current position, i. e. it is still within a given form (i. e. parents are the same) and there are still siblings to the left and/or to the right. Only the current node portion of zipper is nil, but everything else isn't. So a zipper may point at location between nodes, or before the first node, or after the last node. It also keeps all the accumulated changes. Many functions have a natural way of operation in such situation. For example, most navigation functions should work just fine. find functions should work, and so on.

It may even be possible to simplify the API for other things. For example, remove function may keep the position in tact - removal of a node means that returned zipper is pointing between the nodes and it is up to user to choose where to go from there. Insert node function could simply insert node in the current position.

Similarly, left and right functions would be stopping upon reaching the position before the first and after the last element.

Alternative Solutions
Current API, as an alternative, is prone to return nil, loosing all the accumulated results. For example, if you're iterating nodes in a form, when you reaching its end, you're loosing all the data since zipper is now nil. A simple iteration over siblings would be to go right until you run out of nodes and then go up or go next without loosing any changes, nor the ability to move around. In the current API, a developer has to always keep reference to the previous zipper before performing any movement to not loose the data a zipper has and this makes the resulting code harder to reason about.

[lread]

Thanks for your continued interest in rewrite-clj @mrkam2. It does get quiet around here sometimes. It is nice to see some activity!

I'd have to take some time to digest your idea, but remember that any changes we entertain would also have to preserve the existing behavior to avoid breaking rewrite-clj for our many existing users.

Note also that the zip API is based on clojure.zip; as such, folks expect it to behave like clojure.zip.

[mrkam2]

Good points, we can preserve all of the existing behavior and introduce new one in a new functions. Maybe next+, remove+, etc. With regards to clojure.zip, it looks like our API doesn't provide a bunch of functions that exist there: path, lefts, right, seq-zip and such. From this point of view our API is already divergent enough.

remove function is very hard to use in the current API but I just realized that if I do not care about spacing, I can instead replace a node that I want to remove with a single space node. I stoped caring about spacing because in the current API it is very hard to maintain it. Instead, I apply cljfmt to the result and save a lot of development time.

[lread]

With regards to clojure.zip, it looks like our API doesn't provide a bunch of functions that exist there: path, lefts, right, seq-zip and such. From this point of view our API is already divergent enough.

It is not all that obvious and not necessarily recommended, but you can use clojure.zip's path, lefts, etc., on a rewrite-clj. zip-created zipper.

Example REPL session:

(require '[rewrite-clj.zip :as z]
         '[clojure.zip :as cz])

(def zloc (z/of-string "[1 [2 [3]] 4]"))

(-> zloc z/down z/right z/right cz/lefts)
;; => ({:value 1, :string-value "1"}
;;     {:whitespace " "}
;;     {:tag :vector,
;;      :format-string "[%s]",
;;      :wrap-length 2,
;;      :seq-fn #function[clojure.core/vec],
;;      :children
;;      ({:value 2, :string-value "2"}
;;       {:whitespace " "}
;;       {:tag :vector,
;;        :format-string "[%s]",
;;        :wrap-length 2,
;;        :seq-fn #function[clojure.core/vec],
;;        :children ({:value 3, :string-value "3"})})}
;;     {:whitespace " "})

Note that this will not work with a :track-position? true zipper which is not compatible with the clojure.zip zipper.

remove function is very hard to use in the current API but I just realized that if I do not care about spacing, I can instead replace a node that I want to remove with a single space node. I stoped caring about spacing because in the current API it is very hard to maintain it. Instead, I apply cljfmt to the result and save a lot of development time.

Yes, formatting after changes using cljfmt (or zprint) is something a technique we've recommended to folks in the past.

[lread]

I'm re-reading this issue today and I think it might stem from @mrkam2 using the paredit API.

Using paredit-type operations can be awkward with a zipper because you are not at a row/col position, you are at a node.

Take, for example, [] 3. A zipper's location is a node, and therefore, it can be [] or 3 but not inside [] after [.
This makes slurping 3 into [] slightly non-obvious. Here's the current paredit behaviour:

(require '[rewrite-clj.paredit :as pe]
         '[rewrite-clj.zip :as z])

;; slurping into empty vector, pos is at vector
(-> "[] 3"
    z/of-string   ;; at []
    pe/slurp-forward
    z/root-string)
;; => "[3]"

;; slurping into non-empty vector, pos is inside vector
(-> "[1] 3"
    z/of-string   ;; at [1]
    z/down        ;; at 1
    pe/slurp-forward
    z/root-string)
;; => "[1 3]"

;; effect of slurping into non-empty vector at vector is no-op
(-> "[1] 3"
    z/of-string   ;; at [1]
    pe/slurp-forward
    z/root-string)
;; => "[1] 3"

I'm not sure what to retitle this issue to, but I think the current title proposes a solution rather than captures a problem.

Perhaps we are wondering how to map the units of an editor (row/col) to the units of rewrite-clj (node).

[mrkam2]

I'm not sure it is directly related to the paredit API usage. Paredit API has its own nuances.

Here I'm mostly concerned with how easy it is to run into a situation where in some situations you may produce a nil instead of a zipper and the only option to recover is by "going back in time" which you have to plan ahead of time. Maybe I haven't figured out the best way to use the API so that it is always easy to recover. Do you have a usage pattern that zipper works well with?

[lread]

Thanks for following up @mrkam2!

For me, it is usually about checking the next (whether traveling left, right, up or down) zloc for nil to see if I am at the end of what I am traversing. It feels very similar to traversing a linked list.

Just like a linked list, if the next zloc is nil I'm at the end.

I am sure you are doing much more complicated things so please don't be insulted by a very simplistic example:

(require '[rewrite-clj.zip :as z])

(defn inc-sibs-right [zloc]
  (if-let [next (z/right zloc)]
    (recur (z/edit next inc))
    zloc))

(-> "[1 2 3 4 5 6]"
    z/of-string
    z/down
    inc-sibs-right
    z/root-string)
;; => "[1 3 4 5 6 7]"

Does that help at all?

[mrkam2]

Correct, that's how it could be done. So it can't be simply chained in ->, you need a loop and a recur which require writing custom functions such as inc-sibs-right. I was thinking about a solution that works with more constructs of the Clojure language: iterate, reduce, threading, etc.

I haven't used the library recently, so it is hard for me to come up with a good example now. Here are a few generic utilities I ended up creating to workaround some of the edge cases:

(defn- safe-iterate
  "Creates a lazy sequence using the movement function, stopping upon reaching
  end. Also checks for thread's interrupted state so that endless loops can
be interrupted."
  [f zloc]
  (->> (iterate f zloc)
       (take-while #(if (.isInterrupted (Thread/currentThread))
                      (throw (ex-info "Interrupted" {:zloc %}))
                      (not (z/end? %))))))

(defn zloc-remove
  "Removes the current node selecting the node matching the given traversal
  function."
  [zloc f]
  (let [n (z/node (f zloc))
        z (z/remove zloc)]
    (loop [pr z
           nx z]
      (condp = n
        (z/node pr) pr
        (z/node nx) nx
        (recur (z/prev pr) (z/next z))))))

(defn zloc-remove*
  "Removes the current node selecting the node matching the given traversal
  function."
  [zloc f]
  (let [n (z/node (f zloc))
        z (z/remove* zloc)]
    (loop [pr z
           nx z]
      (condp = n
        (z/node pr) pr
        (z/node nx) nx
        (recur (z/prev* pr) (z/next* z))))))

(defn kill
  "Removes the current node and all of its sibling nodes to the right.
  Selects the next node.
  `[{a b} |2 3 4] -> [{a b}] |`"
  [zloc]
  (let [n (->> zloc (safe-iterate z/right*) count)]
    (->> zloc
         (safe-iterate (comp z/next* z/remove*))
         (drop n)
         first)))

I also had some functionality that marks the current node which I borrowed from LSP library although it felt like there is no guarantee that any custom marker will survive through all the updates of the tree:

(defn- node-marked? [node marker]
  (contains? (get node ::markers) marker))

(defn- zloc-marked? [zloc marker]
  (node-marked? (z/node zloc) marker))

(defn- back-to-mark-or-nil
  [zloc marker]
  (z/find zloc z/prev (fn [loc] (zloc-marked? loc marker))))

(defn- mark-position
  [zloc marker]
  (z/replace zloc (update (z/node zloc) ::markers (fnil conj #{}) marker)))

(defn- unmark-position
  [zloc marker]
  (z/replace zloc (update (z/node zloc) ::markers disj marker)))