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