schema_init.c

/* schema_init.c - init builtin schema */
/* $OpenLDAP$ */
/*
 * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
 */

#include "portable.h"

#include <stdio.h>
#include <limits.h>

#include <ac/ctype.h>
#include <ac/errno.h>
#include <ac/string.h>
#include <ac/socket.h>

#include "slap.h"
#include "ldap_pvt.h"
#include "lber_pvt.h"

#include "ldap_utf8.h"

#include "lutil_hash.h"
#define HASH_BYTES				LUTIL_HASH_BYTES
#define HASH_CONTEXT			lutil_HASH_CTX
#define HASH_Init(c)			lutil_HASHInit(c)
#define HASH_Update(c,buf,len)	lutil_HASHUpdate(c,buf,len)
#define HASH_Final(d,c)			lutil_HASHFinal(d,c)

#ifdef SLAP_NVALUES
/* TO BE DELETED */
#define SLAP_MR_DN_FOLD (0)

#define SLAP_MR_ASSOCIATED(mr, with) \
	((mr) == (with) || (mr)->smr_associated == (with))

#define xUTF8StringNormalize NULL
#define xIA5StringNormalize NULL
#define xtelephoneNumberNormalize NULL
#define xgeneralizedTimeNormalize NULL
#define xintegerNormalize NULL
#define xnumericStringNormalize NULL
#define xnameUIDNormalize NULL
#define xdnNormalize NULL

/* (new) normalization routines */
#define caseExactIA5Normalize						IA5StringNormalize
#define caseIgnoreIA5Normalize						IA5StringNormalize
#define caseExactNormalize							UTF8StringNormalize
#define caseIgnoreNormalize							UTF8StringNormalize

#define integerNormalize							NULL
#define integerFirstComponentNormalize				NULL
#define objectIdentifierNormalize					NULL
#define objectIdentifierFirstComponentNormalize		NULL
#define generalizedTimeNormalize					NULL
#define bitStringNormalize							NULL
#define telephoneNumberNormalize					NULL

#define distinguishedNameNormalize	dnNormalize
#define distinguishedNameMatch  	dnMatch
#define distinguishedNameIndexer	octetStringIndexer
#define distinguishedNameFilter		octetStringFilter

#define uniqueMemberMatch			dnMatch

#define objectIdentifierMatch	octetStringMatch
#define objectIdentifierIndexer	octetStringIndexer
#define objectIdentifierFilter	octetStringFilter

#define OpenLDAPaciMatch						NULL

#define bitStringMatch			octetStringMatch
#define bitStringIndexer		octetStringIndexer
#define bitStringFilter			octetStringFilter

#define integerMatch NULL
#define integerOrderingMatch NULL
#define integerIndexer NULL
#define integerFilter NULL

#define generalizedTimeMatch	NULL
#define generalizedTimeOrderingMatch	NULL

#define caseIgnoreMatch		octetStringMatch
#define caseIgnoreOrderingMatch		octetStringOrderingMatch
#define caseIgnoreIndexer	octetStringIndexer
#define caseIgnoreFilter	octetStringFilter

#define caseIgnoreSubstringsMatch		octetStringSubstringsMatch
#define caseIgnoreSubstringsIndexer		octetStringSubstringsIndexer
#define caseIgnoreSubstringsFilter		octetStringSubstringsFilter

#define caseExactMatch		octetStringMatch
#define caseExactOrderingMatch		octetStringOrderingMatch
#define caseExactIndexer	octetStringIndexer
#define caseExactFilter		octetStringFilter

#define caseExactSubstringsMatch		octetStringSubstringsMatch
#define caseExactSubstringsIndexer		octetStringSubstringsIndexer
#define caseExactSubstringsFilter		octetStringSubstringsFilter

#define caseExactIA5Match		octetStringMatch
#define caseExactIA5Indexer		octetStringIndexer
#define caseExactIA5Filter		octetStringFilter

#define caseExactIA5SubstringsMatch			octetStringSubstringsMatch
#define caseExactIA5SubstringsIndexer		octetStringSubstringsIndexer
#define caseExactIA5SubstringsFilter		octetStringSubstringsFilter

#define caseIgnoreIA5Match		octetStringMatch
#define caseIgnoreIA5Indexer	octetStringIndexer
#define caseIgnoreIA5Filter		octetStringFilter

#define caseIgnoreIA5SubstringsMatch		caseExactIA5SubstringsMatch
#define caseIgnoreIA5SubstringsIndexer		caseExactIA5SubstringsIndexer
#define caseIgnoreIA5SubstringsFilter		caseExactIA5SubstringsFilter

