path: root/ldap/servers/slapd/back-ldbm/filterindex.c

/** BEGIN COPYRIGHT BLOCK
 * This Program is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation; version 2 of the License.
 * 
 * This Program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * this Program; if not, write to the Free Software Foundation, Inc., 59 Temple
 * Place, Suite 330, Boston, MA 02111-1307 USA.
 * 
 * In addition, as a special exception, Red Hat, Inc. gives You the additional
 * right to link the code of this Program with code not covered under the GNU
 * General Public License ("Non-GPL Code") and to distribute linked combinations
 * including the two, subject to the limitations in this paragraph. Non-GPL Code
 * permitted under this exception must only link to the code of this Program
 * through those well defined interfaces identified in the file named EXCEPTION
 * found in the source code files (the "Approved Interfaces"). The files of
 * Non-GPL Code may instantiate templates or use macros or inline functions from
 * the Approved Interfaces without causing the resulting work to be covered by
 * the GNU General Public License. Only Red Hat, Inc. may make changes or
 * additions to the list of Approved Interfaces. You must obey the GNU General
 * Public License in all respects for all of the Program code and other code used
 * in conjunction with the Program except the Non-GPL Code covered by this
 * exception. If you modify this file, you may extend this exception to your
 * version of the file, but you are not obligated to do so. If you do not wish to
 * provide this exception without modification, you must delete this exception
 * statement from your version and license this file solely under the GPL without
 * exception. 
 * 
 * 
 * Copyright (C) 2001 Sun Microsystems, Inc. Used by permission.
 * Copyright (C) 2005 Red Hat, Inc.
 * All rights reserved.
 * END COPYRIGHT BLOCK **/

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

/* filterindex.c - generate the list of candidate entries from a filter */

#include "back-ldbm.h"
#include "../index_subsys.h"

extern const char *indextype_PRESENCE;
extern const char *indextype_EQUALITY;
extern const char *indextype_APPROX;
extern const char *indextype_SUB;

static IDList    *ava_candidates(Slapi_PBlock *pb, backend *be, Slapi_Filter *f, int ftype, Slapi_Filter *nextf, int range, int *err);
static IDList    *presence_candidates(Slapi_PBlock *pb, backend *be, Slapi_Filter *f, int *err);
static IDList    *extensible_candidates(Slapi_PBlock *pb, backend *be, Slapi_Filter *f, int *err);
static IDList    *list_candidates(Slapi_PBlock *pb, backend *be, const char *base, Slapi_Filter *flist, int ftype, int *err);
static IDList    *substring_candidates(Slapi_PBlock *pb, backend *be, Slapi_Filter *f, int *err);
static IDList * range_candidates(
    Slapi_PBlock *pb,
    backend *be,
    char *type,
    struct berval *low_val,
    struct berval *high_val,
    int *err,
    const Slapi_Attr *sattr
);
static IDList *
keys2idl(
    backend     *be,
    char        *type,
    const char  *indextype,
    Slapi_Value **ivals,
    int         *err,
    int         *unindexed
);

