Compile mapping: key-value matching

def _compile_mapping(self, schema):
        """ Compile mapping: key-value matching """
        assert not self.matcher, 'Mappings cannot be matchers'

        # This stuff is tricky, but thankfully, I like comments :)

        # Set default Marker on all keys.
        # This makes sure that all keys will still become markers, and hence have the correct default behavior
        schema = {self.default_keys(k) if self.get_schema_type(k) != const.COMPILED_TYPE.MARKER else k: v
                  for k, v in schema.items()}

        # Add `Extra`
        # Every Schema implicitly has an `Extra` that defaults to `extra_keys`.
        # Note that this is the only place in the code where Marker behavior is hardcoded :)
        schema.setdefault(markers.Extra, self.extra_keys)

        # Compile both keys & values as schemas.
        # Key schemas are compiled as "Matchers" for performance.
        compiled = {self.sub_compile(key, matcher=True): self.sub_compile(value)
                    for key, value in schema.items()}

        # Notify Markers that they were compiled.
        # _compile_marker() has already done part of the job: it only specified `key_schema`.
        # Here we let the Marker know its `value_schema` as well.
        for key_schema, value_schema in compiled.items():
            if key_schema.compiled_type == const.COMPILED_TYPE.MARKER:
                key_schema.compiled.on_compiled(value_schema=value_schema, as_mapping_key=True)

        # Sort key schemas for matching.

        # Since various schema types have different priority, we need to sort these accordingly.
        # Then, literals match before types, and Markers can define execution order using `priority`.
        # For instance, Remove() should be called first (before any validation takes place),
        # while Extra() should be checked last so it catches all extra keys that did not match other key schemas.

        # In addition, since mapping keys are mostly literals, we want direct matching instead of the costly function calls.
        # Hence, remember which of them are literals or 'catch-all' markers.
        is_literal  = lambda key_schema: key_schema.compiled.key_schema.compiled_type == const.COMPILED_TYPE.LITERAL
        is_identity = lambda identity: key_schema.compiled.key_schema is Identity

        compiled = [ (key_schema, compiled[key_schema], is_literal(key_schema), is_identity(key_schema))
                     for key_schema in self.sort_schemas(compiled.keys())]
        ''' :var  compiled: Sorted list of CompiledSchemas: (key-schema, value-schema, is-literal),
            :type compiled: list[CompiledSchema, CompiledSchema, bool]
        '''

        # Prepare self
        self.compiled_type = const.COMPILED_TYPE.MAPPING
        self.name = _(u'{mapping_cls}[{mapping_keys}]').format(
            mapping_cls=get_type_name(type(schema)),
            mapping_keys=_(u',').join(key_schema.name for key_schema, value_schema, is_literal, is_identity in compiled)
        )

        # Error partials
        schema_type = type(schema)
        err_type = self.Invalid(_(u'Wrong value type'), get_type_name(schema_type))

        # Validator
        def validate_mapping(d):
            # Type check
            if not isinstance(d, schema_type):
                # expected=<type>, provided=<type>
                raise err_type(provided=get_type_name(type(d)))

            # For each schema key, pick matching input key-value pairs.
            # Since we always have Extra which is a catch-all -- this will always result into a full input coverage.
            # Also, key schemas are sorted according to the priority, we're handling each set of matching keys in order.

            errors = []  # Collect errors on the fly
            d_keys = set(d.keys())  # Make a copy of dict keys for destructive iteration

            for key_schema, value_schema, is_literal, is_identity in compiled:
                # First, collect matching (key, value) pairs for the `key_schema`.
                # Note that `key_schema` can change the value (e.g. `Coerce(int)`), so for every key
                # we store both the initial value (`input-key`) and the sanitized value (`sanitized-key`).
                # This results into a list of triples: [(input-key, sanitized-key, input-value), ...].

                matches = []

                if is_literal:  # (short-circuit for literals)
                    # Since mapping keys are mostly literals --
                    # save some iterations & function calls in favor of direct matching,
                    # which introduces a HUGE performance improvement
                    k = key_schema.schema.key  # get the literal from the marker
                    if k in d_keys:
                        # (See comments below)
                        matches.append(( k, k, d[k] ))
                        d_keys.remove(k)
                elif is_identity:  # (short-circuit for Marker(Identity))
                    # When this value is an identity function -- we plainly add all keys to it.
                    # This is to short-circuit catch-all markers like `Extra`, which, being executed last,
                    # just gets all remaining keys.
                    matches.extend((k, k, d[k]) for k in d_keys)
                    d_keys = None  # empty it since we've processed everything
                elif d_keys:
                    # For non-literal schemas we have to walk all input keys
                    # and detect those that match the current `key_schema`.
                    # In contrast to literals, such keys may have multiple matches (e.g. `{ int: 1 }`).

                    # Note that this condition branch includes the logic from the short-circuited logic implemented above,
                    # but is less performant.

                    for k in tuple(d_keys):
                        # Exec key schema on the input key.
                        # Since all key schemas are compiled as matchers -- we get a tuple (key-matched, sanitized-key)

                        okay, sanitized_k = key_schema(k)

                        # If this key has matched -- append it to the list of matches for the current `key_schema`.
                        # Also, remove the key from the original input so it does not match any other key schemas
                        # with lower priorities.
                        if okay:
                            matches.append(( k, sanitized_k, d[k] ))
                            d_keys.remove(k)

                # Now, having a `key_schema` and a list of matches for it, do validation.
                # If the key is a marker -- execute the marker first so it has a chance to modify the input,
                # and then proceed with value validation.

                # Execute Marker first.
                if key_schema.compiled_type == const.COMPILED_TYPE.MARKER:
                    # Note that Markers can raise errors as well.
                    # Since they're compiled - all marker errors are raised as `Invalid`.
                    try:
                        matches = key_schema.compiled.execute(d, matches)
                    except Invalid as e:
                        # Add marker errors to the list of Invalid reports for this schema.
                        # Using enrich(), we're also setting `path` prefix, and other info known at this step.
                        errors.append(e.enrich(
                            # Markers are responsible to set `expected`, `provided`, `validator`
                            expected=key_schema.name,
                            provided=None,  # Marker's required to set that
                            path=self.path,
                            validator=key_schema.compiled
                        ))
                        # If a marker raised an error -- the (key, value) pair is already Invalid, and no
                        # further validation is required.
                        continue

                # Proceed with validation.
                # Now, we validate values for every (key, value) pairs in the current list of matches,
                # and rebuild the mapping.
                for k, sanitized_k, v in matches:
                    try:
                        # Execute the value schema and store it into the rebuilt mapping
                        # using the sanitized key, which might be different from the original key.
                        d[sanitized_k] = value_schema(v)

                        # Remove the original key in case `key_schema` has transformed it.
                        if k != sanitized_k:
                            del d[k]
                    except signals.RemoveValue:
                        # `value_schema` commanded to drop this value
                        del d[k]
                    except Invalid as e:
                        # Any value validation errors are appended to the list of Invalid reports for the schema
                        # enrich() adds more info on the collected errors.
                        errors.append(e.enrich(
                            expected=value_schema.name,
                            provided=get_literal_name(v),
                            path=self.path + [k],
                            validator=value_schema
                        ))

            assert not d_keys, 'Keys must be empty after destructive iteration. Remainder: {!r}'.format(d_keys)

            # Errors?
            if errors:
                # Note that we did not care about whether a sub-schema raised a single Invalid or MultipleInvalid,
                # since MultipleInvalid will flatten the list for us.
                raise MultipleInvalid.if_multiple(errors)

            # Finish
            return d

        return validate_mapping