thread.c

Go to the documentation of this file.

 
#include "config.h"
#include <limits.h>
#include <stdbool.h>
#include <string.h>
#include "mutt/lib.h"
#include "config/lib.h"
#include "email/lib.h"
#include "core/lib.h"
#include "mutt.h"
#include "thread.h"
#include "globals.h"
#include "mview.h"
#include "mx.h"

static const struct Mapping UseThreadsMethods[] = {
  // clang-format off
  { "unset",         UT_UNSET },
  { "flat",          UT_FLAT },
  { "threads",       UT_THREADS },
  { "reverse",       UT_REVERSE },
  // aliases
  { "no",            UT_FLAT },
  { "yes",           UT_THREADS },
  { NULL, 0 },
  // clang-format on
};

const struct EnumDef UseThreadsTypeDef = {
  "use_threads_type",
  4,
  (struct Mapping *) &UseThreadsMethods,
};

enum UseThreads mutt_thread_style(void)
{
  const unsigned char c_use_threads = cs_subset_enum(NeoMutt->sub, "use_threads");
  const enum EmailSortType c_sort = cs_subset_sort(NeoMutt->sub, "sort");
  if (c_use_threads > UT_FLAT)
    return c_use_threads;
  if ((c_sort & SORT_MASK) != EMAIL_SORT_THREADS)
    return UT_FLAT;
  if (c_sort & SORT_REVERSE)
    return UT_REVERSE;
  return UT_THREADS;
}

const char *get_use_threads_str(enum UseThreads value)
{
  return mutt_map_get_name(value, UseThreadsMethods);
}

int sort_validator(const struct ConfigDef *cdef, intptr_t value, struct Buffer *err)
{
  if (((value & SORT_MASK) == EMAIL_SORT_THREADS) && (value & SORT_LAST))
  {
    buf_printf(err, _("Cannot use 'last-' prefix with 'threads' for %s"), cdef->name);
    return CSR_ERR_INVALID;
  }
  return CSR_SUCCESS;
}

static bool is_visible(struct Email *e)
{
  return e->vnum >= 0 || (e->collapsed && e->visible);
}

static bool need_display_subject(struct Email *e)
{
  struct MuttThread *tmp = NULL;
  struct MuttThread *tree = e->thread;
 
  if (!tree)
  {
    mutt_debug(LL_DEBUG1, "stranded Email with no thread info, stranded Email index=%d\n",
               e->index);
    return true;
  }
 
  /* if the user disabled subject hiding, display it */
  const bool c_hide_thread_subject = cs_subset_bool(NeoMutt->sub, "hide_thread_subject");
  if (!c_hide_thread_subject)
    return true;
 
  /* if our subject is different from our parent's, display it */
  if (e->subject_changed)
    return true;
 
  /* if our subject is different from that of our closest previously displayed
   * sibling, display the subject */
  for (tmp = tree->prev; tmp; tmp = tmp->prev)
  {
    e = tmp->message;
    if (e && is_visible(e))
    {
      if (e->subject_changed)
        return true;
      break;
    }
  }
 
  /* if there is a parent-to-child subject change anywhere between us and our
   * closest displayed ancestor, display the subject */
  for (tmp = tree->parent; tmp; tmp = tmp->parent)
  {
    e = tmp->message;
    if (e)
    {
      if (is_visible(e))
        return false;
      if (e->subject_changed)
        return true;
    }
  }
 
  /* if we have no visible parent or previous sibling, display the subject */
  return true;
}

static void linearize_tree(struct ThreadsContext *tctx)
{
  if (!tctx || !tctx->mailbox_view)
    return;
 
  struct Mailbox *m = tctx->mailbox_view->mailbox;
 
  const bool reverse = (mutt_thread_style() == UT_REVERSE);
  struct MuttThread *tree = tctx->tree;
  struct Email **array = m->emails + (reverse ? m->msg_count - 1 : 0);
 
  while (tree)
  {
    while (!tree->message)
      tree = tree->child;
 
    *array = tree->message;
    array += reverse ? -1 : 1;
 
    if (tree->child)
    {
      tree = tree->child;
    }
    else
    {
      while (tree)
      {
        if (tree->next)
        {
          tree = tree->next;
          break;
        }
        else
        {
          tree = tree->parent;
        }
      }
    }
  }
}

static void calculate_visibility(struct MuttThread *tree, int *max_depth)
{
  if (!tree)
    return;
 
  struct MuttThread *tmp = NULL;
  struct MuttThread *orig_tree = tree;
  const bool c_hide_top_missing = cs_subset_bool(NeoMutt->sub, "hide_top_missing");
  const bool c_hide_missing = cs_subset_bool(NeoMutt->sub, "hide_missing");
  int hide_top_missing = c_hide_top_missing && !c_hide_missing;
  const bool c_hide_top_limited = cs_subset_bool(NeoMutt->sub, "hide_top_limited");
  const bool c_hide_limited = cs_subset_bool(NeoMutt->sub, "hide_limited");
  int hide_top_limited = c_hide_top_limited && !c_hide_limited;
  int depth = 0;
 
  /* Walk each level backwards (right to left) to make it easier to
   * compute next_subtree_visible for each node */
  while (tree->next)
    tree = tree->next;
  *max_depth = 0;
 
  while (true)
  {
    if (depth > *max_depth)
      *max_depth = depth;
 
    tree->subtree_visible = 0;
    if (tree->message)
    {
      FREE(&tree->message->tree);
      if (tree->message->thread != tree)
      {
        mutt_debug(LL_DEBUG1, "thread<->message mismatch: Email index=%d, thread=%p, message->thread=%p\n",
                   tree->message->index, (void *) tree, (void *) tree->message->thread);
      }
      /* Visible messages propagate subtree_visible up to all ancestors */
      if (is_visible(tree->message))
      {
        tree->deep = true;
        tree->visible = true;
        tree->message->display_subject = need_display_subject(tree->message);
        for (tmp = tree; tmp; tmp = tmp->parent)
        {
          if (tmp->subtree_visible)
          {
            tmp->deep = true;
            tmp->subtree_visible = 2;
            break;
          }
          else
          {
            tmp->subtree_visible = 1;
          }
        }
      }
      else
      {
        tree->visible = false;
        tree->deep = !c_hide_limited;
      }
    }
    else
    {
      tree->visible = false;
      tree->deep = !c_hide_missing;
    }
    /* Compute next_subtree_visible from the next sibling, then
     * navigate: descend to children, retreat to previous sibling,
     * or ascend to parent when at the leftmost node */
    tree->next_subtree_visible = tree->next && (tree->next->next_subtree_visible ||
                                                tree->next->subtree_visible);
    if (tree->child)
    {
      depth++;
      tree = tree->child;
      while (tree->next)
        tree = tree->next;
    }
    else if (tree->prev)
    {
      tree = tree->prev;
    }
    else
    {
      while (tree && !tree->prev)
      {
        depth--;
        tree = tree->parent;
      }
      if (!tree)
        break;
      tree = tree->prev;
    }
  }
 
  /* now fix up for the OPTHIDETOP* options if necessary */
  if (hide_top_limited || hide_top_missing)
  {
    tree = orig_tree;
    while (true)
    {
      if (!tree->visible && tree->deep && (tree->subtree_visible < 2) &&
          ((tree->message && hide_top_limited) || (!tree->message && hide_top_missing)))
      {
        tree->deep = false;
      }
      if (!tree->deep && tree->child && tree->subtree_visible)
      {
        tree = tree->child;
      }
      else if (tree->next)
      {
        tree = tree->next;
      }
      else
      {
        while (tree && !tree->next)
          tree = tree->parent;
        if (!tree)
          break;
        tree = tree->next;
      }
    }
  }
}

