correl.phoenixinquis.net

projects and coding adventures


Project maintained by correl Hosted on GitHub Pages — Theme by mattgraham

Use a different theme when publishing Org files


23 February 2016 emacs · org-mode · themes

I've been using material-theme lately, and I sometimes switch around, but I've found that solarized produces the best exported code block results. To avoid having to remember to switch themes when exporting, I wrote a quick wrapper for org-export to do it for me:

(defun my/with-theme (theme fn &rest args)
  (let ((current-themes custom-enabled-themes))
    (mapcar #'disable-theme custom-enabled-themes)
    (load-theme theme t)
    (let ((result (apply fn args)))
      (mapcar #'disable-theme custom-enabled-themes)
      (mapcar (lambda (theme) (load-theme theme t)) current-themes)
      result)))

(advice-add #'org-export-to-file :around (apply-partially #'my/with-theme 'solarized-dark))
(advice-add #'org-export-to-buffer :around (apply-partially #'my/with-theme 'solarized-dark))

Voilà, no more bizarrely formatted code block exports from whatever theme I might have loaded at the time :)

Drawing Git Graphs with Graphviz and Org-Mode


12 July 2015 emacs · org-mode · git · graphviz

Digging through Derek Feichtinger's org-babel examples (which I came across via irreal.org), I found he had some great examples of displaying git-style graphs using graphviz. I thought it'd be a fun exercise to generate my own graphs based on his graphviz source using elisp, and point it at actual git repos.

Getting Started

I started out with the goal of building a simple graph showing a mainline branch and a topic branch forked from it and eventually merged back in.

Using Derek's example as a template, I described 5 commits on a master branch, plus two on a topic branch.

digraph G {
        rankdir="LR";
        bgcolor="transparent";
        node[width=0.15, height=0.15, shape=point];
        edge[weight=2, arrowhead=none];
        node[group=master];
        1 -> 2 -> 3 -> 4 -> 5;
        node[group=branch];
        2 -> 6 -> 7 -> 4;
}

The resulting image looks like this:

G 1 2 1->2 3 2->3 6 2->6 4 3->4 5 4->5 7 6->7 7->4

Designing the Data Structure

The first thing I needed to do was describe my data structure. Leaning on my experiences reading and working through SICP, I got to work building a constructor function, and several accessors.

I decided to represent each node on a graph with an id, a list of parent ids, and a group which will correspond to the branch on the graph the commit belongs to.

(defun git-graph/make-node (id &optional parents group)
  (list id parents group))

(defun git-graph/node-id (node)
  (nth 0 node))

(defun git-graph/node-parents (node)
  (nth 1 node))

(defun git-graph/node-group (node)
  (nth 2 node))

Converting the structure to Graphviz

Now that I had my data structures sorted out, it was time to step through them and generate the graphviz source that'd give me the nice-looking graphs I was after.

The graph is constructed using the example above as a template. The nodes are defined first, followed by the edges between them.

(defun git-graph/to-graphviz (id nodes)
  (string-join
   (list
    (concat "digraph " id " {")
    "bgcolor=\"transparent\";"
    "rankdir=\"LR\";"
    "node[width=0.15,height=0.15,shape=point,fontsize=8.0];"
    "edge[weight=2,arrowhead=none];"
    (string-join
     (-map #'git-graph/to-graphviz-node nodes)
     "\n")
     (string-join
      (-uniq (-flatten (-map #'git-graph/to-graphviz-edges nodes)))
      "\n")
      "}")
   "\n"))

For the sake of readability, I'll format the output:

(defun git-graph/to-graphviz-pretty (id nodes)
  (with-temp-buffer
    (graphviz-dot-mode)
    (insert (git-graph/to-graphviz id nodes))
    (indent-region (point-min) (point-max))
    (buffer-string)))

Each node is built, setting its group attribute when applicable.

(defun git-graph/to-graphviz-node (node)
  (let ((node-id (git-graph/to-graphviz-node-id
                  (git-graph/node-id node))))
    (concat node-id
            (--if-let (git-graph/node-group node)
                (concat "[group=\"" it "\"]"))
            ";")))

Graphviz node identifiers are quoted to avoid running into issues with spaces or other special characters.

(defun git-graph/to-graphviz-node-id (id)
  (format "\"%s\"" id))

For each node, an edge is built connecting the node to each of its parents.

(defun git-graph/to-graphviz-edges (node)
  (let ((node-id (git-graph/node-id node))
        (parents (git-graph/node-parents node)))
    (-map (lambda (parent)
            (git-graph/to-graphviz-edge node-id parent))
          parents)))

(defun git-graph/to-graphviz-edge (from to)
  (concat
   (git-graph/to-graphviz-node-id to)
   " -> "
   (git-graph/to-graphviz-node-id from)
   ";"))

With that done, the simple graph above could be generated with the following code:

(git-graph/to-graphviz-pretty
 "example"
 (list (git-graph/make-node 1 nil "master")
       (git-graph/make-node 2 '(1) "master")
       (git-graph/make-node 3 '(2) "master")
       (git-graph/make-node 4 '(3 7) "master")
       (git-graph/make-node 5 '(4) "master")
       (git-graph/make-node 6 '(2) "branch")
       (git-graph/make-node 7 '(6) "branch")))

Which generates the following graphviz source:

digraph example {
        bgcolor="transparent";
        rankdir="LR";
        node[width=0.15,height=0.15,shape=point,fontsize=8.0];
        edge[weight=2,arrowhead=none];
        "1"[group="master"];
        "2"[group="master"];
        "3"[group="master"];
        "4"[group="master"];
        "5"[group="master"];
        "6"[group="branch"];
        "7"[group="branch"];
        "1" -> "2";
        "2" -> "3";
        "3" -> "4";
        "7" -> "4";
        "4" -> "5";
        "2" -> "6";
        "6" -> "7";
}

The generated image matches the example exactly:

example 1 2 1->2 3 2->3 6 2->6 4 3->4 5 4->5 7 6->7 7->4

Adding Labels

The next thing my graph needed was a way of labeling nodes. Rather than trying to figure out some way of attaching a separate label to a node, I decided to simply draw a labeled node as a box with text.

digraph G {
        rankdir="LR";
        bgcolor="transparent";
        node[width=0.15, height=0.15, shape=point,fontsize=8.0];
        edge[weight=2, arrowhead=none];
        node[group=main];
        1 -> 2 -> 3 -> 4 -> 5;
        5[shape=box,label=master];
        node[group=branch1];
        2 -> 6 -> 7 -> 4;
        7[shape=box,label=branch];
}
G 1 2 1->2 3 2->3 6 2->6 4 3->4 5 master 4->5 7 branch 6->7 7->4

Updating the Data Structure

I updated my data structure to support an optional label applied to a node. I opted to store it in an associative list alongside the group.

(defun git-graph/make-node (id &optional parents options)
  (list id parents options))

(defun git-graph/node-id (node)
  (nth 0 node))

(defun git-graph/node-parents (node)
  (nth 1 node))

(defun git-graph/node-group (node)
  (cdr (assoc 'group (nth 2 node))))

(defun git-graph/node-label (node)
  (cdr (assoc 'label (nth 2 node))))

Updating the Graphviz node generation

The next step was updating the Graphviz generation functions to handle the new data structure, and set the shape and label attributes of labeled nodes.

(defun git-graph/to-graphviz-node (node)
  (let ((node-id (git-graph/to-graphviz-node-id (git-graph/node-id node))))
    (concat node-id
            (git-graph/to-graphviz-node--attributes node)
            ";")))

(defun git-graph/to-graphviz-node--attributes (node)
  (let ((attributes (git-graph/to-graphviz-node--compute-attributes node)))
    (and attributes
         (concat "["
                 (mapconcat (lambda (pair)
                              (format "%s=\"%s\""
                                      (car pair) (cdr pair)))
                            attributes
                            ", ")
                 "]"))))

(defun git-graph/to-graphviz-node--compute-attributes (node)
  (-filter #'identity
           (append (and (git-graph/node-group node)
                        (list (cons 'group (git-graph/node-group node))))
                   (and (git-graph/node-label node)
                        (list (cons 'shape 'box)
                              (cons 'label (git-graph/node-label node)))))))

I could then label the tips of each branch:

(git-graph/to-graphviz-pretty
 "labeled"
 (list (git-graph/make-node 1 nil '((group . "master")))
       (git-graph/make-node 2 '(1) '((group . "master")))
       (git-graph/make-node 3 '(2) '((group . "master")))
       (git-graph/make-node 4 '(3 7) '((group . "master")))
       (git-graph/make-node 5 '(4) '((group . "master")
                                     (label . "master")))
       (git-graph/make-node 6 '(2) '((group . "branch")))
       (git-graph/make-node 7 '(6) '((group . "branch")
                                     (label . "branch")))))
digraph labeled {
        bgcolor="transparent";
        rankdir="LR";
        node[width=0.15,height=0.15,shape=point,fontsize=8.0];
        edge[weight=2,arrowhead=none];
        "1"[group="master"];
        "2"[group="master"];
        "3"[group="master"];
        "4"[group="master"];
        "5"[group="master", shape="box", label="master"];
        "6"[group="branch"];
        "7"[group="branch", shape="box", label="branch"];
        "1" -> "2";
        "2" -> "3";
        "3" -> "4";
        "7" -> "4";
        "4" -> "5";
        "2" -> "6";
        "6" -> "7";
}
labeled 1 2 1->2 3 2->3 6 2->6 4 3->4 5 master 4->5 7 branch 6->7 7->4

Automatic Grouping Using Leaf Nodes

Manually assigning groups to each node is tedious, and easy to accidentally get wrong. Also, with the goal to graph git repositories, I was going to have to figure out groupings automatically anyway.

To do this, it made sense to traverse the nodes in topological order.

Repeating the example above,

digraph G {
        rankdir="LR";
        bgcolor="transparent";
        node[width=0.15, height=0.15, shape=circle];
        edge[weight=2, arrowhead=none];
        node[group=main];
        1 -> 2 -> 3 -> 4 -> 5;
        node[group=branch1];
        2 -> 6 -> 7 -> 4;
}
G 1 1 2 2 1->2 3 3 2->3 6 6 2->6 4 4 3->4 5 5 4->5 7 7 6->7 7->4

These nodes can be represented (right to left) in topological order as either 5, 4, 3, 7, 6, 2, 1 or 5, 4, 7, 6, 3, 2, 1.

Having no further children, 5 is a leaf node, and can be used as a group. All first parents of 5 can therefore be considered to be in group 5.

7 is a second parent to 4, and so should be used as the group for all of its parents not present in group 5.

(defun git-graph/group-topo (nodelist)
  (reverse
   (car
    (-reduce-from
     (lambda (acc node)
       (let* ((grouped-nodes (car acc))
              (group-stack (cdr acc))
              (node-id (git-graph/node-id node))
              (group-from-stack (--if-let (assoc node-id group-stack)
                                    (cdr it)))
              (group (or group-from-stack node-id))
              (parents (git-graph/node-parents node))
              (first-parent (first parents)))
         (if group-from-stack
             (pop group-stack))
         (if (and first-parent (not (assoc first-parent group-stack)))
             (push (cons first-parent group) group-stack))
         (cons (cons (git-graph/make-node node-id
                                    parents
                                    `((group . ,group)
                                      (label . ,(git-graph/node-label node))))
                     grouped-nodes)
               group-stack)))
     nil
     nodelist))))

While iterating through the node list, I maintained a stack of pairs built from the first parent of the current node, and the current group. To determine the group, the head of the stack is checked to see if it contains a group for the current node id. If it does, that group is used and it is popped off the stack, otherwise the current node id is used.

The following table illustrates how the stack is used to store and assign group relationships as the process iterates through the node list:

Table 1: Progressing through the nodes
Node Parents Group Stack Group
5 (4) (4 . 5) 5
4 (3 7) (3 . 5) 5
3 (2) (2 . 5) 5
7 (6) (6 . 7) (2 . 5) 7
6 (2) (2 . 5) 7
2 (1) (1 . 5) 5
1     5

Graph without automatic grouping

(git-graph/to-graphviz-pretty
 "nogroups"
 (list (git-graph/make-node 5 '(4) '((label . master)))
       (git-graph/make-node 4 '(3 7))
       (git-graph/make-node 3 '(2))
       (git-graph/make-node 7 '(6) '((label . develop)))
       (git-graph/make-node 6 '(2))
       (git-graph/make-node 2 '(1))
       (git-graph/make-node 1 nil)))
digraph nogroups {
        bgcolor="transparent";
        rankdir="LR";
        node[width=0.15,height=0.15,shape=point,fontsize=8.0];
        edge[weight=2,arrowhead=none];
        "5"[shape="box", label="master"];
        "4";
        "3";
        "7"[shape="box", label="develop"];
        "6";
        "2";
        "1";
        "4" -> "5";
        "3" -> "4";
        "7" -> "4";
        "2" -> "3";
        "6" -> "7";
        "2" -> "6";
        "1" -> "2";
}
nogroups 5 master 4 4->5 3 3->4 7 develop 7->4 6 6->7 2 2->3 2->6 1 1->2

Graph with automatic grouping

(git-graph/to-graphviz-pretty
 "autogroups"
 (git-graph/group-topo
  (list (git-graph/make-node 5 '(4) '((label . master)))
        (git-graph/make-node 4 '(3 7))
        (git-graph/make-node 3 '(2))
        (git-graph/make-node 7 '(6) '((label . develop)))
        (git-graph/make-node 6 '(2))
        (git-graph/make-node 2 '(1))
        (git-graph/make-node 1 nil))))
digraph autogroups {
        bgcolor="transparent";
        rankdir="LR";
        node[width=0.15,height=0.15,shape=point,fontsize=8.0];
        edge[weight=2,arrowhead=none];
        "5"[group="5", shape="box", label="master"];
        "4"[group="5"];
        "3"[group="5"];
        "7"[group="7", shape="box", label="develop"];
        "6"[group="7"];
        "2"[group="5"];
        "1"[group="5"];
        "4" -> "5";
        "3" -> "4";
        "7" -> "4";
        "2" -> "3";
        "6" -> "7";
        "2" -> "6";
        "1" -> "2";
}
autogroups 5 master 4 4->5 3 3->4 7 develop 7->4 6 6->7 2 2->3 2->6 1 1->2

Graphing a Git Repository

Satisfied that I had all the necessary tools to start graphing real git repositories, I created an example repository to test against.

Creating a Sample Repository

Using the following script, I created a sample repository to test against. I performed the following actions:

  • Forked a develop branch from master.
  • Forked a feature branch from develop, with two commits.
  • Added another commit to develop.
  • Forked a second feature branch from develop, with two commits.
  • Merged the second feature branch to develop.
  • Merged develop to master and tagged it.
mkdir /tmp/test.git
cd /tmp/test.git
git init
touch README
git add README
git commit -m 'initial'
git commit --allow-empty -m 'first'
git checkout -b develop
git commit --allow-empty -m 'second'
git checkout -b feature-1
git commit --allow-empty -m 'feature 1'
git commit --allow-empty -m 'feature 1 again'
git checkout develop
git commit --allow-empty -m 'third'
git checkout -b feature-2
git commit --allow-empty -m 'feature 2'
git commit --allow-empty -m 'feature 2 again'
git checkout develop
git merge --no-ff feature-2
git checkout master
git merge --no-ff develop
git tag -a 1.0 -m '1.0!'

Generating a Graph From a Git Branch

The first order of business was to have a way to call out to git and return the results:

(defun git-graph/git-execute (repo-url command &rest args)
  (with-temp-buffer
    (shell-command (format "git -C \"%s\" %s"
                           repo-url
                           (string-join (cons command args)
                                        " "))
                   t)
    (buffer-string)))

Next, I needed to get the list of commits for a branch in topological order, with a list of parent commits for each. It turns out git provides exactly that via its rev-list command.

(defun git-graph/git-rev-list (repo-url head)
  (-map (lambda (line) (split-string line))
        (split-string (git-graph/git-execute
                       repo-url
                       "rev-list" "--topo-order" "--parents" head)
                      "\n" t)))

I also wanted to label branch heads wherever possible. To do this, I looked up the revision name from git, discarding it if it was relative to some other named commit.

(defun git-graph/git-label (repo-url rev)
  (let ((name (string-trim
               (git-graph/git-execute repo-url
                                      "name-rev" "--name-only" rev))))
    (unless (s-contains? "~" name)
      name)))

Generating the graph for a single branch was as simple as iterating over each commit and creating a node for it.

(defun git-graph/git-graph-head (repo-url head)
  (git-graph/group-topo
   (-map (lambda (rev-with-parents)
           (let* ((rev (car rev-with-parents))
                  (parents (cdr rev-with-parents))
                  (label (git-graph/git-label repo-url rev)))
             (git-graph/make-node rev parents
                                  `((label . ,label)))))
         (git-graph/git-rev-list repo-url head))))

Here's the result of graphing the master branch:

(git-graph/to-graphviz-pretty
 "git"
 (git-graph/git-graph-head
  "/tmp/test.git"
  "master"))
digraph git {
        bgcolor="transparent";
        rankdir="LR";
        node[width=0.15,height=0.15,shape=point,fontsize=8.0];
        edge[weight=2,arrowhead=none];
        "b705cc1cf18544636e46164174e60645c94f3c28"[group="b705cc1cf18544636e46164174e60645c94f3c28", shape="box", label="master"];
        "c417706bcf893d6c97edfd4557bd9aa380ac79aa"[group="c417706bcf893d6c97edfd4557bd9aa380ac79aa", shape="box", label="develop"];
        "2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0"[group="2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0", shape="box", label="feature-2"];
        "e84b9e97fe99f7c9edddf726c531192288868ded"[group="2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0"];
        "bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6"[group="c417706bcf893d6c97edfd4557bd9aa380ac79aa"];
        "16f6f06916f130bf2fd8c2cd6676c237d8b86e68"[group="c417706bcf893d6c97edfd4557bd9aa380ac79aa"];
        "813c0cce8970964c4f30c1c755a494137f16f120"[group="b705cc1cf18544636e46164174e60645c94f3c28"];
        "02d0748a87816cd252097bb53b7d090db5d177e9"[group="b705cc1cf18544636e46164174e60645c94f3c28"];
        "813c0cce8970964c4f30c1c755a494137f16f120" -> "b705cc1cf18544636e46164174e60645c94f3c28";
        "c417706bcf893d6c97edfd4557bd9aa380ac79aa" -> "b705cc1cf18544636e46164174e60645c94f3c28";
        "bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6" -> "c417706bcf893d6c97edfd4557bd9aa380ac79aa";
        "2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0" -> "c417706bcf893d6c97edfd4557bd9aa380ac79aa";
        "e84b9e97fe99f7c9edddf726c531192288868ded" -> "2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0";
        "bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6" -> "e84b9e97fe99f7c9edddf726c531192288868ded";
        "16f6f06916f130bf2fd8c2cd6676c237d8b86e68" -> "bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6";
        "813c0cce8970964c4f30c1c755a494137f16f120" -> "16f6f06916f130bf2fd8c2cd6676c237d8b86e68";
        "02d0748a87816cd252097bb53b7d090db5d177e9" -> "813c0cce8970964c4f30c1c755a494137f16f120";
}
git b705cc1cf18544636e46164174e60645c94f3c28 master c417706bcf893d6c97edfd4557bd9aa380ac79aa develop c417706bcf893d6c97edfd4557bd9aa380ac79aa->b705cc1cf18544636e46164174e60645c94f3c28 2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0 feature-2 2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0->c417706bcf893d6c97edfd4557bd9aa380ac79aa e84b9e97fe99f7c9edddf726c531192288868ded e84b9e97fe99f7c9edddf726c531192288868ded->2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0 bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6 bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6->c417706bcf893d6c97edfd4557bd9aa380ac79aa bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6->e84b9e97fe99f7c9edddf726c531192288868ded 16f6f06916f130bf2fd8c2cd6676c237d8b86e68 16f6f06916f130bf2fd8c2cd6676c237d8b86e68->bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6 813c0cce8970964c4f30c1c755a494137f16f120 813c0cce8970964c4f30c1c755a494137f16f120->b705cc1cf18544636e46164174e60645c94f3c28 813c0cce8970964c4f30c1c755a494137f16f120->16f6f06916f130bf2fd8c2cd6676c237d8b86e68 02d0748a87816cd252097bb53b7d090db5d177e9 02d0748a87816cd252097bb53b7d090db5d177e9->813c0cce8970964c4f30c1c755a494137f16f120

Graphing Multiple Branches

To graph multiple branches, I needed a function for combining histories. To do so, I simply append any nodes I don't already know about in the first history from the second.

(defun git-graph/+ (a b)
  (append a
          (-remove (lambda (node)
                     (assoc (git-graph/node-id node) a))
                   b)))

From there, all that remained was to accumulate the branch histories and output the complete graph:

(defun git-graph/git-load (repo-url heads)
  (-reduce #'git-graph/+
           (-map (lambda (head)
                   (git-graph/git-graph-head repo-url head))
                 heads)))

And here's the example repository, graphed in full:

(git-graph/to-graphviz-pretty
 "git"
 (git-graph/git-load
  "/tmp/test.git"
  '("master" "feature-1")))
digraph git {
        bgcolor="transparent";
        rankdir="LR";
        node[width=0.15,height=0.15,shape=point,fontsize=8.0];
        edge[weight=2,arrowhead=none];
        "b705cc1cf18544636e46164174e60645c94f3c28"[group="b705cc1cf18544636e46164174e60645c94f3c28", shape="box", label="master"];
        "c417706bcf893d6c97edfd4557bd9aa380ac79aa"[group="c417706bcf893d6c97edfd4557bd9aa380ac79aa", shape="box", label="develop"];
        "2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0"[group="2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0", shape="box", label="feature-2"];
        "e84b9e97fe99f7c9edddf726c531192288868ded"[group="2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0"];
        "bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6"[group="c417706bcf893d6c97edfd4557bd9aa380ac79aa"];
        "16f6f06916f130bf2fd8c2cd6676c237d8b86e68"[group="c417706bcf893d6c97edfd4557bd9aa380ac79aa"];
        "813c0cce8970964c4f30c1c755a494137f16f120"[group="b705cc1cf18544636e46164174e60645c94f3c28"];
        "02d0748a87816cd252097bb53b7d090db5d177e9"[group="b705cc1cf18544636e46164174e60645c94f3c28"];
        "2c3627a9512bafa4b67f36fa9284cc8857b41e57"[group="2c3627a9512bafa4b67f36fa9284cc8857b41e57", shape="box", label="feature-1"];
        "b3b234b4b4396e21c027ea40eef997ed9f38d045"[group="2c3627a9512bafa4b67f36fa9284cc8857b41e57"];
        "813c0cce8970964c4f30c1c755a494137f16f120" -> "b705cc1cf18544636e46164174e60645c94f3c28";
        "c417706bcf893d6c97edfd4557bd9aa380ac79aa" -> "b705cc1cf18544636e46164174e60645c94f3c28";
        "bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6" -> "c417706bcf893d6c97edfd4557bd9aa380ac79aa";
        "2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0" -> "c417706bcf893d6c97edfd4557bd9aa380ac79aa";
        "e84b9e97fe99f7c9edddf726c531192288868ded" -> "2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0";
        "bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6" -> "e84b9e97fe99f7c9edddf726c531192288868ded";
        "16f6f06916f130bf2fd8c2cd6676c237d8b86e68" -> "bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6";
        "813c0cce8970964c4f30c1c755a494137f16f120" -> "16f6f06916f130bf2fd8c2cd6676c237d8b86e68";
        "02d0748a87816cd252097bb53b7d090db5d177e9" -> "813c0cce8970964c4f30c1c755a494137f16f120";
        "b3b234b4b4396e21c027ea40eef997ed9f38d045" -> "2c3627a9512bafa4b67f36fa9284cc8857b41e57";
        "16f6f06916f130bf2fd8c2cd6676c237d8b86e68" -> "b3b234b4b4396e21c027ea40eef997ed9f38d045";
}
git b705cc1cf18544636e46164174e60645c94f3c28 master c417706bcf893d6c97edfd4557bd9aa380ac79aa develop c417706bcf893d6c97edfd4557bd9aa380ac79aa->b705cc1cf18544636e46164174e60645c94f3c28 2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0 feature-2 2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0->c417706bcf893d6c97edfd4557bd9aa380ac79aa e84b9e97fe99f7c9edddf726c531192288868ded e84b9e97fe99f7c9edddf726c531192288868ded->2cfd88c610e0d4fd3be5bcbf4c3586e39256c3d0 bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6 bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6->c417706bcf893d6c97edfd4557bd9aa380ac79aa bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6->e84b9e97fe99f7c9edddf726c531192288868ded 16f6f06916f130bf2fd8c2cd6676c237d8b86e68 16f6f06916f130bf2fd8c2cd6676c237d8b86e68->bd5ca4b50b8b7139ef56298b9d1b73a0e0c16be6 b3b234b4b4396e21c027ea40eef997ed9f38d045 16f6f06916f130bf2fd8c2cd6676c237d8b86e68->b3b234b4b4396e21c027ea40eef997ed9f38d045 813c0cce8970964c4f30c1c755a494137f16f120 813c0cce8970964c4f30c1c755a494137f16f120->b705cc1cf18544636e46164174e60645c94f3c28 813c0cce8970964c4f30c1c755a494137f16f120->16f6f06916f130bf2fd8c2cd6676c237d8b86e68 02d0748a87816cd252097bb53b7d090db5d177e9 02d0748a87816cd252097bb53b7d090db5d177e9->813c0cce8970964c4f30c1c755a494137f16f120 2c3627a9512bafa4b67f36fa9284cc8857b41e57 feature-1 b3b234b4b4396e21c027ea40eef997ed9f38d045->2c3627a9512bafa4b67f36fa9284cc8857b41e57

Things I may add in the future

Limiting Commits to Graph

Running this against repos with any substantial history can make the graph unwieldy. It'd be a good idea to abstract out the commit list fetching, and modify it to support different ways of limiting the history to display.

Ideas would include:

  • Specifying commit ranges
  • Stopping at a common ancestor to all graphed branches (e.g., using git-merge-base).
  • Other git commit limiting options, like searches, showing only merge or non-merge commits, etc.

Collapsing History

Another means of reducing the size of the resulting graph would be to collapse unimportant sections of it. It should be possible to collapse a section of the graph, showing a count of skipped nodes.

The difficult part would be determining what parts aren't worth drawing. Something like this would be handy, though, for concisely graphing the state of multiple ongoing development branches (say, to get a picture of what's been going on since the last release, and what's still incomplete).

digraph G {
        rankdir="LR";
        bgcolor="transparent";
        node[width=0.15,height=0.15,shape=point];
        edge[weight=2,arrowhead=none];
        node[group=main];
        1 -> 2 -> 3 -> 4 -> 5;
        node[group=branch];
        2 -> 6 -> 7 -> 8 -> 9 -> 10 -> 4;
}
G 1 2 1->2 3 2->3 6 2->6 4 3->4 5 4->5 7 6->7 8 7->8 9 8->9 10 9->10 10->4
digraph G {
        rankdir="LR";
        bgcolor="transparent";
        node[width=0.15,height=0.15,shape=point];
        edge[weight=2,arrowhead=none];
        node[group=main];
        1 -> 2 -> 3 -> 4 -> 5;
        node[group=branch];
        2 -> 6;
        6 -> 10[style=dashed,label="+3"];
        10 -> 4;
}
G 1 2 1->2 3 2->3 6 2->6 4 3->4 5 4->5 10 6->10 +3 10->4

Clean up and optimize the code a bit

Some parts of this (particularly, the grouping) are probably pretty inefficient. If this turns out to actually be useful, I may take another crack at it.

Final Code

In case anyone would like to use this code for anything, or maybe just pick it apart and play around with it, all the Emacs Lisp code in this post is collected into a single file below:

;;; git-graph.el --- Generate git-style graphs using graphviz

;; Copyright (c) 2015 Correl Roush <correl@gmail.com>

;;; License:

;; This program is free software; you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation; either version 3, or (at your option)
;; any later version.
;;
;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with GNU Emacs; see the file COPYING.  If not, write to the
;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
;; Boston, MA 02110-1301, USA.

;;; Commentary:

;;; Code:

(require 'dash)

(defun git-graph/make-node (id &optional parents options)
  (list id parents options))

(defun git-graph/node-id (node)
  (nth 0 node))

(defun git-graph/node-parents (node)
  (nth 1 node))

(defun git-graph/node-group (node)
  (cdr (assoc 'group (nth 2 node))))

(defun git-graph/node-label (node)
  (cdr (assoc 'label (nth 2 node))))

(defun git-graph/+ (a b)
  (append a
          (-remove (lambda (node)
                     (assoc (git-graph/node-id node) a))
                   b)))

(defun git-graph/to-graphviz (id nodes)
  (string-join
   (list
    (concat "digraph " id " {")
    "bgcolor=\"transparent\";"
    "rankdir=\"LR\";"
    "node[width=0.15,height=0.15,shape=point,fontsize=8.0];"
    "edge[weight=2,arrowhead=none];"
    (string-join
     (-map #'git-graph/to-graphviz-node nodes)
     "\n")
     (string-join
      (-uniq (-flatten (-map #'git-graph/to-graphviz-edges nodes)))
      "\n")
      "}")
   "\n"))
(defun git-graph/to-graphviz-pretty (id nodes)
  (with-temp-buffer
    (graphviz-dot-mode)
    (insert (git-graph/to-graphviz id nodes))
    (indent-region (point-min) (point-max))
    (buffer-string)))

(defun git-graph/to-graphviz-node-id (id)
  (format "\"%s\"" id))
(defun git-graph/to-graphviz-node (node)
  (let ((node-id (git-graph/to-graphviz-node-id (git-graph/node-id node))))
    (concat node-id
            (git-graph/to-graphviz-node--attributes node)
            ";")))

(defun git-graph/to-graphviz-node--attributes (node)
  (let ((attributes (git-graph/to-graphviz-node--compute-attributes node)))
    (and attributes
         (concat "["
                 (mapconcat (lambda (pair)
                              (format "%s=\"%s\""
                                      (car pair) (cdr pair)))
                            attributes
                            ", ")
                 "]"))))

(defun git-graph/to-graphviz-node--compute-attributes (node)
  (-filter #'identity
           (append (and (git-graph/node-group node)
                        (list (cons 'group (git-graph/node-group node))))
                   (and (git-graph/node-label node)
                        (list (cons 'shape 'box)
                              (cons 'label (git-graph/node-label node)))))))

(defun git-graph/to-graphviz-edges (node)
  (let ((node-id (git-graph/node-id node))
        (parents (git-graph/node-parents node)))
    (-map (lambda (parent)
            (git-graph/to-graphviz-edge node-id parent))
          parents)))

(defun git-graph/to-graphviz-edge (from to)
  (concat
   (git-graph/to-graphviz-node-id to)
   " -> "
   (git-graph/to-graphviz-node-id from)
   ";"))

(defun git-graph/group-topo (nodelist)
  (reverse
   (car
    (-reduce-from
     (lambda (acc node)
       (let* ((grouped-nodes (car acc))
              (group-stack (cdr acc))
              (node-id (git-graph/node-id node))
              (group-from-stack (--if-let (assoc node-id group-stack)
                                    (cdr it)))
              (group (or group-from-stack node-id))
              (parents (git-graph/node-parents node))
              (first-parent (first parents)))
         (if group-from-stack
             (pop group-stack))
         (if (and first-parent (not (assoc first-parent group-stack)))
             (push (cons first-parent group) group-stack))
         (cons (cons (git-graph/make-node node-id
                                    parents
                                    `((group . ,group)
                                      (label . ,(git-graph/node-label node))))
                     grouped-nodes)
               group-stack)))
     nil
     nodelist))))

(defun git-graph/git-execute (repo-url command &rest args)
  (with-temp-buffer
    (shell-command (format "git -C \"%s\" %s"
                           repo-url
                           (string-join (cons command args)
                                        " "))
                   t)
    (buffer-string)))
(defun git-graph/git-rev-list (repo-url head)
  (-map (lambda (line) (split-string line))
        (split-string (git-graph/git-execute
                       repo-url
                       "rev-list" "--topo-order" "--parents" head)
                      "\n" t)))
(defun git-graph/git-label (repo-url rev)
  (let ((name (string-trim
               (git-graph/git-execute repo-url
                                      "name-rev" "--name-only" rev))))
    (unless (s-contains? "~" name)
      name)))
(defun git-graph/git-graph-head (repo-url head)
  (git-graph/group-topo
   (-map (lambda (rev-with-parents)
           (let* ((rev (car rev-with-parents))
                  (parents (cdr rev-with-parents))
                  (label (git-graph/git-label repo-url rev)))
             (git-graph/make-node rev parents
                                  `((label . ,label)))))
         (git-graph/git-rev-list repo-url head))))
(defun git-graph/git-load (repo-url heads)
  (-reduce #'git-graph/+
           (-map (lambda (head)
                   (git-graph/git-graph-head repo-url head))
                 heads)))

(provide 'git-graph)
;;; git-graph.el ends here

Download: git-graph.el

Keeping Files And Configuration In Sync


20 April 2015

I have a few computers I use on a daily basis, and I like to keep the same emacs and shell configuration on all of them, along with my org files and a handful of scripts. Since I'm sure other people have this problem as well, I'll share what I'm doing so anyone can learn from (or criticise) my solutions.

Git for configuration and projects

I'm a software developer, so keeping things in git just makes sense to me. I keep my org files in a privately hosted git repository, and Emacs and Zsh configurations in a public repo on github. My blog is also hosted and published on github as well; I like having it cloned to all my machines so I can work on drafts wherever I may be.

My .zshrc installs oh-my-zsh if it isn't installed already, and sets up my shell theme, path, and some other environmental things.

My Emacs configuration behaves similarly, making use of John Wiegley's excellent use-package tool to ensure all my packages are installed if they're not already there and configured the way I like them.

All I have to do to get running on a new system is to install git, emacs and zsh, clone my repo, symlink the files, and grab a cup of tea while everything installs.

Bittorrent sync for personal settings & books

For personal configuration that doesn't belong in and/or is too sensitive to be in a public repo, I have a folder of dotfiles and things that I sync between my machines using Bittorrent Sync. The dotfiles are arranged into directories by their purpose:

[correlr@reason:~/dotenv]
% tree -a -L 2
.
├── authinfo
│   └── .authinfo.gpg
├── bin
│   └── .bin
├── emacs
│   ├── .bbdb
│   └── .emacs.local.d
├── mail
│   ├── .gnus.el
│   ├── .signature
├── README.org
├── .sync
│   ├── Archive
│   ├── ID
│   ├── IgnoreList
│   └── StreamsList
├── tex
│   └── texmf
├── xmonad
│   └── .xmonad
└── zsh
    └── .zshenv

This folder structure allows my configs to be easily installed using GNU Stow from my dotenv folder:

stow -vvS *

Running that command will, for each file in each of the directories, create a symlink to it in my home folder if there isn't a file or directory with that name there already.

Bittorrent sync also comes in handy for syncing my growing Calibre ebook collection, which outgrew my Dropbox account a while back.

Birthday Puzzle


18 April 2015

This logic puzzle has been floating around the internet lately. When I caught wind of it, I thought it would be a great exercise to tackle using Prolog. I'm not especially good with the language yet, so it added to the challenge a bit, but it was a pretty worthwhile undertaking. When I got stumped, I discovered that mapping out the birthdays into a grid helped me visualize the problem and ultimately solve it, so I've included that with my prolog code so you can see how I arrived at the answer.

The Puzzle

Albert and Bernard have just met Cheryl. “When is your birthday?” Albert asked Cheryl. Cheryl thought for a moment and said, “I won’t tell you, but I’ll give you some clues”. She wrote down a list of ten dates:

  • May 15, May 16, May 19
  • June 17, June 18
  • July 14, July 16
  • August 14, August 15, August 17

“One of these is my birthday,” she said.

Cheryl whispered in Albert’s ear the month, and only the month, of her birthday. To Bernard, she whispered the day, and only the day. “Can you figure it out now?” she asked Albert.

Albert: “I don’t know when your birthday is, but I know Bernard doesn’t know, either.”

Bernard: “I didn’t know originally, but now I do.”

Albert: “Well, now I know, too!”

When is Cheryl’s birthday?

The Solution

The Dates

To start off, i entered each of the possible birthdays as facts:

possible_birthday(may, 15).
possible_birthday(may, 16).
possible_birthday(may, 19).
possible_birthday(june, 17).
possible_birthday(june, 18).
possible_birthday(july, 14).
possible_birthday(july, 16).
possible_birthday(august, 14).
possible_birthday(august, 15).
possible_birthday(august, 17).

And here they are, mapped out in a grid:

  May June July August
14     X X
15 X     X
16 X   X  
17   X   X
18   X    
19 X      

Albert's Statement

I don’t know when your birthday is,…

Albert only knows the month, and the month isn't enough to uniquely identify Cheryl's birthday.

month_is_not_unique(M) :-
    bagof(D, possible_birthday(M, D), Days),
    length(Days, Len),
    Len > 1.

… but I know Bernard doesn’t know, either.

Albert knows that Bernard doesn't know Cheryl's birthday. Therefore, the day alone isn't enough to know Cheryl's birthday, and we can infer that the month of Cheryl's birthday does not include any of the unique dates.

day_is_not_unique(D) :-
    bagof(M, possible_birthday(M, D), Months),
    length(Months, Len),
    Len > 1.

month_has_no_unique_days(M) :-
    forall(possible_birthday(M,D),
           day_is_not_unique(D)).

Based on what Albert knows at this point, let's see how we've reduced the possible dates:

part_one(M,D) :-
    possible_birthday(M,D),
    month_is_not_unique(M),
    month_has_no_unique_days(M),
    day_is_not_unique(D).
Results = [ (july, 14), (july, 16), (august, 14), (august, 15), (august, 17)].

So the unique days (the 18th and 19th) are out, as are the months that contained them (May and June).

  July August
14 X X
15   X
16 X  
17   X

Bernard's Statement

I didn’t know originally, but now I do.

For Bernard to know Cheryl's birthday, the day he knows must be unique within the constraints we have so far.

day_is_unique(Month, Day) :-
    findall(M, part_one(M, Day), [Month]).
part_two(Month, Day) :-
    possible_birthday(Month, Day),
    day_is_unique(Month, Day).
Results = [ (july, 16), (august, 15), (august, 17)].

Both July and August contain the 14th, so that row is out.

  July August
15   X
16 X  
17   X

Albert's Second Statement

Well, now I know, too!

Albert's month must be the remaining unique month:

month_is_not_unique(Month, Day) :-
    findall(D, part_two(Month, D), [Day]).
part_three(Month, Day) :-
    possible_birthday(Month, Day),
    month_is_not_unique(Month, Day).
Results = [ (july, 16)].

August had two possible days, so it's now clear that the only possible unique answer is July 16th.

  July
15  
16 X
17  

Cheryl's Birthday

cheryls_birthday(Month, Day) :-
    part_three(Month, Day).
Month = july,
Day = 16.

So, there we have it. Cheryl's birthday is July 16th!

  July
16 X

Coders at Work


28 January 2015

A few days before leaving work for a week and a half of flying and cruising to escape frigid Pennsylvania, I came across a Joe Armstrong quote during my regularly scheduled slacking off on twitter and Hacker News. I'd come across a couple times before, only this time I noticed it had a source link. This led me to discovering (and shortly thereafter, buying) Peter Seibel's "Coders at Work – Reflections on the Craft of Programming". I loaded it onto my nook, and off I went.

The book is essentially a collection of interviews with a series of highly accomplished software developers. Each of them has their own fascinating insights into the craft and its rich history.

While making my way through the book, I highlighted some excerpts that, for one reason or another, resonated with me. I've organized and elaborated on them below.

Incremental Changes

I've seen young programmers say, "Oh, shit, it doesn't work," and then rewrite it all. Stop. Try to figure out what's going on. Learn how to write things incrementally so that at each stage you could verify it.
– Brad Fitzpatrick

I can remember doing this to myself when I was still relatively new to coding (and even worse, before I discovered source control!). Some subroutine or other would be misbehaving, and rather than picking it apart and figuring out what it was I'd done wrong, I'd just blow it away and attempt to write it fresh. While I might be successful, that likely depended on the issue being some sort of typo or missed logic; if it was broken because I misunderstood something or had a bad plan to begin with, rewriting it would only result in more broken code, sometimes in more or different ways than before. I don't think I've ever rewritten someone else's code without first at least getting a firm understanding of it and what it was trying to accomplish, but even then, breaking down changes piece by piece makes it all the easier to maintain sanity.

I do still sometimes catch myself doing too much at once when building a new feature or fixing a bug. I may have to fix a separate bug that's in my way, or I may have to make several different changes in various parts of the code. If I'm not careful, things can get out of hand pretty quickly, and before I know it I have a blob of changes strewn across the codebase in my working directory without a clear picture of what's what. If something goes wrong, it can be pretty tough to sort out which change broke things (or fixed them). Committing changes often helps tremendously to avoid this sort of situation, and when I catch myself going off the rails I try to find a stopping point and split changes up into commits as soon as possible to regain control. Related changes and fixes can always be squashed together afterwards to keep things tidy.

Specifications & Documentation

Many customers won't tell you a problem; they'll tell you a solution. A customer might say, for instance, "I need you to add support for the following 17 attributes to this system. Then you have to ask, 'Why? What are you going to do with the system? How do you expect it to evolve?'" And so on. You go back and forth until you figure out what all the customer really needs the software to do. These are the use cases.
– Joshua Bloch

Whether your customer is your customer, or your CEO, the point stands: customers are really bad at expressing what they want. It's hard to blame them, though; analyzing what you really want and distilling it into a clear specification is tough work. If your customer is your boss, it can be intimidating to push back with questions like "Why?", but if you can get those questions answered you'll end up with a better product, a better understanding of the product, and a happy customer. The agile process of doing quick iterations to get tangible results in front of them is a great way of getting the feedback and answers you need.

The code shows me what it does. It doesn't show me what it's supposed to do. I think the code is the answer to a problem. If you don't have the spec or you don't have any documentation, you have to guess what the problem is from the answer. You might guess wrong.
– Joe Armstrong

Once you've got the definition of what you've got to build and how it's got to work, it's extremely important that you get it documented. Too often, I'm faced with code that's doing something in some way that somebody, either a customer or a developer reading it, takes issue with, and there's no documentation anywhere on why it's doing what it's doing. What happens next is anybody's guess. Code that's clear and conveys its intent is a good start towards avoiding this sort of situation. Comments explaining intent help too, though making sure they're kept up to date with the code can be challenging. At the very least, I try to promote useful commit messages explaining what the purpose of a change is, and reference a ticket in our issue tracker which (hopefully) has a clear accounting of the feature or bugfix that prompted it.

Pair Programming

if you don't know what you're doing then I think it can be very helpful with someone who also doesn't know what they're doing. If you have one programmer who's better than the other one, then there's probably benefit for the weaker programmer or the less-experienced programmer to observe the other one. They're going to learn something from that. But if the gap's too great then they won't learn, they'll just sit there feeling stupid.
– Joe Armstrong

Pairing isn't something I do much. At least, it's pretty rare that I have someone sitting next to me as I code. I do involve peers while I'm figuring out what I want to build as often as I can. The tougher the problem, the more important it is, I think, to get as much feedback and brainstorming in as possible. This way, everybody gets to tackle the problem and learn together, and anyone's input, however small it might seem, can be the key to the "a-ha" moment to figuring out a solution.

Peer Review

I think an hour of code reading is worth two weeks of QA. It's just a really effective way of removing errors. If you have someone who is strong reading, then the novices around them are going to learn a lot that they wouldn't be learning otherwise, and if you have a novice reading, he's going to get a lot of really good advice.
– Douglas Crockford

Just as important as designing the software as a team, I think, is reviewing it as a team. In doing so, each member of the team has an opportunity to understand how the system has been implemented, and to offer their suggestions and constructive criticisms. This helps the team grow together, and results in a higher quality of code overall. This benefits QA as well as the developers themselves for the next time they find themselves in that particular bit of the system.

Object-Oriented Programming

I think the lack of reusability comes in object-oriented languages, not in functional languages. Because the problem with object-oriented languages is they've got all this implicit environment that they carry around with them. You wanted a banana but what you got was a gorilla holding the banana and the entire jungle.
– Joe Armstrong

A lot has been written on why OOP isn't the great thing it claims to be, or was ever intended to be. Having grappled with it myself for years, attempting to find ways to keep my code clean, concise and extensible, I've more or less come to the same conclusion as Armstrong in that coupling data structures with behaviour makes for a terrible mess. Dividing the two led to a sort of moment of clarity; there was no more confusion about what methods belong on what object. There was simply the data, and the methods that act on it. I am still struggling a bit, though, on how to bring this mindset to the PHP I maintain at work. The language seems particularly ill-suited to managing complex data structures (or even simple ones – vectors and hashes are bizarrely intertwined).

Writing

You should read [Elements of Style] for two reasons: The first is that a large part of every software engineer's job is writing prose. If you can't write precise, coherent, readable specs, nobody is going to be able to use your stuff. So anything that improves your prose style is good. The second reason is that most of the ideas in that book are also applicable to programs.
– Joshua Bloch

My advice to everybody is pretty much the same, to read and write.

Are you a good Java programmer, a good C programmer, or whatever? I don't care. I just want to know that you know how to put an algorithm together, you understand data structures, and you know how to document it.
– Douglas Crockford

This is what literate programming is so great for --
I can talk to myself. I can read my program a year later and know exactly what I was thinking.
– Donald Knuth

The more I've program professionally, the clearer it is that writing (and communication in general) is a very important skill to develop. Whether it be writing documentation, putting together a project plan, or whiteboarding and discussing something, clear and concise communication skills are a must. Clarity in writing translates into clarity in coding as well, in my opinion. Code that is short, to the point, clear in its intention, making good use of structure and wording (in the form of function and variable names) is far easier to read and reason about than code that is disorganized and obtuse.

Knuth

I tried to make familiarity with Knuth a hiring criteria, and I was disappointed that I couldn't find enough people that had read him. In my view, anybody who calls himself a professional programmer should have read Knuth's books or at least should have copies of his books.
– Douglas Crockford

… Knuth is really good at telling a story about code. When you read your way through The Art of Computer Programming and you read your way through an algorithm, he's explained it to you and showed you some applications and given you some exercises to work, and you feel like you've been led on a worthwhile journey.
– Guy Steele

At one point I had [The Art of Computer Programming] as my monitor stand because it was one of the biggest set of books I had, and it was just the right height. That was nice because it was always there, and I guess then I was more prone to use it as a reference because it was right in front of me.
– Peter Norvig

I haven't read any of Knuth's books yet, which is something I'll have to rectify soon. I don't think I have the mathematical background necessary to get through some of his stuff, but I expect it will be rewarding nonetheless. I'm also intrigued by his concept of literate programming, and I'm curious to learn more about TeX. I imagine I'll be skimming through TeX: The Program pretty soon now that I've finished Coders at Work :)