lily/axis-group-interface.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2000--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
   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 "axis-group-interface.hh"
  21
  22 #include <map>
  23
  24 #include "align-interface.hh"
  25 #include "directional-element-interface.hh"
  26 #include "grob-array.hh"
  27 #include "hara-kiri-group-spanner.hh"
  28 #include "international.hh"
  29 #include "interval-set.hh"
  30 #include "lookup.hh"
  31 #include "paper-column.hh"
  32 #include "paper-score.hh"
  33 #include "pointer-group-interface.hh"
  34 #include "separation-item.hh"
  35 #include "skyline-pair.hh"
  36 #include "staff-grouper-interface.hh"
  37 #include "stem.hh"
  38 #include "stencil.hh"
  39 #include "system.hh"
  40 #include "warn.hh"
  41 #include "unpure-pure-container.hh"
  42
  43 using std::multimap;
  44 using std::pair;
  45 using std::string;
  46 using std::vector;
  47
  48 static bool
  49 pure_staff_priority_less (Grob *const &g1, Grob *const &g2);
  50
  51 Real Axis_group_interface::default_outside_staff_padding_ = 0.46;
  52
  53 Real
  54 Axis_group_interface::get_default_outside_staff_padding ()
  55 {
  56   return default_outside_staff_padding_;
  57 }
  58
  59 void
  60 Axis_group_interface::add_element (Grob *me, Grob *e)
  61 {
  62   SCM axes = me->get_property ("axes");
  63   if (!scm_is_pair (axes))
  64     programming_error ("axes should be nonempty");
  65
  66   for (SCM ax = axes; scm_is_pair (ax); ax = scm_cdr (ax))
  67     {
  68       Axis a = (Axis) scm_to_int (scm_car (ax));
  69
  70       if (!e->get_parent (a))
  71         e->set_parent (me, a);
  72
  73       e->set_object ((a == X_AXIS)
  74                      ? ly_symbol2scm ("axis-group-parent-X")
  75                      : ly_symbol2scm ("axis-group-parent-Y"),
  76                      me->self_scm ());
  77     }
  78
  79   /* must be ordered, because Align_interface also uses
  80      Axis_group_interface  */
  81   Pointer_group_interface::add_grob (me, ly_symbol2scm ("elements"), e);
  82 }
  83
  84 bool
  85 Axis_group_interface::has_axis (Grob *me, Axis a)
  86 {
  87   SCM axes = me->get_property ("axes");
  88
  89   return (SCM_BOOL_F != scm_memq (scm_from_int (a), axes));
  90 }
  91
  92 Interval
  93 Axis_group_interface::relative_group_extent (vector<Grob *> const &elts,
  94                                              Grob *common, Axis a)
  95 {
  96   return relative_maybe_bound_group_extent (elts, common, a, false);
  97 }
  98
  99 Interval
 100 Axis_group_interface::relative_maybe_bound_group_extent (vector<Grob *> const &elts,
 101                                                          Grob *common, Axis a, bool bound)
 102 {
 103   Interval r;
 104   for (vsize i = 0; i < elts.size (); i++)
 105     {
 106       Grob *se = elts[i];
 107       if (!to_boolean (se->get_property ("cross-staff")))
 108         {
 109           Interval dims = (bound && has_interface<Axis_group_interface> (se)
 110                            ? generic_bound_extent (se, common, a)
 111                            : se->extent (common, a));
 112           if (!dims.is_empty ())
 113             r.unite (dims);
 114         }
 115     }
 116   return r;
 117 }
 118
 119 Interval
 120 Axis_group_interface::generic_bound_extent (Grob *me, Grob *common, Axis a)
 121 {
 122   /* trigger the callback to do skyline-spacing on the children */
 123   if (a == Y_AXIS)
 124     (void) me->get_property ("vertical-skylines");
 125
 126   extract_grob_set (me, "elements", elts);
 127   vector<Grob *> new_elts;
 128
 129   SCM interfaces = me->get_property ("bound-alignment-interfaces");
 130
 131   for (vsize i = 0; i < elts.size (); i++)
 132     for (SCM l = interfaces; scm_is_pair (l); l = scm_cdr (l))
 133       if (elts[i]->internal_has_interface (scm_car (l)))
 134         new_elts.push_back (elts[i]);
 135
 136   if (!new_elts.size ())
 137     return robust_relative_extent (me, common, a);
 138
 139   if (!common)
 140     common = common_refpoint_of_array (new_elts, me, a);
 141
 142   return relative_maybe_bound_group_extent (new_elts, common, a, true);
 143 }
 144
 145 Interval
 146 Axis_group_interface::sum_partial_pure_heights (Grob *me, int start, int end)
 147 {
 148   Interval iv = begin_of_line_pure_height (me, start);
 149   iv.unite (rest_of_line_pure_height (me, start, end));
 150
 151   return iv;
 152 }
 153
 154 Interval
 155 Axis_group_interface::part_of_line_pure_height (Grob *me, bool begin, int start, int end)
 156 {
 157   Spanner *sp = dynamic_cast<Spanner *> (me);
 158   if (!sp)
 159     return Interval (0, 0);
 160   SCM cache_symbol = begin
 161                      ? ly_symbol2scm ("begin-of-line-pure-height")
 162                      : ly_symbol2scm ("rest-of-line-pure-height");
 163   SCM cached = sp->get_cached_pure_property (cache_symbol, start, end);
 164   if (scm_is_pair (cached))
 165     return robust_scm2interval (cached, Interval (0, 0));
 166
 167   SCM adjacent_pure_heights = me->get_property ("adjacent-pure-heights");
 168   Interval ret;
 169
 170   if (!scm_is_pair (adjacent_pure_heights))
 171     ret = Interval (0, 0);
 172   else
 173     {
 174       SCM these_pure_heights = begin
 175                                ? scm_car (adjacent_pure_heights)
 176                                : scm_cdr (adjacent_pure_heights);
 177
 178       if (scm_is_vector (these_pure_heights))
 179         ret = combine_pure_heights (me, these_pure_heights, start, end);
 180       else
 181         ret = Interval (0, 0);
 182     }
 183
 184   sp->cache_pure_property (cache_symbol, start, end, ly_interval2scm (ret));
 185   return ret;
 186 }
 187
 188 Interval
 189 Axis_group_interface::begin_of_line_pure_height (Grob *me, int start)
 190 {
 191   return part_of_line_pure_height (me, true, start, start + 1);
 192 }
 193
 194 Interval
 195 Axis_group_interface::rest_of_line_pure_height (Grob *me, int start, int end)
 196 {
 197   return part_of_line_pure_height (me, false, start, end);
 198 }
 199
 200 Interval
 201 Axis_group_interface::combine_pure_heights (Grob *me, SCM measure_extents, int start, int end)
 202 {
 203   Paper_score *ps = get_root_system (me)->paper_score ();
 204   vector<vsize> breaks = ps->get_break_indices ();
 205   vector<Grob *> cols = ps->get_columns ();
 206
 207   Interval ext;
 208   for (vsize i = 0; i + 1 < breaks.size (); i++)
 209     {
 210       int r = Paper_column::get_rank (cols[breaks[i]]);
 211       if (r >= end)
 212         break;
 213
 214       if (r >= start)
 215         ext.unite (ly_scm2interval (scm_c_vector_ref (measure_extents, i)));
 216     }
 217
 218   return ext;
 219 }
 220
 221 // adjacent-pure-heights is a pair of vectors, each of which has one element
 222 // for every measure in the score. The first vector stores, for each measure,
 223 // the combined height of the elements that are present only when the bar
 224 // is at the beginning of a line. The second vector stores, for each measure,
 225 // the combined height of the elements that are present only when the bar
 226 // is not at the beginning of a line.
 227 MAKE_SCHEME_CALLBACK (Axis_group_interface, adjacent_pure_heights, 1)
 228 SCM
 229 Axis_group_interface::adjacent_pure_heights (SCM smob)
 230 {
 231   Grob *me = unsmob<Grob> (smob);
 232
 233   Grob *common = unsmob<Grob> (me->get_object ("pure-Y-common"));
 234   extract_grob_set (me, "pure-relevant-grobs", elts);
 235
 236   Paper_score *ps = get_root_system (me)->paper_score ();
 237   vector<vsize> ranks = ps->get_break_ranks ();
 238
 239   vector<Interval> begin_line_heights;
 240   vector<Interval> mid_line_heights;
 241   vector<Interval> begin_line_staff_heights;
 242   vector<Interval> mid_line_staff_heights;
 243   begin_line_heights.resize (ranks.size () - 1);
 244   mid_line_heights.resize (ranks.size () - 1);
 245
 246   for (vsize i = 0; i < elts.size (); ++i)
 247     {
 248       Grob *g = elts[i];
 249
 250       if (to_boolean (g->get_property ("cross-staff")))
 251         continue;
 252
 253       if (!g->is_live ())
 254         continue;
 255
 256       bool outside_staff = scm_is_number (g->get_property ("outside-staff-priority"));
 257       Real padding = robust_scm2double (g->get_property ("outside-staff-padding"), get_default_outside_staff_padding ());
 258
 259       // When we encounter the first outside-staff grob, make a copy
 260       // of the current heights to use as an estimate for the staff heights.
 261       // Note that the outside-staff approximation that we use here doesn't
 262       // consider any collisions that might occur between outside-staff grobs,
 263       // but only the fact that outside-staff grobs may need to be raised above
 264       // the staff.
 265       if (outside_staff && begin_line_staff_heights.empty ())
 266         {
 267           begin_line_staff_heights = begin_line_heights;
 268           mid_line_staff_heights = mid_line_heights;
 269         }
 270
 271       // TODO: consider a pure version of get_grob_direction?
 272       Direction d = to_dir (g->get_property_data ("direction"));
 273       d = (d == CENTER) ? UP : d;
 274
 275       Interval_t<int> rank_span = g->spanned_rank_interval ();
 276       vsize first_break = lower_bound (ranks, (vsize)rank_span[LEFT], std::less<vsize> ());
 277       if (first_break > 0 && ranks[first_break] >= (vsize)rank_span[LEFT])
 278         first_break--;
 279
 280       for (vsize j = first_break; j + 1 < ranks.size () && (int)ranks[j] <= rank_span[RIGHT]; ++j)
 281         {
 282           int start = ranks[j];
 283           int end = ranks[j + 1];
 284
 285           // Take grobs that are visible with respect to a slightly longer line.
 286           // Otherwise, we will never include grobs at breakpoints which aren't
 287           // end-of-line-visible.
 288           int visibility_end = j + 2 < ranks.size () ? ranks[j + 2] : end;
 289
 290           if (g->pure_is_visible (start, visibility_end))
 291             {
 292               Interval dims = g->pure_y_extent (common, start, end);
 293               if (!dims.is_empty ())
 294                 {
 295                   if (rank_span[LEFT] <= start)
 296                     {
 297                       if (outside_staff)
 298                         begin_line_heights[j].unite (begin_line_staff_heights[j].union_disjoint (dims, padding, d));
 299                       else
 300                         begin_line_heights[j].unite (dims);
 301                     }
 302                   if (rank_span[RIGHT] > start)
 303                     {
 304                       if (outside_staff)
 305                         mid_line_heights[j].unite (mid_line_staff_heights[j].union_disjoint (dims, padding, d));
 306                       else
 307                         mid_line_heights[j].unite (dims);
 308                     }
 309                 }
 310             }
 311         }
 312     }
 313
 314   // Convert begin_line_heights and min_line_heights to SCM.
 315   SCM begin_scm = scm_c_make_vector (ranks.size () - 1, SCM_EOL);
 316   SCM mid_scm = scm_c_make_vector (ranks.size () - 1, SCM_EOL);
 317   for (vsize i = 0; i < begin_line_heights.size (); ++i)
 318     {
 319       scm_vector_set_x (begin_scm, scm_from_int (i), ly_interval2scm (begin_line_heights[i]));
 320       scm_vector_set_x (mid_scm, scm_from_int (i), ly_interval2scm (mid_line_heights[i]));
 321     }
 322
 323   return scm_cons (begin_scm, mid_scm);
 324 }
 325
 326 Interval
 327 Axis_group_interface::relative_pure_height (Grob *me, int start, int end)
 328 {
 329   /* It saves a _lot_ of time if we assume a VerticalAxisGroup is additive
 330      (ie. height (i, k) = std::max (height (i, j) height (j, k)) for all i <= j <= k).
 331      Unfortunately, it isn't always true, particularly if there is a
 332      VerticalAlignment somewhere in the descendants.
 333
 334      Usually, the only VerticalAlignment comes from Score. This makes it
 335      reasonably safe to assume that if our parent is a VerticalAlignment,
 336      we can assume additivity and cache things nicely. */
 337   Grob *p = me->get_parent (Y_AXIS);
 338   if (has_interface<Align_interface> (p))
 339     return Axis_group_interface::sum_partial_pure_heights (me, start, end);
 340
 341   Grob *common = unsmob<Grob> (me->get_object ("pure-Y-common"));
 342   extract_grob_set (me, "pure-relevant-grobs", elts);
 343
 344   Interval r;
 345   for (vsize i = 0; i < elts.size (); i++)
 346     {
 347       Grob *g = elts[i];
 348       Interval_t<int> rank_span = g->spanned_rank_interval ();
 349       if (rank_span[LEFT] <= end && rank_span[RIGHT] >= start
 350           && g->pure_is_visible (start, end)
 351           && !(to_boolean (g->get_property ("cross-staff"))
 352                && has_interface<Stem> (g)))
 353         {
 354           Interval dims = g->pure_y_extent (common, start, end);
 355           if (!dims.is_empty ())
 356             r.unite (dims);
 357         }
 358     }
 359   return r;
 360 }
 361
 362 MAKE_SCHEME_CALLBACK (Axis_group_interface, width, 1);
 363 SCM
 364 Axis_group_interface::width (SCM smob)
 365 {
 366   Grob *me = unsmob<Grob> (smob);
 367   return generic_group_extent (me, X_AXIS);
 368 }
 369
 370 MAKE_SCHEME_CALLBACK (Axis_group_interface, height, 1);
 371 SCM
 372 Axis_group_interface::height (SCM smob)
 373 {
 374   Grob *me = unsmob<Grob> (smob);
 375   return generic_group_extent (me, Y_AXIS);
 376 }
 377
 378 MAKE_SCHEME_CALLBACK (Axis_group_interface, pure_height, 3);
 379 SCM
 380 Axis_group_interface::pure_height (SCM smob, SCM start_scm, SCM end_scm)
 381 {
 382   int start = robust_scm2int (start_scm, 0);
 383   int end = robust_scm2int (end_scm, INT_MAX);
 384   Grob *me = unsmob<Grob> (smob);
 385
 386   /* Maybe we are in the second pass of a two-pass spacing run. In that
 387      case, the Y-extent of a system is already given to us */
 388   System *system = dynamic_cast<System *> (me);
 389   if (system)
 390     {
 391       SCM line_break_details = system->column (start)->get_property ("line-break-system-details");
 392       SCM system_y_extent = scm_assq (ly_symbol2scm ("system-Y-extent"), line_break_details);
 393       if (scm_is_pair (system_y_extent))
 394         return scm_cdr (system_y_extent);
 395     }
 396
 397   return ly_interval2scm (pure_group_height (me, start, end));
 398 }
 399
 400 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_skylines, 1);
 401 SCM
 402 Axis_group_interface::calc_skylines (SCM smob)
 403 {
 404   Grob *me = unsmob<Grob> (smob);
 405   Skyline_pair skylines = skyline_spacing (me);
 406   return skylines.smobbed_copy ();
 407 }
 408
 409 /* whereas calc_skylines calculates skylines for axis-groups with a lot of
 410    visible children, combine_skylines is designed for axis-groups whose only
 411    children are other axis-groups (ie. VerticalAlignment). Rather than
 412    calculating all the skylines from scratch, we just merge the skylines
 413    of the children.
 414 */
 415 MAKE_SCHEME_CALLBACK (Axis_group_interface, combine_skylines, 1);
 416 SCM
 417 Axis_group_interface::combine_skylines (SCM smob)
 418 {
 419   Grob *me = unsmob<Grob> (smob);
 420   extract_grob_set (me, "elements", elements);
 421   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 422   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 423
 424   if (y_common != me)
 425     programming_error ("combining skylines that don't belong to me");
 426
 427   Skyline_pair ret;
 428   for (vsize i = 0; i < elements.size (); i++)
 429     {
 430       SCM skyline_scm = elements[i]->get_property ("vertical-skylines");
 431       if (unsmob<Skyline_pair> (skyline_scm))
 432         {
 433           Real offset = elements[i]->relative_coordinate (y_common, Y_AXIS);
 434           Skyline_pair other = *unsmob<Skyline_pair> (skyline_scm);
 435           other.raise (offset);
 436           other.shift (elements[i]->relative_coordinate (x_common, X_AXIS));
 437           ret.merge (other);
 438         }
 439     }
 440   return ret.smobbed_copy ();
 441 }
 442
 443 SCM
 444 Axis_group_interface::generic_group_extent (Grob *me, Axis a)
 445 {
 446   extract_grob_set (me, "elements", elts);
 447
 448   /* trigger the callback to do skyline-spacing on the children */
 449   if (a == Y_AXIS)
 450     for (vsize i = 0; i < elts.size (); i++)
 451       if (!(has_interface<Stem> (elts[i])
 452             && to_boolean (elts[i]->get_property ("cross-staff"))))
 453         (void) elts[i]->get_property ("vertical-skylines");
 454
 455   Grob *common = common_refpoint_of_array (elts, me, a);
 456
 457   Real my_coord = me->relative_coordinate (common, a);
 458   Interval r (relative_group_extent (elts, common, a));
 459
 460   return ly_interval2scm (r - my_coord);
 461 }
 462
 463 /* This is like generic_group_extent, but it only counts the grobs that
 464    are children of some other axis-group. This is uncached; if it becomes
 465    commonly used, it may be necessary to cache it somehow. */
 466 Interval
 467 Axis_group_interface::staff_extent (Grob *me, Grob *refp, Axis ext_a, Grob *staff, Axis parent_a)
 468 {
 469   extract_grob_set (me, "elements", elts);
 470   vector<Grob *> new_elts;
 471
 472   for (vsize i = 0; i < elts.size (); i++)
 473     if (elts[i]->common_refpoint (staff, parent_a) == staff)
 474       new_elts.push_back (elts[i]);
 475
 476   return relative_group_extent (new_elts, refp, ext_a);
 477 }
 478
 479 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_relevant_grobs, 1);
 480 SCM
 481 Axis_group_interface::calc_pure_relevant_grobs (SCM smob)
 482 {
 483   Grob *me = unsmob<Grob> (smob);
 484   /* TODO: Filter out elements that belong to a different Axis_group,
 485      such as the tie in
 486      << \new Staff=A { c'1~ \change Staff=B c'}
 487         \new Staff=B { \clef bass R1 R } >>
 488     because thier location relative to this Axis_group is not known before
 489     page layout.  For now, we need to trap this case in calc_pure_y_common.
 490   */
 491   return internal_calc_pure_relevant_grobs (me, "elements");
 492 }
 493
 494 SCM
 495 Axis_group_interface::internal_calc_pure_relevant_grobs (Grob *me, const string &grob_set_name)
 496 {
 497   extract_grob_set (me, grob_set_name.c_str (), elts);
 498
 499   vector<Grob *> relevant_grobs;
 500
 501   for (vsize i = 0; i < elts.size (); i++)
 502     {
 503       if (elts[i] && elts[i]->is_live ())
 504         relevant_grobs.push_back (elts[i]);
 505       /*
 506         TODO (mikesol): it is probably bad that we're reading prebroken
 507         pieces from potentially suicided elements.  This behavior
 508         has been in current master since at least 2.16.
 509
 510         We need to fully suicide all Items, meaning that their
 511         prebroken pieces should not be accessible, which means that
 512         Item::handle_prebroken_dependencies should only be called
 513         AFTER this list is composed.  The list composition function
 514         should probably not check for suicided items or NULL pointers
 515         but leave that to the various methods that use it.
 516       */
 517       if (Item *it = dynamic_cast<Item *> (elts[i]))
 518         {
 519           for (LEFT_and_RIGHT (d))
 520             {
 521               Item *piece = it->find_prebroken_piece (d);
 522               if (piece && piece->is_live ())
 523                 relevant_grobs.push_back (piece);
 524             }
 525         }
 526     }
 527
 528   vector_sort (relevant_grobs, pure_staff_priority_less);
 529   SCM grobs_scm = Grob_array::make_array ();
 530   unsmob<Grob_array> (grobs_scm)->set_array (relevant_grobs);
 531
 532   return grobs_scm;
 533 }
 534
 535 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_y_common, 1);
 536 SCM
 537 Axis_group_interface::calc_pure_y_common (SCM smob)
 538 {
 539   Grob *me = unsmob<Grob> (smob);
 540
 541   extract_grob_set (me, "pure-relevant-grobs", elts);
 542   Grob *common = common_refpoint_of_array (elts, me, Y_AXIS);
 543   if (common != me && has_interface<Align_interface> (common))
 544     {
 545       me->programming_error("My pure_y_common is a VerticalAlignment,"
 546                             " which might contain several staves.");
 547       common = me;
 548     }
 549   if (!common)
 550     {
 551       me->programming_error ("No common parent found in calc_pure_y_common.");
 552       return SCM_EOL;
 553     }
 554
 555   return common->self_scm ();
 556 }
 557
 558 SCM
 559 Axis_group_interface::calc_common (Grob *me, Axis axis)
 560 {
 561   extract_grob_set (me, "elements", elts);
 562   Grob *common = common_refpoint_of_array (elts, me, axis);
 563   if (!common)
 564     {
 565       me->programming_error ("No common parent found in calc_common axis.");
 566       return SCM_EOL;
 567     }
 568
 569   return common->self_scm ();
 570 }
 571
 572 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_x_common, 1);
 573 SCM
 574 Axis_group_interface::calc_x_common (SCM grob)
 575 {
 576   return calc_common (unsmob<Grob> (grob), X_AXIS);
 577 }
 578
 579 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_y_common, 1);
 580 SCM
 581 Axis_group_interface::calc_y_common (SCM grob)
 582 {
 583   return calc_common (unsmob<Grob> (grob), Y_AXIS);
 584 }
 585
 586 Interval
 587 Axis_group_interface::pure_group_height (Grob *me, int start, int end)
 588 {
 589   Grob *common = unsmob<Grob> (me->get_object ("pure-Y-common"));
 590
 591   if (!common)
 592     {
 593       programming_error ("no pure Y common refpoint");
 594       return Interval ();
 595     }
 596   Real my_coord = me->pure_relative_y_coordinate (common, start, end);
 597   Interval r (relative_pure_height (me, start, end));
 598
 599   return r - my_coord;
 600 }
 601
 602 void
 603 Axis_group_interface::get_children (Grob *me, vector<Grob *> *found)
 604 {
 605   found->push_back (me);
 606
 607   if (!has_interface<Axis_group_interface> (me))
 608     return;
 609
 610   extract_grob_set (me, "elements", elements);
 611   for (vsize i = 0; i < elements.size (); i++)
 612     {
 613       Grob *e = elements[i];
 614       Axis_group_interface::get_children (e, found);
 615     }
 616 }
 617
 618 static bool
 619 staff_priority_less (Grob *const &g1, Grob *const &g2)
 620 {
 621   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 622   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 623
 624   if (priority_1 < priority_2)
 625     return true;
 626   else if (priority_1 > priority_2)
 627     return false;
 628
 629   /* if neither grob has an outside-staff priority, the ordering will have no
 630      effect -- we just need to choose a consistent ordering. We do this to
 631      avoid the side-effect of calculating extents. */
 632   if (isinf (priority_1))
 633     return g1 < g2;
 634
 635   /* if there is no preference in staff priority, choose the left-most one */
 636   Grob *common = g1->common_refpoint (g2, X_AXIS);
 637   Real start_1 = g1->extent (common, X_AXIS)[LEFT];
 638   Real start_2 = g2->extent (common, X_AXIS)[LEFT];
 639   return start_1 < start_2;
 640 }
 641
 642 static bool
 643 pure_staff_priority_less (Grob *const &g1, Grob *const &g2)
 644 {
 645   Real priority_1 = robust_scm2double (g1->get_property ("outside-staff-priority"), -infinity_f);
 646   Real priority_2 = robust_scm2double (g2->get_property ("outside-staff-priority"), -infinity_f);
 647
 648   return priority_1 < priority_2;
 649 }
 650
 651 static void
 652 add_interior_skylines (Grob *me, Grob *x_common, Grob *y_common, vector<Skyline_pair> *skylines)
 653 {
 654   if (Grob_array *elements = unsmob<Grob_array> (me->get_object ("elements")))
 655     {
 656       for (vsize i = 0; i < elements->size (); i++)
 657         add_interior_skylines (elements->grob (i), x_common, y_common, skylines);
 658     }
 659   else if (!scm_is_number (me->get_property ("outside-staff-priority"))
 660            && !to_boolean (me->get_property ("cross-staff")))
 661     {
 662       Skyline_pair *maybe_pair = unsmob<Skyline_pair> (me->get_property ("vertical-skylines"));
 663       if (!maybe_pair)
 664         return;
 665       if (maybe_pair->is_empty ())
 666         return;
 667       skylines->push_back (Skyline_pair (*maybe_pair));
 668       skylines->back ().shift (me->relative_coordinate (x_common, X_AXIS));
 669       skylines->back ().raise (me->relative_coordinate (y_common, Y_AXIS));
 670     }
 671 }
 672
 673 // Raises the grob elt (whose skylines are given by h_skyline
 674 // and v_skyline) so that it doesn't intersect with staff_skyline,
 675 // or with anything in other_h_skylines and other_v_skylines.
 676 void
 677 avoid_outside_staff_collisions (Grob *elt,
 678                                 Skyline_pair *v_skyline,
 679                                 Real padding,
 680                                 Real horizon_padding,
 681                                 vector<Skyline_pair> const &other_v_skylines,
 682                                 vector<Real> const &other_padding,
 683                                 vector<Real> const &other_horizon_padding,
 684                                 Direction const dir)
 685 {
 686   assert (other_v_skylines.size () == other_padding.size ());
 687   assert (other_v_skylines.size () == other_horizon_padding.size ());
 688   vector<Interval> forbidden_intervals;
 689   for (vsize j = 0; j < other_v_skylines.size (); j++)
 690     {
 691       Skyline_pair const &v_other = other_v_skylines[j];
 692       Real pad = std::max (padding, other_padding[j]);
 693       Real horizon_pad = std::max (horizon_padding, other_horizon_padding[j]);
 694
 695       // We need to push elt up by at least this much to be above v_other.
 696       Real up = (*v_skyline)[DOWN].distance (v_other[UP], horizon_pad) + pad;
 697       // We need to push elt down by at least this much to be below v_other.
 698       Real down = (*v_skyline)[UP].distance (v_other[DOWN], horizon_pad) + pad;
 699
 700       forbidden_intervals.push_back (Interval (-down, up));
 701     }
 702
 703   Interval_set allowed_shifts
 704     = Interval_set::interval_union (forbidden_intervals).complement ();
 705   Real move = allowed_shifts.nearest_point (0, dir);
 706   v_skyline->raise (move);
 707   elt->translate_axis (move, Y_AXIS);
 708 }
 709
 710 SCM
 711 valid_outside_staff_placement_directive (Grob *me)
 712 {
 713   SCM directive = me->get_property ("outside-staff-placement-directive");
 714
 715   if (scm_is_eq (directive, ly_symbol2scm ("left-to-right-greedy"))
 716       || scm_is_eq (directive, ly_symbol2scm ("left-to-right-polite"))
 717       || scm_is_eq (directive, ly_symbol2scm ("right-to-left-greedy"))
 718       || scm_is_eq (directive, ly_symbol2scm ("right-to-left-polite")))
 719     return directive;
 720
 721   me->warning (_f ("\"%s\" is not a valid outside-staff-placement-directive",
 722                    robust_symbol2string (directive, "").c_str ()));
 723
 724   return ly_symbol2scm ("left-to-right-polite");
 725 }
 726
 727 // Shifts the grobs in elements to ensure that they (and any
 728 // connected riders) don't collide with the staff skylines
 729 // or anything in all_X_skylines.  Afterwards, the skylines
 730 // of the grobs in elements will be added to all_v_skylines.
 731 static void
 732 add_grobs_of_one_priority (Grob *me,
 733                            Drul_array<vector<Skyline_pair> > *all_v_skylines,
 734                            Drul_array<vector<Real> > *all_paddings,
 735                            Drul_array<vector<Real> > *all_horizon_paddings,
 736                            vector<Grob *> elements,
 737                            Grob *x_common,
 738                            Grob *y_common,
 739                            multimap<Grob *, Grob *> const &riders)
 740 {
 741
 742   SCM directive
 743     = valid_outside_staff_placement_directive (me);
 744
 745   bool l2r = (scm_is_eq (directive, ly_symbol2scm ("left-to-right-greedy"))
 746               || scm_is_eq (directive, ly_symbol2scm ("left-to-right-polite")));
 747
 748   bool polite = (scm_is_eq (directive, ly_symbol2scm ("left-to-right-polite"))
 749                  || scm_is_eq (directive, ly_symbol2scm ("right-to-left-polite")));
 750
 751   vector<Box> boxes;
 752   vector<Skyline_pair> skylines_to_merge;
 753
 754   // We want to avoid situations like this:
 755   //           still more text
 756   //      more text
 757   //   text
 758   //   -------------------
 759   //   staff
 760   //   -------------------
 761
 762   // The point is that "still more text" should be positioned under
 763   // "more text".  In order to achieve this, we place the grobs in several
 764   // passes.  We keep track of the right-most horizontal position that has been
 765   // affected by the current pass so far (actually we keep track of 2
 766   // positions, one for above the staff, one for below).
 767
 768   // In each pass, we loop through the unplaced grobs from left to right.
 769   // If the grob doesn't overlap the right-most affected position, we place it
 770   // (and then update the right-most affected position to point to the right
 771   // edge of the just-placed grob).  Otherwise, we skip it until the next pass.
 772   while (!elements.empty ())
 773     {
 774       Drul_array<Real> last_end (-infinity_f, -infinity_f);
 775       vector<Grob *> skipped_elements;
 776       for (vsize i = l2r ? 0 : elements.size ();
 777            l2r ? i < elements.size () : i--;
 778            l2r ? i++ : 0)
 779         {
 780           Grob *elt = elements[i];
 781           Real padding
 782             = robust_scm2double (elt->get_property ("outside-staff-padding"),
 783                                  Axis_group_interface
 784                                  ::get_default_outside_staff_padding ());
 785           Real horizon_padding
 786             = robust_scm2double (elt->get_property ("outside-staff-horizontal-padding"), 0.0);
 787           Interval x_extent = elt->extent (x_common, X_AXIS);
 788           x_extent.widen (horizon_padding);
 789
 790           Direction dir = get_grob_direction (elt);
 791           if (dir == CENTER)
 792             {
 793               warning (_ ("an outside-staff object should have a direction, defaulting to up"));
 794               dir = UP;
 795             }
 796
 797           if (x_extent[LEFT] <= last_end[dir] && polite)
 798             {
 799               skipped_elements.push_back (elt);
 800               continue;
 801             }
 802           last_end[dir] = x_extent[RIGHT];
 803
 804           Skyline_pair *v_orig = unsmob<Skyline_pair> (elt->get_property ("vertical-skylines"));
 805           if (!v_orig || v_orig->is_empty ())
 806             continue;
 807
 808           // Find the riders associated with this grob, and merge their
 809           // skylines with elt's skyline.
 810           typedef multimap<Grob *, Grob *>::const_iterator GrobMapIterator;
 811           pair<GrobMapIterator, GrobMapIterator> range = riders.equal_range (elt);
 812           vector<Skyline_pair> rider_v_skylines;
 813           for (GrobMapIterator j = range.first; j != range.second; j++)
 814             {
 815               Grob *rider = j->second;
 816               Skyline_pair *v_rider = unsmob<Skyline_pair> (rider->get_property ("vertical-skylines"));
 817               if (v_rider)
 818                 {
 819                   Skyline_pair copy (*v_rider);
 820                   copy.shift (rider->relative_coordinate (x_common, X_AXIS));
 821                   copy.raise (rider->relative_coordinate (y_common, Y_AXIS));
 822                   rider_v_skylines.push_back (copy);
 823                 }
 824             }
 825           Skyline_pair v_skylines (*v_orig);
 826           v_skylines.shift (elt->relative_coordinate (x_common, X_AXIS));
 827           v_skylines.raise (elt->relative_coordinate (y_common, Y_AXIS));
 828           v_skylines.merge (Skyline_pair (rider_v_skylines));
 829
 830           avoid_outside_staff_collisions (elt,
 831                                           &v_skylines,
 832                                           padding,
 833                                           horizon_padding,
 834                                           (*all_v_skylines)[dir],
 835                                           (*all_paddings)[dir],
 836                                           (*all_horizon_paddings)[dir],
 837                                           dir);
 838
 839           elt->set_property ("outside-staff-priority", SCM_BOOL_F);
 840           (*all_v_skylines)[dir].push_back (v_skylines);
 841           (*all_paddings)[dir].push_back (padding);
 842           (*all_horizon_paddings)[dir].push_back (horizon_padding);
 843         }
 844       std::swap (elements, skipped_elements);
 845       skipped_elements.clear ();
 846     }
 847 }
 848
 849 // If the Grob has a Y-ancestor with outside-staff-priority, return it.
 850 // Otherwise, return 0.
 851 Grob *
 852 Axis_group_interface::outside_staff_ancestor (Grob *me)
 853 {
 854   Grob *parent = me->get_parent (Y_AXIS);
 855   if (!parent)
 856     return 0;
 857
 858   if (scm_is_number (parent->get_property ("outside-staff-priority")))
 859     return parent;
 860
 861   return outside_staff_ancestor (parent);
 862 }
 863
 864 // It is tricky to correctly handle skyline placement of cross-staff grobs.
 865 // For example, cross-staff beams cannot be formatted until the distance between
 866 // staves is known and therefore any grobs that depend on the beam cannot be placed
 867 // until the skylines are known. On the other hand, the distance between staves should
 868 // really depend on position of the cross-staff grobs that lie between them.
 869 // Currently, we just leave cross-staff grobs out of the
 870 // skyline altogether, but this could mean that staves are placed so close together
 871 // that there is no room for the cross-staff grob. It also means, of course, that
 872 // we don't get the benefits of skyline placement for cross-staff grobs.
 873 Skyline_pair
 874 Axis_group_interface::skyline_spacing (Grob *me)
 875 {
 876   extract_grob_set (me, unsmob<Grob_array> (me->get_object ("vertical-skyline-elements")) ? "vertical-skyline-elements" : "elements", fakeelements);
 877   vector<Grob *> elements (fakeelements);
 878   for (vsize i = 0; i < elements.size (); i++)
 879     /*
 880       As a sanity check, we make sure that no grob with an outside staff priority
 881       has a Y-parent that also has an outside staff priority, which would result
 882       in two movings.
 883     */
 884     if (scm_is_number (elements[i]->get_property ("outside-staff-priority"))
 885         && outside_staff_ancestor (elements[i]))
 886       {
 887         elements[i]->warning ("Cannot set outside-staff-priority for element and elements' Y parent.");
 888         elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F);
 889       }
 890
 891   /* For grobs with an outside-staff-priority, the sorting function might
 892      call extent and cause suicide. This breaks the contract that is required
 893      for the STL sort function. To avoid this, we make sure that any suicides
 894      are triggered beforehand.
 895   */
 896   for (vsize i = 0; i < elements.size (); i++)
 897     if (scm_is_number (elements[i]->get_property ("outside-staff-priority")))
 898       elements[i]->extent (elements[i], X_AXIS);
 899
 900   vector_sort (elements, staff_priority_less);
 901   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
 902   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 903
 904   if (y_common != me)
 905     {
 906       me->programming_error("Some of my vertical-skyline-elements"
 907                             " are outside my VerticalAxisGroup.");
 908       y_common = me;
 909     }
 910
 911   // A rider is a grob that is not outside-staff, but has an outside-staff
 912   // ancestor.  In that case, the rider gets moved along with its ancestor.
 913   multimap<Grob *, Grob *> riders;
 914
 915   vsize i = 0;
 916   vector<Skyline_pair> inside_staff_skylines;
 917
 918   for (i = 0; i < elements.size ()
 919        && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++)
 920     {
 921       Grob *elt = elements[i];
 922       Grob *ancestor = outside_staff_ancestor (elt);
 923       if (!(to_boolean (elt->get_property ("cross-staff")) || ancestor))
 924         add_interior_skylines (elt, x_common, y_common, &inside_staff_skylines);
 925       if (ancestor)
 926         riders.insert (pair<Grob *, Grob *> (ancestor, elt));
 927     }
 928
 929   Skyline_pair skylines (inside_staff_skylines);
 930
 931   // These are the skylines of all outside-staff grobs
 932   // that have already been processed.  We keep them around in order to
 933   // check them for collisions with the currently active outside-staff grob.
 934   Drul_array<vector<Skyline_pair> > all_v_skylines;
 935   Drul_array<vector<Real> > all_paddings;
 936   Drul_array<vector<Real> > all_horizon_paddings;
 937   for (UP_and_DOWN (d))
 938     {
 939       all_v_skylines[d].push_back (skylines);
 940       all_paddings[d].push_back (0);
 941       all_horizon_paddings[d].push_back (0);
 942     }
 943
 944   for (; i < elements.size (); i++)
 945     {
 946       if (to_boolean (elements[i]->get_property ("cross-staff")))
 947         continue;
 948
 949       // Collect all the outside-staff grobs that have a particular priority.
 950       SCM priority = elements[i]->get_property ("outside-staff-priority");
 951       vector<Grob *> current_elts;
 952       current_elts.push_back (elements[i]);
 953       while (i + 1 < elements.size ()
 954              && scm_is_eq (elements[i + 1]->get_property ("outside-staff-priority"), priority))
 955         {
 956           if (!to_boolean (elements[i + 1]->get_property ("cross-staff")))
 957             current_elts.push_back (elements[i + 1]);
 958           ++i;
 959         }
 960
 961       add_grobs_of_one_priority (me,
 962                                  &all_v_skylines,
 963                                  &all_paddings,
 964                                  &all_horizon_paddings,
 965                                  current_elts,
 966                                  x_common,
 967                                  y_common,
 968                                  riders);
 969     }
 970
 971   // Now everything in all_v_skylines has been shifted appropriately; merge
 972   // them all into skylines to get the complete outline.
 973   Skyline_pair other_skylines (all_v_skylines[UP]);
 974   other_skylines.merge (Skyline_pair (all_v_skylines[DOWN]));
 975   skylines.merge (other_skylines);
 976
 977   // We began by shifting my skyline to be relative to the common refpoint; now
 978   // shift it back.
 979   skylines.shift (-me->relative_coordinate (x_common, X_AXIS));
 980
 981   return skylines;
 982 }
 983
 984 MAKE_SCHEME_CALLBACK (Axis_group_interface, print, 1)
 985 SCM
 986 Axis_group_interface::print (SCM smob)
 987 {
 988   if (!debug_skylines)
 989     return SCM_BOOL_F;
 990
 991   Grob *me = unsmob<Grob> (smob);
 992   Stencil ret;
 993   if (Skyline_pair *s = unsmob<Skyline_pair> (me->get_property ("vertical-skylines")))
 994     {
 995       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[UP].to_points (X_AXIS))
 996                        .in_color (255, 0, 255));
 997       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[DOWN].to_points (X_AXIS))
 998                        .in_color (0, 255, 255));
 999     }
