schema_init.c

/* schema_init.c - init builtin schema */
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
 * Copyright 1998-2005 The OpenLDAP Foundation.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted only as authorized by the OpenLDAP
 * Public License.
 *
 * A copy of this license is available in the file LICENSE in the
 * top-level directory of the distribution or, alternatively, at
 * <http://www.OpenLDAP.org/license.html>.
 */

#include "portable.h"

#include <stdio.h>
#ifdef HAVE_LIMITS_H
#include <limits.h>
#endif

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

#include "slap.h"

#include "ldap_utf8.h"

#ifdef HAVE_TLS
#include <openssl/x509.h>
#include <openssl/err.h>
#include <openssl/rsa.h>
#include <openssl/crypto.h>
#include <openssl/pem.h>
#include <openssl/bio.h>
#include <openssl/asn1.h>
#include <openssl/x509v3.h>
#include <openssl/ssl.h>
#endif

#include "lutil.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)

#define	OpenLDAPaciMatch			octetStringMatch

/* approx matching rules */
#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

/* Change Sequence Number (CSN) - much of this will change */
#define csnValidate				blobValidate
#define csnMatch				octetStringMatch
#define csnOrderingMatch		octetStringOrderingMatch
#define csnIndexer				generalizedTimeIndexer
#define csnFilter				generalizedTimeFilter

#ifdef SLAP_AUTHZ_SYNTAX
/* FIXME: temporary */
#define authzMatch				octetStringMatch
#endif /* SLAP_AUTHZ_SYNTAX */

unsigned int index_substr_if_minlen = SLAP_INDEX_SUBSTR_IF_MINLEN_DEFAULT;
unsigned int index_substr_if_maxlen = SLAP_INDEX_SUBSTR_IF_MAXLEN_DEFAULT;
unsigned int index_substr_any_len = SLAP_INDEX_SUBSTR_ANY_LEN_DEFAULT;
unsigned int index_substr_any_step = SLAP_INDEX_SUBSTR_ANY_STEP_DEFAULT;

ldap_pvt_thread_mutex_t	ad_undef_mutex;
ldap_pvt_thread_mutex_t	oc_undef_mutex;

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;
}

#define berValidate blobValidate

static int
sequenceValidate(
	Syntax *syntax,
	struct berval *in )
{
	if ( in->bv_len < 2 ) return LDAP_INVALID_SYNTAX;
	if ( in->bv_val[0] != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;

	return LDAP_SUCCESS;
}


#ifdef HAVE_TLS
static int certificateValidate( Syntax *syntax, struct berval *in )
{
	X509 *xcert=NULL;
	unsigned char *p = (unsigned char *)in->bv_val;
 
	xcert = d2i_X509(NULL, &p, in->bv_len);
	if ( !xcert ) return LDAP_INVALID_SYNTAX;
	X509_free(xcert);
	return LDAP_SUCCESS;
}
#else
#define certificateValidate sequenceValidate
#endif

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

