/** BEGIN COPYRIGHT BLOCK
 * Copyright (C) 2001 Sun Microsystems, Inc. Used by permission.
 * Copyright (C) 2021 Red Hat, Inc.
 * All rights reserved.
 *
 * License: GPL (version 3 or any later version).
 * See LICENSE for details.
 * END COPYRIGHT BLOCK **/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

/* filtercmp.c - routines for comparing filters */

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include "slap.h"


/* very simple hash function */
static PRUint32
addhash(PRUint32 hash, unsigned char *data, int size)
{
    int i;

    if (!data || !size)
        return hash;
    for (i = 0; i < size; i++)
        hash = (hash << 5) + (hash >> 27) + data[i];
    return hash;
}
#define addhash_long(h, l) addhash((h), (unsigned char *)&(l), sizeof(long))
#define addhash_str(h, str) addhash((h), (unsigned char *)(str), strlen(str))
#define addhash_bv(h, bv) addhash((h), (unsigned char *)(bv).bv_val, \
                                  (bv).bv_len)

static PRUint32
addhash_casestr(PRUint32 hash, char *data)
{
    unsigned char *normstr;

    normstr = slapi_utf8StrToLower((unsigned char *)data);
    hash = addhash(hash, normstr,
                   normstr ? strlen((char *)normstr) : 0);
    if ((char *)normstr != data)
        slapi_ch_free((void **)&normstr);
    return hash;
}

static PRUint32
stir(PRUint32 hash, PRUint32 x)
{
    hash = (hash << 5) + (hash >> 27);
    hash = hash ^ (x << 16);
    hash = hash ^ (x >> 16);
    return hash;
}
#define STIR(h) (h) = stir((h), 0x2EC6DEAD);

static Slapi_Value **
get_normalized_value(const Slapi_Attr *sattr, struct ava *ava)
{
    Slapi_Value *svlist[2], **keylist, sv;

    sv.bv = ava->ava_value;
    sv.v_csnset = NULL;
    sv.v_flags = 0;
    svlist[0] = &sv;
    svlist[1] = NULL;
    if ((slapi_attr_values2keys_sv(sattr, svlist, &keylist,
                                   LDAP_FILTER_EQUALITY) != 0) ||
        !keylist || !keylist[0])
        return NULL;
    return keylist;
}

/* this is not pretty.  matching rules seem to be pretty elaborate to use,
 * so comparing these kind of filters may be undesirably slow just because
 * of the overhead of normalizing the values.  most of this code is stolen
 * from the backend vlv code (matchrule.c)
 */
static Slapi_PBlock *
get_mr_normval(char *oid, char *type, struct berval **inval, struct berval ***outval)
{
    Slapi_PBlock *pb = slapi_pblock_new();
    unsigned int sort_indicator = SLAPI_PLUGIN_MR_USAGE_SORT;
    IFP mrIndex = NULL;

    if (!pb) {
        return NULL;
    }
    slapi_pblock_set(pb, SLAPI_PLUGIN_MR_OID, oid);
    slapi_pblock_set(pb, SLAPI_PLUGIN_MR_TYPE, type);
    slapi_pblock_set(pb, SLAPI_PLUGIN_MR_USAGE, (void *)&sort_indicator);
    if (slapi_mr_indexer_create(pb) != 0) {
        slapi_pblock_destroy(pb);
        return NULL;
    }
    if ((slapi_pblock_get(pb, SLAPI_PLUGIN_MR_INDEX_FN, &mrIndex) != 0) ||
        !mrIndex) {
        /* shouldn't ever happen */
        slapi_pblock_destroy(pb);
        return NULL;
    }

    /* now, call the indexer */
    slapi_pblock_set(pb, SLAPI_PLUGIN_MR_VALUES, inval);
    (*mrIndex)(pb);
    slapi_pblock_get(pb, SLAPI_PLUGIN_MR_KEYS, outval);
    return pb;
}

