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