4
\$\begingroup\$

I was reminded by an achievement notification yesterday of this question of mine, posted nearly four and a half years ago. After reading through my own code and the review posted, I decided to re-implement it.

Thus far, I have implemented a few changes:

  • The function has been renamed to mapping_replace, perhaps more clear than keymap_replace.
  • The scope-creep features of lower_keys=False, lower_values=False, lower_string=False have been removed; as pointed out by alexwlchan, behaviors like these should be left to the end-user.
  • The function will now, by default, throw an error if a key-value conflict is detected; if the end-user so desires, however, this behavior can be suppressed (e.g.: { "A": "B", "B": "C" } - the second key "B" conflicts with the value of "A").
  • The function now supports replacement with regular expressions, using re.sub. I am concerned in particular about this portion of the code, as it would seem that compiling a (potentially) significant number of regular expressions on the fly over-and-over again is an expensive operation; I tried to implement some form of memoization, but to no avail.
  • Finally, this function has been re-implemented in Python 3.8, under which dictionaries now retain their order of insertion.

dict_replace.py

import re


_DUPLICATE_KEY_EXCEPTION_MSG = "Key '{0}' already provided."
_KEY_VALUE_CONFLICT_EXCEPTION_MSG = "The key of '{0}' -> '{1}' conflicts with a separate mapping containing the value '{0}'."


class _KeyValueConflictException(Exception):
    pass      


def _validate_mappings(mappings: dict) -> None:
    """Validate a set of mappings provided to mapping_replace function.

    This function takes a dictionary provided to the mapping_replace function by the end-
    -user and determines whether or not the dictionary contains key-value conflicts.

    Keyword arguments:
    mappings -- The set of mappings to validate.
    """
    keys = []
    values = []
    for key, value in mappings.items():
        if key in values:
            raise _KeyValueConflictException(_KEY_VALUE_CONFLICT_EXCEPTION_MSG.format(key, value))

        keys.append(key)
        values.append(value)


def mapping_replace(string: str, mappings: dict, use_regex=False, *, validate_mappings=True) -> str:
    """Replace portions of a string with a replacement.

    This function takes a dictionary either of the format 'string -> replacement string' 
    or of the format 'regular expression -> replacement string'; in the case of the 
    former, it will replace all instances of 'string' with the provided replacement string, 
    and in the the case of the latter it will replace all expression matches with the
    provided replacement string. 

    It should be noted that this function, by default, will raise an error if key-value
    conflicts are found (e.g.: { 'A': 'B', 'B': 'C' } -- value 'B' and key 'B' conflict),
    but this behavior can be suppressed by calling the function with validate_mappings=False.

    Keyword arguments:
    string            -- The string to perform replacement operations on.
    mappings          -- The mapping of strings -> replacements or patterns -> replacements.
    use_regex         -- Whether or not the function uses regular expressions. False by default.
    validate_mappings -- Whether or not to validate the provided mappings for conflicts.
    """
    if validate_mappings:
        _validate_mappings(mappings)

    replaced_string = string
    if use_regex:
        for key, value in mappings.items():
            replaced_string = re.sub(key, value, replaced_string)
    else:
        for key, value in mappings.items():
            replaced_string = replaced_string.replace(key, value)

    return replaced_string

Some example usage:

print(mapping_replace("simple test", { "simple": "complex", "test": "haha" }))
print(mapping_replace("124233 test", { r"\d+": "letters" }, True))
print(mapping_replace("Hello world", { "H": "J", "J": "Y"}, False, validate_mappings=False)) # No exception!
print(mapping_replace("Hello world", { "H": "J", "J": "Y" }))                                # Raises exception!
\$\endgroup\$
6
\$\begingroup\$

Ways of optimizing

  • _validate_mappings function
    Two lists keys = [] and values = [] are just used for accumulation and membership check, though inefficiently.
    Instead, the more optimized way is to rely on dict.values() view object converted to set for fast containment check.
    The optimized function would look as (docstrings are skipped for demo):

    def _validate_mappings(mappings: dict) -> None:
        values = set(mappings.values())
        for key, value in mappings.items():
            if key in values:
                raise _KeyValueConflictException(_KEY_VALUE_CONFLICT_EXCEPTION_MSG.format(key, value))
    
  • mapping_replace function in use_regex=True mode and dealing with multiple regex replacements.
    To replace a loop of numerous subsequent regex compilations and substitutions I would suggest a "single-pass" substitution powered by the following features:

    • regex alternation group (...)|(...)|(...) to combine all raw patterns into one
    • Python dict preserves its insertion order since 3.7
    • the respective replacement string is found using Match.lastindex feature (the integer index of the last matched capturing group)

    Although, this trick may require non-overlapping patterns provided in mappings dict.
    The crucial if use_regex: block:

    ...
    if use_regex:
        keys_list = list(mappings.keys())
        replacer = lambda m: mappings[keys_list[m.lastindex - 1]]
        pat = fr"{'|'.join(f'({k})' for k in mappings.keys())}"   # composing regex alternation group
        replaced_string = re.sub(pat, replacer, replaced_string)
    

