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