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 - 2018 Steffen (Daode) Nurpmeso <steffen@sdaoden.eu>.
   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 #undef n_FILE
  40 #define n_FILE thread
  41
  42 #ifndef HAVE_AMALGAMATION
  43 # include "nail.h"
  44 #endif
  45
  46 /* Open addressing is used for Message-IDs because the maximum number of
  47  * messages in the table is known in advance (== msgCount) */
  48 struct mitem {
  49    struct message *mi_data;
  50    char           *mi_id;
  51 };
  52 #define NOT_AN_ID ((struct mitem*)-1)
  53
  54 struct msort {
  55    union {
  56 #ifdef HAVE_SPAM
  57       ui32_t   ms_ui;
  58 #endif
  59       long     ms_long;
  60       char     *ms_char;
  61    }           ms_u;
  62    int         ms_n;
  63 };
  64
  65 /* Return the hash value for a message id modulo mprime, or mprime if the
  66  * passed string does not look like a message-id */
  67 static ui32_t           _mhash(char const *cp, ui32_t mprime);
  68
  69 /* Look up a message id. Returns NOT_AN_ID if the passed string does not look
  70  * like a message-id */
  71 static struct mitem *   _mlook(char *id, struct mitem *mt,
  72                            struct message *mdata, ui32_t mprime);
  73
  74 /* Child is to be adopted by parent.  A thread tree is structured as follows:
  75  *
  76  *  ------       m_child       ------        m_child
  77  *  |    |-------------------->|    |------------------------> . . .
  78  *  |    |<--------------------|    |<-----------------------  . . .
  79  *  ------      m_parent       ------       m_parent
  80  *     ^^                       |  ^
  81  *     | \____        m_younger |  |
  82  *     |      \                 |  |
  83  *     |       ----             |  |
  84  *     |           \            |  | m_elder
  85  *     |   m_parent ----        |  |
  86  *                      \       |  |
  87  *                       ----   |  |
  88  *                           \  +  |
  89  *                             ------        m_child
  90  *                             |    |------------------------> . . .
  91  *                             |    |<-----------------------  . . .
  92  *                             ------       m_parent
  93  *                              |  ^
  94  *                              . . .
  95  *
  96  * The base message of a thread does not have a m_parent link.  Elements
  97  * connected by m_younger/m_elder links are replies to the same message, which
  98  * is connected to them by m_parent links.  The first reply to a message gets
  99  * the m_child link */
 100 static void             _adopt(struct message *parent, struct message *child,
 101                            int dist);
 102
 103 /* Connect all msgs on the lowest thread level with m_younger/m_elder links */
 104 static struct message * _interlink(struct message *m, ui32_t cnt, int nmail);
 105
 106 static void             _finalize(struct message *mp);
 107
 108 /* Several sort comparison PTFs */
 109 #ifdef HAVE_SPAM
 110 static int              _mui32lt(void const *a, void const *b);
 111 #endif
 112 static int              _mlonglt(void const *a, void const *b);
 113 static int              _mcharlt(void const *a, void const *b);
 114
 115 static void             _lookup(struct message *m, struct mitem *mi,
 116                            ui32_t mprime);
 117 static void             _makethreads(struct message *m, ui32_t cnt, int nmail);
 118 static int              _colpt(int *msgvec, int cl);
 119 static void             _colps(struct message *b, int cl);
 120 static void             _colpm(struct message *m, int cl, int *cc, int *uc);
 121
 122 static ui32_t
 123 _mhash(char const *cp, ui32_t mprime)
 124 {
 125    ui32_t h = 0, g, at = 0;
 126    NYD2_ENTER;
 127
 128    for (--cp; *++cp != '\0';) {
 129       /* Pay attention not to hash characters which are irrelevant for
 130        * Message-ID semantics */
 131       if (*cp == '(') {
 132          cp = skip_comment(cp + 1) - 1;
 133          continue;
 134       }
 135       if (*cp == '"' || *cp == '\\')
 136          continue;
 137       if (*cp == '@')
 138          ++at;
 139       /* TODO torek hash */
 140       h = ((h << 4) & 0xffffffff) + lowerconv(*cp);
 141       if ((g = h & 0xf0000000) != 0) {
 142          h = h ^ (g >> 24);
 143          h = h ^ g;
 144       }
 145    }
 146    NYD2_LEAVE;
 147    return (at ? h % mprime : mprime);
 148 }
 149
 150 static struct mitem *
 151 _mlook(char *id, struct mitem *mt, struct message *mdata, ui32_t mprime)
 152 {
 153    struct mitem *mp = NULL;
 154    ui32_t h, c, n = 0;
 155    NYD2_ENTER;
 156
 157    if (id == NULL) {
 158       if ((id = hfield1("message-id", mdata)) == NULL)
 159          goto jleave;
 160       /* Normalize, what hfield1() doesn't do (TODO should now GREF, too!!) */
 161       if (id[0] == '<') {
 162          id[strlen(id) -1] = '\0';
 163          if (*id != '\0')
 164             ++id;
 165       }
 166    }
 167
 168    if (mdata != NULL && mdata->m_idhash)
 169       h = ~mdata->m_idhash;
 170    else {
 171       h = _mhash(id, mprime);
 172       if (h == mprime) {
 173          mp = NOT_AN_ID;
 174          goto jleave;
 175       }
 176    }
 177
 178    mp = mt + (c = h);
 179    while (mp->mi_id != NULL) {
 180       if (!msgidcmp(mp->mi_id, id))
 181          break;
 182       c += (n & 1) ? -((n+1)/2) * ((n+1)/2) : ((n+1)/2) * ((n+1)/2);
 183       ++n;
 184       if ((si32_t)c < 0)
 185          c = 0;
 186       else while (c >= mprime)
 187          c -= mprime;
 188       mp = mt + c;
 189    }
 190
 191    if (mdata != NULL && mp->mi_id == NULL) {
 192       mp->mi_id = sstrdup(id);
 193       mp->mi_data = mdata;
 194       mdata->m_idhash = ~h;
 195    }
 196    if (mp->mi_id == NULL)
 197       mp = NULL;
 198 jleave:
 199    NYD2_LEAVE;
 200    return mp;
 201 }
 202
 203 static void
 204 _adopt(struct message *parent, struct message *child, int dist)
 205 {
 206    struct message *mp, *mq;
 207    NYD2_ENTER;
 208
 209    for (mp = parent; mp != NULL; mp = mp->m_parent)
 210       if (mp == child)
 211          goto jleave;
 212
 213    child->m_level = dist; /* temporarily store distance */
 214    child->m_parent = parent;
 215
 216    if (parent->m_child != NULL) {
 217       mq = NULL;
 218       for (mp = parent->m_child; mp != NULL; mp = mp->m_younger) {
 219          if (mp->m_date >= child->m_date) {
 220             if (mp->m_elder != NULL)
 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             goto jleave;
 228          }
 229          mq = mp;
 230       }
 231       mq->m_younger = child;
 232       child->m_elder = mq;
 233    } else
 234       parent->m_child = child;
 235 jleave:
 236    NYD2_LEAVE;
 237 }
 238
 239 static struct message *
 240 _interlink(struct message *m, ui32_t cnt, int nmail)
 241 {
 242    struct message *root;
 243    ui32_t n;
 244    struct msort *ms;
 245    int i, autocollapse;
 246    NYD2_ENTER;
 247
 248    autocollapse = (!nmail && !(n_pstate & n_PS_HOOK_NEWMAIL) &&
 249          ok_blook(autocollapse));
 250    ms = smalloc(sizeof *ms * cnt);
 251
 252    for (n = 0, i = 0; UICMP(32, i, <, cnt); ++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
 262    if (n > 0) {
 263       qsort(ms, n, sizeof *ms, &_mlonglt);
 264       root = m + ms[0].ms_n;
 265       for (i = 1; UICMP(32, i, <, n); ++i) {
 266          m[ms[i-1].ms_n].m_younger = m + ms[i].ms_n;
 267          m[ms[i].ms_n].m_elder = m + ms[i - 1].ms_n;
 268       }
 269    } else
 270       root = NULL;
 271
 272    free(ms);
 273    NYD2_LEAVE;
 274    return root;
 275 }
 276
 277 static void
 278 _finalize(struct message *mp)
 279 {
 280    long n;
 281    NYD2_ENTER;
 282
 283    for (n = 0; mp; mp = next_in_thread(mp)) {
 284       mp->m_threadpos = ++n;
 285       mp->m_level = mp->m_parent ? mp->m_level + mp->m_parent->m_level : 0;
 286    }
 287    NYD2_LEAVE;
 288 }
 289
 290 #ifdef HAVE_SPAM
 291 static int
 292 _mui32lt(void const *a, void const *b)
 293 {
 294    struct msort const *xa = a, *xb = b;
 295    int i;
 296    NYD2_ENTER;
 297
 298    i = (int)(xa->ms_u.ms_ui - xb->ms_u.ms_ui);
 299    if (i == 0)
 300       i = xa->ms_n - xb->ms_n;
 301    NYD2_LEAVE;
 302    return i;
 303 }
 304 #endif
 305
 306 static int
 307 _mlonglt(void const *a, void const *b)
 308 {
 309    struct msort const *xa = a, *xb = b;
 310    int i;
 311    NYD2_ENTER;
 312
 313    i = (int)(xa->ms_u.ms_long - xb->ms_u.ms_long);
 314    if (i == 0)
 315       i = xa->ms_n - xb->ms_n;
 316    NYD2_LEAVE;
 317    return i;
 318 }
 319
 320 static int
 321 _mcharlt(void const *a, void const *b)
 322 {
 323    struct msort const *xa = a, *xb = b;
 324    int i;
 325    NYD2_ENTER;
 326
 327    i = strcoll(xa->ms_u.ms_char, xb->ms_u.ms_char);
 328    if (i == 0)
 329       i = xa->ms_n - xb->ms_n;
 330    NYD2_LEAVE;
 331    return i;
 332 }
 333
 334 static void
 335 _lookup(struct message *m, struct mitem *mi, ui32_t mprime)
 336 {
 337    struct name *np;
 338    struct mitem *ip;
 339    char *cp;
 340    long dist;
 341    NYD2_ENTER;
 342
 343    if (m->m_flag & MHIDDEN)
 344       goto jleave;
 345
 346    dist = 1;
 347    if ((cp = hfield1("in-reply-to", m)) != NULL) {
 348       if ((np = extract(cp, GREF)) != NULL)
 349          do {
 350             if ((ip = _mlook(np->n_name, mi, NULL, mprime)) != NULL &&
 351                   ip != NOT_AN_ID) {
 352                _adopt(ip->mi_data, m, 1);
 353                goto jleave;
 354             }
 355          } while ((np = np->n_flink) != NULL);
 356    }
 357
 358    if ((cp = hfield1("references", m)) != NULL) {
 359       if ((np = extract(cp, GREF)) != NULL) {
 360          while (np->n_flink != NULL)
 361             np = np->n_flink;
 362          do {
 363             if ((ip = _mlook(np->n_name, mi, NULL, mprime)) != NULL) {
 364                if (ip == NOT_AN_ID)
 365                   continue; /* skip dist++ */
 366                _adopt(ip->mi_data, m, dist);
 367                goto jleave;
 368             }
 369             ++dist;
 370          } while ((np = np->n_blink) != NULL);
 371       }
 372    }
 373 jleave:
 374    NYD2_LEAVE;
 375 }
 376
 377 static void
 378 _makethreads(struct message *m, ui32_t cnt, int nmail)
 379 {
 380    struct mitem *mt;
 381    char *cp;
 382    ui32_t i, mprime;
 383    NYD2_ENTER;
 384
 385    if (cnt == 0)
 386       goto jleave;
 387
 388    /* It is performance crucial to space this large enough in order to minimize
 389     * bucket sharing */
 390    mprime = n_prime_next((cnt < UI32_MAX >> 3) ? cnt << 2 : cnt);
 391    mt = scalloc(mprime, sizeof *mt);
 392
 393    srelax_hold();
 394
 395    for (i = 0; i < cnt; ++i) {
 396       if (!(m[i].m_flag & MHIDDEN)) {
 397          _mlook(NULL, mt, m + i, mprime);
 398          if (m[i].m_date == 0) {
 399             if ((cp = hfield1("date", m + i)) != NULL)
 400                m[i].m_date = rfctime(cp);
 401          }
 402       }
 403       m[i].m_child = m[i].m_younger = m[i].m_elder = m[i].m_parent = NULL;
 404       m[i].m_level = 0;
 405       if (!nmail && !(n_pstate & n_PS_HOOK_NEWMAIL))
 406          m[i].m_collapsed = 0;
 407       srelax();
 408    }
 409
 410    /* Most folders contain the eldest messages first.  Traversing them in
 411     * descending order makes it more likely that younger brothers are found
 412     * first, so elder ones can be prepended to the brother list, which is
 413     * faster.  The worst case is still in O(n^2) and occurs when all but one
 414     * messages in a folder are replies to the one message, and are sorted such
 415     * that youngest messages occur first */
 416    for (i = cnt; i > 0; --i) {
 417       _lookup(m + i - 1, mt, mprime);
 418       srelax();
 419    }
 420
 421    srelax_rele();
 422
 423    threadroot = _interlink(m, cnt, nmail);
 424    _finalize(threadroot);
 425
 426    for (i = 0; i < mprime; ++i)
 427       if (mt[i].mi_id != NULL)
 428          free(mt[i].mi_id);
 429
 430    free(mt);
 431    mb.mb_threaded = 1;
 432 jleave:
 433    NYD2_LEAVE;
 434 }
 435
 436 static int
 437 _colpt(int *msgvec, int cl)
 438 {
 439    int *ip, rv;
 440    NYD2_ENTER;
 441
 442    if (mb.mb_threaded != 1) {
 443       fputs("Not in threaded mode.\n", n_stdout);
 444       rv = 1;
 445    } else {
 446       for (ip = msgvec; *ip != 0; ++ip)
 447          _colps(message + *ip - 1, cl);
 448       rv = 0;
 449    }
 450    NYD2_LEAVE;
 451    return rv;
 452 }
 453
 454 static void
 455 _colps(struct message *b, int cl)
 456 {
 457    struct message *m;
 458    int cc = 0, uc = 0;
 459    NYD2_ENTER;
 460
 461    if (cl && (b->m_collapsed > 0 || (b->m_flag & (MNEW | MREAD)) == MNEW))
 462       goto jleave;
 463
 464    if (b->m_child != NULL) {
 465       m = b->m_child;
 466       _colpm(m, cl, &cc, &uc);
 467       for (m = m->m_younger; m != NULL; m = m->m_younger)
 468          _colpm(m, cl, &cc, &uc);
 469    }
 470
 471    if (cl) {
 472       b->m_collapsed = -cc;
 473       for (m = b->m_parent; m != NULL; m = m->m_parent)
 474          if (m->m_collapsed <= -uc) {
 475             m->m_collapsed += uc;
 476             break;
 477          }
 478    } else {
 479       if (b->m_collapsed > 0) {
 480          b->m_collapsed = 0;
 481          ++uc;
 482       }
 483       for (m = b; m != NULL; m = m->m_parent)
 484          if (m->m_collapsed <= -uc) {
 485             m->m_collapsed += uc;
 486             break;
 487          }
 488    }
 489 jleave:
 490    NYD2_LEAVE;
 491 }
 492
 493 static void
 494 _colpm(struct message *m, int cl, int *cc, int *uc)
 495 {
 496    NYD2_ENTER;
 497    if (cl) {
 498       if (m->m_collapsed > 0)
 499          ++(*uc);
 500       if ((m->m_flag & (MNEW | MREAD)) != MNEW || m->m_collapsed < 0)
 501          m->m_collapsed = 1;
 502       if (m->m_collapsed > 0)
 503          ++(*cc);
 504    } else {
 505       if (m->m_collapsed > 0) {
 506          m->m_collapsed = 0;
 507          ++(*uc);
 508       }
 509    }
 510
 511    if (m->m_child != NULL) {
 512       m = m->m_child;
 513       _colpm(m, cl, cc, uc);
 514       for (m = m->m_younger; m != NULL; m = m->m_younger)
 515          _colpm(m, cl, cc, uc);
 516    }
 517    NYD2_LEAVE;
 518 }
 519
 520 FL int
 521 c_thread(void *vp)
 522 {
 523    int rv;
 524    NYD_ENTER;
 525
 526    if (mb.mb_threaded != 1 || vp == NULL || vp == (void*)-1) {
 527 #ifdef HAVE_IMAP
 528       if (mb.mb_type == MB_IMAP)
 529          imap_getheaders(1, msgCount);
 530 #endif
 531       _makethreads(message, msgCount, (vp == (void*)-1));
 532       if (mb.mb_sorted != NULL)
 533          free(mb.mb_sorted);
 534       mb.mb_sorted = sstrdup("thread");
 535    }
 536
 537    if (vp != NULL && vp != (void*)-1 && !(n_pstate & n_PS_HOOK_MASK) &&
 538          ok_blook(header))
 539       rv = print_header_group(vp);
 540    else
 541       rv = 0;
 542    NYD_LEAVE;
 543    return rv;
 544 }
 545
 546 FL int
 547 c_unthread(void *vp)
 548 {
 549    struct message *m;
 550    int rv;
 551    NYD_ENTER;
 552
 553    mb.mb_threaded = 0;
 554    if (mb.mb_sorted != NULL)
 555       free(mb.mb_sorted);
 556    mb.mb_sorted = NULL;
 557
 558    for (m = message; PTRCMP(m, <, message + msgCount); ++m)
 559       m->m_collapsed = 0;
 560
 561    if (vp && !(n_pstate & n_PS_HOOK_MASK) && ok_blook(header))
 562       rv = print_header_group(vp);
 563    else
 564       rv = 0;
 565    NYD_LEAVE;
 566    return rv;
 567 }
 568
 569 FL struct message *
 570 next_in_thread(struct message *mp)
 571 {
 572    struct message *rv;
 573    NYD2_ENTER;
 574
 575    if ((rv = mp->m_child) != NULL)
 576       goto jleave;
 577    if ((rv = mp->m_younger) != NULL)
 578       goto jleave;
 579
 580    while ((rv = mp->m_parent) != NULL) {
 581       mp = rv;
 582       if ((rv = rv->m_younger) != NULL)
 583          goto jleave;
 584    }
 585 jleave:
 586    NYD2_LEAVE;
 587    return rv;
 588 }
 589
 590 FL struct message *
 591 prev_in_thread(struct message *mp)
 592 {
 593    struct message *rv;
 594    NYD2_ENTER;
 595
 596    if ((rv = mp->m_elder) != NULL) {
 597       for (mp = rv; (rv = mp->m_child) != NULL;) {
 598          mp = rv;
 599          while ((rv = mp->m_younger) != NULL)
 600             mp = rv;
 601       }
 602       rv = mp;
 603       goto jleave;
 604    }
 605    rv = mp->m_parent;
 606 jleave:
 607    NYD2_LEAVE;
 608    return rv;
 609 }
 610
 611 FL struct message *
 612 this_in_thread(struct message *mp, long n)
 613 {
 614    struct message *rv;
 615    NYD2_ENTER;
 616
 617    if (n == -1) { /* find end of thread */
 618       while (mp != NULL) {
 619          if ((rv = mp->m_younger) != NULL) {
 620             mp = rv;
 621             continue;
 622          }
 623          rv = next_in_thread(mp);
 624          if (rv == NULL || rv->m_threadpos < mp->m_threadpos) {
 625             rv = mp;
 626             goto jleave;
 627          }
 628          mp = rv;
 629       }
 630       rv = mp;
 631       goto jleave;
 632    }
 633
 634    while (mp != NULL && mp->m_threadpos < n) {
 635       if ((rv = mp->m_younger) != NULL && rv->m_threadpos <= n) {
 636          mp = rv;
 637          continue;
 638       }
 639       mp = next_in_thread(mp);
 640    }
 641    rv = (mp != NULL && mp->m_threadpos == n) ? mp : NULL;
 642 jleave:
 643    NYD2_LEAVE;
 644    return rv;
 645 }
 646
 647 FL int
 648 c_sort(void *vp)
 649 {
 650    enum method {SORT_SUBJECT, SORT_DATE, SORT_STATUS, SORT_SIZE, SORT_FROM,
 651       SORT_TO, SORT_SPAM, SORT_THREAD} method;
 652    struct {
 653       char const *me_name;
 654       enum method me_method;
 655       int         (*me_func)(void const *, void const *);
 656    } const methnames[] = {
 657       {"date", SORT_DATE, &_mlonglt},
 658       {"from", SORT_FROM, &_mcharlt},
 659       {"to", SORT_TO, &_mcharlt},
 660       {"subject", SORT_SUBJECT, &_mcharlt},
 661       {"size", SORT_SIZE, &_mlonglt},
 662 #ifdef HAVE_SPAM
 663       {"spam", SORT_SPAM, &_mui32lt},
 664 #endif
 665       {"status", SORT_STATUS, &_mlonglt},
 666       {"thread", SORT_THREAD, NULL}
 667    };
 668
 669    struct str in, out;
 670    char *_args[2], *cp, **args = vp;
 671    int msgvec[2], i, n;
 672    int (*func)(void const *, void const *);
 673    struct msort *ms;
 674    struct message *mp;
 675    bool_t showname;
 676    NYD_ENTER;
 677
 678    if (vp == NULL || vp == (void*)-1) {
 679       _args[0] = savestr((mb.mb_sorted != NULL) ? mb.mb_sorted : "unsorted");
 680       _args[1] = NULL;
 681       args = _args;
 682    } else if (args[0] == NULL) {
 683       fprintf(n_stdout, "Current sorting criterion is: %s\n",
 684             (mb.mb_sorted != NULL) ? mb.mb_sorted : "unsorted");
 685       i = 0;
 686       goto jleave;
 687    }
 688
 689    i = 0;
 690    for (;;) {
 691       if (*args[0] != '\0' && is_prefix(args[0], methnames[i].me_name))
 692          break;
 693       if (UICMP(z, ++i, >=, n_NELEM(methnames))) {
 694          n_err(_("Unknown sorting method: %s\n"), args[0]);
 695          i = 1;
 696          goto jleave;
 697       }
 698    }
 699
 700    if (mb.mb_sorted != NULL)
 701       free(mb.mb_sorted);
 702    mb.mb_sorted = sstrdup(args[0]);
 703
 704    method = methnames[i].me_method;
 705    func = methnames[i].me_func;
 706    msgvec[0] = (int)PTR2SIZE(dot - message + 1);
 707    msgvec[1] = 0;
 708
 709    if (method == SORT_THREAD) {
 710       i = c_thread((vp != NULL && vp != (void*)-1) ? msgvec : vp);
 711       goto jleave;
 712    }
 713
 714    showname = ok_blook(showname);
 715    ms = ac_alloc(sizeof *ms * msgCount);
 716 #ifdef HAVE_IMAP
 717    switch (method) {
 718    case SORT_SUBJECT:
 719    case SORT_DATE:
 720    case SORT_FROM:
 721    case SORT_TO:
 722       if (mb.mb_type == MB_IMAP)
 723          imap_getheaders(1, msgCount);
 724       break;
 725    default:
 726       break;
 727    }
 728 #endif
 729
 730    srelax_hold();
 731    for (n = 0, i = 0; i < msgCount; ++i) {
 732       mp = message + i;
 733       if (!(mp->m_flag & MHIDDEN)) {
 734          switch (method) {
 735          case SORT_DATE:
 736             if (mp->m_date == 0 && (cp = hfield1("date", mp)) != NULL)
 737                mp->m_date = rfctime(cp);
 738             ms[n].ms_u.ms_long = mp->m_date;
 739             break;
 740          case SORT_STATUS:
 741             if (mp->m_flag & MDELETED)
 742                ms[n].ms_u.ms_long = 1;
 743             else if ((mp->m_flag & (MNEW | MREAD)) == MNEW)
 744                ms[n].ms_u.ms_long = 90;
 745             else if (mp->m_flag & MFLAGGED)
 746                ms[n].ms_u.ms_long = 85;
 747             else if ((mp->m_flag & (MNEW | MBOX)) == MBOX)
 748                ms[n].ms_u.ms_long = 70;
 749             else if (mp->m_flag & MNEW)
 750                ms[n].ms_u.ms_long = 80;
 751             else if (mp->m_flag & MREAD)
 752                ms[n].ms_u.ms_long = 40;
 753             else
 754                ms[n].ms_u.ms_long = 60;
 755             break;
 756          case SORT_SIZE:
 757             ms[n].ms_u.ms_long = mp->m_xsize;
 758             break;
 759 #ifdef HAVE_SPAM
 760          case SORT_SPAM:
 761             ms[n].ms_u.ms_ui = mp->m_spamscore;
 762             break;
 763 #endif
 764          case SORT_FROM:
 765          case SORT_TO:
 766             if ((cp = hfield1((method == SORT_FROM ?  "from" : "to"), mp)) !=
 767                   NULL) {
 768                ms[n].ms_u.ms_char = sstrdup(showname ? realname(cp) : skin(cp));
 769                makelow(ms[n].ms_u.ms_char);
 770             } else
 771                ms[n].ms_u.ms_char = sstrdup(n_empty);
 772             break;
 773          default:
 774          case SORT_SUBJECT:
 775             if ((cp = hfield1("subject", mp)) != NULL) {
 776                in.s = cp;
 777                in.l = strlen(in.s);
 778                mime_fromhdr(&in, &out, TD_ICONV);
 779                ms[n].ms_u.ms_char = sstrdup(subject_re_trim(out.s));
 780                free(out.s);
 781                makelow(ms[n].ms_u.ms_char);
 782             } else
 783                ms[n].ms_u.ms_char = sstrdup(n_empty);
 784             break;
 785          }
 786          ms[n++].ms_n = i;
 787       }
 788       mp->m_child = mp->m_younger = mp->m_elder = mp->m_parent = NULL;
 789       mp->m_level = 0;
 790       mp->m_collapsed = 0;
 791       srelax();
 792    }
 793    srelax_rele();
 794
 795    if (n > 0) {
 796       qsort(ms, n, sizeof *ms, func);
 797       threadroot = message + ms[0].ms_n;
 798       for (i = 1; i < n; ++i) {
 799          message[ms[i - 1].ms_n].m_younger = message + ms[i].ms_n;
 800          message[ms[i].ms_n].m_elder = message + ms[i - 1].ms_n;
 801       }
 802    } else
 803       threadroot = NULL;
 804
 805    _finalize(threadroot);
 806    mb.mb_threaded = 2;
 807
 808    switch (method) {
 809    case SORT_FROM:
 810    case SORT_TO:
 811    case SORT_SUBJECT:
 812       for (i = 0; i < n; ++i)
 813          free(ms[i].ms_u.ms_char);
 814       /* FALLTHRU */
 815    default:
 816       break;
 817    }
 818    ac_free(ms);
 819
 820    i = ((vp != NULL && vp != (void*)-1 && !(n_pstate & n_PS_HOOK_MASK) &&
 821       ok_blook(header)) ? print_header_group(msgvec) : 0);
 822 jleave:
 823    NYD_LEAVE;
 824    return i;
 825 }
 826
 827 FL int
 828 c_collapse(void *v)
 829 {
 830    int rv;
 831    NYD_ENTER;
 832
 833    rv = _colpt(v, 1);
 834    NYD_LEAVE;
 835    return rv;
 836 }
 837
 838 FL int
 839 c_uncollapse(void *v)
 840 {
 841    int rv;
 842    NYD_ENTER;
 843
 844    rv = _colpt(v, 0);
 845    NYD_LEAVE;
 846    return rv;
 847 }
 848
 849 FL void
 850 uncollapse1(struct message *mp, int always)
 851 {
 852    NYD_ENTER;
 853    if (mb.mb_threaded == 1 && (always || mp->m_collapsed > 0))
 854       _colps(mp, 0);
 855    NYD_LEAVE;
 856 }
 857
 858 /* s-it-mode */