Newer
Older
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
*
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted only as authorized by the OpenLDAP
* Public License.
*
* A copy of this license is available in the file LICENSE in the
* top-level directory of the distribution or, alternatively, at
* <http://www.OpenLDAP.org/license.html>.
*/
#include "portable.h"
#include <stdio.h>
#include "sets.h"
Pierangelo Masarati
committed
static BerVarray set_chase( SLAP_SET_GATHER gatherer,
SetCookie *cookie, BerVarray set, AttributeDescription *desc, int closure );
/* Count the array members */
Pierangelo Masarati
committed
static long
slap_set_size( BerVarray set )
long i = 0;
Pierangelo Masarati
committed
if ( set != NULL ) {
i++;
Pierangelo Masarati
committed
}
}
/* Return 0 if there is at least one array member, non-zero otherwise */
static int
slap_set_isempty( BerVarray set )
{
if ( set == NULL ) {
return 1;
}
if ( !BER_BVISNULL( &set[ 0 ] ) ) {
return 0;
}
return 1;
}
/* Dispose of the contents of the array and the array itself according
* to the flags value. If SLAP_SET_REFVAL, don't dispose of values;
* if SLAP_SET_REFARR, don't dispose of the array itself. In case of
* binary operators, there are LEFT flags and RIGHT flags, referring to
* the first and the second operator arguments, respectively. In this
* case, flags must be transformed using macros SLAP_SET_LREF2REF() and
* SLAP_SET_RREF2REF() before calling this function.
*/
Pierangelo Masarati
committed
static void
slap_set_dispose( SetCookie *cp, BerVarray set, unsigned flags )
if ( flags & SLAP_SET_REFVAL ) {
if ( ! ( flags & SLAP_SET_REFARR ) ) {
cp->set_op->o_tmpfree( set, cp->set_op->o_tmpmemctx );
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
/* Duplicate a set. If SLAP_SET_REFARR, is not set, the original array
* with the original values is returned, otherwise the array is duplicated;
* if SLAP_SET_REFVAL is set, also the values are duplicated.
*/
static BerVarray
set_dup( SetCookie *cp, BerVarray set, unsigned flags )
{
BerVarray newset = NULL;
if ( set == NULL ) {
return NULL;
}
if ( flags & SLAP_SET_REFARR ) {
int i;
for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ )
;
newset = cp->set_op->o_tmpcalloc( i + 1,
cp->set_op->o_tmpmemctx );
if ( newset == NULL ) {
return NULL;
}
if ( flags & SLAP_SET_REFVAL ) {
for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
ber_dupbv_x( &newset[ i ], &set[ i ],
cp->set_op->o_tmpmemctx );
}
} else {
AC_MEMCPY( newset, set, ( i + 1 ) * sizeof( struct berval ) );
}
} else {
newset = set;
}
return newset;
}
/* Join two sets according to operator op and flags op_flags.
* op can be:
* '|' (or): the union between the two sets is returned,
* '&' (and): the intersection between the two sets
* is returned
* '+' (add): the inner product of the two sets is returned,
* namely a set containing the concatenation of
* all combinations of the two sets members,
* except for duplicates.
* The two sets are disposed of according to the flags as described
* for slap_set_dispose().
*/
slap_set_join(
SetCookie *cp,
BerVarray lset,
unsigned op_flags,
BerVarray rset )
long i, j, last, rlast;
unsigned op = ( op_flags & SLAP_SET_OPMASK );
set = NULL;
if ( lset == NULL || BER_BVISNULL( &lset[ 0 ] ) ) {
if ( rset == NULL ) {
if ( lset == NULL ) {
set = cp->set_op->o_tmpcalloc( 1,
cp->set_op->o_tmpmemctx );
BER_BVZERO( &set[ 0 ] );
set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
goto done2;
slap_set_dispose( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
set = set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
goto done2;
if ( rset == NULL || BER_BVISNULL( &rset[ 0 ] ) ) {
slap_set_dispose( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
goto done2;
}
/* worst scenario: no duplicates */
rlast = slap_set_size( rset );
i = slap_set_size( lset ) + rlast + 1;
set = cp->set_op->o_tmpcalloc( i, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
/* set_chase() depends on this routine to
* keep the first elements of the result
* set the same (and in the same order)
* as the left-set.
*/
for ( i = 0; !BER_BVISNULL( &lset[ i ] ); i++ ) {
if ( op_flags & SLAP_SET_LREFVAL ) {
ber_dupbv_x( &set[ i ], &lset[ i ], cp->set_op->o_tmpmemctx );
} else {
set[ i ] = lset[ i ];
}
/* pointers to values have been used in set - don't free twice */
op_flags |= SLAP_SET_LREFVAL;
for ( i = 0; !BER_BVISNULL( &rset[ i ] ); i++ ) {
for ( j = 0; !BER_BVISNULL( &set[ j ] ); j++ ) {
if ( bvmatch( &rset[ i ], &set[ j ] ) )
Pierangelo Masarati
committed
{
if ( !( op_flags & SLAP_SET_RREFVAL ) ) {
cp->set_op->o_tmpfree( rset[ i ].bv_val, cp->set_op->o_tmpmemctx );
rset[ i ] = rset[ --rlast ];
BER_BVZERO( &rset[ rlast ] );
break;
}
if ( !exists ) {
if ( op_flags & SLAP_SET_RREFVAL ) {
ber_dupbv_x( &set[ last ], &rset[ i ], cp->set_op->o_tmpmemctx );
/* pointers to values have been used in set - don't free twice */
op_flags |= SLAP_SET_RREFVAL;
case '&': /* intersection */
if ( lset == NULL || BER_BVISNULL( &lset[ 0 ] )
|| rset == NULL || BER_BVISNULL( &rset[ 0 ] ) )
set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
cp->set_op->o_tmpmemctx );
BER_BVZERO( &set[ 0 ] );
break;
} else {
long llen, rlen;
BerVarray sset;
llen = slap_set_size( lset );
rlen = slap_set_size( rset );
/* dup the shortest */
if ( llen < rlen ) {
set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
lset = NULL;
sset = rset;
} else {
set = set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
rset = NULL;
sset = lset;
}
if ( set == NULL ) {
break;
}
for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
for ( j = 0; !BER_BVISNULL( &sset[ j ] ); j++ ) {
if ( bvmatch( &set[ i ], &sset[ j ] ) ) {
break;
Pierangelo Masarati
committed
}
if ( BER_BVISNULL( &sset[ j ] ) ) {
cp->set_op->o_tmpfree( set[ i ].bv_val, cp->set_op->o_tmpmemctx );
set[ i ] = set[ --last ];
i--;
}
}
}
case '+': /* string concatenation */
i = slap_set_size( rset );
j = slap_set_size( lset );
/* handle empty set cases */
if ( i == 0 || j == 0 ) {
set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
cp->set_op->o_tmpmemctx );
if ( set == NULL ) {
break;
}
break;
}
set = cp->set_op->o_tmpcalloc( i * j + 1, sizeof( struct berval ),
cp->set_op->o_tmpmemctx );
if ( set == NULL ) {
break;
}
for ( last = 0, i = 0; !BER_BVISNULL( &lset[ i ] ); i++ ) {
for ( j = 0; !BER_BVISNULL( &rset[ j ] ); j++ ) {
struct berval bv;
long k;
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
/* don't concatenate with the empty string */
if ( BER_BVISEMPTY( &lset[ i ] ) ) {
ber_dupbv_x( &bv, &rset[ j ], cp->set_op->o_tmpmemctx );
if ( bv.bv_val == NULL ) {
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
set = NULL;
goto done;
}
} else if ( BER_BVISEMPTY( &rset[ j ] ) ) {
ber_dupbv_x( &bv, &lset[ i ], cp->set_op->o_tmpmemctx );
if ( bv.bv_val == NULL ) {
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
set = NULL;
goto done;
}
} else {
bv.bv_len = lset[ i ].bv_len + rset[ j ].bv_len;
bv.bv_val = cp->set_op->o_tmpalloc( bv.bv_len + 1,
cp->set_op->o_tmpmemctx );
if ( bv.bv_val == NULL ) {
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
set = NULL;
goto done;
}
AC_MEMCPY( bv.bv_val, lset[ i ].bv_val, lset[ i ].bv_len );
AC_MEMCPY( &bv.bv_val[ lset[ i ].bv_len ], rset[ j ].bv_val, rset[ j ].bv_len );
bv.bv_val[ bv.bv_len ] = '\0';
}
for ( k = 0; k < last; k++ ) {
if ( bvmatch( &set[ k ], &bv ) ) {
cp->set_op->o_tmpfree( bv.bv_val, cp->set_op->o_tmpmemctx );
break;
}
}
if ( k == last ) {
set[ last++ ] = bv;
}
}
}
BER_BVZERO( &set[ last ] );
break;
if ( lset ) slap_set_dispose( cp, lset, SLAP_SET_LREF2REF( op_flags ) );
if ( rset ) slap_set_dispose( cp, rset, SLAP_SET_RREF2REF( op_flags ) );
done2:;
if ( LogTest( LDAP_DEBUG_ACL ) ) {
if ( BER_BVISNULL( set ) ) {
Debug( LDAP_DEBUG_ACL, " ACL set: empty\n", 0, 0, 0 );
} else {
for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
Debug( LDAP_DEBUG_ACL, " ACL set[%ld]=%s\n", i, set[i].bv_val, 0 );
}
static BerVarray
Pierangelo Masarati
committed
set_chase( SLAP_SET_GATHER gatherer,
SetCookie *cp, BerVarray set, AttributeDescription *desc, int closure )
set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
cp->set_op->o_tmpmemctx );
if ( set != NULL ) {
BER_BVZERO( &set[ 0 ] );
}
if ( BER_BVISNULL( set ) ) {
Pierangelo Masarati
committed
return set;
nset = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
Pierangelo Masarati
committed
if ( nset == NULL ) {
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
Pierangelo Masarati
committed
return NULL;
for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
vals = gatherer( cp, &set[ i ], desc );
Pierangelo Masarati
committed
if ( vals != NULL ) {
nset = slap_set_join( cp, nset, '|', vals );
}
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
Pierangelo Masarati
committed
if ( closure ) {
for ( i = 0; !BER_BVISNULL( &nset[ i ] ); i++ ) {
vals = gatherer( cp, &nset[ i ], desc );
Pierangelo Masarati
committed
if ( vals != NULL ) {
nset = slap_set_join( cp, nset, '|', vals );
if ( nset == NULL ) {
break;
Pierangelo Masarati
committed
}
}
}
}
Pierangelo Masarati
committed
return nset;
}
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
static BerVarray
set_parents( SetCookie *cp, BerVarray set )
{
int i, j, last;
struct berval bv, pbv;
BerVarray nset, vals;
if ( set == NULL ) {
set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
cp->set_op->o_tmpmemctx );
if ( set != NULL ) {
BER_BVZERO( &set[ 0 ] );
}
return set;
}
if ( BER_BVISNULL( &set[ 0 ] ) ) {
return set;
}
nset = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
if ( nset == NULL ) {
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
return NULL;
}
BER_BVZERO( &nset[ 0 ] );
for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
int level = 1;
pbv = bv = set[ i ];
for ( ; !BER_BVISEMPTY( &pbv ); dnParent( &bv, &pbv ) ) {
level++;
bv = pbv;
}
vals = cp->set_op->o_tmpcalloc( level + 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
if ( vals == NULL ) {
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
ber_bvarray_free_x( nset, cp->set_op->o_tmpmemctx );
return NULL;
}
BER_BVZERO( &vals[ 0 ] );
last = 0;
bv = set[ i ];
for ( j = 0 ; j < level ; j++ ) {
ber_dupbv_x( &vals[ last ], &bv, cp->set_op->o_tmpmemctx );
last++;
dnParent( &bv, &bv );
}
BER_BVZERO( &vals[ last ] );
nset = slap_set_join( cp, nset, '|', vals );
}
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
return nset;
}
static BerVarray
set_parent( SetCookie *cp, BerVarray set, int level )
{
int i, j, last;
struct berval bv;
BerVarray nset;
if ( set == NULL ) {
set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ),
cp->set_op->o_tmpmemctx );
if ( set != NULL ) {
BER_BVZERO( &set[ 0 ] );
}
return set;
}
if ( BER_BVISNULL( &set[ 0 ] ) ) {
return set;
}
nset = cp->set_op->o_tmpcalloc( slap_set_size( set ) + 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx );
if ( nset == NULL ) {
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
return NULL;
}
BER_BVZERO( &nset[ 0 ] );
last = 0;
for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) {
bv = set[ i ];
for ( j = 0 ; j < level ; j++ ) {
dnParent( &bv, &bv );
}
for ( j = 0; !BER_BVISNULL( &nset[ j ] ); j++ ) {
if ( bvmatch( &bv, &nset[ j ] ) )
{
break;
}
}
if ( BER_BVISNULL( &nset[ j ] ) ) {
ber_dupbv_x( &nset[ last ], &bv, cp->set_op->o_tmpmemctx );
last++;
}
}
BER_BVZERO( &nset[ last ] );
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
return nset;
}
int
Pierangelo Masarati
committed
slap_set_filter( SLAP_SET_GATHER gatherer,
Pierangelo Masarati
committed
struct berval *user, struct berval *target, BerVarray *results )
#define IS_SET(x) ( (unsigned long)(x) >= 256 )
#define IS_OP(x) ( (unsigned long)(x) < 256 )
#define SF_ERROR(x) do { rc = -1; goto _error; } while ( 0 )
#define SF_TOP() ( (BerVarray)( ( stp < 0 ) ? 0 : stack[ stp ] ) )
#define SF_POP() ( (BerVarray)( ( stp < 0 ) ? 0 : stack[ stp-- ] ) )
#define SF_PUSH(x) do { \
if ( stp >= ( STACK_SIZE - 1 ) ) SF_ERROR( overflow ); \
BerVarray stack[ STACK_SIZE ] = { 0 };
unsigned long op;
*results = NULL;
stp = -1;
set = NULL;
case ' ':
case '\t':
case '\x0A':
case '\x0D':
break;
case '(' /* ) */ :
if ( IS_SET( SF_TOP() ) ) {
SF_ERROR( syntax );
}
SF_PUSH( c );
break;
set = SF_POP();
if ( IS_OP( set ) ) {
SF_ERROR( syntax );
}
if ( SF_TOP() == (void *)'(' /* ) */ ) {
SF_POP();
set = NULL;
op = (unsigned long)SF_POP();
lset = SF_POP();
SF_POP();
set = slap_set_join( cp, lset, op, set );
if ( set == NULL ) {
set = NULL;
} else {
}
break;
case '|': /* union */
case '&': /* intersection */
case '+': /* string concatenation */
set = SF_POP();
if ( IS_OP( set ) ) {
SF_ERROR( syntax );
}
if ( SF_TOP() == 0 || SF_TOP() == (void *)'(' /* ) */ ) {
SF_PUSH( set );
set = NULL;
op = (unsigned long)SF_POP();
lset = SF_POP();
set = slap_set_join( cp, lset, op, set );
if ( set == NULL ) {
SF_ERROR( memory );
}
SF_PUSH( set );
set = NULL;
} else {
break;
case '[' /* ] */:
if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
SF_ERROR( syntax );
}
for ( len = 0; ( c = *filter++ ) && ( c != /* [ */ ']' ); len++ )
set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
cp->set_op->o_tmpmemctx );
set->bv_val = cp->set_op->o_tmpcalloc( len + 1, sizeof( char ),
cp->set_op->o_tmpmemctx );
if ( BER_BVISNULL( set ) ) {
SF_ERROR( memory );
}
AC_MEMCPY( set->bv_val, &filter[ - len - 1 ], len );
set = NULL;
break;
case '-':
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
if ( ( SF_TOP() == (void *)'/' )
&& ( *filter == '*' || ASCII_DIGIT( *filter ) ) )
{
SF_POP();
if ( *filter == '*' ) {
set = set_parents( cp, SF_POP() );
filter++;
} else {
char *next = NULL;
long parent = strtol( filter, &next, 10 );
if ( next == filter ) {
SF_ERROR( syntax );
}
set = SF_POP();
if ( parent != 0 ) {
set = set_parent( cp, set, parent );
}
filter = next;
}
if ( set == NULL ) {
SF_ERROR( memory );
}
SF_PUSH( set );
set = NULL;
break;
} else {
c = *filter++;
if ( c != '>' ) {
SF_ERROR( syntax );
}
/* fall through to next case */
case '/':
if ( IS_OP( SF_TOP() ) ) {
SF_ERROR( syntax );
}
SF_PUSH( '/' );
break;
default:
}
filter--;
( c = filter[ len ] ) && AD_CHAR( c );
len++ )
{
/* count */
if ( c == '-' && !AD_CHAR( filter[ len + 1 ] ) ) {
break;
}
}
if ( len == 4
&& memcmp( "this", filter, len ) == 0 )
assert( !BER_BVISNULL( target ) );
if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
SF_ERROR( syntax );
}
set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
cp->set_op->o_tmpmemctx );
if ( set == NULL ) {
SF_ERROR( memory );
}
ber_dupbv_x( set, target, cp->set_op->o_tmpmemctx );
if ( BER_BVISNULL( set ) ) {
SF_ERROR( memory );
}
} else if ( len == 4
&& memcmp( "user", filter, len ) == 0 )
if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) {
SF_ERROR( syntax );
}
if ( BER_BVISNULL( user ) ) {
SF_ERROR( memory );
}
set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ),
cp->set_op->o_tmpmemctx );
if ( set == NULL ) {
SF_ERROR( memory );
}
ber_dupbv_x( set, user, cp->set_op->o_tmpmemctx );
} else if ( SF_TOP() != (void *)'/' ) {
SF_ERROR( syntax );
} else {
Pierangelo Masarati
committed
struct berval fb2;
AttributeDescription *ad = NULL;
const char *text = NULL;
fb2.bv_val = filter;
fb2.bv_len = len;
Pierangelo Masarati
committed
if ( slap_bv2ad( &fb2, &ad, &text ) != LDAP_SUCCESS ) {
Pierangelo Masarati
committed
}
/* NOTE: ad must have distinguishedName syntax
* or expand in an LDAP URI if c == '*'
*/
Pierangelo Masarati
committed
set = set_chase( gatherer,
Pierangelo Masarati
committed
cp, SF_POP(), ad, c == '*' );
if ( set == NULL ) {
SF_ERROR( memory );
}
if ( c == '*' ) {
len++;
}
filter += len;
set = NULL;
break;
}
}
set = SF_POP();
if ( IS_OP( set ) ) {
SF_ERROR( syntax );
}
if ( SF_TOP() == 0 ) {
/* FIXME: ok ? */ ;
op = (unsigned long)SF_POP();
lset = SF_POP();
set = slap_set_join( cp, lset, op, set );
if ( set == NULL ) {
SF_ERROR( memory );
}
} else {
}
rc = slap_set_isempty( set ) ? 0 : 1;
if ( results ) {
*results = set;
set = NULL;
}
_error:
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );
}
while ( ( set = SF_POP() ) ) {
if ( IS_SET( set ) ) {
ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx );