/*

   Unix SMB/CIFS Implementation.

   DSDB schema header

   Copyright (C) Stefan Metzmacher <metze@samba.org> 2006-2007

   Copyright (C) Andrew Bartlett <abartlet@samba.org> 2006-2008

   This program is free software; you can redistribute it and/or modify

   it under the terms of the GNU General Public License as published by

   the Free Software Foundation; either version 3 of the License, or

   (at your option) any later version.

   This program is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License

   along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

#include "includes.h"

#include "dsdb/samdb/samdb.h"

#include <ldb_module.h>

#include "lib/util/binsearch.h"

#include "lib/util/tsort.h"

#include "util/dlinklist.h"

#undef strcasecmp

#undef strncasecmp

static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,

                  const struct dsdb_schema *schema,

                  const char **class_list,

                  enum dsdb_attr_list_query query);

static int uint32_cmp(uint32_t c1, uint32_t c2)

{

  if (c1 == c2) return 0;

  return c1 > c2 ? 1 : -1;

}

static int strcasecmp_with_ldb_val(const struct ldb_val *target, const char *str)

{

  int ret = strncasecmp((const char *)target->data, str, target->length);

  if (ret == 0) {

    size_t len = strlen(str);

    if (target->length > len) {

      if (target->data[len] == 0) {

        return 0;

      }

      return 1;

    }

    if (target->length < len) {

      return -1;

    }

  }

  return ret;

}

const struct dsdb_attribute *dsdb_attribute_by_attributeID_id(const struct dsdb_schema *schema,

                    uint32_t id)

{

  struct dsdb_attribute *c;

  /*

   * 0xFFFFFFFF is used as value when no mapping table is available,

   * so don't try to match with it

   */

  if (id == 0xFFFFFFFF) return NULL;

  /* check for msDS-IntId type attribute */

  if (dsdb_pfm_get_attid_type(id) == DSDB_ATTID_TYPE_INTID) {

    BINARY_ARRAY_SEARCH_P(schema->attributes_by_msDS_IntId,

              schema->num_int_id_attr, msDS_IntId, id, uint32_cmp, c);

    return c;

  }

  BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_id,

            schema->num_attributes, attributeID_id, id, uint32_cmp, c);

  return c;

}

const struct dsdb_attribute *dsdb_attribute_by_attributeID_oid(const struct dsdb_schema *schema,

                     const char *oid)

{

  struct dsdb_attribute *c;

  if (!oid) return NULL;

  BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_oid,

            schema->num_attributes, attributeID_oid, oid, strcasecmp, c);

  return c;

}

const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName(const struct dsdb_schema *schema,

                     const char *name)

{

  struct dsdb_attribute *c;

  if (!name) return NULL;

  BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,

            schema->num_attributes, lDAPDisplayName, name, strcasecmp, c);

  return c;

}

const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,

                       const struct ldb_val *name)

{

  struct dsdb_attribute *a;

  if (!name) return NULL;

  BINARY_ARRAY_SEARCH_P(schema->attributes_by_lDAPDisplayName,

            schema->num_attributes, lDAPDisplayName, name, strcasecmp_with_ldb_val, a);

  return a;

}

const struct dsdb_attribute *dsdb_attribute_by_linkID(const struct dsdb_schema *schema,

                  int linkID)

{

  struct dsdb_attribute *c;

  BINARY_ARRAY_SEARCH_P(schema->attributes_by_linkID,

            schema->num_attributes, linkID, linkID, uint32_cmp, c);

  return c;

}

const struct dsdb_attribute *dsdb_attribute_by_cn_ldb_val(const struct dsdb_schema *schema,

                const struct ldb_val *cn)

{

  struct dsdb_attribute *c;

  BINARY_ARRAY_SEARCH_P(schema->attributes_by_cn,

            schema->num_attributes, cn, cn, strcasecmp_with_ldb_val, c);

  return c;

}

const struct dsdb_class *dsdb_class_by_governsID_id(const struct dsdb_schema *schema,

                uint32_t id)

