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