2 * Paper printing pre-backend for Halibut.
4 * This module does all the processing common to both PostScript
5 * and PDF output: selecting fonts, line wrapping and page breaking
6 * in accordance with font metrics, laying out the contents and
7 * index pages, generally doing all the page layout. After this,
8 * bk_ps.c and bk_pdf.c should only need to do linear translations
9 * into their literal output format.
17 * - header/footer? Page numbers at least would be handy. Fully
18 * configurable footer can wait, though.
20 * That should bring us to the same level of functionality that
21 * original-Halibut had, and the same in PDF plus the obvious
22 * interactive navigation features. After that, in future work:
24 * - linearised PDF, perhaps?
26 * - I'm uncertain of whether I need to include a ToUnicode CMap
27 * in each of my font definitions in PDF. Currently things (by
28 * which I mean cut and paste out of acroread) seem to be
29 * working fairly happily without it, but I don't know.
42 typedef struct paper_conf_Tag paper_conf
;
44 struct paper_conf_Tag
{
51 int indent_list_bullet
;
55 int base_para_spacing
;
56 int chapter_top_space
;
57 int sect_num_left_space
;
58 int chapter_underline_depth
;
59 int chapter_underline_thickness
;
62 int contents_indent_step
;
64 int leader_separation
;
65 /* These are derived from the above */
68 /* Fonts used in the configuration */
69 font_data
*tr
, *ti
, *hr
, *hi
, *cr
, *co
, *cb
;
72 static font_data
*make_std_font(font_list
*fontlist
, char const *name
);
73 static void wrap_paragraph(para_data
*pdata
, word
*words
,
74 int w
, int i1
, int i2
);
75 static page_data
*page_breaks(line_data
*first
, line_data
*last
,
77 static int render_string(page_data
*page
, font_data
*font
, int fontsize
,
78 int x
, int y
, wchar_t *str
);
79 static int render_line(line_data
*ldata
, int left_x
, int top_y
,
80 xref_dest
*dest
, keywordlist
*keywords
);
81 static int paper_width_simple(para_data
*pdata
, word
*text
);
82 static para_data
*code_paragraph(int indent
, word
*words
, paper_conf
*conf
);
83 static para_data
*rule_paragraph(int indent
, paper_conf
*conf
);
84 static void add_rect_to_page(page_data
*page
, int x
, int y
, int w
, int h
);
85 static para_data
*make_para_data(int ptype
, int paux
, int indent
, int rmargin
,
86 word
*pkwtext
, word
*pkwtext2
, word
*pwords
,
88 static void standard_line_spacing(para_data
*pdata
, paper_conf
*conf
);
89 static wchar_t *prepare_outline_title(word
*first
, wchar_t *separator
,
91 static word
*fake_word(wchar_t *text
);
92 static word
*prepare_contents_title(word
*first
, wchar_t *separator
,
95 void *paper_pre_backend(paragraph
*sourceform
, keywordlist
*keywords
,
99 int indent
, used_contents
;
100 para_data
*pdata
, *firstpara
= NULL
, *lastpara
= NULL
;
101 para_data
*firstcont
, *lastcont
;
102 line_data
*ldata
, *firstline
, *lastline
, *firstcontline
, *lastcontline
;
108 * FIXME: All these things ought to become configurable.
110 conf
= mknew(paper_conf
);
111 conf
->paper_width
= 595 * 4096;
112 conf
->paper_height
= 841 * 4096;
113 conf
->left_margin
= 72 * 4096;
114 conf
->top_margin
= 72 * 4096;
115 conf
->right_margin
= 72 * 4096;
116 conf
->bottom_margin
= 108 * 4096;
117 conf
->indent_list_bullet
= 6 * 4096;
118 conf
->indent_list
= 24 * 4096;
119 conf
->indent_quote
= 18 * 4096;
120 conf
->base_leading
= 4096;
121 conf
->base_para_spacing
= 10 * 4096;
122 conf
->chapter_top_space
= 72 * 4096;
123 conf
->sect_num_left_space
= 12 * 4096;
124 conf
->chapter_underline_depth
= 14 * 4096;
125 conf
->chapter_underline_thickness
= 3 * 4096;
126 conf
->rule_thickness
= 1 * 4096;
127 conf
->base_font_size
= 12;
128 conf
->contents_indent_step
= 24 * 4096;
129 conf
->contents_margin
= 84 * 4096;
130 conf
->leader_separation
= 12 * 4096;
133 conf
->paper_width
- conf
->left_margin
- conf
->right_margin
;
135 conf
->paper_height
- conf
->top_margin
- conf
->bottom_margin
;
137 IGNORE(idx
); /* FIXME */
140 * First, set up some font structures.
142 fontlist
= mknew(font_list
);
143 fontlist
->head
= fontlist
->tail
= NULL
;
144 conf
->tr
= make_std_font(fontlist
, "Times-Roman");
145 conf
->ti
= make_std_font(fontlist
, "Times-Italic");
146 conf
->hr
= make_std_font(fontlist
, "Helvetica-Bold");
147 conf
->hi
= make_std_font(fontlist
, "Helvetica-BoldOblique");
148 conf
->cr
= make_std_font(fontlist
, "Courier");
149 conf
->co
= make_std_font(fontlist
, "Courier-Oblique");
150 conf
->cb
= make_std_font(fontlist
, "Courier-Bold");
153 * Format the contents entry for each heading.
156 word
*contents_title
;
157 contents_title
= fake_word(L
"Contents");
159 firstcont
= make_para_data(para_UnnumberedChapter
, 0, 0, 0,
160 NULL
, NULL
, contents_title
, conf
);
161 lastcont
= firstcont
;
162 lastcont
->next
= NULL
;
163 firstcontline
= firstcont
->first
;
164 lastcontline
= lastcont
->last
;
165 for (p
= sourceform
; p
; p
= p
->next
) {
172 case para_UnnumberedChapter
:
178 words
= prepare_contents_title(p
->kwtext
, L
": ", p
->words
);
181 case para_UnnumberedChapter
:
182 words
= prepare_contents_title(NULL
, NULL
, p
->words
);
187 words
= prepare_contents_title(p
->kwtext2
, L
" ", p
->words
);
188 indent
= (p
->aux
+ 1) * conf
->contents_indent_step
;
191 pdata
= make_para_data(para_Normal
, p
->aux
, indent
,
192 conf
->contents_margin
,
193 NULL
, NULL
, words
, conf
);
195 pdata
->contents_entry
= p
;
196 lastcont
->next
= pdata
;
200 * Link all contents line structures together into
205 lastcontline
->next
= pdata
->first
;
206 pdata
->first
->prev
= lastcontline
;
208 firstcontline
= pdata
->first
;
209 pdata
->first
->prev
= NULL
;
211 lastcontline
= pdata
->last
;
212 lastcontline
->next
= NULL
;
221 * Do the main paragraph formatting.
224 used_contents
= FALSE
;
225 firstline
= lastline
= NULL
;
226 for (p
= sourceform
; p
; p
= p
->next
) {
227 p
->private_data
= NULL
;
231 * These paragraph types are either invisible or don't
232 * define text in the normal sense. Either way, they
233 * don't require wrapping.
238 case para_NotParaType
:
245 * These paragraph types don't require wrapping, but
246 * they do affect the line width to which we wrap the
247 * rest of the paragraphs, so we need to pay attention.
250 indent
+= conf
->indent_list
; break;
252 indent
-= conf
->indent_list
; assert(indent
>= 0); break;
254 indent
+= conf
->indent_quote
; break;
256 indent
-= conf
->indent_quote
; assert(indent
>= 0); break;
259 * This paragraph type is special. Process it
263 pdata
= code_paragraph(indent
, p
->words
, conf
);
264 p
->private_data
= pdata
;
265 if (pdata
->first
!= pdata
->last
) {
266 pdata
->first
->penalty_after
+= 100000;
267 pdata
->last
->penalty_before
+= 100000;
272 * This paragraph is also special.
275 pdata
= rule_paragraph(indent
, conf
);
276 p
->private_data
= pdata
;
280 * All of these paragraph types require wrapping in the
281 * ordinary way. So we must supply a set of fonts, a
282 * line width and auxiliary information (e.g. bullet
283 * text) for each one.
287 case para_UnnumberedChapter
:
291 case para_BiblioCited
:
293 case para_NumberedList
:
294 case para_DescribedThing
:
295 case para_Description
:
298 pdata
= make_para_data(p
->type
, p
->aux
, indent
, 0,
299 p
->kwtext
, p
->kwtext2
, p
->words
, conf
);
301 p
->private_data
= pdata
;
306 if (p
->private_data
) {
307 pdata
= (para_data
*)p
->private_data
;
310 * If this is the first non-title heading, we link the
311 * contents section in before it.
313 if (!used_contents
&& pdata
->outline_level
> 0) {
314 used_contents
= TRUE
;
316 lastpara
->next
= firstcont
;
318 firstpara
= firstcont
;
320 assert(lastpara
->next
== NULL
);
323 lastline
->next
= firstcontline
;
324 firstcontline
->prev
= lastline
;
326 firstline
= firstcontline
;
327 firstcontline
->prev
= NULL
;
329 assert(lastcontline
!= NULL
);
330 lastline
= lastcontline
;
331 lastline
->next
= NULL
;
335 * Link all line structures together into a big list.
339 lastline
->next
= pdata
->first
;
340 pdata
->first
->prev
= lastline
;
342 firstline
= pdata
->first
;
343 pdata
->first
->prev
= NULL
;
345 lastline
= pdata
->last
;
346 lastline
->next
= NULL
;
350 * Link all paragraph structures together similarly.
354 lastpara
->next
= pdata
;
362 * Now we have an enormous linked list of every line of text in
363 * the document. Break it up into pages.
365 pages
= page_breaks(firstline
, lastline
, conf
->page_height
);
373 for (page
= pages
; page
; page
= page
->next
) {
375 sprintf(buf
, "%d", ++num
);
376 page
->number
= ufroma_dup(buf
);
381 * Now we're ready to actually lay out the pages. We do this by
382 * looping over _paragraphs_, since we may need to track cross-
383 * references between lines and even across pages.
385 for (pdata
= firstpara
; pdata
; pdata
= pdata
->next
) {
388 page_data
*cxref_page
;
396 for (ldata
= pdata
->first
; ldata
; ldata
= ldata
->next
) {
398 * If this is a contents entry, we expect to have a single
399 * enormous cross-reference rectangle covering the whole
400 * thing. (Unless, of course, it spans multiple pages.)
402 if (pdata
->contents_entry
&& ldata
->page
!= cxref_page
) {
403 cxref_page
= ldata
->page
;
406 cxref
->dest
.type
= PAGE
;
407 assert(pdata
->contents_entry
->private_data
);
408 target
= (para_data
*)pdata
->contents_entry
->private_data
;
409 cxref
->dest
.page
= target
->first
->page
;
410 cxref
->dest
.url
= NULL
;
411 if (ldata
->page
->last_xref
)
412 ldata
->page
->last_xref
->next
= cxref
;
414 ldata
->page
->first_xref
= cxref
;
415 ldata
->page
->last_xref
= cxref
;
416 cxref
->lx
= conf
->left_margin
;
417 cxref
->rx
= conf
->paper_width
- conf
->right_margin
;
418 cxref
->ty
= conf
->paper_height
- conf
->top_margin
419 - ldata
->ypos
+ ldata
->line_height
;
421 if (pdata
->contents_entry
) {
422 assert(cxref
!= NULL
);
423 cxref
->by
= conf
->paper_height
- conf
->top_margin
427 last_x
= render_line(ldata
, conf
->left_margin
,
428 conf
->paper_height
- conf
->top_margin
,
430 if (ldata
== pdata
->last
)
435 * If this is a contents entry, add leaders and a page
438 if (pdata
->contents_entry
) {
444 assert(pdata
->contents_entry
->private_data
);
445 target
= (para_data
*)pdata
->contents_entry
->private_data
;
446 num
= target
->first
->page
->number
;
449 wid
= paper_width_simple(pdata
, w
);
452 render_string(pdata
->last
->page
,
453 pdata
->fonts
[FONT_NORMAL
],
454 pdata
->sizes
[FONT_NORMAL
],
455 conf
->paper_width
- conf
->right_margin
- wid
,
456 (conf
->paper_height
- conf
->top_margin
-
457 pdata
->last
->ypos
), num
);
459 for (x
= 0; x
< conf
->base_width
; x
+= conf
->leader_separation
)
460 if (x
- conf
->leader_separation
> last_x
- conf
->left_margin
&&
461 x
+ conf
->leader_separation
< conf
->base_width
- wid
)
462 render_string(pdata
->last
->page
,
463 pdata
->fonts
[FONT_NORMAL
],
464 pdata
->sizes
[FONT_NORMAL
],
465 conf
->left_margin
+ x
,
466 (conf
->paper_height
- conf
->top_margin
-
467 pdata
->last
->ypos
), L
".");
471 * Render any rectangle (chapter title underline or rule)
472 * that goes with this paragraph.
474 switch (pdata
->rect_type
) {
475 case RECT_CHAPTER_UNDERLINE
:
476 add_rect_to_page(pdata
->last
->page
,
478 (conf
->paper_height
- conf
->top_margin
-
480 conf
->chapter_underline_depth
),
482 conf
->chapter_underline_thickness
);
485 add_rect_to_page(pdata
->first
->page
,
486 conf
->left_margin
+ pdata
->first
->xpos
,
487 (conf
->paper_height
- conf
->top_margin
-
489 pdata
->last
->line_height
),
490 conf
->base_width
- pdata
->first
->xpos
,
491 pdata
->last
->line_height
);
493 default: /* placate gcc */
499 * Start putting together the overall document structure we're
502 doc
= mknew(document
);
503 doc
->fonts
= fontlist
;
505 doc
->paper_width
= conf
->paper_width
;
506 doc
->paper_height
= conf
->paper_height
;
509 * Collect the section heading paragraphs into a document
510 * outline. This is slightly fiddly because the Title paragraph
511 * isn't required to be at the start, although all the others
517 doc
->outline_elements
= mknewa(outline_element
, osize
);
518 doc
->n_outline_elements
= 0;
520 /* First find the title. */
521 for (pdata
= firstpara
; pdata
; pdata
= pdata
->next
) {
522 if (pdata
->outline_level
== 0) {
523 doc
->outline_elements
[0].level
= 0;
524 doc
->outline_elements
[0].pdata
= pdata
;
525 doc
->n_outline_elements
++;
530 /* Then collect the rest. */
531 for (pdata
= firstpara
; pdata
; pdata
= pdata
->next
) {
532 if (pdata
->outline_level
> 0) {
533 if (doc
->n_outline_elements
>= osize
) {
535 doc
->outline_elements
=
536 resize(doc
->outline_elements
, osize
);
539 doc
->outline_elements
[doc
->n_outline_elements
].level
=
540 pdata
->outline_level
;
541 doc
->outline_elements
[doc
->n_outline_elements
].pdata
= pdata
;
542 doc
->n_outline_elements
++;
552 static para_data
*make_para_data(int ptype
, int paux
, int indent
, int rmargin
,
553 word
*pkwtext
, word
*pkwtext2
, word
*pwords
,
558 int extra_indent
, firstline_indent
, aux_indent
;
561 pdata
= mknew(para_data
);
562 pdata
->outline_level
= -1;
563 pdata
->outline_title
= NULL
;
564 pdata
->rect_type
= RECT_NONE
;
565 pdata
->contents_entry
= NULL
;
568 * Choose fonts for this paragraph.
570 * FIXME: All of this ought to be completely
575 pdata
->fonts
[FONT_NORMAL
] = conf
->hr
;
576 pdata
->sizes
[FONT_NORMAL
] = 24;
577 pdata
->fonts
[FONT_EMPH
] = conf
->hi
;
578 pdata
->sizes
[FONT_EMPH
] = 24;
579 pdata
->fonts
[FONT_CODE
] = conf
->cb
;
580 pdata
->sizes
[FONT_CODE
] = 24;
581 pdata
->outline_level
= 0;
586 case para_UnnumberedChapter
:
587 pdata
->fonts
[FONT_NORMAL
] = conf
->hr
;
588 pdata
->sizes
[FONT_NORMAL
] = 20;
589 pdata
->fonts
[FONT_EMPH
] = conf
->hi
;
590 pdata
->sizes
[FONT_EMPH
] = 20;
591 pdata
->fonts
[FONT_CODE
] = conf
->cb
;
592 pdata
->sizes
[FONT_CODE
] = 20;
593 pdata
->outline_level
= 1;
598 pdata
->fonts
[FONT_NORMAL
] = conf
->hr
;
599 pdata
->fonts
[FONT_EMPH
] = conf
->hi
;
600 pdata
->fonts
[FONT_CODE
] = conf
->cb
;
601 pdata
->sizes
[FONT_NORMAL
] =
602 pdata
->sizes
[FONT_EMPH
] =
603 pdata
->sizes
[FONT_CODE
] =
604 (paux
== 0 ?
16 : paux
== 1 ?
14 : 13);
605 pdata
->outline_level
= 2 + paux
;
609 case para_BiblioCited
:
611 case para_NumberedList
:
612 case para_DescribedThing
:
613 case para_Description
:
615 pdata
->fonts
[FONT_NORMAL
] = conf
->tr
;
616 pdata
->sizes
[FONT_NORMAL
] = 12;
617 pdata
->fonts
[FONT_EMPH
] = conf
->ti
;
618 pdata
->sizes
[FONT_EMPH
] = 12;
619 pdata
->fonts
[FONT_CODE
] = conf
->cr
;
620 pdata
->sizes
[FONT_CODE
] = 12;
625 * Also select an indentation level depending on the
626 * paragraph type (list paragraphs other than
627 * para_DescribedThing need extra indent).
629 * (FIXME: Perhaps at some point we might even arrange
630 * for the user to be able to request indented first
631 * lines in paragraphs.)
633 if (ptype
== para_Bullet
||
634 ptype
== para_NumberedList
||
635 ptype
== para_Description
) {
636 extra_indent
= firstline_indent
= conf
->indent_list
;
638 extra_indent
= firstline_indent
= 0;
642 * Find the auxiliary text for this paragraph.
653 * For some heading styles (FIXME: be able to
654 * configure which), the auxiliary text contains
655 * the chapter number and is arranged to be
656 * right-aligned a few points left of the primary
657 * margin. For other styles, the auxiliary text is
658 * the full chapter _name_ and takes up space
659 * within the (wrapped) chapter title, meaning that
660 * we must move the first line indent over to make
663 if (ptype
== para_Heading
|| ptype
== para_Subsect
) {
667 len
= paper_width_simple(pdata
, pkwtext2
);
668 aux_indent
= -len
- conf
->sect_num_left_space
;
670 pdata
->outline_title
=
671 prepare_outline_title(pkwtext2
, L
" ", pwords
);
674 aux2
= fake_word(L
": ");
677 firstline_indent
+= paper_width_simple(pdata
, aux
);
678 firstline_indent
+= paper_width_simple(pdata
, aux2
);
680 pdata
->outline_title
=
681 prepare_outline_title(pkwtext
, L
": ", pwords
);
687 * Auxiliary text consisting of a bullet. (FIXME:
688 * configurable bullet.)
690 aux
= fake_word(L
"\x2022");
691 aux_indent
= indent
+ conf
->indent_list_bullet
;
694 case para_NumberedList
:
696 * Auxiliary text consisting of the number followed
697 * by a (FIXME: configurable) full stop.
700 aux2
= fake_word(L
".");
701 aux_indent
= indent
+ conf
->indent_list_bullet
;
704 case para_BiblioCited
:
706 * Auxiliary text consisting of the bibliography
707 * reference text, and a trailing space.
710 aux2
= fake_word(L
" ");
712 firstline_indent
+= paper_width_simple(pdata
, aux
);
713 firstline_indent
+= paper_width_simple(pdata
, aux2
);
717 if (pdata
->outline_level
>= 0 && !pdata
->outline_title
) {
718 pdata
->outline_title
=
719 prepare_outline_title(NULL
, NULL
, pwords
);
722 wrap_paragraph(pdata
, pwords
, conf
->base_width
- rmargin
,
723 indent
+ firstline_indent
,
724 indent
+ extra_indent
);
726 pdata
->first
->aux_text
= aux
;
727 pdata
->first
->aux_text_2
= aux2
;
728 pdata
->first
->aux_left_indent
= aux_indent
;
731 * Line breaking penalties.
738 case para_UnnumberedChapter
:
740 * Fixed and large penalty for breaking straight
741 * after a heading; corresponding bonus for
742 * breaking straight before.
744 pdata
->first
->penalty_before
= -500000;
745 pdata
->last
->penalty_after
= 500000;
746 for (ldata
= pdata
->first
; ldata
; ldata
= ldata
->next
)
747 ldata
->penalty_after
= 500000;
750 case para_DescribedThing
:
752 * This is treated a bit like a small heading:
753 * there's a penalty for breaking after it (i.e.
754 * between it and its description), and a bonus for
755 * breaking before it (actually _between_ list
758 pdata
->first
->penalty_before
= -200000;
759 pdata
->last
->penalty_after
= 200000;
764 * Most paragraph types: widow/orphan control by
765 * discouraging breaking one line from the end of
768 if (pdata
->first
!= pdata
->last
) {
769 pdata
->first
->penalty_after
= 100000;
770 pdata
->last
->penalty_before
= 100000;
775 standard_line_spacing(pdata
, conf
);
778 * Some kinds of section heading require a page break before
779 * them and an underline after.
781 if (ptype
== para_Title
||
782 ptype
== para_Chapter
||
783 ptype
== para_Appendix
||
784 ptype
== para_UnnumberedChapter
) {
785 pdata
->first
->page_break
= TRUE
;
786 pdata
->first
->space_before
= conf
->chapter_top_space
;
787 pdata
->last
->space_after
+=
788 (conf
->chapter_underline_depth
+
789 conf
->chapter_underline_thickness
);
790 pdata
->rect_type
= RECT_CHAPTER_UNDERLINE
;
796 static void standard_line_spacing(para_data
*pdata
, paper_conf
*conf
)
801 * Set the line spacing for each line in this paragraph.
803 for (ldata
= pdata
->first
; ldata
; ldata
= ldata
->next
) {
804 if (ldata
== pdata
->first
)
805 ldata
->space_before
= conf
->base_para_spacing
/ 2;
807 ldata
->space_before
= conf
->base_leading
/ 2;
808 if (ldata
== pdata
->last
)
809 ldata
->space_after
= conf
->base_para_spacing
/ 2;
811 ldata
->space_after
= conf
->base_leading
/ 2;
812 ldata
->page_break
= FALSE
;
816 static font_encoding
*new_font_encoding(font_data
*font
)
821 fe
= mknew(font_encoding
);
824 if (font
->list
->tail
)
825 font
->list
->tail
->next
= fe
;
827 font
->list
->head
= fe
;
828 font
->list
->tail
= fe
;
833 for (i
= 0; i
< 256; i
++) {
834 fe
->vector
[i
] = NULL
;
836 fe
->to_unicode
[i
] = 0xFFFF;
842 static font_data
*make_std_font(font_list
*fontlist
, char const *name
)
850 widths
= ps_std_font_widths(name
);
854 for (nglyphs
= 0; ps_std_glyphs
[nglyphs
] != NULL
; nglyphs
++);
856 f
= mknew(font_data
);
860 f
->nglyphs
= nglyphs
;
861 f
->glyphs
= ps_std_glyphs
;
863 f
->subfont_map
= mknewa(subfont_map_entry
, nglyphs
);
866 * Our first subfont will contain all of US-ASCII. This isn't
867 * really necessary - we could just create custom subfonts
868 * precisely as the whim of render_string dictated - but
869 * instinct suggests that it might be nice to have the text in
870 * the output files look _marginally_ recognisable.
872 fe
= new_font_encoding(f
);
873 fe
->free_pos
= 0xA1; /* only the top half is free */
874 f
->latest_subfont
= fe
;
876 for (i
= 0; i
< (int)lenof(f
->bmp
); i
++)
879 for (i
= 0; i
< nglyphs
; i
++) {
881 ucs
= ps_glyph_to_unicode(f
->glyphs
[i
]);
882 assert(ucs
!= 0xFFFF);
884 if (ucs
>= 0x20 && ucs
<= 0x7E) {
885 fe
->vector
[ucs
] = f
->glyphs
[i
];
886 fe
->indices
[ucs
] = i
;
887 fe
->to_unicode
[ucs
] = ucs
;
888 f
->subfont_map
[i
].subfont
= fe
;
889 f
->subfont_map
[i
].position
= ucs
;
892 * This character is not yet assigned to a subfont.
894 f
->subfont_map
[i
].subfont
= NULL
;
895 f
->subfont_map
[i
].position
= 0;
902 static int string_width(font_data
*font
, wchar_t const *string
, int *errs
)
909 for (; *string
; string
++) {
912 index
= font
->bmp
[(unsigned short)*string
];
913 if (index
== 0xFFFF) {
917 width
+= font
->widths
[index
];
924 static int paper_width_internal(void *vctx
, word
*word
, int *nspaces
);
926 struct paper_width_ctx
{
931 static int paper_width_list(void *vctx
, word
*text
, word
*end
, int *nspaces
) {
933 while (text
&& text
!= end
) {
934 w
+= paper_width_internal(vctx
, text
, nspaces
);
940 static int paper_width_internal(void *vctx
, word
*word
, int *nspaces
)
942 struct paper_width_ctx
*ctx
= (struct paper_width_ctx
*)vctx
;
943 int style
, type
, findex
, width
, errs
;
946 switch (word
->type
) {
956 style
= towordstyle(word
->type
);
957 type
= removeattr(word
->type
);
959 findex
= (style
== word_Normal ? FONT_NORMAL
:
960 style
== word_Emph ? FONT_EMPH
:
963 if (type
== word_Normal
) {
965 } else if (type
== word_WhiteSpace
) {
966 if (findex
!= FONT_CODE
) {
969 return ctx
->minspacewidth
;
972 } else /* if (type == word_Quote) */ {
973 if (word
->aux
== quote_Open
)
974 str
= L
"\x2018"; /* FIXME: configurability! */
976 str
= L
"\x2019"; /* FIXME: configurability! */
979 width
= string_width(ctx
->pdata
->fonts
[findex
], str
, &errs
);
981 if (errs
&& word
->alt
)
982 return paper_width_list(vctx
, word
->alt
, NULL
, nspaces
);
984 return ctx
->pdata
->sizes
[findex
] * width
;
987 static int paper_width(void *vctx
, word
*word
)
989 return paper_width_internal(vctx
, word
, NULL
);
992 static int paper_width_simple(para_data
*pdata
, word
*text
)
994 struct paper_width_ctx ctx
;
998 (pdata
->sizes
[FONT_NORMAL
] *
999 string_width(pdata
->fonts
[FONT_NORMAL
], L
" ", NULL
));
1001 return paper_width_list(&ctx
, text
, NULL
, NULL
);
1004 static void wrap_paragraph(para_data
*pdata
, word
*words
,
1005 int w
, int i1
, int i2
)
1007 wrappedline
*wrapping
, *p
;
1009 struct paper_width_ctx ctx
;
1013 * We're going to need to store the line height in every line
1014 * structure we generate.
1019 for (i
= 0; i
< NFONTS
; i
++)
1020 if (line_height
< pdata
->sizes
[i
])
1021 line_height
= pdata
->sizes
[i
];
1022 line_height
*= 4096;
1025 spacewidth
= (pdata
->sizes
[FONT_NORMAL
] *
1026 string_width(pdata
->fonts
[FONT_NORMAL
], L
" ", NULL
));
1027 if (spacewidth
== 0) {
1029 * A font without a space?! Disturbing. I hope this never
1030 * comes up, but I'll make a random guess anyway and set my
1031 * space width to half the point size.
1033 spacewidth
= pdata
->sizes
[FONT_NORMAL
] * 4096 / 2;
1037 * I'm going to set the _minimum_ space width to 3/5 of the
1038 * standard one, and use the standard one as the optimum.
1040 ctx
.minspacewidth
= spacewidth
* 3 / 5;
1043 wrapping
= wrap_para(words
, w
- i1
, w
- i2
, paper_width
, &ctx
, spacewidth
);
1046 * Having done the wrapping, we now concoct a set of line_data
1049 pdata
->first
= pdata
->last
= NULL
;
1051 for (p
= wrapping
; p
; p
= p
->next
) {
1054 int len
, wid
, spaces
;
1056 ldata
= mknew(line_data
);
1058 ldata
->pdata
= pdata
;
1059 ldata
->first
= p
->begin
;
1060 ldata
->end
= p
->end
;
1061 ldata
->line_height
= line_height
;
1063 ldata
->xpos
= (p
== wrapping ? i1
: i2
);
1066 pdata
->last
->next
= ldata
;
1067 ldata
->prev
= pdata
->last
;
1069 pdata
->first
= ldata
;
1073 pdata
->last
= ldata
;
1076 len
= paper_width_list(&ctx
, ldata
->first
, ldata
->end
, &spaces
);
1077 wid
= (p
== wrapping ? w
- i1
: w
- i2
);
1080 ldata
->hshortfall
= wid
- len
;
1081 ldata
->nspaces
= spaces
;
1083 * This tells us how much the space width needs to
1084 * change from _min_spacewidth. But we want to store
1085 * its difference from the _natural_ space width, to
1086 * make the text rendering easier.
1088 ldata
->hshortfall
+= ctx
.minspacewidth
* spaces
;
1089 ldata
->hshortfall
-= spacewidth
* spaces
;
1091 * Special case: on the last line of a paragraph, we
1092 * never stretch spaces.
1094 if (ldata
->hshortfall
> 0 && !p
->next
)
1095 ldata
->hshortfall
= 0;
1097 ldata
->aux_text
= NULL
;
1098 ldata
->aux_text_2
= NULL
;
1099 ldata
->aux_left_indent
= 0;
1100 ldata
->penalty_before
= ldata
->penalty_after
= 0;
1105 static page_data
*page_breaks(line_data
*first
, line_data
*last
,
1112 * Page breaking is done by a close analogue of the optimal
1113 * paragraph wrapping algorithm used by wrap_para(). We work
1114 * backwards from the end of the document line by line; for
1115 * each line, we contemplate every possible number of lines we
1116 * could put on a page starting with that line, determine a
1117 * cost function for each one, add it to the pre-computed cost
1118 * function for optimally page-breaking everything after that
1119 * page, and pick the best option.
1121 * Since my line_data structures are only used for this
1122 * purpose, I might as well just store the algorithm data
1126 for (l
= last
; l
; l
= l
->prev
) {
1127 int minheight
, text
= 0, space
= 0;
1131 for (m
= l
; m
; m
= m
->next
) {
1132 if (m
!= l
&& m
->page_break
)
1133 break; /* we've gone as far as we can */
1136 space
+= m
->prev
->space_after
;
1137 if (m
!= l
|| m
->page_break
)
1138 space
+= m
->space_before
;
1139 text
+= m
->line_height
;
1140 minheight
= text
+ space
;
1142 if (m
!= l
&& minheight
> page_height
)
1146 * Compute the cost of this arrangement, as the square
1147 * of the amount of wasted space on the page.
1148 * Exception: if this is the last page before a
1149 * mandatory break or the document end, we don't
1150 * penalise a large blank area.
1152 if (m
->next
&& !m
->next
->page_break
)
1154 int x
= page_height
- minheight
;
1161 cost
+= (x
* xf
) >> 8;
1165 if (m
->next
&& !m
->next
->page_break
) {
1166 cost
+= m
->penalty_after
;
1167 cost
+= m
->next
->penalty_before
;
1170 if (m
->next
&& !m
->next
->page_break
)
1171 cost
+= m
->next
->bestcost
;
1172 if (l
->bestcost
== -1 || l
->bestcost
> cost
) {
1174 * This is the best option yet for this starting
1178 if (m
->next
&& !m
->next
->page_break
)
1179 l
->vshortfall
= page_height
- minheight
;
1190 * Now go through the line list forwards and assemble the
1200 page
= mknew(page_data
);
1209 page
->first_line
= l
;
1210 page
->last_line
= l
->page_last
;
1212 page
->first_text
= page
->last_text
= NULL
;
1213 page
->first_xref
= page
->last_xref
= NULL
;
1214 page
->first_rect
= page
->last_rect
= NULL
;
1217 * Now assign a y-coordinate to each line on the page.
1220 for (l
= page
->first_line
; l
; l
= l
->next
) {
1221 if (l
!= page
->first_line
)
1222 space
+= l
->prev
->space_after
;
1223 if (l
!= page
->first_line
|| l
->page_break
)
1224 space
+= l
->space_before
;
1225 text
+= l
->line_height
;
1228 l
->ypos
= text
+ space
+
1229 space
* (float)page
->first_line
->vshortfall
/
1230 page
->first_line
->space
;
1232 if (l
== page
->last_line
)
1236 l
= page
->last_line
->next
;
1242 static void add_rect_to_page(page_data
*page
, int x
, int y
, int w
, int h
)
1244 rect
*r
= mknew(rect
);
1247 if (page
->last_rect
)
1248 page
->last_rect
->next
= r
;
1250 page
->first_rect
= r
;
1251 page
->last_rect
= r
;
1259 static void add_string_to_page(page_data
*page
, int x
, int y
,
1260 font_encoding
*fe
, int size
, char *text
)
1262 text_fragment
*frag
;
1264 frag
= mknew(text_fragment
);
1267 if (page
->last_text
)
1268 page
->last_text
->next
= frag
;
1270 page
->first_text
= frag
;
1271 page
->last_text
= frag
;
1276 frag
->fontsize
= size
;
1277 frag
->text
= dupstr(text
);
1281 * Returns the updated x coordinate.
1283 static int render_string(page_data
*page
, font_data
*font
, int fontsize
,
1284 int x
, int y
, wchar_t *str
)
1287 int textpos
, textwid
, glyph
;
1288 font_encoding
*subfont
= NULL
, *sf
;
1290 text
= mknewa(char, 1 + ustrlen(str
));
1291 textpos
= textwid
= 0;
1294 glyph
= font
->bmp
[*str
];
1296 if (glyph
== 0xFFFF)
1297 continue; /* nothing more we can do here */
1300 * Find which subfont this character is going in.
1302 sf
= font
->subfont_map
[glyph
].subfont
;
1308 * This character is not yet in a subfont. Assign one.
1310 if (font
->latest_subfont
->free_pos
>= 0x100)
1311 font
->latest_subfont
= new_font_encoding(font
);
1313 c
= font
->latest_subfont
->free_pos
++;
1314 if (font
->latest_subfont
->free_pos
== 0x7F)
1315 font
->latest_subfont
->free_pos
= 0xA1;
1317 font
->subfont_map
[glyph
].subfont
= font
->latest_subfont
;
1318 font
->subfont_map
[glyph
].position
= c
;
1319 font
->latest_subfont
->vector
[c
] = font
->glyphs
[glyph
];
1320 font
->latest_subfont
->indices
[c
] = glyph
;
1321 font
->latest_subfont
->to_unicode
[c
] = *str
;
1323 sf
= font
->latest_subfont
;
1326 if (!subfont
|| sf
!= subfont
) {
1328 text
[textpos
] = '\0';
1329 add_string_to_page(page
, x
, y
, subfont
, fontsize
, text
);
1332 assert(textpos
== 0);
1338 text
[textpos
++] = font
->subfont_map
[glyph
].position
;
1339 textwid
+= font
->widths
[glyph
] * fontsize
;
1345 text
[textpos
] = '\0';
1346 add_string_to_page(page
, x
, y
, subfont
, fontsize
, text
);
1354 * Returns the updated x coordinate.
1356 static int render_text(page_data
*page
, para_data
*pdata
, line_data
*ldata
,
1357 int x
, int y
, word
*text
, word
*text_end
, xref
**xr
,
1358 int shortfall
, int nspaces
, int *nspace
,
1359 keywordlist
*keywords
)
1361 while (text
&& text
!= text_end
) {
1362 int style
, type
, findex
, errs
;
1366 switch (text
->type
) {
1368 * Start a cross-reference.
1370 case word_HyperLink
:
1371 case word_UpperXref
:
1372 case word_LowerXref
:
1374 if (text
->type
== word_HyperLink
) {
1376 dest
.url
= utoa_dup(text
->text
);
1379 keyword
*kwl
= kw_lookup(keywords
, text
->text
);
1383 assert(kwl
->para
->private_data
);
1384 pdata
= (para_data
*) kwl
->para
->private_data
;
1386 dest
.page
= pdata
->first
->page
;
1390 * Shouldn't happen, but *shrug*
1397 if (dest
.type
!= NONE
) {
1399 (*xr
)->dest
= dest
; /* structure copy */
1400 if (page
->last_xref
)
1401 page
->last_xref
->next
= *xr
;
1403 page
->first_xref
= *xr
;
1404 page
->last_xref
= *xr
;
1408 * FIXME: Ideally we should have, and use, some
1409 * vertical font metric information here so that
1410 * our cross-ref rectangle can take account of
1411 * descenders and the font's cap height. This will
1412 * do for the moment, but it isn't ideal.
1414 (*xr
)->lx
= (*xr
)->rx
= x
;
1416 (*xr
)->ty
= y
+ ldata
->line_height
;
1421 * Finish extending a cross-reference box.
1431 * FIXME: we should do something with this.
1435 style
= towordstyle(text
->type
);
1436 type
= removeattr(text
->type
);
1438 findex
= (style
== word_Normal ? FONT_NORMAL
:
1439 style
== word_Emph ? FONT_EMPH
:
1442 if (type
== word_Normal
) {
1444 } else if (type
== word_WhiteSpace
) {
1445 x
+= pdata
->sizes
[findex
] *
1446 string_width(pdata
->fonts
[findex
], L
" ", NULL
);
1447 if (nspaces
&& findex
!= FONT_CODE
) {
1448 x
+= (*nspace
+1) * shortfall
/ nspaces
;
1449 x
-= *nspace
* shortfall
/ nspaces
;
1453 } else /* if (type == word_Quote) */ {
1454 if (text
->aux
== quote_Open
)
1455 str
= L
"\x2018"; /* FIXME: configurability! */
1457 str
= L
"\x2019"; /* FIXME: configurability! */
1460 (void) string_width(pdata
->fonts
[findex
], str
, &errs
);
1462 if (errs
&& text
->alt
)
1463 x
= render_text(page
, pdata
, ldata
, x
, y
, text
->alt
, NULL
,
1464 xr
, shortfall
, nspaces
, nspace
, keywords
);
1466 x
= render_string(page
, pdata
->fonts
[findex
],
1467 pdata
->sizes
[findex
], x
, y
, str
);
1480 * Returns the last x position used on the line.
1482 static int render_line(line_data
*ldata
, int left_x
, int top_y
,
1483 xref_dest
*dest
, keywordlist
*keywords
)
1489 if (ldata
->aux_text
) {
1493 x
= render_text(ldata
->page
, ldata
->pdata
, ldata
,
1494 left_x
+ ldata
->aux_left_indent
,
1495 top_y
- ldata
->ypos
,
1496 ldata
->aux_text
, NULL
, &xr
, 0, 0, &nspace
, keywords
);
1497 if (ldata
->aux_text_2
)
1498 render_text(ldata
->page
, ldata
->pdata
, ldata
,
1499 x
, top_y
- ldata
->ypos
,
1500 ldata
->aux_text_2
, NULL
, &xr
, 0, 0, &nspace
, keywords
);
1506 * There might be a cross-reference carried over from a
1509 if (dest
->type
!= NONE
) {
1512 xr
->dest
= *dest
; /* structure copy */
1513 if (ldata
->page
->last_xref
)
1514 ldata
->page
->last_xref
->next
= xr
;
1516 ldata
->page
->first_xref
= xr
;
1517 ldata
->page
->last_xref
= xr
;
1518 xr
->lx
= xr
->rx
= left_x
+ ldata
->xpos
;
1519 xr
->by
= top_y
- ldata
->ypos
;
1520 xr
->ty
= top_y
- ldata
->ypos
+ ldata
->line_height
;
1524 ret
= render_text(ldata
->page
, ldata
->pdata
, ldata
,
1525 left_x
+ ldata
->xpos
,
1526 top_y
- ldata
->ypos
, ldata
->first
, ldata
->end
, &xr
,
1527 ldata
->hshortfall
, ldata
->nspaces
, &nspace
,
1532 * There's a cross-reference continued on to the next line.
1542 static para_data
*code_paragraph(int indent
, word
*words
, paper_conf
*conf
)
1544 para_data
*pdata
= mknew(para_data
);
1547 * For code paragraphs, I'm going to hack grievously and
1548 * pretend the three normal fonts are the three code paragraph
1551 pdata
->fonts
[FONT_NORMAL
] = conf
->cb
;
1552 pdata
->fonts
[FONT_EMPH
] = conf
->co
;
1553 pdata
->fonts
[FONT_CODE
] = conf
->cr
;
1554 pdata
->sizes
[FONT_NORMAL
] =
1555 pdata
->sizes
[FONT_EMPH
] =
1556 pdata
->sizes
[FONT_CODE
] = 12;
1558 pdata
->first
= pdata
->last
= NULL
;
1559 pdata
->outline_level
= -1;
1560 pdata
->rect_type
= RECT_NONE
;
1561 pdata
->contents_entry
= NULL
;
1563 for (; words
; words
= words
->next
) {
1564 wchar_t *t
, *e
, *start
;
1565 word
*lhead
= NULL
, *ltail
= NULL
, *w
;
1567 int prev
= -1, curr
;
1570 if (words
->next
&& words
->next
->type
== word_Emph
) {
1571 e
= words
->next
->text
;
1572 words
= words
->next
;
1582 else if (*e
== L
'i')
1584 else if (*e
== L
'b')
1601 * We've isolated a maximal subsequence of the line
1602 * which has the same emphasis. Form it into a word
1608 w
->type
= (prev
== 0 ? word_WeakCode
:
1609 prev
== 1 ? word_Emph
: word_Normal
);
1610 w
->text
= mknewa(wchar_t, t
-start
+1);
1611 memcpy(w
->text
, start
, (t
-start
) * sizeof(wchar_t));
1612 w
->text
[t
-start
] = '\0';
1625 ldata
= mknew(line_data
);
1627 ldata
->pdata
= pdata
;
1628 ldata
->first
= lhead
;
1630 ldata
->line_height
= conf
->base_font_size
* 4096;
1632 ldata
->xpos
= indent
;
1635 pdata
->last
->next
= ldata
;
1636 ldata
->prev
= pdata
->last
;
1638 pdata
->first
= ldata
;
1642 pdata
->last
= ldata
;
1644 ldata
->hshortfall
= 0;
1646 ldata
->aux_text
= NULL
;
1647 ldata
->aux_text_2
= NULL
;
1648 ldata
->aux_left_indent
= 0;
1649 /* General opprobrium for breaking in a code paragraph. */
1650 ldata
->penalty_before
= ldata
->penalty_after
= 50000;
1653 standard_line_spacing(pdata
, conf
);
1658 static para_data
*rule_paragraph(int indent
, paper_conf
*conf
)
1660 para_data
*pdata
= mknew(para_data
);
1663 ldata
= mknew(line_data
);
1665 ldata
->pdata
= pdata
;
1666 ldata
->first
= NULL
;
1668 ldata
->line_height
= conf
->rule_thickness
;
1670 ldata
->xpos
= indent
;
1675 ldata
->hshortfall
= 0;
1677 ldata
->aux_text
= NULL
;
1678 ldata
->aux_text_2
= NULL
;
1679 ldata
->aux_left_indent
= 0;
1682 * Better to break after a rule than before it
1684 ldata
->penalty_after
+= 100000;
1685 ldata
->penalty_before
+= -100000;
1687 pdata
->first
= pdata
->last
= ldata
;
1688 pdata
->outline_level
= -1;
1689 pdata
->rect_type
= RECT_RULE
;
1690 pdata
->contents_entry
= NULL
;
1692 standard_line_spacing(pdata
, conf
);
1698 * Plain-text-like formatting for outline titles.
1700 static void paper_rdaddw(rdstring
*rs
, word
*text
) {
1701 for (; text
; text
= text
->next
) switch (text
->type
) {
1702 case word_HyperLink
:
1704 case word_UpperXref
:
1705 case word_LowerXref
:
1714 case word_WhiteSpace
:
1715 case word_EmphSpace
:
1716 case word_CodeSpace
:
1717 case word_WkCodeSpace
:
1719 case word_EmphQuote
:
1720 case word_CodeQuote
:
1721 case word_WkCodeQuote
:
1722 assert(text
->type
!= word_CodeQuote
&&
1723 text
->type
!= word_WkCodeQuote
);
1724 if (towordstyle(text
->type
) == word_Emph
&&
1725 (attraux(text
->aux
) == attr_First
||
1726 attraux(text
->aux
) == attr_Only
))
1727 rdadd(rs
, L
'_'); /* FIXME: configurability */
1728 else if (towordstyle(text
->type
) == word_Code
&&
1729 (attraux(text
->aux
) == attr_First
||
1730 attraux(text
->aux
) == attr_Only
))
1731 rdadd(rs
, L
'\''); /* FIXME: configurability */
1732 if (removeattr(text
->type
) == word_Normal
) {
1733 rdadds(rs
, text
->text
);
1734 } else if (removeattr(text
->type
) == word_WhiteSpace
) {
1736 } else if (removeattr(text
->type
) == word_Quote
) {
1737 rdadd(rs
, L
'\''); /* fixme: configurability */
1739 if (towordstyle(text
->type
) == word_Emph
&&
1740 (attraux(text
->aux
) == attr_Last
||
1741 attraux(text
->aux
) == attr_Only
))
1742 rdadd(rs
, L
'_'); /* FIXME: configurability */
1743 else if (towordstyle(text
->type
) == word_Code
&&
1744 (attraux(text
->aux
) == attr_Last
||
1745 attraux(text
->aux
) == attr_Only
))
1746 rdadd(rs
, L
'\''); /* FIXME: configurability */
1751 static wchar_t *prepare_outline_title(word
*first
, wchar_t *separator
,
1754 rdstring rs
= {0, 0, NULL
};
1757 paper_rdaddw(&rs
, first
);
1759 rdadds(&rs
, separator
);
1761 paper_rdaddw(&rs
, second
);
1766 static word
*fake_word(wchar_t *text
)
1768 word
*ret
= mknew(word
);
1771 ret
->type
= word_Normal
;
1772 ret
->text
= ustrdup(text
);
1773 ret
->breaks
= FALSE
;
1778 static word
*prepare_contents_title(word
*first
, wchar_t *separator
,
1787 w
= dup_word_list(first
);
1795 w
= fake_word(separator
);
1801 *wptr
= dup_word_list(second
);