source4/lib/ldb/common/ldb_dn.c

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