schema_init.c 106 KB
Newer Older
1
2
3
/* schema_init.c - init builtin schema */
/* $OpenLDAP$ */
/*
Kurt Zeilenga's avatar
Kurt Zeilenga committed
4
 * Copyright 1998-2002 The OpenLDAP Foundation, All Rights Reserved.
5
6
7
8
9
10
 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
 */

#include "portable.h"

#include <stdio.h>
Kurt Zeilenga's avatar
Kurt Zeilenga committed
11
#include <limits.h>
12
13

#include <ac/ctype.h>
14
#include <ac/errno.h>
15
16
17
18
19
#include <ac/string.h>
#include <ac/socket.h>

#include "slap.h"
#include "ldap_pvt.h"
Pierangelo Masarati's avatar
Pierangelo Masarati committed
20
#include "lber_pvt.h"
21

22
23
#include "ldap_utf8.h"

24
25
26
27
28
29
#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)
30

31
/* recycled validatation routines */
32
#define berValidate						blobValidate
33
34

/* unimplemented pretters */
35
#define integerPretty					NULL
36
37

/* recycled matching routines */
38
#define bitStringMatch					octetStringMatch
39
40
41
#define numericStringMatch				caseIgnoreIA5Match
#define objectIdentifierMatch			caseIgnoreIA5Match
#define telephoneNumberMatch			caseIgnoreIA5Match
42
#define telephoneNumberSubstringsMatch	caseIgnoreIA5SubstringsMatch
43
44
#define generalizedTimeMatch			caseIgnoreIA5Match
#define generalizedTimeOrderingMatch	caseIgnoreIA5Match
45
#define uniqueMemberMatch				dnMatch
46
#define integerFirstComponentMatch		integerMatch
47

48
49
/* approx matching rules */
#define directoryStringApproxMatchOID	"1.3.6.1.4.1.4203.666.4.4"
Gary Williams's avatar
Gary Williams committed
50
51
52
#define directoryStringApproxMatch	approxMatch
#define directoryStringApproxIndexer	approxIndexer
#define directoryStringApproxFilter	approxFilter
53
#define IA5StringApproxMatchOID			"1.3.6.1.4.1.4203.666.4.5"
Gary Williams's avatar
Gary Williams committed
54
#define IA5StringApproxMatch			approxMatch
55
#define IA5StringApproxIndexer			approxIndexer
Gary Williams's avatar
Gary Williams committed
56
#define IA5StringApproxFilter			approxFilter
57

58
/* ordering matching rules */
59
60
#define caseIgnoreOrderingMatch			caseIgnoreMatch
#define caseExactOrderingMatch			caseExactMatch
61
#define integerOrderingMatch			integerMatch
62

63
/* unimplemented matching routines */
64
65
66
67
#define caseIgnoreListMatch				NULL
#define caseIgnoreListSubstringsMatch	NULL
#define protocolInformationMatch		NULL

Kurt Zeilenga's avatar
Kurt Zeilenga committed
68
#ifdef SLAPD_ACI_ENABLED
69
#define OpenLDAPaciMatch				NULL
Kurt Zeilenga's avatar
Kurt Zeilenga committed
70
71
#endif
#ifdef SLAPD_AUTHPASSWD
72
#define authPasswordMatch				NULL
Kurt Zeilenga's avatar
Kurt Zeilenga committed
73
#endif
74
75

/* recycled indexing/filtering routines */
76
77
#define dnIndexer				caseExactIgnoreIndexer
#define dnFilter				caseExactIgnoreFilter
78
79
#define bitStringFilter			octetStringFilter
#define bitStringIndexer		octetStringIndexer
80

81
82
83
84
85
#define telephoneNumberIndexer			caseIgnoreIA5Indexer
#define telephoneNumberFilter			caseIgnoreIA5Filter
#define telephoneNumberSubstringsIndexer	caseIgnoreIA5SubstringsIndexer
#define telephoneNumberSubstringsFilter		caseIgnoreIA5SubstringsFilter

86
87
88
89
90
91
92
93
94
95
96
97
98
99
static MatchingRule *caseExactMatchingRule;
static MatchingRule *caseExactSubstringsMatchingRule;
static MatchingRule *integerFirstComponentMatchingRule;

