File size: 23,067 Bytes
2523bef
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
"""
Copyright (C) 2023 Artifex Software, Inc.

This file is part of PyMuPDF.

PyMuPDF is free software: you can redistribute it and/or modify it under the
terms of the GNU Affero General Public License as published by the Free
Software Foundation, either version 3 of the License, or (at your option)
any later version.

PyMuPDF is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
details.

You should have received a copy of the GNU Affero General Public License
along with MuPDF. If not, see <https://www.gnu.org/licenses/agpl-3.0.en.html>

Alternative licensing terms are available from the licensor.
For commercial licensing, see <https://www.artifex.com/> or contact
Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
CA 94129, USA, for further information.

---------------------------------------------------------------------

PyMuPDF table cell-span resolution (opt-in extension).

Provides SpanCell and resolve_spans (plus the _span_* helpers), which
reconstruct a detected table's merged-cell (colspan / rowspan) structure.
Re-exported by pymupdf.table; never runs on the default find_tables() path.
Reuses the word-selection helpers of pymupdf._table_refine.
"""

import pymupdf

from pymupdf._table_refine import (
    _refine_is_vertical_or_rotated,
    _refine_page_words,
)


class SpanCell:
    """One reconstructed table cell after span resolution (PyMuPDF extension).

    ``bbox`` is the placement's ``(x0, y0, x1, y1)`` union rect, ``text`` the
    page text it claims (lines joined by ``\\n``), and ``colspan``/``rowspan``
    how many grid columns/rows it covers. resolve_spans always sets a real bbox;
    a caller padding its own grid may construct SpanCells with ``bbox=None``.

    ``tag`` is the cell's HTML tag (``"td"``/``"th"``), defaulting to ``"td"``.
    resolve_spans leaves it at the default; find_tables(refine=True) overwrites
    it from the resolved header region so Table.to_html() can serialize the grid
    directly, and a caller building its own grid may set it too."""

    def __init__(self, bbox, text, colspan, rowspan, tag="td"):
        self.bbox = bbox
        self.text = text
        self.colspan = colspan
        self.rowspan = rowspan
        self.tag = tag


# --- slot geometry: cluster cell edges into column/row boundaries ------------
def _span_clustered_boundaries(values, *, tolerance=3.0):
    """Greedy 1-D clustering of edge coordinates into slot boundaries.

    Keeps a sorted value only when it is more than ``tolerance`` from the last
    kept boundary, so the first value of each run is the retained boundary."""
    boundaries = []
    for value in sorted(values):
        if boundaries and value - boundaries[-1] <= tolerance:
            continue
        boundaries.append(float(value))
    return boundaries


def _span_covered_slot_count(start, end, boundaries, *, tolerance=1.0):
    """How many [boundaries[i], boundaries[i+1]] slots the span start..end covers."""
    count = 0
    for index in range(len(boundaries) - 1):
        midpoint = (boundaries[index] + boundaries[index + 1]) / 2.0
        if start - tolerance <= midpoint <= end + tolerance:
            count += 1
    return max(1, count)


def _span_slot_range(rect, x_boundaries, *, tolerance=1.0):
    """The half-open column-slot range (first, last+1) a rect's x-extent covers."""
    hits = []
    for index in range(len(x_boundaries) - 1):
        midpoint = (x_boundaries[index] + x_boundaries[index + 1]) / 2.0
        if rect.x0 - tolerance <= midpoint <= rect.x1 + tolerance:
            hits.append(index)
    if not hits:
        return (0, 1)
    return (min(hits), max(hits) + 1)


def _span_ranges_intersect(a, b):
    return a[0] < b[1] and b[0] < a[1]


def _span_point_in_rect(x, y, rect):
    return float(rect.x0) <= x <= float(rect.x1) and float(rect.y0) <= y <= float(rect.y1)


def _span_rect_union(rects):
    return pymupdf.Rect(
        min(rect.x0 for rect in rects),
        min(rect.y0 for rect in rects),
        max(rect.x1 for rect in rects),
        max(rect.y1 for rect in rects),
    )


def _span_x_overlap(a, b):
    return min(a.x1, b.x1) - max(a.x0, b.x0)


