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                   last_spaceable_line_translation = -solution_[spring_idx - 1];
 428
 429                   staff->translate_axis (translation, Y_AXIS);
 430                   found_spaceable_staff = true;
 431                 }
 432               else
 433                 {
 434                   if (loose_lines.empty ())
 435                     loose_lines.push_back (last_spaceable_line);
 436
 437                   if (staff_idx)
 438                     // NOTE: the way we do distances between loose lines (and other lines too, actually)
 439                     // is not the most accurate way possible: we only insert rods between adjacent
 440                     // lines.  To be more accurate, we could insert rods between non-adjacent lines
 441                     // using a scheme similar to the one in set_column_rods.
 442                     loose_line_min_distances.push_back (min_offsets[staff_idx-1] - min_offsets[staff_idx]);
 443                   else
 444                     {
 445                       Real min_dist = 0;
 446                       if (loose_lines.back ())
 447                         min_dist = Axis_group_interface::minimum_distance (loose_lines.back (),
 448                                                                            staff,
 449                                                                            Y_AXIS);
 450                       else if (!last_title_extent.is_empty ())
 451                         { // distance to the preceding title
 452                           // TODO: add options for controlling the space between a loose line
 453                           // and a title/markup preceding it.
 454                           min_dist = staff->extent (staff, Y_AXIS)[UP] - last_title_extent[DOWN];
 455                         }
 456                       else // distance to the top margin
 457                         min_dist = header_padding_ + header_height_ + staff->extent (staff, Y_AXIS)[UP];
 458
 459                       loose_line_min_distances.push_back (min_dist);
 460                     }
 461                   loose_lines.push_back (staff);
 462                 }
 463             }
 464
 465           // Corner case: even if a system has no live staves, it still takes up
 466           // one spring (a system with one live staff also takes up one spring),
 467           // which we need to increment past.
 468           if (!found_spaceable_staff)
 469             spring_idx++;
 470
 471           *tail = scm_cons (scm_from_double (system_position), SCM_EOL);
 472           tail = SCM_CDRLOC (*tail);
 473         }
 474     }
 475
 476   if (loose_lines.size ())
 477     {
 478       Grob *last = loose_lines.back ();
 479       Interval last_ext = last->extent (last, Y_AXIS);
 480       loose_line_min_distances.push_back (-last_ext[DOWN] + footer_height_ + footer_padding_);
 481       loose_lines.push_back (0);
 482
 483       distribute_loose_lines (loose_lines, loose_line_min_distances,
 484                               last_spaceable_line_translation, -page_height_);
 485
 486     }
 487
 488   assert (spring_idx == solution_.size () - 1);
 489   return system_offsets;
 490 }
 491
 492 // Given two lines that are already spaced (the first and last
 493 // elements of loose_lines), distribute some unspaced lines between
 494 // them.
 495 // first_translation and last_translation are relative to the page.
 496 void
 497 Page_layout_problem::distribute_loose_lines (vector<Grob*> const &loose_lines,
 498                                              vector<Real> const &min_distances,
 499                                              Real first_translation, Real last_translation)
 500 {
 501   Simple_spacer spacer;
 502   for (vsize i = 0; i + 1 < loose_lines.size (); ++i)
 503     {
 504       SCM spec = get_spacing_spec (loose_lines[i], loose_lines[i+1], false, 0, INT_MAX);
 505       Spring spring (1.0, 0.0);
 506       alter_spring_from_spacing_spec (spec, &spring);
 507       spring.ensure_min_distance (min_distances[i]);
 508       spacer.add_spring (spring);
 509     }
 510
 511   // Remember: offsets are decreasing, since we're going from UP to DOWN!
 512   spacer.solve (first_translation - last_translation, false);
 513
 514   vector<Real> solution = spacer.spring_positions ();
 515   for (vsize i = 1; i + 1 < solution.size (); ++i)
 516     {
 517       Real system_offset = scm_to_double (loose_lines[i]->get_property ("system-Y-offset"));
 518       loose_lines[i]->translate_axis (first_translation - solution[i] - system_offset, Y_AXIS);
 519     }
 520 }
 521
 522 SCM
 523 Page_layout_problem::solution (bool ragged)
 524 {
 525   solve_rod_spring_problem (ragged);
 526   return find_system_offsets ();
 527 }
 528
 529 // Build upper and lower skylines for a system. We don't yet know the positions
 530 // of the staves within the system, so we make the skyline as conservative as
 531 // possible. That is, for the upper skyline, we pretend that all of the staves
 532 // in the system are packed together close to the top system; for the lower
 533 // skyline, we pretend that all of the staves are packed together close to
 534 // the bottom system.
 535 //
 536 // The upper skyline is relative to the top staff; the lower skyline is relative to
 537 // the bottom staff.
 538 void
 539 Page_layout_problem::build_system_skyline (vector<Grob*> const& staves,
 540                                            vector<Real> const& minimum_translations,
 541                                            Skyline *up,
 542                                            Skyline *down)
 543 {
 544   if (minimum_translations.empty ())
 545     return;
 546
 547   assert (staves.size () == minimum_translations.size ());
 548   Real first_translation = minimum_translations[0];
 549   Real last_spaceable_dy = 0;
 550   Real first_spaceable_dy = 0;
 551   bool found_spaceable_staff = false;
 552
 553   for (vsize i = 0; i < staves.size (); ++i)
 554     {
 555       Real dy = minimum_translations[i] - first_translation;
 556       Grob *g = staves[i];
 557       Skyline_pair *sky = Skyline_pair::unsmob (g->get_property ("vertical-skylines"));
 558       if (sky)
 559         {
 560           up->raise (-dy);
 561           up->merge ((*sky)[UP]);
 562           up->raise (dy);
 563
 564           down->raise (-dy);
 565           down->merge ((*sky)[DOWN]);
 566           down->raise (dy);
 567         }
 568       if (is_spaceable (staves[i]))
 569         {
 570           if (!found_spaceable_staff)
 571             {
 572               found_spaceable_staff = true;
 573               first_spaceable_dy = dy;
 574             }
 575           last_spaceable_dy = dy;
 576         }
 577     }
 578
 579   // Leave the up skyline at a position relative
 580   // to the top spaceable staff.
 581   up->raise (-first_spaceable_dy);
 582
 583   // Leave the down skyline at a position
 584   // relative to the bottom spaceable staff.
 585   down->raise (-last_spaceable_dy);
 586 }
 587
 588 Interval
 589 Page_layout_problem::prob_extent (Prob *p)
 590 {
 591   Stencil *sten = unsmob_stencil (p->get_property ("stencil"));
 592   return sten ? sten->extent (Y_AXIS) : Interval (0, 0);
 593 }
 594
 595 Interval
 596 Page_layout_problem::first_staff_extent (Element const& e)
 597 {
 598   if (e.prob)
 599     return prob_extent (e.prob);
 600   else if (e.staves.size ())
 601     return e.staves[0]->extent (e.staves[0], Y_AXIS);
 602
 603   return Interval (0, 0);
 604 }
 605
 606 Interval
 607 Page_layout_problem::last_staff_extent (Element const& e)
 608 {
 609   if (e.prob)
 610     return prob_extent (e.prob);
 611   else if (e.staves.size ())
 612     return e.staves.back ()->extent (e.staves.back (), Y_AXIS);
 613
 614   return Interval (0, 0);
 615 }
 616
 617 SCM
 618 Page_layout_problem::get_details (Element const& elt)
 619 {
 620   if (elt.staves.empty ())
 621     return SCM_EOL;
 622
 623   return get_details (elt.staves.back ()->get_system ());
 624 }
 625
 626 SCM
 627 Page_layout_problem::get_details (Grob *g)
 628 {
 629   Grob *left_bound = dynamic_cast<Spanner*> (g)->get_bound (LEFT);
 630   return left_bound->get_property ("line-break-system-details");
 631 }
 632
 633 bool
 634 Page_layout_problem::is_spaceable (Grob *g)
 635 {
 636   return !scm_is_number (g->get_property ("staff-affinity"));
 637 }
 638
 639 void
 640 Page_layout_problem::mark_as_spaceable (Grob *g)
 641 {
 642   g->set_property ("staff-affinity", SCM_BOOL_F);
 643 }
 644
 645 bool
 646 Page_layout_problem::read_spacing_spec (SCM spec, Real* dest, SCM sym)
 647 {
 648   SCM pair = scm_sloppy_assq (sym, spec);
 649   if (scm_is_pair (pair) && scm_is_number (scm_cdr (pair)))
 650     {
 651       *dest = scm_to_double (scm_cdr (pair));
 652       return true;
 653     }
 654   return false;
 655 }
 656
 657 // If there is a forced, fixed spacing between BEFORE and AFTER, return it.
 658 // Otherwise, return -infinity_f.
 659 // If after is spaceable, it is the (spaceable_index + 1)th spaceable grob in
 660 // its alignment.
 661 Real
 662 Page_layout_problem::get_fixed_spacing (Grob *before, Grob *after, int spaceable_index, bool pure, int start, int end)
 663 {
 664   Spanner *after_sp = dynamic_cast<Spanner*> (after);
 665   SCM cache_symbol = (is_spaceable (before) && is_spaceable (after))
 666     ? ly_symbol2scm ("spaceable-fixed-spacing")
 667     : ly_symbol2scm ("loose-fixed-spacing");
 668   if (pure)
 669     {
 670       // The result of this function doesn't depend on "end," so we can reduce the
 671       // size of the cache by ignoring it.
 672       SCM cached = after_sp->get_cached_pure_property (cache_symbol, start, 0);
 673       if (scm_is_number (cached))
 674         return robust_scm2double (cached, 0.0);
 675     }
 676
 677   SCM spec = Page_layout_problem::get_spacing_spec (before, after, pure, start, end);
 678   Real ret = -infinity_f;
 679   Real stretchability = 0;
 680   if (Page_layout_problem::read_spacing_spec (spec, &stretchability, ly_symbol2scm ("stretchability"))
 681       && stretchability == 0)
 682     Page_layout_problem::read_spacing_spec (spec, &ret, ly_symbol2scm ("basic-distance"));
 683
 684   // If we're pure, then paper-columns have not had their systems set,
 685   // and so elts[i]->get_system () is unreliable.
 686   System *sys = pure ? Grob::get_system (before) : before->get_system ();
 687   Grob *left_bound = sys ? sys->get_maybe_pure_bound (LEFT, pure, start, end) : 0;
 688
 689   if (is_spaceable (before) && is_spaceable (after) && left_bound)
 690     {
 691       SCM details = left_bound->get_property ("line-break-system-details");
 692       SCM manual_dists = ly_assoc_get (ly_symbol2scm ("alignment-distances"), details, SCM_EOL);
 693       if (scm_is_pair (manual_dists))
 694         {
 695           SCM forced = robust_list_ref (spaceable_index - 1, manual_dists);
 696           if (scm_is_number (forced))
 697             ret = max (ret, scm_to_double (forced));
 698         }
 699     }
 700
 701   // Cache the result.  As above, we ignore "end."
 702   if (pure)
 703     after_sp->cache_pure_property (cache_symbol, start, 0, scm_from_double (ret));
 704
 705   return ret;
 706 }
 707
 708 static SCM
 709 add_stretchability (SCM alist, Real stretch)
 710 {
 711   if (!scm_is_pair (scm_sloppy_assq (ly_symbol2scm ("stretchability"), alist)))
 712     return scm_acons (ly_symbol2scm ("stretchability"), scm_from_double (stretch), alist);
 713
 714   return alist;
 715 }
 716
 717 // We want to put a large stretch between a non-spaceable line and its
 718 // non-affinity staff. We want to put an even larger stretch between
 719 // a non-spaceable line and the top/bottom of the page. That way,
 720 // a spacing-affinity UP line at the bottom of the page will still be
 721 // placed close to its staff.
 722 const double LARGE_STRETCH = 10e5;
 723 const double HUGE_STRETCH = 10e7;
 724
 725 // Returns the spacing spec connecting BEFORE to AFTER.
 726 SCM
 727 Page_layout_problem::get_spacing_spec (Grob *before, Grob *after, bool pure, int start, int end)
 728 {
 729   // If there are no spacing wishes, return a very flexible spring.
 730   // This will occur, for example, if there are lyrics at the bottom of
 731   // the page, in which case we don't want the spring from the lyrics to
 732   // the bottom of the page to have much effect.
 733   if (!before || !after)
 734     return add_stretchability (SCM_EOL, HUGE_STRETCH);
 735
 736   if (is_spaceable (before))
 737     {
 738       if (is_spaceable (after))
 739         return before->get_maybe_pure_property ("staff-staff-spacing", pure, start, end);
 740       else
 741         {
 742           Direction affinity = to_dir (after->get_maybe_pure_property ("staff-affinity", pure, start, end));
 743           return (affinity == DOWN)
 744             ? add_stretchability (after->get_maybe_pure_property ("nonstaff-unrelatedstaff-spacing", pure, start, end),
 745                                   LARGE_STRETCH)
 746             : after->get_maybe_pure_property ("nonstaff-relatedstaff-spacing", pure, start, end);
 747         }
 748     }
 749   else
 750     {
 751       if (is_spaceable (after))
 752         {
 753           Direction affinity = to_dir (before->get_maybe_pure_property ("staff-affinity", pure, start, end));
 754           return (affinity == UP)
 755             ? add_stretchability (before->get_maybe_pure_property ("nonstaff-unrelatedstaff-spacing", pure, start, end),
 756                                   LARGE_STRETCH)
 757             : before->get_maybe_pure_property ("nonstaff-relatedstaff-spacing", pure, start, end);
 758         }
 759       else
 760         {
 761           Direction before_affinity = to_dir (before->get_maybe_pure_property ("staff-affinity", pure, start, end));
 762           Direction after_affinity = to_dir (after->get_maybe_pure_property ("staff-affinity", pure, start, end));
 763           if (after_affinity > before_affinity)
 764             {
 765               warning (_ ("staff-affinities should only decrease"));
 766               after_affinity = before_affinity;
 767             }
 768           if (before_affinity != UP)
 769             return before->get_maybe_pure_property ("nonstaff-nonstaff-spacing", pure, start, end);
 770           else if (after_affinity != DOWN)
 771             return before->get_maybe_pure_property ("nonstaff-nonstaff-spacing", pure, start, end);
 772           return add_stretchability (before->get_maybe_pure_property ("nonstaff-unrelatedstaff-spacing", pure, start, end),
 773                                      LARGE_STRETCH);
 774         }
 775     }
 776
 777   assert (0);
 778   return SCM_BOOL_F;
 779 }
 780
 781 void
 782 Page_layout_problem::alter_spring_from_spacing_spec (SCM spec, Spring* spring)
 783 {
 784   Real space;
 785   Real stretch;
 786   Real min_dist;
 787   if (read_spacing_spec (spec, &space, ly_symbol2scm ("basic-distance")))
 788     spring->set_distance (space);
 789   if (read_spacing_spec (spec, &min_dist, ly_symbol2scm ("minimum-distance")))
 790     spring->set_min_distance (min_dist);
 791   spring->set_default_strength ();
 792
 793   if (read_spacing_spec (spec, &stretch, ly_symbol2scm ("stretchability")))
 794     {
 795       spring->set_inverse_stretch_strength (stretch);
 796       spring->set_inverse_compress_strength (stretch);
 797     }
 798 }
 799
 800 vector<Grob*>
 801 Page_layout_problem::filter_dead_elements (vector<Grob*> const& input)
 802 {
 803   vector<Grob*> output;
 804   for (vsize i = 0; i < input.size (); ++i)
 805     {
 806       if (Hara_kiri_group_spanner::has_interface (input[i]))
 807         Hara_kiri_group_spanner::consider_suicide (input[i]);
 808
 809       if (input[i]->is_live ())
 810         output.push_back (input[i]);
 811     }
 812
 813   return output;
 814 }