771339 - Live function editing

Status: NEW

(DevTools :: Debugger, enhancement, P5)

Description

[Jim Blandy :jimb]

Dave Camp suggested a beautiful, obvious-in-retrospect way to get live function code replacement easily and safely, without modifications to the JavaScript engine, and which fails gracefully in the presence of optimizations that lose information (like flat closures or other scope chain reductions).

Let's assume that we can identify the Debugger.Script that corresponds to a particular portion of code, and that we only worry about edits that fall neatly within the function body.

When a function's body is edited, we find the extant script for that body, and set a breakpoint at its start. When the breakpoint is hit, we call Debugger.Frame.prototype.eval on the newly edited source. When that call finishes with some completion value C, we return from the breakpoint handler with C as the resumption value, forcing the call to return immediately with the eval's completion as its own.

This reduces the problem of live-replacing a function's body to the problem of doing eval-in-frame. Any effort we invest in making eval-in-frame yield the right errors in the presence of optimizations will also benefit function body replacement. If we claim that eval-in-frame does not make the engine state unsound, then those claims will cover function body replacement as well.

It will not be as fast, but these edits are always ephemeral anyway, as web pages are designed to be reloaded.

Comment 1

[Panos Astithas (he/him) [:past] (please ni?)]

YES! This is an excellent idea!
I think I could do this right away, even though bug 637572 would be nice to have, in order to avoid messing with the SourceEditor.

Comment 2

[Rob Campbell [:rc] (:robcee)]

awesome.

Comment 3

[Pedro Alves]

This is absolutely amazing!

Comment 4

[Victor Porof [:vporof][:vp]]

Is bug 757254 a dupe?

Comment 6

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: wip

work in progress

Comment 7

[Florent Fayolle]

Very nice idea!

> forcing the call to return immediately with the eval's completion as its own.

How would you do that? Doesn't this bug depend on bug #736733 ?
https://bugzilla.mozilla.org/show_bug.cgi?id=736733

Florent

Comment 8

[Jason Orendorff [:jorendorff]]

No, this doesn't require frame.pop(). You can just return {return: value} from the breakpoint.hit callback.

See https://wiki.mozilla.org/Debugger#Resumption_Values .

Comment 9

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

I'm unassigning myself because I won't be working on this anytime soon.

Comment 10

[J. Ryan Stinnett [:jryans] (Use needinfo, replies may be slow)]

I am interested in this work.  Nick, could you provide a few more clues about how you saw this fitting together?  I see you've attached a tree diff and patch algorithm.  So the core of this would be to use eval-in-frame to call the tree patch algorithm with the diff of the user's edit using the breakpoint "trick" outlined in comment #0?  

Are there further complications you were anticipating?  Trying to get an idea of the difficulty here.

Comment 11

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

(In reply to J. Ryan Stinnett [:jryans] from comment #10)
> I am interested in this work.  Nick, could you provide a few more clues
> about how you saw this fitting together?  I see you've attached a tree diff
> and patch algorithm.  So the core of this would be to use eval-in-frame to
> call the tree patch algorithm with the diff of the user's edit using the
> breakpoint "trick" outlined in comment #0?  
> 
> Are there further complications you were anticipating?  Trying to get an
> idea of the difficulty here.

Note that this is still blocked on bug 905700, which is probably about a quarters worth of work before we really have sources in a place where we have the infrastructure for live editing. I'd estimate at least another quarter to work on this stuff and track down bugs, corner cases we didn't think of, really work out the kinks, etc.

It's still a bit fuzzy, but this was the plan I came up with after bouncing ideas back and forth with Jim:

We have two sources: first, the old source that the VM is currently executing; second, the new source we want the VM to be running. We want to "eval" the new source in the most minimal way possible, preserving as much existing function / object identity as possible so that existing listeners that are already registered just execute new code instead of needing to somehow unregister the old listener and register new listeners and all that.

To do this, we would parse the ASTs of both sources and do a diff comparison to find the minimum set of changes to get from the old ast to the new AST. Let's call these changes C. This diffing would definitely need to be in a worker, could probably throw the parsing in with it.

Then we would need to set a hidden breakpoint on the first offset of every function that has a subnode that is affected by a change in C. When we hit this breakpoint, we would slice the new source so that we have only the source text for the current function. We would do a |let newFunc = new Function(text)| so that we can cache the changes and not repeat work by calling eval every single time. Then we complete the current frame with the results of calling |newFunc|, instead of continuing and executing the old code. Note that we should hide the |newFunc| frame from the client, if possible, since we already have the original function's frame on the stack.

It is a little bit hairy :P

I really want this stuff, too, but right now it is just a matter of priorities. At least we have Cmd+E in the scratchpad in the meantime :)

Comment 12

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

> At least we have Cmd+E in the scratchpad in the meantime :)

http://fitzgeraldnick.com/weblog/52/

Comment 13

[Thaddee Tyl [:espadrine]]

I believe this: <https://github.com/qfox/recompiler> may be relevant, although the approach taken is different from that suggested above.

Also, it holds an issue related to adding new functions to the code, which may be overcome by burning some more neurons.

Comment 14

[Thaddee Tyl [:espadrine]]

TL;DR of qfox' recompiler, with personal design changes (for the better, I believe).
Let's say we have the following code to deal with. Call it the Origin.

    function foo() {
      var infoo = 0;
      function bar() {
        infoo++;
      }
      return bar;
    }

The |bar()| function will be substituted by a wrapping mechanism. We get this
(as a partial step), call it the Hidden Mechanism.

    function foo() {
      var infoo = 0;
      function bar() {eval($ƒ[0][1]||($ƒ[0][1]=
        'infoo++;'
      ))}
      return bar;
    }

The whole contents of |bar()| is replaced by a String containing the most
up-to-date version of the function. The |$ƒ[0]| links a unique identifier,
the 0-indexed order of the current function's declaration in the Origin
(ie, ~ the number of |function| keywords before the targeted function),
to the currently defined code to be executed.

    var $ƒ = [[]];

We can simulate the user's action:

    var fromFoo = foo();
    fromFoo();
    
    // Here, the user edits the function.
    $ƒ[0][1] = 'console.log(infoo);';
    
    fromFoo();  // prints "1".

Every time the user edits code, we parse the New Code, we find the innermost functions
that were edited, we update the corresponding edited code in each revision in |$ƒ|.
The New Code becomes the Origin, a new |$ƒ[1]| is made (in case a newly written function
shifts the indices). Since neither the Origin nor the New Code are ever run, each new Origin
needs to be SourceMapped.

This results in a more accurate recompilation (hidden breakpoints fail to re-adjust their
position when some other part of the code above gets rewritten), at the expense of a
heavy script load time and inaccurate performance, which require file edition to be
"opt-in": there'd be a "start editing" button which would recompile all scripts
by creating the Hidden Mechanism and running it.

Tbh, I'd like to have my cake and eat it too. Since any other option requires a new API call,
(the breakpoint one needs |Debugger.Frame::pop()|), I'd like to see if we can go uphill
and change the code for a function defined at a location in a script, much like we can
set up a breakpoint for a function defined at a location in a script.