	if( match == 0 ) {
		match = memcmp( value->bv_val, asserted->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 )
{
	struct berval *asserted = (struct berval *) assertedValue;
	ber_len_t v_len  = value->bv_len;
	ber_len_t av_len = asserted->bv_len;

	int match = memcmp( value->bv_val, asserted->bv_val,
		(v_len < av_len ? v_len : av_len) );

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

	*matchp = match;
	return LDAP_SUCCESS;
}

void
hashDigestify(
	HASH_CONTEXT *HASHcontext,
	unsigned char *HASHdigest,
	struct berval *prefix,
	char pre,
	Syntax *syntax,
	MatchingRule *mr,
	unsigned char *value,
	int value_len)
{
	HASH_Init(HASHcontext);
	if(prefix && prefix->bv_len > 0) {
		HASH_Update(HASHcontext,
			(unsigned char *)prefix->bv_val, prefix->bv_len);
	}
	if(pre) HASH_Update(HASHcontext, (unsigned char*)&pre, sizeof(pre));
	HASH_Update(HASHcontext, (unsigned char*)syntax->ssyn_oid, syntax->ssyn_oidlen);
	HASH_Update(HASHcontext, (unsigned char*)mr->smr_oid, mr->smr_oidlen);
	HASH_Update(HASHcontext, value, value_len);
	HASH_Final(HASHdigest, HASHcontext);
	return;
}

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

	for( i=0; !BER_BVISNULL( &values[i] ); i++ ) {
		/* just count them */
	}

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

	keys = slap_sl_malloc( sizeof( struct berval ) * (i+1), ctx );

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

	for( i=0; !BER_BVISNULL( &values[i] ); i++ ) {
		hashDigestify( &HASHcontext, HASHdigest, prefix, 0,
			syntax, mr, (unsigned char *)values[i].bv_val, values[i].bv_len );
		ber_dupbv_x( &keys[i], &digest, ctx );
	}

	BER_BVZERO( &keys[i] );

	*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,
	void *ctx )
{
	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 = (char *)HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

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

	keys = slap_sl_malloc( sizeof( struct berval ) * 2, ctx );

	hashDigestify( &HASHcontext, HASHdigest, prefix, 0,
		syntax, mr, (unsigned char *)value->bv_val, value->bv_len );

	ber_dupbv_x( keys, &digest, ctx );
	BER_BVZERO( &keys[1] );

	*keysp = keys;

	return LDAP_SUCCESS;
}

static int
octetStringSubstringsMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	int match = 0;
	SubstringsAssertion *sub = assertedValue;
	struct berval left = *value;
	int i;
	ber_len_t inlen = 0;

	/* Add up asserted input length */
	if ( !BER_BVISNULL( &sub->sa_initial ) ) {
		inlen += sub->sa_initial.bv_len;
	}
	if ( sub->sa_any ) {
		for ( i = 0; !BER_BVISNULL( &sub->sa_any[i] ); i++ ) {
			inlen += sub->sa_any[i].bv_len;
		}
	}
	if ( !BER_BVISNULL( &sub->sa_final ) ) {
		inlen += sub->sa_final.bv_len;
	}

	if ( !BER_BVISNULL( &sub->sa_initial ) ) {
		if ( inlen > left.bv_len ) {
			match = 1;
			goto done;
		}

		match = memcmp( sub->sa_initial.bv_val, left.bv_val,
			sub->sa_initial.bv_len );

		if ( match != 0 ) {
			goto done;
		}

		left.bv_val += sub->sa_initial.bv_len;
		left.bv_len -= sub->sa_initial.bv_len;
		inlen -= sub->sa_initial.bv_len;
	}

	if ( !BER_BVISNULL( &sub->sa_final ) ) {
		if ( inlen > left.bv_len ) {
			match = 1;
			goto done;
		}

		match = memcmp( sub->sa_final.bv_val,
			&left.bv_val[left.bv_len - sub->sa_final.bv_len],
			sub->sa_final.bv_len );

		if ( match != 0 ) {
			goto done;
		}

		left.bv_len -= sub->sa_final.bv_len;
		inlen -= sub->sa_final.bv_len;
	}

	if ( sub->sa_any ) {
		for ( i = 0; !BER_BVISNULL( &sub->sa_any[i] ); i++ ) {
			ber_len_t idx;
			char *p;

retry:
			if ( inlen > left.bv_len ) {
				/* not enough length */
				match = 1;
				goto done;
			}

			if ( BER_BVISEMPTY( &sub->sa_any[i] ) ) {
				continue;
			}

			p = memchr( left.bv_val, *sub->sa_any[i].bv_val, left.bv_len );

			if( p == NULL ) {
				match = 1;
				goto done;
			}

			idx = p - left.bv_val;

			if ( idx >= left.bv_len ) {
				/* this shouldn't happen */
				return LDAP_OTHER;
			}

			left.bv_val = p;
			left.bv_len -= idx;

			if ( sub->sa_any[i].bv_len > left.bv_len ) {
				/* not enough left */
				match = 1;
				goto done;
			}

			match = memcmp( left.bv_val,
				sub->sa_any[i].bv_val,
				sub->sa_any[i].bv_len );

			if ( match != 0 ) {
				left.bv_val++;
				left.bv_len--;
				goto retry;
			}

			left.bv_val += sub->sa_any[i].bv_len;
			left.bv_len -= sub->sa_any[i].bv_len;
			inlen -= sub->sa_any[i].bv_len;
		}
	}

done:
	*matchp = match;
	return LDAP_SUCCESS;
}

