filterindex.c 18.8 KB
Newer Older
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1
/* filterindex.c - generate the list of candidate entries from a filter */
2
3
/* $OpenLDAP$ */
/*
4
 * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
5
6
7
8
 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
 */

#include "portable.h"
Kurt Zeilenga's avatar
Kurt Zeilenga committed
9
10
11

#include <stdio.h>

12
13
#include <ac/socket.h>
#include <ac/string.h>
Kurt Zeilenga's avatar
Kurt Zeilenga committed
14

15
16
#include "slap.h"
#include "back-ldbm.h"
Kurt Zeilenga's avatar
Kurt Zeilenga committed
17

18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
static ID_BLOCK	*presence_candidates(
	Backend *be,
	AttributeDescription *desc );
static ID_BLOCK	*equality_candidates(
	Backend *be, AttributeAssertion *ava );
static ID_BLOCK	*approx_candidates(
	Backend *be, AttributeAssertion *ava );
static ID_BLOCK	*substring_candidates(
	Backend *be,
	SubstringsAssertion *sub );
static ID_BLOCK	*list_candidates(
	Backend *be,
	Filter *flist,
	int ftype );

ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
34
35
36
37
38
filter_candidates(
    Backend	*be,
    Filter	*f
)
{
39
	ID_BLOCK	*result;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
40

41
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
42
	LDAP_LOG( FILTER, ENTRY, "filter_candidates: enter\n", 0, 0, 0 );
43
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
44
	Debug( LDAP_DEBUG_TRACE, "=> filter_candidates\n", 0, 0, 0 );
45
46
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
47
48
49

	result = NULL;
	switch ( f->f_choice ) {
50
51
52
53
	case SLAPD_FILTER_COMPUTED:
		switch( f->f_result ) {
		case SLAPD_COMPARE_UNDEFINED:
		/* This technically is not the same as FALSE, but it
Howard Chu's avatar
Howard Chu committed
54
		 * certainly will produce no matches.
55
56
57
58
59
60
61
62
63
64
65
		 */
		/* FALLTHRU */
		case LDAP_COMPARE_FALSE:
			result = NULL;
			break;
		case LDAP_COMPARE_TRUE:
			result = idl_allids( be );
			break;
		}
		break;

66
67
	case SLAPD_FILTER_DN_ONE:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
68
69
		LDAP_LOG( FILTER, DETAIL1, 
			   "filter_candidates:  DN ONE (%s)\n", f->f_dn, 0, 0 );
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#else
		Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 );
#endif

		/* an error is treated as an empty list */
		if ( dn2idl( be, f->f_dn, DN_ONE_PREFIX, &result ) != 0
				&& result != NULL ) {
			idl_free( result );
			result = NULL;
		}
		break;

	case SLAPD_FILTER_DN_SUBTREE:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
84
85
		LDAP_LOG( FILTER, DETAIL1, 
			   "filter_candidates:  DN SUBTREE (%s)\n", f->f_dn, 0, 0 );
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#else
		Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 );
#endif

		/* an error is treated as an empty list */
		if ( dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX, &result ) != 0
				&& result != NULL ) {
			idl_free( result );
			result = NULL;
		}
		break;

	case LDAP_FILTER_PRESENT:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
100
101
102
		LDAP_LOG( FILTER, DETAIL1, 
			"filter_candidates:  Present (%s)\n", 
			f->f_desc->ad_cname.bv_val, 0, 0 );
103
104
105
106
107
108
109
#else
		Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 );
#endif

		result = presence_candidates( be, f->f_desc );
		break;

Kurt Zeilenga's avatar
Kurt Zeilenga committed
110
	case LDAP_FILTER_EQUALITY:
111
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
112
		LDAP_LOG( FILTER, DETAIL1, 
113
114
			   "filter_candidates:  EQUALITY (%s),(%s)\n",
			   f->f_ava->aa_desc->ad_cname.bv_val,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
115
			   f->f_ava->aa_value.bv_val, 0 );
116
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
117
		Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 );
