lib: Rearrange the exclude code in query.cc
[notmuch] / lib / query.cc
1 /* query.cc - Support for searching a notmuch database
2  *
3  * Copyright © 2009 Carl Worth
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program.  If not, see http://www.gnu.org/licenses/ .
17  *
18  * Author: Carl Worth <cworth@cworth.org>
19  */
20
21 #include "notmuch-private.h"
22 #include "database-private.h"
23
24 #include <glib.h> /* GHashTable, GPtrArray */
25
26 struct _notmuch_query {
27     notmuch_database_t *notmuch;
28     const char *query_string;
29     notmuch_sort_t sort;
30     notmuch_string_list_t *exclude_terms;
31 };
32
33 typedef struct _notmuch_mset_messages {
34     notmuch_messages_t base;
35     notmuch_database_t *notmuch;
36     Xapian::MSetIterator iterator;
37     Xapian::MSetIterator iterator_end;
38 } notmuch_mset_messages_t;
39
40 struct _notmuch_doc_id_set {
41     unsigned int *bitmap;
42     unsigned int bound;
43 };
44
45 #define DOCIDSET_WORD(bit) ((bit) / sizeof (unsigned int))
46 #define DOCIDSET_BIT(bit) ((bit) % sizeof (unsigned int))
47
48 struct visible _notmuch_threads {
49     notmuch_query_t *query;
50
51     /* The ordered list of doc ids matched by the query. */
52     GArray *doc_ids;
53     /* Our iterator's current position in doc_ids. */
54     unsigned int doc_id_pos;
55     /* The set of matched docid's that have not been assigned to a
56      * thread. Initially, this contains every docid in doc_ids. */
57     notmuch_doc_id_set_t match_set;
58 };
59
60 notmuch_query_t *
61 notmuch_query_create (notmuch_database_t *notmuch,
62                       const char *query_string)
63 {
64     notmuch_query_t *query;
65
66 #ifdef DEBUG_QUERY
67     fprintf (stderr, "Query string is:\n%s\n", query_string);
68 #endif
69
70     query = talloc (NULL, notmuch_query_t);
71     if (unlikely (query == NULL))
72         return NULL;
73
74     query->notmuch = notmuch;
75
76     query->query_string = talloc_strdup (query, query_string);
77
78     query->sort = NOTMUCH_SORT_NEWEST_FIRST;
79
80     query->exclude_terms = _notmuch_string_list_create (query);
81
82     return query;
83 }
84
85 const char *
86 notmuch_query_get_query_string (notmuch_query_t *query)
87 {
88     return query->query_string;
89 }
90
91 void
92 notmuch_query_set_sort (notmuch_query_t *query, notmuch_sort_t sort)
93 {
94     query->sort = sort;
95 }
96
97 notmuch_sort_t
98 notmuch_query_get_sort (notmuch_query_t *query)
99 {
100     return query->sort;
101 }
102
103 void
104 notmuch_query_add_tag_exclude (notmuch_query_t *query, const char *tag)
105 {
106     char *term = talloc_asprintf (query, "%s%s", _find_prefix ("tag"), tag);
107     _notmuch_string_list_append (query->exclude_terms, term);
108 }
109
110 /* We end up having to call the destructors explicitly because we had
111  * to use "placement new" in order to initialize C++ objects within a
112  * block that we allocated with talloc. So C++ is making talloc
113  * slightly less simple to use, (we wouldn't need
114  * talloc_set_destructor at all otherwise).
115  */
116 static int
117 _notmuch_messages_destructor (notmuch_mset_messages_t *messages)
118 {
119     messages->iterator.~MSetIterator ();
120     messages->iterator_end.~MSetIterator ();
121
122     return 0;
123 }
124
125 /* Return a query that matches messages with the excluded tags
126  * registered with query.  Any tags that explicitly appear in xquery
127  * will not be excluded. The caller of this function has to combine
128  * the returned query appropriately.*/
129 static Xapian::Query
130 _notmuch_exclude_tags (notmuch_query_t *query, Xapian::Query xquery)
131 {
132     Xapian::Query exclude_query = Xapian::Query::MatchNothing;
133
134     for (notmuch_string_node_t *term = query->exclude_terms->head; term;
135          term = term->next) {
136         Xapian::TermIterator it = xquery.get_terms_begin ();
137         Xapian::TermIterator end = xquery.get_terms_end ();
138         for (; it != end; it++) {
139             if ((*it).compare (term->string) == 0)
140                 break;
141         }
142         if (it == end)
143             exclude_query = Xapian::Query (Xapian::Query::OP_OR,
144                                     exclude_query, Xapian::Query (term->string));
145     }
146     return exclude_query;
147 }
148
149 notmuch_messages_t *
150 notmuch_query_search_messages (notmuch_query_t *query)
151 {
152     notmuch_database_t *notmuch = query->notmuch;
153     const char *query_string = query->query_string;
154     notmuch_mset_messages_t *messages;
155
156     messages = talloc (query, notmuch_mset_messages_t);
157     if (unlikely (messages == NULL))
158         return NULL;
159
160     try {
161
162         messages->base.is_of_list_type = FALSE;
163         messages->base.iterator = NULL;
164         messages->notmuch = notmuch;
165         new (&messages->iterator) Xapian::MSetIterator ();
166         new (&messages->iterator_end) Xapian::MSetIterator ();
167
168         talloc_set_destructor (messages, _notmuch_messages_destructor);
169
170         Xapian::Enquire enquire (*notmuch->xapian_db);
171         Xapian::Query mail_query (talloc_asprintf (query, "%s%s",
172                                                    _find_prefix ("type"),
173                                                    "mail"));
174         Xapian::Query string_query, final_query, exclude_query;
175         Xapian::MSet mset;
176         unsigned int flags = (Xapian::QueryParser::FLAG_BOOLEAN |
177                               Xapian::QueryParser::FLAG_PHRASE |
178                               Xapian::QueryParser::FLAG_LOVEHATE |
179                               Xapian::QueryParser::FLAG_BOOLEAN_ANY_CASE |
180                               Xapian::QueryParser::FLAG_WILDCARD |
181                               Xapian::QueryParser::FLAG_PURE_NOT);
182
183         if (strcmp (query_string, "") == 0 ||
184             strcmp (query_string, "*") == 0)
185         {
186             final_query = mail_query;
187         } else {
188             string_query = notmuch->query_parser->
189                 parse_query (query_string, flags);
190             final_query = Xapian::Query (Xapian::Query::OP_AND,
191                                          mail_query, string_query);
192         }
193
194         exclude_query = _notmuch_exclude_tags (query, final_query);
195
196         final_query = Xapian::Query (Xapian::Query::OP_AND_NOT,
197                                          final_query, exclude_query);
198
199         enquire.set_weighting_scheme (Xapian::BoolWeight());
200
201         switch (query->sort) {
202         case NOTMUCH_SORT_OLDEST_FIRST:
203             enquire.set_sort_by_value (NOTMUCH_VALUE_TIMESTAMP, FALSE);
204             break;
205         case NOTMUCH_SORT_NEWEST_FIRST:
206             enquire.set_sort_by_value (NOTMUCH_VALUE_TIMESTAMP, TRUE);
207             break;
208         case NOTMUCH_SORT_MESSAGE_ID:
209             enquire.set_sort_by_value (NOTMUCH_VALUE_MESSAGE_ID, FALSE);
210             break;
211         case NOTMUCH_SORT_UNSORTED:
212             break;
213         }
214
215 #if DEBUG_QUERY
216         fprintf (stderr, "Final query is:\n%s\n", final_query.get_description().c_str());
217 #endif
218
219         enquire.set_query (final_query);
220
221         mset = enquire.get_mset (0, notmuch->xapian_db->get_doccount ());
222
223         messages->iterator = mset.begin ();
224         messages->iterator_end = mset.end ();
225
226         return &messages->base;
227
228     } catch (const Xapian::Error &error) {
229         fprintf (stderr, "A Xapian exception occurred performing query: %s\n",
230                  error.get_msg().c_str());
231         fprintf (stderr, "Query string was: %s\n", query->query_string);
232         notmuch->exception_reported = TRUE;
233         talloc_free (messages);
234         return NULL;
235     }
236 }
237
238 notmuch_bool_t
239 _notmuch_mset_messages_valid (notmuch_messages_t *messages)
240 {
241     notmuch_mset_messages_t *mset_messages;
242
243     mset_messages = (notmuch_mset_messages_t *) messages;
244
245     return (mset_messages->iterator != mset_messages->iterator_end);
246 }
247
248 static Xapian::docid
249 _notmuch_mset_messages_get_doc_id (notmuch_messages_t *messages)
250 {
251     notmuch_mset_messages_t *mset_messages;
252
253     mset_messages = (notmuch_mset_messages_t *) messages;
254
255     if (! _notmuch_mset_messages_valid (&mset_messages->base))
256         return 0;
257
258     return *mset_messages->iterator;
259 }
260
261 notmuch_message_t *
262 _notmuch_mset_messages_get (notmuch_messages_t *messages)
263 {
264     notmuch_message_t *message;
265     Xapian::docid doc_id;
266     notmuch_private_status_t status;
267     notmuch_mset_messages_t *mset_messages;
268
269     mset_messages = (notmuch_mset_messages_t *) messages;
270
271     if (! _notmuch_mset_messages_valid (&mset_messages->base))
272         return NULL;
273
274     doc_id = *mset_messages->iterator;
275
276     message = _notmuch_message_create (mset_messages,
277                                        mset_messages->notmuch, doc_id,
278                                        &status);
279
280     if (message == NULL &&
281        status == NOTMUCH_PRIVATE_STATUS_NO_DOCUMENT_FOUND)
282     {
283         INTERNAL_ERROR ("a messages iterator contains a non-existent document ID.\n");
284     }
285
286     return message;
287 }
288
289 void
290 _notmuch_mset_messages_move_to_next (notmuch_messages_t *messages)
291 {
292     notmuch_mset_messages_t *mset_messages;
293
294     mset_messages = (notmuch_mset_messages_t *) messages;
295
296     mset_messages->iterator++;
297 }
298
299 static notmuch_bool_t
300 _notmuch_doc_id_set_init (void *ctx,
301                           notmuch_doc_id_set_t *doc_ids,
302                           GArray *arr)
303 {
304     unsigned int max = 0;
305     unsigned int *bitmap;
306
307     for (unsigned int i = 0; i < arr->len; i++)
308         max = MAX(max, g_array_index (arr, unsigned int, i));
309     bitmap = talloc_zero_array (ctx, unsigned int, 1 + max / sizeof (*bitmap));
310
311     if (bitmap == NULL)
312         return FALSE;
313
314     doc_ids->bitmap = bitmap;
315     doc_ids->bound = max + 1;
316
317     for (unsigned int i = 0; i < arr->len; i++) {
318         unsigned int doc_id = g_array_index (arr, unsigned int, i);
319         bitmap[DOCIDSET_WORD(doc_id)] |= 1 << DOCIDSET_BIT(doc_id);
320     }
321
322     return TRUE;
323 }
324
325 notmuch_bool_t
326 _notmuch_doc_id_set_contains (notmuch_doc_id_set_t *doc_ids,
327                               unsigned int doc_id)
328 {
329     if (doc_id >= doc_ids->bound)
330         return FALSE;
331     return doc_ids->bitmap[DOCIDSET_WORD(doc_id)] & (1 << DOCIDSET_BIT(doc_id));
332 }
333
334 void
335 _notmuch_doc_id_set_remove (notmuch_doc_id_set_t *doc_ids,
336                             unsigned int doc_id)
337 {
338     if (doc_id < doc_ids->bound)
339         doc_ids->bitmap[DOCIDSET_WORD(doc_id)] &= ~(1 << DOCIDSET_BIT(doc_id));
340 }
341
342 /* Glib objects force use to use a talloc destructor as well, (but not
343  * nearly as ugly as the for messages due to C++ objects). At
344  * this point, I'd really like to have some talloc-friendly
345  * equivalents for the few pieces of glib that I'm using. */
346 static int
347 _notmuch_threads_destructor (notmuch_threads_t *threads)
348 {
349     if (threads->doc_ids)
350         g_array_unref (threads->doc_ids);
351
352     return 0;
353 }
354
355 notmuch_threads_t *
356 notmuch_query_search_threads (notmuch_query_t *query)
357 {
358     notmuch_threads_t *threads;
359     notmuch_messages_t *messages;
360
361     threads = talloc (query, notmuch_threads_t);
362     if (threads == NULL)
363         return NULL;
364     threads->doc_ids = NULL;
365     talloc_set_destructor (threads, _notmuch_threads_destructor);
366
367     threads->query = query;
368
369     messages = notmuch_query_search_messages (query);
370     if (messages == NULL) {
371             talloc_free (threads);
372             return NULL;
373     }
374
375     threads->doc_ids = g_array_new (FALSE, FALSE, sizeof (unsigned int));
376     while (notmuch_messages_valid (messages)) {
377         unsigned int doc_id = _notmuch_mset_messages_get_doc_id (messages);
378         g_array_append_val (threads->doc_ids, doc_id);
379         notmuch_messages_move_to_next (messages);
380     }
381     threads->doc_id_pos = 0;
382
383     talloc_free (messages);
384
385     if (! _notmuch_doc_id_set_init (threads, &threads->match_set,
386                                     threads->doc_ids)) {
387         talloc_free (threads);
388         return NULL;
389     }
390
391     return threads;
392 }
393
394 void
395 notmuch_query_destroy (notmuch_query_t *query)
396 {
397     talloc_free (query);
398 }
399
400 notmuch_bool_t
401 notmuch_threads_valid (notmuch_threads_t *threads)
402 {
403     unsigned int doc_id;
404
405     while (threads->doc_id_pos < threads->doc_ids->len) {
406         doc_id = g_array_index (threads->doc_ids, unsigned int,
407                                 threads->doc_id_pos);
408         if (_notmuch_doc_id_set_contains (&threads->match_set, doc_id))
409             break;
410
411         threads->doc_id_pos++;
412     }
413
414     return threads->doc_id_pos < threads->doc_ids->len;
415 }
416
417 notmuch_thread_t *
418 notmuch_threads_get (notmuch_threads_t *threads)
419 {
420     unsigned int doc_id;
421
422     if (! notmuch_threads_valid (threads))
423         return NULL;
424
425     doc_id = g_array_index (threads->doc_ids, unsigned int,
426                             threads->doc_id_pos);
427     return _notmuch_thread_create (threads->query,
428                                    threads->query->notmuch,
429                                    doc_id,
430                                    &threads->match_set,
431                                    threads->query->sort);
432 }
433
434 void
435 notmuch_threads_move_to_next (notmuch_threads_t *threads)
436 {
437     threads->doc_id_pos++;
438 }
439
440 void
441 notmuch_threads_destroy (notmuch_threads_t *threads)
442 {
443     talloc_free (threads);
444 }
445
446 unsigned
447 notmuch_query_count_messages (notmuch_query_t *query)
448 {
449     notmuch_database_t *notmuch = query->notmuch;
450     const char *query_string = query->query_string;
451     Xapian::doccount count = 0;
452
453     try {
454         Xapian::Enquire enquire (*notmuch->xapian_db);
455         Xapian::Query mail_query (talloc_asprintf (query, "%s%s",
456                                                    _find_prefix ("type"),
457                                                    "mail"));
458         Xapian::Query string_query, final_query, exclude_query;
459         Xapian::MSet mset;
460         unsigned int flags = (Xapian::QueryParser::FLAG_BOOLEAN |
461                               Xapian::QueryParser::FLAG_PHRASE |
462                               Xapian::QueryParser::FLAG_LOVEHATE |
463                               Xapian::QueryParser::FLAG_BOOLEAN_ANY_CASE |
464                               Xapian::QueryParser::FLAG_WILDCARD |
465                               Xapian::QueryParser::FLAG_PURE_NOT);
466
467         if (strcmp (query_string, "") == 0 ||
468             strcmp (query_string, "*") == 0)
469         {
470             final_query = mail_query;
471         } else {
472             string_query = notmuch->query_parser->
473                 parse_query (query_string, flags);
474             final_query = Xapian::Query (Xapian::Query::OP_AND,
475                                          mail_query, string_query);
476         }
477
478         exclude_query = _notmuch_exclude_tags (query, final_query);
479
480         final_query = Xapian::Query (Xapian::Query::OP_AND_NOT,
481                                          final_query, exclude_query);
482
483         enquire.set_weighting_scheme(Xapian::BoolWeight());
484         enquire.set_docid_order(Xapian::Enquire::ASCENDING);
485
486 #if DEBUG_QUERY
487         fprintf (stderr, "Final query is:\n%s\n", final_query.get_description().c_str());
488 #endif
489
490         enquire.set_query (final_query);
491
492         mset = enquire.get_mset (0, notmuch->xapian_db->get_doccount ());
493
494         count = mset.get_matches_estimated();
495
496     } catch (const Xapian::Error &error) {
497         fprintf (stderr, "A Xapian exception occurred: %s\n",
498                  error.get_msg().c_str());
499         fprintf (stderr, "Query string was: %s\n", query->query_string);
500     }
501
502     return count;
503 }
504
505 unsigned
506 notmuch_query_count_threads (notmuch_query_t *query)
507 {
508     notmuch_messages_t *messages;
509     GHashTable *hash;
510     unsigned int count;
511     notmuch_sort_t sort;
512
513     sort = query->sort;
514     query->sort = NOTMUCH_SORT_UNSORTED;
515     messages = notmuch_query_search_messages (query);
516     query->sort = sort;
517     if (messages == NULL)
518         return 0;
519
520     hash = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, NULL);
521     if (hash == NULL) {
522         talloc_free (messages);
523         return 0;
524     }
525
526     while (notmuch_messages_valid (messages)) {
527         notmuch_message_t *message = notmuch_messages_get (messages);
528         const char *thread_id = notmuch_message_get_thread_id (message);
529         char *thread_id_copy = talloc_strdup (messages, thread_id);
530         if (unlikely (thread_id_copy == NULL)) {
531             notmuch_message_destroy (message);
532             count = 0;
533             goto DONE;
534         }
535         g_hash_table_insert (hash, thread_id_copy, NULL);
536         notmuch_message_destroy (message);
537         notmuch_messages_move_to_next (messages);
538     }
539
540     count = g_hash_table_size (hash);
541
542   DONE:
543     g_hash_table_unref (hash);
544     talloc_free (messages);
545
546     return count;
547 }