#define numericStringMatch		octetStringMatch
#define numericStringIndexer	octetStringIndexer
#define numericStringFilter		octetStringFilter

#define numericStringSubstringsMatch		caseExactIA5SubstringsMatch
#define numericStringSubstringsIndexer		caseExactIA5SubstringsIndexer
#define numericStringSubstringsFilter		caseExactIA5SubstringsFilter

#define telephoneNumberMatch		octetStringMatch
#define telephoneNumberIndexer		octetStringIndexer
#define telephoneNumberFilter		octetStringFilter

#define telephoneNumberSubstringsMatch		caseExactIA5SubstringsMatch
#define telephoneNumberSubstringsIndexer	caseExactIA5SubstringsIndexer
#define telephoneNumberSubstringsFilter		caseExactIA5SubstringsFilter

#define booleanIndexer					octetStringIndexer
#define booleanFilter					octetStringFilter
#endif

/* validatation routines */
#define berValidate						blobValidate

/* approx matching rules */
#ifdef SLAP_NVALUES
#define directoryStringApproxMatchOID	NULL
#define IA5StringApproxMatchOID			NULL
#else
#define directoryStringApproxMatchOID	"1.3.6.1.4.1.4203.666.4.4"
#define directoryStringApproxMatch	approxMatch
#define directoryStringApproxIndexer	approxIndexer
#define directoryStringApproxFilter	approxFilter
#define IA5StringApproxMatchOID			"1.3.6.1.4.1.4203.666.4.5"
#define IA5StringApproxMatch			approxMatch
#define IA5StringApproxIndexer			approxIndexer
#define IA5StringApproxFilter			approxFilter
#endif

#ifndef SLAP_NVALUES

#define xdnNormalize dnNormalize

/* (new) normalization routines */
#define caseExactNormalize							NULL
#define caseExactIA5Normalize						NULL
#define caseIgnoreNormalize							NULL
#define caseIgnoreIA5Normalize						NULL
#define distinguishedNameNormalize					NULL
#define integerNormalize							NULL
#define integerFirstComponentNormalize				NULL
#define numericStringNormalize						NULL
#define objectIdentifierNormalize					NULL
#define objectIdentifierFirstComponentNormalize		NULL
#define generalizedTimeNormalize					NULL
#define uniqueMemberNormalize						NULL
#define bitStringNormalize							NULL
#define telephoneNumberNormalize					NULL


/* matching routines */
#define bitStringMatch					octetStringMatch
#define bitStringIndexer				octetStringIndexer
#define bitStringFilter					octetStringFilter

#define numericStringMatch				caseIgnoreIA5Match
#define numericStringIndexer			NULL
#define numericStringFilter				NULL
#define numericStringSubstringsIndexer	NULL
#define numericStringSubstringsFilter	NULL

#define objectIdentifierMatch			octetStringMatch
#define objectIdentifierIndexer			caseIgnoreIA5Indexer
#define objectIdentifierFilter			caseIgnoreIA5Filter

#define octetStringSubstringsMatch		NULL
#define OpenLDAPaciMatch				NULL

#define generalizedTimeMatch			caseIgnoreIA5Match
#define generalizedTimeOrderingMatch	caseIgnoreIA5Match

#define uniqueMemberMatch				dnMatch
#define numericStringSubstringsMatch    NULL

#define caseExactIndexer				caseExactIgnoreIndexer
#define caseExactFilter					caseExactIgnoreFilter
#define caseExactOrderingMatch			caseExactMatch
#define caseExactSubstringsMatch		caseExactIgnoreSubstringsMatch
#define caseExactSubstringsIndexer		caseExactIgnoreSubstringsIndexer
#define caseExactSubstringsFilter		caseExactIgnoreSubstringsFilter
#define caseIgnoreIndexer				caseExactIgnoreIndexer
#define caseIgnoreFilter				caseExactIgnoreFilter
#define caseIgnoreOrderingMatch			caseIgnoreMatch
#define caseIgnoreSubstringsMatch		caseExactIgnoreSubstringsMatch
#define caseIgnoreSubstringsIndexer		caseExactIgnoreSubstringsIndexer
#define caseIgnoreSubstringsFilter		caseExactIgnoreSubstringsFilter

#define integerOrderingMatch			integerMatch
#define integerFirstComponentMatch		integerMatch