struct ThreadsContext *mutt_thread_ctx_init(struct MailboxView *mv)
{
  struct ThreadsContext *tctx = MUTT_MEM_CALLOC(1, struct ThreadsContext);
  tctx->mailbox_view = mv;
  return tctx;
}

void mutt_thread_ctx_free(struct ThreadsContext **ptr)
{
  if (!ptr || !*ptr)
  {
    return;
  }
 
  struct ThreadsContext *tctx = *ptr;
 
  mutt_hash_free(&tctx->hash);
 
  FREE(ptr);
}

static int thread_check_integrity(struct MuttThread *tree)
{
  if (!tree)
    return 0;
 
  /* Rewind to the true head of this sibling level */
  while (tree->prev)
    tree = tree->prev;
 
  int repairs = 0;
 
  while (true)
  {
    if (tree->message && (tree->message->thread != tree))
    {
      mutt_debug(LL_DEBUG1, "repairing thread<->message: Email index=%d, expected=%p, actual=%p\n",
                 tree->message->index, (void *) tree, (void *) tree->message->thread);
      tree->message->thread = tree;
      repairs++;
    }
 
    if (tree->child)
    {
      tree = tree->child;
      /* Rewind to the true head of this sibling level */
      while (tree->prev)
        tree = tree->prev;
    }
    else if (tree->next)
    {
      tree = tree->next;
    }
    else
    {
      while (tree && !tree->next)
        tree = tree->parent;
      if (!tree)
        break;
      tree = tree->next;
    }
  }
 
  return repairs;
}

void mutt_draw_tree(struct ThreadsContext *tctx)
{
  if (!tctx || !tctx->tree)
    return;
 
  char *pfx = NULL;
  char *mypfx = NULL;
  char *arrow = NULL;
  char *myarrow = NULL;
  char *new_tree = NULL;
  const bool reverse = (mutt_thread_style() == UT_REVERSE);
  enum TreeChar corner = reverse ? MUTT_TREE_ULCORNER : MUTT_TREE_LLCORNER;
  enum TreeChar vtee = reverse ? MUTT_TREE_BTEE : MUTT_TREE_TTEE;
  const bool c_narrow_tree = cs_subset_bool(NeoMutt->sub, "narrow_tree");
  int depth = 0;
  int start_depth = 0;
  int max_depth = 0;
  int width = c_narrow_tree ? 1 : 2;
  struct MuttThread *nextdisp = NULL;
  struct MuttThread *pseudo = NULL;
  struct MuttThread *parent = NULL;
 
  struct MuttThread *tree = tctx->tree;
 
  /* Verify and repair thread<->message back-pointers before traversal */
  thread_check_integrity(tree);
 
  /* Do the visibility calculations and free the old thread chars.
   * From now on we can simply ignore invisible subtrees */
  calculate_visibility(tree, &max_depth);
  pfx = MUTT_MEM_MALLOC((width * max_depth) + 2, char);
  arrow = MUTT_MEM_MALLOC((width * max_depth) + 2, char);
  const bool c_hide_limited = cs_subset_bool(NeoMutt->sub, "hide_limited");
  const bool c_hide_missing = cs_subset_bool(NeoMutt->sub, "hide_missing");
  while (tree)
  {
    if (depth != 0)
    {
      myarrow = arrow + (depth - start_depth - ((start_depth != 0) ? 0 : 1)) * width;
      if (start_depth == depth)
        myarrow[0] = nextdisp ? MUTT_TREE_LTEE : corner;
      else if (parent->message && !c_hide_limited)
        myarrow[0] = MUTT_TREE_HIDDEN;
      else if (!parent->message && !c_hide_missing)
        myarrow[0] = MUTT_TREE_MISSING;
      else
        myarrow[0] = vtee;
      if (width == 2)
      {
        myarrow[1] = pseudo ? MUTT_TREE_STAR :
                              (tree->duplicate_thread ? MUTT_TREE_EQUALS : MUTT_TREE_HLINE);
      }
      if (tree->visible)
      {
        myarrow[width] = MUTT_TREE_RARROW;
        myarrow[width + 1] = 0;
        new_tree = MUTT_MEM_MALLOC(((size_t) depth * width) + 2, char);
        if (start_depth > 1)
        {
          strncpy(new_tree, pfx, (size_t) width * (start_depth - 1));
          mutt_str_copy(new_tree + (start_depth - 1) * width, arrow,
                        (1 + depth - start_depth) * width + 2);
        }
        else
        {
          mutt_str_copy(new_tree, arrow, ((size_t) depth * width) + 2);
        }
        tree->message->tree = new_tree;
      }
    }
    if (tree->child && (depth != 0))
    {
      mypfx = pfx + (depth - 1) * width;
      mypfx[0] = nextdisp ? MUTT_TREE_VLINE : MUTT_TREE_SPACE;
      if (width == 2)
        mypfx[1] = MUTT_TREE_SPACE;
    }
    parent = tree;
    nextdisp = NULL;
    pseudo = NULL;
    do
    {
      if (tree->child && tree->subtree_visible)
      {
        if (tree->deep)
          depth++;
        if (tree->visible)
          start_depth = depth;
        tree = tree->child;
 
        /* we do this here because we need to make sure that the first child thread
         * of the old tree that we deal with is actually displayed if any are,
         * or we might set the parent variable wrong while going through it. */
        while (!tree->subtree_visible && tree->next)
          tree = tree->next;
      }
      else
      {
        while (!tree->next && tree->parent)
        {
          if (tree == pseudo)
            pseudo = NULL;
          if (tree == nextdisp)
            nextdisp = NULL;
          if (tree->visible)
            start_depth = depth;
          tree = tree->parent;
          if (tree->deep)
          {
            if (start_depth == depth)
              start_depth--;
            depth--;
          }
        }
        if (tree == pseudo)
          pseudo = NULL;
        if (tree == nextdisp)
          nextdisp = NULL;
        if (tree->visible)
          start_depth = depth;
        tree = tree->next;
        if (!tree)
          break;
      }
      if (!pseudo && tree->fake_thread)
        pseudo = tree;
      if (!nextdisp && tree->next_subtree_visible)
        nextdisp = tree;
    } while (!tree->deep);
  }
 
  FREE(&pfx);
  FREE(&arrow);
}

