schema_init.c 104 KB
Newer Older
1
2
3
/* schema_init.c - init builtin schema */
/* $OpenLDAP$ */
/*
Kurt Zeilenga's avatar
Kurt Zeilenga committed
4
 * Copyright 1998-2000 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"
20

21
22
#include "ldap_utf8.h"

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

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

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

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

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

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

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

#define OpenLDAPaciMatch				NULL
#define authPasswordMatch				NULL
68
69

/* recycled indexing/filtering routines */
70
71
#define dnIndexer				caseExactIgnoreIndexer
#define dnFilter				caseExactIgnoreFilter
72
73
#define bitStringFilter			octetStringFilter
#define bitStringIndexer		octetStringIndexer
74

75
76
77
78
79
#define telephoneNumberIndexer			caseIgnoreIA5Indexer
#define telephoneNumberFilter			caseIgnoreIA5Filter
#define telephoneNumberSubstringsIndexer	caseIgnoreIA5SubstringsIndexer
#define telephoneNumberSubstringsFilter		caseIgnoreIA5SubstringsFilter

80
81
82
83
/* must match OIDs below */
#define caseExactMatchOID			"2.5.13.5"
#define caseExactSubstringsMatchOID		"2.5.13.7"

84
85
86
87
static char *strcasechr( const char *str, int c )
{
	char *lower = strchr( str, TOLOWER(c) );
	char *upper = strchr( str, TOUPPER(c) );
88

89
90
91
92
93
94
95
96
	if( lower && upper ) {
		return lower < upper ? lower : upper;
	} else if ( lower ) {
		return lower;
	} else {
		return upper;
	}
}
97

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

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

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

145
146
147
148
149
150
	keys = ch_malloc( sizeof( struct berval * ) * (i+1) );

	slen = strlen( syntax->ssyn_oid );
	mlen = strlen( mr->smr_oid );

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

		keys[i] = ber_bvdup( &digest );
	}

	keys[i] = NULL;

	*keysp = keys;

	return LDAP_SUCCESS;
}

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

	slen = strlen( syntax->ssyn_oid );
	mlen = strlen( mr->smr_oid );

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

198
	HASH_Init( &HASHcontext );
199
	if( prefix != NULL && prefix->bv_len > 0 ) {
200
		HASH_Update( &HASHcontext,
201
202
			prefix->bv_val, prefix->bv_len );
	}
203
	HASH_Update( &HASHcontext,
204
		syntax->ssyn_oid, slen );
205
	HASH_Update( &HASHcontext,
206
		mr->smr_oid, mlen );
207
	HASH_Update( &HASHcontext,
208
		value->bv_val, value->bv_len );
209
	HASH_Final( HASHdigest, &HASHcontext );
210
211
212
213
214
215
216
217

	keys[0] = ber_bvdup( &digest );
	keys[1] = NULL;

	*keysp = keys;

	return LDAP_SUCCESS;
}
218

219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
static int
nameUIDValidate(
	Syntax *syntax,
	struct berval *in )
{
	int rc;
	struct berval *dn;

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

	dn = ber_bvdup( in );

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

		for(i=dn->bv_len-2; i>2; i--) {
			if( dn->bv_val[i] != '0' &&	dn->bv_val[i] != '1' ) {
				break;
			}
		}
Stig Venaas's avatar
Stig Venaas committed
240
241
242
243
		if( dn->bv_val[i] != '\'' ||
		    dn->bv_val[i-1] != 'B' ||
		    dn->bv_val[i-2] != '#' ) {
			ber_bvfree( dn );
244
245
246
247
248
249
250
			return LDAP_INVALID_SYNTAX;
		}

		/* trim the UID to allow use of dn_validate */
		dn->bv_val[i-2] = '\0';
	}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
251
	/* FIXME: should use dnValidate */
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
	rc = dn_validate( dn->bv_val ) == NULL
		? LDAP_INVALID_SYNTAX : LDAP_SUCCESS;

	ber_bvfree( dn );
	return rc;
}

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

	if( out->bv_len != 0 ) {
		char *dn;
		ber_len_t dnlen;
		char *uid = NULL;
		ber_len_t uidlen = 0;

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

			if( uid == NULL ) {
				ber_bvfree( out );
				return LDAP_INVALID_SYNTAX;
			}

			uidlen = out->bv_len - (out->bv_val - uid);
			/* temporarily trim the UID */
			*uid = '\0';
		}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