IDList *
filter_candidates(
    Slapi_PBlock *pb,
    backend      *be,
    const char   *base,
    Slapi_Filter *f,
    Slapi_Filter *nextf,
    int          range,
    int          *err
)
{
    struct ldbminfo *li = (struct ldbminfo *) be->be_database->plg_private;
    IDList          *result;
    int             ftype;

    LDAPDebug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
    
    /* check if this is to be serviced by a virtual index */
    if(INDEX_FILTER_EVALUTED == index_subsys_evaluate_filter(f, (Slapi_DN*)slapi_be_getsuffix(be, 0), (IndexEntryList**)&result))
    {
        LDAPDebug( LDAP_DEBUG_TRACE, "<= filter_candidates %lu (vattr)\n",
               (u_long)IDL_NIDS(result), 0, 0 );
        return result;
    }

    if (li->li_use_vlv) {
        /* first, check to see if this particular filter node matches any
         * vlv indexes we're keeping.  if so, we can use that index
         * instead.
         */
        result = vlv_find_index_by_filter(be, base, f);
        if (result) {
            LDAPDebug( LDAP_DEBUG_TRACE, "<= filter_candidates %lu (vlv)\n",
                    (u_long)IDL_NIDS(result), 0, 0 );
            return result;
        }
    }

    result = NULL;
    switch ( (ftype = slapi_filter_get_choice( f )) ) {
    case LDAP_FILTER_EQUALITY:
        LDAPDebug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
        result = ava_candidates( pb, be, f, LDAP_FILTER_EQUALITY, nextf, range, err );
        break;

    case LDAP_FILTER_SUBSTRINGS:
        LDAPDebug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
        result = substring_candidates( pb, be, f, err );
        break;

    case LDAP_FILTER_GE:
        LDAPDebug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
        result = ava_candidates( pb, be, f, LDAP_FILTER_GE, nextf, range,
            err );
        break;

    case LDAP_FILTER_LE:
        LDAPDebug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
        result = ava_candidates( pb, be, f, LDAP_FILTER_LE, nextf, range,
            err );
        break;

    case LDAP_FILTER_PRESENT:
        LDAPDebug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
        result = presence_candidates( pb, be, f, err );
        break;

    case LDAP_FILTER_APPROX:
        LDAPDebug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
        result = ava_candidates( pb, be, f, LDAP_FILTER_APPROX, nextf,
            range, err );
        break;

    case LDAP_FILTER_EXTENDED:
        LDAPDebug( LDAP_DEBUG_FILTER, "\tEXTENSIBLE\n", 0, 0, 0 );
        result = extensible_candidates( pb, be, f, err );
        break;

    case LDAP_FILTER_AND:
        LDAPDebug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
        result = list_candidates( pb, be, base, f, LDAP_FILTER_AND, err );
        break;

    case LDAP_FILTER_OR:
        LDAPDebug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
        result = list_candidates( pb, be, base, f, LDAP_FILTER_OR, err );
        break;

    case LDAP_FILTER_NOT:
        LDAPDebug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
        result = idl_allids( be );
        break;

    default:
        LDAPDebug( LDAP_DEBUG_FILTER,
            "filter_candidates: unknown type 0x%X\n",
            ftype, 0, 0 );
        break;
    }

    LDAPDebug( LDAP_DEBUG_TRACE, "<= filter_candidates %lu\n",
                   (u_long)IDL_NIDS(result), 0, 0 );
    return( result );
}