/* the opposite of above: shut down the matching rule pblock and free
 * the memory.
 */
static void
done_mr_normval(Slapi_PBlock *pb)
{
    IFP mrDestroy = NULL;

    if (slapi_pblock_get(pb, SLAPI_PLUGIN_DESTROY_FN, &mrDestroy) == 0) {
        if (mrDestroy)
            (*mrDestroy)(pb);
    }
    slapi_pblock_destroy(pb);
}

static int hash_filters = 0;

void
set_hash_filters(int i)
{
    hash_filters = i;
}

/* calculate the hash value of a node in a filter (assumes that any sub-nodes
 * of the filter have already had their hash value calculated).
 * -- the annoying part of this is normalizing any values in the filter.
 */
void
filter_compute_hash(struct slapi_filter *f)
{
    PRUint32 h;
    char **a;
    struct slapi_filter *fx;
    Slapi_Value **keylist;
    Slapi_PBlock *pb;
    struct berval *inval[2], **outval;
    Slapi_Attr sattr;

    if (!hash_filters)
        return;

    h = addhash_long(0, f->f_choice);
    switch (f->f_choice) {
    case LDAP_FILTER_EQUALITY:
    case LDAP_FILTER_GE:
    case LDAP_FILTER_LE:
    case LDAP_FILTER_APPROX:
        slapi_attr_init(&sattr, f->f_ava.ava_type);
        keylist = get_normalized_value(&sattr, &f->f_ava);
        attr_done(&sattr);
        if (keylist) {
            h = addhash_str(h, f->f_avtype);
            STIR(h);
            h = addhash_bv(h, *(slapi_value_get_berval(keylist[0])));
            valuearray_free(&keylist);
        }
        break;
    case LDAP_FILTER_SUBSTRINGS:
        h = addhash_str(h, f->f_sub_type);
        STIR(h);
        if (f->f_sub_initial)
            h = addhash_casestr(h, f->f_sub_initial);
        if (f->f_sub_any) {
            for (a = f->f_sub_any; *a; a++) {
                STIR(h);
                h = addhash_casestr(h, *a);
            }
        }
        STIR(h);
        if (f->f_sub_final)
            h = addhash_casestr(h, f->f_sub_final);
        break;
    case LDAP_FILTER_PRESENT:
        h = addhash_str(h, f->f_type);
        break;
    case LDAP_FILTER_AND:
    case LDAP_FILTER_OR:
    case LDAP_FILTER_NOT:
        /* should be able to just mix in the hashes from lower levels */
        for (fx = f->f_list; fx; fx = fx->f_next)
            h = h ^ fx->f_hash;
        break;
    case LDAP_FILTER_EXTENDED:
        if (f->f_mr_oid)
            h = addhash_str(h, f->f_mr_oid);
        STIR(h);
        if (f->f_mr_type) {
            h = addhash_str(h, f->f_mr_type);
            inval[0] = &f->f_mr_value;
            inval[1] = NULL;
            /* get the normalized value (according to the matching rule) */
            pb = get_mr_normval(f->f_mr_oid, f->f_mr_type, inval, &outval);
            if (!pb) {
                slapi_log_err(SLAPI_LOG_ERR, "filter_compute_hash", "Out of memory!\n");
                return;
            }
            if (outval && outval[0]) {
                STIR(h);
                h = addhash_bv(h, *(outval[0]));
            }
            done_mr_normval(pb);
            if (f->f_mr_dnAttrs)
                STIR(h);
        }
        break;
    default:
        slapi_log_err(SLAPI_LOG_ERR, "filter_compute_hash", "Can't handle filter type %lX !\n",
                      f->f_choice);
    }

    f->f_hash = h;
}


/* match compare: given two arrays of size N, determine if each item in
 * the first array matches with each item in the second array, with a
 * one-to-one correspondence.  this will be DOG SLOW for large values of N
 * (it scales as N^2) but we generally expect N < 5.
 */
