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