#include "config.h"

#include "lib/libconfig.h"
#include "lib/libcyr_cfg.h"

#include "cunit/cyrunit.h"
#include "prot.h"
#include "xmalloc.h"
#include "imap/imapd.h"
#include "imap/index.h"
#include "imap/imapparse.h"
#include "util.h"
#include "cunit/timezones.h"
#include "cunit/timeofday.h"

static struct namespace ns;
static const char *userid = "fred";
static struct auth_state *authstate = NULL;
static int isadmin = 0;

#define DATE1_RFC3501   "8-Dec-2012"
#define DATE1_BEGIN     "1354885200"
#define DATE1_MID       "1354928400"
#define DATE1_END       "1354971600"
#define DATE1_MID_TIME  1354928400

#define DBDIR   "test-dbdir"

static void test_get_search_program(void)
{
/*TODO: test initial state */
/*TODO: test charset */
#define TESTCASE(in, exp_out) \
    { \
        static const char _in[] = in; \
        static const char expected_out[] = exp_out; \
        static const char expected_errs[] = ""; \
        struct searchargs *searchargs; \
        int c; \
        char *actual_out = NULL; \
        struct protstream *pin; \
        struct protstream *pout; \
        struct buf actual_errs = BUF_INITIALIZER; \
 \
        searchargs = new_searchargs(".", 0, &ns, userid, authstate, isadmin); \
        pin = prot_readmap(_in, sizeof(_in)-1); \
        pout = prot_writebuf(&actual_errs); \
        c = get_search_program(pin, pout, searchargs); \
        CU_ASSERT_EQUAL(c, '\r'); \
        buf_cstring(&actual_errs); \
        CU_ASSERT_STRING_EQUAL(actual_errs.s, expected_errs); \
        if (c != EOF) { \
            CU_ASSERT_STRING_EQUAL(charset_canon_name(searchargs->charset), "us-ascii"); \
            CU_ASSERT_PTR_NOT_NULL(searchargs->root); \
            actual_out = search_expr_serialise(searchargs->root); \
            CU_ASSERT_STRING_EQUAL(actual_out, expected_out); \
        } \
 \
        free(actual_out); \
        buf_free(&actual_errs); \
        prot_free(pin); \
        prot_free(pout); \
        freesearchargs(searchargs); \
    }

    /*
     * Search criteria from RFC 3501
     */

    /* <sequence set> */
    TESTCASE("1\r\n",
             "(and (match msgno 1))");
    TESTCASE("1:4\r\n",
             "(and (match msgno 1:4))");
    TESTCASE("1:*\r\n",
             "(and (match msgno 1:*))");
    TESTCASE("1,3,5\r\n",
             "(and (match msgno 1,3,5))");
    TESTCASE("1,3,5:7\r\n",
             "(and (match msgno 1,3,5:7))");

    /* ALL */
    TESTCASE("all\r\n",
             "(and (true))");

    /* ANSWERED */
    TESTCASE("answered\r\n",
             "(and (match systemflags \\Answered))");

    /* BCC <string> */
    TESTCASE("bcc \"shoreditch\"\r\n",
             "(and (match bcc \"shoreditch\"))");

    /* BEFORE <date> */
    TESTCASE("before "DATE1_RFC3501"\r\n",
             "(and (lt internaldate "DATE1_BEGIN"))");

    /* BODY <string> */
    TESTCASE("body \"williamsburg\"\r\n",
             "(and (match body \"williamsburg\"))");

    /* CC <string> */
    TESTCASE("cc \"brooklyn\"\r\n",
             "(and (match cc \"brooklyn\"))");

    /* DELETED */
    TESTCASE("deleted\r\n",
             "(and (match systemflags \\Deleted))");

    /* DRAFT */
    TESTCASE("draft\r\n",
             "(and (match systemflags \\Draft))");

    /* FLAGGED */
    TESTCASE("flagged\r\n",
             "(and (match systemflags \\Flagged))");

    /* FROM <string> */
    TESTCASE("from \"dreamcatcher\"\r\n",
             "(and (match from \"dreamcatcher\"))");

    /* HEADER <field-name> <string> */
    TESTCASE("header \"Cosby\" \"Sweater\"\r\n",
             "(and (match header:cosby \"Sweater\"))");

    /* KEYWORD <flag> */
    TESTCASE("keyword $Mustache\r\n",
             "(and (match keyword \"$Mustache\"))");

    /* LARGER <n> */
    TESTCASE("larger 123\r\n",
             "(and (gt size 123))");

    /* NEW */
    TESTCASE("new\r\n",
             "(and "
                "(and "
                    "(not "
                        "(match indexflags \\Seen)"
                    ")"
                    " "
                    "(match indexflags \\Recent)"
                ")"
             ")");

    /* NOT <search-key> */
    TESTCASE("not subject \"tumblr\"\r\n",
             "(and (not (match subject \"tumblr\")))");

    /* OLD */
    /* inexplicably, the RFC specifies OLD != NOT NEW */
    TESTCASE("old\r\n",
             "(and (not (match indexflags \\Recent)))");

    /* ON <date> */
    TESTCASE("on "DATE1_RFC3501"\r\n",
             "(and "
                 "(and "
                    "(lt internaldate "DATE1_END")"
                    " "
                    "(ge internaldate "DATE1_BEGIN")"
                 ")"
             ")");

    /* OR <search-key> <search-key> */
    TESTCASE("or subject \"black\" subject \"white\"\r\n",
             "(and "
                "(or "
                    "(match subject \"black\")"
                    " "
                    "(match subject \"white\")"
                ")"
             ")");

    /* RECENT */
    TESTCASE("recent\r\n",
             "(and (match indexflags \\Recent))");

    /* SEEN */
    TESTCASE("seen\r\n",
             "(and (match indexflags \\Seen))");

    /* SENTBEFORE <date> */
    TESTCASE("sentbefore "DATE1_RFC3501"\r\n",
             "(and (lt sentdate "DATE1_BEGIN"))");

    /* SENTON <date> */
    TESTCASE("senton "DATE1_RFC3501"\r\n",
             "(and "
                 "(and "
                    "(lt sentdate "DATE1_END")"
                    " "
                    "(ge sentdate "DATE1_BEGIN")"
                 ")"
             ")");

    /* SENTSINCE <date> */
    /* SENTSINCE, like SINCE, includes the given date */
    TESTCASE("sentsince "DATE1_RFC3501"\r\n",
             "(and (ge sentdate "DATE1_BEGIN"))");

    /* SINCE <date> */
    /* Note: BEFORE excludes the date, SINCE includes it */
    TESTCASE("since "DATE1_RFC3501"\r\n",
             "(and (ge internaldate "DATE1_BEGIN"))");

    /* SMALLER <n> */
    /* Note: neither LARGER nor SMALLER includes the exact size */
    TESTCASE("smaller 456\r\n",
             "(and (lt size 456))");

    /* SUBJECT <string> */
    TESTCASE("subject \"selvage\"\r\n",
             "(and (match subject \"selvage\"))");

    /* TEXT <string> */
    TESTCASE("text \"letterpress\"\r\n",
             "(and (match text \"letterpress\"))");

    /* TO <string> */
    TESTCASE("to \"readymade\"\r\n",
             "(and (match to \"readymade\"))");

    /* UID <sequence set> */
    TESTCASE("uid 1\r\n",
             "(and (match uid 1))");
    TESTCASE("uid 1:4\r\n",
             "(and (match uid 1:4))");
    TESTCASE("uid 1:*\r\n",
             "(and (match uid 1:*))");
    TESTCASE("uid 1,3,5\r\n",
             "(and (match uid 1,3,5))");
    TESTCASE("uid 1,3,5:7\r\n",
             "(and (match uid 1,3,5:7))");

    /* UNANSWERED */
    TESTCASE("unanswered\r\n",
             "(and (not (match systemflags \\Answered)))");

    /* UNDELETED */
    TESTCASE("undeleted\r\n",
             "(and (not (match systemflags \\Deleted)))");

    /* UNDRAFT */
    TESTCASE("undraft\r\n",
             "(and (not (match systemflags \\Draft)))");

    /* UNFLAGGED */
    TESTCASE("unflagged\r\n",
             "(and (not (match systemflags \\Flagged)))");

    /* UNKEYWORD <flag> */
    TESTCASE("unkeyword $Viral\r\n",
             "(and (not (match keyword \"$Viral\")))");

    /* UNSEEN */
    TESTCASE("unseen\r\n",
             "(and (not (match indexflags \\Seen)))");

    /* ( <search-key>* ) */
    TESTCASE("(subject \"bicycle\" to \"rights\")\r\n",
             "(and "
                "(and "
                    "(match subject \"bicycle\")"
                    " "
                    "(match to \"rights\")"
                ")"
             ")");
    TESTCASE("not (subject \"bicycle\" to \"rights\")\r\n",
             "(and "
                "(not "
                    "(and "
                        "(match subject \"bicycle\")"
                        " "
                        "(match to \"rights\")"
                    ")"
                ")"
             ")");
    TESTCASE("or (subject \"bicycle\" to \"rights\") from \"quinoa\"\r\n",
             "(and "
                "(or "
                    "(and "
                        "(match subject \"bicycle\")"
                        " "
                        "(match to \"rights\")"
                    ")"
                    " "
                    "(match from \"quinoa\")"
                ")"
             ")");

    /*
     * Search criteria from RFC 4551
     */

    /* MODSEQ <modseq>
     * Note, the full RFC syntax is
     * MODSEQ [<entry-name> <entry-type-req>] <mod-sequence-valzer>
     * but we don't support the optional but in the middle */
/*TODO: negative should fail*/
    TESTCASE("modseq 0\r\n",        /* not a valid modseq but we can search on it */
             "(and (ge modseq 0))");
    TESTCASE("modseq 1\r\n",
             "(and (ge modseq 1))");
    TESTCASE("modseq 12345\r\n",
             "(and (ge modseq 12345))");
    TESTCASE("modseq 12345678\r\n",
             "(and (ge modseq 12345678))");
    /* MODSEQ is a 64b value */
    TESTCASE("modseq 12345678901\r\n",
             "(and (ge modseq 12345678901))");
    TESTCASE("modseq 2147483647\r\n",   /* 0x7fff_ffff */
             "(and (ge modseq 2147483647))");
    TESTCASE("modseq 2147483648\r\n",   /* 0x8000_0000 */
             "(and (ge modseq 2147483648))");
    TESTCASE("modseq 4294967295\r\n",   /* 0xffff_ffff */
             "(and (ge modseq 4294967295))");
    TESTCASE("modseq 4294967296\r\n",   /* 0x1_0000_0000 */
             "(and (ge modseq 4294967296))");
    TESTCASE("modseq 12345678901234\r\n",
             "(and (ge modseq 12345678901234))");
    TESTCASE("modseq 18446744073709551615\r\n", /* 0xffff_ffff_ffff_ffff */
             "(and (ge modseq 18446744073709551615))");

    /*
     * Search criteria from RFC 5032
     */

    /* OLDER <nz-number> in seconds ago */
    /* YOUNGER <nz-number> in seconds ago */
    /* Inexplicably, the RFC defines that *both*  YOUNGER and OLDER
     * include the specified second */
    time_push_fixed(DATE1_MID_TIME);
    TESTCASE("older 0\r\n",
             "(and (le internaldate "DATE1_MID"))");
    TESTCASE("older 43200\r\n",
             "(and (le internaldate "DATE1_BEGIN"))");
    TESTCASE("younger 0\r\n",
             "(and (ge internaldate "DATE1_MID"))");
    TESTCASE("younger 43200\r\n",
             "(and (ge internaldate "DATE1_BEGIN"))");
    time_pop();

    /*
     * Search criteria from RFC 5257
     */
    /* ANNOTATION <entry> <attrib> </value> */
    TESTCASE("annotation /comment value \"stumptown\"\r\n",
             "(and (match annotation (entry \"/comment\" attrib \"value\" value \"stumptown\")))");
    TESTCASE("annotation /comment value.priv \"stumptown\"\r\n",
             "(and (match annotation (entry \"/comment\" attrib \"value.priv\" value \"stumptown\")))");
    TESTCASE("annotation /comment value.shared \"stumptown\"\r\n",
             "(and (match annotation (entry \"/comment\" attrib \"value.shared\" value \"stumptown\")))");

    /*
     * Cyrus vendor specific search criteria
     */
    /* FOLDER <mboxname> */
    TESTCASE("folder INBOX\r\n",
             "(and (match folder \"user.fred\"))");
    TESTCASE("folder GastroPub\r\n",
             "(and (match folder \"user.fred.GastroPub\"))");

    /* XLISTID <string> */
    TESTCASE("xlistid \"semiotics\"\r\n",
             "(and (match listid \"semiotics\"))");

    /* XCONTENTTYPE <string> */
    TESTCASE("xcontenttype text\r\n",
             "(and (match contenttype \"text\"))");
    TESTCASE("xcontenttype \"text\"\r\n",
             "(and (match contenttype \"text\"))");
    TESTCASE("xcontenttype \"plain\"\r\n",
             "(and (match contenttype \"plain\"))");
    TESTCASE("xcontenttype \"text_plain\"\r\n",
             "(and (match contenttype \"text_plain\"))");

/* TODO: test that conv* are rejected if conversations:off */
    /* CONVFLAG <flag> */
    TESTCASE("convflag $Forage\r\n",
             "(and (match convflags \"$forage\"))");

    /* CONVREAD */
    TESTCASE("convread\r\n",
             "(and (match convflags \"\\Seen\"))");

    /* CONVUNREAD */
    TESTCASE("convunread\r\n",
             "(and (not (match allconvflags \"\\Seen\")))");

    /* CONVSEEN */
    TESTCASE("convseen\r\n",
             "(and (match convflags \"\\Seen\"))");

    /* CONVUNSEEN */
    TESTCASE("convunseen\r\n",
             "(and (not (match allconvflags \"\\Seen\")))");

    /* CONVMODSEQ <modseq> */
    TESTCASE("convmodseq 0\r\n",            /* not a valid modseq but we can search on it */
             "(and (ge convmodseq 0))");
    TESTCASE("convmodseq 1\r\n",
             "(and (ge convmodseq 1))");
    TESTCASE("convmodseq 12345\r\n",
             "(and (ge convmodseq 12345))");
    TESTCASE("convmodseq 12345678\r\n",
             "(and (ge convmodseq 12345678))");
    /* MODSEQ is a 64b value */
    TESTCASE("convmodseq 12345678901\r\n",
             "(and (ge convmodseq 12345678901))");
    TESTCASE("convmodseq 2147483647\r\n",       /* 0x7fff_ffff */
             "(and (ge convmodseq 2147483647))");
    TESTCASE("convmodseq 2147483648\r\n",       /* 0x8000_0000 */
             "(and (ge convmodseq 2147483648))");
    TESTCASE("convmodseq 4294967295\r\n",       /* 0xffff_ffff */
             "(and (ge convmodseq 4294967295))");
    TESTCASE("convmodseq 4294967296\r\n",       /* 0x1_0000_0000 */
             "(and (ge convmodseq 4294967296))");
    TESTCASE("convmodseq 12345678901234\r\n",
             "(and (ge convmodseq 12345678901234))");
    TESTCASE("convmodseq 18446744073709551615\r\n", /* 0xffff_ffff_ffff_ffff */
             "(and (ge convmodseq 18446744073709551615))");

    /* CID <cid> */
    TESTCASE("cid NIL\r\n",
             "(and (match cid NIL))");
    TESTCASE("cid 0000000000000000\r\n",
             "(and (match cid NIL))");
    TESTCASE("cid 0123456789abcdef\r\n",
             "(and (match cid 0123456789abcdef))");

    /* TODO: charset */
    /* TODO: return */
    /* TODO: return */

#undef TESTCASE
}