static void make_subject_list(struct ListHead *subjects, struct MuttThread *cur, time_t *dateptr)
{
  struct MuttThread *start = cur;
  struct Envelope *env = NULL;
  time_t thisdate;
  int rc = 0;
 
  const bool c_thread_received = cs_subset_bool(NeoMutt->sub, "thread_received");
  const bool c_sort_re = cs_subset_bool(NeoMutt->sub, "sort_re");
  while (true)
  {
    while (!cur->message)
      cur = cur->child;
 
    if (dateptr)
    {
      thisdate = c_thread_received ? cur->message->received : cur->message->date_sent;
      if ((*dateptr == 0) || (thisdate < *dateptr))
        *dateptr = thisdate;
    }
 
    env = cur->message->env;
    if (env->real_subj && ((env->real_subj != env->subject) || !c_sort_re))
    {
      struct ListNode *np = NULL;
      STAILQ_FOREACH(np, subjects, entries)
      {
        rc = mutt_str_cmp(env->real_subj, np->data);
        if (rc >= 0)
          break;
      }
      if (!np)
        mutt_list_insert_head(subjects, env->real_subj);
      else if (rc > 0)
        mutt_list_insert_after(subjects, np, env->real_subj);
    }
 
    while (!cur->next && (cur != start))
    {
      cur = cur->parent;
    }
    if (cur == start)
      break;
    cur = cur->next;
  }
}

static struct MuttThread *find_subject(struct Mailbox *m, struct MuttThread *cur)
{
  if (!m)
    return NULL;
 
  struct HashElem *he = NULL;
  struct MuttThread *tmp = NULL;
  struct MuttThread *last = NULL;
  struct ListHead subjects = STAILQ_HEAD_INITIALIZER(subjects);
  time_t date = 0;
 
  make_subject_list(&subjects, cur, &date);
 
  struct ListNode *np = NULL;
  const bool c_thread_received = cs_subset_bool(NeoMutt->sub, "thread_received");
  STAILQ_FOREACH(np, &subjects, entries)
  {
    for (he = mutt_hash_find_bucket(m->subj_hash, np->data); he; he = he->next)
    {
      tmp = ((struct Email *) he->data)->thread;
      if ((tmp != cur) &&                  /* don't match the same message */
          !tmp->fake_thread &&             /* don't match pseudo threads */
          tmp->message->subject_changed && /* only match interesting replies */
          !is_descendant(tmp, cur) &&      /* don't match in the same thread */
          (date >= (c_thread_received ? tmp->message->received : tmp->message->date_sent)) &&
          (!last || (c_thread_received ?
                         (last->message->received < tmp->message->received) :
                         (last->message->date_sent < tmp->message->date_sent))) &&
          tmp->message->env->real_subj &&
          mutt_str_equal(np->data, tmp->message->env->real_subj))
      {
        last = tmp; /* best match so far */
      }
    }
  }
 
  mutt_list_clear(&subjects);
  return last;
}

static struct HashTable *make_subj_hash(struct Mailbox *m)
{
  if (!m)
    return NULL;
 
  struct HashTable *hash = mutt_hash_new(m->msg_count * 2, MUTT_HASH_ALLOW_DUPS);
 
  for (int i = 0; i < m->msg_count; i++)
  {
    struct Email *e = m->emails[i];
    if (!e || !e->env)
      continue;
    if (e->env->real_subj)
      mutt_hash_insert(hash, e->env->real_subj, e);
  }
 
  return hash;
}