#define distinguishedNameMatch			dnMatch
#define distinguishedNameIndexer		caseExactIgnoreIndexer
#define distinguishedNameFilter			caseExactIgnoreFilter

#define telephoneNumberMatch			caseIgnoreIA5Match
#define telephoneNumberSubstringsMatch	caseIgnoreIA5SubstringsMatch
#define telephoneNumberIndexer				caseIgnoreIA5Indexer
#define telephoneNumberFilter				caseIgnoreIA5Filter
#define telephoneNumberSubstringsIndexer	caseIgnoreIA5SubstringsIndexer
#define telephoneNumberSubstringsFilter		caseIgnoreIA5SubstringsFilter

#define booleanIndexer					octetStringIndexer
#define booleanFilter					octetStringFilter
#endif


static char *bvcasechr( struct berval *bv, unsigned char c, ber_len_t *len )
{
	ber_len_t i;
	char lower = TOLOWER( c );
	char upper = TOUPPER( c );

	if( c == 0 ) return NULL;
	
	for( i=0; i < bv->bv_len; i++ ) {
		if( upper == bv->bv_val[i] || lower == bv->bv_val[i] ) {
			*len = i;
			return &bv->bv_val[i];
		}
	}

	return NULL;
}

static int
octetStringMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	int match = value->bv_len - ((struct berval *) assertedValue)->bv_len;

	if( match == 0 ) {
		match = memcmp( value->bv_val,
			((struct berval *) assertedValue)->bv_val,
			value->bv_len );
	}

	*matchp = match;
	return LDAP_SUCCESS;
}

static int
octetStringOrderingMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	ber_len_t v_len  = value->bv_len;
	ber_len_t av_len = ((struct berval *) assertedValue)->bv_len;

	int match = memcmp( value->bv_val,
		((struct berval *) assertedValue)->bv_val,
		(v_len < av_len ? v_len : av_len) );

	if( match == 0 ) match = v_len - av_len;

	*matchp = match;
	return LDAP_SUCCESS;
}

/* Index generation function */
int octetStringIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	BerVarray values,
	BerVarray *keysp )
{
	int i;
	size_t slen, mlen;
	BerVarray keys;
	HASH_CONTEXT   HASHcontext;
	unsigned char	HASHdigest[HASH_BYTES];
	struct berval digest;
	digest.bv_val = HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

	for( i=0; values[i].bv_val != NULL; i++ ) {
		/* just count them */
	}

	/* we should have at least one value at this point */
	assert( i > 0 );

	keys = ch_malloc( sizeof( struct berval ) * (i+1) );

	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;

	for( i=0; values[i].bv_val != NULL; i++ ) {
		HASH_Init( &HASHcontext );
		if( prefix != NULL && prefix->bv_len > 0 ) {
			HASH_Update( &HASHcontext,
				prefix->bv_val, prefix->bv_len );
		}
		HASH_Update( &HASHcontext,
			syntax->ssyn_oid, slen );
		HASH_Update( &HASHcontext,
			mr->smr_oid, mlen );
		HASH_Update( &HASHcontext,
			values[i].bv_val, values[i].bv_len );
		HASH_Final( HASHdigest, &HASHcontext );

		ber_dupbv( &keys[i], &digest );
	}

	keys[i].bv_val = NULL;
	keys[i].bv_len = 0;

	*keysp = keys;

	return LDAP_SUCCESS;
}

/* Index generation function */
int octetStringFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertedValue,
	BerVarray *keysp )
{
	size_t slen, mlen;
	BerVarray keys;
	HASH_CONTEXT   HASHcontext;
	unsigned char	HASHdigest[HASH_BYTES];
	struct berval *value = (struct berval *) assertedValue;
	struct berval digest;
	digest.bv_val = HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;

	keys = ch_malloc( sizeof( struct berval ) * 2 );

	HASH_Init( &HASHcontext );
	if( prefix != NULL && prefix->bv_len > 0 ) {
		HASH_Update( &HASHcontext,
			prefix->bv_val, prefix->bv_len );
	}
	HASH_Update( &HASHcontext,
		syntax->ssyn_oid, slen );
	HASH_Update( &HASHcontext,
		mr->smr_oid, mlen );
	HASH_Update( &HASHcontext,
		value->bv_val, value->bv_len );
	HASH_Final( HASHdigest, &HASHcontext );

	ber_dupbv( keys, &digest );
	keys[1].bv_val = NULL;
	keys[1].bv_len = 0;

	*keysp = keys;

	return LDAP_SUCCESS;
}

