]> git.sur5r.net Git - openldap/blob - servers/slapd/sets.c
e7c807cf256de636238f9a646e591d94ae249eb9
[openldap] / servers / slapd / sets.c
1 /* $OpenLDAP$ */
2 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
3  *
4  * Copyright 2000-2007 The OpenLDAP Foundation.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted only as authorized by the OpenLDAP
9  * Public License.
10  *
11  * A copy of this license is available in the file LICENSE in the
12  * top-level directory of the distribution or, alternatively, at
13  * <http://www.OpenLDAP.org/license.html>.
14  */
15
16 #include "portable.h"
17
18 #include <stdio.h>
19 #include <ac/string.h>
20
21 #include "slap.h"
22 #include "sets.h"
23
24 static BerVarray set_chase( SLAP_SET_GATHER gatherer,
25         SetCookie *cookie, BerVarray set, AttributeDescription *desc, int closure );
26
27 static long
28 slap_set_size( BerVarray set )
29 {
30         long    i;
31
32         i = 0;
33         if ( set != NULL ) {
34                 while ( !BER_BVISNULL( &set[ i ] ) ) {
35                         i++;
36                 }
37         }
38         return i;
39 }
40
41 static int
42 slap_set_isempty( BerVarray set )
43 {
44         if ( set == NULL ) {
45                 return 1;
46         }
47
48         if ( !BER_BVISNULL( &set[ 0 ] ) ) {
49                 return 0;
50         }
51
52         return 1;
53 }
54
55 static void
56 slap_set_dispose( SetCookie *cp, BerVarray set, unsigned flags )
57 {
58         if ( flags & SLAP_SET_REFVAL ) {
59                 if ( ! ( flags & SLAP_SET_REFARR ) ) {
60                         cp->set_op->o_tmpfree( set, cp->set_op->o_tmpmemctx );
61                 }
62
63         } else {
64                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
65         }
66 }
67
68 static BerVarray
69 set_dup( SetCookie *cp, BerVarray set, unsigned flags )
70 {
71         BerVarray       newset = NULL;
72
73         if ( set == NULL ) {
74                 return NULL;
75         }
76
77         if ( flags & SLAP_SET_REFARR ) {
78                 int     i;
79
80                 for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ )
81                         ;
82                 newset = cp->set_op->o_tmpcalloc( i + 1,
83                                 sizeof( struct berval ), 
84                                 cp->set_op->o_tmpmemctx );
85                 if ( newset == NULL ) {
86                         return NULL;
87                 }
88
89                 if ( flags & SLAP_SET_REFVAL ) {
90                         for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
91                                 ber_dupbv_x( &newset[ i ], &set[ i ],
92                                                 cp->set_op->o_tmpmemctx );
93                         }
94
95                 } else {
96                         AC_MEMCPY( newset, set, ( i + 1 ) * sizeof( struct berval ) );
97                 }
98                 
99         } else {
100                 newset = set;
101         }
102
103         return newset;
104 }
105
106 BerVarray
107 slap_set_join(
108         SetCookie       *cp,
109         BerVarray       lset,
110         unsigned        op_flags,
111         BerVarray       rset )
112 {
113         BerVarray       set;
114         long            i, j, last, rlast;
115         unsigned        op = ( op_flags & SLAP_SET_OPMASK );
116
117         set = NULL;
118         switch ( op ) {
119         case '|':       /* union */
120                 if ( lset == NULL || BER_BVISNULL( &lset[ 0 ] ) ) {
121                         if ( rset == NULL ) {
122                                 if ( lset == NULL ) {
123                                         set = cp->set_op->o_tmpcalloc( 1,
124                                                         sizeof( struct berval ),
125                                                         cp->set_op->o_tmpmemctx );
126                                         BER_BVZERO( &set[ 0 ] );
127                                         return set;
128                                 }
129                                 return set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
130                         }
131                         slap_set_dispose( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
132                         return set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
133                 }
134                 if ( rset == NULL || BER_BVISNULL( &rset[ 0 ] ) ) {
135                         slap_set_dispose( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
136                         return set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
137                 }
138
139                 /* worst scenario: no duplicates */
140                 rlast = slap_set_size( rset );
141                 i = slap_set_size( lset ) + rlast + 1;
142                 set = cp->set_op->o_tmpcalloc( i, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
143                 if ( set != NULL ) {
144                         /* set_chase() depends on this routine to
145                          * keep the first elements of the result
146                          * set the same (and in the same order)
147                          * as the left-set.
148                          */
149                         for ( i = 0; !BER_BVISNULL( &lset[ i ] ); i++ ) {
150                                 if ( op_flags & SLAP_SET_LREFVAL ) {
151                                         ber_dupbv_x( &set[ i ], &lset[ i ], cp->set_op->o_tmpmemctx );
152
153                                 } else {
154                                         set[ i ] = lset[ i ];
155                                 }
156                         }
157
158                         /* pointers to values have been used in set - don't free twice */
159                         op_flags |= SLAP_SET_LREFVAL;
160
161                         last = i;
162
163                         for ( i = 0; !BER_BVISNULL( &rset[ i ] ); i++ ) {
164                                 int     exists = 0;
165
166                                 for ( j = 0; !BER_BVISNULL( &set[ j ] ); j++ ) {
167                                         if ( bvmatch( &rset[ i ], &set[ j ] ) )
168                                         {
169                                                 if ( !( op_flags & SLAP_SET_RREFVAL ) ) {
170                                                         cp->set_op->o_tmpfree( rset[ i ].bv_val, cp->set_op->o_tmpmemctx );
171                                                         rset[ i ] = rset[ --rlast ];
172                                                         BER_BVZERO( &rset[ rlast ] );
173                                                 }
174                                                 exists = 1;
175                                                 break;
176                                         }
177                                 }
178
179                                 if ( !exists ) {
180                                         if ( op_flags & SLAP_SET_RREFVAL ) {
181                                                 ber_dupbv_x( &set[ last ], &rset[ i ], cp->set_op->o_tmpmemctx );
182
183                                         } else {
184                                                 set[ last ] = rset[ i ];
185                                         }
186                                         last++;
187                                 }
188                         }
189
190                         /* pointers to values have been used in set - don't free twice */
191                         op_flags |= SLAP_SET_RREFVAL;
192
193                         BER_BVZERO( &set[ last ] );
194                 }
195                 break;
196
197         case '&':       /* intersection */
198                 if ( lset == NULL || BER_BVISNULL( &lset[ 0 ] )
199                         || rset == NULL || BER_BVISNULL( &rset[ 0 ] ) )
200                 {
201                         set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
202                                         cp->set_op->o_tmpmemctx );
203                         BER_BVZERO( &set[ 0 ] );
204                         break;
205
206                 } else {
207                         long llen, rlen;
208                         BerVarray sset;
209
210                         llen = slap_set_size( lset );
211                         rlen = slap_set_size( rset );
212
213                         /* dup the shortest */
214                         if ( llen < rlen ) {
215                                 set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
216                                 lset = NULL;
217                                 sset = rset;
218
219                         } else {
220                                 set = set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
221                                 rset = NULL;
222                                 sset = lset;
223                         }
224
225                         if ( set == NULL ) {
226                                 break;
227                         }
228
229                         last = slap_set_size( set );
230                         for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
231                                 for ( j = 0; !BER_BVISNULL( &sset[ j ] ); j++ ) {
232                                         if ( bvmatch( &set[ i ], &sset[ j ] ) ) {
233                                                 break;
234                                         }
235                                 }
236
237                                 if ( BER_BVISNULL( &sset[ j ] ) ) {
238                                         cp->set_op->o_tmpfree( set[ i ].bv_val, cp->set_op->o_tmpmemctx );
239                                         set[ i ] = set[ --last ];
240                                         BER_BVZERO( &set[ last ] );
241                                         i--;
242                                 }
243                         }
244                 }
245                 break;
246
247         case '+':       /* string concatenation */
248                 i = slap_set_size( rset );
249                 j = slap_set_size( lset );
250
251                 /* handle empty set cases */
252                 if ( i == 0 ) {
253                         if ( j == 0 ) {
254                                 set = cp->set_op->o_tmpcalloc( i * j + 1, sizeof( struct berval ),
255                                                 cp->set_op->o_tmpmemctx );
256                                 if ( set == NULL ) {
257                                         break;
258                                 }
259                                 BER_BVZERO( &set[ 0 ] );
260                                 break;
261
262                         } else {
263                                 set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
264                                 break;
265                         }
266
267                 } else if ( j == 0 ) {
268                         set = set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
269                         break;
270                 }
271
272                 set = cp->set_op->o_tmpcalloc( i * j + 1, sizeof( struct berval ),
273                                 cp->set_op->o_tmpmemctx );
274                 if ( set == NULL ) {
275                         break;
276                 }
277
278                 for ( last = 0, i = 0; !BER_BVISNULL( &lset[ i ] ); i++ ) {
279                         for ( j = 0; !BER_BVISNULL( &rset[ j ] ); j++ ) {
280                                 struct berval   bv;
281                                 long            k;
282
283                                 /* don't concatenate with the empty string */
284                                 if ( BER_BVISEMPTY( &lset[ i ] ) ) {
285                                         ber_dupbv_x( &bv, &rset[ j ], cp->set_op->o_tmpmemctx );
286                                         if ( bv.bv_val == NULL ) {
287                                                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
288                                                 set = NULL;
289                                                 goto done;
290                                         }
291
292                                 } else if ( BER_BVISEMPTY( &rset[ j ] ) ) {
293                                         ber_dupbv_x( &bv, &lset[ i ], cp->set_op->o_tmpmemctx );
294                                         if ( bv.bv_val == NULL ) {
295                                                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
296                                                 set = NULL;
297                                                 goto done;
298                                         }
299
300                                 } else {
301                                         bv.bv_len = lset[ i ].bv_len + rset[ j ].bv_len;
302                                         bv.bv_val = cp->set_op->o_tmpalloc( bv.bv_len + 1,
303                                                         cp->set_op->o_tmpmemctx );
304                                         if ( bv.bv_val == NULL ) {
305                                                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
306                                                 set = NULL;
307                                                 goto done;
308                                         }
309                                         AC_MEMCPY( bv.bv_val, lset[ i ].bv_val, lset[ i ].bv_len );
310                                         AC_MEMCPY( &bv.bv_val[ lset[ i ].bv_len ], rset[ j ].bv_val, rset[ j ].bv_len );
311                                         bv.bv_val[ bv.bv_len ] = '\0';
312                                 }
313
314                                 for ( k = 0; k < last; k++ ) {
315                                         if ( bvmatch( &set[ k ], &bv ) ) {
316                                                 cp->set_op->o_tmpfree( bv.bv_val, cp->set_op->o_tmpmemctx );
317                                                 break;
318                                         }
319                                 }
320
321                                 if ( k == last ) {
322                                         set[ last++ ] = bv;
323                                 }
324                         }
325                 }
326                 BER_BVZERO( &set[ last ] );
327                 break;
328
329         default:
330                 break;
331         }
332
333 done:;
334         if ( lset ) slap_set_dispose( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
335         if ( rset ) slap_set_dispose( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
336
337         return set;
338 }
339
340 static BerVarray
341 set_chase( SLAP_SET_GATHER gatherer,
342         SetCookie *cp, BerVarray set, AttributeDescription *desc, int closure )
343 {
344         BerVarray       vals, nset;
345         int             i;
346
347         if ( set == NULL ) {
348                 set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
349                                 cp->set_op->o_tmpmemctx );
350                 if ( set != NULL ) {
351                         BER_BVZERO( &set[ 0 ] );
352                 }
353                 return set;
354         }
355
356         if ( BER_BVISNULL( set ) ) {
357                 return set;
358         }
359
360         nset = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
361         if ( nset == NULL ) {
362                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
363                 return NULL;
364         }
365         for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
366                 vals = gatherer( cp, &set[ i ], desc );
367                 if ( vals != NULL ) {
368                         nset = slap_set_join( cp, nset, '|', vals );
369                 }
370         }
371         ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
372
373         if ( closure ) {
374                 for ( i = 0; !BER_BVISNULL( &nset[ i ] ); i++ ) {
375                         vals = gatherer( cp, &nset[ i ], desc );
376                         if ( vals != NULL ) {
377                                 nset = slap_set_join( cp, nset, '|', vals );
378                                 if ( nset == NULL ) {
379                                         break;
380                                 }
381                         }
382                 }
383         }
384
385         return nset;
386 }
387
388 int
389 slap_set_filter( SLAP_SET_GATHER gatherer,
390         SetCookie *cp, struct berval *fbv,
391         struct berval *user, struct berval *target, BerVarray *results )
392 {
393 #define STACK_SIZE      64
394 #define IS_SET(x)       ( (unsigned long)(x) >= 256 )
395 #define IS_OP(x)        ( (unsigned long)(x) < 256 )
396 #define SF_ERROR(x)     do { rc = -1; goto _error; } while ( 0 )
397 #define SF_TOP()        ( (BerVarray)( ( stp < 0 ) ? 0 : stack[ stp ] ) )
398 #define SF_POP()        ( (BerVarray)( ( stp < 0 ) ? 0 : stack[ stp-- ] ) )
399 #define SF_PUSH(x)      do { \
400                 if ( stp >= ( STACK_SIZE - 1 ) ) SF_ERROR( overflow ); \
401                 stack[ ++stp ] = (BerVarray)(long)(x); \
402         } while ( 0 )
403
404         BerVarray       set, lset;
405         BerVarray       stack[ STACK_SIZE ] = { 0 };
406         int             len, rc, stp;
407         unsigned long   op;
408         char            c, *filter = fbv->bv_val;
409
410         if ( results ) {
411                 *results = NULL;
412         }
413
414         stp = -1;
415         while ( ( c = *filter++ ) ) {
416                 set = NULL;
417                 switch ( c ) {
418                 case ' ':
419                 case '\t':
420                 case '\x0A':
421                 case '\x0D':
422                         break;
423
424                 case '(' /* ) */ :
425                         if ( IS_SET( SF_TOP() ) ) {
426                                 SF_ERROR( syntax );
427                         }
428                         SF_PUSH( c );
429                         break;
430
431                 case /* ( */ ')':
432                         set = SF_POP();
433                         if ( IS_OP( set ) ) {
434                                 SF_ERROR( syntax );
435                         }
436                         if ( SF_TOP() == (void *)'(' /* ) */ ) {
437                                 SF_POP();
438                                 SF_PUSH( set );
439                                 set = NULL;
440
441                         } else if ( IS_OP( SF_TOP() ) ) {
442                                 op = (unsigned long)SF_POP();
443                                 lset = SF_POP();
444                                 SF_POP();
445                                 set = slap_set_join( cp, lset, op, set );
446                                 if ( set == NULL ) {
447                                         SF_ERROR( memory );
448                                 }
449                                 SF_PUSH( set );
450                                 set = NULL;
451
452                         } else {
453                                 SF_ERROR( syntax );
454                         }
455                         break;
456
457                 case '|':       /* union */
458                 case '&':       /* intersection */
459                 case '+':       /* string concatenation */
460                         set = SF_POP();
461                         if ( IS_OP( set ) ) {
462                                 SF_ERROR( syntax );
463                         }
464                         if ( SF_TOP() == 0 || SF_TOP() == (void *)'(' /* ) */ ) {
465                                 SF_PUSH( set );
466                                 set = NULL;
467
468                         } else if ( IS_OP( SF_TOP() ) ) {
469                                 op = (unsigned long)SF_POP();
470                                 lset = SF_POP();
471                                 set = slap_set_join( cp, lset, op, set );
472                                 if ( set == NULL ) {
473                                         SF_ERROR( memory );
474                                 }
475                                 SF_PUSH( set );
476                                 set = NULL;
477                                 
478                         } else {
479                                 SF_ERROR( syntax );
480                         }
481                         SF_PUSH( c );
482                         break;
483
484                 case '[' /* ] */:
485                         if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
486                                 SF_ERROR( syntax );
487                         }
488                         for ( len = 0; ( c = *filter++ ) && ( c != /* [ */ ']' ); len++ )
489                                 ;
490                         if ( c == 0 ) {
491                                 SF_ERROR( syntax );
492                         }
493                         
494                         set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
495                                         cp->set_op->o_tmpmemctx );
496                         if ( set == NULL ) {
497                                 SF_ERROR( memory );
498                         }
499                         set->bv_val = cp->set_op->o_tmpcalloc( len + 1, sizeof( char ),
500                                         cp->set_op->o_tmpmemctx );
501                         if ( BER_BVISNULL( set ) ) {
502                                 SF_ERROR( memory );
503                         }
504                         AC_MEMCPY( set->bv_val, &filter[ - len - 1 ], len );
505                         set->bv_len = len;
506                         SF_PUSH( set );
507                         set = NULL;
508                         break;
509
510                 case '-':
511                         c = *filter++;
512                         if ( c != '>' ) {
513                                 SF_ERROR( syntax );
514                         }
515                         /* fall through to next case */
516
517                 case '/':
518                         if ( IS_OP( SF_TOP() ) ) {
519                                 SF_ERROR( syntax );
520                         }
521                         SF_PUSH( '/' );
522                         break;
523
524                 default:
525                         if ( ( c != '_' )
526                                         && ( c < 'A' || c > 'Z' )
527                                         && ( c < 'a' || c > 'z' ) )
528                         {
529                                 SF_ERROR( syntax );
530                         }
531                         filter--;
532                         for ( len = 1;
533                                         ( c = filter[ len ] )
534                                                 && ( ( c >= '0' && c <= '9' )
535                                                         || ( c >= 'A' && c <= 'Z' )
536                                                         || ( c >= 'a' && c <= 'z' ) );
537                                         len++ )
538                                 /* count */ ;
539                         if ( len == 4
540                                 && memcmp( "this", filter, len ) == 0 )
541                         {
542                                 if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
543                                         SF_ERROR( syntax );
544                                 }
545                                 set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
546                                                 cp->set_op->o_tmpmemctx );
547                                 if ( set == NULL ) {
548                                         SF_ERROR( memory );
549                                 }
550                                 ber_dupbv_x( set, target, cp->set_op->o_tmpmemctx );
551                                 if ( BER_BVISNULL( set ) ) {
552                                         SF_ERROR( memory );
553                                 }
554                                 BER_BVZERO( &set[ 1 ] );
555                                 
556                         } else if ( len == 4
557                                 && memcmp( "user", filter, len ) == 0 ) 
558                         {
559                                 if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
560                                         SF_ERROR( syntax );
561                                 }
562                                 set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
563                                                 cp->set_op->o_tmpmemctx );
564                                 if ( set == NULL ) {
565                                         SF_ERROR( memory );
566                                 }
567                                 ber_dupbv_x( set, user, cp->set_op->o_tmpmemctx );
568                                 if ( BER_BVISNULL( set ) ) {
569                                         SF_ERROR( memory );
570                                 }
571                                 BER_BVZERO( &set[ 1 ] );
572                                 
573                         } else if ( SF_TOP() != (void *)'/' ) {
574                                 SF_ERROR( syntax );
575
576                         } else {
577                                 struct berval           fb2;
578                                 AttributeDescription    *ad = NULL;
579                                 const char              *text = NULL;
580
581                                 SF_POP();
582                                 fb2.bv_val = filter;
583                                 fb2.bv_len = len;
584
585                                 if ( slap_bv2ad( &fb2, &ad, &text ) != LDAP_SUCCESS ) {
586                                         SF_ERROR( syntax );
587                                 }
588
589                                 /* NOTE: ad must have distinguishedName syntax
590                                  * or expand in an LDAP URI if c == '*'
591                                  */
592                                 
593                                 set = set_chase( gatherer,
594                                         cp, SF_POP(), ad, c == '*' );
595                                 if ( set == NULL ) {
596                                         SF_ERROR( memory );
597                                 }
598                                 if ( c == '*' ) {
599                                         len++;
600                                 }
601                         }
602                         filter += len;
603                         SF_PUSH( set );
604                         set = NULL;
605                         break;
606                 }
607         }
608
609         set = SF_POP();
610         if ( IS_OP( set ) ) {
611                 SF_ERROR( syntax );
612         }
613         if ( SF_TOP() == 0 ) {
614                 /* FIXME: ok ? */ ;
615
616         } else if ( IS_OP( SF_TOP() ) ) {
617                 op = (unsigned long)SF_POP();
618                 lset = SF_POP();
619                 set = slap_set_join( cp, lset, op, set );
620                 if ( set == NULL ) {
621                         SF_ERROR( memory );
622                 }
623                 
624         } else {
625                 SF_ERROR( syntax );
626         }
627
628         rc = slap_set_isempty( set ) ? 0 : 1;
629         if ( results ) {
630                 *results = set;
631                 set = NULL;
632         }
633
634 _error:
635         if ( IS_SET( set ) ) {
636                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
637         }
638         while ( ( set = SF_POP() ) ) {
639                 if ( IS_SET( set ) ) {
640                         ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
641                 }
642         }
643         return rc;
644 }