slpd_predicate.c

SLP协议在linux下的实现。此版本为1.2.1版。官方网站为www.openslp.org

/***************************************************************************/
/*                                                                         */
/* Project:     OpenSLP - OpenSource implementation of Service Location    */
/*              Protocol Version 2                                         */
/*                                                                         */
/* File:        slpd_database.c                                            */
/*                                                                         */
/* Abstract:    This files contains an implementation of LDAPv3 search     */
/*              filters for SLP (as specified in RFC 2254).                */
/*                                                                         */
/*-------------------------------------------------------------------------*/
/*                                                                         */
/*     Please submit patches to http://www.openslp.org                     */
/*                                                                         */
/*-------------------------------------------------------------------------*/
/*                                                                         */
/* Copyright (C) 2000 Caldera Systems, Inc                                 */
/* All rights reserved.                                                    */
/*                                                                         */
/* Redistribution and use in source and binary forms, with or without      */
/* modification, are permitted provided that the following conditions are  */
/* met:                                                                    */ 
/*                                                                         */
/*      Redistributions of source code must retain the above copyright     */
/*      notice, this list of conditions and the following disclaimer.      */
/*                                                                         */
/*      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.                                                      */
/*                                                                         */
/*      Neither the name of Caldera Systems nor the names of its           */
/*      contributors may be used to endorse or promote products derived    */
/*      from this software without specific prior written permission.      */
/*                                                                         */
/* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS     */
/* `AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT      */
/* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR   */
/* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE CALDERA      */
/* SYSTEMS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, */
/* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT        */
/* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;  LOSS OF USE,  */
/* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON       */
/* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT */
/* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE   */
/* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.    */
/*                                                                         */
/***************************************************************************/

/*********/
/* TODO: The current implementation reparses the predicate string every    */
/*       time it is evaluated. This implementation should be refactored to */
/*       parse the predicate string once, build some sort of data-         */
/*       structure out of that, and then compare the predicate DS with the */
/*       attribute DS.                                                     */
/*********/

/*********
 *
 * Assumptions:
 *  - If a tag specified in the query string does not exist, that's a FALSE
 *  - The "Undefined" value mentioned in the LDAPv3 RFC (2251) is synonymous 
 *    with "false".
 *  - The "Approx" operator matches as an equal operator. 
 *  - Variable matching on type is strict: ie, the right-hand-side of an 
 *    operator must evaluate to the same type as the tag referenced on the 
 *    left-hand-side. 
 *
 * Known Bugs/TODO:
 *  - If trash follows the last operand to a binary argument, it will be 
 *    ignored if the operand is not evaluated due to short circuiting: 
 *    ie, in "(&(first=*)(second<=3)trash)", "trash" will be silently 
 *    ignored _if_ "(first=*)" is true.
 *  - Escaped '*' characters are treated as wildcards in the string equality 
 *    operator: ie, in "(string=abc\2axyz)" will match the literal string
 *    "abc\2axyz" instead of "abc*xyz". 
 *  - No operations can be performed on opaque data types. 
 *********/

#include <assert.h>
#include <ctype.h>
#include <stdlib.h>

#include "slpd_predicate.h"

#include "../libslpattr/libslpattr.h"
#include "../libslpattr/libslpattr_internal.h"

/* The character that is a wildcard. */
#define WILDCARD ('*')
#define BRACKET_OPEN '('
#define BRACKET_CLOSE ')'

#ifndef MIN
    #define MIN(x,y) (x < y ? x : y)
#endif

/************************* <Lifted from slp_attr.c> ***********************/

/* Tests a character to see if it reserved (as defined in RFC 2608, p11). */
#define IS_RESERVED(x) (((x) == '(' || (x) == ')' || (x) == ',' || (x) == '\\' || (x) == '!' || (x) == '<' || (x) == '=' || (x) == '>' || (x) == '~') || ((((char)0x01 <= (x)) && ((char)0x1F >= (x))) || ((x) == (char)0x7F)))


#define IS_INVALID_VALUE_CHAR(x) IS_RESERVED(x)

#define IS_INVALID_TAG_CHAR(x) (IS_RESERVED(x) || ((x) == '*') || ((x) == (char)0x0D) || ((x) == (char)0x0A) || ((x) == (char)0x09) || ((x) == '_'))

#define IS_VALID_TAG_CHAR(x) (!IS_INVALID_TAG_CHAR(x))

/************************* </Lifted from slp_attr.c> ***********************/


