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