02/2669c5a880b392bd3e49e795f3113880e1fd9a

   1 Return-Path: <bgamari@gmail.com>\r
   2 X-Original-To: notmuch@notmuchmail.org\r
   3 Delivered-To: notmuch@notmuchmail.org\r
   4 Received: from localhost (localhost [127.0.0.1])\r
   5         by olra.theworths.org (Postfix) with ESMTP id 0B375431FBC\r
   6         for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:38:18 -0800 (PST)\r
   7 X-Virus-Scanned: Debian amavisd-new at olra.theworths.org\r
   8 X-Spam-Flag: NO\r
   9 X-Spam-Score: 0.001\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=0.001 tagged_above=-999 required=5\r
  12         tests=[BAYES_50=0.001] autolearn=ham\r
  13 Received: from olra.theworths.org ([127.0.0.1])\r
  14         by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024)\r
  15         with ESMTP id R+eSkGMl2PtE for <notmuch@notmuchmail.org>;\r
  16         Wed, 17 Feb 2010 20:38:17 -0800 (PST)\r
  17 Received: from qw-out-1920.google.com (qw-out-1920.google.com [74.125.92.150])\r
  18         by olra.theworths.org (Postfix) with ESMTP id 45BBE431FAE\r
  19         for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:38:17 -0800 (PST)\r
  20 Received: by qw-out-1920.google.com with SMTP id 5so1085717qwc.32\r
  21         for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:38:16 -0800 (PST)\r
  22 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma;\r
  23         h=domainkey-signature:received:received:content-type:subject:from:to\r
  24         :date:message-id:user-agent:content-transfer-encoding;\r
  25         bh=+z0xtkmvIupPmJMHvJ5LPprzD5ghU4fZNSQMu6naGAA=;\r
  26         b=b8pABbBbhb1dIsZxNRumml4maJU/DnntQ4phbgqEC+X1myLrnZLfxmdR+qyu2n9wPQ\r
  27         hNG45fGAgn4XoebceENWwk8M7Sqj9MRX2K0pDG/V4/VCEi5TS4tEQvumTh+CBIka7sy2\r
  28         yamx7HtsOj7TT0fnH+c/ouVt9aBh+j84zw1ug=\r
  29 DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;\r
  30         h=content-type:subject:from:to:date:message-id:user-agent\r
  31         :content-transfer-encoding;\r
  32         b=plinDTioCILE26rLDobAP6h9usmE1UX6MqULtoZcpqjS+gzjWAd5AaN52cHHotfyK1\r
  33         ggBzv5/QCoikeESDW/g/K+qNz+nIGKLAGznTEYrNjaHTR3O9UpVXrMWA3L0HI1ia23Xs\r
  34         MCff4EiFKxJ7DoZFM1nsWZesAEURqFSF2bygo=\r
  35 Received: by 10.224.140.144 with SMTP id i16mr2235066qau.149.1266467896674;\r
  36         Wed, 17 Feb 2010 20:38:16 -0800 (PST)\r
  37 Received: from localhost (pool-96-236-125-203.spfdma.east.verizon.net\r
  38         [96.236.125.203])\r
  39         by mx.google.com with ESMTPS id 23sm6430113qyk.3.2010.02.17.20.38.14\r
  40         (version=TLSv1/SSLv3 cipher=RC4-MD5);\r
  41         Wed, 17 Feb 2010 20:38:15 -0800 (PST)\r
  42 Content-Type: text/plain; charset=UTF-8\r
  43 From: Ben Gamari <bgamari@gmail.com>\r
  44 To: notmuch <notmuch@notmuchmail.org>\r
  45 Date: Wed, 17 Feb 2010 23:38:13 -0500\r
  46 Message-Id: <1266467878-sup-1425@ben-laptop>\r
  47 User-Agent: Sup/git\r
  48 Content-Transfer-Encoding: 8bit\r
  49 Subject: [notmuch] Fwd: Re: nested tag trees (was:  Mail in git)\r
  50 X-BeenThere: notmuch@notmuchmail.org\r
  51 X-Mailman-Version: 2.1.13\r
  52 Precedence: list\r
  53 List-Id: "Use and development of the notmuch mail system."\r
  54         <notmuch.notmuchmail.org>\r
  55 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  56         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  57 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  58 List-Post: <mailto:notmuch@notmuchmail.org>\r
  59 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  60 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  61         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  62 X-List-Received-Date: Thu, 18 Feb 2010 04:38:18 -0000\r
  63 \r
  64 --- Begin forwarded message from martin f krafft ---\r
  65 From: martin f krafft <madduck@madduck.net>\r
  66 To: Ben Gamari <bgamari@gmail.com>\r
  67 Date: Wed, 17 Feb 2010 22:46:13 -0500\r
  68 Subject: Re: nested tag trees (was: [notmuch] Mail in git)\r
  69 \r
  70 You ought to have sent to the list, and I want to send mine there\r
  71 too, so please give permission.\r
  72 \r
  73 also sprach Ben Gamari <bgamari@gmail.com> [2010.02.18.1620 +1300]:\r
  74 > This is a very good point. From what I've read about the database\r
  75 > format, I can't think of any way that reverse dependencies could be\r
  76 > easily found, unfortunately. If there really is no way to do this, then\r
  77 > we could have a problem. I'm not sure rewriting tens of megabytes\r
  78 > everytime you receive a mail message is acceptable.\r
  79 \r
  80 You would not need to do that, since the messages don't change, and\r
  81 thus their blobs remain the same.\r
  82 \r
  83 However, for every manipulation of a message, you would need to\r
  84 iterate *all* tag trees (O(n)) and update the ones referencing the\r
  85 message (also O(n)).\r
  86 \r
  87 The entire process will still be O(n) per message, and O(m×n) for\r
  88 all:\r
  89 \r
  90   messages=[list of messages]\r
  91   add_tags=[list of tags to add]\r
  92   remove_tags=[list of tags to remove]\r
  93   tagtrees=[all tag trees]\r
  94   trees_to_update=[]\r
  95 \r
  96   for t in remove_tags:\r
  97     if intersection(t.tree.children, messages):\r
  98       T = new_tree(t.name)\r
  99       write_tree(T, t.tree.children - messages)\r
 100       write_tree(t.tree, [])\r
 101       t.tree = T\r
 102 \r
 103   for t in add_tags:\r
 104     t.tree = new_tree(t.name)\r
 105     rewrite_tree(t.tree, messages)\r
 106 \r
 107 This can probably be further optimised, but still: it's not quite as\r
 108 nice as enumerating all parents of a message in O(1) time (which\r
 109 would still result in O(m×n)).\r
 110 \r
 111 --- End forwarded message ---\r