/*--------------------------------------------------------------------------*/
const char *substr(const char *haystack, 
                   const char *needle, 
                   int needle_len)
/* Does a case insensitive substring match for needle in haystack.          */
/*                                                                          */
/* Returns pointer to the start of the substring. NULL if the substring is  */
/* not found.                                                               */
/* FIXME This implementation isn't exactly blazingly fast...                */
/*--------------------------------------------------------------------------*/
{
    const char *hs_cur; 

    for(hs_cur = haystack; *hs_cur != 0; hs_cur++)
    {
        if(strncasecmp(hs_cur, needle, needle_len) == 0)
        {
            return hs_cur;
        }
    }

    return NULL;
}


/*--------------------------------------------------------------------------*/
typedef enum
{
    FR_UNSET /* Placeholder. Used to detect errors. */, 
    FR_INTERNAL_SYSTEM_ERROR /* Internal error. */,
    FR_PARSE_ERROR /* Parse error detected. */, 
    FR_MEMORY_ALLOC_FAILED /* Ran out of memory. */, 
    FR_EVAL_TRUE /* Expression successfully evaluated to true. */, 
    FR_EVAL_FALSE /* Expression successfully evaluated to false. */
} FilterResult;
/*--------------------------------------------------------------------------*/

/*--------------------------------------------------------------------------*/
int escaped_verify(char *escaped, int len, int *punescaped_len) 
/* Verifies and finds the length of an escaped string                       */
/*                                                                          */
/* Params:                                                                  */
/*  escaped -- (IN) string of escaped characters                            */
/*  len -- (IN) length of escaped                                           */
/*  unescaped_len -- (OUT) pointer to location to write the unescaped       */
/*     length of escaped to                                                 */
/*                                                                          */
/* Returns:                                                                 */
/*  1 if valid string, 0 if invalid. If 0, then punescaped_count will not   */
/*  be set                                                                  */
/*--------------------------------------------------------------------------*/
{
    int i;
    int unescaped_len;
    int seq_pos; /* Position in the current escape sequence. Set to zero when not in escape seq. */

    seq_pos = 0;

    for(i = unescaped_len = 0; i < len; i++)
    {
        /* Verify escape sequences. */
        if(seq_pos == 1 || seq_pos == 2)
        {
            if(!isxdigit((int) escaped[i]))
            {
                return 0;
            }

            if(seq_pos == 2)
            {
                seq_pos = 0;
            }
            else
            {
                seq_pos++;
            }
        }
        else
        {
            unescaped_len++;
        }


        /* Check for escape sequences. */
        if(escaped[i] == '\\')
        {
            seq_pos = 1;
        }
    }

    if(punescaped_len)
    {
        *punescaped_len = unescaped_len;
    }

    return 1;
}

/*--------------------------------------------------------------------------*/
int unescape_check(char d1, char d2, char *val) 
/* Unescape the character represented by the two given hex values.          */
/*                                                                          */
/* Params:                                                                  */
/*  d1 -- (IN) First hex char                                               */
/*  d1 -- (IN) second hex char                                              */
/*  val -- (OUT) the value of the character is written to here              */
/*                                                                          */
/* Returns:                                                                 */
/*  1 on successful conversion, 0 if one or more of the hex digits are      */
/*  invalid                                                                 */
/*--------------------------------------------------------------------------*/
{
    if(!isxdigit((int) d1) || !isxdigit((int) d2))
    {
        return 0;
    }

    if((d1 >= 'A') && (d1 <= 'F'))
        d1 = d1 - 'A' + 0x0A;
    else
        d1 = d1 - '0';

    if((d2 >= 'A') && (d2 <= 'F'))
        d2 = d2 - 'A' + 0x0A;
    else
        d2 = d2 - '0';

    *val = d2 + (d1 * 0x10);
    return 1;
}