static void pseudo_threads(struct ThreadsContext *tctx)
{
  if (!tctx || !tctx->mailbox_view)
    return;
 
  struct Mailbox *m = tctx->mailbox_view->mailbox;
 
  struct MuttThread *tree = tctx->tree;
  struct MuttThread *top = tree;
  struct MuttThread *tmp = NULL;
  struct MuttThread *cur = NULL;
  struct MuttThread *parent = NULL;
  struct MuttThread *curchild = NULL;
  struct MuttThread *nextchild = NULL;
 
  if (!m->subj_hash)
    m->subj_hash = make_subj_hash(m);
 
  while (tree)
  {
    cur = tree;
    tree = tree->next;
    parent = find_subject(m, cur);
    if (parent)
    {
      cur->fake_thread = true;
      unlink_message(&top, cur);
      insert_message(&parent->child, parent, cur);
      parent->sort_children = true;
      tmp = cur;
      while (true)
      {
        while (!tmp->message)
          tmp = tmp->child;
 
        /* if the message we're attaching has pseudo-children, they
         * need to be attached to its parent, so move them up a level.
         * but only do this if they have the same real subject as the
         * parent, since otherwise they rightly belong to the message
         * we're attaching. */
        if ((tmp == cur) || mutt_str_equal(tmp->message->env->real_subj,
                                           parent->message->env->real_subj))
        {
          tmp->message->subject_changed = false;
 
          for (curchild = tmp->child; curchild;)
          {
            nextchild = curchild->next;
            if (curchild->fake_thread)
            {
              unlink_message(&tmp->child, curchild);
              insert_message(&parent->child, parent, curchild);
            }
            curchild = nextchild;
          }
        }
 
        while (!tmp->next && (tmp != cur))
        {
          tmp = tmp->parent;
        }
        if (tmp == cur)
          break;
        tmp = tmp->next;
      }
    }
  }
  tctx->tree = top;
}

void mutt_clear_threads(struct ThreadsContext *tctx)
{
  if (!tctx || !tctx->tree)
    return;
 
  struct MailboxView *mv = tctx->mailbox_view;
  if (!mv)
    return;
 
  struct Mailbox *m = mv->mailbox;
  if (!m || !m->emails)
    return;
 
  for (int i = 0; i < m->msg_count; i++)
  {
    struct Email *e = m->emails[i];
    if (!e)
    {
      // Keep processing, in case there are other holes in the Email array
      continue;
    }
 
    /* mailbox may have been only partially read */
    e->thread = NULL;
    e->threaded = false;
  }
  tctx->tree = NULL;
  mutt_hash_free(&tctx->hash);
}

static int compare_threads(const void *a, const void *b, void *sdata)
{
  const struct MuttThread *ta = *(struct MuttThread const *const *) a;
  const struct MuttThread *tb = *(struct MuttThread const *const *) b;
  const struct ThreadsContext *tctx = sdata;
  ASSERT(ta->parent == tb->parent);
 
  /* If c_sort ties, remember we are building the thread array in
   * reverse from the index the mails had in the mailbox.  */
  struct Mailbox *m = tctx->mailbox_view->mailbox;
  const enum MailboxType mtype = mx_type(m);
  if (ta->parent)
  {
    return mutt_compare_emails(ta->sort_aux_key, tb->sort_aux_key, mtype,
                               tctx->c_sort_aux, SORT_REVERSE | EMAIL_SORT_UNSORTED);
  }
  else
  {
    return mutt_compare_emails(ta->sort_thread_key, tb->sort_thread_key, mtype,
                               tctx->c_sort, SORT_REVERSE | EMAIL_SORT_UNSORTED);
  }
}

static void mutt_sort_subthreads(struct ThreadsContext *tctx, bool init)
{
  struct MuttThread *thread = tctx->tree;
  if (!thread)
    return;
 
  struct MuttThread **array = NULL;
  struct MuttThread *top = NULL;
  struct MuttThread *tmp = NULL;
  struct Email *sort_aux_key = NULL;
  struct Email *oldsort_aux_key = NULL;
  struct Email *oldsort_thread_key = NULL;
  int i;
  int array_size;
  bool sort_top = false;
 
  /* we put things into the array backwards to save some cycles,
   * but we want to have to move less stuff around if we're
   * resorting, so we sort backwards and then put them back
   * in reverse order so they're forwards */
  const bool reverse = (mutt_thread_style() == UT_REVERSE);
  enum EmailSortType c_sort = cs_subset_sort(NeoMutt->sub, "sort");
  enum EmailSortType c_sort_aux = cs_subset_sort(NeoMutt->sub, "sort_aux");
  if ((c_sort & SORT_MASK) == EMAIL_SORT_THREADS)
  {
    ASSERT(!(c_sort & SORT_REVERSE) != reverse);
    c_sort = c_sort_aux;
  }
  c_sort ^= SORT_REVERSE;
  c_sort_aux ^= SORT_REVERSE;
  if (init || (tctx->c_sort != c_sort) || (tctx->c_sort_aux != c_sort_aux))
  {
    tctx->c_sort = c_sort;
    tctx->c_sort_aux = c_sort_aux;
    init = true;
  }
 
  top = thread;
 
  array_size = 256;
  array = MUTT_MEM_CALLOC(array_size, struct MuttThread *);
  while (true)
  {
    if (init || !thread->sort_thread_key || !thread->sort_aux_key)
    {
      thread->sort_thread_key = NULL;
      thread->sort_aux_key = NULL;
 
      if (thread->parent)
        thread->parent->sort_children = true;
      else
        sort_top = true;
    }
 
    if (thread->child)
    {
      thread = thread->child;
      continue;
    }
    else
    {
      /* if it has no children, it must be real. sort it on its own merits */
      thread->sort_thread_key = thread->message;
      thread->sort_aux_key = thread->message;
 
      if (thread->next)
      {
        thread = thread->next;
        continue;
      }
    }
 
    struct Mailbox *m = tctx->mailbox_view->mailbox;
    const enum MailboxType mtype = mx_type(m);
    while (!thread->next)
    {
      /* if it has siblings and needs to be sorted, sort it... */
      if (thread->prev && (thread->parent ? thread->parent->sort_children : sort_top))
      {
        /* put them into the array */
        for (i = 0; thread; i++, thread = thread->prev)
        {
          if (i >= array_size)
          {
            array_size *= 2;
            MUTT_MEM_REALLOC(&array, array_size, struct MuttThread *);
          }
 
          array[i] = thread;
        }
 
        mutt_qsort_r((void *) array, i, sizeof(struct MuttThread *), compare_threads, tctx);
 
        /* attach them back together.  make thread the last sibling. */
        thread = array[0];
        thread->next = NULL;
        array[i - 1]->prev = NULL;
 
        if (thread->parent)
          thread->parent->child = array[i - 1];
        else
          top = array[i - 1];
 
        while (--i)
        {
          array[i - 1]->prev = array[i];
          array[i]->next = array[i - 1];
        }
      }
 
      if (thread->parent)
      {
        tmp = thread;
        thread = thread->parent;
 
        if (!thread->sort_thread_key || !thread->sort_aux_key || thread->sort_children)
        {
          /* we just sorted its children */
          thread->sort_children = false;
 
          oldsort_aux_key = thread->sort_aux_key;
          oldsort_thread_key = thread->sort_thread_key;
 
          /* update sort keys. sort_aux_key will be the first or last
           * sibling, as appropriate... */
          thread->sort_aux_key = thread->message;
          sort_aux_key = ((!(c_sort_aux & SORT_LAST)) ^ (!(c_sort_aux & SORT_REVERSE))) ?
                             thread->child->sort_aux_key :
                             tmp->sort_aux_key;
 
          if (c_sort_aux & SORT_LAST)
          {
            if (!thread->sort_aux_key ||
                (mutt_compare_emails(thread->sort_aux_key, sort_aux_key, mtype,
                                     c_sort_aux | SORT_REVERSE, EMAIL_SORT_UNSORTED) > 0))
            {
              thread->sort_aux_key = sort_aux_key;
            }
          }
          else if (!thread->sort_aux_key)
          {
            thread->sort_aux_key = sort_aux_key;
          }
 
          /* ...but sort_thread_key may require searching the entire
           * list of siblings */
          if ((c_sort_aux & ~SORT_REVERSE) == (c_sort & ~SORT_REVERSE))
          {
            thread->sort_thread_key = thread->sort_aux_key;
          }
          else
          {
            if (thread->message)
            {
              thread->sort_thread_key = thread->message;
            }
            else if (reverse != (!(c_sort_aux & SORT_REVERSE)))
            {
              thread->sort_thread_key = tmp->sort_thread_key;
            }
            else
            {
              thread->sort_thread_key = thread->child->sort_thread_key;
            }
            if (c_sort & SORT_LAST)
            {
              for (tmp = thread->child; tmp; tmp = tmp->next)
              {
                if (tmp->sort_thread_key == thread->sort_thread_key)
                  continue;
                if ((mutt_compare_emails(thread->sort_thread_key, tmp->sort_thread_key, mtype,
                                         c_sort | SORT_REVERSE, EMAIL_SORT_UNSORTED) > 0))
                {
                  thread->sort_thread_key = tmp->sort_thread_key;
                }
              }
            }
          }
 
          /* if a sort_key has changed, we need to resort it and siblings */
          if ((oldsort_aux_key != thread->sort_aux_key) ||
              (oldsort_thread_key != thread->sort_thread_key))
          {
            if (thread->parent)
              thread->parent->sort_children = true;
            else
              sort_top = true;
          }
        }
      }
      else
      {
        FREE(&array);
        tctx->tree = top;
        return;
      }
    }
 
    thread = thread->next;
  }
}

