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 a stencil for the footnote of each system.  This stencil may
  39    itself be comprised of several footnotes.
  40 */
  41
  42 SCM
  43 Page_layout_problem::get_footnotes_from_lines (SCM lines, Real padding)
  44 {
  45   SCM footnotes = SCM_EOL;
  46   // ugh...code dup from the Page_layout_problem constructor
  47   for (SCM s = lines; scm_is_pair (s); s = scm_cdr (s))
  48     {
  49       if (Grob *g = unsmob_grob (scm_car (s)))
  50         {
  51           System *sys = dynamic_cast<System *> (g);
  52           if (!sys)
  53             {
  54               programming_error ("got a grob for footnotes that wasn't a System");
  55               continue;
  56             }
  57           footnotes = scm_cons (sys->make_footnote_stencil (padding).smobbed_copy (), footnotes);
  58         }
  59       else if (Prob *p = unsmob_prob (scm_car (s)))
  60         {
  61           SCM stencils = p->get_property ("footnotes");
  62           if (stencils == SCM_EOL)
  63             continue;
  64           Stencil footnote_stencil;
  65
  66           for (SCM st = stencils; scm_is_pair (st); st = scm_cdr (st))
  67             footnote_stencil.add_at_edge (Y_AXIS, DOWN, *unsmob_stencil (scm_car (st)), padding);
  68           footnotes = scm_cons (footnote_stencil.smobbed_copy (), footnotes);
  69         }
  70     }
  71
  72   if (!scm_is_pair (footnotes))
  73     return SCM_EOL;
  74
  75   return scm_reverse (footnotes);
  76 }
  77
  78 Stencil*
  79 Page_layout_problem::get_footnote_separator_stencil (Output_def *paper)
  80 {
  81   SCM props = scm_call_1 (ly_lily_module_constant ("layout-extract-page-properties"),
  82                           paper->self_scm ());
  83
  84   SCM markup = paper->c_variable ("footnote-separator-markup");
  85
  86   if (!Text_interface::is_markup (markup))
  87     return NULL;
  88
  89   SCM footnote_stencil = Text_interface::interpret_markup (paper->self_scm (),
  90                                                            props, markup);
  91
  92   Stencil *footnote_separator = unsmob_stencil (footnote_stencil);
  93
  94   return footnote_separator;
  95 }
  96
  97 void
  98 Page_layout_problem::add_footnotes_to_footer (SCM footnotes, Stencil *foot, Paper_book *pb)
  99 {
 100   bool footnotes_found = false;
 101   Real footnote_padding = robust_scm2double (pb->paper_->c_variable ("footnote-padding"), 0.0);
 102
 103   footnotes = scm_reverse (footnotes);
 104   for (SCM s = footnotes; scm_is_pair (s); s = scm_cdr (s))
 105     {
 106       Stencil *stencil = unsmob_stencil (scm_car (s));
 107
 108       if (!stencil)
 109         continue;
 110
 111       if (!stencil->is_empty ())
 112         {
 113           foot->add_at_edge (Y_AXIS, UP, *stencil, footnote_padding);
 114           footnotes_found = true;
 115         }
 116     }
 117
 118   if (footnotes_found)
 119     {
 120       Stencil *separator = get_footnote_separator_stencil (pb->paper_);
 121       if (separator)
 122         foot->add_at_edge (Y_AXIS, UP, *separator, footnote_padding);
 123     }
 124 }
 125
 126 Page_layout_problem::Page_layout_problem (Paper_book *pb, SCM page_scm, SCM systems)
 127   : bottom_skyline_ (DOWN)
 128 {
 129   Prob *page = unsmob_prob (page_scm);
 130   header_height_ = 0;
 131   footer_height_ = 0;
 132   header_padding_ = 0;
 133   footer_padding_ = 0;
 134   page_height_ = 100;
 135
 136   if (page)
 137     {
 138       Stencil *head = unsmob_stencil (page->get_property ("head-stencil"));
 139       Stencil *foot = unsmob_stencil (page->get_property ("foot-stencil"));
 140
 141       Real footnote_padding = 0.0;
 142       if (pb && pb->paper_)
 143         footnote_padding = robust_scm2double (pb->paper_->c_variable ("footnote-padding"), 0.0);
 144       SCM footnotes = get_footnotes_from_lines (systems, footnote_padding);
 145       add_footnotes_to_footer (footnotes, foot, pb);
 146
 147       header_height_ = head ? head->extent (Y_AXIS).length () : 0;
 148       footer_height_ = foot ? foot->extent (Y_AXIS).length () : 0;
 149       page_height_ = robust_scm2double (page->get_property ("paper-height"), 100);
 150     }
 151
 152   // Initially, bottom_skyline_ represents the top of the page. Make
 153   // it solid, so that the top of the first system will be forced
 154   // below the top of the printable area.
 155   bottom_skyline_.set_minimum_height (-header_height_);
 156
 157   SCM system_system_spacing = SCM_EOL;
 158   SCM score_system_spacing = SCM_EOL;
 159   SCM markup_system_spacing = SCM_EOL;
 160   SCM score_markup_spacing = SCM_EOL;
 161   SCM markup_markup_spacing = SCM_EOL;
 162
 163   // top_system_spacing controls the spring from the top of the printable
 164   // area to the first staff. It allows the user to control the offset of
 165   // the first staff (as opposed to the top of the first system) from the
 166   // top of the page. Similarly for last_bottom_spacing.
 167   SCM top_system_spacing = SCM_EOL;
 168   SCM last_bottom_spacing = SCM_EOL;
 169   if (pb && pb->paper_)
 170     {
 171       Output_def *paper = pb->paper_;
 172       system_system_spacing = paper->c_variable ("system-system-spacing");
 173       score_system_spacing = paper->c_variable ("score-system-spacing");
 174       markup_system_spacing = paper->c_variable ("markup-system-spacing");
 175       score_markup_spacing = paper->c_variable ("score-markup-spacing");
 176       markup_markup_spacing = paper->c_variable ("markup-markup-spacing");
 177       last_bottom_spacing = paper->c_variable ("last-bottom-spacing");
 178       top_system_spacing = paper->c_variable ("top-system-spacing");
 179       if (scm_is_pair (systems) && unsmob_prob (scm_car (systems)))
 180         top_system_spacing = paper->c_variable ("top-markup-spacing");
 181
 182       // Note: the page height here does _not_ reserve space for headers and
 183       // footers. This is because we want to anchor the top-system-spacing
 184       // spring at the _top_ of the header.
 185       page_height_ -= robust_scm2double (paper->c_variable ("top-margin"), 0)
 186         + robust_scm2double (paper->c_variable ("bottom-margin"), 0);
 187
 188       read_spacing_spec (top_system_spacing, &header_padding_, ly_symbol2scm ("padding"));
 189       read_spacing_spec (last_bottom_spacing, &footer_padding_, ly_symbol2scm ("padding"));
 190     }
 191   bool last_system_was_title = false;
 192
 193
 194   for (SCM s = systems; scm_is_pair (s); s = scm_cdr (s))
 195     {
 196       bool first = (s == systems);
 197
 198       if (Grob *g = unsmob_grob (scm_car (s)))
 199         {
 200           System *sys = dynamic_cast<System*> (g);
 201           if (!sys)
 202             {
 203               programming_error ("got a grob for vertical spacing that wasn't a System");
 204               continue;
 205             }
 206
 207           SCM spec = system_system_spacing;
 208           if (first)
 209             spec = top_system_spacing;
 210           else if (last_system_was_title)
 211             spec = markup_system_spacing;
 212           else if (0 == Paper_column::get_rank (sys->get_bound (LEFT)))
 213             spec = score_system_spacing;
 214
 215           Spring spring (0, 0);
 216           Real padding = 0.0;
 217           Real indent = line_dimensions_int (sys->paper_score ()->layout (), sys->get_rank ())[LEFT];
 218           alter_spring_from_spacing_spec (spec, &spring);
 219           read_spacing_spec (spec, &padding, ly_symbol2scm ("padding"));
 220
 221           append_system (sys, spring, indent, padding);
 222           last_system_was_title = false;
 223         }
 224       else if (Prob *p = unsmob_prob (scm_car (s)))
 225         {
 226           SCM spec = first ? top_system_spacing
 227             : (last_system_was_title ? markup_markup_spacing : score_markup_spacing);
 228           Spring spring (0, 0);
 229           Real padding = 0.0;
 230           alter_spring_from_spacing_spec (spec, &spring);
 231           read_spacing_spec (spec, &padding, ly_symbol2scm ("padding"));
 232
 233           append_prob (p, spring, padding);
 234           last_system_was_title = true;
 235         }
 236       else
 237         programming_error ("got a system that was neither a Grob nor a Prob");
 238     }
 239
 240   Spring last_spring (0, 0);
 241   Real last_padding = 0;
 242   alter_spring_from_spacing_spec (last_bottom_spacing, &last_spring);
 243   read_spacing_spec (last_bottom_spacing, &last_padding, ly_symbol2scm ("padding"));
 244   last_spring.ensure_min_distance (last_padding - bottom_skyline_.max_height () + footer_height_);
 245   springs_.push_back (last_spring);
 246
 247   if (elements_.size ())
 248     {
 249       Real bottom_padding = 0;
 250
 251       // TODO: junk bottom-space now that we have last-bottom-spacing?
 252       // bottom-space has the flexibility that one can do it per-system.
 253       // NOTE: bottom-space is misnamed since it is not stretchable space.
 254       if (Prob *p = elements_.back ().prob)
 255         bottom_padding = robust_scm2double (p->get_property ("bottom-space"), 0);
 256       else if (elements_.back ().staves.size ())
 257         {
 258           SCM details = get_details (elements_.back ());
 259           bottom_padding = robust_scm2double (ly_assoc_get (ly_symbol2scm ("bottom-space"),
 260                                                             details,
 261                                                             SCM_BOOL_F),
 262                                               0.0);
 263         }
 264       page_height_ -= bottom_padding;
 265     }
 266 }
 267
 268 void
 269 Page_layout_problem::set_header_height (Real height)
 270 {
 271   header_height_ = height;
 272 }
 273
 274 void
 275 Page_layout_problem::set_footer_height (Real height)
 276 {
 277   footer_height_ = height;
 278 }
 279
 280 void
 281 Page_layout_problem::append_system (System *sys, Spring const& spring, Real indent, Real padding)
 282 {
 283   Grob *align = sys->get_vertical_alignment ();
 284   if (!align)
 285     return;
 286
 287   align->set_property ("positioning-done", SCM_BOOL_T);
 288
 289   extract_grob_set (align, "elements", all_elts);
 290   vector<Grob*> elts = filter_dead_elements (all_elts);
 291   vector<Real> minimum_offsets = Align_interface::get_minimum_translations_without_min_dist (align, elts, Y_AXIS);
 292   vector<Real> minimum_offsets_with_min_dist = Align_interface::get_minimum_translations (align, elts, Y_AXIS);
 293
 294   Skyline up_skyline (UP);
 295   Skyline down_skyline (DOWN);
 296   build_system_skyline (elts, minimum_offsets_with_min_dist, &up_skyline, &down_skyline);
 297   up_skyline.shift (indent);
 298   down_skyline.shift (indent);
 299
 300   /*
 301     We need to call distance with skyline-horizontal-padding because
 302     the system skyline-horizontal-padding is not added during the creation
 303     of an individual staff.  So we add the padding for the distance check
 304     at the time of adding in the system.
 305   */
 306   Real minimum_distance = up_skyline.distance (bottom_skyline_, robust_scm2double (sys->get_property ("skyline-horizontal-padding"), 0)) + padding;
 307
 308   Spring spring_copy = spring;
 309   spring_copy.ensure_min_distance (minimum_distance);
 310   springs_.push_back (spring_copy);
 311
 312   bottom_skyline_ = down_skyline;
 313   elements_.push_back (Element (elts, minimum_offsets));
 314
 315   // Add the springs for the VerticalAxisGroups in this system.
 316
 317   // If the user has specified the offsets of the individual staves, fix the
 318   // springs at the given distances. Otherwise, use stretchable springs.
 319   SCM details = get_details (elements_.back ());
 320   SCM manual_dists = ly_assoc_get (ly_symbol2scm ("alignment-distances"), details, SCM_EOL);
 321   vsize last_spaceable_staff = 0;
 322   bool found_spaceable_staff = false;
 323   for (vsize i = 0; i < elts.size (); ++i)
 324     {
 325       if (is_spaceable (elts[i]))
 326         {
 327           // We don't add a spring for the first staff, since
 328           // we are only adding springs _between_ staves here.
 329           if (!found_spaceable_staff)
 330             {
 331               found_spaceable_staff = true;
 332               last_spaceable_staff = i;
 333               continue;
 334             }
 335
 336           Spring spring (0.5, 0.0);
 337           SCM spec = elts[last_spaceable_staff]->get_property ("staff-staff-spacing");
 338           alter_spring_from_spacing_spec (spec, &spring);
 339
 340           springs_.push_back (spring);
 341           Real min_distance = (found_spaceable_staff ? minimum_offsets[last_spaceable_staff] : 0) - minimum_offsets[i];
 342           springs_.back ().ensure_min_distance (min_distance);
 343
 344           if (scm_is_pair (manual_dists))
 345             {
 346               if (scm_is_number (scm_car (manual_dists)))
 347                 {
 348                   Real dy = scm_to_double (scm_car (manual_dists));
 349
 350                   springs_.back ().set_distance (dy);
 351                   springs_.back ().set_min_distance (dy);
 352                   springs_.back ().set_inverse_stretch_strength (0);
 353                 }
 354               manual_dists = scm_cdr (manual_dists);
 355             }
 356           last_spaceable_staff = i;
 357         }
 358     }
 359
 360   // Corner case: there was only one staff, and it wasn't spaceable.
 361   // Mark it spaceable, because we do not allow non-spaceable staves
 362   // to be at the top or bottom of a system.
 363   if (!found_spaceable_staff && elts.size ())
 364     mark_as_spaceable (elts[0]);
 365 }
 366
 367 void
 368 Page_layout_problem::append_prob (Prob *prob, Spring const& spring, Real padding)
 369 {
 370   Skyline_pair *sky = Skyline_pair::unsmob (prob->get_property ("vertical-skylines"));
 371   Real minimum_distance = 0;
 372   bool tight_spacing = to_boolean (prob->get_property ("tight-spacing"));
 373
 374   if (sky)
 375     {
 376       minimum_distance = (*sky)[UP].distance (bottom_skyline_);
 377       bottom_skyline_ = (*sky)[DOWN];
 378     }
 379   else if (Stencil *sten = unsmob_stencil (prob->get_property ("stencil")))
 380     {
 381       Interval iv = sten->extent (Y_AXIS);
 382       minimum_distance = iv[UP] - bottom_skyline_.max_height ();
 383
 384       bottom_skyline_.clear ();
 385       bottom_skyline_.set_minimum_height (iv[DOWN]);
 386     }
 387
 388   Spring spring_copy = spring;
 389   if (tight_spacing)
 390     {
 391       spring_copy.set_min_distance (minimum_distance);
 392       spring_copy.set_inverse_stretch_strength (0.0);
 393       spring_copy.set_distance (0.0);
 394     }
 395   else
 396     spring_copy.ensure_min_distance (minimum_distance + padding);
 397
 398   springs_.push_back (spring_copy);
 399   elements_.push_back (Element (prob));
 400 }
 401
 402 void
 403 Page_layout_problem::solve_rod_spring_problem (bool ragged)
 404 {
 405   Simple_spacer spacer;
 406
 407   for (vsize i = 0; i < springs_.size (); ++i)
 408     spacer.add_spring (springs_[i]);
 409
 410   spacer.solve (page_height_, ragged);
 411   solution_ = spacer.spring_positions ();
 412
 413   if (!spacer.fits ())
 414     {
 415       Real overflow = spacer.configuration_length (spacer.force ())
 416                       - page_height_;
 417       if (ragged && overflow < 1e-6)
 418         warning (_ ("cannot fit music on page: ragged-spacing was requested, but page was compressed"));
 419       else
 420         {
 421           warning (_f ("cannot fit music on page: overflow is %f",
 422                        overflow));
 423           warning (_ ("compressing music to fit"));
 424           vsize space_count = solution_.size ();
 425           Real spacing_increment = overflow / (space_count - 2);
 426           for (vsize i = 2; i < space_count; i++)
 427             solution_[i] -= (i-1) * spacing_increment;
 428         }
 429     }
 430 }
 431
 432 // The solution_ vector stores the position of every live VerticalAxisGroup
 433 // and every title. From that information,
 434 // 1) within each system, stretch the staves so they land at the right position
 435 // 2) find the offset of each system (relative to the printable area of the page).
 436 // TODO: this function is getting too long, maybe split it up?
 437 SCM
 438 Page_layout_problem::find_system_offsets ()
 439 {
 440   SCM system_offsets = SCM_EOL;
 441   SCM *tail = &system_offsets;
 442
 443   // spring_idx 0 is the top of the page. Interesting values start from 1.
 444   vsize spring_idx = 1;
 445   vector<Grob*> loose_lines;
 446   vector<Real> loose_line_min_distances;
 447   Grob *last_spaceable_line = 0;
 448   Real last_spaceable_line_translation = 0;
 449   Interval last_title_extent;
 450   for (vsize i = 0; i < elements_.size (); ++i)
 451     {
 452       if (elements_[i].prob)
 453         {
 454           *tail = scm_cons (scm_from_double (solution_[spring_idx]), SCM_EOL);
 455           tail = SCM_CDRLOC (*tail);
 456           Interval prob_extent = unsmob_stencil (elements_[i].prob->get_property ("stencil"))->extent (Y_AXIS);
 457
 458           // Lay out any non-spaceable lines between this line and
 459           // the last one.
 460           if (loose_lines.size ())
 461             {
 462               Interval loose_extent = loose_lines.back ()->extent (loose_lines.back (), Y_AXIS);
 463               Real min_distance = -loose_extent[DOWN] + prob_extent[UP]; // TODO: include padding/minimum-distance
 464
 465               loose_line_min_distances.push_back (min_distance);
 466               loose_lines.push_back (0);
 467
 468               distribute_loose_lines (loose_lines, loose_line_min_distances,
 469                                       last_spaceable_line_translation, -solution_[spring_idx]);
 470               loose_lines.clear ();
 471               loose_line_min_distances.clear ();
 472             }
 473
 474           last_spaceable_line = 0;
 475           last_spaceable_line_translation = -solution_[spring_idx];
 476           last_title_extent = prob_extent;
 477           spring_idx++;
 478         }
 479       else
 480         {
 481           // Getting this signs right here is a little tricky. The configuration
 482           // we return has zero at the top of the page and positive numbers further
 483           // down, as does the solution_ vector.  Within a staff, however, positive
 484           // numbers are up.
 485           // TODO: perhaps change the way the page 'configuration variable works so
 486           // that it is consistent with the usual up/down sign conventions in
 487           // Lilypond. Then this would be less confusing.
 488
 489           // These two positions are relative to the page (with positive numbers being
 490           // down).
 491           Real first_staff_position = solution_[spring_idx];
 492           Real first_staff_min_translation = elements_[i].min_offsets.size () ? elements_[i].min_offsets[0] : 0;
 493           Real system_position = first_staff_position + first_staff_min_translation;
 494
 495           // Position the staves within this system.
 496           Real translation = 0;
 497           vector<Real> const& min_offsets = elements_[i].min_offsets;
 498           bool found_spaceable_staff = false;
 499           for (vsize staff_idx = 0; staff_idx < elements_[i].staves.size (); ++staff_idx)
 500             {
 501               Grob *staff = elements_[i].staves[staff_idx];
 502               staff->set_property ("system-Y-offset", scm_from_double (-system_position));
 503
 504               if (is_spaceable (staff))
 505                 {
 506                   // this is relative to the system: negative numbers are down.
 507                   translation = system_position - solution_[spring_idx];
 508                   spring_idx++;
 509
 510                   // Lay out any non-spaceable lines between this line and
 511                   // the last one.
 512                   if (loose_lines.size ())
 513                     {
 514                       loose_line_min_distances.push_back (min_offsets[staff_idx-1] - min_offsets[staff_idx]);
 515                       loose_lines.push_back (staff);
 516
 517                       distribute_loose_lines (loose_lines, loose_line_min_distances,
 518                                               last_spaceable_line_translation, translation - system_position);
 519                       loose_lines.clear ();
 520                       loose_line_min_distances.clear ();
 521                     }
 522                   last_spaceable_line = staff;
 523                   // Negative is down but the translation is relative to the whole page.
 524                   last_spaceable_line_translation = -system_position + translation;
 525
 526                   staff->translate_axis (translation, Y_AXIS);
 527                   found_spaceable_staff = true;
 528                 }
 529               else
 530                 {
 531                   if (loose_lines.empty ())
 532                     loose_lines.push_back (last_spaceable_line);
 533
 534                   if (staff_idx)
 535                     loose_line_min_distances.push_back (min_offsets[staff_idx-1] - min_offsets[staff_idx]);
 536                   else
 537                     {
 538                       Real min_dist = 0;
 539                       if (loose_lines.back ())
 540                         min_dist = Axis_group_interface::minimum_distance (loose_lines.back (),
 541                                                                            staff,
 542                                                                            Y_AXIS);
 543                       else if (!last_title_extent.is_empty ())
 544                         { // distance to the preceding title
 545                           // TODO: add options for controlling the space between a loose line
 546                           // and a title/markup preceding it.
 547                           min_dist = staff->extent (staff, Y_AXIS)[UP] - last_title_extent[DOWN];
 548                         }
 549                       else // distance to the top margin
 550                         min_dist = header_padding_ + header_height_ + staff->extent (staff, Y_AXIS)[UP];
 551
 552                       loose_line_min_distances.push_back (min_dist);
 553                     }
 554                   loose_lines.push_back (staff);
 555                 }
 556             }
 557
 558           // Corner case: even if a system has no live staves, it still takes up
 559           // one spring (a system with one live staff also takes up one spring),
 560           // which we need to increment past.
 561           if (!found_spaceable_staff)
 562             spring_idx++;
 563
 564           *tail = scm_cons (scm_from_double (system_position), SCM_EOL);
 565           tail = SCM_CDRLOC (*tail);
 566         }
 567     }
 568
 569   if (loose_lines.size ())
 570     {
 571       Grob *last = loose_lines.back ();
 572       Interval last_ext = last->extent (last, Y_AXIS);
 573       loose_line_min_distances.push_back (-last_ext[DOWN] + footer_height_ + footer_padding_);
 574       loose_lines.push_back (0);
 575
 576       distribute_loose_lines (loose_lines, loose_line_min_distances,
 577                               last_spaceable_line_translation, -page_height_);
 578
 579     }
 580
 581   assert (spring_idx == solution_.size () - 1);
 582   return system_offsets;
 583 }
 584
 585 // Given two lines that are already spaced (the first and last
 586 // elements of loose_lines), distribute some unspaced lines between
 587 // them.
 588 // first_translation and last_translation are relative to the page.
 589 void
 590 Page_layout_problem::distribute_loose_lines (vector<Grob*> const &loose_lines,
 591                                              vector<Real> const &min_distances,
 592                                              Real first_translation, Real last_translation)
 593 {
 594   Simple_spacer spacer;
 595   for (vsize i = 0; i + 1 < loose_lines.size (); ++i)
 596     {
 597       SCM spec = get_spacing_spec (loose_lines[i], loose_lines[i+1], false, 0, INT_MAX);
 598       Spring spring (1.0, 0.0);
 599       alter_spring_from_spacing_spec (spec, &spring);
 600       spring.ensure_min_distance (min_distances[i]);
 601       spacer.add_spring (spring);
 602     }
 603
 604   // Remember: offsets are decreasing, since we're going from UP to DOWN!
 605   spacer.solve (first_translation - last_translation, false);
 606
 607   vector<Real> solution = spacer.spring_positions ();
 608   for (vsize i = 1; i + 1 < solution.size (); ++i)
 609     {
 610       Real system_offset = scm_to_double (loose_lines[i]->get_property ("system-Y-offset"));
 611       loose_lines[i]->translate_axis (first_translation - solution[i] - system_offset, Y_AXIS);
 612     }
 613 }
 614
 615 SCM
 616 Page_layout_problem::solution (bool ragged)
 617 {
 618   solve_rod_spring_problem (ragged);
 619   return find_system_offsets ();
 620 }
 621
 622 // Build upper and lower skylines for a system. We don't yet know the positions
 623 // of the staves within the system, so we make the skyline as conservative as
 624 // possible. That is, for the upper skyline, we pretend that all of the staves
 625 // in the system are packed together close to the top system; for the lower
 626 // skyline, we pretend that all of the staves are packed together close to
 627 // the bottom system.
 628 //
 629 // The upper skyline is relative to the top staff; the lower skyline is relative to
 630 // the bottom staff.
 631 void
 632 Page_layout_problem::build_system_skyline (vector<Grob*> const& staves,
 633                                            vector<Real> const& minimum_translations,
 634                                            Skyline *up,
 635                                            Skyline *down)
 636 {
 637   if (minimum_translations.empty ())
 638     return;
 639
 640   assert (staves.size () == minimum_translations.size ());
 641   Real first_translation = minimum_translations[0];
 642   Real last_spaceable_dy = 0;
 643   Real first_spaceable_dy = 0;
 644   bool found_spaceable_staff = false;
 645
 646   for (vsize i = 0; i < staves.size (); ++i)
 647     {
 648       Real dy = minimum_translations[i] - first_translation;
 649       Grob *g = staves[i];
 650       Skyline_pair *sky = Skyline_pair::unsmob (g->get_property ("vertical-skylines"));
 651       if (sky)
 652         {
 653           up->raise (-dy);
 654           up->merge ((*sky)[UP]);
 655           up->raise (dy);
 656
 657           down->raise (-dy);
 658           down->merge ((*sky)[DOWN]);
 659           down->raise (dy);
 660         }
 661       if (is_spaceable (staves[i]))
 662         {
 663           if (!found_spaceable_staff)
 664             {
 665               found_spaceable_staff = true;
 666               first_spaceable_dy = dy;
 667             }
 668           last_spaceable_dy = dy;
 669         }
 670     }
 671
 672   // Leave the up skyline at a position relative
 673   // to the top spaceable staff.
 674   up->raise (-first_spaceable_dy);
 675
 676   // Leave the down skyline at a position
 677   // relative to the bottom spaceable staff.
 678   down->raise (-last_spaceable_dy);
 679 }
 680
 681 Interval
 682 Page_layout_problem::prob_extent (Prob *p)
 683 {
 684   Stencil *sten = unsmob_stencil (p->get_property ("stencil"));
 685   return sten ? sten->extent (Y_AXIS) : Interval (0, 0);
 686 }
 687
 688 Interval
 689 Page_layout_problem::first_staff_extent (Element const& e)
 690 {
 691   if (e.prob)
 692     return prob_extent (e.prob);
 693   else if (e.staves.size ())
 694     return e.staves[0]->extent (e.staves[0], Y_AXIS);
 695
 696   return Interval (0, 0);
 697 }
 698
 699 Interval
 700 Page_layout_problem::last_staff_extent (Element const& e)
 701 {
 702   if (e.prob)
 703     return prob_extent (e.prob);
 704   else if (e.staves.size ())
 705     return e.staves.back ()->extent (e.staves.back (), Y_AXIS);
 706
 707   return Interval (0, 0);
 708 }
 709
 710 SCM
 711 Page_layout_problem::get_details (Element const& elt)
 712 {
 713   if (elt.staves.empty ())
 714     return SCM_EOL;
 715
 716   return get_details (elt.staves.back ()->get_system ());
 717 }
 718
 719 SCM
 720 Page_layout_problem::get_details (Grob *g)
 721 {
 722   Grob *left_bound = dynamic_cast<Spanner*> (g)->get_bound (LEFT);
 723   return left_bound->get_property ("line-break-system-details");
 724 }
 725
 726 bool
 727 Page_layout_problem::is_spaceable (Grob *g)
 728 {
 729   return !scm_is_number (g->get_property ("staff-affinity"));
 730 }
 731
 732 void
 733 Page_layout_problem::mark_as_spaceable (Grob *g)
 734 {
 735   g->set_property ("staff-affinity", SCM_BOOL_F);
 736 }
 737
 738 bool
 739 Page_layout_problem::read_spacing_spec (SCM spec, Real* dest, SCM sym)
 740 {
 741   SCM pair = scm_sloppy_assq (sym, spec);
 742   if (scm_is_pair (pair) && scm_is_number (scm_cdr (pair)))
 743     {
 744       *dest = scm_to_double (scm_cdr (pair));
 745       return true;
 746     }
 747   return false;
 748 }
 749
 750 // If there is a forced, fixed spacing between BEFORE and AFTER, return it.
 751 // Otherwise, return -infinity_f.
 752 // If after is spaceable, it is the (spaceable_index + 1)th spaceable grob in
 753 // its alignment.
 754 Real
 755 Page_layout_problem::get_fixed_spacing (Grob *before, Grob *after, int spaceable_index, bool pure, int start, int end)
 756 {
 757   Spanner *after_sp = dynamic_cast<Spanner*> (after);
 758   SCM cache_symbol = (is_spaceable (before) && is_spaceable (after))
 759     ? ly_symbol2scm ("spaceable-fixed-spacing")
 760     : ly_symbol2scm ("loose-fixed-spacing");
 761   if (pure)
 762     {
 763       // The result of this function doesn't depend on "end," so we can reduce the
 764       // size of the cache by ignoring it.
 765       SCM cached = after_sp->get_cached_pure_property (cache_symbol, start, 0);
 766       if (scm_is_number (cached))
 767         return robust_scm2double (cached, 0.0);
 768     }
 769
 770   SCM spec = Page_layout_problem::get_spacing_spec (before, after, pure, start, end);
 771   Real ret = -infinity_f;
 772   Real stretchability = 0;
 773   if (Page_layout_problem::read_spacing_spec (spec, &stretchability, ly_symbol2scm ("stretchability"))
 774       && stretchability == 0)
 775     Page_layout_problem::read_spacing_spec (spec, &ret, ly_symbol2scm ("basic-distance"));
 776
 777   // If we're pure, then paper-columns have not had their systems set,
 778   // and so elts[i]->get_system () is unreliable.
 779   System *sys = pure ? Grob::get_system (before) : before->get_system ();
 780   Grob *left_bound = sys ? sys->get_maybe_pure_bound (LEFT, pure, start, end) : 0;
 781
 782   if (is_spaceable (before) && is_spaceable (after) && left_bound)
 783     {
 784       SCM details = left_bound->get_property ("line-break-system-details");
 785       SCM manual_dists = ly_assoc_get (ly_symbol2scm ("alignment-distances"), details, SCM_EOL);
 786       if (scm_is_pair (manual_dists))
 787         {
 788           SCM forced = robust_list_ref (spaceable_index - 1, manual_dists);
 789           if (scm_is_number (forced))
 790             ret = max (ret, scm_to_double (forced));
 791         }
 792     }
 793
 794   // Cache the result.  As above, we ignore "end."
 795   if (pure)
 796     after_sp->cache_pure_property (cache_symbol, start, 0, scm_from_double (ret));
 797
 798   return ret;
 799 }
 800
 801 static SCM
 802 add_stretchability (SCM alist, Real stretch)
 803 {
 804   if (!scm_is_pair (scm_sloppy_assq (ly_symbol2scm ("stretchability"), alist)))
 805     return scm_acons (ly_symbol2scm ("stretchability"), scm_from_double (stretch), alist);
 806
 807   return alist;
 808 }
 809
 810 // We want to put a large stretch between a non-spaceable line and its
 811 // non-affinity staff. We want to put an even larger stretch between
 812 // a non-spaceable line and the top/bottom of the page. That way,
 813 // a spacing-affinity UP line at the bottom of the page will still be
 814 // placed close to its staff.
 815 const double LARGE_STRETCH = 10e5;
 816 const double HUGE_STRETCH = 10e7;
 817
 818 // Returns the spacing spec connecting BEFORE to AFTER.
 819 SCM
 820 Page_layout_problem::get_spacing_spec (Grob *before, Grob *after, bool pure, int start, int end)
 821 {
 822   // If there are no spacing wishes, return a very flexible spring.
 823   // This will occur, for example, if there are lyrics at the bottom of
 824   // the page, in which case we don't want the spring from the lyrics to
 825   // the bottom of the page to have much effect.
 826   if (!before || !after)
 827     return add_stretchability (SCM_EOL, HUGE_STRETCH);
 828
 829   if (is_spaceable (before))
 830     {
 831       if (is_spaceable (after))
 832         return before->get_maybe_pure_property ("staff-staff-spacing", pure, start, end);
 833       else
 834         {
 835           Direction affinity = to_dir (after->get_maybe_pure_property ("staff-affinity", pure, start, end));
 836           return (affinity == DOWN)
 837             ? add_stretchability (after->get_maybe_pure_property ("nonstaff-unrelatedstaff-spacing", pure, start, end),
 838                                   LARGE_STRETCH)
 839             : after->get_maybe_pure_property ("nonstaff-relatedstaff-spacing", pure, start, end);
 840         }
 841     }
 842   else
 843     {
 844       if (is_spaceable (after))
 845         {
 846           Direction affinity = to_dir (before->get_maybe_pure_property ("staff-affinity", pure, start, end));
 847           return (affinity == UP)
 848             ? add_stretchability (before->get_maybe_pure_property ("nonstaff-unrelatedstaff-spacing", pure, start, end),
 849                                   LARGE_STRETCH)
 850             : before->get_maybe_pure_property ("nonstaff-relatedstaff-spacing", pure, start, end);
 851         }
 852       else
 853         {
 854           Direction before_affinity = to_dir (before->get_maybe_pure_property ("staff-affinity", pure, start, end));
 855           Direction after_affinity = to_dir (after->get_maybe_pure_property ("staff-affinity", pure, start, end));
 856           if (after_affinity > before_affinity)
 857             {
 858               warning (_ ("staff-affinities should only decrease"));
 859               after_affinity = before_affinity;
 860             }
 861           if (before_affinity != UP)
 862             return before->get_maybe_pure_property ("nonstaff-nonstaff-spacing", pure, start, end);
 863           else if (after_affinity != DOWN)
 864             return before->get_maybe_pure_property ("nonstaff-nonstaff-spacing", pure, start, end);
 865           return add_stretchability (before->get_maybe_pure_property ("nonstaff-unrelatedstaff-spacing", pure, start, end),
 866                                      LARGE_STRETCH);
 867         }
 868     }
 869
 870   assert (0);
 871   return SCM_BOOL_F;
 872 }
 873
 874 void
 875 Page_layout_problem::alter_spring_from_spacing_spec (SCM spec, Spring* spring)
 876 {
 877   Real space;
 878   Real stretch;
 879   Real min_dist;
 880   if (read_spacing_spec (spec, &space, ly_symbol2scm ("basic-distance")))
 881     spring->set_distance (space);
 882   if (read_spacing_spec (spec, &min_dist, ly_symbol2scm ("minimum-distance")))
 883     spring->set_min_distance (min_dist);
 884   spring->set_default_strength ();
 885
 886   if (read_spacing_spec (spec, &stretch, ly_symbol2scm ("stretchability")))
 887     {
 888       spring->set_inverse_stretch_strength (stretch);
 889       spring->set_inverse_compress_strength (stretch);
 890     }
 891 }
 892
 893 vector<Grob*>
 894 Page_layout_problem::filter_dead_elements (vector<Grob*> const& input)
 895 {
 896   vector<Grob*> output;
 897   for (vsize i = 0; i < input.size (); ++i)
 898     {
 899       if (Hara_kiri_group_spanner::has_interface (input[i]))
 900         Hara_kiri_group_spanner::consider_suicide (input[i]);
 901
 902       if (input[i]->is_live ())
 903         output.push_back (input[i]);
 904     }
 905
 906   return output;
 907 }