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