thread.c

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