table-stomp: Remove dead code.
[pspp] / src / output / render.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2009, 2010, 2011, 2013, 2014, 2016 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
17 #include <config.h>
18
19 #include <math.h>
20 #include <stdio.h>
21 #include <stdint.h>
22 #include <stdlib.h>
23 #include <string.h>
24
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"
33
34 #include "gl/minmax.h"
35 #include "gl/xalloc.h"
36
37 #include "gettext.h"
38 #define _(msgid) gettext (msgid)
39
40 /* This file uses TABLE_HORZ and TABLE_VERT enough to warrant abbreviating. */
41 #define H TABLE_HORZ
42 #define V TABLE_VERT
43 \f
44 /* A layout for rendering a specific table on a specific device.
45
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.
49
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. */
53 struct render_page
54   {
55     const struct render_params *params; /* Parameters of the target device. */
56     struct table *table;                /* Table rendered. */
57     int ref_cnt;
58
59     /* Local copies of table->n and table->h, for convenience. */
60     int n[TABLE_N_AXES];
61     int h[TABLE_N_AXES][2];
62
63     /* "Cell positions".
64
65        cp[H] represents x positions within the table.
66        cp[H][0] = 0.
67        cp[H][1] = the width of the leftmost vertical rule.
68        cp[H][2] = cp[H][1] + the width of the leftmost column.
69        cp[H][3] = cp[H][2] + the width of the second-from-left vertical rule.
70        and so on:
71        cp[H][2 * nc] = x position of the rightmost vertical rule.
72        cp[H][2 * nc + 1] = total table width including all rules.
73
74        Similarly, cp[V] represents y positions within the table.
75        cp[V][0] = 0.
76        cp[V][1] = the height of the topmost horizontal rule.
77        cp[V][2] = cp[V][1] + the height of the topmost row.
78        cp[V][3] = cp[V][2] + the height of the second-from-top horizontal rule.
79        and so on:
80        cp[V][2 * nr] = y position of the bottommost horizontal rule.
81        cp[V][2 * nr + 1] = total table height including all rules.
82
83        Rules and columns can have width or height 0, in which case consecutive
84        values in this array are equal. */
85     int *cp[TABLE_N_AXES];
86
87     /* render_break_next() can break a table such that some cells are not fully
88        contained within a render_page.  This will happen if a cell is too wide
89        or two tall to fit on a single page, or if a cell spans multiple rows or
90        columns and the page only includes some of those rows or columns.
91
92        This hash table contains "struct render_overflow"s that represents each
93        such cell that doesn't completely fit on this page.
94
95        Each overflow cell borders at least one header edge of the table and may
96        border more.  (A single table cell that is so large that it fills the
97        entire page can overflow on all four sides!) */
98     struct hmap overflows;
99
100     /* If a single column (or row) is too wide (or tall) to fit on a page
101        reasonably, then render_break_next() will split a single row or column
102        across multiple render_pages.  This member indicates when this has
103        happened:
104
105        is_edge_cutoff[H][0] is true if pixels have been cut off the left side
106        of the leftmost column in this page, and false otherwise.
107
108        is_edge_cutoff[H][1] is true if pixels have been cut off the right side
109        of the rightmost column in this page, and false otherwise.
110
111        is_edge_cutoff[V][0] and is_edge_cutoff[V][1] are similar for the top
112        and bottom of the table.
113
114        The effect of is_edge_cutoff is to prevent rules along the edge in
115        question from being rendered.
116
117        When is_edge_cutoff is true for a given edge, the 'overflows' hmap will
118        contain a node for each cell along that edge. */
119     bool is_edge_cutoff[TABLE_N_AXES][2];
120
121     /* If part of a joined cell would be cut off by breaking a table along
122        'axis' at the rule with offset 'z' (where 0 <= z <= n[axis]), then
123        join_crossing[axis][z] is the thickness of the rule that would be cut
124        off.
125
126        This is used to know to allocate extra space for breaking at such a
127        position, so that part of the cell's content is not lost.
128
129        This affects breaking a table only when headers are present.  When
130        headers are not present, the rule's thickness is used for cell content,
131        so no part of the cell's content is lost (and in fact it is duplicated
132        across both pages). */
133     int *join_crossing[TABLE_N_AXES];
134   };
135
136 static struct render_page *render_page_create (const struct render_params *,
137                                                struct table *, int min_width);
138
139 struct render_page *render_page_ref (const struct render_page *page_);
140 static void render_page_unref (struct render_page *);
141
142 /* Returns the offset in struct render_page's cp[axis] array of the rule with
143    index RULE_IDX.  That is, if RULE_IDX is 0, then the offset is that of the
144    leftmost or topmost rule; if RULE_IDX is 1, then the offset is that of the
145    next rule to the right (or below); and so on. */
146 static int
147 rule_ofs (int rule_idx)
148 {
149   return rule_idx * 2;
150 }
151
152 /* Returns the offset in struct render_page's cp[axis] array of the rule with
153    index RULE_IDX_R, which counts from the right side (or bottom) of the page
154    left (or up), according to whether AXIS is H or V, respectively.  That is,
155    if RULE_IDX_R is 0, then the offset is that of the rightmost or bottommost
156    rule; if RULE_IDX is 1, then the offset is that of the next rule to the left
157    (or above); and so on. */
158 static int
159 rule_ofs_r (const struct render_page *page, int axis, int rule_idx_r)
160 {
161   return (page->n[axis] - rule_idx_r) * 2;
162 }
163
164 /* Returns the offset in struct render_page's cp[axis] array of the cell with
165    index CELL_IDX.  That is, if CELL_IDX is 0, then the offset is that of the
166    leftmost or topmost cell; if CELL_IDX is 1, then the offset is that of the
167    next cell to the right (or below); and so on. */
168 static int
169 cell_ofs (int cell_idx)
170 {
171   return cell_idx * 2 + 1;
172 }
173
174 /* Returns the width of PAGE along AXIS from OFS0 to OFS1, exclusive. */
175 static int
176 axis_width (const struct render_page *page, int axis, int ofs0, int ofs1)
177 {
178   return page->cp[axis][ofs1] - page->cp[axis][ofs0];
179 }
180
181 /* Returns the width of the headers in PAGE along AXIS. */
182 static int
183 headers_width (const struct render_page *page, int axis)
184 {
185   int h0 = page->h[axis][0];
186   int w0 = axis_width (page, axis, rule_ofs (0), cell_ofs (h0));
187   int n = page->n[axis];
188   int h1 = page->h[axis][1];
189   int w1 = axis_width (page, axis, rule_ofs_r (page, axis, h1), cell_ofs (n));
190   return w0 + w1;
191 }
192
193 /* Returns the width of cell X along AXIS in PAGE. */
194 static int
195 cell_width (const struct render_page *page, int axis, int x)
196 {
197   return axis_width (page, axis, cell_ofs (x), cell_ofs (x) + 1);
198 }
199
200 /* Returns the width of rule X along AXIS in PAGE. */
201 static int
202 rule_width (const struct render_page *page, int axis, int x)
203 {
204   return axis_width (page, axis, rule_ofs (x), rule_ofs (x) + 1);
205 }
206
207 /* Returns the width of rule X along AXIS in PAGE. */
208 static int
209 rule_width_r (const struct render_page *page, int axis, int x)
210 {
211   int ofs = rule_ofs_r (page, axis, x);
212   return axis_width (page, axis, ofs, ofs + 1);
213 }
214
215 /* Returns the width of cells X0 through X1, exclusive, along AXIS in PAGE. */
216 static int
217 joined_width (const struct render_page *page, int axis, int x0, int x1)
218 {
219   return axis_width (page, axis, cell_ofs (x0), cell_ofs (x1) - 1);
220 }
221
222 /* Returns the width of the widest cell, excluding headers, along AXIS in
223    PAGE. */
224 static int
225 max_cell_width (const struct render_page *page, int axis)
226 {
227   int n = page->n[axis];
228   int x0 = page->h[axis][0];
229   int x1 = n - page->h[axis][1];
230   int x, max;
231
232   max = 0;
233   for (x = x0; x < x1; x++)
234     {
235       int w = cell_width (page, axis, x);
236       if (w > max)
237         max = w;
238     }
239   return max;
240 }
241 \f
242 /* A cell that doesn't completely fit on the render_page. */
243 struct render_overflow
244   {
245     struct hmap_node node;      /* In render_page's 'overflows' hmap. */
246
247     /* Occupied region of page.
248
249        d[H][0] is the leftmost column.
250        d[H][1] is the rightmost column, plus 1.
251        d[V][0] is the top row.
252        d[V][1] is the bottom row, plus 1.
253
254        The cell in its original table might occupy a larger region.  This
255        member reflects the size of the cell in the current render_page, after
256        trimming off any rows or columns due to page-breaking. */
257     int d[TABLE_N_AXES];
258
259     /* The space that has been trimmed off the cell:
260
261        overflow[H][0]: space trimmed off its left side.
262        overflow[H][1]: space trimmed off its right side.
263        overflow[V][0]: space trimmed off its top.
264        overflow[V][1]: space trimmed off its bottom.
265
266        During rendering, this information is used to position the rendered
267        portion of the cell within the available space.
268
269        When a cell is rendered, sometimes it is permitted to spill over into
270        space that is ordinarily reserved for rules.  Either way, this space is
271        still included in overflow values.
272
273        Suppose, for example, that a cell that joins 2 columns has a width of 60
274        pixels and content "abcdef", that the 2 columns that it joins have
275        widths of 20 and 30 pixels, respectively, and that therefore the rule
276        between the two joined columns has a width of 10 (20 + 10 + 30 = 60).
277        It might render like this, if each character is 10x10, and showing a few
278        extra table cells for context:
279
280                                      +------+
281                                      |abcdef|
282                                      +--+---+
283                                      |gh|ijk|
284                                      +--+---+
285
286        If this render_page is broken at the rule that separates "gh" from
287        "ijk", then the page that contains the left side of the "abcdef" cell
288        will have overflow[H][1] of 10 + 30 = 40 for its portion of the cell,
289        and the page that contains the right side of the cell will have
290        overflow[H][0] of 20 + 10 = 30.  The two resulting pages would look like
291        this:
292
293
294                                        +---
295                                        |abc
296                                        +--+
297                                        |gh|
298                                        +--+
299
300        and:
301
302                                        ----+
303                                        cdef|
304                                        +---+
305                                        |ijk|
306                                        +---+
307     */
308     int overflow[TABLE_N_AXES][2];
309   };
310
311 /* Returns a hash value for (,Y). */
312 static unsigned int
313 hash_cell (int x, int y)
314 {
315   return hash_int (x + (y << 16), 0);
316 }
317
318 /* Searches PAGE's set of render_overflow for one whose top-left cell is
319    (X,Y).  Returns it, if there is one, otherwise a null pointer. */
320 static const struct render_overflow *
321 find_overflow (const struct render_page *page, int x, int y)
322 {
323   if (!hmap_is_empty (&page->overflows))
324     {
325       const struct render_overflow *of;
326
327       HMAP_FOR_EACH_WITH_HASH (of, struct render_overflow, node,
328                                hash_cell (x, y), &page->overflows)
329         if (x == of->d[H] && y == of->d[V])
330           return of;
331     }
332
333   return NULL;
334 }
335 \f
336 /* Row or column dimensions.  Used to figure the size of a table in
337    render_page_create() and discarded after that. */
338 struct render_row
339   {
340     /* Width without considering rows (or columns) that span more than one (or
341        column). */
342     int unspanned;
343
344     /* Width taking spanned rows (or columns) into consideration. */
345     int width;
346   };
347
348 /* Modifies the 'width' members of the N elements of ROWS so that their sum,
349    when added to rule widths RULES[1] through RULES[N - 1] inclusive, is at
350    least WIDTH. */
351 static void
352 distribute_spanned_width (int width,
353                           struct render_row *rows, const int *rules, int n)
354 {
355   /* Sum up the unspanned widths of the N rows for use as weights. */
356   int total_unspanned = 0;
357   for (int x = 0; x < n; x++)
358     total_unspanned += rows[x].unspanned;
359   for (int x = 0; x < n - 1; x++)
360     total_unspanned += rules[x + 1];
361   if (total_unspanned >= width)
362     return;
363
364   /* The algorithm used here is based on the following description from HTML 4:
365
366          For cells that span multiple columns, a simple approach consists of
367          apportioning the min/max widths evenly to each of the constituent
368          columns.  A slightly more complex approach is to use the min/max
369          widths of unspanned cells to weight how spanned widths are
370          apportioned.  Experiments suggest that a blend of the two approaches
371          gives good results for a wide range of tables.
372
373      We blend the two approaches half-and-half, except that we cannot use the
374      unspanned weights when 'total_unspanned' is 0 (because that would cause a
375      division by zero).
376
377      The calculation we want to do is this:
378
379         w0 = width / n
380         w1 = width * (column's unspanned width) / (total unspanned width)
381         (column's width) = (w0 + w1) / 2
382
383      We implement it as a precise calculation in integers by multiplying w0 and
384      w1 by the common denominator of all three calculations (d), dividing that
385      out in the column width calculation, and then keeping the remainder for
386      the next iteration.
387
388      (We actually compute the unspanned width of a column as twice the
389      unspanned width, plus the width of the rule on the left, plus the width of
390      the rule on the right.  That way each rule contributes to both the cell on
391      its left and on its right.)
392   */
393   long long int d0 = n;
394   long long int d1 = 2LL * MAX (total_unspanned, 1);
395   long long int d = d0 * d1;
396   if (total_unspanned > 0)
397     d *= 2;
398   long long int w = d / 2;
399   for (int x = 0; x < n; x++)
400     {
401       w += width * d1;
402       if (total_unspanned > 0)
403         {
404           long long int unspanned = rows[x].unspanned * 2LL;
405           if (x < n - 1)
406             unspanned += rules[x + 1];
407           if (x > 0)
408             unspanned += rules[x];
409           w += width * unspanned * d0;
410         }
411
412       rows[x].width = MAX (rows[x].width, w / d);
413       w -= rows[x].width * d;
414     }
415 }
416
417 /* Initializes PAGE->cp[AXIS] from the row widths in ROWS and the rule widths
418    in RULES. */
419 static void
420 accumulate_row_widths (const struct render_page *page, enum table_axis axis,
421                        const struct render_row *rows, const int *rules)
422 {
423   int n = page->n[axis];
424   int *cp;
425   int z;
426
427   cp = page->cp[axis];
428   cp[0] = 0;
429   for (z = 0; z < n; z++)
430     {
431       cp[1] = cp[0] + rules[z];
432       cp[2] = cp[1] + rows[z].width;
433       cp += 2;
434     }
435   cp[1] = cp[0] + rules[n];
436 }
437
438 /* Returns the sum of widths of the N ROWS and N+1 RULES. */
439 static int
440 calculate_table_width (int n, const struct render_row *rows, int *rules)
441 {
442   int width;
443   int x;
444
445   width = 0;
446   for (x = 0; x < n; x++)
447     width += rows[x].width;
448   for (x = 0; x <= n; x++)
449     width += rules[x];
450
451   return width;
452 }
453 \f
454 /* Rendering utility functions. */
455
456 /* Returns the line style to use for drawing a rule of the given TYPE. */
457 static enum render_line_style
458 rule_to_render_type (unsigned char type)
459 {
460   switch (type)
461     {
462     case TAL_NONE:
463       return RENDER_LINE_NONE;
464     case TAL_SOLID:
465       return RENDER_LINE_SINGLE;
466     case TAL_DASHED:
467       return RENDER_LINE_DASHED;
468     case TAL_THICK:
469       return RENDER_LINE_THICK;
470     case TAL_THIN:
471       return RENDER_LINE_THIN;
472     case TAL_DOUBLE:
473       return RENDER_LINE_DOUBLE;
474     default:
475       NOT_REACHED ();
476     }
477 }
478
479 /* Returns the width of the rule in TABLE that is at offset Z along axis A, if
480    rendered with PARAMS.  */
481 static int
482 measure_rule (const struct render_params *params, const struct table *table,
483               enum table_axis a, int z)
484 {
485   enum table_axis b = !a;
486   unsigned int rules;
487   int d[TABLE_N_AXES];
488
489   /* Determine all types of rules that are present, as a bitmap in 'rules'
490      where rule type 't' is present if bit 2**t is set. */
491   struct cell_color color;
492   rules = 0;
493   d[a] = z;
494   for (d[b] = 0; d[b] < table->n[b]; d[b]++)
495     rules |= 1u << table_get_rule (table, a, d[H], d[V], &color);
496
497   /* Turn off TAL_NONE because it has width 0 and we needn't bother.  However,
498      if the device doesn't support margins, make sure that there is at least a
499      small gap between cells (but we don't need any at the left or right edge
500      of the table). */
501   if (rules & (1u << TAL_NONE))
502     {
503       rules &= ~(1u << TAL_NONE);
504       if (z > 0 && z < table->n[a] && !params->supports_margins && a == H)
505         rules |= 1u << TAL_SOLID;
506     }
507
508   /* Calculate maximum width of the rules that are present. */
509   int width = 0;
510   for (size_t i = 0; i < N_LINES; i++)
511     if (rules & (1u << i))
512       width = MAX (width, params->line_widths[a][rule_to_render_type (i)]);
513   return width;
514 }
515
516 /* Allocates and returns a new render_page using PARAMS and TABLE.  Allocates
517    space for all of the members of the new page, but the caller must initialize
518    the 'cp' member itself. */
519 static struct render_page *
520 render_page_allocate (const struct render_params *params,
521                       struct table *table)
522 {
523   struct render_page *page;
524   int i;
525
526   page = xmalloc (sizeof *page);
527   page->params = params;
528   page->table = table;
529   page->ref_cnt = 1;
530   page->n[H] = table->n[H];
531   page->n[V] = table->n[V];
532   page->h[H][0] = table->h[H][0];
533   page->h[H][1] = table->h[H][1];
534   page->h[V][0] = table->h[V][0];
535   page->h[V][1] = table->h[V][1];
536
537   for (i = 0; i < TABLE_N_AXES; i++)
538     {
539       page->cp[i] = xmalloc ((2 * page->n[i] + 2) * sizeof *page->cp[i]);
540       page->join_crossing[i] = xzalloc ((page->n[i] + 1) * sizeof *page->join_crossing[i]);
541     }
542
543   hmap_init (&page->overflows);
544   memset (page->is_edge_cutoff, 0, sizeof page->is_edge_cutoff);
545
546   return page;
547 }
548
549 /* Allocates and returns a new render_page for PARAMS and TABLE, initializing
550    cp[H] in the new page from ROWS and RULES.  The caller must still initialize
551    cp[V]. */
552 static struct render_page *
553 create_page_with_exact_widths (const struct render_params *params,
554                                struct table *table,
555                                const struct render_row *rows, int *rules)
556 {
557   struct render_page *page = render_page_allocate (params, table);
558   accumulate_row_widths (page, H, rows, rules);
559   return page;
560 }
561
562 /* Allocates and returns a new render_page for PARAMS and TABLE.
563
564    Initializes cp[H] in the new page by setting the width of each row 'i' to
565    somewhere between the minimum cell width ROW_MIN[i].width and the maximum
566    ROW_MAX[i].width.  Sets the width of rules to those in RULES.
567
568    W_MIN is the sum of ROWS_MIN[].width.
569
570    W_MAX is the sum of ROWS_MAX[].width.
571
572    The caller must still initialize cp[V]. */
573 static struct render_page *
574 create_page_with_interpolated_widths (const struct render_params *params,
575                                       struct table *table,
576                                       const struct render_row *rows_min,
577                                       const struct render_row *rows_max,
578                                       int w_min, int w_max, const int *rules)
579 {
580   const int n = table->n[H];
581   const long long int avail = params->size[H] - w_min;
582   const long long int wanted = w_max - w_min;
583
584   assert (wanted > 0);
585
586   struct render_page *page = render_page_allocate (params, table);
587
588   int *cph = page->cp[H];
589   *cph = 0;
590   long long int w = wanted / 2;
591   for (int x = 0; x < n; x++)
592     {
593       w += avail * (rows_max[x].width - rows_min[x].width);
594       int extra = w / wanted;
595       w -= extra * wanted;
596
597       cph[1] = cph[0] + rules[x];
598       cph[2] = cph[1] + rows_min[x].width + extra;
599       cph += 2;
600     }
601   cph[1] = cph[0] + rules[n];
602
603   assert (page->cp[H][n * 2 + 1] == params->size[H]);
604   return page;
605 }
606
607 \f
608 static void
609 set_join_crossings (struct render_page *page, enum table_axis axis,
610                     const struct table_cell *cell, int *rules)
611 {
612   int z;
613
614   for (z = cell->d[axis][0] + 1; z <= cell->d[axis][1] - 1; z++)
615     page->join_crossing[axis][z] = rules[z];
616 }
617
618 /* Creates and returns a new render_page for rendering TABLE on a device
619    described by PARAMS.
620
621    The new render_page will be suitable for rendering on a device whose page
622    size is PARAMS->size, but the caller is responsible for actually breaking it
623    up to fit on such a device, using the render_break abstraction.  */
624 static struct render_page *
625 render_page_create (const struct render_params *params, struct table *table,
626                     int min_width)
627 {
628   struct render_page *page;
629   enum { MIN, MAX };
630   struct render_row *columns[2];
631   struct render_row *rows;
632   int table_widths[2];
633   int *rules[TABLE_N_AXES];
634   int nr, nc;
635   int x, y;
636   int i;
637   enum table_axis axis;
638
639   nc = table_nc (table);
640   nr = table_nr (table);
641
642   /* Figure out rule widths. */
643   for (axis = 0; axis < TABLE_N_AXES; axis++)
644     {
645       int n = table->n[axis] + 1;
646       int z;
647
648       rules[axis] = xnmalloc (n, sizeof *rules);
649       for (z = 0; z < n; z++)
650         rules[axis][z] = measure_rule (params, table, axis, z);
651     }
652
653   /* Calculate minimum and maximum widths of cells that do not
654      span multiple columns. */
655   for (i = 0; i < 2; i++)
656     columns[i] = xzalloc (nc * sizeof *columns[i]);
657   for (y = 0; y < nr; y++)
658     for (x = 0; x < nc; )
659       {
660         struct table_cell cell;
661
662         table_get_cell (table, x, y, &cell);
663         if (y == cell.d[V][0])
664           {
665             if (table_cell_colspan (&cell) == 1)
666               {
667                 int w[2];
668                 int i;
669
670                 params->measure_cell_width (params->aux, &cell,
671                                             &w[MIN], &w[MAX]);
672                 for (i = 0; i < 2; i++)
673                   if (columns[i][x].unspanned < w[i])
674                     columns[i][x].unspanned = w[i];
675               }
676           }
677         x = cell.d[H][1];
678         table_cell_free (&cell);
679       }
680
681   /* Distribute widths of spanned columns. */
682   for (i = 0; i < 2; i++)
683     for (x = 0; x < nc; x++)
684       columns[i][x].width = columns[i][x].unspanned;
685   for (y = 0; y < nr; y++)
686     for (x = 0; x < nc; )
687       {
688         struct table_cell cell;
689
690         table_get_cell (table, x, y, &cell);
691         if (y == cell.d[V][0] && table_cell_colspan (&cell) > 1)
692           {
693             int w[2];
694
695             params->measure_cell_width (params->aux, &cell, &w[MIN], &w[MAX]);
696             for (i = 0; i < 2; i++)
697               distribute_spanned_width (w[i], &columns[i][cell.d[H][0]],
698                                         rules[H], table_cell_colspan (&cell));
699           }
700         x = cell.d[H][1];
701         table_cell_free (&cell);
702       }
703   if (min_width > 0)
704     for (i = 0; i < 2; i++)
705       distribute_spanned_width (min_width, &columns[i][0], rules[H], nc);
706
707   /* In pathological cases, spans can cause the minimum width of a column to
708      exceed the maximum width.  This bollixes our interpolation algorithm
709      later, so fix it up. */
710   for (i = 0; i < nc; i++)
711     if (columns[MIN][i].width > columns[MAX][i].width)
712       columns[MAX][i].width = columns[MIN][i].width;
713
714   /* Decide final column widths. */
715   for (i = 0; i < 2; i++)
716     table_widths[i] = calculate_table_width (table_nc (table),
717                                              columns[i], rules[H]);
718   if (table_widths[MAX] <= params->size[H])
719     {
720       /* Fits even with maximum widths.  Use them. */
721       page = create_page_with_exact_widths (params, table, columns[MAX],
722                                             rules[H]);
723     }
724   else if (table_widths[MIN] <= params->size[H])
725     {
726       /* Fits with minimum widths, so distribute the leftover space. */
727       page = create_page_with_interpolated_widths (
728         params, table, columns[MIN], columns[MAX],
729         table_widths[MIN], table_widths[MAX], rules[H]);
730     }
731   else
732     {
733       /* Doesn't fit even with minimum widths.  Assign minimums for now, and
734          later we can break it horizontally into multiple pages. */
735       page = create_page_with_exact_widths (params, table, columns[MIN],
736                                             rules[H]);
737     }
738
739   /* Calculate heights of cells that do not span multiple rows. */
740   rows = xzalloc (nr * sizeof *rows);
741   for (y = 0; y < nr; y++)
742     {
743       for (x = 0; x < nc; )
744         {
745           struct render_row *r = &rows[y];
746           struct table_cell cell;
747
748           table_get_cell (table, x, y, &cell);
749           if (y == cell.d[V][0])
750             {
751               if (table_cell_rowspan (&cell) == 1)
752                 {
753                   int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
754                   int h = params->measure_cell_height (params->aux, &cell, w);
755                   if (h > r->unspanned)
756                     r->unspanned = r->width = h;
757                 }
758               else
759                 set_join_crossings (page, V, &cell, rules[V]);
760
761               if (table_cell_colspan (&cell) > 1)
762                 set_join_crossings (page, H, &cell, rules[H]);
763             }
764           x = cell.d[H][1];
765           table_cell_free (&cell);
766         }
767     }
768   for (i = 0; i < 2; i++)
769     free (columns[i]);
770
771   /* Distribute heights of spanned rows. */
772   for (y = 0; y < nr; y++)
773     for (x = 0; x < nc; )
774       {
775         struct table_cell cell;
776
777         table_get_cell (table, x, y, &cell);
778         if (y == cell.d[V][0] && table_cell_rowspan (&cell) > 1)
779           {
780             int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
781             int h = params->measure_cell_height (params->aux, &cell, w);
782             distribute_spanned_width (h, &rows[cell.d[V][0]], rules[V],
783                                       table_cell_rowspan (&cell));
784           }
785         x = cell.d[H][1];
786         table_cell_free (&cell);
787       }
788
789   /* Decide final row heights. */
790   accumulate_row_widths (page, V, rows, rules[V]);
791   free (rows);
792
793   /* Measure headers.  If they are "too big", get rid of them.  */
794   for (axis = 0; axis < TABLE_N_AXES; axis++)
795     {
796       int hw = headers_width (page, axis);
797       if (hw * 2 >= page->params->size[axis]
798           || hw + max_cell_width (page, axis) > page->params->size[axis])
799         {
800           page->table = table_unshare (page->table);
801           page->table->h[axis][0] = page->table->h[axis][1] = 0;
802           page->h[axis][0] = page->h[axis][1] = 0;
803         }
804     }
805
806   free (rules[H]);
807   free (rules[V]);
808
809   return page;
810 }
811
812 /* Increases PAGE's reference count. */
813 struct render_page *
814 render_page_ref (const struct render_page *page_)
815 {
816   struct render_page *page = CONST_CAST (struct render_page *, page_);
817   page->ref_cnt++;
818   return page;
819 }
820
821 /* Decreases PAGE's reference count and destroys PAGE if this causes the
822    reference count to fall to zero. */
823 static void
824 render_page_unref (struct render_page *page)
825 {
826   if (page != NULL && --page->ref_cnt == 0)
827     {
828       int i;
829       struct render_overflow *overflow, *next;
830
831       HMAP_FOR_EACH_SAFE (overflow, next, struct render_overflow, node,
832                           &page->overflows)
833         free (overflow);
834       hmap_destroy (&page->overflows);
835
836       table_unref (page->table);
837
838       for (i = 0; i < TABLE_N_AXES; ++i)
839         {
840           free (page->join_crossing[i]);
841           free (page->cp[i]);
842         }
843
844       free (page);
845     }
846 }
847
848 /* Returns the size of PAGE along AXIS.  (This might be larger than the page
849    size specified in the parameters passed to render_page_create().  Use a
850    render_break to break up a render_page into page-sized chunks.) */
851 static int
852 render_page_get_size (const struct render_page *page, enum table_axis axis)
853 {
854   return page->cp[axis][page->n[axis] * 2 + 1];
855 }
856
857 static int
858 render_page_get_best_breakpoint (const struct render_page *page, int height)
859 {
860   int y;
861
862   /* If there's no room for at least the top row and the rules above and below
863      it, don't include any of the table. */
864   if (page->cp[V][3] > height)
865     return 0;
866
867   /* Otherwise include as many rows and rules as we can. */
868   for (y = 5; y <= 2 * page->n[V] + 1; y += 2)
869     if (page->cp[V][y] > height)
870       return page->cp[V][y - 2];
871   return height;
872 }
873 \f
874 /* Drawing render_pages. */
875
876 static inline enum render_line_style
877 get_rule (const struct render_page *page, enum table_axis axis,
878           const int d[TABLE_N_AXES], struct cell_color *color)
879 {
880   return rule_to_render_type (table_get_rule (page->table,
881                                               axis, d[H] / 2, d[V] / 2,
882                                               color));
883 }
884
885 static bool
886 is_rule (int z)
887 {
888   return !(z & 1);
889 }
890
891 bool
892 render_direction_rtl (void)
893 {
894   /* TRANSLATORS: Do not translate this string.  If the script of your language
895      reads from right to left (eg Persian, Arabic, Hebrew etc), then replace
896      this string with "output-direction-rtl".  Otherwise either leave it
897      untranslated or copy it verbatim. */
898   const char *dir = _("output-direction-ltr");
899   if ( 0 == strcmp ("output-direction-rtl", dir))
900     return true;
901
902   if ( 0 != strcmp ("output-direction-ltr", dir))
903     fprintf (stderr, "This localisation has been incorrectly translated.  Complain to the translator.\n");
904
905   return false;
906 }
907
908 static void
909 render_rule (const struct render_page *page, const int ofs[TABLE_N_AXES],
910              const int d[TABLE_N_AXES])
911 {
912   enum render_line_style styles[TABLE_N_AXES][2];
913   struct cell_color colors[TABLE_N_AXES][2];
914   enum table_axis a;
915
916   for (a = 0; a < TABLE_N_AXES; a++)
917     {
918       enum table_axis b = !a;
919
920       styles[a][0] = styles[a][1] = RENDER_LINE_NONE;
921
922       if (!is_rule (d[a])
923           || (page->is_edge_cutoff[a][0] && d[a] == 0)
924           || (page->is_edge_cutoff[a][1] && d[a] == page->n[a] * 2))
925         continue;
926
927       if (is_rule (d[b]))
928         {
929           if (d[b] > 0)
930             {
931               int e[TABLE_N_AXES];
932               e[H] = d[H];
933               e[V] = d[V];
934               e[b]--;
935               styles[a][0] = get_rule (page, a, e, &colors[a][0]);
936             }
937
938           if (d[b] / 2 < page->table->n[b])
939             styles[a][1] = get_rule (page, a, d, &colors[a][1]);
940         }
941       else
942         {
943           styles[a][0] = styles[a][1] = get_rule (page, a, d, &colors[a][0]);
944           colors[a][1] = colors[a][0];
945         }
946     }
947
948   if (styles[H][0] != RENDER_LINE_NONE || styles[H][1] != RENDER_LINE_NONE
949       || styles[V][0] != RENDER_LINE_NONE || styles[V][1] != RENDER_LINE_NONE)
950     {
951       int bb[TABLE_N_AXES][2];
952
953       bb[H][0] = ofs[H] + page->cp[H][d[H]];
954       bb[H][1] = ofs[H] + page->cp[H][d[H] + 1];
955       if (render_direction_rtl ())
956         {
957           int temp = bb[H][0];
958           bb[H][0] = render_page_get_size (page, H) - bb[H][1];
959           bb[H][1] = render_page_get_size (page, H) - temp;
960         }
961       bb[V][0] = ofs[V] + page->cp[V][d[V]];
962       bb[V][1] = ofs[V] + page->cp[V][d[V] + 1];
963       page->params->draw_line (page->params->aux, bb, styles, colors);
964     }
965 }
966
967 static void
968 render_cell (const struct render_page *page, const int ofs[TABLE_N_AXES],
969              const struct table_cell *cell)
970 {
971   const struct render_overflow *of;
972   int bb[TABLE_N_AXES][2];
973   int clip[TABLE_N_AXES][2];
974
975   bb[H][0] = clip[H][0] = ofs[H] + page->cp[H][cell->d[H][0] * 2 + 1];
976   bb[H][1] = clip[H][1] = ofs[H] + page->cp[H][cell->d[H][1] * 2];
977   if (render_direction_rtl ())
978     {
979       int temp = bb[H][0];
980       bb[H][0] = clip[H][0] = render_page_get_size (page, H) - bb[H][1];
981       bb[H][1] = clip[H][1] = render_page_get_size (page, H) - temp;
982     }
983   bb[V][0] = clip[V][0] = ofs[V] + page->cp[V][cell->d[V][0] * 2 + 1];
984   bb[V][1] = clip[V][1] = ofs[V] + page->cp[V][cell->d[V][1] * 2];
985
986   int valign = (cell->n_contents
987                 ? cell->contents->options & TAB_VALIGN
988                 : TAB_TOP);
989   if (valign != TAB_TOP)
990     {
991       int height = page->params->measure_cell_height (
992         page->params->aux, cell, bb[H][1] - bb[H][0]);
993       int extra = bb[V][1] - bb[V][0] - height;
994       if (extra > 0)
995         {
996           if (valign == TAB_MIDDLE)
997             extra /= 2;
998           bb[V][0] += extra;
999         }
1000     }
1001
1002   of = find_overflow (page, cell->d[H][0], cell->d[V][0]);
1003   if (of)
1004     {
1005       enum table_axis axis;
1006
1007       for (axis = 0; axis < TABLE_N_AXES; axis++)
1008         {
1009           if (of->overflow[axis][0])
1010             {
1011               bb[axis][0] -= of->overflow[axis][0];
1012               if (cell->d[axis][0] == 0 && !page->is_edge_cutoff[axis][0])
1013                 clip[axis][0] = ofs[axis] + page->cp[axis][cell->d[axis][0] * 2];
1014             }
1015           if (of->overflow[axis][1])
1016             {
1017               bb[axis][1] += of->overflow[axis][1];
1018               if (cell->d[axis][1] == page->n[axis] && !page->is_edge_cutoff[axis][1])
1019                 clip[axis][1] = ofs[axis] + page->cp[axis][cell->d[axis][1] * 2 + 1];
1020             }
1021         }
1022     }
1023
1024   int spill[TABLE_N_AXES][2];
1025   for (enum table_axis axis = 0; axis < TABLE_N_AXES; axis++)
1026     {
1027       spill[axis][0] = rule_width (page, axis, cell->d[axis][0]) / 2;
1028       spill[axis][1] = rule_width (page, axis, cell->d[axis][1]) / 2;
1029     }
1030
1031   int color_idx = (cell->d[V][0] < page->h[V][0]
1032                    || page->n[V] - (cell->d[V][0] + 1) < page->h[V][1]
1033                    ? 0
1034                    : (cell->d[V][0] - page->h[V][0]) & 1);
1035   page->params->draw_cell (page->params->aux, cell, color_idx,
1036                            bb, spill, clip);
1037 }
1038
1039 /* Draws the cells of PAGE indicated in BB. */
1040 static void
1041 render_page_draw_cells (const struct render_page *page,
1042                         int ofs[TABLE_N_AXES], int bb[TABLE_N_AXES][2])
1043 {
1044   for (int y = bb[V][0]; y < bb[V][1]; y++)
1045     for (int x = bb[H][0]; x < bb[H][1]; )
1046       if (!is_rule (x) && !is_rule (y))
1047         {
1048           struct table_cell cell;
1049
1050           table_get_cell (page->table, x / 2, y / 2, &cell);
1051           if (y / 2 == bb[V][0] / 2 || y / 2 == cell.d[V][0])
1052             render_cell (page, ofs, &cell);
1053           x = rule_ofs (cell.d[H][1]);
1054           table_cell_free (&cell);
1055         }
1056       else
1057         x++;
1058
1059   for (int y = bb[V][0]; y < bb[V][1]; y++)
1060     for (int x = bb[H][0]; x < bb[H][1]; x++)
1061       if (is_rule (x) || is_rule (y))
1062         {
1063           int d[TABLE_N_AXES];
1064           d[H] = x;
1065           d[V] = y;
1066           render_rule (page, ofs, d);
1067         }
1068 }
1069
1070 /* Renders PAGE, by calling the 'draw_line' and 'draw_cell' functions from the
1071    render_params provided to render_page_create(). */
1072 static void
1073 render_page_draw (const struct render_page *page, int ofs[TABLE_N_AXES])
1074 {
1075   int bb[TABLE_N_AXES][2];
1076
1077   bb[H][0] = 0;
1078   bb[H][1] = page->n[H] * 2 + 1;
1079   bb[V][0] = 0;
1080   bb[V][1] = page->n[V] * 2 + 1;
1081
1082   render_page_draw_cells (page, ofs, bb);
1083 }
1084
1085 /* Returns the greatest value i, 0 <= i < n, such that cp[i] <= x0. */
1086 static int
1087 get_clip_min_extent (int x0, const int cp[], int n)
1088 {
1089   int low, high, best;
1090
1091   low = 0;
1092   high = n;
1093   best = 0;
1094   while (low < high)
1095     {
1096       int middle = low + (high - low) / 2;
1097
1098       if (cp[middle] <= x0)
1099         {
1100           best = middle;
1101           low = middle + 1;
1102         }
1103       else
1104         high = middle;
1105     }
1106
1107   return best;
1108 }
1109
1110 /* Returns the least value i, 0 <= i < n, such that cp[i] >= x1. */
1111 static int
1112 get_clip_max_extent (int x1, const int cp[], int n)
1113 {
1114   int low, high, best;
1115
1116   low = 0;
1117   high = n;
1118   best = n;
1119   while (low < high)
1120     {
1121       int middle = low + (high - low) / 2;
1122
1123       if (cp[middle] >= x1)
1124         best = high = middle;
1125       else
1126         low = middle + 1;
1127     }
1128
1129   while (best > 0 && cp[best - 1] == cp[best])
1130     best--;
1131
1132   return best;
1133 }
1134
1135 /* Renders the cells of PAGE that intersect (X,Y)-(X+W,Y+H), by calling the
1136    'draw_line' and 'draw_cell' functions from the render_params provided to
1137    render_page_create(). */
1138 static void
1139 render_page_draw_region (const struct render_page *page,
1140                          int ofs[TABLE_N_AXES], int clip[TABLE_N_AXES][2])
1141 {
1142   int bb[TABLE_N_AXES][2];
1143
1144   bb[H][0] = get_clip_min_extent (clip[H][0], page->cp[H], page->n[H] * 2 + 1);
1145   bb[H][1] = get_clip_max_extent (clip[H][1], page->cp[H], page->n[H] * 2 + 1);
1146   bb[V][0] = get_clip_min_extent (clip[V][0], page->cp[V], page->n[V] * 2 + 1);
1147   bb[V][1] = get_clip_max_extent (clip[V][1], page->cp[V], page->n[V] * 2 + 1);
1148
1149   render_page_draw_cells (page, ofs, bb);
1150 }
1151
1152 /* Breaking up tables to fit on a page. */
1153
1154 /* An iterator for breaking render_pages into smaller chunks. */
1155 struct render_break
1156   {
1157     struct render_page *page;   /* Page being broken up. */
1158     enum table_axis axis;       /* Axis along which 'page' is being broken. */
1159     int z;                      /* Next cell along 'axis'. */
1160     int pixel;                  /* Pixel offset within cell 'z' (usually 0). */
1161     int hw;                     /* Width of headers of 'page' along 'axis'. */
1162   };
1163
1164 static int needed_size (const struct render_break *, int cell);
1165 static bool cell_is_breakable (const struct render_break *, int cell);
1166 static struct render_page *render_page_select (const struct render_page *,
1167                                                enum table_axis,
1168                                                int z0, int p0,
1169                                                int z1, int p1);
1170
1171 /* Initializes render_break B for breaking PAGE along AXIS.
1172    Takes ownership of PAGE. */
1173 static void
1174 render_break_init (struct render_break *b, struct render_page *page,
1175                    enum table_axis axis)
1176 {
1177   b->page = page;
1178   b->axis = axis;
1179   b->z = page->h[axis][0];
1180   b->pixel = 0;
1181   b->hw = headers_width (page, axis);
1182 }
1183
1184 /* Initializes B as a render_break structure for which
1185    render_break_has_next() always returns false. */
1186 static void
1187 render_break_init_empty (struct render_break *b)
1188 {
1189   b->page = NULL;
1190   b->axis = TABLE_HORZ;
1191   b->z = 0;
1192   b->pixel = 0;
1193   b->hw = 0;
1194 }
1195
1196 /* Frees B and unrefs the render_page that it owns. */
1197 static void
1198 render_break_destroy (struct render_break *b)
1199 {
1200   if (b != NULL)
1201     {
1202       render_page_unref (b->page);
1203       b->page = NULL;
1204     }
1205 }
1206
1207 /* Returns true if B still has cells that are yet to be returned,
1208    false if all of B's page has been processed. */
1209 static bool
1210 render_break_has_next (const struct render_break *b)
1211 {
1212   const struct render_page *page = b->page;
1213   enum table_axis axis = b->axis;
1214
1215   return page != NULL && b->z < page->n[axis] - page->h[axis][1];
1216 }
1217
1218 /* Returns a new render_page that is up to SIZE pixels wide along B's axis.
1219    Returns a null pointer if B has already been completely broken up, or if
1220    SIZE is too small to reasonably render any cells.  The latter will never
1221    happen if SIZE is at least as large as the page size passed to
1222    render_page_create() along B's axis. */
1223 static struct render_page *
1224 render_break_next (struct render_break *b, int size)
1225 {
1226   const struct render_page *page = b->page;
1227   enum table_axis axis = b->axis;
1228   struct render_page *subpage;
1229   int z, pixel;
1230
1231   if (!render_break_has_next (b))
1232     return NULL;
1233
1234   pixel = 0;
1235   for (z = b->z; z < page->n[axis] - page->h[axis][1]; z++)
1236     {
1237       int needed = needed_size (b, z + 1);
1238       if (needed > size)
1239         {
1240           if (cell_is_breakable (b, z))
1241             {
1242               /* If there is no right header and we render a partial cell on
1243                  the right side of the body, then we omit the rightmost rule of
1244                  the body.  Otherwise the rendering is deceptive because it
1245                  looks like the whole cell is present instead of a partial
1246                  cell.
1247
1248                  This is similar to code for the left side in needed_size(). */
1249               int rule_allowance = (page->h[axis][1]
1250                                     ? 0
1251                                     : rule_width (page, axis, z));
1252
1253               /* The amount that, if we added cell 'z', the rendering would
1254                  overfill the allocated 'size'. */
1255               int overhang = needed - size - rule_allowance;
1256
1257               /* The width of cell 'z'. */
1258               int cell_size = cell_width (page, axis, z);
1259
1260               /* The amount trimmed off the left side of 'z',
1261                  and the amount left to render. */
1262               int cell_ofs = z == b->z ? b->pixel : 0;
1263               int cell_left = cell_size - cell_ofs;
1264
1265               /* A small but visible width.  */
1266               int em = page->params->font_size[axis];
1267
1268               /* If some of the cell remains to render,
1269                  and there would still be some of the cell left afterward,
1270                  then partially render that much of the cell. */
1271               pixel = (cell_left && cell_left > overhang
1272                        ? cell_left - overhang + cell_ofs
1273                        : 0);
1274
1275               /* If there would be only a tiny amount of the cell left after
1276                  rendering it partially, reduce the amount rendered slightly
1277                  to make the output look a little better. */
1278               if (pixel + em > cell_size)
1279                 pixel = MAX (pixel - em, 0);
1280
1281               /* If we're breaking vertically, then consider whether the cells
1282                  being broken have a better internal breakpoint than the exact
1283                  number of pixels available, which might look bad e.g. because
1284                  it breaks in the middle of a line of text. */
1285               if (axis == TABLE_VERT && page->params->adjust_break)
1286                 {
1287                   int x;
1288
1289                   for (x = 0; x < page->n[H]; )
1290                     {
1291                       struct table_cell cell;
1292                       int better_pixel;
1293                       int w;
1294
1295                       table_get_cell (page->table, x, z, &cell);
1296                       w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
1297                       better_pixel = page->params->adjust_break (
1298                         page->params->aux, &cell, w, pixel);
1299                       x = cell.d[H][1];
1300                       table_cell_free (&cell);
1301
1302                       if (better_pixel < pixel)
1303                         {
1304                           if (better_pixel > (z == b->z ? b->pixel : 0))
1305                             {
1306                               pixel = better_pixel;
1307                               break;
1308                             }
1309                           else if (better_pixel == 0 && z != b->z)
1310                             {
1311                               pixel = 0;
1312                               break;
1313                             }
1314                         }
1315                     }
1316                 }
1317             }
1318           break;
1319         }
1320     }
1321
1322   if (z == b->z && !pixel)
1323     return NULL;
1324
1325   subpage = render_page_select (page, axis, b->z, b->pixel,
1326                                 pixel ? z + 1 : z,
1327                                 pixel ? cell_width (page, axis, z) - pixel
1328                                 : 0);
1329   b->z = z;
1330   b->pixel = pixel;
1331   return subpage;
1332 }
1333
1334 /* Returns the width that would be required along B's axis to render a page
1335    from B's current position up to but not including CELL. */
1336 static int
1337 needed_size (const struct render_break *b, int cell)
1338 {
1339   const struct render_page *page = b->page;
1340   enum table_axis axis = b->axis;
1341   int size;
1342
1343   /* Width of left header not including its rightmost rule.  */
1344   size = axis_width (page, axis, 0, rule_ofs (page->h[axis][0]));
1345
1346   /* If we have a pixel offset and there is no left header, then we omit the
1347      leftmost rule of the body.  Otherwise the rendering is deceptive because
1348      it looks like the whole cell is present instead of a partial cell.
1349
1350      Otherwise (if there are headers) we will be merging two rules: the
1351      rightmost rule in the header and the leftmost rule in the body.  We assume
1352      that the width of a merged rule is the larger of the widths of either rule
1353      invidiually. */
1354   if (b->pixel == 0 || page->h[axis][0])
1355     size += MAX (rule_width (page, axis, page->h[axis][0]),
1356                  rule_width (page, axis, b->z));
1357
1358   /* Width of body, minus any pixel offset in the leftmost cell. */
1359   size += joined_width (page, axis, b->z, cell) - b->pixel;
1360
1361   /* Width of rightmost rule in body merged with leftmost rule in headers. */
1362   size += MAX (rule_width_r (page, axis, page->h[axis][1]),
1363                rule_width (page, axis, cell));
1364
1365   /* Width of right header not including its leftmost rule. */
1366   size += axis_width (page, axis, rule_ofs_r (page, axis, page->h[axis][1]),
1367                       rule_ofs_r (page, axis, 0));
1368
1369   /* Join crossing. */
1370   if (page->h[axis][0] && page->h[axis][1])
1371     size += page->join_crossing[axis][b->z];
1372
1373   return size;
1374 }
1375
1376 /* Returns true if CELL along B's axis may be broken across a page boundary.
1377
1378    This is just a heuristic.  Breaking cells across page boundaries can save
1379    space, but it looks ugly. */
1380 static bool
1381 cell_is_breakable (const struct render_break *b, int cell)
1382 {
1383   const struct render_page *page = b->page;
1384   enum table_axis axis = b->axis;
1385
1386   return cell_width (page, axis, cell) >= page->params->min_break[axis];
1387 }
1388 \f
1389 /* render_pager. */
1390
1391 struct render_pager
1392   {
1393     const struct render_params *params;
1394
1395     struct render_page **pages;
1396     size_t n_pages, allocated_pages;
1397
1398     size_t cur_page;
1399     struct render_break x_break;
1400     struct render_break y_break;
1401   };
1402
1403 static const struct render_page *
1404 render_pager_add_table (struct render_pager *p, struct table *table,
1405                         int min_width)
1406 {
1407   struct render_page *page;
1408
1409   if (p->n_pages >= p->allocated_pages)
1410     p->pages = x2nrealloc (p->pages, &p->allocated_pages, sizeof *p->pages);
1411   page = p->pages[p->n_pages++] = render_page_create (p->params, table,
1412                                                       min_width);
1413   return page;
1414 }
1415
1416 static void
1417 render_pager_start_page (struct render_pager *p)
1418 {
1419   render_break_init (&p->x_break, render_page_ref (p->pages[p->cur_page++]),
1420                      H);
1421   render_break_init_empty (&p->y_break);
1422 }
1423
1424 static void
1425 add_footnote_page (struct render_pager *p, const struct table_item *item)
1426 {
1427   const struct footnote **f;
1428   size_t n_footnotes = table_collect_footnotes (item, &f);
1429   if (!n_footnotes)
1430     return;
1431
1432   struct tab_table *t = tab_create (2, n_footnotes);
1433
1434   for (size_t i = 0; i < n_footnotes; i++)
1435     if (f[i])
1436       {
1437         tab_text_format (t, 0, i, TAB_LEFT, "%s.", f[i]->marker);
1438         tab_text (t, 1, i, TAB_LEFT, f[i]->content);
1439         if (f[i]->style)
1440           {
1441             tab_add_style (t, 0, i, f[i]->style);
1442             tab_add_style (t, 1, i, f[i]->style);
1443           }
1444       }
1445   render_pager_add_table (p, &t->table, 0);
1446
1447   free (f);
1448 }
1449
1450 static void
1451 add_text_page (struct render_pager *p, const struct table_item_text *t,
1452                int min_width)
1453 {
1454   if (!t)
1455     return;
1456
1457   struct tab_table *tab = tab_create (1, 1);
1458   tab_text (tab, 0, 0, t->halign, t->content);
1459   for (size_t i = 0; i < t->n_footnotes; i++)
1460     tab_add_footnote (tab, 0, 0, t->footnotes[i]);
1461   if (t->style)
1462     tab->styles[0] = cell_style_clone (tab->container, t->style);
1463   render_pager_add_table (p, &tab->table, min_width);
1464 }
1465
1466 /* Creates and returns a new render_pager for rendering TABLE_ITEM on the
1467    device with the given PARAMS. */
1468 struct render_pager *
1469 render_pager_create (const struct render_params *params,
1470                      const struct table_item *table_item)
1471 {
1472   const struct table *table = table_item_get_table (table_item);
1473   struct render_pager *p;
1474
1475   p = xzalloc (sizeof *p);
1476   p->params = params;
1477
1478   struct render_page *page = render_page_create (params, table_ref (table), 0);
1479   struct render_break b;
1480   render_break_init (&b, page, H);
1481   struct render_page *subpage = render_break_next (&b, p->params->size[H]);
1482   int title_width = subpage ? subpage->cp[H][2 * subpage->n[H] + 1] : 0;
1483   render_page_unref (subpage);
1484   render_break_destroy (&b);
1485
1486   /* Title. */
1487   add_text_page (p, table_item_get_title (table_item), title_width);
1488
1489   /* Layers. */
1490   add_text_page (p, table_item_get_layers (table_item), title_width);
1491
1492   /* Body. */
1493   render_pager_add_table (p, table_ref (table_item_get_table (table_item)), 0);
1494
1495   /* Caption. */
1496   add_text_page (p, table_item_get_caption (table_item), 0);
1497
1498   /* Footnotes. */
1499   add_footnote_page (p, table_item);
1500
1501   render_pager_start_page (p);
1502
1503   return p;
1504 }
1505
1506 /* Destroys P. */
1507 void
1508 render_pager_destroy (struct render_pager *p)
1509 {
1510   if (p)
1511     {
1512       size_t i;
1513
1514       render_break_destroy (&p->x_break);
1515       render_break_destroy (&p->y_break);
1516       for (i = 0; i < p->n_pages; i++)
1517         render_page_unref (p->pages[i]);
1518       free (p->pages);
1519       free (p);
1520     }
1521 }
1522
1523 /* Returns true if P has content remaining to render, false if rendering is
1524    done. */
1525 bool
1526 render_pager_has_next (const struct render_pager *p_)
1527 {
1528   struct render_pager *p = CONST_CAST (struct render_pager *, p_);
1529
1530   while (!render_break_has_next (&p->y_break))
1531     {
1532       render_break_destroy (&p->y_break);
1533       if (!render_break_has_next (&p->x_break))
1534         {
1535           render_break_destroy (&p->x_break);
1536           if (p->cur_page >= p->n_pages)
1537             {
1538               render_break_init_empty (&p->x_break);
1539               render_break_init_empty (&p->y_break);
1540               return false;
1541             }
1542           render_pager_start_page (p);
1543         }
1544       else
1545         render_break_init (&p->y_break,
1546                            render_break_next (&p->x_break, p->params->size[H]), V);
1547     }
1548   return true;
1549 }
1550
1551 /* Draws a chunk of content from P to fit in a space that has vertical size
1552    SPACE and the horizontal size specified in the render_params passed to
1553    render_page_create().  Returns the amount of space actually used by the
1554    rendered chunk, which will be 0 if SPACE is too small to render anything or
1555    if no content remains (use render_pager_has_next() to distinguish these
1556    cases). */
1557 int
1558 render_pager_draw_next (struct render_pager *p, int space)
1559 {
1560   int ofs[TABLE_N_AXES] = { 0, 0 };
1561   size_t start_page = SIZE_MAX;
1562
1563   while (render_pager_has_next (p))
1564     {
1565       struct render_page *page;
1566
1567       if (start_page == p->cur_page)
1568         break;
1569       start_page = p->cur_page;
1570
1571       page = render_break_next (&p->y_break, space - ofs[V]);
1572       if (!page)
1573         break;
1574
1575       render_page_draw (page, ofs);
1576       ofs[V] += render_page_get_size (page, V);
1577       render_page_unref (page);
1578     }
1579   return ofs[V];
1580 }
1581
1582 /* Draws all of P's content. */
1583 void
1584 render_pager_draw (const struct render_pager *p)
1585 {
1586   render_pager_draw_region (p, 0, 0, INT_MAX, INT_MAX);
1587 }
1588
1589 /* Draws the region of P's content that lies in the region (X,Y)-(X+W,Y+H).
1590    Some extra content might be drawn; the device should perform clipping as
1591    necessary. */
1592 void
1593 render_pager_draw_region (const struct render_pager *p,
1594                           int x, int y, int w, int h)
1595 {
1596   int ofs[TABLE_N_AXES] = { 0, 0 };
1597   int clip[TABLE_N_AXES][2];
1598   size_t i;
1599
1600   clip[H][0] = x;
1601   clip[H][1] = x + w;
1602   for (i = 0; i < p->n_pages; i++)
1603     {
1604       const struct render_page *page = p->pages[i];
1605       int size = render_page_get_size (page, V);
1606
1607       clip[V][0] = MAX (y, ofs[V]) - ofs[V];
1608       clip[V][1] = MIN (y + h, ofs[V] + size) - ofs[V];
1609       if (clip[V][1] > clip[V][0])
1610         render_page_draw_region (page, ofs, clip);
1611
1612       ofs[V] += size;
1613     }
1614 }
1615
1616 /* Returns the size of P's content along AXIS; i.e. the content's width if AXIS
1617    is TABLE_HORZ and its length if AXIS is TABLE_VERT. */
1618 int
1619 render_pager_get_size (const struct render_pager *p, enum table_axis axis)
1620 {
1621   int size = 0;
1622   size_t i;
1623
1624   for (i = 0; i < p->n_pages; i++)
1625     {
1626       int subsize = render_page_get_size (p->pages[i], axis);
1627       size = axis == H ? MAX (size, subsize) : size + subsize;
1628     }
1629
1630   return size;
1631 }
1632
1633 int
1634 render_pager_get_best_breakpoint (const struct render_pager *p, int height)
1635 {
1636   int y = 0;
1637   size_t i;
1638
1639   for (i = 0; i < p->n_pages; i++)
1640     {
1641       int size = render_page_get_size (p->pages[i], V);
1642       if (y + size >= height)
1643         return render_page_get_best_breakpoint (p->pages[i], height - y) + y;
1644       y += size;
1645     }
1646
1647   return height;
1648 }
1649 \f
1650 /* render_page_select() and helpers. */
1651
1652 struct render_page_selection
1653   {
1654     const struct render_page *page; /* Page whose slice we are selecting. */
1655     struct render_page *subpage; /* New page under construction. */
1656     enum table_axis a;   /* Axis of 'page' along which 'subpage' is a slice. */
1657     enum table_axis b;   /* The opposite of 'a'. */
1658     int z0;              /* First cell along 'a' being selected. */
1659     int z1;              /* Last cell being selected, plus 1. */
1660     int p0;              /* Number of pixels to trim off left side of z0. */
1661     int p1;              /* Number of pixels to trim off right side of z1-1. */
1662   };
1663
1664 static void cell_to_subpage (struct render_page_selection *,
1665                              const struct table_cell *,
1666                              int subcell[TABLE_N_AXES]);
1667 static const struct render_overflow *find_overflow_for_cell (
1668   struct render_page_selection *, const struct table_cell *);
1669 static struct render_overflow *insert_overflow (struct render_page_selection *,
1670                                                 const struct table_cell *);
1671
1672 /* Creates and returns a new render_page whose contents are a subregion of
1673    PAGE's contents.  The new render_page includes cells Z0 through Z1
1674    (exclusive) along AXIS, plus any headers on AXIS.
1675
1676    If P0 is nonzero, then it is a number of pixels to exclude from the left or
1677    top (according to AXIS) of cell Z0.  Similarly, P1 is a number of pixels to
1678    exclude from the right or bottom of cell Z1 - 1.  (P0 and P1 are used to
1679    render cells that are too large to fit on a single page.)
1680
1681    The whole of axis !AXIS is included.  (The caller may follow up with another
1682    call to render_page_select() to select on !AXIS to select on that axis as
1683    well.)
1684
1685    The caller retains ownership of PAGE, which is not modified. */
1686 static struct render_page *
1687 render_page_select (const struct render_page *page, enum table_axis axis,
1688                     int z0, int p0, int z1, int p1)
1689 {
1690   struct render_page_selection s;
1691   enum table_axis a = axis;
1692   enum table_axis b = !a;
1693   struct render_page *subpage;
1694   struct render_overflow *ro;
1695   int *dcp, *scp;
1696   int *jc;
1697   int z;
1698
1699
1700   /* Optimize case where all of PAGE is selected by just incrementing the
1701      reference count. */
1702   if (z0 == page->h[a][0] && p0 == 0
1703       && z1 == page->n[a] - page->h[a][1] && p1 == 0)
1704     {
1705       struct render_page *page_rw = CONST_CAST (struct render_page *, page);
1706       page_rw->ref_cnt++;
1707       return page_rw;
1708     }
1709
1710   /* Allocate subpage. */
1711   subpage = render_page_allocate (page->params,
1712                                   table_select_slice (
1713                                     table_ref (page->table),
1714                                     a, z0, z1, true));
1715
1716   /* An edge is cut off if it was cut off in PAGE or if we're trimming pixels
1717      off that side of the page and there are no headers. */
1718   subpage->is_edge_cutoff[a][0] =
1719     subpage->h[a][0] == 0 && (p0 || (z0 == 0 && page->is_edge_cutoff[a][0]));
1720   subpage->is_edge_cutoff[a][1] =
1721     subpage->h[a][1] == 0 && (p1 || (z1 == page->n[a]
1722                                      && page->is_edge_cutoff[a][1]));
1723   subpage->is_edge_cutoff[b][0] = page->is_edge_cutoff[b][0];
1724   subpage->is_edge_cutoff[b][1] = page->is_edge_cutoff[b][1];
1725
1726   /* Select join crossings from PAGE into subpage. */
1727   jc = subpage->join_crossing[a];
1728   for (z = 0; z < page->h[a][0]; z++)
1729     *jc++ = page->join_crossing[a][z];
1730   for (z = z0; z <= z1; z++)
1731     *jc++ = page->join_crossing[a][z];
1732   for (z = page->n[a] - page->h[a][1]; z < page->n[a]; z++)
1733     *jc++ = page->join_crossing[a][z];
1734   assert (jc == &subpage->join_crossing[a][subpage->n[a] + 1]);
1735
1736   memcpy (subpage->join_crossing[b], page->join_crossing[b],
1737           (subpage->n[b] + 1) * sizeof **subpage->join_crossing);
1738
1739   /* Select widths from PAGE into subpage. */
1740   scp = page->cp[a];
1741   dcp = subpage->cp[a];
1742   *dcp = 0;
1743   for (z = 0; z <= rule_ofs (subpage->h[a][0]); z++, dcp++)
1744     {
1745       if (z == 0 && subpage->is_edge_cutoff[a][0])
1746         dcp[1] = dcp[0];
1747       else
1748         dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1749     }
1750   for (z = cell_ofs (z0); z <= cell_ofs (z1 - 1); z++, dcp++)
1751     {
1752       dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1753       if (z == cell_ofs (z0))
1754         {
1755           dcp[1] -= p0;
1756           if (page->h[a][0] && page->h[a][1])
1757             dcp[1] += page->join_crossing[a][z / 2];
1758         }
1759       if (z == cell_ofs (z1 - 1))
1760         dcp[1] -= p1;
1761     }
1762   for (z = rule_ofs_r (page, a, subpage->h[a][1]);
1763        z <= rule_ofs_r (page, a, 0); z++, dcp++)
1764     {
1765       if (z == rule_ofs_r (page, a, 0) && subpage->is_edge_cutoff[a][1])
1766         dcp[1] = dcp[0];
1767       else
1768         dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1769     }
1770   assert (dcp == &subpage->cp[a][2 * subpage->n[a] + 1]);
1771
1772   for (z = 0; z < page->n[b] * 2 + 2; z++)
1773     subpage->cp[b][z] = page->cp[b][z];
1774
1775   /* Add new overflows. */
1776   s.page = page;
1777   s.a = a;
1778   s.b = b;
1779   s.z0 = z0;
1780   s.z1 = z1;
1781   s.p0 = p0;
1782   s.p1 = p1;
1783   s.subpage = subpage;
1784
1785   if (!page->h[a][0] || z0 > page->h[a][0] || p0)
1786     for (z = 0; z < page->n[b]; )
1787       {
1788         struct table_cell cell;
1789         int d[TABLE_N_AXES];
1790         bool overflow0;
1791         bool overflow1;
1792
1793         d[a] = z0;
1794         d[b] = z;
1795
1796         table_get_cell (page->table, d[H], d[V], &cell);
1797         overflow0 = p0 || cell.d[a][0] < z0;
1798         overflow1 = cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1);
1799         if (overflow0 || overflow1)
1800           {
1801             ro = insert_overflow (&s, &cell);
1802
1803             if (overflow0)
1804               {
1805                 ro->overflow[a][0] += p0 + axis_width (
1806                   page, a, cell_ofs (cell.d[a][0]), cell_ofs (z0));
1807                 if (page->h[a][0] && page->h[a][1])
1808                   ro->overflow[a][0] -= page->join_crossing[a][cell.d[a][0]
1809                                                                + 1];
1810               }
1811
1812             if (overflow1)
1813               {
1814                 ro->overflow[a][1] += p1 + axis_width (
1815                   page, a, cell_ofs (z1), cell_ofs (cell.d[a][1]));
1816                 if (page->h[a][0] && page->h[a][1])
1817                   ro->overflow[a][1] -= page->join_crossing[a][cell.d[a][1]];
1818               }
1819           }
1820         z = cell.d[b][1];
1821         table_cell_free (&cell);
1822       }
1823
1824   if (!page->h[a][1] || z1 < page->n[a] - page->h[a][1] || p1)
1825     for (z = 0; z < page->n[b]; )
1826       {
1827         struct table_cell cell;
1828         int d[TABLE_N_AXES];
1829
1830         d[a] = z1 - 1;
1831         d[b] = z;
1832         table_get_cell (page->table, d[H], d[V], &cell);
1833         if ((cell.d[a][1] > z1 || (cell.d[a][1] == z1 && p1))
1834             && find_overflow_for_cell (&s, &cell) == NULL)
1835           {
1836             ro = insert_overflow (&s, &cell);
1837             ro->overflow[a][1] += p1 + axis_width (page, a, cell_ofs (z1),
1838                                                    cell_ofs (cell.d[a][1]));
1839           }
1840         z = cell.d[b][1];
1841         table_cell_free (&cell);
1842       }
1843
1844   /* Copy overflows from PAGE into subpage. */
1845   HMAP_FOR_EACH (ro, struct render_overflow, node, &page->overflows)
1846     {
1847       struct table_cell cell;
1848
1849       table_get_cell (page->table, ro->d[H], ro->d[V], &cell);
1850       if (cell.d[a][1] > z0 && cell.d[a][0] < z1
1851           && find_overflow_for_cell (&s, &cell) == NULL)
1852         insert_overflow (&s, &cell);
1853       table_cell_free (&cell);
1854     }
1855
1856   return subpage;
1857 }
1858
1859 /* Given CELL, a table_cell within S->page, stores in SUBCELL the (x,y)
1860    coordinates of the top-left cell as it will appear in S->subpage.
1861
1862    CELL must actually intersect the region of S->page that is being selected
1863    by render_page_select() or the results will not make any sense. */
1864 static void
1865 cell_to_subpage (struct render_page_selection *s,
1866                  const struct table_cell *cell, int subcell[TABLE_N_AXES])
1867 {
1868   enum table_axis a = s->a;
1869   enum table_axis b = s->b;
1870   int ha0 = s->subpage->h[a][0];
1871
1872   subcell[a] = MAX (cell->d[a][0] - s->z0 + ha0, ha0);
1873   subcell[b] = cell->d[b][0];
1874 }
1875
1876 /* Given CELL, a table_cell within S->page, returns the render_overflow for
1877    that cell in S->subpage, if there is one, and a null pointer otherwise.
1878
1879    CELL must actually intersect the region of S->page that is being selected
1880    by render_page_select() or the results will not make any sense. */
1881 static const struct render_overflow *
1882 find_overflow_for_cell (struct render_page_selection *s,
1883                         const struct table_cell *cell)
1884 {
1885   int subcell[2];
1886
1887   cell_to_subpage (s, cell, subcell);
1888   return find_overflow (s->subpage, subcell[H], subcell[V]);
1889 }
1890
1891 /* Given CELL, a table_cell within S->page, inserts a render_overflow for that
1892    cell in S->subpage (which must not already exist).  Initializes the new
1893    render_overflow's 'overflow' member from the overflow for CELL in S->page,
1894    if there is one.
1895
1896    CELL must actually intersect the region of S->page that is being selected
1897    by render_page_select() or the results will not make any sense. */
1898 static struct render_overflow *
1899 insert_overflow (struct render_page_selection *s,
1900                  const struct table_cell *cell)
1901 {
1902   const struct render_overflow *old;
1903   struct render_overflow *of;
1904
1905   of = xzalloc (sizeof *of);
1906   cell_to_subpage (s, cell, of->d);
1907   hmap_insert (&s->subpage->overflows, &of->node,
1908                hash_cell (of->d[H], of->d[V]));
1909
1910   old = find_overflow (s->page, cell->d[H][0], cell->d[V][0]);
1911   if (old != NULL)
1912     memcpy (of->overflow, old->overflow, sizeof of->overflow);
1913
1914   return of;
1915 }