thread.c

   1 /*
   2  * Heirloom mailx - a mail user agent derived from Berkeley Mail.
   3  *
   4  * Copyright (c) 2000-2004 Gunnar Ritter, Freiburg i. Br., Germany.
   5  * Copyright (c) 2012 Steffen "Daode" Nurpmeso.
   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 #ifndef lint
  41 #ifdef  DOSCCS
  42 static char sccsid[] = "@(#)thread.c    1.57 (gritter) 3/4/06";
  43 #endif
  44 #endif /* not lint */
  45
  46 #include "config.h"
  47
  48 #include "rcv.h"
  49 #include "extern.h"
  50 #include <time.h>
  51
  52 /*
  53  * Mail -- a mail program
  54  *
  55  * Message threading.
  56  */
  57
  58 /*
  59  * Open addressing is used for Message-IDs because the maximum number of
  60  * messages in the table is known in advance (== msgCount).
  61  */
  62 struct  mitem {
  63         struct message  *mi_data;
  64         char    *mi_id;
  65 };
  66
  67 struct msort {
  68         union {
  69                 long    ms_long;
  70                 char    *ms_char;
  71                 float   ms_float;
  72         } ms_u;
  73         int     ms_n;
  74 };
  75
  76 static unsigned mhash(const char *cp, int mprime);
  77 static struct mitem *mlook(char *id, struct mitem *mt, struct message *mdata,
  78                 int mprime);
  79 static void adopt(struct message *parent, struct message *child, int dist);
  80 static struct message *interlink(struct message *m, long count, int newmail);
  81 static void finalize(struct message *mp);
  82 static int mlonglt(const void *a, const void *b);
  83 static int mfloatlt(const void *a, const void *b);
  84 static int mcharlt(const void *a, const void *b);
  85 static void lookup(struct message *m, struct mitem *mi, int mprime);
  86 static void makethreads(struct message *m, long count, int newmail);
  87 static char *skipre(const char *cp);
  88 static int colpt(int *msgvec, int cl);
  89 static void colps(struct message *b, int cl);
  90 static void colpm(struct message *m, int cl, int *cc, int *uc);
  91
  92 /*
  93  * Return the hash value for a message id modulo mprime, or mprime
  94  * if the passed string does not look like a message-id.
  95  */
  96 static unsigned
  97 mhash(const char *cp, int mprime)
  98 {
  99
 100         unsigned        h = 0, g, at = 0;
 101
 102         cp--;
 103         while (*++cp) {
 104                 /*
 105                  * Pay attention not to hash characters which are
 106                  * irrelevant for Message-ID semantics.
 107                  */
 108                 if (*cp == '(') {
 109                         cp = skip_comment(&cp[1]) - 1;
 110                         continue;
 111                 }
 112                 if (*cp == '"' || *cp == '\\')
 113                         continue;
 114                 if (*cp == '@')
 115                         at++;
 116                 h = ((h << 4) & 0xffffffff) + lowerconv(*cp & 0377);
 117                 if ((g = h & 0xf0000000) != 0) {
 118                         h = h ^ (g >> 24);
 119                         h = h ^ g;
 120                 }
 121         }
 122         return at ? h % (unsigned int)mprime : (unsigned int)mprime;
 123 }
 124
 125 #define NOT_AN_ID       ((struct mitem *)-1)
 126
 127 /*
 128  * Look up a message id. Returns NOT_AN_ID if the passed string does
 129  * not look like a message-id.
 130  */
 131 static struct mitem *
 132 mlook(char *id, struct mitem *mt, struct message *mdata, int mprime)
 133 {
 134         struct mitem    *mp;
 135         unsigned        h, c, n = 0;
 136
 137         if (id == NULL && (id = hfield("message-id", mdata)) == NULL)
 138                 return NULL;
 139         if (mdata && mdata->m_idhash)
 140                 h = ~mdata->m_idhash;
 141         else {
 142                 h = mhash(id, mprime);
 143                 if (h == (unsigned int)mprime)
 144                         return NOT_AN_ID;
 145         }
 146         mp = &mt[c = h];
 147         while (mp->mi_id != NULL) {
 148                 if (msgidcmp(mp->mi_id, id) == 0)
 149                         break;
 150                 c += n&1 ? -((n+1)/2) * ((n+1)/2) : ((n+1)/2) * ((n+1)/2);
 151                 n++;
 152                 while (c >= (unsigned int)mprime)
 153                         c -= mprime;
 154                 mp = &mt[c];
 155         }
 156         if (mdata != NULL && mp->mi_id == NULL) {
 157                 mp->mi_id = id;
 158                 mp->mi_data = mdata;
 159                 mdata->m_idhash = ~h;
 160         }
 161         return mp->mi_id ? mp : NULL;
 162 }
 163
 164 /*
 165  * Child is to be adopted by parent. A thread tree is structured
 166  * as follows:
 167  *
 168  *  ------       m_child       ------        m_child
 169  *  |    |-------------------->|    |------------------------> . . .
 170  *  |    |<--------------------|    |<-----------------------  . . .
 171  *  ------      m_parent       ------       m_parent
 172  *     ^^                       |  ^
 173  *     | \____        m_younger |  |
 174  *     |      \                 |  |
 175  *     |       ----             |  |
 176  *     |           \            |  | m_elder
 177  *     |   m_parent ----        |  |
 178  *     |                \       |  |
 179  *     |                 ----   |  |
 180  *     |                     \  +  |
 181  *     |                       ------        m_child
 182  *     |                       |    |------------------------> . . .
 183  *     |                       |    |<-----------------------  . . .
 184  *     |                       ------       m_parent
 185  *     |                        |  ^
 186  *      \-----        m_younger |  |
 187  *            \                 |  |
 188  *             ----             |  |
 189  *                 \            |  | m_elder
 190  *         m_parent ----        |  |
 191  *                      \       |  |
 192  *                       ----   |  |
 193  *                           \  +  |
 194  *                             ------        m_child
 195  *                             |    |------------------------> . . .
 196  *                             |    |<-----------------------  . . .
 197  *                             ------       m_parent
 198  *                              |  ^
 199  *                              . . .
 200  *
 201  * The base message of a thread does not have a m_parent link. Elements
 202  * connected by m_younger/m_elder links are replies to the same message,
 203  * which is connected to them by m_parent links. The first reply to a
 204  * message gets the m_child link.
 205  */
 206 static void
 207 adopt(struct message *parent, struct message *child, int dist)
 208 {
 209         struct message  *mp, *mq;
 210
 211         for (mp = parent; mp; mp = mp->m_parent)
 212                 if (mp == child)
 213                         return;
 214         child->m_level = dist;  /* temporarily store distance */
 215         child->m_parent = parent;
 216         if (parent->m_child != NULL) {
 217                 mq = NULL;
 218                 for (mp = parent->m_child; mp; mp = mp->m_younger) {
 219                         if (mp->m_date >= child->m_date) {
 220                                 if (mp->m_elder)
 221                                         mp->m_elder->m_younger = child;
 222                                 child->m_elder = mp->m_elder;
 223                                 mp->m_elder = child;
 224                                 child->m_younger = mp;
 225                                 if (mp == parent->m_child)
 226                                         parent->m_child = child;
 227                                 return;
 228                         }
 229                         mq = mp;
 230                 }
 231                 mq->m_younger = child;
 232                 child->m_elder = mq;
 233         } else
 234                 parent->m_child = child;
 235 }
 236
 237 /*
 238  * Connect all messages on the lowest thread level with m_younger/m_elder
 239  * links.
 240  */
 241 static struct message *
 242 interlink(struct message *m, long count, int newmail)
 243 {
 244         int     i;
 245         long    n;
 246         struct msort    *ms;
 247         struct message  *root;
 248         int     autocollapse = !newmail && !(inhook&2) &&
 249                         value("autocollapse") != NULL;
 250
 251         ms = smalloc(sizeof *ms * count);
 252         for (n = 0, i = 0; i < count; i++) {
 253                 if (m[i].m_parent == NULL) {
 254                         if (autocollapse)
 255                                 colps(&m[i], 1);
 256                         ms[n].ms_u.ms_long = m[i].m_date;
 257                         ms[n].ms_n = i;
 258                         n++;
 259                 }
 260         }
 261         if (n > 0) {
 262                 qsort(ms, n, sizeof *ms, mlonglt);
 263                 root = &m[ms[0].ms_n];
 264                 for (i = 1; i < n; i++) {
 265                         m[ms[i-1].ms_n].m_younger = &m[ms[i].ms_n];
 266                         m[ms[i].ms_n].m_elder = &m[ms[i-1].ms_n];
 267                 }
 268         } else
 269                 root = &m[0];
 270         free(ms);
 271         return root;
 272 }
 273
 274 static void
 275 finalize(struct message *mp)
 276 {
 277         long    n;
 278
 279         for (n = 0; mp; mp = next_in_thread(mp)) {
 280                 mp->m_threadpos = ++n;
 281                 mp->m_level = mp->m_parent ?
 282                         mp->m_level + mp->m_parent->m_level : 0;
 283         }
 284 }
 285
 286 static int
 287 mlonglt(const void *a, const void *b)
 288 {
 289         int     i;
 290
 291         i = ((struct msort *)a)->ms_u.ms_long -
 292                 ((struct msort *)b)->ms_u.ms_long;
 293         if (i == 0)
 294                 i = ((struct msort *)a)->ms_n - ((struct msort *)b)->ms_n;
 295         return i;
 296 }
 297
 298 static int
 299 mfloatlt(const void *a, const void *b)
 300 {
 301         float   i;
 302
 303         i = ((struct msort *)a)->ms_u.ms_float -
 304                 ((struct msort *)b)->ms_u.ms_float;
 305         if (i == 0)
 306                 i = ((struct msort *)a)->ms_n - ((struct msort *)b)->ms_n;
 307         return i > 0 ? 1 : i < 0 ? -1 : 0;
 308 }
 309
 310 static int
 311 mcharlt(const void *a, const void *b)
 312 {
 313         int     i;
 314
 315         i = strcoll(((struct msort *)a)->ms_u.ms_char,
 316                         ((struct msort *)b)->ms_u.ms_char);
 317         if (i == 0)
 318                 i = ((struct msort *)a)->ms_n - ((struct msort *)b)->ms_n;
 319         return i;
 320 }
 321
 322
 323 static void
 324 lookup(struct message *m, struct mitem *mi, int mprime)
 325 {
 326         struct name     *np;
 327         struct mitem    *ip;
 328         char    *cp;
 329         long    dist;
 330
 331         if (m->m_flag & MHIDDEN)
 332                 return;
 333         dist = 1;
 334         if ((cp = hfield("in-reply-to", m)) != NULL) {
 335                 if ((np = extract(cp, GREF)) != NULL)
 336                         do {
 337                                 if ((ip = mlook(np->n_name, mi, NULL, mprime))
 338                                                 != NULL && ip != NOT_AN_ID) {
 339                                         adopt(ip->mi_data, m, 1);
 340                                         return;
 341                                 }
 342                         } while ((np = np->n_flink) != NULL);
 343         }
 344         if ((cp = hfield("references", m)) != NULL) {
 345                 if ((np = extract(cp, GREF)) != NULL) {
 346                         while (np->n_flink != NULL)
 347                                 np = np->n_flink;
 348                         do {
 349                                 if ((ip = mlook(np->n_name, mi, NULL, mprime))
 350                                                 != NULL) {
 351                                         if (ip == NOT_AN_ID)
 352                                                 continue; /* skip dist++ */
 353                                         adopt(ip->mi_data, m, dist);
 354                                         return;
 355                                 }
 356                                 dist++;
 357                         } while ((np = np->n_blink) != NULL);
 358                 }
 359         }
 360 }
 361
 362 static void
 363 makethreads(struct message *m, long count, int newmail)
 364 {
 365         struct mitem    *mt;
 366         char    *cp;
 367         long    i, mprime;
 368
 369         if (count == 0)
 370                 return;
 371         mprime = nextprime(count);
 372         mt = scalloc(mprime, sizeof *mt);
 373         for (i = 0; i < count; i++) {
 374                 if ((m[i].m_flag&MHIDDEN) == 0) {
 375                         mlook(NULL, mt, &m[i], mprime);
 376                         if (m[i].m_date == 0) {
 377                                 if ((cp = hfield("date", &m[i])) != NULL)
 378                                         m[i].m_date = rfctime(cp);
 379                         }
 380                 }
 381                 m[i].m_child = m[i].m_younger = m[i].m_elder =
 382                         m[i].m_parent = NULL;
 383                 m[i].m_level = 0;
 384                 if (!newmail && !(inhook&2))
 385                         m[i].m_collapsed = 0;
 386         }
 387         /*
 388          * Most folders contain the eldest messages first. Traversing
 389          * them in descending order makes it more likely that younger
 390          * brothers are found first, so elder ones can be prepended to
 391          * the brother list, which is faster. The worst case is still
 392          * in O(n^2) and occurs when all but one messages in a folder
 393          * are replies to the one message, and are sorted such that
 394          * youngest messages occur first.
 395          */
 396         for (i = count-1; i >= 0; i--)
 397                 lookup(&m[i], mt, mprime);
 398         threadroot = interlink(m, count, newmail);
 399         finalize(threadroot);
 400         free(mt);
 401         mb.mb_threaded = 1;
 402 }
 403
 404 int
 405 thread(void *vp)
 406 {
 407         if (mb.mb_threaded != 1 || vp == NULL || vp == (void *)-1) {
 408                 if (mb.mb_type == MB_IMAP)
 409                         imap_getheaders(1, msgCount);
 410                 makethreads(message, msgCount, vp == (void *)-1);
 411                 free(mb.mb_sorted);
 412                 mb.mb_sorted = sstrdup("thread");
 413         }
 414         if (vp && vp != (void *)-1 && !inhook && value("header"))
 415                 return headers(vp);
 416         return 0;
 417 }
 418
 419 int
 420 unthread(void *vp)
 421 {
 422         struct message  *m;
 423
 424         mb.mb_threaded = 0;
 425         free(mb.mb_sorted);
 426         mb.mb_sorted = NULL;
 427         for (m = &message[0]; m < &message[msgCount]; m++)
 428                 m->m_collapsed = 0;
 429         if (vp && !inhook && value("header"))
 430                 return headers(vp);
 431         return 0;
 432 }
 433
 434 struct message *
 435 next_in_thread(struct message *mp)
 436 {
 437         if (mp->m_child)
 438                 return mp->m_child;
 439         if (mp->m_younger)
 440                 return mp->m_younger;
 441         while (mp->m_parent) {
 442                 if (mp->m_parent->m_younger)
 443                         return mp->m_parent->m_younger;
 444                 mp = mp->m_parent;
 445         }
 446         return NULL;
 447 }
 448
 449 struct message *
 450 prev_in_thread(struct message *mp)
 451 {
 452         if (mp->m_elder) {
 453                 mp = mp->m_elder;
 454                 while (mp->m_child) {
 455                         mp = mp->m_child;
 456                         while (mp->m_younger)
 457                                 mp = mp->m_younger;
 458                 }
 459                 return mp;
 460         }
 461         return mp->m_parent;
 462 }
 463
 464 struct message *
 465 this_in_thread(struct message *mp, long n)
 466 {
 467         struct message  *mq;
 468
 469         if (n == -1) {  /* find end of thread */
 470                 while (mp) {
 471                         if (mp->m_younger) {
 472                                 mp = mp->m_younger;
 473                                 continue;
 474                         }
 475                         mq = next_in_thread(mp);
 476                         if (mq == NULL || mq->m_threadpos < mp->m_threadpos)
 477                                 return mp;
 478                         mp = mq;
 479                 }
 480                 return NULL;
 481         }
 482         while (mp && mp->m_threadpos < n) {
 483                 if (mp->m_younger && mp->m_younger->m_threadpos <= n) {
 484                         mp = mp->m_younger;
 485                         continue;
 486                 }
 487                 mp = next_in_thread(mp);
 488         }
 489         return mp && mp->m_threadpos == n ? mp : NULL;
 490 }
 491
 492 /*
 493  * Sorted mode is internally just a variant of threaded mode with all
 494  * m_parent and m_child links being NULL.
 495  */
 496 int
 497 sort(void *vp)
 498 {
 499         enum method {
 500                 SORT_SUBJECT,
 501                 SORT_DATE,
 502                 SORT_STATUS,
 503                 SORT_SIZE,
 504                 SORT_FROM,
 505                 SORT_TO,
 506                 SORT_SCORE,
 507                 SORT_THREAD
 508         } method;
 509         struct {
 510                 const char      *me_name;
 511                 enum method     me_method;
 512                 int     (*me_func)(const void *, const void *);
 513         } methnames[] = {
 514                 { "date",       SORT_DATE,      mlonglt },
 515                 { "from",       SORT_FROM,      mcharlt },
 516                 { "to",         SORT_TO,        mcharlt },
 517                 { "subject",    SORT_SUBJECT,   mcharlt },
 518                 { "size",       SORT_SIZE,      mlonglt },
 519                 { "status",     SORT_STATUS,    mlonglt },
 520                 { "score",      SORT_SCORE,     mfloatlt },
 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                 if (mb.mb_type == MB_IMAP)
 563                         imap_getheaders(1, msgCount);
 564                 break;
 565         default:
 566                 break;
 567         }
 568         for (n = 0, i = 0; i < msgCount; i++) {
 569                 mp = &message[i];
 570                 if ((mp->m_flag&MHIDDEN) == 0) {
 571                         switch (method) {
 572                         case SORT_DATE:
 573                                 if (mp->m_date == 0 &&
 574                                                 (cp = hfield("date", mp)) != 0)
 575                                         mp->m_date = rfctime(cp);
 576                                 ms[n].ms_u.ms_long = mp->m_date;
 577                                 break;
 578                         case SORT_STATUS:
 579                                 if (mp->m_flag & MDELETED)
 580                                         ms[n].ms_u.ms_long = 1;
 581                                 else if ((mp->m_flag&(MNEW|MREAD)) == MNEW)
 582                                         ms[n].ms_u.ms_long = 90;
 583                                 else if (mp->m_flag & MFLAGGED)
 584                                         ms[n].ms_u.ms_long = 85;
 585                                 else if ((mp->m_flag&(MNEW|MBOX)) == MBOX)
 586                                         ms[n].ms_u.ms_long = 70;
 587                                 else if (mp->m_flag & MNEW)
 588                                         ms[n].ms_u.ms_long = 80;
 589                                 else if (mp->m_flag & MREAD)
 590                                         ms[n].ms_u.ms_long = 40;
 591                                 else
 592                                         ms[n].ms_u.ms_long = 60;
 593                                 break;
 594                         case SORT_SIZE:
 595                                 ms[n].ms_u.ms_long = mp->m_xsize;
 596                                 break;
 597                         case SORT_SCORE:
 598                                 ms[n].ms_u.ms_float = mp->m_score;
 599                                 break;
 600                         case SORT_FROM:
 601                         case SORT_TO:
 602                                 if ((cp = hfield(method == SORT_FROM ?
 603                                                 "from" : "to", mp)) != NULL) {
 604                                         ms[n].ms_u.ms_char = showname ?
 605                                                 realname(cp) : skin(cp);
 606                                         makelow(ms[n].ms_u.ms_char);
 607                                 } else
 608                                         ms[n].ms_u.ms_char = "";
 609                                 break;
 610                         default:
 611                         case SORT_SUBJECT:
 612                                 if ((cp = hfield("subject", mp)) != NULL) {
 613                                         in.s = cp;
 614                                         in.l = strlen(in.s);
 615                                         mime_fromhdr(&in, &out, TD_ICONV);
 616                                         ms[n].ms_u.ms_char =
 617                                                 savestr(skipre(out.s));
 618                                         free(out.s);
 619                                         makelow(ms[n].ms_u.ms_char);
 620                                 } else
 621                                         ms[n].ms_u.ms_char = "";
 622                                 break;
 623                         }
 624                         ms[n++].ms_n = i;
 625                 }
 626                 mp->m_child = mp->m_younger = mp->m_elder = mp->m_parent = NULL;
 627                 mp->m_level = 0;
 628                 mp->m_collapsed = 0;
 629         }
 630         if (n > 0) {
 631                 qsort(ms, n, sizeof *ms, func);
 632                 threadroot = &message[ms[0].ms_n];
 633                 for (i = 1; i < n; i++) {
 634                         message[ms[i-1].ms_n].m_younger = &message[ms[i].ms_n];
 635                         message[ms[i].ms_n].m_elder = &message[ms[i-1].ms_n];
 636                 }
 637         } else
 638                 threadroot = &message[0];
 639         finalize(threadroot);
 640         mb.mb_threaded = 2;
 641         ac_free(ms);
 642         return vp && vp != (void *)-1 && !inhook &&
 643                 value("header") ? headers(msgvec) : 0;
 644 }
 645
 646 static char *
 647 skipre(const char *cp)
 648 {
 649         if (lowerconv(cp[0]&0377) == 'r' &&
 650                         lowerconv(cp[1]&0377) == 'e' &&
 651                         cp[2] == ':' &&
 652                         spacechar(cp[3]&0377)) {
 653                 cp = &cp[4];
 654                 while (spacechar(*cp&0377))
 655                         cp++;
 656         }
 657         return (char *)cp;
 658 }
 659
 660 int
 661 ccollapse(void *v)
 662 {
 663         return colpt(v, 1);
 664 }
 665
 666 int
 667 cuncollapse(void *v)
 668 {
 669         return colpt(v, 0);
 670 }
 671
 672 static int
 673 colpt(int *msgvec, int cl)
 674 {
 675         int     *ip;
 676
 677         if (mb.mb_threaded != 1) {
 678                 puts("Not in threaded mode.");
 679                 return 1;
 680         }
 681         for (ip = msgvec; *ip != 0; ip++)
 682                 colps(&message[*ip-1], cl);
 683         return 0;
 684 }
 685
 686 static void
 687 colps(struct message *b, int cl)
 688 {
 689         struct message  *m;
 690         int     cc = 0, uc = 0;
 691
 692         if (cl && (b->m_collapsed > 0 || (b->m_flag & (MNEW|MREAD)) == MNEW))
 693                 return;
 694         if (b->m_child) {
 695                 m = b->m_child;
 696                 colpm(m, cl, &cc, &uc);
 697                 for (m = m->m_younger; m; m = m->m_younger)
 698                         colpm(m, cl, &cc, &uc);
 699         }
 700         if (cl) {
 701                 b->m_collapsed = -cc;
 702                 for (m = b->m_parent; m; m = m->m_parent)
 703                         if (m->m_collapsed <= -uc ) {
 704                                 m->m_collapsed += uc;
 705                                 break;
 706                         }
 707         } else {
 708                 if (b->m_collapsed > 0) {
 709                         b->m_collapsed = 0;
 710                         uc++;
 711                 }
 712                 for (m = b; m; m = m->m_parent)
 713                         if (m->m_collapsed <= -uc) {
 714                                 m->m_collapsed += uc;
 715                                 break;
 716                         }
 717         }
 718 }
 719
 720 static void
 721 colpm(struct message *m, int cl, int *cc, int *uc)
 722 {
 723         if (cl) {
 724                 if (m->m_collapsed > 0)
 725                         (*uc)++;
 726                 if ((m->m_flag & (MNEW|MREAD)) != MNEW || m->m_collapsed < 0)
 727                         m->m_collapsed = 1;
 728                 if (m->m_collapsed > 0)
 729                         (*cc)++;
 730         } else {
 731                 if (m->m_collapsed > 0) {
 732                         m->m_collapsed = 0;
 733                         (*uc)++;
 734                 }
 735         }
 736         if (m->m_child) {
 737                 m = m->m_child;
 738                 colpm(m, cl, cc, uc);
 739                 for (m = m->m_younger; m; m = m->m_younger)
 740                         colpm(m, cl, cc, uc);
 741         }
 742 }
 743
 744 void
 745 uncollapse1(struct message *m, int always)
 746 {
 747         if (mb.mb_threaded == 1 && (always || m->m_collapsed > 0))
 748                 colps(m, 0);
 749 }