Bug 1547084 Part 4 - Switch to a search focused control logic architecture, r=loganfsmyth.
authorBrian Hackett <bhackett1024@gmail.com>
Sun, 12 May 2019 13:17:40 -1000
changeset 474174 ffc633295190897ae09451a56a0b255fff4d0682
parent 474173 4d7ef85fc81f1f3d37098ec0809ca14c62d79ccd
child 474175 fdd4b06edab957c38eebfaed5c80c8f0b6cc9307
push id36023
push userncsoregi@mozilla.com
push dateThu, 16 May 2019 21:56:43 +0000
treeherdermozilla-central@786f094a30ae [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersloganfsmyth
bugs1547084
milestone68.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1547084 Part 4 - Switch to a search focused control logic architecture, r=loganfsmyth.
devtools/server/actors/replay/control.js
devtools/server/actors/replay/debugger.js
devtools/server/actors/replay/replay.js
devtools/server/actors/replay/rrIControl.idl
devtools/server/actors/replay/rrIReplay.idl
devtools/shared/execution-point-utils.js
devtools/shared/moz.build
--- a/devtools/server/actors/replay/control.js
+++ b/devtools/server/actors/replay/control.js
@@ -1,1127 +1,1292 @@
 /* -*- indent-tabs-mode: nil; js-indent-level: 2; js-indent-level: 2 -*- */
 /* vim: set ft=javascript ts=2 et sw=2 tw=80: */
 /* 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/. */
-/* eslint-disable spaced-comment, brace-style, indent-legacy */
+/* eslint-disable spaced-comment, brace-style, indent-legacy, no-shadow */
 
 "use strict";
 
 // This file provides an interface which the ReplayDebugger uses to interact
 // with a middleman's child recording and replaying processes. There can be
 // several child processes in existence at once; this is largely hidden from the
 // ReplayDebugger, and the position of each child is managed to provide a fast
 // and stable experience when rewinding or running forward.
 
 const CC = Components.Constructor;
 
 // Create a sandbox with the resources we need. require() doesn't work here.
 const sandbox = Cu.Sandbox(CC("@mozilla.org/systemprincipal;1", "nsIPrincipal")());
 Cu.evalInSandbox(
   "Components.utils.import('resource://gre/modules/jsdebugger.jsm');" +
   "Components.utils.import('resource://gre/modules/Services.jsm');" +
+  "Components.utils.import('resource://devtools/shared/execution-point-utils.js');" +
   "addDebuggerToGlobal(this);",
   sandbox
 );
-const RecordReplayControl = sandbox.RecordReplayControl;
-const Services = sandbox.Services;
+const {
+  RecordReplayControl,
+  Services,
+  pointPrecedes,
+  pointEquals,
+  positionEquals,
+  positionSubsumes,
+} = sandbox;
 
 const InvalidCheckpointId = 0;
 const FirstCheckpointId = 1;
 
-const gChildren = [];
-
-let gDebugger;
+// Application State Control
+//
+// This section describes the strategy used for managing child processes so that
+// we can be responsive to user interactions. There is at most one recording
+// child process, and one or more replaying child processes.
+//
+// The recording child cannot rewind: it only runs forward and adds new data to
+// the recording. If we are paused or trying to pause at a place within the
+// recording, then the recording child is also paused.
+//
+// To manage the replaying children, we identify a set of checkpoints that will
+// be saved by some replaying child. The duration between saved checkpoints
+// should be roughly equal, and they must be sufficiently closely spaced that
+// any point in the recording can be quickly reached by some replaying child
+// restoring the previous saved checkpoint and then running forward to the
+// target point.
+//
+// As we identify the saved checkpoints, each is assigned to some replaying
+// child, which is responsible for both saving that checkpoint and for scanning
+// the contents of the recording from that checkpoint until the next saved
+// checkpoint.
+//
+// When adding new data to the recording, replaying children will scan and save
+// the regions and checkpoints they are responsible for, and will otherwise play
+// forward as far as they can in the recording. We always want to have one or
+// more replaying children that are at far end of the recording and able to
+// start scanning/saving as the recording grows. In order to ensure this,
+// consider the following:
+//
+// - Replaying must be faster than recording. While recording there is idle time
+//   as we wait for user input, timers, etc. that is not present while
+//   replaying. Suppose that replaying speed is F times the recording speed.
+//   F must be less than one.
+//
+// - Scanning and saving a section of the recording is slower than recording.
+//   Both of these have a lot of overhead, and suppose that scanning is S times
+//   the recording speed. S will be more than one.
+//
+// - When there is more than one replaying child, each child can divide its time
+//   between scanning/saving and simply replaying. We want its average speed to
+//   match that of the recording. If there are N replaying children, each child
+//   scans 1/N of the recording, so the average speed compared to the recording
+//   is S/N + F*(N-1)/N. We want this term to be one or slightly less.
+//
+// For example, if F = 0.75 and S = 3, then replaying is 33% faster than
+// recording, and scanning is three times slower than recording. If N = 4,
+// the average speed is 3/4 + 0.75*3/4 = 1.31 times that of recording, which
+// will cause the replaying processes to fall further and further behind the
+// recording. If N = 12, the average speed is 3/12 + 0.75*11/12 = 0.94 times
+// that of the recording, which will allow the replaying processes to keep up
+// with the recording.
+//
+// Eventually we'll want to do this analysis dynamically to scale up or throttle
+// back the number of active replaying processes. For now, though, we rely on
+// a fixed number of replaying processes, and hope that it is enough.
 
-function ChildProcess(id, recording, role) {
-  assert(!gChildren[id]);
-  gChildren[id] = this;
+////////////////////////////////////////////////////////////////////////////////
+// Child Processes
+////////////////////////////////////////////////////////////////////////////////
 
+// Information about a child recording or replaying process.
+function ChildProcess(id, recording) {
   this.id = id;
+
+  // Whether this process is recording.
   this.recording = recording;
-  this.role = role;
+
+  // Whether this process is paused.
   this.paused = false;
 
+  // The last point we paused at.
   this.lastPausePoint = null;
-  this.lastPauseAtRecordingEndpoint = false;
+
+  // Manifests which this child needs to send asynchronously.
+  this.asyncManifests = [];
 
-  // The pauseNeeded flag indicates that background replaying children should
-  // not resume execution once the process has paused.
-  this.pauseNeeded = false;
+  // All checkpoints which this process has saved or will save, which is a
+  // subset of all the saved checkpoints.
+  this.savedCheckpoints = new Set(recording ? [] : [FirstCheckpointId]);
 
-  // All currently installed breakpoints
-  this.breakpoints = [];
+  // All saved checkpoints whose region of the recording has been scanned by
+  // this child.
+  this.scannedCheckpoints = new Set();
 
-  // Any debugger requests sent while paused at the current point.
-  this.debuggerRequests = [];
+  // Checkpoints in savedCheckpoints which haven't been sent to the child yet.
+  this.needSaveCheckpoints = [];
 
-  this._willSaveCheckpoints = [];
-  this._majorCheckpoints = [];
-  this._minorCheckpoints = new Set();
+  // Whether this child has diverged from the recording and cannot run forward.
+  this.divergedFromRecording = false;
 
-  // Replaying processes always save the first checkpoint.
-  if (!recording) {
-    this._willSaveCheckpoints.push(FirstCheckpointId);
-  }
-
-  dumpv(`InitRole #${this.id} ${role.name}`);
-  this.role.initialize(this, { startup: true });
+  // Any manifest which is currently being executed. Child processes initially
+  // have a manifest to run forward to the first checkpoint.
+  this.manifest = {
+    onFinished: ({ point }) => {
+      if (this == gMainChild) {
+        getCheckpointInfo(FirstCheckpointId).point = point;
+        Services.tm.dispatchToMainThread(recording ? maybeResumeRecording : setMainChild);
+      }
+    },
+  };
 }
 
 ChildProcess.prototype = {
-  hitExecutionPoint(msg) {
-    assert(!this.paused);
-    this.paused = true;
-    this.lastPausePoint = msg.point;
-    this.lastPauseAtRecordingEndpoint = msg.recordingEndpoint;
-
-    this.role.hitExecutionPoint(msg);
+  // Get the execution point where this child is currently paused.
+  pausePoint() {
+    assert(this.paused);
+    return this.lastPausePoint;
   },
 
-  setRole(role) {
-    dumpv(`SetRole #${this.id} ${role.name}`);
-
-    this.role = role;
-    this.role.initialize(this, { startup: false });
-  },
-
-  addMajorCheckpoint(checkpointId) {
-    this._majorCheckpoints.push(checkpointId);
-  },
-
-  addMinorCheckpoint(checkpointId) {
-    this._minorCheckpoints.add(checkpointId);
+  // Get the checkpoint where this child is currently paused.
+  pauseCheckpoint() {
+    const point = this.pausePoint();
+    assert(!point.position);
+    return point.checkpoint;
   },
 
-  _unpause() {
+  // Send a manifest to paused child to execute. The child unpauses while
+  // executing the manifest, and pauses again when it finishes. Manifests have
+  // the following properties:
+  //
+  // contents: The JSON object to send to the child describing the operation.
+  // onFinished: A callback which is called after the manifest finishes with the
+  //   manifest's result.
+  sendManifest(manifest) {
+    assert(this.paused);
     this.paused = false;
-    this.debuggerRequests.length = 0;
-  },
+    this.manifest = manifest;
 
-  sendResume({ forward }) {
-    assert(this.paused);
-    this._unpause();
-    RecordReplayControl.sendResume(this.id, forward);
+    dumpv(`SendManifest #${this.id} ${JSON.stringify(manifest.contents)}`);
+    RecordReplayControl.sendManifest(this.id, manifest.contents);
   },
 
-  sendRestoreCheckpoint(checkpoint) {
-    assert(this.paused);
-    this._unpause();
-    RecordReplayControl.sendRestoreCheckpoint(this.id, checkpoint);
+  // Called when the child's current manifest finishes.
+  manifestFinished(response) {
+    assert(!this.paused);
+    if (response && response.point) {
+      this.lastPausePoint = response.point;
+    }
+    this.paused = true;
+    this.manifest.onFinished(response);
+    this.manifest = null;
   },
 
-  sendRunToPoint(point) {
-    assert(this.paused);
-    this._unpause();
-    RecordReplayControl.sendRunToPoint(this.id, point);
-  },
-
-  sendFlushRecording() {
-    assert(this.paused);
-    RecordReplayControl.sendFlushRecording(this.id);
-  },
-
+  // Block until this child is paused. If maybeCreateCheckpoint is specified
+  // then a checkpoint is created if this child is recording, so that it pauses
+  // quickly (otherwise it could sit indefinitely if there is no page activity).
   waitUntilPaused(maybeCreateCheckpoint) {
     if (this.paused) {
       return;
     }
-    const msg =
-      RecordReplayControl.waitUntilPaused(this.id, maybeCreateCheckpoint);
-    this.hitExecutionPoint(msg);
+    RecordReplayControl.waitUntilPaused(this.id, maybeCreateCheckpoint);
     assert(this.paused);
   },
 
-  lastCheckpoint() {
-    return this.lastPausePoint.checkpoint;
-  },
-
-  rewindTargetCheckpoint() {
-    return this.lastPausePoint.position
-           ? this.lastCheckpoint()
-           : this.lastCheckpoint() - 1;
-  },
-
-  // Get the last major checkpoint at or before id.
-  lastMajorCheckpointPreceding(id) {
-    let last = InvalidCheckpointId;
-    for (const major of this._majorCheckpoints) {
-      if (major > id) {
-        break;
-      }
-      last = major;
-    }
-    return last;
-  },
-
-  isMajorCheckpoint(id) {
-    return this._majorCheckpoints.some(major => major == id);
-  },
-
-  isMinorCheckpoint(id) {
-    return this._minorCheckpoints.has(id);
-  },
-
-  ensureCheckpointSaved(id, shouldSave) {
-    const willSaveIndex = this._willSaveCheckpoints.indexOf(id);
-    if (shouldSave != (willSaveIndex != -1)) {
-      if (shouldSave) {
-        this._willSaveCheckpoints.push(id);
-      } else {
-        const last = this._willSaveCheckpoints.pop();
-        if (willSaveIndex != this._willSaveCheckpoints.length) {
-          this._willSaveCheckpoints[willSaveIndex] = last;
-        }
-      }
-      RecordReplayControl.sendSetSaveCheckpoint(this.id, id, shouldSave);
+  // Add a checkpoint for this child to save.
+  addSavedCheckpoint(checkpoint) {
+    dumpv(`AddSavedCheckpoint #${this.id} ${checkpoint}`);
+    this.savedCheckpoints.add(checkpoint);
+    if (checkpoint != FirstCheckpointId) {
+      this.needSaveCheckpoints.push(checkpoint);
     }
   },
 
-  // Ensure a checkpoint is saved in this child iff it is a major one.
-  ensureMajorCheckpointSaved(id) {
-    // The first checkpoint is always saved, even if not marked as major.
-    this.ensureCheckpointSaved(id, this.isMajorCheckpoint(id) || id == FirstCheckpointId);
-  },
-
-  hasSavedCheckpoint(id) {
-    return (id <= this.lastCheckpoint()) &&
-           this._willSaveCheckpoints.includes(id);
+  // Get any checkpoints to inform the child that it needs to save.
+  flushNeedSaveCheckpoints() {
+    const rv = this.needSaveCheckpoints;
+    this.needSaveCheckpoints = [];
+    return rv;
   },
 
-  // Return whether this child has saved all minor checkpoints between the last
-  // major checkpoint preceding to id and id itself. This is required in order
-  // for the child to rewind through this span of checkpoints.
-  canRewindFrom(id) {
-    const lastMajorCheckpoint = this.lastMajorCheckpointPreceding(id);
-    for (let i = lastMajorCheckpoint + 1; i <= id; i++) {
-      if (this.isMinorCheckpoint(i) && !this.hasSavedCheckpoint(i)) {
-        return false;
-      }
-    }
-    return true;
+  // Send a manifest to this child asynchronously. The child does not need to be
+  // paused, and will process async manifests in the order they were added.
+  // Async manifests can end up being reassigned to a different child. This
+  // returns a promise that resolves when the manifest finishes. Async manifests
+  // have the following properties:
+  //
+  // shouldSkip: Optional callback invoked with the executing child when it is
+  //   about to be sent. Returns true if the manifest should not be sent, and
+  //   the promise resolved immediately.
+  //
+  // contents: Callback invoked with the executing child when it is being sent.
+  //   Returns the contents to send to the child.
+  //
+  // onFinished: Optional callback invoked with the executing child and manifest
+  //   response after the manifest finishes.
+  //
+  // noReassign: Optional boolean which can be set to prevent the manifest from
+  //   being reassigned to another child.
+  //
+  // The optional point parameter specifies an execution point which the child
+  // should be paused at before executing the manifest. Otherwise it could be
+  // paused anywhere. The returned value is the child which ended up executing
+  // the manifest.
+  sendManifestAsync(manifest, point) {
+    pokeChildSoon(this);
+    return new Promise(resolve => {
+      this.asyncManifests.push({ resolve, manifest, point });
+    });
   },
 
-  lastSavedCheckpointPriorTo(id) {
-    while (!this.hasSavedCheckpoint(id)) {
-      id--;
+  // Return true if progress was made while executing the next async manifest.
+  processAsyncManifest() {
+    if (this.asyncManifests.length == 0) {
+      return false;
     }
-    return id;
-  },
-
-  sendAddBreakpoint(pos) {
-    assert(this.paused);
-    this.breakpoints.push(pos);
-    RecordReplayControl.sendAddBreakpoint(this.id, pos);
-  },
+    const { resolve, manifest, point } = this.asyncManifests[0];
+    if (manifest.shouldSkip && manifest.shouldSkip(this)) {
+      resolve(this);
+      this.asyncManifests.shift();
+      pokeChildSoon(this);
+      return true;
+    }
 
-  sendClearBreakpoints() {
-    assert(this.paused);
-    this.breakpoints.length = 0;
-    RecordReplayControl.sendClearBreakpoints(this.id);
-  },
-
-  sendDebuggerRequest(request) {
-    assert(this.paused);
-    this.debuggerRequests.push(request);
-    return RecordReplayControl.sendDebuggerRequest(this.id, request);
-  },
+    // If this is the active child then we can't process arbitrary manifests.
+    // Only handle those which cannot be reassigned, and hand off others to
+    // random other children.
+    if (this == gActiveChild && !manifest.noReassign) {
+      const child = pickReplayingChild();
+      child.asyncManifests.push(this.asyncManifests.shift());
+      pokeChildSoon(child);
+      pokeChildSoon(this);
+      return true;
+    }
 
-  // When a background child pauses, it does not immediately resume. This will
-  // asynchronously let the role know that it may be able to make progress,
-  // depending on where the active child is and what it is doing.
-  pokeSoon() {
-    if (!this.recording) {
-      Services.tm.dispatchToMainThread(() => {
-        if (this.paused) {
-          this.role.poke();
+    if (point && maybeReachPoint(this, point)) {
+      return true;
+    }
+    this.sendManifest({
+      contents: manifest.contents(this),
+      onFinished: data => {
+        if (manifest.onFinished) {
+          manifest.onFinished(this, data);
         }
-      });
-    }
+        resolve(this);
+        pokeChildSoon(this);
+      },
+    });
+    this.asyncManifests.shift();
+    return true;
   },
 };
 
-function pokeChildren() {
-  for (const child of gChildren) {
+// Child which is always at the end of the recording. When there is a recording
+// child this is it, and when we are replaying an old execution this is a
+// replaying child that is unable to rewind and is used in the same way as the
+// recording child.
+let gMainChild;
+
+// Replaying children available for exploring the interior of the recording,
+// indexed by their ID.
+const gReplayingChildren = [];
+
+function lookupChild(id) {
+  if (id == gMainChild.id) {
+    return gMainChild;
+  }
+  assert(gReplayingChildren[id]);
+  return gReplayingChildren[id];
+}
+
+// ID of the last replaying child we picked for an operation.
+let lastPickedChildId = 0;
+
+function pickReplayingChild() {
+  // Use a round robin approach when picking new children for operations,
+  // to try to keep activity among the children evenly distributed.
+  while (true) {
+    lastPickedChildId = (lastPickedChildId + 1) % gReplayingChildren.length;
+    const child = gReplayingChildren[lastPickedChildId];
     if (child) {
-      child.pokeSoon();
+      return child;
     }
   }
 }
 
+// The singleton ReplayDebugger, or undefined if it doesn't exist.
+let gDebugger;
+
+////////////////////////////////////////////////////////////////////////////////
+// Application State
+////////////////////////////////////////////////////////////////////////////////
+
+// Any child the user is interacting with, which may be paused or not.
+let gActiveChild = null;
+
+// Information about each checkpoint, indexed by the checkpoint's id.
+const gCheckpoints = [ null ];
+
+function CheckpointInfo() {
+  // The time taken to run from this checkpoint to the next one, excluding idle
+  // time.
+  this.duration = 0;
+
+  // Execution point at the checkpoint.
+  this.point = null;
+
+  // If the checkpoint is saved, the replaying child responsible for saving it
+  // and scanning the region up to the next saved checkpoint.
+  this.owner = null;
+}
+
+function getCheckpointInfo(id) {
+  while (id >= gCheckpoints.length) {
+    gCheckpoints.push(new CheckpointInfo());
+  }
+  return gCheckpoints[id];
+}
+
+// How much execution time has elapsed since a checkpoint.
+function timeSinceCheckpoint(id) {
+  let time = 0;
+  for (let i = id ? id : FirstCheckpointId; i < gCheckpoints.length; i++) {
+    time += gCheckpoints[i].duration;
+  }
+  return time;
+}
+
+// The checkpoint up to which the recording runs.
+let gLastFlushCheckpoint = InvalidCheckpointId;
+
+// The last saved checkpoint.
+let gLastSavedCheckpoint = FirstCheckpointId;
+
+// How often we want to flush the recording.
 const FlushMs = .5 * 1000;
-const MajorCheckpointMs = 2 * 1000;
-const MinorCheckpointMs = .25 * 1000;
+
+// How often we want to save a checkpoint.
+const SavedCheckpointMs = .25 * 1000;
+
+function addSavedCheckpoint(checkpoint) {
+  if (getCheckpointInfo(checkpoint).owner) {
+    return;
+  }
+
+  const owner = pickReplayingChild();
+  getCheckpointInfo(checkpoint).owner = owner;
+  owner.addSavedCheckpoint(checkpoint);
+  gLastSavedCheckpoint = checkpoint;
+}
+
+function addCheckpoint(checkpoint, duration) {
+  assert(!getCheckpointInfo(checkpoint).duration);
+  getCheckpointInfo(checkpoint).duration = duration;
+
+  // Mark saved checkpoints as required, unless we haven't spawned any replaying
+  // children yet.
+  if (timeSinceCheckpoint(gLastSavedCheckpoint) >= SavedCheckpointMs &&
+      gReplayingChildren.length > 0) {
+    addSavedCheckpoint(checkpoint + 1);
+  }
+}
+
+function ownerChild(checkpoint) {
+  assert(checkpoint <= gLastSavedCheckpoint);
+  while (!getCheckpointInfo(checkpoint).owner) {
+    checkpoint--;
+  }
+  return getCheckpointInfo(checkpoint).owner;
+}
 
-// This section describes the strategy used for managing child processes. When
-// recording, there is a single recording process and two replaying processes.
-// When replaying, there are two replaying processes. The main advantage of
-// using two replaying processes is to provide a smooth experience when
-// rewinding.
-//
-// At any time there is one active child: the process which the user is
-// interacting with. This may be any of the two or three children in existence,
-// depending on the user's behavior. The other processes do not interact with
-// the user: inactive recording processes are inert, and sit idle until
-// recording is ready to resume, while inactive replaying processes are on
-// standby, staying close to the active process in the recording's execution
-// space and saving checkpoints in case the user starts rewinding.
-//
-// Below are some scenarios showing the state we attempt to keep the children
-// in, and ways in which the active process switches from one to another.
-// The execution diagrams show the position of each process, with '*' and '-'
-// indicating checkpoints the process reached and, respectively, whether
-// the checkpoint was saved or not.
-//
-// When the recording process is actively recording, flushes are issued to it
-// every FlushMs to keep the recording reasonably current and allow the
-// replaying processes to stay behind but close to the position of the
-// recording process. Additionally, one replaying process saves a checkpoint
-// every MajorCheckpointMs with the process saving the checkpoint alternating
-// back and forth so that individual processes save checkpoints every
-// MajorCheckpointMs*2. These are the major checkpoints for each replaying
-// process.
-//
-// Active  Recording:    -----------------------
-// Standby Replaying #1: *---------*---------*
-// Standby Replaying #2: -----*---------*-----
-//
-// When the recording process is explicitly paused (via the debugger UI) at a
-// checkpoint or breakpoint, it is flushed and the replaying processes will
-// navigate around the recording to save a second set of checkpoints going back
-// at least MajorCheckpointSeconds, with the goal of making sure saved
-// checkpoints are no more than MinorCheckpointSeconds apart. No replaying
-// process needs to rewind past its last major checkpoint, and a given
-// minor checkpoint will only ever be saved by the replaying process with the
-// most recent major checkpoint.
-//
-// Active  Recording:    -----------------------
-// Standby Replaying #1: *---------*---------*-*
-// Standby Replaying #2: -----*---------*-*-*
-//
-// If the user starts rewinding, the replaying process with the most recent
-// major checkpoint (and which has been saving the most recent minor
-// checkpoints) becomes the active child.
-//
-// Inert   Recording:    -----------------------
-// Active  Replaying #1: *---------*---------*-
-// Standby Replaying #2: -----*---------*-*-*
-//
-// As the user continues rewinding, the replaying process stays active until it
-// goes past its most recent major checkpoint. At that time the other replaying
-// process (which has been saving checkpoints prior to that point) becomes the
-// active child and allows continuous rewinding. The first replaying process
-// rewinds to its last major checkpoint and begins saving older minor
-// checkpoints, attempting to maintain the invariant that we have saved (or are
-// saving) all checkpoints going back MajorCheckpointMs.
-//
-// Inert   Recording:    -----------------------
-// Standby Replaying #1: *---------*-*-*
-// Active  Replaying #2: -----*---------*-
-//
-// Rewinding continues in this manner, alternating back and forth between the
-// replaying processes as the user continues going back in time.
-//
-// Inert   Recording:    -----------------------
-// Active  Replaying #1: *---------*-*
-// Standby Replaying #2: -----*-*-*
-//
-// If the user starts navigating forward, the replaying processes both run
-// forward and save checkpoints at the same major checkpoints as earlier.
-// Note that this is how all forward execution works when there is no recording
-// process (i.e. we started from a saved recording).
-//
-// Inert   Recording:    -----------------------
-// Active  Replaying #1: *---------*-*-----
-// Standby Replaying #2: -----*-*-*-----*--
-//
-// If the user pauses at a checkpoint or breakpoint in the replay, we again
-// want to fill in all the checkpoints going back MajorCheckpointMs to allow
-// smooth rewinding. This cannot be done simultaneously -- as it was when the
-// recording process was active -- since we need to keep one of the replaying
-// processes at an up to date point and be the active one. This falls on the one
-// whose most recent major checkpoint is oldest, as the other is responsible for
-// saving the most recent minor checkpoints.
-//
-// Inert   Recording:    -----------------------
-// Active  Replaying #1: *---------*-*-----
-// Standby Replaying #2: -----*-*-*-----*-*
-//
-// After the recent minor checkpoints have been saved the process which
-// took them can become active so the older minor checkpoints can be
-// saved.
-//
-// Inert   Recording:    -----------------------
-// Standby Replaying #1: *---------*-*-*
-// Active  Replaying #2: -----*-*-*-----*-*
-//
-// Finally, if the replay plays forward to the end of the recording (the point
-// where the recording process is situated), the recording process takes over
-// again as the active child and the user can resume interacting with a live
-// process.
-//
-// Active  Recording:    ----------------------------------------
-// Standby Replaying #1: *---------*-*-*-----*---------*-------
-// Standby Replaying #2: -----*-*-*-----*-*-------*---------*--
+// Unpause a child and restore it to its most recent saved checkpoint at or
+// before target.
+function restoreCheckpoint(child, target) {
+  while (!child.savedCheckpoints.has(target)) {
+    target--;
+  }
+  child.sendManifest({
+    contents: { kind: "restoreCheckpoint", target },
+    onFinished({ restoredCheckpoint }) {
+      assert(restoredCheckpoint);
+      child.divergedFromRecording = false;
+      pokeChildSoon(child);
+    },
+  });
+}
+
+// Bring a child to the specified execution point, sending it one or more
+// manifests if necessary. Returns true if the child has not reached the point
+// yet but some progress was made, or false if the child is at the point.
+function maybeReachPoint(child, endpoint) {
+  if (pointEquals(child.pausePoint(), endpoint) && !child.divergedFromRecording) {
+    return false;
+  }
+  if (child.divergedFromRecording || child.pausePoint().position) {
+    restoreCheckpoint(child, child.pausePoint().checkpoint);
+    return true;
+  }
+  if (endpoint.checkpoint < child.pauseCheckpoint()) {
+    restoreCheckpoint(child, endpoint.checkpoint);
+    return true;
+  }
+  child.sendManifest({
+    contents: {
+      kind: "runToPoint",
+      endpoint,
+      needSaveCheckpoints: child.flushNeedSaveCheckpoints(),
+    },
+    onFinished() {
+      pokeChildSoon(child);
+    },
+  });
+  return true;
+}
+
+function nextSavedCheckpoint(checkpoint) {
+  assert(gCheckpoints[checkpoint].owner);
+  // eslint-disable-next-line no-empty
+  while (!gCheckpoints[++checkpoint].owner) {}
+  return checkpoint;
+}
 
-// Child processes that can participate in the above management.
-let gRecordingChild;
-let gFirstReplayingChild;
-let gSecondReplayingChild;
-let gActiveChild;
+function forSavedCheckpointsInRange(start, end, callback) {
+  assert(gCheckpoints[start].owner);
+  for (let checkpoint = start;
+       checkpoint < end;
+       checkpoint = nextSavedCheckpoint(checkpoint)) {
+    callback(checkpoint);
+  }
+}
+
+function getSavedCheckpoint(checkpoint) {
+  while (!gCheckpoints[checkpoint].owner) {
+    checkpoint--;
+  }
+  return checkpoint;
+}
+
+// Get the execution point to use for a checkpoint.
+function checkpointExecutionPoint(checkpoint) {
+  return gCheckpoints[checkpoint].point;
+}
+
+// Check to see if an idle replaying child can make any progress.
+function pokeChild(child) {
+  assert(!child.recording);
 
-function otherReplayingChild(child) {
-  assert(child == gFirstReplayingChild || child == gSecondReplayingChild);
-  return child == gFirstReplayingChild
-         ? gSecondReplayingChild
-         : gFirstReplayingChild;
+  if (!child.paused) {
+    return;
+  }
+
+  if (child.processAsyncManifest()) {
+    return;
+  }
+
+  if (child == gActiveChild) {
+    sendChildToPausePoint(child);
+    return;
+  }
+
+  // If there is nothing to do, run forward to the end of the recording.
+  maybeReachPoint(child, checkpointExecutionPoint(gLastFlushCheckpoint));
+}
+
+function pokeChildSoon(child) {
+  Services.tm.dispatchToMainThread(() => pokeChild(child));
+}
+
+function pokeChildren() {
+  for (const child of gReplayingChildren) {
+    if (child) {
+      pokeChild(child);
+    }
+  }
+}
+
+function pokeChildrenSoon() {
+  Services.tm.dispatchToMainThread(() => pokeChildren());
 }
 
 ////////////////////////////////////////////////////////////////////////////////
-// Child Roles
+// Search State
 ////////////////////////////////////////////////////////////////////////////////
 
-function ChildRoleActive() {}
-
-ChildRoleActive.prototype = {
-  name: "Active",
-
-  initialize(child, { startup }) {
-    this.child = child;
-    gActiveChild = child;
-
-    // Mark the child as active unless we are starting up, in which case it is
-    // unpaused and we can't send messages to it.
-    if (!startup) {
-      RecordReplayControl.setActiveChild(child.id);
-    }
-  },
-
-  hitExecutionPoint(msg) {
-    // Ignore HitCheckpoint messages received while doing a time warp.
-    // timeWarp() will immediately resume the child and we don't want to tell
-    // the debugger it ever paused.
-    if (gTimeWarpInProgress) {
-      return;
-    }
-
-    // Make sure the active child is marked as such when starting up.
-    if (msg.point.checkpoint == FirstCheckpointId) {
-      RecordReplayControl.setActiveChild(this.child.id);
-    }
-
-    updateCheckpointTimes(msg);
-
-    // When at the endpoint of the recording, immediately resume. We don't
-    // want to notify the debugger about this: if the user installed a
-    // breakpoint here we will have already gotten a HitExecutionPoint message
-    // *without* mRecordingEndpoint set, and we don't want to pause twice at
-    // the same point.
-    if (msg.recordingEndpoint) {
-      resume(true);
-
-      // When resuming at the end of the recording, we will either switch to a
-      // recording child or stay paused at the endpoint. In either case, this
-      // process will stay paused.
-      assert(this.child.paused);
-      return;
-    }
-
-    // Run forward by default if there is no debugger attached, but post a
-    // runnable so that callers waiting for the child to pause don't starve.
-    if (!gDebugger) {
-      Services.tm.dispatchToMainThread(() => this.child.sendResume({ forward: true }));
-      return;
-    }
+// All currently installed breakpoints.
+const gBreakpoints = [];
 
-    gDebugger._onPause();
-  },
-
-  poke() {},
-};
-
-// The last checkpoint included in the recording.
-let gLastRecordingCheckpoint;
-
-// The role taken by replaying children trying to stay close to the active
-// child and save either major or minor checkpoints, depending on whether the
-// active child is paused or rewinding.
-function ChildRoleStandby() {}
-
-ChildRoleStandby.prototype = {
-  name: "Standby",
-
-  initialize(child) {
-    this.child = child;
-    this.child.pokeSoon();
-  },
-
-  hitExecutionPoint(msg) {
-    assert(!msg.point.position);
-    this.child.pokeSoon();
-  },
-
-  poke() {
-    assert(this.child.paused && !this.child.lastPausePoint.position);
-    const currentCheckpoint = this.child.lastCheckpoint();
-
-    // Stay paused if we need to while the recording is flushed.
-    if (this.child.pauseNeeded) {
-      return;
-    }
-
-    // Minor checkpoints are only saved when the active child is paused
-    // or rewinding.
-    let targetCheckpoint = getActiveChildTargetCheckpoint();
-    if (targetCheckpoint == undefined) {
-      // Minor checkpoints do not need to be saved. Run forward until we
-      // reach either the active child's position, or the last checkpoint
-      // included in the on-disk recording. Only save major checkpoints.
-      if ((currentCheckpoint < gActiveChild.lastCheckpoint()) &&
-          (!gRecordingChild || currentCheckpoint < gLastRecordingCheckpoint)) {
-        this.child.ensureMajorCheckpointSaved(currentCheckpoint + 1);
-        this.child.sendResume({ forward: true });
-      }
-      return;
-    }
-
-    // The startpoint of the range is the most recent major checkpoint prior
-    // to the target.
-    const lastMajorCheckpoint =
-      this.child.lastMajorCheckpointPreceding(targetCheckpoint);
+// Recording Scanning
+//
+// Scanning a section of the recording between two neighboring saved checkpoints
+// allows the execution points for each script breakpoint position to be queried
+// by sending a manifest to the child which performed the scan.
 
-    // If there is no major checkpoint prior to the target, just idle.
-    if (lastMajorCheckpoint == InvalidCheckpointId) {
-      return;
-    }
-
-    // If we haven't reached the last major checkpoint, we need to run forward
-    // without saving minor checkpoints.
-    if (currentCheckpoint < lastMajorCheckpoint) {
-      this.child.ensureMajorCheckpointSaved(currentCheckpoint + 1);
-      this.child.sendResume({ forward: true });
-      return;
-    }
-
-    // The endpoint of the range is the checkpoint prior to either the active
-    // child's current position, or the other replaying child's most recent
-    // major checkpoint.
-    const otherChild = otherReplayingChild(this.child);
-    const otherMajorCheckpoint =
-      otherChild.lastMajorCheckpointPreceding(targetCheckpoint);
-    if (otherMajorCheckpoint > lastMajorCheckpoint) {
-      assert(otherMajorCheckpoint <= targetCheckpoint);
-      targetCheckpoint = otherMajorCheckpoint - 1;
-    }
-
-    // Find the first minor checkpoint in the fill range which we have not saved.
-    let missingCheckpoint;
-    for (let i = lastMajorCheckpoint + 1; i <= targetCheckpoint; i++) {
-      if (this.child.isMinorCheckpoint(i) && !this.child.hasSavedCheckpoint(i)) {
-        missingCheckpoint = i;
-        break;
-      }
-    }
-
-    // If we have already saved everything we need to, we can idle.
-    if (missingCheckpoint == undefined) {
-      return;
-    }
-
-    if (this.child.lastCheckpoint() < missingCheckpoint) {
-      // We can run forward to reach the missing checkpoint.
-    } else {
-      // We need to rewind in order to save the missing checkpoint. Find the
-      // last saved checkpoint prior to the missing one. This must be
-      // lastMajorCheckpoint or later, as we always save major checkpoints.
-      let restoreTarget = missingCheckpoint - 1;
-      while (!this.child.hasSavedCheckpoint(restoreTarget)) {
-        restoreTarget--;
-      }
-      assert(restoreTarget >= lastMajorCheckpoint);
-
-      this.child.sendRestoreCheckpoint(restoreTarget);
-      return;
-    }
+// Ensure the region for a saved checkpoint has been scanned by some child,
+// returning a promise that resolves with that child.
+function scanRecording(checkpoint) {
+  assert(checkpoint < gLastFlushCheckpoint);
 
-    // Make sure the process will save minor checkpoints as it runs forward.
-    if (missingCheckpoint == this.child.lastCheckpoint() + 1) {
-      this.child.ensureCheckpointSaved(missingCheckpoint, true);
-    }
-
-    // Run forward to the next checkpoint.
-    this.child.sendResume({ forward: true });
-  },
-};
-
-// The role taken by a child that always sits idle.
-function ChildRoleInert() {}
-
-ChildRoleInert.prototype = {
-  name: "Inert",
-
-  initialize() {},
-  hitExecutionPoint() {},
-  poke() {},
-};
-
-////////////////////////////////////////////////////////////////////////////////
-// Child Switching
-////////////////////////////////////////////////////////////////////////////////
-
-// Change the current active child, and select a new role for the old one.
-function switchActiveChild(child, recoverPosition = true) {
-  assert(child != gActiveChild);
-  assert(gActiveChild.paused);
-
-  const oldActiveChild = gActiveChild;
-  child.waitUntilPaused();
-
-  // Move the installed breakpoints from the old child to the new child.
-  assert(child.breakpoints.length == 0);
-  for (const pos of oldActiveChild.breakpoints) {
-    child.sendAddBreakpoint(pos);
-  }
-  oldActiveChild.sendClearBreakpoints();
-
-  if (recoverPosition && !child.recording) {
-    child.setRole(new ChildRoleInert());
-    const targetCheckpoint = oldActiveChild.lastCheckpoint();
-    if (child.lastCheckpoint() > targetCheckpoint) {
-      const restoreCheckpoint =
-        child.lastSavedCheckpointPriorTo(targetCheckpoint);
-      child.sendRestoreCheckpoint(restoreCheckpoint);
-      child.waitUntilPaused();
-    }
-    while (child.lastCheckpoint() < targetCheckpoint) {
-      child.ensureMajorCheckpointSaved(child.lastCheckpoint() + 1);
-      child.sendResume({ forward: true });
-      child.waitUntilPaused();
-    }
-    assert(!child.lastPausePoint.position);
-    if (oldActiveChild.lastPausePoint.position) {
-      child.sendRunToPoint(oldActiveChild.lastPausePoint);
-      child.waitUntilPaused();
-    }
-    for (const request of oldActiveChild.debuggerRequests) {
-      child.sendDebuggerRequest(request);
+  for (const child of gReplayingChildren) {
+    if (child && child.scannedCheckpoints.has(checkpoint)) {
+      return child;
     }
   }
 
-  child.setRole(new ChildRoleActive());
-  oldActiveChild.setRole(new ChildRoleInert());
+  const initialChild = ownerChild(checkpoint);
+  const endpoint = nextSavedCheckpoint(checkpoint);
+  return initialChild.sendManifestAsync({
+    shouldSkip: child => child.scannedCheckpoints.has(checkpoint),
+    contents(child) {
+      return {
+        kind: "scanRecording",
+        endpoint,
+        needSaveCheckpoints: child.flushNeedSaveCheckpoints(),
+      };
+    },
+    onFinished: child => child.scannedCheckpoints.add(checkpoint),
+  }, checkpointExecutionPoint(checkpoint));
+}
 
-  if (!oldActiveChild.recording) {
-    if (oldActiveChild.lastPausePoint.position) {
-      // Standby replaying children must be paused at a checkpoint.
-      const oldCheckpoint = oldActiveChild.lastCheckpoint();
-      const restoreCheckpoint =
-        oldActiveChild.lastSavedCheckpointPriorTo(oldCheckpoint);
-      oldActiveChild.sendRestoreCheckpoint(restoreCheckpoint);
-      oldActiveChild.waitUntilPaused();
-    }
-    oldActiveChild.setRole(new ChildRoleStandby());
+// Map from saved checkpoints to information about breakpoint hits within the
+// range of that checkpoint.
+const gHitSearches = new Map();
+
+// Only hits on script locations (Break and OnStep positions) can be found by
+// scanning the recording.
+function canFindHits(position) {
+  return position.kind == "Break" || position.kind == "OnStep";
+}
+
+// Find all hits on the specified position between a saved checkpoint and the
+// following saved checkpoint, using data from scanning the recording. This
+// returns a promise that resolves with the resulting hits.
+async function findHits(checkpoint, position) {
+  assert(canFindHits(position));
+  assert(gCheckpoints[checkpoint].owner);
+
+  if (!gHitSearches.has(checkpoint)) {
+    gHitSearches.set(checkpoint, []);
   }
 
-  // Notify the debugger when switching between recording and replaying
-  // children.
-  if (child.recording != oldActiveChild.recording) {
-    gDebugger._onSwitchChild();
+  // Check if we already have the hits.
+  if (!gHitSearches.has(checkpoint)) {
+    gHitSearches.set(checkpoint, []);
+  }
+  const checkpointHits = gHitSearches.get(checkpoint);
+  let hits = findExistingHits();
+  if (hits) {
+    return hits;
+  }
+
+  const child = await scanRecording(checkpoint);
+  const endpoint = nextSavedCheckpoint(checkpoint);
+  await child.sendManifestAsync({
+    shouldSkip: () => findExistingHits() != null,
+    contents() {
+      return {
+        kind: "findHits",
+        position,
+        startpoint: checkpoint,
+        endpoint,
+      };
+    },
+    onFinished: (_, hits) => checkpointHits.push({ position, hits }),
+    // findHits has to be sent to the child which scanned this portion of the
+    // recording. It can be sent to the active child, though, because it
+    // does not have side effects.
+    noReassign: true,
+  });
+
+  hits = findExistingHits();
+  assert(hits);
+  return hits;
+
+  function findExistingHits() {
+    const entry = checkpointHits.find(({ position: existingPosition, hits }) => {
+      return positionEquals(position, existingPosition);
+    });
+    return entry ? entry.hits : null;
   }
 }
 
-function maybeSwitchToReplayingChild() {
-  if (gActiveChild.recording && RecordReplayControl.canRewind()) {
-    flushRecording();
-    const checkpoint = gActiveChild.rewindTargetCheckpoint();
-    const child = otherReplayingChild(
-      replayingChildResponsibleForSavingCheckpoint(checkpoint));
-    switchActiveChild(child);
+// Frame Steps
+//
+// When the recording scanning is not sufficient to figure out where to stop
+// when resuming, the steps for the currently paused frame can be fetched. This
+// mainly helps with finding the targets for EnterFrame breakpoints used when
+// stepping in, and will be used in the future to improve stepping performance.
+//
+// The steps for a frame are the list of execution points for breakpoint
+// positions traversed when executing a particular script frame, from the
+// initial EnterFrame to the final OnPop. The steps also include the EnterFrame
+// execution points for any direct callees of the frame.
+
+// All steps for frames which have been determined.
+const gFrameSteps = [];
+
+// When there are stepping breakpoints installed, we need to know the steps in
+// the current frame in order to find the next or previous hit.
+function hasSteppingBreakpoint() {
+  return gBreakpoints.some(bp => bp.kind == "EnterFrame" || bp.kind == "OnPop");
+}
+
+// Find all the steps in the frame which point is part of. This returns a
+// promise that resolves with the steps that were found.
+async function findFrameSteps(point) {
+  if (!point.position) {
+    return null;
+  }
+
+  assert(point.position.kind == "EnterFrame" ||
+         point.position.kind == "OnStep" ||
+         point.position.kind == "OnPop");
+
+  let steps = findExistingSteps();
+  if (steps) {
+    return steps;
+  }
+
+  const savedCheckpoint = getSavedCheckpoint(point.checkpoint);
+
+  let entryPoint;
+  if (point.position.kind == "EnterFrame") {
+    entryPoint = point;
+  } else {
+    // The point is in the interior of the frame. Figure out the initial
+    // EnterFrame point for the frame.
+    const {
+      progress: targetProgress,
+      position: { script, frameIndex: targetFrameIndex },
+    } = point;
+
+    // Find a position for the entry point of the frame.
+    const { firstBreakpointOffset } = gControl.sendRequestMainChild({
+      type: "getScript",
+      id: script,
+    });
+    const entryPosition = {
+      kind: "OnStep",
+      script,
+      offset: firstBreakpointOffset,
+      frameIndex: targetFrameIndex,
+    };
+
+    const entryHits = await findHits(savedCheckpoint, entryPosition);
+
+    // Find the last hit on the entry position before the target point, which must
+    // be the entry point of the frame containing the target point. Since frames
+    // do not span checkpoints the hit must be in the range we are searching. Note
+    // that we are not dealing with async/generator frames very well here.
+    let progressAtFrameStart = 0;
+    for (const { progress, position: { frameIndex } } of entryHits) {
+      if (frameIndex == targetFrameIndex &&
+          progress <= targetProgress &&
+          progress > progressAtFrameStart) {
+        progressAtFrameStart = progress;
+      }
+    }
+    assert(progressAtFrameStart);
+
+    // The progress at the initial offset should be the same as at the
+    // EnterFrame which pushed the frame onto the stack. No scripts should be
+    // able to run between these two points, though we don't have a way to check
+    // this.
+    entryPoint = {
+      checkpoint: point.checkpoint,
+      progress: progressAtFrameStart,
+      position: { kind: "EnterFrame" },
+    };
+  }
+
+  const child = ownerChild(savedCheckpoint);
+  await child.sendManifestAsync({
+    shouldSkip: () => findExistingSteps() != null,
+    contents() {
+      return { kind: "findFrameSteps", entryPoint };
+    },
+    onFinished: (_, { frameSteps }) => gFrameSteps.push(frameSteps),
+  }, entryPoint);
+
+  steps = findExistingSteps();
+  assert(steps);
+  return steps;
+
+  function findExistingSteps() {
+    // Frame steps will include EnterFrame for both the initial and callee
+    // frames, so the same point can appear in two sets of steps. In this case
+    // the EnterFrame needs to be the first step.
+    if (point.position.kind == "EnterFrame") {
+      return gFrameSteps.find(steps => pointEquals(point, steps[0]));
+    }
+    return gFrameSteps.find(steps => steps.some(p => pointEquals(point, p)));
   }
 }
 
 ////////////////////////////////////////////////////////////////////////////////
-// Major and Minor Checkpoints
+// Pause State
 ////////////////////////////////////////////////////////////////////////////////
 
-// For each checkpoint N, this vector keeps track of the time intervals taken
-// for the active child (excluding idle time) to run from N to N+1.
-const gCheckpointTimes = [];
+// The pause mode classifies the current state of the debugger.
+const PauseModes = {
+  // Process is actively recording. gPausePoint is the last point the main child
+  // reached.
+  RUNNING: "RUNNING",
+
+  // gActiveChild is paused at gPausePoint.
+  PAUSED: "PAUSED",
 
-// How much time has elapsed (per gCheckpointTimes) since the last flush or
-// major/minor checkpoint was noted.
-let gTimeSinceLastFlush;
-let gTimeSinceLastMajorCheckpoint = 0;
-let gTimeSinceLastMinorCheckpoint = 0;
+  // gActiveChild is being taken to gPausePoint, after which we will pause.
+  ARRIVING: "ARRIVING",
+
+  // gActiveChild is null, and we are looking for the last breakpoint hit prior
+  // to or following gPausePoint, at which we will pause.
+  RESUMING_BACKWARD: "RESUMING_BACKWARD",
+  RESUMING_FORWARD: "RESUMING_FORWARD",
+};
 
-// The replaying process that was given the last major checkpoint.
-let gLastAssignedMajorCheckpoint;
+// Current pause mode.
+let gPauseMode = PauseModes.RUNNING;
+
+// In PAUSED or ARRIVING mode, the point we are paused at or sending the active child to.
+let gPausePoint = null;
+
+// In PAUSED mode, any debugger requests that have been sent to the child.
+const gDebuggerRequests = [];
 
-function assignMajorCheckpoint(child, checkpointId) {
-  dumpv(`AssignMajorCheckpoint: #${child.id} Checkpoint ${checkpointId}`);
-  child.addMajorCheckpoint(checkpointId);
-  gLastAssignedMajorCheckpoint = child;
-}
+function setPauseState(mode, point, child) {
+  assert(mode);
+  const idString = child ? ` #${child.id}` : "";
+  dumpv(`SetPauseState ${mode} ${JSON.stringify(point)}${idString}`);
 
-function assignMinorCheckpoint(child, checkpointId) {
-  dumpv(`AssignMinorCheckpoint: #${child.id} Checkpoint ${checkpointId}`);
-  child.addMinorCheckpoint(checkpointId);
+  gPauseMode = mode;
+  gPausePoint = point;
+  gActiveChild = child;
+
+  pokeChildrenSoon();
 }
 
-function updateCheckpointTimes(msg) {
-  if (msg.point.checkpoint != gCheckpointTimes.length + 1 ||
-      msg.point.position) {
-    return;
-  }
-  gCheckpointTimes.push(msg.duration);
+// Asynchronously send a child to the specific point and pause the debugger.
+function setReplayingPauseTarget(point) {
+  setPauseState(PauseModes.ARRIVING, point, ownerChild(point.checkpoint));
+  gDebuggerRequests.length = 0;
+
+  findFrameSteps(point);
+}
 
-  if (gActiveChild.recording) {
-    gTimeSinceLastFlush += msg.duration;
+// Synchronously send a child to the specific point and pause.
+function pauseReplayingChild(point) {
+  const child = ownerChild(point.checkpoint);
+
+  do {
+    child.waitUntilPaused();
+  } while (maybeReachPoint(child, point));
+
+  setPauseState(PauseModes.PAUSED, point, child);
 
-    // Occasionally flush while recording so replaying processes stay
-    // reasonably current.
-    if (msg.point.checkpoint == FirstCheckpointId ||
-        gTimeSinceLastFlush >= FlushMs) {
-      if (maybeFlushRecording()) {
-        gTimeSinceLastFlush = 0;
-      }
-    }
-  }
+  findFrameSteps(point);
+}
+
+function sendChildToPausePoint(child) {
+  assert(child.paused && child == gActiveChild);
+
+  switch (gPauseMode) {
+  case PauseModes.PAUSED:
+    assert(pointEquals(child.pausePoint(), gPausePoint));
+    return;
 
-  gTimeSinceLastMajorCheckpoint += msg.duration;
-  gTimeSinceLastMinorCheckpoint += msg.duration;
+  case PauseModes.ARRIVING:
+    if (pointEquals(child.pausePoint(), gPausePoint)) {
+      setPauseState(PauseModes.PAUSED, gPausePoint, gActiveChild);
+      gDebugger._onPause();
+      return;
+    }
+    maybeReachPoint(child, gPausePoint);
+    return;
 
-  if (gTimeSinceLastMajorCheckpoint >= MajorCheckpointMs) {
-    // Alternate back and forth between assigning major checkpoints to the
-    // two replaying processes.
-    const child = otherReplayingChild(gLastAssignedMajorCheckpoint);
-    assignMajorCheckpoint(child, msg.point.checkpoint + 1);
-    gTimeSinceLastMajorCheckpoint = 0;
-  } else if (gTimeSinceLastMinorCheckpoint >= MinorCheckpointMs) {
-    // Assign a minor checkpoint to the process which saved the last major one.
-    assignMinorCheckpoint(gLastAssignedMajorCheckpoint, msg.point.checkpoint + 1);
-    gTimeSinceLastMinorCheckpoint = 0;
+  default:
+    throw new Error(`Unexpected pause mode: ${gPauseMode}`);
   }
 }
 
-// Get the replaying process responsible for saving id when rewinding: the one
-// with the most recent major checkpoint preceding id.
-function replayingChildResponsibleForSavingCheckpoint(id) {
-  assert(gFirstReplayingChild && gSecondReplayingChild);
-  const firstMajor = gFirstReplayingChild.lastMajorCheckpointPreceding(id);
-  const secondMajor = gSecondReplayingChild.lastMajorCheckpointPreceding(id);
-  return (firstMajor < secondMajor)
-         ? gSecondReplayingChild
-         : gFirstReplayingChild;
+// After the debugger resumes, find the point where it should pause next.
+async function finishResume() {
+  assert(gPauseMode == PauseModes.RESUMING_FORWARD ||
+         gPauseMode == PauseModes.RESUMING_BACKWARD);
+  const forward = gPauseMode == PauseModes.RESUMING_FORWARD;
+
+  let startCheckpoint = gPausePoint.checkpoint;
+  if (!forward && !gPausePoint.position) {
+    startCheckpoint--;
+  }
+  startCheckpoint = getSavedCheckpoint(startCheckpoint);
+
+  let checkpoint = startCheckpoint;
+  for (;; forward ? checkpoint++ : checkpoint--) {
+    if (checkpoint == gMainChild.pauseCheckpoint()) {
+      // We searched the entire space forward to the end of the recording and
+      // didn't find any breakpoint hits, so resume recording.
+      assert(forward);
+      setPauseState(PauseModes.RUNNING, null, gMainChild);
+      maybeResumeRecording();
+      return;
+    }
+
+    if (checkpoint == InvalidCheckpointId) {
+      // We searched backward to the beginning of the recording, so restore the
+      // first checkpoint.
+      assert(!forward);
+      setReplayingPauseTarget(checkpointExecutionPoint(FirstCheckpointId));
+      return;
+    }
+
+    if (!gCheckpoints[checkpoint].owner) {
+      continue;
+    }
+
+    let hits = [];
+
+    // Find any breakpoint hits in this region of the recording.
+    for (const bp of gBreakpoints) {
+      if (canFindHits(bp)) {
+        const bphits = await findHits(checkpoint, bp);
+        hits = hits.concat(bphits);
+      }
+    }
+
+    // When there are stepping breakpoints, look for breakpoint hits in the
+    // steps for the current frame.
+    if (checkpoint == startCheckpoint && hasSteppingBreakpoint()) {
+      const steps = await findFrameSteps(gPausePoint);
+      hits = hits.concat(steps.filter(point => {
+        return gBreakpoints.some(bp => positionSubsumes(bp, point.position));
+      }));
+    }
+
+    if (forward) {
+      hits = hits.filter(p => pointPrecedes(gPausePoint, p));
+    } else {
+      hits = hits.filter(p => pointPrecedes(p, gPausePoint));
+    }
+
+    if (hits.length) {
+      // We've found the point where the search should end.
+      hits.sort((a, b) => forward ? pointPrecedes(b, a) : pointPrecedes(a, b));
+      setReplayingPauseTarget(hits[0]);
+      return;
+    }
+  }
+}
+
+// Unpause the active child and asynchronously pause at the next or previous
+// breakpoint hit.
+function resume(forward) {
+  if (gActiveChild.recording) {
+    if (forward) {
+      maybeResumeRecording();
+      return;
+    }
+  }
+  if (gPausePoint.checkpoint == FirstCheckpointId && !gPausePoint.position && !forward) {
+    gDebugger._onPause();
+    return;
+  }
+  setPauseState(forward ? PauseModes.RESUMING_FORWARD : PauseModes.RESUMING_BACKWARD,
+                gActiveChild.pausePoint(), null);
+  finishResume();
+  pokeChildren();
+}
+
+// Synchronously bring the active child to the specified execution point.
+function timeWarp(point) {
+  setReplayingPauseTarget(point);
+  while (gPauseMode != PauseModes.PAUSED) {
+    gActiveChild.waitUntilPaused();
+    pokeChildren();
+  }
+  Services.cpmm.sendAsyncMessage("TimeWarpFinished");
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// Logpoints
+////////////////////////////////////////////////////////////////////////////////
+
+// All installed logpoints. Logpoints are given to us by the debugger, after
+// which we need to asynchronously send a child to every point where the
+// logpoint's position is reached, evaluate code there and invoke the callback
+// associated with the logpoint.
+const gLogpoints = [];
+
+// Asynchronously invoke a logpoint's callback with all results from hitting
+// the logpoint in the range of the recording covered by checkpoint.
+async function findLogpointHits(checkpoint, { position, text, condition, callback }) {
+  const hits = await findHits(checkpoint, position);
+  const child = ownerChild(checkpoint);
+  for (const point of hits) {
+    await child.sendManifestAsync({
+      contents() {
+        return { kind: "hitLogpoint", text, condition };
+      },
+      onFinished(child, { result }) {
+        if (result) {
+          callback(point, gDebugger._convertCompletionValue(result));
+        }
+        child.divergedFromRecording = true;
+      },
+    }, point);
+  }
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 // Saving Recordings
 ////////////////////////////////////////////////////////////////////////////////
 
-// Synchronously flush the recording to disk.
-function flushRecording() {
-  assert(gActiveChild.recording && gActiveChild.paused);
-
-  // All replaying children must be paused while the recording is flushed.
-  for (const child of gChildren) {
-    if (child && !child.recording) {
-      child.waitUntilPaused();
-    }
+// Resume manifests are sent when the main child is sent forward through the
+// recording. Update state according to new data produced by the resume.
+function handleResumeManifestResponse({ point, duration, consoleMessages, scripts }) {
+  if (!point.position) {
+    addCheckpoint(point.checkpoint - 1, duration);
+    getCheckpointInfo(point.checkpoint).point = point;
   }
 
-  gActiveChild.sendFlushRecording();
-
-  // Clear out pauseNeeded state set by any earlier maybeFlushRecording().
-  for (const child of gChildren) {
-    if (child && !child.recording) {
-      child.pauseNeeded = false;
-      child.pokeSoon();
-    }
+  if (gDebugger && gDebugger.onConsoleMessage) {
+    consoleMessages.forEach(msg => gDebugger.onConsoleMessage(msg));
   }
 
-  // After flushing the recording there may be more search results.
-  maybeResumeSearch();
-
-  gLastRecordingCheckpoint = gActiveChild.lastCheckpoint();
-
-  // We now have a usable recording for replaying children.
-  if (!gFirstReplayingChild) {
-    spawnInitialReplayingChildren();
+  if (gDebugger && gDebugger.onNewScript) {
+    scripts.forEach(script => gDebugger.onNewScript(script));
   }
 }
 
-// Get the replaying children to pause, and flush the recording if they already
-// are.
-function maybeFlushRecording() {
-  assert(gActiveChild.recording && gActiveChild.paused);
+// If necessary, continue executing in the main child.
+function maybeResumeRecording() {
+  if (gActiveChild != gMainChild) {
+    return;
+  }
 
-  let allPaused = true;
-  for (const child of gChildren) {
-    if (child && !child.recording) {
-      child.pauseNeeded = true;
-      allPaused &= child.paused;
-    }
+  if (timeSinceCheckpoint(gLastFlushCheckpoint) >= FlushMs) {
+    ensureFlushed();
   }
 
-  if (allPaused) {
-    flushRecording();
-    return true;
+  const checkpoint = gMainChild.pausePoint().checkpoint;
+  if (!gMainChild.recording && checkpoint == gRecordingEndpoint) {
+    ensureFlushed();
+    Services.cpmm.sendAsyncMessage("HitRecordingEndpoint");
+    if (gDebugger) {
+      gDebugger._onPause();
+    }
+    return;
+  }
+  gMainChild.sendManifest({
+    contents: { kind: "resume", breakpoints: gBreakpoints },
+    onFinished(response) {
+      handleResumeManifestResponse(response);
+
+      gPausePoint = gMainChild.pausePoint();
+      if (gDebugger) {
+        gDebugger._onPause();
+      } else {
+        Services.tm.dispatchToMainThread(maybeResumeRecording);
+      }
+    },
+  });
+}
+
+// If necessary, synchronously flush the recording to disk.
+function ensureFlushed() {
+  assert(gActiveChild == gMainChild);
+  gMainChild.waitUntilPaused(true);
+
+  if (gLastFlushCheckpoint == gActiveChild.pauseCheckpoint()) {
+    return;
   }
-  return false;
+
+  if (gMainChild.recording) {
+    gMainChild.sendManifest({
+      contents: { kind: "flushRecording" },
+      onFinished() {},
+    });
+    gMainChild.waitUntilPaused();
+  }
+
+  const oldFlushCheckpoint = gLastFlushCheckpoint || FirstCheckpointId;
+  gLastFlushCheckpoint = gMainChild.pauseCheckpoint();
+
+  // We now have a usable recording for replaying children, so spawn them if
+  // necessary.
+  if (gReplayingChildren.length == 0) {
+    spawnReplayingChildren();
+  }
+
+  // Checkpoints where the recording was flushed to disk are always saved.
+  // This allows the recording to be scanned as soon as it has been flushed.
+  addSavedCheckpoint(gLastFlushCheckpoint);
+
+  // Flushing creates a new region of the recording for replaying children
+  // to scan.
+  forSavedCheckpointsInRange(oldFlushCheckpoint, gLastFlushCheckpoint, checkpoint => {
+    scanRecording(checkpoint);
+
+    // Scan for breakpoint and search hits in this new region.
+    gBreakpoints.forEach(position => findHits(checkpoint, position));
+    gLogpoints.forEach(logpoint => findLogpointHits(checkpoint, logpoint));
+  });
+
+  pokeChildren();
 }
 
 // eslint-disable-next-line no-unused-vars
 function BeforeSaveRecording() {
-  if (gActiveChild.recording) {
-    // The recording might not be up to date, flush it now.
-    gActiveChild.waitUntilPaused(true);
-    flushRecording();
+  if (gActiveChild == gMainChild) {
+    // The recording might not be up to date, ensure it flushes after pausing.
+    ensureFlushed();
   }
 }
 
 // eslint-disable-next-line no-unused-vars
 function AfterSaveRecording() {
   Services.cpmm.sendAsyncMessage("SaveRecordingFinished");
 }
 
+let gRecordingEndpoint;
+
+function setMainChild() {
+  assert(!gMainChild.recording);
+
+  gMainChild.sendManifest({
+    contents: { kind: "setMainChild" },
+    onFinished({ endpoint }) {
+      gRecordingEndpoint = endpoint;
+      Services.tm.dispatchToMainThread(maybeResumeRecording);
+    },
+  });
+}
+
 ////////////////////////////////////////////////////////////////////////////////
 // Child Management
 ////////////////////////////////////////////////////////////////////////////////
 
-function spawnReplayingChild(role) {
-  const id = RecordReplayControl.spawnReplayingChild();
-  return new ChildProcess(id, false, role);
-}
+// How many replaying children to spawn. This should be a pref instead...
+const NumReplayingChildren = 4;
 
-function spawnInitialReplayingChildren() {
-  gFirstReplayingChild = spawnReplayingChild(gRecordingChild
-                                             ? new ChildRoleStandby()
-                                             : new ChildRoleActive());
-  gSecondReplayingChild = spawnReplayingChild(new ChildRoleStandby());
-
-  assignMajorCheckpoint(gSecondReplayingChild, FirstCheckpointId);
+function spawnReplayingChildren() {
+  for (let i = 0; i < NumReplayingChildren; i++) {
+    const id = RecordReplayControl.spawnReplayingChild();
+    gReplayingChildren[id] = new ChildProcess(id, false);
+  }
+  addSavedCheckpoint(FirstCheckpointId);
 }
 
 // eslint-disable-next-line no-unused-vars
 function Initialize(recordingChildId) {
   try {
     if (recordingChildId != undefined) {
-      gRecordingChild = new ChildProcess(recordingChildId, true,
-                                         new ChildRoleActive());
+      gMainChild = new ChildProcess(recordingChildId, true);
     } else {
       // If there is no recording child, we have now initialized enough state
       // that we can start spawning replaying children.
-      spawnInitialReplayingChildren();
+      const id = RecordReplayControl.spawnReplayingChild();
+      gMainChild = new ChildProcess(id, false);
+      spawnReplayingChildren();
     }
+    gActiveChild = gMainChild;
     return gControl;
   } catch (e) {
     dump(`ERROR: Initialize threw exception: ${e}\n`);
   }
 }
 
 // eslint-disable-next-line no-unused-vars
-function HitExecutionPoint(id, msg) {
+function ManifestFinished(id, response) {
   try {
-    dumpv(`HitExecutionPoint #${id} ${JSON.stringify(msg)}`);
-    gChildren[id].hitExecutionPoint(msg);
+    dumpv(`ManifestFinished #${id} ${JSON.stringify(response)}`);
+    lookupChild(id).manifestFinished(response);
   } catch (e) {
-    dump(`ERROR: HitExecutionPoint threw exception: ${e}\n`);
-  }
-}
-
-///////////////////////////////////////////////////////////////////////////////
-// Explicit Pauses
-///////////////////////////////////////////////////////////////////////////////
-
-// At the last time the active child was explicitly paused, the ID of the
-// checkpoint that needs to be saved for the child to rewind.
-let gLastExplicitPause = FirstCheckpointId;
-
-// Returns a checkpoint if the active child is explicitly paused somewhere,
-// has started rewinding after being explicitly paused, or is attempting to
-// warp to an execution point. Standby roles will try to save minor checkpoints
-// in the range from their most recent major checkpoint up to the returned
-// checkpoint.
-function getActiveChildTargetCheckpoint() {
-  if (gActiveChild.rewindTargetCheckpoint() <= gLastExplicitPause) {
-    return gActiveChild.rewindTargetCheckpoint();
+    dump(`ERROR: ManifestFinished threw exception: ${e} ${e.stack}\n`);
   }
-  return undefined;
-}
-
-function markExplicitPause() {
-  assert(gActiveChild.paused);
-  const targetCheckpoint = gActiveChild.rewindTargetCheckpoint();
-
-  if (gActiveChild.recording) {
-    // Make sure any replaying children can play forward to the same point as
-    // the recording.
-    flushRecording();
-  } else if (RecordReplayControl.canRewind()) {
-    // Make sure we have a replaying child that has saved the right checkpoints
-    // for rewinding from this point. Switch to the other one if (a) this process
-    // is responsible for rewinding from this point, and (b) this process has
-    // not saved all minor checkpoints going back to its last major checkpoint.
-    if (gActiveChild ==
-        replayingChildResponsibleForSavingCheckpoint(targetCheckpoint)) {
-      if (!gActiveChild.canRewindFrom(targetCheckpoint)) {
-        switchActiveChild(otherReplayingChild(gActiveChild));
-      }
-    }
-  }
-
-  gLastExplicitPause = targetCheckpoint;
-  dumpv(`MarkActiveChildExplicitPause ${gLastExplicitPause}`);
-
-  pokeChildren();
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 // Debugger Operations
 ////////////////////////////////////////////////////////////////////////////////
 
-function maybeSendRepaintMessage() {
-  // In repaint stress mode, we want to trigger a repaint at every checkpoint,
-  // so before resuming after the child pauses at each checkpoint, send it a
-  // repaint message. There might not be a debugger open, so manually craft the
-  // same message which the debugger would send to trigger a repaint and parse
-  // the result.
-  if (RecordReplayControl.inRepaintStressMode()) {
-    maybeSwitchToReplayingChild();
-    const rv = gActiveChild.sendRequest({ type: "repaint" });
-    if ("width" in rv && "height" in rv) {
-      RecordReplayControl.hadRepaint(rv.width, rv.height);
-    }
-  }
-}
+// From the debugger's perspective, there is a single target to interact with,
+// represented by gActiveChild. The details of the various children the control
+// system is managing are hidden away. This object describes the interface which
+// the debugger uses to access the control system.
+const gControl = {
+  // Get the current point where the active child is paused, or null.
+  pausePoint() {
+    return gActiveChild && gActiveChild.paused ? gActiveChild.pausePoint() : null;
+  },
 
-function waitUntilChildHasSavedCheckpoint(child, checkpoint) {
-  while (true) {
-    child.waitUntilPaused();
-    if (child.hasSavedCheckpoint(checkpoint)) {
-      return;
-    }
-    child.role.poke();
-  }
-}
+  // Return whether the active child is currently recording.
+  childIsRecording() {
+    return gActiveChild && gActiveChild.recording;
+  },
 
-function resume(forward) {
-  assert(gActiveChild.paused);
-
-  maybeSendRepaintMessage();
+  // Ensure the active child is paused.
+  waitUntilPaused() {
+    // The debugger should not use this method while we are actively resuming.
+    assert(gActiveChild);
 
-  if (!forward) {
-    const targetCheckpoint = gActiveChild.rewindTargetCheckpoint();
-
-    // Don't rewind if we are at the beginning of the recording.
-    if (targetCheckpoint == InvalidCheckpointId) {
-      Services.cpmm.sendAsyncMessage("HitRecordingBeginning");
-      gDebugger._onPause(gActiveChild.lastPausePoint);
+    if (gActiveChild == gMainChild) {
+      gActiveChild.waitUntilPaused(true);
       return;
     }
 
-    // Make sure the active child has saved minor checkpoints prior to its
-    // position.
-    const targetChild =
-      replayingChildResponsibleForSavingCheckpoint(targetCheckpoint);
-    if (targetChild == gActiveChild) {
-      // markExplicitPause() should ensure that we are only active if the child
-      // has saved the appropriate minor checkpoints.
-      assert(gActiveChild.canRewindFrom(targetCheckpoint));
-    } else {
-      let saveTarget = targetCheckpoint;
-      while (!targetChild.isMajorCheckpoint(saveTarget) &&
-             !targetChild.isMinorCheckpoint(saveTarget)) {
-        saveTarget--;
-      }
-      waitUntilChildHasSavedCheckpoint(targetChild, saveTarget);
-      switchActiveChild(targetChild);
-    }
-  }
-
-  if (forward) {
-    // Don't send a replaying process past the recording endpoint.
-    if (gActiveChild.lastPauseAtRecordingEndpoint) {
-      // Look for a recording child we can transition into.
-      assert(!gActiveChild.recording);
-      if (!gRecordingChild) {
-        Services.cpmm.sendAsyncMessage("HitRecordingEndpoint");
-        if (gDebugger) {
-          gDebugger._onPause(gActiveChild.lastPausePoint);
-        }
+    while (true) {
+      gActiveChild.waitUntilPaused();
+      if (pointEquals(gActiveChild.pausePoint(), gPausePoint)) {
         return;
       }
+      pokeChild(gActiveChild);
+    }
+  },
 
-      // Switch to the recording child as the active child and continue
-      // execution.
-      switchActiveChild(gRecordingChild);
+  // Add a breakpoint where the active child should pause while resuming.
+  addBreakpoint(position) {
+    gBreakpoints.push(position);
+
+    // Start searching for breakpoint hits in the recording immediately.
+    if (canFindHits(position)) {
+      forSavedCheckpointsInRange(FirstCheckpointId, gLastFlushCheckpoint, checkpoint => {
+        findHits(checkpoint, position);
+      });
     }
 
-    gActiveChild.ensureMajorCheckpointSaved(gActiveChild.lastCheckpoint() + 1);
-
-    // Idle children might change their behavior as we run forward.
-    pokeChildren();
-  }
-
-  gActiveChild.sendResume({ forward });
-}
-
-let gTimeWarpInProgress;
-
-function timeWarp(targetPoint) {
-  assert(gActiveChild.paused);
-  const targetCheckpoint = targetPoint.checkpoint;
-
-  // Find the replaying child responsible for saving the target checkpoint.
-  const targetChild =
-    replayingChildResponsibleForSavingCheckpoint(targetCheckpoint);
-  if (targetChild != gActiveChild) {
-    switchActiveChild(otherReplayingChild(gActiveChild));
-  }
+    if (gActiveChild == gMainChild) {
+      // The recording child will update its breakpoints when it reaches the
+      // next checkpoint, so force it to create a checkpoint now.
+      gActiveChild.waitUntilPaused(true);
+    }
+  },
 
-  // Rewind first if the child is past the warp target or if it is not paused
-  // at a checkpoint. RunToPoint can only be used when the child is at a
-  // checkpoint.
-  let restoreTarget;
-  if (gActiveChild.lastCheckpoint() >= targetCheckpoint) {
-    restoreTarget = targetCheckpoint;
-  } else if (gActiveChild.lastPausePoint.position) {
-    restoreTarget = gActiveChild.lastPausePoint.checkpoint;
-  }
-
-  if (restoreTarget) {
-    while (!gActiveChild.hasSavedCheckpoint(restoreTarget)) {
-      restoreTarget--;
-    }
-
-    assert(!gTimeWarpInProgress);
-    gTimeWarpInProgress = true;
-
-    gActiveChild.sendRestoreCheckpoint(restoreTarget);
-    gActiveChild.waitUntilPaused();
-
-    gTimeWarpInProgress = false;
-  }
-
-  gActiveChild.sendRunToPoint(targetPoint);
-  gActiveChild.waitUntilPaused();
-
-  Services.cpmm.sendAsyncMessage("TimeWarpFinished");
-}
-
-const gControl = {
-  pausePoint() { return gActiveChild.paused ? gActiveChild.lastPausePoint : null; },
-  childIsRecording() { return gActiveChild.recording; },
-  waitUntilPaused() {
-    // Use a loop because the active child can change while running if a
-    // replaying active child hits the end of the recording.
-    while (!gActiveChild.paused) {
+  // Clear all installed breakpoints.
+  clearBreakpoints() {
+    gBreakpoints.length = 0;
+    if (gActiveChild == gMainChild) {
+      // As for addBreakpoint(), update the active breakpoints in the recording
+      // child immediately.
       gActiveChild.waitUntilPaused(true);
     }
   },
-  addBreakpoint(pos) { gActiveChild.sendAddBreakpoint(pos); },
-  clearBreakpoints() { gActiveChild.sendClearBreakpoints(); },
-  sendRequest(request) { return gActiveChild.sendDebuggerRequest(request); },
-  markExplicitPause,
-  maybeSwitchToReplayingChild,
-  resume,
-  timeWarp,
-};
 
-////////////////////////////////////////////////////////////////////////////////
-// Search Operations
-////////////////////////////////////////////////////////////////////////////////
-
-let gSearchChild;
-
-function ChildRoleSearch() {}
-
-ChildRoleSearch.prototype = {
-  name: "Search",
-
-  initialize(child, { startup }) {
-    this.child = child;
+  // Get the last known point in the recording.
+  recordingEndpoint() {
+    return gMainChild.lastPausePoint;
   },
 
-  hitExecutionPoint({ point, recordingEndpoint }) {
-    if (point.position) {
-      gDebugger._onSearchPause(point);
-    }
+  // If the active child is currently recording, switch to a replaying one if
+  // possible.
+  maybeSwitchToReplayingChild() {
+    assert(gActiveChild.paused);
+    if (gActiveChild == gMainChild && RecordReplayControl.canRewind()) {
+      const point = gActiveChild.pausePoint();
 
-    if (!recordingEndpoint) {
-      this.child.pokeSoon();
+      if (point.position) {
+        // We can only flush the recording at checkpoints, so we need to send the
+        // main child forward and pause/flush ASAP.
+        gMainChild.sendManifest({
+          contents: { kind: "resume", breakpoints: [] },
+          onFinished(response) {
+            handleResumeManifestResponse(response);
+          },
+        });
+        gMainChild.waitUntilPaused(true);
+      }
+
+      ensureFlushed();
+      pauseReplayingChild(point);
     }
   },
 
-  poke() {
-    if (!this.child.pauseNeeded) {
-      this.child.sendResume({ forward: true });
-    }
-  },
-};
-
-function ensureHasSearchChild() {
-  if (!gSearchChild) {
-    gSearchChild = spawnReplayingChild(new ChildRoleSearch());
-  }
-}
+  // Synchronously send a debugger request to a paused active child, returning
+  // the response.
+  sendRequest(request) {
+    let data;
+    gActiveChild.sendManifest({
+      contents: { kind: "debuggerRequest", request },
+      onFinished(finishData) { data = finishData; },
+    });
+    gActiveChild.waitUntilPaused();
 
-function maybeResumeSearch() {
-  if (gSearchChild && gSearchChild.paused) {
-    gSearchChild.sendResume({ forward: true });
-  }
-}
+    if (data.restoredCheckpoint) {
+      // The child had an unhandled recording diverge and restored an earlier
+      // checkpoint. Restore the child to the point it should be paused at and
+      // fill its paused state back in by resending earlier debugger requests.
+      pauseReplayingChild(gPausePoint);
+      gActiveChild.sendManifest({
+        contents: { kind: "batchDebuggerRequest", requests: gDebuggerRequests },
+        onFinished(finishData) { assert(!finishData.restoredCheckpoint); },
+      });
+      gActiveChild.waitUntilPaused();
+      return { unhandledDivergence: true };
+    }
 
-const gSearchControl = {
-  reset() {
-    ensureHasSearchChild();
-    gSearchChild.waitUntilPaused();
+    if (data.divergedFromRecording) {
+      // Remember whether the child diverged from the recording.
+      gActiveChild.divergedFromRecording = true;
+    }
 
-    if (gSearchChild.lastPausePoint.checkpoint != FirstCheckpointId ||
-        gSearchChild.lastPausePoint.position) {
-      gSearchChild.sendRestoreCheckpoint(FirstCheckpointId);
-      gSearchChild.waitUntilPaused();
-    }
-    gSearchChild.sendClearBreakpoints();
-    gDebugger._forEachSearch(pos => gSearchChild.sendAddBreakpoint(pos));
-    gSearchChild.sendResume({ forward: true });
+    gDebuggerRequests.push(request);
+    return data.response;
   },
 
-  sendRequest(request) { return gSearchChild.sendDebuggerRequest(request); },
+  // Synchronously send a debugger request to the main child, which will always
+  // be at the end of the recording and can receive requests even when the
+  // active child is not currently paused.
+  sendRequestMainChild(request) {
+    gMainChild.waitUntilPaused(true);
+    let data;
+    gMainChild.sendManifest({
+      contents: { kind: "debuggerRequest", request },
+      onFinished(finishData) { data = finishData; },
+    });
+    gMainChild.waitUntilPaused();
+    assert(!data.restoredCheckpoint && !data.divergedFromRecording);
+    return data.response;
+  },
+
+  resume,
+  timeWarp,
+
+  // Add a new logpoint.
+  addLogpoint(logpoint) {
+    gLogpoints.push(logpoint);
+    forSavedCheckpointsInRange(FirstCheckpointId, gLastFlushCheckpoint,
+                               checkpoint => findLogpointHits(checkpoint, logpoint));
+  },
 };
 
 ///////////////////////////////////////////////////////////////////////////////
 // Utilities
 ///////////////////////////////////////////////////////////////////////////////
 
 // eslint-disable-next-line no-unused-vars
 function ConnectDebugger(dbg) {
   gDebugger = dbg;
   dbg._control = gControl;
-  dbg._searchControl = gSearchControl;
 }
 
 function dumpv(str) {
-  //dump("[ReplayControl] " + str + "\n");
+  //dump(`[ReplayControl] ${str}\n`);
 }
 
 function assert(v) {
   if (!v) {
     ThrowError("Assertion Failed!");
   }
 }
 
 function ThrowError(msg)
 {
   const error = new Error(msg);
-  dump("ReplayControl Server Error: " + msg + " Stack: " + error.stack + "\n");
+  dump(`ReplayControl Server Error: ${msg} Stack: ${error.stack}\n`);
   throw error;
 }
 
 // eslint-disable-next-line no-unused-vars
 var EXPORTED_SYMBOLS = [
   "Initialize",
   "ConnectDebugger",
-  "HitExecutionPoint",
+  "ManifestFinished",
   "BeforeSaveRecording",
   "AfterSaveRecording",
 ];
--- a/devtools/server/actors/replay/debugger.js
+++ b/devtools/server/actors/replay/debugger.js
@@ -15,16 +15,20 @@
 // created in the middleman process, and describe things that exist in the
 // recording/replaying process, inspecting them via the interface provided by
 // control.js.
 
 "use strict";
 
 const RecordReplayControl = !isWorker && require("RecordReplayControl");
 const Services = require("Services");
+const ChromeUtils = require("ChromeUtils");
+
+ChromeUtils.defineModuleGetter(this, "positionSubsumes",
+                               "resource://devtools/shared/execution-point-utils.js");
 
 ///////////////////////////////////////////////////////////////////////////////
 // ReplayDebugger
 ///////////////////////////////////////////////////////////////////////////////
 
 // Possible preferred directions of travel.
 const Direction = {
   FORWARD: "FORWARD",
@@ -37,17 +41,16 @@ function ReplayDebugger() {
   if (existing) {
     // There is already a ReplayDebugger in existence, use that. There can only
     // be one ReplayDebugger in the process.
     return existing;
   }
 
   // We should have been connected to control.js by the call above.
   assert(this._control);
-  assert(this._searchControl);
 
   // Preferred direction of travel when not explicitly resumed.
   this._direction = Direction.NONE;
 
   // All breakpoint positions and handlers installed by this debugger.
   this._breakpoints = [];
 
   // All ReplayDebuggerFramees that have been created while paused at the
@@ -71,19 +74,16 @@ function ReplayDebugger() {
 
   // Flag set if the dispatched _performPause() call can be ignored because the
   // server entered a thread-wide pause first.
   this._cancelPerformPause = false;
 
   // After we are done pausing, callback describing how to resume.
   this._resumeCallback = null;
 
-  // Information about all searches that exist.
-  this._searches = [];
-
   // Handler called when hitting the beginning/end of the recording, or when
   // a time warp target has been reached.
   this.replayingOnForcedPause = null;
 
   // Handler called when the child pauses for any reason.
   this.replayingOnPositionChange = null;
 }
 
@@ -96,62 +96,76 @@ ReplayDebugger.prototype = {
   // General methods
   /////////////////////////////////////////////////////////
 
   replaying: true,
 
   canRewind: RecordReplayControl.canRewind,
 
   replayCurrentExecutionPoint() {
-    assert(this._paused);
+    this._ensurePaused();
     return this._control.pausePoint();
   },
 
   replayRecordingEndpoint() {
-    return this._sendRequest({ type: "recordingEndpoint" });
+    return this._control.recordingEndpoint();
   },
 
   replayIsRecording() {
     return this._control.childIsRecording();
   },
 
   addDebuggee() {},
   removeAllDebuggees() {},
 
   replayingContent(url) {
-    this._ensurePaused();
-    return this._sendRequest({ type: "getContent", url });
+    return this._sendRequestMainChild({ type: "getContent", url });
+  },
+
+  _processResponse(request, response, divergeResponse) {
+    dumpv(`SendRequest: ${JSON.stringify(request)} -> ${JSON.stringify(response)}`);
+    if (response.exception) {
+      ThrowError(response.exception);
+    }
+    if (response.unhandledDivergence) {
+      if (divergeResponse) {
+        return divergeResponse;
+      }
+      ThrowError(`Unhandled recording divergence in ${request.type}`);
+    }
+    return response;
   },
 
   // Send a request object to the child process, and synchronously wait for it
-  // to respond.
-  _sendRequest(request) {
-    const data = this._control.sendRequest(request);
-    dumpv("SendRequest: " +
-          JSON.stringify(request) + " -> " + JSON.stringify(data));
-    if (data.exception) {
-      ThrowError(data.exception);
-    }
-    return data;
+  // to respond. divergeResponse must be specified for requests that can diverge
+  // from the recording and which we want to recover gracefully.
+  _sendRequest(request, divergeResponse) {
+    const response = this._control.sendRequest(request);
+    return this._processResponse(request, response, divergeResponse);
   },
 
   // Send a request that requires the child process to perform actions that
   // diverge from the recording. In such cases we want to be interacting with a
   // replaying process (if there is one), as recording child processes won't
   // provide useful responses to such requests.
-  _sendRequestAllowDiverge(request) {
+  _sendRequestAllowDiverge(request, divergeResponse) {
     this._control.maybeSwitchToReplayingChild();
-    return this._sendRequest(request);
+    return this._sendRequest(request, divergeResponse);
+  },
+
+  _sendRequestMainChild(request) {
+    const response = this._control.sendRequestMainChild(request);
+    return this._processResponse(request, response);
   },
 
   // Update graphics according to the current state of the child process. This
   // should be done anytime we pause and allow the user to interact with the
   // debugger.
   _repaint() {
-    const rv = this._sendRequestAllowDiverge({ type: "repaint" });
+    const rv = this._sendRequestAllowDiverge({ type: "repaint" }, {});
     if ("width" in rv && "height" in rv) {
       RecordReplayControl.hadRepaint(rv.width, rv.height);
     } else {
       RecordReplayControl.hadRepaintFailure();
     }
   },
 
   /////////////////////////////////////////////////////////
@@ -255,17 +269,17 @@ ReplayDebugger.prototype = {
     const point = this.replayCurrentExecutionPoint();
     dumpv("PerformPause " + JSON.stringify(point));
 
     if (!point.position) {
       // We paused at a checkpoint, and there are no handlers to call.
     } else {
       // Call any handlers for this point, unless one resumes execution.
       for (const { handler, position } of this._breakpoints) {
-        if (RecordReplayControl.positionSubsumes(position, point.position)) {
+        if (positionSubsumes(position, point.position)) {
           handler();
           assert(!this._threadPauseCount);
           if (this._resumeCallback) {
             break;
           }
         }
       }
     }
@@ -292,19 +306,16 @@ ReplayDebugger.prototype = {
   },
 
   replayPushThreadPause() {
     // The thread has paused so that the user can interact with it. The child
     // will stay paused until this thread-wide pause has been popped.
     assert(this._paused);
     assert(!this._resumeCallback);
     if (++this._threadPauseCount == 1) {
-      // Save checkpoints near the current position in case the user rewinds.
-      this._control.markExplicitPause();
-
       // There is no preferred direction of travel after an explicit pause.
       this._direction = Direction.NONE;
 
       // Update graphics according to the current state of the child.
       this._repaint();
 
       // If breakpoint handlers for the pause haven't been called yet, don't
       // call them at all.
@@ -391,88 +402,31 @@ ReplayDebugger.prototype = {
       this._getObject(data.id)._names = names;
     }
 
     for (const frame of pauseData.frames) {
       this._frames[frame.index] = new ReplayDebuggerFrame(this, frame);
     }
   },
 
-  /////////////////////////////////////////////////////////
-  // Search management
-  /////////////////////////////////////////////////////////
-
-  _forEachSearch(callback) {
-    for (const { position } of this._searches) {
-      callback(position);
-    }
-  },
-
   _virtualConsoleLog(position, text, condition, callback) {
-    this._searches.push({ position, text, condition, callback, results: [] });
-    this._searchControl.reset();
-  },
-
-  _evaluateVirtualConsoleLog(search) {
-    const frameData = this._searchControl.sendRequest({
-      type: "getFrame",
-      index: NewestFrameIndex,
-    });
-    if (!("index" in frameData)) {
-      return null;
-    }
-    if (search.condition) {
-      const rv = this._searchControl.sendRequest({
-        type: "frameEvaluate",
-        index: frameData.index,
-        text: search.condition,
-        convertOptions: { snapshot: true },
-      });
-      const crv = this._convertCompletionValue(rv);
-      if ("return" in crv && !crv.return) {
-        return null;
-      }
-    }
-    const rv = this._searchControl.sendRequest({
-      type: "frameEvaluate",
-      index: frameData.index,
-      text: search.text,
-      convertOptions: { snapshot: true },
-    });
-    return this._convertCompletionValue(rv);
-  },
-
-  _onSearchPause(point) {
-    for (const search of this._searches) {
-      if (RecordReplayControl.positionSubsumes(search.position, point.position)) {
-        if (!search.results.some(existing => point.progress == existing.progress)) {
-          search.results.push(point);
-
-          const evaluateResult = this._evaluateVirtualConsoleLog(search);
-          if (evaluateResult) {
-            search.callback(point, evaluateResult);
-          }
-        }
-      }
-    }
+    this._control.addLogpoint({ position, text, condition, callback });
   },
 
   /////////////////////////////////////////////////////////
   // Breakpoint management
   /////////////////////////////////////////////////////////
 
   _setBreakpoint(handler, position, data) {
-    this._ensurePaused();
     dumpv("AddBreakpoint " + JSON.stringify(position));
     this._control.addBreakpoint(position);
     this._breakpoints.push({handler, position, data});
   },
 
   _clearMatchingBreakpoints(callback) {
-    this._ensurePaused();
     const newBreakpoints = this._breakpoints.filter(bp => !callback(bp));
     if (newBreakpoints.length != this._breakpoints.length) {
       dumpv("ClearBreakpoints");
       this._control.clearBreakpoints();
       for (const { position } of newBreakpoints) {
         dumpv("AddBreakpoint " + JSON.stringify(position));
         this._control.addBreakpoint(position);
       }
@@ -535,36 +489,36 @@ ReplayDebugger.prototype = {
     return this._scripts[data.id];
   },
 
   _convertScriptQuery(query) {
     // Make a copy of the query, converting properties referring to debugger
     // things into their associated ids.
     const rv = Object.assign({}, query);
     if ("global" in query) {
-      rv.global = query.global._data.id;
+      // Script queries might be sent to a different process from the one which
+      // is paused at the current point and which we are interacting with.
+      NYI();
     }
     if ("source" in query) {
       rv.source = query.source._data.id;
     }
     return rv;
   },
 
   findScripts(query) {
-    this._ensurePaused();
-    const data = this._sendRequest({
+    const data = this._sendRequestMainChild({
       type: "findScripts",
       query: this._convertScriptQuery(query),
     });
     return data.map(script => this._addScript(script));
   },
 
   findAllConsoleMessages() {
-    this._ensurePaused();
-    const messages = this._sendRequest({ type: "findConsoleMessages" });
+    const messages = this._sendRequestMainChild({ type: "findConsoleMessages" });
     return messages.map(this._convertConsoleMessage.bind(this));
   },
 
   /////////////////////////////////////////////////////////
   // ScriptSource methods
   /////////////////////////////////////////////////////////
 
   _getSource(id) {
@@ -578,18 +532,17 @@ ReplayDebugger.prototype = {
   _addSource(data) {
     if (!this._scriptSources[data.id]) {
       this._scriptSources[data.id] = new ReplayDebuggerScriptSource(this, data);
     }
     return this._scriptSources[data.id];
   },
 
   findSources() {
-    this._ensurePaused();
-    const data = this._sendRequest({ type: "findSources" });
+    const data = this._sendRequestMainChild({ type: "findSources" });
     return data.map(source => this._addSource(source));
   },
 
   adoptSource(source) {
     assert(source._dbg == this);
     return source;
   },
 
@@ -713,64 +666,22 @@ ReplayDebugger.prototype = {
     }
     return message;
   },
 
   /////////////////////////////////////////////////////////
   // Handlers
   /////////////////////////////////////////////////////////
 
-  _getNewScript() {
-    return this._addScript(this._sendRequest({ type: "getNewScript" }));
-  },
-
-  get onNewScript() { return this._breakpointKindGetter("NewScript"); },
-  set onNewScript(handler) {
-    this._breakpointKindSetter("NewScript", handler,
-                               () => handler.call(this, this._getNewScript()));
-  },
-
   get onEnterFrame() { return this._breakpointKindGetter("EnterFrame"); },
   set onEnterFrame(handler) {
     this._breakpointKindSetter("EnterFrame", handler,
                                () => { handler.call(this, this.getNewestFrame()); });
   },
 
-  get replayingOnPopFrame() {
-    return this._searchBreakpoints(({position, data}) => {
-      return (position.kind == "OnPop" && !position.script) ? data : null;
-    });
-  },
-
-  set replayingOnPopFrame(handler) {
-    if (handler) {
-      this._setBreakpoint(() => {
-        this._capturePauseData();
-        handler.call(this, this.getNewestFrame());
-      }, { kind: "OnPop" }, handler);
-    } else {
-      this._clearMatchingBreakpoints(({position}) => {
-        return position.kind == "OnPop" && !position.script;
-      });
-    }
-  },
-
-  getNewConsoleMessage() {
-    const message = this._sendRequest({ type: "getNewConsoleMessage" });
-    return this._convertConsoleMessage(message);
-  },
-
-  get onConsoleMessage() {
-    return this._breakpointKindGetter("ConsoleMessage");
-  },
-  set onConsoleMessage(handler) {
-    this._breakpointKindSetter("ConsoleMessage", handler,
-                               () => handler.call(this, this.getNewConsoleMessage()));
-  },
-
   clearAllBreakpoints: NYI,
 
 }; // ReplayDebugger.prototype
 
 ///////////////////////////////////////////////////////////////////////////////
 // ReplayDebuggerScript
 ///////////////////////////////////////////////////////////////////////////////
 
@@ -786,18 +697,17 @@ ReplayDebuggerScript.prototype = {
   get startLine() { return this._data.startLine; },
   get lineCount() { return this._data.lineCount; },
   get source() { return this._dbg._getSource(this._data.sourceId); },
   get sourceStart() { return this._data.sourceStart; },
   get sourceLength() { return this._data.sourceLength; },
   get format() { return this._data.format; },
 
   _forward(type, value) {
-    this._dbg._ensurePaused();
-    return this._dbg._sendRequest({ type, id: this._data.id, value });
+    return this._dbg._sendRequestMainChild({ type, id: this._data.id, value });
   },
 
   getLineOffsets(line) { return this._forward("getLineOffsets", line); },
   getOffsetLocation(pc) { return this._forward("getOffsetLocation", pc); },
   getSuccessorOffsets(pc) { return this._forward("getSuccessorOffsets", pc); },
   getPredecessorOffsets(pc) { return this._forward("getPredecessorOffsets", pc); },
   getAllColumnOffsets() { return this._forward("getAllColumnOffsets"); },
   getPossibleBreakpoints(query) {
@@ -901,17 +811,17 @@ ReplayDebuggerFrame.prototype = {
   get live() { return true; },
 
   eval(text, options) {
     const rv = this._dbg._sendRequestAllowDiverge({
       type: "frameEvaluate",
       index: this._data.index,
       text,
       options,
-    });
+    }, { throw: "Recording divergence in frameEvaluate" });
     return this._dbg._convertCompletionValue(rv);
   },
 
   _positionMatches(position, kind) {
     return position.kind == kind
         && position.script == this._data.script
         && position.frameIndex == this._data.index;
   },
@@ -1058,17 +968,17 @@ ReplayDebuggerObject.prototype = {
     this._ensureProperties();
     return this._convertPropertyDescriptor(this._properties[name]);
   },
 
   _ensureProperties() {
     if (!this._properties) {
       const id = this._data.id;
       this._properties =
-        this._dbg._sendRequestAllowDiverge({ type: "getObjectProperties", id });
+        this._dbg._sendRequestAllowDiverge({ type: "getObjectProperties", id }, []);
     }
   },
 
   _convertPropertyDescriptor(desc) {
     if (!desc) {
       return undefined;
     }
     const rv = Object.assign({}, desc);
@@ -1128,17 +1038,17 @@ ReplayDebuggerObject.prototype = {
     thisv = this._dbg._convertValueForChild(thisv);
     args = (args || []).map(v => this._dbg._convertValueForChild(v));
 
     const rv = this._dbg._sendRequestAllowDiverge({
       type: "objectApply",
       id: this._data.id,
       thisv,
       args,
-    });
+    }, { throw: "Recording divergence in objectApply" });
     return this._dbg._convertCompletionValue(rv);
   },
 
   get allocationSite() { NYI(); },
   get errorMessageName() { NYI(); },
   get errorNotes() { NYI(); },
   get errorLineNumber() { NYI(); },
   get errorColumnNumber() { NYI(); },
@@ -1198,17 +1108,17 @@ ReplayDebuggerEnvironment.prototype = {
   get callee() { return this._dbg._getObject(this._data.callee); },
   get optimizedOut() { return this._data.optimizedOut; },
 
   _ensureNames() {
     if (!this._names) {
       const names = this._dbg._sendRequestAllowDiverge({
         type: "getEnvironmentNames",
         id: this._data.id,
-      });
+      }, []);
       this._names = {};
       names.forEach(({ name, value }) => {
         this._names[name] = this._dbg._convertValue(value);
       });
     }
   },
 
   names() {
--- a/devtools/server/actors/replay/replay.js
+++ b/devtools/server/actors/replay/replay.js
@@ -1,29 +1,29 @@
 /* -*- indent-tabs-mode: nil; js-indent-level: 2; js-indent-level: 2 -*- */
 /* vim: set ft=javascript ts=2 et sw=2 tw=80: */
 /* 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/. */
-/* eslint-disable spaced-comment, brace-style, indent-legacy */
+/* eslint-disable spaced-comment, brace-style, indent-legacy, consistent-return */
 
 // This file defines the logic that runs in the record/replay devtools sandbox.
 // This code is loaded into all recording/replaying processes, and responds to
 // requests and other instructions from the middleman via the exported symbols
 // defined at the end of this file.
 //
 // Like all other JavaScript in the recording/replaying process, this code's
 // state is included in memory snapshots and reset when checkpoints are
 // restored. In the process of handling the middleman's requests, however, its
 // state may vary between recording and replaying, or between different
 // replays. As a result, we have to be very careful about performing operations
 // that might interact with the recording --- any time we enter the debuggee
 // and evaluate code or perform other operations.
-// The RecordReplayControl.maybeDivergeFromRecording function should be used at
-// any point where such interactions might occur.
+// The divergeFromRecording function should be used at any point where such
+// interactions might occur.
 // eslint-disable spaced-comment
 
 "use strict";
 
 const CC = Components.Constructor;
 
 // Create a sandbox with the resources we need. require() doesn't work here.
 const sandbox = Cu.Sandbox(CC("@mozilla.org/systemprincipal;1", "nsIPrincipal")(), {
@@ -65,21 +65,26 @@ dbg.onNewGlobalObject = function(global)
 ///////////////////////////////////////////////////////////////////////////////
 // Utilities
 ///////////////////////////////////////////////////////////////////////////////
 
 const dump = RecordReplayControl.dump;
 
 function assert(v) {
   if (!v) {
-    dump("Assertion Failed: " + (new Error()).stack + "\n");
+    dump(`Assertion Failed: ${Error().stack}\n`);
     throw new Error("Assertion Failed!");
   }
 }
 
+function throwError(v) {
+  dump(`Error: ${v}\n`);
+  throw new Error(v);
+}
+
 // Bidirectional map between objects and IDs.
 function IdMap() {
   this._idToObject = [ undefined ];
   this._objectToId = new Map();
 }
 
 IdMap.prototype = {
   add(object) {
@@ -99,20 +104,16 @@ IdMap.prototype = {
     return this._idToObject[id];
   },
 
   forEach(callback) {
     for (let i = 1; i < this._idToObject.length; i++) {
       callback(i, this._idToObject[i]);
     }
   },
-
-  lastId() {
-    return this._idToObject.length - 1;
-  },
 };
 
 function countScriptFrames() {
   let count = 0;
   let frame = dbg.getNewestFrame();
   while (frame) {
     if (considerScript(frame.script)) {
       count++;
@@ -149,16 +150,19 @@ function isNonNullObject(obj) {
 // this table (like all JS state) is included in snapshots, rolled back when
 // rewinding, and so forth.  In debuggee time, this table only grows (there is
 // no way to remove entries). Scripts created for debugger activity (e.g. eval)
 // are ignored, and off thread compilation is disabled, so this table acquires
 // the same scripts in the same order as we roll back and run forward in the
 // recording.
 const gScripts = new IdMap();
 
+// Any scripts added since the last checkpoint.
+const gNewScripts = [];
+
 function addScript(script) {
   gScripts.add(script);
   script.getChildScripts().forEach(addScript);
 }
 
 // Association between Debugger.ScriptSources and their IDs. As for gScripts,
 // the indices assigned to a script source are consistent across all replays
 // and rewinding.
@@ -191,17 +195,19 @@ dbg.onNewScript = function(script) {
   addScript(script);
   addScriptSource(script.source);
 
   // Each onNewScript call advances the progress counter, to preserve the
   // ProgressCounter invariant when onNewScript is called multiple times
   // without executing any scripts.
   RecordReplayControl.advanceProgressCounter();
 
-  hitGlobalHandler("NewScript");
+  if (gManifest.kind == "resume") {
+    gNewScripts.push(getScriptData(gScripts.getId(script)));
+  }
 
   // Check in case any handlers we need to install are on the scripts just
   // created.
   installPendingHandlers();
 };
 
 ///////////////////////////////////////////////////////////////////////////////
 // Object Snapshots
@@ -246,58 +252,59 @@ function makeObjectSnapshot(object) {
     properties: Object.entries(getObjectProperties(object)).map(snapshotObjectProperty),
   };
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 // Console Message State
 ///////////////////////////////////////////////////////////////////////////////
 
+// All console messages that have been generated.
 const gConsoleMessages = [];
 
+// Any new console messages since the last checkpoint.
+const gNewConsoleMessages = [];
+
 function newConsoleMessage(messageType, executionPoint, contents) {
-  // Each new console message advances the progress counter, to make sure
-  // that different messages have different progress values.
-  RecordReplayControl.advanceProgressCounter();
-
   if (!executionPoint) {
-    executionPoint =
-      RecordReplayControl.currentExecutionPoint({ kind: "ConsoleMessage" });
+    executionPoint = currentScriptedExecutionPoint();
   }
 
   contents.messageType = messageType;
   contents.executionPoint = executionPoint;
   gConsoleMessages.push(contents);
 
-  hitGlobalHandler("ConsoleMessage");
+  if (gManifest.kind == "resume") {
+    gNewConsoleMessages.push(contents);
+  }
 }
 
 function convertStack(stack) {
   if (stack) {
     const { source, line, column, functionDisplayName } = stack;
     const parent = convertStack(stack.parent);
     return { source, line, column, functionDisplayName, parent };
   }
   return null;
 }
 
+// Map from warp target values attached to messages to the associated execution
+// point.
+const gWarpTargetPoints = [ null ];
+
 // Listen to all console messages in the process.
 Services.console.registerListener({
   QueryInterface: ChromeUtils.generateQI([Ci.nsIConsoleListener]),
 
   observe(message) {
     if (message instanceof Ci.nsIScriptError) {
-      // If there is a warp target associated with the execution point, use
-      // that. This will take users to the point where the error was originally
-      // generated, rather than where it was reported to the console.
-      let executionPoint;
-      if (message.timeWarpTarget) {
-        executionPoint =
-          RecordReplayControl.timeWarpTargetExecutionPoint(message.timeWarpTarget);
-      }
+      // If there is a warp target associated with the error, use that. This
+      // will take users to the point where the error was originally generated,
+      // rather than where it was reported to the console.
+      const executionPoint = gWarpTargetPoints[message.timeWarpTarget];
 
       const contents = JSON.parse(JSON.stringify(message));
       contents.stack = convertStack(message.stack);
       newConsoleMessage("PageError", executionPoint, contents);
     }
   },
 });
 
@@ -321,16 +328,51 @@ Services.obs.addObserver({
         return convertValue(makeDebuggeeValue(v), { snapshot: true });
       });
     }
 
     newConsoleMessage("ConsoleAPI", null, contents);
   },
 }, "console-api-log-event");
 
+// eslint-disable-next-line no-unused-vars
+function NewTimeWarpTarget() {
+  // Create a counter which will be associated with the current scripted
+  // location if we want to warp here later.
+  gWarpTargetPoints.push(currentScriptedExecutionPoint());
+  return gWarpTargetPoints.length - 1;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+// Recording Scanning
+///////////////////////////////////////////////////////////////////////////////
+
+const gScannedScripts = new Set();
+
+function startScanningScript(script) {
+  const id = gScripts.getId(script);
+  const offsets = script.getPossibleBreakpointOffsets();
+  let lastFrame = null, lastFrameIndex = 0;
+  for (const offset of offsets) {
+    const handler = {
+      hit(frame) {
+        let frameIndex;
+        if (frame == lastFrame) {
+          frameIndex = lastFrameIndex;
+        } else {
+          lastFrame = frame;
+          lastFrameIndex = frameIndex = countScriptFrames() - 1;
+        }
+        RecordReplayControl.addScriptHit(id, offset, frameIndex);
+      },
+    };
+    script.setBreakpoint(offset, handler);
+  }
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 // Position Handler State
 ///////////////////////////////////////////////////////////////////////////////
 
 // Position kinds we are expected to hit.
 let gPositionHandlerKinds = Object.create(null);
 
 // Handlers we tried to install but couldn't due to a script not existing.
@@ -342,59 +384,58 @@ const gPendingPcHandlers = [];
 
 // Script/offset pairs where we have installed a breakpoint handler. We have to
 // avoid installing duplicate handlers here because they will both be called.
 const gInstalledPcHandlers = [];
 
 // Callbacks to test whether a frame should have an OnPop handler.
 const gOnPopFilters = [];
 
-// eslint-disable-next-line no-unused-vars
-function ClearPositionHandlers() {
+function clearPositionHandlers() {
   dbg.clearAllBreakpoints();
   dbg.onEnterFrame = undefined;
 
   gPositionHandlerKinds = Object.create(null);
   gPendingPcHandlers.length = 0;
   gInstalledPcHandlers.length = 0;
   gOnPopFilters.length = 0;
 }
 
 function installPendingHandlers() {
   const pending = gPendingPcHandlers.map(position => position);
   gPendingPcHandlers.length = 0;
 
-  pending.forEach(EnsurePositionHandler);
+  pending.forEach(ensurePositionHandler);
 }
 
 // Hit a position with the specified kind if we are expected to. This is for
 // use with position kinds that have no script/offset/frameIndex information.
-function hitGlobalHandler(kind) {
+function hitGlobalHandler(kind, frame) {
   if (gPositionHandlerKinds[kind]) {
-    RecordReplayControl.positionHit({ kind });
+    positionHit({ kind }, frame);
   }
 }
 
 // The completion state of any frame that is being popped.
 let gPopFrameResult = null;
 
 function onPopFrame(completion) {
   gPopFrameResult = completion;
-  RecordReplayControl.positionHit({
+  positionHit({
     kind: "OnPop",
     script: gScripts.getId(this.script),
     frameIndex: countScriptFrames() - 1,
   });
   gPopFrameResult = null;
 }
 
 function onEnterFrame(frame) {
-  hitGlobalHandler("EnterFrame");
+  if (considerScript(frame.script)) {
+    hitGlobalHandler("EnterFrame", frame);
 
-  if (considerScript(frame.script)) {
     gOnPopFilters.forEach(filter => {
       if (filter(frame)) {
         frame.onPop = onPopFrame;
       }
     });
   }
 }
 
@@ -406,17 +447,17 @@ function addOnPopFilter(filter) {
     }
     frame = frame.older;
   }
 
   gOnPopFilters.push(filter);
   dbg.onEnterFrame = onEnterFrame;
 }
 
-function EnsurePositionHandler(position) {
+function ensurePositionHandler(position) {
   gPositionHandlerKinds[position.kind] = true;
 
   switch (position.kind) {
   case "Break":
   case "OnStep":
     let debugScript;
     if (position.script) {
       debugScript = gScripts.getObject(position.script);
@@ -433,54 +474,36 @@ function EnsurePositionHandler(position)
       return script == position.script && offset == position.offset;
     };
     if (gInstalledPcHandlers.some(match)) {
       return;
     }
     gInstalledPcHandlers.push({ script: position.script, offset: position.offset });
 
     debugScript.setBreakpoint(position.offset, {
-      hit() {
-        RecordReplayControl.positionHit({
+      hit(frame) {
+        positionHit({
           kind: "OnStep",
           script: position.script,
           offset: position.offset,
           frameIndex: countScriptFrames() - 1,
-        });
+        }, frame);
       },
     });
     break;
   case "OnPop":
-    if (position.script) {
-      addOnPopFilter(frame => gScripts.getId(frame.script) == position.script);
-    } else {
-      addOnPopFilter(frame => true);
-    }
+    assert(position.script);
+    addOnPopFilter(frame => gScripts.getId(frame.script) == position.script);
     break;
   case "EnterFrame":
     dbg.onEnterFrame = onEnterFrame;
     break;
   }
 }
 
-// eslint-disable-next-line no-unused-vars
-function GetEntryPosition(position) {
-  if (position.kind == "Break" || position.kind == "OnStep") {
-    const script = gScripts.getObject(position.script);
-    if (script) {
-      return {
-        kind: "Break",
-        script: position.script,
-        offset: script.mainOffset,
-      };
-    }
-  }
-  return null;
-}
-
 ///////////////////////////////////////////////////////////////////////////////
 // Paused State
 ///////////////////////////////////////////////////////////////////////////////
 
 let gPausedObjects = new IdMap();
 let gDereferencedObjects = new Map();
 
 function getObjectId(obj) {
@@ -529,17 +552,17 @@ function convertedValueIsObject(value) {
 
 function convertCompletionValue(value, options) {
   if ("return" in value) {
     return { return: convertValue(value.return, options) };
   }
   if ("throw" in value) {
     return { throw: convertValue(value.throw, options) };
   }
-  throw new Error("Unexpected completion value");
+  throwError("Unexpected completion value");
 }
 
 // Convert a value we received from the parent.
 function convertValueFromParent(value) {
   if (isNonNullObject(value)) {
     if (value.object) {
       return gPausedObjects.getObject(value.object);
     }
@@ -581,31 +604,338 @@ function getDebuggeeValue(value) {
 
 // eslint-disable-next-line no-unused-vars
 function ClearPausedState() {
   gPausedObjects = new IdMap();
   gDereferencedObjects = new Map();
 }
 
 ///////////////////////////////////////////////////////////////////////////////
+// Manifest Management
+///////////////////////////////////////////////////////////////////////////////
+
+// The manifest that is currently being processed.
+let gManifest;
+
+// When processing "resume" manifests this tracks the execution time when we
+// started execution from the initial checkpoint.
+let gTimeWhenResuming;
+
+// Handlers that run when a manifest is first received. This must be specified
+// for all manifests.
+const gManifestStartHandlers = {
+  resume({ breakpoints }) {
+    RecordReplayControl.resumeExecution();
+    gTimeWhenResuming = RecordReplayControl.currentExecutionTime();
+    breakpoints.forEach(ensurePositionHandler);
+  },
+
+  restoreCheckpoint({ target }) {
+    RecordReplayControl.restoreCheckpoint(target);
+    throwError("Unreachable!");
+  },
+
+  runToPoint({ needSaveCheckpoints }) {
+    for (const checkpoint of needSaveCheckpoints) {
+      RecordReplayControl.saveCheckpoint(checkpoint);
+    }
+    RecordReplayControl.resumeExecution();
+  },
+
+  scanRecording(manifest) {
+    gManifestStartHandlers.runToPoint(manifest);
+  },
+
+  findHits({ position, startpoint, endpoint }) {
+    const { kind, script, offset, frameIndex: bpFrameIndex } = position;
+    const hits = [];
+    const allHits = RecordReplayControl.findScriptHits(script, offset);
+    for (const { checkpoint, progress, frameIndex } of allHits) {
+      if (checkpoint >= startpoint && checkpoint < endpoint) {
+        switch (kind) {
+        case "OnStep":
+          if (bpFrameIndex != frameIndex) {
+            continue;
+          }
+          // FALLTHROUGH
+        case "Break":
+          hits.push({
+            checkpoint,
+            progress,
+            position: { kind: "OnStep", script, offset, frameIndex },
+          });
+        }
+      }
+    }
+    RecordReplayControl.manifestFinished(hits);
+  },
+
+  findFrameSteps({ entryPoint }) {
+    assert(entryPoint.position.kind == "EnterFrame");
+    const frameIndex = countScriptFrames() - 1;
+    const script = getFrameData(frameIndex).script;
+    const offsets = gScripts.getObject(script).getPossibleBreakpointOffsets();
+    for (const offset of offsets) {
+      ensurePositionHandler({ kind: "OnStep", script, offset, frameIndex });
+    }
+    ensurePositionHandler({ kind: "EnterFrame" });
+    ensurePositionHandler({ kind: "OnPop", script, frameIndex });
+
+    gFrameSteps = [ entryPoint ];
+    gFrameStepsFrameIndex = frameIndex;
+    RecordReplayControl.resumeExecution();
+  },
+
+  flushRecording() {
+    RecordReplayControl.flushRecording();
+    RecordReplayControl.manifestFinished();
+  },
+
+  setMainChild() {
+    const endpoint = RecordReplayControl.setMainChild();
+    RecordReplayControl.manifestFinished({ endpoint });
+  },
+
+  debuggerRequest({ request }) {
+    const response = processRequest(request);
+    RecordReplayControl.manifestFinished({
+      response,
+      divergedFromRecording: gDivergedFromRecording,
+    });
+  },
+
+  batchDebuggerRequest({ requests }) {
+    for (const request of requests) {
+      processRequest(request);
+    }
+    RecordReplayControl.manifestFinished();
+  },
+
+  hitLogpoint({ text, condition }) {
+    divergeFromRecording();
+
+    const frame = scriptFrameForIndex(countScriptFrames() - 1);
+    if (condition) {
+      const crv = frame.eval(condition);
+      if ("return" in crv && !crv.return) {
+        RecordReplayControl.manifestFinished({ result: null });
+        return;
+      }
+    }
+
+    const rv = frame.eval(text);
+    const converted = convertCompletionValue(rv, { snapshot: true });
+    RecordReplayControl.manifestFinished({ result: converted });
+  },
+};
+
+// eslint-disable-next-line no-unused-vars
+function ManifestStart(manifest) {
+  try {
+    gManifest = manifest;
+
+    if (gManifestStartHandlers[manifest.kind]) {
+      gManifestStartHandlers[manifest.kind](manifest);
+    } else {
+      dump(`Unknown manifest: ${JSON.stringify(manifest)}\n`);
+    }
+  } catch (e) {
+    printError("ManifestStart", e);
+  }
+}
+
+// eslint-disable-next-line no-unused-vars
+function BeforeCheckpoint() {
+  clearPositionHandlers();
+  gScannedScripts.clear();
+}
+
+const FirstCheckpointId = 1;
+
+// The most recent encountered checkpoint.
+let gLastCheckpoint;
+
+function currentExecutionPoint(position) {
+  const checkpoint = gLastCheckpoint;
+  const progress = RecordReplayControl.progressCounter();
+  return { checkpoint, progress, position };
+}
+
+function currentScriptedExecutionPoint() {
+  const numFrames = countScriptFrames();
+  if (!numFrames) {
+    return null;
+  }
+  const frame = getFrameData(numFrames - 1);
+  return currentExecutionPoint({
+    kind: "OnStep",
+    script: frame.script,
+    offset: frame.offset,
+    frameIndex: frame.index,
+  });
+}
+
+// Handlers that run after a checkpoint is reached to see if the manifest has
+// finished. This does not need to be specified for all manifests.
+const gManifestFinishedAfterCheckpointHandlers = {
+  resume(_, point) {
+    RecordReplayControl.manifestFinished({
+      point,
+      duration: RecordReplayControl.currentExecutionTime() - gTimeWhenResuming,
+      consoleMessages: gNewConsoleMessages,
+      scripts: gNewScripts,
+    });
+    gNewConsoleMessages.length = 0;
+    gNewScripts.length = 0;
+  },
+
+  runToPoint({ endpoint }, point) {
+    if (!endpoint.position && point.checkpoint == endpoint.checkpoint) {
+      RecordReplayControl.manifestFinished({ point });
+    }
+  },
+
+  scanRecording({ endpoint }, point) {
+    if (point.checkpoint == endpoint) {
+      RecordReplayControl.manifestFinished({ point });
+    }
+  },
+};
+
+// Handlers that run after a checkpoint is reached and before execution resumes.
+// This does not need to be specified for all manifests. This is specified
+// separately from gManifestFinishedAfterCheckpointHandlers to ensure that if
+// we finish a manifest after the checkpoint and then start a new one, that new
+// one is able to prepare to execute. These handlers must therefore not finish
+// the current manifest.
+const gManifestPrepareAfterCheckpointHandlers = {
+  runToPoint({ endpoint }, point) {
+    if (point.checkpoint == endpoint.checkpoint) {
+      assert(endpoint.position);
+      ensurePositionHandler(endpoint.position);
+    }
+  },
+
+  scanRecording() {
+    dbg.onEnterFrame = frame => {
+      if (considerScript(frame.script) && !gScannedScripts.has(frame.script)) {
+        startScanningScript(frame.script);
+        gScannedScripts.add(frame.script);
+      }
+    };
+  },
+};
+
+function processManifestAfterCheckpoint(point, restoredCheckpoint) {
+  // After rewinding gManifest won't be correct, so we always mark the current
+  // manifest as finished and rely on the middleman to give us a new one.
+  if (restoredCheckpoint) {
+    RecordReplayControl.manifestFinished({
+      restoredCheckpoint,
+      point: currentExecutionPoint(),
+    });
+  }
+
+  if (!gManifest) {
+    // The process is considered to have an initial manifest to run forward to
+    // the first checkpoint.
+    assert(point.checkpoint == FirstCheckpointId);
+    RecordReplayControl.manifestFinished({ point });
+    assert(gManifest);
+  } else if (gManifestFinishedAfterCheckpointHandlers[gManifest.kind]) {
+    gManifestFinishedAfterCheckpointHandlers[gManifest.kind](gManifest, point);
+  }
+
+  if (gManifestPrepareAfterCheckpointHandlers[gManifest.kind]) {
+    gManifestPrepareAfterCheckpointHandlers[gManifest.kind](gManifest, point);
+  }
+}
+
+// eslint-disable-next-line no-unused-vars
+function AfterCheckpoint(id, restoredCheckpoint) {
+  gLastCheckpoint = id;
+  const point = currentExecutionPoint();
+
+  try {
+    processManifestAfterCheckpoint(point, restoredCheckpoint);
+  } catch (e) {
+    printError("AfterCheckpoint", e);
+  }
+}
+
+// In the findFrameSteps manifest, all steps that have been found.
+let gFrameSteps = null;
+
+let gFrameStepsFrameIndex = 0;
+
+// Handlers that run after reaching a position watched by ensurePositionHandler.
+// This must be specified for any manifest that uses ensurePositionHandler.
+const gManifestPositionHandlers = {
+  resume(manifest, point) {
+    RecordReplayControl.manifestFinished({
+      point,
+      consoleMessages: gNewConsoleMessages,
+      scripts: gNewScripts,
+    });
+  },
+
+  runToPoint({ endpoint }, point) {
+    if (point.progress == endpoint.progress &&
+        point.position.frameIndex == endpoint.position.frameIndex) {
+      clearPositionHandlers();
+      RecordReplayControl.manifestFinished({ point });
+    }
+  },
+
+  findFrameSteps(_, point) {
+    switch (point.position.kind) {
+    case "OnStep":
+      gFrameSteps.push(point);
+      break;
+    case "EnterFrame":
+      if (countScriptFrames() == gFrameStepsFrameIndex + 2) {
+        gFrameSteps.push(point);
+      }
+      break;
+    case "OnPop":
+      gFrameSteps.push(point);
+      clearPositionHandlers();
+      RecordReplayControl.manifestFinished({ point, frameSteps: gFrameSteps });
+      break;
+    }
+  },
+};
+
+function positionHit(position, frame) {
+  const point = currentExecutionPoint(position);
+
+  if (gManifestPositionHandlers[gManifest.kind]) {
+    gManifestPositionHandlers[gManifest.kind](gManifest, point);
+  } else {
+    throwError(`Unexpected manifest in positionHit: ${gManifest.kind}`);
+  }
+}
+
+///////////////////////////////////////////////////////////////////////////////
 // Handler Helpers
 ///////////////////////////////////////////////////////////////////////////////
 
 function getScriptData(id) {
   const script = gScripts.getObject(id);
   return {
     id,
     sourceId: gScriptSources.getId(script.source),
     startLine: script.startLine,
     lineCount: script.lineCount,
     sourceStart: script.sourceStart,
     sourceLength: script.sourceLength,
     displayName: script.displayName,
     url: script.url,
     format: script.format,
+    firstBreakpointOffset: script.getPossibleBreakpointOffsets()[0],
   };
 }
 
 function getSourceData(id) {
   const source = gScriptSources.getObject(id);
   const introductionScript = gScripts.getId(source.introductionScript);
   return {
     id: id,
@@ -700,17 +1030,17 @@ function getObjectData(id) {
       kind: "Environment",
       type: object.type,
       parent: getObjectId(object.parent),
       object: object.type == "declarative" ? 0 : getObjectId(object.object),
       callee: getObjectId(object.callee),
       optimizedOut: object.optimizedOut,
     };
   }
-  throw new Error("Unknown object kind");
+  throwError("Unknown object kind");
 }
 
 function getObjectProperties(object) {
   let names;
   try {
     names = object.getOwnPropertyNames();
   } catch (e) {
     return unknownObjectProperties(e.toString());
@@ -916,22 +1246,29 @@ function getPauseData() {
 
   return rv;
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 // Handlers
 ///////////////////////////////////////////////////////////////////////////////
 
+let gDivergedFromRecording = false;
+
+function divergeFromRecording() {
+  RecordReplayControl.divergeFromRecording();
+
+  // This flag can only be unset when we rewind.
+  gDivergedFromRecording = true;
+}
+
 const gRequestHandlers = {
 
   repaint() {
-    if (!RecordReplayControl.maybeDivergeFromRecording()) {
-      return {};
-    }
+    divergeFromRecording();
     return RecordReplayControl.repaint();
   },
 
   /////////////////////////////////////////////////////////
   // Debugger Requests
   /////////////////////////////////////////////////////////
 
   findScripts(request) {
@@ -954,20 +1291,16 @@ const gRequestHandlers = {
     });
     return rv;
   },
 
   getScript(request) {
     return getScriptData(request.id);
   },
 
-  getNewScript(request) {
-    return getScriptData(gScripts.lastId());
-  },
-
   getContent(request) {
     return RecordReplayControl.getContent(request.url);
   },
 
   findSources(request) {
     const sources = [];
     gScriptSources.forEach((id) => {
       sources.push(getSourceData(id));
@@ -979,41 +1312,32 @@ const gRequestHandlers = {
     return getSourceData(request.id);
   },
 
   getObject(request) {
     return getObjectData(request.id);
   },
 
   getObjectProperties(request) {
-    if (!RecordReplayControl.maybeDivergeFromRecording()) {
-      return unknownObjectProperties("Recording divergence in getObjectProperties");
-    }
-
+    divergeFromRecording();
     const object = gPausedObjects.getObject(request.id);
     return getObjectProperties(object);
   },
 
   objectApply(request) {
-    if (!RecordReplayControl.maybeDivergeFromRecording()) {
-      return { throw: "Recording divergence in objectApply" };
-    }
+    divergeFromRecording();
     const obj = gPausedObjects.getObject(request.id);
     const thisv = convertValueFromParent(request.thisv);
     const args = request.args.map(v => convertValueFromParent(v));
     const rv = obj.apply(thisv, args);
     return convertCompletionValue(rv);
   },
 
   getEnvironmentNames(request) {
-    if (!RecordReplayControl.maybeDivergeFromRecording()) {
-      return [{name: "Unknown names",
-               value: "Recording divergence in getEnvironmentNames" }];
-    }
-
+    divergeFromRecording();
     const env = gPausedObjects.getObject(request.id);
     return getEnvironmentNames(env);
   },
 
   getFrame(request) {
     if (request.index == -1 /* NewestFrameIndex */) {
       const numFrames = countScriptFrames();
 
@@ -1023,111 +1347,81 @@ const gRequestHandlers = {
       }
       request.index = numFrames - 1;
     }
 
     return getFrameData(request.index);
   },
 
   pauseData(request) {
-    if (!RecordReplayControl.maybeDivergeFromRecording()) {
-      return { error: "Recording divergence in pauseData" };
-    }
-
+    divergeFromRecording();
     return getPauseData();
   },
 
   getLineOffsets: forwardToScript("getLineOffsets"),
   getOffsetLocation: forwardToScript("getOffsetLocation"),
   getSuccessorOffsets: forwardToScript("getSuccessorOffsets"),
   getPredecessorOffsets: forwardToScript("getPredecessorOffsets"),
   getAllColumnOffsets: forwardToScript("getAllColumnOffsets"),
   getOffsetMetadata: forwardToScript("getOffsetMetadata"),
   getPossibleBreakpoints: forwardToScript("getPossibleBreakpoints"),
   getPossibleBreakpointOffsets: forwardToScript("getPossibleBreakpointOffsets"),
 
   frameEvaluate(request) {
-    if (!RecordReplayControl.maybeDivergeFromRecording()) {
-      return { throw: "Recording divergence in frameEvaluate" };
-    }
-
+    divergeFromRecording();
     const frame = scriptFrameForIndex(request.index);
     const rv = frame.eval(request.text, request.options);
     return convertCompletionValue(rv, request.convertOptions);
   },
 
   popFrameResult(request) {
     return gPopFrameResult ? convertCompletionValue(gPopFrameResult) : {};
   },
 
   findConsoleMessages(request) {
     return gConsoleMessages;
   },
 
-  getNewConsoleMessage(request) {
-    return gConsoleMessages[gConsoleMessages.length - 1];
-  },
-
-  currentExecutionPoint(request) {
-    return RecordReplayControl.currentExecutionPoint();
-  },
-
-  recordingEndpoint(request) {
-    return RecordReplayControl.recordingEndpoint();
-  },
-
   /////////////////////////////////////////////////////////
   // Inspector Requests
   /////////////////////////////////////////////////////////
 
   getFixedObjects(request) {
-    if (!RecordReplayControl.maybeDivergeFromRecording()) {
-      return { throw: "Recording divergence in getWindow" };
-    }
-
+    divergeFromRecording();
     const window = getWindow();
     return {
       window: getObjectId(makeDebuggeeValue(window)),
       document: getObjectId(makeDebuggeeValue(window.document)),
       Services: getObjectId(makeDebuggeeValue(Services)),
       InspectorUtils: getObjectId(makeDebuggeeValue(InspectorUtils)),
       CSSRule: getObjectId(makeDebuggeeValue(CSSRule)),
     };
   },
 
   newDeepTreeWalker(request) {
-    if (!RecordReplayControl.maybeDivergeFromRecording()) {
-      return { throw: "Recording divergence in newDeepTreeWalker" };
-    }
-
+    divergeFromRecording();
     const walker = Cc["@mozilla.org/inspector/deep-tree-walker;1"]
       .createInstance(Ci.inIDeepTreeWalker);
     return { id: getObjectId(makeDebuggeeValue(walker)) };
   },
 
   getObjectPropertyValue(request) {
-    if (!RecordReplayControl.maybeDivergeFromRecording()) {
-      return { throw: "Recording divergence in getObjectPropertyValue" };
-    }
-
+    divergeFromRecording();
     const object = gPausedObjects.getObject(request.id);
 
     try {
       const rv = object.unsafeDereference()[request.name];
       return { "return": convertValue(makeDebuggeeValue(rv)) };
     } catch (e) {
       return { "throw": "" + e };
     }
   },
 
   setObjectPropertyValue(request) {
-    if (!RecordReplayControl.maybeDivergeFromRecording()) {
-      return { throw: "Recording divergence in getObjectPropertyValue" };
-    }
-
+    divergeFromRecording();
     const object = gPausedObjects.getObject(request.id);
     const value = getDebuggeeValue(convertValueFromParent(request.value));
 
     try {
       object.unsafeDereference()[request.name] = value;
       return { "return": request.value };
     } catch (e) {
       return { "throw": "" + e };
@@ -1146,35 +1440,37 @@ const gRequestHandlers = {
     if (!element) {
       return { id: 0 };
     }
     const obj = makeDebuggeeValue(element);
     return { id: getObjectId(obj) };
   },
 };
 
-// eslint-disable-next-line no-unused-vars
-function ProcessRequest(request) {
+function processRequest(request) {
   try {
     if (gRequestHandlers[request.type]) {
       return gRequestHandlers[request.type](request);
     }
     return { exception: "No handler for " + request.type };
   } catch (e) {
-    let msg;
-    try {
-      msg = "" + e + " line " + e.lineNumber;
-    } catch (ee) {
-      msg = "Unknown";
-    }
-    dump("ReplayDebugger Record/Replay Error: " + msg + "\n");
-    return { exception: msg };
+    printError("processRequest", e);
+    return { exception: `Request failed: ${request.type}` };
   }
 }
 
+function printError(why, e) {
+  let msg;
+  try {
+    msg = "" + e + " line " + e.lineNumber;
+  } catch (ee) {
+    msg = "Unknown";
+  }
+  dump(`Record/Replay Error: ${why}: ${msg}\n`);
+}
+
 // eslint-disable-next-line no-unused-vars
 var EXPORTED_SYMBOLS = [
-  "EnsurePositionHandler",
-  "ClearPositionHandlers",
-  "ClearPausedState",
-  "ProcessRequest",
-  "GetEntryPosition",
+  "ManifestStart",
+  "BeforeCheckpoint",
+  "AfterCheckpoint",
+  "NewTimeWarpTarget",
 ];
--- a/devtools/server/actors/replay/rrIControl.idl
+++ b/devtools/server/actors/replay/rrIControl.idl
@@ -6,12 +6,12 @@
 #include "nsISupports.idl"
 
 // This interface defines the methods used for calling into control.js in a
 // middleman process.
 [scriptable, uuid(c296e7c3-8a27-4fd0-94c2-b6e5126909ba)]
 interface rrIControl : nsISupports {
   void Initialize(in jsval recordingChildId);
   void ConnectDebugger(in jsval replayDebugger);
-  void HitExecutionPoint(in long childId, in jsval msg);
+  void ManifestFinished(in long childId, in jsval response);
   void BeforeSaveRecording();
   void AfterSaveRecording();
 };
--- a/devtools/server/actors/replay/rrIReplay.idl
+++ b/devtools/server/actors/replay/rrIReplay.idl
@@ -5,14 +5,13 @@
 
 #include "nsISupports.idl"
 
 // This interface defines the methods used for calling into replay.js in a
 // recording/replaying process. See JSControl.h for the documentation of these
 // methods.
 [scriptable, uuid(8b86b71f-8471-472e-9997-c5f21f9d0598)]
 interface rrIReplay : nsISupports {
-  jsval ProcessRequest(in jsval request);
-  void EnsurePositionHandler(in jsval position);
-  void ClearPositionHandlers();
-  void ClearPausedState();
-  jsval GetEntryPosition(in jsval position);
+  void ManifestStart(in jsval manifest);
+  void BeforeCheckpoint();
+  void AfterCheckpoint(in long checkpoint, in bool restoredCheckpoint);
+  long NewTimeWarpTarget();
 };
new file mode 100644
--- /dev/null
+++ b/devtools/shared/execution-point-utils.js
@@ -0,0 +1,146 @@
+/* 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";
+
+// Utilities for working with execution points and breakpoint positions, which
+// are used when replaying to identify points in the execution where the
+// debugger can stop or where events of interest have occurred.
+//
+// A breakpoint position describes where breakpoints can be installed when
+// replaying, and has the following properties:
+//
+// kind: The kind of breakpoint, which has one of the following values:
+//   "Break": Break at an offset in a script.
+//   "OnStep": Break at an offset in a script with a given frame depth.
+//   "OnPop": Break when a script's frame with a given frame depth is popped.
+//   "EnterFrame": Break when any script is entered.
+//
+// script: For all kinds but "EnterFrame", the ID of the position's script.
+//
+// offset: For "Break" and "OnStep", the offset within the script.
+//
+// frameIndex: For "OnStep" and "OnPop", the index of the topmost script frame.
+//   Indexes start at zero for the first frame pushed, and increase with the
+//   depth of the frame.
+//
+// An execution point is a unique identifier for a point in the recording where
+// the debugger can pause, and has the following properties:
+//
+// checkpoint: ID of the most recent checkpoint.
+//
+// progress: Value of the progress counter when the point is reached.
+//
+// position: Optional breakpoint position where the pause occurs at. This cannot
+//   have the "Break" kind (see below) and is missing if the execution point is
+//   at the checkpoint itself.
+//
+// The above properties must uniquely identify a single point in the recording.
+// This property is ensured mainly through how the progress counter is managed.
+// The position in the point must not be able to execute multiple times without
+// the progress counter being incremented.
+//
+// The progress counter is incremented whenever a frame is pushed onto the stack
+// or a loop entry point is reached. Because it increments when looping, a
+// specific JS frame cannot reach the same position multiple times with the same
+// progress counter. Because it increments when pushing frames, different JS
+// frames with the same frame depth cannot reach the same position multiple
+// times with the same progress counter. The position must specify the frame
+// depth for this argument to hold, so "Break" positions are not used in
+// execution points. They are used when the user-specified breakpoints are being
+// installed, though, and when pausing the execution point will use the
+// appropriate "OnStep" position for the frame depth.
+
+// Return whether pointA happens before pointB in the recording.
+function pointPrecedes(pointA, pointB) {
+  if (pointA.checkpoint != pointB.checkpoint) {
+    return pointA.checkpoint < pointB.checkpoint;
+  }
+  if (pointA.progress != pointB.progress) {
+    return pointA.progress < pointB.progress;
+  }
+
+  const posA = pointA.position;
+  const posB = pointB.position;
+
+  // Except when we're at a checkpoint, all execution points have positions.
+  // Because the progress counter is bumped when executing script, points with
+  // the same checkpoint and progress counter will either both be at that
+  // checkpoint, or both be at an intra-checkpoint point.
+  assert(!!posA == !!posB);
+  if (!posA || positionEquals(posA, posB)) {
+    return false;
+  }
+
+  // If an execution point doesn't have a frame index (i.e. EnterFrame) then it
+  // has bumped the progress counter and predates everything else that is
+  // associated with the same progress counter.
+  if ("frameIndex" in posA != "frameIndex" in posB) {
+    return "frameIndex" in posB;
+  }
+
+  // Only certain execution point kinds do not bump the progress counter.
+  assert(posA.kind == "OnStep" || posA.kind == "OnPop");
+  assert(posB.kind == "OnStep" || posB.kind == "OnPop");
+
+  // Deeper frames predate shallower frames, if the progress counter is the
+  // same. We bump the progress counter when pushing frames, but not when
+  // popping them.
+  assert("frameIndex" in posA && "frameIndex" in posB);
+  if (posA.frameIndex != posB.frameIndex) {
+    return posA.frameIndex > posB.frameIndex;
+  }
+
+  // Within a frame, OnStep points come before OnPop points.
+  if (posA.kind != posB.kind) {
+    return posA.kind == "OnStep";
+  }
+
+  // Earlier script locations predate later script locations.
+  assert("offset" in posA && "offset" in posB);
+  return posA.offset < posB.offset;
+}
+
+// Return whether two execution points are the same.
+// eslint-disable-next-line no-unused-vars
+function pointEquals(pointA, pointB) {
+  return !pointPrecedes(pointA, pointB) && !pointPrecedes(pointB, pointA);
+}
+
+// Return whether two breakpoint positions are the same.
+function positionEquals(posA, posB) {
+  return posA.kind == posB.kind
+      && posA.script == posB.script
+      && posA.offset == posB.offset
+      && posA.frameIndex == posB.frameIndex;
+}
+
+// Return whether an execution point matching posB also matches posA.
+// eslint-disable-next-line no-unused-vars
+function positionSubsumes(posA, posB) {
+  if (positionEquals(posA, posB)) {
+    return true;
+  }
+
+  if (posA.kind == "Break" && posB.kind == "OnStep" &&
+      posA.script == posB.script && posA.offset == posB.offset) {
+    return true;
+  }
+
+  return false;
+}
+
+function assert(v) {
+  if (!v) {
+    dump(`Assertion failed: ${Error().stack}\n`);
+    throw new Error("Assertion failed!");
+  }
+}
+
+this.EXPORTED_SYMBOLS = [
+  "pointPrecedes",
+  "pointEquals",
+  "positionEquals",
+  "positionSubsumes",
+];
--- a/devtools/shared/moz.build
+++ b/devtools/shared/moz.build
@@ -51,16 +51,17 @@ DevToolsModules(
     'content-observer.js',
     'debounce.js',
     'defer.js',
     'deprecated-sync-thenables.js',
     'DevToolsUtils.js',
     'dom-node-constants.js',
     'dom-node-filter-constants.js',
     'event-emitter.js',
+    'execution-point-utils.js',
     'extend.js',
     'flags.js',
     'generate-uuid.js',
     'indentation.js',
     'indexed-db.js',
     'l10n.js',
     'loader-plugin-raw.jsm',
     'Loader.jsm',