]> git.sur5r.net Git - openldap/blob - servers/slapd/sets.c
import fix to ITS#4860
[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                                 last = llen;
216                                 set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
217                                 lset = NULL;
218                                 sset = rset;
219
220                         } else {
221                                 last = rlen;
222                                 set = set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
223                                 rset = NULL;
224                                 sset = lset;
225                         }
226
227                         if ( set == NULL ) {
228                                 break;
229                         }
230
231                         for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
232                                 for ( j = 0; !BER_BVISNULL( &sset[ j ] ); j++ ) {
233                                         if ( bvmatch( &set[ i ], &sset[ j ] ) ) {
234                                                 break;
235                                         }
236                                 }
237
238                                 if ( BER_BVISNULL( &sset[ j ] ) ) {
239                                         cp->set_op->o_tmpfree( set[ i ].bv_val, cp->set_op->o_tmpmemctx );
240                                         set[ i ] = set[ --last ];
241                                         BER_BVZERO( &set[ last ] );
242                                         i--;
243                                 }
244                         }
245                 }
246                 break;
247
248         case '+':       /* string concatenation */
249                 i = slap_set_size( rset );
250                 j = slap_set_size( lset );
251
252                 /* handle empty set cases */
253                 if ( i == 0 ) {
254                         if ( j == 0 ) {
255                                 set = cp->set_op->o_tmpcalloc( i * j + 1, sizeof( struct berval ),
256                                                 cp->set_op->o_tmpmemctx );
257                                 if ( set == NULL ) {
258                                         break;
259                                 }
260                                 BER_BVZERO( &set[ 0 ] );
261                                 break;
262
263                         } else {
264                                 set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
265                                 lset = NULL;
266                                 break;
267                         }
268
269                 } else if ( j == 0 ) {
270                         set = set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
271                         rset = NULL;
272                         break;
273                 }
274
275                 set = cp->set_op->o_tmpcalloc( i * j + 1, sizeof( struct berval ),
276                                 cp->set_op->o_tmpmemctx );
277                 if ( set == NULL ) {
278                         break;
279                 }
280
281                 for ( last = 0, i = 0; !BER_BVISNULL( &lset[ i ] ); i++ ) {
282                         for ( j = 0; !BER_BVISNULL( &rset[ j ] ); j++ ) {
283                                 struct berval   bv;
284                                 long            k;
285
286                                 /* don't concatenate with the empty string */
287                                 if ( BER_BVISEMPTY( &lset[ i ] ) ) {
288                                         ber_dupbv_x( &bv, &rset[ j ], cp->set_op->o_tmpmemctx );
289                                         if ( bv.bv_val == NULL ) {
290                                                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
291                                                 set = NULL;
292                                                 goto done;
293                                         }
294
295                                 } else if ( BER_BVISEMPTY( &rset[ j ] ) ) {
296                                         ber_dupbv_x( &bv, &lset[ i ], cp->set_op->o_tmpmemctx );
297                                         if ( bv.bv_val == NULL ) {
298                                                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
299                                                 set = NULL;
300                                                 goto done;
301                                         }
302
303                                 } else {
304                                         bv.bv_len = lset[ i ].bv_len + rset[ j ].bv_len;
305                                         bv.bv_val = cp->set_op->o_tmpalloc( bv.bv_len + 1,
306                                                         cp->set_op->o_tmpmemctx );
307                                         if ( bv.bv_val == NULL ) {
308                                                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
309                                                 set = NULL;
310                                                 goto done;
311                                         }
312                                         AC_MEMCPY( bv.bv_val, lset[ i ].bv_val, lset[ i ].bv_len );
313                                         AC_MEMCPY( &bv.bv_val[ lset[ i ].bv_len ], rset[ j ].bv_val, rset[ j ].bv_len );
314                                         bv.bv_val[ bv.bv_len ] = '\0';
315                                 }
316
317                                 for ( k = 0; k < last; k++ ) {
318                                         if ( bvmatch( &set[ k ], &bv ) ) {
319                                                 cp->set_op->o_tmpfree( bv.bv_val, cp->set_op->o_tmpmemctx );
320                                                 break;
321                                         }
322                                 }
323
324                                 if ( k == last ) {
325                                         set[ last++ ] = bv;
326                                 }
327                         }
328                 }
329                 BER_BVZERO( &set[ last ] );
330                 break;
331
332         default:
333                 break;
334         }
335
336 done:;
337         if ( lset ) slap_set_dispose( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
338         if ( rset ) slap_set_dispose( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
339
340         return set;
341 }
342
343 static BerVarray
344 set_chase( SLAP_SET_GATHER gatherer,
345         SetCookie *cp, BerVarray set, AttributeDescription *desc, int closure )
346 {
347         BerVarray       vals, nset;
348         int             i;
349
350         if ( set == NULL ) {
351                 set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
352                                 cp->set_op->o_tmpmemctx );
353                 if ( set != NULL ) {
354                         BER_BVZERO( &set[ 0 ] );
355                 }
356                 return set;
357         }
358
359         if ( BER_BVISNULL( set ) ) {
360                 return set;
361         }
362
363         nset = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
364         if ( nset == NULL ) {
365                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
366                 return NULL;
367         }
368         for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
369                 vals = gatherer( cp, &set[ i ], desc );
370                 if ( vals != NULL ) {
371                         nset = slap_set_join( cp, nset, '|', vals );
372                 }
373         }
374         ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
375
376         if ( closure ) {
377                 for ( i = 0; !BER_BVISNULL( &nset[ i ] ); i++ ) {
378                         vals = gatherer( cp, &nset[ i ], desc );
379                         if ( vals != NULL ) {
380                                 nset = slap_set_join( cp, nset, '|', vals );
381                                 if ( nset == NULL ) {
382                                         break;
383                                 }
384                         }
385                 }
386         }
387
388         return nset;
389 }
390
391 int
392 slap_set_filter( SLAP_SET_GATHER gatherer,
393         SetCookie *cp, struct berval *fbv,
394         struct berval *user, struct berval *target, BerVarray *results )
395 {
396 #define STACK_SIZE      64
397 #define IS_SET(x)       ( (unsigned long)(x) >= 256 )
398 #define IS_OP(x)        ( (unsigned long)(x) < 256 )
399 #define SF_ERROR(x)     do { rc = -1; goto _error; } while ( 0 )
400 #define SF_TOP()        ( (BerVarray)( ( stp < 0 ) ? 0 : stack[ stp ] ) )
401 #define SF_POP()        ( (BerVarray)( ( stp < 0 ) ? 0 : stack[ stp-- ] ) )
402 #define SF_PUSH(x)      do { \
403                 if ( stp >= ( STACK_SIZE - 1 ) ) SF_ERROR( overflow ); \
404                 stack[ ++stp ] = (BerVarray)(long)(x); \
405         } while ( 0 )
406
407         BerVarray       set, lset;
408         BerVarray       stack[ STACK_SIZE ] = { 0 };
409         int             len, rc, stp;
410         unsigned long   op;
411         char            c, *filter = fbv->bv_val;
412
413         if ( results ) {
414                 *results = NULL;
415         }
416
417         stp = -1;
418         while ( ( c = *filter++ ) ) {
419                 set = NULL;
420                 switch ( c ) {
421                 case ' ':
422                 case '\t':
423                 case '\x0A':
424                 case '\x0D':
425                         break;
426
427                 case '(' /* ) */ :
428                         if ( IS_SET( SF_TOP() ) ) {
429                                 SF_ERROR( syntax );
430                         }
431                         SF_PUSH( c );
432                         break;
433
434                 case /* ( */ ')':
435                         set = SF_POP();
436                         if ( IS_OP( set ) ) {
437                                 SF_ERROR( syntax );
438                         }
439                         if ( SF_TOP() == (void *)'(' /* ) */ ) {
440                                 SF_POP();
441                                 SF_PUSH( set );
442                                 set = NULL;
443
444                         } else if ( IS_OP( SF_TOP() ) ) {
445                                 op = (unsigned long)SF_POP();
446                                 lset = SF_POP();
447                                 SF_POP();
448                                 set = slap_set_join( cp, lset, op, set );
449                                 if ( set == NULL ) {
450                                         SF_ERROR( memory );
451                                 }
452                                 SF_PUSH( set );
453                                 set = NULL;
454
455                         } else {
456                                 SF_ERROR( syntax );
457                         }
458                         break;
459
460                 case '|':       /* union */
461                 case '&':       /* intersection */
462                 case '+':       /* string concatenation */
463                         set = SF_POP();
464                         if ( IS_OP( set ) ) {
465                                 SF_ERROR( syntax );
466                         }
467                         if ( SF_TOP() == 0 || SF_TOP() == (void *)'(' /* ) */ ) {
468                                 SF_PUSH( set );
469                                 set = NULL;
470
471                         } else if ( IS_OP( SF_TOP() ) ) {
472                                 op = (unsigned long)SF_POP();
473                                 lset = SF_POP();
474                                 set = slap_set_join( cp, lset, op, set );
475                                 if ( set == NULL ) {
476                                         SF_ERROR( memory );
477                                 }
478                                 SF_PUSH( set );
479                                 set = NULL;
480                                 
481                         } else {
482                                 SF_ERROR( syntax );
483                         }
484                         SF_PUSH( c );
485                         break;
486
487                 case '[' /* ] */:
488                         if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
489                                 SF_ERROR( syntax );
490                         }
491                         for ( len = 0; ( c = *filter++ ) && ( c != /* [ */ ']' ); len++ )
492                                 ;
493                         if ( c == 0 ) {
494                                 SF_ERROR( syntax );
495                         }
496                         
497                         set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
498                                         cp->set_op->o_tmpmemctx );
499                         if ( set == NULL ) {
500                                 SF_ERROR( memory );
501                         }
502                         set->bv_val = cp->set_op->o_tmpcalloc( len + 1, sizeof( char ),
503                                         cp->set_op->o_tmpmemctx );
504                         if ( BER_BVISNULL( set ) ) {
505                                 SF_ERROR( memory );
506                         }
507                         AC_MEMCPY( set->bv_val, &filter[ - len - 1 ], len );
508                         set->bv_len = len;
509                         SF_PUSH( set );
510                         set = NULL;
511                         break;
512
513                 case '-':
514                         c = *filter++;
515                         if ( c != '>' ) {
516                                 SF_ERROR( syntax );
517                         }
518                         /* fall through to next case */
519
520                 case '/':
521                         if ( IS_OP( SF_TOP() ) ) {
522                                 SF_ERROR( syntax );
523                         }
524                         SF_PUSH( '/' );
525                         break;
526
527                 default:
528                         if ( ( c != '_' )
529                                         && ( c < 'A' || c > 'Z' )
530                                         && ( c < 'a' || c > 'z' ) )
531                         {
532                                 SF_ERROR( syntax );
533                         }
534                         filter--;
535                         for ( len = 1;
536                                         ( c = filter[ len ] )
537                                                 && ( ( c >= '0' && c <= '9' )
538                                                         || ( c >= 'A' && c <= 'Z' )
539                                                         || ( c >= 'a' && c <= 'z' ) );
540                                         len++ )
541                                 /* count */ ;
542                         if ( len == 4
543                                 && memcmp( "this", filter, len ) == 0 )
544                         {
545                                 if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
546                                         SF_ERROR( syntax );
547                                 }
548                                 set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
549                                                 cp->set_op->o_tmpmemctx );
550                                 if ( set == NULL ) {
551                                         SF_ERROR( memory );
552                                 }
553                                 ber_dupbv_x( set, target, cp->set_op->o_tmpmemctx );
554                                 if ( BER_BVISNULL( set ) ) {
555                                         SF_ERROR( memory );
556                                 }
557                                 BER_BVZERO( &set[ 1 ] );
558                                 
559                         } else if ( len == 4
560                                 && memcmp( "user", filter, len ) == 0 ) 
561                         {
562                                 if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
563                                         SF_ERROR( syntax );
564                                 }
565                                 set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
566                                                 cp->set_op->o_tmpmemctx );
567                                 if ( set == NULL ) {
568                                         SF_ERROR( memory );
569                                 }
570                                 ber_dupbv_x( set, user, cp->set_op->o_tmpmemctx );
571                                 if ( BER_BVISNULL( set ) ) {
572                                         SF_ERROR( memory );
573                                 }
574                                 BER_BVZERO( &set[ 1 ] );
575                                 
576                         } else if ( SF_TOP() != (void *)'/' ) {
577                                 SF_ERROR( syntax );
578
579                         } else {
580                                 struct berval           fb2;
581                                 AttributeDescription    *ad = NULL;
582                                 const char              *text = NULL;
583
584                                 SF_POP();
585                                 fb2.bv_val = filter;
586                                 fb2.bv_len = len;
587
588                                 if ( slap_bv2ad( &fb2, &ad, &text ) != LDAP_SUCCESS ) {
589                                         SF_ERROR( syntax );
590                                 }
591
592                                 /* NOTE: ad must have distinguishedName syntax
593                                  * or expand in an LDAP URI if c == '*'
594                                  */
595                                 
596                                 set = set_chase( gatherer,
597                                         cp, SF_POP(), ad, c == '*' );
598                                 if ( set == NULL ) {
599                                         SF_ERROR( memory );
600                                 }
601                                 if ( c == '*' ) {
602                                         len++;
603                                 }
604                         }
605                         filter += len;
606                         SF_PUSH( set );
607                         set = NULL;
608                         break;
609                 }
610         }
611
612         set = SF_POP();
613         if ( IS_OP( set ) ) {
614                 SF_ERROR( syntax );
615         }
616         if ( SF_TOP() == 0 ) {
617                 /* FIXME: ok ? */ ;
618
619         } else if ( IS_OP( SF_TOP() ) ) {
620                 op = (unsigned long)SF_POP();
621                 lset = SF_POP();
622                 set = slap_set_join( cp, lset, op, set );
623                 if ( set == NULL ) {
624                         SF_ERROR( memory );
625                 }
626                 
627         } else {
628                 SF_ERROR( syntax );
629         }
630
631         rc = slap_set_isempty( set ) ? 0 : 1;
632         if ( results ) {
633                 *results = set;
634                 set = NULL;
635         }
636
637 _error:
638         if ( IS_SET( set ) ) {
639                 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
640         }
641         while ( ( set = SF_POP() ) ) {
642                 if ( IS_SET( set ) ) {
643                         ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
644                 }
645         }
646         return rc;
647 }