branch: externals/crdt
commit 973e761f125b27f1c2c19d4939444dca6a1fdd0c
Author: Qiantan Hong <qh...@mit.edu>
Commit: Qiantan Hong <qh...@mit.edu>
Work on Jean's todo list
- better formatting for docs
- a few more clarification in README
- separate crdt-stop-session and crdt-disconnect
- ask for confirmation when stopping a session
- default display to user full name
- default crdt-connect port to 6530
---
HACKING.org | 27 +++++++++--
README.org | 55 ++++++++++++++++++-----
crdt.el | 146 +++++++++++++++++++++++++++++++++++++++---------------------
3 files changed, 164 insertions(+), 64 deletions(-)
diff --git a/HACKING.org b/HACKING.org
index e20327e..d6bc99b 100644
--- a/HACKING.org
+++ b/HACKING.org
@@ -1,5 +1,7 @@
* Algorithm
+Background reading:
[[https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type][CRDT]]
+
This packages implements the Logoot split algorithm
~André, Luc, et al. "Supporting adaptable granularity of changes for
massive-scale collaborative editing." 9th IEEE International Conference on
Collaborative Computing: Networking, Applications and Worksharing. IEEE, 2013.~
@@ -17,60 +19,76 @@ and second last two bytes represent site ID.
=CRDT--SESSION-LIST= is a list of "CRDT status buffer"s.
Currently those buffers are always empty, but they have some buffer local
variables,
which are used as "session variables" that can be accessed from any buffer
shared in the same session.
+
For a buffer shared in some session, this buffer always has its buffer local
variable
=CRDT--STATUS-BUFFER= set to a CRDT status buffer. It can then access any
session variables through it.
+
For a network process dedicated to a session, its ='status-buffer= process
property is always set to the status buffer for that session.
+
The macro =CRDT--DEFVAR-SESSION= do the chores of defining a buffer local
variable for status buffer,
and creating a function (together with =SETF= setter) with the same name as
the variables, and can
be invoked with no argument in any CRDT shared buffer to access or modify that
session variable.
-
* Protocol
+
Text-based version
(it should be easy to migrate to a binary version. Using text for better
debugging for now)
- Every message takes the form (type . body)
+
+ Every message takes the form =(type . body)=
+
type can be: insert delete cursor hello challenge sync desync
overlay-(add,move,put,remove)
+
- insert ::
body takes the form =(buffer-name crdt-id position-hint content)=
- =position-hint= is the buffer position where the operation happens at
the site
which generates the operation. Then we can play the trick that start
search
near this position at other sites to speedup CRDT ID search
- =content= is the string to be inserted
+
- delete ::
body takes the form =(buffer-name position-hint (crdt-id . length)*)=
+
- cursor ::
body takes the form
=(site-id point-position-hint point-crdt-id mark-position-hint
mark-crdt-id)=
=*-crdt-id= can be either a CRDT ID, or
- =nil=, which means clear the point/mark
- =""=, which means =(point-max)=
+
- contact ::
body takes the form
=(site-id name address port)=
when name is =nil=, clear the contact for this =site-id=
+
- focus ::
body takes the form =(site-id buffer-name)=
+
- hello ::
This message is sent from client to server, when a client connect to the
server.
body takes the form =(client-name &optional response)=
+
- challenge ::
body takes the form =(salt)=
+
- login ::
It's always sent after server receives a hello message.
Assigns an ID to the client
body takes the form =(site-id session-name)=.
+
- sync ::
This message is sent from server to client to get it sync to the state on
the server.
Might be used for error recovery or other optimization in the future.
One optimization I have in mind is let server try to merge all CRDT item
into a single
one and try to synchronize this state to clients at best effort.
- body takes the form =(buffer-name major-mode content . crdt-id-list)=
+ body takes the form =(buffer-name major-mode . crdt-id-list)=
- =major-mode= is the major mode used at the server site
- =content= is the string in the buffer
- =crdt-id-list= is generated from =CRDT--DUMP-IDS=
+
- desync ::
Indicates that the server has stopped sharing a buffer.
body takes the form =(buffer-name)=
+
- overlay-add ::
body takes the form
#+BEGIN_SRC
@@ -79,6 +97,7 @@ be invoked with no argument in any CRDT shared buffer to
access or modify that s
start-position-hint start-crdt-id
end-position-hint end-crdt-id)
#+END_SRC
+
- overlay-move ::
body takes the form
#+BEGIN_SRC
@@ -86,8 +105,10 @@ be invoked with no argument in any CRDT shared buffer to
access or modify that s
start-position-hint start-crdt-id
end-position-hint end-crdt-id)
#+END_SRC
+
- overlay-put ::
body takes the form =(buffer-name site-id logical-clock prop value)=
+
- overlay-remove ::
body takes the form =(buffer-name site-id logical-clock)=
diff --git a/README.org b/README.org
index 2e0ad26..682d279 100644
--- a/README.org
+++ b/README.org
@@ -1,4 +1,5 @@
* Introduction
+
~crdt.el~ is a real-time collaborative editing environment for Emacs using
Conflict-free Replicated Data Types.
Highlights:
@@ -6,30 +7,62 @@ Highlights:
- Share multiple buffer in one session
- See other users' cursor and region
- (experimental) synchronize Org mode folding status
+
* Usage
+
** Installation
+
Just =M-x load-file= =crdt.el=, or =M-x eval-buffer= in =crdt.el=,
or =(require 'crdt)=. Or whatever package management tool you use.
-** Share a buffer
-In that buffer, =M-x crdt-share-buffer=. Then enter session name.
-
-If a new session is to be created, enter port, optional password and your
display name.
-If there's a existing session with the name, current buffer is added to that
session.
-** Connect to a shared buffer
-=M-x crdt-connect=
-** List active users.
+
+** Start a shared session
+
+A shared session is a place that can contains multiple buffers (or files),
+and multiple users can join to collaboratively edit those buffers (or files).
+Think about a meeting room with some people working together on some papers.
+
+In some buffer, =M-x crdt-share-buffer=. Then enter session name.
+This add the current buffer to the existing session with that name.
+If no such exists, it creates a new session with the provided session name,
+and initially contains the current buffer as a shared buffer.
+
+If a new session is to be created, you need to enter port (default to 6530),
+optional password and your display name (default to your current
=(USER-FULL-NAME)=).
+
+** Join a session
+
+=M-x crdt-connect=, then enter address, port, and your display name.
+
+** List active users
+
In a CRDT shared buffer (either server or client), =M-x crdt-list-users=.
In the displayed user list, press ~RET~ on an entry to goto that user's cursor
position.
-** List all sessions, and buffer in current session.
+
+** List all sessions, and buffer in current session
+
=M-x crdt-list-sessions= lists all sessions.
+
=M-x crdt-list-buffers= lists all buffers in current session. Or you can also
press ~RET~ in the session list to see buffers in the selected session.
-** Stop sharing.
-=M-x crdt-stop-session= stops the current session. You can also press ~k~ in
the session list.
+
+** Stop sharing
+
+=M-x crdt-stop-session= stops a session you've started and disconnect all
other users from it.
+This will ask for your confirmation, customize =crdt-confirm-stop-session= if
you want to disable it.
+
+You can also press ~k~ in the session list (show it by =M-x
crdt-list-sessions=).
=M-x crdt-stop-share-buffer= removes current buffer from its CRDT session
(this operation is only allowed at server side). Or press ~k~ in the buffer
list.
+
+** Disconnect from a session
+
+=M-x crdt-disconnect=, then choose a session to disconnect from.
+
+You can also press ~k~ in the session list (show it by =M-x
crdt-list-sessions=).
+
** Synchronizing Org folding status
+
Turn on =crdt-org-sync-overlay-mode=. All peers that have this enabled have
their
folding status synchronized. Peers without enabling this minor mode are
unaffected.
diff --git a/crdt.el b/crdt.el
index 4ea6043..9b33c83 100644
--- a/crdt.el
+++ b/crdt.el
@@ -32,10 +32,10 @@
:group 'applications)
(defcustom crdt-ask-for-name t
- "Ask for display name everytime a CRDT session is to be started."
+ "Ask for display name everytime a CRDT session is to be started or
connected."
:type 'boolean)
-(defcustom crdt-default-name "anonymous"
+(defcustom crdt-default-name (user-full-name)
"Default display name."
:type 'string)
@@ -43,6 +43,11 @@
"Ask for server password everytime a CRDT server is to be started."
:type 'boolean)
+(defcustom crdt-confirm-stop-session t
+ "Ask for confirmation when a CRDT server is to be stopped,
+and there are some client connected to it currently."
+ :type 'boolean)
+
(require 'cl-lib)
(require 'subr-x)
@@ -376,7 +381,7 @@ to avoid recusive calling of CRDT synchronization
functions.")
(interactive)
(with-current-buffer
(tabulated-list-get-id)
- (crdt-stop-session)))
+ (crdt--stop-session (current-buffer))))
(defvar crdt-session-menu-mode-map
(let ((map (make-sparse-keymap)))
@@ -726,9 +731,9 @@ Start the search from POS."
`(delete ,crdt--buffer-network-name
,beg ,@ (crdt--dump-ids 0 (length crdt--changed-string)
crdt--changed-string t)))
-(defun crdt--remote-delete (position-hint id-pairs)
- (dolist (id-pair id-pairs)
- (cl-destructuring-bind (length . id) id-pair
+(defun crdt--remote-delete (position-hint id-items)
+ (dolist (id-item id-items)
+ (cl-destructuring-bind (length id) id-item
(while (> length 0)
(goto-char (crdt--find-id id position-hint t))
(let* ((end-of-block (next-single-property-change (point) 'crdt-id nil
(point-max)))
@@ -836,31 +841,39 @@ Start the search from POS."
;;; CRDT ID (de)serialization
-(defun crdt--dump-ids (beg end object &optional omit-end-of-block-p)
- "Serialize all CRDT ids in OBJECT from BEG to END into a list.
-The list contains CONSes of the form (LENGTH CRDT-ID-BASE64 . END-OF-BLOCK-P),
-or (LENGTH . CRDT-ID-BASE64) if OMIT-END-OF-BLOCK-P is non-NIL.
-in the order that they appears in the document"
+(defun crdt--dump-ids (beg end object &optional omit-end-of-block-p
include-content)
+ "Serialize all CRDT IDs in OBJECT from BEG to END into a list.
+The list contains CONSes of the form (LENGTH CRDT-ID-BASE64 END-OF-BLOCK-P),
+or (LENGTH CRDT-ID-BASE64) if OMIT-END-OF-BLOCK-P is non-NIL,
+in the order that they appears in the document.
+If INCLUDE-CONTENT is non-NIL, the list contains STRING instead of LENGTH."
(let (ids (pos end))
(while (> pos beg)
(let ((prev-pos (previous-single-property-change pos 'crdt-id object
beg)))
- (push (cons (- pos prev-pos)
- (cl-destructuring-bind (id . eob) (crdt--get-crdt-id-pair
prev-pos object)
- (let ((id-base64 (base64-encode-string id)))
- (if omit-end-of-block-p id-base64 (cons id-base64
eob)))))
- ids)
+ (when (crdt--get-crdt-id-pair prev-pos object)
+ (push (cons (if include-content
+ (cond ((not object) (buffer-substring-no-properties
prev-pos pos))
+ ((bufferp object)
+ (with-current-buffer object
+ (buffer-substring-no-properties prev-pos
pos)))
+ (t (substring object prev-pos pos)))
+ (- pos prev-pos))
+ (cl-destructuring-bind (id . eob)
(crdt--get-crdt-id-pair prev-pos object)
+ (print omit-end-of-block-p)
+ (let ((id-base64 (base64-encode-string id)))
+ (if omit-end-of-block-p (list id-base64) (list
id-base64 eob)))))
+ ids))
(setq pos prev-pos)))
ids))
(defun crdt--load-ids (ids)
"Load the CRDT ids in IDS (generated by CRDT--DUMP-IDS)
into current buffer."
- (let ((pos (point-min)))
- (dolist (id-pair ids)
- (let ((next-pos (+ pos (car id-pair))))
- (put-text-property pos next-pos 'crdt-id
- (cons (base64-decode-string (cadr id-pair)) (cddr
id-pair)))
- (setq pos next-pos)))))
+ (goto-char (point-min))
+ (dolist (id-item ids)
+ (cl-destructuring-bind (content id-base64 eob) id-item
+ (insert (propertize content 'crdt-id
+ (cons (base64-decode-string id-base64) eob))))))
(defun crdt--verify-buffer ()
"Debug helper function.
@@ -883,7 +896,9 @@ Verify that CRDT IDs in a document follows ascending order."
;;; Network protocol
(defun crdt--format-message (args)
- (format "%S" args))
+ (let ((print-level nil)
+ (print-length nil))
+ (prin1-to-string args)))
(cl-defun crdt--broadcast-maybe (message-string &optional (without t))
"Broadcast or send MESSAGE-STRING.
@@ -936,8 +951,7 @@ to server when WITHOUT is T."
(process-send-string process (crdt--format-message `(sync
,crdt--buffer-network-name
,major-mode
-
,(buffer-substring-no-properties (point-min) (point-max))
- ,@
(crdt--dump-ids (point-min) (point-max) nil))))
+ ,@
(crdt--dump-ids (point-min) (point-max) nil nil t))))
;; synchronize cursor
(maphash (lambda (site-id ov-pair)
(cl-destructuring-bind (cursor-ov . region-ov)
ov-pair
@@ -1033,7 +1047,7 @@ Must be called when CURRENT-BUFFER is a CRDT status
buffer."
(cl-defmethod crdt-process-message ((message (head delete)) process)
(crdt--broadcast-maybe (crdt--format-message message) (process-get process
'client-id))
(cl-destructuring-bind (buffer-name position-hint . id-base64-pairs) (cdr
message)
- (mapc (lambda (p) (rplacd p (base64-decode-string (cdr p))))
id-base64-pairs)
+ (mapc (lambda (p) (rplaca (cdr p) (base64-decode-string (cadr p))))
id-base64-pairs)
(crdt--with-buffer-name
buffer-name
(crdt--remote-delete position-hint id-base64-pairs))))
@@ -1055,7 +1069,7 @@ Must be called when CURRENT-BUFFER is a CRDT status
buffer."
(cl-defmethod crdt-process-message ((message (head sync)) process)
(unless (crdt--server-p) ; server shouldn't receive this
- (cl-destructuring-bind (buffer-name mode content . ids) (cdr message)
+ (cl-destructuring-bind (buffer-name mode . ids) (cdr message)
(crdt--with-buffer-name
buffer-name
(erase-buffer)
@@ -1064,7 +1078,6 @@ Must be called when CURRENT-BUFFER is a CRDT status
buffer."
(funcall mode) ; trust your server...
(crdt-mode))
(message "Server uses %s, but not available locally." mode))
- (insert content)
(crdt--load-ids ids)))
(crdt--refresh-buffers-maybe)))
@@ -1166,7 +1179,7 @@ Must be called when CURRENT-BUFFER is a CRDT status
buffer."
(process-contact process :host)
(process-contact process :service))
(if (crdt--server-p)
(delete-process process)
- (crdt-stop-session))))))
+ (crdt--stop-session crdt--status-buffer))))))
(delete-region (point-min) (point))
(goto-char (point-min)))))))
@@ -1192,7 +1205,7 @@ Must be called when CURRENT-BUFFER is a CRDT status
buffer."
(defun crdt--client-process-sentinel (process message)
(with-current-buffer (process-get process 'status-buffer)
(unless (eq (process-status process) 'open)
- (crdt-stop-session))))
+ (crdt--stop-session (current-buffer)))))
;;; UI commands
@@ -1223,12 +1236,15 @@ Must be called when CURRENT-BUFFER is a CRDT status
buffer."
,@ (crdt--dump-ids (point-min) (point-max)
nil)))))
(crdt--refresh-buffers-maybe)
(crdt--refresh-sessions-maybe))
- (message "Only server can add new buffer.")))
+ (error "Only server can add new buffer")))
-(defsubst crdt--get-session-names ()
- (mapcar (lambda (s)
- (with-current-buffer s crdt--session-name))
- crdt--session-list))
+(defsubst crdt--get-session-names (server)
+ (let (session-names)
+ (dolist (status-buffer crdt--session-list)
+ (with-current-buffer status-buffer
+ (when (eq (crdt--server-p) server)
+ (push crdt--session-name session-names))))
+ (nreverse session-names)))
(defsubst crdt--get-session (name)
(cl-find name crdt--session-list
@@ -1242,8 +1258,8 @@ If SESSION-NAME is empty, use the buffer name of the
current buffer."
(progn
(when (and crdt-mode crdt--status-buffer)
(error "Current buffer is already shared in a CRDT session"))
- (list (let ((session-name (completing-read "Enter a session name (create
if not exist): "
- (crdt--get-session-names))))
+ (list (let ((session-name (completing-read "Choose a server session
(create if not exist): "
+ (crdt--get-session-names t))))
(unless (and session-name (> (length session-name) 0))
(setq session-name (buffer-name (current-buffer))))
session-name))))
@@ -1251,6 +1267,8 @@ If SESSION-NAME is empty, use the buffer name of the
current buffer."
(if session
(crdt--share-buffer (current-buffer) session)
(let ((port (read-from-minibuffer "Create new session on port (default
6530): " nil nil t nil "6530")))
+ (when (not (numberp port))
+ (error "Port must be a number"))
(crdt--share-buffer (current-buffer) (crdt-new-session port
session-name))))))
(defun crdt-stop-share-buffer ()
@@ -1304,16 +1322,15 @@ If SESSION-NAME is empty, use the buffer name of the
current buffer."
(push new-session crdt--session-list)
new-session))
-(defun crdt-stop-session (&optional session-name)
- "Stop sharing the current session."
- (interactive
- (list (completing-read "Choose a session (create if not exist): "
- (crdt--get-session-names) nil t
- (when crdt--status-buffer (crdt--session-name)))))
- (let ((status-buffer (if session-name
- (crdt--get-session session-name)
- crdt--status-buffer)))
- (with-current-buffer status-buffer
+(defun crdt--stop-session (status-buffer)
+ "Kill the session associated with STATUS-BUFFER.
+Disconnect if it's a client session, or stop serving if it's a server session."
+ (with-current-buffer status-buffer
+ (when (if (and crdt-confirm-stop-session
+ (crdt--server-p)
+ crdt--network-clients)
+ (yes-or-no-p "Stopping the session will disconnect every client,
proceed? ")
+ t)
(dolist (client crdt--network-clients)
(when (process-live-p client)
(delete-process client))
@@ -1331,13 +1348,42 @@ If SESSION-NAME is empty, use the buffer name of the
current buffer."
(delq status-buffer crdt--session-list))
(crdt--refresh-sessions-maybe)
(delete-process crdt--network-process)
- (message "Disconnected."))
- (kill-buffer status-buffer)))
+ (message "Disconnected.")
+ (kill-buffer status-buffer))))
+
+(defun crdt-stop-session (&optional session-name)
+ "Stop sharing the session with SESSION-NAME.
+If SESSION-NAME is nil, stop sharing the current session."
+ (interactive
+ (list (completing-read "Choose a server session: "
+ (crdt--get-session-names t) nil t
+ (when (and crdt--status-buffer (crdt--server-p))
+ (crdt--session-name)))))
+ (let ((status-buffer (if session-name
+ (crdt--get-session session-name)
+ crdt--status-buffer)))
+ (crdt--stop-session status-buffer)))
+
+(defun crdt-disconnect (&optional session-name)
+ (interactive
+ (list (completing-read "Choose a client session: "
+ (crdt--get-session-names nil) nil t
+ (when (and crdt--status-buffer (not
(crdt--server-p)))
+ (crdt--session-name)))))
+ (let ((status-buffer (if session-name
+ (crdt--get-session session-name)
+ crdt--status-buffer)))
+ (crdt--stop-session status-buffer)))
(defun crdt-connect (address port &optional name)
"Connect to a CRDT server running at ADDRESS:PORT.
Open a new buffer to display the shared content."
- (interactive "MAddress: \nnPort: ")
+ (interactive
+ (list (read-from-minibuffer "Address: ")
+ (let ((port (read-from-minibuffer "Port (default 6530): " nil nil t
nil "6530")))
+ (when (not (numberp port))
+ (error "Port must be a number"))
+ port)))
(unless name
(setq name (crdt--read-name)))
(setq crdt--status-buffer