287
		/* FIXME: should use dnNormalize */
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
#ifdef USE_DN_NORMALIZE
		dn = dn_normalize( out->bv_val );
#else
		dn = dn_validate( out->bv_val );
#endif

		if( dn == NULL ) {
			ber_bvfree( out );
			return LDAP_INVALID_SYNTAX;
		}

		dnlen = strlen(dn);

		if( uidlen ) {
			/* restore the separator */
			*uid = '#';
			/* shift the UID */
			SAFEMEMCPY( &dn[dnlen], uid, uidlen );
		}

		out->bv_val = dn;
		out->bv_len = dnlen + uidlen;
	}

	*normalized = out;
	return LDAP_SUCCESS;
}

316
317
318
319
320
321
322
323
324
static int
inValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* any value allowed */
	return LDAP_OTHER;
}

325
static int
326
blobValidate(
327
328
329
330
	Syntax *syntax,
	struct berval *in )
{
	/* any value allowed */
331
	return LDAP_SUCCESS;
332
333
}

334
335
336
337
338
339
340
341
342
343
344
345
346
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;
	}
347

348
349
350
351
352
353
354
355
356
357
	/*
	 * 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' )
358
359
360
361
	{
		return LDAP_INVALID_SYNTAX;
	}

362
	for( i=in->bv_len-3; i>0; i-- ) {
363
364
365
366
367
368
369
370
		if( in->bv_val[i] != '0' && in->bv_val[i] != '1' ) {
			return LDAP_INVALID_SYNTAX;
		}
	}

	return LDAP_SUCCESS;
}

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
static int
bitStringNormalize(
	Syntax *syntax,
	struct berval *val,
	struct berval **normalized )
{
	/*
     * A normalized bitString is has no extaneous (leading) zero bits.
	 * That is, '00010'B is normalized to '10'B
	 * However, as a special case, '0'B requires no normalization.
     */
	struct berval *newval;
	char *p;

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

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

	newval = (struct berval *) ch_malloc( sizeof(struct berval) );

	if( *p == '\'' ) {
		/* no non-zero bits */
		newval->bv_val = ch_strdup("\'0\'B");
		newval->bv_len = sizeof("\'0\'B") - 1;
		goto done;
	}

	newval->bv_val = ch_malloc( val->bv_len + 1 );

	newval->bv_val[0] = '\'';
	newval->bv_len = 1;

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

	newval->bv_val[newval->bv_len] = '\0';

done:
	*normalized = newval;
	return LDAP_SUCCESS;
}

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
/*
 * 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,
447
	slap_mask_t flags,
448
449
450
451
452
453
454
455
456
457
458
	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;
}

459
460
461
462
463
464
465
466
467
static int
UTF8StringValidate(
	Syntax *syntax,
	struct berval *in )
{
	ber_len_t count;
	int len;
	unsigned char *u = in->bv_val;

468
469
	if( !in->bv_len ) return LDAP_INVALID_SYNTAX;

470
	for( count = in->bv_len; count > 0; count-=len, u+=len ) {
471
472
473
474
		/* get the length indicated by the first byte */
		len = LDAP_UTF8_CHARLEN( u );

		/* should not be zero */
475
		if( len == 0 ) return LDAP_INVALID_SYNTAX;
476
477
478

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

482
	if( count != 0 ) return LDAP_INVALID_SYNTAX;
483

484
	return LDAP_SUCCESS;
485
486
487
488
489
490
491
492
493
}