static const struct MatchingRulePtr {
	const char   *oid;
	MatchingRule **mr;
} mr_ptr [] = {
	/* must match OIDs below */
	{ "2.5.13.5",  &caseExactMatchingRule },
	{ "2.5.13.7",  &caseExactSubstringsMatchingRule },
	{ "2.5.13.29", &integerFirstComponentMatchingRule }
};

100

101
static char *bvcasechr( struct berval *bv, unsigned char c, ber_len_t *len )
102
{
103
	ber_len_t i;
104
105
	char lower = TOLOWER( c );
	char upper = TOUPPER( c );
106
107

	if( c == 0 ) return NULL;
108
109
110
111
112
113
	
	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];
		}
114
	}
115
116

	return NULL;
117
}
118

119
120
121
static int
octetStringMatch(
	int *matchp,
122
	slap_mask_t flags,
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
	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;
}

/* Index generation function */
141
static int octetStringIndexer(
142
143
	slap_mask_t use,
	slap_mask_t flags,
144
145
146
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
147
148
	BerVarray values,
	BerVarray *keysp )
149
150
151
{
	int i;
	size_t slen, mlen;
152
	BerVarray keys;
153
	HASH_CONTEXT   HASHcontext;
Gary Williams's avatar
Gary Williams committed
154
	unsigned char	HASHdigest[HASH_BYTES];
155
	struct berval digest;
156
157
	digest.bv_val = HASHdigest;
	digest.bv_len = sizeof(HASHdigest);
158

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

Kurt Zeilenga's avatar
Kurt Zeilenga committed
163
164
165
	/* we should have at least one value at this point */
	assert( i > 0 );

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

168
169
	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;
170

171
	for( i=0; values[i].bv_val != NULL; i++ ) {
172
		HASH_Init( &HASHcontext );
173
		if( prefix != NULL && prefix->bv_len > 0 ) {
174
			HASH_Update( &HASHcontext,
175
176
				prefix->bv_val, prefix->bv_len );
		}
177
		HASH_Update( &HASHcontext,
178
			syntax->ssyn_oid, slen );
179
		HASH_Update( &HASHcontext,
180
			mr->smr_oid, mlen );
181
		HASH_Update( &HASHcontext,
182
			values[i].bv_val, values[i].bv_len );
183
		HASH_Final( HASHdigest, &HASHcontext );
184

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

188
	keys[i].bv_val = NULL;
189
190
191
192
193
194
195

	*keysp = keys;

	return LDAP_SUCCESS;
}

/* Index generation function */
196
static int octetStringFilter(
197
198
	slap_mask_t use,
	slap_mask_t flags,
199
200
201
202
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertValue,
203
	BerVarray *keysp )
204
205
{
	size_t slen, mlen;
206
	BerVarray keys;
207
	HASH_CONTEXT   HASHcontext;
Gary Williams's avatar
Gary Williams committed
208
	unsigned char	HASHdigest[HASH_BYTES];
209
210
	struct berval *value = (struct berval *) assertValue;
	struct berval digest;
211
212
	digest.bv_val = HASHdigest;
	digest.bv_len = sizeof(HASHdigest);
213

214
215
	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;
216

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

219
	HASH_Init( &HASHcontext );
220
	if( prefix != NULL && prefix->bv_len > 0 ) {
221
		HASH_Update( &HASHcontext,
222
223
			prefix->bv_val, prefix->bv_len );
	}
224
	HASH_Update( &HASHcontext,
225
		syntax->ssyn_oid, slen );
226
	HASH_Update( &HASHcontext,
227
		mr->smr_oid, mlen );
228
	HASH_Update( &HASHcontext,
229
		value->bv_val, value->bv_len );
230
	HASH_Final( HASHdigest, &HASHcontext );
231

232
233
	ber_dupbv( keys, &digest );
	keys[1].bv_val = NULL;
234
235
236
237
238

	*keysp = keys;

	return LDAP_SUCCESS;
}
239

240
241
242
243
244
245
246
247
248
static int
inValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* any value allowed */
	return LDAP_OTHER;
}

249
static int
250
blobValidate(
251
252
253
254
	Syntax *syntax,
	struct berval *in )
{
	/* any value allowed */
255
	return LDAP_SUCCESS;
256
257
}