static int
filter_compare_substrings(struct slapi_filter *f1,
                          struct slapi_filter *f2)
{
    int buf[20], *tally;
    char **a1, **a2;
    int count1 = 0, count2 = 0, ret, i, j, ok;

    /* ok to pass NULL to utf8casecmp */

    if ((slapi_UTF8CASECMP(f1->f_sub_initial, f2->f_sub_initial) != 0) ||
        (slapi_UTF8CASECMP(f1->f_sub_final, f2->f_sub_final) != 0))
        return 1;
    /* match compare (would be expensive for large numbers of 'any'
     * substrings, which we don't expect to see)
     */
    for (a1 = f1->f_sub_any; a1 && *a1; a1++, count1++)
        ;
    for (a2 = f2->f_sub_any; a2 && *a2; a2++, count2++)
        ;
    if (count1 != count2)
        return 1;
    ret = 1; /* assume failure until done comparing */
    if (count1 > 20)
        tally = (int *)slapi_ch_malloc(count1);
    else
        tally = buf;
    if (!tally)
        goto done; /* this is bad; out of memory */
    for (i = 0; i < count1; i++)
        tally[i] = 0;
    /* ok.  the theory is we tally up all the matched pairs we find,
     * stopping if we can't find a match that hasn't already been paired.
     */
    a1 = f1->f_sub_any;
    for (i = 0; i < count1; i++, a1++) {
        a2 = f2->f_sub_any;
        ok = 0;
        for (j = 0; j < count1; j++, a2++) {
            if (!tally[j] && (slapi_UTF8CASECMP(*a1, *a2) == 0)) {
                tally[j] = ok = 1;
                break;
            }
        }
        if (!ok)
            goto done; /* didn't find a match for that one */
    }
    /* done!  matched */
    ret = 0;

done:
    if ((count1 > 20) && tally)
        slapi_ch_free((void **)&tally);
    return ret;
}

/* same as above, but this time for lists of filter nodes */
static int
filter_compare_lists(struct slapi_filter *f1,
                     struct slapi_filter *f2)
{
    int buf[20], *tally;
    struct slapi_filter *fx1, *fx2;
    int count1 = 0, count2 = 0, ret, i, j, ok;

    for (fx1 = f1->f_list; fx1; fx1 = fx1->f_next, count1++)
        ;
    for (fx2 = f2->f_list; fx2; fx2 = fx2->f_next, count2++)
        ;
    if (count1 != count2)
        return 1;
    ret = 1;
    if (count1 > 20)
        tally = (int *)slapi_ch_malloc(count1);
    else
        tally = buf;
    if (!tally)
        goto done; /* very bad */
    for (i = 0; i < count1; i++)
        tally[i] = 0;
    /* brute-force match compare now */
    fx1 = f1->f_list;
    for (i = 0; i < count1; i++, fx1 = fx1->f_next) {
        fx2 = f2->f_list;
        ok = 0;
        for (j = 0; j < count1; j++, fx2 = fx2->f_next) {
            if (!tally[j] && (slapi_filter_compare(fx1, fx2) == 0)) {
                tally[j] = ok = 1;
                break;
            }
        }
        if (!ok)
            goto done; /* no match */
    }
    /* done! all matched */
    ret = 0;

done:
    if ((count1 > 20) && tally)
        slapi_ch_free((void **)&tally);
    return ret;
}

/* returns 0 if two filters are "identical"
 * (items under AND/OR are allowed to be in different order)
 */