static IDList *
ava_candidates(
    Slapi_PBlock *pb,
    backend      *be,
    Slapi_Filter *f,
    int             ftype,
    Slapi_Filter *nextf,
    int             range,
    int             *err
)
{
    char          *type, *indextype = NULL;
    Slapi_Value   sv;
    struct berval *bval;
    Slapi_Value   **ivals;
    IDList        *idl = NULL;
    int           unindexed = 0;
    Slapi_Attr    sattr;

    LDAPDebug( LDAP_DEBUG_TRACE, "=> ava_candidates\n", 0, 0, 0 );

    if ( slapi_filter_get_ava( f, &type, &bval ) != 0 ) {
        LDAPDebug( LDAP_DEBUG_TRACE, "  slapi_filter_get_ava failed\n",
            0, 0, 0 );
        return( NULL );
    }

    slapi_attr_init(&sattr, type);

#ifdef LDAP_DEBUG
    if ( LDAPDebugLevelIsSet( LDAP_DEBUG_TRACE )) {
        char    *op = NULL;
        char    buf[BUFSIZ];

        switch ( ftype ) {
        case LDAP_FILTER_GE:
            op = ">=";
            break;
        case LDAP_FILTER_LE:
            op = "<=";
            break;
        case LDAP_FILTER_EQUALITY:
            op = "=";
            break;
        case LDAP_FILTER_APPROX:
            op = "~=";
            break;
        }
        LDAPDebug( LDAP_DEBUG_TRACE, "   %s%s%s\n", type, op,
            encode( bval, buf ) );
    }
#endif

    switch ( ftype ) {
        case LDAP_FILTER_GE:
            idl = range_candidates(pb, be, type, bval, NULL, err, &sattr);
            LDAPDebug( LDAP_DEBUG_TRACE, "<= ava_candidates %lu\n",
                       (u_long)IDL_NIDS(idl), 0, 0 );
            goto done;
            break;
        case LDAP_FILTER_LE:
            idl = range_candidates(pb, be, type, NULL, bval, err, &sattr);
            LDAPDebug( LDAP_DEBUG_TRACE, "<= ava_candidates %lu\n",
                       (u_long)IDL_NIDS(idl), 0, 0 );
            goto done;
            break;
        case LDAP_FILTER_EQUALITY:
            indextype = (char*)indextype_EQUALITY;
            break;
        case LDAP_FILTER_APPROX:
            indextype = (char*)indextype_APPROX;
            break;
        default:
            LDAPDebug( LDAP_DEBUG_TRACE, "<= ava_candidates invalid filter\n", 0, 0, 0 );
            goto done;
            break;
    }

    /* This code is result of performance anlysis; we are trying to
     * optimize our equality filter processing -- mainly by limiting
     * malloc/free calls.
     *
     * When the filter type is LDAP_FILTER_EQUALITY_FAST, the
     * syntax_assertion2keys functions are passed a stack-based
     * destination Slapi_Value array (ivals) that contains room
     * for one key value with a fixed size buffer (also stack-based).
     * If the buffer provided is not large enough, the
     * syntax_assertion2keys function can alloc a new buffer (and
     * reset ivals[0]->bv.bv_val) or alloc an entirely new ivals array.
     */

    if(ftype==LDAP_FILTER_EQUALITY) {
        Slapi_Value tmp, *ptr[2], fake;
        char buf[1024];

        tmp.bv = *bval;
        tmp.v_csnset=NULL;
        fake.bv.bv_val=buf;
        fake.bv.bv_len=sizeof(buf);
        ptr[0]=&fake;
        ptr[1]=NULL;
        ivals=ptr;

        slapi_attr_assertion2keys_ava_sv( &sattr, &tmp, (Slapi_Value ***)&ivals, LDAP_FILTER_EQUALITY_FAST);
        idl = keys2idl( be, type, indextype, ivals, err, &unindexed );
        if ( unindexed ) {
            unsigned int opnote = SLAPI_OP_NOTE_UNINDEXED;
            slapi_pblock_set( pb, SLAPI_OPERATION_NOTES, &opnote );
            pagedresults_set_unindexed( pb->pb_conn );
        }

        /* We don't use valuearray_free here since the valueset, berval
         * and value was all allocated at once in one big chunk for
         * performance reasons
         */
        if (fake.bv.bv_val != buf) {
            slapi_ch_free((void**)&fake.bv.bv_val);
        }

        /* Some syntax_assertion2keys functions may allocate a whole new
         * ivals array. Free it if so.
         */
        if (ivals != ptr) {
            slapi_ch_free((void**)&ivals);
        }
    } else {
        slapi_value_init_berval(&sv, bval);
        ivals=NULL;
        slapi_attr_assertion2keys_ava_sv( &sattr, &sv, &ivals, ftype );
        value_done(&sv);
        if ( ivals == NULL || *ivals == NULL ) {
            LDAPDebug( LDAP_DEBUG_TRACE,
                "<= ava_candidates ALLIDS (no keys)\n", 0, 0, 0 );
            idl = idl_allids( be );
            goto done;
        }
        idl = keys2idl( be, type, indextype, ivals, err, &unindexed );
        if ( unindexed ) {
            unsigned int opnote = SLAPI_OP_NOTE_UNINDEXED;
            slapi_pblock_set( pb, SLAPI_OPERATION_NOTES, &opnote );
            pagedresults_set_unindexed( pb->pb_conn );
        }
         valuearray_free( &ivals );
         LDAPDebug( LDAP_DEBUG_TRACE, "<= ava_candidates %lu\n",
                   (u_long)IDL_NIDS(idl), 0, 0 );
    }
done:
    attr_done(&sattr);
    return( idl );
}

static IDList *
presence_candidates(
    Slapi_PBlock    *pb,
    backend *be,
    Slapi_Filter    *f,
    int            *err
)
{
    char    *type;
    IDList  *idl;
    int     unindexed = 0;

    LDAPDebug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );

    if ( slapi_filter_get_type( f, &type ) != 0 ) {
        LDAPDebug( LDAP_DEBUG_ANY, "   slapi_filter_get_type failed\n",
            0, 0, 0 );
        return( NULL );
    }
    idl = index_read_ext( be, type, indextype_PRESENCE,
                          NULL, NULL, err, &unindexed );

    if ( unindexed ) {
        unsigned int opnote = SLAPI_OP_NOTE_UNINDEXED;
        slapi_pblock_set( pb, SLAPI_OPERATION_NOTES, &opnote );
        pagedresults_set_unindexed( pb->pb_conn );
    }

    if (idl != NULL && ALLIDS(idl) && strcasecmp(type, "nscpentrydn") == 0) {
        /* try the equality index instead */
        LDAPDebug(LDAP_DEBUG_TRACE, 
                      "fallback to eq index as pres index gave allids\n", 
                      0, 0, 0);
        idl_free(idl);
        idl = index_range_read(pb, be, type, indextype_EQUALITY,
                                   SLAPI_OP_GREATER_OR_EQUAL,
                                   NULL, NULL, 0, NULL, err);
    }

    LDAPDebug( LDAP_DEBUG_TRACE, "<= presence_candidates %lu\n",
                   (u_long)IDL_NIDS(idl), 0, 0 );
    return( idl );
}

