lily/page-layout-problem.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2009--2011 Joe Neeman <joeneeman@gmail.com>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "page-layout-problem.hh"
  21
  22 #include "align-interface.hh"
  23 #include "axis-group-interface.hh"
  24 #include "hara-kiri-group-spanner.hh"
  25 #include "international.hh"
  26 #include "item.hh"
  27 #include "output-def.hh"
  28 #include "paper-book.hh"
  29 #include "paper-column.hh"
  30 #include "paper-score.hh"
  31 #include "pointer-group-interface.hh"
  32 #include "prob.hh"
  33 #include "skyline-pair.hh"
  34 #include "system.hh"
  35 #include "text-interface.hh"
  36
  37 /*
  38  Returns the number of footntoes associated with a given line.
  39 */
  40
  41 vsize
  42 Page_layout_problem::get_footnote_count (SCM lines)
  43 {
  44   vsize fn_count = 0;
  45   for (SCM s = lines; scm_is_pair (s); s = scm_cdr (s))
  46     {
  47       if (Grob *g = unsmob_grob (scm_car (s)))
  48         {
  49           System *sys = dynamic_cast<System *> (g);
  50           if (!sys)
  51             {
  52               programming_error ("got a grob for footnotes that wasn't a System");
  53               continue;
  54             }
  55           fn_count += sys->num_footnotes ();
  56         }
  57       else if (Prob *p = unsmob_prob (scm_car (s)))
  58         {
  59           SCM stencils = p->get_property ("footnotes");
  60           if (stencils == SCM_EOL)
  61             continue;
  62           for (SCM st = stencils; scm_is_pair (st); st = scm_cdr (st))
  63             fn_count++;
  64         }
  65     }
  66
  67   return fn_count;
  68 }
  69
  70 SCM
  71 Page_layout_problem::get_footnotes_from_lines (SCM lines)
  72 {
  73   if (!scm_is_pair (lines))
  74     return SCM_EOL;
  75
  76   bool footnotes_added;
  77   if (Grob *g = unsmob_grob (scm_car (lines)))
  78     footnotes_added = !scm_is_null (g->get_property ("footnote-stencil"));
  79   else if (Prob *p = unsmob_prob (scm_car (lines)))
  80     footnotes_added = !scm_is_null (p->get_property ("footnote-stencil"));
  81   else
  82     {
  83       programming_error ("Systems on a page must be a prob or grob.");
  84       return SCM_EOL;
  85     }
  86   if (!footnotes_added)
  87     {
  88       programming_error ("Footnotes must be added to lines before they are retrieved.");
  89       return SCM_EOL;
  90     }
  91
  92   SCM out = SCM_EOL;
  93   for (SCM s = lines; scm_is_pair (s); s = scm_cdr (s))
  94     {
  95       if (Grob *g = unsmob_grob (scm_car (s)))
  96         out = scm_cons (g->get_property ("footnote-stencil"), out);
  97       else if (Prob *p = unsmob_prob (scm_car (s)))
  98         out = scm_cons (p->get_property ("footnote-stencil"), out);
  99       else
 100         programming_error ("Systems on a page must be a prob or grob.");
 101     }
 102
 103   return scm_reverse (out);
 104 }
 105
 106 /*
 107    Adds a footnote stencil to each system.  This stencil may
 108    itself be comprised of several footnotes.
 109
 110    This is a long function, but it seems better to keep it intact rather than
 111    splitting it into parts.
 112 */
 113
 114 void
 115 Page_layout_problem::add_footnotes_to_lines (SCM lines, int counter, Paper_book *pb)
 116 {
 117   /*
 118     first, we have to see how many footnotes are on this page.
 119     we need to do this first so that we can line them up
 120   */
 121
 122   Output_def *paper = pb->paper_;
 123
 124   if (!paper)
 125     {
 126       programming_error ("Cannot get footnotes because there is no valid paper block.");
 127       return;
 128     }
 129
 130   SCM number_footnote_table = pb->top_paper ()->c_variable ("number-footnote-table");
 131   if (!scm_is_pair (number_footnote_table))
 132     number_footnote_table = SCM_EOL;
 133   SCM numbering_function = paper->c_variable ("footnote-numbering-function");
 134   SCM layout = paper->self_scm ();
 135   SCM props = scm_call_1 (ly_lily_module_constant ("layout-extract-page-properties"),
 136                           paper->self_scm ());
 137   Real padding = robust_scm2double (paper->c_variable ("footnote-padding"), 0.0);
 138   Real number_raise = robust_scm2double (paper->c_variable ("footnote-number-raise"), 0.0);
 139
 140   vsize fn_count = get_footnote_count (lines);
 141
 142   // now, make the footnote stencils with the numbering function
 143   SCM numbers = SCM_EOL;
 144   SCM in_text_numbers = SCM_EOL;
 145   /*
 146     TODO: This recalculates numbering every time this function is called, including once
 147     after the balloon prints are called.  Although it is not a huge computational drain,
 148     it'd be more elegant to turn this calculation off when it is no longer needed.
 149
 150     In a separate commit, it'd be nice to streamline the way that page layout property
 151     is handled so that the process of building `config's in page-breaking does result
 152     in duplicated work, either by making this process less complicated or (preferably)
 153     by passing its results downstream.
 154   */
 155   vector<SCM> footnote_number_markups; // Holds the numbering markups.
 156   vector<Stencil *> footnote_number_stencils; // Holds translated versions of the stencilized numbering markups.
 157   for (vsize i = 0; i < fn_count; i++)
 158     {
 159       SCM markup = scm_call_1 (numbering_function, scm_from_int (counter));
 160       Stencil *s = unsmob_stencil (Text_interface::interpret_markup (layout, props, markup));
 161       if (!s)
 162         {
 163           programming_error ("Your numbering function needs to return a stencil.");
 164           markup = SCM_EOL;
 165           s = new Stencil (Box (Interval (0, 0), Interval (0, 0)), SCM_EOL);
 166         }
 167       footnote_number_markups.push_back (markup);
 168       footnote_number_stencils.push_back (s);
 169       counter++;
 170     }
 171
 172   // find the maximum X_AXIS length
 173   Real max_length = -infinity_f;
 174   for (vsize i = 0; i < fn_count; i++)
 175     max_length = max (max_length, footnote_number_stencils[i]->extent (X_AXIS).length ());
 176
 177   /*
 178     translate each stencil such that it attains the correct maximum length and bundle the
 179     footnotes into a scheme object.
 180   */
 181   SCM *tail = &numbers;
 182   SCM *in_text_tail = &in_text_numbers;
 183
 184   for (vsize i = 0; i < fn_count; i++)
 185     {
 186       *in_text_tail = scm_cons (footnote_number_markups[i], SCM_EOL);
 187       in_text_tail = SCM_CDRLOC (*in_text_tail);
 188       footnote_number_stencils[i]->translate_axis ((max_length
 189                                                     - footnote_number_stencils[i]->extent (X_AXIS).length ()),
 190                                                    X_AXIS);
 191       *tail = scm_cons (footnote_number_stencils[i]->smobbed_copy (), SCM_EOL);
 192       tail = SCM_CDRLOC (*tail);
 193     }
 194   // build the footnotes
 195
 196   for (SCM s = lines; scm_is_pair (s); s = scm_cdr (s))
 197     {
 198       // Take care of musical systems.
 199       if (Grob *g = unsmob_grob (scm_car (s)))
 200         {
 201           System *sys = dynamic_cast<System *> (g);
 202           if (!sys)
 203             {
 204               programming_error ("got a grob for footnotes that wasn't a System");
 205               continue;
 206             }
 207           Stencil mol;
 208           Stencil in_note_mol;
 209           for (vsize i = 0; i < sys->footnote_grobs ()->size (); i++)
 210             {
 211               Grob *footnote = sys->footnote_grobs ()->at (i);
 212               SCM footnote_markup = footnote->get_property ("footnote-text");
 213               if (Spanner *orig = dynamic_cast<Spanner *>(footnote))
 214                 if (orig->is_broken ())
 215                   footnote_markup = orig->broken_intos_[0]->get_property ("footnote-text");
 216
 217               SCM props = scm_call_1 (ly_lily_module_constant ("layout-extract-page-properties"),
 218                                       paper->self_scm ());
 219
 220               SCM footnote_stl = Text_interface::interpret_markup (paper->self_scm (),
 221                                                                    props, footnote_markup);
 222
 223               Stencil *footnote_stencil = unsmob_stencil (footnote_stl);
 224               bool do_numbering = to_boolean (footnote->get_property ("automatically-numbered"));
 225               if (Spanner *orig = dynamic_cast<Spanner *>(footnote))
 226                 {
 227                   if (orig->is_broken ())
 228                     for (vsize i = 0; i < orig->broken_intos_.size (); i++)
 229                       do_numbering = do_numbering
 230                                     || to_boolean (orig->broken_intos_[i]->get_property ("automatically-numbered"));
 231                 }
 232               if (do_numbering)
 233                 {
 234                   SCM annotation_scm = scm_car (in_text_numbers);
 235                   footnote->set_property ("text", annotation_scm);
 236                   if (Spanner *orig = dynamic_cast<Spanner *>(footnote))
 237                     {
 238                       orig->set_property ("text", annotation_scm);
 239                       if (orig->is_broken ())
 240                         for (vsize i = 0; i < orig->broken_intos_.size (); i++)
 241                           orig->broken_intos_[i]->set_property ("text", annotation_scm);
 242                     }
 243
 244                   Stencil *annotation = unsmob_stencil (scm_car (numbers));
 245                   annotation->translate_axis ((footnote_stencil->extent (Y_AXIS)[UP]
 246                                                + number_raise
 247                                                - annotation->extent (Y_AXIS)[UP]),
 248                                               Y_AXIS);
 249                   footnote_stencil->add_at_edge (X_AXIS, LEFT, *annotation, 0.0);
 250                   numbers = scm_cdr (numbers);
 251                   in_text_numbers = scm_cdr (in_text_numbers);
 252                 }
 253               if (!footnote_stencil->is_empty ())
 254                 {
 255                   if (to_boolean (footnote->get_property ("footnote")))
 256                     mol.add_at_edge (Y_AXIS, DOWN, *footnote_stencil, padding);
 257                   else
 258                     in_note_mol.add_at_edge (Y_AXIS, DOWN, *footnote_stencil, padding);
 259                 }
 260             }
 261           sys->set_property ("in-note-stencil", in_note_mol.smobbed_copy ());
 262           sys->set_property ("footnote-stencil", mol.smobbed_copy ());
 263         }
 264       // Take care of top-level markups
 265       else if (Prob *p = unsmob_prob (scm_car (s)))
 266         {
 267           SCM stencils = p->get_property ("footnotes");
 268           Stencil mol;
 269
 270           for (SCM st = stencils; scm_is_pair (st); st = scm_cdr (st))
 271             {
 272               Stencil footnote_stencil;
 273               Stencil *footnote = unsmob_stencil (scm_caddar (st));
 274               footnote_stencil.add_stencil (*footnote);
 275               bool do_numbering = to_boolean (scm_cadar (st));
 276               SCM in_text_stencil = Stencil ().smobbed_copy ();
 277               if (do_numbering)
 278                 {
 279                   Stencil *annotation = unsmob_stencil (scm_car (numbers));
 280                   SCM in_text_annotation = scm_car (in_text_numbers);
 281                   in_text_stencil = Text_interface::interpret_markup (layout,
 282                                                                       props,
 283                                                                       in_text_annotation);
 284                   if (!unsmob_stencil (in_text_stencil))
 285                     in_text_stencil = SCM_EOL;
 286                   annotation->translate_axis ((footnote_stencil.extent (Y_AXIS)[UP]
 287                                                + number_raise
 288                                                - annotation->extent (Y_AXIS)[UP]),
 289                                               Y_AXIS);
 290                   footnote_stencil.add_at_edge (X_AXIS, LEFT, *annotation, 0.0);
 291                   numbers = scm_cdr (numbers);
 292                   in_text_numbers = scm_cdr (in_text_numbers);
 293                 }
 294               number_footnote_table = scm_cons (scm_cons (scm_caar (st),
 295                                                           in_text_stencil),
 296                                                 number_footnote_table);
 297               if (!footnote_stencil.is_empty ())
 298                 mol.add_at_edge (Y_AXIS, DOWN, footnote_stencil, padding);
 299             }
 300           p->set_property ("footnote-stencil", mol.smobbed_copy ());
 301         }
 302     }
 303
 304   // note that this line of code doesn't do anything if numbering isn't turned on
 305   pb->top_paper ()->set_variable (ly_symbol2scm ("number-footnote-table"), number_footnote_table);
 306 }
 307
 308 Stencil *
 309 Page_layout_problem::get_footnote_separator_stencil (Output_def *paper)
 310 {
 311   SCM props = scm_call_1 (ly_lily_module_constant ("layout-extract-page-properties"),
 312                           paper->self_scm ());
 313
 314   SCM markup = paper->c_variable ("footnote-separator-markup");
 315
 316   if (!Text_interface::is_markup (markup))
 317     return NULL;
 318
 319   SCM footnote_stencil = Text_interface::interpret_markup (paper->self_scm (),
 320                                                            props, markup);
 321
 322   Stencil *footnote_separator = unsmob_stencil (footnote_stencil);
 323
 324   return footnote_separator;
 325 }
 326
 327 void
 328 Page_layout_problem::add_footnotes_to_footer (SCM footnotes, Stencil *foot, Paper_book *pb)
 329 {
 330   if (!foot && scm_is_pair (footnotes))
 331     {
 332       warning ("Must have a footer to add footnotes.");
 333       return;
 334     }
 335   bool footnotes_found = false;
 336   Real footnote_padding = robust_scm2double (pb->paper_->c_variable ("footnote-padding"), 0.0);
 337   Real footnote_footer_padding = robust_scm2double (pb->paper_->c_variable ("footnote-footer-padding"), 0.0);
 338
 339   footnotes = scm_reverse (footnotes);
 340
 341   for (SCM s = footnotes; scm_is_pair (s); s = scm_cdr (s))
 342     {
 343       Stencil *stencil = unsmob_stencil (scm_car (s));
 344
 345       if (!stencil)
 346         continue;
 347
 348       if (!stencil->is_empty ())
 349         {
 350           foot->add_at_edge (Y_AXIS, UP, *stencil, (!footnotes_found ? footnote_footer_padding : footnote_padding));
 351           footnotes_found = true;
 352         }
 353     }
 354
 355   if (footnotes_found)
 356     {
 357       Stencil *separator = get_footnote_separator_stencil (pb->paper_);
 358       if (separator)
 359         foot->add_at_edge (Y_AXIS, UP, *separator, footnote_padding);
 360     }
 361 }
 362
 363 Page_layout_problem::Page_layout_problem (Paper_book *pb, SCM page_scm, SCM systems)
 364   : bottom_skyline_ (DOWN)
 365 {
 366   Prob *page = unsmob_prob (page_scm);
 367   header_height_ = 0;
 368   footer_height_ = 0;
 369   header_padding_ = 0;
 370   footer_padding_ = 0;
 371   page_height_ = 100;
 372
 373   if (page)
 374     {
 375       Stencil *head = unsmob_stencil (page->get_property ("head-stencil"));
 376       Stencil *foot = unsmob_stencil (page->get_property ("foot-stencil"));
 377
 378       if (pb && pb->paper_)
 379         {
 380           SCM footnotes = get_footnotes_from_lines (systems);
 381           add_footnotes_to_footer (footnotes, foot, pb);
 382         }
 383       else
 384         warning ("A page layout problem has been initiated that cannot accommodate footnotes.");
 385
 386       header_height_ = head ? head->extent (Y_AXIS).length () : 0;
 387       footer_height_ = foot ? foot->extent (Y_AXIS).length () : 0;
 388       page_height_ = robust_scm2double (page->get_property ("paper-height"), 100);
 389     }
 390
 391   // Initially, bottom_skyline_ represents the top of the page. Make
 392   // it solid, so that the top of the first system will be forced
 393   // below the top of the printable area.
 394   bottom_skyline_.set_minimum_height (-header_height_);
 395
 396   SCM system_system_spacing = SCM_EOL;
 397   SCM score_system_spacing = SCM_EOL;
 398   SCM markup_system_spacing = SCM_EOL;
 399   SCM score_markup_spacing = SCM_EOL;
 400   SCM markup_markup_spacing = SCM_EOL;
 401
 402   // top_system_spacing controls the spring from the top of the printable
 403   // area to the first staff. It allows the user to control the offset of
 404   // the first staff (as opposed to the top of the first system) from the
 405   // top of the page. Similarly for last_bottom_spacing.
 406   SCM top_system_spacing = SCM_EOL;
 407   SCM last_bottom_spacing = SCM_EOL;
 408   if (pb && pb->paper_)
 409     {
 410       Output_def *paper = pb->paper_;
 411       system_system_spacing = paper->c_variable ("system-system-spacing");
 412       score_system_spacing = paper->c_variable ("score-system-spacing");
 413       markup_system_spacing = paper->c_variable ("markup-system-spacing");
 414       score_markup_spacing = paper->c_variable ("score-markup-spacing");
 415       markup_markup_spacing = paper->c_variable ("markup-markup-spacing");
 416       last_bottom_spacing = paper->c_variable ("last-bottom-spacing");
 417       top_system_spacing = paper->c_variable ("top-system-spacing");
 418       if (scm_is_pair (systems) && unsmob_prob (scm_car (systems)))
 419         top_system_spacing = paper->c_variable ("top-markup-spacing");
 420
 421       // Note: the page height here does _not_ reserve space for headers and
 422       // footers. This is because we want to anchor the top-system-spacing
 423       // spring at the _top_ of the header.
 424       page_height_ -= robust_scm2double (paper->c_variable ("top-margin"), 0)
 425                       + robust_scm2double (paper->c_variable ("bottom-margin"), 0);
 426
 427       read_spacing_spec (top_system_spacing, &header_padding_, ly_symbol2scm ("padding"));
 428       read_spacing_spec (last_bottom_spacing, &footer_padding_, ly_symbol2scm ("padding"));
 429       in_note_padding_ = robust_scm2double (paper->c_variable ("in-note-padding"), 0.5);
 430       in_note_direction_ = robust_scm2dir (paper->c_variable ("in-note-direction"), UP);
 431     }
 432   bool last_system_was_title = false;
 433
 434   for (SCM s = systems; scm_is_pair (s); s = scm_cdr (s))
 435     {
 436       bool first = (s == systems);
 437
 438       if (Grob *g = unsmob_grob (scm_car (s)))
 439         {
 440           System *sys = dynamic_cast<System *> (g);
 441           if (!sys)
 442             {
 443               programming_error ("got a grob for vertical spacing that wasn't a System");
 444               continue;
 445             }
 446
 447           SCM spec = system_system_spacing;
 448           if (first)
 449             spec = top_system_spacing;
 450           else if (last_system_was_title)
 451             spec = markup_system_spacing;
 452           else if (0 == Paper_column::get_rank (sys->get_bound (LEFT)))
 453             spec = score_system_spacing;
 454
 455           Spring spring (0, 0);
 456           Real padding = 0.0;
 457           Real indent = line_dimensions_int (sys->paper_score ()->layout (), sys->get_rank ())[LEFT];
 458           alter_spring_from_spacing_spec (spec, &spring);
 459           read_spacing_spec (spec, &padding, ly_symbol2scm ("padding"));
 460
 461           append_system (sys, spring, indent, padding);
 462           last_system_was_title = false;
 463         }
 464       else if (Prob *p = unsmob_prob (scm_car (s)))
 465         {
 466           SCM spec = first ? top_system_spacing
 467                      : (last_system_was_title ? markup_markup_spacing : score_markup_spacing);
 468           Spring spring (0, 0);
 469           Real padding = 0.0;
 470           alter_spring_from_spacing_spec (spec, &spring);
 471           read_spacing_spec (spec, &padding, ly_symbol2scm ("padding"));
 472
 473           append_prob (p, spring, padding);
 474           last_system_was_title = true;
 475         }
 476       else
 477         programming_error ("got a system that was neither a Grob nor a Prob");
 478     }
 479
 480   Spring last_spring (0, 0);
 481   Real last_padding = 0;
 482   alter_spring_from_spacing_spec (last_bottom_spacing, &last_spring);
 483   read_spacing_spec (last_bottom_spacing, &last_padding, ly_symbol2scm ("padding"));
 484   last_spring.ensure_min_distance (last_padding - bottom_skyline_.max_height () + footer_height_);
 485   springs_.push_back (last_spring);
 486
 487   if (elements_.size ())
 488     {
 489       Real bottom_padding = 0;
 490
 491       // TODO: junk bottom-space now that we have last-bottom-spacing?
 492       // bottom-space has the flexibility that one can do it per-system.
 493       // NOTE: bottom-space is misnamed since it is not stretchable space.
 494       if (Prob *p = elements_.back ().prob)
 495         bottom_padding = robust_scm2double (p->get_property ("bottom-space"), 0);
 496       else if (elements_.back ().staves.size ())
 497         {
 498           SCM details = get_details (elements_.back ());
 499           bottom_padding = robust_scm2double (ly_assoc_get (ly_symbol2scm ("bottom-space"),
 500                                                             details,
 501                                                             SCM_BOOL_F),
 502                                               0.0);
 503         }
 504       page_height_ -= bottom_padding;
 505     }
 506 }
 507
 508 void
 509 Page_layout_problem::set_header_height (Real height)
 510 {
 511   header_height_ = height;
 512 }
 513
 514 void
 515 Page_layout_problem::set_footer_height (Real height)
 516 {
 517   footer_height_ = height;
 518 }
 519
 520 void
 521 Page_layout_problem::append_system (System *sys, Spring const &spring, Real indent, Real padding)
 522 {
 523   Grob *align = sys->get_vertical_alignment ();
 524   if (!align)
 525     return;
 526
 527   align->set_property ("positioning-done", SCM_BOOL_T);
 528
 529   extract_grob_set (align, "elements", all_elts);
 530   vector<Grob *> elts = filter_dead_elements (all_elts);
 531   vector<Real> minimum_offsets = Align_interface::get_minimum_translations_without_min_dist (align, elts, Y_AXIS);
 532   vector<Real> minimum_offsets_with_min_dist = Align_interface::get_minimum_translations (align, elts, Y_AXIS);
 533
 534   Skyline up_skyline (UP);
 535   Skyline down_skyline (DOWN);
 536   build_system_skyline (elts, minimum_offsets_with_min_dist, &up_skyline, &down_skyline);
 537   up_skyline.shift (indent);
 538   down_skyline.shift (indent);
 539   Stencil *in_note_stencil = unsmob_stencil (sys->get_property ("in-note-stencil"));
 540
 541   if (in_note_stencil && in_note_stencil->extent (Y_AXIS).length () > 0)
 542     {
 543       sys->set_property ("in-note-padding", scm_from_double (in_note_padding_));
 544       sys->set_property ("in-note-direction", scm_from_int (in_note_direction_));
 545       Skyline *sky = in_note_direction_ == UP ? &up_skyline : &down_skyline;
 546       sky->set_minimum_height (sky->max_height ()
 547                                + in_note_direction_
 548                                  * (in_note_padding_
 549                                     + in_note_stencil->extent (Y_AXIS).length ()));
 550     }
 551
 552   /*
 553     We need to call distance with skyline-horizontal-padding because
 554     the system skyline-horizontal-padding is not added during the creation
 555     of an individual staff.  So we add the padding for the distance check
 556     at the time of adding in the system.
 557   */
 558   Real minimum_distance = up_skyline.distance (bottom_skyline_,
 559                                                robust_scm2double (sys->get_property ("skyline-horizontal-padding"),
 560                                                                   0))
 561                           + padding;
 562
 563   Spring spring_copy = spring;
 564   spring_copy.ensure_min_distance (minimum_distance);
 565   springs_.push_back (spring_copy);
 566
 567   bottom_skyline_ = down_skyline;
 568   elements_.push_back (Element (elts, minimum_offsets, padding));
 569
 570   // Add the springs for the VerticalAxisGroups in this system.
 571
 572   // If the user has specified the offsets of the individual staves, fix the
 573   // springs at the given distances. Otherwise, use stretchable springs.
 574   SCM details = get_details (elements_.back ());
 575   SCM manual_dists = ly_assoc_get (ly_symbol2scm ("alignment-distances"), details, SCM_EOL);
 576   vsize last_spaceable_staff = 0;
 577   bool found_spaceable_staff = false;
 578   for (vsize i = 0; i < elts.size (); ++i)
 579     {
 580       if (is_spaceable (elts[i]))
 581         {
 582           // We don't add a spring for the first staff, since
 583           // we are only adding springs _between_ staves here.
 584           if (!found_spaceable_staff)
 585             {
 586               found_spaceable_staff = true;
 587               last_spaceable_staff = i;
 588               continue;
 589             }
 590
 591           Spring spring (0.5, 0.0);
 592           SCM spec = elts[last_spaceable_staff]->get_property ("staff-staff-spacing");
 593           alter_spring_from_spacing_spec (spec, &spring);
 594
 595           springs_.push_back (spring);
 596           Real min_distance = (found_spaceable_staff ? minimum_offsets_with_min_dist[last_spaceable_staff] : 0) - minimum_offsets_with_min_dist[i];
 597           springs_.back ().ensure_min_distance (min_distance);
 598
 599           if (scm_is_pair (manual_dists))
 600             {
 601               if (scm_is_number (scm_car (manual_dists)))
 602                 {
 603                   Real dy = scm_to_double (scm_car (manual_dists));
 604
 605                   springs_.back ().set_distance (dy);
 606                   springs_.back ().set_min_distance (dy);
 607                   springs_.back ().set_inverse_stretch_strength (0);
 608                 }
 609               manual_dists = scm_cdr (manual_dists);
 610             }
 611           last_spaceable_staff = i;
 612         }
 613     }
 614
 615   // Corner case: there was only one staff, and it wasn't spaceable.
 616   // Mark it spaceable, because we do not allow non-spaceable staves
 617   // to be at the top or bottom of a system.
 618   if (!found_spaceable_staff && elts.size ())
 619     mark_as_spaceable (elts[0]);
 620 }
 621
 622 void
 623 Page_layout_problem::append_prob (Prob *prob, Spring const &spring, Real padding)
 624 {
 625   Skyline_pair *sky = Skyline_pair::unsmob (prob->get_property ("vertical-skylines"));
 626   Real minimum_distance = 0;
 627   bool tight_spacing = to_boolean (prob->get_property ("tight-spacing"));
 628
 629   if (sky)
 630     {
 631       minimum_distance = (*sky)[UP].distance (bottom_skyline_);
 632       bottom_skyline_ = (*sky)[DOWN];
 633     }
 634   else if (Stencil *sten = unsmob_stencil (prob->get_property ("stencil")))
 635     {
 636       Interval iv = sten->extent (Y_AXIS);
 637       minimum_distance = iv[UP] - bottom_skyline_.max_height ();
 638
 639       bottom_skyline_.clear ();
 640       bottom_skyline_.set_minimum_height (iv[DOWN]);
 641     }
 642
 643   Spring spring_copy = spring;
 644   if (tight_spacing)
 645     {
 646       spring_copy.set_min_distance (minimum_distance);
 647       spring_copy.set_inverse_stretch_strength (0.0);
 648       spring_copy.set_distance (0.0);
 649     }
 650   else
 651     spring_copy.ensure_min_distance (minimum_distance + padding);
 652
 653   springs_.push_back (spring_copy);
 654   elements_.push_back (Element (prob, padding));
 655 }
 656
 657 void
 658 Page_layout_problem::solve_rod_spring_problem (bool ragged)
 659 {
 660   Simple_spacer spacer;
 661
 662   for (vsize i = 0; i < springs_.size (); ++i)
 663     spacer.add_spring (springs_[i]);
 664
 665   spacer.solve (page_height_, ragged);
 666   solution_ = spacer.spring_positions ();
 667
 668   if (!spacer.fits ())
 669     {
 670       Real overflow = spacer.configuration_length (spacer.force ())
 671                       - page_height_;
 672       if (ragged && overflow < 1e-6)
 673         warning (_ ("cannot fit music on page: ragged-spacing was requested, but page was compressed"));
 674       else
 675         {
 676           warning (_f ("cannot fit music on page: overflow is %f",
 677                        overflow));
 678           warning (_ ("compressing music to fit"));
 679           vsize space_count = solution_.size ();
 680           Real spacing_increment = overflow / (space_count - 2);
 681           for (vsize i = 2; i < space_count; i++)
 682             solution_[i] -= (i - 1) * spacing_increment;
 683         }
 684     }
 685 }
 686
 687 // The solution_ vector stores the position of every live VerticalAxisGroup
 688 // and every title. From that information,
 689 // 1) within each system, stretch the staves so they land at the right position
 690 // 2) find the offset of each system (relative to the printable area of the page).
 691 // TODO: this function is getting too long, maybe split it up?
 692 SCM
 693 Page_layout_problem::find_system_offsets ()
 694 {
 695   SCM system_offsets = SCM_EOL;
 696   SCM *tail = &system_offsets;
 697
 698   // spring_idx 0 is the top of the page. Interesting values start from 1.
 699   vsize spring_idx = 1;
 700   vector<Grob *> loose_lines;
 701   vector<Real> loose_line_min_distances;
 702   Grob *last_spaceable_line = 0;
 703   Real last_spaceable_line_translation = 0;
 704   Interval last_title_extent;
 705   for (vsize i = 0; i < elements_.size (); ++i)
 706     {
 707       if (elements_[i].prob)
 708         {
 709           *tail = scm_cons (scm_from_double (solution_[spring_idx]), SCM_EOL);
 710           tail = SCM_CDRLOC (*tail);
 711           Interval prob_extent = unsmob_stencil (elements_[i].prob->get_property ("stencil"))->extent (Y_AXIS);
 712
 713           // Lay out any non-spaceable lines between this line and
 714           // the last one.
 715           if (loose_lines.size ())
 716             {
 717               Interval loose_extent = loose_lines.back ()->extent (loose_lines.back (), Y_AXIS);
 718               Real min_distance = (-loose_extent[DOWN] + prob_extent[UP]
 719                                    + elements_[i].padding);
 720
 721               loose_line_min_distances.push_back (min_distance);
 722               loose_lines.push_back (0);
 723
 724               distribute_loose_lines (loose_lines, loose_line_min_distances,
 725                                       last_spaceable_line_translation, -solution_[spring_idx]);
 726               loose_lines.clear ();
 727               loose_line_min_distances.clear ();
 728             }
 729
 730           last_spaceable_line = 0;
 731           last_spaceable_line_translation = -solution_[spring_idx];
 732           last_title_extent = prob_extent;
 733           spring_idx++;
 734         }
 735       else
 736         {
 737           // Getting this signs right here is a little tricky. The configuration
 738           // we return has zero at the top of the page and positive numbers further
 739           // down, as does the solution_ vector.  Within a staff, however, positive
 740           // numbers are up.
 741           // TODO: perhaps change the way the page 'configuration variable works so
 742           // that it is consistent with the usual up/down sign conventions in
 743           // Lilypond. Then this would be less confusing.
 744
 745           // These two positions are relative to the page (with positive numbers being
 746           // down).
 747           Real first_staff_position = solution_[spring_idx];
 748           Real first_staff_min_translation = elements_[i].min_offsets.size () ? elements_[i].min_offsets[0] : 0;
 749           Real system_position = first_staff_position + first_staff_min_translation;
 750
 751           // Position the staves within this system.
 752           vector<Real> const &min_offsets = elements_[i].min_offsets;
 753           bool found_spaceable_staff = false;
 754           for (vsize staff_idx = 0; staff_idx < elements_[i].staves.size (); ++staff_idx)
 755             {
 756               Grob *staff = elements_[i].staves[staff_idx];
 757               staff->set_property ("system-Y-offset", scm_from_double (-system_position));
 758
 759               if (is_spaceable (staff))
 760                 {
 761                   // this is relative to the system: negative numbers are down.
 762                   staff->translate_axis (system_position - solution_[spring_idx], Y_AXIS);
 763
 764                   // Lay out any non-spaceable lines between this line and
 765                   // the last one.
 766                   if (loose_lines.size ())
 767                     {
 768                       if (staff_idx)
 769                         loose_line_min_distances.push_back (min_offsets[staff_idx - 1] - min_offsets[staff_idx]);
 770                       else
 771                         loose_line_min_distances.push_back (elements_[i].padding - min_offsets[staff_idx]);
 772                       loose_lines.push_back (staff);
 773
 774                       distribute_loose_lines (loose_lines, loose_line_min_distances,
 775                                               last_spaceable_line_translation, -solution_[spring_idx]);
 776                       loose_lines.clear ();
 777                       loose_line_min_distances.clear ();
 778                     }
 779                   last_spaceable_line = staff;
 780                   last_spaceable_line_translation = -solution_[spring_idx];
 781                   found_spaceable_staff = true;
 782                   spring_idx++;
 783                 }
 784               else
 785                 {
 786                   if (loose_lines.empty ())
 787                     loose_lines.push_back (last_spaceable_line);
 788
 789                   if (staff_idx)
 790                     // NOTE: the way we do distances between loose lines (and other lines too, actually)
 791                     // is not the most accurate way possible: we only insert rods between adjacent
 792                     // lines.  To be more accurate, we could insert rods between non-adjacent lines
 793                     // using a scheme similar to the one in set_column_rods.
 794                     loose_line_min_distances.push_back (min_offsets[staff_idx - 1] - min_offsets[staff_idx]);
 795                   else
 796                     {
 797                       // this is the first line in a system
 798                       Real min_dist = 0;
 799                       if (loose_lines.back ())
 800                         // distance to the final line in the preceding system,
 801                         // including 'system-system-spacing 'padding
 802                         min_dist = (Axis_group_interface::minimum_distance (loose_lines.back (),
 803                                                                             staff,
 804                                                                             Y_AXIS)
 805                                     + elements_[i].padding);
 806                       else if (!last_title_extent.is_empty ())
 807                         // distance to the preceding title,
 808                         //  including 'markup-system-spacing 'padding
 809                         min_dist = (staff->extent (staff, Y_AXIS)[UP] - last_title_extent[DOWN]
 810                                     + elements_[i].padding);
 811                       else // distance to the top margin
 812                         min_dist = header_padding_ + header_height_ + staff->extent (staff, Y_AXIS)[UP];
 813
 814                       loose_line_min_distances.push_back (min_dist);
 815                     }
 816                   loose_lines.push_back (staff);
 817                 }
 818             }
 819
 820           // Corner case: even if a system has no live staves, it still takes up
 821           // one spring (a system with one live staff also takes up one spring),
 822           // which we need to increment past.
 823           if (!found_spaceable_staff)
 824             spring_idx++;
 825
 826           *tail = scm_cons (scm_from_double (system_position), SCM_EOL);
 827           tail = SCM_CDRLOC (*tail);
 828         }
 829     }
 830
 831   if (loose_lines.size ())
 832     {
 833       Grob *last = loose_lines.back ();
 834       Interval last_ext = last->extent (last, Y_AXIS);
 835       loose_line_min_distances.push_back (-last_ext[DOWN] + footer_height_ + footer_padding_);
 836       loose_lines.push_back (0);
 837
 838       distribute_loose_lines (loose_lines, loose_line_min_distances,
 839                               last_spaceable_line_translation, -page_height_);
 840
 841     }
 842
 843   assert (spring_idx == solution_.size () - 1);
 844   return system_offsets;
 845 }
 846
 847 // Given two lines that are already spaced (the first and last
 848 // elements of loose_lines), distribute some unspaced lines between
 849 // them.
 850 // first_translation and last_translation are relative to the page.
 851 void
 852 Page_layout_problem::distribute_loose_lines (vector<Grob *> const &loose_lines,
 853                                              vector<Real> const &min_distances,
 854                                              Real first_translation, Real last_translation)
 855 {
 856   Simple_spacer spacer;
 857   for (vsize i = 0; i + 1 < loose_lines.size (); ++i)
 858     {
 859       SCM spec = get_spacing_spec (loose_lines[i], loose_lines[i + 1], false, 0, INT_MAX);
 860       Spring spring (1.0, 0.0);
 861       alter_spring_from_spacing_spec (spec, &spring);
 862       spring.ensure_min_distance (min_distances[i]);
 863       spacer.add_spring (spring);
 864     }
 865
 866   // Remember: offsets are decreasing, since we're going from UP to DOWN!
 867   spacer.solve (first_translation - last_translation, false);
 868
 869   vector<Real> solution = spacer.spring_positions ();
 870   for (vsize i = 1; i + 1 < solution.size (); ++i)
 871     {
 872       Real system_offset = scm_to_double (loose_lines[i]->get_property ("system-Y-offset"));
 873       loose_lines[i]->translate_axis (first_translation - solution[i] - system_offset, Y_AXIS);
 874     }
 875 }
 876
 877 SCM
 878 Page_layout_problem::solution (bool ragged)
 879 {
 880   solve_rod_spring_problem (ragged);
 881   return find_system_offsets ();
 882 }
 883
 884 // Build upper and lower skylines for a system. We don't yet know the positions
 885 // of the staves within the system, so we make the skyline as conservative as
 886 // possible. That is, for the upper skyline, we pretend that all of the staves
 887 // in the system are packed together close to the top system; for the lower
 888 // skyline, we pretend that all of the staves are packed together close to
 889 // the bottom system.
 890 //
 891 // The upper skyline is relative to the top staff; the lower skyline is relative to
 892 // the bottom staff.
 893 void
 894 Page_layout_problem::build_system_skyline (vector<Grob *> const &staves,
 895                                            vector<Real> const &minimum_translations,
 896                                            Skyline *up,
 897                                            Skyline *down)
 898 {
 899   if (minimum_translations.empty ())
 900     return;
 901
 902   assert (staves.size () == minimum_translations.size ());
 903   Real first_translation = minimum_translations[0];
 904   Real last_spaceable_dy = 0;
 905   Real first_spaceable_dy = 0;
 906   bool found_spaceable_staff = false;
 907
 908   for (vsize i = 0; i < staves.size (); ++i)
 909     {
 910       Real dy = minimum_translations[i] - first_translation;
 911       Grob *g = staves[i];
 912       Skyline_pair *sky = Skyline_pair::unsmob (g->get_property ("vertical-skylines"));
 913       if (sky)
 914         {
 915           up->raise (-dy);
 916           up->merge ((*sky)[UP]);
 917           up->raise (dy);
 918
 919           down->raise (-dy);
 920           down->merge ((*sky)[DOWN]);
 921           down->raise (dy);
 922         }
 923       if (is_spaceable (staves[i]))
 924         {
 925           if (!found_spaceable_staff)
 926             {
 927               found_spaceable_staff = true;
 928               first_spaceable_dy = dy;
 929             }
 930           last_spaceable_dy = dy;
 931         }
 932     }
 933
 934   // Leave the up skyline at a position relative
 935   // to the top spaceable staff.
 936   up->raise (-first_spaceable_dy);
 937
 938   // Leave the down skyline at a position
 939   // relative to the bottom spaceable staff.
 940   down->raise (-last_spaceable_dy);
 941 }
 942
 943 Interval
 944 Page_layout_problem::prob_extent (Prob *p)
 945 {
 946   Stencil *sten = unsmob_stencil (p->get_property ("stencil"));
 947   return sten ? sten->extent (Y_AXIS) : Interval (0, 0);
 948 }
 949
 950 Interval
 951 Page_layout_problem::first_staff_extent (Element const &e)
 952 {
 953   if (e.prob)
 954     return prob_extent (e.prob);
 955   else if (e.staves.size ())
 956     return e.staves[0]->extent (e.staves[0], Y_AXIS);
 957
 958   return Interval (0, 0);
 959 }
 960
 961 Interval
 962 Page_layout_problem::last_staff_extent (Element const &e)
 963 {
 964   if (e.prob)
 965     return prob_extent (e.prob);
 966   else if (e.staves.size ())
 967     return e.staves.back ()->extent (e.staves.back (), Y_AXIS);
 968
 969   return Interval (0, 0);
 970 }
 971
 972 SCM
 973 Page_layout_problem::get_details (Element const &elt)
 974 {
 975   if (elt.staves.empty ())
 976     return SCM_EOL;
 977
 978   return get_details (elt.staves.back ()->get_system ());
 979 }
 980
 981 SCM
 982 Page_layout_problem::get_details (Grob *g)
 983 {
 984   Grob *left_bound = dynamic_cast<Spanner *> (g)->get_bound (LEFT);
 985   return left_bound->get_property ("line-break-system-details");
 986 }
 987
 988 bool
 989 Page_layout_problem::is_spaceable (Grob *g)
 990 {
 991   return !scm_is_number (g->get_property ("staff-affinity"));
 992 }
 993
 994 void
 995 Page_layout_problem::mark_as_spaceable (Grob *g)
 996 {
 997   g->set_property ("staff-affinity", SCM_BOOL_F);
 998 }
 999
