const assert = require('assert')
const Random = require('random-seed')
const LocalDocument = require('./helpers/local-document')
const Document = require('../lib/document')
const Peer = require('./helpers/peer')
const {ZERO_POINT} = require('../lib/point-helpers')

suite('Document', () => {
  suite('operations', () => {
    test('concurrent inserts at 0', () => {
      const replica1 = buildDocument(1)
      const replica2 = replicateDocument(2, replica1)

      const ops1 = performInsert(replica1, {row: 0, column: 0}, 'a')
      const ops2 = performInsert(replica2, {row: 0, column: 0}, 'b')
      integrateOperations(replica1, ops2)
      integrateOperations(replica2, ops1)

      assert.equal(replica1.testLocalDocument.text, 'ab')
      assert.equal(replica2.testLocalDocument.text, 'ab')
    })

    test('concurrent inserts at the same position inside a previous insertion', () => {
      const replica1 = buildDocument(1, 'ABCDEFG')
      const replica2 = replicateDocument(2, replica1)

      const ops1 = performInsert(replica1, {row: 0, column: 2}, '+++')
      const ops2 = performInsert(replica2, {row: 0, column: 2}, '***')
      integrateOperations(replica1, ops2)
      integrateOperations(replica2, ops1)

      assert.equal(replica1.testLocalDocument.text, 'AB+++***CDEFG')
      assert.equal(replica2.testLocalDocument.text, 'AB+++***CDEFG')
    })

    test('concurrent inserts at different positions inside a previous insertion', () => {
      const replica1 = buildDocument(1, 'ABCDEFG')
      const replica2 = replicateDocument(2, replica1)

      const ops1 = performInsert(replica1, {row: 0, column: 6}, '+++')
      const ops2 = performInsert(replica2, {row: 0, column: 2}, '***')
      integrateOperations(replica1, ops2)
      integrateOperations(replica2, ops1)

      assert.equal(replica1.testLocalDocument.text, 'AB***CDEF+++G')
      assert.equal(replica2.testLocalDocument.text, 'AB***CDEF+++G')
    })

    test('concurrent overlapping deletions', () => {
      const replica1 = buildDocument(1, 'ABCDEFG')
      const replica2 = replicateDocument(2, replica1)

      const ops1 = performDelete(replica1, {row: 0, column: 2}, {row: 0, column: 5})
      const ops2 = performDelete(replica2, {row: 0, column: 4}, {row: 0, column: 6})
      integrateOperations(replica1, ops2)
      integrateOperations(replica2, ops1)

      assert.equal(replica1.testLocalDocument.text, 'ABG')
      assert.equal(replica2.testLocalDocument.text, 'ABG')
    })

    test('undoing an insertion containing other insertions', () => {
      const replica1 = buildDocument(1)
      const replica2 = replicateDocument(2, replica1)

      const ops1 = performInsert(replica1, {row: 0, column: 0}, 'ABCDEFG')
      integrateOperations(replica2, ops1)

      const ops2 = performInsert(replica1, {row: 0, column: 3}, '***')
      integrateOperations(replica2, ops2)

      const ops1Undo = performUndoOrRedoOperations(replica1, ops1)
      integrateOperations(replica2, ops1Undo)

      assert.equal(replica1.testLocalDocument.text, '***')
      assert.equal(replica2.testLocalDocument.text, '***')
    })

    test('undoing an insertion containing a deletion', () => {
      const replica1 = buildDocument(1)
      const replica2 = replicateDocument(2, replica1)

      const ops1 = performInsert(replica1, {row: 0, column: 0}, 'ABCDEFG')
      integrateOperations(replica2, ops1)

      const ops2 = performDelete(replica1, {row: 0, column: 3}, {row: 0, column: 6})
      integrateOperations(replica2, ops2)

      const ops1Undo = performUndoOrRedoOperations(replica1, ops1)
      integrateOperations(replica2, ops1Undo)

      assert.equal(replica1.testLocalDocument.text, '')
      assert.equal(replica2.testLocalDocument.text, '')
    })

    test('undoing a deletion that overlaps another concurrent deletion', () => {
      const replica1 = buildDocument(1, 'ABCDEFG')
      const replica2 = replicateDocument(2, replica1)

      const ops1 = performDelete(replica1, {row: 0, column: 1}, {row: 0, column: 4})
      const ops2 = performDelete(replica2, {row: 0, column: 3}, {row: 0, column: 6})
      integrateOperations(replica1, ops2)
      integrateOperations(replica2, ops1)
      const ops2Undo = performUndoOrRedoOperations(replica1, ops2)
      integrateOperations(replica2, ops2Undo)

      assert.equal(replica1.testLocalDocument.text, 'AEFG')
      assert.equal(replica2.testLocalDocument.text, 'AEFG')
    })

    test('inserting in the middle of an undone deletion and then redoing the deletion', () => {
      const document = buildDocument(1, 'ABCDEFG')

      const deleteOps = performDelete(document, {row: 0, column: 1}, {row: 0, column: 6})
      performUndoOrRedoOperations(document, deleteOps)
      performInsert(document, {row: 0, column: 3}, '***')
      performUndoOrRedoOperations(document, deleteOps) // Redo

      assert.equal(document.testLocalDocument.text, 'A***G')
    })

    test('applying remote operations generated by a copy of the local replica', () => {
      const localReplica = buildDocument(1)
      const remoteReplica = buildDocument(1)

      integrateOperations(localReplica, performInsert(remoteReplica, {row: 0, column: 0}, 'ABCDEFG'))
      integrateOperations(localReplica, performInsert(remoteReplica, {row: 0, column: 3}, '+++'))
      performInsert(localReplica, {row: 0, column: 1}, '***')

      assert.equal(localReplica.testLocalDocument.text, 'A***BC+++DEFG')
    })

    test('updating marker layers', () => {
      const replica1 = buildDocument(1, 'ABCDEFG')
      const replica2 = replicateDocument(2, replica1)

      const insert1 = performInsert(replica1, {row: 0, column: 6}, '+++')
      performInsert(replica2, {row: 0, column: 2}, '**')
      integrateOperations(replica2, insert1)

      integrateOperations(replica2, performUpdateMarkers(replica1, {
        1: { // Create a marker layer with 1 marker
          1: {
            range: {
              start: {row: 0, column: 1},
              end: {row: 0, column: 9}
            },
            exclusive: false,
            reversed: false,
            tailed: true
          }
        }
      }))
      assert.deepEqual(replica1.getMarkers(), {
        1: { // Site 1
          1: { // Marker layer 1
            1: { // Marker 1
              range: {
                start: {row: 0, column: 1},
                end: {row: 0, column: 9}
              },
              exclusive: false,
              reversed: false,
              tailed: true
            }
          }
        }
      })
      assert.deepEqual(replica2.getMarkers(), {
        1: { // Site 1
          1: { // Marker layer 1
            1: { // Marker 1
              range: {
                start: {row: 0, column: 1},
                end: {row: 0, column: 11}
              },
              exclusive: false,
              reversed: false,
              tailed: true
            }
          }
        }
      })
      assert.deepEqual(replica2.testLocalDocument.markers, replica2.getMarkers())

      integrateOperations(replica2, performUpdateMarkers(replica1, {
        1: {
          1: { // Update marker
            range: {
              start: {row: 0, column: 2},
              end: {row: 0, column: 10}
            },
            exclusive: true,
            reversed: true
          },
          2: { // Create marker (with default values for exclusive, reversed, and tailed)
            range: {
              start: {row: 0, column: 0},
              end: {row: 0, column: 1}
            }
          }
        },
        2: { // Create marker layer with 1 marker
          1: {
            range: {
              start: {row: 0, column: 1},
              end: {row: 0, column: 2}
            }
          }
        }
      }))
      assert.deepEqual(replica1.getMarkers(), {
        1: {
          1: {
            1: {
              range: {
                start: {row: 0, column: 2},
                end: {row: 0, column: 10}
              },
              exclusive: true,
              reversed: true,
              tailed: true
            },
            2: {
              range: {
                start: {row: 0, column: 0},
                end: {row: 0, column: 1}
              },
              exclusive: false,
              reversed: false,
              tailed: true
            }
          },
          2: {
            1: {
              range: {
                start: {row: 0, column: 1},
                end: {row: 0, column: 2}
              },
              exclusive: false,
              reversed: false,
              tailed: true
            }
          }
        }
      })
      assert.deepEqual(replica2.getMarkers(), {
        1: {
          1: {
            1: {
              range: {
                start: {row: 0, column: 4},
                end: {row: 0, column: 12}
              },
              exclusive: true,
              reversed: true,
              tailed: true
            },
            2: {
              range: {
                start: {row: 0, column: 0},
                end: {row: 0, column: 1}
              },
              exclusive: false,
              reversed: false,
              tailed: true
            }
          },
          2: {
            1: {
              range: {
                start: {row: 0, column: 1},
                end: {row: 0, column: 4}
              },
              exclusive: false,
              reversed: false,
              tailed: true
            }
          }
        }
      })
      assert.deepEqual(replica2.testLocalDocument.markers, replica2.getMarkers())

      integrateOperations(replica2, performUpdateMarkers(replica1, {
        1: {
          2: null // Delete marker
        },
        2: null // Delete marker layer
      }))
      assert.deepEqual(replica1.getMarkers(), {
        1: {
          1: {
            1: {
              range: {
                start: {row: 0, column: 2},
                end: {row: 0, column: 10}
              },
              exclusive: true,
              reversed: true,
              tailed: true
            },
          }
        }
      })
      assert.deepEqual(replica2.getMarkers(), {
        1: {
          1: {
            1: {
              range: {
                start: {row: 0, column: 4},
                end: {row: 0, column: 12}
              },
              exclusive: true,
              reversed: true,
              tailed: true
            },
          }
        }
      })
      assert.deepEqual(replica2.testLocalDocument.markers, replica2.getMarkers())
    })

    test('deferring marker updates until the dependencies of their logical ranges arrive', () => {
      const replica1 = buildDocument(1)
      const replica2 = replicateDocument(2, replica1)

      const insertion1 = performInsert(replica1, {row: 0, column: 0}, 'ABCDEFG')
      const insertion2 = performInsert(replica1, {row: 0, column: 4}, 'WXYZ')

      const layerUpdate1 = replica1.updateMarkers({
        1: {
          // This only depends on insertion 1
          1: {
            range: {
              start: {row: 0, column: 1},
              end: {row: 0, column: 3}
            }
          },
          // This depends on insertion 2
          2: {
            range: {
              start: {row: 0, column: 5},
              end: {row: 0, column: 7}
            }
          },
          // This depends on insertion 2 but will be overwritten before
          // insertion 2 arrives at site 2
          3: {
            range: {
              start: {row: 0, column: 5},
              end: {row: 0, column: 7}
            }
          }
        }
      })

      const layerUpdate2 = replica1.updateMarkers({
        1: {
          3: {
            range: {
              start: {row: 0, column: 1},
              end: {row: 0, column: 3}
            }
          }
        }
      })

      replica2.integrateOperations(insertion1)
      {
        const {markerUpdates} = replica2.integrateOperations(layerUpdate1.concat(layerUpdate2))
        assert.deepEqual(markerUpdates, {
          1: {
            1: {
              1: {
                range: {
                  start: {row: 0, column: 1},
                  end: {row: 0, column: 3}
                },
                exclusive: false,
                reversed: false,
                tailed: true
              },
              3: {
                range: {
                  start: {row: 0, column: 1},
                  end: {row: 0, column: 3}
                },
                exclusive: false,
                reversed: false,
                tailed: true
              }
            }
          }
        })
      }

      {
        const {markerUpdates} = replica2.integrateOperations(insertion2)
        assert.deepEqual(markerUpdates, {
          1: {
            1: {
              2: {
                range: {
                  start: {row: 0, column: 5},
                  end: {row: 0, column: 7}
                },
                exclusive: false,
                reversed: false,
                tailed: true
              }
            }
          }
        })
      }
    })
  })

  suite('history', () => {
    test('basic undo and redo', () => {
      const replicaA = buildDocument(1)
      const replicaB = replicateDocument(2, replicaA)

      integrateOperations(replicaB, performInsert(replicaA, {row: 0, column: 0}, 'a1 '))
      integrateOperations(replicaA, performInsert(replicaB, {row: 0, column: 3}, 'b1 '))
      integrateOperations(replicaB, performInsert(replicaA, {row: 0, column: 6}, 'a2 '))
      integrateOperations(replicaA, performInsert(replicaB, {row: 0, column: 9}, 'b2'))
      integrateOperations(replicaA, performSetTextInRange(replicaB, {row: 0, column: 3}, {row: 0, column: 5}, 'b3'))
      assert.equal(replicaA.testLocalDocument.text, 'a1 b3 a2 b2')
      assert.equal(replicaB.testLocalDocument.text, 'a1 b3 a2 b2')

      {
        integrateOperations(replicaA, performUndo(replicaB).operations)
        assert.equal(replicaA.testLocalDocument.text, 'a1 b1 a2 b2')
        assert.equal(replicaB.testLocalDocument.text, 'a1 b1 a2 b2')
      }

      {
        integrateOperations(replicaB, performUndo(replicaA).operations)
        assert.equal(replicaA.testLocalDocument.text, 'a1 b1 b2')
        assert.equal(replicaB.testLocalDocument.text, 'a1 b1 b2')
      }

      {
        integrateOperations(replicaB, performRedo(replicaA).operations)
        assert.equal(replicaA.testLocalDocument.text, 'a1 b1 a2 b2')
        assert.equal(replicaB.testLocalDocument.text, 'a1 b1 a2 b2')
      }

      {
        integrateOperations(replicaA, performRedo(replicaB).operations)
        assert.equal(replicaA.testLocalDocument.text, 'a1 b3 a2 b2')
        assert.equal(replicaB.testLocalDocument.text, 'a1 b3 a2 b2')
      }

      {
        integrateOperations(replicaA, performUndo(replicaB).operations)
        assert.equal(replicaA.testLocalDocument.text, 'a1 b1 a2 b2')
        assert.equal(replicaB.testLocalDocument.text, 'a1 b1 a2 b2')
      }
    })

    test('does not allow the initial text to be undone', () => {
      const document = buildDocument(1, 'hello')
      performInsert(document, {row: 0, column: 5}, ' world')
      assert.notEqual(document.undo(), null)
      assert.equal(document.getText(), 'hello')
      assert.equal(document.undo(), null)
      assert.equal(document.getText(), 'hello')
    })

    test('constructing the document with an initial history state', () => {
      const document = new Document({
        siteId: 1,
        history: {
          nextCheckpointId: 4,
          baseText: 'a ',
          undoStack: [
            {
              type: 'transaction',
              changes: [
                {oldStart: point(0, 2), oldEnd: point(0, 2), newStart: point(0, 2), newEnd: point(0, 4), oldText: '', newText: 'b '}
              ],
              markersBefore: {1: {1: {range: range(point(0, 0), point(0, 2))}}},
              markersAfter: {1: {1: {range: range(point(0, 2), point(0, 4))}}}
            },
            {
              type: 'checkpoint',
              id: 2,
              markers: {1: {1: {range: range(point(0, 2), point(0, 4))}}}
            },
            {
              type: 'transaction',
              changes: [
                {oldStart: point(0, 4), oldEnd: point(0, 4), newStart: point(0, 4), newEnd: point(0, 6), oldText: '', newText: 'c '}
              ],
              markersBefore: {1: {1: {range: range(point(0, 2), point(0, 4))}}},
              markersAfter: {1: {1: {range: range(point(0, 4), point(0, 6))}}}
            }
          ],
          redoStack: [
            {
              type: 'transaction',
              changes: [
                {oldStart: point(0, 0), oldEnd: point(0, 0), newStart: point(0, 0), newEnd: point(0, 2), oldText: '', newText: 'z '},
                {oldStart: point(0, 8), oldEnd: point(0, 8), newStart: point(0, 10), newEnd: point(0, 11), oldText: '', newText: 'e'}
              ],
              markersBefore: {1: {1: {range: range(point(0, 6), point(0, 8))}}},
              markersAfter: {1: {1: {range: range(point(0, 0), point(0, 2))}}}
            },
            {
              type: 'transaction',
              changes: [
                {oldStart: point(0, 6), oldEnd: point(0, 6), newStart: point(0, 6), newEnd: point(0, 8), oldText: '', newText: 'd '}
              ],
              markersBefore: {1: {1: {range: range(point(0, 4), point(0, 6))}}},
              markersAfter: {1: {1: {range: range(point(0, 6), point(0, 8))}}}
            },
            {
              type: 'checkpoint',
              id: 3,
              markers: {1: {1: {range: range(point(0, 4), point(0, 6))}}}
            }
          ]
        }
      })

      assert.equal(document.getText(), 'a b c ')
      {
        const {markers} = document.redo()
        assert.equal(document.getText(), 'a b c d ')
        assert.deepEqual(markers, {1: {1: {range: range(point(0, 6), point(0, 8))}}})
      }
      {
        const {markers} = document.redo()
        assert.equal(document.getText(), 'z a b c d e')
        assert.deepEqual(markers, {1: {1: {range: range(point(0, 0), point(0, 2))}}})
      }
      {
        const {markers} = document.undo()
        assert.equal(document.getText(), 'a b c d ')
        assert.deepEqual(markers, {1: {1: {range: range(point(0, 6), point(0, 8))}}})
      }
      {
        const {markers} = document.undo()
        assert.equal(document.getText(), 'a b c ')
        assert.deepEqual(markers, {1: {1: {range: range(point(0, 4), point(0, 6))}}})
      }
      {
        const {markers} = document.undo()
        assert.equal(document.getText(), 'a b ')
        assert.deepEqual(markers, {1: {1: {range: range(point(0, 2), point(0, 4))}}})
      }
      {
        const {markers} = document.undo()
        assert.equal(document.getText(), 'a ')
        assert.deepEqual(markers, {1: {1: {range: range(point(0, 0), point(0, 2))}}})
      }
      assert(document.undo() == null)
      assert.equal(document.getText(), 'a ')

      // Redo everything
      while (document.redo()) {}

      // Ensure we set the next checkpoint id appropriately
      const checkpoint = document.createCheckpoint()
      assert.equal(checkpoint, 4)

      {
        const {markers} = document.revertToCheckpoint(3)
        assert.equal(document.getText(), 'a b c ')
        assert.deepEqual(markers, {1: {1: {range: range(point(0, 4), point(0, 6))}}})
      }
      {
        const {markers} = document.revertToCheckpoint(2)
        assert.equal(document.getText(), 'a b ')
        assert.deepEqual(markers, {1: {1: {range: range(point(0, 2), point(0, 4))}}})
      }
    })

    test('clearing undo and redo stacks', () => {
      const document = buildDocument(1)
      performInsert(document, {row: 0, column: 0}, 'a')
      document.clearUndoStack()
      performInsert(document, {row: 0, column: 1}, 'b')
      performInsert(document, {row: 0, column: 2}, 'c')
      document.undo()
      document.undo()
      assert.equal(document.getText(), 'a')
      document.redo()
      assert.equal(document.getText(), 'ab')
      document.clearRedoStack()
      document.redo()
      assert.equal(document.getText(), 'ab')

      // Clears the redo stack on changes
      document.undo()
      performInsert(document, {row: 0, column: 1}, 'd')
      assert.equal(document.getText(), 'ad')
      document.redo()
      assert.equal(document.getText(), 'ad')
    })

    test('grouping changes since a checkpoint', () => {
      const replicaA = buildDocument(1)
      const replicaB = replicateDocument(2, replicaA)

      integrateOperations(replicaB, performInsert(replicaA, {row: 0, column: 0}, 'a1 '))
      const checkpoint = replicaA.createCheckpoint({markers: {
        1: {
          1: {range: buildRange(0, 1), exclusive: true, a: 1},
        },
        2: {
          1: {range: buildRange(1, 2), b: 2}
        }
      }})
      integrateOperations(replicaB, performSetTextInRange(replicaA, {row: 0, column: 1}, {row: 0, column: 3}, '2 a3 '))
      integrateOperations(replicaB, performDelete(replicaA, {row: 0, column: 5}, {row: 0, column: 6}))
      integrateOperations(replicaA, performInsert(replicaB, {row: 0, column: 0}, 'b1 '))
      assert.equal(replicaA.testLocalDocument.text, 'b1 a2 a3')
      assert.equal(replicaB.testLocalDocument.text, replicaA.testLocalDocument.text)
      assert.deepEqual(replicaB.testLocalDocument.markers, replicaA.testLocalDocument.markers)

      const changes = replicaA.groupChangesSinceCheckpoint(checkpoint, {
        markers: {
          1: {
            1: {range: buildRange(3, 5), c: 3},
          }
        }
      })

      assert.deepEqual(changes, [
        {
          oldStart: {row: 0, column: 4},
          oldEnd: {row: 0, column: 6},
          oldText: "1 ",
          newStart: {row: 0, column: 4},
          newEnd: {row: 0, column: 8},
          newText: "2 a3"
        }
      ])
      assert.equal(replicaA.testLocalDocument.text, 'b1 a2 a3')
      assert.equal(replicaB.testLocalDocument.text, 'b1 a2 a3')

      {
        const {operations, markers} = performUndo(replicaA)
        integrateOperations(replicaB, operations)
        assert.equal(replicaA.testLocalDocument.text, 'b1 a1 ')
        assert.equal(replicaB.testLocalDocument.text, replicaA.testLocalDocument.text)
        assert.deepEqual(markers, {
          1: {
            1: {range: buildRange(3, 4), exclusive: true, a: 1},
          },
          2: {
            1: {range: buildRange(4, 5), b: 2}
          }
        })
      }

      {
        const {operations, markers} = performRedo(replicaA)
        integrateOperations(replicaB, operations)
        assert.equal(replicaA.testLocalDocument.text, 'b1 a2 a3')
        assert.equal(replicaB.testLocalDocument.text, replicaA.testLocalDocument.text)
        assert.deepEqual(markers, {
          1: {
            1: {range: buildRange(3, 5), c: 3},
          }
        })
      }

      integrateOperations(replicaA, performUndo(replicaB).operations)

      {
        const {operations, markers} = performUndo(replicaA)
        integrateOperations(replicaB, operations)
        assert.equal(replicaA.testLocalDocument.text, 'a1 ')
        assert.equal(replicaB.testLocalDocument.text, replicaA.testLocalDocument.text)
        assert.deepEqual(markers, {
          1: {
            1: {range: buildRange(0, 1), exclusive: true, a: 1},
          },
          2: {
            1: {range: buildRange(1, 2), b: 2}
          }
        })
      }

      // Delete checkpoint
      assert.deepEqual(replicaA.groupChangesSinceCheckpoint(checkpoint, {deleteCheckpoint: true}), [])
      assert.equal(replicaA.groupChangesSinceCheckpoint(checkpoint), false)
    })

    test('does not allow grouping changes past a barrier checkpoint', () => {
      const document = buildDocument(1)

      const checkpointBeforeBarrier = document.createCheckpoint({isBarrier: false})
      performInsert(document, {row: 0, column: 0}, 'a')
      const barrierCheckpoint = document.createCheckpoint({isBarrier: true})
      performInsert(document, {row: 0, column: 1}, 'b')
      assert.equal(document.groupChangesSinceCheckpoint(checkpointBeforeBarrier), false)

      performInsert(document, {row: 0, column: 2}, 'c')
      const checkpointAfterBarrier = document.createCheckpoint({isBarrier: false})
      const changes = document.groupChangesSinceCheckpoint(barrierCheckpoint)
      assert.deepEqual(changes, [
        {
          oldStart: {row: 0, column: 1},
          oldEnd: {row: 0, column: 1},
          oldText: '',
          newStart: {row: 0, column: 1},
          newEnd: {row: 0, column: 3},
          newText: 'bc'
        }
      ])
    })

    test('reverting to a checkpoint', () => {
      const replicaA = buildDocument(1)
      const replicaB = replicateDocument(2, replicaA)

      integrateOperations(replicaB, performInsert(replicaA, {row: 0, column: 0}, 'a1 '))
      const checkpoint = replicaA.createCheckpoint({markers: {
        1: {
          1: {range: buildRange(0, 1), exclusive: true, a: 1},
        },
        2: {
          1: {range: buildRange(1, 2), b: 2}
        }
      }})
      integrateOperations(replicaB, performSetTextInRange(replicaA, {row: 0, column: 1}, {row: 0, column: 3}, '2 a3 '))
      integrateOperations(replicaB, performDelete(replicaA, {row: 0, column: 5}, {row: 0, column: 6}))
      integrateOperations(replicaA, performInsert(replicaB, {row: 0, column: 0}, 'b1 '))

      assert.equal(replicaA.testLocalDocument.text, 'b1 a2 a3')
      assert.equal(replicaB.testLocalDocument.text, replicaA.testLocalDocument.text)

      const {operations, markers} = performRevertToCheckpoint(replicaA, checkpoint)
      integrateOperations(replicaB, operations)
      assert.equal(replicaA.testLocalDocument.text, 'b1 a1 ')
      assert.equal(replicaB.testLocalDocument.text, replicaA.testLocalDocument.text)
      assert.deepEqual(markers, {
        1: {
          1: {range: buildRange(3, 4), exclusive: true, a: 1},
        },
        2: {
          1: {range: buildRange(4, 5), b: 2}
        }
      })

      // Delete checkpoint
      replicaA.revertToCheckpoint(checkpoint, {deleteCheckpoint: true})
      assert.equal(replicaA.revertToCheckpoint(checkpoint), false)
    })

    test('does not allow reverting past a barrier checkpoint', () => {
      const document = buildDocument(1)
      const checkpointBeforeBarrier = document.createCheckpoint({isBarrier: false})
      performInsert(document, {row: 0, column: 0}, 'a')
      document.createCheckpoint({isBarrier: true})

      assert.equal(document.revertToCheckpoint(checkpointBeforeBarrier), false)
      assert.equal(document.getText(), 'a')

      performInsert(document, {row: 0, column: 1}, 'b')
      assert.equal(document.revertToCheckpoint(checkpointBeforeBarrier), false)
      assert.equal(document.getText(), 'ab')
    })

    test('getting changes since a checkpoint', () => {
      const replicaA = buildDocument(1)
      const replicaB = replicateDocument(2, replicaA)

      integrateOperations(replicaB, performInsert(replicaA, {row: 0, column: 0}, 'a1 '))
      const checkpoint = replicaA.createCheckpoint()
      integrateOperations(replicaB, performSetTextInRange(replicaA, {row: 0, column: 1}, {row: 0, column: 3}, '2 a3 '))
      integrateOperations(replicaB, performDelete(replicaA, {row: 0, column: 5}, {row: 0, column: 6}))
      integrateOperations(replicaA, performInsert(replicaB, {row: 0, column: 0}, 'b1 '))
      assert.equal(replicaA.testLocalDocument.text, 'b1 a2 a3')

      const changesSinceCheckpoint = replicaA.getChangesSinceCheckpoint(checkpoint)
      for (const change of changesSinceCheckpoint.reverse()) {
        replicaA.testLocalDocument.setTextInRange(change.newStart, change.newEnd, change.oldText)
      }
      assert.equal(replicaA.testLocalDocument.text, 'b1 a1 ')

      // Ensure we don't modify the undo stack when getting changes since checkpoint (regression).
      assert.deepEqual(replicaA.getChangesSinceCheckpoint(checkpoint), changesSinceCheckpoint)
    })

    test('undoing and redoing an operation that occurred adjacent to a checkpoint', () => {
      const document = buildDocument(1)
      performInsert(document, {row: 0, column: 0}, 'a')
      performInsert(document, {row: 0, column: 1}, 'b')
      document.createCheckpoint()
      performInsert(document, {row: 0, column: 2}, 'c')

      document.undo()
      assert.equal(document.getText(), 'ab')
      document.undo()
      assert.equal(document.getText(), 'a')
      document.redo()
      assert.equal(document.getText(), 'ab')
      document.redo()
      assert.equal(document.getText(), 'abc')
    })

    test('reverting to a checkpoint after undoing and redoing an operation', () => {
      const document = buildDocument(1)

      performInsert(document, {row: 0, column: 0}, 'a')
      const checkpoint1 = document.createCheckpoint()
      performInsert(document, {row: 0, column: 1}, 'b')
      const checkpoint2 = document.createCheckpoint()

      document.undo()
      assert.equal(document.getText(), 'a')
      document.redo()
      assert.equal(document.getText(), 'ab')

      performInsert(document, {row: 0, column: 2}, 'c')

      document.revertToCheckpoint(checkpoint2)
      assert.equal(document.getText(), 'ab')

      document.revertToCheckpoint(checkpoint1)
      assert.equal(document.getText(), 'a')
    })

    test('undoing preserves checkpoint created prior to any operations', () => {
      const document = buildDocument(1)
      const checkpoint = document.createCheckpoint()
      document.undo()
      performInsert(document, {row: 0, column: 0}, 'a')

      document.revertToCheckpoint(checkpoint)
      assert.equal(document.getText(), '')
    })

    test('does not allow undoing past a barrier checkpoint', () => {
      const document = buildDocument(1)
      performInsert(document, {row: 0, column: 0}, 'a')
      performInsert(document, {row: 0, column: 1}, 'b')
      document.createCheckpoint({isBarrier: true})
      performInsert(document, {row: 0, column: 2}, 'c')
      document.createCheckpoint({isBarrier: false})

      assert.equal(document.getText(), 'abc')
      document.undo()
      assert.equal(document.getText(), 'ab')
      assert.equal(document.undo(), null)
      assert.equal(document.getText(), 'ab')
    })

    test('does not add empty transactions to the undo stack', () => {
      const replicaA = buildDocument(1)
      const replicaB = replicateDocument(2, replicaA)
      integrateOperations(replicaB, performInsert(replicaA, {row: 0, column: 0}, 'a'))
      integrateOperations(replicaB, performInsert(replicaA, {row: 0, column: 1}, 'b'))
      const checkpoint = replicaA.createCheckpoint()
      integrateOperations(replicaA, performInsert(replicaB, {row: 0, column: 2}, 'c'))
      replicaA.groupChangesSinceCheckpoint(checkpoint)
      integrateOperations(replicaB, performUndo(replicaA).operations)

      assert.equal(replicaA.testLocalDocument.text, 'ac')
      assert.equal(replicaB.testLocalDocument.text, 'ac')
    })

    test('grouping the last 2 transactions', () => {
      const document = buildDocument(1)
      performInsert(document, {row: 0, column: 0}, 'a')
      performInsert(document, {row: 0, column: 1}, 'b')
      const checkpoint1 = document.createCheckpoint()
      performInsert(document, {row: 0, column: 2}, 'c')
      const checkpoint2 = document.createCheckpoint()

      assert(document.groupLastChanges())
      assert.equal(document.getText(), 'abc')
      document.undo()
      assert.equal(document.getText(), 'a')
      document.redo()
      assert.equal(document.getText(), 'abc')
      assert(!document.revertToCheckpoint(checkpoint1))
      performInsert(document, {row: 0, column: 3}, 'd')
      assert(!document.revertToCheckpoint(checkpoint2))

      // Can't group past barrier checkpoints
      const checkpoint3 = document.createCheckpoint({isBarrier: true})
      performInsert(document, {row: 0, column: 4}, 'e')
      assert(!document.groupLastChanges())
      assert(document.revertToCheckpoint(checkpoint3))
      assert.equal(document.getText(), 'abcd')
    })

    test('applying a grouping interval', () => {
      const document = buildDocument(1)
      document.getNow = () => now

      let now = 0
      const initialMarkers = {
        1: {
          1: {range: range(point(0, 0), point(0, 0))}
        }
      }
      const checkpoint1 = document.createCheckpoint({markers: initialMarkers})
      performInsert(document, {row: 0, column: 0}, 'a')
      const markersAfterInsertion1 = {
        1: {
          1: {range: range(point(0, 1), point(0, 1))}
        }
      }
      document.groupChangesSinceCheckpoint(checkpoint1, {markers: markersAfterInsertion1, deleteCheckpoint: true})
      document.applyGroupingInterval(101)

      now += 100
      const checkpoint2 = document.createCheckpoint({markers: markersAfterInsertion1})
      performInsert(document, {row: 0, column: 1}, 'b')
      const markersAfterInsertion2 = {
        1: {
          1: {range: range(point(0, 2), point(0, 2))}
        }
      }
      document.groupChangesSinceCheckpoint(checkpoint2, {markers: markersAfterInsertion2, deleteCheckpoint: true})
      document.applyGroupingInterval(201)

      now += 200
      const checkpoint3 = document.createCheckpoint({markers: markersAfterInsertion2})
      performInsert(document, {row: 0, column: 2}, 'c')
      const markersAfterInsertion3 = {
        1: {
          1: {range: range(point(0, 3), point(0, 3))}
        }
      }
      document.groupChangesSinceCheckpoint(checkpoint3, {markers: markersAfterInsertion3, deleteCheckpoint: true})
      document.applyGroupingInterval(201)

      // Not grouped with previous transaction because its associated grouping
      // interval is 201 and we always respect the minimum associated interval
      // between the last and penultimate transaction.
      now += 300
      const checkpoint4 = document.createCheckpoint({markers: markersAfterInsertion3})
      performInsert(document, {row: 0, column: 3}, 'd')
      const markersAfterInsertion4 = {
        1: {
          1: {range: range(point(0, 4), point(0, 4))}
        }
      }
      document.groupChangesSinceCheckpoint(checkpoint4, {markers: markersAfterInsertion4, deleteCheckpoint: true})
      document.applyGroupingInterval(301)

      assert.equal(document.testLocalDocument.text, 'abcd')

      {
        const {markers} = performUndo(document)
        assert.equal(document.testLocalDocument.text, 'abc')
        assert.deepEqual(markers, markersAfterInsertion3)
      }

      {
        const {markers} = performUndo(document)
        assert.equal(document.testLocalDocument.text, '')
        assert.deepEqual(markers, initialMarkers)
      }

      {
        const {markers} = performRedo(document)
        assert.equal(document.testLocalDocument.text, 'abc')
        assert.deepEqual(markers, markersAfterInsertion3)
      }

      {
        const {markers} = performRedo(document)
        assert.equal(document.testLocalDocument.text, 'abcd')
        assert.deepEqual(markers, markersAfterInsertion4)
      }
    })

    test('getting the state of the history', () => {
      const document = buildDocument(1, 'a ')
      performInsert(document, point(0, 2), 'b ')
      performInsert(document, point(0, 4), 'c ')
      const checkpoint1 = document.createCheckpoint({
        markers: {1: {1: {range: range(point(0, 2), point(0, 5))}}}
      })
      performInsert(document, point(0, 0), 'd ')
      performInsert(document, point(0, 8), 'e ')
      document.groupChangesSinceCheckpoint(checkpoint1, {
        markers: {1: {1: {range: range(point(0, 1), point(0, 3))}}}
      })
      performInsert(document, point(0, 10), 'f ')
      const checkpoint2 = document.createCheckpoint({
        markers: {1: {1: {range: range(point(0, 0), point(0, 1))}}}
      })
      performInsert(document, point(0, 10), 'g ')
      document.undo()
      document.undo()
      const replica = replicateDocument(2, document)

      const history = document.getHistory(3)

      // The current implementation of getHistory temporarily mutates the replica.
      // Here we make sure we restore the state of the document and its undo counts.
      assert.equal(document.getText(), replica.getText())
      integrateOperations(document, replica.undoOrRedoOperations(replica.operations.slice()).operations)
      assert.equal(document.getText(), replica.getText())

      assert.equal(history.nextCheckpointId, 3)
      assert.deepEqual(history.undoStack, [
        {
          type: "transaction",
          changes: [
            {oldStart: point(0, 4), oldEnd: point(0, 4), oldText: "", newStart: point(0, 4), newEnd: point(0, 6), newText: "c "}
          ],
          markersBefore: null,
          markersAfter: null
        },
        {
          type: "checkpoint",
          id: 1,
          markers: {1: {1: {range: range(point(0, 2), point(0, 5))}}}
        },
        {
          type: "transaction",
          changes: [
            {oldStart: point(0, 0), oldEnd: point(0, 0), oldText: "", newStart: point(0, 0), newEnd: point(0, 2), newText: "d "},
            {oldStart: point(0, 6), oldEnd: point(0, 6), oldText: "", newStart: point(0, 8), newEnd: point(0, 10), newText: "e "}
          ],
          markersBefore: {1: {1: {range: range(point(0, 2), point(0, 5))}}},
          markersAfter: {1: {1: {range: range(point(0, 1), point(0, 3))}}}
        }
      ])
      assert.deepEqual(history.redoStack, [
        {
          type: "transaction",
          changes: [
            {oldStart: point(0, 10), oldEnd: point(0, 10), oldText: "", newStart: point(0, 10), newEnd: point(0, 12), newText: "g "}
          ],
          markersBefore: null,
          markersAfter: null
        },
        {
          type: "checkpoint",
          id: 2,
          markers: {1: {1: {range: range(point(0, 0), point(0, 1))}}}
        },
        {
          type: "transaction",
          changes: [
            {oldStart: point(0, 10), oldEnd: point(0, 10), oldText: "", newStart: point(0, 10), newEnd: point(0, 12), newText: "f "}
          ],
          markersBefore: null,
          markersAfter: null
        }
      ])
    })
  })

  test('replica convergence with random operations', function () {
    this.timeout(Infinity)
    const initialSeed = Date.now()
    const peerCount = 5
    for (var i = 0; i < 1000; i++) {
      const peers = Peer.buildNetwork(peerCount, '')
      let seed = initialSeed + i
      // seed = 1504270975436
      // global.enableLog = true
      const failureMessage = `Random seed: ${seed}`
      try {
        const random = Random(seed)
        let operationCount = 0
        while (operationCount < 10) {
          const peersWithOutboundOperations = peers.filter(p => !p.isOutboxEmpty())
          if (peersWithOutboundOperations.length === 0 || random(2)) {
            const peer = peers[random(peerCount)]
            const k = random(10)
            if (k < 2 && peer.editOperations.length > 0) {
              peer.undoRandomOperation(random)
            } else if (k < 4) {
              peer.updateRandomMarkers(random)
            } else {
              peer.performRandomEdit(random)
            }

            if (random(10) < 3) {
              peer.verifyTextUpdatesForRandomOperations(random)
            }

            if (random(10) < 3) {
              peer.verifyDocumentReplication()
            }

            assert.equal(peer.document.getText(), peer.localDocument.text)

            operationCount++
          } else {
            const peer = peersWithOutboundOperations[random(peersWithOutboundOperations.length)]
            peer.deliverRandomOperation(random)

            assert.equal(peer.document.getText(), peer.localDocument.text)
          }
        }

        while (true) {
          const peersWithOutboundOperations = peers.filter(p => !p.isOutboxEmpty())
          if (peersWithOutboundOperations.length === 0) break

          const peer = peersWithOutboundOperations[random(peersWithOutboundOperations.length)]
          peer.deliverRandomOperation(random)
        }

        for (let j = 0; j < peers.length; j++) {
          const peer = peers[j]
          peer.log(JSON.stringify(peer.localDocument.text))
        }

        for (let j = 0; j < peers.length; j++) {
          assert.equal(peers[j].localDocument.text, peers[j].document.getText())
        }

        for (let j = 0; j < peers.length - 1; j++) {
          assert.equal(peers[j].localDocument.text, peers[j + 1].localDocument.text, failureMessage)
        }

        // TODO: Get markers to converge. This isn't critical since markers
        // are current just used for decorations and an occasional divergence
        // won't be fatal.
        //
        // for (let j = 0; j < peers.length - 1; j++) {
        //   assert.deepEqual(peers[j].localDocument.markers, peers[j + 1].localDocument.markers, failureMessage)
        // }
      } catch (e) {
        console.log(failureMessage);
        throw e
      }
    }
  })
})