static IDList *
extensible_candidates(
    Slapi_PBlock *glob_pb, 
    backend       *be,
    Slapi_Filter  *f,
    int           *err
)
{
    IDList* idl = NULL;
    Slapi_PBlock* pb = slapi_pblock_new();
    int mrOP = 0;
    Slapi_Operation *op = NULL;
    LDAPDebug (LDAP_DEBUG_TRACE, "=> extensible_candidates\n", 0, 0, 0);
    if ( ! slapi_mr_filter_index (f, pb) &&    !slapi_pblock_get (pb, SLAPI_PLUGIN_MR_QUERY_OPERATOR, &mrOP))
    {
        switch (mrOP)
        {
        case SLAPI_OP_LESS:
        case SLAPI_OP_LESS_OR_EQUAL:
        case SLAPI_OP_EQUAL:
        case SLAPI_OP_GREATER_OR_EQUAL:
        case SLAPI_OP_GREATER:
            {
            IFP mrINDEX = NULL;
            void* mrOBJECT = NULL;
            struct berval** mrVALUES = NULL;
            char* mrOID = NULL;
            char* mrTYPE = NULL;

            /* set the pb->pb_op to glob_pb->pb_op to catch the abandon req.
             * in case the operation is interrupted. */
            slapi_pblock_get (glob_pb, SLAPI_OPERATION, &op);
            slapi_pblock_set (pb, SLAPI_OPERATION, op);

            slapi_pblock_get (pb, SLAPI_PLUGIN_MR_INDEX_FN, &mrINDEX);
            slapi_pblock_get (pb, SLAPI_PLUGIN_OBJECT, &mrOBJECT);
            slapi_pblock_get (pb, SLAPI_PLUGIN_MR_VALUES, &mrVALUES);
            slapi_pblock_get (pb, SLAPI_PLUGIN_MR_OID, &mrOID);
            slapi_pblock_get (pb, SLAPI_PLUGIN_MR_TYPE, &mrTYPE);

            if (mrVALUES != NULL && *mrVALUES != NULL)
            {
                /*
                 * Compute keys for each of the values, individually.
                 * Search the index, for the computed keys.
                 * Collect the resulting IDs in idl.
                 */
                size_t n;
                struct berval** val;
                mrTYPE = slapi_attr_basetype (mrTYPE, NULL, 0);
                for (n=0,val=mrVALUES; *val; ++n,++val)
                {
                    struct berval** keys = NULL;
                    /* keys = mrINDEX (*val), conceptually.  In detail: */
                    struct berval* bvec[2];
                    bvec[0] = *val;
                    bvec[1] = NULL;
                    if (slapi_pblock_set (pb, SLAPI_PLUGIN_OBJECT, mrOBJECT) ||
                        slapi_pblock_set (pb, SLAPI_PLUGIN_MR_VALUES, bvec) ||
                        mrINDEX (pb) ||
                        slapi_pblock_get (pb, SLAPI_PLUGIN_MR_KEYS, &keys))
                    {
                        /* something went wrong.  bail. */
                        break;
                    }
                    else if (keys == NULL || keys[0] == NULL)
                    {
                        /* no keys */
                        idl_free (idl);
                        idl = idl_allids (be);
                    }
                    else
                    {
                        IDList* idl2= NULL;
                        struct berval** key;
                        for (key = keys; *key != NULL; ++key)
                        {
                            int unindexed = 0;
                            IDList* idl3 = (mrOP == SLAPI_OP_EQUAL) ?
                                index_read_ext(be, mrTYPE, mrOID, *key, NULL,
                                                          err, &unindexed) :
                                index_range_read (pb, be, mrTYPE, mrOID, mrOP,
                                                  *key, NULL, 0, NULL, err);
                            if ( unindexed ) {
                                unsigned int opnote = SLAPI_OP_NOTE_UNINDEXED;
                                slapi_pblock_set( glob_pb,
                                               SLAPI_OPERATION_NOTES, &opnote );
                                pagedresults_set_unindexed( glob_pb->pb_conn );
                            }
                            if (idl2 == NULL)
                            {
                                /* first iteration */
                                idl2 = idl3;
                            }
                            else
                            {
                                IDList* tmp = idl_intersection (be, idl2, idl3);
                                idl_free (idl2);
                                idl_free (idl3);
                                idl2 = tmp;
                            }
                            if (idl2 == NULL) break; /* look no further */
                        }
                        if (idl == NULL)
                        {
                            idl = idl2;
                        }
                        else if (idl2 != NULL)
                        {
                            IDList* tmp = idl_union (be, idl, idl2);
                            idl_free (idl);
                            idl_free (idl2);
                            idl = tmp;
                        }
                    }
                }
                slapi_ch_free((void**)&mrTYPE);
                goto return_idl; /* possibly no matches */
            }
            }
            break;
        default:
            /* unsupported query operator */
            break;
        }
    }
    if (idl == NULL)
    {
        /* this filter isn't indexed */
        idl = idl_allids (be); /* all entries are candidates */
    }
return_idl:
    op = NULL;
    slapi_pblock_set (pb, SLAPI_OPERATION, op);
    slapi_pblock_destroy (pb);
    LDAPDebug (LDAP_DEBUG_TRACE, "<= extensible_candidates %lu\n", 
                   (u_long)IDL_NIDS(idl), 0, 0);
    return idl;
}

