7d/9a13f697e065d36fa18c937286f775f7b0e46d

   1 Return-Path: <madduck@lapse.rw.madduck.net>\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 A5C48431FBC\r
   6         for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:34:53 -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: -2.101\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-2.101 tagged_above=-999 required=5 tests=[AWL=0.498,\r
  12         BAYES_00=-2.599] 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 H4ovxZ6vXOQE for <notmuch@notmuchmail.org>;\r
  16         Wed, 17 Feb 2010 20:34:52 -0800 (PST)\r
  17 Received: from clegg.madduck.net (clegg.madduck.net [193.242.105.96])\r
  18         by olra.theworths.org (Postfix) with ESMTP id 74C19431FAE\r
  19         for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:34:52 -0800 (PST)\r
  20 Received: from lapse.rw.madduck.net (unknown\r
  21         [IPv6:2404:130:0:1000:20a:e4ff:fe30:4316])\r
  22         (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))\r
  23         (Client CN "lapse.rw.madduck.net",\r
  24         Issuer "CAcert Class 3 Root" (verified OK))\r
  25         by clegg.madduck.net (postfix) with ESMTPS id 798611D409C\r
  26         for <notmuch@notmuchmail.org>; Thu, 18 Feb 2010 05:34:48 +0100 (CET)\r
  27 Received: by lapse.rw.madduck.net (Postfix, from userid 1000)\r
  28         id 6F57324C; Thu, 18 Feb 2010 17:34:49 +1300 (NZDT)\r
  29 Date: Thu, 18 Feb 2010 17:34:49 +1300\r
  30 From: martin f krafft <madduck@madduck.net>\r
  31 To: notmuch discussion list <notmuch@notmuchmail.org>\r
  32 Message-ID: <20100218043449.GB4127@lapse.rw.madduck.net>\r
  33 Mail-Followup-To: notmuch discussion list <notmuch@notmuchmail.org>\r
  34 References: <20100217012101.GD8249@lapse.rw.madduck.net>\r
  35         <1266418124-sup-6308@ben-laptop>\r
  36         <3wd3a0z7jjv.fsf@mhdcelk-nx01.amd.com>\r
  37         <1266435265-sup-5024@ben-laptop>\r
  38         <20100217235211.GC2628@lapse.rw.madduck.net>\r
  39         <1266453115-sup-7880@ben-laptop>\r
  40         <20100218015847.GB3480@lapse.rw.madduck.net>\r
  41         <1266459453-sup-7234@ben-laptop>\r
  42         <20100218024802.GA795@lapse.rw.madduck.net>\r
  43         <1266463007-sup-8777@ben-laptop>\r
  44 MIME-Version: 1.0\r
  45 Content-Type: multipart/signed; micalg=pgp-ripemd160;\r
  46         protocol="application/pgp-signature"; boundary="uZ3hkaAS1mZxFaxD"\r
  47 Content-Disposition: inline\r
  48 In-Reply-To: <1266463007-sup-8777@ben-laptop>\r
  49 X-Motto: Keep the good times rollin'\r
  50 X-OS: Debian GNU/Linux squeeze/sid kernel 2.6.32-1-686 i686\r
  51 X-Spamtrap: madduck.bogus@madduck.net\r
  52 X-Subliminal-Message: debian/rules!\r
  53 User-Agent: Mutt/1.5.20 (2009-06-14)\r
  54 X-Virus-Scanned: clamav-milter 0.95.3 at clegg\r
  55 X-Virus-Status: Clean\r
  56 Subject: Re: [notmuch] nested tag trees (was:  Mail in git)\r
  57 X-BeenThere: notmuch@notmuchmail.org\r
  58 X-Mailman-Version: 2.1.13\r
  59 Precedence: list\r
  60 List-Id: "Use and development of the notmuch mail system."\r
  61         <notmuch.notmuchmail.org>\r
  62 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  63         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  64 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  65 List-Post: <mailto:notmuch@notmuchmail.org>\r
  66 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  67 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  68         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  69 X-List-Received-Date: Thu, 18 Feb 2010 04:34:53 -0000\r
  70 \r
  71 \r
  72 --uZ3hkaAS1mZxFaxD\r
  73 Content-Type: text/plain; charset=iso-8859-1\r
  74 Content-Disposition: inline\r
  75 Content-Transfer-Encoding: quoted-printable\r
  76 \r
  77 [Taking a private message back to the list with permission]\r
  78 \r
  79 also sprach Ben Gamari <bgamari@gmail.com> [2010.02.18.1620 +1300]:\r
  80 > This is a very good point. From what I've read about the database\r
  81 > format, I can't think of any way that reverse dependencies could be\r
  82 > easily found, unfortunately. If there really is no way to do this, then\r
  83 > we could have a problem. I'm not sure rewriting tens of megabytes\r
  84 > everytime you receive a mail message is acceptable.\r
  85 \r
  86 You would not need to do that, since the messages don't change, and\r
  87 thus their blobs remain the same.\r
  88 \r
  89 However, for every manipulation of a message, you would need to\r
  90 iterate *all* tag trees (O(n)) and update the ones referencing the\r
  91 message (also O(n)).\r
  92 \r
  93 The entire process will still be O(n) per message, and O(m=D7n) for\r
  94 all:\r
  95 \r
  96   messages=3D[list of messages]\r
  97   add_tags=3D[list of tags to add]\r
  98   remove_tags=3D[list of tags to remove]\r
  99   tagtrees=3D[all tag trees]\r
 100   trees_to_update=3D[]\r
 101 \r
 102   for t in remove_tags:\r
 103     if intersection(t.tree.children, messages):\r
 104       T =3D new_tree(t.name)\r
 105       write_tree(T, t.tree.children - messages)\r
 106       write_tree(t.tree, [])\r
 107       t.tree =3D T\r
 108 \r
 109   for t in add_tags:\r
 110     t.tree =3D new_tree(t.name)\r
 111     rewrite_tree(t.tree, messages)\r
 112 \r
 113 This can probably be further optimised, but still: it's not quite as\r
 114 nice as enumerating all parents of a message in O(1) time (which\r
 115 would still result in O(m=D7n)).\r
 116 \r
 117 --=20\r
 118 martin | http://madduck.net/ | http://two.sentenc.es/\r
 119 =20\r
 120 "... (ethik und =E4sthetik sind eins.)"\r
 121                                                        -- wittgenstein\r
 122 =20\r
 123 spamtraps: madduck.bogus@madduck.net\r
 124 \r
 125 --uZ3hkaAS1mZxFaxD\r
 126 Content-Type: application/pgp-signature; name="digital_signature_gpg.asc"\r
 127 Content-Description: Digital signature (see http://martin-krafft.net/gpg/)\r
 128 Content-Disposition: inline\r
 129 \r
 130 -----BEGIN PGP SIGNATURE-----\r
 131 Version: GnuPG v1.4.10 (GNU/Linux)\r
 132 \r
 133 iEYEAREDAAYFAkt8w2kACgkQIgvIgzMMSnVLbgCgwlpf6fA/o7KJsneecT3ACwNU\r
 134 0VIAoLOGCyP8AdClLybXpA2es+soXZSZ\r
 135 =KEWJ\r
 136 -----END PGP SIGNATURE-----\r
 137 \r
 138 --uZ3hkaAS1mZxFaxD--\r