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