static int
slapi_berval_reverse_cmp(const struct berval *a, const struct berval *b)
{
    return slapi_berval_cmp(b, a);
}

static IDList *
range_candidates(
    Slapi_PBlock    *pb,
    backend *be,
    char *type,
    struct berval *low_val,
    struct berval *high_val,
    int *err,
    const Slapi_Attr *sattr
)
{
    IDList *idl = NULL;
    struct berval *low = NULL, *high = NULL;
    struct berval **lows = NULL, **highs = NULL;

    LDAPDebug(LDAP_DEBUG_TRACE, "=> range_candidates attr=%s\n", type, 0, 0);

    if (low_val != NULL) {
        slapi_attr_assertion2keys_ava(sattr, low_val, &lows, LDAP_FILTER_EQUALITY);
        if (lows == NULL || *lows == NULL) {
            LDAPDebug( LDAP_DEBUG_TRACE,
                       "<= range_candidates ALLIDS (no keys)\n", 0, 0, 0 );
            idl = idl_allids( be );
            goto done;
        }
        low = attr_value_lowest(lows, slapi_berval_reverse_cmp);
    }

    if (high_val != NULL) {
        slapi_attr_assertion2keys_ava(sattr, high_val, &highs, LDAP_FILTER_EQUALITY);
        if (highs == NULL || *highs == NULL) {
            LDAPDebug( LDAP_DEBUG_TRACE,
                       "<= range_candidates ALLIDS (no keys)\n", 0, 0, 0 );
            idl = idl_allids( be );
            goto done;
        }
        high = attr_value_lowest(highs, slapi_berval_cmp);
    }

    if (low == NULL) {
        idl = index_range_read(pb, be, type, (char*)indextype_EQUALITY,
                               SLAPI_OP_LESS_OR_EQUAL,
                               high, NULL, 0, NULL, err);
    } else if (high == NULL) {
        idl = index_range_read(pb, be, type, (char*)indextype_EQUALITY,
                               SLAPI_OP_GREATER_OR_EQUAL,
                               low, NULL, 0, NULL, err);
    } else {
        idl = index_range_read(pb, be, type, (char*)indextype_EQUALITY,
                               SLAPI_OP_GREATER_OR_EQUAL,
                               low, high, 1, NULL, err);
    }

done:
    if (lows) ber_bvecfree(lows);
    if (highs) ber_bvecfree(highs);

    LDAPDebug( LDAP_DEBUG_TRACE, "<= range_candidates %lu\n",
               (u_long)IDL_NIDS(idl), 0, 0 );

    return idl;
}

