index.c

/* index.c -- Routines for dealing with the index file in the imapd
 *
 * Copyright (c) 1994-2008 Carnegie Mellon University.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The name "Carnegie Mellon University" must not be used to
 *    endorse or promote products derived from this software without
 *    prior written permission. For permission or any legal
 *    details, please contact
 *      Carnegie Mellon University
 *      Center for Technology Transfer and Enterprise Creation
 *      4615 Forbes Avenue
 *      Suite 302
 *      Pittsburgh, PA  15213
 *      (412) 268-7393, fax: (412) 268-7395
 *      innovation@andrew.cmu.edu
 *
 * 4. Redistributions of any form whatsoever must retain the following
 *    acknowledgment:
 *    "This product includes software developed by Computing Services
 *     at Carnegie Mellon University (http://www.cmu.edu/computing/)."
 *
 * CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO
 * THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS, IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
 * FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
 * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <config.h>

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <errno.h>
#include <fcntl.h>
#include <netinet/in.h>
#include <sysexits.h>
#include <syslog.h>
#include <ctype.h>
#include <stdlib.h>

#ifdef USE_HTTPD
/* For iCalendar indexing */
#include <libical/ical.h>
#include "vcard_support.h"
#endif

#include "acl.h"
#include "annotate.h"
#include "append.h"
#include "assert.h"
#include "backend.h"
#include "charset.h"
#include "conversations.h"
#include "dlist.h"
#include "hash.h"
#include "hashu64.h"
#include "http_client.h"
#include "jmap_util.h"
#include "global.h"
#include "times.h"
#include "imapd.h"
#include "lsort.h"
#include "mailbox.h"
#include "map.h"
#include "message.h"
#include "msgrecord.h"
#include "parseaddr.h"
#include "search_engines.h"
#include "search_query.h"
#include "seen.h"
#include "statuscache.h"
#include "strhash.h"
#include "user.h"
#include "util.h"
#include "xstats.h"
#include "ptrarray.h"
#include "xmalloc.h"
#include "xstrlcpy.h"

#include "index.h"
#include "sync_log.h"

/* generated headers are not necessarily in current directory */
#include "imap/imap_err.h"

EXPORTED unsigned client_capa;

/* Forward declarations */
static void index_refresh_locked(struct index_state *state);
static void index_tellexists(struct index_state *state);
static int index_lock(struct index_state *state, int readonly);
static void index_unlock(struct index_state *state);

struct index_modified_flags {
    int added_flags;
    bit32 added_system_flags;
    bit32 added_user_flags[MAX_USER_FLAGS/32];
    int removed_flags;
    bit32 removed_system_flags;
    bit32 removed_user_flags[MAX_USER_FLAGS/32];
};

static int index_writeseen(struct index_state *state);
static void index_fetchmsg(struct index_state *state,
                    const struct buf *msg,
                    unsigned offset, unsigned size,
                    unsigned start_octet, unsigned octet_count);
static int index_fetchsection(struct index_state *state, const char *resp,
                              const struct buf *msg,
                              char *section, struct body *body, unsigned size,
                              unsigned start_octet, unsigned octet_count);

static void index_fetchfsection(struct index_state *state,
                                const char *msg_base, unsigned long msg_size,
                                struct fieldlist *fsection,
                                struct body *body,
                                unsigned start_octet, unsigned octet_count);
static char *index_readheader(const char *msg_base, unsigned long msg_size,
                              unsigned offset, unsigned size);
static void index_fetchheader(struct index_state *state,
                              const char *msg_base, unsigned long msg_size,
                              unsigned size,
                              const strarray_t *headers,
                              const strarray_t *headers_not);
static void index_fetchcacheheader(struct index_state *state, struct index_record *record,
                                   const strarray_t *headers, unsigned start_octet,
                                   unsigned octet_count);
static void index_listflags(struct index_state *state);
static void index_fetchflags(struct index_state *state, uint32_t msgno);

static int index_copysetup(struct index_state *state, uint32_t msgno,
                           struct copyargs *copyargs);
static int index_storeflag(struct index_state *state,
                           struct index_modified_flags *modified_flags,
                           uint32_t msgno, msgrecord_t *msgrec,
                           struct storeargs *storeargs);
static int index_store_annotation(struct index_state *state, uint32_t msgno,
                           msgrecord_t *mrw, struct storeargs *storeargs,
                           int *dirty);
static int index_fetchreply(struct index_state *state, uint32_t msgno,
                            const struct fetchargs *fetchargs);
static void index_printflags(struct index_state *state, uint32_t msgno,
                             int usinguid, int printmodseq);
static char *get_localpart_addr(const char *header);
static char *get_displayname(const char *header);
static char *index_extract_subject(const char *subj, size_t len, int *is_refwd);
static char *_index_extract_subject(char *s, int *is_refwd);
static void index_get_ids(MsgData *msgdata,
                          char *envtokens[], const char *headers, unsigned size);

static int index_sort_compare(MsgData *md1, MsgData *md2,
                              const struct sortcrit *call_data);

static void *index_thread_getnext(Thread *thread);
static void index_thread_setnext(Thread *thread, Thread *next);
static int index_thread_compare(Thread *t1, Thread *t2,
                                const struct sortcrit *call_data);
static void index_thread_orderedsubj(struct index_state *state,
                                     unsigned *msgno_list, unsigned int nmsg,
                                     int usinguid);
static void index_thread_sort(Thread *root, const struct sortcrit *sortcrit);
static void index_thread_print(struct index_state *state,
                               Thread *threads, int usinguid);
static void index_thread_references(struct index_state *state,
                                    unsigned *msgno_list, unsigned int nmsg,
                                    int usinguid);
static void index_thread_refs(struct index_state *state,
                              unsigned *msgno_list, unsigned int nmsg,
                              int usinguid);

static struct seqset *_parse_sequence(struct index_state *state,
                                      const char *sequence, int usinguid);
static void massage_header(char *hdr);

/* NOTE: Make sure these are listed in CAPABILITY_STRING */
static const struct thread_algorithm thread_algs[] = {
    { "ORDEREDSUBJECT", index_thread_orderedsubj },
    { "REFERENCES", index_thread_references },
    { "REFS", index_thread_refs },
    { NULL, NULL }
};

EXPORTED int index_reload_record(struct index_state *state,
                                 uint32_t msgno,
                                 struct index_record *record)
{
    struct index_map *im = &state->map[msgno-1];
    int r = 0;
    int i;

    memset(record, 0, sizeof(struct index_record));
    if (!im->recno) {
        /* doh, gotta just fill in what we know */
        record->uid = im->uid;
    }
    else {
        record->recno = im->recno;
        record->uid = im->uid;
        r = mailbox_reload_index_record_dirty(state->mailbox, record);
    }
    /* NOTE: we have released the cyrus.index lock at this point, but are
     * still holding the mailbox name relock.  This means nobody can rewrite
     * the file under us - so the offsets are still guaranteed to be correct,
     * and all the immutable fields are unchanged.  That said, we can get a
     * read of a partially updated record which contains an invalid checksum
     * due to incomplete concurrent changes to mutable fields.  That's why we
     * used the _dirty API which ignores checksums.
     * but other errors are still bad */
    if (r) return r;

    /* better be! */
    assert(record->uid == im->uid);

    /* restore mutable fields */
    record->modseq = im->modseq;
    record->system_flags = im->system_flags;
    record->internal_flags = im->internal_flags;
    record->cache_offset = im->cache_offset;
    for (i = 0; i < MAX_USER_FLAGS/32; i++)
        record->user_flags[i] = im->user_flags[i];

    return 0;
}

static int index_rewrite_record(struct index_state *state,
                                uint32_t msgno,
                                struct index_record *record,
                                int silent)
{
    struct index_map *im = &state->map[msgno-1];
    int i;

    assert(record->uid == im->uid);

    if (!silent) {
        int r = mailbox_rewrite_index_record(state->mailbox, record);
        if (r) return r;
    }

    /* update tracking of mutable fields */
    im->modseq = record->modseq;
    im->system_flags = record->system_flags;
    im->internal_flags = record->internal_flags;
    im->cache_offset = record->cache_offset;
    for (i = 0; i < MAX_USER_FLAGS/32; i++)
        im->user_flags[i] = record->user_flags[i];

    return 0;
}

EXPORTED void index_release(struct index_state *state)
{
    if (!state) return;

    message_unref(&state->m);
    if (state->mailbox) {
        mailbox_close(&state->mailbox);
        state->mailbox = NULL; /* should be done by close anyway */
    }
}
static struct sortcrit *the_sortcrit;

/*
 * A mailbox is about to be closed.
 */
EXPORTED void index_close(struct index_state **stateptr)
{
    unsigned i;
    struct index_state *state = *stateptr;

    if (!state) return;

    index_release(state);

    xfree(state->map);
    xfree(state->mboxname);
    xfree(state->userid);
    for (i = 0; i < MAX_USER_FLAGS; i++)
        xfree(state->flagname[i]);
    xfree(state);

    *stateptr = NULL;
}

/*
 * A new mailbox has been selected and already opened, map it into
 * memory and do the initial CHECK.
 */
EXPORTED int index_open_mailbox(struct mailbox *mailbox, struct index_init *init,
                                struct index_state **stateptr)
{
    int r;
    struct index_state *state = xzmalloc(sizeof(struct index_state));

    state->mailbox = mailbox;
    state->mboxname = xstrdup(mailbox->name);

    if (init) {
        state->authstate = init->authstate;
        state->examining = init->examine_mode;
        state->out = init->out;
        state->userid = xstrdupnull(init->userid);
        state->want_dav = init->want_dav;
        state->want_mbtype = init->want_mbtype;
        state->want_expunged = init->want_expunged;

        state->myrights = cyrus_acl_myrights(init->authstate,
                                             state->mailbox->acl);
        if (state->examining)
            state->myrights &= ~ACL_READ_WRITE;

        state->internalseen = mailbox_internal_seen(state->mailbox,
                                                    state->userid);
    }

    if (state->mailbox->mbtype & MBTYPES_NONIMAP) {
        if (state->want_dav) {
            /* User logged in using imapmagicplus token "dav" */
        }
        else if (state->mailbox->mbtype == state->want_mbtype) {
            /* Caller explicitly asks for this NONIMAP type */
        }
        else {
            r = IMAP_MAILBOX_BADTYPE;
            goto fail;
        }
    }

    /* initialise the index_state */
    index_refresh_locked(state);

    /* have to get the vanished list while we're still locked */
    if (init)
        init->vanishedlist = index_vanished(state, &init->vanished);

    index_unlock(state);

    *stateptr = state;

    return 0;

fail:
    xfree(state->mboxname);
    xfree(state->userid);
    xfree(state);
    return r;
}

/*
 * A new mailbox has been selected, map it into memory and do the
 * initial CHECK.
 */
EXPORTED int index_open(const char *name, struct index_init *init,
                        struct index_state **stateptr)
{
    int r;
    struct mailbox *mailbox = NULL;

    r = init && init->examine_mode ? mailbox_open_irl(name, &mailbox) :
                                     mailbox_open_iwl(name, &mailbox);
    if (r) return r;

    r = index_open_mailbox(mailbox, init, stateptr);
    if (r) mailbox_close(&mailbox);

    return r;
}

EXPORTED int index_expunge(struct index_state *state, char *sequence,
                  int need_deleted)
{
    int r;
    uint32_t msgno;
    struct index_map *im;
    struct seqset *seq = NULL;
    struct index_record record;
    int numexpunged = 0;
    struct mboxevent *mboxevent = NULL;
    modseq_t oldmodseq;

    r = index_lock(state, /*readonly*/0);
    if (r) return r;

    /* XXX - check if not mailbox->i.deleted count and need_deleted */
    seq = _parse_sequence(state, sequence, 1);

    mboxevent = mboxevent_new(EVENT_MESSAGE_EXPUNGE);

    for (msgno = 1; msgno <= state->exists; msgno++) {
        im = &state->map[msgno-1];

        if (im->internal_flags & FLAG_INTERNAL_EXPUNGED)
            continue; /* already expunged */

        if (need_deleted && !(im->system_flags & FLAG_DELETED))
            continue; /* no \Deleted flag */

        /* if there is a sequence list, check it */
        if (sequence && !seqset_ismember(seq, im->uid))
            continue; /* not in the list */

        /* load first once we know we have to process this one */
        if (index_reload_record(state, msgno, &record))
            continue;

        oldmodseq = im->modseq;

        if (!im->isseen) {
            if (state->numunseen)
                state->numunseen--;
            else
                syslog(LOG_ERR, "IOERROR: numunseen underflow in expunge: %s %u",
                       state->mboxname, im->uid);
            im->isseen = 1;
        }

        if (im->isrecent) {
            if (state->numrecent)
                state->numrecent--;
            else
                syslog(LOG_ERR, "IOERROR: numrecent underflow in expunge: %s %u",
                       state->mboxname, im->uid);
            im->isrecent = 0;
        }

        /* set the flags */
        record.system_flags |= FLAG_DELETED;
        record.internal_flags |= FLAG_INTERNAL_EXPUNGED;
        numexpunged++;
        state->num_expunged++;

        r = index_rewrite_record(state, msgno, &record, /*silent*/0);
        if (r) break;

        /* avoid telling again (equivalent to STORE FLAGS.SILENT) */
        if (im->told_modseq == oldmodseq)
            im->told_modseq = im->modseq;

        mboxevent_extract_record(mboxevent, state->mailbox, &record);
    }

    seqset_free(seq);

    mboxevent_extract_mailbox(mboxevent, state->mailbox);
    mboxevent_set_access(mboxevent, NULL, NULL, state->userid, state->mailbox->name, 1);
    mboxevent_set_numunseen(mboxevent, state->mailbox, state->numunseen);

    /* unlock before responding */
    index_unlock(state);

    if (!r && (numexpunged > 0)) {
        syslog(LOG_NOTICE, "Expunged %d messages from %s",
               numexpunged, state->mboxname);
        /* send the MessageExpunge event notification for "immediate", "default"
         * and "delayed" expunge */
        mboxevent_notify(&mboxevent);
    }

    mboxevent_free(&mboxevent);

    return r;
}

static char *index_buildseen(struct index_state *state, const char *oldseenuids)
{
    struct seqset *outlist;
    uint32_t msgno;
    unsigned oldmax;
    struct index_map *im;
    char *out;

    outlist = seqset_init(0, SEQ_MERGE);
    for (msgno = 1; msgno <= state->exists; msgno++) {
        im = &state->map[msgno-1];
        seqset_add(outlist, im->uid, im->isseen);
    }

    /* there may be future already seen UIDs that this process isn't
     * allowed to know about, but we can't blat them either!  This is
     * a massive pain... */
    oldmax = seq_lastnum(oldseenuids, NULL);
    if (oldmax > state->last_uid) {
        struct seqset *seq = seqset_parse(oldseenuids, NULL, oldmax);
        uint32_t uid;

        /* for each future UID, copy the state in the old seenuids */
        for (uid = state->last_uid + 1; uid <= oldmax; uid++)
            seqset_add(outlist, uid, seqset_ismember(seq, uid));

        seqset_free(seq);
    }

    out = seqset_cstring(outlist);
    seqset_free(outlist);

    return out;
}

static int index_writeseen(struct index_state *state)
{
    int r;
    struct seen *seendb = NULL;
    struct seendata oldsd = SEENDATA_INITIALIZER;
    struct seendata sd = SEENDATA_INITIALIZER;
    struct mailbox *mailbox = state->mailbox;
    const char *userid = (mailbox->i.options & OPT_IMAP_SHAREDSEEN) ? "anyone" : state->userid;

    if (!state->seen_dirty)
        return 0;

    state->seen_dirty = 0;

    /* only examining, can't write any changes */
    if (state->examining)
        return 0;

    /* always dirty the mailbox, we may just be updating recent counts which doesn't bump the
     * modseq because Recent is all sorts of evil */
    mailbox_index_dirty(mailbox);

    /* already handled! Just update the header fields */
    if (state->internalseen) {
        mailbox->i.recenttime = time(0);
        if (mailbox->i.recentuid < state->last_uid)
            mailbox->i.recentuid = state->last_uid;
        return 0;
    }

    r = seen_open(userid, SEEN_CREATE, &seendb);
    if (r) return r;

    r = seen_lockread(seendb, mailbox->uniqueid, &oldsd);
    if (r) {
        oldsd.lastread = 0;
        oldsd.lastuid = 0;
        oldsd.lastchange = 0;
        oldsd.seenuids = xstrdup("");
    }

    /* fields of interest... */
    sd.lastuid = oldsd.lastuid;
    sd.seenuids = index_buildseen(state, oldsd.seenuids);
    if (!sd.seenuids) sd.seenuids = xstrdup("");

    /* make comparison only catch some changes */
    sd.lastread = oldsd.lastread;
    sd.lastchange = oldsd.lastchange;

    /* update \Recent lowmark */
    if (sd.lastuid < state->last_uid)
        sd.lastuid = state->last_uid;

    /* only commit if interesting fields have changed */
    if (!seen_compare(&sd, &oldsd)) {
        sd.lastread = time(NULL);
        sd.lastchange = mailbox->i.last_appenddate;
        r = seen_write(seendb, mailbox->uniqueid, &sd);
    }

    seen_close(&seendb);

    seen_freedata(&oldsd);
    seen_freedata(&sd);

    return r;
}

/* caller must free the list with seqset_free() when done */
static struct seqset *_readseen(struct index_state *state, unsigned *recentuid)
{
    struct mailbox *mailbox = state->mailbox;
    struct seqset *seenlist = NULL;

    /* Obtain seen information */
    if (state->internalseen) {
        *recentuid = mailbox->i.recentuid;
    }
    else if (state->userid) {
        struct seen *seendb = NULL;
        struct seendata sd = SEENDATA_INITIALIZER;
        const char *userid = (mailbox->i.options & OPT_IMAP_SHAREDSEEN) ? "anyone" : state->userid;
        int r;

        r = seen_open(userid, SEEN_CREATE, &seendb);
        if (!r) r = seen_read(seendb, mailbox->uniqueid, &sd);
        seen_close(&seendb);

        /* handle no seen DB gracefully */
        if (r) {
            *recentuid = mailbox->i.last_uid;
            prot_printf(state->out, "* OK (seen state failure) %s: %s\r\n",
                   error_message(IMAP_NO_CHECKPRESERVE), error_message(r));
            syslog(LOG_ERR, "Could not open seen state for %s (%s)",
                   userid, error_message(r));
        }
        else {
            *recentuid = sd.lastuid;
            seenlist = seqset_parse(sd.seenuids, NULL, *recentuid);
            seen_freedata(&sd);
        }
    }
    else {
        *recentuid = mailbox->i.last_uid; /* nothing is recent! */
    }

    return seenlist;
}

static void index_refresh_locked(struct index_state *state)
{
    struct mailbox *mailbox = state->mailbox;
    const message_t *msg;
    uint32_t msgno = 1;
    uint32_t firstnotseen = 0;
    uint32_t numrecent = 0;
    uint32_t numunseen = 0;
    uint32_t num_expunged = 0;
    uint32_t recentuid = 0;
    modseq_t delayed_modseq = 0;
    struct index_map *im;
    uint32_t need_records;
    struct seqset *seenlist;
    int i;

    /* need to start by having enough space for the entire index state
     * before telling of any expunges (which happens after this refresh
     * if the command allows it).  In the update case, where there's
     * already a map, we have to theoretically fit the number that existed
     * last time plus however many new records might be unEXPUNGEd on the
     * end */

    need_records = state->want_expunged ? mailbox->i.num_records : mailbox->i.exists;
    if (state->last_uid) {
        need_records = state->exists + (mailbox->i.last_uid - state->last_uid);
    }

    /* make sure we have space */
    if (need_records >= state->mapsize) {
        state->mapsize = (need_records | 0xff) + 1; /* round up 1-256 */
        state->map = xrealloc(state->map,
                              state->mapsize * sizeof(struct index_map));
    }

    seenlist = _readseen(state, &recentuid);

    /* walk through all records */
    struct mailbox_iter *iter = mailbox_iter_init(mailbox, 0, ITER_SKIP_UNLINKED);
    while ((msg = mailbox_iter_step(iter))) {
        const struct index_record *record = msg_record(msg);
        im = &state->map[msgno-1];
        while (msgno <= state->exists && im->uid < record->uid) {
            /* NOTE: this same logic is repeated below for messages
             * past the end of recno (repack removing the trailing
             * records).  Make sure to keep them in sync */
            if (!(im->internal_flags & FLAG_INTERNAL_EXPUNGED)) {
                /* we don't even know the modseq of when it was wiped,
                 * but we can be sure it's since the last given highestmodseq,
                 * so simulate the lowest possible value.  This is fine for
                 * our told_modseq logic, and doesn't have to be exact because
                 * QRESYNC/CONDSTORE clients will see deletedmodseq and fall
                 * back to the inefficient codepath anyway */
                im->modseq = state->highestmodseq + 1;
            }
            if (!delayed_modseq || im->modseq < delayed_modseq)
                delayed_modseq = im->modseq - 1;
            im->recno = 0;
            /* simulate expunged flag so we get an EXPUNGE response and
             * tell about unlinked so we don't get IO errors trying to
             * find the file */
            im->internal_flags |= FLAG_INTERNAL_EXPUNGED |
                FLAG_INTERNAL_UNLINKED;
            im = &state->map[msgno++];

            /* this one is expunged */
            num_expunged++;
        }

        /* expunged record not in map, can skip immediately.  It's
         * never been told to this connection, so it doesn't need to
         * get its own msgno */
        if (!state->want_expunged
            && (msgno > state->exists || record->uid < im->uid)
            && (record->internal_flags & FLAG_INTERNAL_EXPUNGED))
            continue;

        /* make sure our UID map is consistent */
        if (msgno <= state->exists) {
            assert(im->uid == record->uid);
        }
        else {
            memset(im, 0, sizeof(struct index_map));
            im->uid = record->uid;
        }

        /* copy all mutable fields */
        im->recno = record->recno;
        im->modseq = record->modseq;
        im->system_flags = record->system_flags;
        im->internal_flags = record->internal_flags;
        im->cache_offset = record->cache_offset;
        for (i = 0; i < MAX_USER_FLAGS/32; i++)
            im->user_flags[i] = record->user_flags[i];

        /* re-calculate seen flags */
        if (state->internalseen)
            im->isseen = (im->system_flags & FLAG_SEEN) ? 1 : 0;
        else
            im->isseen = seqset_ismember(seenlist, im->uid) ? 1 : 0;

        /* for expunged records, just track the modseq */
        if (im->internal_flags & FLAG_INTERNAL_EXPUNGED) {
            num_expunged++;
            /* http://www.rfc-editor.org/errata_search.php?rfc=5162
             * Errata ID: 1809 - if there are expunged records we
             * aren't telling about, need to make the highestmodseq
             * be one lower so the client can safely resync */
            if (!delayed_modseq || im->modseq < delayed_modseq)
                delayed_modseq = im->modseq - 1;
        }
        else {
            if (msgno > state->exists) {
                /* don't auto-tell new records */
                im->told_modseq = im->modseq;
                if (im->uid > recentuid) {
                    /* mark recent if it's newly being added to the index and also
                     * greater than the recentuid - ensures only one session gets
                     * the \Recent flag for any one message */
                    im->isrecent = 1;
                    state->seen_dirty = 1;
                }
                else
                    im->isrecent = 0;
            }

            /* track select values */
            if (!im->isseen) {
                numunseen++;
                if (!firstnotseen)
                    firstnotseen = msgno;
            }
            if (im->isrecent) {
                numrecent++;
            }
        }

        /* make sure we don't overflow the memory we mapped */
        if (msgno > state->mapsize) {
            char buf[2048];
            sprintf(buf, "Exists wrong %u %u %u %u", msgno,
                    state->mapsize, mailbox->i.exists, mailbox->i.num_records);
            fatal(buf, EX_IOERR);
        }

        msgno++;
    }
    mailbox_iter_done(&iter);

    /* may be trailing records which need to be considered for
     * delayed_modseq purposes, and to get the count right for
     * later expunge processing */
    im = &state->map[msgno-1];
    while (msgno <= state->exists) {
        /* this is the same logic as the block above in the main loop,
         * see comments up there, and make sure the blocks are kept
         * in sync! */
        if (!(im->internal_flags & FLAG_INTERNAL_EXPUNGED))
            im->modseq = state->highestmodseq + 1;
        if (!delayed_modseq || im->modseq < delayed_modseq)
            delayed_modseq = im->modseq - 1;
        im->recno = 0;
        im->internal_flags |= FLAG_INTERNAL_EXPUNGED | FLAG_INTERNAL_UNLINKED;
        im = &state->map[msgno++];
        num_expunged++;
    }

    seqset_free(seenlist);

    /* update the header tracking data */
    state->oldexists = state->exists; /* we last knew about this many */
    state->exists = msgno - 1; /* we actually got this many */
    state->delayed_modseq = delayed_modseq;
    state->oldhighestmodseq = state->highestmodseq;
    state->highestmodseq = mailbox->i.highestmodseq;
    state->generation = mailbox->i.generation_no;
    state->uidvalidity = mailbox->i.uidvalidity;
    state->last_uid = mailbox->i.last_uid;
    state->num_records = mailbox->i.num_records;
    state->num_expunged = num_expunged;
    state->firstnotseen = firstnotseen;
    state->numunseen = numunseen;
    state->numrecent = numrecent;
}

EXPORTED modseq_t index_highestmodseq(struct index_state *state)
{
    if (state->delayed_modseq)
        return state->delayed_modseq;
    return state->highestmodseq;
}

EXPORTED void index_select(struct index_state *state, struct index_init *init)
{
    index_tellexists(state);

    /* always print flags */
    index_checkflags(state, 1, 1);

    if (state->firstnotseen)
        prot_printf(state->out, "* OK [UNSEEN %u] Ok\r\n",
                    state->firstnotseen);
    prot_printf(state->out, "* OK [UIDVALIDITY %u] Ok\r\n",
                state->mailbox->i.uidvalidity);
    prot_printf(state->out, "* OK [UIDNEXT %lu] Ok\r\n",
                state->last_uid + 1);
    prot_printf(state->out, "* OK [HIGHESTMODSEQ " MODSEQ_FMT "] Ok\r\n",
                state->highestmodseq);
    prot_printf(state->out, "* OK [URLMECH INTERNAL] Ok\r\n");

    /*
     * RFC5257.  Note that we must report a maximum size for annotations
     * but we don't enforce any such limit, so pick a "large" number.
     */
    prot_printf(state->out, "* OK [ANNOTATIONS %u] Ok\r\n", 64*1024);

    if (init->vanishedlist) {
        char *vanished;
        const char *sequence = NULL;
        struct seqset *seq = NULL;
        struct index_map *im;
        uint32_t msgno;

        /* QRESYNC response:
         * UID FETCH seq FLAGS (CHANGEDSINCE modseq VANISHED)
          */

        vanished = seqset_cstring(init->vanishedlist);
        if (vanished) {
            prot_printf(state->out, "* VANISHED (EARLIER) %s\r\n", vanished);
            free(vanished);
        }

        sequence = init->vanished.sequence;
        if (sequence) seq = _parse_sequence(state, sequence, 1);
        for (msgno = 1; msgno <= state->exists; msgno++) {
            im = &state->map[msgno-1];
            if (sequence && !seqset_ismember(seq, im->uid))
                continue;
            if (im->modseq <= init->vanished.modseq)
                continue;
            index_printflags(state, msgno, 1, 0);
        }
        seqset_free(seq);
    }
}

/*
 * Check for and report updates
 */
EXPORTED int index_check(struct index_state *state, int usinguid, int printuid)
{
    int r;

    if (!state) return 0;

    /* we don't write any records in here, but we want to write the recentuid if
     * there were new emails delivered... */
    r = index_lock(state, /*readonly*/0);

    /* Check for deleted mailbox  */
    if (r == IMAP_MAILBOX_NONEXISTENT) {
        /* Mailbox has been (re)moved */
        if (config_getswitch(IMAPOPT_DISCONNECT_ON_VANISHED_MAILBOX)) {
            syslog(LOG_WARNING,
                   "Mailbox %s has been (re)moved out from under client",
                   state->mboxname);
            mailbox_close(&state->mailbox);
            fatal("Mailbox has been (re)moved", EX_IOERR);
        }

        if (state->exists && (client_capa & CAPA_QRESYNC)) {
            /* XXX - is it OK to just expand to entire possible range? */
            prot_printf(state->out, "* VANISHED 1:%lu\r\n", state->last_uid);
        }
        else {
            int exists;
            for (exists = state->exists; exists > 0; exists--) {
                prot_printf(state->out, "* 1 EXPUNGE\r\n");
            }
        }

        state->exists = 0;
        return IMAP_MAILBOX_NONEXISTENT;
    }

    if (r) return r;

    index_tellchanges(state, usinguid, printuid, 0);

#if TOIMSP
    if (state->firstnotseen) {
        toimsp(state->mboxname, state->mailbox->i.uidvalidity, "SEENsnn", state->userid,
               0, state->mailbox->i.recenttime, 0);
    }
    else {
        toimsp(state->mboxname, state->mailbox->i.uidvalidity, "SEENsnn", state->userid,
               state->mailbox->last_uid, state->mailbox->i.recenttime, 0);
    }
#endif

    index_unlock(state);

    return r;
}

/*
 * Perform UID FETCH (VANISHED) on a sequence.
 */
struct seqset *index_vanished(struct index_state *state,
                              struct vanished_params *params)
{
    struct mailbox *mailbox = state->mailbox;
    struct seqset *outlist;
    struct seqset *seq;

    /* check uidvalidity match */
    if (params->uidvalidity_is_max) {
        if (params->uidvalidity < mailbox->i.uidvalidity) return NULL;
    }
    else {
        if (params->uidvalidity != mailbox->i.uidvalidity) return NULL;
    }

    /* No recently expunged messages */
    if (params->modseq >= state->highestmodseq) return NULL;

    outlist = seqset_init(0, SEQ_SPARSE);
    seq = _parse_sequence(state, params->sequence, 1);

    /* XXX - use match_seq and match_uid */

    if (params->modseq >= mailbox->i.deletedmodseq) {
        const message_t *msg;
        /* all records are significant */
        /* List only expunged UIDs with MODSEQ > requested */
        struct mailbox_iter *iter = mailbox_iter_init(mailbox, params->modseq, 0);
        while ((msg = mailbox_iter_step(iter))) {
            const struct index_record *record = msg_record(msg);
            if (!(record->internal_flags & FLAG_INTERNAL_EXPUNGED))
                continue;
            if (!params->sequence || seqset_ismember(seq, record->uid))
                seqset_add(outlist, record->uid, 1);
        }
        mailbox_iter_done(&iter);
    }
    else {
        unsigned prevuid = 0;
        struct seqset *msgnolist;
        struct seqset *uidlist;
        uint32_t msgno;
        unsigned uid;

        syslog(LOG_NOTICE, "inefficient qresync ("
               MODSEQ_FMT " > " MODSEQ_FMT ") %s",
               mailbox->i.deletedmodseq, params->modseq,
               mailbox->name);

        /* use the sequence to uid mapping provided by the client to
         * skip over any initial matches - see RFC 5162 section 3.1 */
        if (params->match_seq && params->match_uid) {
            msgnolist = _parse_sequence(state, params->match_seq, 0);
            uidlist = _parse_sequence(state, params->match_uid, 1);
            while ((msgno = seqset_getnext(msgnolist)) != 0) {
                uid = seqset_getnext(uidlist);
                /* first non-match, we'll start here */
                if (state->map[msgno-1].uid != uid)
                    break;
                /* ok, they matched - so we can start after here */
                prevuid = uid;
            }
            seqset_free(msgnolist);
            seqset_free(uidlist);
        }

        const message_t *msg;
        struct mailbox_iter *iter = mailbox_iter_init(mailbox, params->modseq, ITER_SKIP_EXPUNGED);
        mailbox_iter_startuid(iter, prevuid);

        /* possible efficiency improvement - use "seq_getnext" on seq
         * to avoid incrementing through every single number for prevuid.
         * Only really an issue if there's a giant block of thousands of
         * expunged messages.  Only likely to be seen in the wild if
         * last_uid winds up being bumped up a few million by a bug... */

        /* for the rest of the mailbox, we're just going to have to assume
         * every record in the requested range which DOESN'T exist has been
         * expunged, so build a complete sequence */
        while ((msg = mailbox_iter_step(iter))) {
            const struct index_record *record = msg_record(msg);
            while (++prevuid < record->uid) {
                if (!params->sequence || seqset_ismember(seq, prevuid))
                    seqset_add(outlist, prevuid, 1);
            }
            prevuid = record->uid;
        }
        mailbox_iter_done(&iter);

        /* include the space past the final record up to last_uid as well */
        while (++prevuid <= mailbox->i.last_uid) {
            if (!params->sequence || seqset_ismember(seq, prevuid))
                seqset_add(outlist, prevuid, 1);
        }
    }