def _span_substantial_x_overlap(span_rect, cell_rect):
    """True if a text span overlaps a cell by enough x to signal a merge.

    A few points of overlap is noise (a span drifting across a column line with
    trailing whitespace or a currency glyph); require >2pt and >=15% of the cell
    width before treating it as a merged-cell signal."""
    overlap = _span_x_overlap(span_rect, cell_rect)
    if overlap <= 2.0:
        return False
    cell_width = max(1.0, cell_rect.width)
    return overlap / cell_width >= 0.15


def _span_contiguous_ranges(indices):
    """Collapse a sorted index list into (start, end) inclusive runs."""
    if not indices:
        return []
    ranges = []
    start = end = indices[0]
    for index in indices[1:]:
        if index == end + 1:
            end = index
            continue
        ranges.append((start, end))
        start = end = index
    ranges.append((start, end))
    return ranges


def _span_merge_intervals(intervals):
    """Merge overlapping (start, end, text) intervals, accumulating their texts."""
    merged = []
    for start, end, text in sorted(intervals, key=lambda item: (item[0], item[1])):
        if start == end:
            continue
        if not merged or start > merged[-1][1]:
            merged.append((start, end, [text]))
            continue
        prev_start, prev_end, texts = merged[-1]
        merged[-1] = (prev_start, max(prev_end, end), texts + [text])
    return merged


# --- cell text: page words + vertical-text lines claimed by a placement -------
def _span_line_text(line):
    """Space-joined non-empty span texts of a get_text('dict') line."""
    parts = [
        str(span.get("text") or "").strip()
        for span in line.get("spans", [])
        if str(span.get("text") or "").strip()
    ]
    return " ".join(parts)


def _span_line_rect(line):
    """Bounding rect of a dict line (its bbox, else the union of its span bboxes)."""
    bbox = line.get("bbox")
    if bbox:
        rect = pymupdf.Rect(bbox)
        if not rect.is_empty:
            return rect
    rects = [
        pymupdf.Rect(span.get("bbox") or [])
        for span in line.get("spans", [])
        if span.get("bbox")
    ]
    rects = [rect for rect in rects if not rect.is_empty]
    if not rects:
        return None
    return _span_rect_union(rects)


def _span_vertical_text_lines(page):
    """Vertical/rotated text lines as (rect, text), cached on the page.

    Selects non-horizontal lines whose reading order get_text('dict') already
    preserves."""
    cached = getattr(page, "_span_vertical_lines_cache", None)
    if cached is not None:
        return cached
    lines = []
    for block in page.get_text("dict").get("blocks", []):
        if block.get("type") not in (None, 0):
            continue
        for line in block.get("lines", []):
            if not _refine_is_vertical_or_rotated(line):
                continue
            text = _span_line_text(line)
            if not text:
                continue
            rect = _span_line_rect(line)
            if rect is None:
                continue
            lines.append((rect, text))
    try:
        setattr(page, "_span_vertical_lines_cache", lines)
    except Exception:
        pass
    return lines


def _span_vertical_text_for_rect(page, rect, selected_words):
    """Text of vertical lines centered in rect, when they dominate the rect.

    Returns the stacked line text only if vertical lines are centered in the rect,
    cover >=60% of the rect's selected words, and carry >=2 tokens; else None so
    the caller falls back to horizontal line synthesis."""
    if not selected_words:
        return None
    candidates = []
    for line_rect, text in _span_vertical_text_lines(page):
        cx = (float(line_rect.x0) + float(line_rect.x1)) * 0.5
        cy = (float(line_rect.y0) + float(line_rect.y1)) * 0.5
        if _span_point_in_rect(cx, cy, rect):
            candidates.append((line_rect, text))
    if not candidates:
        return None
    vertical_hits = 0
    for _, (wx0, wy0, wx1, wy1, _) in selected_words:
        cx = (wx0 + wx1) * 0.5
        cy = (wy0 + wy1) * 0.5
        if any(_span_point_in_rect(cx, cy, line_rect) for line_rect, _ in candidates):
            vertical_hits += 1
    if vertical_hits / max(1, len(selected_words)) < 0.6:
        return None
    if sum(len(text.split()) for _, text in candidates) < 2:
        return None
    return "\n".join(
        text
        for _, text in sorted(
            candidates,
            key=lambda item: (float(item[0].x0), -float((item[0].y0 + item[0].y1) * 0.5)),
        )
    )