static IDList *
list_candidates(
    Slapi_PBlock  *pb,
    backend       *be,
    const char    *base,
    Slapi_Filter  *flist,
    int           ftype,
    int           *err
)
{
    IDList        *idl, *tmp, *tmp2;
    Slapi_Filter  *f, *nextf, *f_head;
    int           range = 0;
    int           isnot;
    int           f_count = 0, le_count = 0, ge_count = 0, is_bounded_range = 1;
    struct berval *low_val = NULL, *high_val = NULL;
    char          *t1;
    Slapi_Filter  *fpairs[2] = {NULL, NULL}; /* low, high */
    char          *tpairs[2] = {NULL, NULL};
    struct berval *vpairs[2] = {NULL, NULL};
    int is_and = 0;

    LDAPDebug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );

    /* 
     * Optimize bounded range queries such as (&(cn>=A)(cn<=B)).
     * Could be better by matching pairs in a longer list
     * but for now support only a single pair.
     */
    if (ftype != LDAP_FILTER_AND) 
    {
        is_bounded_range = 0;
    }
    for ( f = slapi_filter_list_first( flist ); 
          f != NULL && is_bounded_range;
          f = slapi_filter_list_next( flist, f ) ) {
        f_count++;
        switch (slapi_filter_get_choice(f)) {
        case LDAP_FILTER_GE:
            if ( slapi_filter_get_ava(f, &t1, &low_val) != 0 ) {
                is_bounded_range = 0;
                continue;
            }
            ge_count++;
            if (NULL == fpairs[0])
            {
                fpairs[0] = f;
                tpairs[0] = slapi_ch_strdup(t1);
                vpairs[0] = slapi_ch_bvdup(low_val);
            }
            else if (NULL != fpairs[1] &&
                slapi_attr_type_cmp(tpairs[1], t1, SLAPI_TYPE_CMP_EXACT) != 0)
            {
                fpairs[0] = f;
                slapi_ch_free_string(&tpairs[0]);
                tpairs[0] = slapi_ch_strdup(t1);
                slapi_ch_bvfree(&vpairs[0]);
                vpairs[0] = slapi_ch_bvdup(low_val);
            }
            break;
        case LDAP_FILTER_LE:
            if ( slapi_filter_get_ava(f, &t1, &high_val) != 0 ) {
                is_bounded_range = 0;
                continue;
            }
            le_count++;
            if (NULL == fpairs[1])
            {
                fpairs[1] = f;
                tpairs[1] = slapi_ch_strdup(t1);
                vpairs[1] = slapi_ch_bvdup(high_val);
            }
            else if (NULL != fpairs[0] &&
                slapi_attr_type_cmp(tpairs[0], t1, SLAPI_TYPE_CMP_EXACT) != 0)
            {
                fpairs[1] = f;
                slapi_ch_free_string(&tpairs[1]);
                tpairs[1] = slapi_ch_strdup(t1);
                slapi_ch_bvfree(&vpairs[1]);
                vpairs[1] = slapi_ch_bvdup(high_val);
            }
            break;
        default:
            continue;
        }
    }
    if (ftype == LDAP_FILTER_AND && f_count > 1)
    {
        slapi_pblock_get(pb, SLAPI_SEARCH_IS_AND, &is_and);
        if (is_and) {
            /* Outer candidates function already set IS_AND.
             * So, this function does not touch it. */
            is_and = 0;
        } else {
            /* Outer candidates function hasn't set IS_AND */
            is_and = 1;
            slapi_pblock_set(pb, SLAPI_SEARCH_IS_AND, &is_and);
        }
    }
    if (le_count != 1 || ge_count != 1 || f_count != 2)
    {
        is_bounded_range = 0;
    }
    if (NULL == fpairs[0] || NULL == fpairs[1] ||
        0 != strcmp(tpairs[0], tpairs[1]) /* avoid "&(cn<=A)(sn>=B)" type */ )
    {
        fpairs[0] = fpairs[1] = NULL;
        slapi_ch_free_string(&tpairs[0]);
        slapi_ch_bvfree(&vpairs[0]);
        slapi_ch_free_string(&tpairs[1]);
        slapi_ch_bvfree(&vpairs[1]);
        is_bounded_range = 0;
    }
    if (is_bounded_range) {
        Slapi_Attr sattr;

        slapi_attr_init(&sattr, tpairs[0]);
        idl = range_candidates(pb, be, tpairs[0], vpairs[0], vpairs[1], err, &sattr);
        attr_done(&sattr);
        LDAPDebug( LDAP_DEBUG_TRACE, "<= list_candidates %lu\n",
                   (u_long)IDL_NIDS(idl), 0, 0 );
        goto out;
    }

    idl = NULL;
    nextf = NULL;
    isnot = 0;
    for ( f_head = f = slapi_filter_list_first( flist ); f != NULL;
        f = slapi_filter_list_next( flist, f ) ) {

        /* Look for NOT foo type filter elements where foo is simple equality */
        isnot = (LDAP_FILTER_NOT == slapi_filter_get_choice( f )) &&
                (LDAP_FILTER_AND == ftype &&
                (LDAP_FILTER_EQUALITY == slapi_filter_get_choice(slapi_filter_list_first(f))));

        if (isnot) {
            /* if this is the first filter we have an allid search anyway, so bail */
            if(f == f_head)
            {
                idl = idl_allids( be );
                break;
            }

            /* Fetch the IDL for foo */
            /* Later we'll remember to call idl_notin() */
            LDAPDebug( LDAP_DEBUG_TRACE,"NOT filter\n", 0, 0, 0 );
            tmp = ava_candidates( pb, be, slapi_filter_list_first(f), LDAP_FILTER_EQUALITY, nextf, range, err );
        } else {
            if (fpairs[0] == f)
            {
                continue;
            }
            else if (fpairs[1] == f)
            {
                Slapi_Attr sattr;

                slapi_attr_init(&sattr, tpairs[0]);
                tmp = range_candidates(pb, be, tpairs[0],
                                       vpairs[0], vpairs[1], err, &sattr);
                attr_done(&sattr);
                if (tmp == NULL && ftype == LDAP_FILTER_AND)
                {
                    LDAPDebug( LDAP_DEBUG_TRACE,
                        "<= list_candidates NULL\n", 0, 0, 0 );
                    idl_free( idl );
                    idl = NULL;
                    goto out;
                }
            }
            /* Proceed as normal */
            else if ( (tmp = filter_candidates( pb, be, base, f, nextf, range, err ))
                == NULL && ftype == LDAP_FILTER_AND ) {
                    LDAPDebug( LDAP_DEBUG_TRACE,
                        "<= list_candidates NULL\n", 0, 0, 0 );
                    idl_free( idl );
                    idl = NULL;
                    goto out;
            }
        }

        tmp2 = idl;
        if ( idl == NULL ) {
            idl = tmp;
            if ( (ftype == LDAP_FILTER_AND) && ((idl == NULL) ||
                (idl_length(idl) <= FILTER_TEST_THRESHOLD))) {
                break; /* We can exit the loop now, since the candidate list is small already */
            }
        } else if ( ftype == LDAP_FILTER_AND ) {
            if (isnot) {
                IDList *new_idl = NULL;
                int notin_result = 0;
                notin_result = idl_notin( be, idl, tmp, &new_idl );
                if (notin_result) {
                    idl_free(idl);
                    idl = new_idl;
                }
            } else {
                idl = idl_intersection(be, idl, tmp);
                idl_free( tmp2 );
            }
            idl_free( tmp );
            /* stop if the list has gotten too small */
            if ((idl == NULL) ||
                (idl_length(idl) <= FILTER_TEST_THRESHOLD))
                break;
        } else {
            Slapi_Operation *operation;
            struct ldbminfo *li;
            slapi_pblock_get( pb, SLAPI_OPERATION, &operation );
            slapi_pblock_get( pb, SLAPI_PLUGIN_PRIVATE, &li );

            idl = idl_union( be, idl, tmp );
            idl_free( tmp );
            idl_free( tmp2 );
            /* stop if we're already committed to an exhaustive
             * search. :(
             */
            /* PAGED RESULTS: if not Directory Manager, we strictly limit
             *                the idlist size by the lookthrough limit.
             */
            if (operation->o_flags & OP_FLAG_PAGED_RESULTS) {
                int nids = IDL_NIDS(idl);
                int lookthroughlimits = compute_lookthrough_limit( pb, li );
                if ( lookthroughlimits > 0 && nids > lookthroughlimits ) {
                    idl_free( idl );
                    idl = idl_allids( be );
                }
            }
            if (idl_is_allids(idl))
                break;
        }
    }

    LDAPDebug( LDAP_DEBUG_TRACE, "<= list_candidates %lu\n",
                   (u_long)IDL_NIDS(idl), 0, 0 );