1000 bool
1001 Page_layout_problem::read_spacing_spec (SCM spec, Real *dest, SCM sym)
1002 {
1003   SCM pair = scm_sloppy_assq (sym, spec);
1004   if (scm_is_pair (pair) && scm_is_number (scm_cdr (pair)))
1005     {
1006       *dest = scm_to_double (scm_cdr (pair));
1007       return true;
1008     }
1009   return false;
1010 }
1011
1012 // If there is a forced, fixed spacing between BEFORE and AFTER, return it.
1013 // Otherwise, return -infinity_f.
1014 // If after is spaceable, it is the (spaceable_index + 1)th spaceable grob in
1015 // its alignment.
1016 Real
1017 Page_layout_problem::get_fixed_spacing (Grob *before, Grob *after, int spaceable_index, bool pure, int start, int end)
1018 {
1019   Spanner *after_sp = dynamic_cast<Spanner *> (after);
1020   SCM cache_symbol = (is_spaceable (before) && is_spaceable (after))
1021                      ? ly_symbol2scm ("spaceable-fixed-spacing")
1022                      : ly_symbol2scm ("loose-fixed-spacing");
1023   if (pure)
1024     {
1025       // The result of this function doesn't depend on "end," so we can reduce the
1026       // size of the cache by ignoring it.
1027       SCM cached = after_sp->get_cached_pure_property (cache_symbol, start, 0);
1028       if (scm_is_number (cached))
1029         return robust_scm2double (cached, 0.0);
1030     }
1031
1032   Real ret = -infinity_f;
1033
1034   // If we're pure, then paper-columns have not had their systems set,
1035   // and so elts[i]->get_system () is unreliable.
1036   System *sys = pure ? Grob::get_system (before) : before->get_system ();
1037   Grob *left_bound = sys ? sys->get_maybe_pure_bound (LEFT, pure, start, end) : 0;
1038
1039   if (is_spaceable (before) && is_spaceable (after) && left_bound)
1040     {
1041       SCM details = left_bound->get_property ("line-break-system-details");
1042       SCM manual_dists = ly_assoc_get (ly_symbol2scm ("alignment-distances"), details, SCM_EOL);
1043       if (scm_is_pair (manual_dists))
1044         {
1045           SCM forced = robust_list_ref (spaceable_index - 1, manual_dists);
1046           if (scm_is_number (forced))
1047             ret = max (ret, scm_to_double (forced));
1048         }
1049     }
1050
1051   // Cache the result.  As above, we ignore "end."
1052   if (pure)
1053     after_sp->cache_pure_property (cache_symbol, start, 0, scm_from_double (ret));
1054
1055   return ret;
1056 }
1057
1058 static SCM
1059 add_stretchability (SCM alist, Real stretch)
1060 {
1061   if (!scm_is_pair (scm_sloppy_assq (ly_symbol2scm ("stretchability"), alist)))
1062     return scm_acons (ly_symbol2scm ("stretchability"), scm_from_double (stretch), alist);
1063
1064   return alist;
1065 }
1066
1067 // We want to put a large stretch between a non-spaceable line and its
1068 // non-affinity staff. We want to put an even larger stretch between
1069 // a non-spaceable line and the top/bottom of the page. That way,
1070 // a spacing-affinity UP line at the bottom of the page will still be
1071 // placed close to its staff.
1072 const double LARGE_STRETCH = 10e5;
1073 const double HUGE_STRETCH = 10e7;
1074
1075 // Returns the spacing spec connecting BEFORE to AFTER.
1076 SCM
1077 Page_layout_problem::get_spacing_spec (Grob *before, Grob *after, bool pure, int start, int end)
1078 {
1079   // If there are no spacing wishes, return a very flexible spring.
1080   // This will occur, for example, if there are lyrics at the bottom of
1081   // the page, in which case we don't want the spring from the lyrics to
1082   // the bottom of the page to have much effect.
1083   if (!before || !after)
1084     return add_stretchability (SCM_EOL, HUGE_STRETCH);
1085
1086   if (is_spaceable (before))
1087     {
1088       if (is_spaceable (after))
1089         return before->get_maybe_pure_property ("staff-staff-spacing", pure, start, end);
1090       else
1091         {
1092           Direction affinity = to_dir (after->get_maybe_pure_property ("staff-affinity", pure, start, end));
1093           return (affinity == DOWN)
1094                  ? add_stretchability (after->get_maybe_pure_property ("nonstaff-unrelatedstaff-spacing", pure, start, end),
1095                                        LARGE_STRETCH)
1096                  : after->get_maybe_pure_property ("nonstaff-relatedstaff-spacing", pure, start, end);
1097         }
1098     }
1099   else
1100     {
1101       if (is_spaceable (after))
1102         {
1103           Direction affinity = to_dir (before->get_maybe_pure_property ("staff-affinity", pure, start, end));
1104           return (affinity == UP)
1105                  ? add_stretchability (before->get_maybe_pure_property ("nonstaff-unrelatedstaff-spacing", pure, start, end),
1106                                        LARGE_STRETCH)
1107                  : before->get_maybe_pure_property ("nonstaff-relatedstaff-spacing", pure, start, end);
1108         }
1109       else
1110         {
1111           Direction before_affinity = to_dir (before->get_maybe_pure_property ("staff-affinity", pure, start, end));
1112           Direction after_affinity = to_dir (after->get_maybe_pure_property ("staff-affinity", pure, start, end));
1113           static bool warned = false;
1114           if (after_affinity > before_affinity
1115               && !warned && !pure)
1116             {
1117               warning (_ ("staff-affinities should only decrease"));
1118               warned = true;
1119             }
1120           if (before_affinity != UP)
1121             return before->get_maybe_pure_property ("nonstaff-nonstaff-spacing", pure, start, end);
1122           else if (after_affinity != DOWN)
1123             return before->get_maybe_pure_property ("nonstaff-nonstaff-spacing", pure, start, end);
1124           return add_stretchability (before->get_maybe_pure_property ("nonstaff-unrelatedstaff-spacing", pure, start, end),
1125                                      LARGE_STRETCH);
1126         }
1127     }
1128
1129   assert (0);
1130   return SCM_BOOL_F;
1131 }
1132
1133 void
1134 Page_layout_problem::alter_spring_from_spacing_spec (SCM spec, Spring *spring)
1135 {
1136   Real space;
1137   Real stretch;
1138   Real min_dist;
1139   if (read_spacing_spec (spec, &space, ly_symbol2scm ("basic-distance")))
1140     spring->set_distance (space);
1141   if (read_spacing_spec (spec, &min_dist, ly_symbol2scm ("minimum-distance")))
1142     spring->set_min_distance (min_dist);
1143   spring->set_default_strength ();
1144
1145   if (read_spacing_spec (spec, &stretch, ly_symbol2scm ("stretchability")))
1146     spring->set_inverse_stretch_strength (stretch);
1147 }
1148
1149 vector<Grob *>
1150 Page_layout_problem::filter_dead_elements (vector<Grob *> const &input)
1151 {
1152   vector<Grob *> output;
1153   for (vsize i = 0; i < input.size (); ++i)
1154     {
1155       if (Hara_kiri_group_spanner::has_interface (input[i]))
1156         Hara_kiri_group_spanner::consider_suicide (input[i]);
1157
1158       if (input[i]->is_live ())
1159         output.push_back (input[i]);
1160     }
1161
1162   return output;
1163 }