static int
inValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* no value allowed */
	return LDAP_INVALID_SYNTAX;
}

static int
blobValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* any value allowed */
	return LDAP_SUCCESS;
}

static int
bitStringValidate(
	Syntax *syntax,
	struct berval *in )
{
	ber_len_t i;

	/* very unforgiving validation, requires no normalization
	 * before simplistic matching
	 */
	if( in->bv_len < 3 ) {
		return LDAP_INVALID_SYNTAX;
	}

	/*
	 * rfc 2252 section 6.3 Bit String
	 * bitstring = "'" *binary-digit "'"
	 * binary-digit = "0" / "1"
	 * example: '0101111101'B
	 */
	
	if( in->bv_val[0] != '\'' ||
		in->bv_val[in->bv_len-2] != '\'' ||
		in->bv_val[in->bv_len-1] != 'B' )
	{
		return LDAP_INVALID_SYNTAX;
	}

	for( i=in->bv_len-3; i>0; i-- ) {
		if( in->bv_val[i] != '0' && in->bv_val[i] != '1' ) {
			return LDAP_INVALID_SYNTAX;
		}
	}

	return LDAP_SUCCESS;
}

static int
nameUIDValidate(
	Syntax *syntax,
	struct berval *in )
{
	int rc;
	struct berval dn;

	if( in->bv_len == 0 ) return LDAP_SUCCESS;

	ber_dupbv( &dn, in );
	if( !dn.bv_val ) return LDAP_OTHER;

	if( dn.bv_val[dn.bv_len-1] == 'B'
		&& dn.bv_val[dn.bv_len-2] == '\'' )
	{
		/* assume presence of optional UID */
		ber_len_t i;

		for(i=dn.bv_len-3; i>1; i--) {
			if( dn.bv_val[i] != '0' &&	dn.bv_val[i] != '1' ) {
				break;
			}
		}
		if( dn.bv_val[i] != '\'' || dn.bv_val[i-1] != '#' ) {
			ber_memfree( dn.bv_val );
			return LDAP_INVALID_SYNTAX;
		}

		/* trim the UID to allow use of dnValidate */
		dn.bv_val[i-1] = '\0';
		dn.bv_len = i-1;
	}

	rc = dnValidate( NULL, &dn );

	ber_memfree( dn.bv_val );
	return rc;
}

#ifdef SLAP_NVALUES
static int
uniqueMemberNormalize(
	slap_mask_t usage,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *val,
	struct berval *normalized )
#else
static int
xnameUIDNormalize(
	Syntax *syntax,
	struct berval *val,
	struct berval *normalized )
#endif
{
	struct berval out;
	int rc;

	ber_dupbv( &out, val );
	if( out.bv_len != 0 ) {
		struct berval uid = { 0, NULL };

		if( out.bv_val[out.bv_len-1] == 'B'
			&& out.bv_val[out.bv_len-2] == '\'' )
		{
			/* assume presence of optional UID */
			uid.bv_val = strrchr( out.bv_val, '#' );

			if( uid.bv_val == NULL ) {
				free( out.bv_val );
				return LDAP_INVALID_SYNTAX;
			}

			uid.bv_len = out.bv_len - (uid.bv_val - out.bv_val);
			out.bv_len -= uid.bv_len--;

			/* temporarily trim the UID */
			*(uid.bv_val++) = '\0';
		}

		rc = dnNormalize2( NULL, &out, normalized );

		if( rc != LDAP_SUCCESS ) {
			free( out.bv_val );
			return LDAP_INVALID_SYNTAX;
		}

		if( uid.bv_len ) {
			normalized->bv_val = ch_realloc( normalized->bv_val,
				normalized->bv_len + uid.bv_len + sizeof("#") );

			/* insert the separator */
			normalized->bv_val[normalized->bv_len++] = '#';

			/* append the UID */
			AC_MEMCPY( &normalized->bv_val[normalized->bv_len],
				uid.bv_val, uid.bv_len );
			normalized->bv_len += uid.bv_len;

			/* terminate */
			normalized->bv_val[normalized->bv_len] = '\0';
		}

		free( out.bv_val );
	}

	return LDAP_SUCCESS;
}

/*
 * Handling boolean syntax and matching is quite rigid.
 * A more flexible approach would be to allow a variety
 * of strings to be normalized and prettied into TRUE
 * and FALSE.
 */
