schema_init.c 105 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

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

57
58
59
60
/* orderring matching rules */
#define caseIgnoreOrderingMatch			caseIgnoreMatch
#define caseExactOrderingMatch			caseExactMatch

61
/* unimplemented matching routines */
62
63
64
65
66
#define caseIgnoreListMatch				NULL
#define caseIgnoreListSubstringsMatch	NULL
#define protocolInformationMatch		NULL
#define integerFirstComponentMatch		NULL

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

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

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

85
86
87
88
/* must match OIDs below */
#define caseExactMatchOID			"2.5.13.5"
#define caseExactSubstringsMatchOID		"2.5.13.7"

89
static char *bvcasechr( struct berval *bv, int c, ber_len_t *len )
90
{
91
92
93
	ber_len_t i;
	int lower = TOLOWER( c );
	int upper = TOUPPER( c );
94
95

	if( c == 0 ) return NULL;
96
97
98
99
100
101
	
	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];
		}
102
	}
103
104

	return NULL;
105
}
106

107
108
109
static int
octetStringMatch(
	int *matchp,
110
	slap_mask_t flags,
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
	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 */
129
static int octetStringIndexer(
130
131
	slap_mask_t use,
	slap_mask_t flags,
132
133
134
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
135
136
	BerVarray values,
	BerVarray *keysp )
137
138
139
{
	int i;
	size_t slen, mlen;
140
	BerVarray keys;
141
	HASH_CONTEXT   HASHcontext;
Gary Williams's avatar
Gary Williams committed
142
	unsigned char	HASHdigest[HASH_BYTES];
143
	struct berval digest;
144
145
	digest.bv_val = HASHdigest;
	digest.bv_len = sizeof(HASHdigest);
146

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

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

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

156
157
	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;
158

159
	for( i=0; values[i].bv_val != NULL; i++ ) {
160
		HASH_Init( &HASHcontext );
161
		if( prefix != NULL && prefix->bv_len > 0 ) {
162
			HASH_Update( &HASHcontext,
163
164
				prefix->bv_val, prefix->bv_len );
		}
165
		HASH_Update( &HASHcontext,
166
			syntax->ssyn_oid, slen );
167
		HASH_Update( &HASHcontext,
168
			mr->smr_oid, mlen );
169
		HASH_Update( &HASHcontext,
170
			values[i].bv_val, values[i].bv_len );
171
		HASH_Final( HASHdigest, &HASHcontext );
172

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

176
	keys[i].bv_val = NULL;
177
178
179
180
181
182
183

	*keysp = keys;

	return LDAP_SUCCESS;
}

/* Index generation function */
184
static int octetStringFilter(
185
186
	slap_mask_t use,
	slap_mask_t flags,
187
188
189
190
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertValue,
191
	BerVarray *keysp )
192
193
{
	size_t slen, mlen;
194
	BerVarray keys;
195
	HASH_CONTEXT   HASHcontext;
Gary Williams's avatar
Gary Williams committed
196
	unsigned char	HASHdigest[HASH_BYTES];
197
198
	struct berval *value = (struct berval *) assertValue;
	struct berval digest;
199
200
	digest.bv_val = HASHdigest;
	digest.bv_len = sizeof(HASHdigest);
201

202
203
	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;
204

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

207
	HASH_Init( &HASHcontext );
208
	if( prefix != NULL && prefix->bv_len > 0 ) {
209
		HASH_Update( &HASHcontext,
210
211
			prefix->bv_val, prefix->bv_len );
	}
212
	HASH_Update( &HASHcontext,
213
		syntax->ssyn_oid, slen );
214
	HASH_Update( &HASHcontext,
215
		mr->smr_oid, mlen );
216
	HASH_Update( &HASHcontext,
217
		value->bv_val, value->bv_len );
218
	HASH_Final( HASHdigest, &HASHcontext );
219

220
221
	ber_dupbv( keys, &digest );
	keys[1].bv_val = NULL;
222
223
224
225
226

	*keysp = keys;

	return LDAP_SUCCESS;
}
227

228
229
230
231
232
233
static int
nameUIDValidate(
	Syntax *syntax,
	struct berval *in )
{
	int rc;
234
	struct berval dn;
235
236
237

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

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

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

247
248
		for(i=dn.bv_len-3; i>1; i--) {
			if( dn.bv_val[i] != '0' &&	dn.bv_val[i] != '1' ) {
249
250
251
				break;
			}
		}
252
253
254
		if( dn.bv_val[i] != '\'' ||
		    dn.bv_val[i-1] != '#' ) {
			ber_memfree( dn.bv_val );
255
256
257
			return LDAP_INVALID_SYNTAX;
		}

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

263
	rc = dnValidate( NULL, &dn );
264

265
	ber_memfree( &dn );
266
267
268
269
270
271
272
	return rc;
}

static int
nameUIDNormalize(
	Syntax *syntax,
	struct berval *val,
273
	struct berval *normalized )
274
{
275
	struct berval out;
Howard Chu's avatar
Howard Chu committed
276
	int rc;
277

278
279
	ber_dupbv( &out, val );
	if( out.bv_len != 0 ) {
280
281
282
283
		ber_len_t dnlen;
		char *uid = NULL;
		ber_len_t uidlen = 0;

284
		if( out.bv_val[out.bv_len-1] == '\'' ) {
285
			/* assume presence of optional UID */
286
			uid = strrchr( out.bv_val, '#' );
287
288

			if( uid == NULL ) {
289
				free( out.bv_val );
290
291
292
				return LDAP_INVALID_SYNTAX;
			}

293
			uidlen = out.bv_len - (uid - out.bv_val);
294
295
			/* temporarily trim the UID */
			*uid = '\0';
296
			out.bv_len -= uidlen;
297
298
299
		}

#ifdef USE_DN_NORMALIZE
300
		rc = dnNormalize2( NULL, &out, normalized );
301
#else
302
		rc = dnPretty2( NULL, &out, normalized );
303
304
#endif

Howard Chu's avatar
Howard Chu committed
305
		if( rc != LDAP_SUCCESS ) {
306
			free( out.bv_val );
307
308
309
			return LDAP_INVALID_SYNTAX;
		}

310
		dnlen = normalized->bv_len;
311
312

		if( uidlen ) {
313
314
			struct berval b2;
			b2.bv_val = ch_malloc(dnlen + uidlen + 1);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
315
			AC_MEMCPY( b2.bv_val, normalized->bv_val, dnlen );
Howard Chu's avatar
Howard Chu committed
316

317
318
319
			/* restore the separator */
			*uid = '#';
			/* shift the UID */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
320
			AC_MEMCPY( normalized->bv_val+dnlen, uid, uidlen );
321
322
323
			b2.bv_len = dnlen + uidlen;
			normalized->bv_val[dnlen+uidlen] = '\0';
			free(normalized->bv_val);
Howard Chu's avatar
Howard Chu committed
324
			*normalized = b2;
325
		}
326
		free( out.bv_val );
327
328
329
330
331
	}

	return LDAP_SUCCESS;
}

332
333
334
335
336
337
338
339
340
static int
inValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* any value allowed */
	return LDAP_OTHER;
}

341
static int
342
blobValidate(
343
344
345
346
	Syntax *syntax,
	struct berval *in )
{
	/* any value allowed */
347
	return LDAP_SUCCESS;
348
349
}

350
351
352
353
354
355
356
357
358
359
360
361
362
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;
	}