258
259
260
261
262
263
264
265
266
267
268
269
270
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;
	}
271

272
273
274
275
276
277
278
279
280
281
	/*
	 * 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' )
282
283
284
285
	{
		return LDAP_INVALID_SYNTAX;
	}

286
	for( i=in->bv_len-3; i>0; i-- ) {
287
288
289
290
291
292
293
294
		if( in->bv_val[i] != '0' && in->bv_val[i] != '1' ) {
			return LDAP_INVALID_SYNTAX;
		}
	}

	return LDAP_SUCCESS;
}

295
296
297
298
static int
bitStringNormalize(
	Syntax *syntax,
	struct berval *val,
299
	struct berval *normalized )
300
301
{
	/*
302
	 * A normalized bitString is has no extaneous (leading) zero bits.
303
304
	 * That is, '00010'B is normalized to '10'B
	 * However, as a special case, '0'B requires no normalization.
305
	 */
306
307
308
309
310
311
312
313
314
315
	char *p;

	/* start at the first bit */
	p = &val->bv_val[1];

	/* Find the first non-zero bit */
	while ( *p == '0' ) p++;

	if( *p == '\'' ) {
		/* no non-zero bits */
316
		ber_str2bv( "\'0\'B", sizeof("\'0\'B") - 1, 1, normalized );
317
318
319
		goto done;
	}

320
	normalized->bv_val = ch_malloc( val->bv_len + 1 );
321

322
323
	normalized->bv_val[0] = '\'';
	normalized->bv_len = 1;
324
325

	for( ; *p != '\0'; p++ ) {
326
		normalized->bv_val[normalized->bv_len++] = *p;
327
328
	}

329
	normalized->bv_val[normalized->bv_len] = '\0';
330
331
332
333
334

done:
	return LDAP_SUCCESS;
}

335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
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;
}

static int
nameUIDNormalize(
	Syntax *syntax,
	struct berval *val,
	struct berval *normalized )
{
	struct berval out;
	int rc;

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

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

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

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

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

			rc = bitStringNormalize( syntax, &uidin, &uidout );

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

#ifdef USE_DN_NORMALIZE
		rc = dnNormalize2( NULL, &out, normalized );
#else
		rc = dnPretty2( NULL, &out, normalized );
#endif

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

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

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

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

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

		free( out.bv_val );
	}

	return LDAP_SUCCESS;
}