static int
UTF8StringNormalize(
	Syntax *syntax,
	struct berval *val,
	struct berval **normalized )
{
	struct berval *newval;
494
	char *p, *q, *s;
495

496
	newval = ch_malloc( sizeof( struct berval ) );
497

498
	p = val->bv_val;
499

500
501
502
	/* Ignore initial whitespace */
	while ( ldap_utf8_isspace( p ) ) {
		LDAP_UTF8_INCR( p );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
503
	}
504

505
506
	if( *p == '\0' ) {
		ch_free( newval );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
507
508
		return LDAP_INVALID_SYNTAX;
	}
509

510
511
512
	newval->bv_val = ch_strdup( p );
	p = q = newval->bv_val;
	s = NULL;
513

514
515
	while ( *p ) {
		int len;
516

517
518
519
520
521
		if ( ldap_utf8_isspace( p ) ) {
			len = LDAP_UTF8_COPY(q,p);
			s=q;
			p+=len;
			q+=len;
522

523
524
525
526
			/* Ignore the extra whitespace */
			while ( ldap_utf8_isspace( p ) ) {
				LDAP_UTF8_INCR( p );
			}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
527
		} else {
528
529
530
531
			len = LDAP_UTF8_COPY(q,p);
			s=NULL;
			p+=len;
			q+=len;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
532
		}
533
534
535
536
	}

	assert( *newval->bv_val );
	assert( newval->bv_val < p );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
537
	assert( q <= p );
538

539
540
541
542
543
544
545
546
547
548
549
	/* cannot start with a space */
	assert( !ldap_utf8_isspace(newval->bv_val) );

	/*
	 * 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 ) {
		q = s;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
550
	}
551

552
553
554
555
556
557
558
559
	/* cannot end with a space */
	assert( !ldap_utf8_isspace( LDAP_UTF8_PREV(q) ) );

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

	newval->bv_len = q - newval->bv_val;
	*normalized = newval;
560

561
	return LDAP_SUCCESS;
562
563
}

564
565
/* Returns Unicode cannonically normalized copy of a substring assertion
 * Skipping attribute description */
566
static SubstringsAssertion *
567
568
569
570
571
572
573
574
575
576
577
578
579
UTF8SubstringsassertionNormalize(
	SubstringsAssertion *sa,
	char casefold )
{
	SubstringsAssertion *nsa;
	int i;

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

	if( sa->sa_initial != NULL ) {
580
		nsa->sa_initial = ber_bvstr( UTF8normalize( sa->sa_initial, casefold ) );
581
582
583
584
585
586
587
588
589
590
591
		if( nsa->sa_initial == NULL ) {
			goto err;
		}
	}

	if( sa->sa_any != NULL ) {
		for( i=0; sa->sa_any[i] != NULL; i++ ) {
			/* empty */
		}
		nsa->sa_any = (struct berval **)ch_malloc( (i + 1) * sizeof(struct berval *) );
		for( i=0; sa->sa_any[i] != NULL; i++ ) {
592
			nsa->sa_any[i] = ber_bvstr( UTF8normalize( sa->sa_any[i], casefold ) );
593
594
595
596
597
598
599
600
			if( nsa->sa_any[i] == NULL ) {
				goto err;
			}
		}
		nsa->sa_any[i] = NULL;
	}

	if( sa->sa_final != NULL ) {
601
		nsa->sa_final = ber_bvstr( UTF8normalize( sa->sa_final, casefold ) );
602
603
604
605
606
607
608
609
		if( nsa->sa_final == NULL ) {
			goto err;
		}
	}

	return nsa;

err:
610
	ber_bvfree( nsa->sa_final );
611
	ber_bvecfree( nsa->sa_any );
612
	ber_bvfree( nsa->sa_initial );
613
614
615
616
	ch_free( nsa );
	return NULL;
}

617
/* Strip characters with the 8th bit set */
618
static char *
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
strip8bitChars(
	char *in )      
{
	char *p = in, *q;
  
	if( in == NULL ) {
		return NULL;
	}
	while( *p ) {
		if( *p & 0x80 ) {
			q = p;
			while( *++q & 0x80 ) {
				/* empty */
			}
			p = memmove(p, q, strlen(q) + 1);
		} else {
			p++;
		}
	}
	return in;
}

641
#ifndef SLAPD_APPROX_OLDSINGLESTRING
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659

