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