363

364
365
366
367
368
369
370
371
372
373
	/*
	 * 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' )
374
375
376
377
	{
		return LDAP_INVALID_SYNTAX;
	}

378
	for( i=in->bv_len-3; i>0; i-- ) {
379
380
381
382
383
384
385
386
		if( in->bv_val[i] != '0' && in->bv_val[i] != '1' ) {
			return LDAP_INVALID_SYNTAX;
		}
	}

	return LDAP_SUCCESS;
}

387
388
389
390
static int
bitStringNormalize(
	Syntax *syntax,
	struct berval *val,
391
	struct berval *normalized )
392
393
{
	/*
394
	 * A normalized bitString is has no extaneous (leading) zero bits.
395
396
	 * That is, '00010'B is normalized to '10'B
	 * However, as a special case, '0'B requires no normalization.
397
	 */
398
399
400
401
402
403
404
405
406
407
	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 */
408
		ber_str2bv( "\'0\'B", sizeof("\'0\'B") - 1, 1, normalized );
409
410
411
		goto done;
	}

412
	normalized->bv_val = ch_malloc( val->bv_len + 1 );
413

414
415
	normalized->bv_val[0] = '\'';
	normalized->bv_len = 1;
416
417

	for( ; *p != '\0'; p++ ) {
418
		normalized->bv_val[normalized->bv_len++] = *p;
419
420
	}

