Repository: freelawproject/x-ray (language: python)

Issue:
Characters need to intersect with the bbox more than some threshold
There are a lot of redactions that look like this:

![Screenshot from 2021-09-11 11-17-10](https://user-images.githubusercontent.com/236970/132957411-dd2406f4-1202-43b6-ab41-e7d6f61c5953.png)

In this case, the redaction is just barely covering up the line above and so the line above is showing up as redacted. Alas, just checking for an intersection isn't enough. We need to have some threshold above which an intersection is relevant. Too bad.


Discussion / hints:

Fix patch:
diff --git a/.github/workflows/lint.yml b/.github/workflows/lint.yml
index b320807..bb6308d 100644
--- a/.github/workflows/lint.yml
+++ b/.github/workflows/lint.yml
@@ -59,46 +59,3 @@ jobs:
           --line-length=79
           --transform-concats
           --fail-on-change
-
-  lint-report:
-    runs-on: ubuntu-latest
-    steps:
-      - uses: actions/checkout@v2-beta
-      - uses: actions/setup-python@v2
-        with:
-          python-version: "3.8"
-
-      - name: Install Poetry
-        uses: snok/install-poetry@v1.1.0
-        with:
-          virtualenvs-create: true
-          virtualenvs-in-project: true
-
-      - name: Load cached venv
-        id: cached-poetry-dependencies
-        uses: actions/cache@v2
-        with:
-          path: .venv
-          key: venv-${{ runner.os }}-${{ hashFiles('**/poetry.lock') }}
-
-      - name: Install dependencies
-        run: poetry install
-        if: steps.cached-poetry-dependencies.outputs.cache-hit != 'true'
-
-      - name: Activate venv
-        run: |
-          echo "VIRTUAL_ENV=$GITHUB_WORKSPACE/.venv" >> $GITHUB_ENV
-          echo "PYTHONPATH=$GITHUB_WORKSPACE" >> $GITHUB_ENV
-          echo "$GITHUB_WORKSPACE/.venv/bin" >> $GITHUB_PATH
-
-      - name: pylint Generate Report
-        run: |
-          pip install pylint-json2html
-          pylint --load-plugins=pylint_json2html -f jsonextended xray > pylint-report.json
-          pylint-json2html -f jsonextended -o pylint-report.html pylint-report.json
-
-      - name: Upload report
-        uses: actions/upload-artifact@v2
-        with:
-          name: pylint report
-          path: pylint-report.html
diff --git a/.gitignore b/.gitignore
index 76b0d95..2f56d83 100644
--- a/.gitignore
+++ b/.gitignore
@@ -161,4 +161,4 @@ dmypy.json
 
 # Pyre type checker
 .pyre/
-/.idea/workspace.xml
+/.idea/
diff --git a/mypy.ini b/mypy.ini
new file mode 100644
index 0000000..976ba02
--- /dev/null
+++ b/mypy.ini
@@ -0,0 +1,2 @@
+[mypy]
+ignore_missing_imports = True
diff --git a/pyproject.toml b/pyproject.toml
index c982440..1933ccb 100644
--- a/pyproject.toml
+++ b/pyproject.toml
@@ -28,7 +28,7 @@ version = "0.0.1"
 "Organisation Homepage" = "https://free.law/"
 
 [tool.poetry.dependencies]
-python = "^3.7"
+python = "^3.8"
 PyMuPDF = "^1.18.17"
 
 [tool.poetry.dev-dependencies]
diff --git a/xray/__init__.py b/xray/__init__.py
index e69de29..f43bc1e 100644
--- a/xray/__init__.py
+++ b/xray/__init__.py
@@ -0,0 +1,30 @@
+"""
+Find bad redactions.
+"""
+
+from pathlib import Path
+from typing import Union
+
+import fitz
+
+from .custom_types import PdfRedactionsDict
+from .pdf_utils import get_bad_redactions
+
+
+def inspect(file_path: Union[str, Path]) -> PdfRedactionsDict:
+    """
+    Inspect a file for bad redactions and return a Dict with their info
+
+    :file_path: The PDF to process
+    :return: A dict with the bad redaction information. If no bad redactions
+    are found, returns an empty dict.
+    """
+    pdf = fitz.open(file_path)
+    bad_redactions = {}
+    for page_number, page in enumerate(pdf, start=1):
+        redactions = get_bad_redactions(page)
+        if redactions:
+            bad_redactions[page_number] = redactions
+    pdf.close()
+
+    return bad_redactions
diff --git a/xray/custom_types.py b/xray/custom_types.py
new file mode 100644
index 0000000..e0e2a83
--- /dev/null
+++ b/xray/custom_types.py
@@ -0,0 +1,22 @@
+"""Custom types for MyPy"""
+
+from typing import Dict, List, Tuple, TypedDict
+
+
+class RedactionType(TypedDict):
+    """A type for a redaction"""
+
+    bbox: Tuple[float, ...]
+    text: str
+
+
+# The type used for the top-level dictionary of all redactions for a document
+PdfRedactionsDict = Dict[int, List[RedactionType]]
+
+
+class CharDictType(TypedDict):
+    """A type for a character dictionary"""
+
+    origin: Tuple[float, float]
+    bbox: Tuple[float, float, float, float]
+    c: str
diff --git a/xray/pdf_utils.py b/xray/pdf_utils.py
new file mode 100644
index 0000000..d642978
--- /dev/null
+++ b/xray/pdf_utils.py
@@ -0,0 +1,244 @@
+"""
+Utilities for working with PDFs and redactions
+"""
+import re
+import typing
+from itertools import chain
+from typing import List, Tuple
+
+import fitz
+from fitz import Page, Rect
+
+from .custom_types import CharDictType, RedactionType
+from .text_utils import is_ok_words, is_repeated_chars
+
+
+def get_good_rectangles(page: Page) -> List[Rect]:
+    """Find rectangles in the PDFs that might be redactions.
+
+    :param page: The PyMuPDF Page to look for rectangles within.
+    :returns A list of PyMUPDF.Rect objects for each black rectangle that's
+    big enough to be a possible redaction. If none, returns an empty list.
+    """
+    drawings = page.get_drawings()
+    good_rectangles = []
+    for drawing in drawings:
+        if drawing.get("rect") is None:
+            # Not a rectangle (ok, ok, tetrahedron, technically)
+            continue
+        if drawing["fill"] != (0.0,):
+            # Not black
+            continue
+
+        rectangle = drawing["rect"]
+
+        if rectangle.y1 <= 43:
+            # It's a header, ignore it
+            continue
+
+        if all(
+            [
+                # Eliminate horizontal lines
+                rectangle.height > 4,
+                # Eliminate vertical bars? Unsure what this is supposed to
+                # prevent?
+                rectangle.width > 4,
+            ]
+        ):
+            good_rectangles.append(rectangle)
+    return good_rectangles
+
+
+def intersects(
+    bbox: Tuple[float, ...],
+    rectangles: List[Rect],
+    occlusion_threshold: float = 0.0,
+) -> bool:
+    """Determine if a bbox intersects with any of a list of rectangles
+
+    :param bbox: A four-tuple of floats denoting a bounding box of a rectangle.
+    The first two floats represent the upper left corner, and the second two
+    are the bottom right. Note that the Y-axis is reversed so it starts at the
+    top of the page, not the bottom left.
+    :param rectangles: A list of PyMuPDF.Rect objects
+    :param occlusion_threshold: How much the bbox must be occluded by at least
+    one of the rectangles for it to be considered an intersection, as a
+    percentage. E.g., 1.0 means that the bbox must be fully occluded, 0.10
+    means it must be 10% occluded. The default, 0.0, means they must intersect
+    at least a little.
+    :return True if any part of the bbox intersects with any of the rectangles,
+    else False.
+    """
+    overlapping_areas = []
+    for rect in rectangles:
+        # The overlapping area of two rectangles is defined by the product of
+        # the length of their vertical and horizontal intersections.
+        # See: https://stackoverflow.com/a/52194761/64911, in particular the
+        # image that shows the bolded horizontal and vertical lines that get
+        # multiplied.
+        #
+        # As a formula, this takes the form of:
+        #
+        #   A = max(0, min(r0, r1) - max(l0, l1)) *   # horizontal intersection
+        #         max(0, min(b0, b1) - max(t0, t1))   # vertical intersection
+        bbox_left, bbox_top, bbox_right, bbox_bottom = (
+            bbox[0],
+            bbox[1],
+            bbox[2],
+            bbox[3],
+        )
+        rect_left, rect_top, rect_right, rect_bottom = (
+            rect.x0,
+            rect.y0,
+            rect.x1,
+            rect.y1,
+        )
+        vertical_intersection = max(
+            0.0, min(bbox_bottom, rect_bottom) - max(bbox_top, rect_top)
+        )
+        horizontal_intersection = max(
+            0.0, min(bbox_right, rect_right) - max(bbox_left, rect_left)
+        )
+        overlapping_area = horizontal_intersection * vertical_intersection
+        overlapping_areas.append(overlapping_area)
+
+    greatest_occluded = max(overlapping_areas)
+    area_of_bbox = Rect(*bbox).get_area()
+
+    percent_occluded = greatest_occluded / area_of_bbox
+    if percent_occluded > occlusion_threshold:
+        return True
+    return False
+
+
+def get_intersecting_chars(
+    page: Page, rectangles: List[Rect]
+) -> List[CharDictType]:
+    """Get the chars that are occluded by the rectangles
+
+    PDF pages in PyMuPDF are broken up into blocks of text, those blocks
+    contain lines, the lines contain spans, and the spans contain characters.
+    Due to all this, what we do here is start with the biggest object, then
+    drill down and filter iteratively until we have just the chars we want.
+
+    We start with the block objects and check if any of them intersect with the
+    rectangles. If so, we continue with those. Then we do the same for lines,
+    then spans, then characters. The idea here is that we avoid looking for
+    intersections in every danged character, by eliminating blocks that don't
+    intersect, then lines that don't, then spans that don't, then chars that
+    don't.
+
+    Along the way, we do a couple extra filters, like looking for black text,
+    etc.
+
+    :param page: The PyMuPDF.Page object to inspect
+    :param rectangles: A list of PyMuPDF.Rect objects from the page (aka the
+    redactions).
+    :return A list of characters that are under the rectangles
+    """
+    if len(rectangles) == 0:
+        return []
+
+    blocks = page.get_text(
+        "rawdict",
+        flags=fitz.TEXT_PRESERVE_LIGATURES
+        | fitz.TEXT_PRESERVE_WHITESPACE
+        | fitz.TEXT_DEHYPHENATE,
+    )["blocks"]
+
+    # Filter blocks with lines that intersect
+    good_blocks = filter(lambda block: "lines" in block, blocks)
+    intersecting_blocks = filter(
+        lambda block: intersects(block["bbox"], rectangles),
+        good_blocks,
+    )
+
+    # Filter to intersecting lines
+    lines = chain(*[block["lines"] for block in intersecting_blocks])
+    intersecting_lines = filter(
+        lambda line: intersects(line["bbox"], rectangles),
+        lines,
+    )
+
+    # Filter to intersecting spans that are black
+    spans = chain(*[line["spans"] for line in intersecting_lines])
+    good_spans = filter(lambda span: span["color"] == 0, spans)
+    intersecting_spans = filter(
+        lambda span: intersects(span["bbox"], rectangles),
+        good_spans,
+    )
+
+    # Get a flat list of intersecting chars
+    chars = chain(*[span["chars"] for span in intersecting_spans])
+    intersecting_chars = filter(
+        lambda char: intersects(
+            char["bbox"], rectangles, occlusion_threshold=0.8
+        ),
+        chars,
+    )
+    return list(intersecting_chars)
+
+
+def group_chars_by_rect(
+    chars: List[CharDictType],
+    rectangles: List[Rect],
+) -> List[RedactionType]:
+    """Take the chars that intersected with rectangles, and the rectangles they
+    intersected with and group the chars back into words along with the bboxes
+    of the rectangles they intersected with.
+
+    :param chars: The list of character dicts that intersect with rectangles in
+    the PDF.
+    :param rectangles: A list of PyMuPDF.Rect objects from the page (aka the
+    redactions).
+    :return: A list of dictionaries with keys for the rectangle's BBOX and the
+    words underneath it.
+    """
+    redactions = []
+    for rect in rectangles:
+        redaction: RedactionType = {
+            "bbox": (rect.x0, rect.y0, rect.x1, rect.y1),
+            "text": "",
+        }
+        for char in chars:
+            if Rect(*char["bbox"]) & rect:
+                redaction["text"] += char["c"]
+        redactions.append(redaction)
+
+    return redactions
+
+
+@typing.no_type_check  # It gets confused w/filters
+def filter_redactions(redactions: List[RedactionType]) -> List[RedactionType]:
+    """Filter out redactions that are not actually bad.
+
+    :param redactions: A list of redactions that might be bad
+    :return: A (hopefully) smaller list of redactions
+    """
+    # Isn't just repeated text like XXXX
+    redactions = filter(lambda r: not is_repeated_chars(r["text"]), redactions)
+
+    # Has non-whitespace content and isn't blank
+    redactions = filter(lambda r: r["text"].strip(), redactions)
+
+    # Has some letters or numbers
+    redactions = filter(lambda r: re.search(r"[\d\w]", r["text"]), redactions)
+
+    # Has OK words in redaction
+    redactions = filter(lambda r: is_ok_words(r["text"]), redactions)
+
+    return list(redactions)
+
+
+def get_bad_redactions(page: Page) -> List[RedactionType]:
+    """Get the bad redactions for a page from a PDF
+
+    :param: page: The PyMuPDF.Page from a PDF
+    :returns: A list of char objects that are under the rectangles. Each is a
+    dict that has an origin, bbox, and a character.
+    """
+    good_rectangles = get_good_rectangles(page)
+    intersecting_chars = get_intersecting_chars(page, good_rectangles)
+    redactions = group_chars_by_rect(intersecting_chars, good_rectangles)
+    bad_redactions = filter_redactions(redactions)
+    return bad_redactions
diff --git a/xray/py.typed b/xray/py.typed
new file mode 100644
index 0000000..e69de29
diff --git a/xray/text_utils.py b/xray/text_utils.py
new file mode 100644
index 0000000..33f75f5
--- /dev/null
+++ b/xray/text_utils.py
@@ -0,0 +1,38 @@
+"""Tools for working with text strings"""
+import re
+
+
+def is_repeated_chars(text: str) -> bool:
+    """Find repeated characters in a redaction.
+
+    This often indicates something like XXXXXXXX under the redaction or a bunch
+    of space, etc.
+
+    :param text: A string to check
+    :returns: True if only repeated characters, else False
+    """
+    if len(text) <= 1:
+        return False
+
+    if len(set(text)) == 1:
+        # There's only one unique character in the string
+        return True
+
+    return False
+
+
+def is_ok_words(text: str) -> bool:
+    """Check if the redaction is one of several words that are OK
+
+    :param text: A string to check
+    :returns: True if it's an OK word, else False
+    """
+    text = " ".join(text.strip().split())
+    text = re.sub(
+        r"confidential|name +redacted|privileged?|re|red|reda|redac|redact|"
+        r"redacte|redacted|redacted +and +publicly +filed|",
+        "",
+        text,
+        flags=re.IGNORECASE | re.MULTILINE,
+    )
+    return len(text) > 0


Test patch:
diff --git a/.github/workflows/tests.yml b/.github/workflows/tests.yml
index 924ca22..1d18ca7 100644
--- a/.github/workflows/tests.yml
+++ b/.github/workflows/tests.yml
@@ -7,7 +7,7 @@ jobs:
     runs-on: ubuntu-latest
     strategy:
       matrix:
-        python-version: [3.6, 3.7, 3.8, 3.9]
+        python-version: [3.8, 3.9]
 
     steps:
       - uses: actions/checkout@v2
diff --git a/tests/assets/no_bad_redactions.pdf b/tests/assets/no_bad_redactions.pdf
new file mode 100644
index 0000000..c641d7d
Binary files /dev/null and b/tests/assets/no_bad_redactions.pdf differ
diff --git a/tests/assets/ok_words.pdf b/tests/assets/ok_words.pdf
new file mode 100644
index 0000000..7129330
Binary files /dev/null and b/tests/assets/ok_words.pdf differ
diff --git a/tests/assets/partial_intersections_ok.pdf b/tests/assets/partial_intersections_ok.pdf
new file mode 100644
index 0000000..5f2a272
Binary files /dev/null and b/tests/assets/partial_intersections_ok.pdf differ
diff --git a/tests/assets/rectangles_no.pdf b/tests/assets/rectangles_no.pdf
new file mode 100644
index 0000000..eb507b6
Binary files /dev/null and b/tests/assets/rectangles_no.pdf differ
diff --git a/tests/assets/rectangles_yes.pdf b/tests/assets/rectangles_yes.pdf
new file mode 100644
index 0000000..f28a6bc
Binary files /dev/null and b/tests/assets/rectangles_yes.pdf differ
diff --git a/tests/assets/rectangles_yes_2.pdf b/tests/assets/rectangles_yes_2.pdf
new file mode 100644
index 0000000..6a32e8c
Binary files /dev/null and b/tests/assets/rectangles_yes_2.pdf differ
diff --git a/tests/assets/whitespace_redaction_with_comma.pdf b/tests/assets/whitespace_redaction_with_comma.pdf
new file mode 100644
index 0000000..5056d24
Binary files /dev/null and b/tests/assets/whitespace_redaction_with_comma.pdf differ
diff --git a/tests/assets/whitespace_redactions.pdf b/tests/assets/whitespace_redactions.pdf
new file mode 100644
index 0000000..b9dad4c
Binary files /dev/null and b/tests/assets/whitespace_redactions.pdf differ
diff --git a/tests/assets/whitespace_redactions_2.pdf b/tests/assets/whitespace_redactions_2.pdf
new file mode 100644
index 0000000..abf9dd7
Binary files /dev/null and b/tests/assets/whitespace_redactions_2.pdf differ
diff --git a/tests/test_something.py b/tests/test_something.py
deleted file mode 100644
index 06ebd0a..0000000
--- a/tests/test_something.py
+++ /dev/null
@@ -1,16 +0,0 @@
-from unittest import TestCase
-
-
-class DataTest(TestCase):
-    """Obey the testing goat."""
-
-    def test_something(self):
-        """
-        A testing template -- make to update tests.yml if you change the
-        testing name.
-        """
-
-        matches = True
-        expected_matches = True
-
-        self.assertEqual(matches, expected_matches)
diff --git a/tests/test_utils.py b/tests/test_utils.py
new file mode 100644
index 0000000..41546a4
--- /dev/null
+++ b/tests/test_utils.py
@@ -0,0 +1,154 @@
+"""
+X-Ray Tests
+"""
+import os
+from pathlib import Path
+from unittest import TestCase
+
+import fitz
+from fitz import Rect
+
+import xray
+from xray.pdf_utils import (
+    get_bad_redactions,
+    get_good_rectangles,
+    get_intersecting_chars,
+    intersects,
+)
+
+root_path = Path(__file__).resolve().parent / "assets"
+
+
+class RectTest(TestCase):
+    """Do our rectangle-finding utilities work properly?"""
+
+    def test_pymupdf_works_with_path_or_str(self):
+        path_str = "rectangles_yes.pdf"
+        paths = (
+            root_path / path_str,
+            os.path.join(str(root_path), path_str),
+        )
+        for path in paths:
+            with fitz.open(path) as pdf:
+                page = pdf[0]
+                self.assertTrue(get_good_rectangles(page))
+
+    def test_we_find_rectangles_when_we_should(self):
+        paths = (
+            root_path / "rectangles_yes.pdf",
+            root_path / "rectangles_yes_2.pdf",
+        )
+        for path in paths:
+            with fitz.open(path) as pdf:
+                page = pdf[0]
+                self.assertTrue(get_good_rectangles(page))
+
+    def test_we_do_not_find_rectangles_when_we_should_not(self):
+        path = root_path / "rectangles_no.pdf"
+        with fitz.open(path) as pdf:
+            page = pdf[0]
+            self.assertFalse(get_good_rectangles(page))
+
+
+class IntersectionTest(TestCase):
+    """Do rectangles intersect properly?"""
+
+    bbox = (1, 1, 2, 2)
+
+    def test_in_one_of_many(self):
+        """Does a bbox inside of one, but not all rectangles intersect?"""
+        self.assertTrue(
+            intersects(
+                self.bbox,
+                [Rect(0.5, 0.5, 3, 3), Rect(3, 3, 4, 4)],
+            )
+        )
+
+    def test_not_in_any(self):
+        """Do we return False when things don't intersect?"""
+        self.assertFalse(
+            intersects(
+                self.bbox,
+                [Rect(3, 3, 4, 4), Rect(4, 4, 5, 5)],
+            )
+        )
+
+    def test_in_all(self):
+        """Do we return True when the bbox is in all the rects?"""
+        self.assertTrue(
+            intersects(
+                self.bbox,
+                [Rect(0.5, 0.5, 3, 3), Rect(0.6, 0.6, 4, 4)],
+            )
+        )
+
+    def test_partial_intersection(self):
+        """Do we return true when only corners intersect?"""
+        self.assertTrue(intersects(self.bbox, [Rect(0.5, 0.5, 1.5, 1.5)]))
+
+
+class OcclusionTest(TestCase):
+    """Can we get a list of bad redactions?"""
+
+    def test_finding_bad_redactions(self):
+        path = root_path / "rectangles_yes.pdf"
+        with fitz.open(path) as pdf:
+            page = pdf[0]
+            chars = get_intersecting_chars(page, get_good_rectangles(page))
+        self.assertEqual(len(chars), 64)
+
+    def test_ignoring_partial_occlusions(self):
+        path = root_path / "partial_intersections_ok.pdf"
+        with fitz.open(path) as pdf:
+            page = pdf[0]
+            chars = get_intersecting_chars(page, get_good_rectangles(page))
+        self.assertEqual(len(chars), 0)
+
+
+class IntegrationTest(TestCase):
+    """Do our highest-level APIs work?"""
+
+    path = root_path / "rectangles_yes.pdf"
+
+    def test_bad_redactions_on_single_page(self):
+        with fitz.open(self.path) as pdf:
+            page = pdf[0]
+            bad_redactions = get_bad_redactions(page)
+        self.assertEqual(len(bad_redactions), 3)
+
+    def test_finding_bad_redactions_in_a_file(self):
+        redactions = xray.inspect(self.path)
+        self.assertTrue(len(redactions[1]) == 3)
+
+    def test_empty_pages_no_results(self):
+        path = root_path / "no_bad_redactions.pdf"
+        redactions = xray.inspect(path)
+        self.assertEqual(
+            redactions,
+            {},
+            msg="Didn't get empty dict when there were no redactions.",
+        )
+
+    def test_whitespace_only_redaction_no_results(self):
+        paths = (
+            "whitespace_redactions.pdf",
+            "whitespace_redactions_2.pdf",
+            "whitespace_redaction_with_comma.pdf",
+        )
+        for path in paths:
+            redactions = xray.inspect(root_path / path)
+            self.assertEqual(
+                redactions,
+                {},
+                msg="Didn't get empty dict when encountering exclusively "
+                "whitespace-filled redactions.",
+            )
+
+    def test_ok_words_not_redacted(self):
+        path = root_path / "ok_words.pdf"
+        redactions = xray.inspect(path)
+        self.assertEqual(
+            redactions,
+            {},
+            msg="Got redaction even though none in document",
+        )