Comment 15

[Nicole Fong]

@[e-mail] Who should this be assigned to for the debugger docs?  Can this bug be closed once the debugger doc has been included?

Comment 16

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

This bug can't be closed yet because it hasn't been implemented or landed.

Comment 17

[Axel Kratel]

Needs a user story.

Comment 18

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Attachment: jorendorf's proof of concept

Comment 19

[Nick Fitzgerald [:fitzgen] [⏰PST; UTC-8]]

Note that variables that were not closed over will always be undefined.

Comment 20

[Thaddee Tyl [:espadrine]]

Attachment: [patch] wip

Un-bitrotted version of fitzgen's patch.

Comment 21

[Thaddee Tyl [:espadrine]]

Attachment: [patch] wip

Un-bitrotted version of fitzgen's patch.

Comment 23

[Thaddee Tyl [:espadrine]]

Comment on attachment 8455992 [details] [diff] [review]
[patch] wip

Bug 771339 part 1: Diff-Patch library for trees

diff --git a/toolkit/devtools/Loader.jsm b/toolkit/devtools/Loader.jsm
--- a/toolkit/devtools/Loader.jsm
+++ b/toolkit/devtools/Loader.jsm
@@ -89,6 +89,7 @@ BuiltinProvider.prototype = {
         "devtools": "resource:///modules/devtools",
         "devtools/toolkit": "resource://gre/modules/devtools",
         "devtools/server": "resource://gre/modules/devtools/server",
+        "devtools/diff-patch": "resource://gre/modules/devtools/diff-patch",
         "devtools/toolkit/webconsole": "resource://gre/modules/devtools/toolkit/webconsole",
         "devtools/app-actor-front": "resource://gre/modules/devtools/app-actor-front.js",
         "devtools/styleinspector/css-logic": "resource://gre/modules/devtools/styleinspector/css-logic",
@@ -144,6 +145,7 @@ SrcdirProvider.prototype = {
     let mainURI = this.fileURI(OS.Path.join(devtoolsDir, "main.js"));
     let devtoolsURI = this.fileURI(devtoolsDir);
     let toolkitURI = this.fileURI(toolkitDir);
+    let objectDiffPatchURI = this.fileURI(OS.Path.join(srcdir, "toolkit", "devtools", "object-diff-patch.js"));
     let serverURI = this.fileURI(OS.Path.join(toolkitDir, "server"));
     let webconsoleURI = this.fileURI(OS.Path.join(toolkitDir, "webconsole"));
     let appActorURI = this.fileURI(OS.Path.join(toolkitDir, "apps", "app-actor-front.js"));
@@ -172,6 +174,7 @@ SrcdirProvider.prototype = {
         "devtools/toolkit": toolkitURI,
         "devtools/server": serverURI,
         "devtools/toolkit/webconsole": webconsoleURI,
+        "devtools/object-diff-patch": objectDiffPatchURI,
         "devtools/app-actor-front": appActorURI,
         "devtools/styleinspector/css-logic": cssLogicURI,
         "devtools/css-color": cssColorURI,
diff --git a/toolkit/devtools/diff-patch/array.js b/toolkit/devtools/diff-patch/array.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/array.js
@@ -0,0 +1,138 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+"use strict";
+
+/**
+ * Diff two arrays.
+ *
+ * @param Array a
+ *        The first array to compare.
+ * @param Array b
+ *        The second array to compare.
+ * @param Function createInsert, createDelete, createUpdate
+ *        A function that creates a list of edits.
+ */
+module.exports = function (a, b, { createInsert, createDelete, createUpdate, cost }) {
+  const m = a.length;
+  const n = b.length;
+  const d = createMatrix(m + 1, n + 1);
+
+  // Fill in the base cases.
+  d[0][0] = theEmptyDiffList;
+  for (let i = 1; i <= m; i++) {
+    // Trivial deletes
+    d[i][0] = diffListNode(createDelete(a[i-1], 0),
+                           d[i-1][0],
+                           cost);
+  }
+  for (let j = 1; j <= n; j++) {
+    // Trivial inserts
+    d[0][j] = diffListNode(createInsert(b[j-1], j-1),
+                           d[0][j-1],
+                           cost);
+  }
+
+  // Use dynamic programming to efficiently find a solution by building upon the
+  // solutions to sub-problems. This is similar to calculating edit distance,
+  // but we keep track of the edits along the way rather than just counting
+  // them.
+  for (let i = 1; i <= m; i++) {
+    for (let j = 1; j <= n; j++) {
+      d[i][j] = min(
+        // Insert item from `b`.
+        diffListNode(createInsert(b[j-1], j-1),
+                     d[i][j-1],
+                     cost),
+        // Delete item in `a`.
+        diffListNode(createDelete(a[i-1], j),
+                     d[i-1][j],
+                     cost),
+        // Change `a[i]` into `b[j]`.
+        diffListNode(createUpdate(a[j-1], b[j-1], j-1),
+                     d[i-1][j-1],
+                     cost)
+      );
+    }
+  }
+
+  // Follow the path back through the matrix and collect aggregate our
+  // differences.
+
+  let reversed = [];
+  for (let node = d[m][n]; node != null; node = node.prev) {
+    if (node.difference !== null) {
+      // `node.difference` is a list of operations in the correct order.
+      reversed = node.difference.concat(reversed);
+    }
+  }
+  return reversed;
+}
+
+// Helpers
+
+/**
+ * Create a persistent, immutable, singly linked list of differences.
+ *
+ * `diffListNode`s have the following properties:
+ *
+ *   - cost: The aggregate length of all changes in and ahead of this node in
+ *             this `diffListNode`.
+ *   - difference: The sub-difference; an array of changes, or a single change.
+ *   - prev: If present, the `diffListNode` preceding this one.
+ *
+ * @param difference
+ *        The difference for this node.
+ * @param prev
+ *        The `diffListNode` that is the preceding this one. Optional.
+ * @returns a `diffListNode`.
+ */
+function diffListNode(difference=null, prev=null, cost=null) {
+  const diffCost = difference ? cost(difference) : 0;
+  return Object.preventExtensions(Object.create(null, {
+    cost: {
+      value: prev ? prev.cost + diffCost : diffCost,
+      configurable: false,
+      writable: false,
+      enumerable: false
+    },
+    difference: {
+      value: difference,
+      configurable: false,
+      writable: false,
+      enumerable: false
+    },
+    prev: {
+      value: prev,
+      configurable: false,
+      writable: false,
+      enumerable: false
+    }
+  }));
+};
+
+const theEmptyDiffList = diffListNode();
+
+/**
+ * Create an m x n matrix.
+ */
+function createMatrix(m, n) {
+  let d = new Array(m);
+  for (let i = 0; i < m; i++) {
+    d[i] = new Array(n);
+  }
+  return d;
+}
+
+/**
+ * Return the diffListNode that has the least cost.
+ */
+function min(minDiff, ...choices) {
+  for (let d of choices) {
+    if (d.cost < minDiff.cost) {
+      minDiff = d;
+    }
+  }
+  return minDiff;
+}
diff --git a/toolkit/devtools/diff-patch/moz.build b/toolkit/devtools/diff-patch/moz.build
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/moz.build
@@ -0,0 +1,12 @@
+# -*- Mode: python; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 40 -*-
+# vim: set filetype=python:
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+XPCSHELL_TESTS_MANIFESTS += ['tests/unit/xpcshell.ini']
+
+EXTRA_JS_MODULES.devtools.patch += [
+    'array.js',
+    'tree.js',
+]
diff --git a/toolkit/devtools/diff-patch/tests/unit/head_diffpatch.js b/toolkit/devtools/diff-patch/tests/unit/head_diffpatch.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/head_diffpatch.js
@@ -0,0 +1,53 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+"use strict";
+const Cc = Components.classes;
+const Ci = Components.interfaces;
+const Cu = Components.utils;
+const Cr = Components.results;
+
+const { devtools } = Cu.import("resource://gre/modules/devtools/Loader.jsm", {});
+const { require } = devtools;
+
+Cu.import("resource://gre/modules/devtools/DevToolsUtils.jsm");
+
+// Register a console listener, so console messages don't just disappear
+// into the ether.
+let errorCount = 0;
+let listener = {
+  observe: function (aMessage) {
+    errorCount++;
+    try {
+      // If we've been given an nsIScriptError, then we can print out
+      // something nicely formatted, for tools like Emacs to pick up.
+      var scriptError = aMessage.QueryInterface(Ci.nsIScriptError);
+      dump(aMessage.sourceName + ":" + aMessage.lineNumber + ": " +
+           scriptErrorFlagsToKind(aMessage.flags) + ": " +
+           aMessage.errorMessage + "\n");
+      var string = aMessage.errorMessage;
+    } catch (x) {
+      // Be a little paranoid with message, as the whole goal here is to lose
+      // no information.
+      try {
+        var string = "" + aMessage.message;
+      } catch (x) {
+        var string = "<error converting error message to string>";
+      }
+    }
+
+    do_throw("head_dbg.js got console message: " + string + "\n");
+  }
+};
+
+let consoleService = Cc["@mozilla.org/consoleservice;1"].getService(Ci.nsIConsoleService);
+consoleService.registerListener(listener);
+
+function equal_paths(a, b) {
+  ok(Array.isArray(a));
+  ok(Array.isArray(b));
+  equal(a.length, b.length);
+  for (let i = 0; i < a.length; i++) {
+    equal(a[i], b[i]);
+  }
+}
diff --git a/toolkit/devtools/diff-patch/tests/unit/test_array-01.js b/toolkit/devtools/diff-patch/tests/unit/test_array-01.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/test_array-01.js
@@ -0,0 +1,124 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test diffing arrays.
+
+const arrayDiff = require("devtools/patch/array");
+
+function diff(a, b) {
+  return arrayDiff(a, b, {
+    createInsert: (val, idx) => {
+      return [{
+        type: "insert",
+        value: val,
+        index: idx
+      }];
+    },
+    createDelete: (val, idx) => {
+      return [{
+        type: "delete",
+        value: val,
+        index: idx
+      }];
+    },
+    createUpdate: (old, new_, idx) => {
+      if (old === new_) {
+        return [];
+      }
+      return [{
+        type: "assign",
+        value: new_,
+        index: idx
+      }];
+    },
+    cost: edit => {
+      switch (edit.type) {
+      case "retain":
+        return 0;
+      case "assign":
+        return 1.5;
+      default:
+        return 1;
+      }
+    }
+  });
+}
+
+function run_test() {
+  testAssignArray();
+  testInsertIntoArray();
+  testAssignInsertArray();
+  testDeleteFromArray();
+  testAssignDeleteArray();
+}
+
+function testAssignArray() {
+  const d = diff([1,2,3], [3,2,1]);
+  const [assign3, assign1] = d;
+
+  equal(assign3.index, 0);
+  equal(assign3.type, "assign");
+  equal(assign3.value, 3);
+
+  equal(assign1.index, 2);
+  equal(assign1.type, "assign");
+  equal(assign1.value, 1);
+}
+
+function testInsertIntoArray() {
+  const d = diff([], [4,5,6]);
+  const [insert4, insert5, insert6] = d;
+
+  equal(insert4.index, 0);
+  equal(insert4.type, "insert");
+  equal(insert4.value, 4);
+
+  equal(insert5.index, 1);
+  equal(insert5.type, "insert");
+  equal(insert5.value, 5);
+
+  equal(insert6.index, 2);
+  equal(insert6.type, "insert");
+  equal(insert6.value, 6);
+}
+
+function testAssignInsertArray() {
+  const d = diff([2], [1,3]);
+  const [assign1, insert3] = d;
+
+  equal(assign1.index, 0);
+  equal(assign1.type, "assign");
+  equal(assign1.value, 1);
+
+  equal(insert3.index, 1);
+  equal(insert3.type, "insert");
+  equal(insert3.value, 3);
+}
+
+function testDeleteFromArray() {
+  const [delete7, delete8, delete9] = diff([7,8,9], []);
+
+  equal(delete7.index, 0);
+  equal(delete7.type, "delete");
+  equal(delete7.value, 7);
+
+  equal(delete8.index, 0);
+  equal(delete7.type, "delete");
+  equal(delete8.value, 8);
+
+  equal(delete9.index, 0);
+  equal(delete7.type, "delete");
+  equal(delete9.value, 9);
+}
+
+function testAssignDeleteArray() {
+  const [assign3, delete1] = diff([2, 1], [3]);
+
+  equal(assign3.index, 0);
+  equal(assign3.type, "assign");
+  equal(assign3.value, 3);
+
+  equal(delete1.index, 1);
+  equal(delete1.type, "delete");
+  equal(delete1.value, 1);
+}
diff --git a/toolkit/devtools/diff-patch/tests/unit/test_treediff-01.js b/toolkit/devtools/diff-patch/tests/unit/test_treediff-01.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/test_treediff-01.js
@@ -0,0 +1,67 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test diffing simple values.
+
+const { diff } = require("devtools/patch/tree");
+
+function run_test() {
+  testNumbers();
+  testStrings();
+  testNull();
+  testUndefined();
+  testNaN();
+  testInfinity();
+}
+
+function testNumbers() {
+  const [{ path, edit }] = diff(10, 5);
+  equal_paths(path, []);
+  equal(edit.assign, 5);
+}
+
+function testStrings() {
+  const [{ path, edit }] = diff("foo", "bar");
+  equal_paths(path, []);
+  equal(edit.assign, "bar");
+}
+
+function testNull() {
+  let [{ path, edit }] = diff(null, 10);
+  equal_paths(path, []);
+  equal(edit.assign, 10);
+
+  ([{ path, edit }] = diff(10, null));
+  equal_paths(path, []);
+  equal(edit.assign, null);
+}
+
+function testUndefined() {
+  let [{ path, edit }] = diff(undefined, 10);
+  equal_paths(path, []);
+  equal(edit.assign, 10);
+
+  ([{ path, edit }] = diff(10, undefined));
+  equal_paths(path, []);
+  equal(edit.assign, undefined);
+}
+
+function testNaN() {
+  let [{ path, edit }] = diff(NaN, 10);
+  equal_paths(path, []);
+  equal(edit.assign, 10);
+
+  ([{ path, edit }] = diff(10, NaN));
+  equal_paths(path, []);
+  ok(Number.isNaN(edit.assign));
+}
+
+function testInfinity() {
+  let [{ path, edit }] = diff(Infinity, 10);
+  equal_paths(path, []);
+  equal(edit.assign, 10);
+
+  ([{ path, edit }] = diff(10, Infinity));
+  equal_paths(path, []);
+  equal(edit.assign, Infinity);
+}
diff --git a/toolkit/devtools/diff-patch/tests/unit/test_treediff-02.js b/toolkit/devtools/diff-patch/tests/unit/test_treediff-02.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/test_treediff-02.js
@@ -0,0 +1,93 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test diffing simple arrays.
+
+const { diff } = require("devtools/patch/tree");
+
+function run_test() {
+  testAssignArray();
+  testInsertIntoArray();
+  testAssignInsertArray();
+  testDeleteFromArray();
+  testDeleteFromNestedArray();
+  testAssignDeleteArray();
+  testAssignSimpleArray();
+}
+
+function testAssignArray() {
+  const d = diff([1,2,3], [3,2,1]);
+  const [assign3, assign1] = d;
+
+  equal_paths(assign3.path, [0]);
+  equal(assign3.edit.assign, 3);
+
+  equal_paths(assign1.path, [2]);
+  equal(assign1.edit.assign, 1);
+}
+
+function testInsertIntoArray() {
+  const d = diff([], [4,5,6]);
+  const [insert4, insert5, insert6] = d;
+
+  equal_paths(insert4.path, [0]);
+  equal(insert4.edit.insert, 4);
+
+  equal_paths(insert5.path, [1]);
+  equal(insert5.edit.insert, 5);
+
+  equal_paths(insert6.path, [2]);
+  equal(insert6.edit.insert, 6);
+}
+
+function testAssignInsertArray() {
+  const d = diff([2], [1,3]);
+  const [assign1, insert3] = d;
+
+  equal_paths(assign1.path, [0]);
+  equal(assign1.edit.assign, 1);
+
+  equal_paths(insert3.path, [1]);
+  equal(insert3.edit.insert, 3);
+}
+
+function testDeleteFromArray() {
+  const [delete7, delete8, delete9] = diff([7,8,9], []);
+
+  equal_paths(delete7.path, [0]);
+  equal(delete7.edit.delete, 7);
+
+  equal_paths(delete8.path, [0]);
+  equal(delete8.edit.delete, 8);
+
+  equal_paths(delete9.path, [0]);
+  equal(delete9.edit.delete, 9);
+}
+
+function testDeleteFromNestedArray() {
+  const [delete8, delete9] = diff([[7,8,9]], [[7]]);
+
+  deepEqual(delete8.path, [0, 1]);
+  equal(delete8.edit.delete, 8);
+
+  deepEqual(delete9.path, [0, 1]);
+  equal(delete9.edit.delete, 9);
+}
+
+function testAssignDeleteArray() {
+  const [assign3, delete1] = diff([2, 1], [3]);
+
+  equal_paths(assign3.path, [0]);
+  equal(assign3.edit.assign, 3);
+
+  equal_paths(delete1.path, [1]);
+  equal(delete1.edit.delete, 1);
+}
+
+function testAssignSimpleArray() {
+  const d = diff(null, [42]);
+  const [assign] = d;
+
+  equal_paths(assign.path, []);
+  deepEqual(assign.edit.assign, [42]);
+}
diff --git a/toolkit/devtools/diff-patch/tests/unit/test_treediff-03.js b/toolkit/devtools/diff-patch/tests/unit/test_treediff-03.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/test_treediff-03.js
@@ -0,0 +1,99 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test diffing simple objects.
+
+const { diff } = require("devtools/patch/tree");
+
+function run_test() {
+  testAddProperties();
+  testRemoveProperties();
+  testAssignProperties();
+  testAssignObject();
+  testDeleteObject();
+  testSameObject();
+}
+
+function testAddProperties() {
+  const d = diff({
+    foo: 10
+  }, {
+    foo: 10,
+    bar: 11,
+    baz: 12
+  });
+  const [addBar, addBaz] = d;
+
+  equal_paths(addBar.path, ["bar"]);
+  equal(addBar.edit.assign, 11);
+
+  equal_paths(addBaz.path, ["baz"]);
+  equal(addBaz.edit.assign, 12);
+}
+
+function testRemoveProperties() {
+  const [delBar, delBaz] = diff({
+    foo: 10,
+    bar: 11,
+    baz: 12
+  }, {
+    foo: 10
+  });
+
+  equal_paths(delBar.path, ["bar"]);
+  equal(delBar.edit.delete, 11);
+
+  equal_paths(delBaz.path, ["baz"]);
+  equal(delBaz.edit.delete, 12);
+}
+
+function testAssignProperties() {
+  const [assignBar] = diff({ bar: 1 }, { bar: 2 });
+  equal_paths(assignBar.path, ["bar"]);
+  equal(assignBar.edit.assign, 2);
+}
+
+function testAssignObject() {
+  const [assignment] = diff(null, { bar: 1 });
+
+  equal_paths(assignment.path, []);
+  deepEqual(assignment.edit.assign, { bar: 1 });
+}
+
+function testReassignObject() {
+  const difference = diff({ delete: { me: 1 } }, null);
+  equal(difference.length, 1);
+  const [assignNull] = difference;
+
+  equal_paths(assignNull.path, []);
+  equal(assignNull.edit.assign, null);
+}
+
+function testDeleteObject() {
+  const difference = diff({ delete: { me: 1 } }, { delete: { notme: 1 } });
+  equal(difference.length, 2);
+  const [deletion, assignment] = difference;
+
+  equal_paths(deletion.path, ["delete", "me"]);
+  equal(deletion.edit.delete, 1);
+
+  equal_paths(assignment.path, ["delete", "notme"]);
+  equal(assignment.edit.assign, 1);
+}
+
+function testPatchDeleteObject() {
+  const difference = diff({ delete: { me: 1 } }, { delete: { notme: 1 } });
+  const result = patch({ delete: { me: 1 } }, difference);
+  deepEqual(result, { delete: { notme: 1 } });
+}
+
+function testSameObject() {
+  let d = diff({}, {});
+  equal(d.length, 0);
+
+  d = diff({ foo: 1 }, { foo: 1 });
+  equal(d.length, 0);
+
+  d = diff({ foo: { bar: 3 }, baz: 2 }, { foo: { bar: 3 }, baz: 2 });
+  equal(d.length, 0);
+}
diff --git a/toolkit/devtools/diff-patch/tests/unit/test_treediff-04.js b/toolkit/devtools/diff-patch/tests/unit/test_treediff-04.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/test_treediff-04.js
@@ -0,0 +1,95 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test patching complex objects.
+
+const { diff, patch } = require("devtools/patch/tree");
+Cu.import("resource://gre/modules/reflect.jsm");
+
+function run_test() {
+  testAssignObjectArray();
+  testNestedArrayShifts();
+  testAssignNestedObject();
+  testDeleteNestedObject();
+  testSmallDifference();
+  testLargeDifference();
+}
+
+function testAssignObjectArray() {
+  const a = patch({ foo: 1 }, [
+    { path: ["foo"], edit: { delete: 1 } },
+    { path: [], edit: { assign: [] } },
+    { path: [0], edit: { insert: 3 } },
+  ]);
+  equal(a.length, 1);
+  equal(a[0], 3);
+}
+
+function testNestedArrayShifts() {
+  const a = patch([], [
+    { "path": [0], "edit": { "insert": {} } },
+    { "path": [0, "foo"], "edit": { "assign": 1 } },
+    { "path": [1], "edit": { "insert": {} } },
+    { "path": [1, "bar"], "edit": { "assign": 2 } },
+  ]);
+  equal(a.length, 2);
+  equal(a[0].foo, 1);
+  equal(a[1].bar, 2);
+}
+
+function testAssignNestedObject() {
+  const o = patch({}, diff({}, { foo: { bar: 1 }, baz: { bang: 2 } }));
+  equal(Object.keys(o).length, 2);
+  equal(o.foo.bar, 1);
+  equal(Object.keys(o.foo).length, 1);
+  equal(o.baz.bang, 2);
+  equal(Object.keys(o.baz).length, 1);
+}
+
+function testDeleteNestedObject() {
+  const difference = diff({ foo: { bar: 1 },
+                            baz: { bang: 2 } },
+                          {});
+  const o = patch({ foo: { bar: 1 },
+                    baz: { bang: 2 } },
+                  difference);
+  equal(o.foo, undefined);
+  equal(o.baz, undefined);
+}
+
+function testSmallDifference() {
+  const foo = Reflect.parse("const a = 10;");
+  const bar = Reflect.parse("const b = 10;");
+
+  const newAst = patch(foo, diff(foo, bar));
+  deepEqual(newAst, bar);
+}
+
+function testLargeDifference() {
+  const origin = Reflect.parse("" + function main() {
+    let a = 10;
+    let b = 3;
+    return a + b;
+    a + b;
+  });
+  const target = Reflect.parse("" + function main() {
+    for (let i = 0; i < 10; i ++) {
+      console.log(i);
+    }
+    console.log(b);
+  });
+
+  const difference = diff(origin, target);
+  const newAst = patch(origin, difference);
+  deepEqual(target, newAst);
+}
+
+const isObject = (obj) => typeof obj === "object" && obj !== null;
+const zip = (a, b) => {
+  let pairs = [];
+  for (let i = 0; i < a.length && i < b.length; i++) {
+    pairs.push([a[i], b[i]]);
+  }
+  return pairs;
+};
+
diff --git a/toolkit/devtools/diff-patch/tests/unit/test_treepatch-01.js b/toolkit/devtools/diff-patch/tests/unit/test_treepatch-01.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/test_treepatch-01.js
@@ -0,0 +1,77 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test diffing complex objects.
+
+const { diff } = require("devtools/patch/tree");
+Cu.import("resource://gre/modules/reflect.jsm");
+
+function run_test() {
+  testEquivalent();
+  testNestedArrayShifts();
+  testAssignObjectArray();
+  testSmallDifference();
+  testLargeDifference();
+}
+
+function testEquivalent() {
+  const foo = Reflect.parse("const a = 10;");
+  const bar = Reflect.parse("const a = 10;");
+  const difference = diff(foo, bar);
+  equal(diff(foo, bar).length, 0);
+}
+
+function testNestedArrayShifts() {
+  const [insert1, assign1, insert2, assign2] = diff([], [{ foo: 1 }, { bar: 2 }]);
+
+  equal_paths(insert1.path, [0]);
+  equal(Object.keys(insert1.edit.insert).length, 0);
+
+  equal_paths(assign1.path, [0, "foo"]);
+  equal(assign1.edit.assign, 1);
+
+  equal_paths(insert2.path, [1]);
+  equal(Object.keys(insert2.edit.insert).length, 0);
+
+  equal_paths(assign2.path, [1, "bar"]);
+  equal(assign2.edit.assign, 2);
+}
+
+function testAssignObjectArray() {
+  const [assign] = diff({ foo: 1 }, [3]);
+
+  equal_paths(assign.path, []);
+  deepEqual(assign.edit.assign, [3]);
+}
+
+function testSmallDifference() {
+  const foo = Reflect.parse("const a = 10;");
+  const bar = Reflect.parse("const b = 10;");
+  const [assignB] = diff(foo, bar);
+  equal_paths(assignB.path, ["body", 0, "declarations", 0, "id", "name"]);
+  equal(assignB.edit.assign, "b");
+}
+
+function testLargeDifference() {
+  const foo = Reflect.parse("" + function main() {
+    let a = 10;
+    let b = 3;
+    return a + b;
+  });
+  const bar = Reflect.parse("" + function main() {
+    for (let i = 0; i < 10; i ++) {
+      console.log(i);
+    }
+  });
+
+  const difference = diff(foo, bar);
+
+  // Just test that we didn't get one big delete and one big insert on the body
+  // of the program.
+  ok(difference.length > 2);
+  ok(difference.every(edit => {
+    return !(edit.path.length === 2
+             && edit.path[0] === "body"
+             && edit.path[1] === 0);
+  }));
+}
diff --git a/toolkit/devtools/diff-patch/tests/unit/test_treepatch-02.js b/toolkit/devtools/diff-patch/tests/unit/test_treepatch-02.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/test_treepatch-02.js
@@ -0,0 +1,50 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test patching simple values.
+
+const { patch } = require("devtools/patch/tree");
+
+function run_test() {
+  testNumbers();
+  testStrings();
+  testNull();
+  testUndefined();
+  testNaN();
+  testInfinity();
+  testNested();
+}
+
+function testNumbers() {
+  equal(5, patch(10, [{ path: [], edit: { assign: 5 } }]));
+}
+
+function testStrings() {
+  equal("bar", patch("foo", [{ path: [], edit: { assign: "bar" } }]));
+}
+
+function testNull() {
+  equal(10, patch(null, [{ path: [], edit: { assign: 10 } }]));
+  equal(null, patch(10, [{ path: [], edit: { assign: null } }]));
+}
+
+function testUndefined() {
+  equal(10, patch(undefined, [{ path: [], edit: { assign: 10 } }]));
+  equal(undefined, patch(10, [{ path: [], edit: { assign: undefined } }]));
+}
+
+function testNaN() {
+  equal(10, patch(NaN, [{ path: [], edit: { assign: 10 } }]));
+  do_check_true(isNaN(patch(10, [{ path: [], edit: { assign: NaN } }])));
+}
+
+function testInfinity() {
+  equal(10, patch(Infinity, [{ path: [], edit: { assign: 10 } }]));
+  equal(Infinity, patch(10, [{ path: [], edit: { assign: Infinity } }]));
+}
+
+function testNested() {
+  const obj = patch({ foo: { bar: 10 } },
+                    [{ path: ["foo", "bar"], edit: { assign: 13 } }]);
+  equal(obj.foo.bar, 13);
+}
diff --git a/toolkit/devtools/diff-patch/tests/unit/test_treepatch-03.js b/toolkit/devtools/diff-patch/tests/unit/test_treepatch-03.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/test_treepatch-03.js
@@ -0,0 +1,86 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test patching simple arrays.
+
+const { patch } = require("devtools/patch/tree");
+
+function run_test() {
+  testAssignArray();
+  testInsertIntoArray();
+  testInsertIntoTwoArrays();
+  testInsertAssignArray();
+  testDeleteFromArray();
+  testAssignDeleteArray();
+  testAssignSimpleArray();
+}
+
+function testAssignArray() {
+  const a = patch([1,2,3], [
+    { path: [0], edit: { assign: 3 } },
+    { path: [2], edit: { assign: 1 } },
+  ]);
+  equal(a.length, 3);
+  equal(a[0], 3);
+  equal(a[1], 2);
+  equal(a[2], 1);
+}
+
+function testInsertIntoArray() {
+  const a = patch([], [
+    { path: [0], edit: { insert: 4 } },
+    { path: [1], edit: { insert: 5 } },
+    { path: [2], edit: { insert: 6 } },
+  ]);
+  equal(a.length, 3);
+  equal(a[0], 4);
+  equal(a[1], 5);
+  equal(a[2], 6);
+}
+
+function testInsertIntoTwoArrays() {
+  const a = patch({ foo: [], bar: [] }, [
+    { path: ["foo", 0], edit: { insert: "uno" } },
+    { path: ["bar", 0], edit: { insert: "dos" } },
+  ]);
+  equal(a.foo.length, 1);
+  equal(a.foo[0], "uno");
+  equal(a.bar.length, 1);
+  equal(a.bar[0], "dos");
+}
+
+function testInsertAssignArray() {
+  const a = patch([2], [
+    { path: [0], edit: { assign: 1 } },
+    { path: [1], edit: { insert: 3 } },
+  ]);
+  equal(a[0], 1);
+  equal(a[1], 3);
+}
+
+function testDeleteFromArray() {
+  const a = patch([7,8,9], [
+    { path: [0], edit: { delete: 7 } },
+    { path: [0], edit: { delete: 8 } },
+    { path: [0], edit: { delete: 9 } },
+  ]);
+  equal(a.length, 0);
+}
+
+function testAssignDeleteArray() {
+  const a = patch([2, 1], [
+    { path: [0], edit: { assign: 3 } },
+    { path: [1], edit: { delete: 1 } },
+  ]);
+  equal(a.length, 1);
+  equal(a[0], 3);
+}
+
+function testAssignSimpleArray() {
+  const a = patch(null, [
+    { path: [], edit: { assign: [] } },
+    { path: [0], edit: { insert: 1 } },
+  ]);
+  equal(a.length, 1);
+  equal(a[0], 1);
+}
diff --git a/toolkit/devtools/diff-patch/tests/unit/test_treepatch-04.js b/toolkit/devtools/diff-patch/tests/unit/test_treepatch-04.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/test_treepatch-04.js
@@ -0,0 +1,64 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// Test patching simple objects.
+
+const { patch } = require("devtools/patch/tree");
+
+function run_test() {
+  testAddProperties();
+  testRemoveProperties();
+  testRemoveObject();
+  testRemoveArray();
+  testAssignProperties();
+  testAssignObject();
+}
+
+function testAddProperties() {
+  const o = patch({ foo: 10 }, [
+    { path: ["bar"], edit: { assign: 11 } },
+    { path: ["baz"], edit: { assign: 12 } },
+  ]);
+  equal(o.foo, 10);
+  equal(o.bar, 11);
+  equal(o.baz, 12);
+}
+
+function testRemoveProperties() {
+  const o = patch({ foo: 10, bar: 11, baz: 12 }, [
+    { path: ["bar"], edit: { delete: 11 }},
+    { path: ["baz"], edit: { delete: 12 }},
+  ]);
+  equal(o.foo, 10);
+  equal(o.bar, undefined);
+  equal(o.baz, undefined);
+}
+
+function testRemoveObject() {
+  const o = patch({ foo: {} }, [
+    { path: ["foo"], edit: { delete: {} }},
+  ]);
+  equal(o.foo, undefined);
+}
+
+function testRemoveArray() {
+  const o = patch({ foo: [] }, [
+    { path: ["foo"], edit: { delete: [] }},
+  ]);
+  equal(o.foo, undefined);
+}
+
+function testAssignProperties() {
+  const o = patch({ bar: 1 }, [
+    { path: ["bar"], edit: { assign: 2 } }
+  ]);
+  equal(o.bar, 2);
+}
+
+function testAssignObject() {
+  const o = patch(null, [
+    { path: [], edit: { assign: {} } },
+    { path: ["bar"], edit: { assign: 1 } }
+  ]);
+  equal(o.bar, 1);
+}
diff --git a/toolkit/devtools/diff-patch/tests/unit/xpcshell.ini b/toolkit/devtools/diff-patch/tests/unit/xpcshell.ini
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tests/unit/xpcshell.ini
@@ -0,0 +1,14 @@
+[DEFAULT]
+head = head_diffpatch.js
+tail =
+
+
+[test_array-01.js]
+[test_treediff-01.js]
+[test_treediff-02.js]
+[test_treediff-03.js]
+[test_treediff-04.js]
+[test_treepatch-01.js]
+[test_treepatch-02.js]
+[test_treepatch-03.js]
+[test_treepatch-04.js]
diff --git a/toolkit/devtools/diff-patch/tree.js b/toolkit/devtools/diff-patch/tree.js
new file mode 100644
--- /dev/null
+++ b/toolkit/devtools/diff-patch/tree.js
@@ -0,0 +1,346 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+"use strict";
+
+// Public API
+
+module.exports = {
+  diff: diff,
+  patch: patch
+};
+
+/**
+ * Return the difference between two JS values `a` and `b` such that patching
+ * `a` with the difference will make it equivalent to `b`.
+ *
+ * A difference is a list of changes. A change has a path and an edit.
+ *
+ * @param {any} a
+ *        The first JS value to compare.
+ * @param {any} b
+ *        The second JS value to compare.
+ * @returns array of { path, edit }
+ */
+function diff(a, b, _path=[]) {
+  if (eq(a, b)) {
+    return [];
+  }
+
+  if (isSimple(a)) {
+    return assignObjectChanges(a, b, _path);
+  }
+
+  const aIsArray = Array.isArray(a);
+  const bIsArray = Array.isArray(b);
+  const bothAreArrays = aIsArray && bIsArray;
+  const oneIsArray = (aIsArray || bIsArray) && !bothAreArrays;
+
+  if (isSimple(b) || oneIsArray) {
+    return assignObjectChanges(a, b, _path);
+  }
+
+  if (bothAreArrays) {
+    return diffArrays(a, b, _path);
+  }
+
+  // Both are objects.
+  return diffObjects(a, b, _path);
+}
+
+/**
+ * Returns `obj` patched with `difference`.
+ *
+ * Note that `obj` might be modified in place.
+ *
+ * @param {any} obj
+ *        The JS value we are applying the difference to.
+ * @param Array difference
+ *        The array of { path, edit } as returned by `diff`.
+ * @returns The patched object.
+ */
+function patch(obj, difference) {
+  if (difference.length === 0) {
+    return obj;
+  }
+
+  const [{ path, edit }] = difference;
+  const lastPath = path[path.length - 1];
+
+  if ("assign" in edit) {
+    obj = assign(obj, path, edit.assign);
+  } else if ("insert" in edit) {
+    if ((lastPath|0) !== lastPath) {
+      throw new Error(
+        "Bad path. Can only insert into arrays with integer indexing, got "
+          + lastPath);
+    }
+    insert(obj, path, edit.insert);
+  } else if ("delete" in edit) {
+    if (!path.length) {
+      throw new Error("Bad path. Must have a path to apply a 'delete' edit.");
+    }
+    if ((lastPath|0) === lastPath) {
+      arrayDelete(obj, path, edit.delete);
+    } else {
+      objectDelete(obj, path, edit.delete);
+    }
+  } else {
+    throw new Error("Unknown edit type: " + uneval(edit));
+  }
+
+  return patch(obj, difference.slice(1));
+}
+
+// Patching helper functions
+
+/**
+ * Check that the simple values a and b are equivalent. Empty objects and empty
+ * arrays are also permitted.
+ */
+function eq(a, b) {
+  if (a === b) {
+    return true;
+  }
+  if (Number.isNaN(a) && Number.isNaN(b)) {
+    return true;
+  }
+  if (isSimple(a) || isSimple(b)) {
+    return false;
+  }
+  if (!(isEmpty(a) && isEmpty(b))) {
+    return false;
+  }
+  const aIsArray = Array.isArray(a);
+  const bIsArray = Array.isArray(b);
+  const bothAreArrays = aIsArray && bIsArray;
+  const oneIsArray = (aIsArray || bIsArray) && !bothAreArrays;
+  return !oneIsArray;
+}
+
+/**
+ * Check that the complex values a and b are equivalent.
+ */
+function deepEq(a, b) {
+  if (a === b) {
+    return true;
+  }
+  if (Number.isNaN(a) && Number.isNaN(b)) {
+    return true;
+  }
+  if (Array.isArray(a) && Array.isArray(b)) {
+    return (a.length === b.length) && (a.every((ae, i) => deepEq(ae, b[i])));
+  }
+  if (typeof a === "object" && typeof b === "object") {
+    var aKeys = Object.keys(a);
+    return (aKeys.length === Object.keys(b).length) &&
+      (aKeys.every((key) => deepEq(a[key], b[key])));
+  }
+  return false;
+}
+
+/**
+ * Assign `value` to the property referenced by `path` starting at `obj`.
+ */
+function assign(obj, path, value) {
+  if (path.length === 0) {
+    return value;
+  }
+  const [prop] = path;
+  if (path.length > 1 && !obj.hasOwnProperty(prop)) {
+    throw new Error("Bad path found when patching object. path = "
+                    + uneval(path)
+                    + ", obj = " + uneval(obj));
+  }
+  obj[prop] = assign(obj[prop], path.slice(1), value);
+  return obj;
+}
+
+/**
+ * Insert `value` to the property referenced by `path` starting at `obj`.
+ */
+function insert(obj, path, value) {
+  const [prop] = path;
+  if (path.length === 1) {
+    if (!Array.isArray(obj)) {
+      throw new Error("Bad path. Can only insert into arrays.");
+    }
+    obj.splice(prop, 0, value);
+    return;
+  }
+  if (!obj.hasOwnProperty(prop)) {
+    throw new Error("Bad path found when patching object.");
+  }
+  insert(obj[prop], path.slice(1), value);
+}
+
+/**
+ * Delete `value` from the array at the property referenced by `path` starting
+ * at `obj`.
+ */
+function arrayDelete(obj, path, value) {
+  const [prop] = path;
+  if (path.length === 1) {
+    if (!Array.isArray(obj)) {
+      throw new Error("Bad path. With integer indexing, can only delete from arrays.");
+    }
+    const valToBeDeleted = obj[prop];
+    if (!deepEq(valToBeDeleted, value)) {
+      throw new Error("Expected to delete " + JSON.stringify(value) + ",\n instead found " + JSON.stringify(valToBeDeleted));
+    }
+    obj.splice(prop, 1);
+    return;
+  }
+  if (!obj.hasOwnProperty(prop)) {
+    throw new Error("Bad path found when patching object.");
+  }
+  arrayDelete(obj[prop], path.slice(1), value);
+}
+
+/**
+ * Delete `value` from the object at the property referenced by `path` starting
+ * at `obj`.
+ */
+function objectDelete(obj, path, value) {
+  const [prop] = path;
+  if (path.length === 1) {
+    const valToBeDeleted = obj[prop];
+    if (!deepEq(valToBeDeleted, value)) {
+      throw new Error("Expected to delete " + JSON.stringify(value) +
+        ",\n instead found " + JSON.stringify(valToBeDeleted));
+    }
+    delete obj[prop];
+    return;
+  }
+  if (!obj.hasOwnProperty(prop)) {
+    throw new Error("Bad path found when patching object.");
+  }
+  objectDelete(obj[prop], path.slice(1), value);
+}
+
+// Diffing helper functions
+
+const isObject = obj => typeof obj === "object" && obj !== null;
+const isSimple = obj => !isObject(obj);
+const propIsntUndef = obj => k => obj[k] !== undefined;
+const definedProperties = obj => Object.keys(obj).filter(propIsntUndef(obj));
+const isEmpty = obj => definedProperties(obj).length === 0;
+const arrayDiff = require("./array");
+
+function diffArrays(a, b, path) {
+  return arrayDiff(a, b, {
+    createInsert: (val, index) =>
+      insertObjectChanges(val, path.concat(index)),
+    createDelete: (val, index) =>
+      deleteObjectChanges(val, path.concat(index)),
+    createUpdate: (old, new_, index) =>
+      diff(old, new_, path.concat(index)),
+    cost: edit => {
+      switch (edit.type) {
+      case "retain":
+        return 0;
+      default:
+        return 1;
+      }
+    }
+  });
+}
+
+/**
+ * Yields [key, value] pairs for objects and arrays.
+ */
+function iterItems(obj) {
+  if (Array.isArray(obj)) {
+    let i = 0;
+    for (let val of obj) {
+      yield [i++, val];
+    }
+  } else if (isObject(obj)) {
+    for (let key of Object.keys(obj)) {
+      yield [key, obj[key]];
+    }
+  } else {
+    throw new Error("Can't iterate over " + obj);
+  }
+}
+
+// Change constructors.
+const changes = {
+  insert: (path, value) =>
+    ({ path: path, edit: { insert: value } }),
+  assign: (path, old, new_) =>
+    ({ path: path, edit: { assign: new_ } }),
+  delete: (path, value) =>
+    ({ path: path, edit: { delete: value } })
+};
+
+function simplestForType(obj) {
+  if (isSimple(obj)) {
+    return obj;
+  }
+  if (Array.isArray(obj)) {
+    return [];
+  }
+  return {};
+}
+
+/**
+ * Return the list of changes that will create and insert the given object.
+ */
+function insertObjectChanges(obj, path) {
+  if (isSimple(obj)) {
+    return [changes.insert(path, obj)];
+  }
+
+  let difference = [changes.insert(path, simplestForType(obj))];
+  for (let [key, value] of iterItems(obj)) {
+    [].push.apply(difference, diff(undefined, value, path.concat(key)));
+  }
+  return difference;
+}
+
+/**
+ * Return the list of changes that will break down and delete the given object.
+ */
+function deleteObjectChanges(obj, path) {
+  return [changes.delete(path, obj)];
+}
+
+/**
+ * Return the list of changes that will assign the given path to the given
+ * object.
+ */
+function assignObjectChanges(old, new_, path) {
+  return [changes.assign(path, old, new_)];
+}
+
+/**
+ * Diff two objects.
+ */
+function diffObjects(a, b, path) {
+  const aProps = new Set(definedProperties(a));
+  const bProps = new Set(definedProperties(b));
+  const difference = [];
+
+  for (let x of aProps) {
+    if (bProps.has(x)) {
+      // Properties of the same name in `a` and `b`, which might need to be
+      // updated.
+      [].push.apply(difference, diff(a[x], b[x], path.concat(x)));
+    } else {
+      // Properties missing from `b` that must be removed from `a`.
+      [].push.apply(difference, deleteObjectChanges(a[x], path.concat(x)));
+    }
+  }
+
+  // Properties found in `b` that must be added to `a`.
+  for (let x of bProps) {
+    if (!aProps.has(x)) {
+      [].push.apply(difference,
+                    assignObjectChanges(undefined, b[x], path.concat(x)));
+    }
+  }
+
+  return difference;
+}
diff --git a/toolkit/devtools/moz.build b/toolkit/devtools/moz.build
--- a/toolkit/devtools/moz.build
+++ b/toolkit/devtools/moz.build
@@ -20,6 +20,7 @@ DIRS += [
     'tern',
     'transport',
     'webconsole',
+    'diff-patch',
 ]
 
 MOCHITEST_CHROME_MANIFESTS += ['tests/mochitest/chrome.ini']
diff --git a/toolkit/devtools/tests/unit/head_devtools.js b/toolkit/devtools/tests/unit/head_devtools.js
--- a/toolkit/devtools/tests/unit/head_devtools.js
+++ b/toolkit/devtools/tests/unit/head_devtools.js
@@ -31,10 +31,6 @@ let listener = {
       }
     }
 
-    // Make sure we exit all nested event loops so that the test can finish.
-    while (DebuggerServer.xpcInspector.eventLoopNestLevel > 0) {
-      DebuggerServer.xpcInspector.exitNestedEventLoop();
-    }
     do_throw("head_dbg.js got console message: " + string + "\n");
   }
 };