static int
booleanValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* very unforgiving validation, requires no normalization
	 * before simplistic matching
	 */

	if( in->bv_len == 4 ) {
		if( !memcmp( in->bv_val, "TRUE", 4 ) ) {
			return LDAP_SUCCESS;
		}
	} else if( in->bv_len == 5 ) {
		if( !memcmp( in->bv_val, "FALSE", 5 ) ) {
			return LDAP_SUCCESS;
		}
	}

	return LDAP_INVALID_SYNTAX;
}

static int
booleanMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	/* simplistic matching allowed by rigid validation */
	struct berval *asserted = (struct berval *) assertedValue;
	*matchp = value->bv_len != asserted->bv_len;
	return LDAP_SUCCESS;
}

/*-------------------------------------------------------------------
LDAP/X.500 string syntax / matching rules have a few oddities.  This
comment attempts to detail how slapd(8) treats them.

Summary:
  StringSyntax		X.500	LDAP	Matching/Comments
  DirectoryString	CHOICE	UTF8	i/e + ignore insignificant spaces
  PrintableString	subset	subset	i/e + ignore insignificant spaces
  PrintableString	subset	subset	i/e + ignore insignificant spaces
  NumericString		subset	subset  ignore all spaces
  IA5String			ASCII	ASCII	i/e + ignore insignificant spaces
  TeletexString		T.61	T.61	i/e + ignore insignificant spaces

  TelephoneNumber subset  subset  i + ignore all spaces and "-"

  See draft-ietf-ldapbis-strpro for details (once published).


Directory String -
  In X.500(93), a directory string can be either a PrintableString,
  a bmpString, or a UniversalString (e.g., UCS (a subset of Unicode)).
  In later versions, more CHOICEs were added.  In all cases the string
  must be non-empty.

  In LDAPv3, a directory string is a UTF-8 encoded UCS string.
  A directory string cannot be zero length.

  For matching, there are both case ignore and exact rules.  Both
  also require that "insignificant" spaces be ignored.
	spaces before the first non-space are ignored;
	spaces after the last non-space are ignored;
	spaces after a space are ignored.
  Note: by these rules (and as clarified in X.520), a string of only
  spaces is to be treated as if held one space, not empty (which
  would be a syntax error).

NumericString
  In ASN.1, numeric string is just a string of digits and spaces
  and could be empty.  However, in X.500, all attribute values of
  numeric string carry a non-empty constraint.  For example:

	internationalISDNNumber ATTRIBUTE ::= {
		WITH SYNTAX InternationalISDNNumber
		EQUALITY MATCHING RULE numericStringMatch
		SUBSTRINGS MATCHING RULE numericStringSubstringsMatch
		ID id-at-internationalISDNNumber }
	InternationalISDNNumber ::=
	    NumericString (SIZE(1..ub-international-isdn-number))

  Unforunately, some assertion values are don't carry the same
  constraint (but its unclear how such an assertion could ever
  be true). In LDAP, there is one syntax (numericString) not two
  (numericString with constraint, numericString without constraint).
  This should be treated as numericString with non-empty constraint.
  Note that while someone may have no ISDN number, there are no ISDN
  numbers which are zero length.

  In matching, spaces are ignored.

PrintableString
  In ASN.1, Printable string is just a string of printable characters
  and can be empty.  In X.500, semantics much like NumericString (see
  serialNumber for a like example) excepting uses insignificant space
  handling instead of ignore all spaces.  

IA5String
  Basically same as PrintableString.  There are no examples in X.500,
  but same logic applies.  So we require them to be non-empty as
  well.

-------------------------------------------------------------------*/

static int
UTF8StringValidate(
	Syntax *syntax,
	struct berval *in )
{
	ber_len_t count;
	int len;
	unsigned char *u = in->bv_val;

	if( in->bv_len == 0 && syntax == slap_schema.si_syn_directoryString ) {
		/* directory strings cannot be empty */
		return LDAP_INVALID_SYNTAX;
	}

