Patched code sample

def _fixed_parse_formatting(text, token_type, marker):
    """
    This function demonstrates the logic used to fix the denial-of-service
    vulnerability described in CVE-2026-59922 for the Mistune library.

    The vulnerability was caused by a quadratic-time (O(n^2)) complexity issue.
    The old implementation could repeatedly re-scan the string when processing
    inputs with many formatting markers (e.g., '~~a~~b~~c~~...'), leading to
    CPU exhaustion.

    This fixed implementation avoids that vulnerability by performing a single,
    linear-time (O(n)) scan of the string. It uses `text.find()` to locate
    markers and manually advances a position index (`pos`), ensuring that each
    part of the string is processed only once.
    """
    tokens = []
    pos = 0
    marker_len = len(marker)

    while pos < len(text):
        # Find the next opening marker from the current position. `text.find()`
        # is highly optimized and is a key part of the linear scan.
        start_pos = text.find(marker, pos)

        if start_pos == -1:
            # No more markers found; add the remainder of the text and exit.
            if pos < len(text):
                tokens.append(('text', text[pos:]))
            break

        # Capture any plain text located before this marker.
        if start_pos > pos:
            tokens.append(('text', text[pos:start_pos]))

        # Find the corresponding closing marker. The search starts immediately
        # after the opening marker's position.
        end_pos = text.find(marker, start_pos + marker_len)

        if end_pos == -1:
            # No closing marker was found, so the opening marker and the rest
            # of the string are treated as plain text.
            tokens.append(('text', text[start_pos:]))
            break

        # Extract the content between the markers.
        content = text[start_pos + marker_len : end_pos]

        # Check if content is valid (not empty or just whitespace).
        if content and not content.isspace():
            tokens.append((token_type, content))
            # The crucial step: advance the main position (`pos`) to the end of
            # the just-processed token. This prevents re-scanning this segment.
            pos = end_pos + marker_len
        else:
            # If content is invalid, treat the opening marker as plain text
            # and continue scanning from the character right after it.
            tokens.append(('text', text[start_pos : start_pos + marker_len]))
            pos = start_pos + marker_len

    return tokens