118
119
120
121
122
123
124
#endif

		result = equality_candidates( be, f->f_ava );
		break;

	case LDAP_FILTER_APPROX:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
125
		LDAP_LOG( FILTER, DETAIL1, 
126
127
			   "filter_candidates:  APPROX (%s), (%s)\n",
			   f->f_ava->aa_desc->ad_cname.bv_val,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
128
			   f->f_ava->aa_value.bv_val, 0 );
129
130
131
132
133
#else
		Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 );
#endif

		result = approx_candidates( be, f->f_ava );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
134
135
136
		break;

	case LDAP_FILTER_SUBSTRINGS:
137
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
138
139
		LDAP_LOG( FILTER, DETAIL1,
			   "filter_candidates:  SUBSTRINGS\n", 0, 0, 0 );
140
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
141
		Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 );
142
143
144
#endif

		result = substring_candidates( be, f->f_sub );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
145
146
147
		break;

	case LDAP_FILTER_GE:
148
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
149
		LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  GE\n", 0, 0, 0 );
150
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
151
		Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 );
152
153
154
#endif

		result = presence_candidates( be, f->f_ava->aa_desc );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
155
156
157
		break;

	case LDAP_FILTER_LE:
158
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
159
		LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  LE\n", 0, 0, 0 );
160
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
161
		Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 );
162
#endif
Kurt Zeilenga's avatar
Kurt Zeilenga committed
163

164
		result = presence_candidates( be, f->f_ava->aa_desc );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
165
166
167
		break;

	case LDAP_FILTER_AND:
168
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
169
		LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  AND\n", 0, 0, 0 );
170
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
171
		Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 );
172
173
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
174
175
176
177
		result = list_candidates( be, f->f_and, LDAP_FILTER_AND );
		break;

	case LDAP_FILTER_OR:
178
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
179
		LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  OR\n", 0, 0, 0 );
180
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
181
		Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 );
182
183
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
184
185
186
187
		result = list_candidates( be, f->f_or, LDAP_FILTER_OR );
		break;

	case LDAP_FILTER_NOT:
188
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
189
		LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  NOT\n", 0, 0, 0 );
190
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
191
		Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 );
192
193
194
195
196
197
198
199
200
201
202
203
#endif

		/*
		 * As candidates lists may contain entries which do
		 * not match the assertion, negation of the inner candidate
		 * list could result in matching entries be excluded from
		 * the returned candidate list.
		 */
		result = idl_allids( be );
		break;
	default:
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
204
		LDAP_LOG( FILTER, DETAIL1, "filter_candidates:  UNKNOWN\n", 0, 0, 0 );
205
206
207
208
209
210
211
#else
		Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN\n", 0, 0, 0 );
#endif
		/* unknown filters must not return NULL, to allow
		 * extended filter processing to be done later.
		 */
		result = idl_allids( be );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
212
213
214
		break;
	}

215
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
216
217
218
	LDAP_LOG( FILTER, ENTRY, 
		"filter_candidates: return %ld\n", 
		result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
219
220
221
222
223
#else
	Debug( LDAP_DEBUG_TRACE, "<= filter_candidates %ld\n",
	    result ? ID_BLOCK_NIDS(result) : 0, 0, 0 );
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
224
225
226
	return( result );
}

227
228
static ID_BLOCK *
presence_candidates(
Kurt Zeilenga's avatar
Kurt Zeilenga committed
229
    Backend	*be,
230
	AttributeDescription *desc
Kurt Zeilenga's avatar
Kurt Zeilenga committed
231
232
)
{
233
234
235
236
237
	ID_BLOCK	*idl;
	DBCache	*db;
	int rc;
	char *dbname;
	slap_mask_t mask;
238
	struct berval prefix = {0, NULL};
239
240

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
241
	LDAP_LOG( FILTER, ENTRY, "presence_candidates: enter\n", 0, 0, 0 );
242
243
244
#else
	Debug( LDAP_DEBUG_TRACE, "=> presence_candidates\n", 0, 0, 0 );
#endif
Kurt Zeilenga's avatar
Kurt Zeilenga committed
245

246
	idl = idl_allids( be );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
247

248
249
250
	if( desc == slap_schema.si_ad_objectClass ) {
		return idl;
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
251

252
253
254
255
256
	rc = index_param( be, desc, LDAP_FILTER_PRESENT,
		&dbname, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
257
258
		LDAP_LOG( FILTER, INFO, 
			   "presence_candidates: index_param returned %d\n", rc, 0, 0 );
259
260
261
262
263
264
265
266
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= presence_candidates: index_param returned=%d\n",
			rc, 0, 0 );
#endif

		return idl;
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
267

268
269
270
	if( dbname == NULL ) {
		/* not indexed */
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
271
		LDAP_LOG( FILTER, INFO, "presence_candidates: not indexed\n", 0, 0, 0 );
272
273
274
275
276
277
278
279
280
281
282
283
284
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= presense_candidates: not indexed\n",
			0, 0, 0 );
#endif

		return idl;
	}

	db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
	
	if ( db == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
285
		LDAP_LOG( FILTER, INFO, 
286
			   "presence_candidates: db open failed (%s%s)\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
287
			   dbname, LDBM_SUFFIX, 0 );
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
#else
		Debug( LDAP_DEBUG_ANY,
		    "<= presense_candidates db open failed (%s%s)\n",
			dbname, LDBM_SUFFIX, 0 );
#endif

		return idl;
	}

	if( prefix.bv_val != NULL ) {
		idl_free( idl );
		idl = NULL;

		rc = key_read( be, db, &prefix, &idl );

		if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
305
306
			LDAP_LOG( FILTER, ERR, 
				   "presence_candidates: key read failed (%d)\n", rc, 0, 0 );
307
308
309
310
311
312
313
314
315
#else
			Debug( LDAP_DEBUG_TRACE,
				"<= presense_candidates key read failed (%d)\n",
			    rc, 0, 0 );
#endif


		} else if( idl == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
316
			LDAP_LOG( FILTER, DETAIL1, "presence_candidates: NULL\n", 0, 0, 0 );
317
318
319
320
321
322
323
#else
			Debug( LDAP_DEBUG_TRACE,
				"<= presense_candidates NULL\n",
			    0, 0, 0 );
#endif

		}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
324
325
	}

326
327
328
	ldbm_cache_close( be, db );

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
329
330
331
	LDAP_LOG( FILTER, ENTRY, 
		"presence_candidates:  return %ld\n", 
		idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
332
333
334
335
336
#else
	Debug( LDAP_DEBUG_TRACE, "<= presence_candidates %ld\n",
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
337
338
339
	return( idl );
}

340
341
static ID_BLOCK *
equality_candidates(
Kurt Zeilenga's avatar
Kurt Zeilenga committed
342
    Backend	*be,
343
	AttributeAssertion *ava
Kurt Zeilenga's avatar
Kurt Zeilenga committed
344
345
)
{
346
347
348
349
350
351
	ID_BLOCK	*idl;
	DBCache	*db;
	int i;
	int rc;
	char *dbname;
	slap_mask_t mask;
352
	struct berval prefix = {0, NULL};
353
354
355
356
	struct berval *keys = NULL;
	MatchingRule *mr;

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
357
	LDAP_LOG( FILTER, ENTRY, "equality_candidates: enter\n", 0, 0, 0 );
358
359
360
361
362
363
364
365
366
367
368
369
#else
	Debug( LDAP_DEBUG_TRACE, "=> equality_candidates\n", 0, 0, 0 );
#endif


	idl = idl_allids( be );

	rc = index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY,
		&dbname, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
370
371
		LDAP_LOG( FILTER, ERR, 
			   "equality_candidates:  index_param returned %d\n", rc, 0, 0 );
372
373
374
375
376
377
378
379
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= equality_candidates: index_param returned=%d\n",
			rc, 0, 0 );
#endif

		return idl;
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
380

381
382
383
	if( dbname == NULL ) {
		/* not indexed */
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
384
		LDAP_LOG( FILTER, ERR, "equality_candidates: not indexed\n", 0, 0, 0 );
385
386
387
388
389
390
391
392
393
394
395
396
397
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= equality_candidates: not indexed\n",
			0, 0, 0 );
#endif

		return idl;
	}

	mr = ava->aa_desc->ad_type->sat_equality;
	if( !mr ) {
		return idl;
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
398

399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
	if( !mr->smr_filter ) {
		return idl;
	}

	rc = (mr->smr_filter)(
		LDAP_FILTER_EQUALITY,
		mask,
		ava->aa_desc->ad_type->sat_syntax,
		mr,
		&prefix,
		&ava->aa_value,
		&keys );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
414
		LDAP_LOG( FILTER, ERR, 
415
			   "equality_candidates: (%s%s) MR filter failed (%d\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
416
			   dbname, LDBM_SUFFIX, rc );
417
418
419
420
421
422
423
424
425
426
427
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= equality_candidates: (%s%s) MR filter failed (%d)\n",
			dbname, LDBM_SUFFIX, rc );
#endif

		return idl;
	}

	if( keys == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
428
429
		LDAP_LOG( FILTER, ERR, 
		   "equality_candidates: no keys (%s%s)\n", dbname, LDBM_SUFFIX, 0 );
430
431
432
433
434
435
436
437
438
439
440
441
442
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= equality_candidates: no keys (%s%s)\n",
			dbname, LDBM_SUFFIX, 0 );
#endif

		return idl;
	}

	db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
	
	if ( db == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
443
444
		LDAP_LOG( FILTER, ERR, "equality_candidates: db open failed (%s%s)\n",
			dbname, LDBM_SUFFIX, 0 );
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
#else
		Debug( LDAP_DEBUG_ANY,
		    "<= equality_candidates db open failed (%s%s)\n",
			dbname, LDBM_SUFFIX, 0 );
#endif

		return idl;
	}

	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
		ID_BLOCK *save;
		ID_BLOCK *tmp;

		rc = key_read( be, db, &keys[i], &tmp );

		if( rc != LDAP_SUCCESS ) {
			idl_free( idl );
			idl = NULL;
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
464
465
			LDAP_LOG( FILTER, ERR, 
				   "equality_candidates: key read failed (%d)\n", rc, 0, 0 );
466
467
468
469
470
471
472
473
474
475
476
477
478
#else
			Debug( LDAP_DEBUG_TRACE,
				"<= equality_candidates key read failed (%d)\n",
			    rc, 0, 0 );
#endif

			break;
		}

		if( tmp == NULL ) {
			idl_free( idl );
			idl = NULL;
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
479
			LDAP_LOG( FILTER, INFO, "equality_candidates NULL\n", 0, 0, 0 );
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
#else
			Debug( LDAP_DEBUG_TRACE,
				"<= equality_candidates NULL\n",
			    0, 0, 0 );
#endif

			break;
		}

		save = idl;
		idl = idl_intersection( be, idl, tmp );
		idl_free( save );
		idl_free( tmp );

		if( idl == NULL ) break;
	}

	ber_bvarray_free( keys );

	ldbm_cache_close( be, db );


