def _replace_all(string, substitutions):
    """Replaces occurrences of the given patterns in `string`.

    There are a few reasons this looks complicated:
    * The substitutions are performed with some priority, i.e. patterns that are
      listed first in `substitutions` are higher priority than patterns that are
      listed later.
    * We also take pains to avoid doing replacements that overlap with each
      other, since overlaps invalidate pattern matches.
    * To avoid hairy offset invalidation, we apply the substitutions
      right-to-left.
    * To avoid the "_quote" -> "_quotequote_" rule introducing new pattern
      matches later in the string during decoding, we take the leftmost
      replacement, in cases of overlap.  (Note that no rule can induce new
      pattern matches *earlier* in the string.) (E.g. "_quotedot_" encodes to
      "_quotequote_dot_". Note that "_quotequote_" and "_dot_" both occur in
      this string, and overlap.).

    Args:
        string (string): the string in which the replacements should be performed.
        substitutions: the list of patterns and replacements to apply.

    Returns:
        A string with the appropriate substitutions performed.
    """

    # Find the highest-priority pattern matches for each string index, going
    # left-to-right and skipping indices that are already involved in a
    # pattern match.
    plan = {}
    matched_indices_set = {}
    for pattern_start in range(len(string)):
        if pattern_start in matched_indices_set:
            continue
        for (pattern, replacement) in substitutions:
            if not string.startswith(pattern, pattern_start):
                continue
            length = len(pattern)
            plan[pattern_start] = (length, replacement)
            matched_indices_set.update([(pattern_start + i, True) for i in range(length)])
            break

    # Execute the replacement plan, working from right to left.
    for pattern_start in sorted(plan.keys(), reverse = True):
        length, replacement = plan[pattern_start]
        after_pattern = pattern_start + length
        string = string[:pattern_start] + replacement + string[after_pattern:]

    return string