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/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 /* Region of 'table' to render.
60 The horizontal cells rendered are the leftmost h[H][0], then
61 r[H][0] through r[H][1], exclusive, then the rightmost h[H][1].
63 The vertical cells rendered are the topmost h[V][0], then r[V][0]
64 through r[V][1], exclusive, then the bottommost h[V][1].
66 n[H] = h[H][0] + (r[H][1] - r[H][0]) + h[H][1]
67 n[V] = h[V][0] + (r[V][1] - r[V][0]) + h[V][1]
69 int h[TABLE_N_AXES][2];
70 int r[TABLE_N_AXES][2];
75 cp[H] represents x positions within the table.
77 cp[H][1] = the width of the leftmost vertical rule.
78 cp[H][2] = cp[H][1] + the width of the leftmost column.
79 cp[H][3] = cp[H][2] + the width of the second-from-left vertical rule.
81 cp[H][2 * nc] = x position of the rightmost vertical rule.
82 cp[H][2 * nc + 1] = total table width including all rules.
84 Similarly, cp[V] represents y positions within the table.
86 cp[V][1] = the height of the topmost horizontal rule.
87 cp[V][2] = cp[V][1] + the height of the topmost row.
88 cp[V][3] = cp[V][2] + the height of the second-from-top horizontal rule.
90 cp[V][2 * nr] = y position of the bottommost horizontal rule.
91 cp[V][2 * nr + 1] = total table height including all rules.
93 Rules and columns can have width or height 0, in which case consecutive
94 values in this array are equal. */
95 int *cp[TABLE_N_AXES];
97 /* render_break_next() can break a table such that some cells are not fully
98 contained within a render_page. This will happen if a cell is too wide
99 or two tall to fit on a single page, or if a cell spans multiple rows or
100 columns and the page only includes some of those rows or columns.
102 This hash table contains "struct render_overflow"s that represents each
103 such cell that doesn't completely fit on this page.
105 Each overflow cell borders at least one header edge of the table and may
106 border more. (A single table cell that is so large that it fills the
107 entire page can overflow on all four sides!) */
108 struct hmap overflows;
110 /* If a single column (or row) is too wide (or tall) to fit on a page
111 reasonably, then render_break_next() will split a single row or column
112 across multiple render_pages. This member indicates when this has
115 is_edge_cutoff[H][0] is true if pixels have been cut off the left side
116 of the leftmost column in this page, and false otherwise.
118 is_edge_cutoff[H][1] is true if pixels have been cut off the right side
119 of the rightmost column in this page, and false otherwise.
121 is_edge_cutoff[V][0] and is_edge_cutoff[V][1] are similar for the top
122 and bottom of the table.
124 The effect of is_edge_cutoff is to prevent rules along the edge in
125 question from being rendered.
127 When is_edge_cutoff is true for a given edge, the 'overflows' hmap will
128 contain a node for each cell along that edge. */
129 bool is_edge_cutoff[TABLE_N_AXES][2];
131 /* If part of a joined cell would be cut off by breaking a table along
132 'axis' at the rule with offset 'z' (where 0 <= z <= n[axis]), then
133 join_crossing[axis][z] is the thickness of the rule that would be cut
136 This is used to know to allocate extra space for breaking at such a
137 position, so that part of the cell's content is not lost.
139 This affects breaking a table only when headers are present. When
140 headers are not present, the rule's thickness is used for cell content,
141 so no part of the cell's content is lost (and in fact it is duplicated
142 across both pages). */
143 int *join_crossing[TABLE_N_AXES];
146 static struct render_page *render_page_create (const struct render_params *,
147 struct table *, int min_width);
149 struct render_page *render_page_ref (const struct render_page *page_);
150 static void render_page_unref (struct render_page *);
152 /* Returns the offset in struct render_page's cp[axis] array of the rule with
153 index RULE_IDX. That is, if RULE_IDX is 0, then the offset is that of the
154 leftmost or topmost rule; if RULE_IDX is 1, then the offset is that of the
155 next rule to the right (or below); and so on. */
157 rule_ofs (int rule_idx)
162 /* Returns the offset in struct render_page's cp[axis] array of the rule with
163 index RULE_IDX_R, which counts from the right side (or bottom) of the page
164 left (or up), according to whether AXIS is H or V, respectively. That is,
165 if RULE_IDX_R is 0, then the offset is that of the rightmost or bottommost
166 rule; if RULE_IDX is 1, then the offset is that of the next rule to the left
167 (or above); and so on. */
169 rule_ofs_r (const struct render_page *page, int axis, int rule_idx_r)
171 return (page->n[axis] - rule_idx_r) * 2;
174 /* Returns the offset in struct render_page's cp[axis] array of the cell with
175 index CELL_IDX. That is, if CELL_IDX is 0, then the offset is that of the
176 leftmost or topmost cell; if CELL_IDX is 1, then the offset is that of the
177 next cell to the right (or below); and so on. */
179 cell_ofs (int cell_idx)
181 return cell_idx * 2 + 1;
184 /* Returns the width of PAGE along AXIS from OFS0 to OFS1, exclusive. */
186 axis_width (const struct render_page *page, int axis, int ofs0, int ofs1)
188 return page->cp[axis][ofs1] - page->cp[axis][ofs0];
191 /* Returns the width of the headers in PAGE along AXIS. */
193 headers_width (const struct render_page *page, int axis)
195 int h0 = page->h[axis][0];
196 int w0 = axis_width (page, axis, rule_ofs (0), cell_ofs (h0));
197 int n = page->n[axis];
198 int h1 = page->h[axis][1];
199 int w1 = axis_width (page, axis, rule_ofs_r (page, axis, h1), cell_ofs (n));
203 /* Returns the width of cell X along AXIS in PAGE. */
205 cell_width (const struct render_page *page, int axis, int x)
207 return axis_width (page, axis, cell_ofs (x), cell_ofs (x) + 1);
210 /* Returns the width of rule X along AXIS in PAGE. */
212 rule_width (const struct render_page *page, int axis, int x)
214 return axis_width (page, axis, rule_ofs (x), rule_ofs (x) + 1);
217 /* Returns the width of rule X along AXIS in PAGE. */
219 rule_width_r (const struct render_page *page, int axis, int x)
221 int ofs = rule_ofs_r (page, axis, x);
222 return axis_width (page, axis, ofs, ofs + 1);
225 /* Returns the width of cells X0 through X1, exclusive, along AXIS in PAGE. */
227 joined_width (const struct render_page *page, int axis, int x0, int x1)
229 return axis_width (page, axis, cell_ofs (x0), cell_ofs (x1) - 1);
232 /* Returns the width of the widest cell, excluding headers, along AXIS in
235 max_cell_width (const struct render_page *page, int axis)
237 int n = page->n[axis];
238 int x0 = page->h[axis][0];
239 int x1 = n - page->h[axis][1];
242 for (int x = x0; x < x1; x++)
244 int w = cell_width (page, axis, x);
251 /* A cell that doesn't completely fit on the render_page. */
252 struct render_overflow
254 struct hmap_node node; /* In render_page's 'overflows' hmap. */
256 /* Occupied region of page.
258 d[H][0] is the leftmost column.
259 d[H][1] is the rightmost column, plus 1.
260 d[V][0] is the top row.
261 d[V][1] is the bottom row, plus 1.
263 The cell in its original table might occupy a larger region. This
264 member reflects the size of the cell in the current render_page, after
265 trimming off any rows or columns due to page-breaking. */
268 /* The space that has been trimmed off the cell:
270 overflow[H][0]: space trimmed off its left side.
271 overflow[H][1]: space trimmed off its right side.
272 overflow[V][0]: space trimmed off its top.
273 overflow[V][1]: space trimmed off its bottom.
275 During rendering, this information is used to position the rendered
276 portion of the cell within the available space.
278 When a cell is rendered, sometimes it is permitted to spill over into
279 space that is ordinarily reserved for rules. Either way, this space is
280 still included in overflow values.
282 Suppose, for example, that a cell that joins 2 columns has a width of 60
283 pixels and content "abcdef", that the 2 columns that it joins have
284 widths of 20 and 30 pixels, respectively, and that therefore the rule
285 between the two joined columns has a width of 10 (20 + 10 + 30 = 60).
286 It might render like this, if each character is 10x10, and showing a few
287 extra table cells for context:
295 If this render_page is broken at the rule that separates "gh" from
296 "ijk", then the page that contains the left side of the "abcdef" cell
297 will have overflow[H][1] of 10 + 30 = 40 for its portion of the cell,
298 and the page that contains the right side of the cell will have
299 overflow[H][0] of 20 + 10 = 30. The two resulting pages would look like
317 int overflow[TABLE_N_AXES][2];
320 /* Returns a hash value for (,Y). */
322 hash_cell (int x, int y)
324 return hash_int (x + (y << 16), 0);
327 /* Searches PAGE's set of render_overflow for one whose top-left cell is
328 (X,Y). Returns it, if there is one, otherwise a null pointer. */
329 static const struct render_overflow *
330 find_overflow (const struct render_page *page, int x, int y)
332 if (!hmap_is_empty (&page->overflows))
334 const struct render_overflow *of;
336 HMAP_FOR_EACH_WITH_HASH (of, struct render_overflow, node,
337 hash_cell (x, y), &page->overflows)
338 if (x == of->d[H] && y == of->d[V])
345 /* Row or column dimensions. Used to figure the size of a table in
346 render_page_create() and discarded after that. */
349 /* Width without considering rows (or columns) that span more than one (or
353 /* Width taking spanned rows (or columns) into consideration. */
357 /* Modifies the 'width' members of the N elements of ROWS so that their sum,
358 when added to rule widths RULES[1] through RULES[N - 1] inclusive, is at
361 distribute_spanned_width (int width,
362 struct render_row *rows, const int *rules, int n)
364 /* Sum up the unspanned widths of the N rows for use as weights. */
365 int total_unspanned = 0;
366 for (int x = 0; x < n; x++)
367 total_unspanned += rows[x].unspanned;
368 for (int x = 0; x < n - 1; x++)
369 total_unspanned += rules[x + 1];
370 if (total_unspanned >= width)
373 /* The algorithm used here is based on the following description from HTML 4:
375 For cells that span multiple columns, a simple approach consists of
376 apportioning the min/max widths evenly to each of the constituent
377 columns. A slightly more complex approach is to use the min/max
378 widths of unspanned cells to weight how spanned widths are
379 apportioned. Experiments suggest that a blend of the two approaches
380 gives good results for a wide range of tables.
382 We blend the two approaches half-and-half, except that we cannot use the
383 unspanned weights when 'total_unspanned' is 0 (because that would cause a
386 The calculation we want to do is this:
389 w1 = width * (column's unspanned width) / (total unspanned width)
390 (column's width) = (w0 + w1) / 2
392 We implement it as a precise calculation in integers by multiplying w0 and
393 w1 by the common denominator of all three calculations (d), dividing that
394 out in the column width calculation, and then keeping the remainder for
397 (We actually compute the unspanned width of a column as twice the
398 unspanned width, plus the width of the rule on the left, plus the width of
399 the rule on the right. That way each rule contributes to both the cell on
400 its left and on its right.)
402 long long int d0 = n;
403 long long int d1 = 2LL * MAX (total_unspanned, 1);
404 long long int d = d0 * d1;
405 if (total_unspanned > 0)
407 long long int w = d / 2;
408 for (int x = 0; x < n; x++)
411 if (total_unspanned > 0)
413 long long int unspanned = rows[x].unspanned * 2LL;
415 unspanned += rules[x + 1];
417 unspanned += rules[x];
418 w += width * unspanned * d0;
421 rows[x].width = MAX (rows[x].width, w / d);
422 w -= rows[x].width * d;
426 /* Initializes PAGE->cp[AXIS] from the row widths in ROWS and the rule widths
429 accumulate_row_widths (const struct render_page *page, enum table_axis axis,
430 const struct render_row *rows, const int *rules)
432 int n = page->n[axis];
433 int *cp = page->cp[axis];
435 for (int z = 0; z < n; z++)
437 cp[1] = cp[0] + rules[z];
438 cp[2] = cp[1] + rows[z].width;
441 cp[1] = cp[0] + rules[n];
444 /* Returns the sum of widths of the N ROWS and N+1 RULES. */
446 calculate_table_width (int n, const struct render_row *rows, int *rules)
449 for (int x = 0; x < n; x++)
450 width += rows[x].width;
451 for (int x = 0; x <= n; x++)
457 /* Rendering utility functions. */
459 /* Returns the line style to use for drawing a rule of the given TYPE. */
460 static enum render_line_style
461 rule_to_render_type (unsigned char type)
465 case TABLE_STROKE_NONE:
466 return RENDER_LINE_NONE;
467 case TABLE_STROKE_SOLID:
468 return RENDER_LINE_SINGLE;
469 case TABLE_STROKE_DASHED:
470 return RENDER_LINE_DASHED;
471 case TABLE_STROKE_THICK:
472 return RENDER_LINE_THICK;
473 case TABLE_STROKE_THIN:
474 return RENDER_LINE_THIN;
475 case TABLE_STROKE_DOUBLE:
476 return RENDER_LINE_DOUBLE;
482 /* Returns the width of the rule in TABLE that is at offset Z along axis A, if
483 rendered with PARAMS. */
485 measure_rule (const struct render_params *params, const struct table *table,
486 enum table_axis a, int z)
488 enum table_axis b = !a;
490 /* Determine all types of rules that are present, as a bitmap in 'rules'
491 where rule type 't' is present if bit 2**t is set. */
492 struct cell_color color;
493 unsigned int rules = 0;
496 for (d[b] = 0; d[b] < table->n[b]; d[b]++)
497 rules |= 1u << table_get_rule (table, a, d[H], d[V], &color);
499 /* Turn off TABLE_STROKE_NONE because it has width 0 and we needn't bother.
500 However, if the device doesn't support margins, make sure that there is at
501 least a small gap between cells (but we don't need any at the left or
502 right edge of the table). */
503 if (rules & (1u << TABLE_STROKE_NONE))
505 rules &= ~(1u << TABLE_STROKE_NONE);
506 if (z > 0 && z < table->n[a] && !params->supports_margins && a == H)
507 rules |= 1u << TABLE_STROKE_SOLID;
510 /* Calculate maximum width of the rules that are present. */
512 for (size_t i = 0; i < TABLE_N_STROKES; i++)
513 if (rules & (1u << i))
514 width = MAX (width, params->line_widths[rule_to_render_type (i)]);
518 /* Allocates and returns a new render_page using PARAMS and TABLE. Allocates
519 space for rendering a table with dimensions given in N. The caller must
520 initialize most of the members itself. */
521 static struct render_page *
522 render_page_allocate__ (const struct render_params *params,
523 struct table *table, int n[TABLE_N_AXES])
525 struct render_page *page = xmalloc (sizeof *page);
526 page->params = params;
532 for (int i = 0; i < TABLE_N_AXES; i++)
534 page->cp[i] = xmalloc ((2 * n[i] + 2) * sizeof *page->cp[i]);
535 page->join_crossing[i] = xzalloc ((n[i] + 1)
536 * sizeof *page->join_crossing[i]);
539 hmap_init (&page->overflows);
540 memset (page->is_edge_cutoff, 0, sizeof page->is_edge_cutoff);
545 /* Allocates and returns a new render_page using PARAMS and TABLE. Allocates
546 space for all of the members of the new page, but the caller must initialize
547 the 'cp' member itself. */
548 static struct render_page *
549 render_page_allocate (const struct render_params *params, struct table *table)
551 struct render_page *page = render_page_allocate__ (params, table, table->n);
552 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
554 page->h[a][0] = table->h[a][0];
555 page->h[a][1] = table->h[a][1];
556 page->r[a][0] = table->h[a][0];
557 page->r[a][1] = table->n[a] - table->h[a][1];
562 /* Allocates and returns a new render_page for PARAMS and TABLE, initializing
563 cp[H] in the new page from ROWS and RULES. The caller must still initialize
565 static struct render_page *
566 create_page_with_exact_widths (const struct render_params *params,
568 const struct render_row *rows, int *rules)
570 struct render_page *page = render_page_allocate (params, table);
571 accumulate_row_widths (page, H, rows, rules);
575 /* Allocates and returns a new render_page for PARAMS and TABLE.
577 Initializes cp[H] in the new page by setting the width of each row 'i' to
578 somewhere between the minimum cell width ROW_MIN[i].width and the maximum
579 ROW_MAX[i].width. Sets the width of rules to those in RULES.
581 W_MIN is the sum of ROWS_MIN[].width.
583 W_MAX is the sum of ROWS_MAX[].width.
585 The caller must still initialize cp[V]. */
586 static struct render_page *
587 create_page_with_interpolated_widths (const struct render_params *params,
589 const struct render_row *rows_min,
590 const struct render_row *rows_max,
591 int w_min, int w_max, const int *rules)
593 const int n = table->n[H];
594 const long long int avail = params->size[H] - w_min;
595 const long long int wanted = w_max - w_min;
599 struct render_page *page = render_page_allocate (params, table);
601 int *cph = page->cp[H];
603 long long int w = wanted / 2;
604 for (int x = 0; x < n; x++)
606 w += avail * (rows_max[x].width - rows_min[x].width);
607 int extra = w / wanted;
610 cph[1] = cph[0] + rules[x];
611 cph[2] = cph[1] + rows_min[x].width + extra;
614 cph[1] = cph[0] + rules[n];
616 assert (page->cp[H][n * 2 + 1] == params->size[H]);
621 set_join_crossings (struct render_page *page, enum table_axis axis,
622 const struct table_cell *cell, int *rules)
624 for (int z = cell->d[axis][0] + 1; z <= cell->d[axis][1] - 1; z++)
625 page->join_crossing[axis][z] = rules[z];
628 /* Maps a contiguous range of cells from a page to the underlying table along
629 the horizpntal or vertical dimension. */
632 int p0; /* First ordinate in the page. */
633 int t0; /* First ordinate in the table. */
634 int n; /* Number of ordinates in page and table. */
637 /* Initializes M to a mapping from PAGE to PAGE->table along axis A. The
638 mapping includes ordinate Z (in PAGE). */
640 get_map (const struct render_page *page, enum table_axis a, int z,
643 if (z < page->h[a][0])
647 m->n = page->h[a][0];
649 else if (z < page->n[a] - page->h[a][1])
651 m->p0 = page->h[a][0];
652 m->t0 = page->r[a][0];
653 m->n = page->r[a][1] - page->r[a][0];
657 m->p0 = page->n[a] - page->h[a][1];
658 m->t0 = page->table->n[a] - page->table->h[a][1];
659 m->n = page->h[a][1];
663 /* Initializes CELL with the contents of the table cell at column X and row Y
664 within PAGE. When CELL is no longer needed, the caller is responsible for
665 freeing it by calling table_cell_free(CELL).
667 The caller must ensure that CELL is destroyed before TABLE is unref'ed.
669 This is equivalent to table_get_cell(), except X and Y are in terms of the
670 page's rows and columns rather than the underlying table's. */
672 render_get_cell (const struct render_page *page, int x, int y,
673 struct table_cell *cell)
675 int d[TABLE_N_AXES] = { [H] = x, [V] = y };
676 struct map map[TABLE_N_AXES];
678 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
680 struct map *m = &map[a];
681 get_map (page, a, d[a], m);
682 d[a] += m->t0 - m->p0;
684 table_get_cell (page->table, d[H], d[V], cell);
686 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
688 struct map *m = &map[a];
690 for (int i = 0; i < 2; i++)
691 cell->d[a][i] -= m->t0 - m->p0;
692 cell->d[a][0] = MAX (cell->d[a][0], m->p0);
693 cell->d[a][1] = MIN (cell->d[a][1], m->p0 + m->n);
697 /* Creates and returns a new render_page for rendering TABLE on a device
700 The new render_page will be suitable for rendering on a device whose page
701 size is PARAMS->size, but the caller is responsible for actually breaking it
702 up to fit on such a device, using the render_break abstraction. */
703 static struct render_page *
704 render_page_create (const struct render_params *params, struct table *table,
709 int nc = table_nc (table);
710 int nr = table_nr (table);
712 /* Figure out rule widths. */
713 int *rules[TABLE_N_AXES];
714 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
716 int n = table->n[axis] + 1;
718 rules[axis] = xnmalloc (n, sizeof *rules);
719 for (int z = 0; z < n; z++)
720 rules[axis][z] = measure_rule (params, table, axis, z);
723 /* Calculate minimum and maximum widths of cells that do not
724 span multiple columns. */
725 struct render_row *columns[2];
726 for (int i = 0; i < 2; i++)
727 columns[i] = xzalloc (nc * sizeof *columns[i]);
728 for (int y = 0; y < nr; y++)
729 for (int x = 0; x < nc;)
731 struct table_cell cell;
733 table_get_cell (table, x, y, &cell);
734 if (y == cell.d[V][0])
736 if (table_cell_colspan (&cell) == 1)
739 params->ops->measure_cell_width (params->aux, &cell,
741 for (int i = 0; i < 2; i++)
742 if (columns[i][x].unspanned < w[i])
743 columns[i][x].unspanned = w[i];
749 /* Distribute widths of spanned columns. */
750 for (int i = 0; i < 2; i++)
751 for (int x = 0; x < nc; x++)
752 columns[i][x].width = columns[i][x].unspanned;
753 for (int y = 0; y < nr; y++)
754 for (int x = 0; x < nc;)
756 struct table_cell cell;
758 table_get_cell (table, x, y, &cell);
759 if (y == cell.d[V][0] && table_cell_colspan (&cell) > 1)
763 params->ops->measure_cell_width (params->aux, &cell,
765 for (int i = 0; i < 2; i++)
766 distribute_spanned_width (w[i], &columns[i][cell.d[H][0]],
767 rules[H], table_cell_colspan (&cell));
772 for (int i = 0; i < 2; i++)
773 distribute_spanned_width (min_width, &columns[i][0], rules[H], nc);
775 /* In pathological cases, spans can cause the minimum width of a column to
776 exceed the maximum width. This bollixes our interpolation algorithm
777 later, so fix it up. */
778 for (int i = 0; i < nc; i++)
779 if (columns[MIN][i].width > columns[MAX][i].width)
780 columns[MAX][i].width = columns[MIN][i].width;
782 /* Decide final column widths. */
784 for (int i = 0; i < 2; i++)
785 table_widths[i] = calculate_table_width (table_nc (table),
786 columns[i], rules[H]);
788 struct render_page *page;
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 struct render_row *rows = xzalloc (nr * sizeof *rows);
812 for (int y = 0; y < nr; y++)
813 for (int x = 0; x < nc;)
815 struct render_row *r = &rows[y];
816 struct table_cell cell;
818 render_get_cell (page, x, y, &cell);
819 if (y == cell.d[V][0])
821 if (table_cell_rowspan (&cell) == 1)
823 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
824 int h = params->ops->measure_cell_height (params->aux,
826 if (h > r->unspanned)
827 r->unspanned = r->width = h;
830 set_join_crossings (page, V, &cell, rules[V]);
832 if (table_cell_colspan (&cell) > 1)
833 set_join_crossings (page, H, &cell, rules[H]);
837 for (int i = 0; i < 2; i++)
840 /* Distribute heights of spanned rows. */
841 for (int y = 0; y < nr; y++)
842 for (int x = 0; x < nc;)
844 struct table_cell cell;
846 render_get_cell (page, x, y, &cell);
847 if (y == cell.d[V][0] && table_cell_rowspan (&cell) > 1)
849 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
850 int h = params->ops->measure_cell_height (params->aux, &cell, w);
851 distribute_spanned_width (h, &rows[cell.d[V][0]], rules[V],
852 table_cell_rowspan (&cell));
857 /* Decide final row heights. */
858 accumulate_row_widths (page, V, rows, rules[V]);
861 /* Measure headers. If they are "too big", get rid of them. */
862 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
864 int hw = headers_width (page, axis);
865 if (hw * 2 >= page->params->size[axis]
866 || hw + max_cell_width (page, axis) > page->params->size[axis])
868 page->h[axis][0] = page->h[axis][1] = 0;
869 page->r[axis][0] = 0;
870 page->r[axis][1] = page->n[axis];
880 /* Increases PAGE's reference count. */
882 render_page_ref (const struct render_page *page_)
884 struct render_page *page = CONST_CAST (struct render_page *, page_);
889 /* Decreases PAGE's reference count and destroys PAGE if this causes the
890 reference count to fall to zero. */
892 render_page_unref (struct render_page *page)
894 if (page != NULL && --page->ref_cnt == 0)
896 struct render_overflow *overflow, *next;
897 HMAP_FOR_EACH_SAFE (overflow, next, struct render_overflow, node,
900 hmap_destroy (&page->overflows);
902 table_unref (page->table);
904 for (int i = 0; i < TABLE_N_AXES; ++i)
906 free (page->join_crossing[i]);
914 /* Returns the size of PAGE along AXIS. (This might be larger than the page
915 size specified in the parameters passed to render_page_create(). Use a
916 render_break to break up a render_page into page-sized chunks.) */
918 render_page_get_size (const struct render_page *page, enum table_axis axis)
920 return page->cp[axis][page->n[axis] * 2 + 1];
924 render_page_get_best_breakpoint (const struct render_page *page, int height)
926 /* If there's no room for at least the top row and the rules above and below
927 it, don't include any of the table. */
928 if (page->cp[V][3] > height)
931 /* Otherwise include as many rows and rules as we can. */
932 for (int y = 5; y <= 2 * page->n[V] + 1; y += 2)
933 if (page->cp[V][y] > height)
934 return page->cp[V][y - 2];
938 /* Drawing render_pages. */
940 /* This is like table_get_rule() except:
942 - D is in terms of the page's rows and column rather than the underlying
945 - The result is in the form of a render_line_style. */
946 static enum render_line_style
947 get_rule (const struct render_page *page, enum table_axis axis,
948 const int d_[TABLE_N_AXES], struct cell_color *color)
950 int d[TABLE_N_AXES] = { d_[0] / 2, d_[1] / 2 };
953 enum table_axis a = axis;
954 if (d[a] < page->h[a][0])
956 else if (d[a] <= page->n[a] - page->h[a][1])
958 if (page->h[a][0] && d[a] == page->h[a][0])
960 else if (page->h[a][1] && d[a] == page->n[a] - page->h[a][1])
961 d2 = page->table->n[a] - page->h[a][1];
962 d[a] += page->r[a][0] - page->h[a][0];
965 d[a] += ((page->table->n[a] - page->table->h[a][1])
966 - (page->n[a] - page->h[a][1]));
968 enum table_axis b = !axis;
970 get_map (page, b, d[b], &m);
973 int r = table_get_rule (page->table, axis, d[H], d[V], color);
977 int r2 = table_get_rule (page->table, axis, d[H], d[V], color);
978 r = table_stroke_combine (r, r2);
980 return rule_to_render_type (r);
990 render_direction_rtl (void)
992 /* TRANSLATORS: Do not translate this string. If the script of your language
993 reads from right to left (eg Persian, Arabic, Hebrew etc), then replace
994 this string with "output-direction-rtl". Otherwise either leave it
995 untranslated or copy it verbatim. */
996 const char *dir = _("output-direction-ltr");
997 if (0 == strcmp ("output-direction-rtl", dir))
1000 if (0 != strcmp ("output-direction-ltr", dir))
1001 fprintf (stderr, "This localisation has been incorrectly translated. "
1002 "Complain to the translator.\n");
1008 render_rule (const struct render_page *page, const int ofs[TABLE_N_AXES],
1009 const int d[TABLE_N_AXES])
1011 enum render_line_style styles[TABLE_N_AXES][2];
1012 struct cell_color colors[TABLE_N_AXES][2];
1014 for (enum table_axis a = 0; a < TABLE_N_AXES; a++)
1016 enum table_axis b = !a;
1018 styles[a][0] = styles[a][1] = RENDER_LINE_NONE;
1021 || (page->is_edge_cutoff[a][0] && d[a] == 0)
1022 || (page->is_edge_cutoff[a][1] && d[a] == page->n[a] * 2))
1029 int e[TABLE_N_AXES];
1033 styles[a][0] = get_rule (page, a, e, &colors[a][0]);
1036 if (d[b] / 2 < page->n[b])
1037 styles[a][1] = get_rule (page, a, d, &colors[a][1]);
1041 styles[a][0] = styles[a][1] = get_rule (page, a, d, &colors[a][0]);
1042 colors[a][1] = colors[a][0];
1046 if (styles[H][0] != RENDER_LINE_NONE || styles[H][1] != RENDER_LINE_NONE
1047 || styles[V][0] != RENDER_LINE_NONE || styles[V][1] != RENDER_LINE_NONE)
1049 int bb[TABLE_N_AXES][2];
1051 bb[H][0] = ofs[H] + page->cp[H][d[H]];
1052 bb[H][1] = ofs[H] + page->cp[H][d[H] + 1];
1053 if (page->params->rtl)
1055 int temp = bb[H][0];
1056 bb[H][0] = render_page_get_size (page, H) - bb[H][1];
1057 bb[H][1] = render_page_get_size (page, H) - temp;
1059 bb[V][0] = ofs[V] + page->cp[V][d[V]];
1060 bb[V][1] = ofs[V] + page->cp[V][d[V] + 1];
1061 page->params->ops->draw_line (page->params->aux, bb, styles, colors);
1066 render_cell (const struct render_page *page, const int ofs[TABLE_N_AXES],
1067 const struct table_cell *cell)
1069 int bb[TABLE_N_AXES][2];
1070 int clip[TABLE_N_AXES][2];
1072 bb[H][0] = clip[H][0] = ofs[H] + page->cp[H][cell->d[H][0] * 2 + 1];
1073 bb[H][1] = clip[H][1] = ofs[H] + page->cp[H][cell->d[H][1] * 2];
1074 if (page->params->rtl)
1076 int temp = bb[H][0];
1077 bb[H][0] = clip[H][0] = render_page_get_size (page, H) - bb[H][1];
1078 bb[H][1] = clip[H][1] = render_page_get_size (page, H) - temp;
1080 bb[V][0] = clip[V][0] = ofs[V] + page->cp[V][cell->d[V][0] * 2 + 1];
1081 bb[V][1] = clip[V][1] = ofs[V] + page->cp[V][cell->d[V][1] * 2];
1083 enum table_valign valign = cell->style->cell_style.valign;
1084 int valign_offset = 0;
1085 if (valign != TABLE_VALIGN_TOP)
1087 int height = page->params->ops->measure_cell_height (
1088 page->params->aux, cell, bb[H][1] - bb[H][0]);
1089 int extra = bb[V][1] - bb[V][0] - height;
1092 if (valign == TABLE_VALIGN_CENTER)
1094 valign_offset += extra;
1098 const struct render_overflow *of = find_overflow (
1099 page, cell->d[H][0], cell->d[V][0]);
1101 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
1103 if (of->overflow[axis][0])
1105 bb[axis][0] -= of->overflow[axis][0];
1106 if (cell->d[axis][0] == 0 && !page->is_edge_cutoff[axis][0])
1107 clip[axis][0] = ofs[axis] + page->cp[axis][cell->d[axis][0] * 2];
1109 if (of->overflow[axis][1])
1111 bb[axis][1] += of->overflow[axis][1];
1112 if (cell->d[axis][1] == page->n[axis]
1113 && !page->is_edge_cutoff[axis][1])
1114 clip[axis][1] = ofs[axis] + page->cp[axis][cell->d[axis][1] * 2
1119 int spill[TABLE_N_AXES][2];
1120 for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
1122 spill[axis][0] = rule_width (page, axis, cell->d[axis][0]) / 2;
1123 spill[axis][1] = rule_width (page, axis, cell->d[axis][1]) / 2;
1126 int color_idx = (cell->d[V][0] < page->h[V][0]
1127 || page->n[V] - (cell->d[V][0] + 1) < page->h[V][1]
1129 : (cell->d[V][0] - page->h[V][0]) & 1);
1130 page->params->ops->draw_cell (page->params->aux, cell, color_idx,
1131 bb, valign_offset, spill, clip);
1134 /* Draws the cells of PAGE indicated in BB. */
1136 render_page_draw_cells (const struct render_page *page,
1137 int ofs[TABLE_N_AXES], int bb[TABLE_N_AXES][2])
1139 for (int y = bb[V][0]; y < bb[V][1]; y++)
1140 for (int x = bb[H][0]; x < bb[H][1];)
1141 if (!is_rule (x) && !is_rule (y))
1143 struct table_cell cell;
1145 render_get_cell (page, x / 2, y / 2, &cell);
1146 if (y / 2 == bb[V][0] / 2 || y / 2 == cell.d[V][0])
1147 render_cell (page, ofs, &cell);
1148 x = rule_ofs (cell.d[H][1]);
1153 for (int y = bb[V][0]; y < bb[V][1]; y++)
1154 for (int x = bb[H][0]; x < bb[H][1]; x++)
1155 if (is_rule (x) || is_rule (y))
1157 int d[TABLE_N_AXES];
1160 render_rule (page, ofs, d);
1164 /* Renders PAGE, by calling the 'draw_line' and 'draw_cell' functions from the
1165 render_params provided to render_page_create(). */
1167 render_page_draw (const struct render_page *page, int ofs[TABLE_N_AXES])
1169 int bb[TABLE_N_AXES][2];
1172 bb[H][1] = page->n[H] * 2 + 1;
1174 bb[V][1] = page->n[V] * 2 + 1;
1176 render_page_draw_cells (page, ofs, bb);
1179 /* Returns the greatest value i, 0 <= i < n, such that cp[i] <= x0. */
1181 get_clip_min_extent (int x0, const int cp[], int n)
1188 int middle = low + (high - low) / 2;
1190 if (cp[middle] <= x0)
1202 /* Returns the least value i, 0 <= i < n, such that cp[i] >= x1. */
1204 get_clip_max_extent (int x1, const int cp[], int n)
1211 int middle = low + (high - low) / 2;
1213 if (cp[middle] >= x1)
1214 best = high = middle;
1219 while (best > 0 && cp[best - 1] == cp[best])
1225 /* Renders the cells of PAGE that intersect (X,Y)-(X+W,Y+H), by calling the
1226 'draw_line' and 'draw_cell' functions from the render_params provided to
1227 render_page_create(). */
1229 render_page_draw_region (const struct render_page *page,
1230 int ofs[TABLE_N_AXES], int clip[TABLE_N_AXES][2])
1232 int bb[TABLE_N_AXES][2];
1234 bb[H][0] = get_clip_min_extent (clip[H][0], page->cp[H], page->n[H] * 2 + 1);
1235 bb[H][1] = get_clip_max_extent (clip[H][1], page->cp[H], page->n[H] * 2 + 1);
1236 bb[V][0] = get_clip_min_extent (clip[V][0], page->cp[V], page->n[V] * 2 + 1);
1237 bb[V][1] = get_clip_max_extent (clip[V][1], page->cp[V], page->n[V] * 2 + 1);
1239 render_page_draw_cells (page, ofs, bb);
1242 /* Breaking up tables to fit on a page. */
1244 /* An iterator for breaking render_pages into smaller chunks. */
1247 struct render_page *page; /* Page being broken up. */
1248 enum table_axis axis; /* Axis along which 'page' is being broken. */
1249 int z; /* Next cell along 'axis'. */
1250 int pixel; /* Pixel offset within cell 'z' (usually 0). */
1251 int hw; /* Width of headers of 'page' along 'axis'. */
1254 static int needed_size (const struct render_break *, int cell);
1255 static bool cell_is_breakable (const struct render_break *, int cell);
1256 static struct render_page *render_page_select (const struct render_page *,
1261 /* Initializes render_break B for breaking PAGE along AXIS.
1262 Takes ownership of PAGE. */
1264 render_break_init (struct render_break *b, struct render_page *page,
1265 enum table_axis axis)
1269 b->z = page->h[axis][0];
1271 b->hw = headers_width (page, axis);
1274 /* Initializes B as a render_break structure for which
1275 render_break_has_next() always returns false. */
1277 render_break_init_empty (struct render_break *b)
1280 b->axis = TABLE_HORZ;
1286 /* Frees B and unrefs the render_page that it owns. */
1288 render_break_destroy (struct render_break *b)
1292 render_page_unref (b->page);
1297 /* Returns true if B still has cells that are yet to be returned,
1298 false if all of B's page has been processed. */
1300 render_break_has_next (const struct render_break *b)
1302 const struct render_page *page = b->page;
1303 enum table_axis axis = b->axis;
1305 return page != NULL && b->z < page->n[axis] - page->h[axis][1];
1308 /* Returns a new render_page that is up to SIZE pixels wide along B's axis.
1309 Returns a null pointer if B has already been completely broken up, or if
1310 SIZE is too small to reasonably render any cells. The latter will never
1311 happen if SIZE is at least as large as the page size passed to
1312 render_page_create() along B's axis. */
1313 static struct render_page *
1314 render_break_next (struct render_break *b, int size)
1316 const struct render_page *page = b->page;
1317 enum table_axis axis = b->axis;
1318 struct render_page *subpage;
1320 if (!render_break_has_next (b))
1325 for (z = b->z; z < page->n[axis] - page->h[axis][1]; z++)
1327 int needed = needed_size (b, z + 1);
1330 if (cell_is_breakable (b, z))
1332 /* If there is no right header and we render a partial cell on
1333 the right side of the body, then we omit the rightmost rule of
1334 the body. Otherwise the rendering is deceptive because it
1335 looks like the whole cell is present instead of a partial
1338 This is similar to code for the left side in needed_size(). */
1339 int rule_allowance = (page->h[axis][1]
1341 : rule_width (page, axis, z));
1343 /* The amount that, if we added cell 'z', the rendering would
1344 overfill the allocated 'size'. */
1345 int overhang = needed - size - rule_allowance;
1347 /* The width of cell 'z'. */
1348 int cell_size = cell_width (page, axis, z);
1350 /* The amount trimmed off the left side of 'z',
1351 and the amount left to render. */
1352 int cell_ofs = z == b->z ? b->pixel : 0;
1353 int cell_left = cell_size - cell_ofs;
1355 /* A small but visible width. */
1356 int em = page->params->font_size[axis];
1358 /* If some of the cell remains to render,
1359 and there would still be some of the cell left afterward,
1360 then partially render that much of the cell. */
1361 pixel = (cell_left && cell_left > overhang
1362 ? cell_left - overhang + cell_ofs
1365 /* If there would be only a tiny amount of the cell left after
1366 rendering it partially, reduce the amount rendered slightly
1367 to make the output look a little better. */
1368 if (pixel + em > cell_size)
1369 pixel = MAX (pixel - em, 0);
1371 /* If we're breaking vertically, then consider whether the cells
1372 being broken have a better internal breakpoint than the exact
1373 number of pixels available, which might look bad e.g. because
1374 it breaks in the middle of a line of text. */
1375 if (axis == TABLE_VERT && page->params->ops->adjust_break)
1376 for (int x = 0; x < page->n[H];)
1378 struct table_cell cell;
1380 render_get_cell (page, x, z, &cell);
1381 int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
1382 int better_pixel = page->params->ops->adjust_break (
1383 page->params->aux, &cell, w, pixel);
1386 if (better_pixel < pixel)
1388 if (better_pixel > (z == b->z ? b->pixel : 0))
1390 pixel = better_pixel;
1393 else if (better_pixel == 0 && z != b->z)
1405 if (z == b->z && !pixel)
1408 subpage = render_page_select (page, axis, b->z, b->pixel,
1410 pixel ? cell_width (page, axis, z) - pixel
1417 /* Returns the width that would be required along B's axis to render a page
1418 from B's current position up to but not including CELL. */
1420 needed_size (const struct render_break *b, int cell)
1422 const struct render_page *page = b->page;
1423 enum table_axis axis = b->axis;
1425 /* Width of left header not including its rightmost rule. */
1426 int size = axis_width (page, axis, 0, rule_ofs (page->h[axis][0]));
1428 /* If we have a pixel offset and there is no left header, then we omit the
1429 leftmost rule of the body. Otherwise the rendering is deceptive because
1430 it looks like the whole cell is present instead of a partial cell.
1432 Otherwise (if there are headers) we will be merging two rules: the
1433 rightmost rule in the header and the leftmost rule in the body. We assume
1434 that the width of a merged rule is the larger of the widths of either rule
1436 if (b->pixel == 0 || page->h[axis][0])
1437 size += MAX (rule_width (page, axis, page->h[axis][0]),
1438 rule_width (page, axis, b->z));
1440 /* Width of body, minus any pixel offset in the leftmost cell. */
1441 size += joined_width (page, axis, b->z, cell) - b->pixel;
1443 /* Width of rightmost rule in body merged with leftmost rule in headers. */
1444 size += MAX (rule_width_r (page, axis, page->h[axis][1]),
1445 rule_width (page, axis, cell));
1447 /* Width of right header not including its leftmost rule. */
1448 size += axis_width (page, axis, rule_ofs_r (page, axis, page->h[axis][1]),
1449 rule_ofs_r (page, axis, 0));
1451 /* Join crossing. */
1452 if (page->h[axis][0] && page->h[axis][1])
1453 size += page->join_crossing[axis][b->z];
1458 /* Returns true if CELL along B's axis may be broken across a page boundary.
1460 This is just a heuristic. Breaking cells across page boundaries can save
1461 space, but it looks ugly. */
1463 cell_is_breakable (const struct render_break *b, int cell)
1465 const struct render_page *page = b->page;
1466 enum table_axis axis = b->axis;
1468 return cell_width (page, axis, cell) >= page->params->min_break[axis];
1475 const struct render_params *params;
1477 /* An array of "render_page"s to be rendered, in order, vertically. From
1478 the user's perspective, there's only one table per render_pager, but the
1479 implementation treats the title, table body, caption, footnotes,
1480 etc. each as a table, and that's why we have an array here. */
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 table *t = table_create (1, n_footnotes, 0, 0, 0, 0);
1519 for (size_t i = 0; i < n_footnotes; i++)
1521 table_text_format (t, 0, i, 0, "%s. %s", f[i]->marker, f[i]->content);
1522 table_add_style (t, 0, i, f[i]->style);
1524 render_pager_add_table (p, t, 0);
1530 add_text_page (struct render_pager *p, const struct table_item_text *t,
1536 struct table *tab = table_create (1, 1, 0, 0, 0, 0);
1537 table_text (tab, 0, 0, 0, t->content);
1538 for (size_t i = 0; i < t->n_footnotes; i++)
1539 table_add_footnote (tab, 0, 0, t->footnotes[i]);
1541 tab->styles[0] = table_area_style_clone (tab->container, t->style);
1542 render_pager_add_table (p, tab, min_width);
1546 add_layers_page (struct render_pager *p,
1547 const struct table_item_layers *layers, int min_width)
1552 struct table *tab = table_create (1, layers->n_layers, 0, 0, 0, 0);
1553 for (size_t i = 0; i < layers->n_layers; i++)
1555 const struct table_item_layer *layer = &layers->layers[i];
1556 table_text (tab, 0, i, 0, layer->content);
1557 for (size_t j = 0; j < layer->n_footnotes; j++)
1558 table_add_footnote (tab, 0, i, layer->footnotes[j]);
1561 tab->styles[0] = table_area_style_clone (tab->container, layers->style);
1562 render_pager_add_table (p, tab, min_width);
1565 /* Creates and returns a new render_pager for rendering TABLE_ITEM on the
1566 device with the given PARAMS. */
1567 struct render_pager *
1568 render_pager_create (const struct render_params *params,
1569 const struct table_item *table_item)
1571 const struct table *table = table_item_get_table (table_item);
1573 struct render_pager *p = xzalloc (sizeof *p);
1576 struct render_page *page = render_page_create (params, table_ref (table), 0);
1577 struct render_break b;
1578 render_break_init (&b, page, H);
1579 struct render_page *subpage = render_break_next (&b, p->params->size[H]);
1580 int title_width = subpage ? subpage->cp[H][2 * subpage->n[H] + 1] : 0;
1581 render_page_unref (subpage);
1582 render_break_destroy (&b);
1585 add_text_page (p, table_item_get_title (table_item), title_width);
1588 add_layers_page (p, table_item_get_layers (table_item), title_width);
1591 render_pager_add_table (p, table_ref (table_item_get_table (table_item)), 0);
1594 add_text_page (p, table_item_get_caption (table_item), 0);
1597 add_footnote_page (p, table_item);
1599 render_pager_start_page (p);
1606 render_pager_destroy (struct render_pager *p)
1610 render_break_destroy (&p->x_break);
1611 render_break_destroy (&p->y_break);
1612 for (size_t i = 0; i < p->n_pages; i++)
1613 render_page_unref (p->pages[i]);
1619 /* Returns true if P has content remaining to render, false if rendering is
1622 render_pager_has_next (const struct render_pager *p_)
1624 struct render_pager *p = CONST_CAST (struct render_pager *, p_);
1626 while (!render_break_has_next (&p->y_break))
1628 render_break_destroy (&p->y_break);
1629 if (!render_break_has_next (&p->x_break))
1631 render_break_destroy (&p->x_break);
1632 if (p->cur_page >= p->n_pages)
1634 render_break_init_empty (&p->x_break);
1635 render_break_init_empty (&p->y_break);
1638 render_pager_start_page (p);
1642 &p->y_break, render_break_next (&p->x_break, p->params->size[H]), V);
1647 /* Draws a chunk of content from P to fit in a space that has vertical size
1648 SPACE and the horizontal size specified in the render_params passed to
1649 render_page_create(). Returns the amount of space actually used by the
1650 rendered chunk, which will be 0 if SPACE is too small to render anything or
1651 if no content remains (use render_pager_has_next() to distinguish these
1654 render_pager_draw_next (struct render_pager *p, int space)
1656 int ofs[TABLE_N_AXES] = { 0, 0 };
1657 size_t start_page = SIZE_MAX;
1659 while (render_pager_has_next (p))
1661 if (start_page == p->cur_page)
1663 start_page = p->cur_page;
1665 struct render_page *page
1666 = render_break_next (&p->y_break, space - ofs[V]);
1670 render_page_draw (page, ofs);
1671 ofs[V] += render_page_get_size (page, V);
1672 render_page_unref (page);
1677 /* Draws all of P's content. */
1679 render_pager_draw (const struct render_pager *p)
1681 render_pager_draw_region (p, 0, 0, INT_MAX, INT_MAX);
1684 /* Draws the region of P's content that lies in the region (X,Y)-(X+W,Y+H).
1685 Some extra content might be drawn; the device should perform clipping as
1688 render_pager_draw_region (const struct render_pager *p,
1689 int x, int y, int w, int h)
1691 int ofs[TABLE_N_AXES] = { 0, 0 };
1692 int clip[TABLE_N_AXES][2];
1696 for (size_t i = 0; i < p->n_pages; i++)
1698 const struct render_page *page = p->pages[i];
1699 int size = render_page_get_size (page, V);
1701 clip[V][0] = MAX (y, ofs[V]) - ofs[V];
1702 clip[V][1] = MIN (y + h, ofs[V] + size) - ofs[V];
1703 if (clip[V][1] > clip[V][0])
1704 render_page_draw_region (page, ofs, clip);
1710 /* Returns the size of P's content along AXIS; i.e. the content's width if AXIS
1711 is TABLE_HORZ and its length if AXIS is TABLE_VERT. */
1713 render_pager_get_size (const struct render_pager *p, enum table_axis axis)
1717 for (size_t i = 0; i < p->n_pages; i++)
1719 int subsize = render_page_get_size (p->pages[i], axis);
1720 size = axis == H ? MAX (size, subsize) : size + subsize;
1727 render_pager_get_best_breakpoint (const struct render_pager *p, int height)
1732 for (i = 0; i < p->n_pages; i++)
1734 int size = render_page_get_size (p->pages[i], V);
1735 if (y + size >= height)
1736 return render_page_get_best_breakpoint (p->pages[i], height - y) + y;
1743 /* render_page_select() and helpers. */
1745 struct render_page_selection
1747 const struct render_page *page; /* Page whose slice we are selecting. */
1748 struct render_page *subpage; /* New page under construction. */
1749 enum table_axis a; /* Axis of 'page' along which 'subpage' is a slice. */
1750 enum table_axis b; /* The opposite of 'a'. */
1751 int z0; /* First cell along 'a' being selected. */
1752 int z1; /* Last cell being selected, plus 1. */
1753 int p0; /* Number of pixels to trim off left side of z0. */
1754 int p1; /* Number of pixels to trim off right side of z1-1. */
1757 static void cell_to_subpage (struct render_page_selection *,
1758 const struct table_cell *,
1759 int subcell[TABLE_N_AXES]);
1760 static const struct render_overflow *find_overflow_for_cell (
1761 struct render_page_selection *, const struct table_cell *);
1762 static struct render_overflow *insert_overflow (struct render_page_selection *,
1763 const struct table_cell *);
1765 /* Creates and returns a new render_page whose contents are a subregion of
1766 PAGE's contents. The new render_page includes cells Z0 through Z1
1767 (exclusive) along AXIS, plus any headers on AXIS.
1769 If P0 is nonzero, then it is a number of pixels to exclude from the left or
1770 top (according to AXIS) of cell Z0. Similarly, P1 is a number of pixels to
1771 exclude from the right or bottom of cell Z1 - 1. (P0 and P1 are used to
1772 render cells that are too large to fit on a single page.)
1774 The whole of axis !AXIS is included. (The caller may follow up with another
1775 call to render_page_select() to select on !AXIS to select on that axis as
1778 The caller retains ownership of PAGE, which is not modified. */
1779 static struct render_page *
1780 render_page_select (const struct render_page *page, enum table_axis axis,
1781 int z0, int p0, int z1, int p1)
1783 enum table_axis a = axis;
1784 enum table_axis b = !a;
1786 /* Optimize case where all of PAGE is selected by just incrementing the
1788 if (z0 == page->h[a][0] && p0 == 0
1789 && z1 == page->n[a] - page->h[a][1] && p1 == 0)
1791 struct render_page *page_rw = CONST_CAST (struct render_page *, page);
1796 /* Allocate subpage. */
1797 int trim[2] = { z0 - page->h[a][0], (page->n[a] - page->h[a][1]) - z1 };
1798 int n[TABLE_N_AXES] = { [H] = page->n[H], [V] = page->n[V] };
1799 n[a] -= trim[0] + trim[1];
1800 struct render_page *subpage = render_page_allocate__ (
1801 page->params, table_ref (page->table), n);
1802 for (enum table_axis k = 0; k < TABLE_N_AXES; k++)
1804 subpage->h[k][0] = page->h[k][0];
1805 subpage->h[k][1] = page->h[k][1];
1806 subpage->r[k][0] = page->r[k][0];
1807 subpage->r[k][1] = page->r[k][1];
1809 subpage->r[a][0] += trim[0];
1810 subpage->r[a][1] -= trim[1];
1812 /* An edge is cut off if it was cut off in PAGE or if we're trimming pixels
1813 off that side of the page and there are no headers. */
1814 subpage->is_edge_cutoff[a][0] =
1815 subpage->h[a][0] == 0 && (p0 || (z0 == 0 && page->is_edge_cutoff[a][0]));
1816 subpage->is_edge_cutoff[a][1] =
1817 subpage->h[a][1] == 0 && (p1 || (z1 == page->n[a]
1818 && page->is_edge_cutoff[a][1]));
1819 subpage->is_edge_cutoff[b][0] = page->is_edge_cutoff[b][0];
1820 subpage->is_edge_cutoff[b][1] = page->is_edge_cutoff[b][1];
1822 /* Select join crossings from PAGE into subpage. */
1823 int *jc = subpage->join_crossing[a];
1824 for (int z = 0; z < page->h[a][0]; z++)
1825 *jc++ = page->join_crossing[a][z];
1826 for (int z = z0; z <= z1; z++)
1827 *jc++ = page->join_crossing[a][z];
1828 for (int z = page->n[a] - page->h[a][1]; z < page->n[a]; z++)
1829 *jc++ = page->join_crossing[a][z];
1830 assert (jc == &subpage->join_crossing[a][subpage->n[a] + 1]);
1832 memcpy (subpage->join_crossing[b], page->join_crossing[b],
1833 (subpage->n[b] + 1) * sizeof **subpage->join_crossing);
1835 /* Select widths from PAGE into subpage. */
1836 int *scp = page->cp[a];
1837 int *dcp = subpage->cp[a];
1839 for (int z = 0; z <= rule_ofs (subpage->h[a][0]); z++, dcp++)
1841 int w = !z && subpage->is_edge_cutoff[a][0] ? 0 : scp[z + 1] - scp[z];
1842 dcp[1] = dcp[0] + w;
1844 for (int z = cell_ofs (z0); z <= cell_ofs (z1 - 1); z++, dcp++)
1846 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1847 if (z == cell_ofs (z0))
1850 if (page->h[a][0] && page->h[a][1])
1851 dcp[1] += page->join_crossing[a][z / 2];
1853 if (z == cell_ofs (z1 - 1))
1856 for (int z = rule_ofs_r (page, a, subpage->h[a][1]);
1857 z <= rule_ofs_r (page, a, 0); z++, dcp++)
1859 if (z == rule_ofs_r (page, a, 0) && subpage->is_edge_cutoff[a][1])
1862 dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1864 assert (dcp == &subpage->cp[a][2 * subpage->n[a] + 1]);
1866 for (int z = 0; z < page->n[b] * 2 + 2; z++)
1867 subpage->cp[b][z] = page->cp[b][z];
1869 /* Add new overflows. */
1870 struct render_page_selection s = {
1881 if (!page->h[a][0] || z0 > page->h[a][0] || p0)
1882 for (int z = 0; z < page->n[b];)
1884 int d[TABLE_N_AXES];
1888 struct table_cell cell;
1889 render_get_cell (page, d[H], d[V], &cell);
1890 bool overflow0 = p0 || cell.d[a][0] < z0;
1891 bool overflow1 = cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1);
1892 if (overflow0 || overflow1)
1894 struct render_overflow *ro = insert_overflow (&s, &cell);
1898 ro->overflow[a][0] += p0 + axis_width (
1899 page, a, cell_ofs (cell.d[a][0]), cell_ofs (z0));
1900 if (page->h[a][0] && page->h[a][1])
1901 ro->overflow[a][0] -= page->join_crossing[a][cell.d[a][0]
1907 ro->overflow[a][1] += p1 + axis_width (
1908 page, a, cell_ofs (z1), cell_ofs (cell.d[a][1]));
1909 if (page->h[a][0] && page->h[a][1])
1910 ro->overflow[a][1] -= page->join_crossing[a][cell.d[a][1]];
1916 if (!page->h[a][1] || z1 < page->n[a] - page->h[a][1] || p1)
1917 for (int z = 0; z < page->n[b];)
1919 int d[TABLE_N_AXES];
1923 struct table_cell cell;
1924 render_get_cell (page, d[H], d[V], &cell);
1925 if ((cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1))
1926 && find_overflow_for_cell (&s, &cell) == NULL)
1928 struct render_overflow *ro = insert_overflow (&s, &cell);
1929 ro->overflow[a][1] += p1 + axis_width (page, a, cell_ofs (z1),
1930 cell_ofs (cell.d[a][1]));
1935 /* Copy overflows from PAGE into subpage. */
1936 struct render_overflow *ro;
1937 HMAP_FOR_EACH (ro, struct render_overflow, node, &page->overflows)
1939 struct table_cell cell;
1941 table_get_cell (page->table, ro->d[H], ro->d[V], &cell);
1942 if (cell.d[a][1] > z0 && cell.d[a][0] < z1
1943 && find_overflow_for_cell (&s, &cell) == NULL)
1944 insert_overflow (&s, &cell);
1950 /* Given CELL, a table_cell within S->page, stores in SUBCELL the (x,y)
1951 coordinates of the top-left cell as it will appear in S->subpage.
1953 CELL must actually intersect the region of S->page that is being selected
1954 by render_page_select() or the results will not make any sense. */
1956 cell_to_subpage (struct render_page_selection *s,
1957 const struct table_cell *cell, int subcell[TABLE_N_AXES])
1959 enum table_axis a = s->a;
1960 enum table_axis b = s->b;
1961 int ha0 = s->subpage->h[a][0];
1963 subcell[a] = MAX (cell->d[a][0] - s->z0 + ha0, ha0);
1964 subcell[b] = cell->d[b][0];
1967 /* Given CELL, a table_cell within S->page, returns the render_overflow for
1968 that cell in S->subpage, if there is one, and a null pointer otherwise.
1970 CELL must actually intersect the region of S->page that is being selected
1971 by render_page_select() or the results will not make any sense. */
1972 static const struct render_overflow *
1973 find_overflow_for_cell (struct render_page_selection *s,
1974 const struct table_cell *cell)
1978 cell_to_subpage (s, cell, subcell);
1979 return find_overflow (s->subpage, subcell[H], subcell[V]);
1982 /* Given CELL, a table_cell within S->page, inserts a render_overflow for that
1983 cell in S->subpage (which must not already exist). Initializes the new
1984 render_overflow's 'overflow' member from the overflow for CELL in S->page,
1987 CELL must actually intersect the region of S->page that is being selected
1988 by render_page_select() or the results will not make any sense. */
1989 static struct render_overflow *
1990 insert_overflow (struct render_page_selection *s,
1991 const struct table_cell *cell)
1993 struct render_overflow *of = xzalloc (sizeof *of);
1994 cell_to_subpage (s, cell, of->d);
1995 hmap_insert (&s->subpage->overflows, &of->node,
1996 hash_cell (of->d[H], of->d[V]));
1998 const struct render_overflow *old
1999 = find_overflow (s->page, cell->d[H][0], cell->d[V][0]);
2001 memcpy (of->overflow, old->overflow, sizeof of->overflow);