#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
503
504
505
	LDAP_LOG( FILTER, ENTRY, 
		   "equality_candidates: return %ld\n", 
		   idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
506
507
508
509
#else
	Debug( LDAP_DEBUG_TRACE, "<= equality_candidates %ld\n",
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
#endif
Kurt Zeilenga's avatar
Kurt Zeilenga committed
510
511
512
513

	return( idl );
}

514
static ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
515
516
approx_candidates(
    Backend	*be,
517
	AttributeAssertion *ava
Kurt Zeilenga's avatar
Kurt Zeilenga committed
518
519
)
{
520
521
522
523
524
525
	ID_BLOCK *idl;
	DBCache	*db;
	int i;
	int rc;
	char *dbname;
	slap_mask_t mask;
526
	struct berval prefix = {0, NULL};
527
528
529
530
	struct berval *keys = NULL;
	MatchingRule *mr;

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
531
	LDAP_LOG( FILTER, ENTRY, "approx_candidates: enter\n", 0, 0, 0 );
532
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
533
	Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 );
534
#endif
Kurt Zeilenga's avatar
Kurt Zeilenga committed
535

536
537
538
539
540
541
542
543

	idl = idl_allids( be );

	rc = index_param( be, ava->aa_desc, LDAP_FILTER_APPROX,
		&dbname, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
544
545
		LDAP_LOG( FILTER, ERR, 
			   "approx_candidates: index_param returned %d\n", rc, 0, 0 );
546
547
548
549
550
551
552
553
554
555
556
557
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= approx_candidates: index_param returned=%d\n",
			rc, 0, 0 );
#endif

		return idl;
	}

	if( dbname == NULL ) {
		/* not indexed */
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
558
		LDAP_LOG( FILTER, ERR, "approx_candidates: not indexed\n", 0, 0, 0 );
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
#else
		Debug( LDAP_DEBUG_ANY,
		    "<= approx_candidates: not indexed\n",
			0, 0, 0 );
#endif

		return idl;
	}

	mr = ava->aa_desc->ad_type->sat_approx;
	if( !mr ) {
		/* no approx matching rule, try equality matching rule */
		mr = ava->aa_desc->ad_type->sat_equality;
	}

	if( !mr ) {
		return idl;
	}

	if( !mr->smr_filter ) {
		return idl;
	}

	rc = (mr->smr_filter)(
		LDAP_FILTER_APPROX,
		mask,
		ava->aa_desc->ad_type->sat_syntax,
		mr,
		&prefix,
		&ava->aa_value,
		&keys );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
593
		LDAP_LOG( FILTER, ERR, 
594
			   "approx_candidates: (%s%s) MR filter failed (%d)\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
595
			   dbname, LDBM_SUFFIX, rc );
596
597
598
599
600
601
602
603
604
605
606
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= approx_candidates: (%s%s) MR filter failed (%d)\n",
			dbname, LDBM_SUFFIX, rc );
#endif

		return idl;
	}

	if( keys == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
607
		LDAP_LOG( FILTER, INFO, 
608
			   "approx_candidates: no keys (%s%s)\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
609
			   dbname, LDBM_SUFFIX, 0 );
610
611
612
613
614
615
616
617
618
619
620
621
622
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= approx_candidates: no keys (%s%s)\n",
			dbname, LDBM_SUFFIX, 0 );
#endif

		return idl;
	}

	db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
	
	if ( db == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
623
624
625
		LDAP_LOG( FILTER, ERR, 
			"approx_candidates db open failed (%s%s)\n", 
			dbname, LDBM_SUFFIX, 0 );
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
#else
		Debug( LDAP_DEBUG_ANY,
		    "<= approx_candidates db open failed (%s%s)\n",
			dbname, LDBM_SUFFIX, 0 );
#endif

		return idl;
	}

	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
		ID_BLOCK *save;
		ID_BLOCK *tmp;

		rc = key_read( be, db, &keys[i], &tmp );

		if( rc != LDAP_SUCCESS ) {
			idl_free( idl );
			idl = NULL;
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
645
646
			LDAP_LOG( FILTER, ERR, 
				   "approx_candidates: key read failed (%d)\n", rc, 0, 0 );
647
648
649
650
651
652
653
654
655
#else
			Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n",
			    rc, 0, 0 );
#endif

			break;
		}

		if( tmp == NULL ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
656
			idl_free( idl );
657
658
			idl = NULL;
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
659
			LDAP_LOG( FILTER, INFO, "approx_candidates: NULL\n", 0, 0, 0 );
660
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
661
662
			Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n",
			    0, 0, 0 );
663
#endif
Kurt Zeilenga's avatar
Kurt Zeilenga committed
664

665
			break;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
