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