big change...

6 files changed, 215 insertions, 67 deletions

diff --git a/server/src/authority_string_transformer.py b/server/src/authority_string_transformer.py
index f99daa1..2d58e6e 100644
--- a/server/src/authority_string_transformer.py
+++ b/server/src/authority_string_transformer.py
@@ -3,7 +3,7 @@
 from users_text_manager import AUTHORITY
 
 
-_mappings = [
+_MAPPINGS = [
     (AUTHORITY.READONLY, 'RO'),
     (AUTHORITY.READWRITE, 'RW'),
 ]
@@ -23,7 +23,7 @@ def to_string(authority):
     Return:
         Corrosponding authority in string format.
     """
-    for item in _mappings:
+    for item in _MAPPINGS:
         if item[0] == authority:
             return item[1]
     raise Error('Invalid number.')
@@ -38,7 +38,7 @@ def to_number(string):
     Return:
         Corrosponding authority in number format.
     """
-    for item in _mappings:
+    for item in _MAPPINGS:
         if item[1] == string:
             return item[0]
     raise Error('Invalid string.')
diff --git a/server/src/cmd_ui.py b/server/src/cmd_ui.py
index b7079da..94cbf61 100644
--- a/server/src/cmd_ui.py
+++ b/server/src/cmd_ui.py
@@ -40,7 +40,7 @@ class CmdUI(cmd.Cmd):  # pylint: disable=R0904
             tcp_server: An instance of TCPServer.
             shared_vim_server: An instance of SharedVimServer.
         """
-        super(CmdUI, self).__init__(INTRO)
+        super(CmdUI, self).__init__()
         self.prompt = PROMPT
         self._users_text_manager = users_text_manager
         self._tcp_server = tcp_server
@@ -182,6 +182,14 @@ class CmdUI(cmd.Cmd):  # pylint: disable=R0904
         """Echo."""
         print(text)
 
+    def do_eval(self, text):
+        """For debug, evaluate an peice of python code and prints the result."""
+        try:
+            result = eval(text)  # pylint: disable=W0123
+            self.write('The result is %r\n' % result)
+        except Exception as e:  # pylint: disable=W0703
+            self.write('Exception occured: %r' % e)
+
     def do_help(self, text):
         """Prints the help document, [usage] help"""
         try:
diff --git a/server/src/log.py b/server/src/log.py
index 93ec9bc..9873ade 100644
--- a/server/src/log.py
+++ b/server/src/log.py
@@ -14,7 +14,7 @@ def info(string):
         string: String to be printed.
     """
     with _lock:
-        info.interface.write(string)
+        info.interface.write('info: ' + string)
         info.interface.flush()
 
 info.interface = sys.stdout  # Interface of the info string to be printed at.
@@ -27,7 +27,7 @@ def error(string):
         string: String to be printed.
     """
     with _lock:
-        error.interface.write(string)
+        error.interface.write('error: ' + string)
         error.interface.flush()
 
 error.interface = sys.stderr  # Interface of the error string to be printed at.
diff --git a/server/src/request_handler.py b/server/src/request_handler.py
index 9d820e4..458c554 100644
--- a/server/src/request_handler.py
+++ b/server/src/request_handler.py
@@ -1,5 +1,7 @@
 """RequestHandler."""
 
+import bisect
+import difflib
 import log
 
 from users_text_manager import AUTHORITY
@@ -10,19 +12,145 @@ class JSON_TOKEN:  # pylint:disable=W0232
     """Enumeration the Ttken strings for json object."""
     BYE = 'bye'  # Resets the user and do nothong.
     CURSORS = 'cursors'  # other users' cursor position
+    DIFF = 'diff'  # Difference between this time and last time.
     ERROR = 'error'  # error string
     IDENTITY = 'identity'  # identity of myself
     INIT = 'init'  # initialize connect flag
     MODE = 'mode'  # vim mode.
     NICKNAME = 'nickname'  # nick name of the user.
     OTHERS = 'others'  # other users info.
-    TEXT = 'text'  # text content in the buffer
+
+
+def apply_patch(orig_lines, patch_info):
+    """Applies a patch.
+
+    Args:
+        orig_lines: Original lines of the text.
+        patch_info: A list of replacing information.
+
+    Return:
+        A list of text.
+    """
+    new_lines, done_len = [], 0
+    for beg, end, lines in patch_info:
+        new_lines += orig_lines[done_len : beg]
+        new_lines += lines
+        done_len = end
+    return new_lines + orig_lines[done_len : ]
+
+
+def _squash_patch(patch_info):
+    """Squash list of replacing information to a smaller mount of information.
+
+    Args:
+        patch_info: Information of patches.
+
+    Return:
+        A list of replacing information.
+    """
+    ret, index = [], 0
+    while index < len(patch_info):
+        lines = patch_info[index][2]
+        index2 = index + 1
+        while index2 < len(patch_info) and \
+              patch_info[index2 - 1][1] >= patch_info[index2][0]:
+            lines += patch_info[index2][2]
+            index2 += 1
+        ret.append((patch_info[index][0], patch_info[index2 - 1][1], lines))
+        index = index2
+    return ret
+
+
+def gen_patch(orig_lines, new_lines):
+    """Creates a patch from two lines text.
+
+    Args:
+        orig_lines: Original lines of the text.
+        new_lines: New lines of the text.
+
+    Return:
+        A list of replacing information.
+    """
+    diff_result = list(difflib.Differ().compare(orig_lines, new_lines))
+    orig_index, ret = 0, []
+    for line in diff_result:
+        if line.startswith('  '):
+            orig_index += 1
+        elif line.startswith('+ '):
+            ret.append((orig_index, orig_index, [line[2 : ]]))
+        elif line.startswith('- '):
+            ret.append((orig_index, orig_index + 1, []))
+            orig_index += 1
+    return _squash_patch(ret)
+
+
+class _CursorTransformer(object):
+    """Transformer for format of the cursor position.
+
+    In vim, it use (row, col) to represent an cursor's position.
+    In UsersTextManager, it use numerical notation (byte distance between the
+    first byte in the text).
+
+    Attributes:
+        _sum_len: Sum of each row.
+    """
+    def __init__(self):
+        """Constructor."""
+        self._sum_len = [0]
+
+    def update_lines(self, lines):
+        """Update lines of text.
+
+        Args:
+            lines: Lines of text.
+        """
+        self._sum_len = [0]
+        for line in lines:
+            delta = len(line) + 1  # "+ 1" is for newline char
+            self._sum_len.append(self._sum_len[-1] + delta)
+
+    def rcs_to_nums(self, rcs):
+        """Transform row-col format's cursor position to numerical type.
+
+        Args:
+            lines: List of line text.
+            rcs: List of tuple of row-col format cursor postions
+
+        Return:
+            A list of numerical cursor positions.
+        """
+        ret = []
+        for rc in rcs:
+            base = self._sum_len[min(rc[0], len(self._sum_len) - 1)]
+            ret.append(min(base + rc[1], self._sum_len[-1]))
+        return ret
+
+
+    def nums_to_rcs(self, nums):
+        """Transform numerical format's cursor position to row-col format.
+
+        Args:
+            lines: List of line text.
+            nums: A list of numerical cursor positions.
+
+        Return:
+            List of tuple of row-col format cursor postions
+        """
+        ans, rmin = {}, 0
+        for num in sorted(nums):
+            row = bisect.bisect(self._sum_len, num, lo=rmin) - 1
+            col = (num - self._sum_len[row]) if row < len(self._sum_len) else 0
+            rmin = row + 1
+            ans[num] = (row, col)
+        return [ans[num] for num in nums]
+
 
 class RequestHandler(object):
     """Handles all kinds of request.
 
     Attributes:
         _users_text_manager: An instance of UsersTextManager.
+        _cursor_transformer: An instance of _CursorTransformer.
     """
     def __init__(self, users_text_manager):
         """Constructor.
@@ -32,6 +160,7 @@ class RequestHandler(object):
         """
         super(RequestHandler, self).__init__()
         self._users_text_manager = users_text_manager
+        self._cursor_transformer = _CursorTransformer()
 
     def handle(self, request):
         """Handles the request and returns the response.
@@ -74,41 +203,68 @@ class RequestHandler(object):
             identity: The identity of that user.
             request: The request from that user.
         """
-        if all(key in request for key in [JSON_TOKEN.INIT,
-                                          JSON_TOKEN.TEXT,
-                                          JSON_TOKEN.MODE,
-                                          JSON_TOKEN.CURSORS]):
+        if all(key in request for key in [JSON_TOKEN.INIT, JSON_TOKEN.DIFF,
+                                          JSON_TOKEN.MODE, JSON_TOKEN.CURSORS]):
             log.info('handle sync-request from %r\n' % identity)
             self._check_init(identity, request)
             self._check_authority(identity, request)
+            lines = apply_patch(
+                self._users_text_manager.get_user_text(identity).split('\n'),
+                request[JSON_TOKEN.DIFF])
+            self._cursor_transformer.update_lines(lines)
+            cursors = dict(zip(request[JSON_TOKEN.CURSORS].keys(),
+                               self._cursor_transformer.rcs_to_nums(
+                                   request[JSON_TOKEN.CURSORS].values())))
             new_user_info, new_text = self._users_text_manager.update_user_text(
                 identity,
-                UserInfo(mode=request[JSON_TOKEN.MODE],
-                         cursors=request[JSON_TOKEN.CURSORS]),
-                request[JSON_TOKEN.TEXT])
-            return self._pack_sync_response(identity, new_user_info, new_text)
+                UserInfo(mode=request[JSON_TOKEN.MODE], cursors=cursors),
+                '\n'.join(lines))
+            return self._pack_sync_response(
+                identity, new_user_info, new_text.split('\n'), lines)
 
-    def _pack_sync_response(self, identity, user_info, text):
+    def _pack_sync_response(self, identity, user_info, lines, old_lines):
         """Packs the response for the sync request by the result from manager.
 
         Args:
             identity: Identity of that user.
             user_info: Informations of that user.
-            text: New text.
+            lines: New lines of text.
+            old_lines: Old lines of text.
+
+        Return:
+            The response json object.
+        """
+        self._cursor_transformer.update_lines(lines)
+        return {
+            JSON_TOKEN.DIFF : gen_patch(old_lines, lines),
+            JSON_TOKEN.CURSORS : dict(zip(
+                user_info.cursors.keys(),
+                self._cursor_transformer.nums_to_rcs(
+                    user_info.cursors.values()))),
+            JSON_TOKEN.MODE : user_info.mode,
+            JSON_TOKEN.OTHERS : self._pack_sync_others_response(identity)
+        }
+
+    def _pack_sync_others_response(self, identity):
+        """Packs the response information for other users.
+
+        Args:
+            identity: Identity of that user.
 
         Return:
             The response json object.
         """
-        return {JSON_TOKEN.TEXT : text,
-                JSON_TOKEN.CURSORS : user_info.cursors,
-                JSON_TOKEN.MODE : user_info.mode,
-                JSON_TOKEN.OTHERS : [
-                    {JSON_TOKEN.NICKNAME : other.nick_name,
-                     JSON_TOKEN.MODE : other.mode,
-                     JSON_TOKEN.CURSORS: other.cursors}
-                    for iden, other in self._users_text_manager.get_users_info(
-                        without=[identity], must_online=True).items()
-                ]}
+        return [
+            {
+                JSON_TOKEN.NICKNAME : other.nick_name,
+                JSON_TOKEN.MODE : other.mode,
+                JSON_TOKEN.CURSORS: dict(zip(
+                    other.cursors.keys(),
+                    self._cursor_transformer.nums_to_rcs(
+                        other.cursors.values())))
+            } for iden, other in self._users_text_manager.get_users_info(
+                without=[identity], must_online=True).items()
+        ]
 
     def _check_init(self, identity, request):
         """Checks whether that user should be initialize or not.
@@ -122,9 +278,9 @@ class RequestHandler(object):
         if request[JSON_TOKEN.INIT]:
             log.info('Init the user %r\n' % identity)
             self._users_text_manager.reset_user(identity)
-            request[JSON_TOKEN.TEXT] = ''
+            request[JSON_TOKEN.DIFF] = []
             for mark in request.get(JSON_TOKEN.CURSORS, []):
-                request[JSON_TOKEN.CURSORS][mark] = 0
+                request[JSON_TOKEN.CURSORS][mark] = (0, 0)
 
     def _check_authority(self, identity, request):
         """Checks the authroity and updates the request.
@@ -138,5 +294,4 @@ class RequestHandler(object):
         """
         auth = self._users_text_manager.get_users_info()[identity].authority
         if auth < AUTHORITY.READWRITE:
-            old_text = self._users_text_manager.get_user_text(identity)
-            request[JSON_TOKEN.TEXT] = old_text
+            request[JSON_TOKEN.DIFF] = []
diff --git a/server/src/text_chain.py b/server/src/text_chain.py
index d60ea02..df2c9ba 100644
--- a/server/src/text_chain.py
+++ b/server/src/text_chain.py
@@ -53,8 +53,10 @@ class TextChain(object):
         for info in cursors_info:
             info.apply_commits([cm[1] for cm in self._commits[old_index + 1 :]])
         new_cursors = [cursor_info.position for cursor_info in cursors_info]
-        self._commits.append((new_id, commit))
+        self._commits += [(new_id, commit),
+                          (new_id + 1, _TextCommit(commit.text, commit.text))]
         self.delete(orig_id)
+        self.delete(self._commits[-3][0])
         self._save()
         return new_id, commit.text, new_cursors
 
@@ -190,7 +192,7 @@ class _TextCommit(object):
     @property
     def increased_length(self):
         """Gets the increased length of this commit."""
-        return sum([o.increased_length for o in self._opers])
+        return sum(o.increased_length for o in self._opers)
 
     def copy(self):
         """Returns a copy of myself.
@@ -218,17 +220,9 @@ class _TextCommit(object):
     def get_cursor_info(self, cursor_pos):
         """Gets the cursor information by gived cursor position.
 
-        If the cursor position is in a place that will be modified at this
-        commit, it will return _CursorInfo_OnNewCommit;  Otherwise it will
-        return _CursorInfo_OnOrigText.
-        Ex:
-            The original text with the only oper be "Chage [4, 9) to another
-            string":
-                0 1 2 3 4 5 6 7 8 91011121314
-                a b c d[e f g h i]j k l m n o
-               ^ ^ ^ ^ | | | | | | ^ ^ ^ ^ ^ ^
-               Then for the "^", they belone to _CursorInfo_OnOrigText;
-               Otherwise they belone to _CursorInfo_OnNewCommit.
+        If the cursor position is on character which is inserted at this commit,
+        it will return _CursorInfo_OnNewCommit;  Otherwise it will return
+        _CursorInfo_OnOrigText.
 
         Args:
             cursor_pos: Position of the cursor.
@@ -236,9 +230,12 @@ class _TextCommit(object):
         Return:
             A instance of _CursorInfo_OnNewCommit or _CursorInfo_OnOrigText.
         """
+        offset = 0
         for oper in self._opers:
-            if oper.begin <= cursor_pos <= oper.end:
-                return _CursorInfo_OnNewCommit(oper, cursor_pos - oper.begin)
+            delta = cursor_pos - (oper.begin + offset)
+            if delta <= len(oper.new_text):
+                return _CursorInfo_OnNewCommit(oper, delta)
+            offset += oper.increased_length
         return _CursorInfo_OnOrigText(cursor_pos)
 
     def _rebase_text(self, new_orig_text):
@@ -293,10 +290,12 @@ class _CursorInfo_OnNewCommit(object):
     def position(self):
         """Calculates and returns the final cursor position."""
         dt = self._delta
+        offset = 0
         for oper in self._opers:
-            if oper.begin + dt <= oper.end:
-                return oper.begin + dt
+            if dt <= len(oper.new_text):
+                return oper.begin + offset + dt
             dt -= len(oper.new_text)
+            offset += oper.increased_length
 
 
 class _CursorInfo_OnOrigText(object):
diff --git a/server/src/users_text_manager.py b/server/src/users_text_manager.py
index 93d9d94..cb86e9d 100644
--- a/server/src/users_text_manager.py
+++ b/server/src/users_text_manager.py
@@ -113,9 +113,9 @@ class UsersTextManager(object):
         with self._rlock:
             without = without if without is not None else []
             online_check = lambda x: (x != UNKNOWN if must_online else True)
-            return dict([pair for pair in self._users.items()
-                         if pair[0] not in without and \
-                             online_check(pair[1].mode)])
+            return dict(pair for pair in self._users.items()
+                        if pair[0] not in without and \
+                           online_check(pair[1].mode))
 
     def update_user_text(self, identity, new_user_info, new_text):
         """Updates a user's information with new information and text.
@@ -134,14 +134,14 @@ class UsersTextManager(object):
                 self._users[identity].last_commit_id, new_text, curs)
             self._users[identity].last_commit_id = new_commit_id
             self._users[identity].mode = new_user_info.mode
-            self._users[identity].cursors = _lists_to_dict(curmarks, new_curs)
+            self._users[identity].cursors = dict(zip(curmarks, new_curs))
             for iden, user in self._users.items():
                 if iden == identity:
                     continue
                 curmarks = user.cursors.keys()
                 curs = [user.cursors[mark] for mark in curmarks]
                 new_curs = self._text_chain.update_cursors(curs)
-                user.cursors = _lists_to_dict(curmarks, new_curs)
+                user.cursors = dict(zip(curmarks, new_curs))
             return (self._users[identity], new_text)
 
     def get_user_text(self, identity):
@@ -156,17 +156,3 @@ class UsersTextManager(object):
         with self._rlock:
             return self._text_chain.get_text(
                 self._users[identity].last_commit_id)
-
-
-def _lists_to_dict(list1, list2):
-    """Combines each element in two lists.
-
-    Args:
-        list1: The first list.
-        list2: The second list.
-
-    Return:
-        A list with each element be a tuple of two element in list1 and list2.
-    """
-    l1, l2 = list(list1), list(list2)
-    return {l1[index] : l2[index] for index in range(len(l1))}