source4/lib/ldb/common/ldb_dn.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Simo Sorce 2005
   5
   6      ** NOTE! The following LGPL license applies to the ldb
   7      ** library. This does NOT imply that all of Samba is released
   8      ** under the LGPL
   9
  10    This library is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU Lesser General Public
  12    License as published by the Free Software Foundation; either
  13    version 3 of the License, or (at your option) any later version.
  14
  15    This library is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    Lesser General Public License for more details.
  19
  20    You should have received a copy of the GNU Lesser General Public
  21    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  22 */
  23
  24 /*
  25  *  Name: ldb
  26  *
  27  *  Component: ldb dn creation and manipulation utility functions
  28  *
  29  *  Description: - explode a dn into it's own basic elements
  30  *                 and put them in a structure (only if necessary)
  31  *               - manipulate ldb_dn structures
  32  *
  33  *  Author: Simo Sorce
  34  */
  35
  36 #include "ldb_private.h"
  37 #include <ctype.h>
  38
  39 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
  40
  41 #define LDB_FREE(x) do { talloc_free(x); x = NULL; } while(0)
  42
  43 /**
  44    internal ldb exploded dn structures
  45 */
  46 struct ldb_dn_component {
  47
  48         char *name;
  49         struct ldb_val value;
  50
  51         char *cf_name;
  52         struct ldb_val cf_value;
  53 };
  54
  55 struct ldb_dn_ext_component {
  56
  57         char *name;
  58         struct ldb_val value;
  59 };
  60
  61 struct ldb_dn {
  62
  63         struct ldb_context *ldb;
  64
  65         /* Special DNs are always linearized */
  66         bool special;
  67         bool invalid;
  68
  69         bool valid_case;
  70
  71         char *linearized;
  72         char *ext_linearized;
  73         char *casefold;
  74
  75         unsigned int comp_num;
  76         struct ldb_dn_component *components;
  77
  78         unsigned int ext_comp_num;
  79         struct ldb_dn_ext_component *ext_components;
  80 };
  81
  82 /* it is helpful to be able to break on this in gdb */
  83 static void ldb_dn_mark_invalid(struct ldb_dn *dn)
  84 {
  85         dn->invalid = true;
  86 }
  87
  88 /* strdn may be NULL */
  89 struct ldb_dn *ldb_dn_from_ldb_val(void *mem_ctx,
  90                                    struct ldb_context *ldb,
  91                                    const struct ldb_val *strdn)
  92 {
  93         struct ldb_dn *dn;
  94
  95         if (! ldb) return NULL;
  96
  97         if (strdn && strdn->data
  98             && (strnlen((const char*)strdn->data, strdn->length) != strdn->length)) {
  99                 /* The RDN must not contain a character with value 0x0 */
 100                 return NULL;
 101         }
 102
 103         dn = talloc_zero(mem_ctx, struct ldb_dn);
 104         LDB_DN_NULL_FAILED(dn);
 105
 106         dn->ldb = talloc_get_type(ldb, struct ldb_context);
 107         if (dn->ldb == NULL) {
 108                 /* the caller probably got the arguments to
 109                    ldb_dn_new() mixed up */
 110                 talloc_free(dn);
 111                 return NULL;
 112         }
 113
 114         if (strdn->data && strdn->length) {
 115                 const char *data = (const char *)strdn->data;
 116                 size_t length = strdn->length;
 117
 118                 if (data[0] == '@') {
 119                         dn->special = true;
 120                 }
 121                 dn->ext_linearized = talloc_strndup(dn, data, length);
 122                 LDB_DN_NULL_FAILED(dn->ext_linearized);
 123
 124                 if (data[0] == '<') {
 125                         const char *p_save, *p = dn->ext_linearized;
 126                         do {
 127                                 p_save = p;
 128                                 p = strstr(p, ">;");
 129                                 if (p) {
 130                                         p = p + 2;
 131                                 }
 132                         } while (p);
 133
 134                         if (p_save == dn->ext_linearized) {
 135                                 dn->linearized = talloc_strdup(dn, "");
 136                         } else {
 137                                 dn->linearized = talloc_strdup(dn, p_save);
 138                         }
 139                         LDB_DN_NULL_FAILED(dn->linearized);
 140                 } else {
 141                         dn->linearized = dn->ext_linearized;
 142                         dn->ext_linearized = NULL;
 143                 }
 144         } else {
 145                 dn->linearized = talloc_strdup(dn, "");
 146                 LDB_DN_NULL_FAILED(dn->linearized);
 147         }
 148
 149         return dn;
 150
 151 failed:
 152         talloc_free(dn);
 153         return NULL;
 154 }
 155
 156 /* strdn may be NULL */
 157 struct ldb_dn *ldb_dn_new(void *mem_ctx,
 158                           struct ldb_context *ldb,
 159                           const char *strdn)
 160 {
 161         struct ldb_val blob;
 162         blob.data = discard_const_p(uint8_t, strdn);
 163         blob.length = strdn ? strlen(strdn) : 0;
 164         return ldb_dn_from_ldb_val(mem_ctx, ldb, &blob);
 165 }
 166
 167 struct ldb_dn *ldb_dn_new_fmt(void *mem_ctx,
 168                               struct ldb_context *ldb,
 169                               const char *new_fmt, ...)
 170 {
 171         char *strdn;
 172         va_list ap;
 173
 174         if ( (! mem_ctx) || (! ldb)) return NULL;
 175
 176         va_start(ap, new_fmt);
 177         strdn = talloc_vasprintf(mem_ctx, new_fmt, ap);
 178         va_end(ap);
 179
 180         if (strdn) {
 181                 struct ldb_dn *dn = ldb_dn_new(mem_ctx, ldb, strdn);
 182                 talloc_free(strdn);
 183                 return dn;
 184         }
 185
 186         return NULL;
 187 }
 188
 189 /* see RFC2253 section 2.4 */
 190 static int ldb_dn_escape_internal(char *dst, const char *src, int len)
 191 {
 192         const char *p, *s;
 193         char *d;
 194         int l;
 195
 196         p = s = src;
 197         d = dst;
 198
 199         while (p - src < len) {
 200                 p += strcspn(p, ",=\n\r+<>#;\\\" ");
 201
 202                 if (p - src == len) /* found no escapable chars */
 203                         break;
 204
 205                 /* copy the part of the string before the stop */
 206                 memcpy(d, s, p - s);
 207                 d += (p - s); /* move to current position */
 208
 209                 switch (*p) {
 210                 case ' ':
 211                         if (p == src || (p-src)==(len-1)) {
 212                                 /* if at the beginning or end
 213                                  * of the string then escape */
 214                                 *d++ = '\\';
 215                                 *d++ = *p++;
 216                         } else {
 217                                 /* otherwise don't escape */
 218                                 *d++ = *p++;
 219                         }
 220                         break;
 221
 222                 case '#':
 223                         /* despite the RFC, windows escapes a #
 224                            anywhere in the string */
 225                 case ',':
 226                 case '+':
 227                 case '"':
 228                 case '\\':
 229                 case '<':
 230                 case '>':
 231                 case '?':
 232                         /* these must be escaped using \c form */
 233                         *d++ = '\\';
 234                         *d++ = *p++;
 235                         break;
 236
 237                 default: {
 238                         /* any others get \XX form */
 239                         unsigned char v;
 240                         const char *hexbytes = "0123456789ABCDEF";
 241                         v = *(const unsigned char *)p;
 242                         *d++ = '\\';
 243                         *d++ = hexbytes[v>>4];
 244                         *d++ = hexbytes[v&0xF];
 245                         p++;
 246                         break;
 247                 }
 248                 }
 249                 s = p; /* move forward */
 250         }
 251
 252         /* copy the last part (with zero) and return */
 253         l = len - (s - src);
 254         memcpy(d, s, l + 1);
 255
 256         /* return the length of the resulting string */
 257         return (l + (d - dst));
 258 }
 259
 260 char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
 261 {
 262         char *dst;
 263
 264         if (!value.length)
 265                 return NULL;
 266
 267         /* allocate destination string, it will be at most 3 times the source */
 268         dst = talloc_array(mem_ctx, char, value.length * 3 + 1);
 269         if ( ! dst) {
 270                 talloc_free(dst);
 271                 return NULL;
 272         }
 273
 274         ldb_dn_escape_internal(dst, (const char *)value.data, value.length);
 275
 276         dst = talloc_realloc(mem_ctx, dst, char, strlen(dst) + 1);
 277
 278         return dst;
 279 }
 280
 281 /*
 282   explode a DN string into a ldb_dn structure
 283   based on RFC4514 except that we don't support multiple valued RDNs
 284
 285   TODO: according to MS-ADTS:3.1.1.5.2 Naming Constraints
 286   DN must be compliant with RFC2253
 287 */
 288 static bool ldb_dn_explode(struct ldb_dn *dn)
 289 {
 290         char *p, *ex_name, *ex_value, *data, *d, *dt, *t;
 291         bool trim = false;
 292         bool in_extended = false;
 293         bool in_ex_name = false;
 294         bool in_ex_value = false;
 295         bool in_attr = false;
 296         bool in_value = false;
 297         bool in_quote = false;
 298         bool is_oid = false;
 299         bool escape = false;
 300         unsigned x;
 301         int l, ret;
 302         char *parse_dn;
 303         bool is_index;
 304
 305         if ( ! dn || dn->invalid) return false;
 306
 307         if (dn->components) {
 308                 return true;
 309         }
 310
 311         if (dn->ext_linearized) {
 312                 parse_dn = dn->ext_linearized;
 313         } else {
 314                 parse_dn = dn->linearized;
 315         }
 316
 317         if ( ! parse_dn ) {
 318                 return false;
 319         }
 320
 321         is_index = (strncmp(parse_dn, "DN=@INDEX:", 10) == 0);
 322
 323         /* Empty DNs */
 324         if (parse_dn[0] == '\0') {
 325                 return true;
 326         }
 327
 328         /* Special DNs case */
 329         if (dn->special) {
 330                 return true;
 331         }
 332
 333         /* make sure we free this if alloced previously before replacing */
 334         talloc_free(dn->components);
 335
 336         LDB_FREE(dn->ext_components);
 337         dn->ext_comp_num = 0;
 338
 339         /* in the common case we have 3 or more components */
 340         /* make sure all components are zeroed, other functions depend on it */
 341         dn->components = talloc_zero_array(dn, struct ldb_dn_component, 3);
 342         if ( ! dn->components) {
 343                 return false;
 344         }
 345         dn->comp_num = 0;
 346
 347         /* Components data space is allocated here once */
 348         data = talloc_array(dn->components, char, strlen(parse_dn) + 1);
 349         if (!data) {
 350                 return false;
 351         }
 352
 353         p = parse_dn;
 354         in_extended = true;
 355         in_ex_name = false;
 356         in_ex_value = false;
 357         trim = true;
 358         t = NULL;
 359         d = dt = data;
 360
 361         while (*p) {
 362                 if (in_extended) {
 363
 364                         if (!in_ex_name && !in_ex_value) {
 365
 366                                 if (p[0] == '<') {
 367                                         p++;
 368                                         ex_name = d;
 369                                         in_ex_name = true;
 370                                         continue;
 371                                 } else if (p[0] == '\0') {
 372                                         p++;
 373                                         continue;
 374                                 } else {
 375                                         in_extended = false;
 376                                         in_attr = true;
 377                                         dt = d;
 378
 379                                         continue;
 380                                 }
 381                         }
 382
 383                         if (in_ex_name && *p == '=') {
 384                                 *d++ = '\0';
 385                                 p++;
 386                                 ex_value = d;
 387                                 in_ex_name = false;
 388                                 in_ex_value = true;
 389                                 continue;
 390                         }
 391
 392                         if (in_ex_value && *p == '>') {
 393                                 const struct ldb_dn_extended_syntax *ext_syntax;
 394                                 struct ldb_val ex_val = {
 395                                         .data = (uint8_t *)ex_value,
 396                                         .length = d - ex_value
 397                                 };
 398
 399                                 *d++ = '\0';
 400                                 p++;
 401                                 in_ex_value = false;
 402
 403                                 /* Process name and ex_value */
 404
 405                                 dn->ext_components = talloc_realloc(dn,
 406                                                                     dn->ext_components,
 407                                                                     struct ldb_dn_ext_component,
 408                                                                     dn->ext_comp_num + 1);
 409                                 if ( ! dn->ext_components) {
 410                                         /* ouch ! */
 411                                         goto failed;
 412                                 }
 413
 414                                 ext_syntax = ldb_dn_extended_syntax_by_name(dn->ldb, ex_name);
 415                                 if (!ext_syntax) {
 416                                         /* We don't know about this type of extended DN */
 417                                         goto failed;
 418                                 }
 419
 420                                 dn->ext_components[dn->ext_comp_num].name = talloc_strdup(dn->ext_components, ex_name);
 421                                 if (!dn->ext_components[dn->ext_comp_num].name) {
 422                                         /* ouch */
 423                                         goto failed;
 424                                 }
 425                                 ret = ext_syntax->read_fn(dn->ldb, dn->ext_components,
 426                                                           &ex_val, &dn->ext_components[dn->ext_comp_num].value);
 427                                 if (ret != LDB_SUCCESS) {
 428                                         ldb_dn_mark_invalid(dn);
 429                                         goto failed;
 430                                 }
 431
 432                                 dn->ext_comp_num++;
 433
 434                                 if (*p == '\0') {
 435                                         /* We have reached the end (extended component only)! */
 436                                         talloc_free(data);
 437                                         return true;
 438
 439                                 } else if (*p == ';') {
 440                                         p++;
 441                                         continue;
 442                                 } else {
 443                                         ldb_dn_mark_invalid(dn);
 444                                         goto failed;
 445                                 }
 446                         }
 447
 448                         *d++ = *p++;
 449                         continue;
 450                 }
 451                 if (in_attr) {
 452                         if (trim) {
 453                                 if (*p == ' ') {
 454                                         p++;
 455                                         continue;
 456                                 }
 457
 458                                 /* first char */
 459                                 trim = false;
 460
 461                                 if (!isascii(*p)) {
 462                                         /* attr names must be ascii only */
 463                                         ldb_dn_mark_invalid(dn);
 464                                         goto failed;
 465                                 }
 466
 467                                 if (isdigit(*p)) {
 468                                         is_oid = true;
 469                                 } else
 470                                 if ( ! isalpha(*p)) {
 471                                         /* not a digit nor an alpha,
 472                                          * invalid attribute name */
 473                                         ldb_dn_mark_invalid(dn);
 474                                         goto failed;
 475                                 }
 476
 477                                 /* Copy this character across from parse_dn,
 478                                  * now we have trimmed out spaces */
 479                                 *d++ = *p++;
 480                                 continue;
 481                         }
 482
 483                         if (*p == ' ') {
 484                                 p++;
 485                                 /* valid only if we are at the end */
 486                                 trim = true;
 487                                 continue;
 488                         }
 489
 490                         if (trim && (*p != '=')) {
 491                                 /* spaces/tabs are not allowed */
 492                                 ldb_dn_mark_invalid(dn);
 493                                 goto failed;
 494                         }
 495
 496                         if (*p == '=') {
 497                                 /* attribute terminated */
 498                                 in_attr = false;
 499                                 in_value = true;
 500                                 trim = true;
 501                                 l = 0;
 502
 503                                 /* Terminate this string in d
 504                                  * (which is a copy of parse_dn
 505                                  *  with spaces trimmed) */
 506                                 *d++ = '\0';
 507                                 dn->components[dn->comp_num].name = talloc_strdup(dn->components, dt);
 508                                 if ( ! dn->components[dn->comp_num].name) {
 509                                         /* ouch */
 510                                         goto failed;
 511                                 }
 512
 513                                 dt = d;
 514
 515                                 p++;
 516                                 continue;
 517                         }
 518
 519                         if (!isascii(*p)) {
 520                                 /* attr names must be ascii only */
 521                                 ldb_dn_mark_invalid(dn);
 522                                 goto failed;
 523                         }
 524
 525                         if (is_oid && ( ! (isdigit(*p) || (*p == '.')))) {
 526                                 /* not a digit nor a dot,
 527                                  * invalid attribute oid */
 528                                 ldb_dn_mark_invalid(dn);
 529                                 goto failed;
 530                         } else
 531                         if ( ! (isalpha(*p) || isdigit(*p) || (*p == '-'))) {
 532                                 /* not ALPHA, DIGIT or HYPHEN */
 533                                 ldb_dn_mark_invalid(dn);
 534                                 goto failed;
 535                         }
 536
 537                         *d++ = *p++;
 538                         continue;
 539                 }
 540
 541                 if (in_value) {
 542                         if (in_quote) {
 543                                 if (*p == '\"') {
 544                                         if (p[-1] != '\\') {
 545                                                 p++;
 546                                                 in_quote = false;
 547                                                 continue;
 548                                         }
 549                                 }
 550                                 *d++ = *p++;
 551                                 l++;
 552                                 continue;
 553                         }
 554
 555                         if (trim) {
 556                                 if (*p == ' ') {
 557                                         p++;
 558                                         continue;
 559                                 }
 560
 561                                 /* first char */
 562                                 trim = false;
 563
 564                                 if (*p == '\"') {
 565                                         in_quote = true;
 566                                         p++;
 567                                         continue;
 568                                 }
 569                         }
 570
 571                         switch (*p) {
 572
 573                         /* TODO: support ber encoded values
 574                         case '#':
 575                         */
 576
 577                         case ',':
 578                                 if (escape) {
 579                                         *d++ = *p++;
 580                                         l++;
 581                                         escape = false;
 582                                         continue;
 583                                 }
 584                                 /* ok found value terminator */
 585
 586                                 if ( t ) {
 587                                         /* trim back */
 588                                         d -= (p - t);
 589                                         l -= (p - t);
 590                                 }
 591
 592                                 in_attr = true;
 593                                 in_value = false;
 594                                 trim = true;
 595
 596                                 p++;
 597                                 *d++ = '\0';
 598                                 dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
 599                                 dn->components[dn->comp_num].value.length = l;
 600                                 if ( ! dn->components[dn->comp_num].value.data) {
 601                                         /* ouch ! */
 602                                         goto failed;
 603                                 }
 604
 605                                 dt = d;
 606
 607                                 dn->comp_num++;
 608                                 if (dn->comp_num > 2) {
 609                                         dn->components = talloc_realloc(dn,
 610                                                                         dn->components,
 611                                                                         struct ldb_dn_component,
 612                                                                         dn->comp_num + 1);
 613                                         if ( ! dn->components) {
 614                                                 /* ouch ! */
 615                                                 goto failed;
 616                                         }
 617                                         /* make sure all components are zeroed, other functions depend on this */
 618                                         memset(&dn->components[dn->comp_num], '\0', sizeof(struct ldb_dn_component));
 619                                 }
 620
 621                                 continue;
 622
 623                         case '+':
 624                         case '=':
 625                                 /* to main compatibility with earlier
 626                                 versions of ldb indexing, we have to
 627                                 accept the base64 encoded binary index
 628                                 values, which contain a '+' or '='
 629                                 which should normally be escaped */
 630                                 if (is_index) {
 631                                         if ( t ) t = NULL;
 632                                         *d++ = *p++;
 633                                         l++;
 634                                         break;
 635                                 }
 636                                 /* fall through */
 637                         case '\"':
 638                         case '<':
 639                         case '>':
 640                         case ';':
 641                                 /* a string with not escaped specials is invalid (tested) */
 642                                 if ( ! escape) {
 643                                         ldb_dn_mark_invalid(dn);
 644                                         goto failed;
 645                                 }
 646                                 escape = false;
 647
 648                                 *d++ = *p++;
 649                                 l++;
 650
 651                                 if ( t ) t = NULL;
 652                                 break;
 653
 654                         case '\\':
 655                                 if ( ! escape) {
 656                                         escape = true;
 657                                         p++;
 658                                         continue;
 659                                 }
 660                                 escape = false;
 661
 662                                 *d++ = *p++;
 663                                 l++;
 664
 665                                 if ( t ) t = NULL;
 666                                 break;
 667
 668                         default:
 669                                 if (escape) {
 670                                         if (isxdigit(p[0]) && isxdigit(p[1])) {
 671                                                 if (sscanf(p, "%02x", &x) != 1) {
 672                                                         /* invalid escaping sequence */
 673                                                         ldb_dn_mark_invalid(dn);
 674                                                         goto failed;
 675                                                 }
 676                                                 p += 2;
 677                                                 *d++ = (unsigned char)x;
 678                                         } else {
 679                                                 *d++ = *p++;
 680                                         }
 681
 682                                         escape = false;
 683                                         l++;
 684                                         if ( t ) t = NULL;
 685                                         break;
 686                                 }
 687
 688                                 if (*p == ' ') {
 689                                         if ( ! t) t = p;
 690                                 } else {
 691                                         if ( t ) t = NULL;
 692                                 }
 693
 694                                 *d++ = *p++;
 695                                 l++;
 696
 697                                 break;
 698                         }
 699
 700                 }
 701         }
 702
 703         if (in_attr || in_quote) {
 704                 /* invalid dn */
 705                 ldb_dn_mark_invalid(dn);
 706                 goto failed;
 707         }
 708
 709         /* save last element */
 710         if ( t ) {
 711                 /* trim back */
 712                 d -= (p - t);
 713                 l -= (p - t);
 714         }
 715
 716         *d++ = '\0';
 717         dn->components[dn->comp_num].value.length = l;
 718         dn->components[dn->comp_num].value.data =
 719                                 (uint8_t *)talloc_strdup(dn->components, dt);
 720         if ( ! dn->components[dn->comp_num].value.data) {
 721                 /* ouch */
 722                 goto failed;
 723         }
 724
 725         dn->comp_num++;
 726
 727         talloc_free(data);
 728         return true;
 729
 730 failed:
 731         dn->comp_num = 0;
 732         talloc_free(dn->components);
 733         return false;
 734 }
 735
 736 bool ldb_dn_validate(struct ldb_dn *dn)
 737 {
 738         return ldb_dn_explode(dn);
 739 }
 740
 741 const char *ldb_dn_get_linearized(struct ldb_dn *dn)
 742 {
 743         int i, len;
 744         char *d, *n;
 745
 746         if ( ! dn || ( dn->invalid)) return NULL;
 747
 748         if (dn->linearized) return dn->linearized;
 749
 750         if ( ! dn->components) {
 751                 ldb_dn_mark_invalid(dn);
 752                 return NULL;
 753         }
 754
 755         if (dn->comp_num == 0) {
 756                 dn->linearized = talloc_strdup(dn, "");
 757                 if ( ! dn->linearized) return NULL;
 758                 return dn->linearized;
 759         }
 760
 761         /* calculate maximum possible length of DN */
 762         for (len = 0, i = 0; i < dn->comp_num; i++) {
 763                 /* name len */
 764                 len += strlen(dn->components[i].name);
 765                 /* max escaped data len */
 766                 len += (dn->components[i].value.length * 3);
 767                 len += 2; /* '=' and ',' */
 768         }
 769         dn->linearized = talloc_array(dn, char, len);
 770         if ( ! dn->linearized) return NULL;
 771
 772         d = dn->linearized;
 773
 774         for (i = 0; i < dn->comp_num; i++) {
 775
 776                 /* copy the name */
 777                 n = dn->components[i].name;
 778                 while (*n) *d++ = *n++;
 779
 780                 *d++ = '=';
 781
 782                 /* and the value */
 783                 d += ldb_dn_escape_internal( d,
 784                                 (char *)dn->components[i].value.data,
 785                                 dn->components[i].value.length);
 786                 *d++ = ',';
 787         }
 788
 789         *(--d) = '\0';
 790
 791         /* don't waste more memory than necessary */
 792         dn->linearized = talloc_realloc(dn, dn->linearized,
 793                                         char, (d - dn->linearized + 1));
 794
 795         return dn->linearized;
 796 }
 797
 798 static int ldb_dn_extended_component_compare(const void *p1, const void *p2)
 799 {
 800         const struct ldb_dn_ext_component *ec1 = (const struct ldb_dn_ext_component *)p1;
 801         const struct ldb_dn_ext_component *ec2 = (const struct ldb_dn_ext_component *)p2;
 802         return strcmp(ec1->name, ec2->name);
 803 }
 804
 805 char *ldb_dn_get_extended_linearized(void *mem_ctx, struct ldb_dn *dn, int mode)
 806 {
 807         const char *linearized = ldb_dn_get_linearized(dn);
 808         char *p = NULL;
 809         int i;
 810
 811         if (!linearized) {
 812                 return NULL;
 813         }
 814
 815         if (!ldb_dn_has_extended(dn)) {
 816                 return talloc_strdup(mem_ctx, linearized);
 817         }
 818
 819         if (!ldb_dn_validate(dn)) {
 820                 return NULL;
 821         }
 822
 823         /* sort the extended components by name. The idea is to make
 824          * the resulting DNs consistent, plus to ensure that we put
 825          * 'DELETED' first, so it can be very quickly recognised
 826          */
 827         TYPESAFE_QSORT(dn->ext_components, dn->ext_comp_num,
 828                        ldb_dn_extended_component_compare);
 829
 830         for (i = 0; i < dn->ext_comp_num; i++) {
 831                 const struct ldb_dn_extended_syntax *ext_syntax;
 832                 const char *name = dn->ext_components[i].name;
 833                 struct ldb_val ec_val = dn->ext_components[i].value;
 834                 struct ldb_val val;
 835                 int ret;
 836
 837                 ext_syntax = ldb_dn_extended_syntax_by_name(dn->ldb, name);
 838                 if (!ext_syntax) {
 839                         return NULL;
 840                 }
 841
 842                 if (mode == 1) {
 843                         ret = ext_syntax->write_clear_fn(dn->ldb, mem_ctx,
 844                                                         &ec_val, &val);
 845                 } else if (mode == 0) {
 846                         ret = ext_syntax->write_hex_fn(dn->ldb, mem_ctx,
 847                                                         &ec_val, &val);
 848                 } else {
 849                         ret = -1;
 850                 }
 851
 852                 if (ret != LDB_SUCCESS) {
 853                         return NULL;
 854                 }
 855
 856                 if (i == 0) {
 857                         p = talloc_asprintf(mem_ctx, "<%s=%s>",
 858                                             name, val.data);
 859                 } else {
 860                         p = talloc_asprintf_append_buffer(p, ";<%s=%s>",
 861                                                           name, val.data);
 862                 }
 863
 864                 talloc_free(val.data);
 865
 866                 if (!p) {
 867                         return NULL;
 868                 }
 869         }
 870
 871         if (dn->ext_comp_num && *linearized) {
 872                 p = talloc_asprintf_append_buffer(p, ";%s", linearized);
 873         }
 874
 875         if (!p) {
 876                 return NULL;
 877         }
 878
 879         return p;
 880 }
 881
 882 /*
 883   filter out all but an acceptable list of extended DN components
 884  */
 885 void ldb_dn_extended_filter(struct ldb_dn *dn, const char * const *accept)
 886 {
 887         int i;
 888         for (i=0; i<dn->ext_comp_num; i++) {
 889                 if (!ldb_attr_in_list(accept, dn->ext_components[i].name)) {
 890                         memmove(&dn->ext_components[i],
 891                                 &dn->ext_components[i+1],
 892                                 (dn->ext_comp_num-(i+1))*sizeof(dn->ext_components[0]));
 893                         dn->ext_comp_num--;
 894                         i--;
 895                 }
 896         }
 897         LDB_FREE(dn->ext_linearized);
 898 }
 899
 900
 901 char *ldb_dn_alloc_linearized(void *mem_ctx, struct ldb_dn *dn)
 902 {
 903         return talloc_strdup(mem_ctx, ldb_dn_get_linearized(dn));
 904 }
 905
 906 /*
 907   casefold a dn. We need to casefold the attribute names, and canonicalize
 908   attribute values of case insensitive attributes.
 909 */
 910
 911 static bool ldb_dn_casefold_internal(struct ldb_dn *dn)
 912 {
 913         int i, ret;
 914
 915         if ( ! dn || dn->invalid) return false;
 916
 917         if (dn->valid_case) return true;
 918
 919         if (( ! dn->components) && ( ! ldb_dn_explode(dn))) {
 920                 return false;
 921         }
 922
 923         for (i = 0; i < dn->comp_num; i++) {
 924                 const struct ldb_schema_attribute *a;
 925
 926                 dn->components[i].cf_name =
 927                         ldb_attr_casefold(dn->components,
 928                                           dn->components[i].name);
 929                 if (!dn->components[i].cf_name) {
 930                         goto failed;
 931                 }
 932
 933                 a = ldb_schema_attribute_by_name(dn->ldb,
 934                                                  dn->components[i].cf_name);
 935
 936                 ret = a->syntax->canonicalise_fn(dn->ldb, dn->components,
 937                                                  &(dn->components[i].value),
 938                                                  &(dn->components[i].cf_value));
 939                 if (ret != 0) {
 940                         goto failed;
 941                 }
 942         }
 943
 944         dn->valid_case = true;
 945
 946         return true;
 947
 948 failed:
 949         for (i = 0; i < dn->comp_num; i++) {
 950                 LDB_FREE(dn->components[i].cf_name);
 951                 LDB_FREE(dn->components[i].cf_value.data);
 952         }
 953         return false;
 954 }
 955
 956 const char *ldb_dn_get_casefold(struct ldb_dn *dn)
 957 {
 958         int i, len;
 959         char *d, *n;
 960
 961         if (dn->casefold) return dn->casefold;
 962
 963         if (dn->special) {
 964                 dn->casefold = talloc_strdup(dn, dn->linearized);
 965                 if (!dn->casefold) return NULL;
 966                 dn->valid_case = true;
 967                 return dn->casefold;
 968         }
 969
 970         if ( ! ldb_dn_casefold_internal(dn)) {
 971                 return NULL;
 972         }
 973
 974         if (dn->comp_num == 0) {
 975                 dn->casefold = talloc_strdup(dn, "");
 976                 return dn->casefold;
 977         }
 978
 979         /* calculate maximum possible length of DN */
 980         for (len = 0, i = 0; i < dn->comp_num; i++) {
 981                 /* name len */
 982                 len += strlen(dn->components[i].cf_name);
 983                 /* max escaped data len */
 984                 len += (dn->components[i].cf_value.length * 3);
 985                 len += 2; /* '=' and ',' */
 986         }
 987         dn->casefold = talloc_array(dn, char, len);
 988         if ( ! dn->casefold) return NULL;
 989
 990         d = dn->casefold;
 991
 992         for (i = 0; i < dn->comp_num; i++) {
 993
 994                 /* copy the name */
 995                 n = dn->components[i].cf_name;
 996                 while (*n) *d++ = *n++;
 997
 998                 *d++ = '=';
 999
1000                 /* and the value */
1001                 d += ldb_dn_escape_internal( d,
1002                                 (char *)dn->components[i].cf_value.data,
1003                                 dn->components[i].cf_value.length);
1004                 *d++ = ',';
1005         }
1006         *(--d) = '\0';
1007
1008         /* don't waste more memory than necessary */
1009         dn->casefold = talloc_realloc(dn, dn->casefold,
1010                                       char, strlen(dn->casefold) + 1);
1011
1012         return dn->casefold;
1013 }
1014
1015 char *ldb_dn_alloc_casefold(void *mem_ctx, struct ldb_dn *dn)
1016 {
1017         return talloc_strdup(mem_ctx, ldb_dn_get_casefold(dn));
1018 }
1019
1020 /* Determine if dn is below base, in the ldap tree.  Used for
1021  * evaluating a subtree search.
1022  * 0 if they match, otherwise non-zero
1023  */
1024
1025 int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn)
1026 {
1027         int ret;
1028         int n_base, n_dn;
1029
1030         if ( ! base || base->invalid) return 1;
1031         if ( ! dn || dn->invalid) return -1;
1032
1033         if (( ! base->valid_case) || ( ! dn->valid_case)) {
1034                 if (base->linearized && dn->linearized) {
1035                         /* try with a normal compare first, if we are lucky
1036                          * we will avoid exploding and casfolding */
1037                         int dif;
1038                         dif = strlen(dn->linearized) - strlen(base->linearized);
1039                         if (dif < 0) {
1040                                 return dif;
1041                         }
1042                         if (strcmp(base->linearized,
1043                                    &dn->linearized[dif]) == 0) {
1044                                 return 0;
1045                         }
1046                 }
1047
1048                 if ( ! ldb_dn_casefold_internal(base)) {
1049                         return 1;
1050                 }
1051
1052                 if ( ! ldb_dn_casefold_internal(dn)) {
1053                         return -1;
1054                 }
1055
1056         }
1057
1058         /* if base has more components,
1059          * they don't have the same base */
1060         if (base->comp_num > dn->comp_num) {
1061                 return (dn->comp_num - base->comp_num);
1062         }
1063
1064         if (dn->comp_num == 0) {
1065                 if (dn->special && base->special) {
1066                         return strcmp(base->linearized, dn->linearized);
1067                 } else if (dn->special) {
1068                         return -1;
1069                 } else if (base->special) {
1070                         return 1;
1071                 } else {
1072                         return 0;
1073                 }
1074         }
1075
1076         n_base = base->comp_num - 1;
1077         n_dn = dn->comp_num - 1;
1078
1079         while (n_base >= 0) {
1080                 char *b_name = base->components[n_base].cf_name;
1081                 char *dn_name = dn->components[n_dn].cf_name;
1082
1083                 char *b_vdata = (char *)base->components[n_base].cf_value.data;
1084                 char *dn_vdata = (char *)dn->components[n_dn].cf_value.data;
1085
1086                 size_t b_vlen = base->components[n_base].cf_value.length;
1087                 size_t dn_vlen = dn->components[n_dn].cf_value.length;
1088
1089                 /* compare attr names */
1090                 ret = strcmp(b_name, dn_name);
1091                 if (ret != 0) return ret;
1092
1093                 /* compare attr.cf_value. */
1094                 if (b_vlen != dn_vlen) {
1095                         return b_vlen - dn_vlen;
1096                 }
1097                 ret = strcmp(b_vdata, dn_vdata);
1098                 if (ret != 0) return ret;
1099
1100                 n_base--;
1101                 n_dn--;
1102         }
1103
1104         return 0;
1105 }
1106
1107 /* compare DNs using casefolding compare functions.
1108
1109    If they match, then return 0
1110  */
1111
1112 int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
1113 {
1114         int i, ret;
1115
1116         if (( ! dn0) || dn0->invalid || ! dn1 || dn1->invalid) {
1117                 return -1;
1118         }
1119
1120         if (( ! dn0->valid_case) || ( ! dn1->valid_case)) {
1121                 if (dn0->linearized && dn1->linearized) {
1122                         /* try with a normal compare first, if we are lucky
1123                          * we will avoid exploding and casfolding */
1124                         if (strcmp(dn0->linearized, dn1->linearized) == 0) {
1125                                 return 0;
1126                         }
1127                 }
1128
1129                 if ( ! ldb_dn_casefold_internal(dn0)) {
1130                         return 1;
1131                 }
1132
1133                 if ( ! ldb_dn_casefold_internal(dn1)) {
1134                         return -1;
1135                 }
1136
1137         }
1138
1139         if (dn0->comp_num != dn1->comp_num) {
1140                 return (dn1->comp_num - dn0->comp_num);
1141         }
1142
1143         if (dn0->comp_num == 0) {
1144                 if (dn0->special && dn1->special) {
1145                         return strcmp(dn0->linearized, dn1->linearized);
1146                 } else if (dn0->special) {
1147                         return 1;
1148                 } else if (dn1->special) {
1149                         return -1;
1150                 } else {
1151                         return 0;
1152                 }
1153         }
1154
1155         for (i = 0; i < dn0->comp_num; i++) {
1156                 char *dn0_name = dn0->components[i].cf_name;
1157                 char *dn1_name = dn1->components[i].cf_name;
1158
1159                 char *dn0_vdata = (char *)dn0->components[i].cf_value.data;
1160                 char *dn1_vdata = (char *)dn1->components[i].cf_value.data;
1161
1162                 size_t dn0_vlen = dn0->components[i].cf_value.length;
1163                 size_t dn1_vlen = dn1->components[i].cf_value.length;
1164
1165                 /* compare attr names */
1166                 ret = strcmp(dn0_name, dn1_name);
1167                 if (ret != 0) {
1168                         return ret;
1169                 }
1170
1171                 /* compare attr.cf_value. */
1172                 if (dn0_vlen != dn1_vlen) {
1173                         return dn0_vlen - dn1_vlen;
1174                 }
1175                 ret = strcmp(dn0_vdata, dn1_vdata);
1176                 if (ret != 0) {
1177                         return ret;
1178                 }
1179         }
1180
1181         return 0;
1182 }
1183
1184 static struct ldb_dn_component ldb_dn_copy_component(
1185                                                 void *mem_ctx,
1186                                                 struct ldb_dn_component *src)
1187 {
1188         struct ldb_dn_component dst;
1189
1190         memset(&dst, 0, sizeof(dst));
1191
1192         if (src == NULL) {
1193                 return dst;
1194         }
1195
1196         dst.value = ldb_val_dup(mem_ctx, &(src->value));
1197         if (dst.value.data == NULL) {
1198                 return dst;
1199         }
1200
1201         dst.name = talloc_strdup(mem_ctx, src->name);
1202         if (dst.name == NULL) {
1203                 LDB_FREE(dst.value.data);
1204                 return dst;
1205         }
1206
1207         if (src->cf_value.data) {
1208                 dst.cf_value = ldb_val_dup(mem_ctx, &(src->cf_value));
1209                 if (dst.cf_value.data == NULL) {
1210                         LDB_FREE(dst.value.data);
1211                         LDB_FREE(dst.name);
1212                         return dst;
1213                 }
1214
1215                 dst.cf_name = talloc_strdup(mem_ctx, src->cf_name);
1216                 if (dst.cf_name == NULL) {
1217                         LDB_FREE(dst.cf_name);
1218                         LDB_FREE(dst.value.data);
1219                         LDB_FREE(dst.name);
1220                         return dst;
1221                 }
1222         } else {
1223                 dst.cf_value.data = NULL;
1224                 dst.cf_name = NULL;
1225         }
1226
1227         return dst;
1228 }
1229
1230 static struct ldb_dn_ext_component ldb_dn_ext_copy_component(
1231                                                 void *mem_ctx,
1232                                                 struct ldb_dn_ext_component *src)
1233 {
1234         struct ldb_dn_ext_component dst;
1235
1236         memset(&dst, 0, sizeof(dst));
1237
1238         if (src == NULL) {
1239                 return dst;
1240         }
1241
1242         dst.value = ldb_val_dup(mem_ctx, &(src->value));
1243         if (dst.value.data == NULL) {
1244                 return dst;
1245         }
1246
1247         dst.name = talloc_strdup(mem_ctx, src->name);
1248         if (dst.name == NULL) {
1249                 LDB_FREE(dst.value.data);
1250                 return dst;
1251         }
1252
1253         return dst;
1254 }
1255
1256 struct ldb_dn *ldb_dn_copy(void *mem_ctx, struct ldb_dn *dn)
1257 {
1258         struct ldb_dn *new_dn;
1259
1260         if (!dn || dn->invalid) {
1261                 return NULL;
1262         }
1263
1264         new_dn = talloc_zero(mem_ctx, struct ldb_dn);
1265         if ( !new_dn) {
1266                 return NULL;
1267         }
1268
1269         *new_dn = *dn;
1270
1271         if (dn->components) {
1272                 int i;
1273
1274                 new_dn->components =
1275                         talloc_zero_array(new_dn,
1276                                           struct ldb_dn_component,
1277                                           dn->comp_num);
1278                 if ( ! new_dn->components) {
1279                         talloc_free(new_dn);
1280                         return NULL;
1281                 }
1282
1283                 for (i = 0; i < dn->comp_num; i++) {
1284                         new_dn->components[i] =
1285                                 ldb_dn_copy_component(new_dn->components,
1286                                                       &dn->components[i]);
1287                         if ( ! new_dn->components[i].value.data) {
1288                                 talloc_free(new_dn);
1289                                 return NULL;
1290                         }
1291                 }
1292         }
1293
1294         if (dn->ext_components) {
1295                 int i;
1296
1297                 new_dn->ext_components =
1298                         talloc_zero_array(new_dn,
1299                                           struct ldb_dn_ext_component,
1300                                           dn->ext_comp_num);
1301                 if ( ! new_dn->ext_components) {
1302                         talloc_free(new_dn);
1303                         return NULL;
1304                 }
1305
1306                 for (i = 0; i < dn->ext_comp_num; i++) {
1307                         new_dn->ext_components[i] =
1308                                  ldb_dn_ext_copy_component(
1309                                                 new_dn->ext_components,
1310                                                 &dn->ext_components[i]);
1311                         if ( ! new_dn->ext_components[i].value.data) {
1312                                 talloc_free(new_dn);
1313                                 return NULL;
1314                         }
1315                 }
1316         }
1317
1318         if (dn->casefold) {
1319                 new_dn->casefold = talloc_strdup(new_dn, dn->casefold);
1320                 if ( ! new_dn->casefold) {
1321                         talloc_free(new_dn);
1322                         return NULL;
1323                 }
1324         }
1325
1326         if (dn->linearized) {
1327                 new_dn->linearized = talloc_strdup(new_dn, dn->linearized);
1328                 if ( ! new_dn->linearized) {
1329                         talloc_free(new_dn);
1330                         return NULL;
1331                 }
1332         }
1333
1334         if (dn->ext_linearized) {
1335                 new_dn->ext_linearized = talloc_strdup(new_dn,
1336                                                         dn->ext_linearized);
1337                 if ( ! new_dn->ext_linearized) {
1338                         talloc_free(new_dn);
1339                         return NULL;
1340                 }
1341         }
1342
1343         return new_dn;
1344 }
1345
1346 /* modify the given dn by adding a base.
1347  *
1348  * return true if successful and false if not
1349  * if false is returned the dn may be marked invalid
1350  */
1351 bool ldb_dn_add_base(struct ldb_dn *dn, struct ldb_dn *base)
1352 {
1353         const char *s;
1354         char *t;
1355
1356         if ( !base || base->invalid || !dn || dn->invalid) {
1357                 return false;
1358         }
1359
1360         if (dn->components) {
1361                 int i;
1362
1363                 if ( ! ldb_dn_validate(base)) {
1364                         return false;
1365                 }
1366
1367                 s = NULL;
1368                 if (dn->valid_case) {
1369                         if ( ! (s = ldb_dn_get_casefold(base))) {
1370                                 return false;
1371                         }
1372                 }
1373
1374                 dn->components = talloc_realloc(dn,
1375                                                 dn->components,
1376                                                 struct ldb_dn_component,
1377                                                 dn->comp_num + base->comp_num);
1378                 if ( ! dn->components) {
1379                         ldb_dn_mark_invalid(dn);
1380                         return false;
1381                 }
1382
1383                 for (i = 0; i < base->comp_num; dn->comp_num++, i++) {
1384                         dn->components[dn->comp_num] =
1385                                 ldb_dn_copy_component(dn->components,
1386                                                         &base->components[i]);
1387                         if (dn->components[dn->comp_num].value.data == NULL) {
1388                                 ldb_dn_mark_invalid(dn);
1389                                 return false;
1390                         }
1391                 }
1392
1393                 if (dn->casefold && s) {
1394                         if (*dn->casefold) {
1395                                 t = talloc_asprintf(dn, "%s,%s",
1396                                                     dn->casefold, s);
1397                         } else {
1398                                 t = talloc_strdup(dn, s);
1399                         }
1400                         LDB_FREE(dn->casefold);
1401                         dn->casefold = t;
1402                 }
1403         }
1404
1405         if (dn->linearized) {
1406
1407                 s = ldb_dn_get_linearized(base);
1408                 if ( ! s) {
1409                         return false;
1410                 }
1411
1412                 if (*dn->linearized) {
1413                         t = talloc_asprintf(dn, "%s,%s",
1414                                             dn->linearized, s);
1415                 } else {
1416                         t = talloc_strdup(dn, s);
1417                 }
1418                 if ( ! t) {
1419                         ldb_dn_mark_invalid(dn);
1420                         return false;
1421                 }
1422                 LDB_FREE(dn->linearized);
1423                 dn->linearized = t;
1424         }
1425
1426         /* Wipe the ext_linearized DN,
1427          * the GUID and SID are almost certainly no longer valid */
1428         LDB_FREE(dn->ext_linearized);
1429
1430         LDB_FREE(dn->ext_components);
1431         dn->ext_comp_num = 0;
1432         return true;
1433 }
1434
1435 /* modify the given dn by adding a base.
1436  *
1437  * return true if successful and false if not
1438  * if false is returned the dn may be marked invalid
1439  */
1440 bool ldb_dn_add_base_fmt(struct ldb_dn *dn, const char *base_fmt, ...)
1441 {
1442         struct ldb_dn *base;
1443         char *base_str;
1444         va_list ap;
1445         bool ret;
1446
1447         if ( !dn || dn->invalid) {
1448                 return false;
1449         }
1450
1451         va_start(ap, base_fmt);
1452         base_str = talloc_vasprintf(dn, base_fmt, ap);
1453         va_end(ap);
1454
1455         if (base_str == NULL) {
1456                 return false;
1457         }
1458
1459         base = ldb_dn_new(base_str, dn->ldb, base_str);
1460
1461         ret = ldb_dn_add_base(dn, base);
1462
1463         talloc_free(base_str);
1464
1465         return ret;
1466 }
1467
1468 /* modify the given dn by adding children elements.
1469  *
1470  * return true if successful and false if not
1471  * if false is returned the dn may be marked invalid
1472  */
1473 bool ldb_dn_add_child(struct ldb_dn *dn, struct ldb_dn *child)
1474 {
1475         const char *s;
1476         char *t;
1477
1478         if ( !child || child->invalid || !dn || dn->invalid) {
1479                 return false;
1480         }
1481
1482         if (dn->components) {
1483                 int n, i, j;
1484
1485                 if ( ! ldb_dn_validate(child)) {
1486                         return false;
1487                 }
1488
1489                 s = NULL;
1490                 if (dn->valid_case) {
1491                         if ( ! (s = ldb_dn_get_casefold(child))) {
1492                                 return false;
1493                         }
1494                 }
1495
1496                 n = dn->comp_num + child->comp_num;
1497
1498                 dn->components = talloc_realloc(dn,
1499                                                 dn->components,
1500                                                 struct ldb_dn_component,
1501                                                 n);
1502                 if ( ! dn->components) {
1503                         ldb_dn_mark_invalid(dn);
1504                         return false;
1505                 }
1506
1507                 for (i = dn->comp_num - 1, j = n - 1; i >= 0; i--, j--) {
1508                         dn->components[j] = dn->components[i];
1509                 }
1510
1511                 for (i = 0; i < child->comp_num; i++) {
1512                         dn->components[i] =
1513                                 ldb_dn_copy_component(dn->components,
1514                                                         &child->components[i]);
1515                         if (dn->components[i].value.data == NULL) {
1516                                 ldb_dn_mark_invalid(dn);
1517                                 return false;
1518                         }
1519                 }
1520
1521                 dn->comp_num = n;
1522
1523                 if (dn->casefold && s) {
1524                         t = talloc_asprintf(dn, "%s,%s", s, dn->casefold);
1525                         LDB_FREE(dn->casefold);
1526                         dn->casefold = t;
1527                 }
1528         }
1529
1530         if (dn->linearized) {
1531
1532                 s = ldb_dn_get_linearized(child);
1533                 if ( ! s) {
1534                         return false;
1535                 }
1536
1537                 t = talloc_asprintf(dn, "%s,%s", s, dn->linearized);
1538                 if ( ! t) {
1539                         ldb_dn_mark_invalid(dn);
1540                         return false;
1541                 }
1542                 LDB_FREE(dn->linearized);
1543                 dn->linearized = t;
1544         }
1545
1546         /* Wipe the ext_linearized DN,
1547          * the GUID and SID are almost certainly no longer valid */
1548         LDB_FREE(dn->ext_linearized);
1549
1550         LDB_FREE(dn->ext_components);
1551         dn->ext_comp_num = 0;
1552
1553         return true;
1554 }
1555
1556 /* modify the given dn by adding children elements.
1557  *
1558  * return true if successful and false if not
1559  * if false is returned the dn may be marked invalid
1560  */
1561 bool ldb_dn_add_child_fmt(struct ldb_dn *dn, const char *child_fmt, ...)
1562 {
1563         struct ldb_dn *child;
1564         char *child_str;
1565         va_list ap;
1566         bool ret;
1567
1568         if ( !dn || dn->invalid) {
1569                 return false;
1570         }
1571
1572         va_start(ap, child_fmt);
1573         child_str = talloc_vasprintf(dn, child_fmt, ap);
1574         va_end(ap);
1575
1576         if (child_str == NULL) {
1577                 return false;
1578         }
1579
1580         child = ldb_dn_new(child_str, dn->ldb, child_str);
1581
1582         ret = ldb_dn_add_child(dn, child);
1583
1584         talloc_free(child_str);
1585
1586         return ret;
1587 }
1588
1589 bool ldb_dn_remove_base_components(struct ldb_dn *dn, unsigned int num)
1590 {
1591         int i;
1592
1593         if ( ! ldb_dn_validate(dn)) {
1594                 return false;
1595         }
1596
1597         if (dn->comp_num < num) {
1598                 return false;
1599         }
1600
1601         /* free components */
1602         for (i = num; i > 0; i--) {
1603                 LDB_FREE(dn->components[dn->comp_num - i].name);
1604                 LDB_FREE(dn->components[dn->comp_num - i].value.data);
1605                 LDB_FREE(dn->components[dn->comp_num - i].cf_name);
1606                 LDB_FREE(dn->components[dn->comp_num - i].cf_value.data);
1607         }
1608
1609         dn->comp_num -= num;
1610
1611         if (dn->valid_case) {
1612                 for (i = 0; i < dn->comp_num; i++) {
1613                         LDB_FREE(dn->components[i].cf_name);
1614                         LDB_FREE(dn->components[i].cf_value.data);
1615                 }
1616                 dn->valid_case = false;
1617         }
1618
1619         LDB_FREE(dn->casefold);
1620         LDB_FREE(dn->linearized);
1621
1622         /* Wipe the ext_linearized DN,
1623          * the GUID and SID are almost certainly no longer valid */
1624         LDB_FREE(dn->ext_linearized);
1625
1626         LDB_FREE(dn->ext_components);
1627         dn->ext_comp_num = 0;
1628
1629         return true;
1630 }
1631
1632 bool ldb_dn_remove_child_components(struct ldb_dn *dn, unsigned int num)
1633 {
1634         int i, j;
1635
1636         if ( ! ldb_dn_validate(dn)) {
1637                 return false;
1638         }
1639
1640         if (dn->comp_num < num) {
1641                 return false;
1642         }
1643
1644         for (i = 0, j = num; j < dn->comp_num; i++, j++) {
1645                 if (i < num) {
1646                         LDB_FREE(dn->components[i].name);
1647                         LDB_FREE(dn->components[i].value.data);
1648                         LDB_FREE(dn->components[i].cf_name);
1649                         LDB_FREE(dn->components[i].cf_value.data);
1650                 }
1651                 dn->components[i] = dn->components[j];
1652         }
1653
1654         dn->comp_num -= num;
1655
1656         if (dn->valid_case) {
1657                 for (i = 0; i < dn->comp_num; i++) {
1658                         LDB_FREE(dn->components[i].cf_name);
1659                         LDB_FREE(dn->components[i].cf_value.data);
1660                 }
1661                 dn->valid_case = false;
1662         }
1663
1664         LDB_FREE(dn->casefold);
1665         LDB_FREE(dn->linearized);
1666
1667         /* Wipe the ext_linearized DN,
1668          * the GUID and SID are almost certainly no longer valid */
1669         LDB_FREE(dn->ext_linearized);
1670
1671         LDB_FREE(dn->ext_components);
1672         dn->ext_comp_num = 0;
1673         return true;
1674 }
1675
1676 struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, struct ldb_dn *dn)
1677 {
1678         struct ldb_dn *new_dn;
1679
1680         new_dn = ldb_dn_copy(mem_ctx, dn);
1681         if ( !new_dn ) {
1682                 return NULL;
1683         }
1684
1685         if ( ! ldb_dn_remove_child_components(new_dn, 1)) {
1686                 talloc_free(new_dn);
1687                 return NULL;
1688         }
1689
1690         /* Wipe the ext_linearized DN,
1691          * the GUID and SID are almost certainly no longer valid */
1692         LDB_FREE(dn->ext_linearized);
1693
1694         LDB_FREE(dn->ext_components);
1695         dn->ext_comp_num = 0;
1696         return new_dn;
1697 }
1698
1699 /* Create a 'canonical name' string from a DN:
1700
1701    ie dc=samba,dc=org -> samba.org/
1702       uid=administrator,ou=users,dc=samba,dc=org = samba.org/users/administrator
1703
1704    There are two formats,
1705    the EX format has the last '/' replaced with a newline (\n).
1706
1707 */
1708 static char *ldb_dn_canonical(void *mem_ctx, struct ldb_dn *dn, int ex_format) {
1709         int i;
1710         TALLOC_CTX *tmpctx;
1711         char *cracked = NULL;
1712         const char *format = (ex_format ? "\n" : "/" );
1713
1714         if ( ! ldb_dn_validate(dn)) {
1715                 return NULL;
1716         }
1717
1718         tmpctx = talloc_new(mem_ctx);
1719
1720         /* Walk backwards down the DN, grabbing 'dc' components at first */
1721         for (i = dn->comp_num - 1; i >= 0; i--) {
1722                 if (ldb_attr_cmp(dn->components[i].name, "dc") != 0) {
1723                         break;
1724                 }
1725                 if (cracked) {
1726                         cracked = talloc_asprintf(tmpctx, "%s.%s",
1727                                                   ldb_dn_escape_value(tmpctx,
1728                                                         dn->components[i].value),
1729                                                   cracked);
1730                 } else {
1731                         cracked = ldb_dn_escape_value(tmpctx,
1732                                                         dn->components[i].value);
1733                 }
1734                 if (!cracked) {
1735                         goto done;
1736                 }
1737         }
1738
1739         /* Only domain components?  Finish here */
1740         if (i < 0) {
1741                 cracked = talloc_strdup_append_buffer(cracked, format);
1742                 talloc_steal(mem_ctx, cracked);
1743                 goto done;
1744         }
1745
1746         /* Now walk backwards appending remaining components */
1747         for (; i > 0; i--) {
1748                 cracked = talloc_asprintf_append_buffer(cracked, "/%s",
1749                                                         ldb_dn_escape_value(tmpctx,
1750                                                         dn->components[i].value));
1751                 if (!cracked) {
1752                         goto done;
1753                 }
1754         }
1755
1756         /* Last one, possibly a newline for the 'ex' format */
1757         cracked = talloc_asprintf_append_buffer(cracked, "%s%s", format,
1758                                                 ldb_dn_escape_value(tmpctx,
1759                                                         dn->components[i].value));
1760
1761         talloc_steal(mem_ctx, cracked);
1762 done:
1763         talloc_free(tmpctx);
1764         return cracked;
1765 }
1766
1767 /* Wrapper functions for the above, for the two different string formats */
1768 char *ldb_dn_canonical_string(void *mem_ctx, struct ldb_dn *dn) {
1769         return ldb_dn_canonical(mem_ctx, dn, 0);
1770
1771 }
1772
1773 char *ldb_dn_canonical_ex_string(void *mem_ctx, struct ldb_dn *dn) {
1774         return ldb_dn_canonical(mem_ctx, dn, 1);
1775 }
1776
1777 int ldb_dn_get_comp_num(struct ldb_dn *dn)
1778 {
1779         if ( ! ldb_dn_validate(dn)) {
1780                 return -1;
1781         }
1782         return dn->comp_num;
1783 }
1784
1785 const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num)
1786 {
1787         if ( ! ldb_dn_validate(dn)) {
1788                 return NULL;
1789         }
1790         if (num >= dn->comp_num) return NULL;
1791         return dn->components[num].name;
1792 }
1793
1794 const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn,
1795                                                 unsigned int num)
1796 {
1797         if ( ! ldb_dn_validate(dn)) {
1798                 return NULL;
1799         }
1800         if (num >= dn->comp_num) return NULL;
1801         return &dn->components[num].value;
1802 }
1803
1804 const char *ldb_dn_get_rdn_name(struct ldb_dn *dn)
1805 {
1806         if ( ! ldb_dn_validate(dn)) {
1807                 return NULL;
1808         }
1809         if (dn->comp_num == 0) return NULL;
1810         return dn->components[0].name;
1811 }
1812
1813 const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn)
1814 {
1815         if ( ! ldb_dn_validate(dn)) {
1816                 return NULL;
1817         }
1818         if (dn->comp_num == 0) return NULL;
1819         return &dn->components[0].value;
1820 }
1821
1822 int ldb_dn_set_component(struct ldb_dn *dn, int num,
1823                          const char *name, const struct ldb_val val)
1824 {
1825         char *n;
1826         struct ldb_val v;
1827
1828         if ( ! ldb_dn_validate(dn)) {
1829                 return LDB_ERR_OTHER;
1830         }
1831
1832         if (num >= dn->comp_num) {
1833                 return LDB_ERR_OTHER;
1834         }
1835
1836         n = talloc_strdup(dn, name);
1837         if ( ! n) {
1838                 return LDB_ERR_OTHER;
1839         }
1840
1841         v.length = val.length;
1842         v.data = (uint8_t *)talloc_memdup(dn, val.data, v.length+1);
1843         if ( ! v.data) {
1844                 talloc_free(n);
1845                 return LDB_ERR_OTHER;
1846         }
1847
1848         talloc_free(dn->components[num].name);
1849         talloc_free(dn->components[num].value.data);
1850         dn->components[num].name = n;
1851         dn->components[num].value = v;
1852
1853         if (dn->valid_case) {
1854                 int i;
1855                 for (i = 0; i < dn->comp_num; i++) {
1856                         LDB_FREE(dn->components[i].cf_name);
1857                         LDB_FREE(dn->components[i].cf_value.data);
1858                 }
1859                 dn->valid_case = false;
1860         }
1861         LDB_FREE(dn->casefold);
1862         LDB_FREE(dn->linearized);
1863
1864         /* Wipe the ext_linearized DN,
1865          * the GUID and SID are almost certainly no longer valid */
1866         LDB_FREE(dn->ext_linearized);
1867
1868         dn->ext_comp_num = 0;
1869         LDB_FREE(dn->ext_components);
1870         return LDB_SUCCESS;
1871 }
1872
1873 const struct ldb_val *ldb_dn_get_extended_component(struct ldb_dn *dn,
1874                                                     const char *name)
1875 {
1876         int i;
1877         if ( ! ldb_dn_validate(dn)) {
1878                 return NULL;
1879         }
1880         for (i=0; i < dn->ext_comp_num; i++) {
1881                 if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
1882                         return &dn->ext_components[i].value;
1883                 }
1884         }
1885         return NULL;
1886 }
1887
1888 int ldb_dn_set_extended_component(struct ldb_dn *dn,
1889                                   const char *name, const struct ldb_val *val)
1890 {
1891         struct ldb_dn_ext_component *p;
1892         int i;
1893         struct ldb_val v2;
1894
1895         if ( ! ldb_dn_validate(dn)) {
1896                 return LDB_ERR_OTHER;
1897         }
1898
1899         if (!ldb_dn_extended_syntax_by_name(dn->ldb, name)) {
1900                 /* We don't know how to handle this type of thing */
1901                 return LDB_ERR_INVALID_DN_SYNTAX;
1902         }
1903
1904         for (i=0; i < dn->ext_comp_num; i++) {
1905                 if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
1906                         if (val) {
1907                                 dn->ext_components[i].value =
1908                                         ldb_val_dup(dn->ext_components, val);
1909
1910                                 dn->ext_components[i].name =
1911                                         talloc_strdup(dn->ext_components, name);
1912                                 if (!dn->ext_components[i].name ||
1913                                     !dn->ext_components[i].value.data) {
1914                                         ldb_dn_mark_invalid(dn);
1915                                         return LDB_ERR_OPERATIONS_ERROR;
1916                                 }
1917                                 return LDB_SUCCESS;
1918                         } else {
1919                                 if (i != (dn->ext_comp_num - 1)) {
1920                                         memmove(&dn->ext_components[i],
1921                                                 &dn->ext_components[i+1],
1922                                                 ((dn->ext_comp_num-1) - i) *
1923                                                   sizeof(*dn->ext_components));
1924                                 }
1925                                 dn->ext_comp_num--;
1926
1927                                 dn->ext_components = talloc_realloc(dn,
1928                                                    dn->ext_components,
1929                                                    struct ldb_dn_ext_component,
1930                                                    dn->ext_comp_num);
1931                                 if (!dn->ext_components) {
1932                                         ldb_dn_mark_invalid(dn);
1933                                         return LDB_ERR_OPERATIONS_ERROR;
1934                                 }
1935                                 return LDB_SUCCESS;
1936                         }
1937                         LDB_FREE(dn->ext_linearized);
1938                 }
1939         }
1940
1941         if (val == NULL) {
1942                 /* removing a value that doesn't exist is not an error */
1943                 return LDB_SUCCESS;
1944         }
1945
1946         v2 = *val;
1947
1948         p = dn->ext_components
1949                 = talloc_realloc(dn,
1950                                  dn->ext_components,
1951                                  struct ldb_dn_ext_component,
1952                                  dn->ext_comp_num + 1);
1953         if (!dn->ext_components) {
1954                 ldb_dn_mark_invalid(dn);
1955                 return LDB_ERR_OPERATIONS_ERROR;
1956         }
1957
1958         p[dn->ext_comp_num].value = ldb_val_dup(dn->ext_components, &v2);
1959         p[dn->ext_comp_num].name = talloc_strdup(p, name);
1960
1961         if (!dn->ext_components[i].name || !dn->ext_components[i].value.data) {
1962                 ldb_dn_mark_invalid(dn);
1963                 return LDB_ERR_OPERATIONS_ERROR;
1964         }
1965         dn->ext_components = p;
1966         dn->ext_comp_num++;
1967
1968         return LDB_SUCCESS;
1969 }
1970
1971 void ldb_dn_remove_extended_components(struct ldb_dn *dn)
1972 {
1973         dn->ext_comp_num = 0;
1974         LDB_FREE(dn->ext_components);
1975         LDB_FREE(dn->ext_linearized);
1976 }
1977
1978 bool ldb_dn_is_valid(struct ldb_dn *dn)
1979 {
1980         if ( ! dn) return false;
1981         return ! dn->invalid;
1982 }
1983
1984 bool ldb_dn_is_special(struct ldb_dn *dn)
1985 {
1986         if ( ! dn || dn->invalid) return false;
1987         return dn->special;
1988 }
1989
1990 bool ldb_dn_has_extended(struct ldb_dn *dn)
1991 {
1992         if ( ! dn || dn->invalid) return false;
1993         if (dn->ext_linearized && (dn->ext_linearized[0] == '<')) return true;
1994         return dn->ext_comp_num != 0;
1995 }
1996
1997 bool ldb_dn_check_special(struct ldb_dn *dn, const char *check)
1998 {
1999         if ( ! dn || dn->invalid) return false;
2000         return ! strcmp(dn->linearized, check);
2001 }
2002
2003 bool ldb_dn_is_null(struct ldb_dn *dn)
2004 {
2005         if ( ! dn || dn->invalid) return false;
2006         if (ldb_dn_has_extended(dn)) return false;
2007         if (dn->linearized && (dn->linearized[0] == '\0')) return true;
2008         return false;
2009 }
2010
2011 /*
2012   this updates dn->components, taking the components from ref_dn.
2013   This is used by code that wants to update the DN path of a DN
2014   while not impacting on the extended DN components
2015  */
2016 int ldb_dn_update_components(struct ldb_dn *dn, const struct ldb_dn *ref_dn)
2017 {
2018         dn->components = talloc_realloc(dn, dn->components,
2019                                         struct ldb_dn_component, ref_dn->comp_num);
2020         if (!dn->components) {
2021                 return LDB_ERR_OPERATIONS_ERROR;
2022         }
2023         memcpy(dn->components, ref_dn->components,
2024                sizeof(struct ldb_dn_component)*ref_dn->comp_num);
2025         dn->comp_num = ref_dn->comp_num;
2026
2027         talloc_free(dn->linearized);
2028         talloc_free(dn->ext_linearized);
2029         dn->ext_linearized = NULL;
2030         dn->linearized = NULL;
2031
2032         return LDB_SUCCESS;
2033 }