out:
    if (is_and) {
        /*
         * Sets IS_AND back to 0 only when this function set 1.
         * The info of the outer (&...) needs to be passed to the
         * descendent *_candidates functions called recursively.
         */
        is_and = 0;
        slapi_pblock_set(pb, SLAPI_SEARCH_IS_AND, &is_and);
    }
    slapi_ch_free_string(&tpairs[0]);
    slapi_ch_bvfree(&vpairs[0]);
    slapi_ch_free_string(&tpairs[1]);
    slapi_ch_bvfree(&vpairs[1]);
    return( idl );
}

static IDList *
substring_candidates(
    Slapi_PBlock    *pb,
    backend *be,
    Slapi_Filter    *f,
    int            *err
)
{
    char         *type, *initial, *final;
    char         **any;
    IDList       *idl;
    Slapi_Value  **ivals;
    int          unindexed = 0;
    unsigned int opnote = SLAPI_OP_NOTE_UNINDEXED;
    Slapi_Attr   sattr;

    LDAPDebug( LDAP_DEBUG_TRACE, "=> sub_candidates\n", 0, 0, 0 );

    if (slapi_filter_get_subfilt( f, &type, &initial, &any, &final ) != 0) {
        LDAPDebug( LDAP_DEBUG_ANY, "  slapi_filter_get_subfilt fails\n",
            0, 0, 0 );
        return( NULL );
    }

    /*
     * get the index keys corresponding to the substring
     * assertion values
     */
    slapi_attr_init(&sattr, type);
    slapi_attr_assertion2keys_sub_sv( &sattr, initial, any, final, &ivals );
    attr_done(&sattr);
    if ( ivals == NULL || *ivals == NULL ) {
        slapi_pblock_set( pb, SLAPI_OPERATION_NOTES, &opnote );
        pagedresults_set_unindexed( pb->pb_conn );
        LDAPDebug( LDAP_DEBUG_TRACE,
            "<= sub_candidates ALLIDS (no keys)\n", 0, 0, 0 );
        return( idl_allids( be ) );
    }

    /*
     * look up each key in the index, ANDing the resulting
     * IDLists together.
     */
    idl = keys2idl( be, type, indextype_SUB, ivals, err, &unindexed );
    if ( unindexed ) {
        slapi_pblock_set( pb, SLAPI_OPERATION_NOTES, &opnote );
        pagedresults_set_unindexed( pb->pb_conn );
    }
    valuearray_free( &ivals );

    LDAPDebug( LDAP_DEBUG_TRACE, "<= sub_candidates %lu\n",
                   (u_long)IDL_NIDS(idl), 0, 0 );
    return( idl );
}

