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 "libpspp/pool.h"
29 #include "output/render.h"
30 #include "output/tab.h"
31 #include "output/table-item.h"
32 #include "output/table.h"
34 #include "gl/minmax.h"
35 #include "gl/xalloc.h"
38 #define _(msgid) gettext (msgid)
40 /* This file uses TABLE_HORZ and TABLE_VERT enough to warrant abbreviating. */
44 /* A layout for rendering a specific table on a specific device.
46 May represent the layout of an entire table presented to
47 render_page_create(), or a rectangular subregion of a table broken out using
48 render_break_next() to allow a table to be broken across multiple pages.
50 A page's size is not limited to the size passed in as part of render_params.
51 render_pager breaks a render_page into smaller render_pages that will fit in
52 the available space. */
55 const struct render_params *params; /* Parameters of the target device. */
56 struct table *table; /* Table rendered. */
59 /* Region of 'table' to render.
61 The horizontal cells rendered are the leftmost h[H][0], then
62 r[H][0] through r[H][1], exclusive, then the rightmost h[H][1].
64 The vertical cells rendered are the topmost h[V][0], then r[V][0]
65 through r[V][1], exclusive, then the bottommost h[V][1].
67 n[H] = h[H][0] + (r[H][1] - r[H][0]) + h[H][1]
68 n[V] = h[V][0] + (r[V][1] - r[V][0]) + h[V][1]
70 int h[TABLE_N_AXES][2];
71 int r[TABLE_N_AXES][2];
76 cp[H] represents x positions within the table.
78 cp[H][1] = the width of the leftmost vertical rule.
79 cp[H][2] = cp[H][1] + the width of the leftmost column.
80 cp[H][3] = cp[H][2] + the width of the second-from-left vertical rule.
82 cp[H][2 * nc] = x position of the rightmost vertical rule.
83 cp[H][2 * nc + 1] = total table width including all rules.
85 Similarly, cp[V] represents y positions within the table.
87 cp[V][1] = the height of the topmost horizontal rule.
88 cp[V][2] = cp[V][1] + the height of the topmost row.
89 cp[V][3] = cp[V][2] + the height of the second-from-top horizontal rule.
91 cp[V][2 * nr] = y position of the bottommost horizontal rule.
92 cp[V][2 * nr + 1] = total table height including all rules.
94 Rules and columns can have width or height 0, in which case consecutive
95 values in this array are equal. */
96 int *cp[TABLE_N_AXES];
98 /* render_break_next() can break a table such that some cells are not fully
99 contained within a render_page. This will happen if a cell is too wide
100 or two tall to fit on a single page, or if a cell spans multiple rows or
101 columns and the page only includes some of those rows or columns.
103 This hash table contains "struct render_overflow"s that represents each
104 such cell that doesn't completely fit on this page.
106 Each overflow cell borders at least one header edge of the table and may
107 border more. (A single table cell that is so large that it fills the
108 entire page can overflow on all four sides!) */
109 struct hmap overflows;
111 /* If a single column (or row) is too wide (or tall) to fit on a page
112 reasonably, then render_break_next() will split a single row or column
113 across multiple render_pages. This member indicates when this has
116 is_edge_cutoff[H][0] is true if pixels have been cut off the left side
117 of the leftmost column in this page, and false otherwise.
119 is_edge_cutoff[H][1] is true if pixels have been cut off the right side
120 of the rightmost column in this page, and false otherwise.
122 is_edge_cutoff[V][0] and is_edge_cutoff[V][1] are similar for the top
123 and bottom of the table.
125 The effect of is_edge_cutoff is to prevent rules along the edge in
126 question from being rendered.
128 When is_edge_cutoff is true for a given edge, the 'overflows' hmap will
129 contain a node for each cell along that edge. */
130 bool is_edge_cutoff[TABLE_N_AXES][2];
132 /* If part of a joined cell would be cut off by breaking a table along
133 'axis' at the rule with offset 'z' (where 0 <= z <= n[axis]), then
134 join_crossing[axis][z] is the thickness of the rule that would be cut
137 This is used to know to allocate extra space for breaking at such a
138 position, so that part of the cell's content is not lost.
140 This affects breaking a table only when headers are present. When
141 headers are not present, the rule's thickness is used for cell content,
142 so no part of the cell's content is lost (and in fact it is duplicated
143 across both pages). */
144 int *join_crossing[TABLE_N_AXES];
147 static struct render_page *render_page_create (const struct render_params *,
148 struct table *, int min_width);
150 struct render_page *render_page_ref (const struct render_page *page_);
151 static void render_page_unref (struct render_page *);
153 /* Returns the offset in struct render_page's cp[axis] array of the rule with
154 index RULE_IDX. That is, if RULE_IDX is 0, then the offset is that of the
155 leftmost or topmost rule; if RULE_IDX is 1, then the offset is that of the
156 next rule to the right (or below); and so on. */
158 rule_ofs (int rule_idx)
163 /* Returns the offset in struct render_page's cp[axis] array of the rule with
164 index RULE_IDX_R, which counts from the right side (or bottom) of the page
165 left (or up), according to whether AXIS is H or V, respectively. That is,
166 if RULE_IDX_R is 0, then the offset is that of the rightmost or bottommost
167 rule; if RULE_IDX is 1, then the offset is that of the next rule to the left
168 (or above); and so on. */
170 rule_ofs_r (const struct render_page *page, int axis, int rule_idx_r)
172 return (page->n[axis] - rule_idx_r) * 2;
175 /* Returns the offset in struct render_page's cp[axis] array of the cell with
176 index CELL_IDX. That is, if CELL_IDX is 0, then the offset is that of the
177 leftmost or topmost cell; if CELL_IDX is 1, then the offset is that of the
178 next cell to the right (or below); and so on. */
180 cell_ofs (int cell_idx)
182 return cell_idx * 2 + 1;
185 /* Returns the width of PAGE along AXIS from OFS0 to OFS1, exclusive. */
187 axis_width (const struct render_page *page, int axis, int ofs0, int ofs1)
189 return page->cp[axis][ofs1] - page->cp[axis][ofs0];
192 /* Returns the width of the headers in PAGE along AXIS. */
194 headers_width (const struct render_page *page, int axis)
196 int h0 = page->h[axis][0];
197 int w0 = axis_width (page, axis, rule_ofs (0), cell_ofs (h0));
198 int n = page->n[axis];
199 int h1 = page->h[axis][1];
200 int w1 = axis_width (page, axis, rule_ofs_r (page, axis, h1), cell_ofs (n));
204 /* Returns the width of cell X along AXIS in PAGE. */
206 cell_width (const struct render_page *page, int axis, int x)
208 return axis_width (page, axis, cell_ofs (x), cell_ofs (x) + 1);
211 /* Returns the width of rule X along AXIS in PAGE. */
213 rule_width (const struct render_page *page, int axis, int x)
215 return axis_width (page, axis, rule_ofs (x), rule_ofs (x) + 1);
218 /* Returns the width of rule X along AXIS in PAGE. */
220 rule_width_r (const struct render_page *page, int axis, int x)
222 int ofs = rule_ofs_r (page, axis, x);
223 return axis_width (page, axis, ofs, ofs + 1);
226 /* Returns the width of cells X0 through X1, exclusive, along AXIS in PAGE. */
228 joined_width (const struct render_page *page, int axis, int x0, int x1)
230 return axis_width (page, axis, cell_ofs (x0), cell_ofs (x1) - 1);
233 /* Returns the width of the widest cell, excluding headers, along AXIS in
236 max_cell_width (const struct render_page *page, int axis)
238 int n = page->n[axis];
239 int x0 = page->h[axis][0];
240 int x1 = n - page->h[axis][1];
243 for (int x = x0; x < x1; x++)
245 int w = cell_width (page, axis, x);
252 /* A cell that doesn't completely fit on the render_page. */
253 struct render_overflow
255 struct hmap_node node; /* In render_page's 'overflows' hmap. */
257 /* Occupied region of page.
259 d[H][0] is the leftmost column.
260 d[H][1] is the rightmost column, plus 1.
261 d[V][0] is the top row.
262 d[V][1] is the bottom row, plus 1.
264 The cell in its original table might occupy a larger region. This
265 member reflects the size of the cell in the current render_page, after
266 trimming off any rows or columns due to page-breaking. */
269 /* The space that has been trimmed off the cell:
271 overflow[H][0]: space trimmed off its left side.
272 overflow[H][1]: space trimmed off its right side.
273 overflow[V][0]: space trimmed off its top.
274 overflow[V][1]: space trimmed off its bottom.
276 During rendering, this information is used to position the rendered
277 portion of the cell within the available space.
279 When a cell is rendered, sometimes it is permitted to spill over into
280 space that is ordinarily reserved for rules. Either way, this space is
281 still included in overflow values.
283 Suppose, for example, that a cell that joins 2 columns has a width of 60
284 pixels and content "abcdef", that the 2 columns that it joins have
285 widths of 20 and 30 pixels, respectively, and that therefore the rule
286 between the two joined columns has a width of 10 (20 + 10 + 30 = 60).
287 It might render like this, if each character is 10x10, and showing a few
288 extra table cells for context:
296 If this render_page is broken at the rule that separates "gh" from
297 "ijk", then the page that contains the left side of the "abcdef" cell
298 will have overflow[H][1] of 10 + 30 = 40 for its portion of the cell,
299 and the page that contains the right side of the cell will have
300 overflow[H][0] of 20 + 10 = 30. The two resulting pages would look like
318 int overflow[TABLE_N_AXES][2];
321 /* Returns a hash value for (,Y). */
323 hash_cell (int x, int y)
325 return hash_int (x + (y << 16), 0);
328 /* Searches PAGE's set of render_overflow for one whose top-left cell is
329 (X,Y). Returns it, if there is one, otherwise a null pointer. */
330 static const struct render_overflow *
331 find_overflow (const struct render_page *page, int x, int y)
333 if (!hmap_is_empty (&page->overflows))
335 const struct render_overflow *of;
337 HMAP_FOR_EACH_WITH_HASH (of, struct render_overflow, node,
338 hash_cell (x, y), &page->overflows)
339 if (x == of->d[H] && y == of->d[V])
346 /* Row or column dimensions. Used to figure the size of a table in
347 render_page_create() and discarded after that. */
350 /* Width without considering rows (or columns) that span more than one (or
354 /* Width taking spanned rows (or columns) into consideration. */
358 /* Modifies the 'width' members of the N elements of ROWS so that their sum,
359 when added to rule widths RULES[1] through RULES[N - 1] inclusive, is at
362 distribute_spanned_width (int width,
363 struct render_row *rows, const int *rules, int n)
365 /* Sum up the unspanned widths of the N rows for use as weights. */
366 int total_unspanned = 0;
367 for (int x = 0; x < n; x++)
368 total_unspanned += rows[x].unspanned;
369 for (int x = 0; x < n - 1; x++)
370 total_unspanned += rules[x + 1];
371 if (total_unspanned >= width)
374 /* The algorithm used here is based on the following description from HTML 4:
376 For cells that span multiple columns, a simple approach consists of
377 apportioning the min/max widths evenly to each of the constituent
378 columns. A slightly more complex approach is to use the min/max
379 widths of unspanned cells to weight how spanned widths are
380 apportioned. Experiments suggest that a blend of the two approaches
381 gives good results for a wide range of tables.
383 We blend the two approaches half-and-half, except that we cannot use the
384 unspanned weights when 'total_unspanned' is 0 (because that would cause a
387 The calculation we want to do is this:
390 w1 = width * (column's unspanned width) / (total unspanned width)
391 (column's width) = (w0 + w1) / 2
393 We implement it as a precise calculation in integers by multiplying w0 and
394 w1 by the common denominator of all three calculations (d), dividing that
395 out in the column width calculation, and then keeping the remainder for
398 (We actually compute the unspanned width of a column as twice the
399 unspanned width, plus the width of the rule on the left, plus the width of
400 the rule on the right. That way each rule contributes to both the cell on
401 its left and on its right.)
403 long long int d0 = n;
404 long long int d1 = 2LL * MAX (total_unspanned, 1);
405 long long int d = d0 * d1;
406 if (total_unspanned > 0)
408 long long int w = d / 2;
409 for (int x = 0; x < n; x++)
412 if (total_unspanned > 0)
414 long long int unspanned = rows[x].unspanned * 2LL;
416 unspanned += rules[x + 1];
418 unspanned += rules[x];
419 w += width * unspanned * d0;
422 rows[x].width = MAX (rows[x].width, w / d);
423 w -= rows[x].width * d;
427 /* Initializes PAGE->cp[AXIS] from the row widths in ROWS and the rule widths
430 accumulate_row_widths (const struct render_page *page, enum table_axis axis,
431 const struct render_row *rows, const int *rules)
433 int n = page->n[axis];
434 int *cp = page->cp[axis];
436 for (int z = 0; z < n; z++)
438 cp[1] = cp[0] + rules[z];
439 cp[2] = cp[1] + rows[z].width;
442 cp[1] = cp[0] + rules[n];
445 /* Returns the sum of widths of the N ROWS and N+1 RULES. */
447 calculate_table_width (int n, const struct render_row *rows, int *rules)
450 for (int x = 0; x < n; x++)
451 width += rows[x].width;
452 for (int x = 0; x <= n; x++)
458 /* Rendering utility functions. */
460 /* Returns the line style to use for drawing a rule of the given TYPE. */
461 static enum render_line_style
462 rule_to_render_type (unsigned char type)
467 return RENDER_LINE_NONE;
469 return RENDER_LINE_SINGLE;
471 return RENDER_LINE_DASHED;
473 return RENDER_LINE_THICK;
475 return RENDER_LINE_THIN;
477 return RENDER_LINE_DOUBLE;
483 /* Returns the width of the rule in TABLE that is at offset Z along axis A, if
484 rendered with PARAMS. */
486 measure_rule (const struct render_params *params, const struct table *table,
487 enum table_axis a, int z)
489 enum table_axis b = !a;
491 /* Determine all types of rules that are present, as a bitmap in 'rules'
492 where rule type 't' is present if bit 2**t is set. */
493 struct cell_color color;
494 unsigned int rules = 0;
497 for (d[b] = 0; d[b] < table->n[b]; d[b]++)
498 rules |= 1u << table_get_rule (table, a, d[H], d[V], &color);
500 /* Turn off TAL_NONE because it has width 0 and we needn't bother. However,
501 if the device doesn't support margins, make sure that there is at least a
502 small gap between cells (but we don't need any at the left or right edge
504 if (rules & (1u << TAL_NONE))
506 rules &= ~(1u << TAL_NONE);
507 if (z > 0 && z < table->n[a] && !params->supports_margins && a == H)
508 rules |= 1u << TAL_SOLID;
511 /* Calculate maximum width of the rules that are present. */
513 for (size_t i = 0; i < TABLE_N_STROKES; i++)
514 if (rules & (1u << i))
515 width = MAX (width, params->line_widths[a][rule_to_render_type (i)]);
519 /* Allocates and returns a new render_page using PARAMS and TABLE. Allocates
520 space for rendering a table with dimensions given in N. The caller must
521 initialize most of the members itself. */
522 static struct render_page *
523 render_page_allocate__ (const struct render_params *params,
524 struct table *table, int n[TABLE_N_AXES])
526 struct render_page *page = xmalloc (sizeof *page);
527 page->params = params;
533 for (int i = 0; i < TABLE_N_AXES; i++)
535 page->cp[i] = xmalloc ((2 * n[i] + 2) * sizeof *page->cp[i]);
536 page->join_crossing[i] = xzalloc ((n[i] + 1)
537 * sizeof *page->join_crossing[i]);
540 hmap_init (&page->overflows);
541 memset (page->is_edge_cutoff, 0, sizeof page->is_edge_cutoff);
546 /* Allocates and returns a new render_page using PARAMS and TABLE. Allocates
547 space for all of the members of the new page, but the caller must initialize
548 the 'cp' member itself. */
549 static struct render_page *
550 render_page_allocate (const struct render_params *params, struct table *table)
552 struct render_page *page = render_page_allocate__ (params, table, table->n);
553 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
555 page->h[a][0] = table->h[a][0];
556 page->h[a][1] = table->h[a][1];
557 page->r[a][0] = table->h[a][0];
558 page->r[a][1] = table->n[a] - table->h[a][1];
563 /* Allocates and returns a new render_page for PARAMS and TABLE, initializing
564 cp[H] in the new page from ROWS and RULES. The caller must still initialize
566 static struct render_page *
567 create_page_with_exact_widths (const struct render_params *params,
569 const struct render_row *rows, int *rules)
571 struct render_page *page = render_page_allocate (params, table);
572 accumulate_row_widths (page, H, rows, rules);
576 /* Allocates and returns a new render_page for PARAMS and TABLE.
578 Initializes cp[H] in the new page by setting the width of each row 'i' to
579 somewhere between the minimum cell width ROW_MIN[i].width and the maximum
580 ROW_MAX[i].width. Sets the width of rules to those in RULES.
582 W_MIN is the sum of ROWS_MIN[].width.
584 W_MAX is the sum of ROWS_MAX[].width.
586 The caller must still initialize cp[V]. */
587 static struct render_page *
588 create_page_with_interpolated_widths (const struct render_params *params,
590 const struct render_row *rows_min,
591 const struct render_row *rows_max,
592 int w_min, int w_max, const int *rules)
594 const int n = table->n[H];
595 const long long int avail = params->size[H] - w_min;
596 const long long int wanted = w_max - w_min;
600 struct render_page *page = render_page_allocate (params, table);
602 int *cph = page->cp[H];
604 long long int w = wanted / 2;
605 for (int x = 0; x < n; x++)
607 w += avail * (rows_max[x].width - rows_min[x].width);
608 int extra = w / wanted;
611 cph[1] = cph[0] + rules[x];
612 cph[2] = cph[1] + rows_min[x].width + extra;
615 cph[1] = cph[0] + rules[n];
617 assert (page->cp[H][n * 2 + 1] == params->size[H]);
622 set_join_crossings (struct render_page *page, enum table_axis axis,
623 const struct table_cell *cell, int *rules)
625 for (int z = cell->d[axis][0] + 1; z <= cell->d[axis][1] - 1; z++)
626 page->join_crossing[axis][z] = rules[z];
629 /* Maps a contiguous range of cells from a page to the underlying table along
630 the horizpntal or vertical dimension. */
633 int p0; /* First ordinate in the page. */
634 int t0; /* First ordinate in the table. */
635 int n; /* Number of ordinates in page and table. */
638 /* Initializes M to a mapping from PAGE to PAGE->table along axis A. The
639 mapping includes ordinate Z (in PAGE). */
641 get_map (const struct render_page *page, enum table_axis a, int z,
644 if (z < page->h[a][0])
648 m->n = page->h[a][0];
650 else if (z < page->n[a] - page->h[a][1])
652 m->p0 = page->h[a][0];
653 m->t0 = page->r[a][0];
654 m->n = page->r[a][1] - page->r[a][0];
658 m->p0 = page->n[a] - page->h[a][1];
659 m->t0 = page->table->n[a] - page->table->h[a][1];
660 m->n = page->h[a][1];
664 /* Initializes CELL with the contents of the table cell at column X and row Y
665 within PAGE. When CELL is no longer needed, the caller is responsible for
666 freeing it by calling table_cell_free(CELL).
668 The caller must ensure that CELL is destroyed before TABLE is unref'ed.
670 This is equivalent to table_get_cell(), except X and Y are in terms of the
671 page's rows and columns rather than the underlying table's. */
673 render_get_cell (const struct render_page *page, int x, int y,
674 struct table_cell *cell)
676 int d[TABLE_N_AXES] = { [H] = x, [V] = y };
677 struct map map[TABLE_N_AXES];
679 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
681 struct map *m = &map[a];
682 get_map (page, a, d[a], m);
683 d[a] += m->t0 - m->p0;
685 table_get_cell (page->table, d[H], d[V], cell);
687 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
689 struct map *m = &map[a];
691 for (int i = 0; i < 2; i++)
692 cell->d[a][i] -= m->t0 - m->p0;
693 cell->d[a][0] = MAX (cell->d[a][0], m->p0);
694 cell->d[a][1] = MIN (cell->d[a][1], m->p0 + m->n);
698 /* Creates and returns a new render_page for rendering TABLE on a device
701 The new render_page will be suitable for rendering on a device whose page
702 size is PARAMS->size, but the caller is responsible for actually breaking it
703 up to fit on such a device, using the render_break abstraction. */
704 static struct render_page *
705 render_page_create (const struct render_params *params, struct table *table,
710 int nc = table_nc (table);
711 int nr = table_nr (table);
713 /* Figure out rule widths. */
714 int *rules[TABLE_N_AXES];
715 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
717 int n = table->n[axis] + 1;
719 rules[axis] = xnmalloc (n, sizeof *rules);
720 for (int z = 0; z < n; z++)
721 rules[axis][z] = measure_rule (params, table, axis, z);
724 /* Calculate minimum and maximum widths of cells that do not
725 span multiple columns. */
726 struct render_row *columns[2];
727 for (int i = 0; i < 2; i++)
728 columns[i] = xzalloc (nc * sizeof *columns[i]);
729 for (int y = 0; y < nr; y++)
730 for (int x = 0; x < nc; )
732 struct table_cell cell;
734 table_get_cell (table, x, y, &cell);
735 if (y == cell.d[V][0])
737 if (table_cell_colspan (&cell) == 1)
740 params->measure_cell_width (params->aux, &cell,
742 for (int i = 0; i < 2; i++)
743 if (columns[i][x].unspanned < w[i])
744 columns[i][x].unspanned = w[i];
748 table_cell_free (&cell);
751 /* Distribute widths of spanned columns. */
752 for (int i = 0; i < 2; i++)
753 for (int x = 0; x < nc; x++)
754 columns[i][x].width = columns[i][x].unspanned;
755 for (int y = 0; y < nr; y++)
756 for (int x = 0; x < nc; )
758 struct table_cell cell;
760 table_get_cell (table, x, y, &cell);
761 if (y == cell.d[V][0] && table_cell_colspan (&cell) > 1)
765 params->measure_cell_width (params->aux, &cell, &w[MIN], &w[MAX]);
766 for (int i = 0; i < 2; i++)
767 distribute_spanned_width (w[i], &columns[i][cell.d[H][0]],
768 rules[H], table_cell_colspan (&cell));
771 table_cell_free (&cell);
774 for (int i = 0; i < 2; i++)
775 distribute_spanned_width (min_width, &columns[i][0], rules[H], nc);
777 /* In pathological cases, spans can cause the minimum width of a column to
778 exceed the maximum width. This bollixes our interpolation algorithm
779 later, so fix it up. */
780 for (int i = 0; i < nc; i++)
781 if (columns[MIN][i].width > columns[MAX][i].width)
782 columns[MAX][i].width = columns[MIN][i].width;
784 /* Decide final column widths. */
786 for (int i = 0; i < 2; i++)
787 table_widths[i] = calculate_table_width (table_nc (table),
788 columns[i], rules[H]);
790 struct render_page *page;
791 if (table_widths[MAX] <= params->size[H])
793 /* Fits even with maximum widths. Use them. */
794 page = create_page_with_exact_widths (params, table, columns[MAX],
797 else if (table_widths[MIN] <= params->size[H])
799 /* Fits with minimum widths, so distribute the leftover space. */
800 page = create_page_with_interpolated_widths (
801 params, table, columns[MIN], columns[MAX],
802 table_widths[MIN], table_widths[MAX], rules[H]);
806 /* Doesn't fit even with minimum widths. Assign minimums for now, and
807 later we can break it horizontally into multiple pages. */
808 page = create_page_with_exact_widths (params, table, columns[MIN],
812 /* Calculate heights of cells that do not span multiple rows. */
813 struct render_row *rows = xzalloc (nr * sizeof *rows);
814 for (int y = 0; y < nr; y++)
815 for (int x = 0; x < nc; )
817 struct render_row *r = &rows[y];
818 struct table_cell cell;
820 render_get_cell (page, x, y, &cell);
821 if (y == cell.d[V][0])
823 if (table_cell_rowspan (&cell) == 1)
825 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
826 int h = params->measure_cell_height (params->aux, &cell, 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);
839 for (int i = 0; i < 2; i++)
842 /* Distribute heights of spanned rows. */
843 for (int y = 0; y < nr; y++)
844 for (int x = 0; x < nc; )
846 struct table_cell cell;
848 render_get_cell (page, x, y, &cell);
849 if (y == cell.d[V][0] && table_cell_rowspan (&cell) > 1)
851 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
852 int h = params->measure_cell_height (params->aux, &cell, w);
853 distribute_spanned_width (h, &rows[cell.d[V][0]], rules[V],
854 table_cell_rowspan (&cell));
857 table_cell_free (&cell);
860 /* Decide final row heights. */
861 accumulate_row_widths (page, V, rows, rules[V]);
864 /* Measure headers. If they are "too big", get rid of them. */
865 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
867 int hw = headers_width (page, axis);
868 if (hw * 2 >= page->params->size[axis]
869 || hw + max_cell_width (page, axis) > page->params->size[axis])
871 page->h[axis][0] = page->h[axis][1] = 0;
872 page->r[axis][0] = 0;
873 page->r[axis][1] = page->n[axis];
883 /* Increases PAGE's reference count. */
885 render_page_ref (const struct render_page *page_)
887 struct render_page *page = CONST_CAST (struct render_page *, page_);
892 /* Decreases PAGE's reference count and destroys PAGE if this causes the
893 reference count to fall to zero. */
895 render_page_unref (struct render_page *page)
897 if (page != NULL && --page->ref_cnt == 0)
899 struct render_overflow *overflow, *next;
900 HMAP_FOR_EACH_SAFE (overflow, next, struct render_overflow, node,
903 hmap_destroy (&page->overflows);
905 table_unref (page->table);
907 for (int i = 0; i < TABLE_N_AXES; ++i)
909 free (page->join_crossing[i]);
917 /* Returns the size of PAGE along AXIS. (This might be larger than the page
918 size specified in the parameters passed to render_page_create(). Use a
919 render_break to break up a render_page into page-sized chunks.) */
921 render_page_get_size (const struct render_page *page, enum table_axis axis)
923 return page->cp[axis][page->n[axis] * 2 + 1];
927 render_page_get_best_breakpoint (const struct render_page *page, int height)
929 /* If there's no room for at least the top row and the rules above and below
930 it, don't include any of the table. */
931 if (page->cp[V][3] > height)
934 /* Otherwise include as many rows and rules as we can. */
935 for (int y = 5; y <= 2 * page->n[V] + 1; y += 2)
936 if (page->cp[V][y] > height)
937 return page->cp[V][y - 2];
941 /* Drawing render_pages. */
943 /* This is like table_get_rule() except:
945 - D is in terms of the page's rows and column rather than the underlying
948 - The result is in the form of a render_line_style. */
949 static enum render_line_style
950 get_rule (const struct render_page *page, enum table_axis axis,
951 const int d_[TABLE_N_AXES], struct cell_color *color)
953 int d[TABLE_N_AXES] = { d_[0] / 2, d_[1] / 2 };
956 enum table_axis a = axis;
957 if (d[a] < page->h[a][0])
959 else if (d[a] <= page->n[a] - page->h[a][1])
961 if (page->h[a][0] && d[a] == page->h[a][0])
963 else if (page->h[a][1] && d[a] == page->n[a] - page->h[a][1])
964 d2 = page->table->n[a] - page->h[a][1];
965 d[a] += page->r[a][0] - page->h[a][0];
968 d[a] += ((page->table->n[a] - page->table->h[a][1])
969 - (page->n[a] - page->h[a][1]));
971 enum table_axis b = !axis;
973 get_map (page, b, d[b], &m);
976 int r = table_get_rule (page->table, axis, d[H], d[V], color);
980 int r2 = table_get_rule (page->table, axis, d[H], d[V], color);
981 r = table_rule_combine (r, r2);
983 return rule_to_render_type (r);
993 render_direction_rtl (void)
995 /* TRANSLATORS: Do not translate this string. If the script of your language
996 reads from right to left (eg Persian, Arabic, Hebrew etc), then replace
997 this string with "output-direction-rtl". Otherwise either leave it
998 untranslated or copy it verbatim. */
999 const char *dir = _("output-direction-ltr");
1000 if ( 0 == strcmp ("output-direction-rtl", dir))
1003 if ( 0 != strcmp ("output-direction-ltr", dir))
1004 fprintf (stderr, "This localisation has been incorrectly translated. "
1005 "Complain to the translator.\n");
1011 render_rule (const struct render_page *page, const int ofs[TABLE_N_AXES],
1012 const int d[TABLE_N_AXES])
1014 enum render_line_style styles[TABLE_N_AXES][2];
1015 struct cell_color colors[TABLE_N_AXES][2];
1017 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
1019 enum table_axis b = !a;
1021 styles[a][0] = styles[a][1] = RENDER_LINE_NONE;
1024 || (page->is_edge_cutoff[a][0] && d[a] == 0)
1025 || (page->is_edge_cutoff[a][1] && d[a] == page->n[a] * 2))
1032 int e[TABLE_N_AXES];
1036 styles[a][0] = get_rule (page, a, e, &colors[a][0]);
1039 if (d[b] / 2 < page->n[b])
1040 styles[a][1] = get_rule (page, a, d, &colors[a][1]);
1044 styles[a][0] = styles[a][1] = get_rule (page, a, d, &colors[a][0]);
1045 colors[a][1] = colors[a][0];
1049 if (styles[H][0] != RENDER_LINE_NONE || styles[H][1] != RENDER_LINE_NONE
1050 || styles[V][0] != RENDER_LINE_NONE || styles[V][1] != RENDER_LINE_NONE)
1052 int bb[TABLE_N_AXES][2];
1054 bb[H][0] = ofs[H] + page->cp[H][d[H]];
1055 bb[H][1] = ofs[H] + page->cp[H][d[H] + 1];
1056 if (page->params->rtl)
1058 int temp = bb[H][0];
1059 bb[H][0] = render_page_get_size (page, H) - bb[H][1];
1060 bb[H][1] = render_page_get_size (page, H) - temp;
1062 bb[V][0] = ofs[V] + page->cp[V][d[V]];
1063 bb[V][1] = ofs[V] + page->cp[V][d[V] + 1];
1064 page->params->draw_line (page->params->aux, bb, styles, colors);
1069 render_cell (const struct render_page *page, const int ofs[TABLE_N_AXES],
1070 const struct table_cell *cell)
1072 int bb[TABLE_N_AXES][2];
1073 int clip[TABLE_N_AXES][2];
1075 bb[H][0] = clip[H][0] = ofs[H] + page->cp[H][cell->d[H][0] * 2 + 1];
1076 bb[H][1] = clip[H][1] = ofs[H] + page->cp[H][cell->d[H][1] * 2];
1077 if (page->params->rtl)
1079 int temp = bb[H][0];
1080 bb[H][0] = clip[H][0] = render_page_get_size (page, H) - bb[H][1];
1081 bb[H][1] = clip[H][1] = render_page_get_size (page, H) - temp;
1083 bb[V][0] = clip[V][0] = ofs[V] + page->cp[V][cell->d[V][0] * 2 + 1];
1084 bb[V][1] = clip[V][1] = ofs[V] + page->cp[V][cell->d[V][1] * 2];
1086 enum table_valign valign = cell->style->cell_style.valign;
1087 if (valign != TABLE_VALIGN_TOP)
1089 int height = page->params->measure_cell_height (
1090 page->params->aux, cell, bb[H][1] - bb[H][0]);
1091 int extra = bb[V][1] - bb[V][0] - height;
1094 if (valign == TABLE_VALIGN_CENTER)
1100 const struct render_overflow *of = find_overflow (
1101 page, cell->d[H][0], cell->d[V][0]);
1103 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
1105 if (of->overflow[axis][0])
1107 bb[axis][0] -= of->overflow[axis][0];
1108 if (cell->d[axis][0] == 0 && !page->is_edge_cutoff[axis][0])
1109 clip[axis][0] = ofs[axis] + page->cp[axis][cell->d[axis][0] * 2];
1111 if (of->overflow[axis][1])
1113 bb[axis][1] += of->overflow[axis][1];
1114 if (cell->d[axis][1] == page->n[axis]
1115 && !page->is_edge_cutoff[axis][1])
1116 clip[axis][1] = ofs[axis] + page->cp[axis][cell->d[axis][1] * 2
1121 int spill[TABLE_N_AXES][2];
1122 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
1124 spill[axis][0] = rule_width (page, axis, cell->d[axis][0]) / 2;
1125 spill[axis][1] = rule_width (page, axis, cell->d[axis][1]) / 2;
1128 int color_idx = (cell->d[V][0] < page->h[V][0]
1129 || page->n[V] - (cell->d[V][0] + 1) < page->h[V][1]
1131 : (cell->d[V][0] - page->h[V][0]) & 1);
1132 page->params->draw_cell (page->params->aux, cell, color_idx,
1136 /* Draws the cells of PAGE indicated in BB. */
1138 render_page_draw_cells (const struct render_page *page,
1139 int ofs[TABLE_N_AXES], int bb[TABLE_N_AXES][2])
1141 for (int y = bb[V][0]; y < bb[V][1]; y++)
1142 for (int x = bb[H][0]; x < bb[H][1]; )
1143 if (!is_rule (x) && !is_rule (y))
1145 struct table_cell cell;
1147 render_get_cell (page, x / 2, y / 2, &cell);
1148 if (y / 2 == bb[V][0] / 2 || y / 2 == cell.d[V][0])
1149 render_cell (page, ofs, &cell);
1150 x = rule_ofs (cell.d[H][1]);
1151 table_cell_free (&cell);
1156 for (int y = bb[V][0]; y < bb[V][1]; y++)
1157 for (int x = bb[H][0]; x < bb[H][1]; x++)
1158 if (is_rule (x) || is_rule (y))
1160 int d[TABLE_N_AXES];
1163 render_rule (page, ofs, d);
1167 /* Renders PAGE, by calling the 'draw_line' and 'draw_cell' functions from the
1168 render_params provided to render_page_create(). */
1170 render_page_draw (const struct render_page *page, int ofs[TABLE_N_AXES])
1172 int bb[TABLE_N_AXES][2];
1175 bb[H][1] = page->n[H] * 2 + 1;
1177 bb[V][1] = page->n[V] * 2 + 1;
1179 render_page_draw_cells (page, ofs, bb);
1182 /* Returns the greatest value i, 0 <= i < n, such that cp[i] <= x0. */
1184 get_clip_min_extent (int x0, const int cp[], int n)
1191 int middle = low + (high - low) / 2;
1193 if (cp[middle] <= x0)
1205 /* Returns the least value i, 0 <= i < n, such that cp[i] >= x1. */
1207 get_clip_max_extent (int x1, const int cp[], int n)
1214 int middle = low + (high - low) / 2;
1216 if (cp[middle] >= x1)
1217 best = high = middle;
1222 while (best > 0 && cp[best - 1] == cp[best])
1228 /* Renders the cells of PAGE that intersect (X,Y)-(X+W,Y+H), by calling the
1229 'draw_line' and 'draw_cell' functions from the render_params provided to
1230 render_page_create(). */
1232 render_page_draw_region (const struct render_page *page,
1233 int ofs[TABLE_N_AXES], int clip[TABLE_N_AXES][2])
1235 int bb[TABLE_N_AXES][2];
1237 bb[H][0] = get_clip_min_extent (clip[H][0], page->cp[H], page->n[H] * 2 + 1);
1238 bb[H][1] = get_clip_max_extent (clip[H][1], page->cp[H], page->n[H] * 2 + 1);
1239 bb[V][0] = get_clip_min_extent (clip[V][0], page->cp[V], page->n[V] * 2 + 1);
1240 bb[V][1] = get_clip_max_extent (clip[V][1], page->cp[V], page->n[V] * 2 + 1);
1242 render_page_draw_cells (page, ofs, bb);
1245 /* Breaking up tables to fit on a page. */
1247 /* An iterator for breaking render_pages into smaller chunks. */
1250 struct render_page *page; /* Page being broken up. */
1251 enum table_axis axis; /* Axis along which 'page' is being broken. */
1252 int z; /* Next cell along 'axis'. */
1253 int pixel; /* Pixel offset within cell 'z' (usually 0). */
1254 int hw; /* Width of headers of 'page' along 'axis'. */
1257 static int needed_size (const struct render_break *, int cell);
1258 static bool cell_is_breakable (const struct render_break *, int cell);
1259 static struct render_page *render_page_select (const struct render_page *,
1264 /* Initializes render_break B for breaking PAGE along AXIS.
1265 Takes ownership of PAGE. */
1267 render_break_init (struct render_break *b, struct render_page *page,
1268 enum table_axis axis)
1272 b->z = page->h[axis][0];
1274 b->hw = headers_width (page, axis);
1277 /* Initializes B as a render_break structure for which
1278 render_break_has_next() always returns false. */
1280 render_break_init_empty (struct render_break *b)
1283 b->axis = TABLE_HORZ;
1289 /* Frees B and unrefs the render_page that it owns. */
1291 render_break_destroy (struct render_break *b)
1295 render_page_unref (b->page);
1300 /* Returns true if B still has cells that are yet to be returned,
1301 false if all of B's page has been processed. */
1303 render_break_has_next (const struct render_break *b)
1305 const struct render_page *page = b->page;
1306 enum table_axis axis = b->axis;
1308 return page != NULL && b->z < page->n[axis] - page->h[axis][1];
1311 /* Returns a new render_page that is up to SIZE pixels wide along B's axis.
1312 Returns a null pointer if B has already been completely broken up, or if
1313 SIZE is too small to reasonably render any cells. The latter will never
1314 happen if SIZE is at least as large as the page size passed to
1315 render_page_create() along B's axis. */
1316 static struct render_page *
1317 render_break_next (struct render_break *b, int size)
1319 const struct render_page *page = b->page;
1320 enum table_axis axis = b->axis;
1321 struct render_page *subpage;
1323 if (!render_break_has_next (b))
1328 for (z = b->z; z < page->n[axis] - page->h[axis][1]; z++)
1330 int needed = needed_size (b, z + 1);
1333 if (cell_is_breakable (b, z))
1335 /* If there is no right header and we render a partial cell on
1336 the right side of the body, then we omit the rightmost rule of
1337 the body. Otherwise the rendering is deceptive because it
1338 looks like the whole cell is present instead of a partial
1341 This is similar to code for the left side in needed_size(). */
1342 int rule_allowance = (page->h[axis][1]
1344 : rule_width (page, axis, z));
1346 /* The amount that, if we added cell 'z', the rendering would
1347 overfill the allocated 'size'. */
1348 int overhang = needed - size - rule_allowance;
1350 /* The width of cell 'z'. */
1351 int cell_size = cell_width (page, axis, z);
1353 /* The amount trimmed off the left side of 'z',
1354 and the amount left to render. */
1355 int cell_ofs = z == b->z ? b->pixel : 0;
1356 int cell_left = cell_size - cell_ofs;
1358 /* A small but visible width. */
1359 int em = page->params->font_size[axis];
1361 /* If some of the cell remains to render,
1362 and there would still be some of the cell left afterward,
1363 then partially render that much of the cell. */
1364 pixel = (cell_left && cell_left > overhang
1365 ? cell_left - overhang + cell_ofs
1368 /* If there would be only a tiny amount of the cell left after
1369 rendering it partially, reduce the amount rendered slightly
1370 to make the output look a little better. */
1371 if (pixel + em > cell_size)
1372 pixel = MAX (pixel - em, 0);
1374 /* If we're breaking vertically, then consider whether the cells
1375 being broken have a better internal breakpoint than the exact
1376 number of pixels available, which might look bad e.g. because
1377 it breaks in the middle of a line of text. */
1378 if (axis == TABLE_VERT && page->params->adjust_break)
1379 for (int x = 0; x < page->n[H]; )
1381 struct table_cell cell;
1383 render_get_cell (page, x, z, &cell);
1384 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
1385 int better_pixel = page->params->adjust_break (
1386 page->params->aux, &cell, w, pixel);
1388 table_cell_free (&cell);
1390 if (better_pixel < pixel)
1392 if (better_pixel > (z == b->z ? b->pixel : 0))
1394 pixel = better_pixel;
1397 else if (better_pixel == 0 && z != b->z)
1409 if (z == b->z && !pixel)
1412 subpage = render_page_select (page, axis, b->z, b->pixel,
1414 pixel ? cell_width (page, axis, z) - pixel
1421 /* Returns the width that would be required along B's axis to render a page
1422 from B's current position up to but not including CELL. */
1424 needed_size (const struct render_break *b, int cell)
1426 const struct render_page *page = b->page;
1427 enum table_axis axis = b->axis;
1429 /* Width of left header not including its rightmost rule. */
1430 int size = axis_width (page, axis, 0, rule_ofs (page->h[axis][0]));
1432 /* If we have a pixel offset and there is no left header, then we omit the
1433 leftmost rule of the body. Otherwise the rendering is deceptive because
1434 it looks like the whole cell is present instead of a partial cell.
1436 Otherwise (if there are headers) we will be merging two rules: the
1437 rightmost rule in the header and the leftmost rule in the body. We assume
1438 that the width of a merged rule is the larger of the widths of either rule
1440 if (b->pixel == 0 || page->h[axis][0])
1441 size += MAX (rule_width (page, axis, page->h[axis][0]),
1442 rule_width (page, axis, b->z));
1444 /* Width of body, minus any pixel offset in the leftmost cell. */
1445 size += joined_width (page, axis, b->z, cell) - b->pixel;
1447 /* Width of rightmost rule in body merged with leftmost rule in headers. */
1448 size += MAX (rule_width_r (page, axis, page->h[axis][1]),
1449 rule_width (page, axis, cell));
1451 /* Width of right header not including its leftmost rule. */
1452 size += axis_width (page, axis, rule_ofs_r (page, axis, page->h[axis][1]),
1453 rule_ofs_r (page, axis, 0));
1455 /* Join crossing. */
1456 if (page->h[axis][0] && page->h[axis][1])
1457 size += page->join_crossing[axis][b->z];
1462 /* Returns true if CELL along B's axis may be broken across a page boundary.
1464 This is just a heuristic. Breaking cells across page boundaries can save
1465 space, but it looks ugly. */
1467 cell_is_breakable (const struct render_break *b, int cell)
1469 const struct render_page *page = b->page;
1470 enum table_axis axis = b->axis;
1472 return cell_width (page, axis, cell) >= page->params->min_break[axis];
1479 const struct render_params *params;
1481 struct render_page **pages;
1482 size_t n_pages, allocated_pages;
1485 struct render_break x_break;
1486 struct render_break y_break;
1489 static const struct render_page *
1490 render_pager_add_table (struct render_pager *p, struct table *table,
1493 if (p->n_pages >= p->allocated_pages)
1494 p->pages = x2nrealloc (p->pages, &p->allocated_pages, sizeof *p->pages);
1496 struct render_page *page = render_page_create (p->params, table, min_width);
1497 p->pages[p->n_pages++] = page;
1502 render_pager_start_page (struct render_pager *p)
1504 render_break_init (&p->x_break, render_page_ref (p->pages[p->cur_page++]),
1506 render_break_init_empty (&p->y_break);
1510 add_footnote_page (struct render_pager *p, const struct table_item *item)
1512 const struct footnote **f;
1513 size_t n_footnotes = table_collect_footnotes (item, &f);
1517 struct tab_table *t = tab_create (2, n_footnotes);
1519 for (size_t i = 0; i < n_footnotes; i++)
1522 tab_text_format (t, 0, i, TAB_LEFT, "%s.", f[i]->marker);
1523 tab_text (t, 1, i, TAB_LEFT, f[i]->content);
1526 tab_add_style (t, 0, i, f[i]->style);
1527 tab_add_style (t, 1, i, f[i]->style);
1530 render_pager_add_table (p, &t->table, 0);
1536 add_text_page (struct render_pager *p, const struct table_item_text *t,
1542 struct tab_table *tab = tab_create (1, 1);
1543 tab_text (tab, 0, 0, 0, t->content);
1544 for (size_t i = 0; i < t->n_footnotes; i++)
1545 tab_add_footnote (tab, 0, 0, t->footnotes[i]);
1547 tab->styles[0] = area_style_clone (tab->container, t->style);
1548 render_pager_add_table (p, &tab->table, min_width);
1551 /* Creates and returns a new render_pager for rendering TABLE_ITEM on the
1552 device with the given PARAMS. */
1553 struct render_pager *
1554 render_pager_create (const struct render_params *params,
1555 const struct table_item *table_item)
1557 const struct table *table = table_item_get_table (table_item);
1559 struct render_pager *p = xzalloc (sizeof *p);
1562 struct render_page *page = render_page_create (params, table_ref (table), 0);
1563 struct render_break b;
1564 render_break_init (&b, page, H);
1565 struct render_page *subpage = render_break_next (&b, p->params->size[H]);
1566 int title_width = subpage ? subpage->cp[H][2 * subpage->n[H] + 1] : 0;
1567 render_page_unref (subpage);
1568 render_break_destroy (&b);
1571 add_text_page (p, table_item_get_title (table_item), title_width);
1574 add_text_page (p, table_item_get_layers (table_item), title_width);
1577 render_pager_add_table (p, table_ref (table_item_get_table (table_item)), 0);
1580 add_text_page (p, table_item_get_caption (table_item), 0);
1583 add_footnote_page (p, table_item);
1585 render_pager_start_page (p);
1592 render_pager_destroy (struct render_pager *p)
1596 render_break_destroy (&p->x_break);
1597 render_break_destroy (&p->y_break);
1598 for (size_t i = 0; i < p->n_pages; i++)
1599 render_page_unref (p->pages[i]);
1605 /* Returns true if P has content remaining to render, false if rendering is
1608 render_pager_has_next (const struct render_pager *p_)
1610 struct render_pager *p = CONST_CAST (struct render_pager *, p_);
1612 while (!render_break_has_next (&p->y_break))
1614 render_break_destroy (&p->y_break);
1615 if (!render_break_has_next (&p->x_break))
1617 render_break_destroy (&p->x_break);
1618 if (p->cur_page >= p->n_pages)
1620 render_break_init_empty (&p->x_break);
1621 render_break_init_empty (&p->y_break);
1624 render_pager_start_page (p);
1628 &p->y_break, render_break_next (&p->x_break, p->params->size[H]), V);
1633 /* Draws a chunk of content from P to fit in a space that has vertical size
1634 SPACE and the horizontal size specified in the render_params passed to
1635 render_page_create(). Returns the amount of space actually used by the
1636 rendered chunk, which will be 0 if SPACE is too small to render anything or
1637 if no content remains (use render_pager_has_next() to distinguish these
1640 render_pager_draw_next (struct render_pager *p, int space)
1642 int ofs[TABLE_N_AXES] = { 0, 0 };
1643 size_t start_page = SIZE_MAX;
1645 while (render_pager_has_next (p))
1647 if (start_page == p->cur_page)
1649 start_page = p->cur_page;
1651 struct render_page *page
1652 = render_break_next (&p->y_break, space - ofs[V]);
1656 render_page_draw (page, ofs);
1657 ofs[V] += render_page_get_size (page, V);
1658 render_page_unref (page);
1663 /* Draws all of P's content. */
1665 render_pager_draw (const struct render_pager *p)
1667 render_pager_draw_region (p, 0, 0, INT_MAX, INT_MAX);
1670 /* Draws the region of P's content that lies in the region (X,Y)-(X+W,Y+H).
1671 Some extra content might be drawn; the device should perform clipping as
1674 render_pager_draw_region (const struct render_pager *p,
1675 int x, int y, int w, int h)
1677 int ofs[TABLE_N_AXES] = { 0, 0 };
1678 int clip[TABLE_N_AXES][2];
1682 for (size_t i = 0; i < p->n_pages; i++)
1684 const struct render_page *page = p->pages[i];
1685 int size = render_page_get_size (page, V);
1687 clip[V][0] = MAX (y, ofs[V]) - ofs[V];
1688 clip[V][1] = MIN (y + h, ofs[V] + size) - ofs[V];
1689 if (clip[V][1] > clip[V][0])
1690 render_page_draw_region (page, ofs, clip);
1696 /* Returns the size of P's content along AXIS; i.e. the content's width if AXIS
1697 is TABLE_HORZ and its length if AXIS is TABLE_VERT. */
1699 render_pager_get_size (const struct render_pager *p, enum table_axis axis)
1703 for (size_t i = 0; i < p->n_pages; i++)
1705 int subsize = render_page_get_size (p->pages[i], axis);
1706 size = axis == H ? MAX (size, subsize) : size + subsize;
1713 render_pager_get_best_breakpoint (const struct render_pager *p, int height)
1718 for (i = 0; i < p->n_pages; i++)
1720 int size = render_page_get_size (p->pages[i], V);
1721 if (y + size >= height)
1722 return render_page_get_best_breakpoint (p->pages[i], height - y) + y;
1729 /* render_page_select() and helpers. */
1731 struct render_page_selection
1733 const struct render_page *page; /* Page whose slice we are selecting. */
1734 struct render_page *subpage; /* New page under construction. */
1735 enum table_axis a; /* Axis of 'page' along which 'subpage' is a slice. */
1736 enum table_axis b; /* The opposite of 'a'. */
1737 int z0; /* First cell along 'a' being selected. */
1738 int z1; /* Last cell being selected, plus 1. */
1739 int p0; /* Number of pixels to trim off left side of z0. */
1740 int p1; /* Number of pixels to trim off right side of z1-1. */
1743 static void cell_to_subpage (struct render_page_selection *,
1744 const struct table_cell *,
1745 int subcell[TABLE_N_AXES]);
1746 static const struct render_overflow *find_overflow_for_cell (
1747 struct render_page_selection *, const struct table_cell *);
1748 static struct render_overflow *insert_overflow (struct render_page_selection *,
1749 const struct table_cell *);
1751 /* Creates and returns a new render_page whose contents are a subregion of
1752 PAGE's contents. The new render_page includes cells Z0 through Z1
1753 (exclusive) along AXIS, plus any headers on AXIS.
1755 If P0 is nonzero, then it is a number of pixels to exclude from the left or
1756 top (according to AXIS) of cell Z0. Similarly, P1 is a number of pixels to
1757 exclude from the right or bottom of cell Z1 - 1. (P0 and P1 are used to
1758 render cells that are too large to fit on a single page.)
1760 The whole of axis !AXIS is included. (The caller may follow up with another
1761 call to render_page_select() to select on !AXIS to select on that axis as
1764 The caller retains ownership of PAGE, which is not modified. */
1765 static struct render_page *
1766 render_page_select (const struct render_page *page, enum table_axis axis,
1767 int z0, int p0, int z1, int p1)
1769 enum table_axis a = axis;
1770 enum table_axis b = !a;
1772 /* Optimize case where all of PAGE is selected by just incrementing the
1774 if (z0 == page->h[a][0] && p0 == 0
1775 && z1 == page->n[a] - page->h[a][1] && p1 == 0)
1777 struct render_page *page_rw = CONST_CAST (struct render_page *, page);
1782 /* Allocate subpage. */
1783 int trim[2] = { z0 - page->h[a][0], (page->n[a] - page->h[a][1]) - z1 };
1784 int n[TABLE_N_AXES] = { [H] = page->n[H], [V] = page->n[V] };
1785 n[a] -= trim[0] + trim[1];
1786 struct render_page *subpage = render_page_allocate__ (
1787 page->params, table_ref (page->table), n);
1788 for (enum table_axis k = 0; k < TABLE_N_AXES; k++)
1790 subpage->h[k][0] = page->h[k][0];
1791 subpage->h[k][1] = page->h[k][1];
1792 subpage->r[k][0] = page->r[k][0];
1793 subpage->r[k][1] = page->r[k][1];
1795 subpage->r[a][0] += trim[0];
1796 subpage->r[a][1] -= trim[1];
1798 /* An edge is cut off if it was cut off in PAGE or if we're trimming pixels
1799 off that side of the page and there are no headers. */
1800 subpage->is_edge_cutoff[a][0] =
1801 subpage->h[a][0] == 0 && (p0 || (z0 == 0 && page->is_edge_cutoff[a][0]));
1802 subpage->is_edge_cutoff[a][1] =
1803 subpage->h[a][1] == 0 && (p1 || (z1 == page->n[a]
1804 && page->is_edge_cutoff[a][1]));
1805 subpage->is_edge_cutoff[b][0] = page->is_edge_cutoff[b][0];
1806 subpage->is_edge_cutoff[b][1] = page->is_edge_cutoff[b][1];
1808 /* Select join crossings from PAGE into subpage. */
1809 int *jc = subpage->join_crossing[a];
1810 for (int z = 0; z < page->h[a][0]; z++)
1811 *jc++ = page->join_crossing[a][z];
1812 for (int z = z0; z <= z1; z++)
1813 *jc++ = page->join_crossing[a][z];
1814 for (int z = page->n[a] - page->h[a][1]; z < page->n[a]; z++)
1815 *jc++ = page->join_crossing[a][z];
1816 assert (jc == &subpage->join_crossing[a][subpage->n[a] + 1]);
1818 memcpy (subpage->join_crossing[b], page->join_crossing[b],
1819 (subpage->n[b] + 1) * sizeof **subpage->join_crossing);
1821 /* Select widths from PAGE into subpage. */
1822 int *scp = page->cp[a];
1823 int *dcp = subpage->cp[a];
1825 for (int z = 0; z <= rule_ofs (subpage->h[a][0]); z++, dcp++)
1827 int w = !z && subpage->is_edge_cutoff[a][0] ? 0 : scp[z + 1] - scp[z];
1828 dcp[1] = dcp[0] + w;
1830 for (int z = cell_ofs (z0); z <= cell_ofs (z1 - 1); z++, dcp++)
1832 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1833 if (z == cell_ofs (z0))
1836 if (page->h[a][0] && page->h[a][1])
1837 dcp[1] += page->join_crossing[a][z / 2];
1839 if (z == cell_ofs (z1 - 1))
1842 for (int z = rule_ofs_r (page, a, subpage->h[a][1]);
1843 z <= rule_ofs_r (page, a, 0); z++, dcp++)
1845 if (z == rule_ofs_r (page, a, 0) && subpage->is_edge_cutoff[a][1])
1848 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1850 assert (dcp == &subpage->cp[a][2 * subpage->n[a] + 1]);
1852 for (int z = 0; z < page->n[b] * 2 + 2; z++)
1853 subpage->cp[b][z] = page->cp[b][z];
1855 /* Add new overflows. */
1856 struct render_page_selection s = {
1867 if (!page->h[a][0] || z0 > page->h[a][0] || p0)
1868 for (int z = 0; z < page->n[b]; )
1870 int d[TABLE_N_AXES];
1874 struct table_cell cell;
1875 render_get_cell (page, d[H], d[V], &cell);
1876 bool overflow0 = p0 || cell.d[a][0] < z0;
1877 bool overflow1 = cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1);
1878 if (overflow0 || overflow1)
1880 struct render_overflow *ro = insert_overflow (&s, &cell);
1884 ro->overflow[a][0] += p0 + axis_width (
1885 page, a, cell_ofs (cell.d[a][0]), cell_ofs (z0));
1886 if (page->h[a][0] && page->h[a][1])
1887 ro->overflow[a][0] -= page->join_crossing[a][cell.d[a][0]
1893 ro->overflow[a][1] += p1 + axis_width (
1894 page, a, cell_ofs (z1), cell_ofs (cell.d[a][1]));
1895 if (page->h[a][0] && page->h[a][1])
1896 ro->overflow[a][1] -= page->join_crossing[a][cell.d[a][1]];
1900 table_cell_free (&cell);
1903 if (!page->h[a][1] || z1 < page->n[a] - page->h[a][1] || p1)
1904 for (int z = 0; z < page->n[b]; )
1906 int d[TABLE_N_AXES];
1910 struct table_cell cell;
1911 render_get_cell (page, d[H], d[V], &cell);
1912 if ((cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1))
1913 && find_overflow_for_cell (&s, &cell) == NULL)
1915 struct render_overflow *ro = insert_overflow (&s, &cell);
1916 ro->overflow[a][1] += p1 + axis_width (page, a, cell_ofs (z1),
1917 cell_ofs (cell.d[a][1]));
1920 table_cell_free (&cell);
1923 /* Copy overflows from PAGE into subpage. */
1924 struct render_overflow *ro;
1925 HMAP_FOR_EACH (ro, struct render_overflow, node, &page->overflows)
1927 struct table_cell cell;
1929 table_get_cell (page->table, ro->d[H], ro->d[V], &cell);
1930 if (cell.d[a][1] > z0 && cell.d[a][0] < z1
1931 && find_overflow_for_cell (&s, &cell) == NULL)
1932 insert_overflow (&s, &cell);
1933 table_cell_free (&cell);
1939 /* Given CELL, a table_cell within S->page, stores in SUBCELL the (x,y)
1940 coordinates of the top-left cell as it will appear in S->subpage.
1942 CELL must actually intersect the region of S->page that is being selected
1943 by render_page_select() or the results will not make any sense. */
1945 cell_to_subpage (struct render_page_selection *s,
1946 const struct table_cell *cell, int subcell[TABLE_N_AXES])
1948 enum table_axis a = s->a;
1949 enum table_axis b = s->b;
1950 int ha0 = s->subpage->h[a][0];
1952 subcell[a] = MAX (cell->d[a][0] - s->z0 + ha0, ha0);
1953 subcell[b] = cell->d[b][0];
1956 /* Given CELL, a table_cell within S->page, returns the render_overflow for
1957 that cell in S->subpage, if there is one, and a null pointer otherwise.
1959 CELL must actually intersect the region of S->page that is being selected
1960 by render_page_select() or the results will not make any sense. */
1961 static const struct render_overflow *
1962 find_overflow_for_cell (struct render_page_selection *s,
1963 const struct table_cell *cell)
1967 cell_to_subpage (s, cell, subcell);
1968 return find_overflow (s->subpage, subcell[H], subcell[V]);
1971 /* Given CELL, a table_cell within S->page, inserts a render_overflow for that
1972 cell in S->subpage (which must not already exist). Initializes the new
1973 render_overflow's 'overflow' member from the overflow for CELL in S->page,
1976 CELL must actually intersect the region of S->page that is being selected
1977 by render_page_select() or the results will not make any sense. */
1978 static struct render_overflow *
1979 insert_overflow (struct render_page_selection *s,
1980 const struct table_cell *cell)
1982 struct render_overflow *of = xzalloc (sizeof *of);
1983 cell_to_subpage (s, cell, of->d);
1984 hmap_insert (&s->subpage->overflows, &of->node,
1985 hash_cell (of->d[H], of->d[V]));
1987 const struct render_overflow *old
1988 = find_overflow (s->page, cell->d[H][0], cell->d[V][0]);
1990 memcpy (of->overflow, old->overflow, sizeof of->overflow);