Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Building a Collaborative Text Editor

Building a Collaborative Text Editor

Have you ever clicked "Save" on a document, and caused a coworker to lose hours of work? Or spent more time coordinating "Who has permission to edit" in Slack than you did actually writing the document?

Google-Docs-style collaboration used to be nice to have. Now, it's expected. Companies like Quip and Coda have based their business on real-time collaboration features. Atom and Sublime Text have collaborative editing plugins. Even Confluence now supports collaborative editing!

In this talk, you'll learn how to build a great collaborative experience, based on solid fundamental ideas.

Justin Weiss

April 18, 2018
Tweet

More Decks by Justin Weiss

Other Decks in Programming

Transcript

  1. hello hello, world Client A hello hello, world Client B

    insert “, world” @ 5 insert “, world” @ 5
  2. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5
  3. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 c a t 0 1 2 3 4 5 insert c, 0
  4. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 c a t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 insert c, 0 insert r, 1
  5. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 c a t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 insert c, 0 insert r, 1
  6. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 c a t 0 1 2 3 4 5 c r a t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 insert c, 0 insert r, 1 insert r, 1
  7. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 c a t 0 1 2 3 4 5 c r a t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 insert c, 0 insert r, 1 insert r, 1 ≠
  8. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 c a t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 insert c, 0 insert r, 1
  9. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 c a t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 insert c, 0 insert r, 1 insert r, ?
  10. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 c a t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 insert c, 0 insert r, 1 insert r, 2
  11. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 c a t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 insert c, 0 insert r, 1 insert r, 2 c a r t 0 1 2 3 4 5 insert c, 0
  12. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 c
  13. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 a r t 0 1 2 3 4 5 ? ? ? ? 0 1 2 3 4 5 insert c, 0 insert r, 1 c
  14. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 a r t 0 1 2 3 4 5 ? ? ? ? 0 1 2 3 4 5 insert c, 0 insert r, 1 c
  15. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 insert r, 1 c
  16. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 insert r, 1 c insert r, 2 insert c, 0 insert c, 0
  17. @justinweiss #collabeditor test “insert vs insert” do top = {

    type: :insert, text: “c”, position: 0 } left = { type: :insert, text: “r”, position: 1 } bottom, right = transform(top, left) assert_equal { type: insert, text: “c”, position: 0 }, bottom assert_equal { type: insert, text: “r”, position: 2 }, right end
  18. @justinweiss #collabeditor document = “ca” top = { type: :insert,

    text: “r”, position: 2, client_id: 1 } left = { type: :insert, text: “p”, position: 2, client_id: 2 } # Should our document be “carp” or “capr”? # left is server, server always wins transform(top, left, false) How do you break ties?
  19. @justinweiss #collabeditor document = “ca” top = { type: :insert,

    text: “r”, position: 2, client_id: 1 } left = { type: :insert, text: “p”, position: 2, client_id: 2 } # left is server, server always wins transform(top, left, false) # bigger client_id wins transform(top, left, top.client_id > left.client_id) How do you break ties?
  20. @justinweiss #collabeditor test “insert vs insert” do top = {

    type: :insert, text: “c”, position: 0 } left = { type: :insert, text: “r”, position: 1 } bottom, right = transform(top, left) assert_equal { type: insert, text: “c”, position: 0 }, bottom assert_equal { type: insert, text: “r”, position: 2 }, right end
  21. @justinweiss #collabeditor def transform(top, left, win_tiebreakers = false) bottom =

    transform_operation(top, left, win_tiebreakers), right = transform_operation(left, top, !win_tiebreakers) [bottom, right] end a t 0 1 2 3 4 5 a t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 insert r, 1 c insert r, 2 insert c, 0 insert c, 0
  22. @justinweiss #collabeditor def transform(top, left, win_tiebreakers = false) bottom =

    transform_operation(top, left, win_tiebreakers), right = transform_operation(left, top, !win_tiebreakers) [bottom, right] end a t 0 1 2 3 4 5 a t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 insert r, 1 c insert r, 2 insert c, 0 insert c, 0
  23. @justinweiss #collabeditor # ours: { type: :insert, text: “r”, position:

    1 } # theirs: { type: :insert, text: “c”, position: 0 } def transform_operation(ours, theirs, win_tiebreakers) # TODO: handle other kinds of operations transformed_op = ours.dup if ours[:position] > theirs[:position] || (ours[:position] == theirs[:position] && !win_tiebreakers ) transformed_op[:position] = transformed_op[:position] + theirs[:text].length end transformed_op end
  24. @justinweiss #collabeditor # ours: { type: :insert, text: “r”, position:

    1 } # theirs: { type: :insert, text: “c”, position: 0 } def transform_operation(ours, theirs, win_tiebreakers) # TODO: handle other kinds of operations transformed_op = ours.dup if ours[:position] > theirs[:position] || (ours[:position] == theirs[:position] && !win_tiebreakers ) transformed_op[:position] = transformed_op[:position] + theirs[:text].length end transformed_op end
  25. @justinweiss #collabeditor # ours: { type: :insert, text: “r”, position:

    1 } # theirs: { type: :insert, text: “c”, position: 0 } def transform_operation(ours, theirs, win_tiebreakers) # TODO: handle other kinds of operations transformed_op = ours.dup if ours[:position] > theirs[:position] || (ours[:position] == theirs[:position] && !win_tiebreakers ) transformed_op[:position] = transformed_op[:position] + theirs[:text].length end transformed_op end
  26. @justinweiss #collabeditor # ours: { type: :insert, text: “r”, position:

    1 } # theirs: { type: :insert, text: “c”, position: 0 } def transform_operation(ours, theirs, win_tiebreakers) # TODO: handle other kinds of operations transformed_op = ours.dup if ours[:position] > theirs[:position] || (ours[:position] == theirs[:position] && !win_tiebreakers ) transformed_op[:position] = transformed_op[:position] + theirs[:text].length end transformed_op end
  27. @justinweiss #collabeditor # ours: { type: :insert, text: “r”, position:

    1 } # theirs: { type: :insert, text: “c”, position: 0 } def transform_operation(ours, theirs, win_tiebreakers) # TODO: handle other kinds of operations transformed_op = ours.dup if ours[:position] > theirs[:position] || (ours[:position] == theirs[:position] && !win_tiebreakers ) transformed_op[:position] = transformed_op[:position] + theirs[:text].length end transformed_op end
  28. @justinweiss #collabeditor apply([op1, T(op2, op1)]) == apply([op2, T(op1, op2)]) #

    or, in other words: bottom = transform_operation(top, left, true) right = transform_operation(left, top, false) document.apply([top, right]) == document.apply([left, bottom]) Transform Property 1
  29. @justinweiss #collabeditor apply([op1, T(op2, op1)]) == apply([op2, T(op1, op2)]) #

    or, in other words: bottom = transform_operation(top, left, true) right = transform_operation(left, top, false) document.apply([top, right]) == document.apply([left, bottom]) Transform Property 1 a t 0 1 2 3 4 5 a t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 insert r, 1 c insert r, 2 insert c, 0 insert c, 0
  30. @justinweiss #collabeditor apply([op1, T(op2, op1)]) == apply([op2, T(op1, op2)]) #

    or, in other words: bottom = transform_operation(top, left, true) right = transform_operation(left, top, false) document.apply([top, right]) == document.apply([left, bottom]) Transform Property 1 a t 0 1 2 3 4 5 a t 0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 insert r, 1 c insert r, 2 insert c, 0 insert c, 0
  31. @justinweiss #collabeditor Math makes testing easy! • Take a document

    • Generate random operations • Transform them • Apply them, to the document, according to TP1 • Are the documents equal?
  32. a t 0 1 2 3 4 5 a t

    0 1 2 3 4 5 a r t 0 1 2 3 4 5 c a r t 0 1 2 3 4 5 insert c, 0 insert r, 1 c insert r, 2 insert c, 0 insert c, 0
  33. a t a t a t e c a t

    e insert c, 0 (server) insert e, 2 (client 2) c insert e, 3 (client 2) insert c, 0 (server) a t a t a r t c a r t insert c, 0 (server) insert r, 1 (client 1) c insert r, 2 (client 1) insert c, 0 (server)
  34. @justinweiss #collabeditor > document { content: “at”, version: 2 }

    > operation { type: :insert, text: “r”, position: 1, version: 2 }
  35. @justinweiss #collabeditor > top { type: :insert, text: “c”, position:

    0, version: 2 } > left { type: :insert, text: “r”, position: 1, version: 2 }
  36. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c right[0] bottom[0] r t s 1 2 3 4 5 top[1] c ? c h a r 0 1 2 3 4 5 left[1] ? r s 1 2 3 4 5 bottom[1] c ? c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 ? c right[1] 0 0 0
  37. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c r t s 1 2 3 4 5 top[1] c right[0] c h a r 0 1 2 3 4 5 left[1] bottom[0] r s 1 2 3 4 5 c right[1] c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 bottom[1] c 0 0 0
  38. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c transformed left[0] transformed top[0] r t s 1 2 3 4 5 top[1] c right[0] c h a r 0 1 2 3 4 5 left[1] bottom[0] r s 1 2 3 4 5 transformed top[1] c right[1] c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 bottom[1] c transformed left[1] 0 0 0
  39. a r t 1 2 3 4 5 r t

    0 1 2 3 4 5 a r 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c transformed left[0] transformed top[0] transf
  40. r t 0 1 2 3 4 5 c r

    0 1 2 3 4 5 c transformed left[0] op[0] r t s 1 2 3 4 5 top[1] c right[0] r s 1 2 3 4 5 transformed top[1] c 0 0
  41. @justinweiss #collabeditor An Integrating, Transformation-Oriented Approach to Concurrency Control and

    Undo in Group Editors “In fact, it took us a long time to detect this flaw. Our solution became evident, however, as we had the idea of visualizing transformations as grid-like diagrams.”
  42. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c r t s 1 2 3 4 5 top[1] c right[0] c h a r 0 1 2 3 4 5 left[1] bottom[0] r s 1 2 3 4 5 c right[1] c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 bottom[1] c 0 0 0
  43. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c right[0] bottom[0] r t s 1 2 3 4 5 top[1] c ? c h a r 0 1 2 3 4 5 left[1] ? r s 1 2 3 4 5 bottom[1] c ? c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 ? c right[1] 0 0 0
  44. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c transformed left[0] bottom[0] r t s 1 2 3 4 5 top[1] c right[0] c h a r 0 1 2 3 4 5 left[1] bottom[0] r s 1 2 3 4 5 bottom[1] c right[1] c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 bottom[1] c right[1] 0 0 0
  45. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c transformed left[0] bottom[0] r t s 1 2 3 4 5 top[1] c right[0] c h a r 0 1 2 3 4 5 left[1] bottom[0] r s 1 2 3 4 5 bottom[1] c right[1] c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 bottom[1] c right[1] 0 0 0
  46. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c transformed left[0] bottom[0] r t s 1 2 3 4 5 top[1] c right[0] c h a r 0 1 2 3 4 5 left[1] bottom[0] r s 1 2 3 4 5 bottom[1] c right[1] c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 bottom[1] c right[1] 0 0 0
  47. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c right[0] top[0] r t s 1 2 3 4 5 top[1] c right[0] c h a r 0 1 2 3 4 5 left[1] bottom[0] r s 1 2 3 4 5 top[1] c right[1] c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 bottom[1] c transformed left[1] 0 0 0
  48. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c transformed left[0] transformed top[0] r t s 1 2 3 4 5 top[1] c right[0] c h a r 0 1 2 3 4 5 left[1] bottom[0] r s 1 2 3 4 5 transformed top[1] c right[1] c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 bottom[1] c transformed left[1] 0 0 0
  49. @justinweiss #collabeditor def transform(left, top) left = Array(left) top =

    Array(top) return [left, top] if left.empty? || top.empty? if left.length == 1 && top.length == 1 right = transform_operation(left.first, top.first, true) bottom = transform_operation(top.first, left.first, false) return [Array(right), Array(bottom)] end
  50. @justinweiss #collabeditor def transform(left, top) left = Array(left) top =

    Array(top) return [left, top] if left.empty? || top.empty? if left.length == 1 && top.length == 1 right = transform_operation(left.first, top.firs bottom = transform_operation(top.first, left.fir return [Array(right), Array(bottom)] end right = []
  51. @justinweiss #collabeditor top = Array(top) return [left, top] if left.empty?

    || top.empty? if left.length == 1 && top.length == 1 right = transform_operation(left.first, top.first, true) bottom = transform_operation(top.first, left.first, false) return [Array(right), Array(bottom)] end right = [] bottom = [] left.each do |left_op| bottom.clear top.each do |top_op|
  52. @justinweiss #collabeditor right = [] bottom = [] left.each do

    |left_op| bottom.clear top.each do |top_op| new_left, new_top = transform(left_op, top_op) left_op = new_left bottom.concat(new_top) end right = right.concat(left_op) top = bottom end
  53. c a r t 0 1 2 3 4 5

    r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c transformed left[0] bottom[0] r t s 1 2 3 4 5 top[1] c right[0] c h a r 0 1 2 3 4 5 left[1] bottom[0] r s 1 2 3 4 5 bottom[1] c right[1] c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 bottom[1] c right[1] 0 0 0
  54. @justinweiss #collabeditor right = [] bottom = [] left.each do

    |left_op| bottom = [] top.each do |top_op| right_op, bottom_op = transform(left_op, top_op) left_op = right_op bottom.concat(bottom_op) end right.concat(left_op) top = bottom end
  55. @justinweiss #collabeditor right = [] bottom = [] left.each do

    |left_op| bottom = [] top.each do |top_op| right_op, bottom_op = transform(left_op, top_op) left_op = right_op bottom.concat(bottom_op) end right.concat(left_op) top = bottom end
  56. @justinweiss #collabeditor right = [] bottom = [] left.each do

    |left_op| bottom = [] top.each do |top_op| right_op, bottom_op = transform(left_op, top_op) left_op = right_op bottom.concat(bottom_op) end right.concat(left_op) top = bottom end
  57. @justinweiss #collabeditor right = [] bottom = [] left.each do

    |left_op| bottom = [] top.each do |top_op| right_op, bottom_op = transform(left_op, top_op) left_op = right_op bottom.concat(bottom_op) end right.concat(left_op) top = bottom end
  58. @justinweiss #collabeditor right = [] bottom = [] left.each do

    |left_op| bottom = [] top.each do |top_op| right_op, bottom_op = transform(left_op, top_op) left_op = right_op bottom.concat(bottom_op) end right.concat(left_op) top = bottom end c a r t 0 1 2 3 4 5 r t 0 1 2 3 4 5 c a r 0 1 2 3 4 5 c r 0 1 2 3 4 5 top[0] left[0] c right[0] top[0] r t s 1 2 3 4 5 top[1] c right[0] c h a r 0 1 2 3 4 5 left[1] bottom[0] r s 1 2 3 4 5 top[1] c right[1] c h r 0 1 2 3 4 5 h r s 1 2 3 4 5 bottom[1] c transformed left[1] 0 0 0
  59. @justinweiss #collabeditor left.each do |left_op| bottom = [] top.each do

    |top_op| right_op, bottom_op = transform(left_op, top_op) left_op = right_op bottom.concat(bottom_op) end right.concat(left_op) top = bottom end [right, bottom] end
  60. @justinweiss #collabeditor def transform(left, top) left = Array(left) top =

    Array(top) return [left, top] if left.empty? || top.empty? if left.length == 1 && top.length == 1 right = transform_operation(left.first, top.first, true) bottom = transform_operation(top.first, left.first, false) return [Array(right), Array(bottom)] end right = [] bottom = [] left.each do |left_op| bottom = [] top.each do |top_op| right_op, bottom_op = transform(left_op, top_op) left_op = right_op bottom.concat(bottom_op) end right.concat(left_op) top = bottom end [right, bottom] end
  61. @justinweiss #collabeditor Keep your state linear # “easy” state =

    [{:text, “a”, :bold}, {:text, “b”}] # not as easy state = [{ :paragraph, [ {:bold, [ {:text, “a”}]}]}]
  62. hello v1 Client hello v1 Server hello! v2 insert “!”,

    6, v1 hello! v2 insert “!”, 6, v1 acknowledged, v2
  63. hello v1 Client heello v2 Server hello! v1* insert “!”,

    6, v1 insert “!”, 6, v1 Nope. v1 was actually insert “e”, 1
  64. hello v1 Client heello v2 Server hello! v1* insert “!”,

    6, v1 insert “!”, 6, v1 Nope. v1 was actually insert “e”, 1 heello! v2* insert “e”, 1
  65. hello v1 Client heello v2 Server hello! v1* insert “!”,

    6, v1 insert “!”, 6, v1 Nope. v1 was actually insert “e”, 1 heello! v3 insert “e”, 1 heello! v3 insert “!”, 7, v2 acknowledged, v3
  66. hello v1 Client heello v2 Server hello! v1* insert “!”,

    6, v1 insert “!”, 6, v1 Nope. v1 was actually insert “e”, 1 heello! v3 insert “e”, 1 heello! v3 insert “!”, 7, v2 acknowledged, v3
  67. @justinweiss #collabeditor • Client 1: “Car” - Document: “Car” •

    Client 2: “t” - Document: “Cart” • Client 1: Undo! • Should the document be “Car” or should it be “t”?
  68. H e l l o 0 1 2 3 4

    5 Position: 1
  69. H e l l o 0 1 2 3 4

    5 Position: 5
  70. H e l l o 0 1 2 3 4

    5 { state: “Hello”, version: 2, position: 5, cursors: [ { client_id: 3, position: 2 } ] }
  71. H e l l o 0 1 2 3 4

    5 { state: “Hello”, version: 2, position: 5, cursors: [ { client_id: 3, position: 2 } ] }
  72. c a r t 0 1 2 3 4 5

    { state: “Hello”, version: 2, position: 1, cursors: [ { client_id: 2, position: 2 } ] }
  73. c h a r t 0 1 2 3 4

    5 { state: “Hello”, version: 2, position: 2, cursors: [ { client_id: 2, position: ? } ] }
  74. c h a r t 0 1 2 3 4

    5 { state: “Hello”, version: 2, position: 2, cursors: [ { client_id: 2, position: 3 } ] } transform_operation( [:cursor, 2], [:insert, “h”, 1] ) = [:cursor, 3]
  75. @justinweiss #collabeditor When you perform an operation: • Apply it

    to your document • Send it to the server • Transform all cursors against it
  76. @justinweiss #collabeditor You can’t apply a v2 cursor to a

    v1 document (but you can save it for later)
  77. @justinweiss #collabeditor You can’t apply a v1 cursor to a

    v2 document (but you can transform it up to v2) (or just ignore it)
  78. c h a r t 0 1 2 3 4

    5 v15* [insert h, 1] c a r t 0 1 2 3 4 5 v15 [] cursor, 3
  79. c h a r t 0 1 2 3 4

    5 v15* [insert h, 1] c a r t 0 1 2 3 4 5 v15 [] cursor, 3 transform([:cursor, 3], [:insert, “h”, 1]) # => [:cursor, 4]
  80. @justinweiss #collabeditor You can send your cursor at any time

    (as long as all your operations are acknowledged)
  81. c h a r t 0 1 2 3 4

    5 v15* [insert h, 1] c a r t 0 1 2 3 4 5 v15 [] cursor, 5?
  82. @justinweiss #collabeditor undo([:insert, “a”, 3]) # => [:remove, “a”, 3]

    redo([:remove, “a”, 3]) # => [:insert, “a”, 3]
  83. c a r t 0 1 2 3 4 5

    6 undos c a r t s 0 1 2 3 4 5 6 remove s, 4 undos insert s, 4
  84. c a r t s 0 1 2 3 4

    5 6 remove s, 4 undos c h a r t 0 1 2 3 4 5 s 6 remove s, 4 undos insert h, 1
  85. c a r t s 0 1 2 3 4

    5 6 remove s, 4 undos c h a r t 0 1 2 3 4 5 s 6 remove s, 5 undos insert h, 1
  86. c h a r t 0 1 2 3 4

    5 s 6 remove s, 5 undos c h a r t 0 1 2 3 4 5 6 undos undo!
  87. @justinweiss #collabeditor Local undo • When you perform an operation:

    • Invert it, push it on the undo stack • When you receive an operation: • Transform the undo / redo stack against it • When you undo an operation: • Pop it off the stack, apply it, and send it to the server
  88. @justinweiss #collabeditor When you perform an operation: • Apply it

    to your document • Transform all cursors against it • Send it to the server • Add its inverse to the undo stack • Send your cursor… eventually
  89. @justinweiss #collabeditor When you receive an operation: • Transform it

    against operations you haven’t sent • Apply their transformed operations, 
 and send your transformed operations • Transform all cursors against it • Transform your undo / redo stacks against it
  90. @justinweiss #collabeditor When you change your cursor position • Send

    it • But only if you don’t have any unacknowledged operations!
  91. @justinweiss #collabeditor When you receive a cursor: • Older version?

    Transform to your version, or ignore it • Same version? Transform against unacknowledged operations • Newer version? Hold onto it until you see that version, or ignore it
  92. @justinweiss #collabeditor • You need a server • Weird edge

    cases with undo / redo • For certain apps, other collaboration methods might be easier
  93. @justinweiss #collabeditor Open Source • ShareDB: Control algorithm and server

    as a library • CRDTs: • Y.js / Gun.js: Flexible libraries for rich data types • Automerge: Automatically sync JSON data