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