	for( count = in->bv_len; count > 0; count-=len, u+=len ) {
		/* get the length indicated by the first byte */
		len = LDAP_UTF8_CHARLEN2( u, len );

		/* very basic checks */
		switch( len ) {
			case 6:
				if( (u[5] & 0xC0) != 0x80 ) {
					return LDAP_INVALID_SYNTAX;
				}
			case 5:
				if( (u[4] & 0xC0) != 0x80 ) {
					return LDAP_INVALID_SYNTAX;
				}
			case 4:
				if( (u[3] & 0xC0) != 0x80 ) {
					return LDAP_INVALID_SYNTAX;
				}
			case 3:
				if( (u[2] & 0xC0 )!= 0x80 ) {
					return LDAP_INVALID_SYNTAX;
				}
			case 2:
				if( (u[1] & 0xC0) != 0x80 ) {
					return LDAP_INVALID_SYNTAX;
				}
			case 1:
				/* CHARLEN already validated it */
				break;
			default:
				return LDAP_INVALID_SYNTAX;
		}

		/* make sure len corresponds with the offset
			to the next character */
		if( LDAP_UTF8_OFFSET( u ) != len ) return LDAP_INVALID_SYNTAX;
	}

	if( count != 0 ) {
		return LDAP_INVALID_SYNTAX;
	}

	return LDAP_SUCCESS;
}

#ifdef SLAP_NVALUES
static int
UTF8StringNormalize(
	slap_mask_t use,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *val,
	struct berval *normalized )
{
	struct berval tmp, nvalue;
	int flags;
	int i, wasspace;

	if( val->bv_val == NULL ) {
		/* assume we're dealing with a syntax (e.g., UTF8String)
		 * which allows empty strings
		 */
		normalized->bv_len = 0;
		normalized->bv_val = NULL;
		return LDAP_SUCCESS;
	}

	flags = SLAP_MR_ASSOCIATED(mr, slap_schema.si_mr_caseExactMatch )
		? LDAP_UTF8_NOCASEFOLD : LDAP_UTF8_CASEFOLD;
	flags |= ( use & SLAP_MR_EQUALITY_APPROX == SLAP_MR_EQUALITY_APPROX )
		? LDAP_UTF8_APPROX : 0;

	val = UTF8bvnormalize( val, &tmp, flags );
	if( val == NULL ) {
		return LDAP_OTHER;
	}
	
	/* collapse spaces (in place) */
	nvalue.bv_len = 0;
	nvalue.bv_val = tmp.bv_val;

	wasspace=1; /* trim leading spaces */
	for( i=0; i<tmp.bv_len; i++) {
		if ( ASCII_SPACE( tmp.bv_val[i] )) {
			if( wasspace++ == 0 ) {
				/* trim repeated spaces */
				nvalue.bv_val[nvalue.bv_len++] = tmp.bv_val[i];
			}
		} else {
			wasspace = 0;
			nvalue.bv_val[nvalue.bv_len++] = tmp.bv_val[i];
		}
	}

	if( nvalue.bv_len ) {
		if( wasspace ) {
			/* last character was a space, trim it */
			--nvalue.bv_len;
		}
		nvalue.bv_val[nvalue.bv_len] = '\0';

	} else {
		/* string of all spaces is treated as one space */
		nvalue.bv_val[0] = ' ';
		nvalue.bv_val[1] = '\0';
		nvalue.bv_len = 1;
	}

	*normalized = nvalue;
	return LDAP_SUCCESS;
}
#else

static int
xUTF8StringNormalize(
	Syntax *syntax,
	struct berval *val,
	struct berval *normalized )
{
	char *p, *q, *s, *e;
	int len = 0;

	/* validator should have refused an empty string */
	assert( val->bv_len );

	p = val->bv_val;

	/* Ignore initial whitespace */
	/* All space is ASCII. All ASCII is 1 byte */
	for ( ; p < val->bv_val + val->bv_len && ASCII_SPACE( p[ 0 ] ); p++ );

	normalized->bv_len = val->bv_len - (p - val->bv_val);

	if( !normalized->bv_len ) {
		ber_mem2bv( " ", 1, 1, normalized );
		return LDAP_SUCCESS;
	}

	ber_mem2bv( p, normalized->bv_len, 1, normalized );
	e = normalized->bv_val + normalized->bv_len;

	assert( normalized->bv_val );

	p = q = normalized->bv_val;
	s = NULL;

	while ( p < e ) {
		q += len;
		if ( ASCII_SPACE( *p ) ) {
			s = q - len;
			len = 1;
			*q = *p++;

			/* Ignore the extra whitespace */
			while ( ASCII_SPACE( *p ) ) {
				p++;
			}
		} else {
			len = LDAP_UTF8_COPY(q,p);
			s=NULL;
			p+=len;
		}
	}

	assert( normalized->bv_val <= p );
	assert( q+len <= p );

	/* cannot start with a space */
	assert( !ASCII_SPACE( normalized->bv_val[0] ) );