int
slapi_filter_compare(struct slapi_filter *f1, struct slapi_filter *f2)
{
    Slapi_Value **key1, **key2;
    Slapi_PBlock *pb1, *pb2;
    struct berval *inval1[2], *inval2[2], **outval1, **outval2;
    int ret;
    Slapi_Attr sattr;

    slapi_log_err(SLAPI_LOG_TRACE, "slapi_filter_compare", "=>\n");

    /* allow for the possibility that one of the filters hasn't had a hash
     * computed (and is therefore 0).  this means that a filter node whose
     * hash is computed as 0 will always get compared the expensive way,
     * but this should happen VERY rarely (if ever).
     */
    if ((f1->f_hash != f2->f_hash) && (f1->f_hash) && (f2->f_hash)) {
        ret = 1;
        goto done;
    }

    /* brute-force comparison now */
    if (f1->f_choice != f2->f_choice) {
        ret = 1;
        goto done;
    }
    switch (f1->f_choice) {
    case LDAP_FILTER_EQUALITY:
    case LDAP_FILTER_GE:
    case LDAP_FILTER_LE:
    case LDAP_FILTER_APPROX:
        if (slapi_UTF8CASECMP(f1->f_avtype, f2->f_avtype) != 0) {
            ret = 1;
            break;
        }
        slapi_attr_init(&sattr, f1->f_ava.ava_type);
        key1 = get_normalized_value(&sattr, &f1->f_ava);
        key2 = get_normalized_value(&sattr, &f2->f_ava);
        ret = 1;
        if (key1 && key2) {
            const struct berval bvkey1 = {
                slapi_value_get_length(key1[0]),
                (char *)slapi_value_get_string(key1[0])
            };
            const struct berval bvkey2 = {
                slapi_value_get_length(key2[0]),
                (char *)slapi_value_get_string(key2[0])
            };
            ret = slapi_berval_cmp(&bvkey1, &bvkey2);
        }
        if (key1) {
            valuearray_free(&key1);
        }
        if (key2) {
            valuearray_free(&key2);
        }
        attr_done(&sattr);
        break;
    case LDAP_FILTER_PRESENT:
        ret = (slapi_UTF8CASECMP(f1->f_type, f2->f_type));
        break;
    case LDAP_FILTER_SUBSTRINGS:
        ret = filter_compare_substrings(f1, f2);
        break;
    case LDAP_FILTER_AND:
    case LDAP_FILTER_OR:
    case LDAP_FILTER_NOT:
        ret = filter_compare_lists(f1, f2);
        break;
    case LDAP_FILTER_EXTENDED:
        if ((slapi_UTF8CASECMP(f1->f_mr_oid, f2->f_mr_oid) != 0) ||
            (slapi_UTF8CASECMP(f1->f_mr_type, f2->f_mr_type) != 0) ||
            (f1->f_mr_dnAttrs != f2->f_mr_dnAttrs)) {
            ret = 1;
            break;
        }
        /* painstakingly compare the values (using the matching rule) */
        inval1[0] = &f1->f_mr_value;
        inval2[0] = &f2->f_mr_value;
        inval1[1] = inval2[1] = NULL;
        pb1 = get_mr_normval(f1->f_mr_oid, f1->f_mr_type, inval1, &outval1);
        pb2 = get_mr_normval(f2->f_mr_oid, f2->f_mr_type, inval2, &outval2);
        if (!pb1 || !pb2 || !outval1 || !outval2 || !outval1[0] ||
            !outval2[0] || (outval1[0]->bv_len != outval2[0]->bv_len) ||
            (memcmp(outval1[0]->bv_val, outval2[0]->bv_val,
                    outval1[0]->bv_len) != 0)) {
            ret = 1;
        } else {
            ret = 0;
        }
        if (pb1)
            done_mr_normval(pb1);
        if (pb2)
            done_mr_normval(pb2);
        break;
    default:
        slapi_log_err(SLAPI_LOG_ERR, "slapi_filter_compare", "Can't handle filter %lX\n", f1->f_choice);
        ret = 1;
    }

done:
    slapi_log_err(SLAPI_LOG_TRACE, "slapi_filter_compare", "<= %d\n", ret);
    return ret;
}