pattern.c

   1 /*
   2  * Copyright notice from original mutt:
   3  * Copyright (C) 1996-2000 Michael R. Elkins <me@mutt.org>, and others
   4  *
   5  * This file is part of mutt-ng, see http://www.muttng.org/.
   6  * It's licensed under the GNU General Public License,
   7  * please see the file GPL in the top level source directory.
   8  */
   9
  10 #if HAVE_CONFIG_H
  11 # include "config.h"
  12 #endif
  13
  14 #include "mutt.h"
  15 #include "buffer.h"
  16 #include "handler.h"
  17 #include "enter.h"
  18 #include "ascii.h"
  19 #include "mx.h"
  20 #include "mapping.h"
  21 #include "keymap.h"
  22 #include "copy.h"
  23
  24 #include "lib/mem.h"
  25 #include "lib/intl.h"
  26 #include "lib/str.h"
  27
  28 #include <string.h>
  29 #include <stdlib.h>
  30 #include <ctype.h>
  31 #include <sys/stat.h>
  32 #include <unistd.h>
  33 #include <stdarg.h>
  34
  35 #include "mutt_crypt.h"
  36
  37 static int eat_regexp (pattern_t * pat, BUFFER *, BUFFER *);
  38 static int eat_date (pattern_t * pat, BUFFER *, BUFFER *);
  39 static int eat_range (pattern_t * pat, BUFFER *, BUFFER *);
  40
  41 struct pattern_flags {
  42   int tag;                      /* character used to represent this op */
  43   int op;                       /* operation to perform */
  44   int class;
  45   int (*eat_arg) (pattern_t *, BUFFER *, BUFFER *);
  46 } Flags[] = {
  47   {
  48   'A', M_ALL, 0, NULL}, {
  49   'b', M_BODY, M_FULL_MSG, eat_regexp}, {
  50   'B', M_WHOLE_MSG, M_FULL_MSG, eat_regexp}, {
  51   'c', M_CC, 0, eat_regexp}, {
  52   'C', M_RECIPIENT, 0, eat_regexp}, {
  53   'd', M_DATE, 0, eat_date}, {
  54   'D', M_DELETED, 0, NULL}, {
  55   'e', M_SENDER, 0, eat_regexp}, {
  56   'E', M_EXPIRED, 0, NULL}, {
  57   'f', M_FROM, 0, eat_regexp}, {
  58   'F', M_FLAG, 0, NULL}, {
  59   'g', M_CRYPT_SIGN, 0, NULL}, {
  60   'G', M_CRYPT_ENCRYPT, 0, NULL}, {
  61   'h', M_HEADER, M_FULL_MSG, eat_regexp}, {
  62   'H', M_HORMEL, 0, eat_regexp}, {
  63   'i', M_ID, 0, eat_regexp}, {
  64   'k', M_PGP_KEY, 0, NULL}, {
  65   'L', M_ADDRESS, 0, eat_regexp}, {
  66   'l', M_LIST, 0, NULL}, {
  67   'm', M_MESSAGE, 0, eat_range}, {
  68   'n', M_SCORE, 0, eat_range}, {
  69   'N', M_NEW, 0, NULL}, {
  70   'O', M_OLD, 0, NULL}, {
  71   'p', M_PERSONAL_RECIP, 0, NULL}, {
  72   'P', M_PERSONAL_FROM, 0, NULL}, {
  73   'Q', M_REPLIED, 0, NULL}, {
  74   'R', M_READ, 0, NULL}, {
  75   'r', M_DATE_RECEIVED, 0, eat_date}, {
  76   's', M_SUBJECT, 0, eat_regexp}, {
  77   'S', M_SUPERSEDED, 0, NULL}, {
  78   'T', M_TAG, 0, NULL}, {
  79   't', M_TO, 0, eat_regexp}, {
  80   'U', M_UNREAD, 0, NULL}, {
  81   'v', M_COLLAPSED, 0, NULL}, {
  82   'V', M_CRYPT_VERIFIED, 0, NULL},
  83 #ifdef USE_NNTP
  84   {
  85   'w', M_NEWSGROUPS, 0, eat_regexp},
  86 #endif
  87   {
  88   'x', M_REFERENCE, 0, eat_regexp}, {
  89   'y', M_XLABEL, 0, eat_regexp}, {
  90   'z', M_SIZE, 0, eat_range}, {
  91   '=', M_DUPLICATED, 0, NULL}, {
  92   '$', M_UNREFERENCED, 0, NULL}, {
  93   '*', M_REALNAME, 0, NULL}, {
  94   0}
  95 };
  96
  97 static pattern_t *SearchPattern = NULL; /* current search pattern */
  98 static char LastSearch[STRING] = { 0 }; /* last pattern searched for */
  99 static char LastSearchExpn[LONG_STRING] = { 0 };        /* expanded version of
 100                                                            LastSearch */
 101
 102 #define M_MAXRANGE -1
 103
 104 /* constants for parse_date_range() */
 105 #define M_PDR_NONE      0x0000
 106 #define M_PDR_MINUS     0x0001
 107 #define M_PDR_PLUS      0x0002
 108 #define M_PDR_WINDOW    0x0004
 109 #define M_PDR_ABSOLUTE  0x0008
 110 #define M_PDR_DONE      0x0010
 111 #define M_PDR_ERROR     0x0100
 112 #define M_PDR_ERRORDONE (M_PDR_ERROR | M_PDR_DONE)
 113
 114
 115 int mutt_getvaluebychar (char ch, struct mapping_t *table)
 116 {
 117   int i;
 118
 119   for (i = 0; table[i].name; i++) {
 120     if (ch == table[i].name[0])
 121       return table[i].value;
 122   }
 123
 124   return (-1);
 125 }
 126
 127 /* if no uppercase letters are given, do a case-insensitive search */
 128 int mutt_which_case (const char *s)
 129 {
 130   while (*s) {
 131     if (isalpha ((unsigned char) *s) && isupper ((unsigned char) *s))
 132       return 0;                 /* case-sensitive */
 133     s++;
 134   }
 135   return REG_ICASE;             /* case-insensitive */
 136 }
 137
 138 static int
 139 msg_search (CONTEXT * ctx, regex_t * rx, char *buf, size_t blen, int op,
 140             int msgno)
 141 {
 142   char tempfile[_POSIX_PATH_MAX];
 143   MESSAGE *msg = NULL;
 144   STATE s;
 145   struct stat st;
 146   FILE *fp = NULL;
 147   long lng = 0;
 148   int match = 0;
 149   HEADER *h = ctx->hdrs[msgno];
 150
 151   if ((msg = mx_open_message (ctx, msgno)) != NULL) {
 152     if (option (OPTTHOROUGHSRC)) {
 153       /* decode the header / body */
 154       memset (&s, 0, sizeof (s));
 155       s.fpin = msg->fp;
 156       s.flags = M_CHARCONV;
 157       mutt_mktemp (tempfile);
 158       if ((s.fpout = safe_fopen (tempfile, "w+")) == NULL) {
 159         mutt_perror (tempfile);
 160         return (0);
 161       }
 162
 163       if (op != M_BODY)
 164         mutt_copy_header (msg->fp, h, s.fpout, CH_FROM | CH_DECODE, NULL);
 165
 166       if (op != M_HEADER) {
 167         mutt_parse_mime_message (ctx, h);
 168
 169         if (WithCrypto && (h->security & ENCRYPT)
 170             && !crypt_valid_passphrase (h->security)) {
 171           mx_close_message (&msg);
 172           if (fp) {
 173             fclose (fp);
 174             unlink (tempfile);
 175           }
 176           return (0);
 177         }
 178
 179         fseek (msg->fp, h->offset, 0);
 180         mutt_body_handler (h->content, &s);
 181       }
 182
 183       fp = s.fpout;
 184       fflush (fp);
 185       fseek (fp, 0, 0);
 186       fstat (fileno (fp), &st);
 187       lng = (long) st.st_size;
 188     }
 189     else {
 190       /* raw header / body */
 191       fp = msg->fp;
 192       if (op != M_BODY) {
 193         fseek (fp, h->offset, 0);
 194         lng = h->content->offset - h->offset;
 195       }
 196       if (op != M_HEADER) {
 197         if (op == M_BODY)
 198           fseek (fp, h->content->offset, 0);
 199         lng += h->content->length;
 200       }
 201     }
 202
 203     /* search the file "fp" */
 204     while (lng > 0) {
 205       if (fgets (buf, blen - 1, fp) == NULL)
 206         break;                  /* don't loop forever */
 207       if (regexec (rx, buf, 0, NULL, 0) == 0) {
 208         match = 1;
 209         break;
 210       }
 211       lng -= str_len (buf);
 212     }
 213
 214     mx_close_message (&msg);
 215
 216     if (option (OPTTHOROUGHSRC)) {
 217       fclose (fp);
 218       unlink (tempfile);
 219     }
 220   }
 221
 222   return match;
 223 }
 224
 225 int eat_regexp (pattern_t * pat, BUFFER * s, BUFFER * err)
 226 {
 227   BUFFER buf;
 228   int r;
 229
 230   memset (&buf, 0, sizeof (buf));
 231   if (mutt_extract_token (&buf, s, M_TOKEN_PATTERN | M_TOKEN_COMMENT) != 0 ||
 232       !buf.data) {
 233     snprintf (err->data, err->dsize, _("Error in expression: %s"), s->dptr);
 234     return (-1);
 235   }
 236   pat->rx = mem_malloc (sizeof (regex_t));
 237   r =
 238     REGCOMP (pat->rx, buf.data,
 239              REG_NEWLINE | REG_NOSUB | mutt_which_case (buf.data));
 240   mem_free (&buf.data);
 241   if (r) {
 242     regerror (r, pat->rx, err->data, err->dsize);
 243     regfree (pat->rx);
 244     mem_free (&pat->rx);
 245     return (-1);
 246   }
 247   return 0;
 248 }
 249
 250 int eat_range (pattern_t * pat, BUFFER * s, BUFFER * err)
 251 {
 252   char *tmp;
 253   int do_exclusive = 0;
 254   int skip_quote = 0;
 255
 256   /*
 257    * If simple_search is set to "~m %s", the range will have double quotes
 258    * around it...
 259    */
 260   if (*s->dptr == '"') {
 261     s->dptr++;
 262     skip_quote = 1;
 263   }
 264   if (*s->dptr == '<')
 265     do_exclusive = 1;
 266   if ((*s->dptr != '-') && (*s->dptr != '<')) {
 267     /* range minimum */
 268     if (*s->dptr == '>') {
 269       pat->max = M_MAXRANGE;
 270       pat->min = strtol (s->dptr + 1, &tmp, 0) + 1;     /* exclusive range */
 271     }
 272     else
 273       pat->min = strtol (s->dptr, &tmp, 0);
 274     if (toupper ((unsigned char) *tmp) == 'K') {        /* is there a prefix? */
 275       pat->min *= 1024;
 276       tmp++;
 277     }
 278     else if (toupper ((unsigned char) *tmp) == 'M') {
 279       pat->min *= 1048576;
 280       tmp++;
 281     }
 282     if (*s->dptr == '>') {
 283       s->dptr = tmp;
 284       return 0;
 285     }
 286     if (*tmp != '-') {
 287       /* exact value */
 288       pat->max = pat->min;
 289       s->dptr = tmp;
 290       return 0;
 291     }
 292     tmp++;
 293   }
 294   else {
 295     s->dptr++;
 296     tmp = s->dptr;
 297   }
 298
 299   if (isdigit ((unsigned char) *tmp)) {
 300     /* range maximum */
 301     pat->max = strtol (tmp, &tmp, 0);
 302     if (toupper ((unsigned char) *tmp) == 'K') {
 303       pat->max *= 1024;
 304       tmp++;
 305     }
 306     else if (toupper ((unsigned char) *tmp) == 'M') {
 307       pat->max *= 1048576;
 308       tmp++;
 309     }
 310     if (do_exclusive)
 311       (pat->max)--;
 312   }
 313   else
 314     pat->max = M_MAXRANGE;
 315
 316   if (skip_quote && *tmp == '"')
 317     tmp++;
 318
 319   SKIPWS (tmp);
 320   s->dptr = tmp;
 321   return 0;
 322 }
 323
 324 static const char *getDate (const char *s, struct tm *t, BUFFER * err)
 325 {
 326   char *p;
 327   time_t now = time (NULL);
 328   struct tm *tm = localtime (&now);
 329
 330   t->tm_mday = strtol (s, &p, 10);
 331   if (t->tm_mday < 1 || t->tm_mday > 31) {
 332     snprintf (err->data, err->dsize, _("Invalid day of month: %s"), s);
 333     return NULL;
 334   }
 335   if (*p != '/') {
 336     /* fill in today's month and year */
 337     t->tm_mon = tm->tm_mon;
 338     t->tm_year = tm->tm_year;
 339     return p;
 340   }
 341   p++;
 342   t->tm_mon = strtol (p, &p, 10) - 1;
 343   if (t->tm_mon < 0 || t->tm_mon > 11) {
 344     snprintf (err->data, err->dsize, _("Invalid month: %s"), p);
 345     return NULL;
 346   }
 347   if (*p != '/') {
 348     t->tm_year = tm->tm_year;
 349     return p;
 350   }
 351   p++;
 352   t->tm_year = strtol (p, &p, 10);
 353   if (t->tm_year < 70)          /* year 2000+ */
 354     t->tm_year += 100;
 355   else if (t->tm_year > 1900)
 356     t->tm_year -= 1900;
 357   return p;
 358 }
 359
 360 /* Ny   years
 361    Nm   months
 362    Nw   weeks
 363    Nd   days */
 364 static const char *get_offset (struct tm *tm, const char *s, int sign)
 365 {
 366   char *ps;
 367   int offset = strtol (s, &ps, 0);
 368
 369   if ((sign < 0 && offset > 0) || (sign > 0 && offset < 0))
 370     offset = -offset;
 371
 372   switch (*ps) {
 373   case 'y':
 374     tm->tm_year += offset;
 375     break;
 376   case 'm':
 377     tm->tm_mon += offset;
 378     break;
 379   case 'w':
 380     tm->tm_mday += 7 * offset;
 381     break;
 382   case 'd':
 383     tm->tm_mday += offset;
 384     break;
 385   default:
 386     return s;
 387   }
 388   mutt_normalize_time (tm);
 389   return (ps + 1);
 390 }
 391
 392 static void adjust_date_range (struct tm *min, struct tm *max)
 393 {
 394   if (min->tm_year > max->tm_year
 395       || (min->tm_year == max->tm_year && min->tm_mon > max->tm_mon)
 396       || (min->tm_year == max->tm_year && min->tm_mon == max->tm_mon
 397           && min->tm_mday > max->tm_mday)) {
 398     int tmp;
 399
 400     tmp = min->tm_year;
 401     min->tm_year = max->tm_year;
 402     max->tm_year = tmp;
 403
 404     tmp = min->tm_mon;
 405     min->tm_mon = max->tm_mon;
 406     max->tm_mon = tmp;
 407
 408     tmp = min->tm_mday;
 409     min->tm_mday = max->tm_mday;
 410     max->tm_mday = tmp;
 411
 412     min->tm_hour = min->tm_min = min->tm_sec = 0;
 413     max->tm_hour = 23;
 414     max->tm_min = max->tm_sec = 59;
 415   }
 416 }
 417
 418 static const char *parse_date_range (const char *pc, struct tm *min,
 419                                      struct tm *max, int haveMin,
 420                                      struct tm *baseMin, BUFFER * err)
 421 {
 422   int flag = M_PDR_NONE;
 423
 424   while (*pc && ((flag & M_PDR_DONE) == 0)) {
 425     const char *pt;
 426     char ch = *pc++;
 427
 428     SKIPWS (pc);
 429     switch (ch) {
 430     case '-':
 431       {
 432         /* try a range of absolute date minus offset of Ndwmy */
 433         pt = get_offset (min, pc, -1);
 434         if (pc == pt) {
 435           if (flag == M_PDR_NONE) {     /* nothing yet and no offset parsed => absolute date? */
 436             if (!getDate (pc, max, err))
 437               flag |= (M_PDR_ABSOLUTE | M_PDR_ERRORDONE);       /* done bad */
 438             else {
 439               /* reestablish initial base minimum if not specified */
 440               if (!haveMin)
 441                 memcpy (min, baseMin, sizeof (struct tm));
 442               flag |= (M_PDR_ABSOLUTE | M_PDR_DONE);    /* done good */
 443             }
 444           }
 445           else
 446             flag |= M_PDR_ERRORDONE;
 447         }
 448         else {
 449           pc = pt;
 450           if (flag == M_PDR_NONE && !haveMin) { /* the very first "-3d" without a previous absolute date */
 451             max->tm_year = min->tm_year;
 452             max->tm_mon = min->tm_mon;
 453             max->tm_mday = min->tm_mday;
 454           }
 455           flag |= M_PDR_MINUS;
 456         }
 457       }
 458       break;
 459     case '+':
 460       {                         /* enlarge plusRange */
 461         pt = get_offset (max, pc, 1);
 462         if (pc == pt)
 463           flag |= M_PDR_ERRORDONE;
 464         else {
 465           pc = pt;
 466           flag |= M_PDR_PLUS;
 467         }
 468       }
 469       break;
 470     case '*':
 471       {                         /* enlarge window in both directions */
 472         pt = get_offset (min, pc, -1);
 473         if (pc == pt)
 474           flag |= M_PDR_ERRORDONE;
 475         else {
 476           pc = get_offset (max, pc, 1);
 477           flag |= M_PDR_WINDOW;
 478         }
 479       }
 480       break;
 481     default:
 482       flag |= M_PDR_ERRORDONE;
 483     }
 484     SKIPWS (pc);
 485   }
 486   if ((flag & M_PDR_ERROR) && !(flag & M_PDR_ABSOLUTE)) {       /* getDate has its own error message, don't overwrite it here */
 487     snprintf (err->data, err->dsize, _("Invalid relative date: %s"), pc - 1);
 488   }
 489   return ((flag & M_PDR_ERROR) ? NULL : pc);
 490 }
 491
 492 static int eat_date (pattern_t * pat, BUFFER * s, BUFFER * err)
 493 {
 494   BUFFER buffer;
 495   struct tm min, max;
 496
 497   memset (&buffer, 0, sizeof (buffer));
 498   if (mutt_extract_token (&buffer, s, M_TOKEN_COMMENT | M_TOKEN_PATTERN) != 0
 499       || !buffer.data) {
 500     strfcpy (err->data, _("error in expression"), err->dsize);
 501     return (-1);
 502   }
 503
 504   memset (&min, 0, sizeof (min));
 505   /* the `0' time is Jan 1, 1970 UTC, so in order to prevent a negative time
 506      when doing timezone conversion, we use Jan 2, 1970 UTC as the base
 507      here */
 508   min.tm_mday = 2;
 509   min.tm_year = 70;
 510
 511   memset (&max, 0, sizeof (max));
 512
 513   /* Arbitrary year in the future.  Don't set this too high
 514      or mutt_mktime() returns something larger than will
 515      fit in a time_t on some systems */
 516   max.tm_year = 130;
 517   max.tm_mon = 11;
 518   max.tm_mday = 31;
 519   max.tm_hour = 23;
 520   max.tm_min = 59;
 521   max.tm_sec = 59;
 522
 523   if (strchr ("<>=", buffer.data[0])) {
 524     /* offset from current time
 525        <3d      less than three days ago
 526        >3d      more than three days ago
 527        =3d      exactly three days ago */
 528     time_t now = time (NULL);
 529     struct tm *tm = localtime (&now);
 530     int exact = 0;
 531
 532     if (buffer.data[0] == '<') {
 533       memcpy (&min, tm, sizeof (min));
 534       tm = &min;
 535     }
 536     else {
 537       memcpy (&max, tm, sizeof (max));
 538       tm = &max;
 539
 540       if (buffer.data[0] == '=')
 541         exact++;
 542     }
 543     tm->tm_hour = 23;
 544     tm->tm_min = tm->tm_sec = 59;
 545
 546     /* force negative offset */
 547     get_offset (tm, buffer.data + 1, -1);
 548
 549     if (exact) {
 550       /* start at the beginning of the day in question */
 551       memcpy (&min, &max, sizeof (max));
 552       min.tm_hour = min.tm_sec = min.tm_min = 0;
 553     }
 554   }
 555   else {
 556     const char *pc = buffer.data;
 557
 558     int haveMin = FALSE;
 559     int untilNow = FALSE;
 560
 561     if (isdigit ((unsigned char) *pc)) {
 562       /* mininum date specified */
 563       if ((pc = getDate (pc, &min, err)) == NULL) {
 564         mem_free (&buffer.data);
 565         return (-1);
 566       }
 567       haveMin = TRUE;
 568       SKIPWS (pc);
 569       if (*pc == '-') {
 570         const char *pt = pc + 1;
 571
 572         SKIPWS (pt);
 573         untilNow = (*pt == '\0');
 574       }
 575     }
 576
 577     if (!untilNow) {            /* max date or relative range/window */
 578
 579       struct tm baseMin;
 580
 581       if (!haveMin) {           /* save base minimum and set current date, e.g. for "-3d+1d" */
 582         time_t now = time (NULL);
 583         struct tm *tm = localtime (&now);
 584
 585         memcpy (&baseMin, &min, sizeof (baseMin));
 586         memcpy (&min, tm, sizeof (min));
 587         min.tm_hour = min.tm_sec = min.tm_min = 0;
 588       }
 589
 590       /* preset max date for relative offsets,
 591          if nothing follows we search for messages on a specific day */
 592       max.tm_year = min.tm_year;
 593       max.tm_mon = min.tm_mon;
 594       max.tm_mday = min.tm_mday;
 595
 596       if (!parse_date_range (pc, &min, &max, haveMin, &baseMin, err)) { /* bail out on any parsing error */
 597         mem_free (&buffer.data);
 598         return (-1);
 599       }
 600     }
 601   }
 602
 603   /* Since we allow two dates to be specified we'll have to adjust that. */
 604   adjust_date_range (&min, &max);
 605
 606   pat->min = mutt_mktime (&min, 1);
 607   pat->max = mutt_mktime (&max, 1);
 608
 609   mem_free (&buffer.data);
 610
 611   return 0;
 612 }
 613
 614 static struct pattern_flags *lookup_tag (char tag)
 615 {
 616   int i;
 617
 618   for (i = 0; Flags[i].tag; i++)
 619     if (Flags[i].tag == tag)
 620       return (&Flags[i]);
 621   return NULL;
 622 }
 623
 624 static /* const */ char *find_matching_paren ( /* const */ char *s)
 625 {
 626   int level = 1;
 627
 628   for (; *s; s++) {
 629     if (*s == '(')
 630       level++;
 631     else if (*s == ')') {
 632       level--;
 633       if (!level)
 634         break;
 635     }
 636   }
 637   return s;
 638 }
 639
 640 void mutt_pattern_free (pattern_t ** pat)
 641 {
 642   pattern_t *tmp;
 643
 644   while (*pat) {
 645     tmp = *pat;
 646     *pat = (*pat)->next;
 647
 648     if (tmp->rx) {
 649       regfree (tmp->rx);
 650       mem_free (&tmp->rx);
 651     }
 652     if (tmp->child)
 653       mutt_pattern_free (&tmp->child);
 654     mem_free (&tmp);
 655   }
 656 }
 657
 658 pattern_t *mutt_pattern_comp ( /* const */ char *s, int flags, BUFFER * err)
 659 {
 660   pattern_t *curlist = NULL;
 661   pattern_t *tmp;
 662   pattern_t *last = NULL;
 663   int not = 0;
 664   int alladdr = 0;
 665   int or = 0;
 666   int implicit = 1;             /* used to detect logical AND operator */
 667   struct pattern_flags *entry;
 668   char *p;
 669   char *buf;
 670   BUFFER ps;
 671
 672   memset (&ps, 0, sizeof (ps));
 673   ps.dptr = s;
 674   ps.dsize = str_len (s);
 675
 676   while (*ps.dptr) {
 677     SKIPWS (ps.dptr);
 678     switch (*ps.dptr) {
 679     case '^':
 680       ps.dptr++;
 681       alladdr = !alladdr;
 682       break;
 683     case '!':
 684       ps.dptr++;
 685       not = !not;
 686       break;
 687     case '|':
 688       if (!or) {
 689         if (!curlist) {
 690           snprintf (err->data, err->dsize, _("error in pattern at: %s"),
 691                     ps.dptr);
 692           return NULL;
 693         }
 694         if (curlist->next) {
 695           /* A & B | C == (A & B) | C */
 696           tmp = new_pattern ();
 697           tmp->op = M_AND;
 698           tmp->child = curlist;
 699
 700           curlist = tmp;
 701           last = curlist;
 702         }
 703
 704         or = 1;
 705       }
 706       ps.dptr++;
 707       implicit = 0;
 708       not = 0;
 709       alladdr = 0;
 710       break;
 711     case '~':
 712       if (implicit && or) {
 713         /* A | B & C == (A | B) & C */
 714         tmp = new_pattern ();
 715         tmp->op = M_OR;
 716         tmp->child = curlist;
 717         curlist = tmp;
 718         last = tmp;
 719         or = 0;
 720       }
 721
 722       tmp = new_pattern ();
 723       tmp->not = not;
 724       tmp->alladdr = alladdr;
 725       not = 0;
 726       alladdr = 0;
 727
 728       if (last)
 729         last->next = tmp;
 730       else
 731         curlist = tmp;
 732       last = tmp;
 733
 734       ps.dptr++;                /* move past the ~ */
 735       if ((entry = lookup_tag (*ps.dptr)) == NULL) {
 736         snprintf (err->data, err->dsize, _("%c: invalid command"), *ps.dptr);
 737         mutt_pattern_free (&curlist);
 738         return NULL;
 739       }
 740       if (entry->class && (flags & entry->class) == 0) {
 741         snprintf (err->data, err->dsize, _("%c: not supported in this mode"),
 742                   *ps.dptr);
 743         mutt_pattern_free (&curlist);
 744         return NULL;
 745       }
 746       tmp->op = entry->op;
 747
 748       ps.dptr++;                /* eat the operator and any optional whitespace */
 749       SKIPWS (ps.dptr);
 750
 751       if (entry->eat_arg) {
 752         if (!*ps.dptr) {
 753           snprintf (err->data, err->dsize, _("missing parameter"));
 754           mutt_pattern_free (&curlist);
 755           return NULL;
 756         }
 757         if (entry->eat_arg (tmp, &ps, err) == -1) {
 758           mutt_pattern_free (&curlist);
 759           return NULL;
 760         }
 761       }
 762       implicit = 1;
 763       break;
 764     case '(':
 765       p = find_matching_paren (ps.dptr + 1);
 766       if (*p != ')') {
 767         snprintf (err->data, err->dsize, _("mismatched parenthesis: %s"),
 768                   ps.dptr);
 769         mutt_pattern_free (&curlist);
 770         return NULL;
 771       }
 772       /* compile the sub-expression */
 773       buf = str_substrdup (ps.dptr + 1, p);
 774       if ((tmp = mutt_pattern_comp (buf, flags, err)) == NULL) {
 775         mem_free (&buf);
 776         mutt_pattern_free (&curlist);
 777         return NULL;
 778       }
 779       mem_free (&buf);
 780       if (last)
 781         last->next = tmp;
 782       else
 783         curlist = tmp;
 784       last = tmp;
 785       tmp->not ^= not;
 786       tmp->alladdr |= alladdr;
 787       not = 0;
 788       alladdr = 0;
 789       ps.dptr = p + 1;          /* restore location */
 790       break;
 791     default:
 792       snprintf (err->data, err->dsize, _("error in pattern at: %s"), ps.dptr);
 793       mutt_pattern_free (&curlist);
 794       return NULL;
 795     }
 796   }
 797   if (!curlist) {
 798     strfcpy (err->data, _("empty pattern"), err->dsize);
 799     return NULL;
 800   }
 801   if (curlist->next) {
 802     tmp = new_pattern ();
 803     tmp->op = or ? M_OR : M_AND;
 804     tmp->child = curlist;
 805     curlist = tmp;
 806   }
 807   return (curlist);
 808 }
 809
 810 static int
 811 perform_and (pattern_t * pat, pattern_exec_flag flags, CONTEXT * ctx,
 812              HEADER * hdr)
 813 {
 814   for (; pat; pat = pat->next)
 815     if (mutt_pattern_exec (pat, flags, ctx, hdr) <= 0)
 816       return 0;
 817   return 1;
 818 }
 819
 820 static int
 821 perform_or (struct pattern_t *pat, pattern_exec_flag flags, CONTEXT * ctx,
 822             HEADER * hdr)
 823 {
 824   for (; pat; pat = pat->next)
 825     if (mutt_pattern_exec (pat, flags, ctx, hdr) > 0)
 826       return 1;
 827   return 0;
 828 }
 829
 830 static int match_adrlist (regex_t * rx, int match_personal, int alladdr,
 831                           int n, ...)
 832 {
 833   va_list ap;
 834   ADDRESS *a;
 835
 836   va_start (ap, n);
 837   for (; n; n--) {
 838     for (a = va_arg (ap, ADDRESS *); a; a = a->next) {
 839       if (alladdr ^
 840           ((a->mailbox && regexec (rx, a->mailbox, 0, NULL, 0) == 0) ||
 841            (match_personal && a->personal &&
 842             regexec (rx, a->personal, 0, NULL, 0) == 0))) {
 843         va_end (ap);
 844         return (!alladdr);      /* Found match, or non-match if alladdr */
 845       }
 846     }
 847   }
 848   va_end (ap);
 849   return alladdr;               /* No matches, or all matches if alladdr */
 850 }
 851
 852 static int match_reference (regex_t * rx, LIST * refs)
 853 {
 854   for (; refs; refs = refs->next)
 855     if (regexec (rx, refs->data, 0, NULL, 0) == 0)
 856       return 1;
 857   return 0;
 858 }
 859
 860 int mutt_is_list_recipient (int alladdr, ADDRESS * a1, ADDRESS * a2)
 861 {
 862   for (; a1; a1 = a1->next)
 863     if (alladdr ^ mutt_is_subscribed_list (a1))
 864       return (!alladdr);
 865   for (; a2; a2 = a2->next)
 866     if (alladdr ^ mutt_is_subscribed_list (a2))
 867       return (!alladdr);
 868   return alladdr;
 869 }
 870
 871 int mutt_is_list_cc (int alladdr, ADDRESS * a1, ADDRESS * a2)
 872 {
 873   for (; a1; a1 = a1->next)
 874     if (alladdr ^ mutt_is_mail_list (a1))
 875       return (!alladdr);
 876   for (; a2; a2 = a2->next)
 877     if (alladdr ^ mutt_is_mail_list (a2))
 878       return (!alladdr);
 879   return alladdr;
 880 }
 881
 882 static int match_user (int alladdr, ADDRESS * a1, ADDRESS * a2)
 883 {
 884   for (; a1; a1 = a1->next)
 885     if (alladdr ^ mutt_addr_is_user (a1))
 886       return (!alladdr);
 887   for (; a2; a2 = a2->next)
 888     if (alladdr ^ mutt_addr_is_user (a2))
 889       return (!alladdr);
 890   return alladdr;
 891 }
 892
 893 /* test if name is considered a real name, i.e. consists of at least 2
 894  * space-separated words of which none may end in a dot
 895  */
 896 static int valid_realname (const char *name)
 897 {
 898   const char *p = name;
 899   int ret = 0;
 900
 901   while (*p) {
 902     if (isspace (*p))
 903       ret++;
 904     else if (*p == '.')
 905       /* skip abbr. parts of names (e.g. 'J. User') */
 906       ret--;
 907     p++;
 908   }
 909   return (ret >= 1);
 910 }
 911
 912 /* flags
 913         M_MATCH_FULL_ADDRESS    match both personal and machine address */
 914 int
 915 mutt_pattern_exec (struct pattern_t *pat, pattern_exec_flag flags,
 916                    CONTEXT * ctx, HEADER * h)
 917 {
 918   char buf[STRING];
 919
 920   switch (pat->op) {
 921   case M_AND:
 922     return (pat->not ^ (perform_and (pat->child, flags, ctx, h) > 0));
 923   case M_OR:
 924     return (pat->not ^ (perform_or (pat->child, flags, ctx, h) > 0));
 925   case M_ALL:
 926     return (!pat->not);
 927   case M_EXPIRED:
 928     return (pat->not ^ h->expired);
 929   case M_SUPERSEDED:
 930     return (pat->not ^ h->superseded);
 931   case M_FLAG:
 932     return (pat->not ^ h->flagged);
 933   case M_TAG:
 934     return (pat->not ^ h->tagged);
 935   case M_NEW:
 936     return (pat->not ? h->old || h->read : !(h->old || h->read));
 937   case M_UNREAD:
 938     return (pat->not ? h->read : !h->read);
 939   case M_REPLIED:
 940     return (pat->not ^ h->replied);
 941   case M_OLD:
 942     return (pat->not ? (!h->old || h->read) : (h->old && !h->read));
 943   case M_READ:
 944     return (pat->not ^ h->read);
 945   case M_DELETED:
 946     return (pat->not ^ h->deleted);
 947   case M_MESSAGE:
 948     return (pat->not ^ (h->msgno >= pat->min - 1 && (pat->max == M_MAXRANGE ||
 949                                                      h->msgno <=
 950                                                      pat->max - 1)));
 951   case M_DATE:
 952     return (pat->
 953             not ^ (h->date_sent >= pat->min && h->date_sent <= pat->max));
 954   case M_DATE_RECEIVED:
 955     return (pat->not ^ (h->received >= pat->min && h->received <= pat->max));
 956   case M_BODY:
 957   case M_HEADER:
 958   case M_WHOLE_MSG:
 959     return (pat->
 960             not ^ msg_search (ctx, pat->rx, buf, sizeof (buf), pat->op,
 961                               h->msgno));
 962   case M_SENDER:
 963     return (pat->not ^ match_adrlist (pat->rx, flags & M_MATCH_FULL_ADDRESS,
 964                                       pat->alladdr, 1, h->env->sender));
 965   case M_FROM:
 966     return (pat->not ^ match_adrlist (pat->rx, flags & M_MATCH_FULL_ADDRESS,
 967                                       pat->alladdr, 1, h->env->from));
 968   case M_TO:
 969     return (pat->not ^ match_adrlist (pat->rx, flags & M_MATCH_FULL_ADDRESS,
 970                                       pat->alladdr, 1, h->env->to));
 971   case M_CC:
 972     return (pat->not ^ match_adrlist (pat->rx, flags & M_MATCH_FULL_ADDRESS,
 973                                       pat->alladdr, 1, h->env->cc));
 974   case M_SUBJECT:
 975     return (pat->
 976             not ^ (h->env && h->env->subject
 977                    && regexec (pat->rx, h->env->subject, 0, NULL, 0) == 0));
 978   case M_ID:
 979     return (pat->
 980             not ^ (h->env && h->env->message_id
 981                    && regexec (pat->rx, h->env->message_id, 0, NULL,
 982                                0) == 0));
 983   case M_SCORE:
 984     return (pat->not ^ (h->score >= pat->min && (pat->max == M_MAXRANGE ||
 985                                                  h->score <= pat->max)));
 986   case M_SIZE:
 987     return (pat->
 988             not ^ (h->content->length >= pat->min
 989                    && (pat->max == M_MAXRANGE
 990                        || h->content->length <= pat->max)));
 991   case M_REFERENCE:
 992     return (pat->not ^ match_reference (pat->rx, h->env->references));
 993   case M_ADDRESS:
 994     return (pat->
 995             not ^ (h->env
 996                    && match_adrlist (pat->rx, flags & M_MATCH_FULL_ADDRESS,
 997                                      pat->alladdr, 4, h->env->from,
 998                                      h->env->sender, h->env->to,
 999                                      h->env->cc)));
1000   case M_RECIPIENT:
1001     return (pat->
1002             not ^ (h->env
1003                    && match_adrlist (pat->rx, flags & M_MATCH_FULL_ADDRESS,
1004                                      pat->alladdr, 2, h->env->to,
1005                                      h->env->cc)));
1006   case M_LIST:
1007     return (pat->
1008             not ^ (h->env
1009                    && mutt_is_list_recipient (pat->alladdr, h->env->to,
1010                                               h->env->cc)));
1011   case M_PERSONAL_RECIP:
1012     return (pat->
1013             not ^ (h->env
1014                    && match_user (pat->alladdr, h->env->to, h->env->cc)));
1015   case M_PERSONAL_FROM:
1016     return (pat->
1017             not ^ (h->env && match_user (pat->alladdr, h->env->from, NULL)));
1018   case M_COLLAPSED:
1019     return (pat->not ^ (h->collapsed && h->num_hidden > 1));
1020   case M_CRYPT_SIGN:
1021     if (!WithCrypto)
1022       break;
1023     return (pat->not ^ ((h->security & SIGN) ? 1 : 0));
1024   case M_CRYPT_VERIFIED:
1025     if (!WithCrypto)
1026       break;
1027     return (pat->not ^ ((h->security & GOODSIGN) ? 1 : 0));
1028   case M_CRYPT_ENCRYPT:
1029     if (!WithCrypto)
1030       break;
1031     return (pat->not ^ ((h->security & ENCRYPT) ? 1 : 0));
1032   case M_PGP_KEY:
1033     if (!(WithCrypto & APPLICATION_PGP))
1034       break;
1035     return (pat->not ^ ((h->security & APPLICATION_PGP)
1036                         && (h->security & PGPKEY)));
1037   case M_XLABEL:
1038     return (pat->
1039             not ^ (h->env->x_label
1040                    && regexec (pat->rx, h->env->x_label, 0, NULL, 0) == 0));
1041   case M_HORMEL:
1042     return (pat->
1043             not ^ (h->env->spam && h->env->spam->data
1044                    && regexec (pat->rx, h->env->spam->data, 0, NULL,
1045                                0) == 0));
1046   case M_DUPLICATED:
1047     return (pat->not ^ (h->thread && h->thread->duplicate_thread));
1048   case M_UNREFERENCED:
1049     return (pat->not ^ (h->thread && !h->thread->child));
1050   case M_REALNAME:
1051     /* realname filter:
1052      * we have a match if
1053      * - From: matches $alternates
1054      * - or we have an alias for current address
1055      * - or From: contains valid email address _and_ name has >= 2 fields
1056      */
1057     return (pat->
1058             not ^ (h->env && h->env->from && (mutt_addr_is_user (h->env->from)
1059                                               ||
1060                                               (alias_reverse_lookup
1061                                                (h->env->from) != NULL)
1062                                               || (h->env->from->personal
1063                                                   && valid_realname (h->env->
1064                                                                      from->
1065                                                                      personal)
1066                                                   && h->env->from->mailbox)
1067                    )));
1068 #ifdef USE_NNTP
1069   case M_NEWSGROUPS:
1070     return (pat->
1071             not ^ (h->env->newsgroups
1072                    && regexec (pat->rx, h->env->newsgroups, 0, NULL,
1073                                0) == 0));
1074 #endif
1075   }
1076   mutt_error (_("error: unknown op %d (report this error)."), pat->op);
1077   return (-1);
1078 }
1079
1080 static void quote_simple (char *tmp, size_t len, const char *p)
1081 {
1082   int i = 0;
1083
1084   tmp[i++] = '"';
1085   while (*p && i < len - 3) {
1086     if (*p == '\\' || *p == '"')
1087       tmp[i++] = '\\';
1088     tmp[i++] = *p++;
1089   }
1090   tmp[i++] = '"';
1091   tmp[i] = 0;
1092 }
1093
1094 /* convert a simple search into a real request */
1095 void mutt_check_simple (char *s, size_t len, const char *simple)
1096 {
1097   char tmp[LONG_STRING];
1098
1099   /* XXX - is ascii_strcasecmp() right here, or should we use locale's
1100    * equivalences?
1101    */
1102
1103   if (!strchr (s, '~')) {       /* yup, so spoof a real request */
1104     /* convert old tokens into the new format */
1105     if (ascii_strcasecmp ("all", s) == 0 || !str_cmp ("^", s) || !str_cmp (".", s))     /* ~A is more efficient */
1106       strfcpy (s, "~A", len);
1107     else if (ascii_strcasecmp ("del", s) == 0)
1108       strfcpy (s, "~D", len);
1109     else if (ascii_strcasecmp ("flag", s) == 0)
1110       strfcpy (s, "~F", len);
1111     else if (ascii_strcasecmp ("new", s) == 0)
1112       strfcpy (s, "~N", len);
1113     else if (ascii_strcasecmp ("old", s) == 0)
1114       strfcpy (s, "~O", len);
1115     else if (ascii_strcasecmp ("repl", s) == 0)
1116       strfcpy (s, "~Q", len);
1117     else if (ascii_strcasecmp ("read", s) == 0)
1118       strfcpy (s, "~R", len);
1119     else if (ascii_strcasecmp ("tag", s) == 0)
1120       strfcpy (s, "~T", len);
1121     else if (ascii_strcasecmp ("unread", s) == 0)
1122       strfcpy (s, "~U", len);
1123     else {
1124       quote_simple (tmp, sizeof (tmp), s);
1125       mutt_expand_fmt (s, len, simple, tmp);
1126     }
1127   }
1128 }
1129
1130 int mutt_pattern_func (int op, char *prompt)
1131 {
1132   pattern_t *pat;
1133   char buf[LONG_STRING] = "", *simple, error[STRING];
1134   BUFFER err;
1135   int i;
1136
1137   strfcpy (buf, NONULL (Context->pattern), sizeof (buf));
1138   if (prompt || op != M_LIMIT)
1139     if (mutt_get_field (prompt, buf, sizeof (buf), M_PATTERN | M_CLEAR) != 0)
1140       return (-1);
1141   if (!buf[0]) {
1142     if (op == M_LIMIT)
1143       strncpy (buf, "~A", sizeof (buf));
1144     else
1145       return (-1);
1146   }
1147
1148   mutt_message _("Compiling search pattern...");
1149
1150   simple = str_dup (buf);
1151   mutt_check_simple (buf, sizeof (buf), NONULL (SimpleSearch));
1152
1153   err.data = error;
1154   err.dsize = sizeof (error);
1155   if ((pat = mutt_pattern_comp (buf, M_FULL_MSG, &err)) == NULL) {
1156     mem_free (&simple);
1157     mutt_error ("%s", err.data);
1158     return (-1);
1159   }
1160
1161   mutt_message _("Executing command on matching messages...");
1162
1163 #define THIS_BODY Context->hdrs[i]->content
1164
1165   if (op == M_LIMIT) {
1166     Context->vcount = 0;
1167     Context->vsize = 0;
1168     Context->collapsed = 0;
1169
1170     for (i = 0; i < Context->msgcount; i++) {
1171       /* new limit pattern implicitly uncollapses all threads */
1172       Context->hdrs[i]->virtual = -1;
1173       Context->hdrs[i]->limited = 0;
1174       Context->hdrs[i]->collapsed = 0;
1175       Context->hdrs[i]->num_hidden = 0;
1176       if (mutt_pattern_exec
1177           (pat, M_MATCH_FULL_ADDRESS, Context, Context->hdrs[i])) {
1178         Context->hdrs[i]->virtual = Context->vcount;
1179         Context->hdrs[i]->limited = 1;
1180         Context->v2r[Context->vcount] = i;
1181         Context->vcount++;
1182         Context->vsize += THIS_BODY->length + THIS_BODY->offset -
1183           THIS_BODY->hdr_offset;
1184       }
1185     }
1186   }
1187   else {
1188     for (i = 0; i < Context->vcount; i++) {
1189       if (mutt_pattern_exec
1190           (pat, M_MATCH_FULL_ADDRESS, Context,
1191            Context->hdrs[Context->v2r[i]])) {
1192         switch (op) {
1193         case M_UNDELETE:
1194           mutt_set_flag (Context, Context->hdrs[Context->v2r[i]], M_PURGED,
1195                          0);
1196         case M_DELETE:
1197           mutt_set_flag (Context, Context->hdrs[Context->v2r[i]], M_DELETE,
1198                          (op == M_DELETE));
1199           break;
1200         case M_TAG:
1201         case M_UNTAG:
1202           mutt_set_flag (Context, Context->hdrs[Context->v2r[i]], M_TAG,
1203                          (op == M_TAG));
1204           break;
1205         }
1206       }
1207     }
1208   }
1209
1210 #undef THIS_BODY
1211
1212   mutt_clear_error ();
1213
1214   if (op == M_LIMIT) {
1215     mem_free (&Context->pattern);
1216     if (Context->limit_pattern)
1217       mutt_pattern_free (&Context->limit_pattern);
1218     if (!Context->vcount) {
1219       mutt_error _("No messages matched criteria.");
1220
1221 #if 0
1222       Context->vcount = Context->msgcount;
1223       /* restore full display */
1224       for (i = 0; i < Context->msgcount; i++) {
1225         Context->hdrs[i]->virtual = i;
1226         Context->v2r[i] = i;
1227       }
1228 #endif
1229     }
1230     else if (str_ncmp (buf, "~A", 2) != 0) {
1231       Context->pattern = simple;
1232       simple = NULL;            /* don't clobber it */
1233       Context->limit_pattern = mutt_pattern_comp (buf, M_FULL_MSG, &err);
1234     }
1235   }
1236   mem_free (&simple);
1237   mutt_pattern_free (&pat);
1238   return 0;
1239 }
1240
1241 int mutt_search_command (int cur, int op)
1242 {
1243   int i, j;
1244   char buf[STRING];
1245   char temp[LONG_STRING];
1246   char error[STRING];
1247   BUFFER err;
1248   int incr;
1249   HEADER *h;
1250
1251   if (op != OP_SEARCH_NEXT && op != OP_SEARCH_OPPOSITE) {
1252     strfcpy (buf, LastSearch, sizeof (buf));
1253     if (mutt_get_field ((op == OP_SEARCH) ? _("Search for: ") :
1254                         _("Reverse search for: "), buf, sizeof (buf),
1255                         M_CLEAR | M_PATTERN) != 0 || !buf[0])
1256       return (-1);
1257
1258     if (op == OP_SEARCH)
1259       unset_option (OPTSEARCHREVERSE);
1260     else
1261       set_option (OPTSEARCHREVERSE);
1262
1263     /* compare the *expanded* version of the search pattern in case
1264        $simple_search has changed while we were searching */
1265     strfcpy (temp, buf, sizeof (temp));
1266     mutt_check_simple (temp, sizeof (temp), NONULL (SimpleSearch));
1267
1268     if (!SearchPattern || str_cmp (temp, LastSearchExpn)) {
1269       set_option (OPTSEARCHINVALID);
1270       strfcpy (LastSearch, buf, sizeof (LastSearch));
1271       mutt_message _("Compiling search pattern...");
1272
1273       mutt_pattern_free (&SearchPattern);
1274       err.data = error;
1275       err.dsize = sizeof (error);
1276       if ((SearchPattern =
1277            mutt_pattern_comp (temp, M_FULL_MSG, &err)) == NULL) {
1278         mutt_error ("%s", error);
1279         return (-1);
1280       }
1281       mutt_clear_error ();
1282     }
1283   }
1284   else if (!SearchPattern) {
1285     mutt_error _("No search pattern.");
1286
1287     return (-1);
1288   }
1289
1290   if (option (OPTSEARCHINVALID)) {
1291     for (i = 0; i < Context->msgcount; i++)
1292       Context->hdrs[i]->searched = 0;
1293     unset_option (OPTSEARCHINVALID);
1294   }
1295
1296   incr = (option (OPTSEARCHREVERSE)) ? -1 : 1;
1297   if (op == OP_SEARCH_OPPOSITE)
1298     incr = -incr;
1299
1300   for (i = cur + incr, j = 0; j != Context->vcount; j++) {
1301     if (i > Context->vcount - 1) {
1302       i = 0;
1303       if (option (OPTWRAPSEARCH))
1304         mutt_message (_("Search wrapped to top."));
1305
1306       else {
1307         mutt_message _("Search hit bottom without finding match");
1308
1309         return (-1);
1310       }
1311     }
1312     else if (i < 0) {
1313       i = Context->vcount - 1;
1314       if (option (OPTWRAPSEARCH))
1315         mutt_message (_("Search wrapped to bottom."));
1316
1317       else {
1318         mutt_message _("Search hit top without finding match");
1319
1320         return (-1);
1321       }
1322     }
1323
1324     h = Context->hdrs[Context->v2r[i]];
1325     if (h->searched) {
1326       /* if we've already evaulated this message, use the cached value */
1327       if (h->matched)
1328         return i;
1329     }
1330     else {
1331       /* remember that we've already searched this message */
1332       h->searched = 1;
1333       if ((h->matched =
1334            (mutt_pattern_exec
1335             (SearchPattern, M_MATCH_FULL_ADDRESS, Context, h) > 0)))
1336         return i;
1337     }
1338
1339     if (SigInt) {
1340       mutt_error _("Search interrupted.");
1341
1342       SigInt = 0;
1343       return (-1);
1344     }
1345
1346     i += incr;
1347   }
1348
1349   mutt_error _("Not found.");
1350
1351   return (-1);
1352 }