If the document is valid according to the schema, this function returns
    True.
    If the document is not valid according to the schema, errors are logged
    then False is returned.

def validate(document, schema, log_qualifier = True):
    """
    If the document is valid according to the schema, this function returns
    True.
    If the document is not valid according to the schema, errors are logged
    then False is returned.
    """
    if isinstance(schema, ValidatorNode):
        if not validate(document, schema.content):
            return False
        if not schema.validator(document, schema.content):
            if log_qualifier:
                LOG.error("%r failed to validate with qualifier %s", document, schema.validator.__name__)
            return False
        return True
    elif isinstance(schema, dict):
        if not isinstance(document, dict):
            LOG.error("wanted a dictionary, got a %s", document.__class__.__name__)
            return False
        generic = []
        optional = {}
        optionalnull = {}
        mandatory = []
        for key, schema_val in schema.iteritems():
            if isinstance(key, ValidatorNode):
                if key.mode == 'mandatory':
                    mandatory.append((key, schema_val))
                else:
                    generic.append((key, schema_val))
            elif isinstance(schema_val, Optional):
                optional[key] = schema_val
            elif isinstance(schema_val, OptionalNull):
                optional[key] = schema_val
                optionalnull[key] = True
            else:
                mandatory.append((key, schema_val))

        doc_copy = document.copy()

        for key, schema_val in mandatory:
            if isinstance(key, ValidatorNode):
                nb = 0
                rm = []
                for doc_key, doc_val in doc_copy.iteritems():
                    if not validate(doc_key, key, False):
                        continue

                    nb += 1

                    if validate(doc_val, schema_val):
                        rm.append(doc_key)
                    else:
                        return False

                if nb == 0:
                    LOG.error("missing document %r for qualifier: %r", key.content, key.validator.__name__)
                    return False
                elif key.min is not None and nb < key.min:
                    LOG.error("no enough document %r for qualifier: %r (min: %r, found: %r)", key.content, key.validator.__name__, key.min, nb)
                    return False
                elif key.max is not None and nb > key.max:
                    LOG.error("too many document %r for qualifier: %r (max: %r, found: %r)", key.content, key.validator.__name__, key.max, nb)
                    return False
                else:
                    for x in rm:
                        del doc_copy[x]
                    continue

            doc_val = doc_copy.get(key, Nothing)
            if doc_val is Nothing:
                LOG.error("missing key %r in document", key)
                return False

            if helpers.is_scalar(schema_val):
                if not validate(doc_val, schema_val):
                    return False
                del doc_copy[key]
                continue

            if schema_val.modifier:
                for modname in schema_val.modifier:
                    if modname in _modifiers:
                        document[key] = _modifiers[modname](document[key])
                        doc_val = _modifiers[modname](doc_val)
                    elif hasattr(doc_val, modname):
                        document[key] = getattr(document[key], modname)()
                        doc_val = getattr(doc_val, modname)()

            if _valid_len(key, doc_val, schema_val.min_len, schema_val.max_len) is False:
                return False
            if not validate(doc_val, schema_val.content):
                return False
            del doc_copy[key]

        for key, schema_val in generic:
            nb = 0
            rm = []

            for doc_key, doc_val in doc_copy.iteritems():
                if not validate(doc_key, key, False):
                    continue

                nb += 1

                if validate(doc_val, schema_val):
                    rm.append(doc_key)
                else:
                    return False

            if key.min is not None and nb < key.min:
                LOG.error("no enough document %r for qualifier: %r (min: %r, found: %r)", key.content, key.validator.__name__, key.min, nb)
                return False
            elif key.max is not None and nb > key.max:
                LOG.error("too many document %r for qualifier: %r (max: %r, found: %r)", key.content, key.validator.__name__, key.max, nb)
                return False
            else:
                for x in rm:
                    del doc_copy[x]
                continue

        for key, doc_val in doc_copy.iteritems():
            schema_val = optional.get(key, Nothing)
            if schema_val is Nothing:
                LOG.error("forbidden key %s in document", key)
                return False
            elif optionalnull.has_key(key) and doc_val is None:
                continue
            elif schema_val.min_len == 0 and doc_val is "":
                continue

            if schema_val.modifier:
                for modname in schema_val.modifier:
                    if modname in _modifiers:
                        document[key] = _modifiers[modname](document[key])
                        doc_val = _modifiers[modname](doc_val)
                    elif hasattr(doc_val, modname):
                        document[key] = getattr(document[key], modname)()
                        doc_val = getattr(doc_val, modname)()
                if optionalnull.has_key(key) and doc_val is None:
                    continue
                elif schema_val.min_len == 0 and doc_val is "":
                    continue

            if _valid_len(key, doc_val, schema_val.min_len, schema_val.max_len) is False:
                return False
            if not validate(doc_val, schema_val.content):
                return False
        return True
    elif isinstance(schema, list):
        if not isinstance(document, list):
            LOG.error("wanted a list, got a %s", document.__class__.__name__)
        for elt in document:
            # XXX: give a meaning when there are multiple element in a sequence of a schema?
            if len(schema) < 2:
                if not validate(elt, schema[0]):
                    return False
            elif isinstance(schema[0], dict):
                tmp = {}
                for x in schema:
                    for key, val in x.iteritems():
                        tmp[key] = val
                if not validate(elt, tmp):
                    return False
            else:
                if not validate(elt, schema[0]):
                    return False
        return True
    elif isinstance(schema, Any):
        return True
    elif isinstance(schema, Scalar):
        return helpers.is_scalar(document)
    else: # scalar
        if isinstance(schema, str):
            schema = unicode(schema)
        if isinstance(document, str):
            document = unicode(document, 'utf8')
        if schema.__class__ != document.__class__:
            LOG.error("wanted a %s, got a %s", schema.__class__.__name__, document.__class__.__name__)
            return False
        return True