static void check_subjects(struct MailboxView *mv, bool init)
{
  if (!mv)
    return;
 
  struct Mailbox *m = mv->mailbox;
  for (int i = 0; i < m->msg_count; i++)
  {
    struct Email *e = m->emails[i];
    if (!e || !e->thread)
      continue;
 
    if (e->thread->check_subject)
      e->thread->check_subject = false;
    else if (!init)
      continue;
 
    /* figure out which messages have subjects different than their parents' */
    struct MuttThread *tmp = e->thread->parent;
    while (tmp && !tmp->message)
    {
      tmp = tmp->parent;
    }
 
    if (!tmp)
    {
      e->subject_changed = true;
    }
    else if (e->env->real_subj && tmp->message->env->real_subj)
    {
      e->subject_changed = !mutt_str_equal(e->env->real_subj, tmp->message->env->real_subj);
    }
    else
    {
      e->subject_changed = (e->env->real_subj || tmp->message->env->real_subj);
    }
  }
}

static void thread_hash_destructor(int type, void *obj, intptr_t data)
{
  FREE(&obj);
}

void mutt_sort_threads(struct ThreadsContext *tctx, bool init)
{
  if (!tctx || !tctx->mailbox_view)
    return;
 
  struct MailboxView *mv = tctx->mailbox_view;
  struct Mailbox *m = mv->mailbox;
 
  struct Email *e = NULL;
  int i;
  int using_refs = 0;
  struct MuttThread *thread = NULL;
  struct MuttThread *tnew = NULL;
  struct MuttThread *tmp = NULL;
  struct MuttThread top = { 0 };
  struct ListNode *ref = NULL;
 
  ASSERT(m->msg_count > 0);
  if (!tctx->hash)
    init = true;
 
  if (init)
  {
    tctx->hash = mutt_hash_new(m->msg_count * 2, MUTT_HASH_ALLOW_DUPS);
    mutt_hash_set_destructor(tctx->hash, thread_hash_destructor, 0);
  }
 
  /* we want a quick way to see if things are actually attached to the top of the
   * thread tree or if they're just dangling, so we attach everything to a top
   * node temporarily */
  top.parent = NULL;
  top.next = NULL;
  top.prev = NULL;
 
  top.child = tctx->tree;
  for (thread = tctx->tree; thread; thread = thread->next)
    thread->parent = &top;
 
  /* put each new message together with the matching messageless MuttThread if it
   * exists.  otherwise, if there is a MuttThread that already has a message, thread
   * new message as an identical child.  if we didn't attach the message to a
   * MuttThread, make a new one for it. */
  const bool c_duplicate_threads = cs_subset_bool(NeoMutt->sub, "duplicate_threads");
  for (i = 0; i < m->msg_count; i++)
  {
    e = m->emails[i];
    if (!e)
      continue;
 
    if (e->thread)
    {
      /* unlink pseudo-threads because they might be children of newly
       * arrived messages */
      thread = e->thread;
      for (tnew = thread->child; tnew;)
      {
        tmp = tnew->next;
        if (tnew->fake_thread)
        {
          unlink_message(&thread->child, tnew);
          insert_message(&top.child, &top, tnew);
          tnew->fake_thread = false;
        }
        tnew = tmp;
      }
    }
    else
    {
      if ((!init || c_duplicate_threads) && e->env->message_id)
        thread = mutt_hash_find(tctx->hash, e->env->message_id);
      else
        thread = NULL;
 
      if (thread && !thread->message)
      {
        /* this is a message which was missing before */
        thread->message = e;
        e->thread = thread;
        thread->check_subject = true;
 
        /* mark descendants as needing subject_changed checked */
        for (tmp = (thread->child ? thread->child : thread); tmp != thread;)
        {
          while (!tmp->message)
            tmp = tmp->child;
          tmp->check_subject = true;
          while (!tmp->next && (tmp != thread))
            tmp = tmp->parent;
          if (tmp != thread)
            tmp = tmp->next;
        }
 
        if (thread->parent)
        {
          /* remove threading info above it based on its children, which we'll
           * recalculate based on its headers.  make sure not to leave
           * dangling missing messages.  note that we haven't kept track
           * of what info came from its children and what from its siblings'
           * children, so we just remove the stuff that's definitely from it */
          do
          {
            tmp = thread->parent;
            unlink_message(&tmp->child, thread);
            thread->parent = NULL;
            thread->sort_thread_key = NULL;
            thread->sort_aux_key = NULL;
            thread->fake_thread = false;
            thread = tmp;
          } while (thread != &top && !thread->child && !thread->message);
        }
      }
      else
      {
        tnew = (c_duplicate_threads ? thread : NULL);
 
        thread = MUTT_MEM_CALLOC(1, struct MuttThread);
        thread->message = e;
        thread->check_subject = true;
        e->thread = thread;
        mutt_hash_insert(tctx->hash, e->env->message_id ? e->env->message_id : "", thread);
 
        if (tnew)
        {
          if (tnew->duplicate_thread)
            tnew = tnew->parent;
 
          thread = e->thread;
 
          insert_message(&tnew->child, tnew, thread);
          thread->duplicate_thread = true;
          thread->message->threaded = true;
        }
      }
    }
  }
 
  /* thread by references */
  for (i = 0; i < m->msg_count; i++)
  {
    e = m->emails[i];
    if (!e)
      break;
 
    if (e->threaded)
      continue;
    e->threaded = true;
 
    thread = e->thread;
    if (!thread)
      continue;
    using_refs = 0;
 
    while (true)
    {
      if (using_refs == 0)
      {
        /* look at the beginning of in-reply-to: */
        ref = STAILQ_FIRST(&e->env->in_reply_to);
        if (ref)
        {
          using_refs = 1;
        }
        else
        {
          ref = STAILQ_FIRST(&e->env->references);
          using_refs = 2;
        }
      }
      else if (using_refs == 1)
      {
        /* if there's no references header, use all the in-reply-to:
         * data that we have.  otherwise, use the first reference
         * if it's different than the first in-reply-to, otherwise use
         * the second reference (since at least eudora puts the most
         * recent reference in in-reply-to and the rest in references) */
        if (STAILQ_EMPTY(&e->env->references))
        {
          ref = STAILQ_NEXT(ref, entries);
        }
        else
        {
          if (!mutt_str_equal(ref->data, STAILQ_FIRST(&e->env->references)->data))
            ref = STAILQ_FIRST(&e->env->references);
          else
            ref = STAILQ_NEXT(STAILQ_FIRST(&e->env->references), entries);
 
          using_refs = 2;
        }
      }
      else
      {
        ref = STAILQ_NEXT(ref, entries); /* go on with references */
      }
 
      if (!ref)
        break;
 
      tnew = mutt_hash_find(tctx->hash, ref->data);
      if (tnew)
      {
        if (tnew->duplicate_thread)
          tnew = tnew->parent;
        if (is_descendant(tnew, thread)) /* no loops! */
          continue;
      }
      else
      {
        tnew = MUTT_MEM_CALLOC(1, struct MuttThread);
        mutt_hash_insert(tctx->hash, ref->data, tnew);
      }
 
      if (thread->parent)
        unlink_message(&top.child, thread);
      insert_message(&tnew->child, tnew, thread);
      thread = tnew;
      if (thread->message || (thread->parent && (thread->parent != &top)))
        break;
    }
 
    if (!thread->parent)
      insert_message(&top.child, &top, thread);
  }
 
  /* detach everything from the temporary top node */
  for (thread = top.child; thread; thread = thread->next)
  {
    thread->parent = NULL;
  }
  tctx->tree = top.child;
 
  check_subjects(mv, init);
 
  const bool c_strict_threads = cs_subset_bool(NeoMutt->sub, "strict_threads");
  if (!c_strict_threads)
    pseudo_threads(tctx);
 
  /* if $sort_aux or similar changed after the mailbox is sorted, then
   * all the subthreads need to be resorted */
  if (tctx->tree)
  {
    mutt_sort_subthreads(tctx, init || OptSortSubthreads);
    OptSortSubthreads = false;
 
    /* Put the list into an array. */
    linearize_tree(tctx);
 
    /* Draw the thread tree. */
    mutt_draw_tree(tctx);
  }
}