    seqset_free(seq);

    return outlist;
}

static int _fetch_setseen(struct index_state *state,
                          struct mboxevent *mboxevent,
                          uint32_t msgno)
{
    struct index_map *im = &state->map[msgno-1];
    struct index_record record;
    int r;

    /* already seen */
    if (im->isseen)
        return 0;

    /* no rights to change it */
    if (!(state->myrights & ACL_SETSEEN))
        return 0;

    r = index_reload_record(state, msgno, &record);
    if (r) return r;

    /* track changes internally */
    if (state->numunseen)
        state->numunseen--;
    else
        syslog(LOG_ERR, "IOERROR: unseen underflow on setseen: %s %u",
               state->mboxname, im->uid);
    state->seen_dirty = 1;
    im->isseen = 1;

    /* also store in the record if it's internal seen */
    if (state->internalseen)
        record.system_flags |= FLAG_SEEN;

    /* need to bump modseq anyway, so always rewrite it */
    r = index_rewrite_record(state, msgno, &record, /*silent*/0);
    if (r) return r;

    mboxevent_extract_record(mboxevent, state->mailbox, &record);

    /* RFC2060 says:
     * The \Seen flag is implicitly set; if this causes
     * the flags to change they SHOULD be included as part
     * of the FETCH responses.   This is handled later by
     * always including flags if the modseq has changed.
     */

    return 0;
}

/* seq can be NULL - means "ALL" */
EXPORTED void index_fetchresponses(struct index_state *state,
                          struct seqset *seq,
                          int usinguid,
                          const struct fetchargs *fetchargs,
                          int *fetchedsomething)
{
    uint32_t msgno, start, end;
    struct index_map *im;
    int fetched = 0;
    annotate_db_t *annot_db = NULL;

    /* Keep an open reference on the per-mailbox db to avoid
     * doing too many slow database opens during the fetch */
    if ((fetchargs->fetchitems & FETCH_ANNOTATION))
        annotate_getdb(state->mboxname, &annot_db);

    start = 1;
    end = state->exists;

    /* if we haven't told exists and we're fetching something past the end of the
     * old size, we need to tell exists now...
     * https://github.com/cyrusimap/cyrus-imapd/issues/1967
     */
    if (state->exists != state->oldexists) index_tellexists(state);

    /* if the modseq hasn't changed then there will be no unsolicited updates
     * to send, so we only need to scan messages inside the sequence range.
     * https://github.com/cyrusimap/cyrus-imapd/issues/1971
     */
    if (state->oldhighestmodseq == state->highestmodseq) {
        /* compress the search range down if a sequence was given */
        if (seq) {
            unsigned first = seqset_first(seq);
            unsigned last = seqset_last(seq);

            if (usinguid) {
                if (first > 1)
                    start = index_finduid(state, first);
                if (first == last)
                    end = start;
                else if (last < state->last_uid)
                    end = index_finduid(state, last);
            }
            else {
                start = first;
                end = last;
            }
        }
    }

    /* make sure we didn't go outside the range! */
    if (start < 1) start = 1;
    if (end > state->exists) end = state->exists;

    for (msgno = start; msgno <= end; msgno++) {
        im = &state->map[msgno-1];
        if (seq && !seqset_ismember(seq, usinguid ? im->uid : msgno)) {
            if (im->told_modseq !=0 && im->modseq > im->told_modseq)
                index_printflags(state, msgno, usinguid, 0);
            continue;
        }

        if (index_fetchreply(state, msgno, fetchargs))
            break;
        fetched = 1;
    }

    /* Update oldhighestmodseq, ensuring we don't have unsolicited updates */
    state->oldhighestmodseq = state->highestmodseq;

    if (fetchedsomething) *fetchedsomething = fetched;
    annotate_putdb(&annot_db);
}

/*
 * Perform a FETCH-related command on a sequence.
 * Fetchedsomething argument is 0 if nothing was fetched, 1 if something was
 * fetched.  (A fetch command that fetches nothing is not a valid fetch
 * command.)
 */
EXPORTED int index_fetch(struct index_state *state,
                const char *sequence,
                int usinguid,
                const struct fetchargs *fetchargs,
                int *fetchedsomething)
{
    struct seqset *seq;
    struct seqset *vanishedlist = NULL;
    struct index_map *im;
    uint32_t msgno;
    int r;
    struct mboxevent *mboxevent = NULL;

    r = index_lock(state, /*readonly*/0);  // can't be readonly because of FETCH_SETSEEN
    if (r) return r;

    seq = _parse_sequence(state, sequence, usinguid);

    /* set the \Seen flag if necessary - while we still have the lock */
    if (fetchargs->fetchitems & FETCH_SETSEEN && !state->examining && state->myrights & ACL_SETSEEN) {
        mboxevent = mboxevent_new(EVENT_MESSAGE_READ);

        for (msgno = 1; msgno <= state->exists; msgno++) {
            im = &state->map[msgno-1];
            if (!seqset_ismember(seq, usinguid ? im->uid : msgno))
                continue;
            r = _fetch_setseen(state, mboxevent, msgno);
            if (r) break;
        }

        mboxevent_extract_mailbox(mboxevent, state->mailbox);
        mboxevent_set_access(mboxevent, NULL, NULL, state->userid, state->mailbox->name, 1);
        mboxevent_set_numunseen(mboxevent, state->mailbox,
                                state->numunseen);
    }

    if (fetchargs->vanished) {
        struct vanished_params v;
        v.sequence = sequence;;
        v.uidvalidity = state->mailbox->i.uidvalidity;
        v.modseq = fetchargs->changedsince;
        v.match_seq = fetchargs->match_seq;
        v.match_uid = fetchargs->match_uid;
        /* XXX - return error unless usinguid? */
        vanishedlist = index_vanished(state, &v);
    }

    index_unlock(state);

    /* send MessageRead event notification for successfully rewritten records */
    mboxevent_notify(&mboxevent);
    mboxevent_free(&mboxevent);

    index_checkflags(state, 1, 0);

    if (vanishedlist && vanishedlist->len) {
        char *vanished = seqset_cstring(vanishedlist);
        prot_printf(state->out, "* VANISHED (EARLIER) %s\r\n", vanished);
        free(vanished);
    }

    seqset_free(vanishedlist);

    index_fetchresponses(state, seq, usinguid, fetchargs, fetchedsomething);

    seqset_free(seq);

    index_tellchanges(state, usinguid, usinguid, 0);

    return r;
}

/*
 * Perform a STORE command on a sequence
 */
EXPORTED int index_store(struct index_state *state, char *sequence,
                         struct storeargs *storeargs)
{
    struct mailbox *mailbox;
    int i, r = 0;
    uint32_t msgno;
    int userflag;
    struct seqset *seq;
    struct index_map *im;
    const strarray_t *flags = &storeargs->flags;
    struct mboxevent *mboxevents = NULL;
    struct mboxevent *flagsset = NULL, *flagsclear = NULL;
    struct index_modified_flags modified_flags;
    struct index_record record;

    /* First pass at checking permission */
    if ((storeargs->seen && !(state->myrights & ACL_SETSEEN)) ||
        ((storeargs->system_flags & FLAG_DELETED) &&
         !(state->myrights & ACL_DELETEMSG)) ||
        (((storeargs->system_flags & ~FLAG_DELETED) || flags->count) &&
         !(state->myrights & ACL_WRITE))) {
        return IMAP_PERMISSION_DENIED;
    }

    r = index_lock(state, /*readonly*/0);
    if (r) return r;

    mailbox = state->mailbox;

    seq = _parse_sequence(state, sequence, storeargs->usinguid);

    for (i = 0; i < flags->count ; i++) {
        r = mailbox_user_flag(mailbox, flags->data[i], &userflag, 1);
        if (r) goto out;
        storeargs->user_flags[userflag/32] |= 1<<(userflag&31);
    }

    storeargs->update_time = time((time_t *)0);

    for (msgno = 1; msgno <= state->exists; msgno++) {
        im = &state->map[msgno-1];
        if (!seqset_ismember(seq, storeargs->usinguid ? im->uid : msgno))
            continue;

        /* if it's expunged already, skip it now */
        if ((im->internal_flags & FLAG_INTERNAL_EXPUNGED))
            continue;

        /* if it's changed already, skip it now */
        if (im->modseq > storeargs->unchangedsince) {
            if (!storeargs->modified) {
                uint32_t maxval = (storeargs->usinguid ?
                                   state->last_uid : state->exists);
                storeargs->modified = seqset_init(maxval, SEQ_SPARSE);
            }
            seqset_add(storeargs->modified,
                       (storeargs->usinguid ? im->uid : msgno),
                       /*ismember*/1);
            continue;
        }

        /* TODO(rsto): we need to keep index_reload_record here until we
         * can make sure that the index map doesn't contain uncommitted
         * changes for this msgno. See the comments in index_reload_record
         * on how it releases the cyrus.index lock in the middle of action */
        r = index_reload_record(state, msgno, &record);
        if (r) goto out;

        msgrecord_t *msgrec = msgrecord_from_index_record(state->mailbox, &record);

        switch (storeargs->operation) {
        case STORE_ADD_FLAGS:
        case STORE_REMOVE_FLAGS:
        case STORE_REPLACE_FLAGS:
            r = index_storeflag(state, &modified_flags, msgno, msgrec, storeargs);
            if (r) goto doneloop;

            // nothing to do?
            if (!(modified_flags.added_flags | modified_flags.removed_flags))
                goto doneloop;

            r = msgrecord_rewrite(msgrec);
            if (r) goto doneloop;

            if (modified_flags.added_flags) {
                if (flagsset == NULL)
                    flagsset = mboxevent_enqueue(EVENT_FLAGS_SET, &mboxevents);

                mboxevent_add_flags(flagsset, mailbox->flagname,
                                    modified_flags.added_system_flags,
                                    modified_flags.added_user_flags);
                mboxevent_extract_msgrecord(flagsset, msgrec);
            }
            if (modified_flags.removed_flags) {
                if (flagsclear == NULL)
                    flagsclear = mboxevent_enqueue(EVENT_FLAGS_CLEAR, &mboxevents);

                mboxevent_add_flags(flagsclear, mailbox->flagname,
                                    modified_flags.removed_system_flags,
                                    modified_flags.removed_user_flags);
                mboxevent_extract_msgrecord(flagsclear, msgrec);
            }
            break;

        case STORE_ANNOTATION: {
            int dirty = 0;
            r = index_store_annotation(state, msgno, msgrec, storeargs, &dirty);
            if (r) goto doneloop;
            if (!dirty) goto doneloop;

            // rewrite message
            r = msgrecord_rewrite(msgrec);
            if (r) goto doneloop;

            // XXX mboxevents?

            break;
        }

        default:
            r = IMAP_INTERNAL;
            break;
        }
        if (r) goto doneloop;

        /* msgrecord_rewrite already took care of rewriting the index_record,
         * but we want to stay up to date of the changes in the index_map.
         * Pass the silent flag to index_rewrite_record. */
        r = msgrecord_get_index_record(msgrec, &record);
        if (r) goto doneloop;
        r = index_rewrite_record(state, msgno, &record, /*silent*/1);

doneloop:
        msgrecord_unref(&msgrec);
        if (r) goto out;
    }


    /* let mboxevent_notify split FlagsSet into MessageRead, MessageTrash
     * and FlagsSet events */
    mboxevent_extract_mailbox(flagsset, mailbox);
    mboxevent_set_numunseen(flagsset, mailbox, state->numunseen);
    mboxevent_set_access(flagsset, NULL, NULL, state->userid, state->mailbox->name, 1);

    mboxevent_extract_mailbox(flagsclear, mailbox);
    mboxevent_set_access(flagsclear, NULL, NULL, state->userid, state->mailbox->name, 1);
    mboxevent_set_numunseen(flagsclear, mailbox, state->numunseen);

    mboxevent_notify(&mboxevents);

out:
    mboxevent_freequeue(&mboxevents);
    if (storeargs->operation == STORE_ANNOTATION && r)
        annotate_state_abort(&mailbox->annot_state);
    seqset_free(seq);
    index_unlock(state);
    index_tellchanges(state, storeargs->usinguid, storeargs->usinguid,
                      (storeargs->unchangedsince != ~0ULL));

    return r;
}

static void prefetch_messages(struct index_state *state,
                              struct seqset *seq,
                              int usinguid)
{
    struct mailbox *mailbox = state->mailbox;
    struct index_map *im;
    uint32_t msgno;
    const char *fname;
    struct index_record record;

    syslog(LOG_ERR, "Prefetching initial parts of messages\n");

    for (msgno = 1; msgno <= state->exists; msgno++) {
        im = &state->map[msgno-1];
        if (!seqset_ismember(seq, usinguid ? im->uid : msgno))
            continue;

        if (index_reload_record(state, msgno, &record))
            continue;

        fname = mailbox_record_fname(mailbox, &record);
        if (!fname)
            continue;

        warmup_file(fname, 0, 16384);
    }
}


/*
 * Perform the XRUNANNOTATOR command which runs the
 * annotator callout for each message in the given sequence.
 */
EXPORTED int index_run_annotator(struct index_state *state,
                        const char *sequence, int usinguid,
                        struct namespace *namespace, int isadmin)
{
    struct index_record record;
    struct seqset *seq = NULL;
    struct index_map *im;
    uint32_t msgno;
    struct appendstate as;
    msgrecord_t *msgrec = NULL;
    int r = 0;

    /* We do the acl check here rather than in append_setup_mbox()
     * to account for the EXAMINE command where state->myrights has
     * fewer rights than the ACL actually grants */
    if (!(state->myrights & (ACL_WRITE|ACL_ANNOTATEMSG)))
        return IMAP_PERMISSION_DENIED;

    if (!config_getstring(IMAPOPT_ANNOTATION_CALLOUT))
        return 0;

    r = index_lock(state, /*readonly*/0);
    if (r) return r;

    r = append_setup_mbox(&as, state->mailbox,
                          state->userid, state->authstate,
                          0, NULL, namespace, isadmin, 0);
    if (r) goto out;

    seq = _parse_sequence(state, sequence, usinguid);
    if (!seq) goto out;

    prefetch_messages(state, seq, usinguid);

    for (msgno = 1; msgno <= state->exists; msgno++) {
        im = &state->map[msgno-1];
        if (!seqset_ismember(seq, usinguid ? im->uid : msgno))
            continue;

        /* if it's expunged already, skip it now */
        if ((im->internal_flags & FLAG_INTERNAL_EXPUNGED))
            continue;

        r = index_reload_record(state, msgno, &record);
        if (r) goto out;

        msgrec = msgrecord_from_index_record(state->mailbox, &record);

        r = append_run_annotator(&as, msgrec);
        if (r) goto out;

        /* msgrecord_rewrite already took care of rewriting the index_record,
         * but we want to stay up to date of the changes in the index_map.
         * Pass the silent flag to index_rewrite_record. */
        r = msgrecord_get_index_record(msgrec, &record);
        if (r) goto out;
        r = index_rewrite_record(state, msgno, &record, /*silent*/1);
        if (r) goto out;

        msgrecord_unref(&msgrec);
    }

out:
    seqset_free(seq);

    if (msgrec) msgrecord_unref(&msgrec);
    if (!r) {
        r = append_commit(&as);
    }
    else {
        append_abort(&as);
    }
    index_unlock(state);

    index_tellchanges(state, usinguid, usinguid, 1);

    return r;
}

EXPORTED int index_warmup(struct mboxlist_entry *mbentry,
                          unsigned int warmup_flags,
                          struct seqset *uids)
{
    const char *fname = NULL;
    char *userid = NULL;
    char *tofree1 = NULL;
    char *tofree2 = NULL;
    unsigned int uid;
    strarray_t files = STRARRAY_INITIALIZER;
    int i;
    int r = 0;

    if (warmup_flags & WARMUP_INDEX) {
        fname = mboxname_metapath(mbentry->partition, mbentry->name, mbentry->uniqueid, META_INDEX, 0);
        r = warmup_file(fname, 0, 0);
        if (r) goto out;
    }
    if (warmup_flags & WARMUP_CONVERSATIONS) {
        if (config_getswitch(IMAPOPT_CONVERSATIONS)) {
            fname = tofree1 = conversations_getmboxpath(mbentry->name);
            r = warmup_file(fname, 0, 0);
            if (r) goto out;
        }
    }
    if (warmup_flags & WARMUP_ANNOTATIONS) {
        fname = mboxname_metapath(mbentry->partition, mbentry->name, mbentry->uniqueid, META_ANNOTATIONS, 0);
        r = warmup_file(fname, 0, 0);
        if (r) goto out;
    }
    if (warmup_flags & WARMUP_SEARCH) {
        userid = mboxname_to_userid(mbentry->name);
        r = search_list_files(userid, &files);
        if (r) goto out;
        for (i = 0 ; i < files.count ; i++) {
            fname = strarray_nth(&files, i);
            r = warmup_file(fname, 0, 0);
            if (r) goto out;
        }
    }
    while ((uid = seqset_getnext(uids))) {
        fname = mboxname_datapath(mbentry->partition, mbentry->name, mbentry->uniqueid, uid);
        r = warmup_file(fname, 0, 0);
        if (r) goto out;
    }

out:
    if (r == ENOENT || r == ENOSYS)
        r = 0;
    if (r)
        syslog(LOG_ERR, "IOERROR: unable to warmup file %s: %s",
                fname, error_message(r));
    free(userid);
    free(tofree1);
    free(tofree2);
    strarray_fini(&files);
    return r;
}

static void build_query(search_builder_t *bx,
                        search_expr_t *e,
                        int remove,
                        int *nmatchesp)
{
    search_expr_t *child;
    int bop = -1;

    switch (e->op) {

    case SEOP_NOT:
        bop = SEARCH_OP_NOT;
        break;

    case SEOP_AND:
        bop = SEARCH_OP_AND;
        break;

    case SEOP_OR:
        bop = SEARCH_OP_OR;
        break;

    case SEOP_FUZZYMATCH:
        if (e->attr && e->attr->part >= 0) {
            bx->match(bx, e->attr->part, e->value.s);
            (*nmatchesp)++;
            if (remove && e->attr->part != SEARCH_PART_HEADERS) {
                /*
                 * We're relying on the search engine to correctly
                 * find matching messages, so we don't need to
                 * keep this node in the expression tree anymore.
                 * Rather than remove it we neuter it.
                 */
                search_expr_neutralise(e);
            }
        }
        return;

    default:
        return;
    }

    if (e->children) {
        assert(bop != -1);
        bx->begin_boolean(bx, bop);
        for (child = e->children ; child ; child = child->next)
            build_query(bx, child, remove, nmatchesp);
        bx->end_boolean(bx, bop);
    }
}

static int index_prefilter_messages(unsigned* msg_list,
                                    struct index_state *state,
                                    struct searchargs *searchargs __attribute((unused)))
{
    unsigned int msgno;

    xstats_inc(SEARCH_TRIVIAL);

    /* Just put in all possible messages. This falls back to Cyrus' default
     * search. */

    for (msgno = 1; msgno <= state->exists; msgno++)
        msg_list[msgno-1] = msgno;

    return state->exists;
}

static int index_scan_work(const char *s, unsigned long len,
                           const char *match, unsigned long min)
{
    while (len > min) {
        if (!strncasecmp(s, match, min)) return(1);
        s++;
        len--;
    }
    return(0);
}

/*
 * Guts of the SCAN command, lifted from _index_search()
 *
 * Returns 1 if we get a hit, otherwise returns 0.
 */
EXPORTED int index_scan(struct index_state *state, const char *contents)
{
    unsigned *msgno_list;
    uint32_t msgno;
    int n = 0;
    int listindex;
    int listcount;
    struct searchargs searchargs;
    unsigned long length;
    struct mailbox *mailbox = state->mailbox;
    charset_t ascii = charset_lookupname("US-ASCII");

    if (!(contents && contents[0])) return(0);

    if (index_check(state, 0, 0))
        return 0;

    if (state->exists <= 0) return 0;

    length = strlen(contents);

    memset(&searchargs, 0, sizeof(struct searchargs));
    searchargs.root = search_expr_new(NULL, SEOP_MATCH);
    searchargs.root->attr = search_attr_find("text");

    /* Use US-ASCII to emulate fgrep */

    searchargs.root->value.s = charset_convert(contents, ascii, charset_flags);

    search_expr_internalise(state, searchargs.root);

    msgno_list = (unsigned *) xmalloc(state->exists * sizeof(unsigned));

    listcount = index_prefilter_messages(msgno_list, state, &searchargs);

    for (listindex = 0; !n && listindex < listcount; listindex++) {
        if (!(listindex % 128) && cmd_cancelled(/*insearch*/1))
            break;
        struct buf buf = BUF_INITIALIZER;
        struct index_record record;
        msgno = msgno_list[listindex];

        if (index_reload_record(state, msgno, &record))
            continue;

        if (mailbox_map_record(mailbox, &record, &buf))
            continue;

        n += index_scan_work(buf.s, buf.len, contents, length);

        buf_free(&buf);
    }

    charset_free(&ascii);
    search_expr_free(searchargs.root);
    free(msgno_list);

    return n;
}

EXPORTED uint32_t index_getuid(struct index_state *state, uint32_t msgno)
{
    assert(msgno <= state->exists);
    return state->map[msgno-1].uid;
}

/* 'uid_list' is malloc'd string representing the hits from searchargs;
   returns number of hits */
EXPORTED int index_getuidsequence(struct index_state *state,
                         struct searchargs *searchargs,
                         unsigned **uid_list)
{
    search_query_t *query = NULL;
    search_folder_t *folder = NULL;
    int r;
    int n = 0;

    query = search_query_new(state, searchargs);
    r = search_query_run(query);
    if (r) goto out;
    folder = search_query_find_folder(query, index_mboxname(state));
    if (!folder) goto out;

    n = search_folder_get_array(folder, uid_list);

out:
    search_query_free(query);
    return n;
}

static int index_lock(struct index_state *state, int readonly)
{
    int r;

    if (state->mailbox) {
        if (state->examining || readonly) {
            r = mailbox_lock_index(state->mailbox, LOCK_SHARED);
            if (r) return r;
        }
        else {
            r = mailbox_lock_index(state->mailbox, LOCK_EXCLUSIVE);
            if (r) return r;
        }
    }
    else {
        if (state->examining || readonly) {
            r = mailbox_open_irl(state->mboxname, &state->mailbox);
            if (r) return r;
        }
        else {
            r = mailbox_open_iwl(state->mboxname, &state->mailbox);
            if (r) return r;
        }
    }

    /* if the UIDVALIDITY has changed, treat as a delete */
    if (state->mailbox->i.uidvalidity != state->uidvalidity) {
        mailbox_close(&state->mailbox);
        return IMAP_MAILBOX_NONEXISTENT;
    }

    /* if highestmodseq has changed or file is repacked, read updates */
    if (state->highestmodseq != state->mailbox->i.highestmodseq
        || state->generation != state->mailbox->i.generation_no)
        index_refresh_locked(state);

    return 0;
}

EXPORTED int index_status(struct index_state *state, struct statusdata *sdata)
{
    int r = index_lock(state, /*readonly*/1);
    if (r) return r;

    status_fill_mailbox(state->mailbox, sdata);
    status_fill_seen(state->userid, sdata, state->numrecent, state->numunseen);

    index_unlock(state);
    return 0;
}

EXPORTED int index_refresh(struct index_state *state)
{
    int r;

    r = index_lock(state, /*readonly*/1);  /* calls index_refresh_locked */
    if (r) return r;
    index_unlock(state);
    return 0;
}

static void index_unlock(struct index_state *state)
{
    // only update seen if we've got a writelocked mailbox
    if (mailbox_index_islocked(state->mailbox, 1))
        index_writeseen(state);  // XXX: errors?

    /* grab the latest modseq */
    state->highestmodseq = state->mailbox->i.highestmodseq;

    if (state->mailbox->i.dirty) {
        struct statusdata sdata = STATUSDATA_INIT;
        status_fill_mailbox(state->mailbox, &sdata);
        // we zero out recent data for everyone else
        status_fill_seen(state->userid, &sdata, /*recent*/0, state->numunseen);
        mailbox_unlock_index(state->mailbox, &sdata);
    }
    else {
        mailbox_unlock_index(state->mailbox, NULL);
    }
}

/*
 * RFC 4551 says:
 * If client specifies a MODSEQ criterion in a SEARCH command
 * and the server returns a non-empty SEARCH result, the server
 * MUST also append (to the end of the untagged SEARCH response)
 * the highest mod-sequence for all messages being returned.
 */
static int needs_modseq(const struct searchargs *searchargs,
                        const struct sortcrit *sortcrit)
{
    int i;

    if (search_expr_uses_attr(searchargs->root, "modseq"))
        return 1;

    if (sortcrit) {
        for (i = 0 ; sortcrit[i].key != SORT_SEQUENCE ; i++)
            if (sortcrit[i].key == SORT_MODSEQ)
                return 1;
    }

    return 0;
}

/*
 * Performs a SEARCH command.
 * This is a wrapper around the search_query API which simply prints the results.
 */
EXPORTED int index_search(struct index_state *state,
                          struct searchargs *searchargs,
                          int usinguid)
{
    search_query_t *query = NULL;
    search_folder_t *folder;
    int nmsg = 0;
    int i;
    modseq_t highestmodseq = 0;
    int r;

    /* update the index */
    if (index_check(state, 0, 0))
        return 0;

    highestmodseq = needs_modseq(searchargs, NULL);

    query = search_query_new(state, searchargs);
    r = search_query_run(query);
    if (r) goto out;        /* search failed */
    folder = search_query_find_folder(query, index_mboxname(state));

    if (folder) {
        if (!usinguid)
            search_folder_use_msn(folder, state);
        if (highestmodseq)
            highestmodseq = search_folder_get_highest_modseq(folder);
        nmsg = search_folder_get_count(folder);
    }
    else
        nmsg = 0;

    if (searchargs->returnopts) {
        /*
         * Implement RFC 4731 return options.
         */
        prot_printf(state->out, "* ESEARCH");
        if (searchargs->tag) {
            prot_printf(state->out, " (TAG \"%s\")", searchargs->tag);
        }
        /* RFC4731: 3.1
         * An extended UID SEARCH command MUST cause an ESEARCH response with
         * the UID indicator present. */
        if (usinguid) prot_printf(state->out, " UID");
        if (nmsg) {
            if (searchargs->returnopts & SEARCH_RETURN_MIN) {
                prot_printf(state->out, " MIN %u", search_folder_get_min(folder));
                if (highestmodseq && searchargs->returnopts == SEARCH_RETURN_MIN)
                     highestmodseq = search_folder_get_first_modseq(folder);
            }
            if (searchargs->returnopts & SEARCH_RETURN_MAX) {
                prot_printf(state->out, " MAX %u", search_folder_get_max(folder));
                if (highestmodseq && searchargs->returnopts == SEARCH_RETURN_MAX)
                     highestmodseq = search_folder_get_last_modseq(folder);
            }
            if (highestmodseq && searchargs->returnopts == (SEARCH_RETURN_MIN|SEARCH_RETURN_MAX)) {
                /* special case min and max should be greatest of the two */
                uint64_t last = search_folder_get_last_modseq(folder);
                highestmodseq = search_folder_get_first_modseq(folder);
                if (last > highestmodseq) highestmodseq = last;
            }
            if (searchargs->returnopts & SEARCH_RETURN_ALL) {
                struct seqset *seq = search_folder_get_seqset(folder);

                if (seq->len) {
                    char *str = seqset_cstring(seq);
                    prot_printf(state->out, " ALL %s", str);
                    free(str);
                }

                seqset_free(seq);
            }
            if (searchargs->returnopts & SEARCH_RETURN_RELEVANCY) {
                prot_printf(state->out, " RELEVANCY (");
                for (i = 0; i < nmsg; i++) {
                    if (i) prot_putc(' ', state->out);
                    /* for now all messages have relevancy=100 */
                    prot_printf(state->out, "%u", 100);
                }
                prot_printf(state->out, ")");
            }
            if (highestmodseq)
                prot_printf(state->out, " MODSEQ " MODSEQ_FMT, highestmodseq);
        }
        if (searchargs->returnopts & SEARCH_RETURN_COUNT) {
            prot_printf(state->out, " COUNT %u", nmsg);
        }
    }
    else {
        prot_printf(state->out, "* SEARCH");

        if (nmsg) {
            search_folder_foreach(folder, i) {
                prot_printf(state->out, " %u", i);
            }
        }

        if (highestmodseq)
            prot_printf(state->out, " (MODSEQ " MODSEQ_FMT ")", highestmodseq);
    }

    prot_printf(state->out, "\r\n");

out:
    search_query_free(query);
    return nmsg;
}

/*
 * Performs a SORT command
 */
EXPORTED int index_sort(struct index_state *state,
               const struct sortcrit *sortcrit,
               struct searchargs *searchargs, int usinguid)
{
    int i;
    int nmsg = 0;
    modseq_t highestmodseq = 0;
    search_query_t *query = NULL;
    search_folder_t *folder = NULL;
    int r;

    /* update the index */
    if (index_check(state, 0, 0))
        return 0;

    highestmodseq = needs_modseq(searchargs, NULL);

    /* Search for messages based on the given criteria */
    query = search_query_new(state, searchargs);
    query->sortcrit = sortcrit;
    r = search_query_run(query);
    if (r) goto out;        /* search failed */
    folder = search_query_find_folder(query, index_mboxname(state));

    if (folder) {
        if (highestmodseq)
            highestmodseq = search_folder_get_highest_modseq(folder);
        nmsg = search_folder_get_count(folder);
    }

    prot_printf(state->out, "* SORT");

    if (nmsg) {
        /* Output the sorted messages */
        for (i = 0 ; i < query->merged_msgdata.count ; i++) {
            MsgData *md = ptrarray_nth(&query->merged_msgdata, i);
            prot_printf(state->out, " %u",
                        (usinguid ? md->uid : md->msgno));
        }
    }

    if (highestmodseq)
        prot_printf(state->out, " (MODSEQ " MODSEQ_FMT ")", highestmodseq);

    prot_printf(state->out, "\r\n");

out:
    search_query_free(query);
    return nmsg;
}