/* Substrings Index generation function */
static int
octetStringSubstringsIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	BerVarray values,
	BerVarray *keysp,
	void *ctx )
{
	ber_len_t i, nkeys;
	size_t slen, mlen;
	BerVarray keys;

	HASH_CONTEXT HASHcontext;
	unsigned char HASHdigest[HASH_BYTES];
	struct berval digest;
	digest.bv_val = (char *)HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

	nkeys = 0;

	for ( i = 0; !BER_BVISNULL( &values[i] ); i++ ) {
		/* count number of indices to generate */
		if( flags & SLAP_INDEX_SUBSTR_INITIAL ) {
			if( values[i].bv_len >= index_substr_if_maxlen ) {
				nkeys += index_substr_if_maxlen -
					(index_substr_if_minlen - 1);
			} else if( values[i].bv_len >= index_substr_if_minlen ) {
				nkeys += values[i].bv_len - (index_substr_if_minlen - 1);
			}
		}

		if( flags & SLAP_INDEX_SUBSTR_ANY ) {
			if( values[i].bv_len >= index_substr_any_len ) {
				nkeys += values[i].bv_len - (index_substr_any_len - 1);
			}
		}

		if( flags & SLAP_INDEX_SUBSTR_FINAL ) {
			if( values[i].bv_len >= index_substr_if_maxlen ) {
				nkeys += index_substr_if_maxlen -
					(index_substr_if_minlen - 1);
			} else if( values[i].bv_len >= index_substr_if_minlen ) {
				nkeys += values[i].bv_len - (index_substr_if_minlen - 1);
			}
		}
	}

	if( nkeys == 0 ) {
		/* no keys to generate */
		*keysp = NULL;
		return LDAP_SUCCESS;
	}

	keys = slap_sl_malloc( sizeof( struct berval ) * (nkeys+1), ctx );

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

	nkeys = 0;
	for ( i = 0; !BER_BVISNULL( &values[i] ); i++ ) {
		ber_len_t j,max;

		if( ( flags & SLAP_INDEX_SUBSTR_ANY ) &&
			( values[i].bv_len >= index_substr_any_len ) )
		{
			char pre = SLAP_INDEX_SUBSTR_PREFIX;
			max = values[i].bv_len - (index_substr_any_len - 1);

			for( j=0; j<max; j++ ) {
				hashDigestify( &HASHcontext, HASHdigest, prefix, pre,
					syntax, mr, (unsigned char *)&values[i].bv_val[j], index_substr_any_len);
				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}
		}

		/* skip if too short */ 
		if( values[i].bv_len < index_substr_if_minlen ) continue;

		max = index_substr_if_maxlen < values[i].bv_len
			? index_substr_if_maxlen : values[i].bv_len;

		for( j=index_substr_if_minlen; j<=max; j++ ) {
			char pre;

			if( flags & SLAP_INDEX_SUBSTR_INITIAL ) {
				pre = SLAP_INDEX_SUBSTR_INITIAL_PREFIX;
				hashDigestify( &HASHcontext, HASHdigest, prefix, pre,
					syntax, mr, (unsigned char *)values[i].bv_val, j );
				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}

			if( flags & SLAP_INDEX_SUBSTR_FINAL ) {
				pre = SLAP_INDEX_SUBSTR_FINAL_PREFIX;
				hashDigestify( &HASHcontext, HASHdigest, prefix, pre,
					syntax, mr, (unsigned char *)&values[i].bv_val[values[i].bv_len-j], j );
				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}

		}
	}

	if( nkeys > 0 ) {
		BER_BVZERO( &keys[nkeys] );
		*keysp = keys;
	} else {
		ch_free( keys );
		*keysp = NULL;
	}

	return LDAP_SUCCESS;
}

