Getting back into Clojure a bit and trying out Datomic as a possible database to transition to using for some projects. Datomic schemas are rather neat, as they are simply data-structures that you commit to the database. However, they can be rather verbose, so I’ve been using a simple preprocessing that uses inline-defined templates in a schema defintion for expansions. This keeps the schema definition with the templates still a simple data structure.

It only supports merging of maps, so cannot be used (as currently implemented) for defining higher level abstractions, but it does give you great flexibility to still override attributes specified by a template, and also to compose multiple templates together.

(defn extract-key [m k]
  (when-let [value (k m)] [(dissoc m k) value]))

(defn expand-entry-id [entry]
  (if (keyword? (:db/id entry))
    (update-in entry [:db/id] d/tempid)
    entry))

(defn expand-schema-entry [entry templates]
  (if (and (map? entry) (:meta/templates entry))
    (let [[entry template-refs] (extract-key entry :meta/templates)]
      (merge (apply merge (map templates template-refs)) entry))
    entry))

(defn preprocess-schema
  ; If passed a set of entries, return a processed set of entries
  ; Otherwise expect a {:schema :templates} map.
  ([schema]
    (if (map? schema)
      (preprocess-schema (:schema schema :templates schema))
      (:schema (preprocess-schema schema {}))))

  ([schema templates]
    (reduce
      (fn [res entry]
        (let [entry (expand-schema-entry entry (:templates res))]
          (if-let [[templ templ-name] (extract-key entry :meta/def-template)]
            (update-in res [:templates] assoc templ-name templ)
            (update-in res [:schema] conj (expand-entry-id entry)))))
      {:schema [] :templates {}}
      schema)))

And a simple example use (note that the :db/id should be just the partition it’s to be installed in, otherwise the reader will expand the id literal prematurely, resulting in duplicates):

[
 {:meta/def-template :string-attr
  :db/id :db.part/db
  :db/valueType :db.type/string
  :db/cardinality :db.cardinality/one
  :db.install/_attribute :db.part/db}

 {:meta/templates [:string-attr]
  :db/ident :user/forename
  :db/doc "The forename of the user."}
]

For the current code, an expanded example, and feedback, please see this gist: gist.github.com/4387703

(Updated 29/12/2012 to remove use of transients and atoms)


If you spot an error and would like to submit a correction, you can view the source for this post on GitHub.

To follow on from the note on redo at the end of The Mighty Undoer, today I’m releasing an alpha version of Commandant which provides higher level management of side-effects. Commandant is more complicated than a simple Undoer (both internally and to implement and use) because of the issues that arise when attempting to provide robust reapplication of side-effects.

Commandant supports the managing of a chain of actions, and undoing and redoing them. To do this, it requires that all commands be defined and registered, an implementation of the Command Pattern. It also supports Transient Commands, which are commands supporting the modification of the action before completion of that action. (As an example, dragging an element in a diagram. As soon as the drag starts you know you want to move the element, but the final position will change many times before finishing into a recordable action.)

The approach of Commandant is that all modifications to a given scope should occur through the Commandant assigned to that scope. The scope could be an individual form, a scene describing a canvas, or a large interactive document. This introduces an initially large overhead of defining the interactions (which will require thinking about how they can be both done and undone), but provides a solid definition of the interactions, which has a number of benefits:

  • Easier to verify how changes are made and applied to the scope.
  • Once basic interactions are defined with the document, higher level interactions can be defined by composition.
  • By having named interactions with your data model, making your documents scriptable by third parties is more straightforward. (You are the first consumer of your own document API.)
  • Can easily serialise the actions on a document, so can support undo/redo saved to a document, providing a history of how a document was built.
  • Can listen to events from the Commandant, allowing e.g. broadcast of changes to the document locally to remote clients (Future Work, straightforward)

For the code and usage documentation, please see the Commandant Repository.


If you spot an error and would like to submit a correction, you can view the source for this post on GitHub.

I’m going to talk about something today that I was introduced to by a friend, which is such a ridiculously simple bit of code that I’m going to feel a little silly writing an entire post about it, but I think it might be worthwhile.

function Undoer() {
  this.actions = [];
}

Undoer.prototype.record = function (fn) {
  this.actions.push(fn);
}

Undoer.prototype.run = function () {
  while (this.actions.length > 0) {
    this.actions.pop()();
  }
}

All it does is hold an array, some functions, and eventually calls them in reverse order. Big deal, right? It’s actually surprisingly powerful and useful with just a couple of additional helper functions, and applied in the right circumstances.

Undoer#onoff

Undoer.prototype.onoff = function (target) {
  var args = Array.prototype.slice.call(arguments, 1);
  target.on.apply(target, args);
  this.record(target.off.bind.apply(target, args));
}