1000   return ret.smobbed_copy ();
1001 }
1002
1003 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_staff_staff_spacing, 3)
1004 SCM
1005 Axis_group_interface::calc_pure_staff_staff_spacing (SCM smob, SCM start, SCM end)
1006 {
1007   return calc_maybe_pure_staff_staff_spacing (unsmob<Grob> (smob),
1008                                               true,
1009                                               scm_to_int (start),
1010                                               scm_to_int (end));
1011 }
1012
1013 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_staff_staff_spacing, 1)
1014 SCM
1015 Axis_group_interface::calc_staff_staff_spacing (SCM smob)
1016 {
1017   return calc_maybe_pure_staff_staff_spacing (unsmob<Grob> (smob),
1018                                               false,
1019                                               0,
1020                                               INT_MAX);
1021 }
1022
1023 SCM
1024 Axis_group_interface::calc_maybe_pure_staff_staff_spacing (Grob *me, bool pure, int start, int end)
1025 {
1026   Grob *grouper = unsmob<Grob> (me->get_object ("staff-grouper"));
1027
1028   if (grouper)
1029     {
1030       bool within_group = Staff_grouper_interface::maybe_pure_within_group (grouper, me, pure, start, end);
1031       if (within_group)
1032         return grouper->get_maybe_pure_property ("staff-staff-spacing", pure, start, end);
1033       else
1034         return grouper->get_maybe_pure_property ("staffgroup-staff-spacing", pure, start, end);
1035     }
1036   return me->get_maybe_pure_property ("default-staff-staff-spacing", pure, start, end);
1037 }
1038
1039 ADD_INTERFACE (Axis_group_interface,
1040                "An object that groups other layout objects.",
1041
1042                // TODO: some of these properties are specific to
1043                // VerticalAxisGroup. We should split off a
1044                // vertical-axis-group-interface.
1045                /* properties */
1046                "adjacent-pure-heights "
1047                "axes "
1048                "bound-alignment-interfaces "
1049                "default-staff-staff-spacing "
1050                "elements "
1051                "max-stretch "
1052                "no-alignment "
1053                "nonstaff-nonstaff-spacing "
1054                "nonstaff-relatedstaff-spacing "
1055                "nonstaff-unrelatedstaff-spacing "
1056                "pure-relevant-grobs "
1057                "pure-relevant-items "
1058                "pure-relevant-spanners "
1059                "pure-Y-common "
1060                "staff-affinity "
1061                "staff-grouper "
1062                "staff-staff-spacing "
1063                "system-Y-offset "
1064                "X-common "
1065                "Y-common "
1066               );