def _span_words_to_line_text(words):
    """Join center-point-selected cell words into text, re-synthesizing lines.

    ``words`` are (y0, x0, y1, text) tuples; they are grouped into lines by an
    adaptive median-height nearest-line rule, each line's words ordered by x, and
    the lines joined by newlines."""
    if not words:
        return ""
    heights = [max(0.1, y1 - y0) for y0, _, y1, _ in words]
    median_height = sorted(heights)[len(heights) // 2]
    line_threshold = max(2.0, median_height * 0.55)
    lines = []
    for y0, x0, y1, text in sorted(words, key=lambda item: (item[0], item[1])):
        cy = (y0 + y1) / 2.0
        best_line = None
        best_distance = line_threshold
        for line in lines:
            distance = abs(cy - float(line["center_y"]))
            if distance <= best_distance:
                best_line = line
                best_distance = distance
        if best_line is None:
            lines.append({"center_y": cy, "words": [(x0, text)]})
            continue
        best_line["words"].append((x0, text))
        count = len(best_line["words"])
        best_line["center_y"] = (float(best_line["center_y"]) * (count - 1) + cy) / count
    text_lines = []
    for line in sorted(lines, key=lambda item: float(item["center_y"])):
        text_lines.append(" ".join(text for _, text in sorted(line["words"], key=lambda item: item[0])))
    return "\n".join(text_lines)


def _span_word_line_tuple(word):
    """Reorder a (x0, y0, x1, y1, text) word to the (y0, x0, y1, text) line tuple."""
    x0, y0, _x1, y1, text = word
    return (float(y0), float(x0), float(y1), str(text))


def _span_select_words_in_rect(page_words, rect):
    """(index, word) pairs whose center lies in rect, index into ``page_words``.

    The index is what lets resolve_spans claim each page word for exactly one
    placement (an earlier cell's word is not re-claimed by a later one)."""
    selected = []
    for index, word in enumerate(page_words):
        wx0, wy0, wx1, wy1, text = word
        if not str(text).strip():
            continue
        cx = (wx0 + wx1) * 0.5
        cy = (wy0 + wy1) * 0.5
        if _span_point_in_rect(cx, cy, rect):
            selected.append((index, word))
    return selected


def _span_words_text_for_rect(page, rect, selected_words):
    """Text for a rect: vertical-line text if it dominates, else line synthesis."""
    vertical_text = _span_vertical_text_for_rect(page, rect, selected_words)
    if vertical_text is not None:
        return vertical_text
    return _span_words_to_line_text([_span_word_line_tuple(word) for _, word in selected_words])


def _span_claim_text_in_rect(page, rect, page_words, claimed_words):
    """Text of rect's words, skipping words already claimed and claiming the rest."""
    selected = [
        (index, word)
        for index, word in _span_select_words_in_rect(page_words, rect)
        if index not in claimed_words
    ]
    for index, _ in selected:
        claimed_words.add(index)
    return _span_words_text_for_rect(page, rect, selected)


def _span_text_spans(page):
    """Page text spans as (rect, text), length>=2, cached on the page.

    These drive merged-cell detection: a single span whose x-extent crosses a
    grid column line signals cells the line grid split but text joins."""
    cached = getattr(page, "_span_text_spans_cache", None)
    if cached is not None:
        return cached
    spans = []
    for block in page.get_text("dict").get("blocks", []):
        for line in block.get("lines", []):
            for span in line.get("spans", []):
                text = str(span.get("text") or "").strip()
                if len(text) < 2:
                    continue
                bbox = span.get("bbox")
                if not bbox:
                    continue
                rect = pymupdf.Rect(bbox)
                if rect.is_empty:
                    continue
                spans.append((rect, text))
    try:
        setattr(page, "_span_text_spans_cache", spans)
    except Exception:
        pass
    return spans


def _span_crossing_intervals(entries, text_spans):
    """Column ranges within one grid row that a single text span crosses.

    ``entries`` are the row's cell rects (in column order). A text span centered
    in the row band and substantially overlapping >=2 adjacent cells marks those
    cells for merging; overlapping intervals are merged. Returns
    (start, end, texts) with end>start."""
    if len(entries) < 2:
        return []
    row_y0 = min(entry.y0 for entry in entries)
    row_y1 = max(entry.y1 for entry in entries)
    intervals = []
    for span_rect, span_text in text_spans:
        center_y = (span_rect.y0 + span_rect.y1) / 2.0
        if center_y < row_y0 - 1.0 or center_y > row_y1 + 1.0:
            continue
        hit_positions = [
            position
            for position, entry in enumerate(entries)
            if _span_substantial_x_overlap(span_rect, entry)
        ]
        if len(hit_positions) < 2:
            continue
        for start, end in _span_contiguous_ranges(hit_positions):
            if end > start:
                intervals.append((start, end, span_text))
    return _span_merge_intervals(intervals)


# --- strict-colspan gate: reject a merge that fights the header/body split ----
# When strict_colspan is set, a header cell may only merge across columns if the
# body rows below actually split there (and vice-versa for a body cell against a
# leaf header). This keeps a stray text span from collapsing a real column.
def _span_is_leaf_header_range(row_idx, cols, base, body_start):
    if row_idx >= body_start:
        return False
    for other in base:
        if other["role"] not in {"header", "header_leaf", "header_group"}:
            continue
        if other["row"] <= row_idx or other["row"] >= body_start:
            continue
        if _span_ranges_intersect(cols, other["cols"]):
            return False
    return True


def _span_build_base_cells(cells, x_boundaries, body_start):
    """Describe every grid cell by row/slot-range/role for the strict-colspan gate.

    Header cells split into ``header_leaf`` (no header cell below within body) vs
    ``header_group`` (spans over a lower leaf), which the reject rules compare
    against the body split."""
    base = []
    for row_idx, row in enumerate(cells):
        for position, cell in enumerate([cell for cell in row if cell is not None]):
            rect = pymupdf.Rect(cell)
            cols = _span_slot_range(rect, x_boundaries)
            base.append(
                {
                    "row": row_idx,
                    "position": position,
                    "rect": rect,
                    "cols": cols,
                    "colspan": cols[1] - cols[0],
                    "role": "body" if row_idx >= body_start else "header",
                }
            )
    for item in base:
        if item["role"] != "header":
            continue
        item["role"] = (
            "header_leaf"
            if _span_is_leaf_header_range(item["row"], item["cols"], base, body_start)
            else "header_group"
        )
    return base


def _span_body_rows_split_under(cols, base, body_start):
    """True if some body row splits the column range ``cols`` into >1 cell."""
    body_rows = sorted({item["row"] for item in base if item["role"] == "body" and item["row"] >= body_start})
    for row_idx in body_rows:
        hits = [
            item
            for item in base
            if item["role"] == "body" and item["row"] == row_idx and _span_ranges_intersect(cols, item["cols"])
        ]
        if not hits:
            continue
        if len(hits) == 1 and hits[0]["cols"] == cols:
            continue
        covered_start = min(max(cols[0], item["cols"][0]) for item in hits)
        covered_end = max(min(cols[1], item["cols"][1]) for item in hits)
        if covered_start <= cols[0] and covered_end >= cols[1]:
            return True
    return False


def _span_header_leafs_split_over(cols, base):
    """True if leaf-header cells split the column range ``cols`` into >1 cell."""
    hits = [item for item in base if item["role"] == "header_leaf" and _span_ranges_intersect(cols, item["cols"])]
    if not hits:
        return False
    if len(hits) == 1 and hits[0]["cols"] == cols:
        return False
    covered_start = min(max(cols[0], item["cols"][0]) for item in hits)
    covered_end = max(min(cols[1], item["cols"][1]) for item in hits)
    return covered_start <= cols[0] and covered_end >= cols[1]


def _span_reject_colspan_mismatch_merge(*, row_idx, cols, base, body_start):
    """Whether to reject a candidate merge over ``cols`` as a (reason,) mismatch."""
    if cols[1] - cols[0] <= 1:
        return False, ""
    if row_idx < body_start:
        if not _span_is_leaf_header_range(row_idx, cols, base, body_start):
            return False, ""
        if _span_body_rows_split_under(cols, base, body_start):
            return True, "header_leaf_colspan_changed_against_body_split"
        return False, ""
    if _span_header_leafs_split_over(cols, base):
        return True, "body_colspan_changed_against_header_leaf_split"
    return False, ""


def _span_cell_texts_for_entries(page, entries, start, end, page_words):
    texts = []
    for entry in entries[start : end + 1]:
        words = _span_select_words_in_rect(page_words, entry)
        texts.append(_span_words_text_for_rect(page, entry, words))
    return texts


def _span_allow_header_colspan_merge_with_empty_part(*, reason, page, entries, start, end, page_words):
    """Allow an otherwise-rejected header merge when a covered part is empty.

    A header leaf that would be rejected against a body split is still merged if
    one of the merged parts has no text (an empty header slot the body fills)."""
    if reason != "header_leaf_colspan_changed_against_body_split":
        return False
    part_texts = [text.strip() for text in _span_cell_texts_for_entries(page, entries, start, end, page_words)]
    return not all(part_texts)


def resolve_spans(page, cells, *, header_row_count=None, strict_colspan=False):
    """Resolve a detected table's merged-cell (colspan/rowspan) structure.

    ``cells`` is a row-major grid: a list of rows, each a list of ``[x0, y0, x1,
    y1]`` cell rectangles (``None`` for a gap) -- the same grid shape
    :func:`refine_grid` accepts. Returns a row-major grid of :class:`SpanCell`
    placements, ragged where cells span: each placement carries its union
    ``bbox``, the page ``text`` it claims, and its ``colspan``/``rowspan`` (how
    many clustered column/row slots it covers). Every page word is claimed by at
    most one placement.

    ``header_row_count`` is the number of leading header rows (default a
    conservative 1); it only matters together with ``strict_colspan``.
    ``strict_colspan`` (default False), when set, refuses a merge whose colspan
    would contradict the header/body column split. This is a PyMuPDF extension;
    it reads page text/graphics but does not mutate the page.
    """
    rows = len(cells)

    x_edges = []
    y_edges = []
    for row in cells:
        for cell in row:
            if cell is None:
                continue
            rect = pymupdf.Rect(cell)
            x_edges.extend([rect.x0, rect.x1])
            y_edges.extend([rect.y0, rect.y1])

    x_boundaries = _span_clustered_boundaries(x_edges)
    y_boundaries = _span_clustered_boundaries(y_edges)
    body_start = max(1, min(int(header_row_count or 1), rows)) if rows else 0
    base_cells = _span_build_base_cells(cells, x_boundaries, body_start) if strict_colspan else []

    text_spans = _span_text_spans(page)
    page_words = _refine_page_words(page)
    claimed_words = set()
    placements = []
    for row_idx, row in enumerate(cells):
        placement_row = []
        entries = [pymupdf.Rect(cell) for cell in row if cell is not None]
        intervals = _span_crossing_intervals(entries, text_spans)
        intervals_by_start = {start: (end, texts) for start, end, texts in intervals}
        position = 0
        while position < len(entries):
            interval = intervals_by_start.get(position)
            if interval is not None:
                end_position, _crossing_texts = interval
                rect = _span_rect_union(entries[position : end_position + 1])
                if strict_colspan:
                    candidate_cols = _span_slot_range(rect, x_boundaries)
                    reject, reason = _span_reject_colspan_mismatch_merge(
                        row_idx=row_idx,
                        cols=candidate_cols,
                        base=base_cells,
                        body_start=body_start,
                    )
                    if reject and _span_allow_header_colspan_merge_with_empty_part(
                        reason=reason,
                        page=page,
                        entries=entries,
                        start=position,
                        end=end_position,
                        page_words=page_words,
                    ):
                        reject = False
                    if reject:
                        rect = entries[position]
                        position += 1
                    else:
                        position = end_position + 1
                else:
                    position = end_position + 1
            else:
                rect = entries[position]
                position += 1

            if rect.is_empty:
                continue
            colspan = _span_covered_slot_count(rect.x0, rect.x1, x_boundaries)
            rowspan = _span_covered_slot_count(rect.y0, rect.y1, y_boundaries)
            placement_row.append(
                SpanCell(
                    bbox=tuple(rect),
                    text=_span_claim_text_in_rect(page, rect, page_words, claimed_words),
                    colspan=colspan,
                    rowspan=rowspan,
                )
            )
        placements.append(placement_row)

    return placements