redlines.processor

  1from __future__ import annotations
  2
  3import re
  4from abc import ABC, abstractmethod
  5from dataclasses import dataclass
  6from difflib import SequenceMatcher
  7from typing import TYPE_CHECKING, Any, Literal
  8
  9if TYPE_CHECKING:
 10    from collections.abc import Sequence
 11    from typing import Callable
 12
 13try:
 14    from nupunkt import sent_tokenize
 15
 16    NUPUNKT_AVAILABLE = True
 17except ImportError:
 18    NUPUNKT_AVAILABLE = False
 19    sent_tokenize: Callable[[str], Any] = lambda x: []  # type: ignore[no-redef]
 20
 21try:
 22    import Levenshtein
 23
 24    LEVENSHTEIN_AVAILABLE = True
 25except ImportError:
 26    LEVENSHTEIN_AVAILABLE = False
 27
 28from .document import Document
 29
 30__all__: tuple[str, ...] = (
 31    "RedlinesProcessor",
 32    "WholeDocumentProcessor",
 33    "NupunktProcessor",
 34    "Redline",
 35    "Stats",
 36    "DiffOperation",
 37    "Chunk",
 38)
 39
 40tokenizer = re.compile(r"((?:[^()\s]+|[().?!-])\s*)")
 41r"""
 42This regular expression matches a group of characters that can include any character except for parentheses
 43and whitespace characters (which include spaces, tabs, and line breaks) or any character
 44that is a parenthesis or punctuation mark (.?!-).
 45The group can also include any whitespace characters that follow these characters.
 46
 47Breaking it down further:
 48
 49* `(` and `)` indicate a capturing group
 50* `(?: )` is a non-capturing group, meaning it matches the pattern but doesn't capture the matched text
 51* `[^()\s]+` matches one or more characters that are not parentheses or whitespace characters
 52* `|` indicates an alternative pattern
 53* `[().?!-]` matches any character that is a parenthesis or punctuation mark `(.?!-)`
 54* `\s*` matches zero or more whitespace characters (spaces, tabs, or line breaks) that follow the previous pattern.
 55"""
 56# This pattern matches one or more newline characters `\n`, and any spaces between them.
 57
 58paragraph_pattern = re.compile(r"((?:\n *)+)")
 59r"""
 60It is used to split the text into paragraphs.
 61
 62* `(?:\\n *)` is a non-capturing group that must start with a `\\n`   and be followed by zero or more spaces.
 63* `((?:\\n *)+)` is the previous non-capturing group repeated one or more times.
 64"""
 65
 66space_pattern = re.compile(r"(\s+)")
 67"""It is used to detect space."""
 68
 69PARAGRAPH_MARKER = "¶"
 70"""
 71The character (U+00B6 PILCROW SIGN) used internally to mark a paragraph boundary.
 72Renderers convert '¶ ' into '\\n\\n'. Input text that literally contains '¶'
 73collides with this convention and may render incorrectly.
 74"""
 75
 76SENTENCE_MARKER = "¦"
 77"""
 78The character (U+00A6 BROKEN BAR) used internally to mark a sentence boundary
 79within a paragraph in sentence-level tokenization (`NupunktProcessor`).
 80
 81Because '¦' is neither whitespace nor a parenthesis, the tokenizer emits '¦ '
 82as a single token — exactly like '¶ ' — so it anchors `SequenceMatcher` at
 83sentence boundaries (a change cannot silently span sentences) without encoding
 84fake paragraph structure. Renderers strip it entirely, so it never appears in
 85output. As with '¶', input text that literally contains '¦ ' collides with this
 86convention and will be silently dropped from rendered output.
 87"""
 88
 89punctuation_token_pattern = re.compile(r"[^\w\s]+")
 90r"""
 91It is used to detect a normalized token that consists entirely of punctuation.
 92
 93* `[^\w\s]` matches any character that is neither a word character (`\w`) nor a
 94  whitespace character (`\s`), which covers parentheses, punctuation marks
 95  (.?!-) and other unicode punctuation such as em-dashes and quotes.
 96* `[^\w\s]+` is the previous character class repeated one or more times.
 97"""
 98
 99