Suddently we have a great tool for managing event subscriptions. To show its use, we can try and use it to simplify a fairly common issue in JavaScript event handling, which is dealing with dragging. In a naive implementation of element drag, you bind mousedown, mousemove, and mouseup to some element that you want to add drag functionality to. We’re also going to add a little bit of utility, such that there’s a shared object passed between drag events. This can be very handy when doing coordinate calculations and moving elements.

(I’m going to assume we have jQuery available for this, but it would work given any event wrapper exposing on/off functions for event binding, and simplifies the demonstration.)

function assignDrag(target, onstart, onmove, onend) {
  var drag_context = {};

  $(target).on('mousedown', function (e) { onstart.call(this, e, drag_context); })
           .on('mousemove', function (e) { onmove.call(this, e, drag_context); })
           .on('mouseup', function (e) { onend.call(this, e, drag_context); });
}

This will work rather well, up until the point you drag near the edge, and your mouse leaves the element before you can move the element underneath. The solution? Lazily adding the mousemove and mouseup handlers to the document on mousedown, and removing them again on mouseup.

function assignDrag(target, onstart, onmove, onend) {
  var doc = $(document),
      drag_context = {};

  $(target).on('mousedown', function (e) {
    onstart.call(this, e, drag_context);
    doc.on('mousemove', bound_move);
    doc.on('mouseup', bound_end);
  });

  function bound_move(e) {
    onmove.call(this, e, drag_context);
  }

  function bound_end(e) {
    onend.call(this, e, drag_context);
    doc.off('mousemove', bound_move);
    doc.off('mouseup', bound_end);
  }
}

Well, it still works, but it’s gained a bit of weight. Conceptually we’re doing something very similar to before, but because of the need for unbinding we have to be a bit more careful with anonymous functions so that we can unbind them later. Would an Undoer help here?

function assignDrag(target, onstart, onmove, onend) {
  var u = new Undoer(),
      doc = $(document),
      drag_context = { undoer: u };

  $(target).on('mousedown', function (e) {
    onstart.call(this, e, drag_context);
    u.onoff(doc, 'mousemove', function (e) {
      onmove.call(this, e, drag_context);
    });
    u.onoff(doc, 'mouseup', function (e) {
      onend.call(this, e, drag_context);
      u.run();
    });
  });
}

With Undoer.onoff managing our subscriptions, we don’t have to worry about naming our trivial functions. As long as we run the undoer we’re guaranteed to remove all the callbacks. We can also pass the undoer along inside the context. This could be useful on a drag if you needed to create auxillary elements when starting the drag and wanted to ensure they were removed when the drag completed. The onstart callback can then setup those elements and ensure they are removed, without having to remember about it in the onend callback.

The undoer could also be run by the onstart/onmove functions if a drag wants to cancel itself. We get the ability to cancel a drag from the inside for free, because we’ve packaged up the cleanup. But what if there are side effects inside the drag, and we don’t want to allow the drag to be cancelled like that? We now have two separate object lifecycles (the drag, and side effects within the drag) and to deal with that neatly, we need another helper.

Undoer#child

Undoer.prototype.child = function () {
  var undoer = new Undoer();
  this.record(undoer.run.bind(undoer));
  return undoer;
}

All this does is create a new undoer, add its run function to our actions, and return the new undoer. Now we can deal with hierarchies.

drag_context = { undoer: u.child() }

With this change, the onstart and onmove (and onend, but that’s probably pointless) functions can safely make actions with side effects and be sure that they’re cleaned up when the drag completes.

This ability to form hierarchies becomes very useful when dealing with MVC style applications, and ensuring that views clean up after themselves even in the presence of nested views or other elements they inject into the page. Each subview can be passed its own undoer which is a child of the parents undoer, and then if the parent view is ever removed, the subviews side effects are guaranteed to be cleared up. This isn’t so much of a gain if your Models and Views lifecycles are tightly coupled, but when you can have long-lived Models and short-lived views, it provides an easy verification that you’re not leaking subscriptions and thwarting the garbage collector.

Helpers are cheap and powerful

Not quite right for your needs? Remember that extending it to add different management options for the actions is just a prototype away. I haven’t created a repository, put a 10 line file up, given it a silly name like ‘Remembrall’ and published it on npm, because the core is so small and it’s best to adapt and extend it to your own needs as they arise. I’m including a couple of examples here of simple extensions for managing other side effects.

Adding/removing a DOM element

Maybe we need to add elements inside of others, as might be the case of plugins which inject into different areas of an application, rather than being neatly contained.

Undoer.prototype.appendChild = function (parent, child) {
  parent.appendChild(child);
  this.record(function () {
    try {
      child.parentNode.removeChild(child);
    } catch (exc) {}
  });
}

Limiting the action queue

If we wanted to display a trail of elements behind our cursor when dragging, we could record those elements with appendChild as defined above, and then call limitActions each time to remove the oldest one, keeping the most recent n. And the trail would be automatically collected when we finished dragging.

