thread.c

   1 /*@ S-nail - a mail user agent derived from Berkeley Mail.
   2  *@ Message threading.
   3  *
   4  * Copyright (c) 2000-2004 Gunnar Ritter, Freiburg i. Br., Germany.
   5  * Copyright (c) 2012 - 2013 Steffen "Daode" Nurpmeso <sdaoden@users.sf.net>.
   6  */
   7 /*
   8  * Copyright (c) 2004
   9  *      Gunnar Ritter.  All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. All advertising materials mentioning features or use of this software
  20  *    must display the following acknowledgement:
  21  *      This product includes software developed by Gunnar Ritter
  22  *      and his contributors.
  23  * 4. Neither the name of Gunnar Ritter nor the names of his contributors
  24  *    may be used to endorse or promote products derived from this software
  25  *    without specific prior written permission.
  26  *
  27  * THIS SOFTWARE IS PROVIDED BY GUNNAR RITTER AND CONTRIBUTORS ``AS IS'' AND
  28  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30  * ARE DISCLAIMED.  IN NO EVENT SHALL GUNNAR RITTER OR CONTRIBUTORS BE LIABLE
  31  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  32  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  33  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  34  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  35  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  36  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  37  * SUCH DAMAGE.
  38  */
  39
  40 #include "rcv.h"
  41
  42 #include <time.h>
  43
  44 #include "extern.h"
  45
  46 /*
  47  * Open addressing is used for Message-IDs because the maximum number of
  48  * messages in the table is known in advance (== msgCount).
  49  */
  50 struct  mitem {
  51         struct message  *mi_data;
  52         char    *mi_id;
  53 };
  54
  55 struct msort {
  56         union {
  57 #ifdef HAVE_SPAM
  58                 ui_it   ms_ui;
  59 #endif
  60                 long    ms_long;
  61                 char *  ms_char;
  62         } ms_u;
  63         int     ms_n;
  64 };
  65
  66 static unsigned mhash(const char *cp, int mprime);
  67 static struct mitem *mlook(char *id, struct mitem *mt, struct message *mdata,
  68                 int mprime);
  69 static void adopt(struct message *parent, struct message *child, int dist);
  70 static struct message *interlink(struct message *m, long cnt, int nmail);
  71 static void finalize(struct message *mp);
  72 #ifdef HAVE_SPAM
  73 static int muilt(void const *a, void const *b);
  74 #endif
  75 static int mlonglt(const void *a, const void *b);
  76 static int mcharlt(const void *a, const void *b);
  77 static void lookup(struct message *m, struct mitem *mi, int mprime);
  78 static void makethreads(struct message *m, long cnt, int nmail);
  79 static char const *skipre(char const *cp);
  80 static int colpt(int *msgvec, int cl);
  81 static void colps(struct message *b, int cl);
  82 static void colpm(struct message *m, int cl, int *cc, int *uc);
  83
  84 /*
  85  * Return the hash value for a message id modulo mprime, or mprime
  86  * if the passed string does not look like a message-id.
  87  */
  88 static unsigned
  89 mhash(const char *cp, int mprime)
  90 {
  91
  92         unsigned        h = 0, g, at = 0;
  93
  94         cp--;
  95         while (*++cp) {
  96                 /*
  97                  * Pay attention not to hash characters which are
  98                  * irrelevant for Message-ID semantics.
  99                  */
 100                 if (*cp == '(') {
 101                         cp = skip_comment(&cp[1]) - 1;
 102                         continue;
 103                 }
 104                 if (*cp == '"' || *cp == '\\')
 105                         continue;
 106                 if (*cp == '@')
 107                         at++;
 108                 h = ((h << 4) & 0xffffffff) + lowerconv(*cp & 0377);
 109                 if ((g = h & 0xf0000000) != 0) {
 110                         h = h ^ (g >> 24);
 111                         h = h ^ g;
 112                 }
 113         }
 114         return at ? h % (unsigned int)mprime : (unsigned int)mprime;
 115 }
 116
 117 #define NOT_AN_ID       ((struct mitem *)-1)
 118
 119 /*
 120  * Look up a message id. Returns NOT_AN_ID if the passed string does
 121  * not look like a message-id.
 122  */
 123 static struct mitem *
 124 mlook(char *id, struct mitem *mt, struct message *mdata, int mprime)
 125 {
 126         struct mitem    *mp;
 127         unsigned        h, c, n = 0;
 128
 129         if (id == NULL && (id = hfield1("message-id", mdata)) == NULL)
 130                 return NULL;
 131         if (mdata && mdata->m_idhash)
 132                 h = ~mdata->m_idhash;
 133         else {
 134                 h = mhash(id, mprime);
 135                 if (h == (unsigned int)mprime)
 136                         return NOT_AN_ID;
 137         }
 138         mp = &mt[c = h];
 139         while (mp->mi_id != NULL) {
 140                 if (msgidcmp(mp->mi_id, id) == 0)
 141                         break;
 142                 c += n&1 ? -((n+1)/2) * ((n+1)/2) : ((n+1)/2) * ((n+1)/2);
 143                 n++;
 144                 while (c >= (unsigned int)mprime)
 145                         c -= mprime;
 146                 mp = &mt[c];
 147         }
 148         if (mdata != NULL && mp->mi_id == NULL) {
 149                 mp->mi_id = id;
 150                 mp->mi_data = mdata;
 151                 mdata->m_idhash = ~h;
 152         }
 153         return mp->mi_id ? mp : NULL;
 154 }
 155
 156 /*
 157  * Child is to be adopted by parent. A thread tree is structured
 158  * as follows:
 159  *
 160  *  ------       m_child       ------        m_child
 161  *  |    |-------------------->|    |------------------------> . . .
 162  *  |    |<--------------------|    |<-----------------------  . . .
 163  *  ------      m_parent       ------       m_parent
 164  *     ^^                       |  ^
 165  *     | \____        m_younger |  |
 166  *     |      \                 |  |
 167  *     |       ----             |  |
 168  *     |           \            |  | m_elder
 169  *     |   m_parent ----        |  |
 170  *     |                \       |  |
 171  *     |                 ----   |  |
 172  *     |                     \  +  |
 173  *     |                       ------        m_child
 174  *     |                       |    |------------------------> . . .
 175  *     |                       |    |<-----------------------  . . .
 176  *     |                       ------       m_parent
 177  *     |                        |  ^
 178  *      \-----        m_younger |  |
 179  *            \                 |  |
 180  *             ----             |  |
 181  *                 \            |  | m_elder
 182  *         m_parent ----        |  |
 183  *                      \       |  |
 184  *                       ----   |  |
 185  *                           \  +  |
 186  *                             ------        m_child
 187  *                             |    |------------------------> . . .
 188  *                             |    |<-----------------------  . . .
 189  *                             ------       m_parent
 190  *                              |  ^
 191  *                              . . .
 192  *
 193  * The base message of a thread does not have a m_parent link. Elements
 194  * connected by m_younger/m_elder links are replies to the same message,
 195  * which is connected to them by m_parent links. The first reply to a
 196  * message gets the m_child link.
 197  */
 198 static void
 199 adopt(struct message *parent, struct message *child, int dist)
 200 {
 201         struct message  *mp, *mq;
 202
 203         for (mp = parent; mp; mp = mp->m_parent)
 204                 if (mp == child)
 205                         return;
 206         child->m_level = dist;  /* temporarily store distance */
 207         child->m_parent = parent;
 208         if (parent->m_child != NULL) {
 209                 mq = NULL;
 210                 for (mp = parent->m_child; mp; mp = mp->m_younger) {
 211                         if (mp->m_date >= child->m_date) {
 212                                 if (mp->m_elder)
 213                                         mp->m_elder->m_younger = child;
 214                                 child->m_elder = mp->m_elder;
 215                                 mp->m_elder = child;
 216                                 child->m_younger = mp;
 217                                 if (mp == parent->m_child)
 218                                         parent->m_child = child;
 219                                 return;
 220                         }
 221                         mq = mp;
 222                 }
 223                 mq->m_younger = child;
 224                 child->m_elder = mq;
 225         } else
 226                 parent->m_child = child;
 227 }
 228
 229 /*
 230  * Connect all messages on the lowest thread level with m_younger/m_elder
 231  * links.
 232  */
 233 static struct message *
 234 interlink(struct message *m, long cnt, int nmail)
 235 {
 236         int     i;
 237         long    n;
 238         struct msort    *ms;
 239         struct message  *root;
 240         int     autocollapse = !nmail && !(inhook&2) &&
 241                         value("autocollapse") != NULL;
 242
 243         ms = smalloc(sizeof *ms * cnt);
 244         for (n = 0, i = 0; i < cnt; i++) {
 245                 if (m[i].m_parent == NULL) {
 246                         if (autocollapse)
 247                                 colps(&m[i], 1);
 248                         ms[n].ms_u.ms_long = m[i].m_date;
 249                         ms[n].ms_n = i;
 250                         n++;
 251                 }
 252         }
 253         if (n > 0) {
 254                 qsort(ms, n, sizeof *ms, mlonglt);
 255                 root = &m[ms[0].ms_n];
 256                 for (i = 1; i < n; i++) {
 257                         m[ms[i-1].ms_n].m_younger = &m[ms[i].ms_n];
 258                         m[ms[i].ms_n].m_elder = &m[ms[i-1].ms_n];
 259                 }
 260         } else
 261                 root = &m[0];
 262         free(ms);
 263         return root;
 264 }
 265
 266 static void
 267 finalize(struct message *mp)
 268 {
 269         long    n;
 270
 271         for (n = 0; mp; mp = next_in_thread(mp)) {
 272                 mp->m_threadpos = ++n;
 273                 mp->m_level = mp->m_parent ?
 274                         mp->m_level + mp->m_parent->m_level : 0;
 275         }
 276 }
 277
 278 #ifdef HAVE_SPAM
 279 static int
 280 muilt(void const *a, void const *b)
 281 {
 282         struct msort const *xa = a, *xb = b;
 283         int i;
 284
 285         i = (int)(xa->ms_u.ms_ui - xb->ms_u.ms_ui);
 286         if (i == 0)
 287                 i = xa->ms_n - xb->ms_n;
 288         return i;
 289 }
 290 #endif
 291
 292 static int
 293 mlonglt(const void *a, const void *b)
 294 {
 295         struct msort const *xa = a, *xb = b;
 296         int i;
 297
 298         i = (int)(xa->ms_u.ms_long - xb->ms_u.ms_long);
 299         if (i == 0)
 300                 i = xa->ms_n - xb->ms_n;
 301         return i;
 302 }
 303
 304 static int
 305 mcharlt(const void *a, const void *b)
 306 {
 307         struct msort const *xa = a, *xb = b;
 308         int i;
 309
 310         i = strcoll(xa->ms_u.ms_char, xb->ms_u.ms_char);
 311         if (i == 0)
 312                 i = xa->ms_n - xb->ms_n;
 313         return i;
 314 }
 315
 316 static void
 317 lookup(struct message *m, struct mitem *mi, int mprime)
 318 {
 319         struct name     *np;
 320         struct mitem    *ip;
 321         char    *cp;
 322         long    dist;
 323
 324         if (m->m_flag & MHIDDEN)
 325                 return;
 326         dist = 1;
 327         if ((cp = hfield1("in-reply-to", m)) != NULL) {
 328                 if ((np = extract(cp, GREF)) != NULL)
 329                         do {
 330                                 if ((ip = mlook(np->n_name, mi, NULL, mprime))
 331                                                 != NULL && ip != NOT_AN_ID) {
 332                                         adopt(ip->mi_data, m, 1);
 333                                         return;
 334                                 }
 335                         } while ((np = np->n_flink) != NULL);
 336         }
 337         if ((cp = hfield1("references", m)) != NULL) {
 338                 if ((np = extract(cp, GREF)) != NULL) {
 339                         while (np->n_flink != NULL)
 340                                 np = np->n_flink;
 341                         do {
 342                                 if ((ip = mlook(np->n_name, mi, NULL, mprime))
 343                                                 != NULL) {
 344                                         if (ip == NOT_AN_ID)
 345                                                 continue; /* skip dist++ */
 346                                         adopt(ip->mi_data, m, dist);
 347                                         return;
 348                                 }
 349                                 dist++;
 350                         } while ((np = np->n_blink) != NULL);
 351                 }
 352         }
 353 }
 354
 355 static void
 356 makethreads(struct message *m, long cnt, int nmail)
 357 {
 358         struct mitem    *mt;
 359         char    *cp;
 360         long    i, mprime;
 361
 362         if (cnt == 0)
 363                 return;
 364         mprime = nextprime(cnt);
 365         mt = scalloc(mprime, sizeof *mt);
 366         for (i = 0; i < cnt; i++) {
 367                 if ((m[i].m_flag&MHIDDEN) == 0) {
 368                         mlook(NULL, mt, &m[i], mprime);
 369                         if (m[i].m_date == 0) {
 370                                 if ((cp = hfield1("date", &m[i])) != NULL)
 371                                         m[i].m_date = rfctime(cp);
 372                         }
 373                 }
 374                 m[i].m_child = m[i].m_younger = m[i].m_elder =
 375                         m[i].m_parent = NULL;
 376                 m[i].m_level = 0;
 377                 if (!nmail && !(inhook&2))
 378                         m[i].m_collapsed = 0;
 379         }
 380         /*
 381          * Most folders contain the eldest messages first. Traversing
 382          * them in descending order makes it more likely that younger
 383          * brothers are found first, so elder ones can be prepended to
 384          * the brother list, which is faster. The worst case is still
 385          * in O(n^2) and occurs when all but one messages in a folder
 386          * are replies to the one message, and are sorted such that
 387          * youngest messages occur first.
 388          */
 389         for (i = cnt-1; i >= 0; i--)
 390                 lookup(&m[i], mt, mprime);
 391         threadroot = interlink(m, cnt, nmail);
 392         finalize(threadroot);
 393         free(mt);
 394         mb.mb_threaded = 1;
 395 }
 396
 397 int
 398 thread(void *vp)
 399 {
 400         if (mb.mb_threaded != 1 || vp == NULL || vp == (void *)-1) {
 401 #ifdef HAVE_IMAP
 402                 if (mb.mb_type == MB_IMAP)
 403                         imap_getheaders(1, msgCount);
 404 #endif
 405                 makethreads(message, msgCount, vp == (void *)-1);
 406                 if (mb.mb_sorted != NULL)
 407                         free(mb.mb_sorted);
 408                 mb.mb_sorted = sstrdup("thread");
 409         }
 410         if (vp && vp != (void *)-1 && !inhook && value("header"))
 411                 return headers(vp);
 412         return 0;
 413 }
 414
 415 int
 416 unthread(void *vp)
 417 {
 418         struct message  *m;
 419
 420         mb.mb_threaded = 0;
 421         free(mb.mb_sorted);
 422         mb.mb_sorted = NULL;
 423         for (m = &message[0]; m < &message[msgCount]; m++)
 424                 m->m_collapsed = 0;
 425         if (vp && !inhook && value("header"))
 426                 return headers(vp);
 427         return 0;
 428 }
 429
 430 struct message *
 431 next_in_thread(struct message *mp)
 432 {
 433         if (mp->m_child)
 434                 return mp->m_child;
 435         if (mp->m_younger)
 436                 return mp->m_younger;
 437         while (mp->m_parent) {
 438                 if (mp->m_parent->m_younger)
 439                         return mp->m_parent->m_younger;
 440                 mp = mp->m_parent;
 441         }
 442         return NULL;
 443 }
 444
 445 struct message *
 446 prev_in_thread(struct message *mp)
 447 {
 448         if (mp->m_elder) {
 449                 mp = mp->m_elder;
 450                 while (mp->m_child) {
 451                         mp = mp->m_child;
 452                         while (mp->m_younger)
 453                                 mp = mp->m_younger;
 454                 }
 455                 return mp;
 456         }
 457         return mp->m_parent;
 458 }
 459
 460 struct message *
 461 this_in_thread(struct message *mp, long n)
 462 {
 463         struct message  *mq;
 464
 465         if (n == -1) {  /* find end of thread */
 466                 while (mp) {
 467                         if (mp->m_younger) {
 468                                 mp = mp->m_younger;
 469                                 continue;
 470                         }
 471                         mq = next_in_thread(mp);
 472                         if (mq == NULL || mq->m_threadpos < mp->m_threadpos)
 473                                 return mp;
 474                         mp = mq;
 475                 }
 476                 return NULL;
 477         }
 478         while (mp && mp->m_threadpos < n) {
 479                 if (mp->m_younger && mp->m_younger->m_threadpos <= n) {
 480                         mp = mp->m_younger;
 481                         continue;
 482                 }
 483                 mp = next_in_thread(mp);
 484         }
 485         return mp && mp->m_threadpos == n ? mp : NULL;
 486 }
 487
 488 /*
 489  * Sorted mode is internally just a variant of threaded mode with all
 490  * m_parent and m_child links being NULL.
 491  */
 492 int
 493 sort(void *vp)
 494 {
 495         enum method {
 496                 SORT_SUBJECT,
 497                 SORT_DATE,
 498                 SORT_STATUS,
 499                 SORT_SIZE,
 500                 SORT_FROM,
 501                 SORT_TO,
 502 #ifdef HAVE_SPAM
 503                 SORT_SPAM,
 504 #endif
 505                 SORT_THREAD
 506         } method;
 507         struct {
 508                 const char      *me_name;
 509                 enum method     me_method;
 510                 int     (*me_func)(const void *, const void *);
 511         } methnames[] = {
 512                 { "date",       SORT_DATE,      mlonglt },
 513                 { "from",       SORT_FROM,      mcharlt },
 514                 { "to",         SORT_TO,        mcharlt },
 515                 { "subject",    SORT_SUBJECT,   mcharlt },
 516                 { "size",       SORT_SIZE,      mlonglt },
 517 #ifdef HAVE_SPAM
 518                 { "spam",       SORT_SPAM,      muilt },
 519 #endif
 520                 { "status",     SORT_STATUS,    mlonglt },
 521                 { "thread",     SORT_THREAD,    NULL },
 522                 { NULL,         -1,             NULL }
 523         };
 524         char    **args = (char **)vp, *cp, *_args[2];
 525         int     (*func)(const void *, const void *);
 526         struct msort    *ms;
 527         struct str      in, out;
 528         int     i, n, msgvec[2];
 529         int     showname = value("showname") != NULL;
 530         struct message  *mp;
 531
 532         msgvec[0] = dot - &message[0] + 1;
 533         msgvec[1] = 0;
 534         if (vp == NULL || vp == (void *)-1) {
 535                 _args[0] = savestr(mb.mb_sorted);
 536                 _args[1] = NULL;
 537                 args = _args;
 538         } else if (args[0] == NULL) {
 539                 printf("Current sorting criterion is: %s\n",
 540                                 mb.mb_sorted ? mb.mb_sorted : "unsorted");
 541                 return 0;
 542         }
 543         for (i = 0; methnames[i].me_name; i++)
 544                 if (*args[0] && is_prefix(args[0], methnames[i].me_name))
 545                         break;
 546         if (methnames[i].me_name == NULL) {
 547                 fprintf(stderr, "Unknown sorting method \"%s\"\n", args[0]);
 548                 return 1;
 549         }
 550         method = methnames[i].me_method;
 551         func = methnames[i].me_func;
 552         free(mb.mb_sorted);
 553         mb.mb_sorted = sstrdup(args[0]);
 554         if (method == SORT_THREAD)
 555                 return thread(vp && vp != (void *)-1 ? msgvec : vp);
 556         ms = ac_alloc(sizeof *ms * msgCount);
 557         switch (method) {
 558         case SORT_SUBJECT:
 559         case SORT_DATE:
 560         case SORT_FROM:
 561         case SORT_TO:
 562 #ifdef HAVE_IMAP
 563                 if (mb.mb_type == MB_IMAP)
 564                         imap_getheaders(1, msgCount);
 565 #endif
 566                 break;
 567         default:
 568                 break;
 569         }
 570         for (n = 0, i = 0; i < msgCount; i++) {
 571                 mp = &message[i];
 572                 if ((mp->m_flag&MHIDDEN) == 0) {
 573                         switch (method) {
 574                         case SORT_DATE:
 575                                 if (mp->m_date == 0 &&
 576                                                 (cp = hfield1("date", mp)) != 0)
 577                                         mp->m_date = rfctime(cp);
 578                                 ms[n].ms_u.ms_long = mp->m_date;
 579                                 break;
 580                         case SORT_STATUS:
 581                                 if (mp->m_flag & MDELETED)
 582                                         ms[n].ms_u.ms_long = 1;
 583                                 else if ((mp->m_flag&(MNEW|MREAD)) == MNEW)
 584                                         ms[n].ms_u.ms_long = 90;
 585                                 else if (mp->m_flag & MFLAGGED)
 586                                         ms[n].ms_u.ms_long = 85;
 587                                 else if ((mp->m_flag&(MNEW|MBOX)) == MBOX)
 588                                         ms[n].ms_u.ms_long = 70;
 589                                 else if (mp->m_flag & MNEW)
 590                                         ms[n].ms_u.ms_long = 80;
 591                                 else if (mp->m_flag & MREAD)
 592                                         ms[n].ms_u.ms_long = 40;
 593                                 else
 594                                         ms[n].ms_u.ms_long = 60;
 595                                 break;
 596                         case SORT_SIZE:
 597                                 ms[n].ms_u.ms_long = mp->m_xsize;
 598                                 break;
 599 #ifdef HAVE_SPAM
 600                         case SORT_SPAM:
 601                                 ms[n].ms_u.ms_ui = mp->m_spamscore;
 602                                 break;
 603 #endif
 604                         case SORT_FROM:
 605                         case SORT_TO:
 606                                 if ((cp = hfield1(method == SORT_FROM ?
 607                                                 "from" : "to", mp)) != NULL) {
 608                                         ms[n].ms_u.ms_char = showname ?
 609                                                 realname(cp) : skin(cp);
 610                                         makelow(ms[n].ms_u.ms_char);
 611                                 } else
 612                                         ms[n].ms_u.ms_char = UNCONST("");
 613                                 break;
 614                         default:
 615                         case SORT_SUBJECT:
 616                                 if ((cp = hfield1("subject", mp)) != NULL) {
 617                                         in.s = cp;
 618                                         in.l = strlen(in.s);
 619                                         mime_fromhdr(&in, &out, TD_ICONV);
 620                                         ms[n].ms_u.ms_char =
 621                                                 savestr(skipre(out.s));
 622                                         free(out.s);
 623                                         makelow(ms[n].ms_u.ms_char);
 624                                 } else
 625                                         ms[n].ms_u.ms_char = UNCONST("");
 626                                 break;
 627                         }
 628                         ms[n++].ms_n = i;
 629                 }
 630                 mp->m_child = mp->m_younger = mp->m_elder = mp->m_parent = NULL;
 631                 mp->m_level = 0;
 632                 mp->m_collapsed = 0;
 633         }
 634         if (n > 0) {
 635                 qsort(ms, n, sizeof *ms, func);
 636                 threadroot = &message[ms[0].ms_n];
 637                 for (i = 1; i < n; i++) {
 638                         message[ms[i-1].ms_n].m_younger = &message[ms[i].ms_n];
 639                         message[ms[i].ms_n].m_elder = &message[ms[i-1].ms_n];
 640                 }
 641         } else
 642                 threadroot = &message[0];
 643         finalize(threadroot);
 644         mb.mb_threaded = 2;
 645         ac_free(ms);
 646         return vp && vp != (void *)-1 && !inhook &&
 647                 value("header") ? headers(msgvec) : 0;
 648 }
 649
 650 static char const *
 651 skipre(char const *cp)
 652 {
 653         if (lowerconv(cp[0]) == 'r' && lowerconv(cp[1]) == 'e' &&
 654                         cp[2] == ':' && spacechar(cp[3])) {
 655                 cp = &cp[4];
 656                 while (spacechar(*cp))
 657                         cp++;
 658         }
 659         return cp;
 660 }
 661
 662 int
 663 ccollapse(void *v)
 664 {
 665         return colpt(v, 1);
 666 }
 667
 668 int
 669 cuncollapse(void *v)
 670 {
 671         return colpt(v, 0);
 672 }
 673
 674 static int
 675 colpt(int *msgvec, int cl)
 676 {
 677         int     *ip;
 678
 679         if (mb.mb_threaded != 1) {
 680                 puts("Not in threaded mode.");
 681                 return 1;
 682         }
 683         for (ip = msgvec; *ip != 0; ip++)
 684                 colps(&message[*ip-1], cl);
 685         return 0;
 686 }
 687
 688 static void
 689 colps(struct message *b, int cl)
 690 {
 691         struct message  *m;
 692         int     cc = 0, uc = 0;
 693
 694         if (cl && (b->m_collapsed > 0 || (b->m_flag & (MNEW|MREAD)) == MNEW))
 695                 return;
 696         if (b->m_child) {
 697                 m = b->m_child;
 698                 colpm(m, cl, &cc, &uc);
 699                 for (m = m->m_younger; m; m = m->m_younger)
 700                         colpm(m, cl, &cc, &uc);
 701         }
 702         if (cl) {
 703                 b->m_collapsed = -cc;
 704                 for (m = b->m_parent; m; m = m->m_parent)
 705                         if (m->m_collapsed <= -uc ) {
 706                                 m->m_collapsed += uc;
 707                                 break;
 708                         }
 709         } else {
 710                 if (b->m_collapsed > 0) {
 711                         b->m_collapsed = 0;
 712                         uc++;
 713                 }
 714                 for (m = b; m; m = m->m_parent)
 715                         if (m->m_collapsed <= -uc) {
 716                                 m->m_collapsed += uc;
 717                                 break;
 718                         }
 719         }
 720 }
 721
 722 static void
 723 colpm(struct message *m, int cl, int *cc, int *uc)
 724 {
 725         if (cl) {
 726                 if (m->m_collapsed > 0)
 727                         (*uc)++;
 728                 if ((m->m_flag & (MNEW|MREAD)) != MNEW || m->m_collapsed < 0)
 729                         m->m_collapsed = 1;
 730                 if (m->m_collapsed > 0)
 731                         (*cc)++;
 732         } else {
 733                 if (m->m_collapsed > 0) {
 734                         m->m_collapsed = 0;
 735                         (*uc)++;
 736                 }
 737         }
 738         if (m->m_child) {
 739                 m = m->m_child;
 740                 colpm(m, cl, cc, uc);
 741                 for (m = m->m_younger; m; m = m->m_younger)
 742                         colpm(m, cl, cc, uc);
 743         }
 744 }
 745
 746 void
 747 uncollapse1(struct message *m, int always)
 748 {
 749         if (mb.mb_threaded == 1 && (always || m->m_collapsed > 0))
 750                 colps(m, 0);
 751 }