static int
octetStringSubstringsFilter (
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertedValue,
	BerVarray *keysp,
	void *ctx)
{
	SubstringsAssertion *sa;
	char pre;
	ber_len_t nkeys = 0;
	size_t slen, mlen, klen;
	BerVarray keys;
	HASH_CONTEXT HASHcontext;
	unsigned char HASHdigest[HASH_BYTES];
	struct berval *value;
	struct berval digest;

	sa = (SubstringsAssertion *) assertedValue;

	if( flags & SLAP_INDEX_SUBSTR_INITIAL &&
		!BER_BVISNULL( &sa->sa_initial ) &&
		sa->sa_initial.bv_len >= index_substr_if_minlen )
	{
		nkeys++;
		if ( sa->sa_initial.bv_len > index_substr_if_maxlen &&
			( flags & SLAP_INDEX_SUBSTR_ANY ))
		{
			nkeys += 1 + (sa->sa_initial.bv_len - index_substr_if_maxlen) / index_substr_any_step;
		}
	}

	if ( flags & SLAP_INDEX_SUBSTR_ANY && sa->sa_any != NULL ) {
		ber_len_t i;
		for( i=0; !BER_BVISNULL( &sa->sa_any[i] ); i++ ) {
			if( sa->sa_any[i].bv_len >= index_substr_any_len ) {
				/* don't bother accounting with stepping */
				nkeys += sa->sa_any[i].bv_len -
					( index_substr_any_len - 1 );
			}
		}
	}

	if( flags & SLAP_INDEX_SUBSTR_FINAL &&
		!BER_BVISNULL( &sa->sa_final ) &&
		sa->sa_final.bv_len >= index_substr_if_minlen )
	{
		nkeys++;
		if ( sa->sa_final.bv_len > index_substr_if_maxlen &&
			( flags & SLAP_INDEX_SUBSTR_ANY ))
		{
			nkeys += 1 + (sa->sa_final.bv_len - index_substr_if_maxlen) / index_substr_any_step;
		}
	}

	if( nkeys == 0 ) {
		*keysp = NULL;
		return LDAP_SUCCESS;
	}

	digest.bv_val = (char *)HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

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

	keys = slap_sl_malloc( sizeof( struct berval ) * (nkeys+1), ctx );
	nkeys = 0;

	if( flags & SLAP_INDEX_SUBSTR_INITIAL &&
		!BER_BVISNULL( &sa->sa_initial ) &&
		sa->sa_initial.bv_len >= index_substr_if_minlen )
	{
		pre = SLAP_INDEX_SUBSTR_INITIAL_PREFIX;
		value = &sa->sa_initial;

		klen = index_substr_if_maxlen < value->bv_len
			? index_substr_if_maxlen : value->bv_len;

		hashDigestify( &HASHcontext, HASHdigest, prefix, pre,
			syntax, mr, (unsigned char *)value->bv_val, klen );
		ber_dupbv_x( &keys[nkeys++], &digest, ctx );

		/* If initial is too long and we have subany indexed, use it
		 * to match the excess...
		 */
		if (value->bv_len > index_substr_if_maxlen && (flags & SLAP_INDEX_SUBSTR_ANY))
		{
			ber_len_t j;
			pre = SLAP_INDEX_SUBSTR_PREFIX;
			for ( j=index_substr_if_maxlen-1; j <= value->bv_len - index_substr_any_len; j+=index_substr_any_step )
			{
				hashDigestify( &HASHcontext, HASHdigest, prefix, pre,
					syntax, mr, (unsigned char *)&value->bv_val[j], index_substr_any_len );
				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}
		}
	}

	if( flags & SLAP_INDEX_SUBSTR_ANY && sa->sa_any != NULL ) {
		ber_len_t i, j;
		pre = SLAP_INDEX_SUBSTR_PREFIX;
		klen = index_substr_any_len;

		for( i=0; !BER_BVISNULL( &sa->sa_any[i] ); i++ ) {
			if( sa->sa_any[i].bv_len < index_substr_any_len ) {
				continue;
			}

			value = &sa->sa_any[i];

			for(j=0;
				j <= value->bv_len - index_substr_any_len;
				j += index_substr_any_step )
			{
				hashDigestify( &HASHcontext, HASHdigest, prefix, pre,
					syntax, mr, (unsigned char *)&value->bv_val[j], klen ); 
				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}
		}
	}

	if( flags & SLAP_INDEX_SUBSTR_FINAL &&
		!BER_BVISNULL( &sa->sa_final ) &&
		sa->sa_final.bv_len >= index_substr_if_minlen )
	{
		pre = SLAP_INDEX_SUBSTR_FINAL_PREFIX;
		value = &sa->sa_final;

		klen = index_substr_if_maxlen < value->bv_len
			? index_substr_if_maxlen : value->bv_len;

		hashDigestify( &HASHcontext, HASHdigest, prefix, pre,
			syntax, mr, (unsigned char *)&value->bv_val[value->bv_len-klen], klen );
		ber_dupbv_x( &keys[nkeys++], &digest, ctx );

		/* If final is too long and we have subany indexed, use it
		 * to match the excess...
		 */
		if (value->bv_len > index_substr_if_maxlen && (flags & SLAP_INDEX_SUBSTR_ANY))
		{
			ber_len_t j;
			pre = SLAP_INDEX_SUBSTR_PREFIX;
			for ( j=0; j <= value->bv_len - index_substr_if_maxlen; j+=index_substr_any_step )
			{
				hashDigestify( &HASHcontext, HASHdigest, prefix, pre,
					syntax, mr, (unsigned char *)&value->bv_val[j], index_substr_any_len );
				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}
		}
	}

	if( nkeys > 0 ) {
		BER_BVZERO( &keys[nkeys] );
		*keysp = keys;
	} else {
		ch_free( keys );
		*keysp = NULL;
	}

	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 "'B"
	 *	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;
}

