]> git.donarmstrong.com Git - lilypond.git/blobdiff - lily/axis-group-interface.cc
Web-ja: update introduction
[lilypond.git] / lily / axis-group-interface.cc
index 1b937985eeee2aab63444c47401f2a49e9a59af7..ac6f85feb8e25bb810875d47567708194d762cd3 100644 (file)
@@ -1,7 +1,7 @@
 /*
   This file is part of LilyPond, the GNU music typesetter.
 
-  Copyright (C) 2000--2012 Han-Wen Nienhuys <hanwen@xs4all.nl>
+  Copyright (C) 2000--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
 
   LilyPond is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
 
 #include "axis-group-interface.hh"
 
+#include <map>
+
 #include "align-interface.hh"
 #include "directional-element-interface.hh"
 #include "grob-array.hh"
 #include "hara-kiri-group-spanner.hh"
 #include "international.hh"
+#include "interval-set.hh"
 #include "lookup.hh"
 #include "paper-column.hh"
 #include "paper-score.hh"
 static bool
 pure_staff_priority_less (Grob *const &g1, Grob *const &g2);
 
+Real Axis_group_interface::default_outside_staff_padding_ = 0.46;
+
+Real
+Axis_group_interface::get_default_outside_staff_padding ()
+{
+  return default_outside_staff_padding_;
+}
+
 void
 Axis_group_interface::add_element (Grob *me, Grob *e)
 {
@@ -70,7 +81,7 @@ Axis_group_interface::has_axis (Grob *me, Axis a)
 {
   SCM axes = me->get_property ("axes");
 
-  return (SCM_BOOL_F != scm_memq (scm_from_int (a), axes));
+  return scm_is_true (scm_memq (scm_from_int (a), axes));
 }
 
 Interval
@@ -90,7 +101,7 @@ Axis_group_interface::relative_maybe_bound_group_extent (vector<Grob *> const &e
       Grob *se = elts[i];
       if (!to_boolean (se->get_property ("cross-staff")))
         {
-          Interval dims = (bound && has_interface (se)
+          Interval dims = (bound && has_interface<Axis_group_interface> (se)
                            ? generic_bound_extent (se, common, a)
                            : se->extent (common, a));
           if (!dims.is_empty ())
@@ -139,6 +150,8 @@ Interval
 Axis_group_interface::part_of_line_pure_height (Grob *me, bool begin, int start, int end)
 {
   Spanner *sp = dynamic_cast<Spanner *> (me);
+  if (!sp)
+    return Interval (0, 0);
   SCM cache_symbol = begin
                      ? ly_symbol2scm ("begin-of-line-pure-height")
                      : ly_symbol2scm ("rest-of-line-pure-height");
@@ -210,9 +223,9 @@ MAKE_SCHEME_CALLBACK (Axis_group_interface, adjacent_pure_heights, 1)
 SCM
 Axis_group_interface::adjacent_pure_heights (SCM smob)
 {
-  Grob *me = unsmob_grob (smob);
+  Grob *me = unsmob<Grob> (smob);
 
-  Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
+  Grob *common = unsmob<Grob> (me->get_object ("pure-Y-common"));
   extract_grob_set (me, "pure-relevant-grobs", elts);
 
   Paper_score *ps = get_root_system (me)->paper_score ();
@@ -232,8 +245,11 @@ Axis_group_interface::adjacent_pure_heights (SCM smob)
       if (to_boolean (g->get_property ("cross-staff")))
         continue;
 
+      if (!g->is_live ())
+        continue;
+
       bool outside_staff = scm_is_number (g->get_property ("outside-staff-priority"));
-      Real padding = robust_scm2double (g->get_property ("outside-staff-padding"), 0.5);
+      Real padding = robust_scm2double (g->get_property ("outside-staff-padding"), get_default_outside_staff_padding ());
 
       // When we encounter the first outside-staff grob, make a copy
       // of the current heights to use as an estimate for the staff heights.
@@ -268,7 +284,7 @@ Axis_group_interface::adjacent_pure_heights (SCM smob)
 
           if (g->pure_is_visible (start, visibility_end))
             {
-              Interval dims = g->pure_height (common, start, end);
+              Interval dims = g->pure_y_extent (common, start, end);
               if (!dims.is_empty ())
                 {
                   if (rank_span[LEFT] <= start)
@@ -314,10 +330,10 @@ Axis_group_interface::relative_pure_height (Grob *me, int start, int end)
      reasonably safe to assume that if our parent is a VerticalAlignment,
      we can assume additivity and cache things nicely. */
   Grob *p = me->get_parent (Y_AXIS);