static IDList *
keys2idl(
    backend     *be,
    char        *type,
    const char  *indextype,
    Slapi_Value **ivals,
    int         *err,
    int         *unindexed
)
{
    IDList    *idl;
    int    i;

    LDAPDebug( LDAP_DEBUG_TRACE, "=> keys2idl type %s indextype %s\n",
        type, indextype, 0 );
    idl = NULL;
    for ( i = 0; ivals[i] != NULL; i++ ) {
        IDList    *idl2;

        idl2 = index_read_ext( be, type, indextype, slapi_value_get_berval(ivals[i]), NULL, err, unindexed );

#ifdef LDAP_DEBUG
        /* XXX if ( slapd_ldap_debug & LDAP_DEBUG_TRACE ) { XXX */
        {
            char    buf[BUFSIZ];

            LDAPDebug( LDAP_DEBUG_TRACE,
                "   ival[%d] = \"%s\" => %lu IDs\n", i,
                encode( slapi_value_get_berval(ivals[i]), buf ), (u_long)IDL_NIDS(idl2) );
        }
#endif
        if ( idl2 == NULL ) {
            idl_free( idl );
            idl = NULL;
            break;
        }

        if (idl == NULL) {
            idl = idl2;
        } else {
            IDList    *tmp;

            tmp = idl;
            idl = idl_intersection(be, idl, idl2);
            idl_free( idl2 );
            idl_free( tmp );
            if ( idl == NULL ) {
                break;
            }
        }
    }

    return( idl );
}