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