/*
 * Syntax is [RFC2252]:
 *

6.3. Bit String

   ( 1.3.6.1.4.1.1466.115.121.1.6 DESC 'Bit String' )

   Values in this syntax are encoded according to the following BNF:

      bitstring = "'" *binary-digit "'B"

      binary-digit = "0" / "1"

   ... 

6.21. Name And Optional UID

   ( 1.3.6.1.4.1.1466.115.121.1.34 DESC 'Name And Optional UID' )

   Values in this syntax are encoded according to the following BNF:

      NameAndOptionalUID = DistinguishedName [ "#" bitstring ]

   Although the '#' character may occur in a string representation of a
   distinguished name, no additional special quoting is done.  This
   syntax has been added subsequent to RFC 1778.

   Example:

      1.3.6.1.4.1.1466.0=#04024869,O=Test,C=GB#'0101'B

 *
 * draft-ietf-ldapbis-syntaxes-xx.txt says:
 *

3.3.2.  Bit String

   A value of the Bit String syntax is a sequence of binary digits.  The
   LDAP-specific encoding of a value of this syntax is defined by the
   following ABNF:

      BitString    = SQUOTE *binary-digit SQUOTE "B"

      binary-digit = "0" / "1"

   The <SQUOTE> rule is defined in [MODELS].

      Example:
         '0101111101'B

   The LDAP definition for the Bit String syntax is:

      ( 1.3.6.1.4.1.1466.115.121.1.6 DESC 'Bit String' )

   This syntax corresponds to the BIT STRING ASN.1 type from [ASN.1].

   ...

3.3.21.  Name and Optional UID

   A value of the Name and Optional UID syntax is the distinguished name
   [MODELS] of an entity optionally accompanied by a unique identifier
   that serves to differentiate the entity from others with an identical
   distinguished name.

   The LDAP-specific encoding of a value of this syntax is defined by
   the following ABNF:

       NameAndOptionalUID = distinguishedName [ SHARP BitString ]

   The <BitString> rule is defined in Section 3.3.2.  The
   <distinguishedName> rule is defined in [LDAPDN].  The <SHARP> rule is
   defined in [MODELS].

   Note that although the '#' character may occur in the string
   representation of a distinguished name, no additional escaping of
   this character is performed when a <distinguishedName> is encoded in
   a <NameAndOptionalUID>.

      Example:
         1.3.6.1.4.1.1466.0=#04024869,O=Test,C=GB#'0101'B

   The LDAP definition for the Name and Optional UID syntax is:

      ( 1.3.6.1.4.1.1466.115.121.1.34 DESC 'Name And Optional UID' )

   This syntax corresponds to the NameAndOptionalUID ASN.1 type from
   [X.520].

 *
 * draft-ietf-ldapbis-models-xx.txt [MODELS] says:
 *

1.4. Common ABNF Productions

  ...
      SHARP   = %x23 ; octothorpe (or sharp sign) ("#")
  ...
      SQUOTE  = %x27 ; single quote ("'")
  ...
      
 *
 * Note: normalization strips any leading "0"s, unless the
 * bit string is exactly "'0'B", so the normalized example,
 * in slapd, would result in
 * 
 * 1.3.6.1.4.1.1466.0=#04024869,o=test,c=gb#'101'B
 * 
 * Since draft-ietf-ldapbis-dn-xx.txt clarifies that SHARP,
 * i.e. "#", doesn't have to be escaped except when at the
 * beginning of a value, the definition of Name and Optional
 * UID appears to be flawed, because there is no clear means
 * to determine whether the UID part is present or not.
 *
 * Example:
 *
 * 	cn=Someone,dc=example,dc=com#'1'B
 *
 * could be either a NameAndOptionalUID with trailing UID, i.e.
 *
 * 	DN = "cn=Someone,dc=example,dc=com"
 * 	UID = "'1'B"
 * 
 * or a NameAndOptionalUID with no trailing UID, and the AVA
 * in the last RDN made of
 *
 * 	attributeType = dc 
 * 	attributeValue = com#'1'B
 *
 * in fact "com#'1'B" is a valid IA5 string.
 *
 * As a consequence, current slapd code assumes that the
 * presence of portions of a BitString at the end of the string 
 * representation of a NameAndOptionalUID means a BitString
 * is expected, and cause an error otherwise.  This is quite
 * arbitrary, and might change in the future.
 */


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

	if( BER_BVISEMPTY( in ) ) return LDAP_SUCCESS;

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

	/* if there's a "#", try bitStringValidate()... */
	uid.bv_val = strrchr( dn.bv_val, '#' );
	if ( !BER_BVISNULL( &uid ) ) {
		uid.bv_val++;
		uid.bv_len = dn.bv_len - ( uid.bv_val - dn.bv_val );

		rc = bitStringValidate( NULL, &uid );
		if ( rc == LDAP_SUCCESS ) {
			/* in case of success, trim the UID,
			 * otherwise treat it as part of the DN */
			dn.bv_len -= uid.bv_len + 1;
			uid.bv_val[-1] = '\0';
		}
	}

	rc = dnValidate( NULL, &dn );

	ber_memfree( dn.bv_val );
	return rc;
}