Comment 24

[Thaddee Tyl [:espadrine]]

Attachment: [wip] part 1: Diff-Patch library for trees

Comment 25

[Alexandre Poirot [:ochameau]]

ping.

Bug 905700 has been fixed in November 2014. We are now in March 2016.

Are we ready to go?
It it now just matter of actually doing it, or do we have still other dependencies?

Can't wait to have this!

Comment 26

[James Long (:jlongster)]

(In reply to Alexandre Poirot [:ochameau] from comment #25)
> ping.
> 
> Bug 905700 has been fixed in November 2014. We are now in March 2016.
> 
> Are we ready to go?
> It it now just matter of actually doing it, or do we have still other
> dependencies?
> 
> Can't wait to have this!

The solutions outlined in this bug are not going to work as they would totally mess with anything involving locations (breakpoints, etc). The real solution is supported this in SpiderMonkey itself and currently nobody is working on that. There hasn't been a good enough use case yet to justify a high priority. Fixing the debugger UI is much higher priority and is what we are focusing on right now.

Comment 27

[Alexandre Poirot [:ochameau]]

Sure. This priority makes a lot of sense.
As I see contributor around I was wondering if that something we can get some additional hands on.

Is there a spidermonkey bug filled somewhere?

Comment 28

[James Long (:jlongster)]

I don't think there is a SpiderMonkey bug yet (at least I couldn't find one). I've only talked with shu at work weeks and there are a few ideas of how it would work. Haven't filed a bug yet until we have an intention to work on it, but we could file one.