function buildDocument (siteId, text) {
  const document = new Document({siteId, text})
  document.testLocalDocument = new LocalDocument(document.getText())
  return document
}

function replicateDocument (siteId, document) {
  const replica = document.replicate(siteId)
  replica.testLocalDocument = new LocalDocument(replica.getText())
  return replica
}

function performInsert (replica, position, text) {
  return performSetTextInRange(replica, position, position, text)
}

function performDelete (replica, start, end) {
  return performSetTextInRange(replica, start, end, '')
}

function performSetTextInRange (replica, start, end, text, options) {
  replica.testLocalDocument.setTextInRange(start, end, text)
  return replica.setTextInRange(start, end, text, options)
}

function performUndo (replica) {
  const {operations, textUpdates, markers} = replica.undo()
  replica.testLocalDocument.updateText(textUpdates)
  return {operations, markers}
}

function performRedo (replica) {
  const {operations, textUpdates, markers} = replica.redo()
  replica.testLocalDocument.updateText(textUpdates)
  return {operations, markers}
}

function performUndoOrRedoOperations (replica, operationToUndo) {
  const {operations, textUpdates} = replica.undoOrRedoOperations(operationToUndo)
  replica.testLocalDocument.updateText(textUpdates)
  return operations
}

function performRevertToCheckpoint (replica, checkpoint, options) {
  const {operations, textUpdates, markers} = replica.revertToCheckpoint(checkpoint, options)
  replica.testLocalDocument.updateText(textUpdates)
  return {operations, markers}
}

function performUpdateMarkers (replica, markerUpdates) {
  replica.testLocalDocument.updateMarkers({[replica.siteId]: markerUpdates})
  return replica.updateMarkers(markerUpdates)
}

function integrateOperations (replica, ops) {
  const {textUpdates, markerUpdates} = replica.integrateOperations(ops)
  replica.testLocalDocument.updateText(textUpdates)
  replica.testLocalDocument.updateMarkers(markerUpdates)
}

function buildRange (startColumn, endColumn) {
  return {
    start: {row: 0, column: startColumn},
    end: {row: 0, column: endColumn}
  }
}

function range (start, end) {
  return {start, end}
}

function point(row, column) {
  return {row, column}
}
