2 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 * Copyright 2000-2007 The OpenLDAP Foundation.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted only as authorized by the OpenLDAP
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>.
19 #include <ac/string.h>
24 static BerVarray set_chase( SLAP_SET_GATHER gatherer,
25 SetCookie *cookie, BerVarray set, AttributeDescription *desc, int closure );
27 /* Count the array members */
29 slap_set_size( BerVarray set )
34 while ( !BER_BVISNULL( &set[ i ] ) ) {
42 /* Return 0 if there is at least one array member, non-zero otherwise */
44 slap_set_isempty( BerVarray set )
50 if ( !BER_BVISNULL( &set[ 0 ] ) ) {
57 /* Dispose of the contents of the array and the array itself according
58 * to the flags value. If SLAP_SET_REFVAL, don't dispose of values;
59 * if SLAP_SET_REFARR, don't dispose of the array itself. In case of
60 * binary operators, there are LEFT flags and RIGHT flags, referring to
61 * the first and the second operator arguments, respectively. In this
62 * case, flags must be transformed using macros SLAP_SET_LREF2REF() and
63 * SLAP_SET_RREF2REF() before calling this function.
66 slap_set_dispose( SetCookie *cp, BerVarray set, unsigned flags )
68 if ( flags & SLAP_SET_REFVAL ) {
69 if ( ! ( flags & SLAP_SET_REFARR ) ) {
70 cp->set_op->o_tmpfree( set, cp->set_op->o_tmpmemctx );
74 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
78 /* Duplicate a set. If SLAP_SET_REFARR, is not set, the original array
79 * with the original values is returned, otherwise the array is duplicated;
80 * if SLAP_SET_REFVAL is set, also the values are duplicated.
83 set_dup( SetCookie *cp, BerVarray set, unsigned flags )
85 BerVarray newset = NULL;
91 if ( flags & SLAP_SET_REFARR ) {
94 for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ )
96 newset = cp->set_op->o_tmpcalloc( i + 1,
97 sizeof( struct berval ),
98 cp->set_op->o_tmpmemctx );
99 if ( newset == NULL ) {
103 if ( flags & SLAP_SET_REFVAL ) {
104 for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
105 ber_dupbv_x( &newset[ i ], &set[ i ],
106 cp->set_op->o_tmpmemctx );
110 AC_MEMCPY( newset, set, ( i + 1 ) * sizeof( struct berval ) );
120 /* Join two sets according to operator op and flags op_flags.
122 * '|' (or): the union between the two sets is returned,
123 * eliminating diplicates
124 * '&' (and): the intersection between the two sets
126 * '+' (add): the inner product of the two sets is returned,
127 * namely a set containing the concatenation of
128 * all combinations of the two sets members,
129 * except for duplicates.
130 * The two sets are disposed of according to the flags as described
131 * for slap_set_dispose().
141 long i, j, last, rlast;
142 unsigned op = ( op_flags & SLAP_SET_OPMASK );
146 case '|': /* union */
147 if ( lset == NULL || BER_BVISNULL( &lset[ 0 ] ) ) {
148 if ( rset == NULL ) {
149 if ( lset == NULL ) {
150 set = cp->set_op->o_tmpcalloc( 1,
151 sizeof( struct berval ),
152 cp->set_op->o_tmpmemctx );
153 BER_BVZERO( &set[ 0 ] );
156 set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
159 slap_set_dispose( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
160 set = set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
163 if ( rset == NULL || BER_BVISNULL( &rset[ 0 ] ) ) {
164 slap_set_dispose( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
165 set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
169 /* worst scenario: no duplicates */
170 rlast = slap_set_size( rset );
171 i = slap_set_size( lset ) + rlast + 1;
172 set = cp->set_op->o_tmpcalloc( i, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
174 /* set_chase() depends on this routine to
175 * keep the first elements of the result
176 * set the same (and in the same order)
179 for ( i = 0; !BER_BVISNULL( &lset[ i ] ); i++ ) {
180 if ( op_flags & SLAP_SET_LREFVAL ) {
181 ber_dupbv_x( &set[ i ], &lset[ i ], cp->set_op->o_tmpmemctx );
184 set[ i ] = lset[ i ];
188 /* pointers to values have been used in set - don't free twice */
189 op_flags |= SLAP_SET_LREFVAL;
193 for ( i = 0; !BER_BVISNULL( &rset[ i ] ); i++ ) {
196 for ( j = 0; !BER_BVISNULL( &set[ j ] ); j++ ) {
197 if ( bvmatch( &rset[ i ], &set[ j ] ) )
199 if ( !( op_flags & SLAP_SET_RREFVAL ) ) {
200 cp->set_op->o_tmpfree( rset[ i ].bv_val, cp->set_op->o_tmpmemctx );
201 rset[ i ] = rset[ --rlast ];
202 BER_BVZERO( &rset[ rlast ] );
210 if ( op_flags & SLAP_SET_RREFVAL ) {
211 ber_dupbv_x( &set[ last ], &rset[ i ], cp->set_op->o_tmpmemctx );
214 set[ last ] = rset[ i ];
220 /* pointers to values have been used in set - don't free twice */
221 op_flags |= SLAP_SET_RREFVAL;
223 BER_BVZERO( &set[ last ] );
227 case '&': /* intersection */
228 if ( lset == NULL || BER_BVISNULL( &lset[ 0 ] )
229 || rset == NULL || BER_BVISNULL( &rset[ 0 ] ) )
231 set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
232 cp->set_op->o_tmpmemctx );
233 BER_BVZERO( &set[ 0 ] );
240 llen = slap_set_size( lset );
241 rlen = slap_set_size( rset );
243 /* dup the shortest */
246 set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
252 set = set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
261 for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
262 for ( j = 0; !BER_BVISNULL( &sset[ j ] ); j++ ) {
263 if ( bvmatch( &set[ i ], &sset[ j ] ) ) {
268 if ( BER_BVISNULL( &sset[ j ] ) ) {
269 cp->set_op->o_tmpfree( set[ i ].bv_val, cp->set_op->o_tmpmemctx );
270 set[ i ] = set[ --last ];
271 BER_BVZERO( &set[ last ] );
278 case '+': /* string concatenation */
279 i = slap_set_size( rset );
280 j = slap_set_size( lset );
282 /* handle empty set cases */
283 if ( i == 0 || j == 0 ) {
284 set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
285 cp->set_op->o_tmpmemctx );
289 BER_BVZERO( &set[ 0 ] );
293 set = cp->set_op->o_tmpcalloc( i * j + 1, sizeof( struct berval ),
294 cp->set_op->o_tmpmemctx );
299 for ( last = 0, i = 0; !BER_BVISNULL( &lset[ i ] ); i++ ) {
300 for ( j = 0; !BER_BVISNULL( &rset[ j ] ); j++ ) {
304 /* don't concatenate with the empty string */
305 if ( BER_BVISEMPTY( &lset[ i ] ) ) {
306 ber_dupbv_x( &bv, &rset[ j ], cp->set_op->o_tmpmemctx );
307 if ( bv.bv_val == NULL ) {
308 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
313 } else if ( BER_BVISEMPTY( &rset[ j ] ) ) {
314 ber_dupbv_x( &bv, &lset[ i ], cp->set_op->o_tmpmemctx );
315 if ( bv.bv_val == NULL ) {
316 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
322 bv.bv_len = lset[ i ].bv_len + rset[ j ].bv_len;
323 bv.bv_val = cp->set_op->o_tmpalloc( bv.bv_len + 1,
324 cp->set_op->o_tmpmemctx );
325 if ( bv.bv_val == NULL ) {
326 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
330 AC_MEMCPY( bv.bv_val, lset[ i ].bv_val, lset[ i ].bv_len );
331 AC_MEMCPY( &bv.bv_val[ lset[ i ].bv_len ], rset[ j ].bv_val, rset[ j ].bv_len );
332 bv.bv_val[ bv.bv_len ] = '\0';
335 for ( k = 0; k < last; k++ ) {
336 if ( bvmatch( &set[ k ], &bv ) ) {
337 cp->set_op->o_tmpfree( bv.bv_val, cp->set_op->o_tmpmemctx );
347 BER_BVZERO( &set[ last ] );
355 if ( lset ) slap_set_dispose( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
356 if ( rset ) slap_set_dispose( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
359 if ( LogTest( LDAP_DEBUG_ACL ) ) {
360 if ( BER_BVISNULL( set ) ) {
361 Debug( LDAP_DEBUG_ACL, " ACL set: empty\n", 0, 0, 0 );
364 for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
365 Debug( LDAP_DEBUG_ACL, " ACL set[%ld]=%s\n", i, set[i].bv_val, 0 );
374 set_chase( SLAP_SET_GATHER gatherer,
375 SetCookie *cp, BerVarray set, AttributeDescription *desc, int closure )
377 BerVarray vals, nset;
381 set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
382 cp->set_op->o_tmpmemctx );
384 BER_BVZERO( &set[ 0 ] );
389 if ( BER_BVISNULL( set ) ) {
393 nset = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
394 if ( nset == NULL ) {
395 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
398 for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
399 vals = gatherer( cp, &set[ i ], desc );
400 if ( vals != NULL ) {
401 nset = slap_set_join( cp, nset, '|', vals );
404 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
407 for ( i = 0; !BER_BVISNULL( &nset[ i ] ); i++ ) {
408 vals = gatherer( cp, &nset[ i ], desc );
409 if ( vals != NULL ) {
410 nset = slap_set_join( cp, nset, '|', vals );
411 if ( nset == NULL ) {
423 set_parents( SetCookie *cp, BerVarray set )
426 struct berval bv, pbv;
427 BerVarray nset, vals;
430 set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
431 cp->set_op->o_tmpmemctx );
433 BER_BVZERO( &set[ 0 ] );
438 if ( BER_BVISNULL( &set[ 0 ] ) ) {
442 nset = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
443 if ( nset == NULL ) {
444 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
448 BER_BVZERO( &nset[ 0 ] );
450 for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
454 for ( ; !BER_BVISEMPTY( &pbv ); dnParent( &bv, &pbv ) ) {
459 vals = cp->set_op->o_tmpcalloc( level + 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
460 if ( vals == NULL ) {
461 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
462 ber_bvarray_free_x( nset, cp->set_op->o_tmpmemctx );
465 BER_BVZERO( &vals[ 0 ] );
469 for ( j = 0 ; j < level ; j++ ) {
470 ber_dupbv_x( &vals[ last ], &bv, cp->set_op->o_tmpmemctx );
472 dnParent( &bv, &bv );
474 BER_BVZERO( &vals[ last ] );
476 nset = slap_set_join( cp, nset, '|', vals );
479 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
487 set_parent( SetCookie *cp, BerVarray set, int level )
494 set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
495 cp->set_op->o_tmpmemctx );
497 BER_BVZERO( &set[ 0 ] );
502 if ( BER_BVISNULL( &set[ 0 ] ) ) {
506 nset = cp->set_op->o_tmpcalloc( slap_set_size( set ) + 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
507 if ( nset == NULL ) {
508 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
512 BER_BVZERO( &nset[ 0 ] );
515 for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
518 for ( j = 0 ; j < level ; j++ ) {
519 dnParent( &bv, &bv );
522 for ( j = 0; !BER_BVISNULL( &nset[ j ] ); j++ ) {
523 if ( bvmatch( &bv, &nset[ j ] ) )
529 if ( BER_BVISNULL( &nset[ j ] ) ) {
530 ber_dupbv_x( &nset[ last ], &bv, cp->set_op->o_tmpmemctx );
535 BER_BVZERO( &nset[ last ] );
537 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
543 slap_set_filter( SLAP_SET_GATHER gatherer,
544 SetCookie *cp, struct berval *fbv,
545 struct berval *user, struct berval *target, BerVarray *results )
547 #define STACK_SIZE 64
548 #define IS_SET(x) ( (unsigned long)(x) >= 256 )
549 #define IS_OP(x) ( (unsigned long)(x) < 256 )
550 #define SF_ERROR(x) do { rc = -1; goto _error; } while ( 0 )
551 #define SF_TOP() ( (BerVarray)( ( stp < 0 ) ? 0 : stack[ stp ] ) )
552 #define SF_POP() ( (BerVarray)( ( stp < 0 ) ? 0 : stack[ stp-- ] ) )
553 #define SF_PUSH(x) do { \
554 if ( stp >= ( STACK_SIZE - 1 ) ) SF_ERROR( overflow ); \
555 stack[ ++stp ] = (BerVarray)(long)(x); \
559 BerVarray stack[ STACK_SIZE ] = { 0 };
562 char c, *filter = fbv->bv_val;
569 while ( ( c = *filter++ ) ) {
579 if ( IS_SET( SF_TOP() ) ) {
587 if ( IS_OP( set ) ) {
590 if ( SF_TOP() == (void *)'(' /* ) */ ) {
595 } else if ( IS_OP( SF_TOP() ) ) {
596 op = (unsigned long)SF_POP();
599 set = slap_set_join( cp, lset, op, set );
611 case '|': /* union */
612 case '&': /* intersection */
613 case '+': /* string concatenation */
615 if ( IS_OP( set ) ) {
618 if ( SF_TOP() == 0 || SF_TOP() == (void *)'(' /* ) */ ) {
622 } else if ( IS_OP( SF_TOP() ) ) {
623 op = (unsigned long)SF_POP();
625 set = slap_set_join( cp, lset, op, set );
639 if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
642 for ( len = 0; ( c = *filter++ ) && ( c != /* [ */ ']' ); len++ )
648 set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
649 cp->set_op->o_tmpmemctx );
653 set->bv_val = cp->set_op->o_tmpcalloc( len + 1, sizeof( char ),
654 cp->set_op->o_tmpmemctx );
655 if ( BER_BVISNULL( set ) ) {
658 AC_MEMCPY( set->bv_val, &filter[ - len - 1 ], len );
665 if ( ( SF_TOP() == (void *)'/' )
666 && ( *filter == '*' || ASCII_DIGIT( *filter ) ) )
670 if ( *filter == '*' ) {
671 set = set_parents( cp, SF_POP() );
676 long parent = strtol( filter, &next, 10 );
678 if ( next == filter ) {
684 set = set_parent( cp, set, parent );
701 /* fall through to next case */
705 if ( IS_OP( SF_TOP() ) ) {
713 && ( c < 'A' || c > 'Z' )
714 && ( c < 'a' || c > 'z' ) )
720 ( c = filter[ len ] )
721 && ( ( c >= '0' && c <= '9' )
722 || ( c >= 'A' && c <= 'Z' )
723 || ( c >= 'a' && c <= 'z' ) );
727 && memcmp( "this", filter, len ) == 0 )
729 if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
732 set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
733 cp->set_op->o_tmpmemctx );
737 ber_dupbv_x( set, target, cp->set_op->o_tmpmemctx );
738 if ( BER_BVISNULL( set ) ) {
741 BER_BVZERO( &set[ 1 ] );
744 && memcmp( "user", filter, len ) == 0 )
746 if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
749 set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
750 cp->set_op->o_tmpmemctx );
754 ber_dupbv_x( set, user, cp->set_op->o_tmpmemctx );
755 if ( BER_BVISNULL( set ) ) {
758 BER_BVZERO( &set[ 1 ] );
760 } else if ( SF_TOP() != (void *)'/' ) {
765 AttributeDescription *ad = NULL;
766 const char *text = NULL;
772 if ( slap_bv2ad( &fb2, &ad, &text ) != LDAP_SUCCESS ) {
776 /* NOTE: ad must have distinguishedName syntax
777 * or expand in an LDAP URI if c == '*'
780 set = set_chase( gatherer,
781 cp, SF_POP(), ad, c == '*' );
797 if ( IS_OP( set ) ) {
800 if ( SF_TOP() == 0 ) {
803 } else if ( IS_OP( SF_TOP() ) ) {
804 op = (unsigned long)SF_POP();
806 set = slap_set_join( cp, lset, op, set );
815 rc = slap_set_isempty( set ) ? 0 : 1;
822 if ( IS_SET( set ) ) {
823 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
825 while ( ( set = SF_POP() ) ) {
826 if ( IS_SET( set ) ) {
827 ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );