lib/ldb/common/ldb_dn.c

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