#define UNPREDICTABLE       (-1)
static int search_predict_total(struct index_state *state,
                                struct conversations_state *cstate,
                                const struct searchargs *searchargs,
                                int conversations,
                                modseq_t *xconvmodseqp)
{
    conv_status_t convstatus = CONV_STATUS_INIT;
    uint32_t exists;

    if (conversations) {
        conversation_getstatus(cstate, index_mboxname(state), &convstatus);
        /* always grab xconvmodseq, so we report a growing
         * highestmodseq to all callers */
        if (xconvmodseqp) *xconvmodseqp = convstatus.threadmodseq;
        exists = convstatus.threadexists;
    }
    else {
        if (xconvmodseqp) *xconvmodseqp = state->highestmodseq;
        /* we may be in xconvupdates, where expunged are present */
        exists = state->exists - state->num_expunged;
    }

    switch (search_expr_get_countability(searchargs->root)) {
    case SEC_EXISTS:
        return exists;

    case SEC_EXISTS|SEC_NOT:
        return 0;

    /* we don't try to optimise searches on \Recent */
    case SEC_SEEN:
        assert(state->exists >= state->numunseen);
        return state->exists - state->numunseen;

    case SEC_SEEN|SEC_NOT:
        return state->numunseen;

    case SEC_CONVSEEN:
        assert(conversations);
        assert(convstatus.threadexists >= convstatus.threadunseen);
        return convstatus.threadexists - convstatus.threadunseen;

    case SEC_CONVSEEN|SEC_NOT:
        assert(conversations);
        return convstatus.threadunseen;

    default:
        return UNPREDICTABLE;
    }
}

/*
 * Performs a XCONVSORT command
 */
EXPORTED int index_convsort(struct index_state *state,
                            struct sortcrit *sortcrit,
                            struct searchargs *searchargs,
                            const struct windowargs *windowargs)
{
    MsgData **msgdata = NULL;
    unsigned int mi;
    modseq_t xconvmodseq = 0;
    int i;
    hashu64_table seen_cids = HASHU64_TABLE_INITIALIZER;
    uint32_t pos = 0;
    int found_anchor = 0;
    uint32_t anchor_pos = 0;
    uint32_t first_pos = 0;
    unsigned int ninwindow = 0;
    ptrarray_t results = PTRARRAY_INITIALIZER;
    int total = 0;
    int r = 0;
    struct conversations_state *cstate = NULL;

    assert(windowargs);
    assert(!windowargs->changedsince);
    assert(!windowargs->upto);

    /* Check the client didn't specify MULTIANCHOR. */
    if (windowargs->anchor && windowargs->anchorfolder)
        return IMAP_PROTOCOL_BAD_PARAMETERS;

    /* make sure \Deleted messages are expunged.  Will also lock the
     * mailbox state and read any new information */
    r = index_expunge(state, NULL, 1);
    if (r) return r;

    if (windowargs->conversations) {
        cstate = conversations_get_mbox(index_mboxname(state));
        if (!cstate)
            return IMAP_INTERNAL;
    }

    search_expr_internalise(state, searchargs->root);

    /* this works both with and without conversations */
    total = search_predict_total(state, cstate, searchargs,
                                windowargs->conversations,
                                &xconvmodseq);
    /* not going to match anything? bonus */
    if (!total)
        goto out;

    construct_hashu64_table(&seen_cids, state->exists/4+4, 0);

    /* Create/load the msgdata array.
     * load data for ALL messages always.  We sort before searching so
     * we can take advantage of the window arguments to stop searching
     * early */
    msgdata = index_msgdata_load(state, NULL, state->exists, sortcrit,
                                 windowargs->anchor, &found_anchor);
    if (windowargs->anchor && !found_anchor) {
        r = IMAP_ANCHOR_NOT_FOUND;
        goto out;
    }

    /* Sort the messages based on the given criteria */
    index_msgdata_sort(msgdata, state->exists, sortcrit);

    /* One pass through the message list */
    for (mi = 0 ; mi < state->exists ; mi++) {
        MsgData *msg = msgdata[mi];
        struct index_map *im = &state->map[msg->msgno-1];

        /* can happen if we didn't "tellchanges" yet */
        if (im->internal_flags & FLAG_INTERNAL_EXPUNGED)
            continue;

        /* run the search program against all messages */
        if (!index_search_evaluate(state, searchargs->root, msg->msgno))
            continue;

        /* figure out whether this message is an exemplar */
        if (windowargs->conversations) {
            /* in conversations mode => only the first message seen
             * with each unique CID is an exemplar */
            if (hashu64_lookup(msg->cid, &seen_cids))
                continue;
            hashu64_insert(msg->cid, (void *)1, &seen_cids);
        }
        /* else not in conversations mode => all messages are exemplars */

        pos++;

        if (!anchor_pos &&
            windowargs->anchor == msg->uid) {
            /* we've found the anchor's position, rejoice! */
            anchor_pos = pos;
        }

        if (windowargs->anchor) {
            if (!anchor_pos)
                continue;
            if (pos < anchor_pos + windowargs->offset)
                continue;
        }
        else if (windowargs->position) {
            if (pos < windowargs->position)
                continue;
        }
        if (windowargs->limit &&
            ++ninwindow > windowargs->limit) {
            if (total == UNPREDICTABLE) {
                /* the total was not predictable, so we need to keep
                 * going over the whole list to count it */
                continue;
            }
            break;
        }

        if (!first_pos)
            first_pos = pos;
        ptrarray_append(&results, msg);
    }

    if (total == UNPREDICTABLE) {
        /* the total was not predictable prima facie */
        total = pos;
    }

    if (windowargs->anchor && !anchor_pos) {
        /* the anchor was present but not an exemplar */
        assert(results.count == 0);
        r = IMAP_ANCHOR_NOT_FOUND;
        goto out;
    }

    /* Print the resulting list */

    /* Yes, we could use a seqset here, but apparently the most common
     * sort order seen in the field is reverse date, which is basically
     * the worst case for seqset.  So we don't bother */
    if (results.count) {
        prot_printf(state->out, "* SORT");  /* uids */
        for (i = 0 ; i < results.count ; i++) {
            MsgData *msg = results.data[i];
            prot_printf(state->out, " %u", msg->uid);
        }
        prot_printf(state->out, "\r\n");
    }

out:
    if (!r) {
        if (first_pos)
            prot_printf(state->out, "* OK [POSITION %u]\r\n", first_pos);

        prot_printf(state->out, "* OK [HIGHESTMODSEQ " MODSEQ_FMT "]\r\n",
                    MAX(xconvmodseq, state->mailbox->i.highestmodseq));
        prot_printf(state->out, "* OK [UIDVALIDITY %u]\r\n",
                    state->mailbox->i.uidvalidity);
        prot_printf(state->out, "* OK [UIDNEXT %u]\r\n",
                    state->mailbox->i.last_uid + 1);
        prot_printf(state->out, "* OK [TOTAL %u]\r\n",
                    total);
    }

    /* free all our temporary data */
    index_msgdata_free(msgdata, state->exists);
    ptrarray_fini(&results);
    free_hashu64_table(&seen_cids, NULL);

    return r;
}

/*
 * Performs a XCONVMULTISORT command
 */
EXPORTED int index_convmultisort(struct index_state *state,
                                 struct sortcrit *sortcrit,
                                 struct searchargs *searchargs,
                                 const struct windowargs *windowargs)
{
    int mi;
    int fi;
    int i;
    hashu64_table seen_cids = HASHU64_TABLE_INITIALIZER;
    uint32_t pos = 0;
    uint32_t anchor_pos = 0;
    uint32_t first_pos = 0;
    unsigned int ninwindow = 0;
    /* array of (arrays of msgdata* with the same CID) */
    ptrarray_t results = PTRARRAY_INITIALIZER;
    /* Used as a placeholder which provides a non-NULL entry in the
     * seen_cids hashtable for conversations which are outside the
     * specified window. */
    ptrarray_t dummy_response;
    int total = UNPREDICTABLE;
    int r = 0;
    struct mboxname_counters counters;
    search_query_t *query = NULL;
    search_folder_t *folder = NULL;
    search_folder_t *anchor_folder = NULL;

    assert(windowargs);
    assert(!windowargs->changedsince);
    assert(!windowargs->upto);

    /* Client needs to have specified MULTIANCHOR which includes
     * the folder name instead of just ANCHOR.  Check that here
     * 'cos it's easier than doing so during parsing */
    if (windowargs->anchor && !windowargs->anchorfolder)
        return IMAP_PROTOCOL_BAD_PARAMETERS;

    /* make sure folder still exists and map in data */
    r = index_refresh(state);
    if (r) return r;

    r = mboxname_read_counters(index_mboxname(state), &counters);
    if (r) return r;
    query = search_query_new(state, searchargs);
    query->multiple = 1;
    query->need_ids = 1;
    query->need_expunge = 1;
    query->sortcrit = sortcrit;

    r = search_query_run(query);
    if (r) return r;

    if (windowargs->anchorfolder) {
        anchor_folder = search_query_find_folder(query, windowargs->anchorfolder);
        if (!anchor_folder) {
            r = IMAP_ANCHOR_NOT_FOUND;
            goto out;
        }
    }

    /* going to need to do conversation-level breakdown */
    if (windowargs->conversations)
        construct_hashu64_table(&seen_cids, query->merged_msgdata.count/4+4, 0);
    /* no need */
    else
        total = query->merged_msgdata.count;

    /* Another pass through the merged message list */
    for (mi = 0 ; mi < query->merged_msgdata.count ; mi++) {
        MsgData *md = ptrarray_nth(&query->merged_msgdata, mi);
        ptrarray_t *response = NULL;

        /* figure out whether this message is an exemplar */
        if (windowargs->conversations) {
            response = hashu64_lookup(md->cid, &seen_cids);
            /* in conversations mode => only the first message seen
             * with each unique CID is an exemplar */
            if (response) {
                if (response != &dummy_response)
                    ptrarray_append(response, md);
                continue;
            }
            hashu64_insert(md->cid, &dummy_response, &seen_cids);
        }
        /* else not in conversations mode => all messages are exemplars */

        pos++;

        if (!anchor_pos &&
            windowargs->anchor == md->uid &&
            anchor_folder == md->folder) {
            /* we've found the anchor's position, rejoice! */
            anchor_pos = pos;
        }

        if (windowargs->anchor) {
            if (!anchor_pos)
                continue;
            if (pos < anchor_pos + windowargs->offset)
                continue;
        }
        else if (windowargs->position) {
            if (pos < windowargs->position)
                continue;
        }
        if (windowargs->limit &&
            ++ninwindow > windowargs->limit) {
            if (total == UNPREDICTABLE) {
                /* the total was not predictable, so we need to keep
                 * going over the whole list to count it */
                continue;
            }
            break;
        }

        if (!first_pos)
            first_pos = pos;

        /* the message is the exemplar of a conversation which is inside
         * the specified window, so record a non-dummy seen_cids entry
         * and a results entry */
        response = ptrarray_new();
        ptrarray_push(response, md);
        ptrarray_push(&results, response);

        if (windowargs->conversations) {
            hashu64_insert(md->cid, response, &seen_cids);
        }
    }

    if (total == UNPREDICTABLE) {
        /* the total was not predictable prima facie */
        total = pos;
    }

    if (windowargs->anchor && !anchor_pos) {
        /* the anchor was not found */
        assert(results.count == 0);
        r = IMAP_ANCHOR_NOT_FOUND;
        goto out;
    }

    /* Print the resulting list */

    xstats_add(SEARCH_RESULT, results.count);
    if (results.count) {
        /* The untagged response would be XCONVMULTISORT but
         * Mail::IMAPTalk has an undocumented hack whereby any untagged
         * response matching /sort/i is assumed to be a sequence of
         * numeric uids.  Meh. */
        prot_printf(state->out, "* XCONVMULTI (");
        for (fi = 0 ; fi < query->folders_by_id.count ; fi++) {
            folder = ptrarray_nth(&query->folders_by_id, fi);

            char *extname = mboxname_to_external(folder->mboxname, searchargs->namespace, searchargs->userid);

            if (fi)
                prot_printf(state->out, " ");
            prot_printf(state->out, "(");
            prot_printstring(state->out, extname);
            prot_printf(state->out, " %u)", folder->uidvalidity);
            free(extname);
        }
        prot_printf(state->out, ") (");
        for (i = 0 ; i < results.count ; i++) {
            ptrarray_t *response = ptrarray_nth(&results, i);
            int j;
            if (i)
                prot_printf(state->out, " ");
            for (j = 0; j < response->count; j++) {
                MsgData *md = ptrarray_nth(response, j);
                if (!j)
                    prot_printf(state->out, "(%s" , conversation_id_encode(md->cid));
                prot_printf(state->out, " (%u %u)", md->folder->id, md->uid);
            }
            prot_printf(state->out, ")");
        }
        prot_printf(state->out, ")\r\n");
    }

out:
    if (!r) {
        if (first_pos)
            prot_printf(state->out, "* OK [POSITION %u]\r\n", first_pos);

        prot_printf(state->out, "* OK [HIGHESTMODSEQ " MODSEQ_FMT "]\r\n",
                    counters.mailmodseq);
#if 0
        prot_printf(state->out, "* OK [UIDNEXT %u]\r\n",
                    state->mailbox->i.last_uid + 1);
#endif
        prot_printf(state->out, "* OK [TOTAL %u]\r\n",
                    total);
    }

    /* free all our temporary data */
    free_hashu64_table(&seen_cids, NULL);
    for (i = 0 ; i < results.count ; i++) {
        ptrarray_t *response = ptrarray_nth(&results, i);
        ptrarray_free(response);
    }
    ptrarray_fini(&results);
    search_query_free(query);

    return r;
}

struct snippet_rock {
    struct protstream *out;
    struct namespace *namespace;
    const char *userid;
};

static int emit_snippet(struct mailbox *mailbox, uint32_t uid,
                        int part, const char *snippet, void *rock)
{
    struct snippet_rock *sr = (struct snippet_rock *)rock;
    const char *partname = search_part_as_string(part);

    if (!partname) return 0;

    char *extname = mboxname_to_external(mailbox->name, sr->namespace, sr->userid);

    prot_printf(sr->out, "* SNIPPET ");
    prot_printstring(sr->out, extname);
    prot_printf(sr->out, " %u %u %s ", mailbox->i.uidvalidity, uid, partname);
    prot_printstring(sr->out, snippet);
    prot_printf(sr->out, "\r\n");

    free(extname);

    return 0;
}

EXPORTED int index_snippets(struct index_state *state,
                            const struct snippetargs *snippetargs,
                            struct searchargs *searchargs)
{
    void *intquery = NULL;
    search_builder_t *bx = NULL;
    search_text_receiver_t *rx = NULL;
    struct mailbox *mailbox = NULL;
    int i;
    int r = 0;
    int nmatches = 0;
    struct snippet_rock srock;

    /* reload index */
    r = index_refresh(state);
    if (r) return r;

    bx = search_begin_search(state->mailbox, SEARCH_MULTIPLE);
    if (!bx) {
        r = IMAP_INTERNAL;
        goto out;
    }

    build_query(bx, searchargs->root, 0, &nmatches);
    if (!bx->get_internalised) goto out;
    intquery = bx->get_internalised(bx);
    search_end_search(bx);
    if (!intquery) goto out;

    srock.out = state->out;
    srock.namespace = searchargs->namespace;
    srock.userid = searchargs->userid;
    rx = search_begin_snippets(intquery, 0/*verbose*/, &default_snippet_markup,
                               emit_snippet, &srock);
    if (!rx) goto out;

    for ( ; snippetargs ; snippetargs = snippetargs->next) {

        mailbox = NULL;
        if (!strcmp(snippetargs->mboxname, index_mboxname(state))) {
            mailbox = state->mailbox;
        }
        else {
            r = mailbox_open_irl(snippetargs->mboxname, &mailbox);
            if (r) goto out;
            mailbox_unlock_index(mailbox, NULL);
        }

        if (snippetargs->uidvalidity &&
            snippetargs->uidvalidity != mailbox->i.uidvalidity) {
            r = IMAP_NOTFOUND;
            goto out;
        }

        r = rx->begin_mailbox(rx, mailbox, /*incremental*/0);

        for (i = 0 ; i < snippetargs->uids.count ; i++) {
            uint32_t uid = snippetargs->uids.data[i];
            struct index_record record;

            /* It's OK to do a dirty read, because we only care about
             * the UID of the message */
            r = mailbox_find_index_record(mailbox, uid, &record);
            if (r == IMAP_MAILBOX_CHECKSUM) r = 0;
            if (r) continue;

            if (state->m) message_set_from_record(mailbox, &record, state->m);
            else state->m = message_new_from_record(mailbox, &record);

            index_getsearchtext(state->m, NULL, rx, /*snippet*/1);
        }

        r = rx->end_mailbox(rx, mailbox);
        if (r) goto out;
        if (mailbox != state->mailbox)
            mailbox_close(&mailbox);
    }

out:
    if (rx) search_end_snippets(rx);
    if (intquery) search_free_internalised(intquery);
    if (mailbox != state->mailbox)
        mailbox_close(&mailbox);
    return r;
}

static modseq_t get_modseq_of(MsgData *msg,
                              struct conversations_state *cstate)
{
    modseq_t modseq = 0;

    if (cstate) {
        conversation_get_modseq(cstate, msg->cid, &modseq);
        /* TODO: error handling dammit */
    } else {
        modseq = msg->modseq;
    }
    return modseq;
}

/*
 * Performs a XCONVUPDATES command
 */
EXPORTED int index_convupdates(struct index_state *state,
                      struct sortcrit *sortcrit,
                      struct searchargs *searchargs,
                      const struct windowargs *windowargs)
{
    MsgData **msgdata = NULL;
    modseq_t xconvmodseq = 0;
    unsigned int mi;
    int i;
    hashu64_table seen_cids = HASHU64_TABLE_INITIALIZER;
    hashu64_table old_seen_cids = HASHU64_TABLE_INITIALIZER;
    int32_t pos = 0;
    uint32_t upto_pos = 0;
    ptrarray_t added = PTRARRAY_INITIALIZER;
    ptrarray_t removed = PTRARRAY_INITIALIZER;
    ptrarray_t changed = PTRARRAY_INITIALIZER;
    int total = 0;
    struct conversations_state *cstate = NULL;
    int is_mutable = search_is_mutable(sortcrit, searchargs->root);
    int r = 0;

    assert(windowargs);
    assert(windowargs->changedsince);
    assert(windowargs->offset == 0);
    assert(!windowargs->position);

    /* make sure \Deleted messages are expunged.  Will also lock the
     * mailbox state and read any new information */
    r = index_expunge(state, NULL, 1);
    if (r) return r;

    if (windowargs->conversations) {
        cstate = conversations_get_mbox(index_mboxname(state));
        if (!cstate)
            return IMAP_INTERNAL;
    }

    search_expr_internalise(state, searchargs->root);

    total = search_predict_total(state, cstate, searchargs,
                                windowargs->conversations,
                                &xconvmodseq);
    /* If there are no current and no expunged messages, we won't
     * have any results at all and can short circuit the main loop;
     * note that is a righter criterion than for XCONVSORT. */
    if (!total && !state->exists)
        goto out;

    construct_hashu64_table(&seen_cids, state->exists/4+4, 0);
    construct_hashu64_table(&old_seen_cids, state->exists/4+4, 0);

    /* Create/load the msgdata array
     * initial list - load data for ALL messages always */
    msgdata = index_msgdata_load(state, NULL, state->exists, sortcrit, 0, NULL);

    /* Sort the messages based on the given criteria */
    index_msgdata_sort(msgdata, state->exists, sortcrit);

    /* Discover exemplars */
    for (mi = 0 ; mi < state->exists ; mi++) {
        MsgData *msg = msgdata[mi];
        struct index_map *im = &state->map[msg->msgno-1];
        int was_old_exemplar = 0;
        int is_new_exemplar = 0;
        int is_deleted = 0;
        int is_new = 0;
        int was_deleted = 0;
        int is_changed = 0;
        int in_search = 0;

        in_search = index_search_evaluate(state, searchargs->root, msg->msgno);
        is_deleted = !!(im->internal_flags & FLAG_INTERNAL_EXPUNGED);
        is_new = (im->uid >= windowargs->uidnext);
        was_deleted = is_deleted && (im->modseq <= windowargs->modseq);

        /* is this message a current exemplar? */
        if (!is_deleted &&
            in_search &&
            (!windowargs->conversations || !hashu64_lookup(msg->cid, &seen_cids))) {
            is_new_exemplar = 1;
            pos++;
            if (windowargs->conversations)
                hashu64_insert(msg->cid, (void *)1, &seen_cids);
        }

        /* optimisation for when the total is
         * not known but we've hit 'upto' */
        if (upto_pos)
            continue;

        modseq_t modseq = get_modseq_of(msg, cstate);
        is_changed = (modseq > windowargs->modseq);

        /* was this message an old exemplar, or in the case of mutable
         * searches, possible an old exemplar? */
        if (!is_new &&
            !was_deleted &&
            (in_search || (is_mutable && is_changed)) &&
            (!windowargs->conversations || !hashu64_lookup(msg->cid, &old_seen_cids))) {
            was_old_exemplar = 1;
            if (windowargs->conversations)
                hashu64_insert(msg->cid, (void *)1, &old_seen_cids);
        }

        if (was_old_exemplar && !is_new_exemplar) {
            ptrarray_push(&removed, msg);
        } else if (!was_old_exemplar && is_new_exemplar) {
            msg->msgno = pos;   /* hacky: reuse ->msgno for pos */
            ptrarray_push(&added, msg);
        } else if (was_old_exemplar && is_new_exemplar) {
            if (is_changed) {
                ptrarray_push(&changed, msg);
                if (is_mutable) {
                    /* is the search is mutable, we're in a whole world of
                     * uncertainty about the client's state, so we just
                     * report the exemplar in all three lists and let the
                     * client sort it out. */
                    ptrarray_push(&removed, msg);
                    msg->msgno = pos;   /* hacky: reuse ->msgno for pos */
                    ptrarray_push(&added, msg);
                }
            }
        }

        /* if this is the last message the client cares about ('upto')
         * then we can break early...unless its a mutable search or
         * we need to keep going to calculate an accurate total */
        if (!is_mutable &&
            !upto_pos &&
            msg->uid == windowargs->upto) {
            if (total != UNPREDICTABLE)
                break;
            upto_pos = pos;
        }
    }

    /* unlike 'anchor', the case of not finding 'upto' is not an error */

    if (total == UNPREDICTABLE) {
        /* the total was not predictable prima facie */
        total = pos;
    }

    /* Print the resulting lists */

    if (added.count) {
        prot_printf(state->out, "* ADDED"); /* (uid pos) tuples */
        for (i = 0 ; i < added.count ; i++) {
            MsgData *msg = added.data[i];
            prot_printf(state->out, " (%u %u)",
                        msg->uid, msg->msgno);
        }
        prot_printf(state->out, "\r\n");
    }

    if (removed.count) {
        prot_printf(state->out, "* REMOVED");   /* uids */
        for (i = 0 ; i < removed.count ; i++) {
            MsgData *msg = removed.data[i];
            prot_printf(state->out, " %u", msg->uid);
        }
        prot_printf(state->out, "\r\n");
    }

    if (changed.count) {
        prot_printf(state->out, "* CHANGED");   /* cids or uids */
        for (i = 0 ; i < changed.count ; i++) {
            MsgData *msg = changed.data[i];
            if (windowargs->conversations)
                prot_printf(state->out, " %s",
                        conversation_id_encode(msg->cid));
            else
                prot_printf(state->out, " %u", msg->uid);
        }
        prot_printf(state->out, "\r\n");
    }

out:
    if (!r) {
        prot_printf(state->out, "* OK [HIGHESTMODSEQ " MODSEQ_FMT "]\r\n",
                    MAX(xconvmodseq, state->mailbox->i.highestmodseq));
        prot_printf(state->out, "* OK [UIDVALIDITY %u]\r\n",
                    state->mailbox->i.uidvalidity);
        prot_printf(state->out, "* OK [UIDNEXT %u]\r\n",
                    state->mailbox->i.last_uid + 1);
        prot_printf(state->out, "* OK [TOTAL %u]\r\n",
                    total);
    }

    /* free all our temporary data */
    index_msgdata_free(msgdata, state->exists);
    ptrarray_fini(&added);
    ptrarray_fini(&removed);
    ptrarray_fini(&changed);
    free_hashu64_table(&seen_cids, NULL);
    free_hashu64_table(&old_seen_cids, NULL);

    return r;
}

/*
 * Performs a THREAD command
 */
EXPORTED int index_thread(struct index_state *state, int algorithm,
                 struct searchargs *searchargs, int usinguid)
{
    search_query_t *query = NULL;
    search_folder_t *folder;
    unsigned *msgno_list;
    int nmsg = 0;
    clock_t start;
    modseq_t highestmodseq = 0;
    int r;

    /* update the index */
    if (index_check(state, 0, 0))
        return 0;

    highestmodseq = needs_modseq(searchargs, NULL);

    if(CONFIG_TIMING_VERBOSE)
        start = clock();

    /* Search for messages based on the given criteria */
    query = search_query_new(state, searchargs);
    r = search_query_run(query);
    if (r) goto out;        /* search failed */
    folder = search_query_find_folder(query, index_mboxname(state));

    if (folder) {
        search_folder_use_msn(folder, state);
        if (highestmodseq)
            highestmodseq = search_folder_get_highest_modseq(folder);
        nmsg = search_folder_get_array(folder, &msgno_list);
    }

    if (nmsg) {
        /* Thread messages using given algorithm */
        (*thread_algs[algorithm].threader)(state, msgno_list, nmsg, usinguid);

        free(msgno_list);

        if (highestmodseq)
            prot_printf(state->out, " (MODSEQ " MODSEQ_FMT ")", highestmodseq);
    }

    /* print an empty untagged response */
    else
        index_thread_print(state, NULL, usinguid);

    prot_printf(state->out, "\r\n");

    if (CONFIG_TIMING_VERBOSE) {
        /* debug */
        syslog(LOG_DEBUG, "THREAD %s processing time: %d msg in %f sec",
               thread_algs[algorithm].alg_name, nmsg,
               (clock() - start) / (double) CLOCKS_PER_SEC);
    }

out:
    search_query_free(query);
    return nmsg;
}

/*
 * Performs a COPY command
 */
EXPORTED int
index_copy(struct index_state *state,
           char *sequence,
           int usinguid,
           char *name,
           char **copyuidp,
           int nolink,
           struct namespace *namespace,
           int isadmin,
           int ismove,
           int ignorequota)
{
    struct copyargs copyargs;
    int i;
    quota_t qdiffs[QUOTA_NUMRESOURCES] = QUOTA_DIFFS_INITIALIZER;
    quota_t *qptr = NULL;
    int r;
    struct appendstate appendstate;
    uint32_t msgno, checkval;
    long docopyuid;
    struct seqset *seq;
    struct mailbox *srcmailbox = NULL;
    struct mailbox *destmailbox = NULL;
    struct index_map *im;
    int is_same_user;
    ptrarray_t *msgrecs = ptrarray_new();

    *copyuidp = NULL;

    memset(&copyargs, 0, sizeof(struct copyargs));

    /* let's just see how common this is... */
    if (!strcmp(index_mboxname(state), name))
        syslog(LOG_NOTICE, "same mailbox copy %s (%s)", name, sequence);

    is_same_user = mboxname_same_userid(index_mboxname(state), name);
    if (is_same_user < 0)
        return is_same_user;

    r = index_check(state, usinguid, usinguid);
    if (r) return r;

    srcmailbox = state->mailbox;

    seq = _parse_sequence(state, sequence, usinguid);

    for (msgno = 1; msgno <= state->exists; msgno++) {
        im = &state->map[msgno-1];
        checkval = usinguid ? im->uid : msgno;
        if (!seqset_ismember(seq, checkval))
            continue;
        index_copysetup(state, msgno, &copyargs);
    }

    seqset_free(seq);

    if (copyargs.nummsg == 0) {
        r =  IMAP_NO_NOSUCHMSG;
        goto done;
    }

    r = mailbox_open_iwl(name, &destmailbox);
    if (r) goto done;

    /* make sure copying into this mailbox is enabled */
    r = insert_into_mailbox_allowed(destmailbox);
    if (r) goto done;

    /* not moving or different quota root - need to check quota */
    if (!ismove || strcmpsafe(srcmailbox->quotaroot, destmailbox->quotaroot)) {
        for (i = 0; i < copyargs.nummsg; i++)
            qdiffs[QUOTA_STORAGE] += copyargs.records[i].size;
        qdiffs[QUOTA_MESSAGE] = copyargs.nummsg;
        qptr = qdiffs;
    }

    r = append_setup_mbox(&appendstate, destmailbox, state->userid,
                          state->authstate, ACL_INSERT,
                          ignorequota ? NULL : qptr, namespace, isadmin,
                          ismove ? EVENT_MESSAGE_MOVE : EVENT_MESSAGE_COPY);
    if (r) goto done;

    docopyuid = (appendstate.myrights & ACL_READ);

    for (i = 0; i < copyargs.nummsg; i++) {
        msgrecord_t *mr = msgrecord_from_index_record(srcmailbox, &copyargs.records[i]);
        ptrarray_append(msgrecs, mr);
    }
    r = append_copy(srcmailbox, &appendstate, msgrecs, nolink, is_same_user);
    if (r) {
        append_abort(&appendstate);
        goto done;
    }

    r = append_commit(&appendstate);
    if (r) goto done;

    /* unlock first so we don't hold the lock while expunging
     * the source */
    mailbox_unlock_index(destmailbox, NULL);

    if (docopyuid || ismove) {
        char *source;
        struct seqset *seq;
        unsigned uidvalidity = destmailbox->i.uidvalidity;

        seq = seqset_init(0, SEQ_SPARSE);

        for (i = 0; i < copyargs.nummsg; i++)
            seqset_add(seq, copyargs.records[i].uid, 1);

        source = seqset_cstring(seq);

        /* remove the source messages */
        if (ismove)
            r = index_expunge(state, source, 0);

        if (docopyuid) {
            *copyuidp = xmalloc(strlen(source) + 50);

            if (appendstate.nummsg == 1)
                sprintf(*copyuidp, "%u %s %u", uidvalidity, source,
                        appendstate.baseuid);
            else
                sprintf(*copyuidp, "%u %s %u:%u", uidvalidity, source,
                        appendstate.baseuid,
                        appendstate.baseuid + appendstate.nummsg - 1);
        }

        free(source);
        seqset_free(seq);
    }

    /* we log the first name to get GUID-copy magic */
    if (!r)
        sync_log_mailbox_double(index_mboxname(state), name);

done:
    free(copyargs.records);
    mailbox_close(&destmailbox);
    for (i = 0; i < msgrecs->count; i++) {
        msgrecord_t *mr = ptrarray_nth(msgrecs, i);
        msgrecord_unref(&mr);
    }
    ptrarray_free(msgrecs);

    return r;
}

/*
 * Helper function to multiappend a message to remote mailbox
 */
static int index_appendremote(struct index_state *state, uint32_t msgno,
                              struct protstream *pout)
{
    struct mailbox *mailbox = state->mailbox;
    struct buf buf = BUF_INITIALIZER;
    unsigned flag, flagmask = 0;
    char datebuf[RFC3501_DATETIME_MAX+1];
    char sepchar = '(';
    struct index_record record;
    int r;

    r = index_reload_record(state, msgno, &record);
    if (r) return r;

    /* Open the message file */
    if (mailbox_map_record(mailbox, &record, &buf))
        return IMAP_NO_MSGGONE;

    /* start the individual append */
    prot_printf(pout, " ");

    /* add system flags */
    if (record.system_flags & FLAG_ANSWERED) {
        prot_printf(pout, "%c\\Answered", sepchar);
        sepchar = ' ';
    }
    if (record.system_flags & FLAG_FLAGGED) {
        prot_printf(pout, "%c\\Flagged", sepchar);
        sepchar = ' ';
    }
    if (record.system_flags & FLAG_DRAFT) {
        prot_printf(pout, "%c\\Draft", sepchar);
        sepchar = ' ';
    }
    if (record.system_flags & FLAG_DELETED) {
        prot_printf(pout, "%c\\Deleted", sepchar);
        sepchar = ' ';
    }
    if (record.system_flags & FLAG_SEEN) {
        prot_printf(pout, "%c\\Seen", sepchar);
        sepchar = ' ';
    }

    /* add user flags */
    for (flag = 0; flag < MAX_USER_FLAGS; flag++) {
        if ((flag & 31) == 0) {
            flagmask = record.user_flags[flag/32];
        }
        if (state->flagname[flag] && (flagmask & (1<<(flag & 31)))) {
            prot_printf(pout, "%c%s", sepchar, state->flagname[flag]);
            sepchar = ' ';
        }
    }

    /* add internal date */
    time_to_rfc3501(record.internaldate, datebuf, sizeof(datebuf));
    prot_printf(pout, ") \"%s\" ", datebuf);

    /* message literal */
    index_fetchmsg(state, &buf, 0, record.size, 0, 0);

    /* close the message file */
    buf_free(&buf);

    return 0;
}

/*
 * Performs a COPY command from a local mailbox to a remote mailbox
 */
EXPORTED int index_copy_remote(struct index_state *state, char *sequence,
                      int usinguid, struct protstream *pout)
{
    uint32_t msgno;
    struct seqset *seq;
    struct index_map *im;
    int r;

    r = index_check(state, usinguid, usinguid);
    if (r) return r;

    seq = _parse_sequence(state, sequence, usinguid);

    for (msgno = 1; msgno <= state->exists; msgno++) {
        im = &state->map[msgno-1];
        if (!seqset_ismember(seq, usinguid ? im->uid : msgno))
            continue;
        index_appendremote(state, msgno, pout);
    }

    seqset_free(seq);

    return 0;
}

/*
 * Returns the msgno of the message with UID 'uid'.
 * If no message with UID 'uid', returns the message with
 * the highest UID not greater than 'uid'.
 */
EXPORTED uint32_t index_finduid(struct index_state *state, uint32_t uid)
{
    unsigned low = 1;
    unsigned high = state->exists;
    unsigned mid;
    unsigned miduid;

    while (low <= high) {
        mid = (high - low)/2 + low;
        miduid = index_getuid(state, mid);
        if (miduid == uid)
            return mid;
        else if (miduid > uid)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return high;
}

/* Helper function to determine domain of data */
enum {
    DOMAIN_7BIT = 0,
    DOMAIN_8BIT,
    DOMAIN_BINARY
};

static int data_domain(const char *p, size_t n)
{
    int r = DOMAIN_7BIT;

    while (n--) {
        if (!*p) return DOMAIN_BINARY;
        if (*p & 0x80) r = DOMAIN_8BIT;
        p++;
    }

    return r;
}

/*
 * Helper function to fetch data from a message file.  Writes a
 * quoted-string or literal containing data from 'msg_base', which is
 * of size 'msg_size', starting at 'offset' and containing 'size'
 * octets.  If 'octet_count' is nonzero, the data is
 * further constrained by 'start_octet' and 'octet_count' as per the
 * IMAP command PARTIAL.
 */
void index_fetchmsg(struct index_state *state, const struct buf *msg,
                    unsigned offset,
                    unsigned size,     /* this is the correct size for a news message after
                                          having LF translated to CRLF */
                    unsigned start_octet, unsigned octet_count)
{
    unsigned n, domain;

    /* If no data, output NIL */
    if (!msg || !msg->s) {
        prot_printf(state->out, "NIL");
        return;
    }

    /* partial fetch: adjust 'size' */
    if (octet_count) {
        if (size <= start_octet) {
            size = 0;
        }
        else {
            size -= start_octet;
        }
        if (size > octet_count) size = octet_count;
    }

    /* If zero-length data, output empty quoted string */
    if (size == 0) {
        prot_printf(state->out, "\"\"");
        return;
    }

    /* Seek over PARTIAL constraint */
    offset += start_octet;
    n = size;
    if (offset + size > msg->len) {
        if (msg->len > offset) {
            n = msg->len - offset;
        }
        else {
            prot_printf(state->out, "\"\"");
            return;
        }
    }

    /* Get domain of the data */
    domain = data_domain(msg->s + offset, n);

    if (domain == DOMAIN_BINARY) {
        /* Write size of literal8 */
        prot_printf(state->out, "~{%u}\r\n", size);
    } else {
        /* Write size of literal */
        prot_printf(state->out, "{%u}\r\n", size);
    }

    /* Non-text literal -- tell the protstream about it */
    if (domain != DOMAIN_7BIT) prot_data_boundary(state->out);

    prot_write(state->out, msg->s + offset, n);
    while (n++ < size) {
        /* File too short, resynch client.
         *
         * This can only happen if the reported size of the part
         * is incorrect and would push us past EOF.
         */
        (void)prot_putc(' ', state->out);
    }

    /* End of non-text literal -- tell the protstream about it */
    if (domain != DOMAIN_7BIT) prot_data_boundary(state->out);
}

static int body_is_rfc822(struct body *body)
{
    return body &&
        !strcasecmpsafe(body->type, "MESSAGE") &&
        !strcasecmpsafe(body->subtype, "RFC822");
}

static struct body *find_part(struct body *body, int32_t part)
{
    if (body_is_rfc822(body))
        body = body->subpart;
    else if (!body->numparts)
        return NULL;

    if (body->numparts) {
        /* A multipart */
        if (part >= body->numparts + 1)
            return NULL;
        body = body->subpart + part - 1;
    }
    else {
        /* Every message has at least one part number. */
        if (part > 1)
            return NULL;
    }

    return body;
}

/*
 * Helper function to fetch a body section
 */
static int index_fetchsection(struct index_state *state, const char *resp,
                              const struct buf *inmsg,
                              char *section, struct body *body, unsigned size,
                              unsigned start_octet, unsigned octet_count)
{
    const char *p;
    unsigned offset = 0;
    char *decbuf = NULL;
    struct buf msg = BUF_INITIALIZER;
    struct body *top = body;
    int wantheader = 0;
    int32_t mimenum = 0;
    int r;

    p = section;

    buf_init_ro(&msg, inmsg->s, inmsg->len);

    /* Special-case BODY[] */
    if (*p == ']') {
        if (strstr(resp, "BINARY.SIZE")) {
            prot_printf(state->out, "%s%u", resp, size);
        } else {
            prot_printf(state->out, "%s", resp);
            index_fetchmsg(state, &msg, 0, size,
                           start_octet, octet_count);
        }
        return 0;
    }

    /*
       section         = "[" [section-spec] "]"

       section-msgtext = "HEADER" / "HEADER.FIELDS" [".NOT"] SP header-list /
                         "TEXT"
                    ; top-level or MESSAGE/RFC822 part

       section-part    = nz-number *("." nz-number)
                    ; body part nesting

       section-spec    = section-msgtext / (section-part ["." section-text])

       section-text    = section-msgtext / "MIME"
                    ; text other than actual body part (headers, etc.)
     */

    while (*p != ']') {
        switch (*p) {
        case 'H':
            if (!body_is_rfc822(body)) goto badpart;
            body = body->subpart;
            p += 6;
            wantheader = 1;
            goto emitpart;
        case 'T':
            if (!body_is_rfc822(body)) goto badpart;
            body = body->subpart;
            p += 4;
            goto emitpart;
        case 'M':
            if (body == top) goto badpart;
            p += 4;
            wantheader = 1;
            goto emitpart;
        default:
            mimenum = 0;
            r = parseint32(p, &p, &mimenum);
            if (*p == '.') p++;
            if (r || !mimenum) goto badpart;
            body = find_part(body, mimenum);
            if (!body) goto badpart;
            break;
        }
    }

emitpart:
    if (*p != ']') goto badpart;

    if (wantheader) {
        offset = body->header_offset;
        size = body->header_size;
    }
    else {
        offset = body->content_offset;
        size = body->content_size;
    }

    if (msg.s && !wantheader && (p = strstr(resp, "BINARY"))) {
        /* BINARY or BINARY.SIZE */
        int encoding = body->charset_enc & 0xff;
        size_t newsize;

        /* check that the offset isn't corrupt */
        if (offset + size > msg.len) {
            syslog(LOG_ERR, "invalid part offset in %s", index_mboxname(state));
            return IMAP_IOERROR;
        }

        msg.s = (char *)charset_decode_mimebody(msg.s + offset, size, encoding,
                                                &decbuf, &newsize);

        if (!msg.s) {
            /* failed to decode */
            if (decbuf) free(decbuf);
            return IMAP_NO_UNKNOWN_CTE;
        }
        else if (p[6] == '.') {
            /* BINARY.SIZE */
            prot_printf(state->out, "%s%zd", resp, newsize);
            if (decbuf) free(decbuf);
            return 0;
        }
        else {
            /* BINARY */
            offset = 0;
            size = newsize;
            msg.len = newsize;
        }
    }

    /* Output body part */
    prot_printf(state->out, "%s", resp);
    index_fetchmsg(state, &msg, offset, size,
                   start_octet, octet_count);

    if (decbuf) free(decbuf);
    return 0;

 badpart:
    if (strstr(resp, "BINARY.SIZE"))
        prot_printf(state->out, "%s0", resp);
    else
        prot_printf(state->out, "%sNIL", resp);
    return 0;
}

/*
 * Helper function to fetch a HEADER.FIELDS[.NOT] body section
 */
static void index_fetchfsection(struct index_state *state,
                                const char *msg_base,
                                unsigned long msg_size,
                                struct fieldlist *fsection,
                                struct body *body,
                                unsigned start_octet, unsigned octet_count)
{
    const char *p;
    int32_t mimenum = 0;
    int fields_not = 0;
    const char *crlf = "\r\n";
    unsigned crlf_start = 0;
    unsigned crlf_size = 2;
    char *buf;
    unsigned size;
    int r;

    /* If no data, output null quoted string */
    if (!msg_base) {
        prot_printf(state->out, "\"\"");
        return;
    }

    p = fsection->section;

    while (*p != 'H') {
        r = parseint32(p, &p, &mimenum);
        if (*p == '.') p++;

        if (r || !mimenum) goto badpart;

        body = find_part(body, mimenum);
        if (!body) goto badpart;
    }

    if (body_is_rfc822(body)) body = body->subpart;

    if (!body->header_size) goto badpart;

    if (p[13]) fields_not++;    /* Check for "." after "HEADER.FIELDS" */

    buf = index_readheader(msg_base, msg_size,
                           body->header_offset,
                           body->header_size);

    if (fields_not) {
        message_pruneheader(buf, 0, fsection->fields);
    }
    else {
        message_pruneheader(buf, fsection->fields, 0);
    }
    size = strlen(buf);

    /* partial fetch: adjust 'size' */
    if (octet_count) {
        if (size <= start_octet) {
            crlf_start = start_octet - size;
            size = 0;
            start_octet = 0;
            if (crlf_size <= crlf_start) {
                crlf_size = 0;
            }
            else {
                crlf_size -= crlf_start;
            }
        }
        else {
            size -= start_octet;
        }
        if (size > octet_count) {
            size = octet_count;
            crlf_size = 0;
        }
        else if (size + crlf_size > octet_count) {
            crlf_size = octet_count - size;
        }
    }

    /* If no data, output null quoted string */
    if (size + crlf_size == 0) {
        prot_printf(state->out, "\"\"");
        return;
    }

    /* Write literal */
    prot_printf(state->out, "{%u}\r\n", size + crlf_size);
    prot_write(state->out, buf + start_octet, size);
    prot_write(state->out, crlf + crlf_start, crlf_size);

    return;

 badpart:
    prot_printf(state->out, "NIL");
}

/*
 * Helper function to read a header section into a static buffer
 */
static char *index_readheader(const char *msg_base, unsigned long msg_size,
                              unsigned offset, unsigned size)
{
    static struct buf buf = BUF_INITIALIZER;

    if (offset + size > msg_size) {
        /* Message file is too short, truncate request */
        if (offset < msg_size) {
            size = msg_size - offset;
        }
        else {
            size = 0;
        }
    }

    buf_reset(&buf);
    buf_appendmap(&buf, msg_base+offset, size);
    return (char *)buf_cstring(&buf);
}

/*
 * Handle a FETCH RFC822.HEADER.LINES or RFC822.HEADER.LINES.NOT
 * that can't use the cacheheaders in cyrus.cache
 */
static void index_fetchheader(struct index_state *state,
                              const char *msg_base,
                              unsigned long msg_size,
                              unsigned size,
                              const strarray_t *headers,
                              const strarray_t *headers_not)
{
    char *buf;

    /* If no data, output null quoted string */
    if (!msg_base) {
        prot_printf(state->out, "\"\"");
        return;
    }

    buf = index_readheader(msg_base, msg_size, 0, size);

    message_pruneheader(buf, headers, headers_not);

    size = strlen(buf);
    prot_printf(state->out, "{%u}\r\n%s\r\n", size+2, buf);
}

/*
 * Handle a FETCH RFC822.HEADER.LINES that can use the
 * cacheheaders in cyrus.cache
 */
static void
index_fetchcacheheader(struct index_state *state, struct index_record *record,
                       const strarray_t *headers, unsigned start_octet,
                       unsigned octet_count)
{
    static struct buf buf = BUF_INITIALIZER;
    unsigned size;
    const char *crlf = "\r\n";
    unsigned crlf_start = 0;
    unsigned crlf_size = 2;
    struct mailbox *mailbox = state->mailbox;

    if (mailbox_cacherecord(mailbox, record)) {
        /* bogus cache record */
        prot_printf(state->out, "\"\"");
        return;
    }

    buf_setmap(&buf, cacheitem_base(record, CACHE_HEADERS),
                     cacheitem_size(record, CACHE_HEADERS));
    buf_cstring(&buf);

    message_pruneheader(buf.s, headers, 0);
    size = strlen(buf.s); /* not buf.len, it has been pruned */

    /* partial fetch: adjust 'size' */
    if (octet_count) {
        if (size <= start_octet) {
            crlf_start = start_octet - size;
            size = 0;
            start_octet = 0;
            if (crlf_size <= crlf_start) {
                crlf_size = 0;
            }
            else {
                crlf_size -= crlf_start;
            }
        }
        else {
            size -= start_octet;
        }
        if (size > octet_count) {
            size = octet_count;
            crlf_size = 0;
        }
        else if (size + crlf_size > octet_count) {
            crlf_size = octet_count - size;
        }
    }

    if (size + crlf_size == 0) {
        prot_printf(state->out, "\"\"");
    }
    else {
        prot_printf(state->out, "{%u}\r\n", size + crlf_size);
        prot_write(state->out, buf.s + start_octet, size);
        prot_write(state->out, crlf + crlf_start, crlf_size);
    }
}

/*
 * Send a * FLAGS response.
 */
static void index_listflags(struct index_state *state)
{
    unsigned i;
    int cancreate = 0;
    char sepchar = '(';

    prot_printf(state->out, "* FLAGS (\\Answered \\Flagged \\Draft \\Deleted \\Seen");
    for (i = 0; i < MAX_USER_FLAGS; i++) {
        if (state->flagname[i]) {
            prot_printf(state->out, " %s", state->flagname[i]);
        }
        else cancreate++;
    }
    prot_printf(state->out, ")\r\n* OK [PERMANENTFLAGS ");
    if (!state->examining) {
        if (state->myrights & ACL_WRITE) {
            prot_printf(state->out, "%c\\Answered \\Flagged \\Draft", sepchar);
            sepchar = ' ';
        }
        if (state->myrights & ACL_DELETEMSG) {
            prot_printf(state->out, "%c\\Deleted", sepchar);
            sepchar = ' ';
        }
        if (state->myrights & ACL_SETSEEN) {
            prot_printf(state->out, "%c\\Seen", sepchar);
            sepchar = ' ';
        }
        if (state->myrights & ACL_WRITE) {
            for (i = 0; i < MAX_USER_FLAGS; i++) {
                if (state->flagname[i]) {
                    prot_printf(state->out, " %s", state->flagname[i]);
                }
            }
            if (cancreate) {
                prot_printf(state->out, " \\*");
            }
        }
    }
    if (sepchar == '(') prot_printf(state->out, "(");
    prot_printf(state->out, ")] Ok\r\n");
}

EXPORTED void index_checkflags(struct index_state *state, int print, int dirty)
{
    struct mailbox *mailbox = state->mailbox;
    unsigned i;

    for (i = 0; i < MAX_USER_FLAGS; i++) {
        /* both empty */
        if (!mailbox->flagname[i] && !state->flagname[i])
            continue;

        /* both same */
        if (mailbox->flagname[i] && state->flagname[i] &&
            !strcmp(mailbox->flagname[i], state->flagname[i]))
            continue;

        /* ok, got something to change! */
        if (state->flagname[i])
            free(state->flagname[i]);
        if (mailbox->flagname[i])
            state->flagname[i] = xstrdup(mailbox->flagname[i]);
        else
            state->flagname[i] = NULL;

        dirty = 1;
    }

    if (dirty && print)
        index_listflags(state);
}

static void index_tellexpunge(struct index_state *state)
{
    unsigned oldmsgno;
    uint32_t msgno = 1;
    struct seqset *vanishedlist;
    struct index_map *im;
    unsigned exists = state->exists;

    // if we want expunged, we can't tell them!
    if (state->want_expunged) return;

    vanishedlist = seqset_init(0, SEQ_SPARSE);

    for (oldmsgno = 1; oldmsgno <= exists; oldmsgno++) {
        im = &state->map[oldmsgno-1];

        /* inform about expunges */
        if (im->internal_flags & FLAG_INTERNAL_EXPUNGED) {
            state->exists--;
            state->num_expunged--;
            /* they never knew about this one, skip */
            if (msgno > state->oldexists)
                continue;
            state->oldexists--;
            if ((client_capa & CAPA_QRESYNC))
                seqset_add(vanishedlist, im->uid, 1);
            else
                prot_printf(state->out, "* %u EXPUNGE\r\n", msgno);
            continue;
        }

        /* copy back if necessary (after first expunge) */
        if (msgno < oldmsgno)
            state->map[msgno-1] = *im;

        msgno++;
    }

    /* report all vanished if we're doing it this way */
    if (vanishedlist->len) {
        char *vanished = seqset_cstring(vanishedlist);
        prot_printf(state->out, "* VANISHED %s\r\n", vanished);
        free(vanished);
    }
    seqset_free(vanishedlist);

    /* highestmodseq can now come forward to real-time */
    state->delayed_modseq = 0;
}

static void index_tellexists(struct index_state *state)
{
    prot_printf(state->out, "* %u EXISTS\r\n", state->exists);
    prot_printf(state->out, "* %u RECENT\r\n", state->numrecent);
    state->oldexists = state->exists;
}

EXPORTED void index_tellchanges(struct index_state *state, int canexpunge,
                       int printuid, int printmodseq)
{
    uint32_t msgno;
    struct index_map *im;

    /* must call tellexpunge before tellexists, because tellexpunge changes
     * the size of oldexists to mention expunges, and tellexists will reset
     * oldexists.  If we do these out of order, we will tell the user about
     * expunges of messages they never saw, which would be wrong */
    if (canexpunge) index_tellexpunge(state);

    if (state->oldexists != state->exists) index_tellexists(state);

    if (state->oldhighestmodseq == state->highestmodseq) return;

    index_checkflags(state, 1, 0);

    /* print any changed message flags */
    for (msgno = 1; msgno <= state->exists; msgno++) {
        im = &state->map[msgno-1];

        /* report if it's changed since last told */
        if (im->modseq > im->told_modseq)
            index_printflags(state, msgno, printuid, printmodseq);
    }
}

struct fetch_annotation_rock {
    struct protstream *pout;
    const char *sep;
};

static void fetch_annotation_response(const char *mboxname
                                        __attribute__((unused)),
                                      uint32_t uid
                                        __attribute__((unused)),
                                      const char *entry,
                                      struct attvaluelist *attvalues,
                                      void *rock)
{
    char sep2 = '(';
    struct attvaluelist *l;
    struct fetch_annotation_rock *frock = rock;

    prot_printf(frock->pout, "%s", frock->sep);
    prot_printastring(frock->pout, entry);
    prot_putc(' ', frock->pout);

    for (l = attvalues ; l ; l = l->next) {
        prot_putc(sep2, frock->pout);
        sep2 = ' ';
        prot_printastring(frock->pout, l->attrib);
        prot_putc(' ', frock->pout);
        prot_printmap(frock->pout, l->value.s, l->value.len);
    }
    prot_putc(')', frock->pout);

    frock->sep = " ";
}

/*
 * Helper function to send FETCH data for the ANNOTATION
 * fetch item.
 */
static int index_fetchannotations(struct index_state *state,
                                  uint32_t msgno,
                                  const struct fetchargs *fetchargs)
{
    annotate_state_t *astate = NULL;
    struct fetch_annotation_rock rock;
    int r = 0;

    r = mailbox_get_annotate_state(state->mailbox,
                                   state->map[msgno-1].uid,
                                   &astate);
    if (r) return r;
    annotate_state_set_auth(astate, fetchargs->isadmin,
                            fetchargs->userid, fetchargs->authstate);

    memset(&rock, 0, sizeof(rock));
    rock.pout = state->out;
    rock.sep = "";

    r = annotate_state_fetch(astate,
                             &fetchargs->entries, &fetchargs->attribs,
                             fetch_annotation_response, &rock);

    return r;
}

struct fetch_mailbox_rock {
    struct index_state *state;
    int sep;
    int wantname;
    const struct fetchargs *fetchargs;
};

static int fetch_mailbox_cb(const conv_guidrec_t *rec, void *rock)
{
    static const int needrights = ACL_READ|ACL_LOOKUP;
    struct fetch_mailbox_rock *fmb_rock = (struct fetch_mailbox_rock *) rock;
    mbentry_t *mbentry = NULL;
    int myrights = 0;
    struct mailbox *mailbox = NULL;
    msgrecord_t *msgrecord = NULL;
    char *extname = NULL;
    int r = 0;

    assert(fmb_rock->state != NULL);
    assert(fmb_rock->fetchargs != NULL);

    /* convdb has flags: skip if flag deleted or flag internal expunged */
    if (rec->version >= 1) {
        if ((rec->system_flags & FLAG_DELETED)
            || (rec->internal_flags & FLAG_INTERNAL_EXPUNGED))
            goto done;
    }

    /* make sure we have appropriate rights */
    r = mboxlist_lookup(rec->mboxname, &mbentry, NULL);
    if (r) goto done;
    myrights = cyrus_acl_myrights(fmb_rock->state->authstate, mbentry->acl);
    if ((myrights & needrights) != needrights)
        goto done;

    /* convdb does not have flags: grab them from message record */
    if (rec->version == 0) {
        uint32_t system_flags, internal_flags;

        r = mailbox_open_irl(rec->mboxname, &mailbox);
        if (r) goto done;

        r = msgrecord_find(mailbox, rec->uid, &msgrecord);
        if (r) goto done;

        r = msgrecord_get_systemflags(msgrecord, &system_flags);
        if (!r) r = msgrecord_get_internalflags(msgrecord, &internal_flags);
        if (r) goto done;

        if ((system_flags & FLAG_DELETED)
            || (internal_flags & FLAG_INTERNAL_EXPUNGED))
            goto done;
    }

    if (fmb_rock->wantname) {
        extname = mboxname_to_external(rec->mboxname,
                                       fmb_rock->fetchargs->namespace,
                                       fmb_rock->fetchargs->userid);
    }

    if (fmb_rock->sep)
        prot_putc(fmb_rock->sep, fmb_rock->state->out);
    prot_printf(fmb_rock->state->out, "%s",
                fmb_rock->wantname ? extname : mbentry->uniqueid);
    fmb_rock->sep = ' ';

done:
    if (extname) free(extname);
    if (msgrecord) msgrecord_unref(&msgrecord);
    if (mailbox) mailbox_close(&mailbox);
    if (mbentry) mboxlist_entry_free(&mbentry);
    return r;
}

/*
 * Helper function to send FETCH data for the MAILBOXES
 * fetch item.
 */
static int index_fetchmailboxes(struct index_state *state,
                                uint32_t msgno,
                                const struct fetchargs *fetchargs)
{
    struct fetch_mailbox_rock rock = { state, 0, /*wantname*/ 1, fetchargs};
    struct index_record record;
    int r;

    if (!fetchargs->convstate) return 0;

    r = index_reload_record(state, msgno, &record);
    if (r) return r;

    return conversations_guid_foreach(fetchargs->convstate,
                                      message_guid_encode(&record.guid),
                                      &fetch_mailbox_cb,
                                      &rock);
}

/*
 * Helper function to send FETCH data for the MAILBOXIDS
 * fetch item.
 */
static int index_fetchmailboxids(struct index_state *state,
                                 uint32_t msgno,
                                 const struct fetchargs *fetchargs)
{
    struct fetch_mailbox_rock rock = { state, 0, /*wantname*/ 0, fetchargs};
    struct index_record record;
    int r;

    if (!fetchargs->convstate) return 0;

    r = index_reload_record(state, msgno, &record);
    if (r) return r;

    return conversations_guid_foreach(fetchargs->convstate,
                                      message_guid_encode(&record.guid),
                                      &fetch_mailbox_cb,
                                      &rock);
}

/*
 * Helper function to send * FETCH (FLAGS data.
 * Does not send the terminating close paren or CRLF.
 * Also sends preceeding * FLAGS if necessary.
 */
static void index_fetchflags(struct index_state *state,
                             uint32_t msgno)
{
    int sepchar = '(';
    unsigned flag;
    bit32 flagmask = 0;
    struct index_map *im = &state->map[msgno-1];

    prot_printf(state->out, "* %u FETCH (FLAGS ", msgno);

    if (im->isrecent) {
        prot_printf(state->out, "%c\\Recent", sepchar);
        sepchar = ' ';
    }
    if (im->system_flags & FLAG_ANSWERED) {
        prot_printf(state->out, "%c\\Answered", sepchar);
        sepchar = ' ';
    }
    if (im->system_flags & FLAG_FLAGGED) {
        prot_printf(state->out, "%c\\Flagged", sepchar);
        sepchar = ' ';
    }
    if (im->system_flags & FLAG_DRAFT) {
        prot_printf(state->out, "%c\\Draft", sepchar);
        sepchar = ' ';
    }
    if (im->system_flags & FLAG_DELETED) {
        prot_printf(state->out, "%c\\Deleted", sepchar);
        sepchar = ' ';
    }
    if (state->want_expunged && (im->internal_flags & FLAG_INTERNAL_EXPUNGED)) {
        prot_printf(state->out, "%c\\Expunged", sepchar);
        sepchar = ' ';
    }
    if (im->isseen) {
        prot_printf(state->out, "%c\\Seen", sepchar);
        sepchar = ' ';
    }
    for (flag = 0; flag < VECTOR_SIZE(state->flagname); flag++) {
        if ((flag & 31) == 0) {
            flagmask = im->user_flags[flag/32];
        }
        if (state->flagname[flag] && (flagmask & (1<<(flag & 31)))) {
            prot_printf(state->out, "%c%s", sepchar, state->flagname[flag]);
            sepchar = ' ';
        }
    }
    if (sepchar == '(') (void)prot_putc('(', state->out);
    (void)prot_putc(')', state->out);
    im->told_modseq = im->modseq;
}

static void index_printflags(struct index_state *state,
                             uint32_t msgno, int usinguid,
                             int printmodseq)
{
    struct index_map *im = &state->map[msgno-1];

    index_fetchflags(state, msgno);
    /* http://www.rfc-editor.org/errata_search.php?rfc=5162
     * Errata ID: 1807 - MUST send UID and MODSEQ to all
     * untagged FETCH unsolicited responses */
    if (usinguid || (client_capa & CAPA_QRESYNC))
        prot_printf(state->out, " UID %u", im->uid);
    if (printmodseq || (client_capa & CAPA_CONDSTORE))
        prot_printf(state->out, " MODSEQ (" MODSEQ_FMT ")", im->modseq);
    prot_printf(state->out, ")\r\n");
}

/* interface message_read_bodystructure which makes sure the cache record
 * exists and adds the MESSAGE/RFC822 wrapper to make fetch BODY[*]
 * work consistently */
static void loadbody(struct mailbox *mailbox, struct index_record *record,
                     struct body **bodyp)
{
    if (*bodyp) return;
    if (mailbox_cacherecord(mailbox, record)) return;
    struct body *body = xzmalloc(sizeof(struct body));
    message_read_bodystructure(record, &body->subpart);
    body->type = xstrdup("MESSAGE");
    body->subtype = xstrdup("RFC822");
    body->header_offset = 0;
    body->header_size = 0;
    body->content_offset = 0;
    body->content_offset = record->size;
    *bodyp = body;
}

/*
 * Helper function to send requested * FETCH data for a message
 */
static int index_fetchreply(struct index_state *state, uint32_t msgno,
                            const struct fetchargs *fetchargs)
{
    struct mailbox *mailbox = state->mailbox;
    int fetchitems = fetchargs->fetchitems;
    struct buf buf = BUF_INITIALIZER;
    struct octetinfo *oi = NULL;
    int sepchar = '(';
    int started = 0;
    struct section *section;
    struct fieldlist *fsection;
    char respbuf[100];
    int r = 0;
    struct index_map *im = &state->map[msgno-1];
    struct index_record record;
    struct body *body = NULL;

    /* Check the modseq against changedsince */
    if (fetchargs->changedsince && im->modseq <= fetchargs->changedsince)
        return 0;

    /* skip missing records entirely */
    if (!im->recno)
        return 0;

    r = index_reload_record(state, msgno, &record);
    if (r) {
        prot_printf(state->out, "* OK ");
        prot_printf(state->out, error_message(IMAP_NO_MSGGONE), msgno);
        prot_printf(state->out, "\r\n");
        return 0;
    }

    /* Check against the CID list filter */
    if (fetchargs->cidhash) {
        const char *key = conversation_id_encode(record.cid);
        if (!hash_lookup(key, fetchargs->cidhash))
            return 0;
    }

    /* Open the message file if we're going to need it */
    if ((fetchitems & (FETCH_HEADER|FETCH_TEXT|FETCH_SHA1|FETCH_RFC822)) ||
        fetchargs->cache_atleast > record.cache_version ||
        fetchargs->binsections || fetchargs->sizesections ||
        fetchargs->bodysections) {
        if (mailbox_map_record(mailbox, &record, &buf)) {
            prot_printf(state->out, "* OK ");
            prot_printf(state->out, error_message(IMAP_NO_MSGGONE), msgno);
            prot_printf(state->out, "\r\n");
            return 0;
        }
    }
    int ischanged = im->told_modseq < record.modseq;

    /* display flags if asked _OR_ if they've changed */
    if (fetchitems & FETCH_FLAGS || ischanged) {
        index_fetchflags(state, msgno);
        sepchar = ' ';
    }
    else if ((fetchitems & ~FETCH_SETSEEN) || fetchargs->fsections ||
             fetchargs->headers.count || fetchargs->headers_not.count) {
        /* these fetch items will always succeed, so start the response */
        prot_printf(state->out, "* %u FETCH ", msgno);
        started = 1;
    }
    if (fetchitems & FETCH_UID || (ischanged && (client_capa & CAPA_QRESYNC))) {
        prot_printf(state->out, "%cUID %u", sepchar, record.uid);
        sepchar = ' ';
    }
    if (fetchitems & FETCH_GUID) {
        prot_printf(state->out, "%cDIGEST.SHA1 %s", sepchar,
                    message_guid_encode(&record.guid));
        sepchar = ' ';
    }

    if (fetchitems & FETCH_INTERNALDATE) {
        time_t msgdate = record.internaldate;
        char datebuf[RFC3501_DATETIME_MAX+1];

        time_to_rfc3501(msgdate, datebuf, sizeof(datebuf));

        prot_printf(state->out, "%cINTERNALDATE \"%s\"",
                    sepchar, datebuf);
        sepchar = ' ';
    }

    if (fetchitems & FETCH_LASTUPDATED) {
        time_t msgdate = record.last_updated;
        char datebuf[RFC3501_DATETIME_MAX+1];

        time_to_rfc3501(msgdate, datebuf, sizeof(datebuf));

        prot_printf(state->out, "%cLASTUPDATED \"%s\"",
                    sepchar, datebuf);
        sepchar = ' ';
    }

    if (fetchitems & FETCH_MODSEQ || (ischanged && (client_capa & CAPA_CONDSTORE))) {
        prot_printf(state->out, "%cMODSEQ (" MODSEQ_FMT ")",
                    sepchar, record.modseq);
        sepchar = ' ';
    }
    if (fetchitems & FETCH_SIZE) {
        prot_printf(state->out, "%cRFC822.SIZE %u",
                    sepchar, record.size);
        sepchar = ' ';
    }
    if ((fetchitems & FETCH_ANNOTATION)) {
        prot_printf(state->out, "%cANNOTATION (", sepchar);
        r = index_fetchannotations(state, msgno, fetchargs);
        r = 0;
        prot_printf(state->out, ")");
        sepchar = ' ';
    }
    if (fetchitems & FETCH_PREVIEW) {
        prot_printf(state->out, "%cPREVIEW (FUZZY ", sepchar);
        const char *annot = config_getstring(IMAPOPT_JMAP_PREVIEW_ANNOT);
        if (annot && !strncmp(annot, "/shared/", 8)) {
            struct buf previewbuf = BUF_INITIALIZER;
            annotatemore_msg_lookup(mailbox->name, record.uid, annot+7,
                                    /*userid*/"", &previewbuf);
            if (buf_len(&previewbuf) > 256)
                buf_truncate(&previewbuf, 256); // XXX - utf8 chars
            prot_printastring(state->out, buf_cstring(&previewbuf));
            buf_free(&previewbuf);
        }
        else {
            prot_printf(state->out, "NIL");
        }


        prot_printf(state->out, ")");
        sepchar = ' ';
    }
    if (fetchitems & FETCH_FILESIZE) {
        unsigned int msg_size = buf.len;
        if (!buf.s) {
            const char *fname = mailbox_record_fname(mailbox, &record);
            struct stat sbuf;
            /* Find the size of the message file */
            if (stat(fname, &sbuf) == -1)
                syslog(LOG_ERR, "IOERROR: stat on %s: %m", fname);
            else
                msg_size = sbuf.st_size;
        }
        prot_printf(state->out, "%cRFC822.FILESIZE %lu", sepchar,
                    (long unsigned)msg_size);
        sepchar = ' ';
    }
    if (fetchitems & FETCH_SHA1) {
        struct message_guid tmpguid;
        message_guid_generate(&tmpguid, buf.s, buf.len);
        prot_printf(state->out, "%cRFC822.SHA1 %s", sepchar, message_guid_encode(&tmpguid));
        sepchar = ' ';
    }
    if (fetchitems & FETCH_EMAILID) {
        char emailid[26];
        emailid[0] = 'M';
        memcpy(emailid+1, message_guid_encode(&record.guid), 24);
        emailid[25] = '\0';
        prot_printf(state->out, "%cEMAILID (%s)", sepchar, emailid);
        sepchar = ' ';
    }
    if ((fetchitems & FETCH_CID) &&
        config_getswitch(IMAPOPT_CONVERSATIONS)) {
        struct buf buf = BUF_INITIALIZER;
        if (!record.cid)
            buf_appendcstr(&buf, "NIL");
        else
            buf_printf(&buf, CONV_FMT, record.cid);
        prot_printf(state->out, "%cCID %s", sepchar, buf_cstring(&buf));
        buf_free(&buf);
        sepchar = ' ';
    }
    if ((fetchitems & FETCH_THREADID)) {
        char threadid[18];
        if (!record.cid) {
            threadid[0] = 'N';
            threadid[1] = 'I';
            threadid[2] = 'L';
            threadid[3] = '\0';
        }
        else {
            threadid[0] = 'T';
            memcpy(threadid+1, conversation_id_encode(record.cid), 16);
            threadid[17] = '\0';
        }

        prot_printf(state->out, "%cTHREADID (%s)", sepchar, threadid);
        sepchar = ' ';
    }
    if (fetchitems & FETCH_SAVEDATE) {
        time_t msgdate = record.savedate;
        char datebuf[RFC3501_DATETIME_MAX+1];

        // handle internaldate
        if (!msgdate) msgdate = record.internaldate;

        time_to_rfc3501(msgdate, datebuf, sizeof(datebuf));

        prot_printf(state->out, "%cSAVEDATE \"%s\"",
                    sepchar, datebuf);
        sepchar = ' ';
    }
    if (fetchitems & FETCH_CREATEDMODSEQ) {
        prot_printf(state->out, "%cCREATEDMODSEQ (" MODSEQ_FMT ")",
                    sepchar, record.createdmodseq);
        sepchar = ' ';
    }

    if ((fetchitems & FETCH_BASECID) &&
        config_getswitch(IMAPOPT_CONVERSATIONS)) {
        mailbox_read_basecid(mailbox, &record);
        struct buf buf = BUF_INITIALIZER;
        if (!record.basecid)
            buf_appendcstr(&buf, "NIL");
        else
            buf_printf(&buf, CONV_FMT, record.basecid);
        prot_printf(state->out, "%cBASECID %s", sepchar, buf_cstring(&buf));
        buf_free(&buf);
        sepchar = ' ';
    }
    if ((fetchitems & FETCH_FOLDER)) {
        char *extname = mboxname_to_external(index_mboxname(state),
                                             fetchargs->namespace, fetchargs->userid);
        prot_printf(state->out, "%cFOLDER ", sepchar);
        prot_printastring(state->out, extname);
        sepchar = ' ';
        free(extname);
    }
    if ((fetchitems & FETCH_UIDVALIDITY)) {
        prot_printf(state->out, "%cUIDVALIDITY %u", sepchar,
                    state->mailbox->i.uidvalidity);
        sepchar = ' ';
    }
    if (config_getswitch(IMAPOPT_CONVERSATIONS)) {
        if (fetchitems & FETCH_MAILBOXES) {
            prot_printf(state->out, "%cMAILBOXES (", sepchar);
            r = index_fetchmailboxes(state, msgno, fetchargs);
            r = 0;
            prot_printf(state->out, ")");
            sepchar = ' ';
        }
        if (fetchitems & FETCH_MAILBOXIDS) {
            prot_printf(state->out, "%cMAILBOXIDS (", sepchar);
            r = index_fetchmailboxids(state, msgno, fetchargs);
            r = 0;
            prot_printf(state->out, ")");
            sepchar = ' ';
        }
    }
    if (fetchitems & FETCH_ENVELOPE) {
        if (!mailbox_cacherecord(mailbox, &record)) {
            prot_printf(state->out, "%cENVELOPE ", sepchar);
            sepchar = ' ';
            prot_putbuf(state->out, cacheitem_buf(&record, CACHE_ENVELOPE));
        }
    }
    if (fetchitems & FETCH_BODYSTRUCTURE) {
        if (!mailbox_cacherecord(mailbox, &record)) {
            prot_printf(state->out, "%cBODYSTRUCTURE ", sepchar);
            sepchar = ' ';
            prot_putbuf(state->out, cacheitem_buf(&record, CACHE_BODYSTRUCTURE));
        }
    }
    if (fetchitems & FETCH_BODY) {
        if (!mailbox_cacherecord(mailbox, &record)) {
            prot_printf(state->out, "%cBODY ", sepchar);
            sepchar = ' ';
            prot_putbuf(state->out, cacheitem_buf(&record, CACHE_BODY));
        }
    }

    if (fetchitems & FETCH_HEADER) {
        prot_printf(state->out, "%cRFC822.HEADER ", sepchar);
        sepchar = ' ';
        index_fetchmsg(state, &buf, 0,
                       record.header_size,
                       (fetchitems & FETCH_IS_PARTIAL) ?
                         fetchargs->start_octet : 0,
                       (fetchitems & FETCH_IS_PARTIAL) ?
                         fetchargs->octet_count : 0);
    }
    else if (fetchargs->headers.count || fetchargs->headers_not.count) {
        prot_printf(state->out, "%cRFC822.HEADER ", sepchar);
        sepchar = ' ';
        if (fetchargs->cache_atleast > record.cache_version) {
            index_fetchheader(state, buf.s, buf.len,
                              record.header_size,
                              &fetchargs->headers, &fetchargs->headers_not);
        } else {
            index_fetchcacheheader(state, &record, &fetchargs->headers, 0, 0);
        }
    }

    if (fetchitems & FETCH_TEXT) {
        prot_printf(state->out, "%cRFC822.TEXT ", sepchar);
        sepchar = ' ';
        index_fetchmsg(state, &buf,
                       record.header_size, record.size - record.header_size,
                       (fetchitems & FETCH_IS_PARTIAL) ?
                         fetchargs->start_octet : 0,
                       (fetchitems & FETCH_IS_PARTIAL) ?
                         fetchargs->octet_count : 0);
    }
    if (fetchitems & FETCH_RFC822) {
        prot_printf(state->out, "%cRFC822 ", sepchar);
        sepchar = ' ';
        index_fetchmsg(state, &buf, 0, record.size,
                       (fetchitems & FETCH_IS_PARTIAL) ?
                         fetchargs->start_octet : 0,
                       (fetchitems & FETCH_IS_PARTIAL) ?
                         fetchargs->octet_count : 0);
    }

    for (fsection = fetchargs->fsections; fsection; fsection = fsection->next) {
        int i;
        prot_printf(state->out, "%cBODY[%s ", sepchar, fsection->section);
        sepchar = '(';
        for (i = 0 ; i < fsection->fields->count ; i++) {
            (void)prot_putc(sepchar, state->out);
            sepchar = ' ';
            prot_printastring(state->out, fsection->fields->data[i]);
        }
        (void)prot_putc(')', state->out);
        sepchar = ' ';

        oi = (struct octetinfo *)fsection->rock;

        prot_printf(state->out, "%s ", fsection->trail);

        if (fetchargs->cache_atleast > record.cache_version) {
            loadbody(mailbox, &record, &body);
            if (body) {
                index_fetchfsection(state, buf.s, buf.len,
                                    fsection,
                                    body,
                                    (fetchitems & FETCH_IS_PARTIAL) ?
                                      fetchargs->start_octet : oi->start_octet,
                                    (fetchitems & FETCH_IS_PARTIAL) ?
                                      fetchargs->octet_count : oi->octet_count);
            } else {
                prot_printf(state->out, "NIL");
            }

        }
        else {
            index_fetchcacheheader(state, &record, fsection->fields,
                                   (fetchitems & FETCH_IS_PARTIAL) ?
                                     fetchargs->start_octet : oi->start_octet,
                                   (fetchitems & FETCH_IS_PARTIAL) ?
                                     fetchargs->octet_count : oi->octet_count);
        }
    }
    for (section = fetchargs->bodysections; section; section = section->next) {
        respbuf[0] = 0;
        if (sepchar == '(' && !started) {
            /* we haven't output a fetch item yet, so start the response */
            snprintf(respbuf, sizeof(respbuf), "* %u FETCH ", msgno);
        }
        snprintf(respbuf+strlen(respbuf), sizeof(respbuf)-strlen(respbuf),
                 "%cBODY[%s ", sepchar, section->name);

        oi = &section->octetinfo;

        loadbody(mailbox, &record, &body);
        if (body) {
            r = index_fetchsection(state, respbuf, &buf,
                    section->name, body, record.size,
                    (fetchitems & FETCH_IS_PARTIAL) ?
                    fetchargs->start_octet : oi->start_octet,
                    (fetchitems & FETCH_IS_PARTIAL) ?
                    fetchargs->octet_count : oi->octet_count);
            if (!r) sepchar = ' ';
        }
    }
    for (section = fetchargs->binsections; section; section = section->next) {
        respbuf[0] = 0;
        if (sepchar == '(' && !started) {
            /* we haven't output a fetch item yet, so start the response */
            snprintf(respbuf, sizeof(respbuf), "* %u FETCH ", msgno);
        }
        snprintf(respbuf+strlen(respbuf), sizeof(respbuf)-strlen(respbuf),
                 "%cBINARY[%s ", sepchar, section->name);

        loadbody(mailbox, &record, &body);
        if (body) {
            oi = &section->octetinfo;
            r = index_fetchsection(state, respbuf, &buf,
                                   section->name, body, record.size,
                                   (fetchitems & FETCH_IS_PARTIAL) ?
                                    fetchargs->start_octet : oi->start_octet,
                                   (fetchitems & FETCH_IS_PARTIAL) ?
                                    fetchargs->octet_count : oi->octet_count);
            if (!r) sepchar = ' ';
        }
    }
    for (section = fetchargs->sizesections; section; section = section->next) {
        respbuf[0] = 0;
        if (sepchar == '(' && !started) {
            /* we haven't output a fetch item yet, so start the response */
            snprintf(respbuf, sizeof(respbuf), "* %u FETCH ", msgno);
        }
        snprintf(respbuf+strlen(respbuf), sizeof(respbuf)-strlen(respbuf),
                 "%cBINARY.SIZE[%s ", sepchar, section->name);

        loadbody(mailbox, &record, &body);
        if (body) {
            r = index_fetchsection(state, respbuf, &buf,
                                   section->name, body, record.size,
                                   fetchargs->start_octet, fetchargs->octet_count);
            if (!r) sepchar = ' ';
        }
    }
    if (sepchar != '(') {
        /* finsh the response if we have one */
        prot_printf(state->out, ")\r\n");
    }
    buf_free(&buf);
    if (body) {
        message_free_body(body);
        free(body);
    }

    return r;
}

/*
 * Fetch the text data associated with an IMAP URL.
 *
 * If outsize is NULL, the data will be output as a literal (URLFETCH),
 * otherwise just the data will be output (CATENATE), and its size returned
 * in *outsize.
 *
 * This is an amalgamation of index_fetchreply(), index_fetchsection()
 * and index_fetchmsg().
 */
EXPORTED int index_urlfetch(struct index_state *state, uint32_t msgno,
                   unsigned params, const char *section,
                   unsigned long start_octet, unsigned long octet_count,
                   struct protstream *pout, unsigned long *outsize)
{
    /* dumbass eM_Client sends this:
     * A4 APPEND "INBOX.Junk Mail" () "14-Jul-2013 17:01:02 +0000"
     * CATENATE (URL "/INBOX/;uid=83118/;section=TEXT.MIME"
     * URL "/INBOX/;uid=83118/;section=TEXT")
     *
     * genius.  I can sort of see how TEXT.MIME kinda == "HEADER",
     * so there we go */
    static char text_mime[] = "HEADER";
    struct buf buf = BUF_INITIALIZER;
    int domain = DOMAIN_7BIT;
    const char *data;
    size_t size;
    int32_t wantheader = 0;
    unsigned long n;
    int r = 0;
    char *decbuf = NULL;
    struct index_record record;
    struct body *top = NULL, *body = NULL;
    size_t section_offset, section_size;

    r = index_lock(state, /*readonly*/1); // XXX: do we need to stay locked for this entire function?
    if (r) return r;

    struct mailbox *mailbox = state->mailbox;

    if (!strcasecmpsafe(section, "TEXT.MIME"))
        section = text_mime;

    if (outsize) *outsize = 0;

    r = index_reload_record(state, msgno, &record);
    if (r) goto done;

    loadbody(mailbox, &record, &body);
    if (!body) goto done;
    top = body;

    /* Open the message file */
    if (mailbox_map_record(mailbox, &record, &buf)) {
        r = IMAP_NO_MSGGONE;
        goto done;
    }

    data = buf.s;
    size = buf.len;

    int is_binary = params & URLFETCH_BINARY;

    /* Special-case BODY[] */
    if (!section || !*section) {
        /* whole message, no further parsing */
    }
    else {
        const char *p = ucase((char *) section);
        int32_t mimenum = 0;

        while (*p) {
            switch(*p) {
            case 'H':
                if (is_binary) goto badpart;
                if (!body_is_rfc822(body)) goto badpart;
                body = body->subpart;
                p += 6;
                wantheader = 1;
                goto getoffset;
            case 'T':
                if (is_binary) goto badpart;
                if (!body_is_rfc822(body)) goto badpart;
                body = body->subpart;
                p += 4;
                goto getoffset;
            case 'M':
                if (is_binary) goto badpart;
                if (top == body) goto badpart;
                p += 4;
                wantheader = 1;
                goto getoffset;
            default:
                mimenum = 0;
                r = parseint32(p, &p, &mimenum);
                if (*p == '.') p++;
                if (r || !mimenum) goto badpart;
                body = find_part(body, mimenum);
                if (!body) goto badpart;
                break;
            }
        }

      getoffset:
        if (*p) goto badpart;

        section_offset = wantheader ? body->header_offset : body->content_offset;
        section_size = wantheader ? body->header_size : body->content_size;

        if (section_offset + section_size < section_offset
            || section_offset + section_size > size) {
            r = IMAP_INTERNAL;
            goto done;
        }

        data += section_offset;
        size = section_size;
    }

    if (is_binary) {
        int encoding = body->charset_enc & 0xff;

        data = charset_decode_mimebody(data, size, encoding,
                                       &decbuf, &size);

        /* update the encoding of this part per RFC5524:3.2 */
        if (data && encoding) {
            domain = data_domain(data, size);
            free(body->encoding);
            switch (domain) {
            case DOMAIN_BINARY:
                body->encoding = xstrdup("BINARY");
                break;
            case DOMAIN_8BIT:
                body->encoding = xstrdup("8BIT");
                break;
            default:
                body->encoding = NULL; // will output 7BIT
                break;
            }
            body->content_size = size;
            body->content_lines = 0;
        }
    }

    if (params & URLFETCH_BODYPARTSTRUCTURE) {
        struct buf buf = BUF_INITIALIZER;
        message_write_body(&buf, body, 1);
        prot_puts(pout, " (BODYPARTSTRUCTURE ");
        if (buf_len(&buf))
            prot_putbuf(pout, &buf);
        else
            prot_puts(pout, "NIL");
        prot_puts(pout, ")");
        buf_free(&buf);
    }

    if (params & URLFETCH_BODY) {
        prot_printf(pout, " (BODY");
    }
    else if (params & URLFETCH_BINARY) {
        prot_printf(pout, " (BINARY");
        if (!data) {
            /* failed to decode */
            prot_printf(pout, " NIL)");
            r = 0;
            goto done;
        }
    }
    else if (params) {
        r = 0;
        goto done;
    }

    /* Handle PARTIAL request */
    n = octet_count ? octet_count : size;

    /* Sanity check the requested size */
    if (start_octet > size) {
        start_octet = size;
        n = 0;
    }
    else if (start_octet + n < start_octet || start_octet + n > size) {
        n = size - start_octet;
    }

    if (outsize) {
        /* Return size (CATENATE) */
        *outsize = n;
    } else {
        domain = data_domain(data + start_octet, n);

        if (domain == DOMAIN_BINARY) {
            /* Write size of literal8 */
            prot_printf(pout, " ~{%lu}\r\n", n);
        } else {
            /* Write size of literal */
            prot_printf(pout, " {%lu}\r\n", n);
        }
    }

    /* Non-text literal -- tell the protstream about it */
    if (domain != DOMAIN_7BIT) prot_data_boundary(pout);

    if (n) prot_write(pout, data + start_octet, n);

    /* End of non-text literal -- tell the protstream about it */
    if (domain != DOMAIN_7BIT) prot_data_boundary(pout);

    /* Complete extended URLFETCH response */
    if (params) prot_printf(pout, ")");

    r = 0;

  done:
    /* Close the message file */
    index_unlock(state);
    buf_free(&buf);

    if (top) {
        message_free_body(top);
        free(top);
    }
    if (decbuf) free(decbuf);
    return r;

  badpart:
    r = IMAP_PROTOCOL_BAD_PARAMETERS;
    goto done;
}

/*
 * Helper function to perform a STORE command for flags.
 */
static int index_storeflag(struct index_state *state,
                           struct index_modified_flags *modified_flags,
                           uint32_t msgno, msgrecord_t *msgrec,
                           struct storeargs *storeargs)
{
    uint32_t old, new, keep;
    unsigned i;
    int dirty = 0;
    modseq_t oldmodseq;
    struct index_map *im = &state->map[msgno-1];
    struct index_record *record;
    int r;

    memset(modified_flags, 0, sizeof(struct index_modified_flags));

    oldmodseq = im->modseq;

    /* Change \Seen flag.  This gets done on the index first and will only be
       copied into the record later if internalseen is set */
    if (state->myrights & ACL_SETSEEN) {
        old = im->isseen ? 1 : 0;
        new = old;
        if (storeargs->operation == STORE_REPLACE_FLAGS)
            new = storeargs->seen ? 1 : 0;
        else if (storeargs->seen)
            new = (storeargs->operation == STORE_ADD_FLAGS) ? 1 : 0;

        if (new != old) {
            if (state->numunseen || new < old)
                state->numunseen += (old - new);
            else
                syslog(LOG_ERR, "IOERROR: numunseen underflow in storeflag: %s %u",
                       state->mboxname, im->uid);
            im->isseen = new;
            state->seen_dirty = 1;
            dirty++;
        }
    }

    uint32_t system_flags;
    uint32_t internal_flags;
    uint32_t user_flags[MAX_USER_FLAGS/32];

    r = msgrecord_get_index_record_rw(msgrec, &record);
    if (r) return r;

    r = msgrecord_get_systemflags(msgrec, &system_flags);
    if (r) return r;

    r = msgrecord_get_internalflags(msgrec, &internal_flags);
    if (r) return r;

    r = msgrecord_get_userflags(msgrec, user_flags);
    if (r) return r;

    keep = internal_flags;
    old = system_flags & FLAGS_SYSTEM;
    new = storeargs->system_flags & FLAGS_SYSTEM;

    /* all other updates happen directly to the record */
    if (storeargs->operation == STORE_REPLACE_FLAGS) {
        if (!(state->myrights & ACL_WRITE)) {
            /* ACL_DELETE handled in index_store() */
            if ((old & FLAG_DELETED) != (new & FLAG_DELETED)) {
                dirty++;
                system_flags = (old & ~FLAG_DELETED) | (new & FLAG_DELETED);
            }
        }
        else {
            if (!(state->myrights & ACL_DELETEMSG)) {
                if ((old & ~FLAG_DELETED) != (new & ~FLAG_DELETED)) {
                    dirty++;
                    system_flags = (old & FLAG_DELETED) | (new & ~FLAG_DELETED);
                }
            }
            else {
                if (old != new) {
                    dirty++;
                    system_flags = new;
                }
            }
            for (i = 0; i < (MAX_USER_FLAGS/32); i++) {
                if (user_flags[i] != storeargs->user_flags[i]) {
                    uint32_t changed;
                    dirty++;

                    changed = ~user_flags[i] & storeargs->user_flags[i];
                    if (changed) {
                        modified_flags->added_user_flags[i] = changed;
                        modified_flags->added_flags++;
                    }

                    changed = user_flags[i] & ~storeargs->user_flags[i];
                    if (changed) {
                        modified_flags->removed_user_flags[i] = changed;
                        modified_flags->removed_flags++;
                    }
                    user_flags[i] = storeargs->user_flags[i];
                }
            }
        }
    }
    else if (storeargs->operation == STORE_ADD_FLAGS) {
        uint32_t added;

        if (~old & new) {
            dirty++;
            system_flags = old | new;
        }
        for (i = 0; i < (MAX_USER_FLAGS/32); i++) {
            added = ~user_flags[i] & storeargs->user_flags[i];
            if (added) {
                dirty++;
                user_flags[i] |= storeargs->user_flags[i];

                modified_flags->added_user_flags[i] = added;
                modified_flags->added_flags++;
            }
        }
    }
    else { /* STORE_REMOVE_FLAGS */
        uint32_t removed;

        if (old & new) {
            dirty++;
            system_flags &= ~storeargs->system_flags;
        }
        for (i = 0; i < (MAX_USER_FLAGS/32); i++) {
            removed = user_flags[i] & storeargs->user_flags[i];
            if (removed) {
                dirty++;
                user_flags[i] &= ~storeargs->user_flags[i];

                modified_flags->removed_user_flags[i] = removed;
                modified_flags->removed_flags++;
            }
        }
    }

    /* rfc4551:
     * 3.8.  Additional Quality-of-Implementation Issues
     *
     * Server implementations should follow the following rule, which
     * applies to any successfully completed STORE/UID STORE (with and
     * without UNCHANGEDSINCE modifier), as well as to a FETCH command that
     * implicitly sets \Seen flag:
     *
     *    Adding the flag when it is already present or removing when it is
     *    not present SHOULD NOT change the mod-sequence.
     *
     * This will prevent spurious client synchronization requests.
     */
    if (!dirty) return 0;

    if (state->internalseen) {
        /* copy the seen flag from the index */
        if (im->isseen)
            system_flags |= FLAG_SEEN;
        else
            system_flags &= ~FLAG_SEEN;
    }
    /* add back the internal tracking flags */
    system_flags |= keep;

    modified_flags->added_system_flags = ~old & system_flags & FLAGS_SYSTEM;
    if (modified_flags->added_system_flags)
        modified_flags->added_flags++;
    modified_flags->removed_system_flags = old & ~system_flags & FLAGS_SYSTEM;
    if (modified_flags->removed_system_flags)
        modified_flags->removed_flags++;

    r = msgrecord_set_systemflags(msgrec, system_flags);
    if (r) return r;
    r = msgrecord_set_internalflags(msgrec, internal_flags);
    if (r) return r;
    r = msgrecord_set_userflags(msgrec, user_flags);
    if (r) return r;
    r = index_rewrite_record(state, msgno, record, /*silent*/0);
    if (r) return r;

    /* if it's silent and unchanged, update the seen value, but
     * not if qresync is enabled - RFC 4551 says that the MODSEQ
     * must always been told, and we prefer just to tell flags
     * as well in this case, it's simpler and not much more
     * bandwidth */
    if (!(client_capa & CAPA_CONDSTORE) && storeargs->silent && im->told_modseq == oldmodseq)
        im->told_modseq = im->modseq;

    return 0;
}

/*
 * Helper function to perform a STORE command for annotations
 */
static int index_store_annotation(struct index_state *state,
                                  uint32_t msgno,
                                  msgrecord_t *msgrec,
                                  struct storeargs *storeargs,
                                  int *dirty)
{
    modseq_t oldmodseq;
    struct index_record *record;
    struct index_map *im = &state->map[msgno-1];
    int r;

    r = msgrecord_get_index_record_rw(msgrec, &record);
    if (r) goto out;

    r = index_reload_record(state, msgno, record);
    if (r) goto out;

    oldmodseq = record->modseq;

    r = msgrecord_annot_set_auth(msgrec, storeargs->isadmin, storeargs->userid,
                                 storeargs->authstate);
    if (r) goto out;

    r = msgrecord_annot_writeall(msgrec, storeargs->entryatts);
    if (r) goto out;

    /* It would be nice if the annotate layer told us whether it
     * actually made a change to the database, but it doesn't, so
     * we have to assume the message is dirty */
    *dirty = 1;

    r = index_rewrite_record(state, msgno, record, /*silent*/1);
    if (r) goto out;

    /* if it's silent and unchanged, update the seen value */
    if (!(client_capa & CAPA_CONDSTORE) && storeargs->silent && im->told_modseq == oldmodseq)
        im->told_modseq = im->modseq;

out:
    return r;
}


/*
 * Evaluate a searchargs structure on a msgno
 */
EXPORTED int index_search_evaluate(struct index_state *state,
                                   const search_expr_t *e,
                                   uint32_t msgno)
{
    struct index_map *im = &state->map[msgno-1];
    struct index_record record;

    int always = search_expr_always_same(e);
    if (always < 0) return 0;
    if (always > 0) return 1;

    // failure to load is an error!
    int r = index_reload_record(state, msgno, &record);
    if (r) return 0;

    xstats_inc(SEARCH_EVALUATE);

    int flags = (im->isrecent ? MESSAGE_RECENT : 0)
              | (im->isseen ? MESSAGE_SEEN : 0);
    if (state->m) message_set_from_index(state->mailbox, &record, msgno, flags, state->m);
    else state->m = message_new_from_index(state->mailbox, &record, msgno, flags);
    int match = search_expr_evaluate(state->m, e);

    return match;
}

struct extractor_ctx {
    struct backend *be;
    struct protstream *clientin;
    unsigned failed;
};

struct getsearchtext_rock
{
    search_text_receiver_t *receiver;
    int indexed_headers;
    int charset_flags;
    const strarray_t *partids;
    int snippet_iteration; /* 0..no snippet, 1..first run, 2..second run */
    struct extractor_ctx *ext;
};

static void stuff_part(search_text_receiver_t *receiver,
                       int part,
                       const struct message_guid *content_guid,
                       const struct buf *buf)
{
    // don't try to index a zero length part
    if (!buf_len(buf)) return;

    if (part == SEARCH_PART_HEADERS &&
        !config_getswitch(IMAPOPT_SEARCH_INDEX_HEADERS))
        return;

    receiver->begin_part(receiver, part, content_guid);
    receiver->append_text(receiver, buf);
    receiver->end_part(receiver, part);
}

static void extract_cb(const struct buf *text, void *rock)
{
    struct getsearchtext_rock *str = (struct getsearchtext_rock *)rock;
    str->receiver->append_text(str->receiver, text);
}

#ifdef USE_HTTPD
static int extract_icalbuf(struct buf *raw, charset_t charset, int encoding,
                           const struct message_guid *content_guid,
                           struct getsearchtext_rock *str)
{
    icalcomponent *comp = NULL, *ical = NULL;
    const char *s;
    int r = 0;
    struct buf buf = BUF_INITIALIZER;

    /* Parse the message into an iCalendar object */
    const struct buf *icalbuf = NULL;
    if (encoding || strcasecmp(charset_canon_name(charset), "utf-8")) {
        char *tmp = charset_to_utf8(buf_cstring(raw), buf_len(raw), charset, encoding);
        if (!tmp) return 0; /* could be a bogus header - ignore */
        buf_initm(&buf, tmp, strlen(tmp));
        icalbuf = &buf;
    }
    else {
        icalbuf = raw;
    }
    ical = icalparser_parse_string(buf_cstring(icalbuf));
    buf_reset(&buf);
    if (!ical) {
        r = IMAP_INTERNAL;
        goto done;
    }

    for (comp = icalcomponent_get_first_real_component(ical);
         comp;
         comp = icalcomponent_get_next_component(ical, icalcomponent_isa(comp))) {

        icalproperty *prop;
        icalparameter *param;

        /* description */
        if ((s = icalcomponent_get_description(comp))) {
            buf_setcstr(&buf, s);
            charset_t utf8 = charset_lookupname("utf-8");
            str->receiver->begin_part(str->receiver, SEARCH_PART_BODY, content_guid);
            charset_extract(extract_cb, str, &buf, utf8, 0, "calendar",
                            str->charset_flags);
            str->receiver->end_part(str->receiver, SEARCH_PART_BODY);
            charset_free(&utf8);
            buf_reset(&buf);
        }

        /* summary */
        if ((prop = icalcomponent_get_first_property(comp, ICAL_SUMMARY_PROPERTY))) {
            if ((s = icalproperty_get_summary(prop))) {
                buf_setcstr(&buf, s);
                stuff_part(str->receiver, SEARCH_PART_SUBJECT, NULL, &buf);
                buf_reset(&buf);
            }
        }

        /* organizer */
        if ((prop = icalcomponent_get_first_property(comp, ICAL_ORGANIZER_PROPERTY))) {
            if ((s = icalproperty_get_organizer(prop))) {
                if (!strncasecmp(s, "mailto:", 7)) {
                    s += 7;
                }
                param = icalproperty_get_first_parameter(prop, ICAL_CN_PARAMETER);
                if (param) {
                    buf_printf(&buf, "\"%s\" <%s>", icalparameter_get_cn(param), s);
                } else {
                    buf_setcstr(&buf, s);
                }
                stuff_part(str->receiver, SEARCH_PART_FROM, NULL, &buf);
                buf_reset(&buf);
            }
        }

        /* attendees */
        for (prop = icalcomponent_get_first_property(comp, ICAL_ATTENDEE_PROPERTY);
             prop;
             prop = icalcomponent_get_next_property(comp, ICAL_ATTENDEE_PROPERTY)) {
            if ((s = icalproperty_get_attendee(prop))) {
                if (!strncasecmp(s, "mailto:", 7)) {
                    s += 7;
                }
                param = icalproperty_get_first_parameter(prop, ICAL_CN_PARAMETER);
                if (buf.len) {
                    buf_appendcstr(&buf, ", ");
                }
                if (param) {
                    buf_printf(&buf, "\"%s\" <%s>", icalparameter_get_cn(param), s);
                } else {
                    buf_appendcstr(&buf, s);
                }
            }
        }
        if (buf.len) {
            stuff_part(str->receiver, SEARCH_PART_TO, NULL, &buf);
            buf_reset(&buf);
        }

        /* location */
        if ((prop = icalcomponent_get_first_property(comp, ICAL_LOCATION_PROPERTY))) {
            if ((s = icalproperty_get_location(prop))) {
                buf_setcstr(&buf, s);
                stuff_part(str->receiver, SEARCH_PART_LOCATION, content_guid, &buf);
                buf_reset(&buf);
            }
        }
    }

done:
    if (ical) icalcomponent_free(ical);
    buf_free(&buf);
    return r;
}

static void _add_vcard_singlval(struct vparse_card *card, const char *key, struct buf *buf)
{
    struct vparse_entry *entry;
    for (entry = card->properties; entry; entry = entry->next) {
        if (strcasecmp(entry->name, key)) continue;
        const char *val = entry->v.value;
        if (val && val[0]) {
            if (buf_len(buf)) buf_putc(buf, ' ');
            buf_appendcstr(buf, val);
        }
    }
}

static void _add_vcard_multival(struct vparse_card *card, const char *key, struct buf *buf)
{
    struct vparse_entry *entry;
    for (entry = card->properties; entry; entry = entry->next) {
        if (strcasecmp(entry->name, key)) continue;
        const strarray_t *sa = entry->v.values;
        int i;
        for (i = 0; i < strarray_size(sa); i++) {
            const char *val = strarray_nth(sa, i);
            if (val && val[0]) {
                if (buf_len(buf)) buf_putc(buf, ' ');
                buf_appendcstr(buf, val);
            }
        }
    }
}

static int extract_vcardbuf(struct buf *raw, charset_t charset, int encoding,
                            const struct message_guid *content_guid,
                            struct getsearchtext_rock *str)
{
    struct vparse_card *vcard = NULL;
    int r = 0;
    struct buf buf = BUF_INITIALIZER;

    /* Parse the message into a vcard object */
    const struct buf *vcardbuf = NULL;
    if (encoding || strcasecmp(charset_canon_name(charset), "utf-8")) {
        char *tmp = charset_to_utf8(buf_cstring(raw), buf_len(raw), charset, encoding);
        if (!tmp) return 0; /* could be a bogus header - ignore */
        buf_initm(&buf, tmp, strlen(tmp));
        vcardbuf = &buf;
    }
    else {
        vcardbuf = raw;
    }

    vcard = vcard_parse_string(buf_cstring(vcardbuf), /*repair*/1);
    if (!vcard || !vcard->objects) {
        r = IMAP_INTERNAL;
        goto done;
    }

    buf_reset(&buf);

    // these are all the things that we think might be interesting
    _add_vcard_singlval(vcard->objects, "fn", &buf);
    _add_vcard_singlval(vcard->objects, "email", &buf);
    _add_vcard_singlval(vcard->objects, "tel", &buf);
    _add_vcard_singlval(vcard->objects, "url", &buf);
    _add_vcard_singlval(vcard->objects, "impp", &buf);
    _add_vcard_singlval(vcard->objects, "x-social-profile", &buf);
    _add_vcard_singlval(vcard->objects, "x-fm-online-other", &buf);
    _add_vcard_singlval(vcard->objects, "nickname", &buf);
    _add_vcard_singlval(vcard->objects, "note", &buf);

    _add_vcard_multival(vcard->objects, "n", &buf);
    _add_vcard_multival(vcard->objects, "org", &buf);
    _add_vcard_multival(vcard->objects, "adr", &buf);

    if (buf.len) {
        charset_t utf8 = charset_lookupname("utf-8");
        str->receiver->begin_part(str->receiver, SEARCH_PART_BODY, content_guid);
        charset_extract(extract_cb, str, &buf, utf8, 0, "vcard",
                        str->charset_flags);
        str->receiver->end_part(str->receiver, SEARCH_PART_BODY);
        charset_free(&utf8);
        buf_reset(&buf);
    }

done:
    if (vcard) vparse_free_card(vcard);
    buf_free(&buf);
    return r;
}

#endif /* USE_HTTPD */


#define IDLE_TIMEOUT (5 * 60)  /* 5 min */

struct backend_ctx {
    char *path;
    int timeout;
};

static int login(struct backend *s __attribute__((unused)),
                 const char *userid __attribute__((unused)),
                 sasl_callback_t *cb __attribute__((unused)),
                 const char **status __attribute__((unused)),
                 int noauth __attribute__((unused)))
{
    return 0;
}

static int ping(struct backend *s,
                const char *userid __attribute__((unused)))
{
    struct backend_ctx *ctx = (struct backend_ctx *) s->context;
    size_t hostlen = strcspn(s->hostname, "/");
    hdrcache_t resp_hdrs = NULL;
    struct body_t resp_body;
    unsigned statuscode = 0;
    const char *errstr;
    int r = 0;

    prot_printf(s->out,
                "HEAD %s %s\r\n"
                "Host: %.*s\r\n"
                "User-Agent: Cyrus/%s\r\n"
                "Connection: Keep-Alive\r\n"
                "Keep-Alive: timeout=%u\r\n"
                "Accept: text/plain\r\n"
                "\r\n",
                ctx->path, HTTP_VERSION,
                (int) hostlen, s->hostname, CYRUS_VERSION, ctx->timeout);
    prot_flush(s->out);

    /* Read response(s) from backend until final response or error */
    do {
        resp_body.flags = BODY_DISCARD;
        r = http_read_response(s, METH_HEAD, &statuscode,
                               &resp_hdrs, &resp_body, &errstr);
        if (r) {
            break;
        }
    } while (statuscode < 200);

    if (r) {
        syslog(LOG_DEBUG, "extractor_ping: HEAD %s: failed (%s): %s",
               ctx->path, error_message(r), errstr);
    }
    else {
        syslog(LOG_DEBUG, "extractor_ping: HEAD %s: got status %u",
               ctx->path, statuscode);
    }

    if (resp_hdrs) spool_free_hdrcache(resp_hdrs);

    return r;
}

static int logout(struct backend *s __attribute__((unused)))
{
    return 0;
}

static void extractor_disconnect(struct backend *be)
{
    syslog(LOG_DEBUG, "extractor_disconnect(%p)", be);

    if (!be || (be->sock == -1)) {
        /* already disconnected */
        return;
    }

    /* need to logout of server */
    backend_disconnect(be);

    /* remove the timeout */
    if (be->timeout) prot_removewaitevent(be->clientin, be->timeout);
    be->timeout = NULL;
    be->clientin = NULL;
}

static struct prot_waitevent *
extractor_timeout(struct protstream *s __attribute__((unused)),
                  struct prot_waitevent *ev __attribute__((unused)),
                  void *rock)
{
    struct backend *be = (struct backend *) rock;

    syslog(LOG_DEBUG, "extractor_timeout(%p)", be);

    /* too long since we last used the extractor - disconnect */
    extractor_disconnect(be);

    return NULL;
}

static struct protocol_t http =
{ "http", "HTTP", TYPE_SPEC, { .spec = { &login, &ping, &logout } } };

__attribute__((unused)) // disabled experimental feature
static int extractor_connect(const char *exturl, struct extractor_ctx *ext)
{
    struct backend *be;
    struct backend_ctx *ctx = NULL;
    struct buf buf = BUF_INITIALIZER;
    const char *hostname;
    char path[256];
    time_t now = time(NULL);
    int r = 0;

    syslog(LOG_DEBUG, "extractor_connect(%s)", exturl);

    if (!ext || ext->failed > 1) return IMAP_INTERNAL;

    be = ext->be;
    if (be) {
        ctx = be->context;
        hostname = be->hostname;
    }
    else {
        char scheme[6], server[100], *p;
        unsigned https, port;

        /* Parse URL (cheesy parser without having to use libxml2) */
        int n = sscanf(exturl, "%5[^:]://%99[^/]%255[^\n]",
                       scheme, server, path);
        if (n != 3 ||
            strncmp(lcase(scheme), "http", 4) || (scheme[4] && scheme[4] != 's')) {
            syslog(LOG_ERR,
                   "extract_attachment: unexpected non-HTTP URL %s", exturl);
            return IMAP_INTERNAL;
        }

        /* Normalize URL parts */
        https = (scheme[4] == 's');
        if (*(p = path + strlen(path) - 1) == '/') *p = '\0';
        if ((p = strrchr(server, ':'))) {
            *p++ = '\0';
            port = atoi(p);
        }
        else port = https ? 443 : 80;

        /* Build servername, port, and options */
        buf_printf(&buf, "%s:%u%s/noauth", server, port, https ? "/tls" : "");
        hostname = buf_cstring(&buf);
    }

    if (be && (be->sock != -1)) {
        syslog(LOG_DEBUG, "extractor_connect: ping existing connection");

        /* ping the extractor */
        if (ping(be, NULL)) extractor_disconnect(be);
    }

    if (!be || (be->sock == -1)) {
        /* Connect to extractor service */
        syslog(LOG_DEBUG, "extractor_connect: %sconnect to %s",
               be ? "re" : "", hostname);

        be = ext->be = backend_connect(be, hostname,
                                       &http, NULL, NULL, NULL, -1);

        if (!be) {
            syslog(LOG_ERR, "extract_connect: failed to connect to %s",
                   hostname);
            ext->failed++;
            r = IMAP_IOERROR;
        }
        else if (!ctx) {
            ctx = be->context = xzmalloc(sizeof(struct backend_ctx));
            ctx->path = xstrdup(path);

            if (ext->clientin) {
                /* add a default timeout */
                be->clientin = ext->clientin;
                be->timeout = prot_addwaitevent(ext->clientin,
                                                now + IDLE_TIMEOUT,
                                                extractor_timeout, be);
            }
        }
    }

    if (be->timeout && ctx->timeout) be->timeout->mark = now + ctx->timeout;

    buf_free(&buf);

    return r;
}


static int extract_attachment(const char *type, const char *subtype,
                              const struct param *type_params,
                              const struct buf *data, int encoding,
                              const struct message_guid *content_guid,
                              struct getsearchtext_rock *str)
{
    struct extractor_ctx *ext = str->ext;
    struct backend *be;
    struct backend_ctx *ctx;
    struct buf buf = BUF_INITIALIZER;
    hdrcache_t hdrs = NULL;
    struct body_t body = { 0, 0, 0, 0, 0, BUF_INITIALIZER };
    const char *guidstr, *errstr = NULL;
    size_t hostlen;
    int r = 0;

    if (!ext) return 0;

    be = ext->be;
    ctx = (struct backend_ctx *) be->context;
    hostlen = strcspn(be->hostname, "/");

    if (message_guid_isnull(content_guid)) {
        syslog(LOG_DEBUG, "extract_attachment: ignoring null guid for %s/%s",
                type ? type : "<null>", subtype ? subtype : "<null>");
        return 0;
    }

    /* Fetch previously extracted text */
    unsigned statuscode = 0;
    guidstr = message_guid_encode(content_guid);
    prot_printf(be->out,
                "GET %s/%s %s\r\n"
                "Host: %.*s\r\n"
                "User-Agent: Cyrus/%s\r\n"
                "Connection: Keep-Alive\r\n"
                "Keep-Alive: timeout=%u\r\n"
                "Accept: text/plain\r\n"
                "\r\n",
                ctx->path, guidstr, HTTP_VERSION,
                (int) hostlen, be->hostname, CYRUS_VERSION,
                ctx->timeout ? ctx->timeout : IDLE_TIMEOUT);
    prot_flush(be->out);

    /* Read GET response */
    do {
        r = http_read_response(be, METH_GET,
                               &statuscode, &hdrs, &body, &errstr);
        if (r) {
            syslog(LOG_ERR,
                   "extract_attachment: failed to read response for GET %s/%s",
                   ctx->path, guidstr);
            r = IMAP_IOERROR;
            goto done;
        }
    } while (statuscode < 200);

    syslog(LOG_DEBUG, "extract_attachment: GET %s/%s: got status %u",
           ctx->path, guidstr, statuscode);

    /* Abide by server's timeout, if any */
    if (!ctx->timeout) {
        const char **hdr, *p;

        if ((hdr = spool_getheader(hdrs, "Keep-Alive")) &&
            (p = strstr(hdr[0], "timeout="))) {
            ctx->timeout = atoi(p+8);
        }
        else ctx->timeout = IDLE_TIMEOUT;

        if (be->timeout) be->timeout->mark = time(NULL) + ctx->timeout;
    }

    if (statuscode == 404) {
        /* Decode data */
        struct buf decbuf = BUF_INITIALIZER;
        if (encoding) {
            if (charset_decode(&decbuf, buf_base(data), buf_len(data), encoding)) {
                syslog(LOG_ERR, "extract_attachment: failed to decode data");
                r = IMAP_IOERROR;
                goto done;
            }
            data = &decbuf;
        }

        /* Build list of Content-Type parameters */
        const struct param *param = type_params;
        while (param && param->attribute) {
            buf_putc(&buf, ';');
            buf_appendcstr(&buf, param->attribute);
            if (param->value) {
                buf_putc(&buf, '=');
                buf_appendcstr(&buf, param->value);
            }
            param = param->next;
        }

        /* Send attachment to service for text extraction */
        prot_printf(be->out,
                    "PUT %s/%s %s\r\n"
                    "Host: %.*s\r\n"
                    "User-Agent: Cyrus/%s\r\n"
                    "Connection: Keep-Alive\r\n"
                    "Keep-Alive: timeout=%u\r\n"
                    "Accept: text/plain\r\n"
                    "Content-Type: %s/%s%s\r\n"
                    "Content-Length: " SIZE_T_FMT "\r\n"
                    "\r\n",
                    ctx->path, guidstr, HTTP_VERSION,
                    (int) hostlen, be->hostname, CYRUS_VERSION, ctx->timeout,
                    type, subtype, buf_cstring(&buf), buf_len(data));
        prot_putbuf(be->out, (struct buf *) data);
        prot_flush(be->out);
        buf_free(&decbuf);

        /* Read PUT response */
        body.flags = 0;
        do {
            r = http_read_response(be, METH_PUT,
                                   &statuscode, &hdrs, &body, &errstr);
            if (r) {
                syslog(LOG_ERR,
                       "extract_attachment: failed to read response for PUT %s/%s",
                       ctx->path, guidstr);
                r = IMAP_IOERROR;
                goto done;
            }
        } while (statuscode < 200);

        syslog(LOG_DEBUG, "extract_attachment: PUT %s/%s: got status %u",
               ctx->path, guidstr, statuscode);
    }

    if (statuscode >= 400 && statuscode <= 499) {
        /* indexer can't extract this for some reason, never try again */
        goto done;
    }
    if (statuscode != 200 && statuscode != 201) {
        /* any other status code is an error */
        r = IMAP_IOERROR;
        goto done;
    }

    /* Append extracted text */
    if (buf_len(&body.payload)) {
        str->receiver->begin_part(str->receiver, SEARCH_PART_ATTACHMENTBODY, content_guid);
        str->receiver->append_text(str->receiver, &body.payload);
        str->receiver->end_part(str->receiver, SEARCH_PART_ATTACHMENTBODY);
    }

done:
    spool_free_hdrcache(hdrs);
    buf_free(&body.payload);
    buf_free(&buf);
    return r;
}

static struct extractor_ctx *index_text_extractor = NULL;

EXPORTED void index_text_extractor_init(struct protstream *clientin)
{
    syslog(LOG_DEBUG, "extractor_init(%p)", clientin);

    index_text_extractor = xzmalloc(sizeof(struct extractor_ctx));
    index_text_extractor->clientin = clientin;
}

EXPORTED void index_text_extractor_destroy(void)
{
    struct extractor_ctx *ext = index_text_extractor;

    syslog(LOG_DEBUG, "extractor_destroy(%p)", ext);

    if (!ext) return;

    if (ext->be) {
        struct backend *be = ext->be;

        extractor_disconnect(be);
        free(((struct backend_ctx *) be->context)->path);
        free(be->context);
        free(be);
    }
    free(ext);

    index_text_extractor = NULL;
}


static int getsearchtext_cb(int isbody, charset_t charset, int encoding,
                            const char *type, const char *subtype,
                            const struct param *type_params __attribute__((unused)),
                            const char *disposition,
                            const struct param *disposition_params,
                            const struct message_guid *content_guid,
                            const char *part,
                            struct buf *data,
                            void *rock)
{
    struct getsearchtext_rock *str = (struct getsearchtext_rock *)rock;
    char *q;
    struct buf text = BUF_INITIALIZER;
    int r = 0;

    if (isbody && part && str->partids && strarray_find(str->partids, part, 0) < 0) {
        /* Skip part */
        return 0;
    }

    if (!isbody) {

        if (str->snippet_iteration >= 2) goto done;

        if (!str->indexed_headers) {
            /* Only index the headers of the top message */
            q = charset_decode_mimeheader(buf_cstring(data), str->charset_flags);
            buf_init_ro_cstr(&text, q);
            stuff_part(str->receiver, SEARCH_PART_HEADERS, NULL, &text);
            free(q);
            buf_free(&text);
            str->indexed_headers = 1;
        }

        /* Index attachment file names */
        const struct param *param;
        if (disposition && !strcmp(disposition, "ATTACHMENT")) {
            /* Look for "Content-Disposition: attachment;filename=" header */
            for (param = disposition_params; param; param = param->next) {
                if (!strcmp(param->attribute, "FILENAME")) {
                    char *tmp = charset_decode_mimeheader(param->value, charset_flags);
                    buf_init_ro_cstr(&text, tmp);
                    stuff_part(str->receiver, SEARCH_PART_ATTACHMENTNAME, NULL, &text);
                    buf_free(&text);
                    free(tmp);
                }
                else if (!strcmp(param->attribute, "FILENAME*")) {
                    char *xval = charset_parse_mimexvalue(param->value, NULL);
                    if (!xval) xval = xstrdup(param->value);
                    if (xval) {
                        char *tmp = charset_decode_mimeheader(xval, charset_flags|CHARSET_MIME_UTF8);
                        buf_init_ro_cstr(&text, tmp);
                        stuff_part(str->receiver, SEARCH_PART_ATTACHMENTNAME, NULL, &text);
                        buf_free(&text);
                        free(tmp);
                        free(xval);
                    }
                }
            }
        }
        for(param = type_params; param; param = param->next) {
            /* Look for "Content-Type: foo;name=" header */
            if (strcmp(param->attribute, "NAME"))
                continue;
            char *tmp = charset_decode_mimeheader(param->value, charset_flags);
            buf_init_ro_cstr(&text, tmp);
            stuff_part(str->receiver, SEARCH_PART_ATTACHMENTNAME, NULL, &text);
            buf_free(&text);
            free(tmp);
        }
    }
    else if (buf_len(data) > 50 && !memcmp(data->s, "-----BEGIN PGP MESSAGE-----", 27)) {
        /* PGP encrypted body part - we don't want to index this,
         * it's a ton of random base64 noise */
    }
    else if (isbody && !strcmp(type, "TEXT")) {

        if (str->snippet_iteration >= 2) goto done;

        if (!strcmp(subtype, "CALENDAR")) {
#ifdef USE_HTTPD
            extract_icalbuf(data, charset, encoding, content_guid, str);
#endif /* USE_HTTPD */
        }
        else if (!strcmp(subtype, "VCARD")) {
#ifdef USE_HTTPD
            extract_vcardbuf(data, charset, encoding, content_guid, str);
#endif /* USE_HTTPD */
        }
        else {
            /* body-like */
            str->receiver->begin_part(str->receiver, SEARCH_PART_BODY, content_guid);
            charset_extract(extract_cb, str, data, charset, encoding, subtype,
                            str->charset_flags);
            str->receiver->end_part(str->receiver, SEARCH_PART_BODY);
        }
    }
    else if (isbody && !strcmp(type, "APPLICATION")) {

        /* Ignore attachments in first snippet generation pass */
        if (str->snippet_iteration == 1) goto done;

        /* Only generate snippets from named attachmend parts */
        if (str->snippet_iteration >= 2 && !str->partids) goto done;

        r = extract_attachment(type, subtype, type_params, data, encoding,
                               content_guid, str);
        if (r) {
            syslog(LOG_ERR, "index: can't extract text from attachment: %s",
                    error_message(r));
            goto done;
        }
    }

done:
    return r;
}

static void append_alnum(struct buf *buf, const char *ss)
{
    const unsigned char *s = (const unsigned char *)ss;

    for ( ; *s ; ++s) {
        if (Uisalnum(*s))
            buf_putc(buf, *s);
    }
}

EXPORTED int index_getsearchtext(message_t *msg, const strarray_t *partids,
                                 search_text_receiver_t *receiver,
                                 int snippet)
{
    struct getsearchtext_rock str;
    struct buf buf = BUF_INITIALIZER;
    int format = MESSAGE_SEARCH;
    strarray_t types = STRARRAY_INITIALIZER;
    const char *type = NULL, *subtype = NULL;
    int i;
    int r;

    /* Determine Content-Type */
    r = message_get_type(msg, &type);
    if (r) return r;
    r = message_get_subtype(msg, &subtype);
    if (r) return r;

    /* Set up search receiver */
    r = receiver->begin_message(receiver, msg);
    if (r) return r;

    memset(&str, 0, sizeof(struct getsearchtext_rock));
    str.receiver = receiver;
    str.indexed_headers = 0;
    str.charset_flags = charset_flags;
    str.partids = partids;
    str.snippet_iteration = 0;

    /* Search receiver can override text conversion */
    if (receiver->index_charset_flags) {
        str.charset_flags = receiver->index_charset_flags(str.charset_flags);
    }

    if (snippet) {
        str.charset_flags |= CHARSET_KEEPCASE;
        format = MESSAGE_SNIPPET;
    }

    /* Choose index scheme for Content=Type */
    if (!strcasecmp(type, "TEXT") && !strcasecmp(subtype, "CALENDAR")) {
#ifdef USE_HTTPD
        /* An iCalendar entry. */
        struct buf buf = BUF_INITIALIZER;
        int encoding = 0;
        const char *charset_id = NULL;
        charset_t charset = CHARSET_UNKNOWN_CHARSET;
        const struct body *body = NULL;

        r = message_get_field(msg, "rawbody", MESSAGE_RAW, &buf);
        if (!r) r = message_get_cachebody(msg, &body);
        if (!r) r = message_get_encoding(msg, &encoding);
        if (!r) r = message_get_charset_id(msg, &charset_id);
        if (!r) charset = charset_lookupname(charset_id);
        if (charset != CHARSET_UNKNOWN_CHARSET)
            r = extract_icalbuf(&buf, charset, encoding, &body->content_guid, &str);
        charset_free(&charset);
        buf_free(&buf);
#endif
    }
    else {
        if (!message_get_field(msg, "From", format, &buf))
            stuff_part(receiver, SEARCH_PART_FROM, NULL, &buf);

        if (!message_get_field(msg, "To", format, &buf))
            stuff_part(receiver, SEARCH_PART_TO, NULL, &buf);

        if (!message_get_field(msg, "Cc", format, &buf))
            stuff_part(receiver, SEARCH_PART_CC, NULL, &buf);

        if (!message_get_field(msg, "Bcc", format, &buf))
            stuff_part(receiver, SEARCH_PART_BCC, NULL, &buf);

        if (!message_get_field(msg, "Subject", format, &buf))
            stuff_part(receiver, SEARCH_PART_SUBJECT, NULL, &buf);

        if (!message_get_field(msg, "List-Id", format, &buf))
            stuff_part(receiver, SEARCH_PART_LISTID, NULL, &buf);

        if (!message_get_field(msg, "Mailing-List", format, &buf))
            stuff_part(receiver, SEARCH_PART_LISTID, NULL, &buf);

        if (!message_get_leaf_types(msg, &types) && types.count) {
            /* We add three search terms: the type, subtype, and a combined
             * type+subtype string.  We carefully control punctuation to
             * ensure that each word in indexed as a single term.  For
             * example if the original message has "application/x-pdf" then
             * we index "APPLICATION" "XPDF" "APPLICATION_XPDF".  */

            receiver->begin_part(receiver, SEARCH_PART_TYPE, NULL);
            for (i = 0 ; i < types.count ; i+= 2) {
                buf_reset(&buf);

                if (i) buf_putc(&buf, ' ');

                /* type */
                append_alnum(&buf, types.data[i]);
                buf_putc(&buf, ' ');
                /* subtype */
                append_alnum(&buf, types.data[i+1]);
                buf_putc(&buf, ' ');
                /* combined type_subtype */
                append_alnum(&buf, types.data[i]);
                buf_putc(&buf, '_');
                append_alnum(&buf, types.data[i+1]);

                receiver->append_text(receiver, &buf);
            }
            receiver->end_part(receiver, SEARCH_PART_TYPE);
        }

        /* A regular message. Generate snippets in two passes. */
        str.snippet_iteration = snippet ? 1 : 0;
        r = message_foreach_section(msg, getsearchtext_cb, &str);
        if (snippet) {
            if (receiver->flush) {
                r = receiver->flush(receiver);
            }
            if (!r) {
                str.snippet_iteration = 2;
                r = message_foreach_section(msg, getsearchtext_cb, &str);
            }
            if (r == IMAP_OK_COMPLETED) r = 0;
        }
        if (r) goto done;
    }

    r = receiver->end_message(receiver);

done:
    buf_free(&buf);
    strarray_fini(&types);

    return r;
}

/*
 * Helper function to set up arguments to append_copy()
 */
#define COPYARGSGROW 30
static int index_copysetup(struct index_state *state, uint32_t msgno,
                           struct copyargs *copyargs)
{
    struct index_map *im = &state->map[msgno-1];
    int r;

    if (copyargs->nummsg == copyargs->msgalloc) {
        copyargs->msgalloc += COPYARGSGROW;
        copyargs->records = (struct index_record *)
          xrealloc((char *)copyargs->records,
                   copyargs->msgalloc * sizeof(struct index_record));
    }

    r = index_reload_record(state, msgno, &copyargs->records[copyargs->nummsg]);
    if (r) return r;

    /* seen is per user - embed it in the record */
    if (im->isseen)
        copyargs->records[copyargs->nummsg].system_flags |= FLAG_SEEN;
    else
        copyargs->records[copyargs->nummsg].system_flags &= ~FLAG_SEEN;

    if (state->want_expunged && (im->internal_flags & FLAG_INTERNAL_EXPUNGED)) {
        copyargs->records[copyargs->nummsg].system_flags &= ~FLAG_DELETED;
        copyargs->records[copyargs->nummsg].internal_flags &= ~FLAG_INTERNAL_EXPUNGED;
    }

    copyargs->nummsg++;

    return 0;
}

/*
 * Creates a list, and optionally also an array of pointers to, of msgdata.
 *
 * We fill these structs with the processed info that will be needed
 * by the specified sort criteria.
 */
MsgData **index_msgdata_load(struct index_state *state,
                             unsigned *msgno_list, int n,
                             const struct sortcrit *sortcrit,
                             unsigned int anchor, int *found_anchor)
{
    MsgData **ptrs, *md, *cur;
    int i, j;
    char *tmpenv;
    char *envtokens[NUMENVTOKENS];
    int did_cache, did_env, did_conv;
    int label;
    struct mailbox *mailbox = state->mailbox;
    struct index_record record;
    struct conversations_state *cstate = NULL;
    conversation_t conv = CONVERSATION_INIT;

    if (!n) return NULL;

    /* create an array of MsgData */
    ptrs = (MsgData **) xzmalloc(n * sizeof(MsgData *) + n * sizeof(MsgData));
    md = (MsgData *)(ptrs + n);
    xstats_add(MSGDATA_LOAD, n);

    if (found_anchor)
        *found_anchor = 0;

    for (i = 0 ; i < n ; i++) {
        cur = &md[i];
        ptrs[i] = cur;

        /* set msgno */
        cur->msgno = (msgno_list ? msgno_list[i] : (unsigned)(i+1));

        if (index_reload_record(state, cur->msgno, &record))
            continue;

        cur->uid = record.uid;
        cur->cid = record.cid;
        cur->system_flags = record.system_flags;
        cur->internal_flags = record.internal_flags;
        message_guid_copy(&cur->guid, &record.guid);
        if (found_anchor && record.uid == anchor)
            *found_anchor = 1;

        /* useful for convupdates */
        cur->modseq = record.modseq;

        did_cache = did_env = did_conv = 0;
        tmpenv = NULL;

        for (j = 0; sortcrit[j].key; j++) {
            label = sortcrit[j].key;

            if ((label == SORT_CC ||
                 label == SORT_FROM || label == SORT_SUBJECT ||
                 label == SORT_TO || label == LOAD_IDS ||
                 label == SORT_DISPLAYFROM || label == SORT_DISPLAYTO ||
                 label == SORT_SPAMSCORE) &&
                !did_cache) {

                /* fetch cached info */
                if (mailbox_cacherecord(mailbox, &record))
                    continue; /* can't do this with a broken cache */

                did_cache++;
            }

            if ((label == LOAD_IDS) && !did_env) {
                /* no point if we don't have enough data */
                if (cacheitem_size(&record, CACHE_ENVELOPE) <= 2)
                    continue;

                /* make a working copy of envelope -- strip outer ()'s */
                /* +1 -> skip the leading paren */
                /* -2 -> don't include the size of the outer parens */
                tmpenv = xstrndup(cacheitem_base(&record, CACHE_ENVELOPE) + 1,
                                  cacheitem_size(&record, CACHE_ENVELOPE) - 2);

                /* parse envelope into tokens */
                parse_cached_envelope(tmpenv, envtokens,
                                      VECTOR_SIZE(envtokens));

                did_env++;
            }

            if ((label == SORT_HASCONVFLAG || label == SORT_CONVMODSEQ ||
                label == SORT_CONVEXISTS || label == SORT_CONVSIZE) && !did_conv) {
                if (!cstate) cstate = conversations_get_mbox(index_mboxname(state));
                assert(cstate);
                if (conversation_load_advanced(cstate, record.cid, &conv, /*flags*/0))
                    continue;
                did_conv++;
            }

            switch (label) {
            case SORT_CC:
                cur->cc = get_localpart_addr(cacheitem_base(&record, CACHE_CC));
                break;
            case SORT_DATE:
                cur->sentdate = record.gmtime;
                /* fall through */
            case SORT_ARRIVAL:
                cur->internaldate = record.internaldate;
                break;
            case SORT_FROM:
                cur->from = get_localpart_addr(cacheitem_base(&record, CACHE_FROM));
                break;
            case SORT_MODSEQ:
                /* already copied above */
                break;
            case SORT_CREATEDMODSEQ:
                cur->createdmodseq = record.createdmodseq;
                break;
            case SORT_SIZE:
                cur->size = record.size;
                break;
            case SORT_SUBJECT:
                cur->xsubj = index_extract_subject(cacheitem_base(&record, CACHE_SUBJECT),
                                                   cacheitem_size(&record, CACHE_SUBJECT),
                                                   &cur->is_refwd);
                cur->xsubj_hash = strhash(cur->xsubj);
                break;
            case SORT_TO:
                cur->to = get_localpart_addr(cacheitem_base(&record, CACHE_TO));
                break;
            case SORT_ANNOTATION: {
                struct buf value = BUF_INITIALIZER;

                annotatemore_msg_lookup(state->mboxname,
                                        record.uid,
                                        sortcrit[j].args.annot.entry,
                                        sortcrit[j].args.annot.userid,
                                        &value);

                /* buf_release() never returns NULL, so if the lookup
                 * fails for any reason we just get an empty string here */
                strarray_appendm(&cur->annot, buf_release(&value));
                break;
            }
            case SORT_SAVEDATE:
                if (!strcmpnull(mailbox->uniqueid, sortcrit[j].args.mailbox.id)) {
                    cur->savedate = record.savedate;
                }
                else {
                    /* If not in mailboxId, we use receivedAt */
                    cur->internaldate = record.internaldate;
                }
                break;
            case SORT_SNOOZEDUNTIL:
#ifdef WITH_JMAP
                if ((record.internal_flags & FLAG_INTERNAL_SNOOZED) &&
                    !strcmpnull(mailbox->uniqueid, sortcrit[j].args.mailbox.id)) {
                    /* SAVEDATE == snoozed#until */
                    cur->savedate = record.savedate;

                    if (!cur->savedate) {
                        /* Try fetching snoozed#until directly */
                        json_t *snoozed =
                            jmap_fetch_snoozed(mailbox->name, record.uid);

                        if (snoozed) {
                            time_from_iso8601(
                                json_string_value(json_object_get(snoozed,
                                                                  "until")),
                                &cur->savedate);
                            json_decref(snoozed);
                        }
                    }
                }
#endif
                if (!cur->savedate) {
                    /* If not snoozed in mailboxId, we use receivedAt */
                    cur->internaldate = record.internaldate;
                }
                break;
            case LOAD_IDS:
                index_get_ids(cur, envtokens, cacheitem_base(&record, CACHE_HEADERS),
                                              cacheitem_size(&record, CACHE_HEADERS));
                break;
            case SORT_DISPLAYFROM:
                cur->displayfrom = get_displayname(
                                   cacheitem_base(&record, CACHE_FROM));
                break;
            case SORT_DISPLAYTO:
                cur->displayto = get_displayname(
                                 cacheitem_base(&record, CACHE_TO));
                break;
            case SORT_SPAMSCORE: {
                const char *score = index_getheader(state, cur->msgno, "X-Spam-score");
                /* multiply by 100 to give an integer score */
                cur->spamscore = (int)((atof(score) * 100) + 0.5);
                break;
            }
            case SORT_HASFLAG: {
                const char *name = sortcrit[j].args.flag.name;
                if (mailbox_record_hasflag(mailbox, &record, name))
                    cur->hasflag |= (1<<j);
                break;
            }
            case SORT_HASCONVFLAG: {
                const char *name = sortcrit[j].args.flag.name;
                int idx = -1;
                if (cstate->counted_flags)
                    idx = strarray_find_case(cstate->counted_flags, name, 0);
                /* flag exists in the conversation at all */
                if (idx >= 0 && conv.counts[idx] > 0 && j < 31)
                    cur->hasflag |= (1<<j);
                break;
            }
            case SORT_CONVEXISTS:
                cur->convexists = conv.exists;
                break;
            case SORT_CONVSIZE:
                cur->convsize = conv.size;
                break;
            case SORT_CONVMODSEQ:
                cur->convmodseq = conv.modseq;
                break;
            case SORT_RELEVANCY:
                /* for now all messages have relevancy=100 */
                break;
            }
        }

        free(tmpenv);
        conversation_fini(&conv);
    }

    return ptrs;
}

static char *get_localpart_addr(const char *header)
{
    struct address *addr = NULL;
    char *ret = NULL;

    parseaddr_list(header, &addr);
    if (!addr) return NULL;

    if (addr->mailbox)
        ret = xstrdup(addr->mailbox);

    parseaddr_free(addr);

    return ret;
}

/*
 * Get the 'display-name' of an address from a header
 */
static char *get_displayname(const char *header)
{
    struct address *addr = NULL;
    char *ret = NULL;
    char *p;

    parseaddr_list(header, &addr);
    if (!addr) return NULL;

    if (addr->name && addr->name[0]) {
        /* pure RFC5255 compatible "searchform" conversion */
        ret = charset_utf8_to_searchform(addr->name, /*flags*/0);
    }
    else if (addr->domain && addr->mailbox) {
        ret = strconcat(addr->mailbox, "@", addr->domain, (char *)NULL);
        /* gotta uppercase mailbox/domain */
        for (p = ret; *p; p++)
            *p = toupper(*p);
    }
    else if (addr->mailbox) {
        ret = xstrdup(addr->mailbox);
        /* gotta uppercase mailbox/domain */
        for (p = ret; *p; p++)
            *p = toupper(*p);
    }

    parseaddr_free(addr);

    return ret;
}

/*
 * Extract base subject from subject header
 *
 * This is a wrapper around _index_extract_subject() which preps the
 * subj NSTRING and checks for Netscape "[Fwd: ]".
 */
static char *index_extract_subject(const char *subj, size_t len, int *is_refwd)
{
    char *rawbuf, *buf, *s, *base;

    /* parse the subj NSTRING and make a working copy */
    if (!strcmp(subj, "NIL")) {                 /* NIL? */
        return xstrdup("");                     /* yes, return empty */
    } else if (*subj == '"') {                  /* quoted? */
        rawbuf = xstrndup(subj + 1, len - 2);   /* yes, strip quotes */
    } else {
        s = strchr(subj, '}') + 3;              /* literal, skip { }\r\n */
        rawbuf = xstrndup(s, len - (s - subj));
    }

    buf = charset_parse_mimeheader(rawbuf, charset_flags);
    free(rawbuf);

    for (s = buf;;) {
        base = _index_extract_subject(s, is_refwd);

        /* If we have a Netscape "[Fwd: ...]", extract the contents */
        if (!strncasecmp(base, "[fwd:", 5) &&
            base[strlen(base) - 1]  == ']') {

            /* inc refwd counter */
            *is_refwd += 1;

            /* trim "]" */
            base[strlen(base) - 1] = '\0';

            /* trim "[fwd:" */
            s = base + 5;
        }
        else /* otherwise, we're done */
            break;
    }

    base = xstrdup(base);

    free(buf);

    for (s = base; *s; s++) {
        *s = toupper(*s);
    }

    return base;
}

/*
 * Guts of subject extraction.
 *
 * Takes a subject string and returns a pointer to the base.
 */
static char *_index_extract_subject(char *s, int *is_refwd)
{
    char *base, *x;

    /* trim trailer
     *
     * start at the end of the string and work towards the front,
     * resetting the end of the string as we go.
     */
    for (x = s + strlen(s) - 1; x >= s;) {
        if (Uisspace(*x)) {                             /* whitespace? */
            *x = '\0';                                  /* yes, trim it */
            x--;                                        /* skip past it */
        }
        else if (x - s >= 4 &&
                 !strncasecmp(x-4, "(fwd)", 5)) {       /* "(fwd)"? */
            *(x-4) = '\0';                              /* yes, trim it */
            x -= 5;                                     /* skip past it */
            *is_refwd += 1;                             /* inc refwd counter */
        }
        else
            break;                                      /* we're done */
    }

    /* trim leader
     *
     * start at the head of the string and work towards the end,
     * skipping over stuff we don't care about.
     */
    for (base = s; base;) {
        if (Uisspace(*base)) base++;                    /* whitespace? */

        /* possible refwd */
        else if ((!strncasecmp(base, "re", 2) &&        /* "re"? */
                  (x = base + 2)) ||                    /* yes, skip past it */
                 (!strncasecmp(base, "fwd", 3) &&       /* "fwd"? */
                  (x = base + 3)) ||                    /* yes, skip past it */
                 (!strncasecmp(base, "fw", 2) &&        /* "fw"? */
                  (x = base + 2))) {                    /* yes, skip past it */
            int count = 0;                              /* init counter */

            while (Uisspace(*x)) x++;                   /* skip whitespace */

            if (*x == '[') {                            /* start of blob? */
                for (x++; x;) {                         /* yes, get count */
                    if (!*x) {                          /* end of subj, quit */
                        x = NULL;
                        break;
                    }
                    else if (*x == ']') {               /* end of blob, done */
                        break;
                                        /* if we have a digit, and we're still
                                           counting, keep building the count */
                    } else if (cyrus_isdigit((int) *x) && count != -1) {
                        count = count * 10 + *x - '0';
                        if (count < 0) {                /* overflow */
                            count = -1; /* abort counting */
                        }
                    } else {                            /* no digit, */
                        count = -1;                     /*  abort counting */
                    }
                    x++;
                }

                if (x)                                  /* end of blob? */
                    x++;                                /* yes, skip past it */
                else
                    break;                              /* no, we're done */
            }

            while (Uisspace(*x)) x++;                   /* skip whitespace */

            if (*x == ':') {                            /* ending colon? */
                base = x + 1;                           /* yes, skip past it */
                *is_refwd += (count > 0 ? count : 1);   /* inc refwd counter
                                                           by count or 1 */
            }
            else
                break;                                  /* no, we're done */
        }

#if 0 /* do nested blobs - wait for decision on this */
        else if (*base == '[') {                        /* start of blob? */
            int count = 1;                              /* yes, */
            x = base + 1;                               /*  find end of blob */
            while (count) {                             /* find matching ']' */
                if (!*x) {                              /* end of subj, quit */
                    x = NULL;
                    break;
                }
                else if (*x == '[')                     /* new open */
                    count++;                            /* inc counter */
                else if (*x == ']')                     /* close */
                    count--;                            /* dec counter */
                x++;
            }

            if (!x)                                     /* blob didn't close */
                break;                                  /*  so quit */

            else if (*x)                                /* end of subj? */
                base = x;                               /* no, skip blob */
#else
        else if (*base == '[' &&                        /* start of blob? */
                 (x = strpbrk(base+1, "[]")) &&         /* yes, end of blob */
                 *x == ']') {                           /*  (w/o nesting)? */

            if (*(x+1))                                 /* yes, end of subj? */
                base = x + 1;                           /* no, skip blob */
#endif
            else
                break;                                  /* yes, return blob */
        }
        else
            break;                                      /* we're done */
    }

    return base;
}

/* Get message-id, and references/in-reply-to */

void index_get_ids(MsgData *msgdata, char *envtokens[], const char *headers,
                   unsigned size)
{
    static struct buf buf;
    strarray_t refhdr = STRARRAY_INITIALIZER;
    char *refstr, *ref, *in_reply_to;

    buf_reset(&buf);

    /* get msgid */
    msgdata->msgid = find_msgid(envtokens[ENV_MSGID], NULL);
     /* if we don't have one, create one */
    if (!msgdata->msgid) {
        buf_printf(&buf, "<Empty-ID: %u>", msgdata->msgno);
        msgdata->msgid = xstrdup(buf.s);
        buf_reset(&buf);
    }

    /* Copy headers to the buffer */
    buf_appendmap(&buf, headers, size);
    buf_cstring(&buf);

    /* grab the References header */
    strarray_append(&refhdr, "references");
    message_pruneheader(buf.s, &refhdr, 0);
    strarray_fini(&refhdr);

    if (buf.s) {
        /* allocate some space for refs */
        /* find references */
        refstr = buf.s;
        massage_header(refstr);
        while ((ref = find_msgid(refstr, &refstr)) != NULL)
            strarray_appendm(&msgdata->ref, ref);
    }

    /* if we have no references, try in-reply-to */
    if (!msgdata->ref.count) {
        /* get in-reply-to id */
        in_reply_to = find_msgid(envtokens[ENV_INREPLYTO], NULL);
        /* if we have an in-reply-to id, make it the ref */
        if (in_reply_to)
            strarray_appendm(&msgdata->ref, in_reply_to);
    }
}

/*
 * Function for comparing two integers.
 */
#ifdef HAVE_DECLARE_OPTIMIZE
static inline int numcmp(modseq_t n1, modseq_t n2)
    __attribute__((pure, always_inline, optimize("-O3")));
#endif
static int numcmp(modseq_t n1, modseq_t n2)
{
    if (n1 < n2) return -1;
    if (n1 > n2) return 1;
    return 0;
    return ((n1 < n2) ? -1 : (n1 > n2) ? 1 : 0);
}

/*
 * Comparison function for sorting message lists.
 */
static int index_sort_compare(MsgData *md1, MsgData *md2,
                              const struct sortcrit *sortcrit)
{
    int reverse, ret = 0, i = 0, ann = 0;

    do {
        /* determine sort order from reverse flag bit */
        reverse = sortcrit[i].flags & SORT_REVERSE;

        switch (sortcrit[i].key) {
        case SORT_SEQUENCE:
            ret = numcmp(md1->msgno, md2->msgno);
            break;
        case SORT_ARRIVAL:
            ret = numcmp(md1->internaldate, md2->internaldate);
            break;
        case SORT_CC:
            ret = strcmpsafe(md1->cc, md2->cc);
            break;
        case SORT_DATE: {
            time_t d1 = md1->sentdate ? md1->sentdate : md1->internaldate;
            time_t d2 = md2->sentdate ? md2->sentdate : md2->internaldate;
            ret = numcmp(d1, d2);
            break;
        }
        case SORT_SNOOZEDUNTIL:
        case SORT_SAVEDATE: {
            time_t d1 = md1->savedate ? md1->savedate : md1->internaldate;
            time_t d2 = md2->savedate ? md2->savedate : md2->internaldate;
            ret = numcmp(d1, d2);
            break;
        }
        case SORT_FROM:
            ret = strcmpsafe(md1->from, md2->from);
            break;
        case SORT_SIZE:
            ret = numcmp(md1->size, md2->size);
            break;
        case SORT_SUBJECT:
            ret = strcmpsafe(md1->xsubj, md2->xsubj);
            break;
        case SORT_TO:
            ret = strcmpsafe(md1->to, md2->to);
            break;
        case SORT_ANNOTATION:
            ret = strcmpsafe(md1->annot.data[ann], md2->annot.data[ann]);
            ann++;
            break;
        case SORT_MODSEQ:
            ret = numcmp(md1->modseq, md2->modseq);
            break;
        case SORT_CREATEDMODSEQ:
            ret = numcmp(md1->createdmodseq, md2->createdmodseq);
            break;
        case SORT_DISPLAYFROM:
            ret = strcmpsafe(md1->displayfrom, md2->displayfrom);
            break;
        case SORT_DISPLAYTO:
            ret = strcmpsafe(md1->displayto, md2->displayto);
            break;
        case SORT_UID:
            ret = numcmp(md1->uid, md2->uid);
            break;
        case SORT_CONVMODSEQ:
            ret = numcmp(md1->convmodseq, md2->convmodseq);
            break;
        case SORT_CONVEXISTS:
            ret = numcmp(md1->convexists, md2->convexists);
            break;
        case SORT_CONVSIZE:
            ret = numcmp(md1->convsize, md2->convsize);
            break;
        case SORT_SPAMSCORE:
            ret = numcmp(md1->spamscore, md2->spamscore);
            break;
        case SORT_HASFLAG:
        case SORT_HASCONVFLAG:
            if (i < 31)
                ret = numcmp(md1->hasflag & (1<<i),
                             md2->hasflag & (1<<i));
            break;
        case SORT_FOLDER:
            if (md1->folder && md2->folder)
                ret = strcmpsafe(md1->folder->mboxname, md2->folder->mboxname);
            break;
        case SORT_RELEVANCY:
            ret = 0;        /* for now all messages have relevancy=100 */
            break;
        case SORT_GUID:
            ret = message_guid_cmp(&md1->guid, &md2->guid);
            break;
        }
    } while (!ret && sortcrit[i++].key != SORT_SEQUENCE);

    // must be multi-folder with the same UID!  tiebreaker is GUID
    if (!ret) return message_guid_cmp(&md1->guid, &md2->guid);

    return (reverse ? -ret : ret);
}

static int sortcrit_is_uid(const struct sortcrit *sortcrit)
{
    if ((sortcrit->flags & SORT_REVERSE)) return 0;
    if (!(sortcrit->key == SORT_SEQUENCE)) return 0;
    return 1;
}

static int sortcrit_is_reverse_uid(const struct sortcrit *sortcrit)
{
    if (!(sortcrit->flags & SORT_REVERSE)) return 0;
    if (!(sortcrit->key == SORT_SEQUENCE)) return 0;
    return 1;
}

static int sortcrit_is_modseq(const struct sortcrit *sortcrit)
{
    if ((sortcrit->flags & SORT_REVERSE)) return 0;
    if (!(sortcrit->key == SORT_MODSEQ)) return 0;
    sortcrit++;
    if ((sortcrit->flags & SORT_REVERSE)) return 0;
    if (!(sortcrit->key == SORT_SEQUENCE)) return 0;
    return 1;
}

static int sortcrit_is_arrival(const struct sortcrit *sortcrit)
{
    if ((sortcrit->flags & SORT_REVERSE)) return 0;
    if (!(sortcrit->key == SORT_ARRIVAL)) return 0;
    sortcrit++;
    if ((sortcrit->flags & SORT_REVERSE)) return 0;
    if (!(sortcrit->key == SORT_SEQUENCE)) return 0;
    return 1;
}

static int sortcrit_is_reverse_arrival(const struct sortcrit *sortcrit)
{
    if (!(sortcrit->flags & SORT_REVERSE)) return 0;
    if (!(sortcrit->key == SORT_ARRIVAL)) return 0;
    sortcrit++;
    if ((sortcrit->flags & SORT_REVERSE)) return 0;
    if (!(sortcrit->key == SORT_SEQUENCE)) return 0;
    return 1;
}

static int sortcrit_is_reverse_flagged(const struct sortcrit *sortcrit)
{
    if (!(sortcrit->flags & SORT_REVERSE)) return 0;
    // both HASFLAG and HASCONVFLAG have the same representation internally
    if (!(sortcrit->key == SORT_HASFLAG ||
          sortcrit->key == SORT_HASCONVFLAG)) return 0;
    sortcrit++;
    if (!(sortcrit->flags & SORT_REVERSE)) return 0;
    if (!(sortcrit->key == SORT_ARRIVAL)) return 0;
    sortcrit++;
    if ((sortcrit->flags & SORT_REVERSE)) return 0;
    if (!(sortcrit->key == SORT_SEQUENCE)) return 0;
    return 1;
}

static int index_sort_compare_generic_qsort(const void *v1, const void *v2)
{
    MsgData *md1 = *(MsgData **)v1;
    MsgData *md2 = *(MsgData **)v2;

    return index_sort_compare(md1, md2, the_sortcrit);
}

#ifdef HAVE_DECLARE_OPTIMIZE
static inline int index_sort_compare_uid(const void *v1, const void *v2)
    __attribute__((pure, always_inline, optimize("-O3")));
#endif
static int index_sort_compare_uid(const void *v1, const void *v2)
{
    MsgData *md1 = *(MsgData **)v1;
    MsgData *md2 = *(MsgData **)v2;
    int ret;

    ret = md1->uid - md2->uid;
    if (ret) return ret;

    return message_guid_cmp(&md1->guid, &md2->guid);
}

#ifdef HAVE_DECLARE_OPTIMIZE
static inline int index_sort_compare_reverse_uid(const void *v1, const void *v2)
    __attribute__((pure, always_inline, optimize("-O3")));
#endif
static int index_sort_compare_reverse_uid(const void *v1, const void *v2)
{
    MsgData *md1 = *(MsgData **)v1;
    MsgData *md2 = *(MsgData **)v2;
    int ret;

    ret = md2->uid - md1->uid;
    if (ret) return ret;

    return message_guid_cmp(&md1->guid, &md2->guid);
}

#ifdef HAVE_DECLARE_OPTIMIZE
static inline int index_sort_compare_modseq(const void *v1, const void *v2)
    __attribute__((pure, always_inline, optimize("-O3")));
#endif
static int index_sort_compare_modseq(const void *v1, const void *v2)
{
    MsgData *md1 = *(MsgData **)v1;
    MsgData *md2 = *(MsgData **)v2;
    int ret;

    ret = md1->modseq - md2->modseq;
    if (ret) return ret;

    ret = md1->uid - md2->uid;
    if (ret) return ret;

    return message_guid_cmp(&md1->guid, &md2->guid);
}

#ifdef HAVE_DECLARE_OPTIMIZE
static inline int index_sort_compare_arrival(const void *v1, const void *v2)
    __attribute__((pure, always_inline, optimize("-O3")));
#endif
static int index_sort_compare_arrival(const void *v1, const void *v2)
{
    MsgData *md1 = *(MsgData **)v1;
    MsgData *md2 = *(MsgData **)v2;
    int ret;

    ret = md1->internaldate - md2->internaldate;
    if (ret) return ret;

    ret = md1->createdmodseq - md2->createdmodseq;
    if (ret) return ret;

    ret = md1->uid - md2->uid;
    if (ret) return ret;

    return message_guid_cmp(&md1->guid, &md2->guid);
}

#ifdef HAVE_DECLARE_OPTIMIZE
static inline int index_sort_compare_reverse_arrival(const void *v1, const void *v2)
    __attribute__((pure, always_inline, optimize("-O3")));
#endif
static int index_sort_compare_reverse_arrival(const void *v1, const void *v2)
{
    MsgData *md1 = *(MsgData **)v1;
    MsgData *md2 = *(MsgData **)v2;
    int ret;

    ret = md2->internaldate - md1->internaldate;
    if (ret) return ret;

    ret = md2->createdmodseq - md1->createdmodseq;
    if (ret) return ret;

    ret = md1->uid - md2->uid;
    if (ret) return ret;

    return message_guid_cmp(&md1->guid, &md2->guid);
}

#ifdef HAVE_DECLARE_OPTIMIZE
static inline int index_sort_compare_reverse_flagged(const void *v1, const void *v2)
    __attribute__((pure, always_inline, optimize("-O3")));
#endif
static int index_sort_compare_reverse_flagged(const void *v1, const void *v2)
{
    MsgData *md1 = *(MsgData **)v1;
    MsgData *md2 = *(MsgData **)v2;
    int ret;

    ret = md2->hasflag - md1->hasflag;
    if (ret) return ret;

    ret = md2->internaldate - md1->internaldate;
    if (ret) return ret;

    ret = md2->createdmodseq - md1->createdmodseq;
    if (ret) return ret;

    ret = md1->uid - md2->uid;
    if (ret) return ret;

    return message_guid_cmp(&md1->guid, &md2->guid);
}

void index_msgdata_sort(MsgData **msgdata, int n, const struct sortcrit *sortcrit)
{
    if (sortcrit_is_uid(sortcrit)) {
        qsort(msgdata, n, sizeof(MsgData *), index_sort_compare_uid);
    }
    else if (sortcrit_is_reverse_uid(sortcrit)) {
        qsort(msgdata, n, sizeof(MsgData *), index_sort_compare_reverse_uid);
    }
    else if (sortcrit_is_modseq(sortcrit)) {
        qsort(msgdata, n, sizeof(MsgData *), index_sort_compare_modseq);
    }
    else if (sortcrit_is_arrival(sortcrit)) {
        qsort(msgdata, n, sizeof(MsgData *), index_sort_compare_arrival);
    }
    else if (sortcrit_is_reverse_arrival(sortcrit)) {
        qsort(msgdata, n, sizeof(MsgData *), index_sort_compare_reverse_arrival);
    }
    else if (sortcrit_is_reverse_flagged(sortcrit)) {
        qsort(msgdata, n, sizeof(MsgData *), index_sort_compare_reverse_flagged);
    }
    else {
        char *tmp = sortcrit_as_string(sortcrit);
        syslog(LOG_DEBUG, "GENERICSORT: %s", tmp);
        free(tmp);
        the_sortcrit = (struct sortcrit *)sortcrit;
        qsort(msgdata, n, sizeof(MsgData *), index_sort_compare_generic_qsort);
    }
}

/*
 * Free an array of MsgData* as built by index_msgdata_load()
 */
void index_msgdata_free(MsgData **msgdata, unsigned int n)
{
    unsigned int i;

    if (!msgdata)
        return;
    for (i = 0 ; i < n ; i++) {
        MsgData *md = msgdata[i];

        if (!md) continue;

        xfree(md->cc);
        xfree(md->from);
        xfree(md->to);
        xfree(md->displayfrom);
        xfree(md->displayto);
        xfree(md->xsubj);
        xfree(md->msgid);
        xfree(md->listid);
        xfree(md->contenttype);
        strarray_fini(&md->ref);
        strarray_fini(&md->annot);
    }
    free(msgdata);
}

/*
 * Getnext function for sorting thread lists.
 */
static void *index_thread_getnext(Thread *thread)
{
    return thread->next;
}

/*
 * Setnext function for sorting thread lists.
 */
static void index_thread_setnext(Thread *thread, Thread *next)
{
    thread->next = next;
}

/*
 * Comparison function for sorting threads.
 */
static int index_thread_compare(Thread *t1, Thread *t2,
                                const struct sortcrit *call_data)
{
    MsgData *md1, *md2;

    /* if the container is empty, use the first child's container */
    md1 = t1->msgdata ? t1->msgdata : t1->child->msgdata;
    md2 = t2->msgdata ? t2->msgdata : t2->child->msgdata;
    return index_sort_compare(md1, md2, call_data);
}

/*
 * Sort a list of threads.
 */
static void index_thread_sort(Thread *root,
                              const struct sortcrit *sortcrit)
{
    Thread *child;

    /* sort the grandchildren */
    child = root->child;
    while (child) {
        /* if the child has children, sort them */
        if (child->child)
            index_thread_sort(child, sortcrit);
        child = child->next;
    }

    /* sort the children */
    root->child = lsort(root->child,
                        (void * (*)(void*)) index_thread_getnext,
                        (void (*)(void*,void*)) index_thread_setnext,
                        (int (*)(void*,void*,void*)) index_thread_compare,
                        (void *)sortcrit);
}

/*
 * Thread a list of messages using the ORDEREDSUBJECT algorithm.
 */
static void index_thread_orderedsubj(struct index_state *state,
                                     unsigned *msgno_list, unsigned int nmsg,
                                     int usinguid)
{
    MsgData **msgdata;
    unsigned int mi;
    static const struct sortcrit sortcrit[] =
                                 {{ SORT_SUBJECT,  0, {{NULL, NULL}} },
                                  { SORT_DATE,     0, {{NULL, NULL}} },
                                  { SORT_SEQUENCE, 0, {{NULL, NULL}} }};
    unsigned psubj_hash = 0;
    char *psubj;
    Thread *head, *newnode, *cur, *parent, *last;

    /* Create/load the msgdata array */
    msgdata = index_msgdata_load(state, msgno_list, nmsg, sortcrit, 0, NULL);

    /* Sort messages by subject and date */
    index_msgdata_sort(msgdata, nmsg, sortcrit);

    /* create an array of Thread to use as nodes of thread tree
     *
     * we will be building threads under a dummy head,
     * so we need (nmsg + 1) nodes
     */
    head = (Thread *) xzmalloc((nmsg + 1) * sizeof(Thread));

    newnode = head + 1; /* set next newnode to the second
                           one in the array (skip the head) */
    parent = head;      /* parent is the head node */
    psubj = NULL;       /* no previous subject */
    cur = NULL;         /* no current thread */
    last = NULL;        /* no last child */

    for (mi = 0 ; mi < nmsg ; mi++) {
        MsgData *msg = msgdata[mi];
        newnode->msgdata = msg;

        /* if no previous subj, or
           current subj = prev subj (subjs have same hash, and
           the strings are equal), then add message to current thread */
        if (!psubj ||
            (msg->xsubj_hash == psubj_hash &&
             !strcmp(msg->xsubj, psubj))) {
            /* if no children, create first child */
            if (!parent->child) {
                last = parent->child = newnode;
                if (!cur)               /* first thread */
                    parent = cur = parent->child;
            }
            /* otherwise, add to siblings */
            else {
                last->next = newnode;
                last = last->next;
            }
        }
        /* otherwise, create a new thread */
        else {
            cur->next = newnode;        /* create and start a new thread */
            parent = cur = cur->next;   /* now work with the new thread */
        }

        psubj_hash = msg->xsubj_hash;
        psubj = msg->xsubj;
        newnode++;
    }

    /* Sort threads by date */
    index_thread_sort(head, sortcrit+1);

    /* Output the threaded messages */
    index_thread_print(state, head, usinguid);

    /* free the thread array */
    free(head);

    /* free the msgdata array */
    index_msgdata_free(msgdata, nmsg);
}

/*
 * Guts of thread printing.  Recurses over children when necessary.
 *
 * Frees contents of msgdata as a side effect.
 */
static void _index_thread_print(struct index_state *state,
                                Thread *thread, int usinguid)
{
    Thread *child;

    /* for each thread... */
    while (thread) {
        /* start the thread */
        prot_printf(state->out, "(");

        /* if we have a message, print its identifier
         * (do nothing for empty containers)
         */
        if (thread->msgdata && thread->msgdata->uid) {
            prot_printf(state->out, "%u",
                        usinguid ? thread->msgdata->uid :
                        thread->msgdata->msgno);

            /* if we have a child, print the parent-child separator */
            if (thread->child) prot_printf(state->out, " ");
        }

        /* for each child, grandchild, etc... */
        child = thread->child;
        while (child) {
            /* if the child has siblings, print new branch and break */
            if (child->next) {
                _index_thread_print(state, child, usinguid);
                break;
            }
            /* otherwise print the only child */
            else {
                prot_printf(state->out, "%u",
                            usinguid ? child->msgdata->uid :
                            child->msgdata->msgno);

                /* if we have a child, print the parent-child separator */
                if (child->child) prot_printf(state->out, " ");

                child = child->child;
            }
        }

        /* end the thread */
        prot_printf(state->out, ")");

        thread = thread->next;
    }
}

/*
 * Print a list of threads.
 *
 * This is a wrapper around _index_thread_print() which simply prints the
 * start and end of the untagged thread response.
 */
static void index_thread_print(struct index_state *state,
                               Thread *thread, int usinguid)
{
    prot_printf(state->out, "* THREAD");

    if (thread) {
        prot_printf(state->out, " ");
        _index_thread_print(state, thread->child, usinguid);
    }
}

/*
 * Find threading algorithm for given arg.
 * Returns index into thread_algs[], or -1 if not found.
 */
EXPORTED int find_thread_algorithm(char *arg)
{
    int alg;

    ucase(arg);
    for (alg = 0; thread_algs[alg].alg_name; alg++) {
        if (!strcmp(arg, thread_algs[alg].alg_name))
            return alg;
    }
    return -1;
}

/*
 * The following code is an interpretation of JWZ's description
 * and pseudo-code in http://www.jwz.org/doc/threading.html.
 *
 * It has been modified to match the THREAD=REFERENCES algorithm.
 */

/*
 * Determines if child is a descendent of parent.
 *
 * Returns 1 if yes, 0 otherwise.
 */
static int thread_is_descendent(Thread *parent, Thread *child)
{
    Thread *kid;

    /* self */
    if (parent == child)
        return 1;

    /* search each child's descendents */
    for (kid = parent->child; kid; kid = kid->next) {
        if (thread_is_descendent(kid, child))
            return 1;
    }
    return 0;
}

/*
 * Links child into parent's children.
 */
static void thread_adopt_child(Thread *parent, Thread *child)
{
    child->parent = parent;
    child->next = parent->child;
    parent->child = child;
}

/*
 * Unlinks child from it's parent's children.
 */
static void thread_orphan_child(Thread *child)
{
    Thread *prev, *cur;

    /* sanity check -- make sure child is actually a child of parent */
    for (prev = NULL, cur = child->parent->child;
         cur != child && cur != NULL; prev = cur, cur = cur->next);

    if (!cur) {
        /* uh oh!  couldn't find the child in it's parent's children
         * we should probably return NO to thread command
         */
        return;
    }

    /* unlink child */
    if (!prev)  /* first child */
        child->parent->child = child->next;
    else
        prev->next = child->next;
    child->parent = child->next = NULL;
}

/*
 * Link messages together using message-id and references.
 */
static void ref_link_messages(MsgData **msgdata, unsigned int nmsg,
                              Thread **newnode, struct hash_table *id_table)
{
    Thread *cur, *parent, *ref;
    unsigned int mi;
    int dup_count = 0;
    char buf[100];
    int i;

    /* for each message... */
    for (mi = 0 ; mi < nmsg ; mi++) {
        MsgData *msg = msgdata[mi];

        /* fill the containers with msgdata
         *
         * if we already have a container, use it
         */
        if ((cur = (Thread *) hash_lookup(msg->msgid, id_table))) {
            /* If this container is not empty, then we have a duplicate
             * Message-ID.  Make this one unique so that we don't stomp
             * on the old one.
             */
            if (cur->msgdata) {
                snprintf(buf, sizeof(buf), "-dup%d", dup_count++);
                msg->msgid =
                    (char *) xrealloc(msg->msgid,
                                      strlen(msg->msgid) + strlen(buf) + 1);
                strcat(msg->msgid, buf);
                /* clear cur so that we create a new container */
                cur = NULL;
            }
            else
                cur->msgdata = msg;
        }

        /* otherwise, make and index a new container */
        if (!cur) {
            cur = *newnode;
            cur->msgdata = msg;
            hash_insert(msg->msgid, cur, id_table);
            (*newnode)++;
        }

        /* Step 1.A */
        for (i = 0, parent = NULL; i < msg->ref.count; i++) {
            /* if we don't already have a container for the reference,
             * make and index a new (empty) container
             */
            if (!(ref = (Thread *) hash_lookup(msg->ref.data[i], id_table))) {
                ref = *newnode;
                hash_insert(msg->ref.data[i], ref, id_table);
                (*newnode)++;
            }

            /* link the references together as parent-child iff:
             * - we won't change existing links, AND
             * - we won't create a loop
             */
            if (!ref->parent &&
                parent && !thread_is_descendent(ref, parent)) {
                thread_adopt_child(parent, ref);
            }

            parent = ref;
        }

        /* Step 1.B
         *
         * if we have a parent already, it is probably bogus (the result
         * of a truncated references field), so unlink from it because
         * we now have the actual parent
         */
        if (cur->parent) thread_orphan_child(cur);

        /* make the last reference the parent of our message iff:
         * - we won't create a loop
         */
        if (parent && !thread_is_descendent(cur, parent))
            thread_adopt_child(parent, cur);
    }
}

/*
 * Gather orphan messages under the root node.
 */
static void ref_gather_orphans(const char *key __attribute__((unused)),
                               void *data, void *rock)
{
    Thread *node = (Thread *)data;
    struct rootset *rootset = (struct rootset *)rock;

    /* we only care about nodes without parents */
    if (!node->parent) {
        if (node->next) {
            /* uh oh!  a node without a parent should not have a sibling
             * we should probably return NO to thread command
             */
            return;
        }

        /* add this node to root's children */
        node->next = rootset->root->child;
        rootset->root->child = node;
        rootset->nroot++;
    }
}

/*
 * Prune tree of empty containers.
 */
static void ref_prune_tree(Thread *parent)
{
    Thread *cur, *prev, *next, *child;

    for (prev = NULL, cur = parent->child, next = cur->next;
         cur;
         prev = cur, cur = next, next = (cur ? cur->next : NULL)) {

retry:
        /* if we have an empty container with no children, delete it */
        if (!cur->msgdata && !cur->child) {
            if (!prev)  /* first child */
                parent->child = cur->next;
            else
                prev->next = cur->next;

            /* we just removed cur from our list,
             * so we need to keep the same prev for the next pass
             */
            cur = prev;
        }

        /* if we have an empty container with children, AND
         * we're not at the root OR we only have one child,
         * then remove the container but promote its children to this level
         * (splice them into the current child list)
         */
        else if (!cur->msgdata && cur->child &&
                 (cur->parent || !cur->child->next)) {
            /* move cur's children into cur's place (start the splice) */
            if (!prev)  /* first child */
                parent->child = cur->child;
            else
                prev->next = cur->child;

            /* make cur's parent the new parent of cur's children
             * (they're moving in with grandma!)
             */
            child = cur->child;
            do {
                child->parent = cur->parent;
            } while (child->next && (child = child->next));

            /* make the cur's last child point to cur's next sibling
             * (finish the splice)
             */
            child->next = cur->next;

            /* we just replaced cur with it's children
             * so make it's first child the next node to process
             */
            next = cur->child;

            /* make cur childless and siblingless */
            cur->child = cur->next = NULL;

            /* we just removed cur from our list,
             * so we need to keep the same prev for the next pass
             */
            cur = prev;
        }

        /* if we have a message with children, prune it's children */
        else if (cur->child) {
            ref_prune_tree(cur);
            if (!cur->msgdata && !cur->child) {
                /* Did we end up with a completely empty node here?
                 * Go back and prune it too.  See Bug 3784.  */
                goto retry;
            }
        }
    }
}

/*
 * Sort the messages in the root set by date.
 */
static void ref_sort_root(Thread *root)
{
    Thread *cur;
    static const struct sortcrit sortcrit[] =
                                 {{ SORT_DATE,     0, {{NULL, NULL}} },
                                  { SORT_SEQUENCE, 0, {{NULL, NULL}} }};

    cur = root->child;
    while (cur) {
        /* if the message is a dummy, sort its children */
        if (!cur->msgdata) {
            cur->child = lsort(cur->child,
                               (void * (*)(void*)) index_thread_getnext,
                               (void (*)(void*,void*)) index_thread_setnext,
                               (int (*)(void*,void*,void*)) index_thread_compare,
                               (void *)sortcrit);
        }
        cur = cur->next;
    }

    /* sort the root set */
    root->child = lsort(root->child,
                        (void * (*)(void*)) index_thread_getnext,
                        (void (*)(void*,void*)) index_thread_setnext,
                        (int (*)(void*,void*,void*)) index_thread_compare,
                        (void *)sortcrit);
}

/*
 * Group threads with same subject.
 */
static void ref_group_subjects(Thread *root, unsigned nroot, Thread **newnode)
{
    Thread *cur, *old, *prev, *next, *child;
    struct hash_table subj_table;
    char *subj;

    /* Step 5.A: create a subj_table with one bucket for every possible
     * subject in the root set
     */
    construct_hash_table(&subj_table, nroot, 1);

    /* Step 5.B: populate the table with a container for each subject
     * at the root
     */
    for (cur = root->child; cur; cur = cur->next) {
        /* Step 5.B.i: find subject of the thread
         *
         * if the container is not empty, use it's subject
         */
        if (cur->msgdata)
            subj = cur->msgdata->xsubj;
        /* otherwise, use the subject of it's first child */
        else
            subj = cur->child->msgdata->xsubj;

        /* Step 5.B.ii: if subject is empty, skip it */
        if (!strlen(subj)) continue;

        /* Step 5.B.iii: lookup this subject in the table */
        old = (Thread *) hash_lookup(subj, &subj_table);

        /* Step 5.B.iv: insert the current container into the table iff:
         * - this subject is not in the table, OR
         * - this container is empty AND the one in the table is not
         *   (the empty one is more interesting as a root), OR
         * - the container in the table is a re/fwd AND this one is not
         *   (the non-re/fwd is the more interesting of the two)
         */
        if (!old ||
            (!cur->msgdata && old->msgdata) ||
            (old->msgdata && old->msgdata->is_refwd &&
             cur->msgdata && !cur->msgdata->is_refwd)) {
          hash_insert(subj, cur, &subj_table);
        }
    }

    /* 5.C - group containers with the same subject together */
    for (prev = NULL, cur = root->child, next = cur->next;
         cur;
         prev = cur, cur = next, next = (next ? next->next : NULL)) {
        /* Step 5.C.i: find subject of the thread
         *
         * if container is not empty, use it's subject
         */
        if (cur->msgdata)
            subj = cur->msgdata->xsubj;
        /* otherwise, use the subject of it's first child */
        else
            subj = cur->child->msgdata->xsubj;

        /* Step 5.C.ii: if subject is empty, skip it */
        if (!strlen(subj)) continue;

        /* Step 5.C.iii: lookup this subject in the table */
        old = (Thread *) hash_lookup(subj, &subj_table);

        /* Step 5.C.iv: if we found ourselves, skip it */
        if (!old || old == cur) continue;

        /* ok, we already have a container which contains our current subject,
         * so pull this container out of the root set, because we are going to
         * merge this node with another one
         */
        if (!prev)      /* we're at the root */
            root->child = cur->next;
        else
            prev->next = cur->next;
        cur->next = NULL;

        /* if both containers are dummies, append cur's children to old's */
        if (!old->msgdata && !cur->msgdata) {
            /* find old's last child */
            for (child = old->child; child->next; child = child->next);

            /* append cur's children to old's children list */
            child->next = cur->child;

            /* make old the parent of cur's children */
            for (child = cur->child; child; child = child->next)
                child->parent = old;

            /* make cur childless */
            cur->child = NULL;
        }

        /* if:
         * - old container is empty, OR
         * - the current message is a re/fwd AND the old one is not,
         * make the current container a child of the old one
         *
         * Note: we don't have to worry about the reverse cases
         * because step 5.B guarantees that they won't happen
         */
        else if (!old->msgdata ||
                 (cur->msgdata && cur->msgdata->is_refwd &&
                  !old->msgdata->is_refwd)) {
            thread_adopt_child(old, cur);
        }

        /* if both messages are re/fwds OR neither are re/fwds,
         * then make them both children of a new dummy container
         * (we don't want to assume any parent-child relationship between them)
         *
         * perhaps we can create a parent-child relationship
         * between re/fwds by counting the number of re/fwds
         *
         * Note: we need the hash table to still point to old,
         * so we must make old the dummy and make the contents of the
         * new container a copy of old's original contents
         */
        else {
            Thread *new = (*newnode)++;

            /* make new a copy of old (except parent and next) */
            new->msgdata = old->msgdata;
            new->child = old->child;
            new->next = NULL;

            /* make new the parent of it's newly adopted children */
            for (child = new->child; child; child = child->next)
                child->parent = new;

            /* make old the parent of cur and new */
            cur->parent = old;
            new->parent = old;

            /* empty old and make it have two children (cur and new) */
            old->msgdata = NULL;
            old->child = cur;
            cur->next = new;
        }

        /* we just removed cur from our list,
         * so we need to keep the same prev for the next pass
         */
        cur = prev;
    }

    free_hash_table(&subj_table, NULL);
}

/*
 * Guts of thread searching.  Recurses over children when necessary.
 */
static int _index_thread_search(struct index_state *state,
                                Thread *thread, int (*searchproc) (MsgData *))
{
    Thread *child;

    /* test the head node */
    if (thread->msgdata && searchproc(thread->msgdata)) return 1;

    /* test the children recursively */
    child = thread->child;
    while (child) {
        if (_index_thread_search(state, child, searchproc)) return 1;
        child = child->next;
    }

    /* if we get here, we struck out */
    return 0;
}

/*
 * Search a thread to see if it contains a message which matches searchproc().
 *
 * This is a wrapper around _index_thread_search() which iterates through
 * each thread and removes any which fail the searchproc().
 */
static void index_thread_search(struct index_state *state,
                                Thread *root, int (*searchproc) (MsgData *))
{
    Thread *cur, *prev, *next;

    for (prev = NULL, cur = root->child, next = cur->next;
         cur;
         prev = cur, cur= next, next = (cur ? cur->next : NULL)) {
        if (!_index_thread_search(state, cur, searchproc)) {
            /* unlink the thread from the list */
            if (!prev)  /* first thread */
                root->child = cur->next;
            else
                prev->next = cur->next;

            /* we just removed cur from our list,
             * so we need to keep the same prev for the next pass
             */
            cur = prev;
        }
    }
}

/*
 * Guts of the REFERENCES algorithms.  Behavior is tweaked with loadcrit[],
 * threadproc(), searchproc() and sortcrit[].
 */
static void _index_thread_ref(struct index_state *state, unsigned *msgno_list,
                              unsigned int nmsg,
                              const struct sortcrit loadcrit[],
                              MsgData **(*threadproc) (struct rootset *, Thread **),
                              int (*searchproc) (MsgData *),
                              const struct sortcrit sortcrit[], int usinguid)
{
    MsgData **msgdata, **thrdata = NULL;
    unsigned int mi;
    int tref, nnode;
    Thread *newnode;
    struct hash_table id_table;
    struct rootset rootset;

    /* Create/load the msgdata array */
    msgdata = index_msgdata_load(state, msgno_list, nmsg, loadcrit, 0, NULL);

    /* calculate the sum of the number of references for all messages */
    for (mi = 0, tref = 0 ; mi < nmsg ; mi++)
        tref += msgdata[mi]->ref.count;

    /* create an array of Thread to use as nodes of thread tree (including
     * empty containers)
     *
     * - We will be building threads under a dummy root, so we need at least
     *   (nmsg + 1) nodes.
     * - We also will need containers for references to non-existent messages.
     *   To make sure we have enough, we will take the worst case and
     *   use the sum of the number of references for all messages.
     * - Finally, we will need containers to group threads with the same
     *   subject together.  To make sure we have enough, we will take the
     *   worst case which will be half of the number of messages.
     *
     * This is overkill, but it is the only way to make sure we have enough
     * ahead of time.  If we tried to use xrealloc(), the array might be moved,
     * and our parent/child/next pointers will no longer be correct
     * (been there, done that).
     */
    nnode = (int) (1.5 * nmsg + 1 + tref);
    rootset.root = (Thread *) xmalloc(nnode * sizeof(Thread));
    memset(rootset.root, 0, nnode * sizeof(Thread));

    newnode = rootset.root + 1; /* set next newnode to the second
                                   one in the array (skip the root) */

    /* Step 0: create an id_table with one bucket for every possible
     * message-id and reference (nmsg + tref)
     */
    construct_hash_table(&id_table, nmsg + tref, 1);

    /* Step 1: link messages together */
    ref_link_messages(msgdata, nmsg, &newnode, &id_table);

    /* Step 2: find the root set (gather all of the orphan messages) */
    rootset.nroot = 0;
    hash_enumerate(&id_table, ref_gather_orphans, &rootset);

    /* discard id_table */
    free_hash_table(&id_table, NULL);

    /* Step 3: prune tree of empty containers - get our deposit back :^) */
    ref_prune_tree(rootset.root);

    /* Steps 4/5: algorithm-specific thread processing */
    if (threadproc) thrdata = threadproc(&rootset, &newnode);

    /* Optionally search threads (to be used by REFERENCES derivatives) */
    if (searchproc) index_thread_search(state, rootset.root, searchproc);

    /* Step 6: sort threads */
    if (sortcrit) index_thread_sort(rootset.root, sortcrit);

    /* Output the threaded messages */
    index_thread_print(state, rootset.root, usinguid);

    /* free the thread array */
    free(rootset.root);

    /* free the msgdata array */
    index_msgdata_free(msgdata, nmsg);
    index_msgdata_free(thrdata, rootset.nroot);
}

/*
 * Thread a list of messages using the REFERENCES algorithm.
 */
static MsgData **references_thread_proc(struct rootset *rootset,
                                        Thread **newnode)
{
    /* Step 4: sort the root set */
    ref_sort_root(rootset->root);
    
    /* Step 5: group root set by subject */
    ref_group_subjects(rootset->root, rootset->nroot, newnode);

    return NULL;
}

static void index_thread_references(struct index_state *state,
                                    unsigned *msgno_list, unsigned int nmsg,
                                    int usinguid)
{
    static const struct sortcrit loadcrit[] =
                                 {{ LOAD_IDS,      0, {{NULL,NULL}} },
                                  { SORT_SUBJECT,  0, {{NULL,NULL}} },
                                  { SORT_DATE,     0, {{NULL,NULL}} },
                                  { SORT_SEQUENCE, 0, {{NULL,NULL}} }};
    static const struct sortcrit sortcrit[] =
                                 {{ SORT_DATE,     0, {{NULL,NULL}} },
                                  { SORT_SEQUENCE, 0, {{NULL,NULL}} }};

    _index_thread_ref(state, msgno_list, nmsg, loadcrit,
                      references_thread_proc, NULL, sortcrit, usinguid);
}

/* Find most recent internaldate of all messages in thread */
static void find_most_recent(Thread *thread, MsgData *recent)
{
    Thread *child;

    /* test the head node */
    if (thread->msgdata->internaldate > recent->internaldate)
        recent->internaldate = thread->msgdata->internaldate;

    /* test the children recursively */
    child = thread->child;
    while (child) {
        find_most_recent(child, recent);
        child = child->next;
    }
}

/*
 * Tag the root of each thread with the most recent internaldate of all
 * messages in the thread.  The actual sorting will be done by the calling
 * function, but we leverage the fact that sorting by sentdate will fallback
 * to internaldate if sentdate == 0.
 */
static MsgData **refs_thread_proc(struct rootset *rootset,
                                  Thread **newnode __attribute((unused)))
{
    MsgData **ptrs, *md;
    Thread *cur;
    int i = 0;

    /* Create an array of MsgData for dummy roots */
    ptrs = (MsgData **) xzmalloc(rootset->nroot *
                                 (sizeof(MsgData *) + sizeof(MsgData)));
    md = (MsgData *)(ptrs + rootset->nroot);

    /* Find most recent internaldate in each thread */
    cur = rootset->root->child;
    while (cur) {
        /* If the message is a dummy, assign it MsgData for sorting */
        if (!cur->msgdata) {
            cur->msgdata = ptrs[i] = &md[i];
            i++;
            cur->msgdata->internaldate = cur->child->msgdata->internaldate;
        }
        cur->msgdata->sentdate = 0; /* force date sort to use internaldate */

        find_most_recent(cur, cur->msgdata);
        cur = cur->next;
    }

    return ptrs;
}

/*
 * Thread a list of messages using the REFS algorithm.
 */
static void index_thread_refs(struct index_state *state,
                              unsigned *msgno_list, unsigned int nmsg,
                              int usinguid)
{
    static const struct sortcrit loadcrit[] =
                                 {{ LOAD_IDS,      0, {{NULL,NULL}} },
                                  { SORT_DATE,     0, {{NULL,NULL}} },
                                  { SORT_ARRIVAL,  0, {{NULL,NULL}} },
                                  { SORT_SEQUENCE, 0, {{NULL,NULL}} }};
    static const struct sortcrit sortcrit[] =
                                 {{ SORT_DATE,     0, {{NULL,NULL}} },
                                  { SORT_ARRIVAL,  0, {{NULL,NULL}} },
                                  { SORT_SEQUENCE, 0, {{NULL,NULL}} }};

    _index_thread_ref(state, msgno_list, nmsg, loadcrit,
                      refs_thread_proc, NULL, sortcrit, usinguid);
}

/*
 * NNTP specific stuff.
 */
EXPORTED char *index_get_msgid(struct index_state *state,
                               uint32_t msgno)
{
    struct mailbox *mailbox = state->mailbox;
    struct index_record record;

    if (index_reload_record(state, msgno, &record))
        return NULL;

    return mailbox_cache_get_env(mailbox, &record, ENV_MSGID);
}

static void massage_header(char *hdr)
{
    int n = 0;
    char *p, c;

    for (p = hdr; *p; p++) {
        if (*p == ' ' || *p == '\t' || *p == '\r') {
            if (!n || *(p+1) == '\n') {
                /* no leading or trailing whitespace */
                continue;
            }
            /* replace with space */
            c = ' ';
        }
        else if (*p == '\n') {
            if (*(p+1) == ' ' || *(p+1) == '\t') {
                /* folded header */
                continue;
            }
            /* end of header */
            break;
        }
        else
            c = *p;

        hdr[n++] = c;
    }
    hdr[n] = '\0';
}

EXPORTED extern struct nntp_overview *index_overview(struct index_state *state,
                                                     uint32_t msgno)
{
    static struct nntp_overview over;
    static char *env = NULL, *from = NULL, *hdr = NULL;
    static int envsize = 0, fromsize = 0, hdrsize = 0;
    int size;
    char *envtokens[NUMENVTOKENS];
    struct address addr = { NULL, NULL, NULL, NULL, NULL, NULL, 0 };
    strarray_t refhdr = STRARRAY_INITIALIZER;
    struct mailbox *mailbox = state->mailbox;
    struct index_record record;

    /* flush any previous data */
    memset(&over, 0, sizeof(struct nntp_overview));

    if (index_reload_record(state, msgno, &record))
        return NULL;

    if (mailbox_cacherecord(mailbox, &record))
        return NULL; /* upper layers can cope! */

    /* make a working copy of envelope; strip outer ()'s */
    /* -2 -> don't include the size of the outer parens */
    /* +1 -> leave space for NUL */
    size = cacheitem_size(&record, CACHE_ENVELOPE) - 2 + 1;
    if (envsize < size) {
        envsize = size;
        env = xrealloc(env, envsize);
    }
    /* +1 -> skip the leading paren */
    strlcpy(env, cacheitem_base(&record, CACHE_ENVELOPE) + 1, size);

    /* make a working copy of headers */
    size = cacheitem_size(&record, CACHE_HEADERS);
    if (hdrsize < size+2) {
        hdrsize = size+100;
        hdr = xrealloc(hdr, hdrsize);
    }
    memcpy(hdr, cacheitem_base(&record, CACHE_HEADERS), size);
    hdr[size] = '\0';

    parse_cached_envelope(env, envtokens, VECTOR_SIZE(envtokens));

    over.uid = record.uid;
    over.bytes = record.size;
    over.lines = index_getlines(state, msgno);
    over.date = envtokens[ENV_DATE];
    over.msgid = envtokens[ENV_MSGID];

    /* massage subject */
    if ((over.subj = envtokens[ENV_SUBJECT]))
        massage_header(over.subj);

    /* build original From: header */
    if (envtokens[ENV_FROM]) /* paranoia */
        message_parse_env_address(envtokens[ENV_FROM], &addr);

    if (addr.mailbox && addr.domain) { /* paranoia */
        /* +3 -> add space for quotes and space */
        /* +4 -> add space for < @ > NUL */
        size = (addr.name ? strlen(addr.name) + 3 : 0) +
            strlen(addr.mailbox) + strlen(addr.domain) + 4;
        if (fromsize < size) {
            fromsize = size;
            from = xrealloc(from, fromsize);
        }
        from[0] = '\0';
        if (addr.name) sprintf(from, "\"%s\" ", addr.name);
        snprintf(from + strlen(from), fromsize - strlen(from),
                 "<%s@%s>", addr.mailbox, addr.domain);

        over.from = from;
    }

    /* massage references */
    strarray_append(&refhdr, "references");
    message_pruneheader(hdr, &refhdr, 0);
    strarray_fini(&refhdr);

    if (*hdr) {
        over.ref = hdr + 11; /* skip over header name */
        massage_header(over.ref);
    }

    return &over;
}

EXPORTED extern char *index_getheader(struct index_state *state,
                                      uint32_t msgno, char *hdr)
{
    static struct buf staticbuf = BUF_INITIALIZER;
    strarray_t headers = STRARRAY_INITIALIZER;
    struct mailbox *mailbox = state->mailbox;
    struct index_record record;
    char *buf;

    if (index_reload_record(state, msgno, &record))
        return NULL;

    /* see if the header is cached */
    if (mailbox_cached_header(hdr) != BIT32_MAX &&
        !mailbox_cacherecord(mailbox, &record)) {
        buf_copy(&staticbuf, cacheitem_buf(&record, CACHE_HEADERS));
    }
    else {
        /* uncached header */
        struct buf msgbuf = BUF_INITIALIZER;
        if (mailbox_map_record(mailbox, &record, &msgbuf))
            return NULL;
        buf_setcstr(&staticbuf, index_readheader(msgbuf.s, msgbuf.len, 0, record.header_size));
        buf_free(&msgbuf);
    }

    buf_cstring(&staticbuf);

    strarray_append(&headers, hdr);
    message_pruneheader(staticbuf.s, &headers, NULL);
    strarray_fini(&headers);

    buf = staticbuf.s;
    if (*buf) {
        buf += strlen(hdr) + 1; /* skip header: */
        massage_header(buf);
    }

    return buf;
}

EXPORTED extern unsigned long index_getsize(struct index_state *state,
                                            uint32_t msgno)
{
    struct index_record record;

    if (index_reload_record(state, msgno, &record))
        return 0;

    return record.size;
}

EXPORTED extern unsigned long index_getlines(struct index_state *state,
                                             uint32_t msgno)
{
    struct index_record record;
    struct body *body = NULL;
    unsigned long lines = 0;

    if (index_reload_record(state, msgno, &record))
        return 0;

    if (mailbox_cacherecord(state->mailbox, &record))
        return 0;

    message_read_bodystructure(&record, &body);
    if (!body) return 0;

    lines = body->content_lines;

    message_free_body(body);
    free(body);

    return lines;
}

EXPORTED const char *index_mboxname(const struct index_state *state)
{
    if (!state) return NULL;
    return state->mboxname;
}

EXPORTED int index_hasrights(const struct index_state *state, int rights)
{
    return state->myrights & rights;
}

/*
 * Parse a sequence into an array of sorted & merged ranges.
 */
static struct seqset *_parse_sequence(struct index_state *state,
                                      const char *sequence, int usinguid)
{
    unsigned maxval = usinguid ? state->last_uid : state->exists;
    return seqset_parse(sequence, NULL, maxval);
}

EXPORTED void freesequencelist(struct seqset *l)
{
    seqset_free(l);
}

/*
 * Create a new search program.
 */
EXPORTED struct searchargs *new_searchargs(const char *tag, int state,
                                           struct namespace *namespace,
                                           const char *userid,
                                           struct auth_state *authstate,
                                           int isadmin)
{
    struct searchargs *sa;

    sa = (struct searchargs *)xzmalloc(sizeof(struct searchargs));
    sa->tag = tag;
    sa->state = state;
    /* default charset is US-ASCII */
    sa->charset = charset_lookupname("US-ASCII");

    sa->namespace = namespace;
    sa->userid = userid;
    sa->authstate = authstate;
    sa->isadmin = isadmin;

    return sa;
}

/*
 * Free the searchargs 's'
 */
EXPORTED void freesearchargs(struct searchargs *s)
{
    if (!s) return;

    charset_free(&s->charset);
    search_expr_free(s->root);
    free(s);
}

EXPORTED char *sortcrit_as_string(const struct sortcrit *sortcrit)
{
    struct buf b = BUF_INITIALIZER;
    static const char * const key_names[] = {
        "SEQUENCE", "ARRIVAL", "CC", "DATE",
        "DISPLAYFROM", "DISPLAYTO", "FROM",
        "SIZE", "SUBJECT", "TO", "ANNOTATION",
        "MODSEQ", "UID", "HASFLAG", "CONVMODSEQ",
        "CONVEXISTS", "CONVSIZE", "HASCONVFLAG",
        "FOLDER", "RELEVANCY", "SPAMSCORE", "GUID",
        "EMAILID", "THREADID", "SAVEDATE", "SNOOZEDUNTIL"
    };

    do {
        if (b.len)
            buf_putc(&b, ' ');
        if (sortcrit->flags & SORT_REVERSE)
            buf_appendcstr(&b, "REVERSE ");

        if (sortcrit->key < VECTOR_SIZE(key_names))
            buf_appendcstr(&b, key_names[sortcrit->key]);
        else
            buf_printf(&b, "UNKNOWN%u", sortcrit->key);

        switch (sortcrit->key) {
        case SORT_ANNOTATION:
            buf_printf(&b, " \"%s\" \"%s\"",
                       sortcrit->args.annot.entry,
                       *sortcrit->args.annot.userid ?
                            "value.priv" : "value.shared");
            break;
        }
        sortcrit++;
    } while (sortcrit->key);

    return buf_release(&b);
}

/*
 * Free an array of sortcrit
 */
EXPORTED void freesortcrit(struct sortcrit *s)
{
    int i = 0;

    if (!s) return;
    do {
        switch (s[i].key) {
        case SORT_ANNOTATION:
            free(s[i].args.annot.entry);
            free(s[i].args.annot.userid);
            break;
        case SORT_HASFLAG:
        case SORT_HASCONVFLAG:
            free(s[i].args.flag.name);
            break;
        case SORT_SAVEDATE:
        case SORT_SNOOZEDUNTIL:
            free(s[i].args.mailbox.id);
            break;
        }
        i++;
    } while (s[i].key != SORT_SEQUENCE);
    free(s);
}

EXPORTED int insert_into_mailbox_allowed(struct mailbox *mailbox)
{
    int r = 0;

    /* prohibit inserting into \Snoozed mailbox */
    if (mailbox->i.options & OPT_IMAP_HAS_ALARMS) {
        struct buf attrib = BUF_INITIALIZER;
        char *userid = mboxname_to_userid(mailbox->name);

        r = annotatemore_lookup(mailbox->name, "/specialuse", userid, &attrib);
        free(userid);

        if (!r && buf_len(&attrib)) {
            strarray_t *specialuse =
                strarray_split(buf_cstring(&attrib), NULL, 0);

            if (strarray_find(specialuse, "\\Snoozed", 0) >= 0) {
                r = IMAP_MAILBOX_NOTSUPPORTED;
            }
            strarray_free(specialuse);
        }
        buf_free(&attrib);
    }

    return r;
}