{

  struct dsdb_class *c;

  /*

   * 0xFFFFFFFF is used as value when no mapping table is available,

   * so don't try to match with it

   */

  if (id == 0xFFFFFFFF) return NULL;

  BINARY_ARRAY_SEARCH_P(schema->classes_by_governsID_id,

            schema->num_classes, governsID_id, id, uint32_cmp, c);

  return c;

}

const struct dsdb_class *dsdb_class_by_governsID_oid(const struct dsdb_schema *schema,

                 const char *oid)

{

  struct dsdb_class *c;

  if (!oid) return NULL;

  BINARY_ARRAY_SEARCH_P(schema->classes_by_governsID_oid,

            schema->num_classes, governsID_oid, oid, strcasecmp, c);

  return c;

}

const struct dsdb_class *dsdb_class_by_lDAPDisplayName(const struct dsdb_schema *schema,

                   const char *name)

{

  struct dsdb_class *c;

  if (!name) return NULL;

  BINARY_ARRAY_SEARCH_P(schema->classes_by_lDAPDisplayName,

            schema->num_classes, lDAPDisplayName, name, strcasecmp, c);

  return c;

}

const struct dsdb_class *dsdb_class_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,

                     const struct ldb_val *name)

{

  struct dsdb_class *c;

  if (!name) return NULL;

  BINARY_ARRAY_SEARCH_P(schema->classes_by_lDAPDisplayName,

            schema->num_classes, lDAPDisplayName, name, strcasecmp_with_ldb_val, c);

  return c;

}

const struct dsdb_class *dsdb_class_by_cn_ldb_val(const struct dsdb_schema *schema,

              const struct ldb_val *cn)

{

  struct dsdb_class *c;

  if (!cn) return NULL;

  BINARY_ARRAY_SEARCH_P(schema->classes_by_cn,

            schema->num_classes, cn, cn, strcasecmp_with_ldb_val, c);

  return c;

}

const char *dsdb_lDAPDisplayName_by_id(const struct dsdb_schema *schema,

               uint32_t id)

{

  const struct dsdb_attribute *a;

  const struct dsdb_class *c;

  a = dsdb_attribute_by_attributeID_id(schema, id);

  if (a) {

    return a->lDAPDisplayName;

  }

  c = dsdb_class_by_governsID_id(schema, id);

  if (c) {

    return c->lDAPDisplayName;

  }

  return NULL;

}

/**

    Return a list of linked attributes, in lDAPDisplayName format.

    This may be used to determine if a modification would require

    backlinks to be updated, for example

*/

WERROR dsdb_linked_attribute_lDAPDisplayName_list(const struct dsdb_schema *schema, TALLOC_CTX *mem_ctx, const char ***attr_list_ret)

{

  const char **attr_list = NULL;

  struct dsdb_attribute *cur;

  unsigned int i = 0;

  for (cur = schema->attributes; cur; cur = cur->next) {

    if (cur->linkID == 0) continue;

    attr_list = talloc_realloc(mem_ctx, attr_list, const char *, i+2);

    if (!attr_list) {

      return WERR_NOT_ENOUGH_MEMORY;

    }

    attr_list[i] = cur->lDAPDisplayName;

    i++;

  }

  if (attr_list != NULL && attr_list[i] != NULL) {

    attr_list[i] = NULL;

  }

  *attr_list_ret = attr_list;

  return WERR_OK;

}

const char **merge_attr_list(TALLOC_CTX *mem_ctx,

           const char **attrs, const char * const*new_attrs)

{

  const char **ret_attrs;

  unsigned int i;

  size_t new_len, new_attr_len, orig_len = str_list_length(attrs);

  if (new_attrs == NULL || new_attrs[0] == NULL) {

    return attrs;

  }

  new_attr_len = str_list_length(new_attrs);

  ret_attrs = talloc_realloc(mem_ctx,

           attrs, const char *, orig_len + new_attr_len + 1);

  if (ret_attrs) {

    for (i = 0; i < new_attr_len; i++) {

      ret_attrs[orig_len + i] = new_attrs[i];

    }

    new_len = orig_len + new_attr_len;

    ret_attrs[new_len] = NULL;

  }

  return ret_attrs;

}