#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 )
{
660
	char *val, *nval, *assertv, **values, **words, *c;
661
	int i, count, len, nextchunk=0, nextavail=0;
662
	size_t avlen;
663

664
	/* Yes, this is necessary */
665
	nval = UTF8normalize( value, UTF8_NOCASEFOLD );
666
	if( nval == NULL ) {
667
668
669
		*matchp = 1;
		return LDAP_SUCCESS;
	}
670
	strip8bitChars( nval );
671
672

	/* Yes, this is necessary */
673
	assertv = UTF8normalize( ((struct berval *)assertedValue),
674
675
				 UTF8_NOCASEFOLD );
	if( assertv == NULL ) {
676
		ch_free( nval );
677
678
679
680
681
		*matchp = 1;
		return LDAP_SUCCESS;
	}
	strip8bitChars( assertv );
	avlen = strlen( assertv );
682
683

	/* Isolate how many words there are */
684
	for( c=nval,count=1; *c; c++ ) {
685
686
687
688
689
690
691
692
693
		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 *) );
694
	for( c=nval,i=0;  i<count;  i++,c+=strlen(c)+1 ) {
695
696
697
698
		words[i] = c;
		values[i] = phonetic(c);
	}

699
	/* Work through the asserted value's words, to see if at least some
700
701
	   of the words are there, in the same order. */
	len = 0;
702
	while ( (size_t) nextchunk < avlen ) {
703
		len = strcspn( assertv + nextchunk, SLAPD_APPROX_DELIMITER);
704
705
706
707
		if( len == 0 ) {
			nextchunk++;
			continue;
		}
708
#if defined(SLAPD_APPROX_INITIALS)
709
		else if( len == 1 ) {
710
711
			/* Single letter words need to at least match one word's initial */
			for( i=nextavail; i<count; i++ )
712
713
				if( !strncasecmp( assertv+nextchunk, words[i], 1 )) {
					nextavail=i+1;
714
					break;
715
				}
716
717
		}
#endif
718
		else {
719
720
721
722
723
724
725
726
727
728
729
			/* 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;
				}
			}
730
			ch_free( val );
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
		}

		/* 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 */
752
	free( assertv );
753
754
755
756
757
	for( i=0; i<count; i++ ) {
		ch_free( values[i] );
	}
	ch_free( values );
	ch_free( words );
758
	ch_free( nval );
759
760
761
762

	return LDAP_SUCCESS;
}

763
static int 
764
765
766
767
768
769
770
771
772
773
774
775
776
777
approxIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	struct berval **values,
	struct berval ***keysp )
{
	char *val, *c;
	int i,j, len, wordcount, keycount=0;
	struct berval **newkeys, **keys=NULL;

	for( j=0; values[j] != NULL; j++ ) {
778
		/* Yes, this is necessary */
779
		val = UTF8normalize( values[j], UTF8_NOCASEFOLD );
780
781
		strip8bitChars( val );

782
		/* Isolate how many words there are. There will be a key for each */
Gary Williams's avatar
Gary Williams committed
783
		for( wordcount=0,c=val;	 *c;  c++) {
784
785
786
787
788
789
790
791
792
			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) 
Kurt Zeilenga's avatar
Kurt Zeilenga committed
793
			* sizeof(struct berval *) );
794
795
796
797
798
		memcpy( newkeys, keys, keycount * sizeof(struct berval *) );
		if( keys ) ch_free( keys );
		keys = newkeys;

		/* Get a phonetic copy of each word */
Gary Williams's avatar
Gary Williams committed
799
		for( c=val,i=0;	 i<wordcount;  c+=len+1	 ) {
800
801
802
803
804
805
806
807
808
			len = strlen( c );
			if( len < SLAPD_APPROX_WORDLEN ) continue;
			keys[keycount] = (struct berval *)ch_malloc( sizeof(struct berval) );
			keys[keycount]->bv_val = phonetic( c );
			keys[keycount]->bv_len = strlen( keys[keycount]->bv_val );
			keycount++;
			i++;
		}

809
		free( val );
810
811
812
813
814
815
816
	}
	keys[keycount] = NULL;
	*keysp = keys;

	return LDAP_SUCCESS;
}