-  if (p && Align_interface::has_interface (p))
+  if (has_interface<Align_interface> (p))
     return Axis_group_interface::sum_partial_pure_heights (me, start, end);
 
-  Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
+  Grob *common = unsmob<Grob> (me->get_object ("pure-Y-common"));
   extract_grob_set (me, "pure-relevant-grobs", elts);
 
   Interval r;
@@ -328,9 +344,9 @@ Axis_group_interface::relative_pure_height (Grob *me, int start, int end)
       if (rank_span[LEFT] <= end && rank_span[RIGHT] >= start
           && g->pure_is_visible (start, end)
           && !(to_boolean (g->get_property ("cross-staff"))
-               && Stem::has_interface (g)))
+               && has_interface<Stem> (g)))
         {
-          Interval dims = g->pure_height (common, start, end);
+          Interval dims = g->pure_y_extent (common, start, end);
           if (!dims.is_empty ())
             r.unite (dims);
         }
@@ -342,7 +358,7 @@ MAKE_SCHEME_CALLBACK (Axis_group_interface, width, 1);
 SCM
 Axis_group_interface::width (SCM smob)
 {
-  Grob *me = unsmob_grob (smob);
+  Grob *me = unsmob<Grob> (smob);
   return generic_group_extent (me, X_AXIS);
 }
 
@@ -350,7 +366,7 @@ MAKE_SCHEME_CALLBACK (Axis_group_interface, height, 1);
 SCM
 Axis_group_interface::height (SCM smob)
 {
-  Grob *me = unsmob_grob (smob);
+  Grob *me = unsmob<Grob> (smob);
   return generic_group_extent (me, Y_AXIS);
 }
 
@@ -360,7 +376,7 @@ Axis_group_interface::pure_height (SCM smob, SCM start_scm, SCM end_scm)
 {
   int start = robust_scm2int (start_scm, 0);
   int end = robust_scm2int (end_scm, INT_MAX);
-  Grob *me = unsmob_grob (smob);
+  Grob *me = unsmob<Grob> (smob);
 
   /* Maybe we are in the second pass of a two-pass spacing run. In that
      case, the Y-extent of a system is already given to us */
@@ -380,10 +396,8 @@ MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_skylines, 1);
 SCM
 Axis_group_interface::calc_skylines (SCM smob)
 {
-  Grob *me = unsmob_grob (smob);
-  extract_grob_set (me, "elements", elts);
-  Skyline_pair skylines = skyline_spacing (me, elts);
-
+  Grob *me = unsmob<Grob> (smob);
+  Skyline_pair skylines = skyline_spacing (me);
   return skylines.smobbed_copy ();
 }
 