	/*
	 * If the string ended in space, backup the pointer one
	 * position.  One is enough because the above loop collapsed
	 * all whitespace to a single space.
	 */

	if ( s != NULL ) {
		len = q - s;
		q = s;
	}

	/* cannot end with a space */
	assert( !ASCII_SPACE( *q ) );

	q += len;

	/* null terminate */
	*q = '\0';

	normalized->bv_len = q - normalized->bv_val;

	return LDAP_SUCCESS;
}

/* Returns Unicode canonically normalized copy of a substring assertion
 * Skipping attribute description */
static SubstringsAssertion *
UTF8SubstringsAssertionNormalize(
	SubstringsAssertion *sa,
	unsigned casefold )
{
	SubstringsAssertion *nsa;
	int i;

	nsa = (SubstringsAssertion *)SLAP_CALLOC( 1, sizeof(SubstringsAssertion) );
	if( nsa == NULL ) {
		return NULL;
	}

	if( sa->sa_initial.bv_val != NULL ) {
		UTF8bvnormalize( &sa->sa_initial, &nsa->sa_initial, casefold );
		if( nsa->sa_initial.bv_val == NULL ) {
			goto err;
		}
	}

	if( sa->sa_any != NULL ) {
		for( i=0; sa->sa_any[i].bv_val != NULL; i++ ) {
			/* empty */
		}
		nsa->sa_any = (struct berval *)
			SLAP_MALLOC( (i + 1) * sizeof(struct berval) );
		if( nsa->sa_any == NULL ) {
				goto err;
		}

		for( i=0; sa->sa_any[i].bv_val != NULL; i++ ) {
			UTF8bvnormalize( &sa->sa_any[i], &nsa->sa_any[i], 
				casefold );
			if( nsa->sa_any[i].bv_val == NULL ) {
				goto err;
			}
		}
		nsa->sa_any[i].bv_val = NULL;
	}

	if( sa->sa_final.bv_val != NULL ) {
		UTF8bvnormalize( &sa->sa_final, &nsa->sa_final, casefold );
		if( nsa->sa_final.bv_val == NULL ) {
			goto err;
		}
	}

	return nsa;

err:
	if ( nsa->sa_final.bv_val ) free( nsa->sa_final.bv_val );
	if ( nsa->sa_any ) ber_bvarray_free( nsa->sa_any );
	if ( nsa->sa_initial.bv_val ) free( nsa->sa_initial.bv_val );
	ch_free( nsa );
	return NULL;
}

#ifndef SLAPD_APPROX_OLDSINGLESTRING

#if defined(SLAPD_APPROX_INITIALS)
#define SLAPD_APPROX_DELIMITER "._ "
#define SLAPD_APPROX_WORDLEN 2
#else
#define SLAPD_APPROX_DELIMITER " "
#define SLAPD_APPROX_WORDLEN 1
#endif

static int
approxMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	struct berval *nval, *assertv;
	char *val, **values, **words, *c;
	int i, count, len, nextchunk=0, nextavail=0;

	/* Yes, this is necessary */
	nval = UTF8bvnormalize( value, NULL, LDAP_UTF8_APPROX );
	if( nval == NULL ) {
		*matchp = 1;
		return LDAP_SUCCESS;
	}

	/* Yes, this is necessary */
	assertv = UTF8bvnormalize( ((struct berval *)assertedValue),
		NULL, LDAP_UTF8_APPROX );
	if( assertv == NULL ) {
		ber_bvfree( nval );
		*matchp = 1;
		return LDAP_SUCCESS;
	}

	/* Isolate how many words there are */
	for ( c = nval->bv_val, count = 1; *c; c++ ) {
		c = strpbrk( c, SLAPD_APPROX_DELIMITER );
		if ( c == NULL ) break;
		*c = '\0';
		count++;
	}

	/* Get a phonetic copy of each word */
	words = (char **)ch_malloc( count * sizeof(char *) );
	values = (char **)ch_malloc( count * sizeof(char *) );
	for ( c = nval->bv_val, i = 0;  i < count; i++, c += strlen(c) + 1 ) {
		words[i] = c;
		values[i] = phonetic(c);
	}

	/* Work through the asserted value's words, to see if at least some
	   of the words are there, in the same order. */
	len = 0;
	while ( (ber_len_t) nextchunk < assertv->bv_len ) {
		len = strcspn( assertv->bv_val + nextchunk, SLAPD_APPROX_DELIMITER);
		if( len == 0 ) {
			nextchunk++;
			continue;
		}
#if defined(SLAPD_APPROX_INITIALS)
		else if( len == 1 ) {
			/* Single letter words need to at least match one word's initial */
			for( i=nextavail; i<count; i++ )
				if( !strncasecmp( assertv->bv_val + nextchunk, words[i], 1 )) {
					nextavail=i+1;
					break;
				}
		}
#endif
		else {
			/* Isolate the next word in the asserted value and phonetic it */
			assertv->bv_val[nextchunk+len] = '\0';
			val = phonetic( assertv->bv_val + nextchunk );

			/* See if this phonetic chunk is in the remaining words of *value */
			for( i=nextavail; i<count; i++ ){
				if( !strcmp( val, values[i] ) ){
					nextavail = i+1;
					break;
				}
			}
			ch_free( val );
		}

		/* This chunk in the asserted value was NOT within the *value. */
		if( i >= count ) {
			nextavail=-1;
			break;
		}

		/* Go on to the next word in the asserted value */
		nextchunk += len+1;
	}

	/* If some of the words were seen, call it a match */
	if( nextavail > 0 ) {
		*matchp = 0;
	}
	else {
		*matchp = 1;
	}

	/* Cleanup allocs */
	ber_bvfree( assertv );
	for( i=0; i<count; i++ ) {
		ch_free( values[i] );
	}
	ch_free( values );
	ch_free( words );
	ber_bvfree( nval );

	return LDAP_SUCCESS;
}