817
static int 
818
819
820
821
822
823
824
825
826
827
828
829
830
approxFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertValue,
	struct berval ***keysp )
{
	char *val, *c;
	int i, count, len;
	struct berval **keys;

831
	/* Yes, this is necessary */
832
	val = UTF8normalize( ((struct berval *)assertValue),
833
834
835
836
837
838
839
840
841
			     UTF8_NOCASEFOLD );
	if( val == NULL ) {
		keys = (struct berval **)ch_malloc( sizeof(struct berval *) );
		keys[0] = NULL;
		*keysp = keys;
		return LDAP_SUCCESS;
	}
	strip8bitChars( val );

842
843
844
845
846
847
848
849
850
851
852
853
854
	/* 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 */
	keys = (struct berval **)ch_malloc( (count + 1) * sizeof(struct berval *) );

	/* Get a phonetic copy of each word */
Gary Williams's avatar
Gary Williams committed
855
	for( c=val,i=0;	 i<count; c+=len+1 ) {
856
857
		len = strlen(c);
		if( len < SLAPD_APPROX_WORDLEN ) continue;
858
		keys[i] = ber_bvstr( phonetic( c ) );
859
860
861
		i++;
	}

862
	free( val );
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883

	keys[count] = NULL;
	*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;
884
	char *s, *t;
885

886
	/* Yes, this is necessary */
887
	s = UTF8normalize( value, UTF8_NOCASEFOLD );
888
889
890
891
892
893
	if( s == NULL ) {
		*matchp = 1;
		return LDAP_SUCCESS;
	}

	/* Yes, this is necessary */
894
	t = UTF8normalize( ((struct berval *)assertedValue),
895
896
897
898
899
900
901
902
903
904
905
906
			   UTF8_NOCASEFOLD );
	if( t == NULL ) {
		free( s );
		*matchp = -1;
		return LDAP_SUCCESS;
	}

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

	free( s );
	free( t );
907
908
909
910
911
912
913
914
915

	*matchp = strcmp( vapprox, avapprox );

	ch_free( vapprox );
	ch_free( avapprox );

	return LDAP_SUCCESS;
}

916
static int 
917
918
919
920
921
922
923
924
925
926
927
approxIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	struct berval **values,
	struct berval ***keysp )
{
	int i;
	struct berval **keys;
928
	char *s;
929
930

	for( i=0; values[i] != NULL; i++ ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
931
		/* empty - just count them */
932
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
933
934

	/* we should have at least one value at this point */
935
936
937
938
939
940
	assert( i > 0 );

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

	/* Copy each value and run it through phonetic() */
	for( i=0; values[i] != NULL; i++ ) {
941
		/* Yes, this is necessary */
942
		s = UTF8normalize( values[i], UTF8_NOCASEFOLD );
943
944
945
946

		/* strip 8-bit chars and run through phonetic() */
		keys[i] = ber_bvstr( phonetic( strip8bitChars( s ) ) );
		free( s );
947
948
949
950
951
952
953
954
	}
	keys[i] = NULL;

	*keysp = keys;
	return LDAP_SUCCESS;
}


955
static int 
956
957
958
959
960
961
962
963
964
965
approxFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertValue,
	struct berval ***keysp )
{
	struct berval **keys;
966
	char *s;
967
968
969

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

970
	/* Yes, this is necessary */
971
	s = UTF8normalize( ((struct berval *)assertValue),
972
973
974
975
976
977
978
979
980
			     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;
	}
981
982
983
984
985
986
987

	*keysp = keys;
	return LDAP_SUCCESS;
}
#endif


988
static int
989
caseExactMatch(
990
	int *matchp,
991
	slap_mask_t flags,
992
993
994
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
995
	void *assertedValue )
996
{
997
998
999
	*matchp = UTF8normcmp( value->bv_val,
		((struct berval *) assertedValue)->bv_val,
		UTF8_NOCASEFOLD );
1000
	return LDAP_SUCCESS;
1001
1002
}

