File content structures

To store the current state of an opened file in memory, a datastructure called a piece table is used. For an explanation of the default implementation, see this page. We do not use the traditional implementation however, as we will discuss below.

Piece Table

As is shown on the aforementioned page, piece tables are ordinarily ordered with characters as their smalles unit. In our implementation, however, pieces consist of a certain number of lines of text, delimited with a \n (newline character). These lines are stored in blocks stored in a block list. Each piece represents a certain number of lines from a particular block and by ordering these pieces in a list, a file can be constructed and manupulated.

The piece table is primarily designed to allow for concurrent editing and easy creation of locks, the second of which we discuss in more detail over at the filesystem page. By giving every piece an unique UUID, which is re-generated every time the piece changes, clients can accurately specify where to perform certain actions within the file, without the problems inherent to a line-based editing schemes.

Pieces

The pieces are implemented as Python dataclasses with the following structure:

@dataclasses.dataclass
class Piece:
    piece_id: str
    block_id: int
    start:    int
    length:   int
    owner:    str

The piece_id is a UUID used to identify individual pieces. The block_id is the id of the block containing the piece's content. The start and length are used to determine which lines in the block are represented by a particular piece. As might be obvious from the name, start indicates the starting line---starting from 0---and length indicates the number of lines starting from start which are represented by the piece. Finally, owner is either equal to an empty string or equal to the user which owns this piece.

Table

These pieces are ordered in a list. The ordering determines the positions of the represented lines in the eventually constructed file. Below is a common example, consisting of three pieces and two blocks. The first and last pieces refer to block 0, although to different sections (in fact, two pieces can never refer to the same section within a block). The second piece refers to block 1, starting at line 3 and until line 3+5 = 8. Its owner is "User1".

[
    Piece("817254c0-ebb9-418b-8970-b663cef2816b", 0, 0, 2, ""),
    Piece("d3a290af-a995-44d7-b90f-70c081a082a0", 1, 3, 5, "User1"),
    Piece("c548dd68-1f28-462a-af68-198b7813accd", 0, 4, 3, ""),
]

The table can be modified in several ways, of which the most important is the put_piece function, which overlays a new piece in the table (possibly overwriting other pieces). New pieces can also be inserted.

Block list

Blocks are simply lists of strings. Accessing and storing these blocks can be done using a dictionary called the block table. An example with two blocks can be found below.

{
    0: ["file\n", "content\n"],
    1: ["more\n", "\n", file\n", "\n", "content\n"]
}

Block id 0 is special in the sense that it is the only permanent block in the list. When initialising the piece table, the origal file content is loaded within it. When cleaning up unnecessary pieces in the table, this block will become the current file content according to the piece table, and all unlocked pieces will be rebased on it.

When blocks are unused, they can be unloaded from memory. This is handled in the Filesystem class.

Specifying operations

In general, file operations are linked to a specific position in the file. This is specified as a piece UUID and an offset within this piece. Like this, the server always knows which exact position the clients means, even when other pieces have been edited. If the uuid is not present in the table, the server immediately knows the clients has an outdated version locally, and can act accordingly.

An additional length parameter will often be specified too, which starts from the given position to indicate operations that span multiple lines.