I agree that it would be really cool for newer devs to be able to add "console.log" statements and other things like that. I've been interested in hacking on this to learn more about SpiderMonkey but I'm focusing on the frontend right now. Last time I discussed this with the SpiderMonkey team I think they needed some more use cases to spend any time on it.

Comment 29

[Jens]

@jlongster: I thought this here would be a blocker for Bug 894997 (might be added as "See also" or "Blocks" here imho): That is, being able to edit (not just view) in the devtool's debugger.

Comment 30

[James Long (:jlongster)]

Yep

Comment 31

[Jens]

(In reply to James Long (:jlongster) from comment #28)
> Last time I discussed this with the SpiderMonkey team I
> think they needed some more use cases to spend any time on it.

Bug 1282039 would be (AFIAU this bug here technically) another use case related to live editing. That is, the ability to go/step backwards in the JS Debugger (and rerun possibly changed/edited code)

Comment 32

[James Long (:jlongster)]

(In reply to Jens from comment #31)
> (In reply to James Long (:jlongster) from comment #28)
> > Last time I discussed this with the SpiderMonkey team I
> > think they needed some more use cases to spend any time on it.
> 
> Bug 1282039 would be (AFIAU this bug here technically) another use case
> related to live editing. That is, the ability to go/step backwards in the JS
> Debugger (and rerun possibly changed/edited code)

Live editing would not allow you to step backwards. In fact, you cannot live edit functions at all while the debugger is paused (no editing functions on the stack). This would not only be incredibly difficult, but the UX would be hard to get right too.

Stepping backwards is an unrelated feature with it's own difficulties. I heard someone is experimenting with that in Firefox but it's not clear if that will land.

Comment 33

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to James Long (:jlongster) from comment #32)
> Stepping backwards is an unrelated feature with it's own difficulties. I
> heard someone is experimenting with that in Firefox but it's not clear if
> that will land.

Reverse debugging in the JS debugger (a.k.a rr in the browser) is known as WebReplay [0] and work is being done under bug 1207696.

[0] https://developer.mozilla.org/en-US/docs/Mozilla/Projects/WebReplay