ed/467cca9400b32d8c6538bb5f73e331c97f2235

   1 Return-Path: <amthrax@drake.mit.edu>\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 2A17F42D298\r
   6         for <notmuch@notmuchmail.org>; Sun, 16 Jan 2011 00:11:33 -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\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=0 tagged_above=-999 required=5\r
  12         tests=[RCVD_IN_DNSWL_NONE=-0.0001] autolearn=disabled\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 VIf9t-WhBXDl for <notmuch@notmuchmail.org>;\r
  16         Sun, 16 Jan 2011 00:11:30 -0800 (PST)\r
  17 Received: from dmz-mailsec-scanner-5.mit.edu (DMZ-MAILSEC-SCANNER-5.MIT.EDU\r
  18         [18.7.68.34])\r
  19         by olra.theworths.org (Postfix) with ESMTP id 35ACD42D291\r
  20         for <notmuch@notmuchmail.org>; Sun, 16 Jan 2011 00:11:23 -0800 (PST)\r
  21 X-AuditID: 12074422-b7c3eae000000a70-4e-4d32a82a8225\r
  22 Received: from mailhub-auth-1.mit.edu ( [18.9.21.35])\r
  23         by dmz-mailsec-scanner-5.mit.edu (Symantec Brightmail Gateway) with\r
  24         SMTP id 28.9A.02672.A28A23D4; Sun, 16 Jan 2011 03:11:22 -0500 (EST)\r
  25 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103])\r
  26         by mailhub-auth-1.mit.edu (8.13.8/8.9.2) with ESMTP id p0G8BMhJ004719; \r
  27         Sun, 16 Jan 2011 03:11:22 -0500\r
  28 Received: from drake.mit.edu (a074.catapulsion.net [70.36.81.74])\r
  29         (authenticated bits=0)\r
  30         (User authenticated as amdragon@ATHENA.MIT.EDU)\r
  31         by outgoing.mit.edu (8.13.6/8.12.4) with ESMTP id p0G8BKDh010520\r
  32         (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT);\r
  33         Sun, 16 Jan 2011 03:11:22 -0500 (EST)\r
  34 Received: from amthrax by drake.mit.edu with local (Exim 4.72)\r
  35         (envelope-from <amthrax@drake.mit.edu>)\r
  36         id 1PeNho-0002XU-IF; Sun, 16 Jan 2011 03:11:20 -0500\r
  37 From: Austin Clements <amdragon@MIT.EDU>\r
  38 To: notmuch@notmuchmail.org\r
  39 Subject: [PATCH 3/8] Parse wildcard queries.\r
  40 Date: Sun, 16 Jan 2011 03:10:53 -0500\r
  41 Message-Id: <1295165458-9573-4-git-send-email-amdragon@mit.edu>\r
  42 X-Mailer: git-send-email 1.7.2.3\r
  43 In-Reply-To: <1295165458-9573-1-git-send-email-amdragon@mit.edu>\r
  44 References: <1295165458-9573-1-git-send-email-amdragon@mit.edu>\r
  45 X-Brightmail-Tracker: AAAAAA==\r
  46 Cc: amdragon@mit.edu\r
  47 X-BeenThere: notmuch@notmuchmail.org\r
  48 X-Mailman-Version: 2.1.13\r
  49 Precedence: list\r
  50 List-Id: "Use and development of the notmuch mail system."\r
  51         <notmuch.notmuchmail.org>\r
  52 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  53         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  54 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  55 List-Post: <mailto:notmuch@notmuchmail.org>\r
  56 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  57 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  58         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  59 X-List-Received-Date: Sun, 16 Jan 2011 08:11:33 -0000\r
  60 \r
  61 This implements support in the lexer and generator for wildcard terms,\r
  62 expanding them into synonym queries the way Xapian does.  Since this\r
  63 expansion is performed by the generator, it's easy to take advantage\r
  64 of in query transforms.\r
  65 \r
  66 With this, * works anywhere in the query, so we'll no longer need\r
  67 special case code for '*' queries in query.cc.\r
  68 ---\r
  69  TODO                  |    3 --\r
  70  lib/notmuch-private.h |    6 +++-\r
  71  lib/qparser.cc        |   75 +++++++++++++++++++++++++++++++++++++++----------\r
  72  3 files changed, 65 insertions(+), 19 deletions(-)\r
  73 \r
  74 diff --git a/TODO b/TODO\r
  75 index 438f7aa..10c8c12 100644\r
  76 --- a/TODO\r
  77 +++ b/TODO\r
  78 @@ -228,9 +228,6 @@ for all messages with the word "to". If we don't provide the first\r
  79  behavior, perhaps we should exit on an error when a configured prefix\r
  80  is provided with no value?\r
  81  \r
  82 -Support "*" in all cases and not just as a special case. That is, "* "\r
  83 -should also work, as well as "* and tag:inbox".\r
  84 -\r
  85  Implement a syntax for requesting set-theoertic operations on results\r
  86  of multiple searches. For example, I would like to do:\r
  87  \r
  88 diff --git a/lib/notmuch-private.h b/lib/notmuch-private.h\r
  89 index a42afd6..eb346ea 100644\r
  90 --- a/lib/notmuch-private.h\r
  91 +++ b/lib/notmuch-private.h\r
  92 @@ -522,7 +522,8 @@ enum _notmuch_token_type {\r
  93       * of TOK_TERMS, with the left child being a TOK_TERMS and the\r
  94       * right being another TOK_ADJ/TOK_NEAR.  The final right must be\r
  95       * NULL.  Both tokens can also carry distances; the highest\r
  96 -     * distance in the chain will be used. */\r
  97 +     * distance in the chain will be used.  The operand terms may not\r
  98 +     * be prefixed or wildcards. */\r
  99      TOK_ADJ, TOK_NEAR,\r
 100      /* Unary operators.  These have only a left child.  Xapian::Query\r
 101       * has no pure NOT operator, so the generator treats NOT as the\r
 102 @@ -572,6 +573,9 @@ typedef struct _notmuch_token {\r
 103       * generating database terms.  This must be filled in a\r
 104       * transformation pass. */\r
 105      const char *prefix;\r
 106 +    /* For TOK_TERMS and TOK_LIT, indicates that this token should\r
 107 +     * match any terms prefixed with text. */\r
 108 +    notmuch_bool_t wildcard;\r
 109  \r
 110      /* Link in the lexer token list. */\r
 111      struct _notmuch_token *next;\r
 112 diff --git a/lib/qparser.cc b/lib/qparser.cc\r
 113 index 5a6d39b..bd0296a 100644\r
 114 --- a/lib/qparser.cc\r
 115 +++ b/lib/qparser.cc\r
 116 @@ -33,7 +33,8 @@\r
 117   * 3) We transform the parse tree, running a sequence of\r
 118   *    caller-provided transformation functions over the tree.\r
 119   * 4) We generate the Xapian::Query from the transformed IR.  This\r
 120 - *    step also splits phrase tokens into multiple query terms.\r
 121 + *    step also splits phrase tokens into multiple query terms and\r
 122 + *    expands wildcard terms.\r
 123   *\r
 124   * To use the query parser, call _notmuch_qparser_parse to perform\r
 125   * steps 1 and 2, _notmuch_qparser_transform to perform step 3, and\r
 126 @@ -42,10 +43,7 @@\r
 127   * Still missing from this implementation:\r
 128   * * Stemming - The stemming should probably be marked on TOK_TERMS\r
 129   *   tokens.  Ideally, we can just pass this to the term generator.\r
 130 - * * Wildcard queries - This should be available in the IR so it's\r
 131 - *   easy to generate wildcard queries in a transformer.\r
 132   * * Value ranges in the IR\r
 133 - * * Queries "" and "*"\r
 134   */\r
 135  \r
 136  /* XXX notmuch currently registers "tag" as an exclusive boolean\r
 137 @@ -55,7 +53,7 @@\r
 138  #include "notmuch-private.h"\r
 139  #include "database-private.h"\r
 140  \r
 141 -#include <glib.h>              /* GHashTable */\r
 142 +#include <glib.h>              /* GHashTable, GPtrArray */\r
 143  \r
 144  struct _notmuch_qparser {\r
 145      notmuch_database_t *notmuch;\r
 146 @@ -107,7 +105,7 @@ static const char *token_types[] = {\r
 147  \r
 148  /* The distinguished end token.  This simplifies the parser since it\r
 149   * never has to worry about dereferencing next. */\r
 150 -static _notmuch_token_t tok_end = {TOK_END, NULL, -1, FALSE, NULL,\r
 151 +static _notmuch_token_t tok_end = {TOK_END, NULL, -1, FALSE, NULL, FALSE,\r
 152                                    &tok_end, NULL, NULL};\r
 153  \r
 154  _notmuch_token_t *\r
 155 @@ -142,9 +140,11 @@ _notmuch_token_show (const void *ctx, _notmuch_token_t *tok)\r
 156         return talloc_asprintf (ctx, "<bad type %d>", tok->type);\r
 157  \r
 158      if (tok->type == TOK_TERMS)\r
 159 -       return talloc_asprintf (ctx, "\"%s\"", tok->text);\r
 160 +       return talloc_asprintf (ctx, "\"%s\"%s", tok->text,\r
 161 +                               tok->wildcard ? "*" : "");\r
 162      else if (tok->type == TOK_LIT)\r
 163 -       return talloc_asprintf (ctx, "'%s'", tok->text);\r
 164 +       return talloc_asprintf (ctx, "'%s'%s", tok->text,\r
 165 +                               tok->wildcard ? "*" : "");\r
 166      else if (tok->type == TOK_ERROR)\r
 167         return talloc_asprintf (ctx, "ERROR/\"%s\"", tok->text);\r
 168  \r
 169 @@ -348,7 +348,7 @@ lex (const void *ctx, _notmuch_qparser_t *qparser, const char *query)\r
 170      struct _notmuch_lex_state *s = &state;\r
 171      struct _notmuch_token *tok;\r
 172      char *term;\r
 173 -    int prefixFlags, literal;\r
 174 +    int prefixFlags, literal, wildcard, n;\r
 175  \r
 176      while (it != end) {\r
 177         unsigned ch;\r
 178 @@ -433,7 +433,15 @@ lex (const void *ctx, _notmuch_qparser_t *qparser, const char *query)\r
 179             continue;\r
 180  \r
 181         /* Must be a term */\r
 182 -       lex_emit (s, TOK_TERMS, term);\r
 183 +       wildcard = 0;\r
 184 +       n = strlen(term);\r
 185 +       if (n && term[n-1] == '*') {\r
 186 +           /* Wildcard */\r
 187 +           wildcard = 1;\r
 188 +           term[n-1] = 0;\r
 189 +       }\r
 190 +       tok = lex_emit (s, TOK_TERMS, term);\r
 191 +       tok->wildcard = wildcard;\r
 192      }\r
 193  \r
 194      return s->head;\r
 195 @@ -713,8 +721,39 @@ generate_term (struct _notmuch_generate_state *s, const char *term,\r
 196  }\r
 197  \r
 198  static Xapian::Query\r
 199 +generate_wildcard (struct _notmuch_generate_state *s, const char *term)\r
 200 +{\r
 201 +    GPtrArray *subarr;\r
 202 +    Xapian::Query query, **qs;\r
 203 +    Xapian::Database *db = s->qparser->notmuch->xapian_db;\r
 204 +    Xapian::TermIterator i = db->allterms_begin (term),\r
 205 +       end = db->allterms_end (term);\r
 206 +\r
 207 +    subarr = g_ptr_array_new ();\r
 208 +    for (; i != end; i++)\r
 209 +       g_ptr_array_add (subarr, new Xapian::Query (*i, 1, s->termpos));\r
 210 +    /* If the term didn't expand, then return a query over the\r
 211 +     * unexpanded term, which is guaranteed not to match anything.\r
 212 +     * We can't simply return an empty query because Xapian treats\r
 213 +     * those specially. */\r
 214 +    if (!subarr->len) {\r
 215 +       g_ptr_array_free (subarr, TRUE);\r
 216 +       return Xapian::Query (term);\r
 217 +    }\r
 218 +\r
 219 +    s->termpos++;\r
 220 +    qs = (Xapian::Query**)subarr->pdata;\r
 221 +    query = Xapian::Query (Xapian::Query::OP_SYNONYM, qs, qs + subarr->len);\r
 222 +    for (unsigned int i = 0; i < subarr->len; ++i)\r
 223 +       delete qs[i];\r
 224 +    g_ptr_array_free (subarr, TRUE);\r
 225 +    return query;\r
 226 +}\r
 227 +\r
 228 +static Xapian::Query\r
 229  generate_terms (struct _notmuch_generate_state *s, const char *text,\r
 230 -               const char *prefix, int distance, Xapian::Query::op op)\r
 231 +               const char *prefix, notmuch_bool_t wildcard, int distance,\r
 232 +               Xapian::Query::op op)\r
 233  {\r
 234      Xapian::TermGenerator tg;\r
 235      Xapian::Document doc;\r
 236 @@ -740,6 +779,8 @@ generate_terms (struct _notmuch_generate_state *s, const char *text,\r
 237      }\r
 238      if (nterms == 0)\r
 239         return Xapian::Query ();\r
 240 +    if (nterms == 1 && wildcard)\r
 241 +       return generate_wildcard (s, text);\r
 242  \r
 243      /* Extract terms */\r
 244      qs = new Xapian::Query[nterms];\r
 245 @@ -762,6 +803,7 @@ generate (struct _notmuch_generate_state *s, _notmuch_token_t *root)\r
 246      using Xapian::Query;\r
 247      Query l, r;\r
 248      Query::op op;\r
 249 +    char *term;\r
 250  \r
 251      if (!root)\r
 252         return Query ();\r
 253 @@ -842,7 +884,7 @@ generate (struct _notmuch_generate_state *s, _notmuch_token_t *root)\r
 254          * phrases, they will be split out and treated like any other\r
 255          * term in the operand list. */\r
 256         op = root->type == TOK_ADJ ? Query::OP_PHRASE : Query::OP_NEAR;\r
 257 -       l = generate_terms (s, terms, NULL, dist - 1, op);\r
 258 +       l = generate_terms (s, terms, NULL, FALSE, dist - 1, op);\r
 259         talloc_free (terms);\r
 260         return l;\r
 261      }\r
 262 @@ -851,11 +893,14 @@ generate (struct _notmuch_generate_state *s, _notmuch_token_t *root)\r
 263         return generate (s, root->left);\r
 264  \r
 265      case TOK_TERMS:\r
 266 -       return generate_terms (s, root->text, root->prefix, 0,\r
 267 -                              Query::OP_PHRASE);\r
 268 +       return generate_terms (s, root->text, root->prefix, root->wildcard,\r
 269 +                              0, Query::OP_PHRASE);\r
 270  \r
 271      case TOK_LIT:\r
 272 -       return Query (generate_term (s, root->text, root->prefix));\r
 273 +       term = generate_term (s, root->text, root->prefix);\r
 274 +       if (root->wildcard)\r
 275 +           return generate_wildcard (s, term);\r
 276 +       return Query (term);\r
 277  \r
 278      case TOK_ERROR:\r
 279         if (!s->error)\r
 280 -- \r
 281 1.7.2.3\r
 282 \r