schema_init.c 109 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
#define numericStringMatch				caseIgnoreIA5Match
40
#define objectIdentifierMatch			octetStringMatch
41
#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
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
	keys[i].bv_len = 0;
190
191
192
193
194
195
196

	*keysp = keys;

	return LDAP_SUCCESS;
}

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

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

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

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

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

	*keysp = keys;

	return LDAP_SUCCESS;
}
241

242
243
244
245
246
static int
inValidate(
	Syntax *syntax,
	struct berval *in )
{
Kurt Zeilenga's avatar
Kurt Zeilenga committed
247
248
	/* no value allowed */
	return LDAP_INVALID_SYNTAX;
249
250
}

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

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

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

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

	return LDAP_SUCCESS;
}

297
298
299
300
static int
bitStringNormalize(
	Syntax *syntax,
	struct berval *val,
301
	struct berval *normalized )
302
303
{
	/*
304
	 * A normalized bitString is has no extaneous (leading) zero bits.
305
306
	 * That is, '00010'B is normalized to '10'B
	 * However, as a special case, '0'B requires no normalization.
307
	 */
308
309
310
311
312
313
314
315
316
317
	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 */
318
		ber_str2bv( "\'0\'B", sizeof("\'0\'B") - 1, 1, normalized );
319
320
321
		goto done;
	}

322
	normalized->bv_val = ch_malloc( val->bv_len + 1 );
323

324
325
	normalized->bv_val[0] = '\'';
	normalized->bv_len = 1;
326
327

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

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

