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 2 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, write to the Free Software
  22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23 */
  24
  25 /*
  26  *  Name: ldb
  27  *
  28  *  Component: ldb dn creation and manipulation utility functions
  29  *
  30  *  Description: - explode a dn into it's own basic elements
  31  *                 and put them in a structure (only if necessary)
  32  *               - manipulate ldb_dn structures
  33  *
  34  *  Author: Simo Sorce
  35  */
  36
  37 #include "includes.h"
  38 #include <ctype.h>
  39 #include "ldb/include/includes.h"
  40
  41 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
  42
  43 #define LDB_FREE(x) do { talloc_free(x); x = NULL; } while(0)
  44
  45 /**
  46    internal ldb exploded dn structures
  47 */
  48 struct ldb_dn_component {
  49
  50         char *name;
  51         struct ldb_val value;
  52
  53         char *cf_name;
  54         struct ldb_val cf_value;
  55 };
  56
  57 struct ldb_dn {
  58
  59         struct ldb_context *ldb;
  60
  61         /* Special DNs are always linearized */
  62         bool special;
  63         bool invalid;
  64
  65         bool valid_case;
  66
  67         char *linearized;
  68         char *casefold;
  69
  70         unsigned int comp_num;
  71         struct ldb_dn_component *components;
  72
  73 };
  74
  75 /* strdn may be NULL */
  76 struct ldb_dn *ldb_dn_new(void *mem_ctx, struct ldb_context *ldb, const char *strdn)
  77 {
  78         struct ldb_dn *dn;
  79
  80         if ( (! mem_ctx) || (! ldb)) return NULL;
  81
  82         dn = talloc_zero(mem_ctx, struct ldb_dn);
  83         LDB_DN_NULL_FAILED(dn);
  84
  85         dn->ldb = ldb;
  86
  87         if (strdn) {
  88                 if (strdn[0] == '@') {
  89                         dn->special = true;
  90                 }
  91                 if (strncasecmp(strdn, "<GUID=", 6) == 0) {
  92                         /* this is special DN returned when the
  93                          * exploded_dn control is used */
  94                         dn->special = true;
  95                         /* FIXME: add a GUID string to ldb_dn structure */
  96                 }
  97                 dn->linearized = talloc_strdup(dn, strdn);
  98         } else {
  99                 dn->linearized = talloc_strdup(dn, "");
 100         }
 101         LDB_DN_NULL_FAILED(dn->linearized);
 102
 103         return dn;
 104
 105 failed:
 106         talloc_free(dn);
 107         return NULL;
 108 }
 109
 110 struct ldb_dn *ldb_dn_new_fmt(void *mem_ctx, struct ldb_context *ldb, const char *new_fmt, ...)
 111 {
 112         struct ldb_dn *dn;
 113         char *strdn;
 114         va_list ap;
 115
 116         if ( (! mem_ctx) || (! ldb)) return NULL;
 117
 118         dn = talloc_zero(mem_ctx, struct ldb_dn);
 119         LDB_DN_NULL_FAILED(dn);
 120
 121         dn->ldb = ldb;
 122
 123         va_start(ap, new_fmt);
 124         strdn = talloc_vasprintf(dn, new_fmt, ap);
 125         va_end(ap);
 126         LDB_DN_NULL_FAILED(strdn);
 127
 128         if (strdn[0] == '@') {
 129                 dn->special = true;
 130         }
 131         if (strncasecmp(strdn, "<GUID=", 6) == 0) {
 132                 /* this is special DN returned when the
 133                  * exploded_dn control is used */
 134                 dn->special = true;
 135                 /* FIXME: add a GUID string to ldb_dn structure */
 136         }
 137         dn->linearized = strdn;
 138
 139         return dn;
 140
 141 failed:
 142         talloc_free(dn);
 143         return NULL;
 144 }
 145
 146 static int ldb_dn_escape_internal(char *dst, const char *src, int len)
 147 {
 148         const char *p, *s;
 149         char *d;
 150         int l;
 151
 152         p = s = src;
 153         d = dst;
 154
 155         while (p - src < len) {
 156
 157                 p += strcspn(p, ",=\n+<>#;\\\"");
 158
 159                 if (p - src == len) /* found no escapable chars */
 160                         break;
 161
 162                 memcpy(d, s, p - s); /* copy the part of the string before the stop */
 163                 d += (p - s); /* move to current position */
 164
 165                 if (*p) { /* it is a normal escapable character */
 166                         *d++ = '\\';
 167                         *d++ = *p++;
 168                 } else { /* we have a zero byte in the string */
 169                         strncpy(d, "\00", 3); /* escape the zero */
 170                         d += 3;
 171                         p++; /* skip the zero */
 172                 }
 173                 s = p; /* move forward */
 174         }
 175
 176         /* copy the last part (with zero) and return */
 177         l = len - (s - src);
 178         memcpy(d, s, l + 1);
 179
 180         /* return the length of the resulting string */
 181         return (l + (d - dst));
 182 }
 183
 184 char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
 185 {
 186         char *dst;
 187
 188         if (!value.length)
 189                 return NULL;
 190
 191         /* allocate destination string, it will be at most 3 times the source */
 192         dst = talloc_array(mem_ctx, char, value.length * 3 + 1);
 193         if ( ! dst) {
 194                 talloc_free(dst);
 195                 return NULL;
 196         }
 197
 198         ldb_dn_escape_internal(dst, (const char *)value.data, value.length);
 199
 200         dst = talloc_realloc(mem_ctx, dst, char, strlen(dst) + 1);
 201
 202         return dst;
 203 }
 204
 205 /*
 206   explode a DN string into a ldb_dn structure
 207   based on RFC4514 except that we don't support multiple valued RDNs
 208 */
 209 static bool ldb_dn_explode(struct ldb_dn *dn)
 210 {
 211         char *p, *data, *d, *dt, *t;
 212         bool trim = false;
 213         bool in_attr = false;
 214         bool in_value = false;
 215         bool in_quote = false;
 216         bool is_oid = false;
 217         bool escape = false;
 218         unsigned x;
 219         int l;
 220
 221         if ( ! dn || dn->invalid) return false;
 222
 223         if (dn->components) {
 224                 return true;
 225         }
 226
 227         if ( ! dn->linearized) {
 228                 return false;
 229         }
 230
 231         /* Empty DNs */
 232         if (dn->linearized[0] == '\0') {
 233                 return true;
 234         }
 235
 236         /* Special DNs case */
 237         if (dn->special) {
 238                 return true;
 239         }
 240
 241         /* make sure we free this if alloced previously before replacing */
 242         talloc_free(dn->components);
 243
 244         /* in the common case we have 3 or more components */
 245         /* make sure all components are zeroed, other functions depend on this */
 246         dn->components = talloc_zero_array(dn, struct ldb_dn_component, 3);
 247         if ( ! dn->components) {
 248                 return false;
 249         }
 250         dn->comp_num = 0;
 251
 252         /* Components data space is allocated here once */
 253         data = talloc_array(dn->components, char, strlen(dn->linearized) + 1);
 254         if (!data) {
 255                 return false;
 256         }
 257
 258         p = dn->linearized;
 259         in_attr = true;
 260         trim = true;
 261         t = NULL;
 262         d = dt = data;
 263
 264         while (*p) {
 265
 266                 if (in_attr) {
 267                         if (trim) {
 268                                 if (*p == ' ') {
 269                                         p++;
 270                                         continue;
 271                                 }
 272
 273                                 /* first char */
 274                                 trim = false;
 275
 276                                 if (isdigit(*p)) {
 277                                         is_oid = true;
 278                                 } else
 279                                 if ( ! isalpha(*p)) {
 280                                         /* not a digit nor an alpha, invalid attribute name */
 281                                         dn->invalid = true;
 282                                         goto failed;
 283                                 }
 284
 285                                 *d++ = *p++;
 286                                 continue;
 287                         }
 288
 289                         if (*p == ' ') {
 290                                 p++;
 291                                 /* valid only if we are at the end */
 292                                 trim = true;
 293                                 continue;
 294                         }
 295
 296                         if (trim && (*p != '=')) {
 297                                 /* spaces/tabs are not allowed in attribute names */
 298                                 dn->invalid = true;
 299                                 goto failed;
 300                         }
 301
 302                         if (*p == '=') {
 303                                 /* attribute terminated */
 304                                 in_attr = false;
 305                                 in_value = true;
 306                                 trim = true;
 307                                 l = 0;
 308
 309                                 *d++ = '\0';
 310                                 dn->components[dn->comp_num].name = talloc_strdup(dn->components, dt);
 311                                 if ( ! dn->components[dn->comp_num].name) {
 312                                         /* ouch */
 313                                         goto failed;
 314                                 }
 315
 316                                 dt = d;
 317
 318                                 p++;
 319                                 continue;
 320                         }
 321
 322                         if (is_oid && ( ! (isdigit(*p) || (*p == '.')))) {
 323                                 /* not a digit nor a dot, invalid attribute oid */
 324                                 dn->invalid = true;
 325                                 goto failed;
 326                         } else
 327                         if ( ! (isalpha(*p) || isdigit(*p) || (*p == '-'))) {
 328                                 /* not ALPHA, DIGIT or HYPHEN */
 329                                 dn->invalid = true;
 330                                 goto failed;
 331                         }
 332
 333                         *d++ = *p++;
 334                         continue;
 335                 }
 336
 337                 if (in_value) {
 338                         if (in_quote) {
 339                                 if (*p == '\"') {
 340                                         if (p[-1] != '\\') {
 341                                                 p++;
 342                                                 in_quote = false;
 343                                                 continue;
 344                                         }
 345                                 }
 346                                 *d++ = *p++;
 347                                 l++;
 348                                 continue;
 349                         }
 350
 351                         if (trim) {
 352                                 if (*p == ' ') {
 353                                         p++;
 354                                         continue;
 355                                 }
 356
 357                                 /* first char */
 358                                 trim = false;
 359
 360                                 if (*p == '\"') {
 361                                         in_quote = true;
 362                                         p++;
 363                                         continue;
 364                                 }
 365                         }
 366
 367                         switch (*p) {
 368
 369                         /* TODO: support ber encoded values
 370                         case '#':
 371                         */
 372
 373                         case ',':
 374                                 if (escape) {
 375                                         *d++ = *p++;
 376                                         l++;
 377                                         escape = false;
 378                                         continue;
 379                                 }
 380                                 /* ok found value terminator */
 381
 382                                 if ( t ) {
 383                                         /* trim back */
 384                                         d -= (p - t);
 385                                         l -= (p - t);
 386                                 }
 387
 388                                 in_attr = true;
 389                                 in_value = false;
 390                                 trim = true;
 391
 392                                 p++;
 393                                 *d++ = '\0';
 394                                 dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
 395                                 dn->components[dn->comp_num].value.length = l;
 396                                 if ( ! dn->components[dn->comp_num].value.data) {
 397                                         /* ouch ! */
 398                                         goto failed;
 399                                 }
 400
 401                                 dt = d;
 402
 403                                 dn->comp_num++;
 404                                 if (dn->comp_num > 2) {
 405                                         dn->components = talloc_realloc(dn,
 406                                                                         dn->components,
 407                                                                         struct ldb_dn_component,
 408                                                                         dn->comp_num + 1);
 409                                         if ( ! dn->components) {
 410                                                 /* ouch ! */
 411                                                 goto failed;
 412                                         }
 413                                         /* make sure all components are zeroed, other functions depend on this */
 414                                         memset(&dn->components[dn->comp_num], '\0', sizeof(struct ldb_dn_component));
 415                                 }
 416
 417                                 continue;
 418
 419                         case '=':
 420                         case '\n':
 421                         case '+':
 422                         case '<':
 423                         case '>':
 424                         case '#':
 425                         case ';':
 426                         case '\"':
 427                                 /* a string with not escaped specials is invalid (tested) */
 428                                 if ( ! escape) {
 429                                         dn->invalid = true;
 430                                         goto failed;
 431                                 }
 432                                 escape = false;
 433
 434                                 *d++ = *p++;
 435                                 l++;
 436
 437                                 if ( t ) t = NULL;
 438                                 break;
 439
 440                         case '\\':
 441                                 if ( ! escape) {
 442                                         escape = true;
 443                                         p++;
 444                                         continue;
 445                                 }
 446                                 escape = false;
 447
 448                                 *d++ = *p++;
 449                                 l++;
 450
 451                                 if ( t ) t = NULL;
 452                                 break;
 453
 454                         default:
 455                                 if (escape) {
 456                                         if (sscanf(p, "%02x", &x) != 1) {
 457                                                 /* invalid escaping sequence */
 458                                                 dn->invalid = true;
 459                                                 goto failed;
 460                                         }
 461                                         escape = false;
 462
 463                                         p += 2;
 464                                         *d++ = (unsigned char)x;
 465                                         l++;
 466
 467                                         if ( t ) t = NULL;
 468                                         break;
 469                                 }
 470
 471                                 if (*p == ' ') {
 472                                         if ( ! t) t = p;
 473                                 } else {
 474                                         if ( t ) t = NULL;
 475                                 }
 476
 477                                 *d++ = *p++;
 478                                 l++;
 479
 480                                 break;
 481                         }
 482
 483                 }
 484         }
 485
 486         if (in_attr || in_quote) {
 487                 /* invalid dn */
 488                 dn->invalid = true;
 489                 goto failed;
 490         }
 491
 492         /* save last element */
 493         if ( t ) {
 494                 /* trim back */
 495                 d -= (p - t);
 496                 l -= (p - t);
 497         }
 498
 499         *d++ = '\0';
 500         dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
 501         dn->components[dn->comp_num].value.length = l;
 502
 503         if ( ! dn->components[dn->comp_num].value.data) {
 504                 /* ouch */
 505                 goto failed;
 506         }
 507
 508         dn->comp_num++;
 509
 510         talloc_free(data);
 511         return true;
 512
 513 failed:
 514         dn->comp_num = 0;
 515         talloc_free(dn->components);
 516         return false;
 517 }
 518
 519 bool ldb_dn_validate(struct ldb_dn *dn)
 520 {
 521         return ldb_dn_explode(dn);
 522 }
 523
 524 const char *ldb_dn_get_linearized(struct ldb_dn *dn)
 525 {
 526         int i, len;
 527         char *d, *n;
 528
 529         if ( ! dn || ( dn->invalid)) return NULL;
 530
 531         if (dn->linearized) return dn->linearized;
 532
 533         if ( ! dn->components) {
 534                 dn->invalid = true;
 535                 return NULL;
 536         }
 537
 538         if (dn->comp_num == 0) {
 539                 dn->linearized = talloc_strdup(dn, "");
 540                 if ( ! dn->linearized) return NULL;
 541                 return dn->linearized;
 542         }
 543
 544         /* calculate maximum possible length of DN */
 545         for (len = 0, i = 0; i < dn->comp_num; i++) {
 546                 len += strlen(dn->components[i].name); /* name len */
 547                 len += (dn->components[i].value.length * 3); /* max escaped data len */
 548                 len += 2; /* '=' and ',' */
 549         }
 550         dn->linearized = talloc_array(dn, char, len);
 551         if ( ! dn->linearized) return NULL;
 552
 553         d = dn->linearized;
 554
 555         for (i = 0; i < dn->comp_num; i++) {
 556
 557                 /* copy the name */
 558                 n = dn->components[i].name;
 559                 while (*n) *d++ = *n++;
 560
 561                 *d++ = '=';
 562
 563                 /* and the value */
 564                 d += ldb_dn_escape_internal( d,
 565                                 (char *)dn->components[i].value.data,
 566                                 dn->components[i].value.length);
 567                 *d++ = ',';
 568         }
 569
 570         *(--d) = '\0';
 571
 572         /* don't waste more memory than necessary */
 573         dn->linearized = talloc_realloc(dn, dn->linearized, char, (d - dn->linearized + 1));
 574
 575         return dn->linearized;
 576 }
 577
 578 char *ldb_dn_alloc_linearized(void *mem_ctx, struct ldb_dn *dn)
 579 {
 580         return talloc_strdup(mem_ctx, ldb_dn_get_linearized(dn));
 581 }
 582
 583 /*
 584   casefold a dn. We need to casefold the attribute names, and canonicalize
 585   attribute values of case insensitive attributes.
 586 */
 587
 588 static bool ldb_dn_casefold_internal(struct ldb_dn *dn)
 589 {
 590         int i, ret;
 591
 592         if ( ! dn || dn->invalid) return false;
 593
 594         if (dn->valid_case) return true;
 595
 596         if (( ! dn->components) && ( ! ldb_dn_explode(dn))) {
 597                 return false;
 598         }
 599
 600         for (i = 0; i < dn->comp_num; i++) {
 601                 const struct ldb_attrib_handler *h;
 602
 603                 dn->components[i].cf_name = ldb_attr_casefold(dn->components, dn->components[i].name);
 604                 if (!dn->components[i].cf_name) {
 605                         goto failed;
 606                 }
 607
 608                 h = ldb_attrib_handler(dn->ldb, dn->components[i].cf_name);
 609                 ret = h->canonicalise_fn(dn->ldb, dn->components,
 610                                          &(dn->components[i].value),
 611                                          &(dn->components[i].cf_value));
 612                 if (ret != 0) {
 613                         goto failed;
 614                 }
 615         }
 616
 617         dn->valid_case = true;
 618
 619         return true;
 620
 621 failed:
 622         for (i = 0; i < dn->comp_num; i++) {
 623                 LDB_FREE(dn->components[i].cf_name);
 624                 LDB_FREE(dn->components[i].cf_value.data);
 625         }
 626         return false;
 627 }
 628
 629 const char *ldb_dn_get_casefold(struct ldb_dn *dn)
 630 {
 631         int i, len;
 632         char *d, *n;
 633
 634         if (dn->casefold) return dn->casefold;
 635
 636         if (dn->special) {
 637                 dn->casefold = talloc_strdup(dn, dn->linearized);
 638                 if (!dn->casefold) return NULL;
 639                 dn->valid_case = true;
 640                 return dn->casefold;
 641         }
 642
 643         if ( ! ldb_dn_casefold_internal(dn)) {
 644                 return NULL;
 645         }
 646
 647         if (dn->comp_num == 0) {
 648                 if (dn->linearized && dn->linearized[0] == '\0') {
 649                         /* hmm a NULL dn, should we faild casefolding ? */
 650                         dn->casefold = talloc_strdup(dn, "");
 651                         return dn->casefold;
 652                 }
 653                 /* A DN must be NULL, special, or have components */
 654                 dn->invalid = true;
 655                 return NULL;
 656         }
 657
 658         /* calculate maximum possible length of DN */
 659         for (len = 0, i = 0; i < dn->comp_num; i++) {
 660                 len += strlen(dn->components[i].cf_name); /* name len */
 661                 len += (dn->components[i].cf_value.length * 3); /* max escaped data len */
 662                 len += 2; /* '=' and ',' */
 663         }
 664         dn->casefold = talloc_array(dn, char, len);
 665         if ( ! dn->casefold) return NULL;
 666
 667         d = dn->casefold;
 668
 669         for (i = 0; i < dn->comp_num; i++) {
 670
 671                 /* copy the name */
 672                 n = dn->components[i].cf_name;
 673                 while (*n) *d++ = *n++;
 674
 675                 *d++ = '=';
 676
 677                 /* and the value */
 678                 d += ldb_dn_escape_internal( d,
 679                                 (char *)dn->components[i].cf_value.data,
 680                                 dn->components[i].cf_value.length);
 681                 *d++ = ',';
 682         }
 683         *(--d) = '\0';
 684
 685         /* don't waste more memory than necessary */
 686         dn->casefold = talloc_realloc(dn, dn->casefold, char, strlen(dn->casefold) + 1);
 687
 688         return dn->casefold;
 689 }
 690
 691 char *ldb_dn_alloc_casefold(void *mem_ctx, struct ldb_dn *dn)
 692 {
 693         return talloc_strdup(mem_ctx, ldb_dn_get_casefold(dn));
 694 }
 695
 696 /* Determine if dn is below base, in the ldap tree.  Used for
 697  * evaluating a subtree search.
 698  * 0 if they match, otherwise non-zero
 699  */
 700
 701 int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn)
 702 {
 703         int ret;
 704         int n_base, n_dn;
 705
 706         if ( ! base || base->invalid) return 1;
 707         if ( ! dn || dn->invalid) return -1;
 708
 709         if (( ! base->valid_case) || ( ! dn->valid_case)) {
 710                 if (base->linearized && dn->linearized) {
 711                         /* try with a normal compare first, if we are lucky
 712                          * we will avoid exploding and casfolding */
 713                         int dif;
 714                         dif = strlen(dn->linearized) - strlen(base->linearized);
 715                         if (dif < 0) return dif;
 716                         if (strcmp(base->linearized, &dn->linearized[dif]) == 0) return 0;
 717                 }
 718
 719                 if ( ! ldb_dn_casefold_internal(base)) {
 720                         return 1;
 721                 }
 722
 723                 if ( ! ldb_dn_casefold_internal(dn)) {
 724                         return -1;
 725                 }
 726
 727         }
 728
 729         /* if base has more components,
 730          * they don't have the same base */
 731         if (base->comp_num > dn->comp_num) {
 732                 return (dn->comp_num - base->comp_num);
 733         }
 734
 735         if (dn->comp_num == 0) {
 736                 if (dn->special && base->special) {
 737                         return strcmp(base->linearized, dn->linearized);
 738                 } else if (dn->special) {
 739                         return -1;
 740                 } else if (base->special) {
 741                         return 1;
 742                 } else {
 743                         return 0;
 744                 }
 745         }
 746
 747         n_base = base->comp_num - 1;
 748         n_dn = dn->comp_num - 1;
 749
 750         while (n_base >= 0) {
 751                 /* compare attr names */
 752                 ret = strcmp(base->components[n_base].cf_name, dn->components[n_dn].cf_name);
 753                 if (ret != 0) return ret;
 754
 755                 /* compare attr.cf_value. */
 756                 if (base->components[n_base].cf_value.length != dn->components[n_dn].cf_value.length) {
 757                         return base->components[n_base].cf_value.length - dn->components[n_dn].cf_value.length;
 758                 }
 759                 ret = strcmp((char *)base->components[n_base].cf_value.data, (char *)dn->components[n_dn].cf_value.data);
 760                 if (ret != 0) return ret;
 761
 762                 n_base--;
 763                 n_dn--;
 764         }
 765
 766         return 0;
 767 }
 768
 769 /* compare DNs using casefolding compare functions.
 770
 771    If they match, then return 0
 772  */
 773
 774 int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
 775 {
 776         int i, ret;
 777
 778         if (( ! dn0) || dn0->invalid || ! dn1 || dn1->invalid) return -1;
 779
 780         if (( ! dn0->valid_case) || ( ! dn1->valid_case)) {
 781                 if (dn0->linearized && dn1->linearized) {
 782                         /* try with a normal compare first, if we are lucky
 783                          * we will avoid exploding and casfolding */
 784                         if (strcmp(dn0->linearized, dn1->linearized) == 0) return 0;
 785                 }
 786
 787                 if ( ! ldb_dn_casefold_internal(dn0)) {
 788                         return 1;
 789                 }
 790
 791                 if ( ! ldb_dn_casefold_internal(dn1)) {
 792                         return -1;
 793                 }
 794
 795         }
 796
 797         if (dn0->comp_num != dn1->comp_num) {
 798                 return (dn1->comp_num - dn0->comp_num);
 799         }
 800
 801         if (dn0->comp_num == 0) {
 802                 if (dn0->special && dn1->special) {
 803                         return strcmp(dn0->linearized, dn1->linearized);
 804                 } else if (dn0->special) {
 805                         return 1;
 806                 } else if (dn1->special) {
 807                         return -1;
 808                 } else {
 809                         return 0;
 810                 }
 811         }
 812
 813         for (i = 0; i < dn0->comp_num; i++) {
 814                 /* compare attr names */
 815                 ret = strcmp(dn0->components[i].cf_name, dn1->components[i].cf_name);
 816                 if (ret != 0) return ret;
 817
 818                 /* compare attr.cf_value. */
 819                 if (dn0->components[i].cf_value.length != dn1->components[i].cf_value.length) {
 820                         return dn0->components[i].cf_value.length - dn1->components[i].cf_value.length;
 821                 }
 822                 ret = strcmp((char *)dn0->components[i].cf_value.data, (char *)dn1->components[i].cf_value.data);
 823                 if (ret != 0) return ret;
 824         }
 825
 826         return 0;
 827 }
 828
 829 static struct ldb_dn_component ldb_dn_copy_component(void *mem_ctx, struct ldb_dn_component *src)
 830 {
 831         struct ldb_dn_component dst;
 832
 833         memset(&dst, 0, sizeof(dst));
 834
 835         if (src == NULL) {
 836                 return dst;
 837         }
 838
 839         dst.value = ldb_val_dup(mem_ctx, &(src->value));
 840         if (dst.value.data == NULL) {
 841                 return dst;
 842         }
 843
 844         dst.name = talloc_strdup(mem_ctx, src->name);
 845         if (dst.name == NULL) {
 846                 LDB_FREE(dst.value.data);
 847                 return dst;
 848         }
 849
 850         if (src->cf_value.data) {
 851                 dst.cf_value = ldb_val_dup(mem_ctx, &(src->cf_value));
 852                 if (dst.cf_value.data == NULL) {
 853                         LDB_FREE(dst.value.data);
 854                         LDB_FREE(dst.name);
 855                         return dst;
 856                 }
 857
 858                 dst.cf_name = talloc_strdup(mem_ctx, src->cf_name);
 859                 if (dst.cf_name == NULL) {
 860                         LDB_FREE(dst.cf_name);
 861                         LDB_FREE(dst.value.data);
 862                         LDB_FREE(dst.name);
 863                         return dst;
 864                 }
 865         } else {
 866                 dst.cf_value.data = NULL;
 867                 dst.cf_name = NULL;
 868         }
 869
 870         return dst;
 871 }
 872
 873 struct ldb_dn *ldb_dn_copy(void *mem_ctx, struct ldb_dn *dn)
 874 {
 875         struct ldb_dn *new_dn;
 876
 877         if (!dn || dn->invalid) {
 878                 return NULL;
 879         }
 880
 881         new_dn = talloc_zero(mem_ctx, struct ldb_dn);
 882         if ( !new_dn) {
 883                 return NULL;
 884         }
 885
 886         *new_dn = *dn;
 887
 888         if (dn->components) {
 889                 int i;
 890
 891                 new_dn->components = talloc_zero_array(new_dn, struct ldb_dn_component, dn->comp_num);
 892                 if ( ! new_dn->components) {
 893                         talloc_free(new_dn);
 894                         return NULL;
 895                 }
 896
 897                 for (i = 0; i < dn->comp_num; i++) {
 898                         new_dn->components[i] = ldb_dn_copy_component(new_dn->components, &dn->components[i]);
 899                         if ( ! new_dn->components[i].value.data) {
 900                                 talloc_free(new_dn);
 901                                 return NULL;
 902                         }
 903                 }
 904         }
 905
 906         if (dn->casefold) {
 907                 new_dn->casefold = talloc_strdup(new_dn, dn->casefold);
 908                 if ( ! new_dn->casefold) {
 909                         talloc_free(new_dn);
 910                         return NULL;
 911                 }
 912         }
 913
 914         if (dn->linearized) {
 915                 new_dn->linearized = talloc_strdup(new_dn, dn->linearized);
 916                 if ( ! new_dn->linearized) {
 917                         talloc_free(new_dn);
 918                         return NULL;
 919                 }
 920         }
 921
 922         return new_dn;
 923 }
 924
 925 /* modify the given dn by adding a base.
 926  *
 927  * return true if successful and false if not
 928  * if false is returned the dn may be marked invalid
 929  */
 930 bool ldb_dn_add_base(struct ldb_dn *dn, struct ldb_dn *base)
 931 {
 932         const char *s;
 933         char *t;
 934
 935         if ( !base || base->invalid || !dn || dn->invalid) {
 936                 return false;
 937         }
 938
 939         if (dn->components) {
 940                 int i;
 941
 942                 if ( ! ldb_dn_validate(base)) {
 943                         return false;
 944                 }
 945
 946                 s = NULL;
 947                 if (dn->valid_case) {
 948                         if ( ! (s = ldb_dn_get_casefold(base))) {
 949                                 return false;
 950                         }
 951                 }
 952
 953                 dn->components = talloc_realloc(dn,
 954                                                 dn->components,
 955                                                 struct ldb_dn_component,
 956                                                 dn->comp_num + base->comp_num);
 957                 if ( ! dn->components) {
 958                         dn->invalid = true;
 959                         return false;
 960                 }
 961
 962                 for (i = 0; i < base->comp_num; dn->comp_num++, i++) {
 963                         dn->components[dn->comp_num] = ldb_dn_copy_component(dn->components, &base->components[i]);
 964                         if (dn->components[dn->comp_num].value.data == NULL) {
 965                                 dn->invalid = true;
 966                                 return false;
 967                         }
 968                 }
 969
 970                 if (dn->casefold && s) {
 971                         t = talloc_asprintf(dn, "%s,%s", dn->casefold, s);
 972                         LDB_FREE(dn->casefold);
 973                         dn->casefold = t;
 974                 }
 975         }
 976
 977         if (dn->linearized) {
 978
 979                 s = ldb_dn_get_linearized(base);
 980                 if ( ! s) {
 981                         return false;
 982                 }
 983
 984                 t = talloc_asprintf(dn, "%s,%s", dn->linearized, s);
 985                 if ( ! t) {
 986                         dn->invalid = true;
 987                         return false;
 988                 }
 989                 LDB_FREE(dn->linearized);
 990                 dn->linearized = t;
 991         }
 992
 993         return true;
 994 }
 995
 996 /* modify the given dn by adding a base.
 997  *
 998  * return true if successful and false if not
 999  * if false is returned the dn may be marked invalid
1000  */
1001 bool ldb_dn_add_base_fmt(struct ldb_dn *dn, const char *base_fmt, ...)
1002 {
1003         struct ldb_dn *base;
1004         char *base_str;
1005         va_list ap;
1006         bool ret;
1007
1008         if ( !dn || dn->invalid) {
1009                 return false;
1010         }
1011
1012         va_start(ap, base_fmt);
1013         base_str = talloc_vasprintf(dn, base_fmt, ap);
1014         va_end(ap);
1015
1016         if (base_str == NULL) {
1017                 return false;
1018         }
1019
1020         base = ldb_dn_new(base_str, dn->ldb, base_str);
1021
1022         ret = ldb_dn_add_base(dn, base);
1023
1024         talloc_free(base_str);
1025
1026         return ret;
1027 }
1028
1029 /* modify the given dn by adding children elements.
1030  *
1031  * return true if successful and false if not
1032  * if false is returned the dn may be marked invalid
1033  */
1034 bool ldb_dn_add_child(struct ldb_dn *dn, struct ldb_dn *child)
1035 {
1036         const char *s;
1037         char *t;
1038
1039         if ( !child || child->invalid || !dn || dn->invalid) {
1040                 return false;
1041         }
1042
1043         if (dn->components) {
1044                 int n, i, j;
1045
1046                 if ( ! ldb_dn_validate(child)) {
1047                         return false;
1048                 }
1049
1050                 s = NULL;
1051                 if (dn->valid_case) {
1052                         if ( ! (s = ldb_dn_get_casefold(child))) {
1053                                 return false;
1054                         }
1055                 }
1056
1057                 n = dn->comp_num + child->comp_num;
1058
1059                 dn->components = talloc_realloc(dn,
1060                                                 dn->components,
1061                                                 struct ldb_dn_component,
1062                                                 n);
1063                 if ( ! dn->components) {
1064                         dn->invalid = true;
1065                         return false;
1066                 }
1067
1068                 for (i = dn->comp_num - 1, j = n - 1; i >= 0; i--, j--) {
1069                         dn->components[j] = dn->components[i];
1070                 }
1071
1072                 for (i = 0; i < child->comp_num; i++) {
1073                         dn->components[i] = ldb_dn_copy_component(dn->components, &child->components[i]);
1074                         if (dn->components[i].value.data == NULL) {
1075                                 dn->invalid = true;
1076                                 return false;
1077                         }
1078                 }
1079
1080                 dn->comp_num = n;
1081
1082                 if (dn->casefold && s) {
1083                         t = talloc_asprintf(dn, "%s,%s", s, dn->casefold);
1084                         LDB_FREE(dn->casefold);
1085                         dn->casefold = t;
1086                 }
1087         }
1088
1089         if (dn->linearized) {
1090
1091                 s = ldb_dn_get_linearized(child);
1092                 if ( ! s) {
1093                         return false;
1094                 }
1095
1096                 t = talloc_asprintf(dn, "%s,%s", s, dn->linearized);
1097                 if ( ! t) {
1098                         dn->invalid = true;
1099                         return false;
1100                 }
1101                 LDB_FREE(dn->linearized);
1102                 dn->linearized = t;
1103         }
1104
1105         return true;
1106 }
1107
1108 /* modify the given dn by adding children elements.
1109  *
1110  * return true if successful and false if not
1111  * if false is returned the dn may be marked invalid
1112  */
1113 bool ldb_dn_add_child_fmt(struct ldb_dn *dn, const char *child_fmt, ...)
1114 {
1115         struct ldb_dn *child;
1116         char *child_str;
1117         va_list ap;
1118         bool ret;
1119
1120         if ( !dn || dn->invalid) {
1121                 return false;
1122         }
1123
1124         va_start(ap, child_fmt);
1125         child_str = talloc_vasprintf(dn, child_fmt, ap);
1126         va_end(ap);
1127
1128         if (child_str == NULL) {
1129                 return false;
1130         }
1131
1132         child = ldb_dn_new(child_str, dn->ldb, child_str);
1133
1134         ret = ldb_dn_add_child(dn, child);
1135
1136         talloc_free(child_str);
1137
1138         return ret;
1139 }
1140
1141 bool ldb_dn_remove_base_components(struct ldb_dn *dn, unsigned int num)
1142 {
1143         int i;
1144
1145         if ( ! ldb_dn_validate(dn)) {
1146                 return false;
1147         }
1148
1149         if (dn->comp_num < num) {
1150                 return false;
1151         }
1152
1153         /* free components */
1154         for (i = num; i > 0; i--) {
1155                 LDB_FREE(dn->components[dn->comp_num - i].name);
1156                 LDB_FREE(dn->components[dn->comp_num - i].value.data);
1157                 LDB_FREE(dn->components[dn->comp_num - i].cf_name);
1158                 LDB_FREE(dn->components[dn->comp_num - i].cf_value.data);
1159         }
1160
1161         dn->comp_num -= num;
1162
1163         if (dn->valid_case) {
1164                 for (i = 0; i < dn->comp_num; i++) {
1165                         LDB_FREE(dn->components[i].cf_name);
1166                         LDB_FREE(dn->components[i].cf_value.data);
1167                 }
1168                 dn->valid_case = false;
1169         }
1170
1171         LDB_FREE(dn->casefold);
1172         LDB_FREE(dn->linearized);
1173
1174         return true;
1175 }
1176
1177 bool ldb_dn_remove_child_components(struct ldb_dn *dn, unsigned int num)
1178 {
1179         int i, j;
1180
1181         if ( ! ldb_dn_validate(dn)) {
1182                 return false;
1183         }
1184
1185         if (dn->comp_num < num) {
1186                 return false;
1187         }
1188
1189         for (i = 0, j = num; j < dn->comp_num; i++, j++) {
1190                 if (i < num) {
1191                         LDB_FREE(dn->components[i].name);
1192                         LDB_FREE(dn->components[i].value.data);
1193                         LDB_FREE(dn->components[i].cf_name);
1194                         LDB_FREE(dn->components[i].cf_value.data);
1195                 }
1196                 dn->components[i] = dn->components[j];
1197         }
1198
1199         dn->comp_num -= num;
1200
1201         if (dn->valid_case) {
1202                 for (i = 0; i < dn->comp_num; i++) {
1203                         LDB_FREE(dn->components[i].cf_name);
1204                         LDB_FREE(dn->components[i].cf_value.data);
1205                 }
1206                 dn->valid_case = false;
1207         }
1208
1209         LDB_FREE(dn->casefold);
1210         LDB_FREE(dn->linearized);
1211
1212         return true;
1213 }
1214
1215 struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, struct ldb_dn *dn)
1216 {
1217         struct ldb_dn *new_dn;
1218
1219         new_dn = ldb_dn_copy(mem_ctx, dn);
1220         if ( !new_dn ) {
1221                 return NULL;
1222         }
1223
1224         if ( ! ldb_dn_remove_child_components(new_dn, 1)) {
1225                 talloc_free(new_dn);
1226                 return NULL;
1227         }
1228
1229         return new_dn;
1230 }
1231
1232 /* Create a 'canonical name' string from a DN:
1233
1234    ie dc=samba,dc=org -> samba.org/
1235       uid=administrator,ou=users,dc=samba,dc=org = samba.org/users/administrator
1236
1237    There are two formats, the EX format has the last / replaced with a newline (\n).
1238
1239 */
1240 static char *ldb_dn_canonical(void *mem_ctx, struct ldb_dn *dn, int ex_format) {
1241         int i;
1242         TALLOC_CTX *tmpctx;
1243         char *cracked = NULL;
1244
1245         if ( ! ldb_dn_validate(dn)) {
1246                 return NULL;
1247         }
1248
1249         tmpctx = talloc_new(mem_ctx);
1250
1251         /* Walk backwards down the DN, grabbing 'dc' components at first */
1252         for (i = dn->comp_num - 1 ; i >= 0; i--) {
1253                 if (ldb_attr_cmp(dn->components[i].name, "dc") != 0) {
1254                         break;
1255                 }
1256                 if (cracked) {
1257                         cracked = talloc_asprintf(tmpctx, "%s.%s",
1258                                                   ldb_dn_escape_value(tmpctx, dn->components[i].value),
1259                                                   cracked);
1260                 } else {
1261                         cracked = ldb_dn_escape_value(tmpctx, dn->components[i].value);
1262                 }
1263                 if (!cracked) {
1264                         goto done;
1265                 }
1266         }
1267
1268         /* Only domain components?  Finish here */
1269         if (i < 0) {
1270                 if (ex_format) {
1271                         cracked = talloc_append_string(tmpctx, cracked, "\n");
1272                 } else {
1273                         cracked = talloc_append_string(tmpctx, cracked, "/");
1274                 }
1275                 talloc_steal(mem_ctx, cracked);
1276                 goto done;
1277         }
1278
1279         /* Now walk backwards appending remaining components */
1280         for (; i > 0; i--) {
1281                 cracked = talloc_asprintf_append(cracked, "/%s",
1282                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1283                 if (!cracked) {
1284                         goto done;
1285                 }
1286         }
1287
1288         /* Last one, possibly a newline for the 'ex' format */
1289         if (ex_format) {
1290                 cracked = talloc_asprintf_append(cracked, "\n%s",
1291                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1292         } else {
1293                 cracked = talloc_asprintf_append(cracked, "/%s",
1294                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1295         }
1296
1297         talloc_steal(mem_ctx, cracked);
1298 done:
1299         talloc_free(tmpctx);
1300         return cracked;
1301 }
1302
1303 /* Wrapper functions for the above, for the two different string formats */
1304 char *ldb_dn_canonical_string(void *mem_ctx, struct ldb_dn *dn) {
1305         return ldb_dn_canonical(mem_ctx, dn, 0);
1306
1307 }
1308
1309 char *ldb_dn_canonical_ex_string(void *mem_ctx, struct ldb_dn *dn) {
1310         return ldb_dn_canonical(mem_ctx, dn, 1);
1311 }
1312
1313 int ldb_dn_get_comp_num(struct ldb_dn *dn)
1314 {
1315         if ( ! ldb_dn_validate(dn)) {
1316                 return -1;
1317         }
1318         return dn->comp_num;
1319 }
1320
1321 const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num)
1322 {
1323         if ( ! ldb_dn_validate(dn)) {
1324                 return NULL;
1325         }
1326         if (num >= dn->comp_num) return NULL;
1327         return dn->components[num].name;
1328 }
1329
1330 const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn, unsigned int num)
1331 {
1332         if ( ! ldb_dn_validate(dn)) {
1333                 return NULL;
1334         }
1335         if (num >= dn->comp_num) return NULL;
1336         return &dn->components[num].value;
1337 }
1338
1339 const char *ldb_dn_get_rdn_name(struct ldb_dn *dn)
1340 {
1341         if ( ! ldb_dn_validate(dn)) {
1342                 return NULL;
1343         }
1344         if (dn->comp_num == 0) return NULL;
1345         return dn->components[0].name;
1346 }
1347
1348 const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn)
1349 {
1350         if ( ! ldb_dn_validate(dn)) {
1351                 return NULL;
1352         }
1353         if (dn->comp_num == 0) return NULL;
1354         return &dn->components[0].value;
1355 }
1356
1357 int ldb_dn_set_component(struct ldb_dn *dn, int num, const char *name, const struct ldb_val val)
1358 {
1359         char *n;
1360         struct ldb_val v;
1361
1362         if ( ! ldb_dn_validate(dn)) {
1363                 return LDB_ERR_OTHER;
1364         }
1365
1366         if (num >= dn->comp_num) {
1367                 return LDB_ERR_OTHER;
1368         }
1369
1370         n = talloc_strdup(dn, name);
1371         if ( ! n) {
1372                 return LDB_ERR_OTHER;
1373         }
1374
1375         v.length = val.length;
1376         v.data = (uint8_t *)talloc_memdup(dn, val.data, v.length+1);
1377         if ( ! v.data) {
1378                 talloc_free(n);
1379                 return LDB_ERR_OTHER;
1380         }
1381
1382         talloc_free(dn->components[num].name);
1383         talloc_free(dn->components[num].value.data);
1384         dn->components[num].name = n;
1385         dn->components[num].value = v;
1386
1387         if (dn->valid_case) {
1388                 int i;
1389                 for (i = 0; i < dn->comp_num; i++) {
1390                         LDB_FREE(dn->components[i].cf_name);
1391                         LDB_FREE(dn->components[i].cf_value.data);
1392                 }
1393                 dn->valid_case = false;
1394         }
1395         LDB_FREE(dn->casefold);
1396
1397         return LDB_SUCCESS;
1398 }
1399
1400 bool ldb_dn_is_valid(struct ldb_dn *dn)
1401 {
1402         if ( ! dn) return false;
1403         return ! dn->invalid;
1404 }
1405
1406 bool ldb_dn_is_special(struct ldb_dn *dn)
1407 {
1408         if ( ! dn || dn->invalid) return false;
1409         return dn->special;
1410 }
1411
1412 bool ldb_dn_check_special(struct ldb_dn *dn, const char *check)
1413 {
1414         if ( ! dn || dn->invalid) return false;
1415         return ! strcmp(dn->linearized, check);
1416 }
1417
1418 bool ldb_dn_is_null(struct ldb_dn *dn)
1419 {
1420         if ( ! dn || dn->invalid) return false;
1421         if (dn->linearized && (dn->linearized[0] == '\0')) return true;
1422         return false;
1423 }