Undoer.prototype.limitActions = function (n) {
  while (this.actions.length > n) {
    a.shift()()
  }
}

A note on Metrics

At some point you might want to ensure that your undoers are being called and disposed of correctly, and it’s also rather interesting in large applications to see just how many Views you have flying around the place. To facilitate this, you just have to add a name parameter to the constructor and child helper, and then increment a counter inside the constructor based on the name, and decrement on run. You might need to fiddle with this logic if you call run multiple times on an undoer, of course.

Why not redo?

You may have noticed that the helper methods like onoff actually have enough information to implement basic redo functionality as well, so I thought I’d note why it’s not part of the Undoer. A big reason is because I’ve never found the need for it. Almost always when managing lifecycles and side-effects, you’re just wanting to ensure that everything gets cleaned up in future.

Where I’ve needed redo functionality, it’s inevitably been tied to user input relative to a document, and in that case a centralised manager utilising the Command Pattern is a lot easier to reason about, because the actions you want to step forward/backward become a lot more complicated at the document level, compared with simple subscriptions.


If you spot an error and would like to submit a correction, you can view the source for this post on GitHub.

Starting the blog up again, and moving it to Jekyll in the process so that the blog contents and demonstration code can all be placed on GitHub for inspection, download, and correction. Also fits the processing power the blog is served from (a small Linode instance) better than the rather heavyweight Wordpress.


If you spot an error and would like to submit a correction, you can view the source for this post on GitHub.

Quickdiff (implemented for notepag.es) uses an algorithm for doing a fast difference between two DOM trees. Our assumptions for this algorithm, are that the old and new DOM trees are likely to differ only in a small region. For live previews, this is a very good assumption, as between redraws it is unlikely for parts of the document to change that are far from one another. Our goal here is to decouple the cost of a redraw from the size of the document the update is against. This is particularly useful when there is very expensive post processing done after a DOM is generated, such as image bounds checks, or math rendering.

The algorithm uses two scans over the trees, one iterating forwards over children, and the other iterating backwards. In the diagrams below, the result of the forward scan is indicated in blue, and the result of the backward scan in orange. For purposes of demonstration, I will use a simple DOM containing some divs, spans, and text nodes.

A scan constitutes iterating over nodes and their children of the DOM, for two trees, in lock step. So we first compare the node of each given tree. We then recursively compare the children of each tree against each other until a difference is found, which is returned as the path. For identical trees, the lockstep comparison forwards will return no result, which is taken as the identical case.

Considering a single change in the DOM, then the forward and backwards scans will return identical paths:

single_change

The left scan will compare: div == div, div == div, span == span, a == a, span == span, b != b*. The path it returns will be the offsets of the children to reach this difference, in this case [0, 1, 0] (first div, second span, first text node). Similarly, the backwards scan will return [0, 1, 0] as it counts down the children. These paths are identical, so we have a single node change. If the change were detected higher, for instance, if the second span were a div, then the path would be returned as [0, 1] and that element would be replaced, rather than the text node inside it.

The next case is for there to be multiple changes in differing children:

segment

The first difference found on the forward scan is identical, [0, 1, 0]. However, the backwards scan now finds a different path, [2, 0, 0]. We can use these two paths to find a segment within which any changes must be in. In this case, it is all of the children of the parent node, or the segment [0, 2] with path []. The operation to patch this difference is then to remove the segment of nodes from the original DOM specified, and replace with the nodes specified in the new DOM.

The final case is on insertion (or deletion):

insert

An extra implementation detail is needed to cope with insertions and deletions: the backwards scan returns two paths, to cope with possibly different indices for the same nodes in each tree. For instance, in this example, the “d” text node has path [2, 0, 0] in the original DOM, but path [3, 0, 0] in the second DOM. With this detail, deletions are a straightforward extension of previous methods, as we are simply replacing a found segment in the original DOM, with a smaller segment from the target DOM. Insertions that are accompanied with changes are also handled easily. The case to consider are insertions with no other changes.

For these pure insertions, the difference between our forwards and backwards scan will be a negative segment length. In this case, we need to instead return the parent node instead of a segment, and an index inside its children of where to insert the new DOMs node(s).

This algorithm can very quickly isolate an area of the DOM which has changed. For a sizable document, the scan takes between 1-2 ms (Chrome) to 15ms (IE8). The cost of the scan is infact dwarfed by re-processing even one equation for MathJax, and generating the new DOM in the first place. However, by only doing this partial redraw, refreshing the live preview on chrome dropped from 600-800ms, to 30-40ms, and from 8-10 seconds on IE8, down to 500-600ms. When math is not required to be redrawn, these figures drop down to 10-20ms on Chrome, and 50-60ms on IE8, which allows a much more responsive live preview.

On another note, Notepag.es has been released on github: notepages repo.


If you spot an error and would like to submit a correction, you can view the source for this post on GitHub.