done:
	return LDAP_SUCCESS;
}

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

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
479
480
/*
 * 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,
481
	slap_mask_t flags,
482
483
484
485
486
487
488
489
490
491
492
	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;
}

493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
/*-------------------------------------------------------------------
LDAP/X.500 string syntax / matching rules have a few oddities.  This
comment attempts to detail how slapd(8) treats them.

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

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

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


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

  In LDPAv3, a directory string is a UTF-8 encoded UCS string.

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

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

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

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

  In matching, spaces are ignored.

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

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

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

563
564
565
566
567
568
569
570
571
static int
UTF8StringValidate(
	Syntax *syntax,
	struct berval *in )
{
	ber_len_t count;
	int len;
	unsigned char *u = in->bv_val;

572
573
	if( !in->bv_len ) return LDAP_INVALID_SYNTAX;

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

Kurt Zeilenga's avatar
Kurt Zeilenga committed
578
579
580
		/* very basic checks */
		switch( len ) {
			case 6:
581
				if( (u[5] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
582
583
584
					return LDAP_INVALID_SYNTAX;
				}
			case 5:
585
				if( (u[4] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
586
587
588
					return LDAP_INVALID_SYNTAX;
				}
			case 4:
589
				if( (u[3] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
590
591
592
					return LDAP_INVALID_SYNTAX;
				}
			case 3:
593
				if( (u[2] & 0xC0 )!= 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
594
595
596
					return LDAP_INVALID_SYNTAX;
				}
			case 2:
597
				if( (u[1] & 0xC0) != 0x80 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
598
599
600
					return LDAP_INVALID_SYNTAX;
				}
			case 1:
601
				/* CHARLEN already validated it */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
602
603
604
605
				break;
			default:
				return LDAP_INVALID_SYNTAX;
		}
606
607
608

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

612
	if( count != 0 ) return LDAP_INVALID_SYNTAX;
613

614
	return LDAP_SUCCESS;
615
616
617
618
619
620
}

static int
UTF8StringNormalize(
	Syntax *syntax,
	struct berval *val,
621
	struct berval *normalized )
622
{
623
	char *p, *q, *s, *e;
624
	int len = 0;
625

Kurt Zeilenga's avatar
Kurt Zeilenga committed
626
627
628
	/* validator should have refused an empty string */
	assert( val->bv_len );

629
	p = val->bv_val;
630

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

635
	normalized->bv_len = val->bv_len - (p - val->bv_val);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
636
637
638
639
640
641

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

642
643
	ber_mem2bv( p, normalized->bv_len, 1, normalized );
	e = normalized->bv_val + normalized->bv_len;
644
645
646
647

	assert( normalized->bv_val );

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

650
	while ( p < e ) {
651
652
653
654
655
		q += len;
		if ( ASCII_SPACE( *p ) ) {
			s = q - len;
			len = 1;
			*q = *p++;
656

657
			/* Ignore the extra whitespace */
658
659
			while ( ASCII_SPACE( *p ) ) {
				p++;
660
			}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
661
		} else {
662
663
664
			len = LDAP_UTF8_COPY(q,p);
			s=NULL;
			p+=len;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
665
		}
666
667
	}

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

671
	/* cannot start with a space */
672
	assert( !ASCII_SPACE( normalized->bv_val[0] ) );
673
674
675
676
677
678
679
680

	/*
	 * 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
681
		len = q - s;
682
		q = s;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
683
	}
684

685
	/* cannot end with a space */
686
687
688
	assert( !ASCII_SPACE( *q ) );

	q += len;
689
690
691
692

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

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

695
	return LDAP_SUCCESS;
696
697
}

698
/* Returns Unicode canonically normalized copy of a substring assertion
699
 * Skipping attribute description */
700
static SubstringsAssertion *
701
702
UTF8SubstringsassertionNormalize(
	SubstringsAssertion *sa,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
703
	unsigned casefold )
704
705
706
707
708
709
710
711
712
{
	SubstringsAssertion *nsa;
	int i;

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

713
	if( sa->sa_initial.bv_val != NULL ) {
714
		UTF8bvnormalize( &sa->sa_initial, &nsa->sa_initial, casefold );
715
		if( nsa->sa_initial.bv_val == NULL ) {
716
717
718
719
720
			goto err;
		}
	}

	if( sa->sa_any != NULL ) {
721
		for( i=0; sa->sa_any[i].bv_val != NULL; i++ ) {
722
723
			/* empty */
		}
724
725
726
		nsa->sa_any = (struct berval *)
			ch_malloc( (i + 1) * sizeof(struct berval) );

727
		for( i=0; sa->sa_any[i].bv_val != NULL; i++ ) {
728
			UTF8bvnormalize( &sa->sa_any[i], &nsa->sa_any[i], 
729
				casefold );
730
			if( nsa->sa_any[i].bv_val == NULL ) {
731
732
733
				goto err;
			}
		}
734
		nsa->sa_any[i].bv_val = NULL;
735
736
	}

737
	if( sa->sa_final.bv_val != NULL ) {
738
		UTF8bvnormalize( &sa->sa_final, &nsa->sa_final, casefold );
739
		if( nsa->sa_final.bv_val == NULL ) {
740
741
742
743
744
745
746
			goto err;
		}
	}

	return nsa;

err:
Howard Chu's avatar
Howard Chu committed
747
	if ( nsa->sa_final.bv_val ) free( nsa->sa_final.bv_val );
748
	if ( nsa->sa_any ) ber_bvarray_free( nsa->sa_any );
Howard Chu's avatar
Howard Chu committed
749
	if ( nsa->sa_initial.bv_val ) free( nsa->sa_initial.bv_val );
750
751
752
753
	ch_free( nsa );
	return NULL;
}

754
#ifndef SLAPD_APPROX_OLDSINGLESTRING
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772

#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 )
{
773
774
	struct berval *nval, *assertv;
	char *val, **values, **words, *c;
775
776
	int i, count, len, nextchunk=0, nextavail=0;

777
	/* Yes, this is necessary */
778
	nval = UTF8bvnormalize( value, NULL, LDAP_UTF8_APPROX );
779
	if( nval == NULL ) {
780
781
782
783
784
		*matchp = 1;
		return LDAP_SUCCESS;
	}

	/* Yes, this is necessary */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
785
786
	assertv = UTF8bvnormalize( ((struct berval *)assertedValue),
		NULL, LDAP_UTF8_APPROX );
787
	if( assertv == NULL ) {
788
		ber_bvfree( nval );
789
790
791
		*matchp = 1;
		return LDAP_SUCCESS;
	}
792
793

	/* Isolate how many words there are */
794
	for ( c = nval->bv_val, count = 1; *c; c++ ) {
795
796
797
798
799
800
801
802
803
		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 *) );
804
	for ( c = nval->bv_val, i = 0;  i < count; i++, c += strlen(c) + 1 ) {
805
806
807
808
		words[i] = c;
		values[i] = phonetic(c);
	}

809
	/* Work through the asserted value's words, to see if at least some
810
811
	   of the words are there, in the same order. */
	len = 0;
812
813
	while ( (ber_len_t) nextchunk < assertv->bv_len ) {
		len = strcspn( assertv->bv_val + nextchunk, SLAPD_APPROX_DELIMITER);
814
815
816
817
		if( len == 0 ) {
			nextchunk++;
			continue;
		}
818
#if defined(SLAPD_APPROX_INITIALS)
819
		else if( len == 1 ) {
820
821
			/* Single letter words need to at least match one word's initial */
			for( i=nextavail; i<count; i++ )
822
				if( !strncasecmp( assertv->bv_val + nextchunk, words[i], 1 )) {
823
					nextavail=i+1;
824
					break;
825
				}
826
827
		}
#endif
828
		else {
829
			/* Isolate the next word in the asserted value and phonetic it */
830
831
			assertv->bv_val[nextchunk+len] = '\0';
			val = phonetic( assertv->bv_val + nextchunk );
832
833
834
835
836
837
838
839

			/* 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;
				}
			}
840
			ch_free( val );
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
		}

		/* 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 */
862
	ber_bvfree( assertv );
863
864
865
866
867
	for( i=0; i<count; i++ ) {
		ch_free( values[i] );
	}
	ch_free( values );
	ch_free( words );
868
	ber_bvfree( nval );
869
870
871
872

	return LDAP_SUCCESS;
}

873
static int 
874
875
876
877
878
879
approxIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
880
881
	BerVarray values,
	BerVarray *keysp )
882
{
883
	char *c;
884
	int i,j, len, wordcount, keycount=0;
885
	struct berval *newkeys;
886
	BerVarray keys=NULL;
887

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

894
		/* Isolate how many words there are. There will be a key for each */
895
		for( wordcount = 0, c = val.bv_val; *c; c++) {
896
897
898
899
900
901
902
903
			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 */
904
905
		newkeys = (struct berval *)ch_malloc( (keycount + wordcount + 1) 
			* sizeof(struct berval) );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
906
		AC_MEMCPY( newkeys, keys, keycount * sizeof(struct berval) );
907
908
909
910
		if( keys ) ch_free( keys );
		keys = newkeys;

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

919
		ber_memfree( val.bv_val );
920
	}
921
	keys[keycount].bv_val = NULL;
922
923
924
925
926
	*keysp = keys;

	return LDAP_SUCCESS;
}

927
static int 
928
929
930
931
932
933
934
approxFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertValue,
935
	BerVarray *keysp )
936
{
937
	char *c;
938
	int i, count, len;
939
	struct berval *val;
940
	BerVarray keys;
941

942
	/* Yes, this is necessary */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
943
944
	val = UTF8bvnormalize( ((struct berval *)assertValue),
		NULL, LDAP_UTF8_APPROX );
945
	if( val == NULL || val->bv_val == NULL ) {
946
947
		keys = (struct berval *)ch_malloc( sizeof(struct berval) );
		keys[0].bv_val = NULL;
948
		*keysp = keys;
949
		ber_bvfree( val );
950
951
952
		return LDAP_SUCCESS;
	}

953
	/* Isolate how many words there are. There will be a key for each */
954
	for( count = 0,c = val->bv_val; *c; c++) {
955
956
957
958
959
960
961
962
		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 */
963
	keys = (struct berval *)ch_malloc( (count + 1) * sizeof(struct berval) );
964
965

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

973
	ber_bvfree( val );
974

975
	keys[count].bv_val = NULL;
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
	*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;
995
	char *s, *t;
996

997
	/* Yes, this is necessary */
998
	s = UTF8normalize( value, UTF8_NOCASEFOLD );
999
1000
1001
1002
1003
1004
	if( s == NULL ) {
		*matchp = 1;
		return LDAP_SUCCESS;
	}

	/* Yes, this is necessary */
1005
	t = UTF8normalize( ((struct berval *)assertedValue),
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
			   UTF8_NOCASEFOLD );
	if( t == NULL ) {
		free( s );
		*matchp = -1;
		return LDAP_SUCCESS;
	}

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

	free( s );
	free( t );
1018
1019
1020
1021
1022
1023
1024
1025
1026

	*matchp = strcmp( vapprox, avapprox );

	ch_free( vapprox );
	ch_free( avapprox );

	return LDAP_SUCCESS;
}

1027
static int 
1028
1029
1030
1031
1032
1033
approxIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
1034
1035
	BerVarray values,
	BerVarray *keysp )
1036
1037
{
	int i;
1038
	BerVarray *keys;
1039
	char *s;
1040

1041
	for( i=0; values[i].bv_val != NULL; i++ ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1042
		/* empty - just count them */
1043
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1044
1045

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

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

	/* Copy each value and run it through phonetic() */
1051
	for( i=0; values[i].bv_val != NULL; i++ ) {
1052
		/* Yes, this is necessary */
1053
		s = UTF8normalize( &values[i], UTF8_NOCASEFOLD );
1054
1055

		/* strip 8-bit chars and run through phonetic() */
1056
		ber_str2bv( phonetic( strip8bitChars( s ) ), 0, 0, &keys[i] );
1057
		free( s );
1058
	}
1059
	keys[i].bv_val = NULL;
1060
1061
1062
1063
1064
1065

	*keysp = keys;
	return LDAP_SUCCESS;
}


1066
static int 
1067
1068
1069
1070
1071
1072
1073
approxFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertValue,
1074
	BerVarray *keysp )
1075
{
1076
	BerVarray keys;
1077
	char *s;
1078

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

1081
	/* Yes, this is necessary */
1082
	s = UTF8normalize( ((struct berval *)assertValue),
1083
1084
1085
1086
1087
1088
1089
1090
1091
			     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;
	}
1092
1093
1094
1095
1096
1097
1098

	*keysp = keys;
	return LDAP_SUCCESS;
}
#endif


1099
static int
1100
caseExactMatch(
1101
	int *matchp,
1102
	slap_mask_t flags,
1103
1104
1105
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
1106
	void *assertedValue )
1107
{
1108
1109
1110
	*matchp = UTF8bvnormcmp( value,
		(struct berval *) assertedValue,
		LDAP_UTF8_NOCASEFOLD );
1111
	return LDAP_SUCCESS;
1112
1113
}

1114
static int
1115
caseExactIgnoreSubstringsMatch(
1116
	int *matchp,
1117
	slap_mask_t flags,
1118
1119
1120
1121
1122
1123
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	int match = 0;
Pierangelo Masarati's avatar
Pierangelo Masarati committed
1124
	SubstringsAssertion *sub = NULL;
1125
	struct berval left = { 0, NULL };
1126
1127
	int i;
	ber_len_t inlen=0;
1128
	char *nav = NULL;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1129
	unsigned casefold;
1130

1131
	casefold = ( mr != caseExactSubstringsMatchingRule )