fbc097f31362ad0f3915f241c337562abd7da5b8
[kai/samba.git] / source4 / lib / ldb / ldb_map / 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      ** NOTE! The following LGPL license applies to the ldb
9      ** library. This does NOT imply that all of Samba is released
10      ** under the LGPL
11    
12    This library is free software; you can redistribute it and/or
13    modify it under the terms of the GNU Lesser General Public
14    License as published by the Free Software Foundation; either
15    version 3 of the License, or (at your option) any later version.
16
17    This library 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 GNU
20    Lesser General Public License for more details.
21
22    You should have received a copy of the GNU Lesser General Public
23    License along with this library; if not, see <http://www.gnu.org/licenses/>.
24
25 */
26
27 #include "ldb_includes.h"
28
29 #include "ldb_map.h"
30 #include "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(discard_const_p(char, 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->values = talloc_array(el, struct ldb_val, old->num_values);
232         if (el->values == NULL) {
233                 talloc_free(el);
234                 map_oom(module);
235                 return NULL;
236         }
237
238         el->name = talloc_strdup(el, attr_name);
239         if (el->name == NULL) {
240                 talloc_free(el);
241                 map_oom(module);
242                 return NULL;
243         }
244
245         for (i = 0; i < old->num_values; i++) {
246                 el->values[i] = ldb_val_map_remote(module, el->values, map, &old->values[i]);
247                 /* Conversions might fail, in which case bail */
248                 if (!el->values[i].data) {
249                         talloc_free(el);
250                         return NULL;
251                 }
252                 el->num_values++;
253         }
254
255         return el;
256 }
257
258 /* Merge a remote message element into a local message. */
259 static int ldb_msg_el_merge(struct ldb_module *module, struct ldb_message *local, 
260                             struct ldb_message *remote, const char *attr_name)
261 {
262         const struct ldb_map_context *data = map_get_context(module);
263         const struct ldb_map_attribute *map;
264         struct ldb_message_element *old, *el=NULL;
265         const char *remote_name = NULL;
266
267         /* We handle wildcards in ldb_msg_el_merge_wildcard */
268         if (ldb_attr_cmp(attr_name, "*") == 0) {
269                 return LDB_SUCCESS;
270         }
271
272         map = map_attr_find_local(data, attr_name);
273
274         /* Unknown attribute in remote message:
275          * skip, attribute was probably auto-generated */
276         if (map == NULL) {
277                 return LDB_SUCCESS;
278         }
279
280         switch (map->type) {
281         case MAP_IGNORE:
282                 break;
283         case MAP_CONVERT:
284                 remote_name = map->u.convert.remote_name;
285                 break;
286         case MAP_KEEP:
287                 remote_name = attr_name;
288                 break;
289         case MAP_RENAME:
290                 remote_name = map->u.rename.remote_name;
291                 break;
292         case MAP_GENERATE:
293                 break;
294         }
295
296         switch (map->type) {
297         case MAP_IGNORE:
298                 return LDB_SUCCESS;
299
300         case MAP_CONVERT:
301                 if (map->u.convert.convert_remote == NULL) {
302                         ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
303                                   "Skipping attribute '%s': "
304                                   "'convert_remote' not set\n",
305                                   attr_name);
306                         return LDB_SUCCESS;
307                 }
308                 /* fall through */
309         case MAP_KEEP:
310         case MAP_RENAME:
311                 old = ldb_msg_find_element(remote, remote_name);
312                 if (old) {
313                         el = ldb_msg_el_map_remote(module, local, map, attr_name, old);
314                 } else {
315                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
316                 }
317                 break;
318
319         case MAP_GENERATE:
320                 if (map->u.generate.generate_local == NULL) {
321                         ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
322                                   "Skipping attribute '%s': "
323                                   "'generate_local' not set\n",
324                                   attr_name);
325                         return LDB_SUCCESS;
326                 }
327
328                 el = map->u.generate.generate_local(module, local, attr_name, remote);
329                 if (!el) {
330                         /* Generation failure is probably due to lack of source attributes */
331                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
332                 }
333                 break;
334         }
335
336         if (el == NULL) {
337                 return LDB_ERR_NO_SUCH_ATTRIBUTE;
338         }
339
340         return ldb_msg_replace(local, el);
341 }
342
343 /* Handle wildcard parts of merging a remote message element into a local message. */
344 static int ldb_msg_el_merge_wildcard(struct ldb_module *module, struct ldb_message *local, 
345                                      struct ldb_message *remote)
346 {
347         const struct ldb_map_context *data = map_get_context(module);
348         const struct ldb_map_attribute *map = map_attr_find_local(data, "*");
349         struct ldb_message_element *el=NULL;
350         int i, ret;
351
352         /* Perhaps we have a mapping for "*" */
353         if (map && map->type == MAP_KEEP) {
354                 /* We copy everything over, and hope that anything with a 
355                    more specific rule is overwritten */
356                 for (i = 0; i < remote->num_elements; i++) {
357                         el = ldb_msg_el_map_remote(module, local, map, remote->elements[i].name,
358                                                    &remote->elements[i]);
359                         if (el == NULL) {
360                                 return LDB_ERR_OPERATIONS_ERROR;
361                         }
362                         
363                         ret = ldb_msg_replace(local, el);
364                         if (ret) {
365                                 return ret;
366                         }
367                 }
368         }
369         
370         /* Now walk the list of possible mappings, and apply each */
371         for (i = 0; data->attribute_maps[i].local_name; i++) {
372                 ret = ldb_msg_el_merge(module, local, remote, 
373                                        data->attribute_maps[i].local_name);
374                 if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE) {
375                         continue;
376                 } else if (ret) {
377                         return ret;
378                 } else {
379                         continue;
380                 }
381         }
382
383         return LDB_SUCCESS;
384 }
385
386 /* Mapping messages
387  * ================ */
388
389 /* Merge two local messages into a single one. */
390 static int ldb_msg_merge_local(struct ldb_module *module, struct ldb_message *msg1, struct ldb_message *msg2)
391 {
392         int i, ret;
393
394         for (i = 0; i < msg2->num_elements; i++) {
395                 ret = ldb_msg_replace(msg1, &msg2->elements[i]);
396                 if (ret) {
397                         return ret;
398                 }
399         }
400
401         return LDB_SUCCESS;
402 }
403
404 /* Merge a local and a remote message into a single local one. */
405 static int ldb_msg_merge_remote(struct map_context *ac, struct ldb_message *local, 
406                                 struct ldb_message *remote)
407 {
408         int i, ret;
409         const char * const *attrs = ac->all_attrs;
410         if (!attrs) {
411                 ret = ldb_msg_el_merge_wildcard(ac->module, local, remote);
412                 if (ret) {
413                         return ret;
414                 }
415         }
416
417         for (i = 0; attrs && attrs[i]; i++) {
418                 if (ldb_attr_cmp(attrs[i], "*") == 0) {
419                         ret = ldb_msg_el_merge_wildcard(ac->module, local, remote);
420                         if (ret) {
421                                 return ret;
422                         }
423                         break;
424                 }
425         }
426
427         /* Try to map each attribute back;
428          * Add to local message is possible,
429          * Overwrite old local attribute if necessary */
430         for (i = 0; attrs && attrs[i]; i++) {
431                 ret = ldb_msg_el_merge(ac->module, local, remote, 
432                                        attrs[i]);
433                 if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE) {
434                 } else if (ret) {
435                         return ret;
436                 }
437         }
438
439         return LDB_SUCCESS;
440 }
441
442 /* Mapping search results
443  * ====================== */
444
445 /* Map a search result back into the local partition. */
446 static int map_reply_remote(struct map_context *ac, struct ldb_reply *ares)
447 {
448         struct ldb_message *msg;
449         struct ldb_dn *dn;
450         int ret;
451
452         /* There is no result message, skip */
453         if (ares->type != LDB_REPLY_ENTRY) {
454                 return 0;
455         }
456
457         /* Create a new result message */
458         msg = ldb_msg_new(ares);
459         if (msg == NULL) {
460                 map_oom(ac->module);
461                 return -1;
462         }
463
464         /* Merge remote message into new message */
465         ret = ldb_msg_merge_remote(ac, msg, ares->message);
466         if (ret) {
467                 talloc_free(msg);
468                 return ret;
469         }
470
471         /* Create corresponding local DN */
472         dn = ldb_dn_map_rebase_remote(ac->module, msg, ares->message->dn);
473         if (dn == NULL) {
474                 talloc_free(msg);
475                 return -1;
476         }
477         msg->dn = dn;
478
479         /* Store new message with new DN as the result */
480         talloc_free(ares->message);
481         ares->message = msg;
482
483         return 0;
484 }
485
486 /* Mapping parse trees
487  * =================== */
488
489 /* Check whether a parse tree can safely be split in two. */
490 static bool ldb_parse_tree_check_splittable(const struct ldb_parse_tree *tree)
491 {
492         const struct ldb_parse_tree *subtree = tree;
493         bool negate = false;
494
495         while (subtree) {
496                 switch (subtree->operation) {
497                 case LDB_OP_NOT:
498                         negate = !negate;
499                         subtree = subtree->u.isnot.child;
500                         continue;
501
502                 case LDB_OP_AND:
503                         return !negate; /* if negate: False */
504
505                 case LDB_OP_OR:
506                         return negate;  /* if negate: True */
507
508                 default:
509                         return true;    /* simple parse tree */
510                 }
511         }
512
513         return true;                    /* no parse tree */
514 }
515
516 /* Collect a list of attributes required to match a given parse tree. */
517 static int ldb_parse_tree_collect_attrs(struct ldb_module *module, void *mem_ctx, const char ***attrs, const struct ldb_parse_tree *tree)
518 {
519         const char **new_attrs;
520         int i, ret;
521
522         if (tree == NULL) {
523                 return 0;
524         }
525
526         switch (tree->operation) {
527         case LDB_OP_OR:
528         case LDB_OP_AND:                /* attributes stored in list of subtrees */
529                 for (i = 0; i < tree->u.list.num_elements; i++) {
530                         ret = ldb_parse_tree_collect_attrs(module, mem_ctx, 
531                                                            attrs, tree->u.list.elements[i]);
532                         if (ret) {
533                                 return ret;
534                         }
535                 }
536                 return 0;
537
538         case LDB_OP_NOT:                /* attributes stored in single subtree */
539                 return ldb_parse_tree_collect_attrs(module, mem_ctx, attrs, tree->u.isnot.child);
540
541         default:                        /* single attribute in tree */
542                 new_attrs = ldb_attr_list_copy_add(mem_ctx, *attrs, tree->u.equality.attr);
543                 talloc_free(*attrs);
544                 *attrs = new_attrs;
545                 return 0;
546         }
547
548         return -1;
549 }
550
551 static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
552
553 /* Select a negated subtree that queries attributes in the local partition */
554 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)
555 {
556         struct ldb_parse_tree *child;
557         int ret;
558
559         /* Prepare new tree */
560         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
561         if (*new == NULL) {
562                 map_oom(module);
563                 return -1;
564         }
565
566         /* Generate new subtree */
567         ret = map_subtree_select_local(module, *new, &child, tree->u.isnot.child);
568         if (ret) {
569                 talloc_free(*new);
570                 return ret;
571         }
572
573         /* Prune tree without subtree */
574         if (child == NULL) {
575                 talloc_free(*new);
576                 *new = NULL;
577                 return 0;
578         }
579
580         (*new)->u.isnot.child = child;
581
582         return ret;
583 }
584
585 /* Select a list of subtrees that query attributes in the local partition */
586 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)
587 {
588         int i, j, ret=0;
589
590         /* Prepare new tree */
591         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
592         if (*new == NULL) {
593                 map_oom(module);
594                 return -1;
595         }
596
597         /* Prepare list of subtrees */
598         (*new)->u.list.num_elements = 0;
599         (*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
600         if ((*new)->u.list.elements == NULL) {
601                 map_oom(module);
602                 talloc_free(*new);
603                 return -1;
604         }
605
606         /* Generate new list of subtrees */
607         j = 0;
608         for (i = 0; i < tree->u.list.num_elements; i++) {
609                 struct ldb_parse_tree *child;
610                 ret = map_subtree_select_local(module, *new, &child, tree->u.list.elements[i]);
611                 if (ret) {
612                         talloc_free(*new);
613                         return ret;
614                 }
615
616                 if (child) {
617                         (*new)->u.list.elements[j] = child;
618                         j++;
619                 }
620         }
621
622         /* Prune tree without subtrees */
623         if (j == 0) {
624                 talloc_free(*new);
625                 *new = NULL;
626                 return 0;
627         }
628
629         /* Fix subtree list size */
630         (*new)->u.list.num_elements = j;
631         (*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
632
633         return ret;
634 }
635
636 /* Select a simple subtree that queries attributes in the local partition */
637 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)
638 {
639         /* Prepare new tree */
640         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
641         if (*new == NULL) {
642                 map_oom(module);
643                 return -1;
644         }
645
646         return 0;
647 }
648
649 /* Select subtrees that query attributes in the local partition */
650 static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
651 {
652         const struct ldb_map_context *data = map_get_context(module);
653
654         if (tree == NULL) {
655                 return 0;
656         }
657
658         if (tree->operation == LDB_OP_NOT) {
659                 return map_subtree_select_local_not(module, mem_ctx, new, tree);
660         }
661
662         if (tree->operation == LDB_OP_AND || tree->operation == LDB_OP_OR) {
663                 return map_subtree_select_local_list(module, mem_ctx, new, tree);
664         }
665
666         if (map_attr_check_remote(data, tree->u.equality.attr)) {
667                 *new = NULL;
668                 return 0;
669         }
670
671         return map_subtree_select_local_simple(module, mem_ctx, new, tree);
672 }
673
674 static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
675
676 /* Collect a negated subtree that queries attributes in the remote partition */
677 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)
678 {
679         struct ldb_parse_tree *child;
680         int ret;
681
682         /* Prepare new tree */
683         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
684         if (*new == NULL) {
685                 map_oom(module);
686                 return -1;
687         }
688
689         /* Generate new subtree */
690         ret = map_subtree_collect_remote(module, *new, &child, tree->u.isnot.child);
691         if (ret) {
692                 talloc_free(*new);
693                 return ret;
694         }
695
696         /* Prune tree without subtree */
697         if (child == NULL) {
698                 talloc_free(*new);
699                 *new = NULL;
700                 return 0;
701         }
702
703         (*new)->u.isnot.child = child;
704
705         return ret;
706 }
707
708 /* Collect a list of subtrees that query attributes in the remote partition */
709 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)
710 {
711         int i, j, ret=0;
712
713         /* Prepare new tree */
714         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
715         if (*new == NULL) {
716                 map_oom(module);
717                 return -1;
718         }
719
720         /* Prepare list of subtrees */
721         (*new)->u.list.num_elements = 0;
722         (*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
723         if ((*new)->u.list.elements == NULL) {
724                 map_oom(module);
725                 talloc_free(*new);
726                 return -1;
727         }
728
729         /* Generate new list of subtrees */
730         j = 0;
731         for (i = 0; i < tree->u.list.num_elements; i++) {
732                 struct ldb_parse_tree *child;
733                 ret = map_subtree_collect_remote(module, *new, &child, tree->u.list.elements[i]);
734                 if (ret) {
735                         talloc_free(*new);
736                         return ret;
737                 }
738
739                 if (child) {
740                         (*new)->u.list.elements[j] = child;
741                         j++;
742                 }
743         }
744
745         /* Prune tree without subtrees */
746         if (j == 0) {
747                 talloc_free(*new);
748                 *new = NULL;
749                 return 0;
750         }
751
752         /* Fix subtree list size */
753         (*new)->u.list.num_elements = j;
754         (*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
755
756         return ret;
757 }
758
759 /* Collect a simple subtree that queries attributes in the remote partition */
760 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)
761 {
762         const char *attr;
763
764         /* Prepare new tree */
765         *new = talloc(mem_ctx, struct ldb_parse_tree);
766         if (*new == NULL) {
767                 map_oom(module);
768                 return -1;
769         }
770         **new = *tree;
771         
772         if (map->type == MAP_KEEP) {
773                 /* Nothing to do here */
774                 return 0;
775         }
776
777         /* Store attribute and value in new tree */
778         switch (tree->operation) {
779         case LDB_OP_PRESENT:
780                 attr = map_attr_map_local(*new, map, tree->u.present.attr);
781                 (*new)->u.present.attr = attr;
782                 break;
783         case LDB_OP_SUBSTRING:
784         {
785                 attr = map_attr_map_local(*new, map, tree->u.substring.attr);
786                 (*new)->u.substring.attr = attr;
787                 break;
788         }
789         case LDB_OP_EQUALITY:
790                 attr = map_attr_map_local(*new, map, tree->u.equality.attr);
791                 (*new)->u.equality.attr = attr;
792                 break;
793         case LDB_OP_LESS:
794         case LDB_OP_GREATER:
795         case LDB_OP_APPROX:
796                 attr = map_attr_map_local(*new, map, tree->u.comparison.attr);
797                 (*new)->u.comparison.attr = attr;
798                 break;
799         case LDB_OP_EXTENDED:
800                 attr = map_attr_map_local(*new, map, tree->u.extended.attr);
801                 (*new)->u.extended.attr = attr;
802                 break;
803         default:                        /* unknown kind of simple subtree */
804                 talloc_free(*new);
805                 return -1;
806         }
807
808         if (attr == NULL) {
809                 talloc_free(*new);
810                 *new = NULL;
811                 return 0;
812         }
813
814         if (map->type == MAP_RENAME) {
815                 /* Nothing more to do here, the attribute has been renamed */
816                 return 0;
817         }
818
819         /* Store attribute and value in new tree */
820         switch (tree->operation) {
821         case LDB_OP_PRESENT:
822                 break;
823         case LDB_OP_SUBSTRING:
824         {
825                 int i;
826                 /* Map value */
827                 (*new)->u.substring.chunks = NULL;
828                 for (i=0; tree->u.substring.chunks[i]; i++) {
829                         (*new)->u.substring.chunks = talloc_realloc(*new, (*new)->u.substring.chunks, struct ldb_val *, i+2);
830                         if (!(*new)->u.substring.chunks) {
831                                 talloc_free(*new);
832                                 *new = NULL;
833                                 return 0;
834                         }
835                         (*new)->u.substring.chunks[i] = talloc(*new, struct ldb_val);
836                         if (!(*new)->u.substring.chunks[i]) {
837                                 talloc_free(*new);
838                                 *new = NULL;
839                                 return 0;
840                         }
841                         *(*new)->u.substring.chunks[i] = ldb_val_map_local(module, *new, map, tree->u.substring.chunks[i]);
842                         (*new)->u.substring.chunks[i+1] = NULL;
843                 }
844                 break;
845         }
846         case LDB_OP_EQUALITY:
847                 (*new)->u.equality.value = ldb_val_map_local(module, *new, map, &tree->u.equality.value);
848                 break;
849         case LDB_OP_LESS:
850         case LDB_OP_GREATER:
851         case LDB_OP_APPROX:
852                 (*new)->u.comparison.value = ldb_val_map_local(module, *new, map, &tree->u.comparison.value);
853                 break;
854         case LDB_OP_EXTENDED:
855                 (*new)->u.extended.value = ldb_val_map_local(module, *new, map, &tree->u.extended.value);
856                 (*new)->u.extended.rule_id = talloc_strdup(*new, tree->u.extended.rule_id);
857                 break;
858         default:                        /* unknown kind of simple subtree */
859                 talloc_free(*new);
860                 return -1;
861         }
862
863         return 0;
864 }
865
866 /* Collect subtrees that query attributes in the remote partition */
867 static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
868 {
869         const struct ldb_map_context *data = map_get_context(module);
870         const struct ldb_map_attribute *map;
871
872         if (tree == NULL) {
873                 return 0;
874         }
875
876         if (tree->operation == LDB_OP_NOT) {
877                 return map_subtree_collect_remote_not(module, mem_ctx, new, tree);
878         }
879
880         if ((tree->operation == LDB_OP_AND) || (tree->operation == LDB_OP_OR)) {
881                 return map_subtree_collect_remote_list(module, mem_ctx, new, tree);
882         }
883
884         if (!map_attr_check_remote(data, tree->u.equality.attr)) {
885                 *new = NULL;
886                 return 0;
887         }
888
889         map = map_attr_find_local(data, tree->u.equality.attr);
890         if (map->convert_operator) {
891                 return map->convert_operator(module, mem_ctx, new, tree);
892         }
893
894         if (map->type == MAP_GENERATE) {
895                 ldb_debug(module->ldb, LDB_DEBUG_WARNING, "ldb_map: "
896                           "Skipping attribute '%s': "
897                           "'convert_operator' not set\n",
898                           tree->u.equality.attr);
899                 *new = NULL;
900                 return 0;
901         }
902
903         return map_subtree_collect_remote_simple(module, mem_ctx, new, tree, map);
904 }
905
906 /* Split subtrees that query attributes in the local partition from
907  * those that query the remote partition. */
908 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)
909 {
910         int ret;
911
912         *local_tree = NULL;
913         *remote_tree = NULL;
914
915         /* No original tree */
916         if (tree == NULL) {
917                 return 0;
918         }
919
920         /* Generate local tree */
921         ret = map_subtree_select_local(module, local_ctx, local_tree, tree);
922         if (ret) {
923                 return ret;
924         }
925
926         /* Generate remote tree */
927         ret = map_subtree_collect_remote(module, remote_ctx, remote_tree, tree);
928         if (ret) {
929                 talloc_free(*local_tree);
930                 return ret;
931         }
932
933         return 0;
934 }
935
936 /* Collect a list of attributes required either explicitly from a
937  * given list or implicitly  from a given parse tree; split the
938  * collected list into local and remote parts. */
939 static int map_attrs_collect_and_partition(struct ldb_module *module, struct map_context *ac,
940                                            const char * const *search_attrs, 
941                                            const struct ldb_parse_tree *tree)
942 {
943         void *tmp_ctx;
944         const char **tree_attrs;
945         const char **remote_attrs;
946         const char **local_attrs;
947         int ret;
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_get_linearized(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         if (!module->private_data) /* if we're not yet initialized, go to the next module */
1176                 return ldb_next_request(module, req);
1177
1178         /* Do not manipulate our control entries */
1179         if (ldb_dn_is_special(req->op.search.base))
1180                 return ldb_next_request(module, req);
1181
1182         /* No mapping requested, skip to next module */
1183         if ((req->op.search.base) && (!ldb_dn_check_local(module, req->op.search.base))) {
1184                 return ldb_next_request(module, req);
1185         }
1186
1187         /* TODO: How can we be sure about which partition we are
1188          *       targetting when there is no search base? */
1189
1190         /* Prepare context and handle */
1191         h = map_init_handle(req, module);
1192         if (h == NULL) {
1193                 return LDB_ERR_OPERATIONS_ERROR;
1194         }
1195         ac = talloc_get_type(h->private_data, struct map_context);
1196
1197         ac->search_reqs = talloc_array(ac, struct ldb_request *, 2);
1198         if (ac->search_reqs == NULL) {
1199                 talloc_free(h);
1200                 return LDB_ERR_OPERATIONS_ERROR;
1201         }
1202         ac->num_searches = 1;
1203         ac->search_reqs[1] = NULL;
1204
1205         /* Prepare the remote operation */
1206         ac->search_reqs[0] = talloc(ac, struct ldb_request);
1207         if (ac->search_reqs[0] == NULL) {
1208                 goto oom;
1209         }
1210
1211         *(ac->search_reqs[0]) = *req;   /* copy the request */
1212
1213         ac->search_reqs[0]->handle = h; /* return our own handle to deal with this call */
1214
1215         ac->search_reqs[0]->context = ac;
1216         ac->search_reqs[0]->callback = map_remote_search_callback;
1217
1218         /* It is easier to deal with the two different ways of
1219          * expressing the wildcard in the same codepath */
1220         attrs = req->op.search.attrs;
1221         if (attrs == NULL) {
1222                 attrs = wildcard;
1223         }
1224
1225         /* Split local from remote attrs */
1226         ret = map_attrs_collect_and_partition(module, ac, 
1227                                               attrs, req->op.search.tree);
1228         if (ret) {
1229                 goto failed;
1230         }
1231
1232         ac->search_reqs[0]->op.search.attrs = ac->remote_attrs;
1233
1234         /* Split local from remote tree */
1235         ret = ldb_parse_tree_partition(module, ac, ac->search_reqs[0], 
1236                                        &local_tree, &remote_tree, 
1237                                        req->op.search.tree);
1238         if (ret) {
1239                 goto failed;
1240         }
1241
1242         if (((local_tree != NULL) && (remote_tree != NULL)) &&
1243             (!ldb_parse_tree_check_splittable(req->op.search.tree))) {
1244                 /* The query can't safely be split, enumerate the remote partition */
1245                 local_tree = NULL;
1246                 remote_tree = NULL;
1247         }
1248
1249         if (local_tree == NULL) {
1250                 /* Construct default local parse tree */
1251                 local_tree = talloc_zero(ac, struct ldb_parse_tree);
1252                 if (local_tree == NULL) {
1253                         map_oom(ac->module);
1254                         goto failed;
1255                 }
1256
1257                 local_tree->operation = LDB_OP_PRESENT;
1258                 local_tree->u.present.attr = talloc_strdup(local_tree, IS_MAPPED);
1259         }
1260         if (remote_tree == NULL) {
1261                 /* Construct default remote parse tree */
1262                 remote_tree = ldb_parse_tree(ac->search_reqs[0], NULL);
1263                 if (remote_tree == NULL) {
1264                         goto failed;
1265                 }
1266         }
1267
1268         ac->local_tree = local_tree;
1269         ac->search_reqs[0]->op.search.tree = remote_tree;
1270
1271         ldb_set_timeout_from_prev_req(module->ldb, req, ac->search_reqs[0]);
1272
1273         h->state = LDB_ASYNC_INIT;
1274         h->status = LDB_SUCCESS;
1275
1276         ac->step = MAP_SEARCH_REMOTE;
1277
1278         ret = ldb_next_remote_request(module, ac->search_reqs[0]);
1279         if (ret == LDB_SUCCESS) {
1280                 req->handle = h;
1281         }
1282         return ret;
1283
1284 oom:
1285         map_oom(module);
1286 failed:
1287         talloc_free(h);
1288         return LDB_ERR_OPERATIONS_ERROR;
1289 }