+ paragraph *p;
+ document *doc;
+ int indent, used_contents;
+ para_data *pdata, *firstpara = NULL, *lastpara = NULL;
+ para_data *firstcont, *lastcont;
+ line_data *firstline, *lastline, *firstcontline, *lastcontline;
+ page_data *pages;
+ font_list *fontlist;
+ paper_conf *conf, ourconf;
+ int has_index;
+ int pagenum;
+ paragraph index_placeholder_para;
+ page_data *first_index_page;
+
+ fontlist = snew(font_list);
+ fontlist->head = fontlist->tail = NULL;
+
+ ourconf = paper_configure(sourceform, fontlist);
+ conf = &ourconf;
+
+ /*
+ * Set up a data structure to collect page numbers for each
+ * index entry.
+ */
+ {
+ int i;
+ indexentry *entry;
+
+ has_index = FALSE;
+
+ for (i = 0; (entry = index234(idx->entries, i)) != NULL; i++) {
+ paper_idx *pi = snew(paper_idx);
+
+ has_index = TRUE;
+
+ pi->words = pi->lastword = NULL;
+ pi->lastpage = NULL;
+
+ entry->backend_data = pi;
+ }
+ }
+
+ /*
+ * Format the contents entry for each heading.
+ */
+ {
+ word *contents_title;
+ contents_title = fake_word(L"Contents");
+
+ firstcont = make_para_data(para_UnnumberedChapter, 0, 0, 0,
+ NULL, NULL, contents_title, conf);
+ lastcont = firstcont;
+ lastcont->next = NULL;
+ firstcontline = firstcont->first;
+ lastcontline = lastcont->last;
+ for (p = sourceform; p; p = p->next) {
+ word *words;
+ int indent;
+
+ switch (p->type) {
+ case para_Chapter:
+ case para_Appendix:
+ case para_UnnumberedChapter:
+ case para_Heading:
+ case para_Subsect:
+ switch (p->type) {
+ case para_Chapter:
+ case para_Appendix:
+ words = prepare_contents_title(p->kwtext, L": ", p->words);
+ indent = 0;
+ break;
+ case para_UnnumberedChapter:
+ words = prepare_contents_title(NULL, NULL, p->words);
+ indent = 0;
+ break;
+ case para_Heading:
+ case para_Subsect:
+ words = prepare_contents_title(p->kwtext2, L" ", p->words);
+ indent = (p->aux + 1) * conf->contents_indent_step;
+ break;
+ }
+ pdata = make_para_data(para_Normal, p->aux, indent,
+ conf->contents_margin,
+ NULL, NULL, words, conf);
+ pdata->next = NULL;
+ pdata->contents_entry = p;
+ lastcont->next = pdata;
+ lastcont = pdata;
+
+ /*
+ * Link all contents line structures together into
+ * a big list.
+ */
+ if (pdata->first) {
+ if (lastcontline) {
+ lastcontline->next = pdata->first;
+ pdata->first->prev = lastcontline;
+ } else {
+ firstcontline = pdata->first;
+ pdata->first->prev = NULL;
+ }
+ lastcontline = pdata->last;
+ lastcontline->next = NULL;
+ }
+
+ break;
+ }
+ }
+
+ /*
+ * And one extra one, for the index.
+ */
+ if (has_index) {
+ pdata = make_para_data(para_Normal, 0, 0,
+ conf->contents_margin,
+ NULL, NULL, fake_word(L"Index"), conf);
+ pdata->next = NULL;
+ pdata->contents_entry = &index_placeholder_para;
+ lastcont->next = pdata;
+ lastcont = pdata;
+
+ if (pdata->first) {
+ if (lastcontline) {
+ lastcontline->next = pdata->first;
+ pdata->first->prev = lastcontline;
+ } else {
+ firstcontline = pdata->first;
+ pdata->first->prev = NULL;
+ }
+ lastcontline = pdata->last;
+ lastcontline->next = NULL;
+ }
+ }
+ }
+
+ /*
+ * Do the main paragraph formatting.
+ */
+ indent = 0;
+ used_contents = FALSE;
+ firstline = lastline = NULL;
+ for (p = sourceform; p; p = p->next) {
+ p->private_data = NULL;
+
+ switch (p->type) {
+ /*
+ * These paragraph types are either invisible or don't
+ * define text in the normal sense. Either way, they
+ * don't require wrapping.
+ */
+ case para_IM:
+ case para_BR:
+ case para_Biblio:
+ case para_NotParaType:
+ case para_Config:
+ case para_VersionID:
+ case para_NoCite:
+ break;
+
+ /*
+ * These paragraph types don't require wrapping, but
+ * they do affect the line width to which we wrap the
+ * rest of the paragraphs, so we need to pay attention.
+ */
+ case para_LcontPush:
+ indent += conf->indent_list; break;
+ case para_LcontPop:
+ indent -= conf->indent_list; assert(indent >= 0); break;
+ case para_QuotePush:
+ indent += conf->indent_quote; break;
+ case para_QuotePop:
+ indent -= conf->indent_quote; assert(indent >= 0); break;
+
+ /*
+ * This paragraph type is special. Process it
+ * specially.
+ */
+ case para_Code:
+ pdata = code_paragraph(indent, p->words, conf);
+ p->private_data = pdata;
+ if (pdata->first != pdata->last) {
+ pdata->first->penalty_after += 100000;
+ pdata->last->penalty_before += 100000;
+ }
+ break;
+
+ /*
+ * This paragraph is also special.
+ */
+ case para_Rule:
+ pdata = rule_paragraph(indent, conf);
+ p->private_data = pdata;
+ break;
+
+ /*
+ * All of these paragraph types require wrapping in the
+ * ordinary way. So we must supply a set of fonts, a
+ * line width and auxiliary information (e.g. bullet
+ * text) for each one.
+ */
+ case para_Chapter:
+ case para_Appendix:
+ case para_UnnumberedChapter:
+ case para_Heading:
+ case para_Subsect:
+ case para_Normal:
+ case para_BiblioCited:
+ case para_Bullet:
+ case para_NumberedList:
+ case para_DescribedThing:
+ case para_Description:
+ case para_Copyright:
+ case para_Title:
+ pdata = make_para_data(p->type, p->aux, indent, 0,
+ p->kwtext, p->kwtext2, p->words, conf);
+
+ p->private_data = pdata;
+
+ break;
+ }
+
+ if (p->private_data) {
+ pdata = (para_data *)p->private_data;
+
+ /*
+ * If this is the first non-title heading, we link the
+ * contents section in before it.
+ */
+ if (!used_contents && pdata->outline_level > 0) {
+ used_contents = TRUE;
+ if (lastpara)
+ lastpara->next = firstcont;
+ else
+ firstpara = firstcont;
+ lastpara = lastcont;
+ assert(lastpara->next == NULL);
+
+ if (lastline) {
+ lastline->next = firstcontline;
+ firstcontline->prev = lastline;
+ } else {
+ firstline = firstcontline;
+ firstcontline->prev = NULL;
+ }
+ assert(lastcontline != NULL);
+ lastline = lastcontline;
+ lastline->next = NULL;
+ }
+
+ /*
+ * Link all line structures together into a big list.
+ */
+ if (pdata->first) {
+ if (lastline) {
+ lastline->next = pdata->first;
+ pdata->first->prev = lastline;
+ } else {
+ firstline = pdata->first;
+ pdata->first->prev = NULL;
+ }
+ lastline = pdata->last;
+ lastline->next = NULL;
+ }
+
+ /*
+ * Link all paragraph structures together similarly.
+ */
+ pdata->next = NULL;
+ if (lastpara)
+ lastpara->next = pdata;
+ else
+ firstpara = pdata;
+ lastpara = pdata;
+ }
+ }
+
+ /*
+ * Now we have an enormous linked list of every line of text in
+ * the document. Break it up into pages.
+ */
+ pages = page_breaks(firstline, lastline, conf->page_height, 0, 0);
+
+ /*
+ * Number the pages.
+ */
+ {
+ char buf[40];
+ page_data *page;
+
+ pagenum = 0;
+
+ for (page = pages; page; page = page->next) {
+ sprintf(buf, "%d", ++pagenum);
+ page->number = ufroma_dup(buf, CS_ASCII);
+ }
+
+ if (has_index) {
+ first_index_page = snew(page_data);
+ first_index_page->next = first_index_page->prev = NULL;
+ first_index_page->first_line = NULL;
+ first_index_page->last_line = NULL;
+ first_index_page->first_text = first_index_page->last_text = NULL;
+ first_index_page->first_xref = first_index_page->last_xref = NULL;
+ first_index_page->first_rect = first_index_page->last_rect = NULL;
+
+ /* And don't forget the as-yet-uncreated index. */
+ sprintf(buf, "%d", ++pagenum);
+ first_index_page->number = ufroma_dup(buf, CS_ASCII);
+ }
+ }
+
+ /*
+ * Now we're ready to actually lay out the pages. We do this by
+ * looping over _paragraphs_, since we may need to track cross-
+ * references between lines and even across pages.
+ */
+ for (pdata = firstpara; pdata; pdata = pdata->next)
+ render_para(pdata, conf, keywords, idx,
+ &index_placeholder_para, first_index_page);
+
+ /*
+ * Now we've laid out the main body pages, we should have
+ * acquired a full set of page numbers for the index.
+ */
+ if (has_index) {
+ int i;
+ indexentry *entry;
+ word *index_title;
+ para_data *firstidx, *lastidx;
+ line_data *firstidxline, *lastidxline, *ldata;
+ page_data *ipages, *ipages2, *page;
+
+ /*
+ * Create a set of paragraphs for the index.
+ */
+ index_title = fake_word(L"Index");
+
+ firstidx = make_para_data(para_UnnumberedChapter, 0, 0, 0,
+ NULL, NULL, index_title, conf);
+ lastidx = firstidx;
+ lastidx->next = NULL;
+ firstidxline = firstidx->first;
+ lastidxline = lastidx->last;
+ for (i = 0; (entry = index234(idx->entries, i)) != NULL; i++) {
+ paper_idx *pi = (paper_idx *)entry->backend_data;
+ para_data *text, *pages;
+
+ if (!pi->words)
+ continue;
+
+ text = make_para_data(para_Normal, 0, 0,
+ conf->base_width - conf->index_colwidth,
+ NULL, NULL, entry->text, conf);
+
+ pages = make_para_data(para_Normal, 0, 0,
+ conf->base_width - conf->index_colwidth,
+ NULL, NULL, pi->words, conf);
+
+ text->justification = LEFT;
+ pages->justification = RIGHT;
+ text->last->space_after = pages->first->space_before =
+ conf->base_leading / 2;
+
+ pages->last->space_after = text->first->space_before =
+ conf->base_leading;
+
+ assert(text->first);
+ assert(pages->first);
+ assert(lastidxline);
+ assert(lastidx);
+
+ /*
+ * If feasible, fold the two halves of the index entry
+ * together.
+ */
+ if (text->last->real_shortfall + pages->first->real_shortfall >
+ conf->index_colwidth + conf->index_minsep) {
+ text->last->space_after = -1;
+ pages->first->space_before = -pages->first->line_height+1;
+ }
+
+ lastidx->next = text;
+ text->next = pages;
+ pages->next = NULL;
+ lastidx = pages;
+
+ /*
+ * Link all index line structures together into
+ * a big list.
+ */
+ text->last->next = pages->first;
+ pages->first->prev = text->last;
+
+ lastidxline->next = text->first;
+ text->first->prev = lastidxline;
+
+ lastidxline = pages->last;
+
+ /*
+ * Breaking an index entry anywhere is so bad that I
+ * think I'm going to forbid it totally.
+ */
+ for (ldata = text->first; ldata && ldata->next;
+ ldata = ldata->next) {
+ ldata->next->space_before += ldata->space_after + 1;
+ ldata->space_after = -1;
+ }
+ }
+
+ /*
+ * Now break the index into pages.
+ */
+ ipages = page_breaks(firstidxline, firstidxline, conf->page_height,
+ 0, 0);
+ ipages2 = page_breaks(firstidxline->next, lastidxline,
+ conf->page_height,
+ conf->index_cols,
+ firstidxline->space_before +
+ firstidxline->line_height +
+ firstidxline->space_after);
+
+ /*
+ * This will have put each _column_ of the index on a
+ * separate page, which isn't what we want. Fold the pages
+ * back together.
+ */
+ page = ipages2;
+ while (page) {
+ int i;
+
+ for (i = 1; i < conf->index_cols; i++)
+ if (page->next) {
+ page_data *tpage;
+
+ fold_into_page(page, page->next,
+ i * (conf->index_colwidth +
+ conf->index_gutter));
+ tpage = page->next;
+ page->next = page->next->next;
+ if (page->next)
+ page->next->prev = page;
+ sfree(tpage);
+ }
+
+ page = page->next;
+ }
+ /* Also fold the heading on to the same page as the index items. */
+ fold_into_page(ipages, ipages2, 0);
+ ipages->next = ipages2->next;
+ if (ipages->next)
+ ipages->next->prev = ipages;
+ sfree(ipages2);
+ fold_into_page(first_index_page, ipages, 0);
+ first_index_page->next = ipages->next;
+ if (first_index_page->next)
+ first_index_page->next->prev = first_index_page;
+ sfree(ipages);
+ ipages = first_index_page;
+
+ /*
+ * Number the index pages, except the already-numbered
+ * first one.
+ */
+ for (page = ipages->next; page; page = page->next) {
+ char buf[40];
+ sprintf(buf, "%d", ++pagenum);
+ page->number = ufroma_dup(buf, CS_ASCII);
+ }
+
+ /*
+ * Render the index pages.
+ */
+ for (pdata = firstidx; pdata; pdata = pdata->next)
+ render_para(pdata, conf, keywords, idx,
+ &index_placeholder_para, first_index_page);
+
+ /*
+ * Link the index page list on to the end of the main page
+ * list.
+ */
+ if (!pages)
+ pages = ipages;
+ else {
+ for (page = pages; page->next; page = page->next);
+ page->next = ipages;
+ }
+
+ /*
+ * Same with the paragraph list, which will cause the index
+ * to be mentioned in the document outline.
+ */
+ if (!firstpara)
+ firstpara = firstidx;
+ else
+ lastpara->next = firstidx;
+ lastpara = lastidx;
+ }
+
+ /*
+ * Draw the headers and footers.
+ *
+ * FIXME: this should be fully configurable, but for the moment
+ * I'm just going to put in page numbers in the centre of a
+ * footer and leave it at that.
+ */
+ {
+ page_data *page;
+
+ for (page = pages; page; page = page->next) {
+ int width;
+
+ width = conf->pagenum_fontsize *
+ string_width(conf->tr, page->number, NULL);
+
+ render_string(page, conf->tr, conf->pagenum_fontsize,
+ conf->left_margin + (conf->base_width - width)/2,
+ conf->bottom_margin - conf->footer_distance,
+ page->number);
+ }
+ }
+
+ /*
+ * Start putting together the overall document structure we're
+ * going to return.
+ */
+ doc = snew(document);
+ doc->fonts = fontlist;
+ doc->pages = pages;
+ doc->paper_width = conf->paper_width;
+ doc->paper_height = conf->paper_height;
+
+ /*
+ * Collect the section heading paragraphs into a document
+ * outline. This is slightly fiddly because the Title paragraph
+ * isn't required to be at the start, although all the others
+ * must be in order.
+ */
+ {
+ int osize = 20;
+
+ doc->outline_elements = snewn(osize, outline_element);
+ doc->n_outline_elements = 0;
+
+ /* First find the title. */
+ for (pdata = firstpara; pdata; pdata = pdata->next) {
+ if (pdata->outline_level == 0) {
+ doc->outline_elements[0].level = 0;
+ doc->outline_elements[0].pdata = pdata;
+ doc->n_outline_elements++;
+ break;
+ }
+ }
+
+ /* Then collect the rest. */
+ for (pdata = firstpara; pdata; pdata = pdata->next) {
+ if (pdata->outline_level > 0) {
+ if (doc->n_outline_elements >= osize) {
+ osize += 20;
+ doc->outline_elements =
+ sresize(doc->outline_elements, osize, outline_element);
+ }
+
+ doc->outline_elements[doc->n_outline_elements].level =
+ pdata->outline_level;
+ doc->outline_elements[doc->n_outline_elements].pdata = pdata;
+ doc->n_outline_elements++;
+ }
+ }
+ }
+
+ return doc;
+}
+
+static para_data *make_para_data(int ptype, int paux, int indent, int rmargin,
+ word *pkwtext, word *pkwtext2, word *pwords,
+ paper_conf *conf)
+{
+ para_data *pdata;
+ line_data *ldata;
+ int extra_indent, firstline_indent, aux_indent;
+ word *aux, *aux2;
+
+ pdata = snew(para_data);
+ pdata->outline_level = -1;
+ pdata->outline_title = NULL;
+ pdata->rect_type = RECT_NONE;
+ pdata->contents_entry = NULL;
+ pdata->justification = JUST;
+
+ /*
+ * Choose fonts for this paragraph.
+ *
+ * FIXME: All of this ought to be completely
+ * user-configurable.
+ */
+ switch (ptype) {
+ case para_Title:
+ pdata->fonts[FONT_NORMAL] = conf->hr;
+ pdata->sizes[FONT_NORMAL] = 24;
+ pdata->fonts[FONT_EMPH] = conf->hi;
+ pdata->sizes[FONT_EMPH] = 24;
+ pdata->fonts[FONT_CODE] = conf->cb;
+ pdata->sizes[FONT_CODE] = 24;
+ pdata->outline_level = 0;
+ break;
+
+ case para_Chapter:
+ case para_Appendix:
+ case para_UnnumberedChapter:
+ pdata->fonts[FONT_NORMAL] = conf->hr;
+ pdata->sizes[FONT_NORMAL] = 20;
+ pdata->fonts[FONT_EMPH] = conf->hi;
+ pdata->sizes[FONT_EMPH] = 20;
+ pdata->fonts[FONT_CODE] = conf->cb;
+ pdata->sizes[FONT_CODE] = 20;
+ pdata->outline_level = 1;
+ break;
+
+ case para_Heading:
+ case para_Subsect:
+ pdata->fonts[FONT_NORMAL] = conf->hr;
+ pdata->fonts[FONT_EMPH] = conf->hi;
+ pdata->fonts[FONT_CODE] = conf->cb;
+ pdata->sizes[FONT_NORMAL] =
+ pdata->sizes[FONT_EMPH] =
+ pdata->sizes[FONT_CODE] =
+ (paux == 0 ? 16 : paux == 1 ? 14 : 13);
+ pdata->outline_level = 2 + paux;
+ break;
+
+ case para_Normal:
+ case para_BiblioCited:
+ case para_Bullet:
+ case para_NumberedList:
+ case para_DescribedThing:
+ case para_Description:
+ case para_Copyright:
+ pdata->fonts[FONT_NORMAL] = conf->tr;
+ pdata->sizes[FONT_NORMAL] = 12;
+ pdata->fonts[FONT_EMPH] = conf->ti;
+ pdata->sizes[FONT_EMPH] = 12;
+ pdata->fonts[FONT_CODE] = conf->cr;
+ pdata->sizes[FONT_CODE] = 12;
+ break;
+ }
+
+ /*
+ * Also select an indentation level depending on the
+ * paragraph type (list paragraphs other than
+ * para_DescribedThing need extra indent).
+ *
+ * (FIXME: Perhaps at some point we might even arrange
+ * for the user to be able to request indented first
+ * lines in paragraphs.)
+ */
+ if (ptype == para_Bullet ||
+ ptype == para_NumberedList ||
+ ptype == para_Description) {
+ extra_indent = firstline_indent = conf->indent_list;
+ } else {
+ extra_indent = firstline_indent = 0;
+ }
+
+ /*
+ * Find the auxiliary text for this paragraph.
+ */
+ aux = aux2 = NULL;
+ aux_indent = 0;
+
+ switch (ptype) {
+ case para_Chapter:
+ case para_Appendix:
+ case para_Heading:
+ case para_Subsect:
+ /*
+ * For some heading styles (FIXME: be able to
+ * configure which), the auxiliary text contains
+ * the chapter number and is arranged to be
+ * right-aligned a few points left of the primary
+ * margin. For other styles, the auxiliary text is
+ * the full chapter _name_ and takes up space
+ * within the (wrapped) chapter title, meaning that
+ * we must move the first line indent over to make
+ * space for it.
+ */
+ if (ptype == para_Heading || ptype == para_Subsect) {
+ int len;
+
+ aux = pkwtext2;
+ len = paper_width_simple(pdata, pkwtext2, conf);
+ aux_indent = -len - conf->sect_num_left_space;
+
+ pdata->outline_title =
+ prepare_outline_title(pkwtext2, L" ", pwords);
+ } else {
+ aux = pkwtext;
+ aux2 = fake_word(L": ");
+ aux_indent = 0;
+
+ firstline_indent += paper_width_simple(pdata, aux, conf);
+ firstline_indent += paper_width_simple(pdata, aux2, conf);
+
+ pdata->outline_title =
+ prepare_outline_title(pkwtext, L": ", pwords);
+ }
+ break;
+
+ case para_Bullet:
+ /*
+ * Auxiliary text consisting of a bullet.
+ */
+ aux = fake_word(conf->bullet);
+ aux_indent = indent + conf->indent_list_bullet;
+ break;
+
+ case para_NumberedList:
+ /*
+ * Auxiliary text consisting of the number followed
+ * by a (FIXME: configurable) full stop.
+ */
+ aux = pkwtext;
+ aux2 = fake_word(L".");
+ aux_indent = indent + conf->indent_list_bullet;
+ break;
+
+ case para_BiblioCited:
+ /*
+ * Auxiliary text consisting of the bibliography
+ * reference text, and a trailing space.
+ */
+ aux = pkwtext;
+ aux2 = fake_word(L" ");
+ aux_indent = indent;
+ firstline_indent += paper_width_simple(pdata, aux, conf);
+ firstline_indent += paper_width_simple(pdata, aux2, conf);
+ break;
+ }
+
+ if (pdata->outline_level >= 0 && !pdata->outline_title) {
+ pdata->outline_title =
+ prepare_outline_title(NULL, NULL, pwords);
+ }
+
+ wrap_paragraph(pdata, pwords, conf->base_width - rmargin,
+ indent + firstline_indent,
+ indent + extra_indent, conf);
+
+ pdata->first->aux_text = aux;
+ pdata->first->aux_text_2 = aux2;
+ pdata->first->aux_left_indent = aux_indent;
+
+ /*
+ * Line breaking penalties.
+ */
+ switch (ptype) {
+ case para_Chapter:
+ case para_Appendix:
+ case para_Heading:
+ case para_Subsect:
+ case para_UnnumberedChapter:
+ /*
+ * Fixed and large penalty for breaking straight
+ * after a heading; corresponding bonus for
+ * breaking straight before.
+ */
+ pdata->first->penalty_before = -500000;
+ pdata->last->penalty_after = 500000;
+ for (ldata = pdata->first; ldata; ldata = ldata->next)
+ ldata->penalty_after = 500000;
+ break;
+
+ case para_DescribedThing:
+ /*
+ * This is treated a bit like a small heading:
+ * there's a penalty for breaking after it (i.e.
+ * between it and its description), and a bonus for
+ * breaking before it (actually _between_ list
+ * items).
+ */
+ pdata->first->penalty_before = -200000;
+ pdata->last->penalty_after = 200000;
+ break;
+
+ default:
+ /*
+ * Most paragraph types: widow/orphan control by
+ * discouraging breaking one line from the end of
+ * any paragraph.
+ */
+ if (pdata->first != pdata->last) {
+ pdata->first->penalty_after = 100000;
+ pdata->last->penalty_before = 100000;
+ }
+ break;
+ }
+
+ standard_line_spacing(pdata, conf);
+
+ /*
+ * Some kinds of section heading require a page break before
+ * them and an underline after.
+ */
+ if (ptype == para_Title ||
+ ptype == para_Chapter ||
+ ptype == para_Appendix ||
+ ptype == para_UnnumberedChapter) {
+ pdata->first->page_break = TRUE;
+ pdata->first->space_before = conf->chapter_top_space;
+ pdata->last->space_after +=
+ (conf->chapter_underline_depth +
+ conf->chapter_underline_thickness);
+ pdata->rect_type = RECT_CHAPTER_UNDERLINE;
+ }
+
+ return pdata;
+}
+
+static void standard_line_spacing(para_data *pdata, paper_conf *conf)
+{
+ line_data *ldata;
+
+ /*
+ * Set the line spacing for each line in this paragraph.
+ */
+ for (ldata = pdata->first; ldata; ldata = ldata->next) {
+ if (ldata == pdata->first)
+ ldata->space_before = conf->base_para_spacing / 2;
+ else
+ ldata->space_before = conf->base_leading / 2;
+ if (ldata == pdata->last)
+ ldata->space_after = conf->base_para_spacing / 2;
+ else
+ ldata->space_after = conf->base_leading / 2;
+ ldata->page_break = FALSE;
+ }
+}
+
+static font_encoding *new_font_encoding(font_data *font)
+{
+ font_encoding *fe;
+ int i;
+
+ fe = snew(font_encoding);
+ fe->next = NULL;
+
+ if (font->list->tail)
+ font->list->tail->next = fe;
+ else
+ font->list->head = fe;
+ font->list->tail = fe;
+
+ fe->font = font;
+ fe->free_pos = 0x21;
+
+ for (i = 0; i < 256; i++) {
+ fe->vector[i] = NULL;
+ fe->indices[i] = -1;
+ fe->to_unicode[i] = 0xFFFF;
+ }
+
+ return fe;
+}
+
+static int kern_cmp(void *a, void *b)
+{
+ kern_pair const *ka = a, *kb = b;
+
+ if (ka->left < kb->left)
+ return -1;
+ if (ka->left > kb->left)
+ return 1;
+ if (ka->right < kb->right)
+ return -1;
+ if (ka->right > kb->right)
+ return 1;
+ return 0;
+}
+
+static font_data *make_std_font(font_list *fontlist, char const *name)
+{
+ const int *widths;
+ const kern_pair *kerns;
+ int nglyphs;
+ font_data *f;
+ font_encoding *fe;
+ int i;
+
+ /* XXXKERN */
+ widths = ps_std_font_widths(name);
+ kerns = ps_std_font_kerns(name);
+ if (!widths || !kerns)
+ return NULL;
+
+ for (nglyphs = 0; ps_std_glyphs[nglyphs] != NULL; nglyphs++);
+
+ f = snew(font_data);
+
+ f->list = fontlist;
+ f->name = name;
+ f->nglyphs = nglyphs;
+ f->glyphs = ps_std_glyphs;
+ f->widths = widths;
+ f->kerns = newtree234(kern_cmp);
+ for (;kerns->left != 0xFFFF; kerns++)
+ add234(f->kerns, (void *)kerns);
+ f->subfont_map = snewn(nglyphs, subfont_map_entry);
+
+ /*
+ * Our first subfont will contain all of US-ASCII. This isn't
+ * really necessary - we could just create custom subfonts
+ * precisely as the whim of render_string dictated - but
+ * instinct suggests that it might be nice to have the text in
+ * the output files look _marginally_ recognisable.
+ */
+ fe = new_font_encoding(f);
+ fe->free_pos = 0xA1; /* only the top half is free */
+ f->latest_subfont = fe;
+
+ for (i = 0; i < (int)lenof(f->bmp); i++)
+ f->bmp[i] = 0xFFFF;
+
+ for (i = 0; i < nglyphs; i++) {
+ wchar_t ucs;
+ ucs = ps_glyph_to_unicode(f->glyphs[i]);
+ assert(ucs != 0xFFFF);
+ f->bmp[ucs] = i;
+ if (ucs >= 0x20 && ucs <= 0x7E) {
+ fe->vector[ucs] = f->glyphs[i];
+ fe->indices[ucs] = i;
+ fe->to_unicode[ucs] = ucs;
+ f->subfont_map[i].subfont = fe;
+ f->subfont_map[i].position = ucs;
+ } else {
+ /*
+ * This character is not yet assigned to a subfont.
+ */
+ f->subfont_map[i].subfont = NULL;
+ f->subfont_map[i].position = 0;
+ }
+ }
+
+ return f;
+}
+
+/* NB: arguments are glyph numbers from font->bmp. */
+static int find_kern(font_data *font, int lindex, int rindex)
+{
+ kern_pair wantkp;
+ kern_pair const *kp;
+
+ if (lindex == 0xFFFF || rindex == 0xFFFF)
+ return 0;
+ wantkp.left = lindex;
+ wantkp.right = rindex;
+ kp = find234(font->kerns, &wantkp, NULL);
+ if (kp == NULL)
+ return 0;
+ return kp->kern;
+}
+
+static int string_width(font_data *font, wchar_t const *string, int *errs)
+{
+ int width = 0;
+ int index, oindex;
+
+ if (errs)
+ *errs = 0;
+
+ oindex = 0xFFFF;
+ for (; *string; string++) {
+ index = (*string < 0 || *string > 0xFFFF ? 0xFFFF :
+ font->bmp[*string]);
+
+ if (index == 0xFFFF) {
+ if (errs)
+ *errs = 1;
+ } else {
+ width += find_kern(font, oindex, index) + font->widths[index];
+ }
+ oindex = index;
+ }
+
+ return width;
+}
+
+static int paper_width_internal(void *vctx, word *word, int *nspaces);
+
+struct paper_width_ctx {
+ int minspacewidth;
+ para_data *pdata;
+ paper_conf *conf;
+};
+
+static int paper_width_list(void *vctx, word *text, word *end, int *nspaces) {
+ int w = 0;
+ while (text && text != end) {
+ w += paper_width_internal(vctx, text, nspaces);
+ text = text->next;
+ }
+ return w;
+}
+
+static int paper_width_internal(void *vctx, word *word, int *nspaces)
+{
+ struct paper_width_ctx *ctx = (struct paper_width_ctx *)vctx;
+ int style, type, findex, width, errs;
+ wchar_t *str;
+
+ switch (word->type) {
+ case word_HyperLink:
+ case word_HyperEnd:
+ case word_UpperXref:
+ case word_LowerXref:
+ case word_PageXref:
+ case word_XrefEnd:
+ case word_IndexRef:
+ return 0;
+ }
+
+ style = towordstyle(word->type);
+ type = removeattr(word->type);
+
+ findex = (style == word_Normal ? FONT_NORMAL :
+ style == word_Emph ? FONT_EMPH :
+ FONT_CODE);
+
+ if (type == word_Normal) {
+ str = word->text;
+ } else if (type == word_WhiteSpace) {
+ if (findex != FONT_CODE) {
+ if (nspaces)
+ (*nspaces)++;
+ return ctx->minspacewidth;
+ } else
+ str = L" ";
+ } else /* if (type == word_Quote) */ {
+ if (word->aux == quote_Open)
+ str = ctx->conf->lquote;
+ else
+ str = ctx->conf->rquote;
+ }
+
+ width = string_width(ctx->pdata->fonts[findex], str, &errs);
+
+ if (errs && word->alt)
+ return paper_width_list(vctx, word->alt, NULL, nspaces);
+ else
+ return ctx->pdata->sizes[findex] * width;
+}
+
+static int paper_width(void *vctx, word *word)
+{
+ return paper_width_internal(vctx, word, NULL);
+}
+
+static int paper_width_simple(para_data *pdata, word *text, paper_conf *conf)
+{
+ struct paper_width_ctx ctx;
+
+ ctx.pdata = pdata;
+ ctx.minspacewidth =
+ (pdata->sizes[FONT_NORMAL] *
+ string_width(pdata->fonts[FONT_NORMAL], L" ", NULL));
+ ctx.conf = conf;
+
+ return paper_width_list(&ctx, text, NULL, NULL);
+}
+
+static void wrap_paragraph(para_data *pdata, word *words,
+ int w, int i1, int i2, paper_conf *conf)
+{
+ wrappedline *wrapping, *p;
+ int spacewidth;
+ struct paper_width_ctx ctx;
+ int line_height;
+
+ /*
+ * We're going to need to store the line height in every line
+ * structure we generate.
+ */
+ {
+ int i;
+ line_height = 0;
+ for (i = 0; i < NFONTS; i++)
+ if (line_height < pdata->sizes[i])
+ line_height = pdata->sizes[i];
+ line_height *= UNITS_PER_PT;
+ }
+
+ spacewidth = (pdata->sizes[FONT_NORMAL] *
+ string_width(pdata->fonts[FONT_NORMAL], L" ", NULL));
+ if (spacewidth == 0) {
+ /*
+ * A font without a space?! Disturbing. I hope this never
+ * comes up, but I'll make a random guess anyway and set my
+ * space width to half the point size.
+ */
+ spacewidth = pdata->sizes[FONT_NORMAL] * UNITS_PER_PT / 2;
+ }
+
+ /*
+ * I'm going to set the _minimum_ space width to 3/5 of the
+ * standard one, and use the standard one as the optimum.
+ */
+ ctx.minspacewidth = spacewidth * 3 / 5;
+ ctx.pdata = pdata;
+ ctx.conf = conf;
+
+ wrapping = wrap_para(words, w - i1, w - i2, paper_width, &ctx, spacewidth);
+
+ /*
+ * Having done the wrapping, we now concoct a set of line_data
+ * structures.
+ */
+ pdata->first = pdata->last = NULL;
+
+ for (p = wrapping; p; p = p->next) {
+ line_data *ldata;
+ word *wd;
+ int len, wid, spaces;
+
+ ldata = snew(line_data);
+
+ ldata->pdata = pdata;
+ ldata->first = p->begin;
+ ldata->end = p->end;
+ ldata->line_height = line_height;
+
+ ldata->xpos = (p == wrapping ? i1 : i2);
+
+ if (pdata->last) {
+ pdata->last->next = ldata;
+ ldata->prev = pdata->last;
+ } else {
+ pdata->first = ldata;
+ ldata->prev = NULL;
+ }
+ ldata->next = NULL;
+ pdata->last = ldata;
+
+ spaces = 0;
+ len = paper_width_list(&ctx, ldata->first, ldata->end, &spaces);
+ wid = (p == wrapping ? w - i1 : w - i2);
+ wd = ldata->first;
+
+ ldata->hshortfall = wid - len;
+ ldata->nspaces = spaces;
+ /*
+ * This tells us how much the space width needs to
+ * change from _min_spacewidth. But we want to store
+ * its difference from the _natural_ space width, to
+ * make the text rendering easier.
+ */
+ ldata->hshortfall += ctx.minspacewidth * spaces;
+ ldata->hshortfall -= spacewidth * spaces;
+ ldata->real_shortfall = ldata->hshortfall;
+ /*
+ * Special case: on the last line of a paragraph, we
+ * never stretch spaces.
+ */
+ if (ldata->hshortfall > 0 && !p->next)
+ ldata->hshortfall = 0;
+
+ ldata->aux_text = NULL;
+ ldata->aux_text_2 = NULL;
+ ldata->aux_left_indent = 0;
+ ldata->penalty_before = ldata->penalty_after = 0;
+ }
+
+}
+
+static page_data *page_breaks(line_data *first, line_data *last,
+ int page_height, int ncols, int headspace)
+{
+ line_data *l, *m;
+ page_data *ph, *pt;
+ int n, n1, this_height;
+
+ /*
+ * Page breaking is done by a close analogue of the optimal
+ * paragraph wrapping algorithm used by wrap_para(). We work
+ * backwards from the end of the document line by line; for
+ * each line, we contemplate every possible number of lines we
+ * could put on a page starting with that line, determine a
+ * cost function for each one, add it to the pre-computed cost
+ * function for optimally page-breaking everything after that
+ * page, and pick the best option.
+ *
+ * This is made slightly more complex by the fact that we have
+ * a multi-column index with a heading at the top of the
+ * _first_ page, meaning that the first _ncols_ pages must have
+ * a different length. Hence, we must do the wrapping ncols+1
+ * times over, hypothetically trying to put every subsequence
+ * on every possible page.
+ *
+ * Since my line_data structures are only used for this
+ * purpose, I might as well just store the algorithm data
+ * directly in them.
+ */
+
+ for (l = last; l; l = l->prev) {
+ l->bestcost = snewn(ncols+1, int);
+ l->vshortfall = snewn(ncols+1, int);
+ l->text = snewn(ncols+1, int);
+ l->space = snewn(ncols+1, int);
+ l->page_last = snewn(ncols+1, line_data *);
+
+ for (n = 0; n <= ncols; n++) {
+ int minheight, text = 0, space = 0;
+ int cost;
+
+ n1 = (n < ncols ? n+1 : ncols);
+ if (n < ncols)
+ this_height = page_height - headspace;
+ else
+ this_height = page_height;
+
+ l->bestcost[n] = -1;
+ for (m = l; m; m = m->next) {
+ if (m != l && m->page_break)
+ break; /* we've gone as far as we can */
+
+ if (m != l) {
+ if (m->prev->space_after > 0)
+ space += m->prev->space_after;
+ else
+ text += m->prev->space_after;
+ }
+ if (m != l || m->page_break) {
+ if (m->space_before > 0)
+ space += m->space_before;
+ else
+ text += m->space_before;
+ }
+ text += m->line_height;
+ minheight = text + space;
+
+ if (m != l && minheight > this_height)
+ break;
+
+ /*
+ * If the space after this paragraph is _negative_
+ * (which means the next line is folded on to this
+ * one, which happens in the index), we absolutely
+ * cannot break here.
+ */
+ if (m->space_after >= 0) {
+
+ /*
+ * Compute the cost of this arrangement, as the
+ * square of the amount of wasted space on the
+ * page. Exception: if this is the last page
+ * before a mandatory break or the document
+ * end, we don't penalise a large blank area.
+ */
+ if (m != last && m->next && !m->next->page_break)
+ {
+ int x = (this_height - minheight) / FUNITS_PER_PT *
+ 4096.0;
+ int xf;
+
+ xf = x & 0xFF;
+ x >>= 8;
+
+ cost = x*x;
+ cost += (x * xf) >> 8;
+ } else
+ cost = 0;
+
+ if (m != last && m->next && !m->next->page_break) {
+ cost += m->penalty_after;
+ cost += m->next->penalty_before;
+ }
+
+ if (m != last && m->next && !m->next->page_break)
+ cost += m->next->bestcost[n1];
+ if (l->bestcost[n] == -1 || l->bestcost[n] > cost) {
+ /*
+ * This is the best option yet for this
+ * starting point.
+ */
+ l->bestcost[n] = cost;
+ if (m != last && m->next && !m->next->page_break)
+ l->vshortfall[n] = this_height - minheight;
+ else
+ l->vshortfall[n] = 0;
+ l->text[n] = text;
+ l->space[n] = space;
+ l->page_last[n] = m;
+ }
+ }
+
+ if (m == last)
+ break;
+ }
+ }
+ }
+