static void test_unserialise(void)
{
    search_expr_t *e;

    e = search_expr_unserialise("(true)");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_TRUE);
    CU_ASSERT_PTR_NULL(e->attr);
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NULL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    search_expr_free(e);

    e = search_expr_unserialise("(false)");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_FALSE);
    CU_ASSERT_PTR_NULL(e->attr);
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NULL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    search_expr_free(e);

    e = search_expr_unserialise("(not (false))");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_NOT);
    CU_ASSERT_PTR_NULL(e->attr);
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    CU_ASSERT_EQUAL(e->children->op, SEOP_FALSE);
    CU_ASSERT_PTR_NULL(e->children->attr);
    CU_ASSERT_PTR_NULL(e->children->next);
    CU_ASSERT_PTR_NULL(e->children->children);
    CU_ASSERT_PTR_EQUAL(e->children->parent, e);
    search_expr_free(e);

    e = search_expr_unserialise("(and (false) (true))");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_AND);
    CU_ASSERT_PTR_NULL(e->attr);
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    CU_ASSERT_EQUAL(e->children->op, SEOP_FALSE);
    CU_ASSERT_PTR_NULL(e->children->attr);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->children->next);
    CU_ASSERT_PTR_NULL(e->children->children);
    CU_ASSERT_PTR_EQUAL(e->children->parent, e);
    CU_ASSERT_EQUAL(e->children->next->op, SEOP_TRUE);
    CU_ASSERT_PTR_NULL(e->children->next->attr);
    CU_ASSERT_PTR_NULL(e->children->next->next);
    CU_ASSERT_PTR_NULL(e->children->next->children);
    CU_ASSERT_PTR_EQUAL(e->children->next->parent, e);
    search_expr_free(e);

    e = search_expr_unserialise("(or (false) (true))");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_OR);
    CU_ASSERT_PTR_NULL(e->attr);
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    CU_ASSERT_EQUAL(e->children->op, SEOP_FALSE);
    CU_ASSERT_PTR_NULL(e->children->attr);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->children->next);
    CU_ASSERT_PTR_NULL(e->children->children);
    CU_ASSERT_PTR_EQUAL(e->children->parent, e);
    CU_ASSERT_EQUAL(e->children->next->op, SEOP_TRUE);
    CU_ASSERT_PTR_NULL(e->children->next->attr);
    CU_ASSERT_PTR_NULL(e->children->next->next);
    CU_ASSERT_PTR_NULL(e->children->next->children);
    CU_ASSERT_PTR_EQUAL(e->children->next->parent, e);
    search_expr_free(e);

    e = search_expr_unserialise("(match subject ETSY)");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_MATCH);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->attr);
    CU_ASSERT_STRING_EQUAL(e->attr->name, "subject");
    CU_ASSERT_STRING_EQUAL(e->value.s, "ETSY");
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NULL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    search_expr_free(e);

    e = search_expr_unserialise("(fuzzymatch subject ETSY)");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_FUZZYMATCH);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->attr);
    CU_ASSERT_STRING_EQUAL(e->attr->name, "subject");
    CU_ASSERT_STRING_EQUAL(e->value.s, "ETSY");
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NULL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    search_expr_free(e);

    e = search_expr_unserialise("(fuzzymatch subject \"BESTELLING BEVESTIGD: GRADO IGRADO HEADPHONES ON-EAR NECKBAND BEHIND-THE-NECK STEREO HEADSETS BLACK\")");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_FUZZYMATCH);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->attr);
    CU_ASSERT_STRING_EQUAL(e->attr->name, "subject");
    CU_ASSERT_STRING_EQUAL(e->value.s, "BESTELLING BEVESTIGD: GRADO IGRADO HEADPHONES ON-EAR NECKBAND BEHIND-THE-NECK STEREO HEADSETS BLACK");
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NULL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    search_expr_free(e);

    e = search_expr_unserialise("(fuzzymatch subject \"STENA LINE E-TICKET AND RESERVATION ADVICE FOR BOOKING REFERENCE 72105814\")");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_FUZZYMATCH);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->attr);
    CU_ASSERT_STRING_EQUAL(e->attr->name, "subject");
    CU_ASSERT_STRING_EQUAL(e->value.s, "STENA LINE E-TICKET AND RESERVATION ADVICE FOR BOOKING REFERENCE 72105814");
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NULL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    search_expr_free(e);

    e = search_expr_unserialise("(ge size 123)");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_GE);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->attr);
    CU_ASSERT_STRING_EQUAL(e->attr->name, "size");
    CU_ASSERT_EQUAL(e->value.u, 123);
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NULL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    search_expr_free(e);

    e = search_expr_unserialise("(match uid 1:4,7:*)");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_MATCH);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->attr);
    CU_ASSERT_STRING_EQUAL(e->attr->name, "uid");
    CU_ASSERT_STRING_EQUAL(e->value.s, "1:4,7:*");
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NULL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    search_expr_free(e);

    e = search_expr_unserialise("(match annotation (entry \"/comment\" attrib \"value\" value \"Brooklyn\"))");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e);
    CU_ASSERT_EQUAL(e->op, SEOP_MATCH);
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->attr);
    CU_ASSERT_STRING_EQUAL(e->attr->name, "annotation");
    CU_ASSERT_PTR_NOT_NULL_FATAL(e->value.annot);
    CU_ASSERT_STRING_EQUAL(e->value.annot->entry, "/comment");
    CU_ASSERT_STRING_EQUAL(e->value.annot->attrib, "value");
    CU_ASSERT_STRING_EQUAL(e->value.annot->value.s, "Brooklyn");
    CU_ASSERT_PTR_NULL(e->next);
    CU_ASSERT_PTR_NULL(e->children);
    CU_ASSERT_PTR_NULL(e->parent);
    search_expr_free(e);
}

static void test_duplicate(void)
{
#define TESTCASE(in) \
    { \
        static const char _in[] = (in); \
        search_expr_t *e; \
        search_expr_t *edup; \
        char *s; \
        char *sdup; \
 \
        e = search_expr_unserialise(_in); \
        CU_ASSERT_PTR_NOT_NULL_FATAL(e); \
        edup = search_expr_duplicate(e); \
        CU_ASSERT_PTR_NOT_NULL_FATAL(edup); \
        CU_ASSERT_PTR_NOT_EQUAL(e, edup); \
        s = search_expr_serialise(e); \
        CU_ASSERT_STRING_EQUAL(s, _in); \
        free(s); \
        sdup = search_expr_serialise(edup); \
        CU_ASSERT_STRING_EQUAL(sdup, _in); \
        free(sdup); \
        search_expr_free(e); \
        sdup = search_expr_serialise(edup); \
        CU_ASSERT_STRING_EQUAL(sdup, _in); \
        free(sdup); \
        search_expr_free(edup); \
    }

    TESTCASE("(false)");
    TESTCASE("(true)");
    TESTCASE("(not (false))");
    TESTCASE("(and (false) (true))");
    TESTCASE("(or (false) (true))");
    TESTCASE("(match subject \"ETSY\")");
    TESTCASE("(ge size 123)");
    TESTCASE("(gt size 456)");
    TESTCASE("(le size 789)");
    TESTCASE("(lt size 120)");
    TESTCASE("(match uid 1:4,7:*)");
    TESTCASE("(match annotation (entry \"/comment\" attrib \"value\" value \"Brooklyn\"))");

#undef TESTCASE
}