100def _strip_sentence_markers(text: str) -> str:
101    """
102    Remove the sentence boundary markers ('¦ ') emitted by sentence-level tokenization.
103
104    Unlike the paragraph marker '¶', which renders as a real paragraph break ('\\n\\n'),
105    the sentence marker corresponds to nothing in the input text and must never appear
106    in any output (see `SENTENCE_MARKER`).
107
108    It lives here, beside the marker it strips, because both the v1 renderers in
109    `redlines.redlines` and the change tree's opcode conversion in `redlines.changes`
110    need it, and `redlines.changes` cannot import `redlines.redlines`.
111
112    :param text: The text to clean.
113    :type text: str
114    :return: The text with sentence markers removed.
115    :rtype: str
116    """
117    return text.replace(f"{SENTENCE_MARKER} ", "")
118
119
120def _is_punctuation_only(token: str) -> bool:
121    """
122    Returns True if a normalized (whitespace-stripped) token consists entirely of
123    punctuation, or is empty.
124
125    The paragraph boundary token '¶' is explicitly excluded: although it is a
126    punctuation character, merging edits across it would pull paragraph breaks
127    into deletions/insertions and break paragraph handling in the output.
128
129    :param token: The normalized token to test.
130    :type token: str
131    :return: True if the token is empty or punctuation-only (and not '¶').
132    :rtype: bool
133    """
134    if token == "¶":
135        return False
136    return token == "" or punctuation_token_pattern.fullmatch(token) is not None
137
138
139def _merge_ops_split_by_punctuation(
140    opcodes: Sequence[tuple[str, int, int, int, int]],
141    source_normalized: list[str],
142) -> list[tuple[str, int, int, int, int]]:
143    """
144    Cleanup pass over `SequenceMatcher` opcodes that merges adjacent non-equal
145    operations separated only by an 'equal' run of punctuation-only tokens.
146
147    Without this pass, a change such as "thirty (30)" -> "forty (40)" is reported
148    as two separate changes because the '(' between "thirty"/"forty" and
149    "30"/"40" matches as equal. Merging the two edits (and absorbing the
150    punctuation-only equal run between them) reports the single, human-visible
151    change instead.
152
153    Because a merged operation is itself non-equal, chains of edits separated by
154    punctuation collapse naturally into a single operation. Equal runs at the
155    document boundaries are never absorbed, since they are not flanked by
156    non-equal operations on both sides. Paragraph boundary tokens ('¶') are
157    never merged across (see `_is_punctuation_only`).
158
159    :param opcodes: The opcodes returned by `SequenceMatcher.get_opcodes`.
160    :type opcodes: Sequence[tuple[str, int, int, int, int]]
161    :param source_normalized: The normalized source tokens the matcher compared.
162    :type source_normalized: list[str]
163    :return: The opcodes with punctuation-separated edits merged.
164    :rtype: list[tuple[str, int, int, int, int]]
165    """
166    result: list[tuple[str, int, int, int, int]] = []
167
168    for op in opcodes:
169        tag, i1, i2, j1, j2 = op
170        if (
171            tag != "equal"
172            and len(result) >= 2
173            and result[-1][0] == "equal"
174            and result[-2][0] != "equal"
175            and all(
176                _is_punctuation_only(token)
177                for token in source_normalized[result[-1][1] : result[-1][2]]
178            )
179        ):
180            # Merge the previous non-equal op, the punctuation-only equal run,
181            # and the current non-equal op into a single operation.
182            result.pop()
183            prev = result.pop()
184            merged_i1, merged_i2 = prev[1], i2
185            merged_j1, merged_j2 = prev[3], j2
186            if merged_i1 == merged_i2:
187                merged_tag = "insert"
188            elif merged_j1 == merged_j2:
189                merged_tag = "delete"
190            else:
191                merged_tag = "replace"
192            result.append((merged_tag, merged_i1, merged_i2, merged_j1, merged_j2))
193        else:
194            result.append(op)
195
196    return result
197
198
199def tokenize_text(text: str) -> list[str]:
200    """
201    Tokenizes a string into a list of tokens. A token is defined as a group of characters that can include any character except for parentheses
202    and whitespace characters (which include spaces, tabs, and line breaks) or any character that is a parenthesis or punctuation mark (.?!-).
203    The group can also include any whitespace characters that follow these characters.
204    For example, if the text is "Hello, world! This is a test.", the result will be:
205    ['Hello, ', 'world! ', 'This ', 'is ', 'a ', 'test.']
206
207    :param text: The text to tokenize.
208    :type text: str
209    :return: a list of tokens.
210    :rtype: list[str]
211    """
212    # NOTE: Single capturing group hence findall returns list of strings
213    matches: list[str] = re.findall(tokenizer, text)
214    return matches
215
216
217def split_paragraphs(text: str) -> list[str]:
218    """
219    Splits a string into a list of paragraphs. One or more `\n` splits the paragraphs.
220    For example, if the text is "Hello\nWorld\nThis is a test", the result will be:
221    ['Hello', 'World', 'This is a test']
222
223    :param text: The text to split.
224    :type text: str
225    :return: a list of paragraphs.
226    :rtype: list[str]
227    """
228    # NOTE: Single capturing group hence split returns list of strings
229    split_text: list[str] = re.split(paragraph_pattern, text)
230    result: list[str] = []
231    for s in split_text:
232        if s and not re.fullmatch(space_pattern, s):
233            result.append(s.strip())
234
235    return result
236
237
238def concatenate_paragraphs_and_add_chr_182(text: str) -> str:
239    """
240    Split paragraphs and concatenate them. Then add a character '¶' between paragraphs.
241    For example, if the text is "Hello\nWorld\nThis is a test", the result will be:
242    "Hello¶World¶This is a test"
243
244    :param text: The text to split.
245    :type text: str
246    :return: a list of paragraphs.
247    :rtype: str
248    """
249    paragraphs = split_paragraphs(text)
250
251    result: list[str] = []
252    for p in paragraphs:
253        result.append(p)
254        result.append(" ¶ ")
255        # Add a string ' ¶ ' between paragraphs.
256    if len(paragraphs) > 0:
257        result.pop()
258
259    return "".join(result)
260
261
262def concatenate_sentences_and_add_chr_182(text: str) -> str:
263    """
264    Split text into paragraphs and sentences, marking the boundaries.
265
266    Paragraph boundaries (one or more newlines) are preserved and marked with
267    '¶' (`PARAGRAPH_MARKER`), exactly as in paragraph-level tokenization.
268    Within each paragraph, sentences are detected with nupunkt and their
269    boundaries are marked with '¦' (`SENTENCE_MARKER`), which renderers strip
270    so the input's real paragraph structure is not reflowed.
271
272    Uses intelligent sentence boundary detection that handles:
273    - Abbreviations (Dr., Mr., etc.)
274    - Decimals and numbers (3.14, $5.99)
275    - URLs and email addresses
276    - Complex punctuation
277
278    For example: "One. Two.\\n\\nThree."
279    Returns: "One. ¦ Two. ¶ Three."
280
281    Note: Requires nupunkt to be installed (Python 3.11+)
282
283    :param text: The text to split into sentences.
284    :type text: str
285    :return: Text with sentences separated by ' ¦ ' markers within paragraphs,
286        and paragraphs separated by ' ¶ ' markers.
287    :rtype: str
288    :raises ImportError: If nupunkt is not installed.
289    """
290    if not NUPUNKT_AVAILABLE:
291        raise ImportError(
292            "Missing required package: nupunkt.\n"
293            "\n"
294            "Cause: The nupunkt package is required for sentence-level tokenization but is not installed.\n"
295            "\n"
296            "To fix: Install nupunkt (requires Python 3.11+):\n"
297            "  # Using pip\n"
298            "  pip install nupunkt>=0.6.0\n"
299            "\n"
300            "  # Using uv\n"
301            "  uv pip install nupunkt>=0.6.0\n"
302            "\n"
303            "  # Install redlines with nupunkt support\n"
304            "  pip install redlines[nupunkt]\n"
305        )
306
307    paragraphs = split_paragraphs(text)
308
309    paragraph_results: list[str] = []
310    for paragraph in paragraphs:
311        sentences = sent_tokenize(paragraph)
312
313        sentence_results: list[str] = []
314        for sentence in sentences:
315            # sent_tokenize can return either strings or tuples (text, score)
316            # We only care about the text
317            if isinstance(sentence, tuple):
318                text_part = sentence[0]
319            else:
320                text_part = sentence
321            sentence_results.append(text_part.strip())
322        paragraph_results.append(" ¦ ".join(sentence_results))
323
324    return " ¶ ".join(paragraph_results)
325
326
327@dataclass
328class Chunk:
329    """A chunk of text that is being compared. In some cases, it may be the whole document"""
330
331    text: list[str]
332    """The tokens of the chunk"""
333    chunk_location: str | None
334    """An optional string describing the location of the chunk in the document. For example, a PDF page number"""
335
336
337@dataclass
338class DiffOperation:
339    """Internal representation of a diff operation (includes 'equal' operations for rendering)"""
340
341    source_chunk: Chunk
342    test_chunk: Chunk
343    """The chunk of text that is being compared"""
344    opcodes: tuple[str, int, int, int, int]
345    """The opcodes that describe the operation. See the difflib documentation for more information"""
346
347
348@dataclass
349class Redline:
350    """
351    A structured representation of a single change between source and test text.
352
353    This class provides a user-friendly interface for accessing diff information,
354    with direct access to the changed text and position information.
355    """
356
357    operation: Literal["delete", "insert", "replace"]
358    """The type of change: 'delete', 'insert', or 'replace'"""
359
360    source_text: str | None
361    """The text from the source document. Present for 'delete' and 'replace' operations."""
362
363    test_text: str | None
364    """The text from the test document. Present for 'insert' and 'replace' operations."""
365
366    source_position: tuple[int, int] | None
367    """Position in source tokens as (start, end). None for 'insert' operations."""
368
369    test_position: tuple[int, int] | None
370    """Position in test tokens as (start, end). None for 'delete' operations."""
371
372
373@dataclass
374class Stats:
375    """
376    Statistics about the changes between source and test text.
377
378    Provides a comprehensive summary of all changes including counts by operation type,
379    change size metrics, character-level statistics, and optional Levenshtein distance.
380    """
381
382    total_changes: int
383    """Total number of changes (deletions + insertions + replacements)"""
384
385    deletions: int
386    """Number of deletion operations"""
387
388    insertions: int
389    """Number of insertion operations"""
390
391    replacements: int
392    """Number of replacement operations"""
393
394    # Advanced analytics fields
395    longest_change_length: int
396    """Length of the longest change in characters"""
397
398    shortest_change_length: int | None
399    """Length of the shortest change in characters (None if no changes)"""
400
401    average_change_length: float
402    """Average length of all changes in characters"""
403
404    change_ratio: float
405    """Ratio of changed characters to total characters (0.0 to 1.0)"""
406
407    chars_added: int
408    """Total number of characters added"""
409
410    chars_deleted: int
411    """Total number of characters deleted"""
412
413    chars_net_change: int
414    """Net change in characters (added - deleted)"""
415
416    levenshtein_distance: int | None = None
417    """Levenshtein distance between source and test text (None if library not available)"""
418
419
420class RedlinesProcessor(ABC):
421    """
422    An abstract class that defines the interface for a redlines processor.
423    A redlines processor is a class that takes two documents and generates diff operations from them.
424    Use this class as a base class if you want to create a custom redlines processor.
425    See `WholeDocumentProcessor` for an example of a redlines processor.
426    """
427
428    @abstractmethod
429    def process(
430        self, source: Document | str, test: Document | str
431    ) -> list[DiffOperation]:
432        pass
433
434
435class WholeDocumentProcessor(RedlinesProcessor):
436    """
437    A redlines processor that compares two documents. It compares the entire documents as a single chunk.
438
439    A cleanup pass merges adjacent edits separated only by punctuation, so a change
440    such as "thirty (30)" -> "forty (40)" is reported as a single replace instead of
441    two separate changes (see `_merge_ops_split_by_punctuation`).
442
443    By default, ``difflib``'s ``autojunk`` heuristic is disabled. With autojunk on,
444    any comparison of 200+ tokens treats tokens occurring in more than 1% of positions
445    as unmatchable "popular junk", which silently degrades diffs of repetitive documents
446    (schedules, price lists, "Intentionally omitted" runs) into whole-document replaces.
447    """
448
449    def __init__(self, *, autojunk: bool = False) -> None:
450        """
451        :param autojunk: Passed to difflib.SequenceMatcher. Defaults to False because the
452            default heuristic silently degrades diffs of repetitive documents of 200+ tokens
453            (see ADR-0010); set True to restore difflib's default popular-token heuristic,
454            which can be faster on large repetitive documents.
455        :type autojunk: bool
456        """
457        self.autojunk = autojunk
458
459    def process(
460        self, source: Document | str, test: Document | str
461    ) -> list[DiffOperation]:
462        """
463        Compare two documents as a single chunk.
464
465        :param source: The source document to compare.
466        :type source: Document | str
467        :param test: The test document to compare.
468        :type test: Document | str
469        :return: A list of `DiffOperation` that describe the differences between the two documents.
470        :rtype: list[DiffOperation]
471        """
472        # Extract text from documents if needed
473        source_text = source.text if isinstance(source, Document) else source
474        test_text = test.text if isinstance(test, Document) else test
475
476        # Tokenize the texts
477        source_tokens = tokenize_text(
478            concatenate_paragraphs_and_add_chr_182(source_text)
479        )
480        test_tokens = tokenize_text(concatenate_paragraphs_and_add_chr_182(test_text))
481
482        # Normalize tokens by stripping whitespace for comparison
483        # This allows the matcher to focus on content differences rather than whitespace variations
484        # while still preserving the original tokens (including whitespace) for display in the output
485        seq_source_normalized = [token.strip() for token in source_tokens]
486        seq_test_normalized = [token.strip() for token in test_tokens]
487
488        matcher = SequenceMatcher(
489            None, seq_source_normalized, seq_test_normalized, autojunk=self.autojunk
490        )
491
492        # Merge adjacent edits separated only by punctuation-only equal runs,
493        # so e.g. "thirty (30)" -> "forty (40)" is reported as a single change.
494        opcodes = _merge_ops_split_by_punctuation(
495            matcher.get_opcodes(), seq_source_normalized
496        )
497
498        return [
499            DiffOperation(
500                source_chunk=Chunk(text=source_tokens, chunk_location=None),
501                test_chunk=Chunk(text=test_tokens, chunk_location=None),
502                opcodes=opcode,
503            )
504            for opcode in opcodes
505        ]
506
507
508class NupunktProcessor(RedlinesProcessor):
509    """
510    A redlines processor that uses nupunkt for intelligent sentence boundary detection.
511
512    This processor splits documents into sentences using nupunkt's advanced tokenization,
513    which better handles:
514    - Abbreviations (Dr., Mr., etc.)
515    - Decimals and numbers (3.14, $5.99)
516    - URLs and email addresses
517    - Complex punctuation
518
519    The result is sentence-level granularity in diffs, providing more precise change detection
520    compared to paragraph-level comparison. Paragraph boundaries in the input are preserved:
521    sentences are anchored within their paragraph with an invisible marker, so rendered output
522    keeps the document's real paragraph structure instead of reflowing one sentence per paragraph.
523
524    A cleanup pass merges adjacent edits separated only by punctuation, so a change
525    such as "thirty (30)" -> "forty (40)" is reported as a single replace instead of
526    two separate changes (see `_merge_ops_split_by_punctuation`).
527
528    Note: Requires nupunkt>=0.6.0 (Python 3.11+)
529
530    Example:
531        ```python
532        from redlines import Redlines
533        from redlines.processor import NupunktProcessor
534
535        processor = NupunktProcessor()
536        r = Redlines(source, test, processor=processor)
537        ```
538    """
539
540    def __init__(self, *, autojunk: bool = False) -> None:
541        """
542        :param autojunk: Passed to difflib.SequenceMatcher. Defaults to False because the
543            default heuristic silently degrades diffs of repetitive documents of 200+ tokens
544            (see ADR-0010); set True to restore difflib's default popular-token heuristic,
545            which can be faster on large repetitive documents.
546        :type autojunk: bool
547        """
548        self.autojunk = autojunk
549
550    def process(
551        self, source: Document | str, test: Document | str
552    ) -> list[DiffOperation]:
553        """
554        Compare two documents using sentence-level tokenization.
555
556        Paragraph boundaries are preserved ('¶' markers), and sentence boundaries
557        within each paragraph are anchored with render-invisible '¦' markers.
558
559        :param source: The source document to compare.
560        :type source: Document | str
561        :param test: The test document to compare.
562        :type test: Document | str
563        :return: A list of `DiffOperation` that describe the differences between the two documents.
564        :rtype: list[DiffOperation]
565        :raises ImportError: If nupunkt is not installed.
566        """
567        # Extract text from documents if needed
568        source_text = source.text if isinstance(source, Document) else source
569        test_text = test.text if isinstance(test, Document) else test
570
571        # Tokenize the texts using nupunkt sentence boundaries
572        source_tokens = tokenize_text(
573            concatenate_sentences_and_add_chr_182(source_text)
574        )
575        test_tokens = tokenize_text(concatenate_sentences_and_add_chr_182(test_text))
576
577        # Normalize tokens by stripping whitespace for comparison
578        # This allows the matcher to focus on content differences rather than whitespace variations
579        # while still preserving the original tokens (including whitespace) for display in the output
580        seq_source_normalized = [token.strip() for token in source_tokens]
581        seq_test_normalized = [token.strip() for token in test_tokens]
582
583        matcher = SequenceMatcher(
584            None, seq_source_normalized, seq_test_normalized, autojunk=self.autojunk
585        )
586
587        # Merge adjacent edits separated only by punctuation-only equal runs,
588        # so e.g. "thirty (30)" -> "forty (40)" is reported as a single change.
589        opcodes = _merge_ops_split_by_punctuation(
590            matcher.get_opcodes(), seq_source_normalized
591        )
592
593        return [
594            DiffOperation(
595                source_chunk=Chunk(text=source_tokens, chunk_location=None),
596                test_chunk=Chunk(text=test_tokens, chunk_location=None),
597                opcodes=opcode,
598            )
599            for opcode in opcodes
600        ]