int mutt_aside_thread(struct Email *e, bool forwards, bool subthreads)
{
  if (!e)
    return -1;
 
  struct MuttThread *cur = NULL;
  struct Email *e_tmp = NULL;
 
  const enum UseThreads threaded = mutt_thread_style();
  if (threaded == UT_FLAT)
  {
    mutt_warning(_("Threading is not enabled"));
    return e->vnum;
  }
 
  cur = e->thread;
 
  if (subthreads)
  {
    if (forwards ^ (threaded == UT_REVERSE))
    {
      while (!cur->next && cur->parent)
        cur = cur->parent;
    }
    else
    {
      while (!cur->prev && cur->parent)
        cur = cur->parent;
    }
  }
  else
  {
    while (cur->parent)
      cur = cur->parent;
  }
 
  if (forwards ^ (threaded == UT_REVERSE))
  {
    do
    {
      cur = cur->next;
      if (!cur)
        return -1;
      e_tmp = find_virtual(cur, false);
    } while (!e_tmp);
  }
  else
  {
    do
    {
      cur = cur->prev;
      if (!cur)
        return -1;
      e_tmp = find_virtual(cur, true);
    } while (!e_tmp);
  }
 
  return e_tmp->vnum;
}

int mutt_parent_message(struct Email *e, bool find_root, int count)
{
  if (!e)
    return -1;
 
  struct MuttThread *thread = NULL;
  struct Email *e_parent = NULL;
 
  if (!mutt_using_threads())
  {
    mutt_warning(_("Threading is not enabled"));
    return e->vnum;
  }
 
  /* Normalize count to at least 1 */
  if (count <= 0)
    count = 1;
 
  /* Root may be the current message */
  if (find_root)
    e_parent = e;
 
  for (thread = e->thread->parent; thread; thread = thread->parent)
  {
    e = thread->message;
    if (e)
    {
      e_parent = e;
      if (!find_root)
      {
        count--;
        if (count == 0)
          break;
      }
    }
  }
 
  if (!e_parent)
  {
    mutt_error(_("Parent message is not available"));
    return -1;
  }
  if (!is_visible(e_parent))
  {
    if (find_root)
      mutt_error(_("Root message is not visible in this limited view"));
    else
      mutt_error(_("Parent message is not visible in this limited view"));
    return -1;
  }
  return e_parent->vnum;
}