@@ -397,7 +411,7 @@ MAKE_SCHEME_CALLBACK (Axis_group_interface, combine_skylines, 1);
 SCM
 Axis_group_interface::combine_skylines (SCM smob)
 {
-  Grob *me = unsmob_grob (smob);
+  Grob *me = unsmob<Grob> (smob);
   extract_grob_set (me, "elements", elements);
   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
@@ -409,10 +423,10 @@ Axis_group_interface::combine_skylines (SCM smob)
   for (vsize i = 0; i < elements.size (); i++)
     {
       SCM skyline_scm = elements[i]->get_property ("vertical-skylines");
-      if (Skyline_pair::unsmob (skyline_scm))
+      if (unsmob<Skyline_pair> (skyline_scm))
         {
           Real offset = elements[i]->relative_coordinate (y_common, Y_AXIS);
-          Skyline_pair other = *Skyline_pair::unsmob (skyline_scm);
+          Skyline_pair other = *unsmob<Skyline_pair> (skyline_scm);
           other.raise (offset);
           other.shift (elements[i]->relative_coordinate (x_common, X_AXIS));
           ret.merge (other);
@@ -424,11 +438,15 @@ Axis_group_interface::combine_skylines (SCM smob)
 SCM
 Axis_group_interface::generic_group_extent (Grob *me, Axis a)
 {
+  extract_grob_set (me, "elements", elts);
+
   /* trigger the callback to do skyline-spacing on the children */
   if (a == Y_AXIS)
-    (void) me->get_property ("vertical-skylines");
+    for (vsize i = 0; i < elts.size (); i++)
+      if (!(has_interface<Stem> (elts[i])
+            && to_boolean (elts[i]->get_property ("cross-staff"))))
+        (void) elts[i]->get_property ("vertical-skylines");
 
-  extract_grob_set (me, "elements", elts);
   Grob *common = common_refpoint_of_array (elts, me, a);
 
   Real my_coord = me->relative_coordinate (common, a);
@@ -457,29 +475,46 @@ MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_relevant_grobs, 1);
 SCM
 Axis_group_interface::calc_pure_relevant_grobs (SCM smob)
 {
-  Grob *me = unsmob_grob (smob);
+  Grob *me = unsmob<Grob> (smob);
+  /* TODO: Filter out elements that belong to a different Axis_group,
+     such as the tie in
+     << \new Staff=A { c'1~ \change Staff=B c'}
+        \new Staff=B { \clef bass R1 R } >>
+    because thier location relative to this Axis_group is not known before
+    page layout.  For now, we need to trap this case in calc_pure_y_common.
+  */
   return internal_calc_pure_relevant_grobs (me, "elements");
 }
 
 SCM
-Axis_group_interface::internal_calc_pure_relevant_grobs (Grob *me, string grob_set_name)
+Axis_group_interface::internal_calc_pure_relevant_grobs (Grob *me, const string &grob_set_name)
 {
   extract_grob_set (me, grob_set_name.c_str (), elts);
 
   vector<Grob *> relevant_grobs;
-  SCM pure_relevant_p = ly_lily_module_constant ("pure-relevant?");
 
   for (vsize i = 0; i < elts.size (); i++)
     {
-      if (to_boolean (scm_apply_1 (pure_relevant_p, elts[i]->self_scm (), SCM_EOL)))
+      if (elts[i] && elts[i]->is_live ())
         relevant_grobs.push_back (elts[i]);
-
+      /*
+        TODO (mikesol): it is probably bad that we're reading prebroken
+        pieces from potentially suicided elements.  This behavior
+        has been in current master since at least 2.16.
+
+        We need to fully suicide all Items, meaning that their
+        prebroken pieces should not be accessible, which means that
+        Item::handle_prebroken_dependencies should only be called
+        AFTER this list is composed.  The list composition function
+        should probably not check for suicided items or NULL pointers
+        but leave that to the various methods that use it.
+      */
       if (Item *it = dynamic_cast<Item *> (elts[i]))
         {
           for (LEFT_and_RIGHT (d))
             {
               Item *piece = it->find_prebroken_piece (d);
-              if (piece && to_boolean (scm_apply_1 (pure_relevant_p, piece->self_scm (), SCM_EOL)))
+              if (piece && piece->is_live ())
                 relevant_grobs.push_back (piece);
             }
         }
@@ -487,7 +522,7 @@ Axis_group_interface::internal_calc_pure_relevant_grobs (Grob *me, string grob_s
 
   vector_sort (relevant_grobs, pure_staff_priority_less);
   SCM grobs_scm = Grob_array::make_array ();
-  unsmob_grob_array (grobs_scm)->set_array (relevant_grobs);
+  unsmob<Grob_array> (grobs_scm)->set_array (relevant_grobs);
 
   return grobs_scm;
 }
@@ -496,10 +531,16 @@ MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_y_common, 1);
 SCM
 Axis_group_interface::calc_pure_y_common (SCM smob)
 {
-  Grob *me = unsmob_grob (smob);
+  Grob *me = unsmob<Grob> (smob);
 
   extract_grob_set (me, "pure-relevant-grobs", elts);
   Grob *common = common_refpoint_of_array (elts, me, Y_AXIS);
+  if (common != me && has_interface<Align_interface> (common))
+    {
+      me->programming_error("My pure_y_common is a VerticalAlignment,"
+                            " which might contain several staves.");
+      common = me;
+    }
   if (!common)
     {
       me->programming_error ("No common parent found in calc_pure_y_common.");
@@ -527,27 +568,27 @@ MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_x_common, 1);
 SCM
 Axis_group_interface::calc_x_common (SCM grob)
 {
-  return calc_common (unsmob_grob (grob), X_AXIS);
+  return calc_common (unsmob<Grob> (grob), X_AXIS);
 }
 
 MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_y_common, 1);
 SCM
 Axis_group_interface::calc_y_common (SCM grob)
 {
-  return calc_common (unsmob_grob (grob), Y_AXIS);
+  return calc_common (unsmob<Grob> (grob), Y_AXIS);
 }
 
 Interval
 Axis_group_interface::pure_group_height (Grob *me, int start, int end)
 {
-  Grob *common = unsmob_grob (me->get_object ("pure-Y-common"));
+  Grob *common = unsmob<Grob> (me->get_object ("pure-Y-common"));
 
   if (!common)
     {
       programming_error ("no pure Y common refpoint");
       return Interval ();
     }
-  Real my_coord = me->relative_coordinate (common, Y_AXIS);
+  Real my_coord = me->pure_relative_y_coordinate (common, start, end);
   Interval r (relative_pure_height (me, start, end));
 
   return r - my_coord;
@@ -558,7 +599,7 @@ Axis_group_interface::get_children (Grob *me, vector<Grob *> *found)
 {
   found->push_back (me);
 
-  if (!has_interface (me))
+  if (!has_interface<Axis_group_interface> (me))
     return;
 
   extract_grob_set (me, "elements", elements);
@@ -603,116 +644,219 @@ pure_staff_priority_less (Grob *const &g1, Grob *const &g2)
 }
 
 static void
-add_boxes (Grob *me, Grob *x_common, Grob *y_common, vector<Box> *const boxes, Skyline_pair *skylines)
+add_interior_skylines (Grob *me, Grob *x_common, Grob *y_common, vector<Skyline_pair> *skylines)
 {
-  /* if a child has skylines, use them instead of the extent box */
-  if (Skyline_pair *pair = Skyline_pair::unsmob (me->get_property ("vertical-skylines")))
-    {
-      Skyline_pair s = *pair;
-      s.shift (me->relative_coordinate (x_common, X_AXIS));
-      s.raise (me->relative_coordinate (y_common, Y_AXIS));
-      skylines->merge (s);
-    }
-  else if (Grob_array *elements = unsmob_grob_array (me->get_object ("elements")))
+  if (Grob_array *elements = unsmob<Grob_array> (me->get_object ("elements")))
     {
       for (vsize i = 0; i < elements->size (); i++)
-        add_boxes (elements->grob (i), x_common, y_common, boxes, skylines);
+        add_interior_skylines (elements->grob (i), x_common, y_common, skylines);
     }
   else if (!scm_is_number (me->get_property ("outside-staff-priority"))
            && !to_boolean (me->get_property ("cross-staff")))
     {
-      boxes->push_back (Box (me->extent (x_common, X_AXIS),
-                             me->extent (y_common, Y_AXIS)));
+      Skyline_pair *maybe_pair = unsmob<Skyline_pair> (me->get_property ("vertical-skylines"));
+      if (!maybe_pair)
+        return;
+      if (maybe_pair->is_empty ())
+        return;
+      skylines->push_back (Skyline_pair (*maybe_pair));
+      skylines->back ().shift (me->relative_coordinate (x_common, X_AXIS));
+      skylines->back ().raise (me->relative_coordinate (y_common, Y_AXIS));
     }
 }
 
-/* We want to avoid situations like this:
-           still more text
-      more text
-   text
-   -------------------
-   staff
-   -------------------
-
-   The point is that "still more text" should be positioned under
-   "more text".  In order to achieve this, we place the grobs in several
-   passes.  We keep track of the right-most horizontal position that has been
-   affected by the current pass so far (actually we keep track of 2
-   positions, one for above the staff, one for below).
-
-   In each pass, we loop through the unplaced grobs from left to right.
-   If the grob doesn't overlap the right-most affected position, we place it
-   (and then update the right-most affected position to point to the right
-   edge of the just-placed grob).  Otherwise, we skip it until the next pass.
-*/
+// Raises the grob elt (whose skylines are given by h_skyline
+// and v_skyline) so that it doesn't intersect with staff_skyline,
+// or with anything in other_h_skylines and other_v_skylines.
+void
+avoid_outside_staff_collisions (Grob *elt,
+                                Skyline_pair *v_skyline,
+                                Real padding,
+                                Real horizon_padding,
+                                vector<Skyline_pair> const &other_v_skylines,
+                                vector<Real> const &other_padding,
+                                vector<Real> const &other_horizon_padding,
+                                Direction const dir)
+{
+  assert (other_v_skylines.size () == other_padding.size ());
+  assert (other_v_skylines.size () == other_horizon_padding.size ());
+  vector<Interval> forbidden_intervals;
+  for (vsize j = 0; j < other_v_skylines.size (); j++)
+    {
+      Skyline_pair const &v_other = other_v_skylines[j];
+      Real pad = max (padding, other_padding[j]);
+      Real horizon_pad = max (horizon_padding, other_horizon_padding[j]);
+
+      // We need to push elt up by at least this much to be above v_other.
+      Real up = (*v_skyline)[DOWN].distance (v_other[UP], horizon_pad) + pad;
+      // We need to push elt down by at least this much to be below v_other.
+      Real down = (*v_skyline)[UP].distance (v_other[DOWN], horizon_pad) + pad;
+
+      forbidden_intervals.push_back (Interval (-down, up));
+    }
+
+  Interval_set allowed_shifts
+    = Interval_set::interval_union (forbidden_intervals).complement ();
+  Real move = allowed_shifts.nearest_point (0, dir);
+  v_skyline->raise (move);
+  elt->translate_axis (move, Y_AXIS);
+}
+
+SCM
+valid_outside_staff_placement_directive (Grob *me)
+{
+  SCM directive = me->get_property ("outside-staff-placement-directive");
+
+  if (scm_is_eq (directive, ly_symbol2scm ("left-to-right-greedy"))
+      || scm_is_eq (directive, ly_symbol2scm ("left-to-right-polite"))
+      || scm_is_eq (directive, ly_symbol2scm ("right-to-left-greedy"))
+      || scm_is_eq (directive, ly_symbol2scm ("right-to-left-polite")))
+    return directive;
+
+  me->warning (_f ("\"%s\" is not a valid outside-staff-placement-directive",
+                   robust_symbol2string (directive, "").c_str ()));
+
+  return ly_symbol2scm ("left-to-right-polite");
+}
+
+// Shifts the grobs in elements to ensure that they (and any
+// connected riders) don't collide with the staff skylines
+// or anything in all_X_skylines.  Afterwards, the skylines
+// of the grobs in elements will be added to all_v_skylines.
 static void
-add_grobs_of_one_priority (Skyline_pair *const skylines,
+add_grobs_of_one_priority (Grob *me,
+                           Drul_array<vector<Skyline_pair> > *all_v_skylines,
+                           Drul_array<vector<Real> > *all_paddings,
+                           Drul_array<vector<Real> > *all_horizon_paddings,
                            vector<Grob *> elements,
                            Grob *x_common,
-                           Grob *y_common)
+                           Grob *y_common,
+                           multimap<Grob *, Grob *> const &riders)
 {
-  vector<Box> boxes;
-  Drul_array<Real> last_affected_position;
 
-  reverse (elements);
+  SCM directive
+    = valid_outside_staff_placement_directive (me);
+
+  bool l2r = (scm_is_eq (directive, ly_symbol2scm ("left-to-right-greedy"))
+              || scm_is_eq (directive, ly_symbol2scm ("left-to-right-polite")));
+
+  bool polite = (scm_is_eq (directive, ly_symbol2scm ("left-to-right-polite"))
+                 || scm_is_eq (directive, ly_symbol2scm ("right-to-left-polite")));
+
+  vector<Box> boxes;
+  vector<Skyline_pair> skylines_to_merge;
+
+  // We want to avoid situations like this:
+  //           still more text
+  //      more text
+  //   text
+  //   -------------------
+  //   staff
+  //   -------------------
+
+  // The point is that "still more text" should be positioned under
+  // "more text".  In order to achieve this, we place the grobs in several
+  // passes.  We keep track of the right-most horizontal position that has been
+  // affected by the current pass so far (actually we keep track of 2
+  // positions, one for above the staff, one for below).
+
+  // In each pass, we loop through the unplaced grobs from left to right.
+  // If the grob doesn't overlap the right-most affected position, we place it
+  // (and then update the right-most affected position to point to the right
+  // edge of the just-placed grob).  Otherwise, we skip it until the next pass.
   while (!elements.empty ())
     {
-      last_affected_position[UP] = -infinity_f;
-      last_affected_position[DOWN] = -infinity_f;
-      /* do one pass */
-      for (vsize i = elements.size (); i--;)
+      Drul_array<Real> last_end (-infinity_f, -infinity_f);
+      vector<Grob *> skipped_elements;
+      for (vsize i = l2r ? 0 : elements.size ();
+           l2r ? i < elements.size () : i--;
+           l2r ? i++ : 0)
         {
-          Direction dir = get_grob_direction (elements[i]);
+          Grob *elt = elements[i];
+          Real padding
+            = robust_scm2double (elt->get_property ("outside-staff-padding"),
+                                 Axis_group_interface
+                                 ::get_default_outside_staff_padding ());
+          Real horizon_padding
+            = robust_scm2double (elt->get_property ("outside-staff-horizontal-padding"), 0.0);
+          Interval x_extent = elt->extent (x_common, X_AXIS);
+          x_extent.widen (horizon_padding);
+
+          Direction dir = get_grob_direction (elt);
           if (dir == CENTER)
             {
               warning (_ ("an outside-staff object should have a direction, defaulting to up"));
               dir = UP;
             }
 
-          Box b (elements[i]->extent (x_common, X_AXIS),
-                 elements[i]->extent (y_common, Y_AXIS));
-          SCM horizon_padding_scm = elements[i]->get_property ("outside-staff-horizontal-padding");
-          Real horizon_padding = robust_scm2double (horizon_padding_scm, 0.0);
+          if (x_extent[LEFT] <= last_end[dir] && polite)
+            {
+              skipped_elements.push_back (elt);
+              continue;
+            }
+          last_end[dir] = x_extent[RIGHT];
 
-          if (b[X_AXIS][LEFT] - 2 * horizon_padding < last_affected_position[dir])
+          Skyline_pair *v_orig = unsmob<Skyline_pair> (elt->get_property ("vertical-skylines"));
+          if (!v_orig || v_orig->is_empty ())
             continue;
 
-          if (!b[X_AXIS].is_empty () && !b[Y_AXIS].is_empty ())
+          // Find the riders associated with this grob, and merge their
+          // skylines with elt's skyline.
+          typedef multimap<Grob *, Grob *>::const_iterator GrobMapIterator;
+          pair<GrobMapIterator, GrobMapIterator> range = riders.equal_range (elt);
+          vector<Skyline_pair> rider_v_skylines;
+          for (GrobMapIterator j = range.first; j != range.second; j++)
             {
-              boxes.clear ();
-              boxes.push_back (b);
-              Skyline other = Skyline (boxes, horizon_padding, X_AXIS, -dir);
-              Real padding = robust_scm2double (elements[i]->get_property ("outside-staff-padding"), 0.5);
-              Real dist = (*skylines)[dir].distance (other) + padding;
-
-              if (dist > 0)
+              Grob *rider = j->second;
+              Skyline_pair *v_rider = unsmob<Skyline_pair> (rider->get_property ("vertical-skylines"));
+              if (v_rider)
                 {
-                  b.translate (Offset (0, dir * dist));
-                  elements[i]->translate_axis (dir * dist, Y_AXIS);
+                  Skyline_pair copy (*v_rider);
+                  copy.shift (rider->relative_coordinate (x_common, X_AXIS));
+                  copy.raise (rider->relative_coordinate (y_common, Y_AXIS));
+                  rider_v_skylines.push_back (copy);
                 }
-              skylines->insert (b, 0, X_AXIS);
-              elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F);
-              last_affected_position[dir] = b[X_AXIS][RIGHT];
             }
-
-          /*
-            Ugh: quadratic. --hwn
-           */
-          elements.erase (elements.begin () + i);
+          Skyline_pair v_skylines (*v_orig);
+          v_skylines.shift (elt->relative_coordinate (x_common, X_AXIS));
+          v_skylines.raise (elt->relative_coordinate (y_common, Y_AXIS));
+          v_skylines.merge (Skyline_pair (rider_v_skylines));
+
+          avoid_outside_staff_collisions (elt,
+                                          &v_skylines,
+                                          padding,
+                                          horizon_padding,
+                                          (*all_v_skylines)[dir],
+                                          (*all_paddings)[dir],
+                                          (*all_horizon_paddings)[dir],
+                                          dir);
+
+          elt->set_property ("outside-staff-priority", SCM_BOOL_F);
+          (*all_v_skylines)[dir].push_back (v_skylines);
+          (*all_paddings)[dir].push_back (padding);
+          (*all_horizon_paddings)[dir].push_back (horizon_padding);
         }
+      swap (elements, skipped_elements);
+      skipped_elements.clear ();
     }
 }
 
-bool
-Axis_group_interface::has_outside_staff_parent (Grob *me)
+// If the Grob has a Y-ancestor with outside-staff-priority, return it.
+// Otherwise, return 0.
+Grob *
+Axis_group_interface::outside_staff_ancestor (Grob *me)
 {
-  return (me
-          ? (scm_is_number (me->get_property ("outside-staff-priority"))
-             || has_outside_staff_parent (me->get_parent (Y_AXIS)))
-          : false);
+  Grob *parent = me->get_parent (Y_AXIS);
+  if (!parent)
+    return 0;
+
+  if (scm_is_number (parent->get_property ("outside-staff-priority")))
+    return parent;
+
+  return outside_staff_ancestor (parent);
 }
 
-// TODO: it is tricky to correctly handle skyline placement of cross-staff grobs.
+// It is tricky to correctly handle skyline placement of cross-staff grobs.
 // For example, cross-staff beams cannot be formatted until the distance between
 // staves is known and therefore any grobs that depend on the beam cannot be placed
 // until the skylines are known. On the other hand, the distance between staves should
@@ -722,8 +866,23 @@ Axis_group_interface::has_outside_staff_parent (Grob *me)
 // that there is no room for the cross-staff grob. It also means, of course, that
 // we don't get the benefits of skyline placement for cross-staff grobs.
 Skyline_pair
-Axis_group_interface::skyline_spacing (Grob *me, vector<Grob *> elements)
+Axis_group_interface::skyline_spacing (Grob *me)
 {
+  extract_grob_set (me, unsmob<Grob_array> (me->get_object ("vertical-skyline-elements")) ? "vertical-skyline-elements" : "elements", fakeelements);
+  vector<Grob *> elements (fakeelements);
+  for (vsize i = 0; i < elements.size (); i++)
+    /*
+      As a sanity check, we make sure that no grob with an outside staff priority
+      has a Y-parent that also has an outside staff priority, which would result
+      in two movings.
+    */
+    if (scm_is_number (elements[i]->get_property ("outside-staff-priority"))
+        && outside_staff_ancestor (elements[i]))
+      {
+        elements[i]->warning ("Cannot set outside-staff-priority for element and elements' Y parent.");
+        elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F);
+      }
+
   /* For grobs with an outside-staff-priority, the sorting function might
      call extent and cause suicide. This breaks the contract that is required
      for the STL sort function. To avoid this, we make sure that any suicides
@@ -737,39 +896,83 @@ Axis_group_interface::skyline_spacing (Grob *me, vector<Grob *> elements)
   Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
   Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
 
-  assert (y_common == me);
+  if (y_common != me)
+    {
+      me->programming_error("Some of my vertical-skyline-elements"
+                            " are outside my VerticalAxisGroup.");
+      y_common = me;
+    }
+
+  // A rider is a grob that is not outside-staff, but has an outside-staff
+  // ancestor.  In that case, the rider gets moved along with its ancestor.
+  multimap<Grob *, Grob *> riders;
 
   vsize i = 0;
-  vector<Box> boxes;
+  vector<Skyline_pair> inside_staff_skylines;
 
-  Skyline_pair skylines;
   for (i = 0; i < elements.size ()
        && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++)
-    if (!(to_boolean (elements[i]->get_property ("cross-staff")) || has_outside_staff_parent (elements[i])))
-      add_boxes (elements[i], x_common, y_common, &boxes, &skylines);
+    {
+      Grob *elt = elements[i];
+      Grob *ancestor = outside_staff_ancestor (elt);
+      if (!(to_boolean (elt->get_property ("cross-staff")) || ancestor))
+        add_interior_skylines (elt, x_common, y_common, &inside_staff_skylines);
+      if (ancestor)
+        riders.insert (pair<Grob *, Grob *> (ancestor, elt));
+    }
+
+  Skyline_pair skylines (inside_staff_skylines);
+
+  // These are the skylines of all outside-staff grobs
+  // that have already been processed.  We keep them around in order to
+  // check them for collisions with the currently active outside-staff grob.
+  Drul_array<vector<Skyline_pair> > all_v_skylines;
+  Drul_array<vector<Real> > all_paddings;
+  Drul_array<vector<Real> > all_horizon_paddings;
+  for (UP_and_DOWN (d))
+    {
+      all_v_skylines[d].push_back (skylines);
+      all_paddings[d].push_back (0);
+      all_horizon_paddings[d].push_back (0);
+    }
 
-  SCM padding_scm = me->get_property ("skyline-horizontal-padding");
-  Real padding = robust_scm2double (padding_scm, 0.1);
-  skylines.merge (Skyline_pair (boxes, padding, X_AXIS));
   for (; i < elements.size (); i++)
     {
       if (to_boolean (elements[i]->get_property ("cross-staff")))
         continue;
 
+      // Collect all the outside-staff grobs that have a particular priority.
       SCM priority = elements[i]->get_property ("outside-staff-priority");
       vector<Grob *> current_elts;
       current_elts.push_back (elements[i]);
       while (i + 1 < elements.size ()
-             && scm_is_eq (elements[i + 1]->get_property ("outside-staff-priority"), priority))
+             && ly_is_equal (elements[i + 1]->get_property ("outside-staff-priority"), priority))
         {
           if (!to_boolean (elements[i + 1]->get_property ("cross-staff")))
             current_elts.push_back (elements[i + 1]);
           ++i;
         }
 
-      add_grobs_of_one_priority (&skylines, current_elts, x_common, y_common);
+      add_grobs_of_one_priority (me,
+                                 &all_v_skylines,
+                                 &all_paddings,
+                                 &all_horizon_paddings,
+                                 current_elts,
+                                 x_common,
+                                 y_common,
+                                 riders);
     }
+
+  // Now everything in all_v_skylines has been shifted appropriately; merge
+  // them all into skylines to get the complete outline.
+  Skyline_pair other_skylines (all_v_skylines[UP]);
+  other_skylines.merge (Skyline_pair (all_v_skylines[DOWN]));
+  skylines.merge (other_skylines);
+
+  // We began by shifting my skyline to be relative to the common refpoint; now
+  // shift it back.
   skylines.shift (-me->relative_coordinate (x_common, X_AXIS));
+
   return skylines;
 }
 
@@ -780,9 +983,9 @@ Axis_group_interface::print (SCM smob)
   if (!debug_skylines)
     return SCM_BOOL_F;
 
-  Grob *me = unsmob_grob (smob);
+  Grob *me = unsmob<Grob> (smob);
   Stencil ret;
-  if (Skyline_pair *s = Skyline_pair::unsmob (me->get_property ("vertical-skylines")))
+  if (Skyline_pair *s = unsmob<Skyline_pair> (me->get_property ("vertical-skylines")))
     {
       ret.add_stencil (Lookup::points_to_line_stencil (0.1, (*s)[UP].to_points (X_AXIS))
                        .in_color (255, 0, 255));
@@ -796,7 +999,7 @@ MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_pure_staff_staff_spacing, 3)
 SCM
 Axis_group_interface::calc_pure_staff_staff_spacing (SCM smob, SCM start, SCM end)
 {
-  return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
+  return calc_maybe_pure_staff_staff_spacing (unsmob<Grob> (smob),
                                               true,
                                               scm_to_int (start),
                                               scm_to_int (end));
@@ -806,7 +1009,7 @@ MAKE_SCHEME_CALLBACK (Axis_group_interface, calc_staff_staff_spacing, 1)
 SCM
 Axis_group_interface::calc_staff_staff_spacing (SCM smob)
 {
-  return calc_maybe_pure_staff_staff_spacing (unsmob_grob (smob),
+  return calc_maybe_pure_staff_staff_spacing (unsmob<Grob> (smob),
                                               false,
                                               0,
                                               INT_MAX);
@@ -815,7 +1018,7 @@ Axis_group_interface::calc_staff_staff_spacing (SCM smob)
 SCM
 Axis_group_interface::calc_maybe_pure_staff_staff_spacing (Grob *me, bool pure, int start, int end)
 {
-  Grob *grouper = unsmob_grob (me->get_object ("staff-grouper"));
+  Grob *grouper = unsmob<Grob> (me->get_object ("staff-grouper"));
 
   if (grouper)
     {
@@ -828,18 +1031,6 @@ Axis_group_interface::calc_maybe_pure_staff_staff_spacing (Grob *me, bool pure,
   return me->get_maybe_pure_property ("default-staff-staff-spacing", pure, start, end);
 }
 
-Real
-Axis_group_interface::minimum_distance (Grob *g1, Grob *g2, Axis a)
-{
-  SCM sym = ly_symbol2scm ((a == Y_AXIS) ? "vertical-skylines" : "horizontal-skylines");
-
-  Skyline_pair *s1 = Skyline_pair::unsmob (g1->get_property (sym));
-  Skyline_pair *s2 = Skyline_pair::unsmob (g2->get_property (sym));
-  if (s1 && s2)
-    return (*s1)[DOWN].distance ((*s2)[UP]);
-  return 0;
-}
-
 ADD_INTERFACE (Axis_group_interface,
                "An object that groups other layout objects.",
 
@@ -852,7 +1043,6 @@ ADD_INTERFACE (Axis_group_interface,
                "bound-alignment-interfaces "
                "default-staff-staff-spacing "
                "elements "
-               "max-stretch "
                "no-alignment "
                "nonstaff-nonstaff-spacing "
                "nonstaff-relatedstaff-spacing "
@@ -865,7 +1055,6 @@ ADD_INTERFACE (Axis_group_interface,
                "staff-grouper "
                "staff-staff-spacing "
                "system-Y-offset "
-               "vertical-skylines "
                "X-common "
                "Y-common "
               );