I've added some extended test case (3rd one) to show how's the regex trick goes:

print(mapping_replace("simple test", {"simple": "complex", "test": "haha"}))
print(mapping_replace("124233 test", {r"\d+": "letters"}, True))
print(mapping_replace("011 test ABCbb11www", {"\d+": "symbols", "[A-Z]+": "@", "w+": "W3W"}, True))
print(mapping_replace("Hello world", {"H": "J", "J": "Y"}, False, validate_mappings=False))  # No exception!
print(mapping_replace("Hello world", {"H": "J", "J": "Y"}))

The output:

complex haha
letters test
symbols test @bbsymbolsW3W
Yello world
raise _KeyValueConflictException(_KEY_VALUE_CONFLICT_EXCEPTION_MSG.format(key, value))
__main__._KeyValueConflictException: The key of 'J' -> 'Y' conflicts with a separate mapping containing the value 'J'.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ The validation could be simplified further to if mappings.keys() & mapping.values(), because both are set-like objects. \$\endgroup\$ – Graipher Dec 5 '19 at 11:16
  • 1
    \$\begingroup\$ @Graipher, technically - yes, it could be. But the initial idea was to raise on the 1st conflicting key found. Thus, the exact condition if mappings.keys() & mapping.values() won't be self-sufficient, as on the 1st step - the intersection is checked --> then check if it's not empty (if found - it will hold all keys) --> convert set to iterator and consume the 1st key. conflicts = mappings.keys() & mappings.values(); if conflicts: key = next(iter(conflicts)) raise _KeyValueConflictException(_KEY_VALUE_CONFLICT_EXCEPTION_MSG.format(key, mappings[key])) \$\endgroup\$ – RomanPerekhrest Dec 5 '19 at 11:38
  • 1
    \$\begingroup\$ True, the intersection needs to compare all values and keys. \$\endgroup\$ – Graipher Dec 5 '19 at 11:39
  • \$\begingroup\$ @RomanPerekhrest But the happy path will compare all values and keys anyway, so you lose nothing doing it for the error path. It might even be beneficial to inform the user of all the conflicts at once so they are not frustrated by several rounds of trial and errors. \$\endgroup\$ – 301_Moved_Permanently Dec 6 '19 at 17:46
4
\$\begingroup\$

Naming

In many places, functions are described as operating on "mappings" or "set of mappings". As far as I can tell, the dictionary passed as a parameter is a mapping. Thus, the plural form can be removed in various places.

(As a disclaimer, English is not my native language - let me know if I am wrong.)


Unused value

In _validate_mapping, the list keys is populated but never used.


Limitation of the validation

The validation logic seems to be here to ensure that a substitution will not bring a pattern that will be replaced (or would have been replaced) by a different substitution.

This somehow ensure that the order of the dictionary is not important.

An example would be:

print("Yello world" == mapping_replace("Hello world", { "H": "J", "J": "Y"}, False, validate_mapping=False)) # No exception!
print("Jello world" == mapping_replace("Hello world", { "J": "H", "H": "J"}, False, validate_mapping=False)) # No exception!

However, there are various things that may be misleading with the corresponding logic under the assumption that my understanding is valid .

Handling of regexp

Regexp are not properly handled. For instance, this call:

print("\d+ test" == mapping_replace("124233 test", { r"\d+": r"\d+" }, True, validate_mapping=False))

should have the same behaviour with validate_mapping set to True or False. At the moment, it either works or throws the exception.

Opposite situation

There are situations (like above) where the exception is thrown but but probably shouldn't but there are also situations where no exception is thrown but one would be expected. This may give a feeling of "safety" which is not really valid.

An example would be:

print("YYello world" == mapping_replace("Hello world", { "H": "JJ", "J": "Y" }))
print("JJello world" == mapping_replace("Hello world", { "J": "Y", "H": "JJ" }))

Should this throw ?

My expectations

Here is the behavior I'd have expected at least for the regexp case: check that no value from the dict would be matched by any of the keys (using re.search). In reality I do not see any correct way to check for any mapping that could lead to conflicts.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.