int
nameUIDPretty(
	Syntax *syntax,
	struct berval *val,
	struct berval *out,
	void *ctx )
{
	assert( val != NULL );
	assert( out != NULL );


	Debug( LDAP_DEBUG_TRACE, ">>> nameUIDPretty: <%s>\n", val->bv_val, 0, 0 );

	if( BER_BVISEMPTY( val ) ) {
		ber_dupbv_x( out, val, ctx );

	} else if ( val->bv_len > SLAP_LDAPDN_MAXLEN ) {
		return LDAP_INVALID_SYNTAX;

	} else {
		int		rc;
		struct berval	dnval = *val;
		struct berval	uidval = BER_BVNULL;

		uidval.bv_val = strrchr( val->bv_val, '#' );
		if ( !BER_BVISNULL( &uidval ) ) {
			uidval.bv_val++;
			uidval.bv_len = val->bv_len - ( uidval.bv_val - val->bv_val );

			rc = bitStringValidate( NULL, &uidval );

			if ( rc == LDAP_SUCCESS ) {
				ber_dupbv_x( &dnval, val, ctx );
				dnval.bv_len -= uidval.bv_len + 1;
				dnval.bv_val[dnval.bv_len] = '\0';

			} else {
				BER_BVZERO( &uidval );
			}
		}

		rc = dnPretty( syntax, &dnval, out, ctx );
		if ( dnval.bv_val != val->bv_val ) {
			slap_sl_free( dnval.bv_val, ctx );
		}
		if( rc != LDAP_SUCCESS ) {
			return rc;
		}

		if( !BER_BVISNULL( &uidval ) ) {
			int	i, c, got1;
			char	*tmp;

			tmp = slap_sl_realloc( out->bv_val, out->bv_len 
				+ STRLENOF( "#" ) + uidval.bv_len + 1,
				ctx );
			if( tmp == NULL ) {
				ber_memfree_x( out->bv_val, ctx );
				return LDAP_OTHER;
			}
			out->bv_val = tmp;
			out->bv_val[out->bv_len++] = '#';
			out->bv_val[out->bv_len++] = '\'';

			got1 = uidval.bv_len < sizeof("'0'B"); 
			for( i = 1; i < uidval.bv_len - 2; i++ ) {
				c = uidval.bv_val[i];
				switch(c) {
					case '0':
						if( got1 ) out->bv_val[out->bv_len++] = c;
						break;
					case '1':
						got1 = 1;
						out->bv_val[out->bv_len++] = c;
						break;
				}
			}

			out->bv_val[out->bv_len++] = '\'';
			out->bv_val[out->bv_len++] = 'B';
			out->bv_val[out->bv_len] = '\0';
		}
	}

	Debug( LDAP_DEBUG_TRACE, "<<< nameUIDPretty: <%s>\n", out->bv_val, 0, 0 );

	return LDAP_SUCCESS;
}

