1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2009, 2010, 2011, 2013, 2014, 2016 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
25 #include "libpspp/assertion.h"
26 #include "libpspp/hash-functions.h"
27 #include "libpspp/hmap.h"
28 #include "output/render.h"
29 #include "output/tab.h"
30 #include "output/table-item.h"
31 #include "output/table.h"
33 #include "gl/minmax.h"
34 #include "gl/xalloc.h"
37 #define _(msgid) gettext (msgid)
39 /* This file uses TABLE_HORZ and TABLE_VERT enough to warrant abbreviating. */
43 /* A layout for rendering a specific table on a specific device.
45 May represent the layout of an entire table presented to
46 render_page_create(), or a rectangular subregion of a table broken out using
47 render_break_next() to allow a table to be broken across multiple pages.
49 A page's size is not limited to the size passed in as part of render_params.
50 render_pager breaks a render_page into smaller render_pages that will fit in
51 the available space. */
54 const struct render_params *params; /* Parameters of the target device. */
55 struct table *table; /* Table rendered. */
58 /* Local copies of table->n and table->h, for convenience. */
60 int h[TABLE_N_AXES][2];
62 /* cp[H] represents x positions within the table.
64 cp[H][1] = the width of the leftmost vertical rule.
65 cp[H][2] = cp[H][1] + the width of the leftmost column.
66 cp[H][3] = cp[H][2] + the width of the second-from-left vertical rule.
68 cp[H][2 * nc] = x position of the rightmost vertical rule.
69 cp[H][2 * nc + 1] = total table width including all rules.
71 Similarly, cp[V] represents y positions within the table.
73 cp[V][1] = the height of the topmost horizontal rule.
74 cp[V][2] = cp[V][1] + the height of the topmost row.
75 cp[V][3] = cp[V][2] + the height of the second-from-top horizontal rule.
77 cp[V][2 * nr] = y position of the bottommost horizontal rule.
78 cp[V][2 * nr + 1] = total table height including all rules.
80 Rules and columns can have width or height 0, in which case consecutive
81 values in this array are equal. */
82 int *cp[TABLE_N_AXES];
84 /* render_break_next() can break a table such that some cells are not fully
85 contained within a render_page. This will happen if a cell is too wide
86 or two tall to fit on a single page, or if a cell spans multiple rows or
87 columns and the page only includes some of those rows or columns.
89 This hash table contains "struct render_overflow"s that represents each
90 such cell that doesn't completely fit on this page.
92 Each overflow cell borders at least one header edge of the table and may
93 border more. (A single table cell that is so large that it fills the
94 entire page can overflow on all four sides!) */
95 struct hmap overflows;
97 /* Contains "struct render_footnote"s, one for each cell with one or more
100 'n_footnotes' is the number of footnotes in the table. There might be
101 more than hmap_count(&page->footnotes) because there can be more than
102 one footnote in a cell. */
103 struct hmap footnotes;
106 /* If a single column (or row) is too wide (or tall) to fit on a page
107 reasonably, then render_break_next() will split a single row or column
108 across multiple render_pages. This member indicates when this has
111 is_edge_cutoff[H][0] is true if pixels have been cut off the left side
112 of the leftmost column in this page, and false otherwise.
114 is_edge_cutoff[H][1] is true if pixels have been cut off the right side
115 of the rightmost column in this page, and false otherwise.
117 is_edge_cutoff[V][0] and is_edge_cutoff[V][1] are similar for the top
118 and bottom of the table.
120 The effect of is_edge_cutoff is to prevent rules along the edge in
121 question from being rendered.
123 When is_edge_cutoff is true for a given edge, the 'overflows' hmap will
124 contain a node for each cell along that edge. */
125 bool is_edge_cutoff[TABLE_N_AXES][2];
127 /* If part of a joined cell would be cut off by breaking a table along
128 'axis' at the rule with offset 'z' (where 0 <= z <= n[axis]), then
129 join_crossing[axis][z] is the thickness of the rule that would be cut
132 This is used to know to allocate extra space for breaking at such a
133 position, so that part of the cell's content is not lost.
135 This affects breaking a table only when headers are present. When
136 headers are not present, the rule's thickness is used for cell content,
137 so no part of the cell's content is lost (and in fact it is duplicated
138 across both pages). */
139 int *join_crossing[TABLE_N_AXES];
142 static struct render_page *render_page_create (const struct render_params *,
145 struct render_page *render_page_ref (const struct render_page *page_);
146 static void render_page_unref (struct render_page *);
148 /* Returns the offset in struct render_page's cp[axis] array of the rule with
149 index RULE_IDX. That is, if RULE_IDX is 0, then the offset is that of the
150 leftmost or topmost rule; if RULE_IDX is 1, then the offset is that of the
151 next rule to the right (or below); and so on. */
153 rule_ofs (int rule_idx)
158 /* Returns the offset in struct render_page's cp[axis] array of the rule with
159 index RULE_IDX_R, which counts from the right side (or bottom) of the page
160 left (or up), according to whether AXIS is H or V, respectively. That is,
161 if RULE_IDX_R is 0, then the offset is that of the rightmost or bottommost
162 rule; if RULE_IDX is 1, then the offset is that of the next rule to the left
163 (or above); and so on. */
165 rule_ofs_r (const struct render_page *page, int axis, int rule_idx_r)
167 return (page->n[axis] - rule_idx_r) * 2;
170 /* Returns the offset in struct render_page's cp[axis] array of the cell with
171 index CELL_IDX. That is, if CELL_IDX is 0, then the offset is that of the
172 leftmost or topmost cell; if CELL_IDX is 1, then the offset is that of the
173 next cell to the right (or below); and so on. */
175 cell_ofs (int cell_idx)
177 return cell_idx * 2 + 1;
180 /* Returns the width of PAGE along AXIS from OFS0 to OFS1, exclusive. */
182 axis_width (const struct render_page *page, int axis, int ofs0, int ofs1)
184 return page->cp[axis][ofs1] - page->cp[axis][ofs0];
187 /* Returns the width of the headers in PAGE along AXIS. */
189 headers_width (const struct render_page *page, int axis)
191 int h0 = page->h[axis][0];
192 int w0 = axis_width (page, axis, rule_ofs (0), cell_ofs (h0));
193 int n = page->n[axis];
194 int h1 = page->h[axis][1];
195 int w1 = axis_width (page, axis, rule_ofs_r (page, axis, h1), cell_ofs (n));
199 /* Returns the width of cell X along AXIS in PAGE. */
201 cell_width (const struct render_page *page, int axis, int x)
203 return axis_width (page, axis, cell_ofs (x), cell_ofs (x) + 1);
206 /* Returns the width of rule X along AXIS in PAGE. */
208 rule_width (const struct render_page *page, int axis, int x)
210 return axis_width (page, axis, rule_ofs (x), rule_ofs (x) + 1);
213 /* Returns the width of rule X along AXIS in PAGE. */
215 rule_width_r (const struct render_page *page, int axis, int x)
217 int ofs = rule_ofs_r (page, axis, x);
218 return axis_width (page, axis, ofs, ofs + 1);
221 /* Returns the width of cells X0 through X1, exclusive, along AXIS in PAGE. */
223 joined_width (const struct render_page *page, int axis, int x0, int x1)
225 return axis_width (page, axis, cell_ofs (x0), cell_ofs (x1) - 1);
228 /* Returns the width of the widest cell, excluding headers, along AXIS in
231 max_cell_width (const struct render_page *page, int axis)
233 int n = page->n[axis];
234 int x0 = page->h[axis][0];
235 int x1 = n - page->h[axis][1];
239 for (x = x0; x < x1; x++)
241 int w = cell_width (page, axis, x);
248 /* A cell that doesn't completely fit on the render_page. */
249 struct render_overflow
251 struct hmap_node node; /* In render_page's 'overflows' hmap. */
253 /* Occupied region of page.
255 d[H][0] is the leftmost column.
256 d[H][1] is the rightmost column, plus 1.
257 d[V][0] is the top row.
258 d[V][1] is the bottom row, plus 1.
260 The cell in its original table might occupy a larger region. This
261 member reflects the size of the cell in the current render_page, after
262 trimming off any rows or columns due to page-breaking. */
265 /* The space that has been trimmed off the cell:
267 overflow[H][0]: space trimmed off its left side.
268 overflow[H][1]: space trimmed off its right side.
269 overflow[V][0]: space trimmed off its top.
270 overflow[V][1]: space trimmed off its bottom.
272 During rendering, this information is used to position the rendered
273 portion of the cell within the available space.
275 When a cell is rendered, sometimes it is permitted to spill over into
276 space that is ordinarily reserved for rules. Either way, this space is
277 still included in overflow values.
279 Suppose, for example, that a cell that joins 2 columns has a width of 60
280 pixels and content "abcdef", that the 2 columns that it joins have
281 widths of 20 and 30 pixels, respectively, and that therefore the rule
282 between the two joined columns has a width of 10 (20 + 10 + 30 = 60).
283 It might render like this, if each character is 10x10, and showing a few
284 extra table cells for context:
292 If this render_page is broken at the rule that separates "gh" from
293 "ijk", then the page that contains the left side of the "abcdef" cell
294 will have overflow[H][1] of 10 + 30 = 40 for its portion of the cell,
295 and the page that contains the right side of the cell will have
296 overflow[H][0] of 20 + 10 = 30. The two resulting pages would look like
314 int overflow[TABLE_N_AXES][2];
317 /* Returns a hash value for (,Y). */
319 hash_cell (int x, int y)
321 return hash_int (x + (y << 16), 0);
324 /* Searches PAGE's set of render_overflow for one whose top-left cell is
325 (X,Y). Returns it, if there is one, otherwise a null pointer. */
326 static const struct render_overflow *
327 find_overflow (const struct render_page *page, int x, int y)
329 if (!hmap_is_empty (&page->overflows))
331 const struct render_overflow *of;
333 HMAP_FOR_EACH_WITH_HASH (of, struct render_overflow, node,
334 hash_cell (x, y), &page->overflows)
335 if (x == of->d[H] && y == of->d[V])
343 struct render_footnote
345 struct hmap_node node;
347 /* The area of the table covered by the cell that has the footnote.
349 d[H][0] is the leftmost column.
350 d[H][1] is the rightmost column, plus 1.
351 d[V][0] is the top row.
352 d[V][1] is the bottom row, plus 1.
354 The cell in its original table might occupy a larger region. This
355 member reflects the size of the cell in the current render_page, after
356 trimming off any rows or columns due to page-breaking. */
357 int d[TABLE_N_AXES][2];
359 /* The index of the first footnote in the cell. */
364 count_footnotes (const struct table_cell *cell)
370 for (i = 0; i < cell->n_contents; i++)
371 n += cell->contents[i].n_footnotes;
376 find_footnote_idx (const struct table_cell *cell, const struct hmap *footnotes)
378 const struct render_footnote *f;
380 if (!count_footnotes (cell))
383 HMAP_FOR_EACH_WITH_HASH (f, struct render_footnote, node,
384 hash_cell (cell->d[H][0], cell->d[V][0]), footnotes)
385 if (f->d[H][0] == cell->d[H][0] && f->d[V][0] == cell->d[V][0])
391 /* Row or column dimensions. Used to figure the size of a table in
392 render_page_create() and discarded after that. */
395 /* Width without considering rows (or columns) that span more than one (or
399 /* Width taking spanned rows (or columns) into consideration. */
403 /* Modifies the 'width' members of the N elements of ROWS so that their sum,
404 when added to rule widths RULES[1] through RULES[N - 1] inclusive, is at
407 distribute_spanned_width (int width,
408 struct render_row *rows, const int *rules, int n)
410 /* Sum up the unspanned widths of the N rows for use as weights. */
411 int total_unspanned = 0;
412 for (int x = 0; x < n; x++)
413 total_unspanned += rows[x].unspanned;
414 for (int x = 0; x < n - 1; x++)
415 total_unspanned += rules[x + 1];
416 if (total_unspanned >= width)
419 /* The algorithm used here is based on the following description from HTML 4:
421 For cells that span multiple columns, a simple approach consists of
422 apportioning the min/max widths evenly to each of the constituent
423 columns. A slightly more complex approach is to use the min/max
424 widths of unspanned cells to weight how spanned widths are
425 apportioned. Experiments suggest that a blend of the two approaches
426 gives good results for a wide range of tables.
428 We blend the two approaches half-and-half, except that we cannot use the
429 unspanned weights when 'total_unspanned' is 0 (because that would cause a
432 The calculation we want to do is this:
435 w1 = width * (column's unspanned width) / (total unspanned width)
436 (column's width) = (w0 + w1) / 2
438 We implement it as a precise calculation in integers by multiplying w0 and
439 w1 by the common denominator of all three calculations (d), dividing that
440 out in the column width calculation, and then keeping the remainder for
443 (We actually compute the unspanned width of a column as twice the
444 unspanned width, plus the width of the rule on the left, plus the width of
445 the rule on the right. That way each rule contributes to both the cell on
446 its left and on its right.)
448 long long int d0 = n;
449 long long int d1 = 2LL * MAX (total_unspanned, 1);
450 long long int d = d0 * d1;
451 if (total_unspanned > 0)
453 long long int w = d / 2;
454 for (int x = 0; x < n; x++)
457 if (total_unspanned > 0)
459 long long int unspanned = rows[x].unspanned * 2LL;
461 unspanned += rules[x + 1];
463 unspanned += rules[x];
464 w += width * unspanned * d0;
467 rows[x].width = MAX (rows[x].width, w / d);
468 w -= rows[x].width * d;
472 /* Initializes PAGE->cp[AXIS] from the row widths in ROWS and the rule widths
475 accumulate_row_widths (const struct render_page *page, enum table_axis axis,
476 const struct render_row *rows, const int *rules)
478 int n = page->n[axis];
484 for (z = 0; z < n; z++)
486 cp[1] = cp[0] + rules[z];
487 cp[2] = cp[1] + rows[z].width;
490 cp[1] = cp[0] + rules[n];
493 /* Returns the sum of widths of the N ROWS and N+1 RULES. */
495 calculate_table_width (int n, const struct render_row *rows, int *rules)
501 for (x = 0; x < n; x++)
502 width += rows[x].width;
503 for (x = 0; x <= n; x++)
509 /* Rendering utility functions. */
511 /* Returns the line style to use for drawing a rule of the given TYPE. */
512 static enum render_line_style
513 rule_to_render_type (unsigned char type)
518 return RENDER_LINE_NONE;
520 return RENDER_LINE_SINGLE;
522 return RENDER_LINE_DOUBLE;
528 /* Returns the width of the rule in TABLE that is at offset Z along axis A, if
529 rendered with PARAMS. */
531 measure_rule (const struct render_params *params, const struct table *table,
532 enum table_axis a, int z)
534 enum table_axis b = !a;
539 /* Determine all types of rules that are present, as a bitmap in 'rules'
540 where rule type 't' is present if bit 2**t is set. */
543 for (d[b] = 0; d[b] < table->n[b]; d[b]++)
544 rules |= 1u << table_get_rule (table, a, d[H], d[V]);
546 /* Turn off TAL_NONE because it has width 0 and we needn't bother. However,
547 if the device doesn't support margins, make sure that there is at least a
548 small gap between cells (but we don't need any at the left or right edge
550 if (rules & (1u << TAL_0))
552 rules &= ~(1u << TAL_0);
553 if (z > 0 && z < table->n[a] && !params->supports_margins && a == H)
554 rules |= 1u << TAL_1;
557 /* Calculate maximum width of the rules that are present. */
559 if (rules & (1u << TAL_1)
560 || (z > 0 && z < table->n[a] && rules & (1u << TAL_0)))
561 width = params->line_widths[a][RENDER_LINE_SINGLE];
562 if (rules & (1u << TAL_2))
563 width = MAX (width, params->line_widths[a][RENDER_LINE_DOUBLE]);
567 /* Allocates and returns a new render_page using PARAMS and TABLE. Allocates
568 space for all of the members of the new page, but the caller must initialize
569 the 'cp' member itself. */
570 static struct render_page *
571 render_page_allocate (const struct render_params *params,
574 struct render_page *page;
577 page = xmalloc (sizeof *page);
578 page->params = params;
581 page->n[H] = table->n[H];
582 page->n[V] = table->n[V];
583 page->h[H][0] = table->h[H][0];
584 page->h[H][1] = table->h[H][1];
585 page->h[V][0] = table->h[V][0];
586 page->h[V][1] = table->h[V][1];
588 for (i = 0; i < TABLE_N_AXES; i++)
590 page->cp[i] = xmalloc ((2 * page->n[i] + 2) * sizeof *page->cp[i]);
591 page->join_crossing[i] = xzalloc ((page->n[i] + 1) * sizeof *page->join_crossing[i]);
594 hmap_init (&page->overflows);
595 hmap_init (&page->footnotes);
596 page->n_footnotes = 0;
597 memset (page->is_edge_cutoff, 0, sizeof page->is_edge_cutoff);
602 /* Allocates and returns a new render_page for PARAMS and TABLE, initializing
603 cp[H] in the new page from ROWS and RULES. The caller must still initialize
605 static struct render_page *
606 create_page_with_exact_widths (const struct render_params *params,
608 const struct render_row *rows, int *rules)
610 struct render_page *page = render_page_allocate (params, table);
611 accumulate_row_widths (page, H, rows, rules);
615 /* Allocates and returns a new render_page for PARAMS and TABLE.
617 Initializes cp[H] in the new page by setting the width of each row 'i' to
618 somewhere between the minimum cell width ROW_MIN[i].width and the maximum
619 ROW_MAX[i].width. Sets the width of rules to those in RULES.
621 W_MIN is the sum of ROWS_MIN[].width.
623 W_MAX is the sum of ROWS_MAX[].width.
625 The caller must still initialize cp[V]. */
626 static struct render_page *
627 create_page_with_interpolated_widths (const struct render_params *params,
629 const struct render_row *rows_min,
630 const struct render_row *rows_max,
631 int w_min, int w_max, const int *rules)
633 const int n = table->n[H];
634 const long long int avail = params->size[H] - w_min;
635 const long long int wanted = w_max - w_min;
639 struct render_page *page = render_page_allocate (params, table);
641 int *cph = page->cp[H];
643 long long int w = wanted / 2;
644 for (int x = 0; x < n; x++)
646 w += avail * (rows_max[x].width - rows_min[x].width);
647 int extra = w / wanted;
650 cph[1] = cph[0] + rules[x];
651 cph[2] = cph[1] + rows_min[x].width + extra;
654 cph[1] = cph[0] + rules[n];
656 assert (page->cp[H][n * 2 + 1] == params->size[H]);
662 set_join_crossings (struct render_page *page, enum table_axis axis,
663 const struct table_cell *cell, int *rules)
667 for (z = cell->d[axis][0] + 1; z <= cell->d[axis][1] - 1; z++)
668 page->join_crossing[axis][z] = rules[z];
671 /* Creates and returns a new render_page for rendering TABLE on a device
674 The new render_page will be suitable for rendering on a device whose page
675 size is PARAMS->size, but the caller is responsible for actually breaking it
676 up to fit on such a device, using the render_break abstraction. */
677 static struct render_page *
678 render_page_create (const struct render_params *params, struct table *table)
680 struct render_page *page;
682 struct render_row *columns[2];
683 struct render_row *rows;
685 int *rules[TABLE_N_AXES];
686 struct hmap footnotes;
691 enum table_axis axis;
693 nc = table_nc (table);
694 nr = table_nr (table);
696 /* Figure out rule widths. */
697 for (axis = 0; axis < TABLE_N_AXES; axis++)
699 int n = table->n[axis] + 1;
702 rules[axis] = xnmalloc (n, sizeof *rules);
703 for (z = 0; z < n; z++)
704 rules[axis][z] = measure_rule (params, table, axis, z);
707 /* Calculate minimum and maximum widths of cells that do not
708 span multiple columns. Assign footnote markers. */
709 hmap_init (&footnotes);
711 for (i = 0; i < 2; i++)
712 columns[i] = xzalloc (nc * sizeof *columns[i]);
713 for (y = 0; y < nr; y++)
714 for (x = 0; x < nc; )
716 struct table_cell cell;
718 table_get_cell (table, x, y, &cell);
719 if (y == cell.d[V][0])
723 if (table_cell_colspan (&cell) == 1)
728 params->measure_cell_width (params->aux, &cell, footnote_idx,
730 for (i = 0; i < 2; i++)
731 if (columns[i][x].unspanned < w[i])
732 columns[i][x].unspanned = w[i];
735 n = count_footnotes (&cell);
738 struct render_footnote *f = xmalloc (sizeof *f);
739 f->d[H][0] = cell.d[H][0];
740 f->d[H][1] = cell.d[H][1];
741 f->d[V][0] = cell.d[V][0];
742 f->d[V][1] = cell.d[V][1];
743 f->idx = footnote_idx;
744 hmap_insert (&footnotes, &f->node, hash_cell (x, y));
750 table_cell_free (&cell);
753 /* Distribute widths of spanned columns. */
754 for (i = 0; i < 2; i++)
755 for (x = 0; x < nc; x++)
756 columns[i][x].width = columns[i][x].unspanned;
757 for (y = 0; y < nr; y++)
758 for (x = 0; x < nc; )
760 struct table_cell cell;
762 table_get_cell (table, x, y, &cell);
763 if (y == cell.d[V][0] && table_cell_colspan (&cell) > 1)
767 params->measure_cell_width (params->aux, &cell,
768 find_footnote_idx (&cell, &footnotes),
770 for (i = 0; i < 2; i++)
771 distribute_spanned_width (w[i], &columns[i][cell.d[H][0]],
772 rules[H], table_cell_colspan (&cell));
775 table_cell_free (&cell);
778 /* In pathological cases, spans can cause the minimum width of a column to
779 exceed the maximum width. This bollixes our interpolation algorithm
780 later, so fix it up. */
781 for (i = 0; i < nc; i++)
782 if (columns[MIN][i].width > columns[MAX][i].width)
783 columns[MAX][i].width = columns[MIN][i].width;
785 /* Decide final column widths. */
786 for (i = 0; i < 2; i++)
787 table_widths[i] = calculate_table_width (table_nc (table),
788 columns[i], rules[H]);
789 if (table_widths[MAX] <= params->size[H])
791 /* Fits even with maximum widths. Use them. */
792 page = create_page_with_exact_widths (params, table, columns[MAX],
795 else if (table_widths[MIN] <= params->size[H])
797 /* Fits with minimum widths, so distribute the leftover space. */
798 page = create_page_with_interpolated_widths (
799 params, table, columns[MIN], columns[MAX],
800 table_widths[MIN], table_widths[MAX], rules[H]);
804 /* Doesn't fit even with minimum widths. Assign minimums for now, and
805 later we can break it horizontally into multiple pages. */
806 page = create_page_with_exact_widths (params, table, columns[MIN],
810 /* Calculate heights of cells that do not span multiple rows. */
811 rows = xzalloc (nr * sizeof *rows);
812 for (y = 0; y < nr; y++)
814 for (x = 0; x < nc; )
816 struct render_row *r = &rows[y];
817 struct table_cell cell;
819 table_get_cell (table, x, y, &cell);
820 if (y == cell.d[V][0])
822 if (table_cell_rowspan (&cell) == 1)
824 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
825 int h = params->measure_cell_height (
826 params->aux, &cell, find_footnote_idx (&cell, &footnotes), w);
827 if (h > r->unspanned)
828 r->unspanned = r->width = h;
831 set_join_crossings (page, V, &cell, rules[V]);
833 if (table_cell_colspan (&cell) > 1)
834 set_join_crossings (page, H, &cell, rules[H]);
837 table_cell_free (&cell);
840 for (i = 0; i < 2; i++)
843 /* Distribute heights of spanned rows. */
844 for (y = 0; y < nr; y++)
845 for (x = 0; x < nc; )
847 struct table_cell cell;
849 table_get_cell (table, x, y, &cell);
850 if (y == cell.d[V][0] && table_cell_rowspan (&cell) > 1)
852 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
853 int h = params->measure_cell_height (
854 params->aux, &cell, find_footnote_idx (&cell, &footnotes), w);
855 distribute_spanned_width (h, &rows[cell.d[V][0]], rules[V],
856 table_cell_rowspan (&cell));
859 table_cell_free (&cell);
862 /* Decide final row heights. */
863 accumulate_row_widths (page, V, rows, rules[V]);
866 /* Measure headers. If they are "too big", get rid of them. */
867 for (axis = 0; axis < TABLE_N_AXES; axis++)
869 int hw = headers_width (page, axis);
870 if (hw * 2 >= page->params->size[axis]
871 || hw + max_cell_width (page, axis) > page->params->size[axis])
873 page->table = table_unshare (page->table);
874 page->table->h[axis][0] = page->table->h[axis][1] = 0;
875 page->h[axis][0] = page->h[axis][1] = 0;
879 hmap_swap (&page->footnotes, &footnotes);
880 hmap_destroy (&footnotes);
881 page->n_footnotes = footnote_idx;
889 /* Increases PAGE's reference count. */
891 render_page_ref (const struct render_page *page_)
893 struct render_page *page = CONST_CAST (struct render_page *, page_);
898 /* Decreases PAGE's reference count and destroys PAGE if this causes the
899 reference count to fall to zero. */
901 render_page_unref (struct render_page *page)
903 if (page != NULL && --page->ref_cnt == 0)
906 struct render_overflow *overflow, *next;
908 HMAP_FOR_EACH_SAFE (overflow, next, struct render_overflow, node,
911 hmap_destroy (&page->overflows);
913 table_unref (page->table);
915 for (i = 0; i < TABLE_N_AXES; ++i)
917 free (page->join_crossing[i]);
925 /* Returns the size of PAGE along AXIS. (This might be larger than the page
926 size specified in the parameters passed to render_page_create(). Use a
927 render_break to break up a render_page into page-sized chunks.) */
929 render_page_get_size (const struct render_page *page, enum table_axis axis)
931 return page->cp[axis][page->n[axis] * 2 + 1];
935 render_page_get_best_breakpoint (const struct render_page *page, int height)
939 /* If there's no room for at least the top row and the rules above and below
940 it, don't include any of the table. */
941 if (page->cp[V][3] > height)
944 /* Otherwise include as many rows and rules as we can. */
945 for (y = 5; y <= 2 * page->n[V] + 1; y += 2)
946 if (page->cp[V][y] > height)
947 return page->cp[V][y - 2];
951 /* Drawing render_pages. */
953 static inline enum render_line_style
954 get_rule (const struct render_page *page, enum table_axis axis,
955 const int d[TABLE_N_AXES])
957 return rule_to_render_type (table_get_rule (page->table,
958 axis, d[H] / 2, d[V] / 2));
968 render_direction_rtl (void)
970 /* TRANSLATORS: Do not translate this string. If the script of your language
971 reads from right to left (eg Persian, Arabic, Hebrew etc), then replace
972 this string with "output-direction-rtl". Otherwise either leave it
973 untranslated or copy it verbatim. */
974 const char *dir = _("output-direction-ltr");
975 if ( 0 == strcmp ("output-direction-rtl", dir))
978 if ( 0 != strcmp ("output-direction-ltr", dir))
979 fprintf (stderr, "This localisation has been incorrectly translated. Complain to the translator.\n");
985 render_rule (const struct render_page *page, const int ofs[TABLE_N_AXES],
986 const int d[TABLE_N_AXES])
988 enum render_line_style styles[TABLE_N_AXES][2];
991 for (a = 0; a < TABLE_N_AXES; a++)
993 enum table_axis b = !a;
995 styles[a][0] = styles[a][1] = RENDER_LINE_NONE;
998 || (page->is_edge_cutoff[a][0] && d[a] == 0)
999 || (page->is_edge_cutoff[a][1] && d[a] == page->n[a] * 2))
1006 int e[TABLE_N_AXES];
1010 styles[a][0] = get_rule (page, a, e);
1013 if (d[b] / 2 < page->table->n[b])
1014 styles[a][1] = get_rule (page, a, d);
1017 styles[a][0] = styles[a][1] = get_rule (page, a, d);
1020 if (styles[H][0] != RENDER_LINE_NONE || styles[H][1] != RENDER_LINE_NONE
1021 || styles[V][0] != RENDER_LINE_NONE || styles[V][1] != RENDER_LINE_NONE)
1023 int bb[TABLE_N_AXES][2];
1025 bb[H][0] = ofs[H] + page->cp[H][d[H]];
1026 bb[H][1] = ofs[H] + page->cp[H][d[H] + 1];
1027 if (render_direction_rtl ())
1029 int temp = bb[H][0];
1030 bb[H][0] = render_page_get_size (page, H) - bb[H][1];
1031 bb[H][1] = render_page_get_size (page, H) - temp;
1033 bb[V][0] = ofs[V] + page->cp[V][d[V]];
1034 bb[V][1] = ofs[V] + page->cp[V][d[V] + 1];
1035 page->params->draw_line (page->params->aux, bb, styles);
1040 render_cell (const struct render_page *page, const int ofs[TABLE_N_AXES],
1041 const struct table_cell *cell)
1043 const struct render_overflow *of;
1044 int bb[TABLE_N_AXES][2];
1045 int clip[TABLE_N_AXES][2];
1047 bb[H][0] = clip[H][0] = ofs[H] + page->cp[H][cell->d[H][0] * 2 + 1];
1048 bb[H][1] = clip[H][1] = ofs[H] + page->cp[H][cell->d[H][1] * 2];
1049 if (render_direction_rtl ())
1051 int temp = bb[H][0];
1052 bb[H][0] = clip[H][0] = render_page_get_size (page, H) - bb[H][1];
1053 bb[H][1] = clip[H][1] = render_page_get_size (page, H) - temp;
1055 bb[V][0] = clip[V][0] = ofs[V] + page->cp[V][cell->d[V][0] * 2 + 1];
1056 bb[V][1] = clip[V][1] = ofs[V] + page->cp[V][cell->d[V][1] * 2];
1058 of = find_overflow (page, cell->d[H][0], cell->d[V][0]);
1061 enum table_axis axis;
1063 for (axis = 0; axis < TABLE_N_AXES; axis++)
1065 if (of->overflow[axis][0])
1067 bb[axis][0] -= of->overflow[axis][0];
1068 if (cell->d[axis][0] == 0 && !page->is_edge_cutoff[axis][0])
1069 clip[axis][0] = ofs[axis] + page->cp[axis][cell->d[axis][0] * 2];
1071 if (of->overflow[axis][1])
1073 bb[axis][1] += of->overflow[axis][1];
1074 if (cell->d[axis][1] == page->n[axis] && !page->is_edge_cutoff[axis][1])
1075 clip[axis][1] = ofs[axis] + page->cp[axis][cell->d[axis][1] * 2 + 1];
1080 page->params->draw_cell (page->params->aux, cell,
1081 find_footnote_idx (cell, &page->footnotes), bb, clip);
1084 /* Draws the cells of PAGE indicated in BB. */
1086 render_page_draw_cells (const struct render_page *page,
1087 int ofs[TABLE_N_AXES], int bb[TABLE_N_AXES][2])
1091 for (y = bb[V][0]; y < bb[V][1]; y++)
1092 for (x = bb[H][0]; x < bb[H][1]; )
1093 if (is_rule (x) || is_rule (y))
1095 int d[TABLE_N_AXES];
1098 render_rule (page, ofs, d);
1103 struct table_cell cell;
1105 table_get_cell (page->table, x / 2, y / 2, &cell);
1106 if (y / 2 == bb[V][0] / 2 || y / 2 == cell.d[V][0])
1107 render_cell (page, ofs, &cell);
1108 x = rule_ofs (cell.d[H][1]);
1109 table_cell_free (&cell);
1113 /* Renders PAGE, by calling the 'draw_line' and 'draw_cell' functions from the
1114 render_params provided to render_page_create(). */
1116 render_page_draw (const struct render_page *page, int ofs[TABLE_N_AXES])
1118 int bb[TABLE_N_AXES][2];
1121 bb[H][1] = page->n[H] * 2 + 1;
1123 bb[V][1] = page->n[V] * 2 + 1;
1125 render_page_draw_cells (page, ofs, bb);
1128 /* Returns the greatest value i, 0 <= i < n, such that cp[i] <= x0. */
1130 get_clip_min_extent (int x0, const int cp[], int n)
1132 int low, high, best;
1139 int middle = low + (high - low) / 2;
1141 if (cp[middle] <= x0)
1153 /* Returns the least value i, 0 <= i < n, such that cp[i] >= x1. */
1155 get_clip_max_extent (int x1, const int cp[], int n)
1157 int low, high, best;
1164 int middle = low + (high - low) / 2;
1166 if (cp[middle] >= x1)
1167 best = high = middle;
1172 while (best > 0 && cp[best - 1] == cp[best])
1178 /* Renders the cells of PAGE that intersect (X,Y)-(X+W,Y+H), by calling the
1179 'draw_line' and 'draw_cell' functions from the render_params provided to
1180 render_page_create(). */
1182 render_page_draw_region (const struct render_page *page,
1183 int ofs[TABLE_N_AXES], int clip[TABLE_N_AXES][2])
1185 int bb[TABLE_N_AXES][2];
1187 bb[H][0] = get_clip_min_extent (clip[H][0], page->cp[H], page->n[H] * 2 + 1);
1188 bb[H][1] = get_clip_max_extent (clip[H][1], page->cp[H], page->n[H] * 2 + 1);
1189 bb[V][0] = get_clip_min_extent (clip[V][0], page->cp[V], page->n[V] * 2 + 1);
1190 bb[V][1] = get_clip_max_extent (clip[V][1], page->cp[V], page->n[V] * 2 + 1);
1192 render_page_draw_cells (page, ofs, bb);
1195 /* Breaking up tables to fit on a page. */
1197 /* An iterator for breaking render_pages into smaller chunks. */
1200 struct render_page *page; /* Page being broken up. */
1201 enum table_axis axis; /* Axis along which 'page' is being broken. */
1202 int z; /* Next cell along 'axis'. */
1203 int pixel; /* Pixel offset within cell 'z' (usually 0). */
1204 int hw; /* Width of headers of 'page' along 'axis'. */
1207 static int needed_size (const struct render_break *, int cell);
1208 static bool cell_is_breakable (const struct render_break *, int cell);
1209 static struct render_page *render_page_select (const struct render_page *,
1214 /* Initializes render_break B for breaking PAGE along AXIS.
1215 Takes ownership of PAGE. */
1217 render_break_init (struct render_break *b, struct render_page *page,
1218 enum table_axis axis)
1222 b->z = page->h[axis][0];
1224 b->hw = headers_width (page, axis);
1227 /* Initializes B as a render_break structure for which
1228 render_break_has_next() always returns false. */
1230 render_break_init_empty (struct render_break *b)
1233 b->axis = TABLE_HORZ;
1239 /* Frees B and unrefs the render_page that it owns. */
1241 render_break_destroy (struct render_break *b)
1245 render_page_unref (b->page);
1250 /* Returns true if B still has cells that are yet to be returned,
1251 false if all of B's page has been processed. */
1253 render_break_has_next (const struct render_break *b)
1255 const struct render_page *page = b->page;
1256 enum table_axis axis = b->axis;
1258 return page != NULL && b->z < page->n[axis] - page->h[axis][1];
1261 /* Returns a new render_page that is up to SIZE pixels wide along B's axis.
1262 Returns a null pointer if B has already been completely broken up, or if
1263 SIZE is too small to reasonably render any cells. The latter will never
1264 happen if SIZE is at least as large as the page size passed to
1265 render_page_create() along B's axis. */
1266 static struct render_page *
1267 render_break_next (struct render_break *b, int size)
1269 const struct render_page *page = b->page;
1270 enum table_axis axis = b->axis;
1271 struct render_page *subpage;
1274 if (!render_break_has_next (b))
1278 for (z = b->z; z < page->n[axis] - page->h[axis][1]; z++)
1280 int needed = needed_size (b, z + 1);
1283 if (cell_is_breakable (b, z))
1285 /* If there is no right header and we render a partial cell on
1286 the right side of the body, then we omit the rightmost rule of
1287 the body. Otherwise the rendering is deceptive because it
1288 looks like the whole cell is present instead of a partial
1291 This is similar to code for the left side in needed_size(). */
1292 int rule_allowance = (page->h[axis][1]
1294 : rule_width (page, axis, z));
1296 /* The amount that, if we added cell 'z', the rendering would
1297 overfill the allocated 'size'. */
1298 int overhang = needed - size - rule_allowance;
1300 /* The width of cell 'z'. */
1301 int cell_size = cell_width (page, axis, z);
1303 /* The amount trimmed off the left side of 'z',
1304 and the amount left to render. */
1305 int cell_ofs = z == b->z ? b->pixel : 0;
1306 int cell_left = cell_size - cell_ofs;
1308 /* A small but visible width. */
1309 int em = page->params->font_size[axis];
1311 /* If some of the cell remains to render,
1312 and there would still be some of the cell left afterward,
1313 then partially render that much of the cell. */
1314 pixel = (cell_left && cell_left > overhang
1315 ? cell_left - overhang + cell_ofs
1318 /* If there would be only a tiny amount of the cell left after
1319 rendering it partially, reduce the amount rendered slightly
1320 to make the output look a little better. */
1321 if (pixel + em > cell_size)
1322 pixel = MAX (pixel - em, 0);
1324 /* If we're breaking vertically, then consider whether the cells
1325 being broken have a better internal breakpoint than the exact
1326 number of pixels available, which might look bad e.g. because
1327 it breaks in the middle of a line of text. */
1328 if (axis == TABLE_VERT && page->params->adjust_break)
1332 for (x = 0; x < page->n[H]; )
1334 struct table_cell cell;
1338 table_get_cell (page->table, x, z, &cell);
1339 w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
1340 better_pixel = page->params->adjust_break (
1341 page->params->aux, &cell,
1342 find_footnote_idx (&cell, &page->footnotes), w, pixel);
1344 table_cell_free (&cell);
1346 if (better_pixel < pixel)
1348 if (better_pixel > (z == b->z ? b->pixel : 0))
1350 pixel = better_pixel;
1353 else if (better_pixel == 0 && z != b->z)
1366 if (z == b->z && !pixel)
1369 subpage = render_page_select (page, axis, b->z, b->pixel,
1371 pixel ? cell_width (page, axis, z) - pixel
1378 /* Returns the width that would be required along B's axis to render a page
1379 from B's current position up to but not including CELL. */
1381 needed_size (const struct render_break *b, int cell)
1383 const struct render_page *page = b->page;
1384 enum table_axis axis = b->axis;
1387 /* Width of left header not including its rightmost rule. */
1388 size = axis_width (page, axis, 0, rule_ofs (page->h[axis][0]));
1390 /* If we have a pixel offset and there is no left header, then we omit the
1391 leftmost rule of the body. Otherwise the rendering is deceptive because
1392 it looks like the whole cell is present instead of a partial cell.
1394 Otherwise (if there are headers) we will be merging two rules: the
1395 rightmost rule in the header and the leftmost rule in the body. We assume
1396 that the width of a merged rule is the larger of the widths of either rule
1398 if (b->pixel == 0 || page->h[axis][0])
1399 size += MAX (rule_width (page, axis, page->h[axis][0]),
1400 rule_width (page, axis, b->z));
1402 /* Width of body, minus any pixel offset in the leftmost cell. */
1403 size += joined_width (page, axis, b->z, cell) - b->pixel;
1405 /* Width of rightmost rule in body merged with leftmost rule in headers. */
1406 size += MAX (rule_width_r (page, axis, page->h[axis][1]),
1407 rule_width (page, axis, cell));
1409 /* Width of right header not including its leftmost rule. */
1410 size += axis_width (page, axis, rule_ofs_r (page, axis, page->h[axis][1]),
1411 rule_ofs_r (page, axis, 0));
1413 /* Join crossing. */
1414 if (page->h[axis][0] && page->h[axis][1])
1415 size += page->join_crossing[axis][b->z];
1420 /* Returns true if CELL along B's axis may be broken across a page boundary.
1422 This is just a heuristic. Breaking cells across page boundaries can save
1423 space, but it looks ugly. */
1425 cell_is_breakable (const struct render_break *b, int cell)
1427 const struct render_page *page = b->page;
1428 enum table_axis axis = b->axis;
1430 return cell_width (page, axis, cell) >= page->params->min_break[axis];
1437 const struct render_params *params;
1439 struct render_page **pages;
1440 size_t n_pages, allocated_pages;
1443 struct render_break x_break;
1444 struct render_break y_break;
1447 static const struct render_page *
1448 render_pager_add_table (struct render_pager *p, struct table *table)
1450 struct render_page *page;
1452 if (p->n_pages >= p->allocated_pages)
1453 p->pages = x2nrealloc (p->pages, &p->allocated_pages, sizeof *p->pages);
1454 page = p->pages[p->n_pages++] = render_page_create (p->params, table);
1459 render_pager_start_page (struct render_pager *p)
1461 render_break_init (&p->x_break, render_page_ref (p->pages[p->cur_page++]),
1463 render_break_init_empty (&p->y_break);
1467 add_footnote_page (struct render_pager *p, const struct render_page *body)
1469 const struct table *table = body->table;
1470 int nc = table_nc (table);
1471 int nr = table_nr (table);
1472 int footnote_idx = 0;
1473 struct tab_table *t;
1476 if (!body->n_footnotes)
1479 t = tab_create (2, body->n_footnotes);
1480 for (y = 0; y < nr; y++)
1481 for (x = 0; x < nc; )
1483 struct table_cell cell;
1485 table_get_cell (table, x, y, &cell);
1486 if (y == cell.d[V][0])
1490 for (i = 0; i < cell.n_contents; i++)
1492 const struct cell_contents *cc = &cell.contents[i];
1495 for (j = 0; j < cc->n_footnotes; j++)
1497 const char *f = cc->footnotes[j];
1499 tab_text (t, 0, footnote_idx, TAB_LEFT, "");
1500 tab_footnote (t, 0, footnote_idx, "(none)");
1501 tab_text (t, 1, footnote_idx, TAB_LEFT, f);
1507 table_cell_free (&cell);
1509 render_pager_add_table (p, &t->table);
1512 /* Creates and returns a new render_pager for rendering TABLE_ITEM on the
1513 device with the given PARAMS. */
1514 struct render_pager *
1515 render_pager_create (const struct render_params *params,
1516 const struct table_item *table_item)
1518 const char *caption = table_item_get_caption (table_item);
1519 const char *title = table_item_get_title (table_item);
1520 const struct render_page *body_page;
1521 struct render_pager *p;
1523 p = xzalloc (sizeof *p);
1528 render_pager_add_table (p, table_from_string (TAB_LEFT, title));
1531 body_page = render_pager_add_table (p, table_ref (table_item_get_table (
1536 render_pager_add_table (p, table_from_string (TAB_LEFT, caption));
1539 add_footnote_page (p, body_page);
1541 render_pager_start_page (p);
1548 render_pager_destroy (struct render_pager *p)
1554 render_break_destroy (&p->x_break);
1555 render_break_destroy (&p->y_break);
1556 for (i = 0; i < p->n_pages; i++)
1557 render_page_unref (p->pages[i]);
1563 /* Returns true if P has content remaining to render, false if rendering is
1566 render_pager_has_next (const struct render_pager *p_)
1568 struct render_pager *p = CONST_CAST (struct render_pager *, p_);
1570 while (!render_break_has_next (&p->y_break))
1572 render_break_destroy (&p->y_break);
1573 if (!render_break_has_next (&p->x_break))
1575 render_break_destroy (&p->x_break);
1576 if (p->cur_page >= p->n_pages)
1578 render_break_init_empty (&p->x_break);
1579 render_break_init_empty (&p->y_break);
1582 render_pager_start_page (p);
1585 render_break_init (&p->y_break,
1586 render_break_next (&p->x_break, p->params->size[H]), V);
1591 /* Draws a chunk of content from P to fit in a space that has vertical size
1592 SPACE and the horizontal size specified in the render_params passed to
1593 render_page_create(). Returns the amount of space actually used by the
1594 rendered chunk, which will be 0 if SPACE is too small to render anything or
1595 if no content remains (use render_pager_has_next() to distinguish these
1598 render_pager_draw_next (struct render_pager *p, int space)
1600 int ofs[TABLE_N_AXES] = { 0, 0 };
1601 size_t start_page = SIZE_MAX;
1603 while (render_pager_has_next (p))
1605 struct render_page *page;
1607 if (start_page == p->cur_page)
1609 start_page = p->cur_page;
1611 page = render_break_next (&p->y_break, space - ofs[V]);
1615 render_page_draw (page, ofs);
1616 ofs[V] += render_page_get_size (page, V);
1617 render_page_unref (page);
1622 /* Draws all of P's content. */
1624 render_pager_draw (const struct render_pager *p)
1626 render_pager_draw_region (p, 0, 0, INT_MAX, INT_MAX);
1629 /* Draws the region of P's content that lies in the region (X,Y)-(X+W,Y+H).
1630 Some extra content might be drawn; the device should perform clipping as
1633 render_pager_draw_region (const struct render_pager *p,
1634 int x, int y, int w, int h)
1636 int ofs[TABLE_N_AXES] = { 0, 0 };
1637 int clip[TABLE_N_AXES][2];
1642 for (i = 0; i < p->n_pages; i++)
1644 const struct render_page *page = p->pages[i];
1645 int size = render_page_get_size (page, V);
1647 clip[V][0] = MAX (y, ofs[V]) - ofs[V];
1648 clip[V][1] = MIN (y + h, ofs[V] + size) - ofs[V];
1649 if (clip[V][1] > clip[V][0])
1650 render_page_draw_region (page, ofs, clip);
1656 /* Returns the size of P's content along AXIS; i.e. the content's width if AXIS
1657 is TABLE_HORZ and its length if AXIS is TABLE_VERT. */
1659 render_pager_get_size (const struct render_pager *p, enum table_axis axis)
1664 for (i = 0; i < p->n_pages; i++)
1666 int subsize = render_page_get_size (p->pages[i], axis);
1667 size = axis == H ? MAX (size, subsize) : size + subsize;
1674 render_pager_get_best_breakpoint (const struct render_pager *p, int height)
1679 for (i = 0; i < p->n_pages; i++)
1681 int size = render_page_get_size (p->pages[i], V);
1682 if (y + size >= height)
1683 return render_page_get_best_breakpoint (p->pages[i], height - y) + y;
1690 /* render_page_select() and helpers. */
1692 struct render_page_selection
1694 const struct render_page *page; /* Page whose slice we are selecting. */
1695 struct render_page *subpage; /* New page under construction. */
1696 enum table_axis a; /* Axis of 'page' along which 'subpage' is a slice. */
1697 enum table_axis b; /* The opposite of 'a'. */
1698 int z0; /* First cell along 'a' being selected. */
1699 int z1; /* Last cell being selected, plus 1. */
1700 int p0; /* Number of pixels to trim off left side of z0. */
1701 int p1; /* Number of pixels to trim off right side of z1-1. */
1704 static void cell_to_subpage (struct render_page_selection *,
1705 const struct table_cell *,
1706 int subcell[TABLE_N_AXES]);
1707 static const struct render_overflow *find_overflow_for_cell (
1708 struct render_page_selection *, const struct table_cell *);
1709 static struct render_overflow *insert_overflow (struct render_page_selection *,
1710 const struct table_cell *);
1712 /* Creates and returns a new render_page whose contents are a subregion of
1713 PAGE's contents. The new render_page includes cells Z0 through Z1
1714 (exclusive) along AXIS, plus any headers on AXIS.
1716 If P0 is nonzero, then it is a number of pixels to exclude from the left or
1717 top (according to AXIS) of cell Z0. Similarly, P1 is a number of pixels to
1718 exclude from the right or bottom of cell Z1 - 1. (P0 and P1 are used to
1719 render cells that are too large to fit on a single page.)
1721 The whole of axis !AXIS is included. (The caller may follow up with another
1722 call to render_page_select() to select on !AXIS to select on that axis as
1725 The caller retains ownership of PAGE, which is not modified. */
1726 static struct render_page *
1727 render_page_select (const struct render_page *page, enum table_axis axis,
1728 int z0, int p0, int z1, int p1)
1730 const struct render_footnote *f;
1731 struct render_page_selection s;
1732 enum table_axis a = axis;
1733 enum table_axis b = !a;
1734 struct render_page *subpage;
1735 struct render_overflow *ro;
1741 /* Optimize case where all of PAGE is selected by just incrementing the
1743 if (z0 == page->h[a][0] && p0 == 0
1744 && z1 == page->n[a] - page->h[a][1] && p1 == 0)
1746 struct render_page *page_rw = CONST_CAST (struct render_page *, page);
1751 /* Allocate subpage. */
1752 subpage = render_page_allocate (page->params,
1753 table_select_slice (
1754 table_ref (page->table),
1757 /* An edge is cut off if it was cut off in PAGE or if we're trimming pixels
1758 off that side of the page and there are no headers. */
1759 subpage->is_edge_cutoff[a][0] =
1760 subpage->h[a][0] == 0 && (p0 || (z0 == 0 && page->is_edge_cutoff[a][0]));
1761 subpage->is_edge_cutoff[a][1] =
1762 subpage->h[a][1] == 0 && (p1 || (z1 == page->n[a]
1763 && page->is_edge_cutoff[a][1]));
1764 subpage->is_edge_cutoff[b][0] = page->is_edge_cutoff[b][0];
1765 subpage->is_edge_cutoff[b][1] = page->is_edge_cutoff[b][1];
1767 /* Select join crossings from PAGE into subpage. */
1768 jc = subpage->join_crossing[a];
1769 for (z = 0; z < page->h[a][0]; z++)
1770 *jc++ = page->join_crossing[a][z];
1771 for (z = z0; z <= z1; z++)
1772 *jc++ = page->join_crossing[a][z];
1773 for (z = page->n[a] - page->h[a][1]; z < page->n[a]; z++)
1774 *jc++ = page->join_crossing[a][z];
1775 assert (jc == &subpage->join_crossing[a][subpage->n[a] + 1]);
1777 memcpy (subpage->join_crossing[b], page->join_crossing[b],
1778 (subpage->n[b] + 1) * sizeof **subpage->join_crossing);
1780 /* Select widths from PAGE into subpage. */
1782 dcp = subpage->cp[a];
1784 for (z = 0; z <= rule_ofs (subpage->h[a][0]); z++, dcp++)
1786 if (z == 0 && subpage->is_edge_cutoff[a][0])
1789 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1791 for (z = cell_ofs (z0); z <= cell_ofs (z1 - 1); z++, dcp++)
1793 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1794 if (z == cell_ofs (z0))
1797 if (page->h[a][0] && page->h[a][1])
1798 dcp[1] += page->join_crossing[a][z / 2];
1800 if (z == cell_ofs (z1 - 1))
1803 for (z = rule_ofs_r (page, a, subpage->h[a][1]);
1804 z <= rule_ofs_r (page, a, 0); z++, dcp++)
1806 if (z == rule_ofs_r (page, a, 0) && subpage->is_edge_cutoff[a][1])
1809 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1811 assert (dcp == &subpage->cp[a][2 * subpage->n[a] + 1]);
1813 for (z = 0; z < page->n[b] * 2 + 2; z++)
1814 subpage->cp[b][z] = page->cp[b][z];
1816 /* Add new overflows. */
1824 s.subpage = subpage;
1826 if (!page->h[a][0] || z0 > page->h[a][0] || p0)
1827 for (z = 0; z < page->n[b]; )
1829 struct table_cell cell;
1830 int d[TABLE_N_AXES];
1837 table_get_cell (page->table, d[H], d[V], &cell);
1838 overflow0 = p0 || cell.d[a][0] < z0;
1839 overflow1 = cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1);
1840 if (overflow0 || overflow1)
1842 ro = insert_overflow (&s, &cell);
1846 ro->overflow[a][0] += p0 + axis_width (
1847 page, a, cell_ofs (cell.d[a][0]), cell_ofs (z0));
1848 if (page->h[a][0] && page->h[a][1])
1849 ro->overflow[a][0] -= page->join_crossing[a][cell.d[a][0]
1855 ro->overflow[a][1] += p1 + axis_width (
1856 page, a, cell_ofs (z1), cell_ofs (cell.d[a][1]));
1857 if (page->h[a][0] && page->h[a][1])
1858 ro->overflow[a][1] -= page->join_crossing[a][cell.d[a][1]];
1862 table_cell_free (&cell);
1865 if (!page->h[a][1] || z1 < page->n[a] - page->h[a][1] || p1)
1866 for (z = 0; z < page->n[b]; )
1868 struct table_cell cell;
1869 int d[TABLE_N_AXES];
1873 table_get_cell (page->table, d[H], d[V], &cell);
1874 if ((cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1))
1875 && find_overflow_for_cell (&s, &cell) == NULL)
1877 ro = insert_overflow (&s, &cell);
1878 ro->overflow[a][1] += p1 + axis_width (page, a, cell_ofs (z1),
1879 cell_ofs (cell.d[a][1]));
1882 table_cell_free (&cell);
1885 /* Copy overflows from PAGE into subpage. */
1886 HMAP_FOR_EACH (ro, struct render_overflow, node, &page->overflows)
1888 struct table_cell cell;
1890 table_get_cell (page->table, ro->d[H], ro->d[V], &cell);
1891 if (cell.d[a][1] > z0 && cell.d[a][0] < z1
1892 && find_overflow_for_cell (&s, &cell) == NULL)
1893 insert_overflow (&s, &cell);
1894 table_cell_free (&cell);
1897 /* Copy footnotes from PAGE into subpage. */
1898 HMAP_FOR_EACH (f, struct render_footnote, node, &page->footnotes)
1899 if ((f->d[a][0] >= z0 && f->d[a][0] < z1)
1900 || (f->d[a][1] - 1 >= z0 && f->d[a][1] - 1 < z1))
1902 struct render_footnote *nf = xmalloc (sizeof *nf);
1903 nf->d[a][0] = MAX (z0, f->d[a][0]) - z0 + page->h[a][0];
1904 nf->d[a][1] = MIN (z1, f->d[a][1]) - z0 + page->h[a][0];
1905 nf->d[b][0] = f->d[b][0];
1906 nf->d[b][1] = f->d[b][1];
1908 hmap_insert (&subpage->footnotes, &nf->node,
1909 hash_cell (nf->d[H][0], nf->d[V][0]));
1915 /* Given CELL, a table_cell within S->page, stores in SUBCELL the (x,y)
1916 coordinates of the top-left cell as it will appear in S->subpage.
1918 CELL must actually intersect the region of S->page that is being selected
1919 by render_page_select() or the results will not make any sense. */
1921 cell_to_subpage (struct render_page_selection *s,
1922 const struct table_cell *cell, int subcell[TABLE_N_AXES])
1924 enum table_axis a = s->a;
1925 enum table_axis b = s->b;
1926 int ha0 = s->subpage->h[a][0];
1928 subcell[a] = MAX (cell->d[a][0] - s->z0 + ha0, ha0);
1929 subcell[b] = cell->d[b][0];
1932 /* Given CELL, a table_cell within S->page, returns the render_overflow for
1933 that cell in S->subpage, if there is one, and a null pointer otherwise.
1935 CELL must actually intersect the region of S->page that is being selected
1936 by render_page_select() or the results will not make any sense. */
1937 static const struct render_overflow *
1938 find_overflow_for_cell (struct render_page_selection *s,
1939 const struct table_cell *cell)
1943 cell_to_subpage (s, cell, subcell);
1944 return find_overflow (s->subpage, subcell[H], subcell[V]);
1947 /* Given CELL, a table_cell within S->page, inserts a render_overflow for that
1948 cell in S->subpage (which must not already exist). Initializes the new
1949 render_overflow's 'overflow' member from the overflow for CELL in S->page,
1952 CELL must actually intersect the region of S->page that is being selected
1953 by render_page_select() or the results will not make any sense. */
1954 static struct render_overflow *
1955 insert_overflow (struct render_page_selection *s,
1956 const struct table_cell *cell)
1958 const struct render_overflow *old;
1959 struct render_overflow *of;
1961 of = xzalloc (sizeof *of);
1962 cell_to_subpage (s, cell, of->d);
1963 hmap_insert (&s->subpage->overflows, &of->node,
1964 hash_cell (of->d[H], of->d[V]));
1966 old = find_overflow (s->page, cell->d[H][0], cell->d[V][0]);
1968 memcpy (of->overflow, old->overflow, sizeof of->overflow);