static void test_normalise(void)
{
#define TESTCASE(in, exp_out) \
    { \
        static const char _in[] = (in); \
        static const char expected_out[] = (exp_out); \
        search_expr_t *e; \
        char *s; \
 \
        e = search_expr_unserialise(_in); \
        CU_ASSERT_PTR_NOT_NULL_FATAL(e); \
        search_expr_normalise(&e); \
        CU_ASSERT_PTR_NOT_NULL_FATAL(e); \
        s = search_expr_serialise(e); \
        CU_ASSERT_STRING_EQUAL(s, expected_out); \
        search_expr_free(e); \
    }

    /*
     * A tree comprising a single comparison node
     * is already in DNF.
     */
    TESTCASE("(false)",
             "(false)");
    TESTCASE("(true)",
             "(true)");
    TESTCASE("(match subject \"ETSY\")",
             "(match subject \"ETSY\")");
    TESTCASE("(le size 123)",
             "(le size 123)");
    TESTCASE("(lt size 123)",
             "(lt size 123)");
    TESTCASE("(ge size 123)",
             "(ge size 123)");
    TESTCASE("(gt size 123)",
             "(gt size 123)");

    /*
     * A tree comprising a single comparison node
     * under a NOT node is already in DNF.
     */
    TESTCASE("(not (false))",
             "(not (false))");
    TESTCASE("(not (true))",
             "(not (true))");
    TESTCASE("(not (match subject \"ETSY\"))",
             "(not (match subject \"ETSY\"))");
    TESTCASE("(not (le size 123))",
             "(not (le size 123))");
    TESTCASE("(not (lt size 123))",
             "(not (lt size 123))");
    TESTCASE("(not (ge size 123))",
             "(not (ge size 123))");
    TESTCASE("(not (gt size 123))",
             "(not (gt size 123))");

    /*
     * Ordering of nodes.
     */
    TESTCASE("(and "
                "(match subject \"ALPHA\")"
                " "
                "(match subject \"BETA\")"
                " "
                "(match subject \"GAMMA\")"
             ")",
             "(and "
                "(match subject \"ALPHA\")"
                " "
                "(match subject \"BETA\")"
                " "
                "(match subject \"GAMMA\")"
             ")");
    TESTCASE("(and "
                "(match subject \"GAMMA\")"
                " "
                "(match subject \"BETA\")"
                " "
                "(match subject \"ALPHA\")"
             ")",
             "(and "
                "(match subject \"ALPHA\")"
                " "
                "(match subject \"BETA\")"
                " "
                "(match subject \"GAMMA\")"
             ")");
    TESTCASE("(and "
                "(match subject \"GAMMA\")"
                " "
                "(match subject \"ALPHA\")"
                " "
                "(match subject \"BETA\")"
             ")",
             "(and "
                "(match subject \"ALPHA\")"
                " "
                "(match subject \"BETA\")"
                " "
                "(match subject \"GAMMA\")"
             ")");

    /*
     * A tree comprising a single conjunctive node
     * whose children are all comparison nodes or
     * negations of comparison nodes, is already in DNF.
     */
    TESTCASE("(and (le size 123) (match subject \"ETSY\"))",
             "(and (le size 123) (match subject \"ETSY\"))");
    TESTCASE("(and (not (le size 123)) (match subject \"ETSY\"))",
             "(and (not (le size 123)) (match subject \"ETSY\"))");
    TESTCASE("(and (le size 123) (not (match subject \"ETSY\")))",
             "(and (le size 123) (not (match subject \"ETSY\")))");

    /*
     * A tree comprising a single disjunctive node
     * whose children are all comparison nodes or
     * negations of comparison nodes, is already in DNF.
     */
    TESTCASE("(or (le size 123) (match subject \"ETSY\"))",
             "(or (le size 123) (match subject \"ETSY\"))");
    TESTCASE("(or (not (le size 123)) (match subject \"ETSY\"))",
             "(or (not (le size 123)) (match subject \"ETSY\"))");
    TESTCASE("(or (le size 123) (not (match subject \"ETSY\")))",
             "(or (le size 123) (not (match subject \"ETSY\")))");

    /*
     * A tree already in fully populated DNF: one disjunctive
     * node, then multiple conjunctive nodes, then negations,
     * then comparisons.
     */
    TESTCASE("(or "
                "(and "
                    "(le size 123)"
                    " "
                    "(not "
                        "(match subject \"ETSY\")"
                    ")"
                ")"
                " "
                "(and "
                    "(not "
                        "(le size 456)"
                    ")"
                    " "
                    "(match subject \"TUMBLR\")"
                ")"
             ")",
             "(or "
                "(and "
                    "(le size 123)"
                    " "
                    "(not "
                        "(match subject \"ETSY\")"
                    ")"
                ")"
                " "
                "(and "
                    "(not "
                        "(le size 456)"
                    ")"
                    " "
                    "(match subject \"TUMBLR\")"
                ")"
             ")");

    /*
     * Elimination of trivial nodes
     */
    TESTCASE("(and "
                "(match subject \"COSBY\")"
             ")",
            "(match subject \"COSBY\")");
    TESTCASE("(or "
                "(match subject \"COSBY\")"
             ")",
            "(match subject \"COSBY\")");
    TESTCASE("(and (not) (match subject \"COSBY\"))",
            "(match subject \"COSBY\")");
    TESTCASE("(or (not) (match subject \"COSBY\"))",
            "(match subject \"COSBY\")");

    /*
     * Combining similar parent & child nodes
     */
    TESTCASE("(and "
                "(match subject \"COSBY\")"
                " "
                "(and "
                    "(le size 123)"
                    " "
                    "(match subject \"TUMBLR\")"
                ")"
                " "
                "(match subject \"SWEATER\")"
             ")",
            "(and "
                "(le size 123)"
                " "
                "(match subject \"COSBY\")"
                " "
                "(match subject \"SWEATER\")"
                " "
                "(match subject \"TUMBLR\")"
             ")");
    TESTCASE("(or "
                "(match subject \"COSBY\")"
                " "
                "(or "
                    "(le size 123)"
                    " "
                    "(match subject \"TUMBLR\")"
                ")"
                " "
                "(match subject \"SWEATER\")"
             ")",
             "(or "
                "(le size 123)"
                " "
                "(match subject \"COSBY\")"
                " "
                "(match subject \"SWEATER\")"
                " "
                "(match subject \"TUMBLR\")"
             ")");
    TESTCASE("(not "
                "(not "
                    "(match subject \"SELVAGE\")"
                ")"
             ")",
             "(match subject \"SELVAGE\")");
    TESTCASE("(not "
                "(not "
                    "(not "
                        "(match subject \"SELVAGE\")"
                    ")"
                ")"
             ")",
             "(not "
                "(match subject \"SELVAGE\")"
             ")");
    TESTCASE("(not "
                "(not "
                    "(not "
                        "(not "
                            "(match subject \"SELVAGE\")"
                        ")"
                    ")"
                ")"
             ")",
             "(match subject \"SELVAGE\")");

    /*
     * Applying DeMorgan's laws to invert an AND or OR
     * which is a child or a NOT.
     */
    TESTCASE("(not "
                "(and "
                    "(le size 123)"
                    " "
                    "(match subject \"ETSY\")"
                ")"
             ")",
             "(or "
                "(not "
                    "(le size 123)"
                ")"
                " "
                "(not "
                    "(match subject \"ETSY\")"
                ")"
             ")");
    TESTCASE("(not "
                "(or "
                    "(le size 123)"
                    " "
                    "(match subject \"ETSY\")"
                ")"
             ")",
             "(and "
                "(not "
                    "(le size 123)"
                ")"
                " "
                "(not "
                    "(match subject \"ETSY\")"
                ")"
             ")");

    /*
     * DeMorgan's laws plus combination of similar nodes
     */
    TESTCASE("(not "
                "(and "
                    "(not "
                        "(le size 123)"
                    ")"
                    " "
                    "(match subject \"ETSY\")"
                ")"
             ")",
             "(or "
                "(le size 123)"
                " "
                "(not "
                    "(match subject \"ETSY\")"
                ")"
             ")");
    TESTCASE("(not "
                "(or "
                    "(not "
                        "(le size 123)"
                    ")"
                    " "
                    "(match subject \"ETSY\")"
                ")"
             ")",
             "(and "
                "(le size 123)"
                " "
                "(not "
                    "(match subject \"ETSY\")"
                ")"
             ")");

    /*
     * Distribution.
     */
    TESTCASE("(and "
                "(match subject \"TUMBLR\")"
                " "
                "(or "
                    "(le size 123)"
                    " "
                    "(match subject \"ETSY\")"
                ")"
             ")",
             "(or "
                "(and "
                    "(le size 123)"
                    " "
                    "(match subject \"TUMBLR\")"
                ")"
                " "
                "(and "
                    "(match subject \"ETSY\")"
                    " "
                    "(match subject \"TUMBLR\")"
                ")"
             ")");
    TESTCASE("(and "
                "(or "
                    "(le size 123)"
                    " "
                    "(match subject \"ETSY\")"
                ")"
                " "
                "(match subject \"TUMBLR\")"
             ")",
             "(or "
                "(and "
                    "(le size 123)"
                    " "
                    "(match subject \"TUMBLR\")"
                ")"
                " "
                "(and "
                    "(match subject \"ETSY\")"
                    " "
                    "(match subject \"TUMBLR\")"
                ")"
             ")");
    TESTCASE("(and "
                "(match subject \"COSBY\")"
                " "
                "(or "
                    "(le size 123)"
                    " "
                    "(match subject \"ETSY\")"
                ")"
                " "
                "(match subject \"SWEATER\")"
             ")",
             "(or "
                "(and "
                    "(le size 123)"
                    " "
                    "(match subject \"COSBY\")"
                    " "
                    "(match subject \"SWEATER\")"
                ")"
                " "
                "(and "
                    "(match subject \"COSBY\")"
                    " "
                    "(match subject \"ETSY\")"
                    " "
                    "(match subject \"SWEATER\")"
                ")"
             ")");

    /*
     * Distribution plus elimination of trivial nodes
     */
    TESTCASE("(and "
                "(or "
                    "(le size 123)"
                    " "
                    "(match subject \"ETSY\")"
                ")"
             ")",
             "(or "
                "(le size 123)"
                " "
                "(match subject \"ETSY\")"
             ")");

#undef TESTCASE
}