448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
/*
 * 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,
479
	slap_mask_t flags,
480
481
482
483
484
485
486
487
488
489
490
	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;
}

491
492
493
494
495
496
497
498
499
static int
UTF8StringValidate(
	Syntax *syntax,
	struct berval *in )
{
	ber_len_t count;
	int len;
	unsigned char *u = in->bv_val;

500
501
	if( !in->bv_len ) return LDAP_INVALID_SYNTAX;

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

Kurt Zeilenga's avatar
Kurt Zeilenga committed
506
507
508
		/* very basic checks */
		switch( len ) {
			case 6:
509
				if( (u[5] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
510
511
512
					return LDAP_INVALID_SYNTAX;
				}
			case 5:
513
				if( (u[4] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
514
515
516
					return LDAP_INVALID_SYNTAX;
				}
			case 4:
517
				if( (u[3] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
518
519
520
					return LDAP_INVALID_SYNTAX;
				}
			case 3:
521
				if( (u[2] & 0xC0 )!= 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
522
523
524
					return LDAP_INVALID_SYNTAX;
				}
			case 2:
525
				if( (u[1] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
526
527
528
					return LDAP_INVALID_SYNTAX;
				}
			case 1:
529
				/* CHARLEN already validated it */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
530
531
532
533
				break;
			default:
				return LDAP_INVALID_SYNTAX;
		}
534
535
536

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

540
	if( count != 0 ) return LDAP_INVALID_SYNTAX;
541

542
	return LDAP_SUCCESS;
543
544
545
546
547
548
}

static int
UTF8StringNormalize(
	Syntax *syntax,
	struct berval *val,
549
	struct berval *normalized )
550
{
551
	char *p, *q, *s, *e;
552
	int len = 0;
553

554
	p = val->bv_val;
555

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

560
561
562
	normalized->bv_len = val->bv_len - (p - val->bv_val);
	ber_mem2bv( p, normalized->bv_len, 1, normalized );
	e = normalized->bv_val + normalized->bv_len;
563
564
565
566

	assert( normalized->bv_val );

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

569
	while ( p < e ) {
570
571
572
573
574
		q += len;
		if ( ASCII_SPACE( *p ) ) {
			s = q - len;
			len = 1;
			*q = *p++;
575

576
			/* Ignore the extra whitespace */
577
578
			while ( ASCII_SPACE( *p ) ) {
				p++;
579
			}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
580
		} else {
581
582
583
			len = LDAP_UTF8_COPY(q,p);
			s=NULL;
			p+=len;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
584
		}
585
586
	}

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

590
	/* cannot start with a space */
591
	assert( !ASCII_SPACE(normalized->bv_val[0]) );
592
593
594
595
596
597
598
599

	/*
	 * 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 ) {
Howard Chu's avatar
Howard Chu committed
600
		len = q - s;
601
		q = s;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
602
	}
603

604
	/* cannot end with a space */
605
606
607
	assert( !ASCII_SPACE( *q ) );

	q += len;
608
609
610
611

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

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

614
	return LDAP_SUCCESS;
615
616
}

617
/* Returns Unicode canonically normalized copy of a substring assertion
618
 * Skipping attribute description */
619
static SubstringsAssertion *
620
621
UTF8SubstringsassertionNormalize(
	SubstringsAssertion *sa,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
622
	unsigned casefold )
623
624
625
626
627
628
629
630
631
{
	SubstringsAssertion *nsa;
	int i;

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

632
	if( sa->sa_initial.bv_val != NULL ) {
633
		UTF8bvnormalize( &sa->sa_initial, &nsa->sa_initial, casefold );
634
		if( nsa->sa_initial.bv_val == NULL ) {
635
636
637
638
639
			goto err;
		}
	}

	if( sa->sa_any != NULL ) {
640
		for( i=0; sa->sa_any[i].bv_val != NULL; i++ ) {
641
642
			/* empty */
		}
643
644
		nsa->sa_any = (struct berval *)ch_malloc( (i + 1) * sizeof(struct berval) );
		for( i=0; sa->sa_any[i].bv_val != NULL; i++ ) {
645
646
			UTF8bvnormalize( &sa->sa_any[i], &nsa->sa_any[i], 
					casefold );
647
			if( nsa->sa_any[i].bv_val == NULL ) {
648
649
650
				goto err;
			}
		}
651
		nsa->sa_any[i].bv_val = NULL;
652
653
	}

654
	if( sa->sa_final.bv_val != NULL ) {
655
		UTF8bvnormalize( &sa->sa_final, &nsa->sa_final, casefold );
656
		if( nsa->sa_final.bv_val == NULL ) {
657
658
659
660
661
662
663
			goto err;
		}
	}

	return nsa;

err:
Howard Chu's avatar
Howard Chu committed
664
	if ( nsa->sa_final.bv_val ) free( nsa->sa_final.bv_val );
665
	if ( nsa->sa_any )ber_bvarray_free( nsa->sa_any );
Howard Chu's avatar
Howard Chu committed
666
	if ( nsa->sa_initial.bv_val ) free( nsa->sa_initial.bv_val );
667
668
669
670
	ch_free( nsa );
	return NULL;
}

671
#ifndef SLAPD_APPROX_OLDSINGLESTRING
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689

#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 )
{
690
691
	struct berval *nval, *assertv;
	char *val, **values, **words, *c;
692
693
	int i, count, len, nextchunk=0, nextavail=0;

694
	/* Yes, this is necessary */
695
	nval = UTF8bvnormalize( value, NULL, LDAP_UTF8_APPROX );
696
	if( nval == NULL ) {
697
698
699
700
701
		*matchp = 1;
		return LDAP_SUCCESS;
	}

	/* Yes, this is necessary */
702
	assertv = UTF8bvnormalize( ((struct berval *)assertedValue), NULL, LDAP_UTF8_APPROX );
703
	if( assertv == NULL ) {
704
		ber_bvfree( nval );
705
706
707
		*matchp = 1;
		return LDAP_SUCCESS;
	}
708
709

	/* Isolate how many words there are */
710
	for ( c = nval->bv_val, count = 1; *c; c++ ) {
711
712
713
714
715
716
717
718
719
		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 *) );
720
	for ( c = nval->bv_val, i = 0;  i < count; i++, c += strlen(c) + 1 ) {
721
722
723
724
		words[i] = c;
		values[i] = phonetic(c);
	}

725
	/* Work through the asserted value's words, to see if at least some
726
727
	   of the words are there, in the same order. */
	len = 0;
728
729
	while ( (ber_len_t) nextchunk < assertv->bv_len ) {
		len = strcspn( assertv->bv_val + nextchunk, SLAPD_APPROX_DELIMITER);
730
731
732
733
		if( len == 0 ) {
			nextchunk++;
			continue;
		}
734
#if defined(SLAPD_APPROX_INITIALS)
735
		else if( len == 1 ) {
736
737
			/* Single letter words need to at least match one word's initial */
			for( i=nextavail; i<count; i++ )
738
				if( !strncasecmp( assertv->bv_val + nextchunk, words[i], 1 )) {
739
					nextavail=i+1;
740
					break;
741
				}
742
743
		}
#endif
744
		else {
745
			/* Isolate the next word in the asserted value and phonetic it */
746
747
			assertv->bv_val[nextchunk+len] = '\0';
			val = phonetic( assertv->bv_val + nextchunk );
748
749
750
751
752
753
754
755

			/* 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;
				}
			}
756
			ch_free( val );
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
		}

		/* 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 */
778
	ber_bvfree( assertv );
779
780
781
782
783
	for( i=0; i<count; i++ ) {
		ch_free( values[i] );
	}
	ch_free( values );
	ch_free( words );
784
	ber_bvfree( nval );
785
786
787
788

	return LDAP_SUCCESS;
}

789
static int 
790
791
792
793
794
795
approxIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
796
797
	BerVarray values,
	BerVarray *keysp )
798
{
799
	char *c;
800
	int i,j, len, wordcount, keycount=0;
801
	struct berval *newkeys;
802
	BerVarray keys=NULL;
803

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

810
		/* Isolate how many words there are. There will be a key for each */
811
		for( wordcount = 0, c = val.bv_val; *c; c++) {
812
813
814
815
816
817
818
819
			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 */
820
821
		newkeys = (struct berval *)ch_malloc( (keycount + wordcount + 1) 
			* sizeof(struct berval) );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
822
		AC_MEMCPY( newkeys, keys, keycount * sizeof(struct berval) );
823
824
825
826
		if( keys ) ch_free( keys );
		keys = newkeys;

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

835
		ber_memfree( val.bv_val );
836
	}
837
	keys[keycount].bv_val = NULL;
838
839
840
841
842
	*keysp = keys;

	return LDAP_SUCCESS;
}

843
static int 
844
845
846
847
848
849
850
approxFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertValue,
851
	BerVarray *keysp )
852
{
853
	char *c;
854
	int i, count, len;
855
	struct berval *val;
856
	BerVarray keys;
857

858
	/* Yes, this is necessary */
859
860
	val = UTF8bvnormalize( ((struct berval *)assertValue), NULL, LDAP_UTF8_APPROX );
	if( val == NULL || val->bv_val == NULL ) {
861
862
		keys = (struct berval *)ch_malloc( sizeof(struct berval) );
		keys[0].bv_val = NULL;
863
		*keysp = keys;
864
		ber_bvfree( val );
865
866
867
		return LDAP_SUCCESS;
	}

868
	/* Isolate how many words there are. There will be a key for each */
869
	for( count = 0,c = val->bv_val; *c; c++) {
870
871
872
873
874
875
876
877
		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 */
878
	keys = (struct berval *)ch_malloc( (count + 1) * sizeof(struct berval) );
879
880

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

888
	ber_bvfree( val );
889

890
	keys[count].bv_val = NULL;
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
	*keysp = keys;

	return LDAP_SUCCESS;
}


#else
/* No other form of Approximate Matching is defined */

static int
approxMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	char *vapprox, *avapprox;
910
	char *s, *t;
911

912
	/* Yes, this is necessary */
913
	s = UTF8normalize( value, UTF8_NOCASEFOLD );
914
915
916
917
918
919
	if( s == NULL ) {
		*matchp = 1;
		return LDAP_SUCCESS;
	}

	/* Yes, this is necessary */
920
	t = UTF8normalize( ((struct berval *)assertedValue),
921
922
923
924
925
926
927
928
929
930
931
932
			   UTF8_NOCASEFOLD );
	if( t == NULL ) {
		free( s );
		*matchp = -1;
		return LDAP_SUCCESS;
	}

	vapprox = phonetic( strip8bitChars( s ) );
	avapprox = phonetic( strip8bitChars( t ) );

	free( s );
	free( t );
933
934
935
936
937
938
939
940
941

	*matchp = strcmp( vapprox, avapprox );

	ch_free( vapprox );
	ch_free( avapprox );

	return LDAP_SUCCESS;
}

942
static int 
943
944
945
946
947
948
approxIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
949
950
	BerVarray values,
	BerVarray *keysp )
951
952
{
	int i;
953
	BerVarray *keys;
954
	char *s;
955

956
	for( i=0; values[i].bv_val != NULL; i++ ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
957
		/* empty - just count them */
958
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
959
960

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

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

	/* Copy each value and run it through phonetic() */
966
	for( i=0; values[i].bv_val != NULL; i++ ) {
967
		/* Yes, this is necessary */
968
		s = UTF8normalize( &values[i], UTF8_NOCASEFOLD );
969
970

		/* strip 8-bit chars and run through phonetic() */
971
		ber_str2bv( phonetic( strip8bitChars( s ) ), 0, 0, &keys[i] );
972
		free( s );
973
	}
974
	keys[i].bv_val = NULL;
975
976
977
978
979
980

	*keysp = keys;
	return LDAP_SUCCESS;
}


981
static int 
982
983
984
985
986
987
988
approxFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertValue,
989
	BerVarray *keysp )
990
{
991
	BerVarray keys;
992
	char *s;
993

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

996
	/* Yes, this is necessary */
997
	s = UTF8normalize( ((struct berval *)assertValue),
998
999
1000
1001
1002
1003
1004
1005
1006
			     UTF8_NOCASEFOLD );
	if( s == NULL ) {
		keys[0] = NULL;
	} else {
		/* strip 8-bit chars and run through phonetic() */
		keys[0] = ber_bvstr( phonetic( strip8bitChars( s ) ) );
		free( s );
		keys[1] = NULL;
	}
1007
1008
1009
1010
1011
1012
1013

	*keysp = keys;
	return LDAP_SUCCESS;
}
#endif


1014
static int
1015
caseExactMatch(
1016
	int *matchp,
1017
	slap_mask_t flags,
1018
1019
1020
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
1021
	void *assertedValue )
1022
{
1023
1024
1025
	*matchp = UTF8bvnormcmp( value,
		(struct berval *) assertedValue,
		LDAP_UTF8_NOCASEFOLD );
1026
	return LDAP_SUCCESS;
1027
1028
}

1029
static int
1030
caseExactIgnoreSubstringsMatch(
1031
	int *matchp,
1032
	slap_mask_t flags,
1033
1034
1035
1036
1037
1038
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	int match = 0;
Pierangelo Masarati's avatar
Pierangelo Masarati committed
1039
	SubstringsAssertion *sub = NULL;
1040
	struct berval left = { 0, NULL };
1041
1042
	int i;
	ber_len_t inlen=0;
1043
	char *nav = NULL;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1044
	unsigned casefold;
1045

1046
	casefold = ( mr != caseExactSubstringsMatchingRule )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1047
		? LDAP_UTF8_CASEFOLD : LDAP_UTF8_NOCASEFOLD;
1048

1049
	if ( UTF8bvnormalize( value, &left, casefold ) == NULL ) {
1050
1051
1052
		match = 1;
		goto done;
	}
1053
	nav = left.bv_val;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1054

1055
	sub = UTF8SubstringsassertionNormalize( assertedValue, casefold );
1056
1057
1058
1059
	if( sub == NULL ) {
		match = -1;
		goto done;
	}
1060

1061
	/* Add up asserted input length */
1062
1063
	if( sub->sa_initial.bv_val ) {
		inlen += sub