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