/*

  Return a merged list of the attributes of exactly one class (not

  considering subclasses, auxiliary classes etc)

*/

const char **dsdb_attribute_list(TALLOC_CTX *mem_ctx, const struct dsdb_class *sclass, enum dsdb_attr_list_query query)

{

  const char **attr_list = NULL;

  switch (query) {

  case DSDB_SCHEMA_ALL_MAY:

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);

    break;

  case DSDB_SCHEMA_ALL_MUST:

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);

    break;

  case DSDB_SCHEMA_SYS_MAY:

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);

    break;

  case DSDB_SCHEMA_SYS_MUST:

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);

    break;

  case DSDB_SCHEMA_MAY:

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);

    break;

  case DSDB_SCHEMA_MUST:

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);

    break;

  case DSDB_SCHEMA_ALL:

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);

    break;

  }

  return attr_list;

}

static const char **attribute_list_from_class(TALLOC_CTX *mem_ctx,

                const struct dsdb_schema *schema,

                const struct dsdb_class *sclass,

                enum dsdb_attr_list_query query)

{

  const char **this_class_list;

  const char **system_recursive_list;

  const char **recursive_list;

  const char **attr_list;

  this_class_list = dsdb_attribute_list(mem_ctx, sclass, query);

  recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,

                 sclass->systemAuxiliaryClass,

                 query);

  system_recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,

                  sclass->auxiliaryClass,

                  query);

  attr_list = this_class_list;

  attr_list = merge_attr_list(mem_ctx, attr_list, recursive_list);

  attr_list = merge_attr_list(mem_ctx, attr_list, system_recursive_list);

  return attr_list;

}

/* Return a full attribute list for a given class list

   Via attribute_list_from_class() this calls itself when recursing on auxiliary classes

 */

static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,

                  const struct dsdb_schema *schema,

                  const char **class_list,

                  enum dsdb_attr_list_query query)

{

  unsigned int i;

  const char **attr_list = NULL;

  for (i=0; class_list && class_list[i]; i++) {

    const char **sclass_list

      = attribute_list_from_class(mem_ctx, schema,

                dsdb_class_by_lDAPDisplayName(schema, class_list[i]),

                query);

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);

  }

  return attr_list;

}

/* Return a full attribute list for a given class list (as a ldb_message_element)

   Using the ldb_message_element ensures we do length-limited

   comparisons, rather than casting the possibly-unterminated string

   Via attribute_list_from_class() this calls

   dsdb_full_attribute_list_internal() when recursing on auxiliary classes

 */

static const char **dsdb_full_attribute_list_internal_el(TALLOC_CTX *mem_ctx,

               const struct dsdb_schema *schema,

               const struct ldb_message_element *el,

               enum dsdb_attr_list_query query)

{

  unsigned int i;

  const char **attr_list = NULL;

  for (i=0; i < el->num_values; i++) {

    const char **sclass_list

      = attribute_list_from_class(mem_ctx, schema,

                dsdb_class_by_lDAPDisplayName_ldb_val(schema, &el->values[i]),

                query);

    attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);

  }

  return attr_list;

}

static int qsort_string(const char **s1, const char **s2)

{

  return strcasecmp(*s1, *s2);

}

/* Helper function to remove duplicates from the attribute list to be returned */

static const char **dedup_attr_list(const char **attr_list)

{

  size_t new_len = str_list_length(attr_list);

  /* Remove duplicates */

  if (new_len > 1) {

    size_t i;

    TYPESAFE_QSORT(attr_list, new_len, qsort_string);

    for (i=1; new_len > 0 && i < new_len; i++) {

      const char **val1 = &attr_list[i-1];

      const char **val2 = &attr_list[i];

      if (ldb_attr_cmp(*val1, *val2) == 0) {

        memmove(val1, val2, (new_len - i) * sizeof( *attr_list));

        attr_list[new_len-1] = NULL;

        new_len--;

        i--;

      }

    }

  }

  return attr_list;

}