666
		}
667
668
669
670
671
672
673

		save = idl;
		idl = idl_intersection( be, idl, tmp );
		idl_free( save );
		idl_free( tmp );

		if( idl == NULL ) break;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
674
675
	}

676
677
678
679
680
	ber_bvarray_free( keys );

	ldbm_cache_close( be, db );

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
681
682
683
	LDAP_LOG( FILTER, ENTRY, 
		"approx_candidates: return %ld\n", 
		idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
684
685
686
687
688
#else
	Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n",
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
689
690
691
	return( idl );
}

692
static ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
693
694
695
696
697
698
list_candidates(
    Backend	*be,
    Filter	*flist,
    int		ftype
)
{
699
	ID_BLOCK	*idl, *tmp, *tmp2;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
700
701
	Filter	*f;

702
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
703
	LDAP_LOG( FILTER, ENTRY, "list_candidates: 0x%x\n", ftype, 0, 0 );
704
#else
Kurt Zeilenga's avatar
Kurt Zeilenga committed
705
	Debug( LDAP_DEBUG_TRACE, "=> list_candidates 0x%x\n", ftype, 0, 0 );
706
707
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
708
709
710
711
712

	idl = NULL;
	for ( f = flist; f != NULL; f = f->f_next ) {
		if ( (tmp = filter_candidates( be, f )) == NULL &&
		    ftype == LDAP_FILTER_AND ) {
713
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
714
			LDAP_LOG( FILTER, INFO, "list_candidates: NULL\n", 0, 0, 0 );
715
716
717
718
719
720
721
#else
			Debug( LDAP_DEBUG_TRACE,
			       "<= list_candidates NULL\n", 0, 0, 0 );
#endif

			idl_free( idl );
			return( NULL );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
		}

		tmp2 = idl;
		if ( idl == NULL ) {
			idl = tmp;
		} else if ( ftype == LDAP_FILTER_AND ) {
			idl = idl_intersection( be, idl, tmp );
			idl_free( tmp );
			idl_free( tmp2 );
		} else {
			idl = idl_union( be, idl, tmp );
			idl_free( tmp );
			idl_free( tmp2 );
		}
	}

738
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
739
740
	LDAP_LOG( FILTER, ENTRY, "list_candidates: return %ld\n",
		   idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
741
742
743
744
745
#else
	Debug( LDAP_DEBUG_TRACE, "<= list_candidates %ld\n",
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
#endif

Kurt Zeilenga's avatar
Kurt Zeilenga committed
746
747
748
	return( idl );
}

749
static ID_BLOCK *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
750
751
substring_candidates(
    Backend	*be,
752
    SubstringsAssertion	*sub
Kurt Zeilenga's avatar
Kurt Zeilenga committed
753
754
)
{
755
756
757
758
759
760
	ID_BLOCK *idl;
	DBCache	*db;
	int i;
	int rc;
	char *dbname;
	slap_mask_t mask;
761
	struct berval prefix = {0, NULL};
762
763
764
765
	struct berval *keys = NULL;
	MatchingRule *mr;

#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
766
	LDAP_LOG( FILTER, ENTRY, "substrings_candidates: enter\n", 0, 0, 0 );
767
768
769
770
771
772
773
774
775
776
777
778
#else
	Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 );
#endif


	idl = idl_allids( be );

	rc = index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS,
		&dbname, &mask, &prefix );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
779
780
		LDAP_LOG( FILTER, ERR, 
			   "substrings_candidates: index_param returned %d\n", rc, 0, 0 );
781
782
783
784
785
786
787
788
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= substrings_candidates: index_param returned=%d\n",
			rc, 0, 0 );
#endif

		return idl;
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
789

