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