/* Return a full attribute list for a given class list (as a ldb_message_element)

   Using the ldb_message_element ensures we do length-limited

   comparisons, rather than casting the possibly-unterminated string

   The result contains only unique values

 */

const char **dsdb_full_attribute_list(TALLOC_CTX *mem_ctx,

              const struct dsdb_schema *schema,

              const struct ldb_message_element *class_list,

              enum dsdb_attr_list_query query)

{

  const char **attr_list = dsdb_full_attribute_list_internal_el(mem_ctx, schema, class_list, query);

  return dedup_attr_list(attr_list);

}

/* Return the schemaIDGUID of a class */

const struct GUID *class_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,

                                                          const char *name)

{

        const struct dsdb_class *object_class = dsdb_class_by_lDAPDisplayName(schema, name);

        if (!object_class)

                return NULL;

        return &object_class->schemaIDGUID;

}

const struct GUID *attribute_schemaid_guid_by_lDAPDisplayName(const struct dsdb_schema *schema,

                    const char *name)

{

        const struct dsdb_attribute *attr = dsdb_attribute_by_lDAPDisplayName(schema, name);

        if (!attr)

                return NULL;

        return &attr->schemaIDGUID;

}

/*

 * Sort a "objectClass" attribute (LDB message element "objectclass_element")

 * into correct order and validate that all object classes specified actually

 * exist in the schema.

 * The output is written in an existing LDB message element

 * "out_objectclass_element" where the values will be allocated on "mem_ctx".

 */

int dsdb_sort_objectClass_attr(struct ldb_context *ldb,

             const struct dsdb_schema *schema,

             const struct ldb_message_element *objectclass_element,

             TALLOC_CTX *mem_ctx,

             struct ldb_message_element *out_objectclass_element)

{

  unsigned int i, lowest;

  struct class_list {

    struct class_list *prev, *next;

    const struct dsdb_class *objectclass;

  } *unsorted = NULL, *sorted = NULL, *current = NULL,

    *poss_parent = NULL, *new_parent = NULL,

    *current_lowest = NULL, *current_lowest_struct = NULL;

  struct ldb_message_element *el;

  TALLOC_CTX *tmp_mem_ctx;

  tmp_mem_ctx = talloc_new(mem_ctx);

  if (tmp_mem_ctx == NULL) {

    return ldb_oom(ldb);

  }

  /*

   * DESIGN:

   *

   * We work on 4 different 'bins' (implemented here as linked lists):

   *

   * * sorted:       the eventual list, in the order we wish to push

   *                 into the database.  This is the only ordered list.

   *

   * * parent_class: The current parent class 'bin' we are

   *                 trying to find subclasses for

   *

   * * subclass:     The subclasses we have found so far

   *

   * * unsorted:     The remaining objectClasses

   *

   * The process is a matter of filtering objectClasses up from

   * unsorted into sorted.  Order is irrelevant in the later 3 'bins'.

   *

   * We start with 'top' (found and promoted to parent_class

   * initially).  Then we find (in unsorted) all the direct

   * subclasses of 'top'.  parent_classes is concatenated onto

   * the end of 'sorted', and subclass becomes the list in

   * parent_class.

   *

   * We then repeat, until we find no more subclasses.  Any left

   * over classes are added to the end.

   *

   */

  /*

   * Firstly, dump all the "objectClass" values into the unsorted bin,

   * except for 'top', which is special

   */