790
791
792
	if( dbname == NULL ) {
		/* not indexed */
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
793
		LDAP_LOG( FILTER, ERR, "substrings_candidates: not indexed\n", 0, 0, 0);
794
795
796
797
798
799
800
801
#else
		Debug( LDAP_DEBUG_ANY,
		    "<= substrings_candidates: not indexed\n",
			0, 0, 0 );
#endif

		return idl;
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
802

803
	mr = sub->sa_desc->ad_type->sat_substr;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
804

805
806
	if( !mr ) {
		return idl;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
807
808
	}

809
810
811
	if( !mr->smr_filter ) {
		return idl;
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
812

813
814
815
816
817
818
819
820
821
822
823
	rc = (mr->smr_filter)(
		LDAP_FILTER_SUBSTRINGS,
		mask,
		sub->sa_desc->ad_type->sat_syntax,
		mr,
		&prefix,
		sub,
		&keys );

	if( rc != LDAP_SUCCESS ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
824
		LDAP_LOG( FILTER, ERR, 
825
			   "substrings_candidates: (%s%s) MR filter failed (%d)\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
826
			   dbname, LDBM_SUFFIX, rc );
827
828
829
830
831
832
833
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= substrings_candidates: (%s%s) MR filter failed (%d)\n",
			dbname, LDBM_SUFFIX, rc );
#endif

		return idl;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
834
835
	}

836
837
	if( keys == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
838
		LDAP_LOG( FILTER, ERR, 
839
			   "substrings_candidates: (0x%04lx) no keys (%s%s)\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
840
			   mask, dbname, LDBM_SUFFIX );
841
842
843
844
845
846
847
848
#else
		Debug( LDAP_DEBUG_TRACE,
		    "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n",
			mask, dbname, LDBM_SUFFIX );
#endif

		return idl;
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
849

850
851
852
853
	db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_WRCREAT );
	
	if ( db == NULL ) {
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
854
		LDAP_LOG( FILTER, ERR, 
855
			   "substrings_candidates: db open failed (%s%s)\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
856
			   dbname, LDBM_SUFFIX, 0 );
857
858
859
860
861
862
863
#else
		Debug( LDAP_DEBUG_ANY,
		    "<= substrings_candidates db open failed (%s%s)\n",
			dbname, LDBM_SUFFIX, 0 );
#endif

		return idl;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
864
865
	}

866
867
868
	for ( i= 0; keys[i].bv_val != NULL; i++ ) {
		ID_BLOCK *save;
		ID_BLOCK *tmp;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
869

870
		rc = key_read( be, db, &keys[i], &tmp );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
871

872
873
874
875
		if( rc != LDAP_SUCCESS ) {
			idl_free( idl );
			idl = NULL;
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
876
877
			LDAP_LOG( FILTER, ERR, 
				   "substrings_candidates: key read failed (%d)\n", rc, 0, 0 );
878
879
880
881
882
883
884
#else
			Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n",
			    rc, 0, 0 );
#endif

			break;
		}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
885

886
887
888
889
		if( tmp == NULL ) {
			idl_free( idl );
			idl = NULL;
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
890
			LDAP_LOG( FILTER, INFO, "substrings_candidates: NULL\n", 0, 0, 0 );
891
892
893
894
#else
			Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n",
			    0, 0, 0 );
#endif
Kurt Zeilenga's avatar
Kurt Zeilenga committed
895

896
			break;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
897
898
		}

899
900
901
902
		save = idl;
		idl = idl_intersection( be, idl, tmp );
		idl_free( save );
		idl_free( tmp );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
903

904
		if( idl == NULL ) break;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
905
906
	}

907
	ber_bvarray_free( keys );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
908

909
	ldbm_cache_close( be, db );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
910

911
#ifdef NEW_LOGGING
Kurt Zeilenga's avatar
Kurt Zeilenga committed
912
	LDAP_LOG( FILTER, ENTRY, 
913
		   "substrings_candidates: return %ld\n",
Kurt Zeilenga's avatar
Kurt Zeilenga committed
914
		   idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
915
916
917
918
#else
	Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n",
	    idl ? ID_BLOCK_NIDS(idl) : 0, 0, 0 );
#endif
Kurt Zeilenga's avatar
Kurt Zeilenga committed
919
920
921

	return( idl );
}