s4:ldb_map_outbound - fix memory leak
[ira/wip.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    Copyright (C) Simo Sorce <idra@samba.org> 2008
8
9      ** NOTE! The following LGPL license applies to the ldb
10      ** library. This does NOT imply that all of Samba is released
11      ** under the LGPL
12    
13    This library is free software; you can redistribute it and/or
14    modify it under the terms of the GNU Lesser General Public
15    License as published by the Free Software Foundation; either
16    version 3 of the License, or (at your option) any later version.
17
18    This library is distributed in the hope that it will be useful,
19    but WITHOUT ANY WARRANTY; without even the implied warranty of
20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21    Lesser General Public License for more details.
22
23    You should have received a copy of the GNU Lesser General Public
24    License along with this library; if not, see <http://www.gnu.org/licenses/>.
25
26 */
27
28 #include "ldb_includes.h"
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         struct ldb_context *ldb;
267
268         ldb = ldb_module_get_ctx(module);
269
270         /* We handle wildcards in ldb_msg_el_merge_wildcard */
271         if (ldb_attr_cmp(attr_name, "*") == 0) {
272                 return LDB_SUCCESS;
273         }
274
275         map = map_attr_find_local(data, attr_name);
276
277         /* Unknown attribute in remote message:
278          * skip, attribute was probably auto-generated */
279         if (map == NULL) {
280                 return LDB_SUCCESS;
281         }
282
283         switch (map->type) {
284         case MAP_IGNORE:
285                 break;
286         case MAP_CONVERT:
287                 remote_name = map->u.convert.remote_name;
288                 break;
289         case MAP_KEEP:
290                 remote_name = attr_name;
291                 break;
292         case MAP_RENAME:
293                 remote_name = map->u.rename.remote_name;
294                 break;
295         case MAP_GENERATE:
296                 break;
297         }
298
299         switch (map->type) {
300         case MAP_IGNORE:
301                 return LDB_SUCCESS;
302
303         case MAP_CONVERT:
304                 if (map->u.convert.convert_remote == NULL) {
305                         ldb_debug(ldb, LDB_DEBUG_ERROR, "ldb_map: "
306                                   "Skipping attribute '%s': "
307                                   "'convert_remote' not set",
308                                   attr_name);
309                         return LDB_SUCCESS;
310                 }
311                 /* fall through */
312         case MAP_KEEP:
313         case MAP_RENAME:
314                 old = ldb_msg_find_element(remote, remote_name);
315                 if (old) {
316                         el = ldb_msg_el_map_remote(module, local, map, attr_name, old);
317                 } else {
318                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
319                 }
320                 break;
321
322         case MAP_GENERATE:
323                 if (map->u.generate.generate_local == NULL) {
324                         ldb_debug(ldb, LDB_DEBUG_ERROR, "ldb_map: "
325                                   "Skipping attribute '%s': "
326                                   "'generate_local' not set",
327                                   attr_name);
328                         return LDB_SUCCESS;
329                 }
330
331                 el = map->u.generate.generate_local(module, local, attr_name, remote);
332                 if (!el) {
333                         /* Generation failure is probably due to lack of source attributes */
334                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
335                 }
336                 break;
337         }
338
339         if (el == NULL) {
340                 return LDB_ERR_NO_SUCH_ATTRIBUTE;
341         }
342
343         return ldb_msg_replace(local, el);
344 }
345
346 /* Handle wildcard parts of merging a remote message element into a local message. */
347 static int ldb_msg_el_merge_wildcard(struct ldb_module *module, struct ldb_message *local, 
348                                      struct ldb_message *remote)
349 {
350         const struct ldb_map_context *data = map_get_context(module);
351         const struct ldb_map_attribute *map = map_attr_find_local(data, "*");
352         struct ldb_message_element *el=NULL;
353         int i, ret;
354
355         /* Perhaps we have a mapping for "*" */
356         if (map && map->type == MAP_KEEP) {
357                 /* We copy everything over, and hope that anything with a 
358                    more specific rule is overwritten */
359                 for (i = 0; i < remote->num_elements; i++) {
360                         el = ldb_msg_el_map_remote(module, local, map, remote->elements[i].name,
361                                                    &remote->elements[i]);
362                         if (el == NULL) {
363                                 return LDB_ERR_OPERATIONS_ERROR;
364                         }
365                         
366                         ret = ldb_msg_replace(local, el);
367                         if (ret) {
368                                 return ret;
369                         }
370                 }
371         }
372         
373         /* Now walk the list of possible mappings, and apply each */
374         for (i = 0; data->attribute_maps[i].local_name; i++) {
375                 ret = ldb_msg_el_merge(module, local, remote, 
376                                        data->attribute_maps[i].local_name);
377                 if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE) {
378                         continue;
379                 } else if (ret) {
380                         return ret;
381                 } else {
382                         continue;
383                 }
384         }
385
386         return LDB_SUCCESS;
387 }
388
389 /* Mapping messages
390  * ================ */
391
392 /* Merge two local messages into a single one. */
393 static int ldb_msg_merge_local(struct ldb_module *module, struct ldb_message *msg1, struct ldb_message *msg2)
394 {
395         int i, ret;
396
397         for (i = 0; i < msg2->num_elements; i++) {
398                 ret = ldb_msg_replace(msg1, &msg2->elements[i]);
399                 if (ret) {
400                         return ret;
401                 }
402         }
403
404         return LDB_SUCCESS;
405 }
406
407 /* Merge a local and a remote message into a single local one. */
408 static int ldb_msg_merge_remote(struct map_context *ac, struct ldb_message *local, 
409                                 struct ldb_message *remote)
410 {
411         int i, ret;
412         const char * const *attrs = ac->all_attrs;
413         if (!attrs) {
414                 ret = ldb_msg_el_merge_wildcard(ac->module, local, remote);
415                 if (ret) {
416                         return ret;
417                 }
418         }
419
420         for (i = 0; attrs && attrs[i]; i++) {
421                 if (ldb_attr_cmp(attrs[i], "*") == 0) {
422                         ret = ldb_msg_el_merge_wildcard(ac->module, local, remote);
423                         if (ret) {
424                                 return ret;
425                         }
426                         break;
427                 }
428         }
429
430         /* Try to map each attribute back;
431          * Add to local message is possible,
432          * Overwrite old local attribute if necessary */
433         for (i = 0; attrs && attrs[i]; i++) {
434                 ret = ldb_msg_el_merge(ac->module, local, remote, 
435                                        attrs[i]);
436                 if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE) {
437                 } else if (ret) {
438                         return ret;
439                 }
440         }
441
442         return LDB_SUCCESS;
443 }
444
445 /* Mapping search results
446  * ====================== */
447
448 /* Map a search result back into the local partition. */
449 static int map_reply_remote(struct map_context *ac, struct ldb_reply *ares)
450 {
451         struct ldb_message *msg;
452         struct ldb_dn *dn;
453         int ret;
454
455         /* There is no result message, skip */
456         if (ares->type != LDB_REPLY_ENTRY) {
457                 return 0;
458         }
459
460         /* Create a new result message */
461         msg = ldb_msg_new(ares);
462         if (msg == NULL) {
463                 map_oom(ac->module);
464                 return -1;
465         }
466
467         /* Merge remote message into new message */
468         ret = ldb_msg_merge_remote(ac, msg, ares->message);
469         if (ret) {
470                 talloc_free(msg);
471                 return ret;
472         }
473
474         /* Create corresponding local DN */
475         dn = ldb_dn_map_rebase_remote(ac->module, msg, ares->message->dn);
476         if (dn == NULL) {
477                 talloc_free(msg);
478                 return -1;
479         }
480         msg->dn = dn;
481
482         /* Store new message with new DN as the result */
483         talloc_free(ares->message);
484         ares->message = msg;
485
486         return 0;
487 }
488
489 /* Mapping parse trees
490  * =================== */
491
492 /* Check whether a parse tree can safely be split in two. */
493 static bool ldb_parse_tree_check_splittable(const struct ldb_parse_tree *tree)
494 {
495         const struct ldb_parse_tree *subtree = tree;
496         bool negate = false;
497
498         while (subtree) {
499                 switch (subtree->operation) {
500                 case LDB_OP_NOT:
501                         negate = !negate;
502                         subtree = subtree->u.isnot.child;
503                         continue;
504
505                 case LDB_OP_AND:
506                         return !negate; /* if negate: False */
507
508                 case LDB_OP_OR:
509                         return negate;  /* if negate: True */
510
511                 default:
512                         return true;    /* simple parse tree */
513                 }
514         }
515
516         return true;                    /* no parse tree */
517 }
518
519 /* Collect a list of attributes required to match a given parse tree. */
520 static int ldb_parse_tree_collect_attrs(struct ldb_module *module, void *mem_ctx, const char ***attrs, const struct ldb_parse_tree *tree)
521 {
522         const char **new_attrs;
523         int i, ret;
524
525         if (tree == NULL) {
526                 return 0;
527         }
528
529         switch (tree->operation) {
530         case LDB_OP_OR:
531         case LDB_OP_AND:                /* attributes stored in list of subtrees */
532                 for (i = 0; i < tree->u.list.num_elements; i++) {
533                         ret = ldb_parse_tree_collect_attrs(module, mem_ctx, 
534                                                            attrs, tree->u.list.elements[i]);
535                         if (ret) {
536                                 return ret;
537                         }
538                 }
539                 return 0;
540
541         case LDB_OP_NOT:                /* attributes stored in single subtree */
542                 return ldb_parse_tree_collect_attrs(module, mem_ctx, attrs, tree->u.isnot.child);
543
544         default:                        /* single attribute in tree */
545                 new_attrs = ldb_attr_list_copy_add(mem_ctx, *attrs, tree->u.equality.attr);
546                 talloc_free(*attrs);
547                 *attrs = new_attrs;
548                 return 0;
549         }
550
551         return -1;
552 }
553
554 static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
555
556 /* Select a negated subtree that queries attributes in the local partition */
557 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)
558 {
559         struct ldb_parse_tree *child;
560         int ret;
561
562         /* Prepare new tree */
563         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
564         if (*new == NULL) {
565                 map_oom(module);
566                 return -1;
567         }
568
569         /* Generate new subtree */
570         ret = map_subtree_select_local(module, *new, &child, tree->u.isnot.child);
571         if (ret) {
572                 talloc_free(*new);
573                 return ret;
574         }
575
576         /* Prune tree without subtree */
577         if (child == NULL) {
578                 talloc_free(*new);
579                 *new = NULL;
580                 return 0;
581         }
582
583         (*new)->u.isnot.child = child;
584
585         return ret;
586 }
587
588 /* Select a list of subtrees that query attributes in the local partition */
589 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)
590 {
591         int i, j, ret=0;
592
593         /* Prepare new tree */
594         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
595         if (*new == NULL) {
596                 map_oom(module);
597                 return -1;
598         }
599
600         /* Prepare list of subtrees */
601         (*new)->u.list.num_elements = 0;
602         (*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
603         if ((*new)->u.list.elements == NULL) {
604                 map_oom(module);
605                 talloc_free(*new);
606                 return -1;
607         }
608
609         /* Generate new list of subtrees */
610         j = 0;
611         for (i = 0; i < tree->u.list.num_elements; i++) {
612                 struct ldb_parse_tree *child;
613                 ret = map_subtree_select_local(module, *new, &child, tree->u.list.elements[i]);
614                 if (ret) {
615                         talloc_free(*new);
616                         return ret;
617                 }
618
619                 if (child) {
620                         (*new)->u.list.elements[j] = child;
621                         j++;
622                 }
623         }
624
625         /* Prune tree without subtrees */
626         if (j == 0) {
627                 talloc_free(*new);
628                 *new = NULL;
629                 return 0;
630         }
631
632         /* Fix subtree list size */
633         (*new)->u.list.num_elements = j;
634         (*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
635
636         return ret;
637 }
638
639 /* Select a simple subtree that queries attributes in the local partition */
640 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)
641 {
642         /* Prepare new tree */
643         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
644         if (*new == NULL) {
645                 map_oom(module);
646                 return -1;
647         }
648
649         return 0;
650 }
651
652 /* Select subtrees that query attributes in the local partition */
653 static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
654 {
655         const struct ldb_map_context *data = map_get_context(module);
656
657         if (tree == NULL) {
658                 return 0;
659         }
660
661         if (tree->operation == LDB_OP_NOT) {
662                 return map_subtree_select_local_not(module, mem_ctx, new, tree);
663         }
664
665         if (tree->operation == LDB_OP_AND || tree->operation == LDB_OP_OR) {
666                 return map_subtree_select_local_list(module, mem_ctx, new, tree);
667         }
668
669         if (map_attr_check_remote(data, tree->u.equality.attr)) {
670                 *new = NULL;
671                 return 0;
672         }
673
674         return map_subtree_select_local_simple(module, mem_ctx, new, tree);
675 }
676
677 static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
678
679 /* Collect a negated subtree that queries attributes in the remote partition */
680 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)
681 {
682         struct ldb_parse_tree *child;
683         int ret;
684
685         /* Prepare new tree */
686         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
687         if (*new == NULL) {
688                 map_oom(module);
689                 return -1;
690         }
691
692         /* Generate new subtree */
693         ret = map_subtree_collect_remote(module, *new, &child, tree->u.isnot.child);
694         if (ret) {
695                 talloc_free(*new);
696                 return ret;
697         }
698
699         /* Prune tree without subtree */
700         if (child == NULL) {
701                 talloc_free(*new);
702                 *new = NULL;
703                 return 0;
704         }
705
706         (*new)->u.isnot.child = child;
707
708         return ret;
709 }
710
711 /* Collect a list of subtrees that query attributes in the remote partition */
712 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)
713 {
714         int i, j, ret=0;
715
716         /* Prepare new tree */
717         *new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
718         if (*new == NULL) {
719                 map_oom(module);
720                 return -1;
721         }
722
723         /* Prepare list of subtrees */
724         (*new)->u.list.num_elements = 0;
725         (*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
726         if ((*new)->u.list.elements == NULL) {
727                 map_oom(module);
728                 talloc_free(*new);
729                 return -1;
730         }
731
732         /* Generate new list of subtrees */
733         j = 0;
734         for (i = 0; i < tree->u.list.num_elements; i++) {
735                 struct ldb_parse_tree *child;
736                 ret = map_subtree_collect_remote(module, *new, &child, tree->u.list.elements[i]);
737                 if (ret) {
738                         talloc_free(*new);
739                         return ret;
740                 }
741
742                 if (child) {
743                         (*new)->u.list.elements[j] = child;
744                         j++;
745                 }
746         }
747
748         /* Prune tree without subtrees */
749         if (j == 0) {
750                 talloc_free(*new);
751                 *new = NULL;
752                 return 0;
753         }
754
755         /* Fix subtree list size */
756         (*new)->u.list.num_elements = j;
757         (*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
758
759         return ret;
760 }
761
762 /* Collect a simple subtree that queries attributes in the remote partition */
763 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)
764 {
765         const char *attr;
766
767         /* Prepare new tree */
768         *new = talloc(mem_ctx, struct ldb_parse_tree);
769         if (*new == NULL) {
770                 map_oom(module);
771                 return -1;
772         }
773         **new = *tree;
774         
775         if (map->type == MAP_KEEP) {
776                 /* Nothing to do here */
777                 return 0;
778         }
779
780         /* Store attribute and value in new tree */
781         switch (tree->operation) {
782         case LDB_OP_PRESENT:
783                 attr = map_attr_map_local(*new, map, tree->u.present.attr);
784                 (*new)->u.present.attr = attr;
785                 break;
786         case LDB_OP_SUBSTRING:
787         {
788                 attr = map_attr_map_local(*new, map, tree->u.substring.attr);
789                 (*new)->u.substring.attr = attr;
790                 break;
791         }
792         case LDB_OP_EQUALITY:
793                 attr = map_attr_map_local(*new, map, tree->u.equality.attr);
794                 (*new)->u.equality.attr = attr;
795                 break;
796         case LDB_OP_LESS:
797         case LDB_OP_GREATER:
798         case LDB_OP_APPROX:
799                 attr = map_attr_map_local(*new, map, tree->u.comparison.attr);
800                 (*new)->u.comparison.attr = attr;
801                 break;
802         case LDB_OP_EXTENDED:
803                 attr = map_attr_map_local(*new, map, tree->u.extended.attr);
804                 (*new)->u.extended.attr = attr;
805                 break;
806         default:                        /* unknown kind of simple subtree */
807                 talloc_free(*new);
808                 return -1;
809         }
810
811         if (attr == NULL) {
812                 talloc_free(*new);
813                 *new = NULL;
814                 return 0;
815         }
816
817         if (map->type == MAP_RENAME) {
818                 /* Nothing more to do here, the attribute has been renamed */
819                 return 0;
820         }
821
822         /* Store attribute and value in new tree */
823         switch (tree->operation) {
824         case LDB_OP_PRESENT:
825                 break;
826         case LDB_OP_SUBSTRING:
827         {
828                 int i;
829                 /* Map value */
830                 (*new)->u.substring.chunks = NULL;
831                 for (i=0; tree->u.substring.chunks[i]; i++) {
832                         (*new)->u.substring.chunks = talloc_realloc(*new, (*new)->u.substring.chunks, struct ldb_val *, i+2);
833                         if (!(*new)->u.substring.chunks) {
834                                 talloc_free(*new);
835                                 *new = NULL;
836                                 return 0;
837                         }
838                         (*new)->u.substring.chunks[i] = talloc(*new, struct ldb_val);
839                         if (!(*new)->u.substring.chunks[i]) {
840                                 talloc_free(*new);
841                                 *new = NULL;
842                                 return 0;
843                         }
844                         *(*new)->u.substring.chunks[i] = ldb_val_map_local(module, *new, map, tree->u.substring.chunks[i]);
845                         (*new)->u.substring.chunks[i+1] = NULL;
846                 }
847                 break;
848         }
849         case LDB_OP_EQUALITY:
850                 (*new)->u.equality.value = ldb_val_map_local(module, *new, map, &tree->u.equality.value);
851                 break;
852         case LDB_OP_LESS:
853         case LDB_OP_GREATER:
854         case LDB_OP_APPROX:
855                 (*new)->u.comparison.value = ldb_val_map_local(module, *new, map, &tree->u.comparison.value);
856                 break;
857         case LDB_OP_EXTENDED:
858                 (*new)->u.extended.value = ldb_val_map_local(module, *new, map, &tree->u.extended.value);
859                 (*new)->u.extended.rule_id = talloc_strdup(*new, tree->u.extended.rule_id);
860                 break;
861         default:                        /* unknown kind of simple subtree */
862                 talloc_free(*new);
863                 return -1;
864         }
865
866         return 0;
867 }
868
869 /* Collect subtrees that query attributes in the remote partition */
870 static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
871 {
872         const struct ldb_map_context *data = map_get_context(module);
873         const struct ldb_map_attribute *map;
874         struct ldb_context *ldb;
875
876         ldb = ldb_module_get_ctx(module);
877
878         if (tree == NULL) {
879                 return 0;
880         }
881
882         if (tree->operation == LDB_OP_NOT) {
883                 return map_subtree_collect_remote_not(module, mem_ctx, new, tree);
884         }
885
886         if ((tree->operation == LDB_OP_AND) || (tree->operation == LDB_OP_OR)) {
887                 return map_subtree_collect_remote_list(module, mem_ctx, new, tree);
888         }
889
890         if (!map_attr_check_remote(data, tree->u.equality.attr)) {
891                 *new = NULL;
892                 return 0;
893         }
894
895         map = map_attr_find_local(data, tree->u.equality.attr);
896         if (map->convert_operator) {
897                 return map->convert_operator(module, mem_ctx, new, tree);
898         }
899
900         if (map->type == MAP_GENERATE) {
901                 ldb_debug(ldb, LDB_DEBUG_WARNING, "ldb_map: "
902                           "Skipping attribute '%s': "
903                           "'convert_operator' not set",
904                           tree->u.equality.attr);
905                 *new = NULL;
906                 return 0;
907         }
908
909         return map_subtree_collect_remote_simple(module, mem_ctx, new, tree, map);
910 }
911
912 /* Split subtrees that query attributes in the local partition from
913  * those that query the remote partition. */
914 static int ldb_parse_tree_partition(struct ldb_module *module,
915                                         void *mem_ctx,
916                                         struct ldb_parse_tree **local_tree,
917                                         struct ldb_parse_tree **remote_tree,
918                                         const struct ldb_parse_tree *tree)
919 {
920         int ret;
921
922         *local_tree = NULL;
923         *remote_tree = NULL;
924
925         /* No original tree */
926         if (tree == NULL) {
927                 return 0;
928         }
929
930         /* Generate local tree */
931         ret = map_subtree_select_local(module, mem_ctx, local_tree, tree);
932         if (ret) {
933                 return ret;
934         }
935
936         /* Generate remote tree */
937         ret = map_subtree_collect_remote(module, mem_ctx, remote_tree, tree);
938         if (ret) {
939                 talloc_free(*local_tree);
940                 return ret;
941         }
942
943         return 0;
944 }
945
946 /* Collect a list of attributes required either explicitly from a
947  * given list or implicitly  from a given parse tree; split the
948  * collected list into local and remote parts. */
949 static int map_attrs_collect_and_partition(struct ldb_module *module, struct map_context *ac,
950                                            const char * const *search_attrs, 
951                                            const struct ldb_parse_tree *tree)
952 {
953         void *tmp_ctx;
954         const char **tree_attrs;
955         const char **remote_attrs;
956         const char **local_attrs;
957         int ret;
958
959         /* There is no tree, just partition the searched attributes */
960         if (tree == NULL) {
961                 ret = map_attrs_partition(module, ac, 
962                                           &local_attrs, &remote_attrs, search_attrs);
963                 if (ret == 0) {
964                         ac->local_attrs = local_attrs;
965                         ac->remote_attrs = remote_attrs;
966                         ac->all_attrs = search_attrs;
967                 }
968                 return ret; 
969         }
970
971         /* Create context for temporary memory */
972         tmp_ctx = talloc_new(ac);
973         if (tmp_ctx == NULL) {
974                 goto oom;
975         }
976
977         /* Prepare list of attributes from tree */
978         tree_attrs = talloc_array(tmp_ctx, const char *, 1);
979         if (tree_attrs == NULL) {
980                 talloc_free(tmp_ctx);
981                 goto oom;
982         }
983         tree_attrs[0] = NULL;
984
985         /* Collect attributes from tree */
986         ret = ldb_parse_tree_collect_attrs(module, tmp_ctx, &tree_attrs, tree);
987         if (ret) {
988                 goto done;
989         }
990
991         /* Merge attributes from search operation */
992         ret = map_attrs_merge(module, tmp_ctx, &tree_attrs, search_attrs);
993         if (ret) {
994                 goto done;
995         }
996
997         /* Split local from remote attributes */
998         ret = map_attrs_partition(module, ac, &local_attrs, 
999                                   &remote_attrs, tree_attrs);
1000         
1001         if (ret == 0) {
1002                 ac->local_attrs = local_attrs;
1003                 ac->remote_attrs = remote_attrs;
1004                 talloc_steal(ac, tree_attrs);
1005                 ac->all_attrs = tree_attrs;
1006         }
1007 done:
1008         /* Free temporary memory */
1009         talloc_free(tmp_ctx);
1010         return ret;
1011
1012 oom:
1013         map_oom(module);
1014         return -1;
1015 }
1016
1017
1018 /* Outbound requests: search
1019  * ========================= */
1020
1021 static int map_remote_search_callback(struct ldb_request *req,
1022                                         struct ldb_reply *ares);
1023 static int map_local_merge_callback(struct ldb_request *req,
1024                                         struct ldb_reply *ares);
1025 static int map_search_local(struct map_context *ac);
1026
1027 static int map_save_entry(struct map_context *ac, struct ldb_reply *ares)
1028 {
1029         struct map_reply *mr;
1030
1031         mr = talloc_zero(ac, struct map_reply);
1032         if (mr == NULL) {
1033                 map_oom(ac->module);
1034                 return LDB_ERR_OPERATIONS_ERROR;
1035         }
1036         mr->remote = talloc_steal(mr, ares);
1037         if (ac->r_current) {
1038                 ac->r_current->next = mr;
1039         } else {
1040                 /* first entry */
1041                 ac->r_list = mr;
1042         }
1043         ac->r_current = mr;
1044
1045         return LDB_SUCCESS;
1046 }
1047
1048 /* Pass a merged search result up the callback chain. */
1049 int map_return_entry(struct map_context *ac, struct ldb_reply *ares)
1050 {
1051         struct ldb_message_element *el;
1052         const char * const *attrs;
1053         struct ldb_context *ldb;
1054         int i;
1055
1056         ldb = ldb_module_get_ctx(ac->module);
1057
1058         /* Merged result doesn't match original query, skip */
1059         if (!ldb_match_msg(ldb, ares->message,
1060                            ac->req->op.search.tree,
1061                            ac->req->op.search.base,
1062                            ac->req->op.search.scope)) {
1063                 ldb_debug(ldb, LDB_DEBUG_TRACE, "ldb_map: "
1064                           "Skipping record '%s': "
1065                           "doesn't match original search",
1066                           ldb_dn_get_linearized(ares->message->dn));
1067                 return LDB_SUCCESS;
1068         }
1069
1070         /* Limit result to requested attrs */
1071         if (ac->req->op.search.attrs &&
1072             (! ldb_attr_in_list(ac->req->op.search.attrs, "*"))) {
1073
1074                 attrs = ac->req->op.search.attrs;
1075                 i = 0;
1076
1077                 while (i < ares->message->num_elements) {
1078
1079                         el = &ares->message->elements[i];
1080                         if ( ! ldb_attr_in_list(attrs, el->name)) {
1081                                 ldb_msg_remove_element(ares->message, el);
1082                         } else {
1083                                 i++;
1084                         }
1085                 }
1086         }
1087
1088         return ldb_module_send_entry(ac->req, ares->message, ares->controls);
1089 }
1090
1091 /* Search a record. */
1092 int map_search(struct ldb_module *module, struct ldb_request *req)
1093 {
1094         struct ldb_parse_tree *remote_tree;
1095         struct ldb_parse_tree *local_tree;
1096         struct ldb_request *remote_req;
1097         struct ldb_context *ldb;
1098         struct map_context *ac;
1099         int ret;
1100
1101         const char *wildcard[] = { "*", NULL };
1102         const char * const *attrs;
1103
1104         ldb = ldb_module_get_ctx(module);
1105
1106         /* if we're not yet initialized, go to the next module */
1107         if (!ldb_module_get_private(module))
1108                 return ldb_next_request(module, req);
1109
1110         /* Do not manipulate our control entries */
1111         if (ldb_dn_is_special(req->op.search.base)) {
1112                 return ldb_next_request(module, req);
1113         }
1114
1115         /* No mapping requested, skip to next module */
1116         if ((req->op.search.base) && (!ldb_dn_check_local(module, req->op.search.base))) {
1117                 return ldb_next_request(module, req);
1118         }
1119
1120         /* TODO: How can we be sure about which partition we are
1121          *       targetting when there is no search base? */
1122
1123         /* Prepare context and handle */
1124         ac = map_init_context(module, req);
1125         if (ac == NULL) {
1126                 return LDB_ERR_OPERATIONS_ERROR;
1127         }
1128
1129         /* It is easier to deal with the two different ways of
1130          * expressing the wildcard in the same codepath */
1131         attrs = req->op.search.attrs;
1132         if (attrs == NULL) {
1133                 attrs = wildcard;
1134         }
1135
1136         /* Split local from remote attrs */
1137         ret = map_attrs_collect_and_partition(module, ac, 
1138                                               attrs, req->op.search.tree);
1139         if (ret) {
1140                 return LDB_ERR_OPERATIONS_ERROR;
1141         }
1142
1143         /* Split local from remote tree */
1144         ret = ldb_parse_tree_partition(module, ac,
1145                                        &local_tree, &remote_tree,
1146                                        req->op.search.tree);
1147         if (ret) {
1148                 return LDB_ERR_OPERATIONS_ERROR;
1149         }
1150
1151         if (((local_tree != NULL) && (remote_tree != NULL)) &&
1152             (!ldb_parse_tree_check_splittable(req->op.search.tree))) {
1153                 /* The query can't safely be split, enumerate the remote partition */
1154                 local_tree = NULL;
1155                 remote_tree = NULL;
1156         }
1157
1158         if (local_tree == NULL) {
1159                 /* Construct default local parse tree */
1160                 local_tree = talloc_zero(ac, struct ldb_parse_tree);
1161                 if (local_tree == NULL) {
1162                         map_oom(ac->module);
1163                         return LDB_ERR_OPERATIONS_ERROR;
1164                 }
1165
1166                 local_tree->operation = LDB_OP_PRESENT;
1167                 local_tree->u.present.attr = talloc_strdup(local_tree, IS_MAPPED);
1168         }
1169         if (remote_tree == NULL) {
1170                 /* Construct default remote parse tree */
1171                 remote_tree = ldb_parse_tree(ac, NULL);
1172                 if (remote_tree == NULL) {
1173                         return LDB_ERR_OPERATIONS_ERROR;
1174                 }
1175         }
1176
1177         ac->local_tree = local_tree;
1178
1179         /* Prepare the remote operation */
1180         ret = ldb_build_search_req_ex(&remote_req, ldb, ac,
1181                                       req->op.search.base,
1182                                       req->op.search.scope,
1183                                       remote_tree,
1184                                       ac->remote_attrs,
1185                                       req->controls,
1186                                       ac, map_remote_search_callback,
1187                                       req);
1188         if (ret != LDB_SUCCESS) {
1189                 return LDB_ERR_OPERATIONS_ERROR;
1190         }
1191
1192         return ldb_next_remote_request(module, remote_req);
1193 }
1194
1195 /* Now, search the local part of a remote search result. */
1196 static int map_remote_search_callback(struct ldb_request *req,
1197                                         struct ldb_reply *ares)
1198 {
1199         struct map_context *ac;
1200         int ret;
1201
1202         ac = talloc_get_type(req->context, struct map_context);
1203
1204         if (!ares) {
1205                 return ldb_module_done(ac->req, NULL, NULL,
1206                                         LDB_ERR_OPERATIONS_ERROR);
1207         }
1208         if (ares->error != LDB_SUCCESS) {
1209                 return ldb_module_done(ac->req, ares->controls,
1210                                         ares->response, ares->error);
1211         }
1212
1213         switch (ares->type) {
1214         case LDB_REPLY_REFERRAL:
1215
1216                 /* ignore referrals */
1217                 talloc_free(ares);
1218                 return LDB_SUCCESS;
1219
1220         case LDB_REPLY_ENTRY:
1221
1222                 /* Map result record into a local message */
1223                 ret = map_reply_remote(ac, ares);
1224                 if (ret) {
1225                         talloc_free(ares);
1226                         return ldb_module_done(ac->req, NULL, NULL,
1227                                                 LDB_ERR_OPERATIONS_ERROR);
1228                 }
1229
1230                 /* if we have no local db, then we can just return the reply to
1231                  * the upper layer, otherwise we must save it and process it
1232                  * when all replies ahve been gathered */
1233                 if ( ! map_check_local_db(ac->module)) {
1234                         ret = map_return_entry(ac, ares);
1235                 } else {
1236                         ret = map_save_entry(ac,ares);
1237                 }
1238
1239                 if (ret != LDB_SUCCESS) {
1240                         talloc_free(ares);
1241                         return ldb_module_done(ac->req, NULL, NULL,
1242                                                 LDB_ERR_OPERATIONS_ERROR);
1243                 }
1244                 break;
1245
1246         case LDB_REPLY_DONE:
1247
1248                 if ( ! map_check_local_db(ac->module)) {
1249                         return ldb_module_done(ac->req, ares->controls,
1250                                                 ares->response, LDB_SUCCESS);
1251                 }
1252
1253                 /* reset the pointer to the start of the list */
1254                 ac->r_current = ac->r_list;
1255
1256                 /* no entry just return */
1257                 if (ac->r_current == NULL) {
1258                         ret = ldb_module_done(ac->req, ares->controls,
1259                                                 ares->response, LDB_SUCCESS);
1260                         talloc_free(ares);
1261                         return ret;
1262                 }
1263
1264                 talloc_free(ares);
1265
1266                 ret = map_search_local(ac);
1267                 if (ret != LDB_SUCCESS) {
1268                         return ldb_module_done(ac->req, NULL, NULL, ret);
1269                 }
1270         }
1271
1272         return LDB_SUCCESS;
1273 }
1274
1275 static int map_search_local(struct map_context *ac)
1276 {
1277         struct ldb_request *search_req;
1278
1279         if (ac->r_current == NULL || ac->r_current->remote == NULL) {
1280                 return LDB_ERR_OPERATIONS_ERROR;
1281         }
1282
1283         /* Prepare local search request */
1284         /* TODO: use GUIDs here instead? */
1285         search_req = map_search_base_req(ac,
1286                                          ac->r_current->remote->message->dn,
1287                                          NULL, NULL,
1288                                          ac, map_local_merge_callback);
1289         if (search_req == NULL) {
1290                 return LDB_ERR_OPERATIONS_ERROR;
1291         }
1292
1293         return ldb_next_request(ac->module, search_req);
1294 }
1295
1296 /* Merge the remote and local parts of a search result. */
1297 int map_local_merge_callback(struct ldb_request *req, struct ldb_reply *ares)
1298 {
1299         struct ldb_context *ldb;
1300         struct map_context *ac;
1301         int ret;
1302
1303         ac = talloc_get_type(req->context, struct map_context);
1304         ldb = ldb_module_get_ctx(ac->module);
1305
1306         if (!ares) {
1307                 return ldb_module_done(ac->req, NULL, NULL,
1308                                         LDB_ERR_OPERATIONS_ERROR);
1309         }
1310         if (ares->error != LDB_SUCCESS) {
1311                 return ldb_module_done(ac->req, ares->controls,
1312                                         ares->response, ares->error);
1313         }
1314
1315         switch (ares->type) {
1316         case LDB_REPLY_ENTRY:
1317                 /* We have already found a local record */
1318                 if (ac->r_current->local) {
1319                         talloc_free(ares);
1320                         ldb_set_errstring(ldb, "ldb_map: Too many results!");
1321                         return ldb_module_done(ac->req, NULL, NULL,
1322                                                 LDB_ERR_OPERATIONS_ERROR);
1323                 }
1324
1325                 /* Store local result */
1326                 ac->r_current->local = talloc_steal(ac->r_current, ares);
1327
1328                 break;
1329
1330         case LDB_REPLY_REFERRAL:
1331                 /* ignore referrals */
1332                 talloc_free(ares);
1333                 break;
1334
1335         case LDB_REPLY_DONE:
1336                 talloc_free(ares);
1337
1338                 /* No local record found, map and send remote record */
1339                 if (ac->r_current->local != NULL) {
1340                         /* Merge remote into local message */
1341                         ret = ldb_msg_merge_local(ac->module,
1342                                                   ac->r_current->local->message,
1343                                                   ac->r_current->remote->message);
1344                         if (ret == LDB_SUCCESS) {
1345                                 ret = map_return_entry(ac, ac->r_current->local);
1346                         }
1347                         if (ret != LDB_SUCCESS) {
1348                                 return ldb_module_done(ac->req, NULL, NULL,
1349                                                         LDB_ERR_OPERATIONS_ERROR);
1350                         }
1351                 } else {
1352                         ret = map_return_entry(ac, ac->r_current->remote);
1353                         if (ret != LDB_SUCCESS) {
1354                                 return ldb_module_done(ac->req,
1355                                                         NULL, NULL, ret);
1356                         }
1357                 }
1358
1359                 if (ac->r_current->next != NULL) {
1360                         ac->r_current = ac->r_current->next;
1361                         if (ac->r_current->remote->type == LDB_REPLY_ENTRY) {
1362                                 ret = map_search_local(ac);
1363                                 if (ret != LDB_SUCCESS) {
1364                                         return ldb_module_done(ac->req,
1365                                                                NULL, NULL, ret);
1366                                 }
1367                                 break;
1368                         }
1369                 }
1370
1371                 /* ok we are done with all search, finally it is time to
1372                  * finish operations for this module */
1373                 return ldb_module_done(ac->req,
1374                                         ac->r_current->remote->controls,
1375                                         ac->r_current->remote->response,
1376                                         ac->r_current->remote->error);
1377         }
1378
1379         return LDB_SUCCESS;
1380 }