{"action":"created","comment":{"url":"https://api.github.com/repos/google/xi-editor/pulls/comments/117123624","pull_request_review_id":38802605,"id":117123624,"diff_hunk":"@@ -170,41 +182,67 @@ impl Engine {\n             new_deletes = new_deletes.transform_expand(&new_inserts);\n         }\n \n-        let new_union_str = union_ins_delta.apply(&self.union_str);\n+        // rebase insertions on text and apply\n+        let cur_deletes_from_union = &self.revs.last().unwrap().deletes_from_union;\n+        let text_ins_delta = union_ins_delta.transform_shrink(cur_deletes_from_union);\n+        let text_with_inserts = text_ins_delta.apply(&self.text);\n+        let rebased_deletes_from_union = cur_deletes_from_union.transform_expand(&new_inserts);\n+\n         // is the new edit in an undo group that was already undone due to concurrency?\n         let undone = self.get_current_undo().map_or(false, |undos| undos.contains(&undo_group));\n-        let mut new_deletes_from_union = Cow::Borrowed(&self.revs.last().unwrap().deletes_from_union);\n-        if undone {\n-            if !new_inserts.is_empty() {\n-                new_deletes_from_union = Cow::Owned(new_deletes_from_union.transform_union(&new_inserts));\n-            }\n-        } else {\n-            if !new_inserts.is_empty() {\n-                new_deletes_from_union = Cow::Owned(new_deletes_from_union.transform_expand(&new_inserts));\n-            }\n-            if !new_deletes.is_empty() {\n-                new_deletes_from_union = Cow::Owned(new_deletes_from_union.union(&new_deletes));\n-            }\n-        }\n+        let new_deletes_from_union = {\n+            let to_delete = if undone { &new_inserts } else { &new_deletes };\n+            rebased_deletes_from_union.union(to_delete)\n+        };\n+\n+        // move deleted or undone-inserted things from text to tombstones\n+        let (new_text, new_tombstones) = Engine::shuffle(&text_with_inserts, &self.tombstones,\n+            &rebased_deletes_from_union, &new_deletes_from_union);\n+\n         (Revision {\n             rev_id: self.rev_id_counter,\n-            deletes_from_union: new_deletes_from_union.into_owned(),\n-            union_str_len: new_union_str.len(),\n+            deletes_from_union: new_deletes_from_union,\n+            union_str_len: union_ins_delta.new_document_len(),\n             edit: Edit {\n                 priority: new_priority,\n                 undo_group: undo_group,\n                 inserts: new_inserts,\n                 deletes: new_deletes,\n             }\n-        }, new_union_str)\n+        }, new_text, new_tombstones)\n+    }\n+\n+    /// Move sections from text to tombstones and out of tombstones based on a new and old set of deletions\n+    fn shuffle_tombstones(text: &Rope, tombstones: &Rope,\n+            old_deletes_from_union: &Subset, new_deletes_from_union: &Subset) -> Rope {\n+        // Taking the complement of deletes_from_union leads to an interleaving valid for swapped text and tombstones,\n+        // allowing us to use the same method to insert the text into the tombstones.\n+        let union_len = text.len() + tombstones.len();\n+        let inverse_tombstones_map = old_deletes_from_union.complement(union_len);\n+        let move_delta = Delta::synthesize(text, union_len,\n+            &inverse_tombstones_map, &new_deletes_from_union.complement(union_len));\n+        move_delta.apply(tombstones)\n+    }\n+\n+    /// Move sections from text to tombstones and vice versa based on a new and old set of deletions","path":"rust/rope/src/engine.rs","position":137,"original_position":137,"commit_id":"5749716bc1f60bc1091d901012578644d7660843","original_commit_id":"5749716bc1f60bc1091d901012578644d7660843","user":{"login":"raphlinus","id":242367,"avatar_url":"https://avatars0.githubusercontent.com/u/242367?v=3","gravatar_id":"","url":"https://api.github.com/users/raphlinus","html_url":"https://github.com/raphlinus","followers_url":"https://api.github.com/users/raphlinus/followers","following_url":"https://api.github.com/users/raphlinus/following{/other_user}","gists_url":"https://api.github.com/users/raphlinus/gists{/gist_id}","starred_url":"https://api.github.com/users/raphlinus/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/raphlinus/subscriptions","organizations_url":"https://api.github.com/users/raphlinus/orgs","repos_url":"https://api.github.com/users/raphlinus/repos","events_url":"https://api.github.com/users/raphlinus/events{/privacy}","received_events_url":"https://api.github.com/users/raphlinus/received_events","type":"User","site_admin":false},"body":"Again, explain the meaning of the two `Rope`s on return","created_at":"2017-05-17T22:19:00Z","updated_at":"2017-05-17T22:22:21Z","html_url":"https://github.com/google/xi-editor/pull/299#discussion_r117123624","pull_request_url":"https://api.github.com/repos/google/xi-editor/pulls/299","_links":{"self":{"href":"https://api.github.com/repos/google/xi-editor/pulls/comments/117123624"},"html":{"href":"https://github.com/google/xi-editor/pull/299#discussion_r117123624"},"pull_request":{"href":"https://api.github.com/repos/google/xi-editor/pulls/299"}}},"pull_request":{"url":"https://api.github.com/repos/google/xi-editor/pulls/299","id":120932005,"html_url":"https://github.com/google/xi-editor/pull/299","diff_url":"https://github.com/google/xi-editor/pull/299.diff","patch_url":"https://github.com/google/xi-editor/pull/299.patch","issue_url":"https://api.github.com/repos/google/xi-editor/issues/299","number":299,"state":"open","locked":false,"title":"Store separate tombstones and text instead of a union string","user":{"login":"trishume","id":887610,"avatar_url":"https://avatars2.githubusercontent.com/u/887610?v=3","gravatar_id":"","url":"https://api.github.com/users/trishume","html_url":"https://github.com/trishume","followers_url":"https://api.github.com/users/trishume/followers","following_url":"https://api.github.com/users/trishume/following{/other_user}","gists_url":"https://api.github.com/users/trishume/gists{/gist_id}","starred_url":"https://api.github.com/users/trishume/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/trishume/subscriptions","organizations_url":"https://api.github.com/users/trishume/orgs","repos_url":"https://api.github.com/users/trishume/repos","events_url":"https://api.github.com/users/trishume/events{/privacy}","received_events_url":"https://api.github.com/users/trishume/received_events","type":"User","site_admin":false},"body":"This PR refactors the representation of `Engine` to store the text and tombstones separately. At the moment this has no significant effect on behaviour or time complexity, other than making retrieving the head revision instant. It paves the way however for a tree/rope based representation of subsets to make many other operations much faster.\r\n\r\nThis PR does the refactoring using changes from #297.\r\n\r\nIt also adds some more tests that weren't added in #297 due to me being too lazy to extricate them with advanced Git.\r\n\r\nThis PR should not be merged before #297 and you should probably review that first if you are thinking of reading this. I've targeted this PR at the branch of #297 so that the diff on top of that is easier to look at.\r\n\r\n@raphlinus ","created_at":"2017-05-16T21:40:54Z","updated_at":"2017-05-17T22:22:21Z","closed_at":null,"merged_at":null,"merge_commit_sha":"6e759c11a423e04324a0e66d776143b6b2c6744d","assignee":null,"assignees":[],"requested_reviewers":[],"milestone":null,"commits_url":"https://api.github.com/repos/google/xi-editor/pulls/299/commits","review_comments_url":"https://api.github.com/repos/google/xi-editor/pulls/299/comments","review_comment_url":"https://api.github.com/repos/google/xi-editor/pulls/comments{/number}","comments_url":"https://api.github.com/repos/google/xi-editor/issues/299/comments","statuses_url":"https://api.github.com/repos/google/xi-editor/statuses/5749716bc1f60bc1091d901012578644d7660843","head":{"label":"google:separate-tombstones","ref":"separate-tombstones","sha":"5749716bc1f60bc1091d901012578644d7660843","user":{"login":"google","id":1342004,"avatar_url":"https://avatars2.githubusercontent.com/u/1342004?v=3","gravatar_id":"","url":"https://api.github.com/users/google","html_url":"https://github.com/google","followers_url":"https://api.github.com/users/google/followers","following_url":"https://api.github.com/users/google/following{/other_user}","gists_url":"https://api.github.com/users/google/gists{/gist_id}","starred_url":"https://api.github.com/users/google/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/google/subscriptions","organizations_url":"https://api.github.com/users/google/orgs","repos_url":"https://api.github.com/users/google/repos","events_url":"https://api.github.com/users/google/events{/privacy}","received_events_url":"https://api.github.com/users/google/received_events","type":"Organization","site_admin":false},"repo":{"id":57167764,"name":"xi-editor","full_name":"google/xi-editor","owner":{"login":"google","id":1342004,"avatar_url":"https://avatars2.githubusercontent.com/u/1342004?v=3","gravatar_id":"","url":"https://api.github.com/users/google","html_url":"https://github.com/google","followers_url":"https://api.github.com/users/google/followers","following_url":"https://api.github.com/users/google/following{/other_user}","gists_url":"https://api.github.com/users/google/gists{/gist_id}","starred_url":"https://api.github.com/users/google/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/google/subscriptions","organizations_url":"https://api.github.com/users/google/orgs","repos_url":"https://api.github.com/users/google/repos","events_url":"https://api.github.com/users/google/events{/privacy}","received_events_url":"https://api.github.com/users/google/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/google/xi-editor","description":"A modern editor with a backend written in Rust.","fork":false,"url":"https://api.github.com/repos/google/xi-editor","forks_url":"https://api.github.com/repos/google/xi-editor/forks","keys_url":"https://api.github.com/repos/google/xi-editor/keys{/key_id}","collaborators_url":"https://api.github.com/repos/google/xi-editor/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/google/xi-editor/teams","hooks_url":"https://api.github.com/repos/google/xi-editor/hooks","issue_events_url":"https://api.github.com/repos/google/xi-editor/issues/events{/number}","events_url":"https://api.github.com/repos/google/xi-editor/events","assignees_url":"https://api.github.com/repos/google/xi-editor/assignees{/user}","branches_url":"https://api.github.com/repos/google/xi-editor/branches{/branch}","tags_url":"https://api.github.com/repos/google/xi-editor/tags","blobs_url":"https://api.github.com/repos/google/xi-editor/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/google/xi-editor/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/google/xi-editor/git/refs{/sha}","trees_url":"https://api.github.com/repos/google/xi-editor/git/trees{/sha}","statuses_url":"https://api.github.com/repos/google/xi-editor/statuses/{sha}","languages_url":"https://api.github.com/repos/google/xi-editor/languages","stargazers_url":"https://api.github.com/repos/google/xi-editor/stargazers","contributors_url":"https://api.github.com/repos/google/xi-editor/contributors","subscribers_url":"https://api.github.com/repos/google/xi-editor/subscribers","subscription_url":"https://api.github.com/repos/google/xi-editor/subscription","commits_url":"https://api.github.com/repos/google/xi-editor/commits{/sha}","git_commits_url":"https://api.github.com/repos/google/xi-editor/git/commits{/sha}","comments_url":"https://api.github.com/repos/google/xi-editor/comments{/number}","issue_comment_url":"https://api.github.com/repos/google/xi-editor/issues/comments{/number}","contents_url":"https://api.github.com/repos/google/xi-editor/contents/{+path}","compare_url":"https://api.github.com/repos/google/xi-editor/compare/{base}...{head}","merges_url":"https://api.github.com/repos/google/xi-editor/merges","archive_url":"https://api.github.com/repos/google/xi-editor/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/google/xi-editor/downloads","issues_url":"https://api.github.com/repos/google/xi-editor/issues{/number}","pulls_url":"https://api.github.com/repos/google/xi-editor/pulls{/number}","milestones_url":"https://api.github.com/repos/google/xi-editor/milestones{/number}","notifications_url":"https://api.github.com/repos/google/xi-editor/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/google/xi-editor/labels{/name}","releases_url":"https://api.github.com/repos/google/xi-editor/releases{/id}","deployments_url":"https://api.github.com/repos/google/xi-editor/deployments","created_at":"2016-04-26T23:03:23Z","updated_at":"2017-05-17T21:59:29Z","pushed_at":"2017-05-17T22:03:19Z","git_url":"git://github.com/google/xi-editor.git","ssh_url":"git@github.com:google/xi-editor.git","clone_url":"https://github.com/google/xi-editor.git","svn_url":"https://github.com/google/xi-editor","homepage":"","size":1848,"stargazers_count":7866,"watchers_count":7866,"language":"Rust","has_issues":true,"has_projects":true,"has_downloads":false,"has_wiki":false,"has_pages":false,"forks_count":258,"mirror_url":null,"open_issues_count":81,"forks":258,"open_issues":81,"watchers":7866,"default_branch":"master"}},"base":{"label":"google:master","ref":"master","sha":"c027bed51b9a72952a05a4f19f41bbd77ee35d8c","user":{"login":"google","id":1342004,"avatar_url":"https://avatars2.githubusercontent.com/u/1342004?v=3","gravatar_id":"","url":"https://api.github.com/users/google","html_url":"https://github.com/google","followers_url":"https://api.github.com/users/google/followers","following_url":"https://api.github.com/users/google/following{/other_user}","gists_url":"https://api.github.com/users/google/gists{/gist_id}","starred_url":"https://api.github.com/users/google/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/google/subscriptions","organizations_url":"https://api.github.com/users/google/orgs","repos_url":"https://api.github.com/users/google/repos","events_url":"https://api.github.com/users/google/events{/privacy}","received_events_url":"https://api.github.com/users/google/received_events","type":"Organization","site_admin":false},"repo":{"id":57167764,"name":"xi-editor","full_name":"google/xi-editor","owner":{"login":"google","id":1342004,"avatar_url":"https://avatars2.githubusercontent.com/u/1342004?v=3","gravatar_id":"","url":"https://api.github.com/users/google","html_url":"https://github.com/google","followers_url":"https://api.github.com/users/google/followers","following_url":"https://api.github.com/users/google/following{/other_user}","gists_url":"https://api.github.com/users/google/gists{/gist_id}","starred_url":"https://api.github.com/users/google/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/google/subscriptions","organizations_url":"https://api.github.com/users/google/orgs","repos_url":"https://api.github.com/users/google/repos","events_url":"https://api.github.com/users/google/events{/privacy}","received_events_url":"https://api.github.com/users/google/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/google/xi-editor","description":"A modern editor with a backend written in Rust.","fork":false,"url":"https://api.github.com/repos/google/xi-editor","forks_url":"https://api.github.com/repos/google/xi-editor/forks","keys_url":"https://api.github.com/repos/google/xi-editor/keys{/key_id}","collaborators_url":"https://api.github.com/repos/google/xi-editor/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/google/xi-editor/teams","hooks_url":"https://api.github.com/repos/google/xi-editor/hooks","issue_events_url":"https://api.github.com/repos/google/xi-editor/issues/events{/number}","events_url":"https://api.github.com/repos/google/xi-editor/events","assignees_url":"https://api.github.com/repos/google/xi-editor/assignees{/user}","branches_url":"https://api.github.com/repos/google/xi-editor/branches{/branch}","tags_url":"https://api.github.com/repos/google/xi-editor/tags","blobs_url":"https://api.github.com/repos/google/xi-editor/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/google/xi-editor/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/google/xi-editor/git/refs{/sha}","trees_url":"https://api.github.com/repos/google/xi-editor/git/trees{/sha}","statuses_url":"https://api.github.com/repos/google/xi-editor/statuses/{sha}","languages_url":"https://api.github.com/repos/google/xi-editor/languages","stargazers_url":"https://api.github.com/repos/google/xi-editor/stargazers","contributors_url":"https://api.github.com/repos/google/xi-editor/contributors","subscribers_url":"https://api.github.com/repos/google/xi-editor/subscribers","subscription_url":"https://api.github.com/repos/google/xi-editor/subscription","commits_url":"https://api.github.com/repos/google/xi-editor/commits{/sha}","git_commits_url":"https://api.github.com/repos/google/xi-editor/git/commits{/sha}","comments_url":"https://api.github.com/repos/google/xi-editor/comments{/number}","issue_comment_url":"https://api.github.com/repos/google/xi-editor/issues/comments{/number}","contents_url":"https://api.github.com/repos/google/xi-editor/contents/{+path}","compare_url":"https://api.github.com/repos/google/xi-editor/compare/{base}...{head}","merges_url":"https://api.github.com/repos/google/xi-editor/merges","archive_url":"https://api.github.com/repos/google/xi-editor/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/google/xi-editor/downloads","issues_url":"https://api.github.com/repos/google/xi-editor/issues{/number}","pulls_url":"https://api.github.com/repos/google/xi-editor/pulls{/number}","milestones_url":"https://api.github.com/repos/google/xi-editor/milestones{/number}","notifications_url":"https://api.github.com/repos/google/xi-editor/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/google/xi-editor/labels{/name}","releases_url":"https://api.github.com/repos/google/xi-editor/releases{/id}","deployments_url":"https://api.github.com/repos/google/xi-editor/deployments","created_at":"2016-04-26T23:03:23Z","updated_at":"2017-05-17T21:59:29Z","pushed_at":"2017-05-17T22:03:19Z","git_url":"git://github.com/google/xi-editor.git","ssh_url":"git@github.com:google/xi-editor.git","clone_url":"https://github.com/google/xi-editor.git","svn_url":"https://github.com/google/xi-editor","homepage":"","size":1848,"stargazers_count":7866,"watchers_count":7866,"language":"Rust","has_issues":true,"has_projects":true,"has_downloads":false,"has_wiki":false,"has_pages":false,"forks_count":258,"mirror_url":null,"open_issues_count":81,"forks":258,"open_issues":81,"watchers":7866,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/google/xi-editor/pulls/299"},"html":{"href":"https://github.com/google/xi-editor/pull/299"},"issue":{"href":"https://api.github.com/repos/google/xi-editor/issues/299"},"comments":{"href":"https://api.github.com/repos/google/xi-editor/issues/299/comments"},"review_comments":{"href":"https://api.github.com/repos/google/xi-editor/pulls/299/comments"},"review_comment":{"href":"https://api.github.com/repos/google/xi-editor/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/google/xi-editor/pulls/299/commits"},"statuses":{"href":"https://api.github.com/repos/google/xi-editor/statuses/5749716bc1f60bc1091d901012578644d7660843"}}}}
{"actor":{"display_login":"raphlinus"}}