On Wed, Sep 26, 2012 at 4:15 AM,
address@hidden <address@hidden> wrote:
Hey all,
As was the case in a few of my previous projects, before I start something new I make architecture changes that facilitate my work. Working on 2801, I've realized that any multi-pass algorithm for the spacing of grobs is difficult because results of callback calculations are always cached. So triggering callbacks a second time is, in the current architecture, impractical and requires a fair bit of kludgery.
Are you proposing not to cache callbacks at all? That sounds like a real performance killer to me; we would probably end up re-typesetting each beam hundreds of times.
No, I'm proposing to find way to mark things as dirty so that they are recalculated.
By the way, the problem is not only in the caching of callbacks; there are also many other places with side effects (calls to set_property, translate_axis, suicide, etc).
Exactly - the proposal here is to get rid of the call to translate_axis in axis-group-interface.cc, which is the biggest side effect in the code base in terms of the number and variety of grobs affected. This'll make it easier to mark things as dirty so that multiple passes can happen.
To start this process, I'd like to expand the role of the side-position-interface significantly. All grobs would use this interface for their X and Y offsets and they would have two different grob arrays for X and Y side-position-elements. This would allow me to eliminate two things:
1) parents. Grobs are X/Y aligned to parents, but these parents could be elements in the side-position-elements array. Functions like get_parent, which could be kept around for legacy reasons, could return the first element of these arrays for a given axis and raise a warning if there are multiple elements.
If you get rid of unique parents, what would X-offset mean? Would it be relative to the System? The first element of side-position-elements array?
Relative to the skyline of the elements of the side-position-elements array.
2) outside-staff-priority. Saying a grob has outside staff priority is the same thing as saying that a grob has as its Y side support elements all inside-staff grobs plus all grobs with lower outside staff priority. A callback creating the side-position-elements arrays could do the sorting that takes place in Axis_group_interface::skyline_spacing.
I think you'll have trouble making this fully callbacky/functional. For example, we lay out the outside-staff grobs in a very particular order (the left-to-right layout thing), which we don't know ahead of time. That is, until we get _all_ of the outside-staff grobs together, we don't know which grobs have to depend on which other grobs. That means it isn't really possible for each grob to determine its own position; there needs to be one grob that lays them out simultaneously. The same issue will come up, I think in laying out Accidentals and VerticalAxisGroups.
You're right that, in general, any time that a collecting grob does some type of organizing, this type of problem will come up. However, there are ways around it. For example, a grob can get the elements array from its vertical alignment or system, sort it from left to right, and trigger callbacks for all grobs to the left. This avoids an overarching positioning grob while still achieving the same effect.
At some point, I had grand plans to formalize this problem by having two distinct kinds of properties: one that is user-overridable using callbacks, and one that is internal and gets set by other grobs as a side-effect. Everything would have explicit dependencies so that caches could be invalidated. I even started to write a proof-of-concept in scala, but I never finished it...
My thinking is that in order to make dependencies easier to handle and maintain, we need to reduce the number of side effects like translate_axis and set_property.
The benefits of this are twofold:
1) All work on a multi-pass algorithm could be done with respect to side-positioning, making it simpler to find bugs and modify code.
Not all positioning is side-positioning.
True - my goal is to see if all positioning can be articulated this way. For example, ScriptColumn could have used translate_axis, but whoever wrote it made the good decision to use side-position-interface. I think this grob could be eliminated entirely if all scripts in a script column had a function that calculated the side-position-elements grob-array using the sorting algorithm at the heart of script-column.cc.
Another way to think of this is that, in general, we'd try to eliminate grobs like NoteColumn, ScriptColumn, DynamicLineSpanner, etc that only do traffic-coppery. Or, inversely, we'd say that positioning only happens via traffic-cop grobs and no grob has the right to position itself. But it seems like we need to pick one.
2) A call to translate_axis in avoid_outside_staff_collisions would be eliminated, and translate_axis is bad: it goes against the callback model at the core of LilyPond layout.
Agreed, but this is just one instance of translate_axis, which is just one example of a side-effect in lilypond. Is your eventual goal to remove them all?
Yes - that'd be great. That'll make explicit dependencies a lot easier to handle - everything can be calculated in terms of callbacks.
The disadvantage is that this results in the construction of many more skylines (one for each call to Side_position_interface::skyline_side_position). How this will impact performance is uncertain, but it'd probably require more optimization in skyline.cc and/or caching of skylines.
I would suggest that you completely ignore performance in favor of a clean design. Performance can come later.
I agree.
I haven't been in LilyPond long enough to know how conceptual models have evolved over the years, but I think that there are two competing models in spacing and we need to choose one. Either there are collection grobs that space their elements (like NoteCollision) or grobs that determine their own spacing from a collection of grobs (like Script). I am leaning towards the latter because it seems less prone to error. In the former, if a grob is placed under the auspices of two Y-axis positioning grobs, we do not know which one take precedence. In the latter, grobs control their own spacing, so there is no doubt.
To keep the main thing the main thing, the goal is to be able to wipe certain caches, restore the original callbacks, and know that all grobs properties that depended on the restored property will also be recalculated. My idea is an idea for simplifying LilyPond so that this work is easier, but there is no point in doing that if it won't help reach that goal. I'm open to any and all suggestions.
Cheers,
MS