[notmuch] Fwd: Re: nested tag trees (was: Mail in git)

diff --git a/02/2669c5a880b392bd3e49e795f3113880e1fd9a b/02/2669c5a880b392bd3e49e795f3113880e1fd9a
new file mode 100644 (file)
index 0000000..6ff4f95
--- /dev/null
+++ b/02/2669c5a880b392bd3e49e795f3113880e1fd9a
@@ -0,0 +1,111 @@
+Return-Path: <bgamari@gmail.com>\r
+X-Original-To: notmuch@notmuchmail.org\r
+Delivered-To: notmuch@notmuchmail.org\r
+Received: from localhost (localhost [127.0.0.1])\r
+       by olra.theworths.org (Postfix) with ESMTP id 0B375431FBC\r
+       for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:38:18 -0800 (PST)\r
+X-Virus-Scanned: Debian amavisd-new at olra.theworths.org\r
+X-Spam-Flag: NO\r
+X-Spam-Score: 0.001\r
+X-Spam-Level: \r
+X-Spam-Status: No, score=0.001 tagged_above=-999 required=5\r
+       tests=[BAYES_50=0.001] autolearn=ham\r
+Received: from olra.theworths.org ([127.0.0.1])\r
+       by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024)\r
+       with ESMTP id R+eSkGMl2PtE for <notmuch@notmuchmail.org>;\r
+       Wed, 17 Feb 2010 20:38:17 -0800 (PST)\r
+Received: from qw-out-1920.google.com (qw-out-1920.google.com [74.125.92.150])\r
+       by olra.theworths.org (Postfix) with ESMTP id 45BBE431FAE\r
+       for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:38:17 -0800 (PST)\r
+Received: by qw-out-1920.google.com with SMTP id 5so1085717qwc.32\r
+       for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:38:16 -0800 (PST)\r
+DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma;\r
+       h=domainkey-signature:received:received:content-type:subject:from:to\r
+       :date:message-id:user-agent:content-transfer-encoding;\r
+       bh=+z0xtkmvIupPmJMHvJ5LPprzD5ghU4fZNSQMu6naGAA=;\r
+       b=b8pABbBbhb1dIsZxNRumml4maJU/DnntQ4phbgqEC+X1myLrnZLfxmdR+qyu2n9wPQ\r
+       hNG45fGAgn4XoebceENWwk8M7Sqj9MRX2K0pDG/V4/VCEi5TS4tEQvumTh+CBIka7sy2\r
+       yamx7HtsOj7TT0fnH+c/ouVt9aBh+j84zw1ug=\r
+DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;\r
+       h=content-type:subject:from:to:date:message-id:user-agent\r
+       :content-transfer-encoding;\r
+       b=plinDTioCILE26rLDobAP6h9usmE1UX6MqULtoZcpqjS+gzjWAd5AaN52cHHotfyK1\r
+       ggBzv5/QCoikeESDW/g/K+qNz+nIGKLAGznTEYrNjaHTR3O9UpVXrMWA3L0HI1ia23Xs\r
+       MCff4EiFKxJ7DoZFM1nsWZesAEURqFSF2bygo=\r
+Received: by 10.224.140.144 with SMTP id i16mr2235066qau.149.1266467896674;\r
+       Wed, 17 Feb 2010 20:38:16 -0800 (PST)\r
+Received: from localhost (pool-96-236-125-203.spfdma.east.verizon.net\r
+       [96.236.125.203])\r
+       by mx.google.com with ESMTPS id 23sm6430113qyk.3.2010.02.17.20.38.14\r
+       (version=TLSv1/SSLv3 cipher=RC4-MD5);\r
+       Wed, 17 Feb 2010 20:38:15 -0800 (PST)\r
+Content-Type: text/plain; charset=UTF-8\r
+From: Ben Gamari <bgamari@gmail.com>\r
+To: notmuch <notmuch@notmuchmail.org>\r
+Date: Wed, 17 Feb 2010 23:38:13 -0500\r
+Message-Id: <1266467878-sup-1425@ben-laptop>\r
+User-Agent: Sup/git\r
+Content-Transfer-Encoding: 8bit\r
+Subject: [notmuch] Fwd: Re: nested tag trees (was:  Mail in git)\r
+X-BeenThere: notmuch@notmuchmail.org\r
+X-Mailman-Version: 2.1.13\r
+Precedence: list\r
+List-Id: "Use and development of the notmuch mail system."\r
+       <notmuch.notmuchmail.org>\r
+List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
+       <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
+List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
+List-Post: <mailto:notmuch@notmuchmail.org>\r
+List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
+List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
+       <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
+X-List-Received-Date: Thu, 18 Feb 2010 04:38:18 -0000\r
+\r
+--- Begin forwarded message from martin f krafft ---\r
+From: martin f krafft <madduck@madduck.net>\r
+To: Ben Gamari <bgamari@gmail.com>\r
+Date: Wed, 17 Feb 2010 22:46:13 -0500\r
+Subject: Re: nested tag trees (was: [notmuch] Mail in git)\r
+\r
+You ought to have sent to the list, and I want to send mine there\r
+too, so please give permission.\r
+\r
+also sprach Ben Gamari <bgamari@gmail.com> [2010.02.18.1620 +1300]:\r
+> This is a very good point. From what I've read about the database\r
+> format, I can't think of any way that reverse dependencies could be\r
+> easily found, unfortunately. If there really is no way to do this, then\r
+> we could have a problem. I'm not sure rewriting tens of megabytes\r
+> everytime you receive a mail message is acceptable.\r
+\r
+You would not need to do that, since the messages don't change, and\r
+thus their blobs remain the same.\r
+\r
+However, for every manipulation of a message, you would need to\r
+iterate *all* tag trees (O(n)) and update the ones referencing the\r
+message (also O(n)).\r
+\r
+The entire process will still be O(n) per message, and O(m×n) for\r
+all:\r
+\r
+  messages=[list of messages]\r
+  add_tags=[list of tags to add]\r
+  remove_tags=[list of tags to remove]\r
+  tagtrees=[all tag trees]\r
+  trees_to_update=[]\r
+\r
+  for t in remove_tags:\r
+    if intersection(t.tree.children, messages):\r
+      T = new_tree(t.name)\r
+      write_tree(T, t.tree.children - messages)\r
+      write_tree(t.tree, [])\r
+      t.tree = T\r
+\r
+  for t in add_tags:\r
+    t.tree = new_tree(t.name)\r
+    rewrite_tree(t.tree, messages)\r
+\r
+This can probably be further optimised, but still: it's not quite as\r
+nice as enumerating all parents of a message in O(1) time (which\r
+would still result in O(m×n)).\r
+\r
+--- End forwarded message ---\r