From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Ergus Newsgroups: gmane.emacs.devel Subject: Re: Question collaborative editing. Date: Thu, 1 Oct 2020 01:11:59 +0200 Message-ID: <20200930231159.q6h6etboucwkjcfe@Ergus> References: <20200929215849.zg4wzytbrwx2b7ih@Ergus> <84B86B7C-81F0-42DF-894C-BF577E4B3D6E@mit.edu> <83a6x7js6y.fsf@gnu.org> <83eemji6e8.fsf@gnu.org> <83blhni3kr.fsf@gnu.org> <0B69D727-B2C1-44FC-8382-FDAB6C7CBDAD@mit.edu> <83a6x7i1d0.fsf@gnu.org> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="19700"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Qiantan Hong , fmfs@posteo.net, bugs@gnu.support, npostavs@gmail.com, emacs-devel@gnu.org, kfogel@red-bean.com, monnier@iro.umontreal.ca To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Thu Oct 01 01:13:21 2020 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1kNlHk-00051E-Jj for ged-emacs-devel@m.gmane-mx.org; Thu, 01 Oct 2020 01:13:20 +0200 Original-Received: from localhost ([::1]:52176 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kNlHj-0001Fk-Lz for ged-emacs-devel@m.gmane-mx.org; Wed, 30 Sep 2020 19:13:19 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:43390) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kNlGn-0000Ne-Eu for emacs-devel@gnu.org; Wed, 30 Sep 2020 19:12:21 -0400 Original-Received: from sonic305-3.consmr.mail.bf2.yahoo.com ([74.6.133.42]:33431) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1kNlGj-0008LI-F7 for emacs-devel@gnu.org; Wed, 30 Sep 2020 19:12:20 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aol.com; s=a2048; t=1601507535; bh=qvcTzar46ssfSdyZsRkeY8MKevkWyK1fYeM/8ta1Nk4=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From:Subject; b=cgrqApFeOqgTudIDYnr5attMaT+ddjxjEur5hj9C9AMnUyRL72xQopamYueqFzjHEx5zT43bWQ5FOh/fS9tL+TTmQ0Xr8FO+5RSjtzfZr/J+iukLDUyRr/dhLZhC1WgjOzOPooYkdHsdrYv7YkCHHy+q+CaLH0GLRUen1LgewLN43FFNmEVAh/vFOXnqGr2LlmS5Xr0lkUzACoqM0YiglCxqWueuETQ338hato5gd+fWj7B64uZGaxSb3wAFcUZpnCUe5veoMVt3dETiGci9WZfsM/sx6fk+OQPOvstiPXhTxZNMjG1AA0ldHD97HoQDEcyET4/t5F6dP2sveSNs8Q== X-YMail-OSG: r.D1ucAVM1lcdqPB7u2rg2FT3wx.cb.pVobryCQWBxIBqJEF9v_Z4OrPrRT3UHB Z3nTjCfda8YFdnk_fQgpG4duO3XnXLpPpoyVuQFPZNrEcqBxPWwFwQyOd3BucZE6BiOj4_HXRSwr ecCO0RdvZVsaozkXQBl2oNMp6lH2Uf8mF_GwKlKaitmeQOOQc74XKLh7FW7_oca3Hv_O8w5EdDAp D1XsqLdFTV6AVp7n3nUKjrj2C33pCV23k.RcWTqNaIBXZOlsRZXSFrexJhgjaSRtRQF7Zt94.Pz. vIGpf_lWYLzlTSbtE0uIEyvjMJ88PPDWr3Q9Tt44c8c2SdlkrKoql8Sc.LadBCa9Lu014E9WE4dv W9pHygQNE9gRMKF7fYEq1T1a6Xk6xx9_cTxdfsnT4a.mTssNi27DKY4kc7_UzoK25WXkBltG5acs ttUh2YtwBCv_JtMegUI5skuOhVHldFVNTylAxOsWfICAAWiFvn6NuCmcC0ME2AdyAzJgGuQR_OQU uEINmb2JMEEaVgaeXoRT7ahgEquiB7I1Q3Y2bkXGix_N3ylDCP_ZK9GZNHfMaloZyki1i4AHvdWw uc3z4wg9FJPCXcN3PaG_7_UkhXxVcWYr6oyxj18AL4Q9LojOtJpzTYInqyMBTX1H80XlSZ.CKwmF RZk3epv8EBAVBV1qmAVA.tjJhi8LuWiOrCXKjAzZ9mw0BwJ.99Zox6TkDmzHQQxwvlyb6M7XFHpH JWOAqo6dnQcuiKSZvAJjBlkOP3qKwBmMtR7Vbsp8aHUDDi9dwyaEbQADKISfuE0674_FX.vhmtVC ksW.oDkNmxI3HzHwuDAA7EDJukGtSt00gJS5Tzvps. Original-Received: from sonic.gate.mail.ne1.yahoo.com by sonic305.consmr.mail.bf2.yahoo.com with HTTP; Wed, 30 Sep 2020 23:12:15 +0000 Original-Received: by smtp421.mail.ir2.yahoo.com (VZM Hermes SMTP Server) with ESMTPA ID cdcb179b5c9e52d4fec9ca80177250de; Wed, 30 Sep 2020 23:12:10 +0000 (UTC) Content-Disposition: inline In-Reply-To: <83a6x7i1d0.fsf@gnu.org> X-Mailer: WebService/1.1.16718 mail.backend.jedi.jws.acl:role.jedi.acl.token.atz.jws.hermes.aol Apache-HttpAsyncClient/4.1.4 (Java/11.0.7) Received-SPF: pass client-ip=74.6.133.42; envelope-from=spacibba@aol.com; helo=sonic305-3.consmr.mail.bf2.yahoo.com X-detected-operating-system: by eggs.gnu.org: First seen = 2020/09/30 19:12:15 X-ACL-Warn: Detected OS = Linux 3.11 and newer [fuzzy] X-Spam_score_int: -24 X-Spam_score: -2.5 X-Spam_bar: -- X-Spam_report: (-2.5 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.373, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:256811 Archived-At: On Wed, Sep 30, 2020 at 09:08:27PM +0300, Eli Zaretskii wrote: >> From: Qiantan Hong >> CC: Ergus , Fermin , >> Jean Louis >> , Noam Postavsky , >> Emacs developers >> , >> Karl Fogel , >> Stefan Monnier >> >> Date: Wed, 30 Sep 2020 17:48:13 +0000 >> >> > I'm sorry, I probably miss too much background information here, >> > because I don't really understand what is the issue you are describing >> > here. E.g., why is user intent important, when all you need is to >> > keep buffer text synchronized between several sessions? >> >> That’s the baseline for collaborative editing, there’s apparently >> solution that satisfies this single property (convergence property) >> but are extremely bad — e.g. the effect of some user input takes >> no effect, or a trivial program displaying an empty buffer for >> every user. Actually if we only want this property there’s much >> simpler way than CRDT/OT, e.g. let the server (or one client) >> send the whole buffer periodically. >> >> One example of diff not preserving user intent is: >> suppose in the buffer there is >> “one two one” >> And users agree that this sentence should always end in “one”. >> Now user A deleted the first two words “one two “ >> user B inserted “three” between the first “one” and “two” >> However, the diff have no idea about users’ agreement >> and what exactly user does (unless we get it from modification >> hooks). For user A, the diff just see “one” after and assume >> that A delete the suffix “two one”. The CRDT then does it job >> correctly and gives final synchronization result “one three”. >> Clearly, user intent is violated. > >I understand all that, but (a) you can overcome that by techniques >different from CRDT, and (b) unless we mean very different things by >"user intent", the intent is not important here. What is important, >AFAIU, is to specify the changes in a way that will produce the >desired result even if the buffer in the other Emacs was meanwhile >modified. Hi Eli: I will probably describe the obvious, but it seems that there is a miss communication here. The CRDT algorithm works in a way that every single character in the buffer has a unique ID if you have "ab" then a could be zero and b could be 1... Inserting a char between them (acb) will make c be 0.5; adding another (acdb) will make d=0.75 (this is just a simplified example) So adding a letter only needs to contain the new number and the char to insert {0.5; c} {0.75; d}. And to insert "c" we only need to find which char in the buffer are x < 0.5 and x+1 > 0.5. If I understood the Qiantan idea; his approach is to add such ID as a text property within the emacs buffer. To modify the buffer it is only needed to search (go to) the property ID of text chars/words whatever in the emacs buffer and perform the action. So the error probability is smaller because the IDs ARE in the text itself. This will reduce undetected errors inserting in the wrong positions when translating form the CRDT ID to the real "global" buffer position to do an "insert". Which could happen in some corner cases... (lets say basically synchronization errors between local modifications (which modify local absolute positions) and processing remote ones using outdated information (translating to global indices)... Said that; the external library approach seemed to work with tandem https://github.com/jscheid/tandem-emacs I am not sire how well it did. My previous concerns about the internal storage and performance was because the linear search of text properties in a long linear buffer may be very expensive as described in the refereed paper; so using a two steps search improved performance as described there... There are also other optimizations like grouping operations or remove redundant ones that with the C approach could reduce the operation that arrive to emacs. Probably in our case the improvement may be to use a bisection search and position hints. Any way. I am pretty sure that the Qiantan lisp only implementation could work; but performance is something that needs to be tested (hopefully performance issues will be negligible compared to network latency). The C library implementation was my utopic ideal implementation in order to make it efficient, portable and reusable with other editors... But it will somehow require to start a completely independent project from scratch and would require much more time to implement (algorithm, network handling, json, synchronization between clients and with emacs)... And basically emacs provides all that. Maybe this time simple is not better, but more realistic.