1003
static int
1004
caseExactIgnoreSubstringsMatch(
1005
	int *matchp,
1006
	slap_mask_t flags,
1007
1008
1009
1010
1011
1012
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	int match = 0;
Pierangelo Masarati's avatar
Pierangelo Masarati committed
1013
	SubstringsAssertion *sub = NULL;
1014
	struct berval left;
1015
1016
	int i;
	ber_len_t inlen=0;
1017
1018
1019
1020
	char *nav, casefold;

	casefold = strcmp( mr->smr_oid, caseExactSubstringsMatchOID )
		? UTF8_CASEFOLD : UTF8_NOCASEFOLD;
1021

1022
	nav = UTF8normalize( value, casefold );
1023
1024
1025
1026
1027
1028
	if( nav == NULL ) {
		match = 1;
		goto done;
	}
	left.bv_val = nav;
	left.bv_len = strlen( nav );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1029

1030
	sub = UTF8SubstringsassertionNormalize( assertedValue, casefold );
1031
1032
1033
1034
	if( sub == NULL ) {
		match = -1;
		goto done;
	}
1035

1036
	/* Add up asserted input length */
1037
1038
1039
1040
	if( sub->sa_initial ) {
		inlen += sub->sa_initial->bv_len;
	}
	if( sub->sa_any ) {
1041
1042
		for(i=0; sub->sa_any[i] != NULL; i++) {
			inlen += sub->sa_any[i]->bv_len;
1043
1044
1045
1046
1047
1048
1049
		}
	}
	if( sub->sa_final ) {
		inlen += sub->sa_final->bv_len;
	}

	if( sub->sa_initial ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1050
1051
1052
1053
1054
		if( inlen > left.bv_len ) {
			match = 1;
			goto done;
		}

1055
1056
		match = strncmp( sub->sa_initial->bv_val, left.bv_val,
			sub->sa_initial->bv_len );
1057
1058
1059
1060
1061
1062
1063

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

		left.bv_val += sub->sa_initial->bv_len;
		left.bv_len -= sub->sa_initial->bv_len;
1064
		inlen -= sub->sa_initial->bv_len;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1065
	}
1066

Kurt Zeilenga's avatar
Kurt Zeilenga committed
1067
	if( sub->sa_final ) {
1068
1069
1070
1071
		if( inlen > left.bv_len ) {
			match = 1;
			goto done;
		}
1072

1073
1074
1075
		match = strncmp( sub->sa_final->bv_val,
			&left.bv_val[left.bv_len - sub->sa_final->bv_len],
			sub->sa_final->bv_len );
1076
1077
1078
1079
1080
1081

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

		left.bv_len -= sub->sa_final->bv_len;
1082
		inlen -= sub->sa_final->bv_len;
1083
1084
1085
	}

	if( sub->sa_any ) {
1086
1087
1088
1089
1090
		for(i=0; sub->sa_any[i]; i++) {
			ber_len_t idx;
			char *p;

retry:
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1091
1092
1093
1094
1095
1096
			if( inlen > left.bv_len ) {
				/* not enough length */
				match = 1;
				goto done;
			}

1097
1098
1099
1100
			if( sub->sa_any[i]->bv_len == 0 ) {
				continue;
			}

1101
			p = strchr( left.bv_val, *sub->sa_any[i]->bv_val );
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112

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

			idx = p - left.bv_val;
			assert( idx < left.bv_len );

			if( idx >= left.bv_len ) {
				/* this shouldn't happen */
Stig Venaas's avatar
Stig Venaas committed
1113
1114
1115
1116
1117
				free( nav );
				ch_free( sub->sa_final );
				ber_bvecfree( sub->sa_any );
				ch_free( sub->sa_initial );
				ch_free( sub );
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
				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;
			}

1130
1131
1132
			match = strncmp( left.bv_val,
				sub->sa_any[i]->bv_val,
				sub->sa_any[i]->bv_len );
1133
1134

			if( match != 0 ) {
1135
1136
				left.bv_val++;
				left.bv_len--;
1137
1138
1139
1140
1141
				goto retry;
			}

			left.bv_val += sub->sa_any[i]->bv_len;
			left.bv_len -= sub->sa_any[i]->bv_len;
1142
			inlen -= sub->sa_any[i]->bv_len;
1143
		}
1144
1145
1146
	}

done:
1147
1148
	free( nav );
	if( sub != NULL ) {
1149
		ber_bvfree( sub->sa_final );
1150
		ber_bvecfree( sub->sa_any );
1151
		ber_bvfree( sub->sa_initial );
1152
1153
		ch_free( sub );
	}
1154
1155
1156
1157
	*matchp = match;
	return LDAP_SUCCESS;
}

