Uploaded improved documentation about easysync, thx @Joe Corneli

4 files changed, 200 insertions, 372 deletions

diff --git a/doc/easysync/easysync.pdf b/doc/easysync/easysync.pdf
new file mode 100644
index 00000000..d0af379d
--- /dev/null
+++ b/doc/easysync/easysync.pdf
diff --git a/doc/easysync/easysync.tex b/doc/easysync/easysync.tex
new file mode 100644
index 00000000..b2c43207
--- /dev/null
+++ b/doc/easysync/easysync.tex
@@ -0,0 +1,200 @@
+\documentclass[12pt]{article}
+
+\usepackage[T1]{fontenc}
+\usepackage[USenglish]{babel} 
+
+
+\begin{document}
+
+\title{Easysync Protocol}
+\author{AppJet, Inc., with modifications by the Etherpad Foundation}
+\date{\today}
+
+\maketitle
+
+\section{Attributes}
+
+An ``attribute'' is a (key,value) pair such as
+\verb|(author,abc123)| or \verb|(bold,true)|.
+Sometimes an attribute is treated as an instruction to add
+that attribute, in which case an empty value means to
+remove it.  So \verb|(bold,)| removes the ``bold''
+attribute.  Attributes are interned and given numeric IDs,
+so the number ``\verb|6|'' could represent
+``\verb|(bold,true)|'', for example.  This mapping is
+stored in an attribute pool which may be shared by
+multiple changesets.
+
+Entries in the pool must be unique, so that attributes can
+be compared by their IDs.  Attribute names cannot contain
+commas.
+
+A changeset looks something like the following:
+
+\begin{verbatim}
+Z:5g>1|5=2p=v*4*5+1$x
+\end{verbatim}
+
+With the corresponding pool containing these entries (among others):
+
+\begin{itemize}
+\item[] \verb|4| $\rightarrow$ \verb|(author,1059348573)|
+\item[] \verb|5| $\rightarrow$ \verb|(bold,true)|
+\end{itemize}
+
+This changeset, together with the attribute pool,
+represents inserting a bold letter ``x'' into the middle
+of a line.
+
+The string consists of:
+
+\begin{itemize}
+\item a letter \verb|Z| (the ``magic character'' and
+  format version identifier)
+\item a series punctuation marks (operation codes or
+  ``opcodes'' for short), together with alphanumerics
+  (numeric values in base 36).
+\item a dollar sign (\verb|$|)
+\item a string of characters used for insertion operations
+  (the ``char bank'')
+\end{itemize}
+
+In the example above, if we separate out the operations
+and convert the numbers to base 10, then we get:
+\begin{verbatim}
+Z :196 >1 |5=97 =31 *4 *5 +1 $x
+\end{verbatim}
+Here are descriptions of the operations, where capital
+letters are variables:
+
+\begin{description}
+\item{{\bf :N}} \quad \\ 
+Source text has length $N$ (must be first op)
+\item{{\bf >N}} \quad \\
+Final text is $N$ (positive) characters longer than source
+text (must be second op)
+\item{{\bf <N }} \quad \\
+Final text is $N$ (positive) characters shorter than
+source text (must be second op)
+\item{{\bf >0 }} \quad \\
+Final text is same length as source text
+\item{{\bf +N }} \quad \\
+Insert $N$ characters from the bank, none of them newlines
+\item{{\bf -N}} \quad \\
+Skip over (delete) $N$ characters from the source text,
+none of them newlines
+\item{{\bf =N}} \quad \\
+Keep $N$ characters from the source text, none of them newlines
+\item{{\bf |L+N}} \quad \\
+Insert $N$ characters from the source text, containing $L$
+newlines.  The last character inserted MUST be a newline,
+but not the (new) document's final newline.
+\item{{\bf |L-N}}  \quad \\
+Delete $N$ characters from the source text, containing $L$
+newlines. The last character inserted MUST be a newline,
+but not the (old) document's final newline.
+\item{{\bf |L=N}}  \quad \\
+Keep $N$ characters from the source text, containing L
+newlines.  The last character kept MUST be a newline, and
+the final newline of the document is allowed.
+\item{{\bf *I}} \quad \\
+Apply attribute $I$ from the pool to the following
+\verb|+|, \verb|=|, \verb_|+_, or \verb_|=_ command. In
+other words, any number of \verb|*| ops can come before a
+\verb_+_, \verb_=_, or \verb_|_ but not between a \verb_|_
+and the corresponding \verb_+_ or \verb_=_. If \verb_+_,
+text is inserted having this attribute.  If \verb_=_, text
+is kept but with the attribute applied as an attribute
+addition or removal. Consecutive attributes must be sorted
+lexically by (key,value) with key and value taken as
+strings.  It's illegal to have duplicate keys for
+(key,value) pairs that apply to the same text.  It's
+illegal to have an empty value for a key in the case of an
+insertion (\verb_+_), the pair should just be omitted.
+\end{description}
+
+Characters from the source text that aren't accounted for
+are assumed to be kept with the same attributes.
+
+\paragraph{Additional Constraints}
+
+\begin{itemize}
+\item Consecutive \verb_+_, \verb_-_, and \verb_=_ ops of
+  the same type that could be combined are not allowed.
+  Whether combination is possible depends on the
+  attributes of the ops and whether each is multiline or
+ not.  For example, two multiline deletions can never be
+ consecutive, nor can any insertion come after a
+ non-multiline insertion with the same attributes.
+\item ``No-op'' ops are not allowed, such as deleting 0
+  characters.  However, attribute applications that don't
+  have any effect are allowed.
+\item Characters at the end of the source text cannot be
+  explicitly kept with no changes; if the change doesn't
+  affect the last $N$ characters, those ``keep'' ops must
+  be left off.
+\item In any consecutive sequence of insertions (\verb_+_)
+  and deletions (\verb_-_) with no keeps (\verb_=_), the
+  deletions must come before the insertions.
+\item The document text before and after will always end
+  with a newline.  This policy avoids a lot of
+  special-casing of the end of the document.  If a final
+  newline is always added when importing text and removed
+  when exporting text, then the changeset representation
+  can be used to process text files that may or may not
+  have a final newline.
+\end{itemize}
+
+\paragraph{Attribution string}
+
+An \emph{attribution string} is a series of inserts with
+no deletions or keeps.  For example, ``\verb_*3+8|1+5_''
+describes the attributes of a string of length 13, where
+the first 8 chars have attribute 3 and the next 5 chars
+have no attributes, with the last of these 5 chars being a
+newline.  Constraints apply similar to those affecting
+changesets, but the restriction about the final newline of
+the new document being added doesn't apply.
+
+Attributes in an attribution string cannot be empty, like
+``\verb|(bold,)|'', they should instead be absent.
+
+
+\section{Further Considerations}
+
+\begin{itemize}
+\item composing changesets/attributions with different
+  pools.
+\item generalizing ``applyToAttribution'' to make
+  ``mutateAttributionLines'' and ``compose''
+\end{itemize}
+
+\section{Using Unicode?}
+
+\begin{itemize}
+\item no unicode (for efficient escaping, sightliness)
+\item efficient operations for ACE and collab (attributed text, etc.)
+\item good for time-slider
+\item good for API
+\item line-ending aware
+X more coherent (deleting or styling text merging with insertion)
+\item server-side syntax highlighting?
+\item unify author map with attribute pool
+\item unify attributed text with changeset rep
+\item not: reversible
+\item force final newline of document to be preserved
+\end{itemize}
+
+\paragraph{Unicode bad!}
+
+\begin{itemize}
+\item ugly (hard to read)
+\item more complex to parse
+\item harder to store and transmit correctly
+\item doesn't save all that much space anyway
+\item blows up in size when string-escaped
+\item embarrassing for API
+\end{itemize}
+
+
+\end{document}
diff --git a/doc/easysync/etherpad.pdf b/doc/easysync/etherpad.pdf
deleted file mode 100644
index 170b6ccd..00000000
--- a/doc/easysync/etherpad.pdf
+++ /dev/null
diff --git a/doc/easysync/etherpad.tex b/doc/easysync/etherpad.tex
deleted file mode 100644
index a831da64..00000000
--- a/doc/easysync/etherpad.tex
+++ /dev/null
@@ -1,372 +0,0 @@
-\documentclass{article} 
-\usepackage{hyperref}
-
-\begin{document}
-
-\title{Etherpad and EasySync Technical Manual}
-\author{AppJet, Inc., with modifications by the Etherpad Foundation}
-\date{\today}
-
-\maketitle
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\tableofcontents
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-\section{Documents}
-\begin{itemize}
-\item A document is a list of characters, or a string.
-\item A document can also be represented as a list of \emph{changesets}.
-\end{itemize}
-
-\section{Changesets}
-
-\begin{itemize}
-\item A changeset represents a change to a document.
-\item A changeset can be applied to a document to produce a new document.
-\item When a document is represented as a list of changesets, it is assumed that the first changeset applies to the empty document, [].
-\end{itemize}
-
-
-\section{Changeset representation} \label{representation}
-
-$$(\ell \rightarrow \ell')[c_1,c_2,c_3,...]$$
-
-where
-
-\begin{itemize}
-\item[] $\ell$ is the length of the document before the change,
-\item[] $\ell'$ is the length of the document after the change,
-\item[] $[c_1,c_2,c_3,...]$ is an array of $\ell'$ characters that described the document after the change.
-\end{itemize}
-
-Note that $\forall c_i : 0 \leq i \leq \ell'$ is either an integer or a character.
-
-\begin{itemize}
-\item Integers represent retained characters in the original document.
-\item Characters represent insertions.
-\end{itemize}
-
-\section{Constraints on Changesets}
-
-\begin{itemize}
-\item Changesets are canonical and therefor comparable.  When represented in computer memory, we always use the same representation for the same changeset.  If the memory representation of two changesets differ, they must be different changesets.
-\item Changesets are compact.  Thus, if there are two ways to represent a changeset in computer memory, then we always use the representation that takes up the fewest bytes.
-\end{itemize}
-
-Later we will discuss optimizations to changeset
-representation (using ``strips'' and other such
-techniques).  The two constraints must apply to any
-representation of changesets.
-
-\section{Notation}
-
-\begin{itemize}
-\item We use the algebraic multiplication notation to represent changeset application.
-\item While changesets are defined as operations on documents, documents themselves are represented as a list of changesets, initially applying to the empty document.
-\end{itemize}
-
-\paragraph{Example}
-$A=(0\rightarrow 5)[``hello"]$
-$B=(5\rightarrow 11)[0-4, ``\ world"]$
-
-We can write the document ``hello world'' as $A\cdot B$ or
-just $AB$.  Note that the ``initial document'' can be made
-into the changeset $(0\rightarrow
-N)[``<\mathit{the\ document\ text}>"]$.
-
-When $A$ and $B$ are changesets, we can also refer to $(AB)$ as ``the composition'' of $A$ and $B$.  Changesets are closed under composition.
-
-\section{Composition of Changesets}
-
-For any two changesets $A$, $B$ such that
-
-\begin{itemize}
-\item[] $A=(n_1\rightarrow n_2)[\cdots]$
-\item[] $A=(n_2\rightarrow n_3)[\cdots]$
-\end{itemize}
-it is clear that there is a third changeset $C=(n_1\rightarrow n_3)[\cdots]$ such that applying $C$ to a document $X$ yeilds the same resulting document as does applying $A$ and then $B$.  In this case, we write $AB=C$.
-
-Given the representation from Section \ref{representation}, it is straightforward to compute the composition of two changesets.
-
-\section{Changeset Merging}
-
-Now we come to realtime document editing.  Suppose two different users make two different changes to the same document at the same time.  It is impossible to compose these changes.    For example, if we have the document $X$ of length $n$, we may have $A=(n\rightarrow n_a)[\ldots n_a \mathrm{characters}]$,  $B=(n\rightarrow n_b)[\ldots n_b \mathrm{characters}]$ where $n\neq n_a\neq n_b$.
-
-It is impossible to compute $(XA)B$ because $B$ can only be applied to a document of length $n$, and $(XA)$ has length $n_a$.  Similarly, $A$ cannot be appliet to $(XB)$ because $(XB)$ has length $n_b$.
-
-This is where \emph{merging} comes in.  Merging takes two changesets that apply to the same initial document (and that cannot be composed), and computes a single new changeset that presevers the intent of both changes.  The merge of $A$ and $B$ is written as $m(A,B)$.  For the Etherpad system to work, we require that $m(A,B)=m(B,A)$.
-
-Aside from what we have said so far about merging, there aremany different implementations that will lead to a workable system.  We have created one implementation for text that has the following constraints.
-
-\section{Follows} \label{follows}
-
-When users $A$ and $B$ have the same document $X$ on their screen, and they proceed to make respective changesets $A$ and $B$, it is no use to compute $m(A,B)$, because $m(A,B)$ applies to document $X$, but the users are already looking at document $XA$ and $XB$.  What we really want is to compute $B'$ and $A'$ such that
-$$XAB' = XBA' = Xm(A,B)$$
-
-``Following'' computes these $B'$ and $A'$ changesets.  The definition of the ``follow'' function $f$ is such that $Af(A,B)=Bf(B,A)=m(A,B)=m(B,A)$.  When we computer $f(A,B)$.
-\begin{itemize}
-\item Insertions in $A$ become retained characters in $f(A,B)$
-\item Insertions in $B$ become insertions in $f(A,B)$
-\item Retain whatever characters are retained in \emph{both} $A$ and $B$
-\end{itemize}
-
-\paragraph{Example}
-
-Suppose we have the initial document $X=(0\rightarrow 8)[``\mathit{baseball}"]$ and user $A$ changes it to ``basil'' with changeset $A$, and user $B$ changes it to ``below'' with changeset $B$.
-
-We have
-$X=(0\rightarrow 8)[``\mathit{baseball}"]$ \\
-$A=(8\rightarrow 5)[0-1, ``\mathit{si}", 7]$ \\
-$B=(8\rightarrow 5)[0, ``\mathit{e}", 6, ``\mathit{ow}"]$ \\
-
-First we compute the merge $m(A,B)=m(B,A)$ according to the constraints
-
-$$m(A,B)=(8\rightarrow 6)[0, "e", "si", "ow"] = (8\rightarrow 6)[0, ``\mathit{esiow}"]$$
-
-Then we need to compute the follows $B'=f(A,B)$ and $A'=f(B,A)$.
-
-$$B'=f(A,B)=(5\rightarrow 6)[0,``\mathit{e}",2,3,``\mathit{ow}"]$$
-
-Note that the numbers $0$, $2$, and $3$ are indices into $A=(8\rightarrow 5)[0,1,``\mathit{si}",7]$
-
-\begin{tabular}{ccccc}
-0 & 1 & 2 & 3 & 4 \\
-0 & 1 & s & i & 7
-\end{tabular}
-
-$A'=f(B,A)=(5\rightarrow 6)[0,1,"si",3,4]$
-
-We can now double check that $AB'=BA'=m(A,B)=(8\rightarrow 6)[0,``\mathit{esiow}"]$.
-
-Now that we have made the mathematical meaning of the
-preceding pages complete, we can build a client/server
-system to support realtime editing by multiple users.
-
-\section{System Overview}
-
-There is a server that holds the current state of a
-document.  Clients (users) can connect to the server from
-their web browsers.  The clients and server maintain state
-and can send messages to one another in real-time, but
-because we are in a web browser scenario, clients cannot
-send each other messages directly, and must go through the
-server always.  (This may distinguish from prior art?)
-
-The other critical design feature of the system is that
-\emph{A client must always be able to edit their local
-  copy of the document, so the user is never blocked from
-  typing because of waiting to to send or receive data.}
-
-\section{Client State}
-
-At any moment in time, a client maintains its state in the
-form of 3 changesets.  The client document looks like
-$A\cdot X \cdot Y$, where
-
-$A$ is the latest server version, the composition of all
-changesets committed to the server, from this client or
-from others, that the server has informed this client
-about.  Initially $A=(0\rightarrow N)[<\mathit{initial\ document\ text}>]$.
-
-$X$ is the composition of all changesets this client has
-submitted to the server but has not heard back about yet.
-Initially $X=(N\rightarrow N)[0,1,2,\ldots, N-1]$, in
-other words, the identity, henceforth denoted $I_N$.
-
-$Y$ is the composition of all changesets this client has
-made but has not yet submitted to the server yet.
-Initially $Y=(N\rightarrow N)[0,1,2,\ldots, N-1]$.
-
-\section{Client Operations}
-
-A client can do 5 things.
-
-\begin{enumerate}
-\item Incorporate new typing into local state
-\item Submit a changeset to the server
-\item Hear back acknowledgement of a submitted changeset
-\item Hear from the server about other clients' changesets
-\item Connect to the server and request the initial document
-\end{enumerate}
-
-As these 5 events happen, the client updates its
-representation $A\cdot X \cdot Y$ according to the
-relations that follow.  Changes ``move left'' as time goes
-by: into $Y$ when the user types, into $X$ when change
-sets are submitted to the server, and into $A$ when the
-server acknowledges changesets.
-
-\subsection{New local typing}
-
-When a user makes an edit $E$ to the document, the client
-computes the composition $(Y\cdot E)$ and updates its local
-state, i.e. $Y \leftarrow Y\cdot E$.  I.e., if $Y$ is the
-variable holding local unsubmitted changes, it will be
-assigned the new value $(Y\cdot E)$.
-
-\subsection{Submitting changesets to server}
-
-When a client submit its local changes to the server, it
-transmits a copy of $Y$ and then assigns $Y$ to $X$, and
-assigns the identity to $Y$.  I.e.,
-
-\begin{enumerate}
-\item Send $Y$ to server,
-\item $X \leftarrow Y$
-\item $Y \leftarrow I_N$
-  (the identity).
-\end{enumerate}
-
-This happens every 500ms as long as it receives an
-acknowledgement.  Must receive ACK before submitting
-again.  Note that $X$ is always equal to the identity
-before the second step occurs, so no information is lost.
-
-\subsection{Hear ACK from server}
-
-When the client hears ACK from server,
-
-$A \leftarrow A\cdot X$ \\
-$X \leftarrow I_N$
-
-\subsection{Hear about another client's changeset}
-
-When a client hears about another client's changeset $B$,
-it computes a new $A$, $X$, and $Y$, which we will call
-$A'$, $X'$, and $Y'$ respectively.  It also computes a
-changeset $D$ which is applied to the current text view on
-the client, $V$.  Because $AXY$ must always equal the
-current view, $AXY=V$ before the client hears about $B$,
-and $A'X'Y'=VD$ after the computation is performed.
-
-The steps are:
-
-\begin{enumerate}
-\item Compute $A' = AB$
-\item Compute $X' = f(B,X)$
-\item Compute $Y' = f(f(X,B), Y)$
-\item Compute $D=f(Y,f(X,B))$
-\item Assign $A \leftarrow A'$, $X \leftarrow X'$, $Y \leftarrow Y'$.
-\item Apply $D$ to the current view of the document
-  displayed on the user's screen.
-\end{enumerate}
-
-In steps 2,3, and 4, $f$ is the follow operation described
-in Section \ref{follows}.
-
-\paragraph{Proof that $\mathbf{AXY=V \Rightarrow A'X'Y'=VD}$.}
-Substituting $A'X'Y'=(AB)(f(B,X))(f(f(X,B),Y))$, we
-recall that merges are commutative.  So for any two
-changesets $P$ and $Q$, 
-$$m(P,Q)=m(Q,P)=Qf(Q,P)=Pf(P,Q)$$
-
-Applying this to the relation above, we see
-\begin{eqnarray*}
-A'X'Y'&=& AB f(B,X) f(f(X,B),Y) \\
-      &=&AX f(X,B) f(f(X,B),Y) \\
-      &=&A X Y f(Y, f(X,B)) \\
-      &=&A X Y D \\
-      &=&V D 
-\end{eqnarray*}
-As claimed.
-
-\subsection{Connect to server}
-
-When a client connects to the server for the first time,
-it first generates a random unique ID and sends this to
-the server.  The client remembers this ID and sends it
-with each changeset to the server.
-
-The client receives the latest version of the document
-from the server, called HEADTEXT.  The client then sets
-
-\begin{itemize}
-\item[] $A \leftarrow \mathrm{HEADTEXT}$
-\item[] $X \leftarrow I_N$
-\item[] $Y \leftarrow I_N$
-\end{itemize}
-
-And finally, the client displays HEADTEXT on the screen.
-
-\section{Server Overview}
-
-Like the client(s), the server has state and performs
-operations.  Operations are only performed in response to
-messages from clients.
-
-\section{Server State}
-
-The server maintains a document as an ordered list of
-\emph{revision records}.  A revision record is a data
-structure that contains a changeset and authorship
-information.
-
-\begin{verbatim}
-RevisionRecord = {
-  ChangeSet,
-  Source (unique ID),
-  Revision Number (consecutive order, starting at 0)
-}
-\end{verbatim}
-
-For efficiency, the server may also store a variable
-called HEADTEXT, which is the composition of all
-changesets in the list of revision records.  This is an
-optimization, because clearly this can be computed from
-the set of revision records.
-
-\section{Server Operations Overview}
-
-The server does two things in addition to maintaining
-state representing the set of connected clients and
-remembering what revision number each client is up to date
-with:
-
-\begin{enumerate}
-\item Respond to a client's connection requesting the initial document.
-\item Respond to a client's submission of a new changeset.
-\end{enumerate}
-
-\subsection{Respond to client connect}
-When a server recieves a connection request from a client,
-it receives the client's unique ID and stores that in the
-server's set of connected clients.  It then sends the
-client the contents of HEADTEXT, and the corresponding
-revision number.  Finally the server notes that this
-client is up to date with that revision number.
-
-\subsection{Respond to client changeset}
-
-When the server receives information from a client about
-the client's changeset $C$, it does five things:
-
-\begin{enumerate}
-\item Notes that this change applies to revision number
-  $r_c$ (the client's latest revision).
-\item Creates a new changeset $C'$ that is relative to the
-  server's most recent revision number, which we call
-  $r_H$ ($H$ for HEAD).  $C'$ can be computed using
-  follows (Section \ref{follows}).  Remember that the server has a series of
-  changesets, 
-$$S_0\rightarrow S_1\rightarrow \ldots S_{r_c}\rightarrow S_{r_c+1} \rightarrow \ldots \rightarrow S_{r_H} $$
-$C$ is relative to $S_{r_c}$, but we need to compute $C'$ relative to $S_{r_H}$.
-We can compute a new $C$ relative to $S_{r_c+1}$ by computing $f(S_{r_c+1},C)$.  Similarly we can repeat for
-$S_{r_c+2}$ and so forth until we have $C'$ represented relative to $S_{r_H}$.
-\item Send $C'$ to all other clients
-\item Send ACK back to original client
-\item Add $C'$ to the server's list of revision records by creating a new revision record out of this and the client's ID.
-
-\appendix
-
-\section*{Additional topics}
-\begin{enumerate}
-\item Optimizations (strips, more caching, etc.)
-\item Pseudocode for composition, merge, and follow
-\item How authorship information is used to color-code the document based on who typed what
-\item How persistent connections are maintained between client and server
-\end{enumerate}
-\end{enumerate}
-
-
-\end{document}