static int 
approxIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	BerVarray values,
	BerVarray *keysp )
{
	char *c;
	int i,j, len, wordcount, keycount=0;
	struct berval *newkeys;
	BerVarray keys=NULL;

	for( j=0; values[j].bv_val != NULL; j++ ) {
		struct berval val = { 0, NULL };
		/* Yes, this is necessary */
		UTF8bvnormalize( &values[j], &val, LDAP_UTF8_APPROX );
		assert( val.bv_val != NULL );

		/* Isolate how many words there are. There will be a key for each */
		for( wordcount = 0, c = val.bv_val; *c; c++) {
			len = strcspn(c, SLAPD_APPROX_DELIMITER);
			if( len >= SLAPD_APPROX_WORDLEN ) wordcount++;
			c+= len;
			if (*c == '\0') break;
			*c = '\0';
		}

		/* Allocate/increase storage to account for new keys */
		newkeys = (struct berval *)ch_malloc( (keycount + wordcount + 1) 
			* sizeof(struct berval) );
		AC_MEMCPY( newkeys, keys, keycount * sizeof(struct berval) );
		if( keys ) ch_free( keys );
		keys = newkeys;

		/* Get a phonetic copy of each word */
		for( c = val.bv_val, i = 0; i < wordcount; c += len + 1 ) {
			len = strlen( c );
			if( len < SLAPD_APPROX_WORDLEN ) continue;
			ber_str2bv( phonetic( c ), 0, 0, &keys[keycount] );
			keycount++;
			i++;
		}

		ber_memfree( val.bv_val );
	}
	keys[keycount].bv_val = NULL;
	*keysp = keys;

	return LDAP_SUCCESS;
}

static int 
approxFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertedValue,
	BerVarray *keysp )
{
	char *c;
	int i, count, len;
	struct berval *val;
	BerVarray keys;

	/* Yes, this is necessary */
	val = UTF8bvnormalize( ((struct berval *)assertedValue),
		NULL, LDAP_UTF8_APPROX );
	if( val == NULL || val->bv_val == NULL ) {
		keys = (struct berval *)ch_malloc( sizeof(struct berval) );
		keys[0].bv_val = NULL;
		*keysp = keys;
		ber_bvfree( val );
		return LDAP_SUCCESS;
	}

	/* Isolate how many words there are. There will be a key for each */
	for( count = 0,c = val->bv_val; *c; c++) {
		len = strcspn(c, SLAPD_APPROX_DELIMITER);
		if( len >= SLAPD_APPROX_WORDLEN ) count++;
		c+= len;
		if (*c == '\0') break;
		*c = '\0';
	}

	/* Allocate storage for new keys */
	keys = (struct berval *)ch_malloc( (count + 1) * sizeof(struct berval) );

	/* Get a phonetic copy of each word */
	for( c = val->bv_val, i = 0; i < count; c += len + 1 ) {
		len = strlen(c);
		if( len < SLAPD_APPROX_WORDLEN ) continue;
		ber_str2bv( phonetic( c ), 0, 0, &keys[i] );