Device, Method, and Graphical User Interface for Collaborative Editing in Documents

1 . A method of maintaining a consistent output based on concurrent textual edits received at multiple collaborating devices, including:

at a first device of the multiple collaborating devices, wherein the first device comprises one or more processors, memory, and a display:

maintaining a directed acyclic graph to represent a textual string concurrently edited by the first device and at least a second device of the multiple collaborating devices, wherein the directed acyclic graph includes a plurality of nodes each representing a respective character input received from one or more of the multiple collaborating devices, and wherein the directed acyclic graph further includes multiple parallel paths each including at least one node that represents a respective one of multiple concurrent character inputs received from distinct devices of the multiple collaborating devices;

topologically traversing the directed acyclic graph in accordance with a predetermined ordering rule to deterministically sort the plurality of nodes in the directed acyclic graph into a string sequence; and

displaying the textual string in accordance with the deterministically obtained string sequence.

2 . The method of claim 1 , wherein each node in the directed acyclic graph includes a unique sequence number for the character input represented by the node, and wherein the unique sequence number includes (1) a unique device identifier for a respective device at which the character input was first received, and (2) a local sequence number assigned to the character input in accordance with a local order by which the character input was first received at said respective device.

3 . The method of claim 2 , wherein topologically traversing the directed acyclic graph in accordance with the predetermined ordering rule to deterministically sort the plurality of nodes in the directed acyclic graph into the string sequence further includes:

sorting nodes from a starting node to an end node of the multiple parallel paths by traversing the multiple parallel paths in an order based on a comparison between respective lowest character sequence numbers present in each of the multiple parallel paths.

4 . The method of claim 2 , wherein the multiple parallel paths include at least one linear path.

5 . The method of claim 2 , wherein the multiple parallel paths include at least one path that further includes multiple parallel sub-paths.

6 . The method of claim 2 , wherein the predetermined ordering rule specifies a fixed order between the unique device identifiers of the multiple collaborating devices, and affords a higher significance to the unique device identifiers than the local sequence numbers when comparing the unique sequence identifiers of the character inputs in the multiple parallel paths.

7 . The method of claim 1 , wherein maintaining a directed acyclic graph to represent a textual string concurrently edited by the first device and at least a second device of the multiple collaborating devices further includes:

creating the directed acyclic graph based on initial textual edits received locally at the first device; and

modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on relative timing and relative locations of the additional textual edits to the initial textual edits.

8 . The method of claim 7 , wherein modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on the relative timing and locations of the additional textual edits to the initial textual edits further comprises:

receiving concurrent insertion inputs between a first node and a second node in the directed acyclic graph from multiple ones of the multiple collaborating devices; and

for each of the concurrent insertion inputs, creating a respective path from the first node to the second node in the directed acyclic graph to include one or more nodes representing the insertion input.

9 . The method of claim 7 , wherein modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on the relative timing and locations of the additional textual edits to the initial textual edits further comprises:

receiving a deletion input deleting a character represented by a respective node in the directed acyclic graph; and

in response to the deletion input, changing a status of the respective node for the character to “deleted”, wherein the respective node having the “deleted” status is omitted in the string sequence or skipped when the textual string is displayed at the first device in accordance with the string sequence.

10 . The method of claim 7 , wherein modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on the relative timing and locations of the additional textual edits to the initial textual edits further comprises:

receiving an undo input restoring a deleted character represented by a respective node in the directed acyclic graph, wherein a status of the respective node is a “deleted” status; and

in response to the undo input,

removing the “deleted” status from the respective node for the deleted character in the directed acyclic graph; and

updating a unique sequence number of the respective node for the deleted character in the directed acyclic graph based on a respective timestamp associated with the undo input.

11 . The method of claim 7 , wherein modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on the relative timing and locations of the additional textual edits to the initial textual edits further comprises:

receiving a redo input re-deleting a previously un-deleted character represented by a respective node in the directed acyclic graph, wherein the status of the respective node is an “un-deleted” status; and

in response to the redo input,

changing the status of the respective node for the previously un-deleted character to a “re-deleted” status; and

updating the unique sequence number of the respective node for the re-deleted character in the directed acyclic graph based on a respective timestamp associated with the redo input.

12 . The method of claim 7 , wherein modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on the relative timing and locations of the additional textual edits to the initial textual edits further comprises:

receiving a style input changing a style of a character represented by a respective node in the directed acyclic graph; and

in response to the style input, changing a style attribute of the respective node for the character in the directed acyclic graph, wherein the style attribute includes a respective style and a respective timestamp associated with the style input.

13 . The method of claim 7 , wherein modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on the relative timing and locations of the additional textual edits to the initial textual edits further comprises:

receiving concurrent style inputs changing a style of a character represented by a respective node in the directed acyclic graph, wherein the concurrent style inputs are associated with different devices and timestamps; and

in response to receiving the concurrent style inputs, changing a style attribute of the respective node for the character in the directed acyclic graph in accordance with the style input having the latest timestamp among the concurrent style inputs.

14 . A first electronic device, comprising:

a display;

one or more processors;

memory; and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for:

maintaining a directed acyclic graph to represent a textual string concurrently edited by the first electronic device and at least a second electronic device of multiple collaborating devices, wherein the directed acyclic graph includes a plurality of nodes each representing a respective character input received from one or more of the multiple collaborating devices, and wherein the directed acyclic graph further includes multiple parallel paths each including at least one node that represents a respective one of multiple concurrent character inputs received from distinct devices of the multiple collaborating devices

topologically traversing the directed acyclic graph in accordance with a predetermined ordering rule to deterministically sort the plurality of nodes in the directed acyclic graph into a string sequence; and

displaying the textual string in accordance with the deterministically obtained string sequence.

15 . The first electronic device of claim 14 , wherein each node in the directed acyclic graph includes a unique sequence number for the character input represented by the node, and wherein the unique sequence number includes (1) a unique device identifier for a respective device at which the character input was first received, and (2) a local sequence number assigned to the character input in accordance with a local order by which the character input was first received at said respective device.

16 . The first electronic device of claim 15 , wherein topologically traversing the directed acyclic graph in accordance with the predetermined ordering rule to deterministically sort the plurality of nodes in the directed acyclic graph into the string sequence further includes:

sorting nodes from a starting node to an end node of the multiple parallel paths by traversing the multiple parallel paths in an order based on a comparison between respective lowest character sequence numbers present in each of the multiple parallel paths.

17 . The first electronic device of claim 15 , wherein the predetermined ordering rule specifies a fixed order between the unique device identifiers of the multiple collaborating devices, and affords a higher significance to the unique device identifiers than the local sequence numbers when comparing the unique sequence identifiers of the character inputs in the multiple parallel paths.

18 . The first electronic device of claim 14 , wherein maintaining a directed acyclic graph to represent a textual string concurrently edited by the first device and at least a second device of the multiple collaborating devices further includes:

creating the directed acyclic graph based on initial textual edits received locally at the first device; and

modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on relative timing and relative locations of the additional textual edits to the initial textual edits.

19 . The first electronic device of claim 18 , wherein modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on the relative timing and locations of the additional textual edits to the initial textual edits further comprises:

receiving concurrent insertion inputs between a first node and a second node in the directed acyclic graph from multiple ones of the multiple collaborating devices; and

for each of the concurrent insertion inputs, creating a respective path from the first node to the second node in the directed acyclic graph to include one or more nodes representing the insertion input.

20 . A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a first electronic device with a display, cause the first electronic device to:

maintain a directed acyclic graph to represent a textual string concurrently edited by the first electronic device and at least a second electronic device of multiple collaborating devices, wherein the directed acyclic graph includes a plurality of nodes each representing a respective character input received from one or more of the multiple collaborating devices, and wherein the directed acyclic graph further includes multiple parallel paths each including at least one node that represents a respective one of multiple concurrent character inputs received from distinct devices of the multiple collaborating devices

topologically traverse the directed acyclic graph in accordance with a predetermined ordering rule to deterministically sort the plurality of nodes in the directed acyclic graph into a string sequence; and

display the textual string in accordance with the deterministically obtained string sequence.

21 . The non-transitory computer readable storage medium of claim 20 , wherein each node in the directed acyclic graph includes a unique sequence number for the character input represented by the node, and wherein the unique sequence number includes (1) a unique device identifier for a respective device at which the character input was first received, and (2) a local sequence number assigned to the character input in accordance with a local order by which the character input was first received at said respective device.

22 . The non-transitory computer readable storage medium of claim 21 , wherein topologically traversing the directed acyclic graph in accordance with the predetermined ordering rule to deterministically sort the plurality of nodes in the directed acyclic graph into the string sequence further includes:

sorting nodes from a starting node to an end node of the multiple parallel paths by traversing the multiple parallel paths in an order based on a comparison between respective lowest character sequence numbers present in each of the multiple parallel paths.

23 . The non-transitory computer readable storage medium of claim 21 , wherein the predetermined ordering rule specifies a fixed order between the unique device identifiers of the multiple collaborating devices, and affords a higher significance to the unique device identifiers than the local sequence numbers when comparing the unique sequence identifiers of the character inputs in the multiple parallel paths.

24 . The non-transitory computer readable storage medium of claim 20 , wherein maintaining a directed acyclic graph to represent a textual string concurrently edited by the first device and at least a second device of the multiple collaborating devices further includes:

creating the directed acyclic graph based on initial textual edits received locally at the first device; and

modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on relative timing and relative locations of the additional textual edits to the initial textual edits.

25 . The non-transitory computer readable storage medium of claim 24 , wherein modifying the directed acyclic graph based on additional textual edits received from each of the multiple collaborating devices based on the relative timing and locations of the additional textual edits to the initial textual edits further comprises:

receiving concurrent insertion inputs between a first node and a second node in the directed acyclic graph from multiple ones of the multiple collaborating devices; and

for each of the concurrent insertion inputs, creating a respective path from the first node to the second node in the directed acyclic graph to include one or more nodes representing the insertion input.