421
	normalized->bv_val[normalized->bv_len] = '\0';
422
423
424
425
426

done:
	return LDAP_SUCCESS;
}

427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
/*
 * 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,
458
	slap_mask_t flags,
459
460
461
462
463
464
465
466
467
468
469
	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;
}

470
471
472
473
474
475
476
477
478
static int
UTF8StringValidate(
	Syntax *syntax,
	struct berval *in )
{
	ber_len_t count;
	int len;
	unsigned char *u = in->bv_val;

479
480
	if( !in->bv_len ) return LDAP_INVALID_SYNTAX;

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

Kurt Zeilenga's avatar
Kurt Zeilenga committed
485
486
487
		/* very basic checks */
		switch( len ) {
			case 6:
488
				if( (u[5] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
489
490
491
					return LDAP_INVALID_SYNTAX;
				}
			case 5:
492
				if( (u[4] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
493
494
495
					return LDAP_INVALID_SYNTAX;
				}
			case 4:
496
				if( (u[3] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
497
498
499
					return LDAP_INVALID_SYNTAX;
				}
			case 3:
500
				if( (u[2] & 0xC0 )!= 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
501
502
503
					return LDAP_INVALID_SYNTAX;
				}
			case 2:
504
				if( (u[1] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
505
506
507
					return LDAP_INVALID_SYNTAX;
				}
			case 1:
508
				/* CHARLEN already validated it */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
509
510
511
512
				break;
			default:
				return LDAP_INVALID_SYNTAX;
		}
513
514
515

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

519
	if( count != 0 ) return LDAP_INVALID_SYNTAX;
520

521
	return LDAP_SUCCESS;
522
523
524
525
526
527
}

static int
UTF8StringNormalize(
	Syntax *syntax,
	struct berval *val,
528
	struct berval *normalized )
529
{
530
	char *p, *q, *s, *e;
531
	int len = 0;
532

533
	p = val->bv_val;
534

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

539
540
	ber_mem2bv( p, val->bv_len - (p - val->bv_val), 1, normalized );
	e = normalized->bv_val + val->bv_len - (p - val->bv_val);
541
542
543
544

	assert( normalized->bv_val );

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

547
	while ( p < e ) {
548
549
550
551
552
		q += len;
		if ( ASCII_SPACE( *p ) ) {
			s = q - len;
			len = 1;
			*q = *p++;
553

554
			/* Ignore the extra whitespace */
555
556
			while ( ASCII_SPACE( *p ) ) {
				p++;
557
			}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
558
		} else {
559
560
561
			len = LDAP_UTF8_COPY(q,p);
			s=NULL;
			p+=len;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
562
		}
563
564
	}

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

568
	/* cannot start with a space */
569
	assert( !ASCII_SPACE(normalized->bv_val[0]) );
570
571
572
573
574
575
576
577

	/*
	 * 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
578
		len = q - s;
579
		q = s;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
580
	}
581

582
	/* cannot end with a space */
583
584
585
	assert( !ASCII_SPACE( *q ) );

	q += len;
586
587
588
589

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

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

592
	return LDAP_SUCCESS;
593
594
}

595
/* Returns Unicode canonically normalized copy of a substring assertion
596
 * Skipping attribute description */
597
static SubstringsAssertion *
598
599
UTF8SubstringsassertionNormalize(
	SubstringsAssertion *sa,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
600
	unsigned casefold )
601
602
603
604
605
606
607
608
609
{
	SubstringsAssertion *nsa;
	int i;

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

610
	if( sa->sa_initial.bv_val != NULL ) {
611
		UTF8bvnormalize( &sa->sa_initial, &nsa->sa_initial, casefold );
612
		if( nsa->sa_initial.bv_val == NULL ) {
613
614
615
616
617
			goto err;
		}
	}

	if( sa->sa_any != NULL ) {
618
		for( i=0; sa->sa_any[i].bv_val != NULL; i++ ) {
619
620
			/* empty */
		}
621
622
		nsa->sa_any = (struct berval *)ch_malloc( (i + 1) * sizeof(struct berval) );
		for( i=0; sa->sa_any[i].bv_val != NULL; i++ ) {
623
624
			UTF8bvnormalize( &sa->sa_any[i], &nsa->sa_any[i], 
					casefold );
625
			if( nsa->sa_any[i].bv_val == NULL ) {
626
627
628
				goto err;
			}
		}
629
		nsa->sa_any[i].bv_val = NULL;
630
631
	}

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

	return nsa;

err:
Howard Chu's avatar
Howard Chu committed
642
	if ( nsa->sa_final.bv_val ) free( nsa->sa_final.bv_val );
643
	if ( nsa->sa_any )ber_bvarray_free( nsa->sa_any );
Howard Chu's avatar
Howard Chu committed
644
	if ( nsa->sa_initial.bv_val ) free( nsa->sa_initial.bv_val );
645
646
647
648
	ch_free( nsa );
	return NULL;
}

649
/* Strip characters with the 8th bit set */
650
static char *
651
652
653
654
655
656
657
658
659
660
661
662
663
664
strip8bitChars(
	char *in )      
{
	char *p = in, *q;
  
	if( in == NULL ) {
		return NULL;
	}
	while( *p ) {
		if( *p & 0x80 ) {
			q = p;
			while( *++q & 0x80 ) {
				/* empty */
			}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
665
			p = AC_MEMCPY(p, q, strlen(q) + 1);
666
667
668
669
670
671
672
		} else {
			p++;
		}
	}
	return in;
}

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

#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 )
{
692
	char *val, *nval, *assertv, **values, **words, *c;
693
	int i, count, len, nextchunk=0, nextavail=0;
694
	size_t avlen;
695

696
	/* Yes, this is necessary */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
697
	nval = UTF8normalize( value, LDAP_UTF8_NOCASEFOLD );
698
	if( nval == NULL ) {
699
700
701
		*matchp = 1;
		return LDAP_SUCCESS;
	}
702
	strip8bitChars( nval );
703
704

	/* Yes, this is necessary */
705
	assertv = UTF8normalize( ((struct berval *)assertedValue),
Kurt Zeilenga's avatar
Kurt Zeilenga committed
706
		LDAP_UTF8_NOCASEFOLD );
707
	if( assertv == NULL ) {
708
		ch_free( nval );
709
710
711
712
713
		*matchp = 1;
		return LDAP_SUCCESS;
	}
	strip8bitChars( assertv );
	avlen = strlen( assertv );
714
715

	/* Isolate how many words there are */
716
	for( c=nval,count=1; *c; c++ ) {
717
718
719
720
721
722
723
724
725
		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 *) );
726
	for( c=nval,i=0;  i<count;  i++,c+=strlen(c)+1 ) {
727
728
729
730
		words[i] = c;
		values[i] = phonetic(c);
	}

731
	/* Work through the asserted value's words, to see if at least some
732
733
	   of the words are there, in the same order. */
	len = 0;
734
	while ( (size_t) nextchunk < avlen ) {
735
		len = strcspn( assertv + nextchunk, SLAPD_APPROX_DELIMITER);
736
737
738
739
		if( len == 0 ) {
			nextchunk++;
			continue;
		}
740
#if defined(SLAPD_APPROX_INITIALS)
741
		else if( len == 1 ) {
742
743
			/* Single letter words need to at least match one word's initial */
			for( i=nextavail; i<count; i++ )
744
745
				if( !strncasecmp( assertv+nextchunk, words[i], 1 )) {
					nextavail=i+1;
746
					break;
747
				}
748
749
		}
#endif
750
		else {
751
752
753
754
755
756
757
758
759
760
761
			/* Isolate the next word in the asserted value and phonetic it */
			assertv[nextchunk+len] = '\0';
			val = phonetic( assertv + 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;
				}
			}
762
			ch_free( val );
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
		}

		/* 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 */
784
	free( assertv );
785
786
787
788
789
	for( i=0; i<count; i++ ) {
		ch_free( values[i] );
	}
	ch_free( values );
	ch_free( words );
790
	ch_free( nval );
791
792
793
794

	return LDAP_SUCCESS;
}

795
static int 
796
797
798
799
800
801
approxIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
802
803
	BerVarray values,
	BerVarray *keysp )
804
805
806
{
	char *val, *c;
	int i,j, len, wordcount, keycount=0;
807
	struct berval *newkeys;
808
	BerVarray keys=NULL;
809

810
	for( j=0; values[j].bv_val != NULL; j++ ) {
811
		/* Yes, this is necessary */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
812
		val = UTF8normalize( &values[j], LDAP_UTF8_NOCASEFOLD );
813
814
		strip8bitChars( val );

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

		/* Get a phonetic copy of each word */
Gary Williams's avatar
Gary Williams committed
832
		for( c=val,i=0;	 i<wordcount;  c+=len+1	 ) {
833
834
			len = strlen( c );
			if( len < SLAPD_APPROX_WORDLEN ) continue;
835
			ber_str2bv( phonetic( c ), 0, 0, &keys[keycount] );
836
837
838
839
			keycount++;
			i++;
		}

840
		free( val );
841
	}
842
	keys[keycount].bv_val = NULL;
843
844
845
846
847
	*keysp = keys;

	return LDAP_SUCCESS;
}

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

862
	/* Yes, this is necessary */
863
	val = UTF8normalize( ((struct berval *)assertValue),
Kurt Zeilenga's avatar
Kurt Zeilenga committed
864
		LDAP_UTF8_NOCASEFOLD );
865
	if( val == NULL ) {
866
867
		keys = (struct berval *)ch_malloc( sizeof(struct berval) );
		keys[0].bv_val = NULL;
868
869
870
871
872
		*keysp = keys;
		return LDAP_SUCCESS;
	}
	strip8bitChars( val );

873
874
875
876
877
878
879
880
881
882
	/* Isolate how many words there are. There will be a key for each */
	for( count=0,c=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 */
883
	keys = (struct berval *)ch_malloc( (count + 1) * sizeof(struct berval) );
884
885

	/* Get a phonetic copy of each word */
Gary Williams's avatar
Gary Williams committed
886
	for( c=val,i=0;	 i<count; c+=len+1 ) {
887
888
		len = strlen(c);
		if( len < SLAPD_APPROX_WORDLEN ) continue;
889
		ber_str2bv( phonetic( c ), 0, 0, &keys[i] );
890
891
892
		i++;
	}

893
	free( val );
894

895
	keys[count].bv_val = NULL;
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
	*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;
915
	char *s, *t;
916

917
	/* Yes, this is necessary */
918
	s = UTF8normalize( value, UTF8_NOCASEFOLD );
919
920
921
922
923
924
	if( s == NULL ) {
		*matchp = 1;
		return LDAP_SUCCESS;
	}

	/* Yes, this is necessary */
925
	t = UTF8normalize( ((struct berval *)assertedValue),
926
927
928
929
930
931
932
933
934
935
936
937
			   UTF8_NOCASEFOLD );
	if( t == NULL ) {
		free( s );
		*matchp = -1;
		return LDAP_SUCCESS;
	}

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

	free( s );
	free( t );
938
939
940
941
942
943
944
945
946

	*matchp = strcmp( vapprox, avapprox );

	ch_free( vapprox );
	ch_free( avapprox );

	return LDAP_SUCCESS;
}

947
static int 
948
949
950
951
952
953
approxIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
954
955
	BerVarray values,
	BerVarray *keysp )
956
957
{
	int i;
958
	BerVarray *keys;
959
	char *s;
960

961
	for( i=0; values[i].bv_val != NULL; i++ ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
962
		/* empty - just count them */
963
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
964
965

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

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

	/* Copy each value and run it through phonetic() */
971
	for( i=0; values[i].bv_val != NULL; i++ ) {
972
		/* Yes, this is necessary */
973
		s = UTF8normalize( &values[i], UTF8_NOCASEFOLD );
974
975

		/* strip 8-bit chars and run through phonetic() */
976
		ber_str2bv( phonetic( strip8bitChars( s ) ), 0, 0, &keys[i] );
977
		free( s );
978
	}
979
	keys[i].bv_val = NULL;
980
981
982
983
984
985

	*keysp = keys;
	return LDAP_SUCCESS;
}


986
static int 
987
988
989
990
991
992
993
approxFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertValue,
994
	BerVarray *keysp )
995
{
996
	BerVarray keys;
997
	char *s;
998

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

1001
	/* Yes, this is necessary */
1002
	s = UTF8normalize( ((struct berval *)assertValue),
1003
1004
1005
1006
1007
1008
1009