  for (i=0; i < objectclass_element->num_values; i++) {

    current = talloc(tmp_mem_ctx, struct class_list);

    if (!current) {

      talloc_free(tmp_mem_ctx);

      return ldb_oom(ldb);

    }

    current->objectclass = dsdb_class_by_lDAPDisplayName_ldb_val(schema, &objectclass_element->values[i]);

    if (!current->objectclass) {

      ldb_asprintf_errstring(ldb, "objectclass %.*s is not a valid objectClass in schema",

                 (int)objectclass_element->values[i].length, (const char *)objectclass_element->values[i].data);

      /* This looks weird, but windows apparently returns this for invalid objectClass values */

      talloc_free(tmp_mem_ctx);

      return LDB_ERR_NO_SUCH_ATTRIBUTE;

    } else if (current->objectclass->isDefunct) {

      ldb_asprintf_errstring(ldb, "objectclass %.*s marked as isDefunct objectClass in schema - not valid for new objects",

                 (int)objectclass_element->values[i].length, (const char *)objectclass_element->values[i].data);

      /* This looks weird, but windows apparently returns this for invalid objectClass values */

      talloc_free(tmp_mem_ctx);

      return LDB_ERR_NO_SUCH_ATTRIBUTE;

    }

    /* Don't add top to list, we will do that later */

    if (ldb_attr_cmp("top", current->objectclass->lDAPDisplayName) != 0) {

      DLIST_ADD_END(unsorted, current);

    }

  }

  /* Add top here, to prevent duplicates */

  current = talloc(tmp_mem_ctx, struct class_list);

  current->objectclass = dsdb_class_by_lDAPDisplayName(schema, "top");

  DLIST_ADD_END(sorted, current);

  /* For each object: find parent chain */

  for (current = unsorted; current != NULL; current = current->next) {

    for (poss_parent = unsorted; poss_parent; poss_parent = poss_parent->next) {

      if (ldb_attr_cmp(poss_parent->objectclass->lDAPDisplayName, current->objectclass->subClassOf) == 0) {

        break;

      }

    }

    /* If we didn't get to the end of the list, we need to add this parent */

    if (poss_parent || (ldb_attr_cmp("top", current->objectclass->subClassOf) == 0)) {

      continue;

    }

    new_parent = talloc(tmp_mem_ctx, struct class_list);

    new_parent->objectclass = dsdb_class_by_lDAPDisplayName(schema, current->objectclass->subClassOf);

    DLIST_ADD_END(unsorted, new_parent);

  }

  /* For each object: order by hierarchy */

  while (unsorted != NULL) {

    lowest = UINT_MAX;

    current_lowest = current_lowest_struct = NULL;

    for (current = unsorted; current != NULL; current = current->next) {

      if (current->objectclass->subClass_order <= lowest) {

        /*

         * According to MS-ADTS 3.1.1.1.4 structural

         * and 88 object classes are always listed after

         * the other class types in a subclass hierarchy

         */

        if (current->objectclass->objectClassCategory > 1) {

          current_lowest = current;

        } else {

          current_lowest_struct = current;

        }

        lowest = current->objectclass->subClass_order;

      }

    }

    if (current_lowest == NULL) {

      current_lowest = current_lowest_struct;

    }

    if (current_lowest != NULL) {

      DLIST_REMOVE(unsorted,current_lowest);

      DLIST_ADD_END(sorted,current_lowest);

    }

  }

  /* Now rebuild the sorted "objectClass" message element */

  el = out_objectclass_element;

  el->flags = objectclass_element->flags;

  el->name = talloc_strdup(mem_ctx, objectclass_element->name);

  if (el->name == NULL) {

    talloc_free(tmp_mem_ctx);

    return ldb_oom(ldb);

  }

  el->num_values = 0;

  el->values = NULL;

  for (current = sorted; current != NULL; current = current->next) {

    el->values = talloc_realloc(mem_ctx, el->values,

              struct ldb_val, el->num_values + 1);

    if (el->values == NULL) {

      talloc_free(tmp_mem_ctx);

      return ldb_oom(ldb);

    }

    el->values[el->num_values] = data_blob_string_const(current->objectclass->lDAPDisplayName);

    ++(el->num_values);

  }

  talloc_free(tmp_mem_ctx);

  return LDB_SUCCESS;

}