off_t mutt_set_vnum(struct Mailbox *m)
{
  if (!m)
    return 0;
 
  off_t vsize = 0;
  const int padding = mx_msg_padding_size(m);
 
  m->vcount = 0;
 
  for (int i = 0; i < m->msg_count; i++)
  {
    struct Email *e = m->emails[i];
    if (!e)
      break;
 
    if (e->vnum >= 0)
    {
      e->vnum = m->vcount;
      m->v2r[m->vcount] = i;
      m->vcount++;
      vsize += e->body->length + e->body->offset - e->body->hdr_offset + padding;
    }
  }
 
  return vsize;
}

int mutt_traverse_thread(struct Email *e_cur, MuttThreadFlags flag)
{
  struct MuttThread *thread = NULL;
  struct MuttThread *top = NULL;
  struct Email *e_root = NULL;
  const enum UseThreads threaded = mutt_thread_style();
  int final;
  int reverse = (threaded == UT_REVERSE);
  int minmsgno;
  int num_hidden = 0;
  int new_mail = 0;
  int old_mail = 0;
  bool flagged = false;
  int min_unread_msgno = INT_MAX;
  int min_unread = e_cur->vnum;
 
  if (threaded == UT_FLAT)
  {
    mutt_warning(_("Threading is not enabled"));
    return e_cur->vnum;
  }
 
  if (!e_cur->thread)
  {
    return e_cur->vnum;
  }
 
  final = e_cur->vnum;
  thread = e_cur->thread;
  while (thread->parent)
    thread = thread->parent;
  top = thread;
  while (!thread->message)
    thread = thread->child;
  e_cur = thread->message;
  minmsgno = e_cur->msgno;
 
  if (!e_cur->read && e_cur->visible)
  {
    if (e_cur->old)
      old_mail = 2;
    else
      new_mail = 1;
    if (e_cur->msgno < min_unread_msgno)
    {
      min_unread = e_cur->vnum;
      min_unread_msgno = e_cur->msgno;
    }
  }
 
  if (e_cur->flagged && e_cur->visible)
    flagged = true;
 
  if ((e_cur->vnum == -1) && e_cur->visible)
    num_hidden++;
 
  if (flag & (MUTT_THREAD_COLLAPSE | MUTT_THREAD_UNCOLLAPSE))
  {
    e_cur->attr_color = NULL; /* force index entry's color to be re-evaluated */
    e_cur->collapsed = flag & MUTT_THREAD_COLLAPSE;
    if (e_cur->vnum != -1)
    {
      e_root = e_cur;
      if (flag & MUTT_THREAD_COLLAPSE)
        final = e_root->vnum;
    }
  }
 
  if ((thread == top) && !(thread = thread->child))
  {
    /* return value depends on action requested */
    if (flag & (MUTT_THREAD_COLLAPSE | MUTT_THREAD_UNCOLLAPSE))
    {
      e_cur->num_hidden = num_hidden;
      return final;
    }
    if (flag & MUTT_THREAD_UNREAD)
      return (old_mail && new_mail) ? new_mail : (old_mail ? old_mail : new_mail);
    if (flag & MUTT_THREAD_NEXT_UNREAD)
      return min_unread;
    if (flag & MUTT_THREAD_FLAGGED)
      return flagged;
  }
 
  while (true)
  {
    e_cur = thread->message;
 
    if (e_cur)
    {
      if (flag & (MUTT_THREAD_COLLAPSE | MUTT_THREAD_UNCOLLAPSE))
      {
        e_cur->attr_color = NULL; /* force index entry's color to be re-evaluated */
        e_cur->collapsed = flag & MUTT_THREAD_COLLAPSE;
        if (!e_root && e_cur->visible)
        {
          e_root = e_cur;
          if (flag & MUTT_THREAD_COLLAPSE)
            final = e_root->vnum;
        }
 
        if (reverse && (flag & MUTT_THREAD_COLLAPSE) &&
            (e_cur->msgno < minmsgno) && e_cur->visible)
        {
          minmsgno = e_cur->msgno;
          final = e_cur->vnum;
        }
 
        if (flag & MUTT_THREAD_COLLAPSE)
        {
          if (e_cur != e_root)
            e_cur->vnum = -1;
        }
        else
        {
          if (e_cur->visible)
            e_cur->vnum = e_cur->msgno;
        }
      }
 
      if (!e_cur->read && e_cur->visible)
      {
        if (e_cur->old)
          old_mail = 2;
        else
          new_mail = 1;
        if (e_cur->msgno < min_unread_msgno)
        {
          min_unread = e_cur->vnum;
          min_unread_msgno = e_cur->msgno;
        }
      }
 
      if (e_cur->flagged && e_cur->visible)
        flagged = true;
 
      if ((e_cur->vnum == -1) && e_cur->visible)
        num_hidden++;
    }
 
    if (thread->child)
    {
      thread = thread->child;
    }
    else if (thread->next)
    {
      thread = thread->next;
    }
    else
    {
      bool done = false;
      while (!thread->next)
      {
        thread = thread->parent;
        if (thread == top)
        {
          done = true;
          break;
        }
      }
      if (done)
        break;
      thread = thread->next;
    }
  }
 
  /* re-traverse the thread and store num_hidden in all headers, with or
   * without a virtual index.  this will allow ~v to match all collapsed
   * messages when switching sort order to non-threaded.  */
  if (flag & MUTT_THREAD_COLLAPSE)
  {
    thread = top;
    while (true)
    {
      e_cur = thread->message;
      if (e_cur)
        e_cur->num_hidden = num_hidden + 1;
 
      if (thread->child)
      {
        thread = thread->child;
      }
      else if (thread->next)
      {
        thread = thread->next;
      }
      else
      {
        bool done = false;
        while (!thread->next)
        {
          thread = thread->parent;
          if (thread == top)
          {
            done = true;
            break;
          }
        }
        if (done)
          break;
        thread = thread->next;
      }
    }
  }
 
  /* return value depends on action requested */
  if (flag & (MUTT_THREAD_COLLAPSE | MUTT_THREAD_UNCOLLAPSE))
    return final;
  if (flag & MUTT_THREAD_UNREAD)
    return (old_mail && new_mail) ? new_mail : (old_mail ? old_mail : new_mail);
  if (flag & MUTT_THREAD_NEXT_UNREAD)
    return min_unread;
  if (flag & MUTT_THREAD_FLAGGED)
    return flagged;
 
  return 0;
}