/*--------------------------------------------------------------------------*/
FilterResult unescape_cmp(const char *escaped, int escaped_len, const char *verbatim, int verbatim_len, SLPBoolean strict_len, int *punescaped_count)
/* Compares two strings that (potentially) contain escaped characters       */
/*                                                                          */
/* Params:                                                                  */
/*   escaped -- escaped string to compare                                   */
/*   escaped_len -- length of the escaped string (including esc chars)      */
/*   verbatim -- string to compare against (not escaped)                    */
/*   verbatim_len -- length of the verbatim string                          */
/*   strict_len -- if TRUE, the number of characters in verbatim that match */
/*            must be _exactly_ verbatim_len. If FALSE, at most verbatim_len*/
/*            characters may match                                          */
/*   unescaped_count -- (OUT) the number of unescaped characters. Can be    */
/*            NULL                                                          */
/*                                                                          */
/*--------------------------------------------------------------------------*/
{
    char unesc; /* Holder for unescaped characters. */

    int esc_i; /* Index into escaped. */
    int ver_i; /* Index into verbatim. */

    int unescaped_count;

    unescaped_count = esc_i = ver_i = 0;

    /***** Compare every pair of characters. *****/
    while(1)
    {
        /**** Check for string end. ****/
        if(esc_i >= escaped_len)
        {
            if(punescaped_count != NULL)
            {
                *punescaped_count = unescaped_count;
            }

            if(strict_len == SLP_TRUE)
            {
                if(ver_i >= verbatim_len)
                {
                    return FR_EVAL_TRUE;
                }
                else
                {
                    return FR_EVAL_FALSE;
                }
            }

            return FR_EVAL_TRUE;
        }

        /**** Check for escaping ****/
        if(escaped[esc_i] == '\\')
        {
            /*** Check for truncated escape values. ***/
            if(esc_i + 2 >= escaped_len)
            {
                return FR_PARSE_ERROR;
            }
            /*** Unescape. ***/
            if(!unescape_check(escaped[esc_i+1], escaped[esc_i+2], &unesc))
            {
                return FR_PARSE_ERROR;
            }

            /*** Increment. ***/
            esc_i += 2;
        }
        else
        {
            unesc = escaped[esc_i];
        }

        if(unesc != verbatim[ver_i])        /* quick check for equality*/
        {
            if(! isascii(unesc)         /* case insensitive check */
               || ! isalpha(unesc)
               || ! isalpha(verbatim[ver_i])
               || tolower(unesc) != tolower(verbatim[ver_i]))
            {
                return FR_EVAL_FALSE;
            }
        }

        unescaped_count++;
        esc_i++;
        ver_i++;
    }
}



/*--------------------------------------------------------------------------*/
void *my_memmem(char *haystack, int haystack_len, char *needle, int needle_len, int *punescaped_len) 
/* locate an (escaped) substring                                            */
/*                                                                          */
/* Params:                                                                  */
/*  haystack -- (IN) unescaped memory to look in                            */
/*  haystack_len -- (IN) length of haystack                                 */
/*  needle -- (IN) escaped memory to search for                             */
/*  needle_len -- (IN) length of needle                                     */
/*  punescaped_len -- (OUT) the size of the unescaped needle. invalid if    */
/*       NULL is returned                                                   */
/*                                                                          */
/* Returns:                                                                 */
/*  pointer to substring. NULL if there is no substring                     */
/*--------------------------------------------------------------------------*/
{
    int offset;
    int search_len;

    if(escaped_verify(haystack, haystack_len, &search_len) == 0)
    {
        return NULL;
    }

    for(offset = 0; offset <= search_len; offset++)
    {
        FilterResult err;

        err = unescape_cmp(needle, needle_len, haystack + offset, haystack_len - offset, SLP_FALSE, punescaped_len);
        if(err == FR_EVAL_TRUE)
        {
            return(void *)(haystack + offset);
        }
        else if(err != FR_EVAL_FALSE)
        {
            return NULL;
        }
    }

    return NULL;
}



/*--------------------------------------------------------------------------*/
FilterResult wildcard_wc_str(char *pattern, int pattern_len, char *str, int str_len)
/*                                                                          */
/* Params:                                                                  */
/*  pattern -- the pattern to evaluate                                      */
/*  pattern_len -- the length of the pattern (in bytes)                     */
/*  str -- the  string to test the pattern on                               */
/*  str_len -- the length of the string                                     */
/*                                                                          */
/* Returns:                                                                 */
/*   -1 error,  0 success,  1 failure                                       */
/*--------------------------------------------------------------------------*/
{
    char *text_start; /* Pointer to the text following the WC(s) */
    int text_len; /* Length of the text. */
    char *found; /* The start of a string found in a search. */

    char *rem_start; /* Start of the remaining characters being searched for. */
    int rem_len; /* Length of the remaining charcters being searched for. */

    if(pattern_len == 0 && str_len == 0)
    {
        return FR_EVAL_TRUE;
    }

    if(pattern_len == 0)
    {