static int
uniqueMemberNormalize(
	slap_mask_t usage,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *val,
	struct berval *normalized,
	void *ctx )
{
	struct berval out;
	int rc;

	assert( SLAP_MR_IS_VALUE_OF_SYNTAX( usage ));

	ber_dupbv_x( &out, val, ctx );
	if ( BER_BVISEMPTY( &out ) ) {
		*normalized = out;

	} else {
		struct berval uid = BER_BVNULL;

		uid.bv_val = strrchr( out.bv_val, '#' );
		if ( !BER_BVISNULL( &uid ) ) {
			uid.bv_val++;
			uid.bv_len = out.bv_len - ( uid.bv_val - out.bv_val );

			rc = bitStringValidate( NULL, &uid );
			if ( rc == LDAP_SUCCESS ) {
				uid.bv_val[-1] = '\0';
				out.bv_len -= uid.bv_len + 1;
			} else {
				BER_BVZERO( &uid );
			}
		}

		rc = dnNormalize( 0, NULL, NULL, &out, normalized, ctx );

		if( rc != LDAP_SUCCESS ) {
			slap_sl_free( out.bv_val, ctx );
			return LDAP_INVALID_SYNTAX;
		}

		if( !BER_BVISNULL( &uid ) ) {
			char	*tmp;

			tmp = ch_realloc( normalized->bv_val,
				normalized->bv_len + uid.bv_len
				+ STRLENOF("#") + 1 );
			if ( tmp == NULL ) {
				ber_memfree_x( normalized->bv_val, ctx );
				return LDAP_OTHER;
			}

			normalized->bv_val = tmp;

			/* 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';
		}

		slap_sl_free( out.bv_val, ctx );
	}

	return LDAP_SUCCESS;
}

static int
uniqueMemberMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	int match;
	struct berval *asserted = (struct berval *) assertedValue;
	struct berval assertedDN = *asserted;
	struct berval assertedUID = BER_BVNULL;
	struct berval valueDN = BER_BVNULL;
	struct berval valueUID = BER_BVNULL;
	int approx = ((flags & SLAP_MR_EQUALITY_APPROX) == SLAP_MR_EQUALITY_APPROX);

	if ( !BER_BVISEMPTY( asserted ) ) {
		assertedUID.bv_val = strrchr( assertedDN.bv_val, '#' );
		if ( !BER_BVISNULL( &assertedUID ) ) {
			assertedUID.bv_val++;
			assertedUID.bv_len = assertedDN.bv_len
				- ( assertedUID.bv_val - assertedDN.bv_val );

			if ( bitStringValidate( NULL, &assertedUID ) == LDAP_SUCCESS ) {
				assertedDN.bv_len -= assertedUID.bv_len + 1;

			} else {
				BER_BVZERO( &assertedUID );
			}
		}
	}

	if ( !BER_BVISEMPTY( value ) ) {
		valueDN = *value;

		valueUID.bv_val = strrchr( valueDN.bv_val, '#' );
		if ( !BER_BVISNULL( &valueUID ) ) {
			valueUID.bv_val++;
			valueUID.bv_len = valueDN.bv_len
				- ( valueUID.bv_val - valueDN.bv_val );

			if ( bitStringValidate( NULL, &valueUID ) == LDAP_SUCCESS ) {
				valueDN.bv_len -= valueUID.bv_len + 1;

			} else {
				BER_BVZERO( &valueUID );
			}
		}
	}

	if( valueUID.bv_len && assertedUID.bv_len ) {
		match = valueUID.bv_len - assertedUID.bv_len;
		if ( match ) {
			*matchp = match;
			return LDAP_SUCCESS;
		}

		match = memcmp( valueUID.bv_val, assertedUID.bv_val, valueUID.bv_len );
		if( match ) {
			*matchp = match;
			return LDAP_SUCCESS;
		}

	} else if ( !approx && valueUID.bv_len ) {
		match = -1;
		*matchp = match;
		return LDAP_SUCCESS;

	} else if ( !approx && assertedUID.bv_len ) {
		match = 1;
		*matchp = match;
		return LDAP_SUCCESS;
	}

	return dnMatch( matchp, flags, syntax, mr, &valueDN, &assertedDN );
}

static int 
uniqueMemberIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	BerVarray values,
	BerVarray *keysp,
	void *ctx )
{
	BerVarray dnvalues;
	int rc;
	int i;
	for( i=0; !BER_BVISNULL( &values[i] ); i++ ) {
		/* just count them */                 
	}
	assert( i > 0 );

	dnvalues = slap_sl_malloc( sizeof( struct berval ) * (i+1), ctx );

	for( i=0; !BER_BVISNULL( &values[i] ); i++ ) {
		struct berval assertedDN = values[i];
		struct berval assertedUID = BER_BVNULL;

		if ( !BER_BVISEMPTY( &assertedDN ) ) {
			assertedUID.bv_val = strrchr( assertedDN.bv_val, '#' );
			if ( !BER_BVISNULL( &assertedUID ) ) {
				assertedUID.bv_val++;
				assertedUID.bv_len = assertedDN.bv_len
					- ( assertedUID.bv_val - assertedDN.bv_val );
	
				if ( bitStringValidate( NULL, &assertedUID ) == LDAP_SUCCESS ) {
					assertedDN.bv_len -= assertedUID.bv_len + 1;

				} else {
					BER_BVZERO( &assertedUID );
				}
			}
		}

		dnvalues[i] = assertedDN;
	}
	BER_BVZERO( &dnvalues[i] );

	rc = octetStringIndexer( use, flags, syntax, mr, prefix,
		dnvalues, keysp, ctx );

	slap_sl_free( dnvalues, ctx );
	return rc;
}

static int 
uniqueMemberFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertedValue,
	BerVarray *keysp,
	void *ctx )
{
	struct berval *asserted = (struct berval *) assertedValue;
	struct berval assertedDN = *asserted;
	struct berval assertedUID = BER_BVNULL;

	if ( !BER_BVISEMPTY( asserted ) ) {
		assertedUID.bv_val = strrchr(