From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Joakim Jalap Newsgroups: gmane.emacs.devel Subject: Re: Overlays as an AA-tree Date: Thu, 22 Sep 2016 22:11:07 +0200 Message-ID: <878tujlmp0.fsf@fastmail.com> References: <87d1jylv43.fsf@fastmail.com> <87a8f0p69w.fsf@fastmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1474576059 5194 195.159.176.226 (22 Sep 2016 20:27:39 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 22 Sep 2016 20:27:39 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1.50 (gnu/linux) Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Sep 22 22:27:35 2016 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bnAah-0000P7-K4 for ged-emacs-devel@m.gmane.org; Thu, 22 Sep 2016 22:27:31 +0200 Original-Received: from localhost ([::1]:60716 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bnAaf-0005df-R8 for ged-emacs-devel@m.gmane.org; Thu, 22 Sep 2016 16:27:29 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:44557) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bnAL3-0000II-Of for emacs-devel@gnu.org; Thu, 22 Sep 2016 16:11:22 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bnAKy-0003gn-Hl for emacs-devel@gnu.org; Thu, 22 Sep 2016 16:11:20 -0400 Original-Received: from out2-smtp.messagingengine.com ([66.111.4.26]:33199) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bnAKw-0003WK-3f for emacs-devel@gnu.org; Thu, 22 Sep 2016 16:11:16 -0400 Original-Received: from compute6.internal (compute6.nyi.internal [10.202.2.46]) by mailout.nyi.internal (Postfix) with ESMTP id 5CBC820B48; Thu, 22 Sep 2016 16:11:05 -0400 (EDT) Original-Received: from frontend2 ([10.202.2.161]) by compute6.internal (MEProxy); Thu, 22 Sep 2016 16:11:05 -0400 DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=fastmail.com; h=cc :content-type:date:from:in-reply-to:message-id:mime-version :references:subject:to:x-sasl-enc:x-sasl-enc; s=mesmtp; bh=wkrn7 Xx9KuQwCLWZ1RXqFqp2ibM=; b=dTzr8D8Pd5MribGBCDqwm/Gf3i7+6YlE0jfhM EoPcXG+7fvK77F2A+W6LN92XrbVbdpZ/HpfwQ2bJ+OYI0/CaLrjL9mXRnj4RHKLV TXg0JYeJvUQxLfc/kvfStqmlzQ5+8LYdUwM9wXhrl4f54jqMp/R3ouffG7u854s8 0yczxU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-sasl-enc :x-sasl-enc; s=smtpout; bh=wkrn7Xx9KuQwCLWZ1RXqFqp2ibM=; b=t5b3V DLGOKhi4A2RMWtsiFFYR7GC7uCgN/ukNm2gDRYt2Lmp+AbsGtEH+W5ig8Wzo4rOl KX/UjESIDOTQCLr4asLw2LV4Y8puJ+Yk+i571e3ESxXbOUgq3TvbxnVX5cx2JfeV SuHOl8vxnnW2Rm+3g/0/HLK7rS2VRMnDURTU3I= X-Sasl-enc: nId/V8d2wCl5XEP0Of+DHHU4U0W9a1IBoTYnR+XV1hKt 1474575064 Original-Received: from thinkpad (unknown [5.150.202.248]) by mail.messagingengine.com (Postfix) with ESMTPA id 5EB7FCCE9E; Thu, 22 Sep 2016 16:11:04 -0400 (EDT) In-Reply-To: (Stefan Monnier's message of "Thu, 22 Sep 2016 08:17:40 -0400") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 66.111.4.26 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 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.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:207714 Archived-At: Stefan Monnier writes: >>> which makes me suspect your design might not be quite right. >> Well, I didn't think *too* hard about it. I didn't really think about >> what to do when the intervals of two overlays are the same. Does it even >> matter? > > Not much, no. Do note that in compare_overlays, we do need a total ordering > (this is used for sort_overlays). Your sorting and that of > compare_overlays can't be identical (compare_overlays has to obey the > `priority` property, whereas yours shouldn't pay attention to it), but > you can still use the same idea: i.e. when start and end are equal, just > use the overlays's memory addresses to decide which comes first. Do you mean when a->char_start == b->char_start && a->char_end == b->char_end? Does it even matter what char_end is? I have a feeling it's ok to just return true if a->char_start == b->char_end. >>> Some tricky parts: >>> - because of the insertion_type, two overlays may start with end1>> and finish with end1>end2 without any call to move-overlay. >> Hm, ok. I will have to look into this further. Actually, this sounds like it could be quite complicated... I'm not sure how to handle that in the tree. > I think a more important aspect is that insertion/deletion of text has > to update all char-positions of overlays after the point of > insertion/deletion. I.e. it's an O(n) operation. In the intervals tree > used for text-properties we avoid this by keeping track of distances > rather than positions. and then positions get (re)computed when needed. Hm, I don't really understand this. Do you mean how LENGTH(i) is computed from TOTAL_LENGTH(i->left) and TOTAL_LENGTH(i->right)? Hm, how could I do that in the AA-tree? Store the position in the root and then an offset from the parent in every child node? But doing it like I do it now (updating all the char-positions after the modification) shouldn't be slower than updating the positions of all markers, right? >>> I wouldn't worry about merging (better yet: merge from master right away >>> and then keep doing that on a regular basis, which should be easy since >>> I don't think we've touched (nor will touch) this code very much). >> I tried to do that yesterday. There were some conflicts in insdel.c >> (which I think I fixed) but now I can't commit, because 'git commit' >> complains about trailing whitespace in some regex test files. How do I >> get around this? > > Just remove the trailing whitespace. I just commited with --no-verify instead :)