int mutt_messages_in_thread(struct Mailbox *m, struct Email *e, enum MessageInThread mit)
{
  if (!m || !e)
    return 1;
 
  struct MuttThread *threads[2] = { 0 };
  int rc;
 
  const enum UseThreads threaded = mutt_thread_style();
  if ((threaded == UT_FLAT) || !e->thread)
    return 1;
 
  threads[0] = e->thread;
  while (threads[0]->parent)
    threads[0] = threads[0]->parent;
 
  threads[1] = (mit == MIT_POSITION) ? e->thread : threads[0]->next;
 
  for (int i = 0; i < (((mit == MIT_POSITION) || !threads[1]) ? 1 : 2); i++)
  {
    /* Descend to the first node that references a real Email.
     * Guard against a malformed or partially-built tree:
     * a node with no message and no child would otherwise cause a NULL dereference. */
    while (threads[i] && !threads[i]->message)
      threads[i] = threads[i]->child;
 
    if (!threads[i] || !threads[i]->message)
      return 1;
  }
 
  if (threaded == UT_REVERSE)
  {
    rc = threads[0]->message->msgno - (threads[1] ? threads[1]->message->msgno : -1);
  }
  else
  {
    rc = (threads[1] ? threads[1]->message->msgno : m->msg_count) -
         threads[0]->message->msgno;
  }
 
  if (mit == MIT_POSITION)
    rc += 1;
 
  return rc;
}

struct HashTable *mutt_make_id_hash(struct Mailbox *m)
{
  struct HashTable *hash = mutt_hash_new(m->msg_count * 2, MUTT_HASH_NONE);
 
  for (int i = 0; i < m->msg_count; i++)
  {
    struct Email *e = m->emails[i];
    if (!e || !e->env)
      continue;
 
    if (e->env->message_id)
      mutt_hash_insert(hash, e->env->message_id, e);
  }
 
  return hash;
}

static bool link_threads(struct Email *parent, struct Email *child, struct Mailbox *m)
{
  if (child == parent)
    return false;
 
  mutt_break_thread(child);
  mutt_list_insert_head(&child->env->in_reply_to, mutt_str_dup(parent->env->message_id));
  mutt_set_flag(m, child, MUTT_TAG, false, true);
 
  child->changed = true;
  child->env->changed |= MUTT_ENV_CHANGED_IRT;
  return true;
}

bool mutt_link_threads(struct Email *parent, struct EmailArray *children, struct Mailbox *m)
{
  if (!parent || !children || !m)
    return false;
 
  bool changed = false;
 
  struct Email **ep = NULL;
  ARRAY_FOREACH(ep, children)
  {
    struct Email *e = *ep;
    changed |= link_threads(parent, e, m);
  }
 
  return changed;
}

void mutt_thread_collapse_collapsed(struct ThreadsContext *tctx)
{
  struct MuttThread *thread = NULL;
  struct MuttThread *top = tctx->tree;
  while ((thread = top))
  {
    while (!thread->message)
      thread = thread->child;
 
    struct Email *e = thread->message;
    if (e->collapsed)
      mutt_collapse_thread(e);
    top = top->next;
  }
}

void mutt_thread_collapse(struct ThreadsContext *tctx, bool collapse)
{
  struct MuttThread *thread = NULL;
  struct MuttThread *top = tctx->tree;
  while ((thread = top))
  {
    while (!thread->message)
      thread = thread->child;
 
    struct Email *e = thread->message;
 
    if (e->collapsed != collapse)
    {
      if (e->collapsed)
        mutt_uncollapse_thread(e);
      else if (mutt_thread_can_collapse(e))
        mutt_collapse_thread(e);
    }
    top = top->next;
  }
}

bool mutt_thread_can_collapse(struct Email *e)
{
  const bool c_collapse_flagged = cs_subset_bool(NeoMutt->sub, "collapse_flagged");
  const bool c_collapse_unread = cs_subset_bool(NeoMutt->sub, "collapse_unread");
  return (c_collapse_unread || !mutt_thread_contains_unread(e)) &&
         (c_collapse_flagged || !mutt_thread_contains_flagged(e));
}