1 /* Copyright (c) 2002-2018 Dovecot authors, see the included COPYING file */
2
3 #include "lib.h"
4 #include "array.h"
5 #include "hash.h"
6 #include "mail-search.h"
7
8 struct mail_search_simplify_prev_arg {
9 struct {
10 enum mail_search_arg_type type;
11 enum mail_search_arg_flag search_flags;
12 enum mail_search_date_type date_type;
13 enum mail_flags mail_flags;
14 bool match_not;
15 bool fuzzy;
16 } bin_mask;
17 const char *hdr_field_name_mask;
18 const char *str_mask;
19
20 struct mail_search_arg *prev_arg;
21 };
22
23 struct mail_search_simplify_ctx {
24 pool_t pool;
25 /* arg mask => prev_arg */
26 HASH_TABLE(struct mail_search_simplify_prev_arg *,
27 struct mail_search_simplify_prev_arg *) prev_args;
28 bool parent_and;
29 bool removals;
30 bool initialized;
31 };
32
33 static int
mail_search_simplify_prev_arg_cmp(const struct mail_search_simplify_prev_arg * arg1,const struct mail_search_simplify_prev_arg * arg2)34 mail_search_simplify_prev_arg_cmp(const struct mail_search_simplify_prev_arg *arg1,
35 const struct mail_search_simplify_prev_arg *arg2)
36 {
37 int ret;
38
39 ret = memcmp(&arg1->bin_mask, &arg2->bin_mask, sizeof(arg1->bin_mask));
40 if (ret == 0)
41 ret = null_strcmp(arg1->hdr_field_name_mask, arg2->hdr_field_name_mask);
42 if (ret == 0)
43 ret = null_strcmp(arg1->str_mask, arg2->str_mask);
44 return ret;
45 }
46
47 static unsigned int
mail_search_simplify_prev_arg_hash(const struct mail_search_simplify_prev_arg * arg)48 mail_search_simplify_prev_arg_hash(const struct mail_search_simplify_prev_arg *arg)
49 {
50 unsigned int hash;
51
52 hash = mem_hash(&arg->bin_mask, sizeof(arg->bin_mask));
53 if (arg->hdr_field_name_mask != NULL)
54 hash ^= str_hash(arg->hdr_field_name_mask);
55 if (arg->str_mask != NULL)
56 hash ^= str_hash(arg->str_mask);
57 return hash;
58 }
59
mail_search_arg_get_base_mask(const struct mail_search_arg * arg,struct mail_search_simplify_prev_arg * mask_r)60 static void mail_search_arg_get_base_mask(const struct mail_search_arg *arg,
61 struct mail_search_simplify_prev_arg *mask_r)
62 {
63 i_zero(mask_r);
64 mask_r->bin_mask.type = arg->type;
65 mask_r->bin_mask.fuzzy = arg->fuzzy;
66 mask_r->bin_mask.search_flags = arg->value.search_flags;
67 }
68
69 static struct mail_search_arg **
mail_search_args_simplify_get_prev_argp(struct mail_search_simplify_ctx * ctx,const struct mail_search_simplify_prev_arg * mask)70 mail_search_args_simplify_get_prev_argp(struct mail_search_simplify_ctx *ctx,
71 const struct mail_search_simplify_prev_arg *mask)
72 {
73 struct mail_search_simplify_prev_arg *prev_arg;
74
75 prev_arg = hash_table_lookup(ctx->prev_args, mask);
76 if (prev_arg == NULL) {
77 prev_arg = p_new(ctx->pool, struct mail_search_simplify_prev_arg, 1);
78 prev_arg->bin_mask = mask->bin_mask;
79 prev_arg->hdr_field_name_mask =
80 p_strdup(ctx->pool, mask->hdr_field_name_mask);
81 prev_arg->str_mask =
82 p_strdup(ctx->pool, mask->str_mask);
83 hash_table_insert(ctx->prev_args, prev_arg, prev_arg);
84 }
85 return &prev_arg->prev_arg;
86 }
87
88 static bool
mail_search_args_merge_mask(struct mail_search_simplify_ctx * ctx,struct mail_search_arg * args,const struct mail_search_simplify_prev_arg * mask)89 mail_search_args_merge_mask(struct mail_search_simplify_ctx *ctx,
90 struct mail_search_arg *args,
91 const struct mail_search_simplify_prev_arg *mask)
92 {
93 struct mail_search_arg **prev_argp;
94
95 prev_argp = mail_search_args_simplify_get_prev_argp(ctx, mask);
96 if (*prev_argp == NULL) {
97 *prev_argp = args;
98 return FALSE;
99 }
100
101 if (ctx->initialized)
102 mail_search_arg_one_deinit(args);
103
104 if ((*prev_argp)->match_not != args->match_not) {
105 /* a && !a = 0 */
106 if (ctx->initialized)
107 mail_search_arg_one_deinit(*prev_argp);
108 (*prev_argp)->type = SEARCH_ALL;
109 (*prev_argp)->match_not = ctx->parent_and;
110 }
111 /* duplicate keyword. */
112 return TRUE;
113 }
114
mail_search_args_merge_flags(struct mail_search_simplify_ctx * ctx,struct mail_search_arg * args)115 static bool mail_search_args_merge_flags(struct mail_search_simplify_ctx *ctx,
116 struct mail_search_arg *args)
117 {
118 struct mail_search_simplify_prev_arg mask;
119
120 mail_search_arg_get_base_mask(args, &mask);
121 mask.bin_mask.mail_flags = args->value.flags;
122 return mail_search_args_merge_mask(ctx, args, &mask);
123 }
124
125 static bool
mail_search_args_merge_keywords(struct mail_search_simplify_ctx * ctx,struct mail_search_arg * args)126 mail_search_args_merge_keywords(struct mail_search_simplify_ctx *ctx,
127 struct mail_search_arg *args)
128 {
129 struct mail_search_simplify_prev_arg mask;
130
131 mail_search_arg_get_base_mask(args, &mask);
132 mask.str_mask = args->value.str;
133 return mail_search_args_merge_mask(ctx, args, &mask);
134 }
135
mail_search_args_simplify_set(struct mail_search_arg * args)136 static void mail_search_args_simplify_set(struct mail_search_arg *args)
137 {
138 const struct seq_range *seqset;
139 unsigned int count;
140
141 if (args->match_not) {
142 /* invert the set to drop the NOT. Note that (uint32_t)-1
143 matches the last existing mail, which we don't know at this
144 point. lib-imap/imap-seqset.c has similar code that
145 disallows using (uint32_t)-1 as a real UID. */
146 if (seq_range_exists(&args->value.seqset, (uint32_t)-1))
147 return;
148 args->match_not = FALSE;
149 seq_range_array_invert(&args->value.seqset, 1, (uint32_t)-2);
150 }
151 seqset = array_get(&args->value.seqset, &count);
152 if (count == 1 && seqset->seq1 == 1 && seqset->seq2 >= (uint32_t)-2) {
153 /* 1:* is the same as ALL. */
154 args->type = SEARCH_ALL;
155 } else if (count == 0) {
156 /* empty set is the same as NOT ALL. this is mainly coming
157 from mail_search_args_merge_set() intersection. */
158 args->type = SEARCH_ALL;
159 args->match_not = TRUE;
160 }
161 }
162
mail_search_args_merge_set(struct mail_search_simplify_ctx * ctx,struct mail_search_arg * args)163 static bool mail_search_args_merge_set(struct mail_search_simplify_ctx *ctx,
164 struct mail_search_arg *args)
165 {
166 struct mail_search_simplify_prev_arg mask;
167 struct mail_search_arg **prev_argp;
168
169 if (args->match_not) {
170 /* "*" used - can't simplify it */
171 return FALSE;
172 }
173
174 mail_search_arg_get_base_mask(args, &mask);
175 mask.bin_mask.match_not = args->match_not;
176 prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
177
178 if (*prev_argp == NULL) {
179 *prev_argp = args;
180 return FALSE;
181 } else if (ctx->parent_and) {
182 seq_range_array_intersect(&(*prev_argp)->value.seqset,
183 &args->value.seqset);
184 return TRUE;
185 } else {
186 seq_range_array_merge(&(*prev_argp)->value.seqset,
187 &args->value.seqset);
188 return TRUE;
189 }
190 }
191
mail_search_args_merge_time(struct mail_search_simplify_ctx * ctx,struct mail_search_arg * args)192 static bool mail_search_args_merge_time(struct mail_search_simplify_ctx *ctx,
193 struct mail_search_arg *args)
194 {
195 struct mail_search_simplify_prev_arg mask;
196 struct mail_search_arg **prev_argp, *prev_arg;
197
198 mail_search_arg_get_base_mask(args, &mask);
199 mask.bin_mask.match_not = args->match_not;
200 mask.bin_mask.date_type = args->value.date_type;
201 prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
202
203 if (*prev_argp == NULL) {
204 *prev_argp = args;
205 return FALSE;
206 }
207
208 prev_arg = *prev_argp;
209 switch (args->type) {
210 case SEARCH_BEFORE:
211 if (ctx->parent_and) {
212 if (prev_arg->value.time < args->value.time) {
213 /* prev_arg < 5 AND arg < 10 */
214 } else {
215 /* prev_arg < 10 AND arg < 5 */
216 prev_arg->value.time = args->value.time;
217 }
218 } else {
219 if (prev_arg->value.time < args->value.time) {
220 /* prev_arg < 5 OR arg < 10 */
221 prev_arg->value.time = args->value.time;
222 } else {
223 /* prev_arg < 10 OR arg < 5 */
224 }
225 }
226 return TRUE;
227 case SEARCH_ON:
228 if (prev_arg->value.time == args->value.time)
229 return TRUE;
230 return FALSE;
231 case SEARCH_SINCE:
232 if (ctx->parent_and) {
233 if (prev_arg->value.time < args->value.time) {
234 /* prev_arg >= 5 AND arg >= 10 */
235 prev_arg->value.time = args->value.time;
236 } else {
237 /* prev_arg >= 10 AND arg >= 5 */
238 }
239 } else {
240 if (prev_arg->value.time < args->value.time) {
241 /* prev_arg >= 5 OR arg >= 10 */
242 } else {
243 /* prev_arg >= 10 OR arg >= 5 */
244 prev_arg->value.time = args->value.time;
245 }
246 }
247 return TRUE;
248 default:
249 break;
250 }
251 return FALSE;
252 }
253
mail_search_args_merge_size(struct mail_search_simplify_ctx * ctx,struct mail_search_arg * args)254 static bool mail_search_args_merge_size(struct mail_search_simplify_ctx *ctx,
255 struct mail_search_arg *args)
256 {
257 struct mail_search_simplify_prev_arg mask;
258 struct mail_search_arg **prev_argp, *prev_arg;
259
260 mail_search_arg_get_base_mask(args, &mask);
261 mask.bin_mask.match_not = args->match_not;
262 prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
263
264 if (*prev_argp == NULL) {
265 *prev_argp = args;
266 return FALSE;
267 }
268
269 prev_arg = *prev_argp;
270 switch (args->type) {
271 case SEARCH_SMALLER:
272 if (ctx->parent_and) {
273 if (prev_arg->value.size < args->value.size) {
274 /* prev_arg < 5 AND arg < 10 */
275 } else {
276 /* prev_arg < 10 AND arg < 5 */
277 prev_arg->value.size = args->value.size;
278 }
279 } else {
280 if (prev_arg->value.size < args->value.size) {
281 /* prev_arg < 5 OR arg < 10 */
282 prev_arg->value.size = args->value.size;
283 } else {
284 /* prev_arg < 10 OR arg < 5 */
285 }
286 }
287 return TRUE;
288 case SEARCH_LARGER:
289 if (ctx->parent_and) {
290 if (prev_arg->value.size < args->value.size) {
291 /* prev_arg >= 5 AND arg >= 10 */
292 prev_arg->value.size = args->value.size;
293 } else {
294 /* prev_arg >= 10 AND arg >= 5 */
295 }
296 } else {
297 if (prev_arg->value.size < args->value.size) {
298 /* prev_arg >= 5 OR arg >= 10 */
299 } else {
300 /* prev_arg >= 10 OR arg >= 5 */
301 prev_arg->value.size = args->value.size;
302 }
303 }
304 return TRUE;
305 default:
306 break;
307 }
308 return FALSE;
309 }
310
mail_search_args_merge_text(struct mail_search_simplify_ctx * ctx,struct mail_search_arg * args)311 static bool mail_search_args_merge_text(struct mail_search_simplify_ctx *ctx,
312 struct mail_search_arg *args)
313 {
314 struct mail_search_simplify_prev_arg mask;
315
316 mail_search_arg_get_base_mask(args, &mask);
317 mask.hdr_field_name_mask = args->hdr_field_name;
318 mask.str_mask = args->value.str;
319 return mail_search_args_merge_mask(ctx, args, &mask);
320 }
321
322 static bool
mail_search_args_have_equal(const struct mail_search_arg * args,const struct mail_search_arg * wanted_arg)323 mail_search_args_have_equal(const struct mail_search_arg *args,
324 const struct mail_search_arg *wanted_arg)
325 {
326 const struct mail_search_arg *arg;
327
328 for (arg = args; arg != NULL; arg = arg->next) {
329 if (mail_search_arg_one_equals(arg, wanted_arg))
330 return TRUE;
331 }
332 return FALSE;
333 }
334
335 static bool
mail_search_args_remove_equal(struct mail_search_args * all_args,struct mail_search_arg ** argsp,const struct mail_search_arg * wanted_arg,bool check_subs)336 mail_search_args_remove_equal(struct mail_search_args *all_args,
337 struct mail_search_arg **argsp,
338 const struct mail_search_arg *wanted_arg,
339 bool check_subs)
340 {
341 struct mail_search_arg **argp;
342 bool found = FALSE;
343
344 for (argp = argsp; (*argp) != NULL; ) {
345 if (mail_search_arg_one_equals(*argp, wanted_arg)) {
346 if (all_args->init_refcount > 0)
347 mail_search_arg_one_deinit(*argp);
348 *argp = (*argp)->next;
349 found = TRUE;
350 } else if (check_subs) {
351 i_assert((*argp)->type == SEARCH_SUB ||
352 (*argp)->type == SEARCH_OR);
353 if (!mail_search_args_remove_equal(all_args, &(*argp)->value.subargs, wanted_arg, FALSE)) {
354 /* we already verified that this should have
355 existed. */
356 i_unreached();
357 }
358 if ((*argp)->value.subargs == NULL)
359 *argp = (*argp)->next;
360 else
361 argp = &(*argp)->next;
362 found = TRUE;
363 } else {
364 argp = &(*argp)->next;
365 }
366 }
367 return found;
368 }
369
370 static bool
mail_search_args_have_all_equal(struct mail_search_arg * parent_arg,const struct mail_search_arg * wanted_args)371 mail_search_args_have_all_equal(struct mail_search_arg *parent_arg,
372 const struct mail_search_arg *wanted_args)
373 {
374 const struct mail_search_arg *arg;
375
376 i_assert(parent_arg->type == SEARCH_SUB ||
377 parent_arg->type == SEARCH_OR);
378
379 for (arg = wanted_args; arg != NULL; arg = arg->next) {
380 if (!mail_search_args_have_equal(parent_arg->value.subargs, arg))
381 return FALSE;
382 }
383 return TRUE;
384 }
385
386 static unsigned int
mail_search_args_count(const struct mail_search_arg * args)387 mail_search_args_count(const struct mail_search_arg *args)
388 {
389 unsigned int count;
390
391 for (count = 0; args != NULL; count++)
392 args = args->next;
393 return count;
394 }
395
396 static bool
mail_search_args_simplify_drop_redundant_args(struct mail_search_args * all_args,struct mail_search_arg ** argsp,bool and_arg)397 mail_search_args_simplify_drop_redundant_args(struct mail_search_args *all_args,
398 struct mail_search_arg **argsp,
399 bool and_arg)
400 {
401 struct mail_search_arg *arg, **argp, one_arg, *lowest_arg = NULL;
402 enum mail_search_arg_type child_subargs_type;
403 unsigned int count, lowest_count = UINT_MAX;
404 bool ret = FALSE;
405
406 if (*argsp == NULL)
407 return FALSE;
408
409 child_subargs_type = and_arg ? SEARCH_OR : SEARCH_SUB;
410
411 /* find the arg which has the lowest number of child args */
412 for (arg = *argsp; arg != NULL; arg = arg->next) {
413 if (arg->type != child_subargs_type) {
414 one_arg = *arg;
415 one_arg.next = NULL;
416 lowest_arg = &one_arg;
417 break;
418 }
419 count = mail_search_args_count(arg->value.subargs);
420 if (count < lowest_count) {
421 lowest_arg = arg->value.subargs;
422 lowest_count = count;
423 }
424 }
425 i_assert(lowest_arg != NULL);
426
427 /* if there are any args that include lowest_arg, drop the arg since
428 it's redundant. (non-SUB duplicates are dropped elsewhere.) */
429 for (argp = argsp; *argp != NULL; ) {
430 if (*argp != lowest_arg && (*argp)->type == child_subargs_type &&
431 (*argp)->value.subargs != lowest_arg &&
432 mail_search_args_have_all_equal(*argp, lowest_arg)) {
433 if (all_args->init_refcount > 0)
434 mail_search_arg_one_deinit(*argp);
435 *argp = (*argp)->next;
436 ret = TRUE;
437 } else {
438 argp = &(*argp)->next;
439 }
440 }
441 return ret;
442 }
443
444 static bool
mail_search_args_simplify_extract_common(struct mail_search_args * all_args,struct mail_search_arg ** argsp,pool_t pool,bool and_arg)445 mail_search_args_simplify_extract_common(struct mail_search_args *all_args,
446 struct mail_search_arg **argsp,
447 pool_t pool, bool and_arg)
448 {
449 /* Simple SUB example:
450 (a AND b) OR (a AND c) -> a AND (b OR c)
451
452 More complicated example:
453 (c1 AND c2 AND u1 AND u2) OR (c1 AND c2 AND u3 AND u4) ->
454 c1 AND c2 AND ((u1 AND u2) OR (u3 AND u4))
455
456 Similarly for ORs:
457 (a OR b) AND (a OR c) -> a OR (b AND c)
458
459 (c1 OR c2 OR u1 OR u2) AND (c1 OR c2 OR u3 OR u4) ->
460 c1 OR c2 OR ((u1 OR u2) AND (u3 OR u4))
461
462 */
463 struct mail_search_arg *arg, *sub_arg, *sub_next;
464 struct mail_search_arg *new_arg, *child_arg, *common_args = NULL;
465 enum mail_search_arg_type child_subargs_type;
466
467 if (*argsp == NULL || (*argsp)->next == NULL) {
468 /* single arg, nothing to extract */
469 return FALSE;
470 }
471
472 child_subargs_type = and_arg ? SEARCH_OR : SEARCH_SUB;
473
474 /* find the first arg with child_subargs_type */
475 for (arg = *argsp; arg != NULL; arg = arg->next) {
476 if (arg->type == child_subargs_type)
477 break;
478 }
479 if (arg == NULL)
480 return FALSE;
481
482 for (sub_arg = arg->value.subargs; sub_arg != NULL; sub_arg = sub_next) {
483 sub_next = sub_arg->next;
484
485 /* check if sub_arg is found from all the args */
486 for (arg = *argsp; arg != NULL; arg = arg->next) {
487 if (mail_search_arg_one_equals(arg, sub_arg)) {
488 /* the whole arg matches */
489 } else if (arg->type == child_subargs_type &&
490 mail_search_args_have_equal(arg->value.subargs, sub_arg)) {
491 /* exists as subarg */
492 } else {
493 break;
494 }
495 }
496 if (arg != NULL)
497 continue;
498
499 /* extract the arg and put it to common_args */
500 mail_search_args_remove_equal(all_args, argsp, sub_arg, TRUE);
501 sub_arg->next = common_args;
502 common_args = sub_arg;
503 }
504 if (common_args == NULL)
505 return FALSE;
506
507 /* replace all the original args with a single new SUB/OR arg */
508 new_arg = p_new(pool, struct mail_search_arg, 1);
509 new_arg->type = child_subargs_type;
510 if (*argsp == NULL) {
511 /* there are only common args */
512 new_arg->value.subargs = common_args;
513 } else {
514 /* replace OR arg with AND(OR(non_common_args), common_args)
515 or
516 replace AND arg with OR(AND(non_common_args), common_args) */
517 child_arg = p_new(pool, struct mail_search_arg, 1);
518 child_arg->type = and_arg ? SEARCH_SUB : SEARCH_OR;
519 child_arg->value.subargs = *argsp;
520 child_arg->next = common_args;
521 new_arg->value.subargs = child_arg;
522 }
523 *argsp = new_arg;
524 return TRUE;
525 }
526
527 static bool
mail_search_args_simplify_sub(struct mail_search_args * all_args,pool_t pool,struct mail_search_arg ** argsp,bool parent_and)528 mail_search_args_simplify_sub(struct mail_search_args *all_args, pool_t pool,
529 struct mail_search_arg **argsp, bool parent_and)
530 {
531 struct mail_search_simplify_ctx ctx;
532 struct mail_search_arg *sub, **all_argsp = argsp;
533 bool merged;
534
535 i_zero(&ctx);
536 ctx.initialized = all_args->init_refcount > 0;
537 ctx.parent_and = parent_and;
538 ctx.pool = pool_alloconly_create("mail search args simplify", 1024);
539 hash_table_create(&ctx.prev_args, ctx.pool, 0,
540 mail_search_simplify_prev_arg_hash,
541 mail_search_simplify_prev_arg_cmp);
542
543 while (*argsp != NULL) {
544 struct mail_search_arg *args = *argsp;
545
546 if (args->match_not && (args->type == SEARCH_SUB ||
547 args->type == SEARCH_OR)) {
548 /* neg(p and q and ..) == neg(p) or neg(q) or ..
549 neg(p or q or ..) == neg(p) and neg(q) and .. */
550 args->type = args->type == SEARCH_SUB ?
551 SEARCH_OR : SEARCH_SUB;
552 args->match_not = FALSE;
553 sub = args->value.subargs;
554 do {
555 sub->match_not = !sub->match_not;
556 sub = sub->next;
557 } while (sub != NULL);
558 }
559
560 if ((args->type == SEARCH_SUB && parent_and) ||
561 (args->type == SEARCH_OR && !parent_and) ||
562 ((args->type == SEARCH_SUB || args->type == SEARCH_OR) &&
563 args->value.subargs->next == NULL)) {
564 /* p and (q and ..) == p and q and ..
565 p or (q or ..) == p or q or ..
566 (p) = p */
567 sub = args->value.subargs;
568 for (; sub->next != NULL; sub = sub->next) ;
569 sub->next = args->next;
570 *args = *args->value.subargs;
571 ctx.removals = TRUE;
572 continue;
573 }
574
575 if (args->type == SEARCH_SUB ||
576 args->type == SEARCH_OR ||
577 args->type == SEARCH_INTHREAD) {
578 i_assert(!args->match_not);
579
580 if (args->type != SEARCH_INTHREAD) {
581 bool and_arg = args->type == SEARCH_SUB;
582
583 if (mail_search_args_simplify_drop_redundant_args(all_args, &args->value.subargs, and_arg))
584 ctx.removals = TRUE;
585 if (mail_search_args_simplify_extract_common(all_args, &args->value.subargs, pool, and_arg))
586 ctx.removals = TRUE;
587 }
588 if (mail_search_args_simplify_sub(all_args, pool, &args->value.subargs,
589 args->type != SEARCH_OR))
590 ctx.removals = TRUE;
591 }
592 if (args->type == SEARCH_SEQSET ||
593 args->type == SEARCH_UIDSET)
594 mail_search_args_simplify_set(args);
595
596 /* try to merge arguments */
597 merged = FALSE;
598 switch (args->type) {
599 case SEARCH_ALL: {
600 if (*all_argsp == args && args->next == NULL) {
601 /* this arg has no siblings - no merging */
602 break;
603 }
604 if ((parent_and && !args->match_not) ||
605 (!parent_and && args->match_not)) {
606 /* .. AND ALL ..
607 .. OR NOT ALL ..
608 This arg is irrelevant -> drop */
609 merged = TRUE;
610 break;
611 }
612 /* .. AND NOT ALL ..
613 .. OR ALL ..
614 The other args are irrelevant -> drop them */
615 *all_argsp = args;
616 args->next = NULL;
617 ctx.removals = TRUE;
618 break;
619 }
620 case SEARCH_FLAGS:
621 merged = mail_search_args_merge_flags(&ctx, args);
622 break;
623 case SEARCH_KEYWORDS:
624 merged = mail_search_args_merge_keywords(&ctx, args);
625 break;
626 case SEARCH_SEQSET:
627 case SEARCH_UIDSET:
628 merged = mail_search_args_merge_set(&ctx, args);
629 break;
630 case SEARCH_BEFORE:
631 case SEARCH_ON:
632 case SEARCH_SINCE:
633 merged = mail_search_args_merge_time(&ctx, args);
634 break;
635 case SEARCH_SMALLER:
636 case SEARCH_LARGER:
637 merged = mail_search_args_merge_size(&ctx, args);
638 break;
639 case SEARCH_BODY:
640 case SEARCH_TEXT:
641 if (args->value.str[0] == '\0') {
642 /* BODY "" and TEXT "" matches everything */
643 args->type = SEARCH_ALL;
644 ctx.removals = TRUE;
645 break;
646 }
647 /* fall through */
648 case SEARCH_HEADER:
649 case SEARCH_HEADER_ADDRESS:
650 case SEARCH_HEADER_COMPRESS_LWSP:
651 merged = mail_search_args_merge_text(&ctx, args);
652 break;
653 default:
654 break;
655 }
656 if (merged) {
657 *argsp = args->next;
658 ctx.removals = TRUE;
659 continue;
660 }
661
662 argsp = &args->next;
663 }
664 hash_table_destroy(&ctx.prev_args);
665 pool_unref(&ctx.pool);
666 return ctx.removals;
667 }
668
669 static bool
mail_search_args_simplify_merge_flags(struct mail_search_arg ** argsp,bool parent_and)670 mail_search_args_simplify_merge_flags(struct mail_search_arg **argsp,
671 bool parent_and)
672 {
673 struct mail_search_arg *prev_flags = NULL;
674 bool removals = FALSE;
675
676 while (*argsp != NULL) {
677 struct mail_search_arg *args = *argsp;
678
679 if (args->type == SEARCH_SUB ||
680 args->type == SEARCH_OR ||
681 args->type == SEARCH_INTHREAD) {
682 if (mail_search_args_simplify_merge_flags(&args->value.subargs,
683 args->type != SEARCH_OR))
684 removals = TRUE;
685 } else if (args->type != SEARCH_FLAGS) {
686 /* ignore non-flags */
687 } else if (!((!args->match_not && parent_and) ||
688 (args->match_not && !parent_and))) {
689 /* can't merge these flags args */
690 } else if (prev_flags == NULL) {
691 /* first flags arg */
692 prev_flags = args;
693 } else {
694 /* merge to previous arg */
695 prev_flags->value.flags |= args->value.flags;
696 *argsp = args->next;
697 removals = TRUE;
698 continue;
699 }
700 argsp = &args->next;
701 }
702 return removals;
703 }
704
705 static bool
mail_search_args_unnest_inthreads(struct mail_search_args * args,struct mail_search_arg ** argp,bool parent_inthreads,bool parent_and)706 mail_search_args_unnest_inthreads(struct mail_search_args *args,
707 struct mail_search_arg **argp,
708 bool parent_inthreads, bool parent_and)
709 {
710 struct mail_search_arg *arg, *thread_arg, *or_arg;
711 bool child_inthreads = FALSE, non_inthreads = FALSE;
712
713 for (arg = *argp; arg != NULL; arg = arg->next) {
714 switch (arg->type) {
715 case SEARCH_SUB:
716 case SEARCH_OR:
717 if (!mail_search_args_unnest_inthreads(args,
718 &arg->value.subargs, parent_inthreads,
719 arg->type != SEARCH_OR)) {
720 arg->result = 1;
721 child_inthreads = TRUE;
722 } else {
723 arg->result = 0;
724 non_inthreads = TRUE;
725 }
726 break;
727 case SEARCH_INTHREAD:
728 if (mail_search_args_unnest_inthreads(args,
729 &arg->value.subargs, TRUE, TRUE)) {
730 /* children converted to SEARCH_INTHREADs */
731 arg->type = SEARCH_SUB;
732 }
733 args->have_inthreads = TRUE;
734 arg->result = 1;
735 child_inthreads = TRUE;
736 break;
737 default:
738 arg->result = 0;
739 non_inthreads = TRUE;
740 break;
741 }
742 }
743
744 if (!parent_inthreads || !child_inthreads || !non_inthreads)
745 return FALSE;
746
747 /* put all non-INTHREADs under a single INTHREAD */
748 thread_arg = p_new(args->pool, struct mail_search_arg, 1);
749 thread_arg->type = SEARCH_INTHREAD;
750
751 while (*argp != NULL) {
752 arg = *argp;
753 argp = &(*argp)->next;
754
755 if (arg->result == 0) {
756 /* not an INTHREAD or a SUB/OR with only INTHREADs */
757 arg->next = thread_arg->value.subargs;
758 thread_arg->value.subargs = arg;
759 }
760 }
761 if (!parent_and) {
762 /* We want to OR the args */
763 or_arg = p_new(args->pool, struct mail_search_arg, 1);
764 or_arg->type = SEARCH_OR;
765 or_arg->value.subargs = thread_arg->value.subargs;
766 thread_arg->value.subargs = or_arg;
767 }
768 return TRUE;
769 }
770
mail_search_args_simplify(struct mail_search_args * args)771 void mail_search_args_simplify(struct mail_search_args *args)
772 {
773 bool removals;
774
775 args->simplified = TRUE;
776
777 removals = mail_search_args_simplify_sub(args, args->pool, &args->args, TRUE);
778 if (mail_search_args_unnest_inthreads(args, &args->args,
779 FALSE, TRUE)) {
780 /* we may have added some extra SUBs that could be dropped */
781 if (mail_search_args_simplify_sub(args, args->pool, &args->args, TRUE))
782 removals = TRUE;
783 }
784 do {
785 if (mail_search_args_simplify_drop_redundant_args(args, &args->args, TRUE))
786 removals = TRUE;
787 if (mail_search_args_simplify_extract_common(args, &args->args, args->pool, TRUE))
788 removals = TRUE;
789 if (removals)
790 removals = mail_search_args_simplify_sub(args, args->pool, &args->args, TRUE);
791 /* do the flag merging into a single arg only at the end.
792 up until then they're treated as any other search args,
793 which simplifies their handling. after the flags merging is
794 done, further simplifications are still possible. */
795 if (mail_search_args_simplify_merge_flags(&args->args, TRUE))
796 removals = TRUE;
797 } while (removals);
798 }
799