source4/lib/ldb/modules/ldb_map_outbound.c

   1 /*
   2    ldb database mapping module
   3
   4    Copyright (C) Jelmer Vernooij 2005
   5    Copyright (C) Martin Kuehl <mkhl@samba.org> 2006
   6
   7    * NOTICE: this module is NOT released under the GNU LGPL license as
   8    * other ldb code. This module is release under the GNU GPL v2 or
   9    * later license.
  10
  11    This program is free software; you can redistribute it and/or modify
  12    it under the terms of the GNU General Public License as published by
  13    the Free Software Foundation; either version 2 of the License, or
  14    (at your option) any later version.
  15
  16    This program is distributed in the hope that it will be useful,
  17    but WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19    GNU General Public License for more details.
  20
  21    You should have received a copy of the GNU General Public License
  22    along with this program; if not, write to the Free Software
  23    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  24 */
  25
  26 #include "includes.h"
  27 #include "ldb/include/includes.h"
  28
  29 #include "ldb/modules/ldb_map.h"
  30 #include "ldb/modules/ldb_map_private.h"
  31
  32
  33 /* Mapping attributes
  34  * ================== */
  35
  36 /* Select attributes that stay in the local partition. */
  37 static const char **map_attrs_select_local(struct ldb_module *module, void *mem_ctx, const char * const *attrs)
  38 {
  39         const struct ldb_map_context *data = map_get_context(module);
  40         const char **result;
  41         int i, last;
  42
  43         if (attrs == NULL)
  44                 return NULL;
  45
  46         last = 0;
  47         result = talloc_array(mem_ctx, const char *, 1);
  48         if (result == NULL) {
  49                 goto failed;
  50         }
  51         result[0] = NULL;
  52
  53         for (i = 0; attrs[i]; i++) {
  54                 /* Wildcards and ignored attributes are kept locally */
  55                 if ((ldb_attr_cmp(attrs[i], "*") == 0) ||
  56                     (!map_attr_check_remote(data, attrs[i]))) {
  57                         result = talloc_realloc(mem_ctx, result, const char *, last+2);
  58                         if (result == NULL) {
  59                                 goto failed;
  60                         }
  61
  62                         result[last] = talloc_strdup(result, attrs[i]);
  63                         result[last+1] = NULL;
  64                         last++;
  65                 }
  66         }
  67
  68         return result;
  69
  70 failed:
  71         talloc_free(result);
  72         map_oom(module);
  73         return NULL;
  74 }
  75
  76 /* Collect attributes that are mapped into the remote partition. */
  77 static const char **map_attrs_collect_remote(struct ldb_module *module, void *mem_ctx, const char * const *attrs)
  78 {
  79         const struct ldb_map_context *data = map_get_context(module);
  80         const char **result;
  81         const struct ldb_map_attribute *map;
  82         const char *name=NULL;
  83         int i, j, last;
  84
  85         if (attrs == NULL)
  86                 return NULL;
  87
  88         last = 0;
  89         result = talloc_array(mem_ctx, const char *, 1);
  90         if (result == NULL) {
  91                 goto failed;
  92         }
  93         result[0] = NULL;
  94
  95         for (i = 0; attrs[i]; i++) {
  96                 /* Wildcards are kept remotely, too */
  97                 if (ldb_attr_cmp(attrs[i], "*") == 0) {
  98                         name = attrs[i];
  99                         goto named;
 100                 }
 101
 102                 /* Add remote names of mapped attrs */
 103                 map = map_attr_find_local(data, attrs[i]);
 104                 if (map == NULL) {
 105                         continue;
 106                 }
 107
 108                 switch (map->type) {
 109                 case MAP_IGNORE:
 110                         continue;
 111
 112                 case MAP_KEEP:
 113                         name = attrs[i];
 114                         goto named;
 115
 116                 case MAP_RENAME:
 117                 case MAP_CONVERT:
 118                         name = map->u.rename.remote_name;
 119                         goto named;
 120
 121                 case MAP_GENERATE:
 122                         /* Add all remote names of "generate" attrs */
 123                         for (j = 0; map->u.generate.remote_names[j]; j++) {
 124                                 result = talloc_realloc(mem_ctx, result, const char *, last+2);
 125                                 if (result == NULL) {
 126                                         goto failed;
 127                                 }
 128
 129                                 result[last] = talloc_strdup(result, map->u.generate.remote_names[j]);
 130                                 result[last+1] = NULL;
 131                                 last++;
 132                         }
 133                         continue;
 134                 }
 135
 136         named:  /* We found a single remote name, add that */
 137                 result = talloc_realloc(mem_ctx, result, const char *, last+2);
 138                 if (result == NULL) {
 139                         goto failed;
 140                 }
 141
 142                 result[last] = talloc_strdup(result, name);
 143                 result[last+1] = NULL;
 144                 last++;
 145         }
 146
 147         return result;
 148
 149 failed:
 150         talloc_free(result);
 151         map_oom(module);
 152         return NULL;
 153 }
 154
 155 /* Split attributes that stay in the local partition from those that
 156  * are mapped into the remote partition. */
 157 static int map_attrs_partition(struct ldb_module *module, void *local_ctx, void *remote_ctx, const char ***local_attrs, const char ***remote_attrs, const char * const *attrs)
 158 {
 159         *local_attrs = map_attrs_select_local(module, local_ctx, attrs);
 160         *remote_attrs = map_attrs_collect_remote(module, remote_ctx, attrs);
 161
 162         return 0;
 163 }
 164
 165 /* Merge two lists of attributes into a single one. */
 166 static int map_attrs_merge(struct ldb_module *module, void *mem_ctx, const char ***attrs, const char * const *more_attrs)
 167 {
 168         int i, j, k;
 169
 170         for (i = 0; (*attrs)[i]; i++) /* noop */ ;
 171         for (j = 0; more_attrs[j]; j++) /* noop */ ;
 172
 173         *attrs = talloc_realloc(mem_ctx, *attrs, const char *, i+j+1);
 174         if (*attrs == NULL) {
 175                 map_oom(module);
 176                 return -1;
 177         }
 178
 179         for (k = 0; k < j; k++) {
 180                 (*attrs)[i+k] = more_attrs[k];
 181         }
 182
 183         (*attrs)[i+k] = NULL;
 184
 185         return 0;
 186 }
 187
 188 /* Mapping ldb values
 189  * ================== */
 190
 191 /* Map an ldb value from a parse tree into the remote partition. */
 192 static struct ldb_val ldb_val_map_subtree(struct ldb_module *module, struct ldb_parse_tree *new, const struct ldb_map_attribute *map, const struct ldb_parse_tree *tree)
 193 {
 194         struct ldb_val val;
 195
 196         /* Extract the old value */
 197         switch (tree->operation) {
 198         case LDB_OP_EQUALITY:
 199                 val = tree->u.equality.value;
 200                 break;
 201         case LDB_OP_LESS:
 202         case LDB_OP_GREATER:
 203         case LDB_OP_APPROX:
 204                 val = tree->u.comparison.value;
 205                 break;
 206         case LDB_OP_EXTENDED:
 207                 val = tree->u.extended.value;
 208                 break;
 209         default:
 210                 val.length = 0;
 211                 val.data = NULL;
 212                 return ldb_val_dup(new, &val);
 213         }
 214
 215         /* Convert to the new value */
 216         return ldb_val_map_local(module, new, map, val);
 217 }
 218
 219 /* Mapping message elements
 220  * ======================== */
 221
 222 /* Add an element to a message, overwriting any old identically named elements. */
 223 static int ldb_msg_replace(struct ldb_message *msg, const struct ldb_message_element *el)
 224 {
 225         struct ldb_message_element *old;
 226
 227         old = ldb_msg_find_element(msg, el->name);
 228
 229         /* no local result, add as new element */
 230         if (old == NULL) {
 231                 if (ldb_msg_add_empty(msg, el->name, 0) != 0) {
 232                         return -1;
 233                 }
 234
 235                 old = ldb_msg_find_element(msg, el->name);
 236                 if (old == NULL) {
 237                         return -1;
 238                 }
 239         }
 240
 241         *old = *el;                     /* copy new element */
 242
 243         return 0;
 244 }
 245
 246 /* Map a message element back into the local partition. */
 247 static struct ldb_message_element *ldb_msg_el_map_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_map_attribute *map, const struct ldb_message_element *old)
 248 {
 249         struct ldb_message_element *el;
 250         int i;
 251
 252         el = talloc_zero(mem_ctx, struct ldb_message_element);
 253         if (el == NULL) {
 254                 map_oom(module);
 255                 return NULL;
 256         }
 257
 258         el->num_values = old->num_values;
 259         el->values = talloc_array(el, struct ldb_val, el->num_values);
 260         if (el->values == NULL) {
 261                 talloc_free(el);
 262                 map_oom(module);
 263                 return NULL;
 264         }
 265
 266         el->name = map_attr_map_remote(el, map, old->name);
 267
 268         for (i = 0; i < el->num_values; i++) {
 269                 el->values[i] = ldb_val_map_remote(module, el->values, map, old->values[i]);
 270         }
 271
 272         return el;
 273 }
 274
 275 /* Merge a remote message element into a local message. */
 276 static int ldb_msg_el_merge(struct ldb_module *module, struct ldb_message *local, struct ldb_message *remote, const char *attr_name, const struct ldb_message_element *old)
 277 {
 278         const struct ldb_map_context *data = map_get_context(module);
 279         const struct ldb_map_attribute *map = map_attr_find_remote(data, attr_name);
 280         struct ldb_message_element *el=NULL;
 281
 282         /* Unknown attribute in remote message:
 283          * skip, attribute was probably auto-generated */
 284         if (map == NULL) {
 285                 ldb_debug(module->ldb, LDB_DEBUG_WARNING, "ldb_map: "
 286                           "Skipping attribute '%s': no mapping found\n",
 287                           old->name);
 288                 return 0;
 289         }
 290
 291         switch (map->type) {
 292         case MAP_IGNORE:
 293                 return -1;
 294
 295         case MAP_CONVERT:
 296                 if (map->u.convert.convert_remote == NULL) {
 297                         ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
 298                                   "Skipping attribute '%s': "
 299                                   "'convert_remote' not set\n",
 300                                   old->name);
 301                         return 0;
 302                 }
 303                 /* fall through */
 304         case MAP_KEEP:
 305         case MAP_RENAME:
 306                 el = ldb_msg_el_map_remote(module, local, map, old);
 307                 break;
 308
 309         case MAP_GENERATE:
 310                 if (map->u.generate.generate_local == NULL) {
 311                         ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
 312                                   "Skipping attribute '%s': "
 313                                   "'generate_local' not set\n",
 314                                   old->name);
 315                         return 0;
 316                 }
 317
 318                 el = map->u.generate.generate_local(module, local, old->name, remote);
 319                 break;
 320         }
 321
 322         if (el == NULL) {
 323                 return -1;
 324         }
 325
 326         return ldb_msg_replace(local, el);
 327 }
 328
 329 /* Mapping messages
 330  * ================ */
 331
 332 /* Merge two local messages into a single one. */
 333 static int ldb_msg_merge_local(struct ldb_module *module, struct ldb_message *msg1, struct ldb_message *msg2)
 334 {
 335         int i, ret;
 336
 337         for (i = 0; i < msg2->num_elements; i++) {
 338                 ret = ldb_msg_replace(msg1, &msg2->elements[i]);
 339                 if (ret) {
 340                         return ret;
 341                 }
 342         }
 343
 344         return 0;
 345 }
 346
 347 /* Merge a local and a remote message into a single local one. */
 348 static int ldb_msg_merge_remote(struct ldb_module *module, struct ldb_message *local, struct ldb_message *remote)
 349 {
 350         int i, ret;
 351
 352         /* Try to map each attribute back;
 353          * Add to local message is possible,
 354          * Overwrite old local attribute if necessary */
 355         for (i = 0; i < remote->num_elements; i++) {
 356                 ret = ldb_msg_el_merge(module, local, remote, remote->elements[i].name, &remote->elements[i]);
 357                 if (ret) {
 358                         return ret;
 359                 }
 360         }
 361
 362         return 0;
 363 }
 364
 365 /* Mapping search results
 366  * ====================== */
 367
 368 /* Map a search result back into the local partition. */
 369 static int map_reply_remote(struct ldb_module *module, struct ldb_reply *ares)
 370 {
 371         struct ldb_message *msg;
 372         struct ldb_dn *dn;
 373         int ret;
 374
 375         /* There is no result message, skip */
 376         if (ares->type != LDB_REPLY_ENTRY) {
 377                 return 0;
 378         }
 379
 380         /* Create a new result message */
 381         msg = ldb_msg_new(ares);
 382         if (msg == NULL) {
 383                 map_oom(module);
 384                 return -1;
 385         }
 386
 387         /* Merge remote message into new message */
 388         ret = ldb_msg_merge_remote(module, msg, ares->message);
 389         if (ret) {
 390                 talloc_free(msg);
 391                 return ret;
 392         }
 393
 394         /* Create corresponding local DN */
 395         dn = ldb_dn_map_rebase_remote(module, msg, ares->message->dn);
 396         if (dn == NULL) {
 397                 talloc_free(msg);
 398                 return -1;
 399         }
 400         msg->dn = dn;
 401
 402         /* Store new message with new DN as the result */
 403         talloc_free(ares->message);
 404         ares->message = msg;
 405
 406         return 0;
 407 }
 408
 409 /* Mapping parse trees
 410  * =================== */
 411
 412 /* Check whether a parse tree can safely be split in two. */
 413 static BOOL ldb_parse_tree_check_splittable(const struct ldb_parse_tree *tree)
 414 {
 415         const struct ldb_parse_tree *subtree = tree;
 416         BOOL negate = False;
 417
 418         while (subtree) {
 419                 switch (subtree->operation) {
 420                 case LDB_OP_NOT:
 421                         negate = !negate;
 422                         subtree = subtree->u.isnot.child;
 423                         continue;
 424
 425                 case LDB_OP_AND:
 426                         return !negate; /* if negate: False */
 427
 428                 case LDB_OP_OR:
 429                         return negate;  /* if negate: True */
 430
 431                 default:
 432                         return True;    /* simple parse tree */
 433                 }
 434         }
 435
 436         return True;                    /* no parse tree */
 437 }
 438
 439 /* Collect a list of attributes required to match a given parse tree. */
 440 static int ldb_parse_tree_collect_attrs(struct ldb_module *module, void *mem_ctx, const char ***attrs, const struct ldb_parse_tree *tree)
 441 {
 442         const char **new_attrs;
 443         int i, ret;
 444
 445         if (tree == NULL) {
 446                 return 0;
 447         }
 448
 449         switch (tree->operation) {
 450         case LDB_OP_OR:
 451         case LDB_OP_AND:                /* attributes stored in list of subtrees */
 452                 for (i = 0; i < tree->u.list.num_elements; i++) {
 453                         ret = ldb_parse_tree_collect_attrs(module, mem_ctx, attrs, tree->u.list.elements[i]);
 454                         if (ret) {
 455                                 return ret;
 456                         }
 457                 }
 458                 return 0;
 459
 460         case LDB_OP_NOT:                /* attributes stored in single subtree */
 461                 return ldb_parse_tree_collect_attrs(module, mem_ctx, attrs, tree->u.isnot.child);
 462
 463         default:                        /* single attribute in tree */
 464                 new_attrs = ldb_attr_list_copy_add(mem_ctx, *attrs, tree->u.equality.attr);
 465                 talloc_free(*attrs);
 466                 *attrs = new_attrs;
 467                 return 0;
 468         }
 469
 470         return -1;
 471 }
 472
 473 static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
 474
 475 /* Select a negated subtree that queries attributes in the local partition */
 476 static int map_subtree_select_local_not(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 477 {
 478         struct ldb_parse_tree *child;
 479         int ret;
 480
 481         /* Prepare new tree */
 482         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 483         if (*new == NULL) {
 484                 map_oom(module);
 485                 return -1;
 486         }
 487
 488         /* Generate new subtree */
 489         ret = map_subtree_select_local(module, *new, &child, tree->u.isnot.child);
 490         if (ret) {
 491                 talloc_free(*new);
 492                 return ret;
 493         }
 494
 495         /* Prune tree without subtree */
 496         if (child == NULL) {
 497                 talloc_free(*new);
 498                 *new = NULL;
 499                 return 0;
 500         }
 501
 502         (*new)->u.isnot.child = child;
 503
 504         return ret;
 505 }
 506
 507 /* Select a list of subtrees that query attributes in the local partition */
 508 static int map_subtree_select_local_list(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 509 {
 510         int i, j, ret;
 511
 512         /* Prepare new tree */
 513         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 514         if (*new == NULL) {
 515                 map_oom(module);
 516                 return -1;
 517         }
 518
 519         /* Prepare list of subtrees */
 520         (*new)->u.list.num_elements = 0;
 521         (*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
 522         if ((*new)->u.list.elements == NULL) {
 523                 map_oom(module);
 524                 talloc_free(*new);
 525                 return -1;
 526         }
 527
 528         /* Generate new list of subtrees */
 529         j = 0;
 530         for (i = 0; i < tree->u.list.num_elements; i++) {
 531                 struct ldb_parse_tree *child;
 532                 ret = map_subtree_select_local(module, *new, &child, tree->u.list.elements[i]);
 533                 if (ret) {
 534                         talloc_free(*new);
 535                         return ret;
 536                 }
 537
 538                 if (child) {
 539                         (*new)->u.list.elements[j] = child;
 540                         j++;
 541                 }
 542         }
 543
 544         /* Prune tree without subtrees */
 545         if (j == 0) {
 546                 talloc_free(*new);
 547                 *new = NULL;
 548                 return 0;
 549         }
 550
 551         /* Fix subtree list size */
 552         (*new)->u.list.num_elements = j;
 553         (*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
 554
 555         return ret;
 556 }
 557
 558 /* Select a simple subtree that queries attributes in the local partition */
 559 static int map_subtree_select_local_simple(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 560 {
 561         /* Prepare new tree */
 562         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 563         if (*new == NULL) {
 564                 map_oom(module);
 565                 return -1;
 566         }
 567
 568         return 0;
 569 }
 570
 571 /* Select subtrees that query attributes in the local partition */
 572 static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 573 {
 574         const struct ldb_map_context *data = map_get_context(module);
 575
 576         if (tree == NULL) {
 577                 return 0;
 578         }
 579
 580         if (tree->operation == LDB_OP_NOT) {
 581                 return map_subtree_select_local_not(module, mem_ctx, new, tree);
 582         }
 583
 584         if (tree->operation == LDB_OP_AND || tree->operation == LDB_OP_OR) {
 585                 return map_subtree_select_local_list(module, mem_ctx, new, tree);
 586         }
 587
 588         if (map_attr_check_remote(data, tree->u.equality.attr)) {
 589                 *new = NULL;
 590                 return 0;
 591         }
 592
 593         return map_subtree_select_local_simple(module, mem_ctx, new, tree);
 594 }
 595
 596 static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
 597
 598 /* Collect a negated subtree that queries attributes in the remote partition */
 599 static int map_subtree_collect_remote_not(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 600 {
 601         struct ldb_parse_tree *child;
 602         int ret;
 603
 604         /* Prepare new tree */
 605         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 606         if (*new == NULL) {
 607                 map_oom(module);
 608                 return -1;
 609         }
 610
 611         /* Generate new subtree */
 612         ret = map_subtree_collect_remote(module, *new, &child, tree->u.isnot.child);
 613         if (ret) {
 614                 talloc_free(*new);
 615                 return ret;
 616         }
 617
 618         /* Prune tree without subtree */
 619         if (child == NULL) {
 620                 talloc_free(*new);
 621                 *new = NULL;
 622                 return 0;
 623         }
 624
 625         (*new)->u.isnot.child = child;
 626
 627         return ret;
 628 }
 629
 630 /* Collect a list of subtrees that query attributes in the remote partition */
 631 static int map_subtree_collect_remote_list(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 632 {
 633         int i, j, ret;
 634
 635         /* Prepare new tree */
 636         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 637         if (*new == NULL) {
 638                 map_oom(module);
 639                 return -1;
 640         }
 641
 642         /* Prepare list of subtrees */
 643         (*new)->u.list.num_elements = 0;
 644         (*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
 645         if ((*new)->u.list.elements == NULL) {
 646                 map_oom(module);
 647                 talloc_free(*new);
 648                 return -1;
 649         }
 650
 651         /* Generate new list of subtrees */
 652         j = 0;
 653         for (i = 0; i < tree->u.list.num_elements; i++) {
 654                 struct ldb_parse_tree *child;
 655                 ret = map_subtree_collect_remote(module, *new, &child, tree->u.list.elements[i]);
 656                 if (ret) {
 657                         talloc_free(*new);
 658                         return ret;
 659                 }
 660
 661                 if (child) {
 662                         (*new)->u.list.elements[j] = child;
 663                         j++;
 664                 }
 665         }
 666
 667         /* Prune tree without subtrees */
 668         if (j == 0) {
 669                 talloc_free(*new);
 670                 *new = NULL;
 671                 return 0;
 672         }
 673
 674         /* Fix subtree list size */
 675         (*new)->u.list.num_elements = j;
 676         (*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
 677
 678         return ret;
 679 }
 680
 681 /* Collect a simple subtree that queries attributes in the remote partition */
 682 int map_subtree_collect_remote_simple(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree, const struct ldb_map_attribute *map)
 683 {
 684         const char *attr;
 685         struct ldb_val val;
 686
 687         /* Prepare new tree */
 688         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
 689         if (*new == NULL) {
 690                 map_oom(module);
 691                 return -1;
 692         }
 693
 694         /* Map attribute and value */
 695         attr = map_attr_map_local(*new, map, tree->u.equality.attr);
 696         if (attr == NULL) {
 697                 talloc_free(*new);
 698                 *new = NULL;
 699                 return 0;
 700         }
 701         val = ldb_val_map_subtree(module, *new, map, tree);
 702
 703         /* Store attribute and value in new tree */
 704         switch (tree->operation) {
 705         case LDB_OP_PRESENT:
 706                 (*new)->u.present.attr = attr;
 707                 break;
 708         case LDB_OP_SUBSTRING:
 709                 (*new)->u.substring.attr = attr;
 710                 (*new)->u.substring.chunks = NULL;      /* FIXME! */
 711                 break;
 712         case LDB_OP_EQUALITY:
 713                 (*new)->u.equality.attr = attr;
 714                 (*new)->u.equality.value = val;
 715                 break;
 716         case LDB_OP_LESS:
 717         case LDB_OP_GREATER:
 718         case LDB_OP_APPROX:
 719                 (*new)->u.comparison.attr = attr;
 720                 (*new)->u.comparison.value = val;
 721                 break;
 722         case LDB_OP_EXTENDED:
 723                 (*new)->u.extended.attr = attr;
 724                 (*new)->u.extended.value = val;
 725                 (*new)->u.extended.rule_id = talloc_strdup(*new, tree->u.extended.rule_id);
 726                 break;
 727         default:                        /* unknown kind of simple subtree */
 728                 talloc_free(*new);
 729                 return -1;
 730         }
 731
 732         return 0;
 733 }
 734
 735 /* Collect subtrees that query attributes in the remote partition */
 736 static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
 737 {
 738         const struct ldb_map_context *data = map_get_context(module);
 739         const struct ldb_map_attribute *map;
 740
 741         if (tree == NULL) {
 742                 return 0;
 743         }
 744
 745         if (tree->operation == LDB_OP_NOT) {
 746                 return map_subtree_collect_remote_not(module, mem_ctx, new, tree);
 747         }
 748
 749         if ((tree->operation == LDB_OP_AND) || (tree->operation == LDB_OP_OR)) {
 750                 return map_subtree_collect_remote_list(module, mem_ctx, new, tree);
 751         }
 752
 753         if (!map_attr_check_remote(data, tree->u.equality.attr)) {
 754                 *new = NULL;
 755                 return 0;
 756         }
 757
 758         map = map_attr_find_local(data, tree->u.equality.attr);
 759         if (map->convert_operator) {
 760                 return map->convert_operator(module, mem_ctx, new, tree);
 761         }
 762
 763         if (map->type == MAP_GENERATE) {
 764                 ldb_debug(module->ldb, LDB_DEBUG_WARNING, "ldb_map: "
 765                           "Skipping attribute '%s': "
 766                           "'convert_operator' not set\n",
 767                           tree->u.equality.attr);
 768                 *new = NULL;
 769                 return 0;
 770         }
 771
 772         return map_subtree_collect_remote_simple(module, mem_ctx, new, tree, map);
 773 }
 774
 775 /* Split subtrees that query attributes in the local partition from
 776  * those that query the remote partition. */
 777 static int ldb_parse_tree_partition(struct ldb_module *module, void *local_ctx, void *remote_ctx, struct ldb_parse_tree **local_tree, struct ldb_parse_tree **remote_tree, const struct ldb_parse_tree *tree)
 778 {
 779         int ret;
 780
 781         *local_tree = NULL;
 782         *remote_tree = NULL;
 783
 784         /* No original tree */
 785         if (tree == NULL) {
 786                 return 0;
 787         }
 788
 789         /* Generate local tree */
 790         ret = map_subtree_select_local(module, local_ctx, local_tree, tree);
 791         if (ret) {
 792                 return ret;
 793         }
 794
 795         /* Generate remote tree */
 796         ret = map_subtree_collect_remote(module, remote_ctx, remote_tree, tree);
 797         if (ret) {
 798                 talloc_free(*local_tree);
 799                 return ret;
 800         }
 801
 802         return 0;
 803 }
 804
 805 /* Collect a list of attributes required either explicitly from a
 806  * given list or implicitly  from a given parse tree; split the
 807  * collected list into local and remote parts. */
 808 static int map_attrs_collect_and_partition(struct ldb_module *module, void *local_ctx, void *remote_ctx, const char ***local_attrs, const char ***remote_attrs, const char * const *search_attrs, const struct ldb_parse_tree *tree)
 809 {
 810         void *tmp_ctx;
 811         const char **tree_attrs;
 812         int ret;
 813
 814         /* Clear initial lists of partitioned attributes */
 815         *local_attrs = NULL;
 816         *remote_attrs = NULL;
 817
 818         /* There are no searched attributes, just stick to that */
 819         if (search_attrs == NULL) {
 820                 return 0;
 821         }
 822
 823         /* There is no tree, just partition the searched attributes */
 824         if (tree == NULL) {
 825                 return map_attrs_partition(module, local_ctx, remote_ctx, local_attrs, remote_attrs, search_attrs);
 826         }
 827
 828         /* Create context for temporary memory */
 829         tmp_ctx = talloc_new(local_ctx);
 830         if (tmp_ctx == NULL) {
 831                 goto oom;
 832         }
 833
 834         /* Prepare list of attributes from tree */
 835         tree_attrs = talloc_array(tmp_ctx, const char *, 1);
 836         if (tree_attrs == NULL) {
 837                 talloc_free(tmp_ctx);
 838                 goto oom;
 839         }
 840         tree_attrs[0] = NULL;
 841
 842         /* Collect attributes from tree */
 843         ret = ldb_parse_tree_collect_attrs(module, tmp_ctx, &tree_attrs, tree);
 844         if (ret) {
 845                 goto done;
 846         }
 847
 848         /* Merge attributes from search operation */
 849         ret = map_attrs_merge(module, tmp_ctx, &tree_attrs, search_attrs);
 850         if (ret) {
 851                 goto done;
 852         }
 853
 854         /* Split local from remote attributes */
 855         ret = map_attrs_partition(module, local_ctx, remote_ctx, local_attrs, remote_attrs, tree_attrs);
 856
 857 done:
 858         /* Free temporary memory */
 859         talloc_free(tmp_ctx);
 860         return ret;
 861
 862 oom:
 863         map_oom(module);
 864         return -1;
 865 }
 866
 867
 868 /* Outbound requests: search
 869  * ========================= */
 870
 871 /* Pass a merged search result up the callback chain. */
 872 int map_up_callback(struct ldb_context *ldb, const struct ldb_request *req, struct ldb_reply *ares)
 873 {
 874         int i;
 875
 876         /* No callback registered, stop */
 877         if (req->callback == NULL) {
 878                 return LDB_SUCCESS;
 879         }
 880
 881         /* Only records need special treatment */
 882         if (ares->type != LDB_REPLY_ENTRY) {
 883                 return req->callback(ldb, req->context, ares);
 884         }
 885
 886         /* Merged result doesn't match original query, skip */
 887         if (!ldb_match_msg(ldb, ares->message, req->op.search.tree, req->op.search.base, req->op.search.scope)) {
 888                 ldb_debug(ldb, LDB_DEBUG_TRACE, "ldb_map: "
 889                           "Skipping record '%s': "
 890                           "doesn't match original search\n",
 891                           ldb_dn_linearize(ldb, ares->message->dn));
 892                 return LDB_SUCCESS;
 893         }
 894
 895         /* Limit result to requested attrs */
 896         if ((req->op.search.attrs) && (!ldb_attr_in_list(req->op.search.attrs, "*"))) {
 897                 for (i = 0; i < ares->message->num_elements; i++) {
 898                         const struct ldb_message_element *el = &ares->message->elements[i];
 899                         if (!ldb_attr_in_list(req->op.search.attrs, el->name)) {
 900                                 ldb_msg_remove_attr(ares->message, el->name);
 901                         }
 902                 }
 903         }
 904
 905         return req->callback(ldb, req->context, ares);
 906 }
 907
 908 /* Merge the remote and local parts of a search result. */
 909 int map_local_merge_callback(struct ldb_context *ldb, void *context, struct ldb_reply *ares)
 910 {
 911         struct map_search_context *sc;
 912         int ret;
 913
 914         if (context == NULL || ares == NULL) {
 915                 ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
 916                                                        "NULL Context or Result in `map_local_merge_callback`"));
 917                 return LDB_ERR_OPERATIONS_ERROR;
 918         }
 919
 920         sc = talloc_get_type(context, struct map_search_context);
 921
 922         switch (ares->type) {
 923         case LDB_REPLY_ENTRY:
 924                 /* We have already found a local record */
 925                 if (sc->local_res) {
 926                         ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
 927                                                                "Too many results to base search for local entry"));
 928                         talloc_free(ares);
 929                         return LDB_ERR_OPERATIONS_ERROR;
 930                 }
 931
 932                 /* Store local result */
 933                 sc->local_res = ares;
 934
 935                 /* Merge remote into local message */
 936                 ret = ldb_msg_merge_local(sc->ac->module, ares->message, sc->remote_res->message);
 937                 if (ret) {
 938                         talloc_free(ares);
 939                         return LDB_ERR_OPERATIONS_ERROR;
 940                 }
 941
 942                 return map_up_callback(ldb, sc->ac->orig_req, ares);
 943
 944         case LDB_REPLY_DONE:
 945                 /* No local record found, continue with remote record */
 946                 if (sc->local_res == NULL) {
 947                         return map_up_callback(ldb, sc->ac->orig_req, sc->remote_res);
 948                 }
 949                 return LDB_SUCCESS;
 950
 951         default:
 952                 ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
 953                                                        "Unexpected result type in base search for local entry"));
 954                 talloc_free(ares);
 955                 return LDB_ERR_OPERATIONS_ERROR;
 956         }
 957 }
 958
 959 /* Search the local part of a remote search result. */
 960 int map_remote_search_callback(struct ldb_context *ldb, void *context, struct ldb_reply *ares)
 961 {
 962         struct map_context *ac;
 963         struct map_search_context *sc;
 964         struct ldb_request *req;
 965         int ret;
 966
 967         if (context == NULL || ares == NULL) {
 968                 ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
 969                                                        "NULL Context or Result in `map_remote_search_callback`"));
 970                 return LDB_ERR_OPERATIONS_ERROR;
 971         }
 972
 973         ac = talloc_get_type(context, struct map_context);
 974
 975         /* It's not a record, stop searching */
 976         if (ares->type != LDB_REPLY_ENTRY) {
 977                 return map_up_callback(ldb, ac->orig_req, ares);
 978         }
 979
 980         /* Map result record into a local message */
 981         ret = map_reply_remote(ac->module, ares);
 982         if (ret) {
 983                 talloc_free(ares);
 984                 return LDB_ERR_OPERATIONS_ERROR;
 985         }
 986
 987         /* There is no local db, stop searching */
 988         if (!map_check_local_db(ac->module)) {
 989                 return map_up_callback(ldb, ac->orig_req, ares);
 990         }
 991
 992         /* Prepare local search context */
 993         sc = map_init_search_context(ac, ares);
 994         if (sc == NULL) {
 995                 talloc_free(ares);
 996                 return LDB_ERR_OPERATIONS_ERROR;
 997         }
 998
 999         /* Prepare local search request */
1000         /* TODO: use GUIDs here instead? */
1001
1002         ac->search_reqs = talloc_realloc(ac, ac->search_reqs, struct ldb_request *, ac->num_searches + 2);
1003         if (ac->search_reqs == NULL) {
1004                 talloc_free(ares);
1005                 return LDB_ERR_OPERATIONS_ERROR;
1006         }
1007
1008         ac->search_reqs[ac->num_searches]
1009                 = req = map_search_base_req(ac, ares->message->dn,
1010                                             NULL, NULL, sc, map_local_merge_callback);
1011         if (req == NULL) {
1012                 talloc_free(sc);
1013                 talloc_free(ares);
1014                 return LDB_ERR_OPERATIONS_ERROR;
1015         }
1016         ac->num_searches++;
1017         ac->search_reqs[ac->num_searches] = NULL;
1018
1019         return ldb_next_request(ac->module, req);
1020 }
1021
1022 /* Search a record. */
1023 int map_search(struct ldb_module *module, struct ldb_request *req)
1024 {
1025         struct ldb_handle *h;
1026         struct map_context *ac;
1027         struct ldb_parse_tree *local_tree, *remote_tree;
1028         const char **local_attrs, **remote_attrs;
1029         int ret;
1030
1031         /* Do not manipulate our control entries */
1032         if (ldb_dn_is_special(req->op.search.base))
1033                 return ldb_next_request(module, req);
1034
1035         /* No mapping requested, skip to next module */
1036         if ((req->op.search.base) && (!ldb_dn_check_local(module, req->op.search.base))) {
1037                 return ldb_next_request(module, req);
1038         }
1039
1040         /* TODO: How can we be sure about which partition we are
1041          *       targetting when there is no search base? */
1042
1043         /* Prepare context and handle */
1044         h = map_init_handle(req, module);
1045         if (h == NULL) {
1046                 return LDB_ERR_OPERATIONS_ERROR;
1047         }
1048         ac = talloc_get_type(h->private_data, struct map_context);
1049
1050         ac->search_reqs = talloc_array(ac, struct ldb_request *, 2);
1051         if (ac->search_reqs == NULL) {
1052                 talloc_free(h);
1053                 return LDB_ERR_OPERATIONS_ERROR;
1054         }
1055         ac->num_searches = 1;
1056         ac->search_reqs[1] = NULL;
1057
1058         /* Prepare the remote operation */
1059         ac->search_reqs[0] = talloc(ac, struct ldb_request);
1060         if (ac->search_reqs[0] == NULL) {
1061                 goto oom;
1062         }
1063
1064         *(ac->search_reqs[0]) = *req;   /* copy the request */
1065
1066         ac->search_reqs[0]->handle = h; /* return our own handle to deal with this call */
1067
1068         ac->search_reqs[0]->context = ac;
1069         ac->search_reqs[0]->callback = map_remote_search_callback;
1070
1071         /* Split local from remote attrs */
1072         ret = map_attrs_collect_and_partition(module, ac, ac->search_reqs[0], &local_attrs, &remote_attrs, req->op.search.attrs, req->op.search.tree);
1073         if (ret) {
1074                 goto failed;
1075         }
1076
1077         ac->local_attrs = local_attrs;
1078         ac->search_reqs[0]->op.search.attrs = remote_attrs;
1079
1080         /* Split local from remote tree */
1081         ret = ldb_parse_tree_partition(module, ac, ac->search_reqs[0], &local_tree, &remote_tree, req->op.search.tree);
1082         if (ret) {
1083                 goto failed;
1084         }
1085
1086         if (((local_tree != NULL) && (remote_tree != NULL)) &&
1087             (!ldb_parse_tree_check_splittable(req->op.search.tree))) {
1088                 /* The query can't safely be split, enumerate the remote partition */
1089                 local_tree = NULL;
1090                 remote_tree = NULL;
1091         }
1092
1093         if (local_tree == NULL) {
1094                 /* Construct default local parse tree */
1095                 local_tree = talloc_zero(ac, struct ldb_parse_tree);
1096                 if (local_tree == NULL) {
1097                         map_oom(ac->module);
1098                         goto failed;
1099                 }
1100
1101                 local_tree->operation = LDB_OP_PRESENT;
1102                 local_tree->u.present.attr = talloc_strdup(local_tree, IS_MAPPED);
1103         }
1104         if (remote_tree == NULL) {
1105                 /* Construct default remote parse tree */
1106                 remote_tree = ldb_parse_tree(ac->search_reqs[0], NULL);
1107                 if (remote_tree == NULL) {
1108                         goto failed;
1109                 }
1110         }
1111
1112         ac->local_tree = local_tree;
1113         ac->search_reqs[0]->op.search.tree = remote_tree;
1114
1115         ldb_set_timeout_from_prev_req(module->ldb, req, ac->search_reqs[0]);
1116
1117         h->state = LDB_ASYNC_INIT;
1118         h->status = LDB_SUCCESS;
1119
1120         ac->step = MAP_SEARCH_REMOTE;
1121
1122         ret = ldb_next_remote_request(module, ac->search_reqs[0]);
1123         if (ret == LDB_SUCCESS) {
1124                 req->handle = h;
1125         }
1126         return ret;
1127
1128 oom:
1129         map_oom(module);
1130 failed:
1131         talloc_free(h);
1132         return LDB_ERR_OPERATIONS_ERROR;
1133 }