static void test_countability(void)
{
#define TESTCASE(in, exp) \
    { \
        static const char _in[] = (in); \
        unsigned int expected = (exp); \
        search_expr_t *e; \
        unsigned int actual; \
 \
        e = search_expr_unserialise(_in); \
        CU_ASSERT_PTR_NOT_NULL_FATAL(e); \
        actual = search_expr_get_countability(e); \
        CU_ASSERT_EQUAL(actual, expected); \
        search_expr_free(e); \
    }

    TESTCASE("(true)", SEC_EXISTS);
    TESTCASE("(not (true))", SEC_EXISTS|SEC_NOT);
    // The case (not (false)) doesn't work properly, but this
    // doesn't matter because it will not occur in trees
    // generated from IMAP syntax.
    TESTCASE("(match indexflags \\Recent)", SEC_RECENT);
    TESTCASE("(not (match indexflags \\Recent))", SEC_RECENT|SEC_NOT);
    TESTCASE("(match indexflags \\Seen)", SEC_SEEN);
    TESTCASE("(not (match indexflags \\Seen))", SEC_SEEN|SEC_NOT);
    TESTCASE("(match convflags \\Seen)", SEC_CONVSEEN);
    TESTCASE("(not (match convflags \\Seen))", SEC_CONVSEEN|SEC_NOT);
    TESTCASE("(match subject \"ETSY\")", SEC_UNCOUNTED);
    TESTCASE("(not (match subject \"ETSY\"))", SEC_UNCOUNTED|SEC_NOT);
    TESTCASE("(and (match indexflags \\Seen) (match subject \"ETSY\"))",
             SEC_UNCOUNTED|SEC_SEEN);
    TESTCASE("(not (and (match indexflags \\Seen) (match subject \"ETSY\")))",
             SEC_UNCOUNTED|SEC_SEEN|SEC_NOT);
    TESTCASE("(and (not (match indexflags \\Seen)) (match subject \"ETSY\"))",
             SEC_UNCOUNTED|SEC_SEEN|SEC_NOT);

#undef TESTCASE
}

static void add_subquery(const char *mboxname, search_expr_t *indexed, search_expr_t *e, void *rock)
{
    struct buf *buf = rock;
    char *s;

    if (mboxname)
        buf_printf(buf, "mboxname \"%s\" ", mboxname);

    if (indexed) {
        s = search_expr_serialise(indexed);
        buf_printf(buf, "indexed %s ", s);
        free(s);
    }

    s = search_expr_serialise(e);
    buf_appendcstr(buf, s);
    free(s);

    buf_putc(buf, '\n');
    buf_cstring(buf);

    search_expr_free(e);
    search_expr_free(indexed);
}

static void test_split_by_folder_and_index(void)
{
#define TESTCASE(in, exp) \
    { \
        static const char _in[] = (in); \
        static const char expected[] = (exp); \
        search_expr_t *e; \
        struct buf actual = BUF_INITIALIZER; \
 \
        e = search_expr_unserialise(_in); \
        CU_ASSERT_PTR_NOT_NULL_FATAL(e); \
        search_expr_split_by_folder_and_index(e, add_subquery, &actual); \
        CU_ASSERT_STRING_EQUAL(actual.s, expected); \
        buf_free(&actual); \
    }

    /* Note, we expect that a (match message-id) node is NOT indexable
     * whereas a (fuzzymatch subject) node IS indexable */

    /* comparison nodes and negations of comparison nodes, which don't
     * match any folders, get a NULL mboxname */
    TESTCASE("(false)",
             "(false)\n");
    TESTCASE("(true)",
             "(true)\n");
    TESTCASE("(match message-id \"ETSY\")",
             "(match message-id \"ETSY\")\n");
    TESTCASE("(not (match message-id \"ETSY\"))",
             "(not (match message-id \"ETSY\"))\n");

    /* a folder match node a (true) node and that mboxname */
    TESTCASE("(match folder \"INBOX.Cosby.Sweater\")",
             "mboxname \"INBOX.Cosby.Sweater\" (true)\n");

    /* negation of a folder match node gets a NULL mboxname - it's
     * supposed to match every folder *EXCEPT* the named one */
    TESTCASE("(not (match folder \"INBOX.Cosby.Sweater\"))",
             "(not (match folder \"INBOX.Cosby.Sweater\"))\n");
    TESTCASE("(and (match message-id \"ETSY\") (not (match folder \"INBOX.Cosby.Sweater\")))",
             "(and (not (match folder \"INBOX.Cosby.Sweater\")) (match message-id \"ETSY\"))\n");

    /* a conjuctive node which doesn't match folders
     * gets a NULL mboxname */
    TESTCASE("(and (match message-id \"ETSY\") (le size 123))",
             "(and (le size 123) (match message-id \"ETSY\"))\n");
    TESTCASE("(and (match message-id \"ETSY\") (not (le size 123)))",
             "(and (not (le size 123)) (match message-id \"ETSY\"))\n");
    TESTCASE("(and (le size 123) (not (match message-id \"ETSY\")))",
             "(and (le size 123) (not (match message-id \"ETSY\")))\n");

    /* a conjuctive node which does match a folder gets the remainder
     * of the expression and that named mboxname */
    TESTCASE("(and (match folder \"INBOX.Cosby.Sweater\") (match message-id \"ETSY\"))",
             "mboxname \"INBOX.Cosby.Sweater\" (match message-id \"ETSY\")\n");
    TESTCASE("(and (match folder \"INBOX.Cosby.Sweater\") (not (match message-id \"ETSY\")))",
             "mboxname \"INBOX.Cosby.Sweater\" (not (match message-id \"ETSY\"))\n");
    TESTCASE("(and (match message-id \"ETSY\") (match folder \"INBOX.Cosby.Sweater\"))",
             "mboxname \"INBOX.Cosby.Sweater\" (match message-id \"ETSY\")\n");
    TESTCASE("(and (not (match message-id \"ETSY\")) (match folder \"INBOX.Cosby.Sweater\"))",
             "mboxname \"INBOX.Cosby.Sweater\" (not (match message-id \"ETSY\"))\n");

    /* a disjunctive node which doesn't match folders
     * or indexable attrs is untouched */
    TESTCASE("(or (match message-id \"ETSY\") (le size 123))",
             "(or (le size 123) (match message-id \"ETSY\"))\n");
    TESTCASE("(or (match message-id \"ETSY\") (not (le size 123)))",
             "(or (not (le size 123)) (match message-id \"ETSY\"))\n");
    TESTCASE("(or (le size 123) (not (match message-id \"ETSY\")))",
             "(or (le size 123) (not (match message-id \"ETSY\")))\n");

    /* a disjunctive node which does match folders gets
     * split into two expressions each with the given mboxname*/
    TESTCASE("(or (match folder \"INBOX.Cosby.Sweater\") (le size 123))",
             "mboxname \"INBOX.Cosby.Sweater\" (true)\n"
             "(le size 123)\n");
    TESTCASE("(or (match folder \"INBOX.Mlkshk\") (match folder \"INBOX.Tumblr\"))",
             "mboxname \"INBOX.Mlkshk\" (true)\n"
             "mboxname \"INBOX.Tumblr\" (true)\n");
    TESTCASE("(or (and (ge size 456) (match folder \"INBOX.Mlkshk\")) (and (le size 123) (match folder \"INBOX.Tumblr\")))",
             "mboxname \"INBOX.Mlkshk\" (ge size 456)\n"
             "mboxname \"INBOX.Tumblr\" (le size 123)\n");

    /* indexed comparison nodes and their negations, which don't
     * match any folders, get a NULL mboxname and a trivial scan. */
    TESTCASE("(fuzzymatch subject \"ETSY\")",
             "indexed (fuzzymatch subject \"ETSY\") (true)\n");
    TESTCASE("(not (fuzzymatch subject \"ETSY\"))",
             "indexed (not (fuzzymatch subject \"ETSY\")) (true)\n");

    /* conjunctions of indexed comparison nodes and their negations, which
     * don't match any folders, get a NULL mboxname and a trivial scan. */
    TESTCASE("(and (fuzzymatch subject \"ETSY\") (fuzzymatch subject \"TUMBLR\"))",
             "indexed (and (fuzzymatch subject \"ETSY\") (fuzzymatch subject \"TUMBLR\")) (true)\n");

    /* conjunctions of indexed comparison nodes and their negations, with
     * non-indexed nodes, which don't match any folders, get a NULL mboxname
     * two trees with the indexed nodes separated out */
    TESTCASE("(and (fuzzymatch subject \"ETSY\") (match message-id \"TUMBLR\"))",
             "indexed (fuzzymatch subject \"ETSY\") (match message-id \"TUMBLR\")\n");
    TESTCASE("(and (match message-id \"TUMBLR\") (fuzzymatch subject \"ETSY\"))",
             "indexed (fuzzymatch subject \"ETSY\") (match message-id \"TUMBLR\")\n");

    /* conjunctions of indexed comparison nodes and their negations, which
     * do match folders either positively or negatively, get a NULL mboxname
     * because we favour the index */
    TESTCASE("(and (fuzzymatch subject \"ETSY\") (match folder \"INBOX.Tumblr\"))",
             "indexed (fuzzymatch subject \"ETSY\") (match folder \"INBOX.Tumblr\")\n");
    TESTCASE("(and (match folder \"INBOX.Tumblr\") (fuzzymatch subject \"ETSY\"))",
             "indexed (fuzzymatch subject \"ETSY\") (match folder \"INBOX.Tumblr\")\n");
    TESTCASE("(and (fuzzymatch subject \"ETSY\") (not (match folder \"INBOX.Tumblr\")))",
             "indexed (fuzzymatch subject \"ETSY\") (not (match folder \"INBOX.Tumblr\"))\n");
    TESTCASE("(and (not (match folder \"INBOX.Tumblr\")) (fuzzymatch subject \"ETSY\"))",
             "indexed (fuzzymatch subject \"ETSY\") (not (match folder \"INBOX.Tumblr\"))\n");

    /* a disjunctive node where one side contains indexed matches,
     * is split into multiple callbacks, some indexed, some not */
    TESTCASE("(or (match folder \"INBOX.Cosby.Sweater\") (fuzzymatch subject \"ETSY\"))",
             "mboxname \"INBOX.Cosby.Sweater\" (true)\n"
             "indexed (fuzzymatch subject \"ETSY\") (true)\n");
    TESTCASE("(or (match folder \"INBOX.Cosby.Sweater\") (fuzzymatch subject \"ETSY\"))",
             "mboxname \"INBOX.Cosby.Sweater\" (true)\n"
             "indexed (fuzzymatch subject \"ETSY\") (true)\n");
    TESTCASE("(or (fuzzymatch subject \"MLKSHK\") (fuzzymatch subject \"TUMBLR\"))",
             "indexed (fuzzymatch subject \"MLKSHK\") (true)\n"
             "indexed (fuzzymatch subject \"TUMBLR\") (true)\n");
    TESTCASE("(or (and (le size 123) (fuzzymatch subject \"TUMBLR\")) (and (ge size 456) (fuzzymatch subject \"MLKSHK\")))",
             "indexed (fuzzymatch subject \"TUMBLR\") (le size 123)\n"
             "indexed (fuzzymatch subject \"MLKSHK\") (ge size 456)\n");
}
#undef TESTCASE

static int set_up(void)
{
    int r;

    search_attr_init();

    libcyrus_config_setstring(CYRUSOPT_CONFIG_DIR, DBDIR);
    config_read_string(
        "configdirectory: "DBDIR"/conf\n"
        "conversations: yes\n"
    );

    r = mboxname_init_namespace(&ns, isadmin);
    if (r) return r;

    push_tz(TZ_MELBOURNE);

    return 0;
}

static int tear_down(void)
{
    int r;

    config_reset();
    restore_tz();
    time_restore();

    r = system("rm -rf " DBDIR);

    return r;
}

/* vim: set ft=c: */