1158
/* Index generation function */
1159
static int caseExactIgnoreIndexer(
1160
1161
	slap_mask_t use,
	slap_mask_t flags,
1162
1163
1164
1165
1166
1167
1168
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	struct berval **values,
	struct berval ***keysp )
{
	int i;
1169
	char casefold;
1170
1171
	size_t slen, mlen;
	struct berval **keys;
1172
	HASH_CONTEXT   HASHcontext;
Gary Williams's avatar
Gary Williams committed
1173
	unsigned char	HASHdigest[HASH_BYTES];
1174
	struct berval digest;
1175
1176
	digest.bv_val = HASHdigest;
	digest.bv_len = sizeof(HASHdigest);
1177
1178

	for( i=0; values[i] != NULL; i++ ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1179
		/* empty - just count them */
1180
1181
	}

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

1185
1186
1187
1188
1189
	keys = ch_malloc( sizeof( struct berval * ) * (i+1) );

	slen = strlen( syntax->ssyn_oid );
	mlen = strlen( mr->smr_oid );

1190
1191
1192
	casefold = strcmp( mr->smr_oid, caseExactMatchOID )
		? UTF8_CASEFOLD : UTF8_NOCASEFOLD;

1193
	for( i=0; values[i] != NULL; i++ ) {
1194
		struct berval *value;
1195
		value = ber_bvstr( UTF8normalize( values[i],
1196
			casefold ) );
1197

1198
		HASH_Init( &HASHcontext );
1199
		if( prefix != NULL && prefix->bv_len > 0 ) {
1200
			HASH_Update( &HASHcontext,
1201
1202
				prefix->bv_val, prefix->bv_len );
		}
1203
		HASH_Update( &HASHcontext,
1204
			syntax->ssyn_oid, slen );
1205
		HASH_Update( &HASHcontext,
1206
			mr->smr_oid, mlen );
1207
		HASH_Update( &HASHcontext,
1208
			value->bv_val, value->bv_len );
1209
		HASH_Final( HASHdigest, &HASHcontext );
1210

1211
1212
		ber_bvfree( value );

1213
1214
1215
1216
1217
1218
1219
1220
1221
		keys[i] = ber_bvdup( &digest );
	}

	keys[i] = NULL;
	*keysp = keys;
	return LDAP_SUCCESS;
}

/* Index generation function */
1222
static int caseExactIgnoreFilter(
1223
1224
	slap_mask_t use,
	slap_mask_t flags,
1225
1226
1227
1228
1229
1230
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertValue,
	struct berval ***keysp )
{
1231
	char casefold;
1232
1233
	size_t slen, mlen;
	struct berval **keys;
1234
	HASH_CONTEXT   HASHcontext;
Gary Williams's avatar
Gary Williams committed
1235
	unsigned char	HASHdigest[HASH_BYTES];
1236
1237
	struct berval *value;
	struct berval digest;
1238
1239
	digest.bv_val = HASHdigest;
	digest.bv_len = sizeof(HASHdigest);
1240
1241
1242
1243

	slen = strlen( syntax->ssyn_oid );
	mlen = strlen( mr->smr_oid );

1244
1245
1246
	casefold = strcmp( mr->smr_oid, caseExactMatchOID )
		? UTF8_CASEFOLD : UTF8_NOCASEFOLD;

1247
	value = ber_bvstr( UTF8normalize( ((struct berval *) assertValue),
1248
		casefold ) );
1249
1250
1251
1252
1253
1254
	/* This usually happens if filter contains bad UTF8 */
	if( value == NULL ) {
		keys = ch_malloc( sizeof( struct berval * ) );
		keys[0] = NULL;
		return LDAP_SUCCESS;
	}
1255
1256
1257

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

1258
	HASH_Init( &HASHcontext );
1259
	if( prefix != NULL && prefix->bv_len > 0 ) {
1260
		HASH_Update( &HASHcontext,
1261
1262
			prefix->bv_val, prefix->bv_len );
	}