Rewrite PSPP output engine.
[pspp-builds.git] / src / output / render.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2009 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 <stdlib.h>
22 #include <string.h>
23
24 #include "libpspp/assertion.h"
25 #include "libpspp/hash-functions.h"
26 #include "libpspp/hmap.h"
27 #include "output/render.h"
28 #include "output/table.h"
29
30 #include "gl/minmax.h"
31 #include "gl/xalloc.h"
32
33 /* This file uses TABLE_HORZ and TABLE_VERT enough to warrant abbreviating. */
34 #define H TABLE_HORZ
35 #define V TABLE_VERT
36 \f
37 /* A layout for rendering a specific table on a specific device.
38
39    May represent the layout of an entire table presented to
40    render_page_create(), or a rectangular subregion of a table broken out using
41    render_page_next() to allow a table to be broken across multiple pages. */
42 struct render_page
43   {
44     const struct render_params *params; /* Parameters of the target device. */
45     struct table *table;                /* Table rendered. */
46     int ref_cnt;
47
48     /* Local copies of table->n and table->h, for convenience. */
49     int n[TABLE_N_AXES];
50     int h[TABLE_N_AXES][2];
51
52     /* cp[H] represents x positions within the table.
53        cp[H][0] = 0.
54        cp[H][1] = the width of the leftmost vertical rule.
55        cp[H][2] = cp[H][1] + the width of the leftmost column.
56        cp[H][3] = cp[H][2] + the width of the second-from-left vertical rule.
57        and so on:
58        cp[H][2 * nc] = x position of the rightmost vertical rule.
59        cp[H][2 * nc + 1] = total table width including all rules.
60
61        Similarly, cp[V] represents y positions within the table.
62        cp[V][0] = 0.
63        cp[V][1] = the height of the topmost horizontal rule.
64        cp[V][2] = cp[V][1] + the height of the topmost column.
65        cp[V][3] = cp[V][2] + the height of the second-from-top horizontal rule.
66        and so on:
67        cp[V][2 * nr] = y position of the bottommost horizontal rule.
68        cp[V][2 * nr + 1] = total table height including all rules.
69
70        Rules and columns can have width or height 0, in which case consecutive
71        values in this array are equal. */
72     int *cp[TABLE_N_AXES];
73
74     /* render_break_next() can break a table such that some cells are not fully
75        contained within a render_page.  This will happen if a cell is too wide
76        or two tall to fit on a single page, or if a cell spans multiple rows or
77        columns and the page only includes some of those rows or columns.
78
79        This hash table contains "struct render_overflow"s that represents each
80        such cell that doesn't completely fit on this page.
81
82        Each overflow cell borders at least one header edge of the table and may
83        border more.  (A single table cell that is so large that it fills the
84        entire page can overflow on all four sides!) */
85     struct hmap overflows;
86
87     /* If a single column (or row) is too wide (or tall) to fit on a page
88        reasonably, then render_break_next() will split a single row or column
89        across multiple render_pages.  This member indicates when this has
90        happened:
91
92        is_edge_cutoff[H][0] is true if pixels have been cut off the left side
93        of the leftmost column in this page, and false otherwise.
94
95        is_edge_cutoff[H][1] is true if pixels have been cut off the right side
96        of the rightmost column in this page, and false otherwise.
97
98        is_edge_cutoff[V][0] and is_edge_cutoff[V][1] are similar for the top
99        and bottom of the table.
100
101        The effect of is_edge_cutoff is to prevent rules along the edge in
102        question from being rendered.
103
104        When is_edge_cutoff is true for a given edge, the 'overflows' hmap will
105        contain a node for each cell along that edge. */
106     bool is_edge_cutoff[TABLE_N_AXES][2];
107
108     /* If part of a joined cell would be cut off by breaking a table along
109        'axis' at the rule with offset 'z' (where 0 <= z <= n[axis]), then
110        join_crossing[axis][z] is the thickness of the rule that would be cut
111        off.
112
113        This is used to know to allocate extra space for breaking at such a
114        position, so that part of the cell's content is not lost.
115
116        This affects breaking a table only when headers are present.  When
117        headers are not present, the rule's thickness is used for cell content,
118        so no part of the cell's content is lost (and in fact it is duplicated
119        across both pages). */
120     int *join_crossing[TABLE_N_AXES];
121   };
122
123 /* Returns the offset in struct render_page's cp[axis] array of the rule with
124    index RULE_IDX.  That is, if RULE_IDX is 0, then the offset is that of the
125    leftmost or topmost rule; if RULE_IDX is 1, then the offset is that of the
126    next rule to the right (or below); and so on. */
127 static int
128 rule_ofs (int rule_idx)
129 {
130   return rule_idx * 2;
131 }
132
133 /* Returns the offset in struct render_page's cp[axis] array of the rule with
134    index RULE_IDX_R, which counts from the right side (or bottom) of the page
135    left (or up), according to whether AXIS is H or V, respectively.  That is,
136    if RULE_IDX_R is 0, then the offset is that of the rightmost or bottommost
137    rule; if RULE_IDX is 1, then the offset is that of the next rule to the left
138    (or above); and so on. */
139 static int
140 rule_ofs_r (const struct render_page *page, int axis, int rule_idx_r)
141 {
142   return (page->n[axis] - rule_idx_r) * 2;
143 }
144
145 /* Returns the offset in struct render_page's cp[axis] array of the cell with
146    index CELL_IDX.  That is, if CELL_IDX is 0, then the offset is that of the
147    leftmost or topmost cell; if CELL_IDX is 1, then the offset is that of the
148    next cell to the right (or below); and so on. */
149 static int
150 cell_ofs (int cell_idx)
151 {
152   return cell_idx * 2 + 1;
153 }
154
155 /* Returns the width of PAGE along AXIS from OFS0 to OFS1, exclusive. */
156 static int
157 axis_width (const struct render_page *page, int axis, int ofs0, int ofs1)
158 {
159   return page->cp[axis][ofs1] - page->cp[axis][ofs0];
160 }
161
162 /* Returns the width of the headers in PAGE along AXIS. */
163 static int
164 headers_width (const struct render_page *page, int axis)
165 {
166   int h0 = page->h[axis][0];
167   int w0 = axis_width (page, axis, rule_ofs (0), cell_ofs (h0));
168   int n = page->n[axis];
169   int h1 = page->h[axis][1];
170   int w1 = axis_width (page, axis, rule_ofs_r (page, axis, h1), cell_ofs (n));
171   return w0 + w1;
172 }
173
174 /* Returns the width of cell X along AXIS in PAGE. */
175 static int
176 cell_width (const struct render_page *page, int axis, int x)
177 {
178   return axis_width (page, axis, cell_ofs (x), cell_ofs (x) + 1);
179 }
180
181 /* Returns the width of cells X0 through X1, exclusive, along AXIS in PAGE. */
182 static int
183 joined_width (const struct render_page *page, int axis, int x0, int x1)
184 {
185   return axis_width (page, axis, cell_ofs (x0), cell_ofs (x1) - 1);
186 }
187
188 /* Returns the width of the widest cell, excluding headers, along AXIS in
189    PAGE. */
190 static int
191 max_cell_width (const struct render_page *page, int axis)
192 {
193   int n = page->n[axis];
194   int x0 = page->h[axis][0];
195   int x1 = n - page->h[axis][1];
196   int x, max;
197
198   max = 0;
199   for (x = x0; x < x1; x++)
200     {
201       int w = cell_width (page, axis, x);
202       if (w > max)
203         max = w;
204     }
205   return max;
206 }
207 \f
208 /* A cell that doesn't completely fit on the render_page. */
209 struct render_overflow
210   {
211     struct hmap_node node;      /* In render_page's 'overflows' hmap. */
212
213     /* Occupied region of page.
214
215        d[H][0] is the leftmost column.
216        d[H][1] is the rightmost column, plus 1.
217        d[V][0] is the top row.
218        d[V][1] is the bottom row, plus 1.
219
220        The cell in its original table might occupy a larger region.  This
221        member reflects the size of the cell in the current render_page, after
222        trimming off any rows or columns due to page-breaking. */
223     int d[TABLE_N_AXES];
224
225     /* The space that has been trimmed off the cell:
226
227        overflow[H][0]: space trimmed off its left side.
228        overflow[H][1]: space trimmed off its right side.
229        overflow[V][0]: space trimmed off its top.
230        overflow[V][1]: space trimmed off its bottom.
231
232        During rendering, this information is used to position the rendered
233        portion of the cell within the available space.
234
235        When a cell is rendered, sometimes it is permitted to spill over into
236        space that is ordinarily reserved for rules.  Either way, this space is
237        still included in overflow values.
238
239        Suppose, for example, that a cell that joins 2 columns has a width of 60
240        pixels and content "abcdef", that the 2 columns that it joins have
241        widths of 20 and 30 pixels, respectively, and that therefore the rule
242        between the two joined columns has a width of 10 (20 + 10 + 30 = 60).
243        It might render like this, if each character is 10x10, and showing a few
244        extra table cells for context:
245
246                                      +------+
247                                      |abcdef|
248                                      +--+---+
249                                      |gh|ijk|
250                                      +--+---+
251
252        If this render_page is broken at the rule that separates "gh" from
253        "ijk", then the page that contains the left side of the "abcdef" cell
254        will have overflow[H][1] of 10 + 30 = 40 for its portion of the cell,
255        and the page that contains the right side of the cell will have
256        overflow[H][0] of 20 + 10 = 30.  The two resulting pages would look like
257        this:
258
259
260                                        +---
261                                        |abc
262                                        +--+
263                                        |gh|
264                                        +--+
265
266        and:
267
268                                        ----+
269                                        cdef|
270                                        +---+
271                                        |ijk|
272                                        +---+
273     */
274     int overflow[TABLE_N_AXES][2];
275   };
276
277 /* Returns a hash value for (X,Y). */
278 static unsigned int
279 hash_overflow (int x, int y)
280 {
281   return hash_int (x + (y << 16), 0);
282 }
283
284 /* Searches PAGE's set of render_overflow for one whose top-left cell is
285    (X,Y).  Returns it, if there is one, otherwise a null pointer. */
286 static const struct render_overflow *
287 find_overflow (const struct render_page *page, int x, int y)
288 {
289   if (!hmap_is_empty (&page->overflows))
290     {
291       const struct render_overflow *of;
292
293       HMAP_FOR_EACH_WITH_HASH (of, struct render_overflow, node,
294                                hash_overflow (x, y), &page->overflows)
295         if (x == of->d[H] && y == of->d[V])
296           return of;
297     }
298
299   return NULL;
300 }
301 \f
302 /* Row or column dimensions.  Used to figure the size of a table in
303    render_page_create() and discarded after that. */
304 struct render_row
305   {
306     /* Width without considering rows (or columns) that span more than one (or
307        column). */
308     int unspanned;
309
310     /* Width taking spanned rows (or columns) into consideration. */
311     int width;
312   };
313
314 /* Modifies the 'width' members of the N elements of ROWS so that their sum,
315    when added to rule widths RULES[1] through RULES[N - 1] inclusive, is at
316    least WIDTH. */
317 static void
318 distribute_spanned_width (int width,
319                           struct render_row *rows, const int *rules, int n)
320 {
321   int total_unspanned;
322   double w, d0, d1, d;
323   int x;
324
325   /* Sum up the unspanned widths of the N rows for use as weights. */
326   total_unspanned = 0;
327   for (x = 0; x < n; x++)
328     total_unspanned += rows[x].unspanned;
329   for (x = 0; x < n - 1; x++)
330     total_unspanned += rules[x + 1];
331   if (total_unspanned >= width)
332     return;
333
334   /* The algorithm used here is based on the following description from HTML 4:
335
336          For cells that span multiple columns, a simple approach consists of
337          apportioning the min/max widths evenly to each of the constituent
338          columns.  A slightly more complex approach is to use the min/max
339          widths of unspanned cells to weight how spanned widths are
340          apportioned.  Experiments suggest that a blend of the two approaches
341          gives good results for a wide range of tables.
342
343      We blend the two approaches half-and-half, except that we cannot use the
344      unspanned weights when 'total_unspanned' is 0 (because that would cause a
345      division by zero).
346
347      This implementation uses floating-point types and operators, but all the
348      values involved are integers.  For integers smaller than 53 bits, this
349      should not lose any precision, and it should degrade gracefully for larger
350      values.
351
352      The calculation we want to do is this:
353
354         w0 = width / n
355         w1 = width * (column's unspanned width) / (total unspanned width)
356         (column's width) = (w0 + w1) / 2
357
358      We implement it as a precise calculation in integers by multiplying w0 and
359      w1 by the common denominator of all three calculations (d), dividing that
360      out in the column width calculation, and then keeping the remainder for
361      the next iteration.
362   */
363   d0 = n;
364   d1 = total_unspanned * 2.0;
365   d = d0 * d1;
366   if (total_unspanned > 0)
367     d *= 2.0;
368   w = floor (d / 2.0);
369   for (x = 0; x < n; x++)
370     {
371       w += width * d1;
372       if (total_unspanned > 0)
373         {
374           double unspanned = rows[x].unspanned * 2.0;
375           if (x < n - 1)
376             unspanned += rules[x + 1];
377           if (x > 0)
378             unspanned += rules[x];
379           w += width * unspanned * d0;
380         }
381
382       rows[x].width = w / d;
383       w -= rows[x].width * d;
384     }
385 }
386
387 /* Initializes PAGE->cp[AXIS] from the row widths in ROWS and the rule widths
388    in RULES. */
389 static void
390 accumulate_row_widths (const struct render_page *page, enum table_axis axis,
391                        const struct render_row *rows, const int *rules)
392 {
393   int n = page->n[axis];
394   int *cp;
395   int z;
396
397   cp = page->cp[axis];
398   cp[0] = 0;
399   for (z = 0; z < n; z++)
400     {
401       cp[1] = cp[0] + rules[z];
402       cp[2] = cp[1] + rows[z].width;
403       cp += 2;
404     }
405   cp[1] = cp[0] + rules[n];
406 }
407
408 /* Returns the sum of widths of the N ROWS and N+1 RULES. */
409 static int
410 calculate_table_width (int n, const struct render_row *rows, int *rules)
411 {
412   int width;
413   int x;
414
415   width = 0;
416   for (x = 0; x < n; x++)
417     width += rows[x].width;
418   for (x = 0; x <= n; x++)
419     width += rules[x];
420
421   return width;
422 }
423 \f
424 /* Rendering utility functions. */
425
426 /* Returns the line style to use for drawing a rule of the given TYPE. */
427 static enum render_line_style
428 rule_to_render_type (unsigned char type)
429 {
430   switch (type)
431     {
432     case TAL_0:
433     case TAL_GAP:
434       return RENDER_LINE_NONE;
435     case TAL_1:
436       return RENDER_LINE_SINGLE;
437     case TAL_2:
438       return RENDER_LINE_DOUBLE;
439     default:
440       NOT_REACHED ();
441     }
442 }
443
444 /* Returns the width of the rule in TABLE that is at offset Z along axis A, if
445    rendered with PARAMS.  */
446 static int
447 measure_rule (const struct render_params *params, const struct table *table,
448               enum table_axis a, int z)
449 {
450   enum table_axis b = !a;
451   unsigned int rules;
452   int d[TABLE_N_AXES];
453   int width, i;
454
455   /* Determine all types of rules that are present, as a bitmap in 'rules'
456      where rule type 't' is present if bit 2**t is set. */
457   rules = 0;
458   d[a] = z;
459   for (d[b] = 0; d[b] < table->n[b]; d[b]++)
460     rules |= 1u << table_get_rule (table, a, d[H], d[V]);
461
462   /* Calculate maximum width of the rules that are present. */
463   width = 0;
464   for (i = 0; i < N_LINES; i++)
465     if (rules & (1u << i))
466       width = MAX (width, params->line_widths[a][rule_to_render_type (i)]);
467
468   return width;
469 }
470
471 /* Allocates and returns a new render_page using PARAMS and TABLE.  Allocates
472    space for all of the members of the new page, but the caller must initialize
473    the 'cp' member itself. */
474 static struct render_page *
475 render_page_allocate (const struct render_params *params,
476                       struct table *table)
477 {
478   struct render_page *page;
479   int i;
480
481   page = xmalloc (sizeof *page);
482   page->params = params;
483   page->table = table;
484   page->ref_cnt = 1;
485   page->n[H] = table->n[H];
486   page->n[V] = table->n[V];
487   page->h[H][0] = table->h[H][0];
488   page->h[H][1] = table->h[H][1];
489   page->h[V][0] = table->h[V][0];
490   page->h[V][1] = table->h[V][1];
491
492   for (i = 0; i < TABLE_N_AXES; i++)
493     {
494       page->cp[i] = xmalloc ((2 * page->n[i] + 2) * sizeof *page->cp[i]);
495       page->join_crossing[i] = xzalloc ((page->n[i] + 1) * sizeof *page->join_crossing[i]);
496     }
497
498   hmap_init (&page->overflows);
499   memset (page->is_edge_cutoff, 0, sizeof page->is_edge_cutoff);
500
501   return page;
502 }
503
504 /* Allocates and returns a new render_page for PARAMS and TABLE, initializing
505    cp[H] in the new page from ROWS and RULES.  The caller must still initialize
506    cp[V]. */
507 static struct render_page *
508 create_page_with_exact_widths (const struct render_params *params,
509                                struct table *table,
510                                const struct render_row *rows, int *rules)
511 {
512   struct render_page *page = render_page_allocate (params, table);
513   accumulate_row_widths (page, H, rows, rules);
514   return page;
515 }
516
517 /* Allocates and returns a new render_page for PARAMS and TABLE.
518
519    Initializes cp[H] in the new page by setting the width of each row 'i' to
520    somewhere between the minimum cell width ROW_MIN[i].width and the maximum
521    ROW_MAX[i].width.  Sets the width of rules to those in RULES.
522
523    W_MIN is the sum of ROWS_MIN[].width.
524
525    W_MAX is the sum of ROWS_MAX[].width.
526
527    The caller must still initialize cp[V]. */
528 static struct render_page *
529 create_page_with_interpolated_widths (const struct render_params *params,
530                                       struct table *table,
531                                       const struct render_row *rows_min,
532                                       const struct render_row *rows_max,
533                                       int w_min, int w_max, const int *rules)
534 {
535   /* This implementation uses floating-point types and operators, but all the
536      values involved are integers.  For integers smaller than 53 bits, this
537      should not lose any precision, and it should degrade gracefully for larger
538      values. */
539   const int n = table->n[H];
540   const double avail = params->size[H] - w_min;
541   const double wanted = w_max - w_min;
542   struct render_page *page;
543   double w;
544   int *cph;
545   int x;
546
547   assert (wanted > 0);
548
549   page = render_page_allocate (params, table);
550
551   cph = page->cp[H];
552   *cph = 0;
553   w = (int) wanted / 2;
554   for (x = 0; x < n; x++)
555     {
556       int extra;
557
558       w += avail * (rows_max[x].width - rows_min[x].width);
559       extra = w / wanted;
560       w -= extra * wanted;
561
562       cph[1] = cph[0] + rules[x];
563       cph[2] = cph[1] + rows_min[x].width + extra;
564       cph += 2;
565     }
566   cph[1] = cph[0] + rules[n];
567
568   assert (page->cp[H][n * 2 + 1] == params->size[H]);
569   return page;
570 }
571
572 \f
573 static void
574 set_join_crossings (struct render_page *page, enum table_axis axis,
575                     const struct table_cell *cell, int *rules)
576 {
577   int z;
578
579   for (z = cell->d[axis][0] + 1; z <= cell->d[axis][1] - 1; z++)
580     page->join_crossing[axis][z] = rules[z];
581 }
582
583 /* Creates and returns a new render_page for rendering TABLE on a device
584    described by PARAMS.
585
586    The new render_page will be suitable for rendering on a device whose page
587    size is PARAMS->size, but the caller is responsible for actually breaking it
588    up to fit on such a device, using the render_break abstraction.  */
589 struct render_page *
590 render_page_create (const struct render_params *params,
591                     const struct table *table_)
592 {
593   struct render_page *page;
594   struct table *table;
595   enum { MIN, MAX };
596   struct render_row *columns[2];
597   struct render_row *rows;
598   int table_widths[2];
599   int *rules[TABLE_N_AXES];
600   int nr, nc;
601   int x, y;
602   int i;
603   enum table_axis axis;
604
605   table = table_ref (table_);
606   nc = table_nc (table);
607   nr = table_nr (table);
608
609   /* Figure out rule widths. */
610   for (axis = 0; axis < TABLE_N_AXES; axis++)
611     {
612       int n = table->n[axis] + 1;
613       int z;
614
615       rules[axis] = xnmalloc (n, sizeof *rules);
616       for (z = 0; z < n; z++)
617         rules[axis][z] = measure_rule (params, table, axis, z);
618     }
619
620   /* Calculate minimum and maximum widths of cells that do not
621      span multiple columns. */
622   for (i = 0; i < 2; i++)
623     columns[i] = xzalloc (nc * sizeof *columns[i]);
624   for (y = 0; y < nr; y++)
625     for (x = 0; x < nc; )
626       {
627         struct table_cell cell;
628
629         table_get_cell (table, x, y, &cell);
630         if (y == cell.d[V][0] && table_cell_colspan (&cell) == 1)
631           {
632             int w[2];
633             int i;
634
635             params->measure_cell_width (params->aux, &cell, &w[MIN], &w[MAX]);
636             for (i = 0; i < 2; i++)
637               if (columns[i][x].unspanned < w[i])
638                 columns[i][x].unspanned = w[i];
639           }
640         x = cell.d[H][1];
641         table_cell_free (&cell);
642       }
643
644   /* Distribute widths of spanned columns. */
645   for (i = 0; i < 2; i++)
646     for (x = 0; x < nc; x++)
647       columns[i][x].width = columns[i][x].unspanned;
648   for (y = 0; y < nr; y++)
649     for (x = 0; x < nc; )
650       {
651         struct table_cell cell;
652
653         table_get_cell (table, x, y, &cell);
654         if (y == cell.d[V][0] && table_cell_colspan (&cell) > 1)
655           {
656             int w[2];
657
658             params->measure_cell_width (params->aux, &cell, &w[MIN], &w[MAX]);
659             for (i = 0; i < 2; i++)
660               distribute_spanned_width (w[i], &columns[i][cell.d[H][0]],
661                                         rules[H], table_cell_colspan (&cell));
662           }
663         x = cell.d[H][1];
664         table_cell_free (&cell);
665       }
666
667   /* Decide final column widths. */
668   for (i = 0; i < 2; i++)
669     table_widths[i] = calculate_table_width (table_nc (table),
670                                              columns[i], rules[H]);
671   if (table_widths[MAX] <= params->size[H])
672     {
673       /* Fits even with maximum widths.  Use them. */
674       page = create_page_with_exact_widths (params, table, columns[MAX],
675                                             rules[H]);
676     }
677   else if (table_widths[MIN] <= params->size[H])
678     {
679       /* Fits with minimum widths, so distribute the leftover space. */
680       page = create_page_with_interpolated_widths (
681         params, table, columns[MIN], columns[MAX],
682         table_widths[MIN], table_widths[MAX], rules[H]);
683     }
684   else
685     {
686       /* Doesn't fit even with minimum widths.  Assign minimums for now, and
687          later we can break it horizontally into multiple pages. */
688       page = create_page_with_exact_widths (params, table, columns[MIN],
689                                             rules[H]);
690     }
691
692   /* Calculate heights of cells that do not span multiple rows. */
693   rows = xzalloc (nr * sizeof *rows);
694   for (y = 0; y < nr; y++)
695     {
696       for (x = 0; x < nc; )
697         {
698           struct render_row *r = &rows[y];
699           struct table_cell cell;
700
701           table_get_cell (table, x, y, &cell);
702           if (y == cell.d[V][0])
703             {
704               if (table_cell_rowspan (&cell) == 1)
705                 {
706                   int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
707                   int h = params->measure_cell_height (params->aux, &cell, w);
708                   if (h > r->unspanned)
709                     r->unspanned = r->width = h;
710                 }
711               else
712                 set_join_crossings (page, V, &cell, rules[V]);
713
714               if (table_cell_colspan (&cell) > 1)
715                 set_join_crossings (page, H, &cell, rules[H]);
716             }
717           x = cell.d[H][1];
718           table_cell_free (&cell);
719         }
720     }
721   for (i = 0; i < 2; i++)
722     free (columns[i]);
723
724   /* Distribute heights of spanned rows. */
725   for (y = 0; y < nr; y++)
726     for (x = 0; x < nc; )
727       {
728         struct table_cell cell;
729
730         table_get_cell (table, x, y, &cell);
731         if (y == cell.d[V][0] && table_cell_rowspan (&cell) > 1)
732           {
733             int w = joined_width (page, H, cell.d[H][0], cell.d[H][1]);
734             int h = params->measure_cell_height (params->aux, &cell, w);
735             distribute_spanned_width (h, &rows[cell.d[V][0]], rules[V],
736                                       table_cell_rowspan (&cell));
737           }
738         x = cell.d[H][1];
739         table_cell_free (&cell);
740       }
741
742   /* Decide final row heights. */
743   accumulate_row_widths (page, V, rows, rules[V]);
744   free (rows);
745
746   /* Measure headers.  If they are "too big", get rid of them.  */
747   for (axis = 0; axis < TABLE_N_AXES; axis++)
748     {
749       int hw = headers_width (page, axis);
750       if (hw * 2 >= page->params->size[axis]
751           || hw + max_cell_width (page, axis) > page->params->size[axis])
752         {
753           page->table = table_unshare (page->table);
754           page->table->h[axis][0] = page->table->h[axis][1] = 0;
755           page->h[axis][0] = page->h[axis][1] = 0;
756         }
757     }
758
759   free (rules[H]);
760   free (rules[V]);
761
762   return page;
763 }
764
765 /* Increases PAGE's reference count. */
766 struct render_page *
767 render_page_ref (const struct render_page *page_)
768 {
769   struct render_page *page = CONST_CAST (struct render_page *, page_);
770   page->ref_cnt++;
771   return page;
772 }
773
774 /* Decreases PAGE's reference count and destroys PAGE if this causes the
775    reference count to fall to zero. */
776 void
777 render_page_unref (struct render_page *page)
778 {
779   if (page != NULL && --page->ref_cnt == 0)
780     {
781       struct render_overflow *overflow, *next;
782
783       HMAP_FOR_EACH_SAFE (overflow, next, struct render_overflow, node,
784                           &page->overflows)
785         free (overflow);
786       hmap_destroy (&page->overflows);
787
788       table_unref (page->table);
789       free (page->cp[H]);
790       free (page->cp[V]);
791       free (page);
792     }
793 }
794
795 /* Returns the size of PAGE along AXIS.  (This might be larger than the page
796    size specified in the parameters passed to render_page_create().  Use a
797    render_break to break up a render_page into page-sized chunks.) */
798 int
799 render_page_get_size (const struct render_page *page, enum table_axis axis)
800 {
801   return page->cp[axis][page->n[axis] * 2 + 1];
802 }
803 \f
804 /* Drawing render_pages. */
805
806 static enum render_line_style
807 get_rule (const struct render_page *page, enum table_axis axis,
808           const int d[TABLE_N_AXES])
809 {
810   return rule_to_render_type (table_get_rule (page->table,
811                                               axis, d[H] / 2, d[V] / 2));
812 }
813
814 static bool
815 is_rule (int z)
816 {
817   return !(z & 1);
818 }
819
820 static void
821 render_rule (const struct render_page *page, const int d[TABLE_N_AXES])
822 {
823   enum render_line_style styles[TABLE_N_AXES][2];
824   enum table_axis a;
825
826   for (a = 0; a < TABLE_N_AXES; a++)
827     {
828       enum table_axis b = !a;
829
830       styles[a][0] = styles[a][1] = RENDER_LINE_NONE;
831
832       if (!is_rule (d[a])
833           || (page->is_edge_cutoff[a][0] && d[a] == 0)
834           || (page->is_edge_cutoff[a][1] && d[a] == page->n[a] * 2))
835         continue;
836
837       if (is_rule (d[b]))
838         {
839           if (d[b] > 0)
840             {
841               int e[TABLE_N_AXES];
842               e[H] = d[H];
843               e[V] = d[V];
844               e[b]--;
845               styles[a][0] = get_rule (page, a, e);
846             }
847
848           if (d[b] / 2 < page->table->n[b])
849             styles[a][1] = get_rule (page, a, d);
850         }
851       else
852         styles[a][0] = styles[a][1] = get_rule (page, a, d);
853     }
854
855   if (styles[H][0] != RENDER_LINE_NONE || styles[H][1] != RENDER_LINE_NONE
856       || styles[V][0] != RENDER_LINE_NONE || styles[V][1] != RENDER_LINE_NONE)
857     {
858       int bb[TABLE_N_AXES][2];
859
860       bb[H][0] = page->cp[H][d[H]];
861       bb[H][1] = page->cp[H][d[H] + 1];
862       bb[V][0] = page->cp[V][d[V]];
863       bb[V][1] = page->cp[V][d[V] + 1];
864       page->params->draw_line (page->params->aux, bb, styles);
865     }
866 }
867
868 static void
869 render_cell (const struct render_page *page, const struct table_cell *cell)
870 {
871   const struct render_overflow *of;
872   int bb[TABLE_N_AXES][2];
873   int clip[TABLE_N_AXES][2];
874
875   bb[H][0] = clip[H][0] = page->cp[H][cell->d[H][0] * 2 + 1];
876   bb[H][1] = clip[H][1] = page->cp[H][cell->d[H][1] * 2];
877   bb[V][0] = clip[V][0] = page->cp[V][cell->d[V][0] * 2 + 1];
878   bb[V][1] = clip[V][1] = page->cp[V][cell->d[V][1] * 2];
879
880   of = find_overflow (page, cell->d[H][0], cell->d[V][0]);
881   if (of)
882     {
883       enum table_axis axis;
884
885       for (axis = 0; axis < TABLE_N_AXES; axis++)
886         {
887           if (of->overflow[axis][0])
888             {
889               bb[axis][0] -= of->overflow[axis][0];
890               if (cell->d[axis][0] == 0)
891                 clip[axis][0] = page->cp[axis][cell->d[axis][0] * 2];
892             }
893           if (of->overflow[axis][1])
894             {
895               bb[axis][1] += of->overflow[axis][1];
896               if (cell->d[axis][1] == page->n[axis])
897                 clip[axis][1] = page->cp[axis][cell->d[axis][1] * 2 + 1];
898             }
899         }
900     }
901
902   page->params->draw_cell (page->params->aux, cell, bb, clip);
903 }
904
905 /* Renders PAGE, by calling the 'draw_line' and 'draw_cell' functions from the
906    render_params provided to render_page_create(). */
907 void
908 render_page_draw (const struct render_page *page)
909 {
910   int x, y;
911
912   for (y = 0; y <= page->n[V] * 2; y++)
913     for (x = 0; x <= page->n[H] * 2; )
914       if (is_rule (x) || is_rule (y))
915         {
916           int d[TABLE_N_AXES];
917           d[H] = x;
918           d[V] = y;
919           render_rule (page, d);
920           x++;
921         }
922       else
923         {
924           struct table_cell cell;
925
926           table_get_cell (page->table, x / 2, y / 2, &cell);
927           if (y / 2 == cell.d[V][0])
928             render_cell (page, &cell);
929           x = rule_ofs (cell.d[H][1]);
930           table_cell_free (&cell);
931         }
932 }
933 \f
934 /* Breaking up tables to fit on a page. */
935
936 static int needed_size (const struct render_break *, int cell);
937 static bool cell_is_breakable (const struct render_break *, int cell);
938 static struct render_page *render_page_select (const struct render_page *,
939                                                enum table_axis,
940                                                int z0, int p0,
941                                                int z1, int p1);
942
943 /* Initializes render_break B for breaking PAGE along AXIS.
944
945    Ownership of PAGE is transferred to B.  The caller must use
946    render_page_ref() if it needs to keep a copy of PAGE. */
947 void
948 render_break_init (struct render_break *b, struct render_page *page,
949                    enum table_axis axis)
950 {
951   b->page = page;
952   b->axis = axis;
953   b->cell = page->h[axis][0];
954   b->pixel = 0;
955   b->hw = headers_width (page, axis);
956 }
957
958 /* Frees B and unrefs the render_page that it owns. */
959 void
960 render_break_destroy (struct render_break *b)
961 {
962   if (b != NULL)
963     render_page_unref (b->page);
964 }
965
966 /* Returns true if B still has cells that are yet to be returned,
967    false if all of B's page has been processed. */
968 bool
969 render_break_has_next (const struct render_break *b)
970 {
971   const struct render_page *page = b->page;
972   enum table_axis axis = b->axis;
973
974   return b->cell < page->n[axis] - page->h[axis][1];
975 }
976
977 /* Returns the minimum SIZE argument that, if passed to render_break_next(),
978    will avoid a null return value (if cells are still left). */
979 int
980 render_break_next_size (const struct render_break *b)
981 {
982   const struct render_page *page = b->page;
983   enum table_axis axis = b->axis;
984
985   return (!render_break_has_next (b) ? 0
986           : !cell_is_breakable (b, b->cell) ? needed_size (b, b->cell + 1)
987           : b->hw + page->params->font_size[axis]);
988 }
989
990 /* Returns a new render_page that is up to SIZE pixels wide along B's axis.
991    Returns a null pointer if B has already been completely broken up, or if
992    SIZE is too small to reasonably render any cells.  The latter will never
993    happen if SIZE is at least as large as the page size passed to
994    render_page_create() along B's axis. */
995 struct render_page *
996 render_break_next (struct render_break *b, int size)
997 {
998   const struct render_page *page = b->page;
999   enum table_axis axis = b->axis;
1000   struct render_page *subpage;
1001   int cell, pixel;
1002
1003   if (!render_break_has_next (b))
1004     return NULL;
1005
1006   pixel = 0;
1007   for (cell = b->cell; cell < page->n[axis] - page->h[axis][1]; cell++)
1008     if (needed_size (b, cell + 1) > size)
1009       {
1010         if (!cell_is_breakable (b, cell))
1011           {
1012             if (cell == b->cell)
1013               return NULL;
1014           }
1015         else
1016           pixel = (cell == b->cell
1017                    ? b->pixel + size - b->hw
1018                    : size - needed_size (b, cell));
1019         break;
1020       }
1021
1022   subpage = render_page_select (page, axis, b->cell, b->pixel,
1023                                 pixel ? cell + 1 : cell,
1024                                 pixel ? cell_width (page, axis, cell) - pixel
1025                                 : 0);
1026   b->cell = cell;
1027   b->pixel = pixel;
1028   return subpage;
1029 }
1030
1031 /* Returns the width that would be required along B's axis to render a page
1032    from B's current position up to but not including CELL. */
1033 static int
1034 needed_size (const struct render_break *b, int cell)
1035 {
1036   const struct render_page *page = b->page;
1037   enum table_axis axis = b->axis;
1038   int size;
1039
1040   size = joined_width (page, axis, b->cell, cell) + b->hw - b->pixel;
1041   if (page->h[axis][0] && page->h[axis][1])
1042     size += page->join_crossing[axis][b->cell];
1043
1044   return size;
1045 }
1046
1047 /* Returns true if CELL along B's axis may be broken across a page boundary.
1048
1049    This is just a heuristic.  Breaking cells across page boundaries can save
1050    space, but it looks ugly. */
1051 static bool
1052 cell_is_breakable (const struct render_break *b, int cell)
1053 {
1054   const struct render_page *page = b->page;
1055   enum table_axis axis = b->axis;
1056
1057   return cell_width (page, axis, cell) > page->params->size[axis] / 2;
1058 }
1059 \f
1060 /* render_page_select() and helpers. */
1061
1062 struct render_page_selection
1063   {
1064     const struct render_page *page; /* Page whose slice we are selecting. */
1065     struct render_page *subpage; /* New page under construction. */
1066     enum table_axis a;   /* Axis of 'page' along which 'subpage' is a slice. */
1067     enum table_axis b;   /* The opposite of 'a'. */
1068     int z0;              /* First cell along 'a' being selected. */
1069     int z1;              /* Last cell being selected, plus 1. */
1070     int p0;              /* Number of pixels to trim off left side of z0. */
1071     int p1;              /* Number of pixels to trim off right side of z1-1. */
1072   };
1073
1074 static void cell_to_subpage (struct render_page_selection *,
1075                              const struct table_cell *,
1076                              int subcell[TABLE_N_AXES]);
1077 static const struct render_overflow *find_overflow_for_cell (
1078   struct render_page_selection *, const struct table_cell *);
1079 static struct render_overflow *insert_overflow (struct render_page_selection *,
1080                                                 const struct table_cell *);
1081
1082 /* Creates and returns a new render_page whose contents are a subregion of
1083    PAGE's contents.  The new render_page includes cells Z0 through Z1 along
1084    AXIS, plus any headers on AXIS.
1085
1086    If P0 is nonzero, then it is a number of pixels to exclude from the left or
1087    top (according to AXIS) of cell Z0.  Similarly, P1 is a number of pixels to
1088    exclude from the right or bottom of cell Z1 - 1.  (P0 and P1 are used to
1089    render cells that are too large to fit on a single page.)
1090
1091    The whole of axis !AXIS is included.  (The caller may follow up with another
1092    call to render_page_select() to select on !AXIS to select on that axis as
1093    well.)
1094
1095    The caller retains ownership of PAGE, which is not modified. */
1096 static struct render_page *
1097 render_page_select (const struct render_page *page, enum table_axis axis,
1098                     int z0, int p0, int z1, int p1)
1099 {
1100   struct render_page_selection s;
1101   enum table_axis a = axis;
1102   enum table_axis b = !a;
1103   struct render_page *subpage;
1104   struct render_overflow *ro;
1105   int *dcp, *scp;
1106   int *jc;
1107   int z;
1108
1109
1110   /* Optimize case where all of PAGE is selected by just incrementing the
1111      reference count. */
1112   if (z0 == page->h[a][0] && p0 == 0
1113       && z1 == page->n[a] - page->h[a][1] && p1 == 0)
1114     {
1115       struct render_page *page_rw = (struct render_page *) page;
1116       page_rw->ref_cnt++;
1117       return page_rw;
1118     }
1119
1120   /* Allocate subpage. */
1121   subpage = render_page_allocate (page->params,
1122                                   table_select_slice (
1123                                     table_ref (page->table),
1124                                     a, z0, z1, true));
1125
1126   /* An edge is cut off if it was cut off in PAGE or if we're trimming pixels
1127      off that side of the page and there are no headers. */
1128   subpage->is_edge_cutoff[a][0] =
1129     subpage->h[a][0] == 0 && (p0 || (z0 == 0 && page->is_edge_cutoff[a][0]));
1130   subpage->is_edge_cutoff[a][1] =
1131     subpage->h[a][1] == 0 && (p1 || (z1 == page->n[a]
1132                                      && page->is_edge_cutoff[a][1]));
1133   subpage->is_edge_cutoff[b][0] = page->is_edge_cutoff[b][0];
1134   subpage->is_edge_cutoff[b][1] = page->is_edge_cutoff[b][1];
1135
1136   /* Select join crossings from PAGE into subpage. */
1137   jc = subpage->join_crossing[a];
1138   for (z = 0; z < page->h[a][0]; z++)
1139     *jc++ = page->join_crossing[a][z];
1140   for (z = z0; z <= z1; z++)
1141     *jc++ = page->join_crossing[a][z];
1142   for (z = page->n[a] - page->h[a][1]; z < page->n[a]; z++)
1143     *jc++ = page->join_crossing[a][z];
1144   assert (jc == &subpage->join_crossing[a][subpage->n[a] + 1]);
1145
1146   memcpy (subpage->join_crossing[b], page->join_crossing[b],
1147           (subpage->n[b] + 1) * sizeof **subpage->join_crossing);
1148
1149   /* Select widths from PAGE into subpage. */
1150   scp = page->cp[a];
1151   dcp = subpage->cp[a];
1152   *dcp = 0;
1153   for (z = 0; z <= rule_ofs (subpage->h[a][0]); z++, dcp++)
1154     dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1155   for (z = cell_ofs (z0); z <= cell_ofs (z1 - 1); z++, dcp++)
1156     {
1157       dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1158       if (z == cell_ofs (z0))
1159         {
1160           dcp[1] -= p0;
1161           if (page->h[a][0] && page->h[a][1])
1162             dcp[1] += page->join_crossing[a][z / 2];
1163         }
1164       if (z == cell_ofs (z1 - 1))
1165         dcp[1] -= p1;
1166     }
1167   for (z = rule_ofs_r (page, a, subpage->h[a][1]);
1168        z <= rule_ofs_r (page, a, 0); z++, dcp++)
1169     dcp[1] = dcp[0] + (scp[z + 1] - scp[z]);
1170   assert (dcp == &subpage->cp[a][2 * subpage->n[a] + 1]);
1171
1172   for (z = 0; z < page->n[b] * 2 + 2; z++)
1173     subpage->cp[b][z] = page->cp[b][z];
1174
1175   /* Add new overflows. */
1176   s.page = page;
1177   s.a = a;
1178   s.b = b;
1179   s.z0 = z0;
1180   s.z1 = z1;
1181   s.p0 = p0;
1182   s.p1 = p1;
1183   s.subpage = subpage;
1184
1185   for (z = 0; z < page->n[b]; z++)
1186     {
1187       struct table_cell cell;
1188       int d[TABLE_N_AXES];
1189
1190       d[a] = z0;
1191       d[b] = z;
1192       table_get_cell (page->table, d[H], d[V], &cell);
1193       if ((z == cell.d[b][0] && (p0 || cell.d[a][0] < z0))
1194           || (z == cell.d[b][1] - 1 && p1))
1195         {
1196           ro = insert_overflow (&s, &cell);
1197           ro->overflow[a][0] += p0 + axis_width (page, a,
1198                                                  cell_ofs (cell.d[a][0]),
1199                                                  cell_ofs (z0));
1200           if (z1 == z0 + 1)
1201             ro->overflow[a][1] += p1;
1202           if (page->h[a][0] && page->h[a][1])
1203             ro->overflow[a][0] -= page->join_crossing[a][cell.d[a][0] + 1];
1204           if (cell.d[a][1] > z1)
1205             ro->overflow[a][1] += axis_width (page, a, cell_ofs (z1),
1206                                               cell_ofs (cell.d[a][1]));
1207         }
1208       table_cell_free (&cell);
1209     }
1210
1211   for (z = 0; z < page->n[b]; z++)
1212     {
1213       struct table_cell cell;
1214       int d[TABLE_N_AXES];
1215
1216       /* XXX need to handle p1 below */
1217       d[a] = z1 - 1;
1218       d[b] = z;
1219       table_get_cell (page->table, d[H], d[V], &cell);
1220       if (z == cell.d[b][0] && cell.d[a][1] > z1
1221           && find_overflow_for_cell (&s, &cell) == NULL)
1222         {
1223           ro = insert_overflow (&s, &cell);
1224           ro->overflow[a][1] += axis_width (page, a, cell_ofs (z1),
1225                                             cell_ofs (cell.d[a][1]));
1226         }
1227       table_cell_free (&cell);
1228     }
1229
1230   /* Copy overflows from PAGE into subpage. */
1231   HMAP_FOR_EACH (ro, struct render_overflow, node, &page->overflows)
1232     {
1233       struct table_cell cell;
1234
1235       table_get_cell (page->table, ro->d[H], ro->d[V], &cell);
1236       if (cell.d[a][1] > z0 && cell.d[a][0] < z1
1237           && find_overflow_for_cell (&s, &cell) == NULL)
1238         insert_overflow (&s, &cell);
1239       table_cell_free (&cell);
1240     }
1241
1242   return subpage;
1243 }
1244
1245 /* Given CELL, a table_cell within S->page, stores in SUBCELL the (x,y)
1246    coordinates of the top-left cell as it will appear in S->subpage.
1247
1248    CELL must actually intersect the region of S->page that is being selected
1249    by render_page_select() or the results will not make any sense. */
1250 static void
1251 cell_to_subpage (struct render_page_selection *s,
1252                  const struct table_cell *cell, int subcell[TABLE_N_AXES])
1253 {
1254   enum table_axis a = s->a;
1255   enum table_axis b = s->b;
1256   int ha0 = s->subpage->h[a][0];
1257
1258   subcell[a] = MAX (cell->d[a][0] - s->z0 + ha0, ha0);
1259   subcell[b] = cell->d[b][0];
1260 }
1261
1262 /* Given CELL, a table_cell within S->page, returns the render_overflow for
1263    that cell in S->subpage, if there is one, and a null pointer otherwise.
1264
1265    CELL must actually intersect the region of S->page that is being selected
1266    by render_page_select() or the results will not make any sense. */
1267 static const struct render_overflow *
1268 find_overflow_for_cell (struct render_page_selection *s,
1269                         const struct table_cell *cell)
1270 {
1271   int subcell[2];
1272
1273   cell_to_subpage (s, cell, subcell);
1274   return find_overflow (s->subpage, subcell[H], subcell[V]);
1275 }
1276
1277 /* Given CELL, a table_cell within S->page, inserts a render_overflow for that
1278    cell in S->subpage (which must not already exist).  Initializes the new
1279    render_overflow's 'overflow' member from the overflow for CELL in S->page,
1280    if there is one.
1281
1282    CELL must actually intersect the region of S->page that is being selected
1283    by render_page_select() or the results will not make any sense. */
1284 static struct render_overflow *
1285 insert_overflow (struct render_page_selection *s,
1286                  const struct table_cell *cell)
1287 {
1288   const struct render_overflow *old;
1289   struct render_overflow *of;
1290
1291   of = xzalloc (sizeof *of);
1292   cell_to_subpage (s, cell, of->d);
1293   hmap_insert (&s->subpage->overflows, &of->node,
1294                hash_overflow (of->d[H], of->d[V]));
1295
1296   old = find_overflow (s->page, cell->d[H][0], cell->d[V][0]);
1297   if (old != NULL)
1298     memcpy (of->overflow, old->overflow, sizeof of->overflow);
1299
1300   return of;
1301 }
1302