Re: Project - Eliminating grob parents and outside-staff-priority
"m...@mikesolomon.org" writes: > It is true that line-breaking is a centralized option based on what > the toplevel-book-handler is, but it should be as lightweight as > possible. I think that the smaller we can keep paper-book.cc and > paper-score.cc, the better. I've been saying this for a couple years, > but I'd prefer for Book and PaperScore to be grobs so that even they > could use the callback model. At that point, line breaking could just > be controlled by callbacks. Distributing algorithms in that manner without central control/arbitration means O(n^2) complexity at least. It tends to lend itself better to parallelizing, but when your average system does not have thousands of processors, that advantage remains very limited. Of course, a half-baked not-well-understood global hackery touching stuff in lots of indiscriminate places is not what this is about. The interdependencies need to be stated as local relations, of course. It is just that the resolution is to be done globally. Of course this necessitates that the dependencies are formulated in a _systematic_ manner and in the same way everywhere, using well-crafted interfaces/ways of specification rather than in willy-nilly adhoc jumbles of callbacks. -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 30 sept. 2012, at 14:29, David Kastrup wrote:
> "m...@mikesolomon.org" writes:
>
>> On 30 sept. 2012, at 14:16, Janek Warchoł wrote:
>>
>>> Hi,
>>>
>>> interesting discussion, i learn a lot.
>>>
>>> On Sun, Sep 30, 2012 at 11:39 AM, David Kastrup wrote:
Basically, a grob says "I want to have this and that information for
making my positioning" and LilyPond says "You can't get it right now".
Then the grob says "ok, I'll do a tentative positioning", and LilyPond
will come back with more information later and ask again.
>>
>> Just to clarify things for anyone following the thread: this is not
>> currently how LilyPond works, but I'm assuming what you're proposing
>> is a suggestion for a model.
>>
>> It's an interesting idea for grobs to ping a sort of central hive
>> ("LilyPond" in your text above) to know what information they can
>> access and when. This'd require a major change to the architecture -
>> currently, grobs specify in their request whether they want tentative
>> or permanent information via the use of functions like
>> Grob::pure_relative_y_coordinate versus Grob::relative_coordinate.
>> I'm worried about having a sort of centralized brain that tells grobs
>> what they can and can't know - sounds Kafka-esque. I like the
>> decentralized model where grobs, via their callbacks, self-police for
>> what information they need from other grobs and when it's ok to get
>> it.
>
> I have my doubts that you can do a sensible circular dependency
> resolution strategy in a purely local manner. In fact, the current
> pure/unpure distinction is based on before/after linebreaking, a
> centralized operation.
>
It is true that line-breaking is a centralized option based on what the
toplevel-book-handler is, but it should be as lightweight as possible. I think
that the smaller we can keep paper-book.cc and paper-score.cc, the better.
I've been saying this for a couple years, but I'd prefer for Book and
PaperScore to be grobs so that even they could use the callback model. At that
point, line breaking could just be controlled by callbacks. This would also
pave the way for better Prob / Grob integration - it is currently difficult to
get toplevel markups and systems to play nicely because they are outside of
this callback model.
The current pure/unpure distinction is based on what people ask for and when.
Pure offsets and extents are used until the dim_cache_ is filled, at which
point real offsets and extents are used. As a convention this is before and
after line breaking, but there are places where pure properties are requested
after linebreaking and non-pure properties are requested before.
Cheers,
MS
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
"m...@mikesolomon.org" writes:
> On 30 sept. 2012, at 14:16, Janek Warchoł wrote:
>
>> Hi,
>>
>> interesting discussion, i learn a lot.
>>
>> On Sun, Sep 30, 2012 at 11:39 AM, David Kastrup wrote:
>>> Basically, a grob says "I want to have this and that information for
>>> making my positioning" and LilyPond says "You can't get it right now".
>>> Then the grob says "ok, I'll do a tentative positioning", and LilyPond
>>> will come back with more information later and ask again.
>
> Just to clarify things for anyone following the thread: this is not
> currently how LilyPond works, but I'm assuming what you're proposing
> is a suggestion for a model.
>
> It's an interesting idea for grobs to ping a sort of central hive
> ("LilyPond" in your text above) to know what information they can
> access and when. This'd require a major change to the architecture -
> currently, grobs specify in their request whether they want tentative
> or permanent information via the use of functions like
> Grob::pure_relative_y_coordinate versus Grob::relative_coordinate.
> I'm worried about having a sort of centralized brain that tells grobs
> what they can and can't know - sounds Kafka-esque. I like the
> decentralized model where grobs, via their callbacks, self-police for
> what information they need from other grobs and when it's ok to get
> it.
I have my doubts that you can do a sensible circular dependency
resolution strategy in a purely local manner. In fact, the current
pure/unpure distinction is based on before/after linebreaking, a
centralized operation.
--
David Kastrup
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 30 sept. 2012, at 14:16, Janek Warchoł wrote:
> Hi,
>
> interesting discussion, i learn a lot.
>
> On Sun, Sep 30, 2012 at 11:39 AM, David Kastrup wrote:
>> Basically, a grob says "I want to have this and that information for
>> making my positioning" and LilyPond says "You can't get it right now".
>> Then the grob says "ok, I'll do a tentative positioning", and LilyPond
>> will come back with more information later and ask again.
>
> I have no idea whether there are any not-very-experienced developers
> (or users) following this thread, but if they are, i'm sure this is a
> very nice and helpful explanation for them :)
>
> cheers,
> Janek
Just to clarify things for anyone following the thread: this is not currently
how LilyPond works, but I'm assuming what you're proposing is a suggestion for
a model.
It's an interesting idea for grobs to ping a sort of central hive ("LilyPond"
in your text above) to know what information they can access and when. This'd
require a major change to the architecture - currently, grobs specify in their
request whether they want tentative or permanent information via the use of
functions like Grob::pure_relative_y_coordinate versus
Grob::relative_coordinate. I'm worried about having a sort of centralized
brain that tells grobs what they can and can't know - sounds Kafka-esque. I
like the decentralized model where grobs, via their callbacks, self-police for
what information they need from other grobs and when it's ok to get it.
Cheers,
MS
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
Hi, interesting discussion, i learn a lot. On Sun, Sep 30, 2012 at 11:39 AM, David Kastrup wrote: > Basically, a grob says "I want to have this and that information for > making my positioning" and LilyPond says "You can't get it right now". > Then the grob says "ok, I'll do a tentative positioning", and LilyPond > will come back with more information later and ask again. I have no idea whether there are any not-very-experienced developers (or users) following this thread, but if they are, i'm sure this is a very nice and helpful explanation for them :) cheers, Janek ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 30 sept. 2012, at 11:39, David Kastrup wrote: > David Kastrup writes: > >> "m...@mikesolomon.org" writes: >> >>> On 29 sept. 2012, at 19:54, m...@mikesolomon.org wrote: >>> >>>On 29 sept. 2012, at 19:53, "Keith OHara" >>>wrote: >>> >>>On Sat, 29 Sep 2012 10:30:32 -0700, m...@mikesolomon.org >>> wrote: >>> >>> >>>The way you're using "tentative" is almost exactly how >>>pure properties are used in LilyPond. >>> >>>Specifically, 'pure-height being the estimated vertical extent >>>before line-breaking, while 'height is its extent after >>>line-breaking. >>> >>>If there are distinct properties to describe the position at >>>different stages, then each property can be evaluated just >>>once (as HanWen suggested, and as Mike agreed 100%). >>> >>> More thinking. I'm not enthusiastic about stages - it is a top down >>> approach that locks us into certain points of evaluation. What if we >>> decided to add or get rid of a stage? Would we need to create things >>> like unpure-pure-containers for various stages? What qualifies as a >>> stage? >> >> Dependencies, I should guess. A "stage" is where we break circular >> dependencies. > > Basically, a grob says "I want to have this and that information for > making my positioning" and LilyPond says "You can't get it right now". > Then the grob says "ok, I'll do a tentative positioning", and LilyPond > will come back with more information later and ask again. > > Now the problem here is when we are getting oscillation or even just a > converging process. If there is convergence involved, we are better off > calculation the _relation_ between the positionings. In a linear > optimization problem, those define the surface plane of a simplex (which > has possible solutions inside, impossible solutions outside, and where > we are looking for the furthest distance from 0 as the goal of > optimization) as a constraint. Intersecting with other > surfaces/constraints gives us the total solution space, and travelling > outside along its edges (which are the intersection of two planes) moves > us to the optimal solution. > > Doing this iteratively means jumping around on the inside of the > simplex. Each jump may be quite faster than determining the active > boundaries of the simplex, but of course the simplex method focuses on > _those_ pairings of parameters/positioning which are actually valid > tradeoffs. And since it is an efficient method, it does not get > confused when the heuristics go wrong. I'm not completely sure that I follow what you're saying (I don't know anything about the internals of the simplex method) but if you mean that recalculating tentative property values may result in a series of values that doesn't converge towards anything, then yes, you are right. Most tentative properties will likely have convergent behavior, meaning that as more information becomes available, they'll get closer and closer to actual properties. However, there is no systematic way to enforce this. I've spent a lot of time thinking about making linear programming possible in LilyPond and have come to the conclusion that aspects of LilyPond's logic make it such that decisions are not linear. The classic is: --) We do outside staff positioning, at which point element A gets shifted up. --) Element B, not being able to be placed between element A and the staff, gets placed above element A. --) We redo outside staff positioning after cross-staff-grobs' vertical skylines are calculated. --) Element A is now shifted higher up. --) Element B is now able to be stashed between element A and the staff. That is a leap in heights (we go from having element B in the skyline to not). So discussing convergence is really difficult - I think the best we can do are heuristics to decide when to settle on ok-enough values. Cheers, MS ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
David Kastrup writes: > "m...@mikesolomon.org" writes: > >> On 29 sept. 2012, at 19:54, m...@mikesolomon.org wrote: >> >> On 29 sept. 2012, at 19:53, "Keith OHara" >> wrote: >> >> On Sat, 29 Sep 2012 10:30:32 -0700, m...@mikesolomon.org >> wrote: >> >> >> The way you're using "tentative" is almost exactly how >> pure properties are used in LilyPond. >> >> Specifically, 'pure-height being the estimated vertical extent >> before line-breaking, while 'height is its extent after >> line-breaking. >> >> If there are distinct properties to describe the position at >> different stages, then each property can be evaluated just >> once (as HanWen suggested, and as Mike agreed 100%). >> >> More thinking. I'm not enthusiastic about stages - it is a top down >> approach that locks us into certain points of evaluation. What if we >> decided to add or get rid of a stage? Would we need to create things >> like unpure-pure-containers for various stages? What qualifies as a >> stage? > > Dependencies, I should guess. A "stage" is where we break circular > dependencies. Basically, a grob says "I want to have this and that information for making my positioning" and LilyPond says "You can't get it right now". Then the grob says "ok, I'll do a tentative positioning", and LilyPond will come back with more information later and ask again. Now the problem here is when we are getting oscillation or even just a converging process. If there is convergence involved, we are better off calculation the _relation_ between the positionings. In a linear optimization problem, those define the surface plane of a simplex (which has possible solutions inside, impossible solutions outside, and where we are looking for the furthest distance from 0 as the goal of optimization) as a constraint. Intersecting with other surfaces/constraints gives us the total solution space, and travelling outside along its edges (which are the intersection of two planes) moves us to the optimal solution. Doing this iteratively means jumping around on the inside of the simplex. Each jump may be quite faster than determining the active boundaries of the simplex, but of course the simplex method focuses on _those_ pairings of parameters/positioning which are actually valid tradeoffs. And since it is an efficient method, it does not get confused when the heuristics go wrong. -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
"m...@mikesolomon.org" writes: > On 29 sept. 2012, at 19:54, m...@mikesolomon.org wrote: > > On 29 sept. 2012, at 19:53, "Keith OHara" > wrote: > > On Sat, 29 Sep 2012 10:30:32 -0700, m...@mikesolomon.org > wrote: > > > The way you're using "tentative" is almost exactly how > pure properties are used in LilyPond. > > Specifically, 'pure-height being the estimated vertical extent > before line-breaking, while 'height is its extent after > line-breaking. > > If there are distinct properties to describe the position at > different stages, then each property can be evaluated just > once (as HanWen suggested, and as Mike agreed 100%). > > More thinking. I'm not enthusiastic about stages - it is a top down > approach that locks us into certain points of evaluation. What if we > decided to add or get rid of a stage? Would we need to create things > like unpure-pure-containers for various stages? What qualifies as a > stage? Dependencies, I should guess. A "stage" is where we break circular dependencies. -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 29 sept. 2012, at 19:54, m...@mikesolomon.org wrote:
>
> On 29 sept. 2012, at 19:53, "Keith OHara" wrote:
>
>> On Sat, 29 Sep 2012 10:30:32 -0700, m...@mikesolomon.org
>> wrote:
>>
>>>
>>> The way you're using "tentative" is almost exactly how pure properties are
>>> used in LilyPond.
>>
>> Specifically, 'pure-height being the estimated vertical extent before
>> line-breaking, while 'height is its extent after line-breaking.
>>
>> If there are distinct properties to describe the position at different
>> stages, then each property can be evaluated just once (as HanWen suggested,
>> and as Mike agreed 100%).
More thinking. I'm not enthusiastic about stages - it is a top down approach
that locks us into certain points of evaluation. What if we decided to add or
get rid of a stage? Would we need to create things like unpure-pure-containers
for various stages? What qualifies as a stage? Could users make custom stages?
Furthermore, the idea of properties being pure in LilyPond is impossible to
police. The code almost guarantees that won't be pure, as once the dim_cache_
of a grob is filled, it gives that value instead of the result of a function
call (see Grob::pure_relative_y_coordinate, specifically line 350 of grob.cc as
of 9e605a1bb6644d89cf110f20cb6d46bb0339fca7). I like Keith's idea of
"tentative" and "permanent". The model I'm thinking of is:
--) LilyPond evaluates all callbacks as permanent unless tentative is
explicitly asked for.
--) Permanent properties are stashed in a cache that cannot be erased.
--) Tentative properties may (i.e. heights) or may not (i.e. color) be cached
depending on how we choose to optimize LilyPond. It is the responsibility of
the coder, if she wants an uncached property, to wipe the cache.
--) Most importantly, all notions of pure callbacks disappear. It is the job
of functions to police themselves. For example, a function Grob::has_full_x
can be created to determine if a grob has an X position with respect to the
system. It'd check to see if the dim_cache_[X_AXIS].offset_ of a Paper_column
pointing to a real location in memory. The answer will be false if
System::break_into_pieces has been called and true otherwise. Then, we could
do something like:
MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Slur, height, 1, 2, "");
SCM
Slur::height (SCM smob, SCM begscm, SCM endscm)
{
Grob *me = unsmob_grob (smob);
if (me->has_full_x ())
return permanent_height (me);
int beg = robust_scm2int (begscm, 0);
int end = robust_scm2int (endscm, 0);
return tentative_height (me, beg, end);
}
This'd allow to entirely get rid of all the pure callback lists as well as
unpure-pure-containers.
--) Both permanent and tentative properties can result in calls to
set_property, set_object, translate_axis, and suicide. All setters should be
used sparingly and internally to cache values (like we do for minimum
translations, for example). We can police this via warnings and errors.
Cheers,
MS
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 29 sept. 2012, at 19:53, "Keith OHara" wrote: > On Sat, 29 Sep 2012 10:30:32 -0700, m...@mikesolomon.org > wrote: > >> >> The way you're using "tentative" is almost exactly how pure properties are >> used in LilyPond. > > Specifically, 'pure-height being the estimated vertical extent before > line-breaking, while 'height is its extent after line-breaking. > > If there are distinct properties to describe the position at different > stages, then each property can be evaluated just once (as HanWen suggested, > and as Mike agreed 100%). > >> >> I think all property look-ups should be pure until one is absolutely certain >> that the property won't change, at which point the unpure value should be >> cached and returned for both pure and unpure queries (impure sounds too >> religious, thus unpure). The pure properties need not always return the >> same value - they can get closer and closer to the unpure as more and more >> information gets determined. > > This is the opposite approach, where some "properties" are not permanent at > all. The word 'tentative' is a better label than 'pure', because pure > functions would always return the same value given the same arguments. > True dat. Someone wanna do a perl one-line replace subbing in tenative for pure and post the patch? :-) Cheers, MS ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On Sat, 29 Sep 2012 10:30:32 -0700, m...@mikesolomon.org wrote: The way you're using "tentative" is almost exactly how pure properties are used in LilyPond. Specifically, 'pure-height being the estimated vertical extent before line-breaking, while 'height is its extent after line-breaking. If there are distinct properties to describe the position at different stages, then each property can be evaluated just once (as HanWen suggested, and as Mike agreed 100%). I think all property look-ups should be pure until one is absolutely certain that the property won't change, at which point the unpure value should be cached and returned for both pure and unpure queries (impure sounds too religious, thus unpure). The pure properties need not always return the same value - they can get closer and closer to the unpure as more and more information gets determined. This is the opposite approach, where some "properties" are not permanent at all. The word 'tentative' is a better label than 'pure', because pure functions would always return the same value given the same arguments. ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 29 sept. 2012, at 18:34, Keith OHara wrote:
> Han-Wen Nienhuys gmail.com> writes:
>
>> I think it is a much clearer abstraction to decide that each property
>> can only be evaluated once, and that everything should be driven by
>> callbacks. In fact, one thing I would suggest looking at is removing
>> {before,after}_line_breaking which breaks this model somewhat.
>>
>
> Should that apply to properties that describe positioning of objects?
> Often LilyPond needs tentative positions for objects.
>
> For example, when setting note-spacing constraints, the separation of staves
> is
> taken to be large enough that items do not interfere between staves. The
> widths
> of text items are ignored, based on their extra-spacing-* properties. Rests
> avoiding beams have a tentative position. Some repeated accidentals on tied
> notes exist, but may disappear.
>
> The note-spacing code uses skylines, which depend on positions for the
> enclosed
> objects, and wants tentative positions appropriate to this phase of layout.
>
The way you're using "tentative" is almost exactly how pure properties are used
in LilyPond. The only example that doesn't work that way is the accidental
one, which I believe is a bug in LilyPond - I want to say that the space is
reserved even after the accidental is killed off (I'd have to verify that).
> One way to organize these phases of layout is by registering callbacks to be
> performed (or maybe in future reset) between phases:
> before/after-line-breaking.
>
> The alternative organizational method in the code today is religious
> observance:
> for it is written, On the day of Note-Spacing, thou shalt avert thine eyes
> from
> the stems, for stems keep the company of beams, and beams are impure, thus to
> seek knowledge of the tip of a stem would be impure.
>
>
I am a fan of the second over the first. I think all property look-ups should
be pure until one is absolutely certain that the property won't change, at
which point the unpure value should be cached and returned for both pure and
unpure queries (impure sounds too religious, thus unpure). The pure properties
need not always return the same value - they can get closer and closer to the
unpure as more and more information gets determined. Cached pure values for
Items can be flushed at any point if someone wants a potentially better
approximation, at which point the calculation would be redone and the cache
restocked.
Cheers,
MS
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
Han-Wen Nienhuys gmail.com> writes:
> I think it is a much clearer abstraction to decide that each property
> can only be evaluated once, and that everything should be driven by
> callbacks. In fact, one thing I would suggest looking at is removing
> {before,after}_line_breaking which breaks this model somewhat.
>
Should that apply to properties that describe positioning of objects?
Often LilyPond needs tentative positions for objects.
For example, when setting note-spacing constraints, the separation of staves is
taken to be large enough that items do not interfere between staves. The
widths
of text items are ignored, based on their extra-spacing-* properties. Rests
avoiding beams have a tentative position. Some repeated accidentals on tied
notes exist, but may disappear.
The note-spacing code uses skylines, which depend on positions for the enclosed
objects, and wants tentative positions appropriate to this phase of layout.
One way to organize these phases of layout is by registering callbacks to be
performed (or maybe in future reset) between phases:
before/after-line-breaking.
The alternative organizational method in the code today is religious
observance:
for it is written, On the day of Note-Spacing, thou shalt avert thine eyes from
the stems, for stems keep the company of beams, and beams are impure, thus to
seek knowledge of the tip of a stem would be impure.
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On Sat, Sep 29, 2012 at 11:35 AM, m...@mikesolomon.org
wrote:
>
> On 29 sept. 2012, at 10:59, Han-Wen Nienhuys wrote:
>
>> On Wed, Sep 26, 2012 at 10:40 PM, David Kastrup wrote:
>>> Han-Wen Nienhuys writes:
>>>
In order to do cache invalidation, you will have to construct the
reverse graph. If A.x depends on B.y, now A points to B. For proper
cache invalidation, if B.y changes, then A.x becomes invalid. This
means that A has to store a back-reference to B. Hence all pointers
have to be stored both ways (including inverting 1-N relations into
N-1 relations), and the both-way links have to be rewritten correctly
during line breaking.
>>>
>>> You can assign a generational count to properties. If the generational
>>> count of any dependency is higher than that of the dependent property,
>>> it needs to get regenerated. As long as the dependencies don't get lost
>>> (and we use arbitrary size integers, resetting for each session), this
>>> should be pretty straightforward and not require backwards links. It
>>> "just" requires double-checking your dependencies for change.
>>
>> But since the dependencies are also properties that could be
>> invalidated, you'd have to recurse , so each property access would
>> potentially expand into an almost infinite number of get_property
>> calls.
>>
>> I think it is a much clearer abstraction to decide that each property
>> can only be evaluated once, and that everything should be driven by
>> callbacks. In fact, one thing I would suggest looking at is removing
>> {before,after}_line_breaking which breaks this model somewhat.
>>
>
> I agree 110%. The only corollary I'd add, which comes from my recent work,
> is that pure properties be re-evaluatable all the time (meaning that one
> should be allowed to arbitrarily flush the cache) to store better and better
> approximations of things. For example, if one wants the pure heights of
> cross-staff beamed stems, the approximation one can get before line breaking
> is worse than that which one can get after. After line breaking, one could
> theoretically run beam quanting using the pure heights and actual X
> positions, whereas before, these X positions don't exist. So, pure
> properties in LilyPond become progressively more accurate as they go
> downstream, and once someone is positive that all the information is there to
> evaluate the actual property, get_property (or get_extent or whatever) is
> called.
pure-properties are misnamed. If they are always are recomputed, they
should be called methods or even pure functions and not properties.
Of course, if there is a cache, you have to think about a simple and
rigorous scheme to know when the cache can be thrown away; the real
problem is about caching data based on other grobs, since invalidation
implies a lot more of pointer juggling
> I agree about (before,after)_line_breaking.
>
> The single biggest offenders of this model, in my mind, are to be found in
> the engraver stage. More specifically, I think that if we can get rid of the
> Tweak_engraver such that every property is initialized via the Grob::Grob
> (SCM basicprops) constructor (like in engraver.cc, for example) and not via
> set_property at the engraver stage, everything else will be easier.
You could make a separate routine that prepends sym/value pairs onto
the immutable list; I'm not certain that this would intrinsically buy
you anything, though.
--
Han-Wen Nienhuys - han...@xs4all.nl - http://www.xs4all.nl/~hanwen
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 29 sept. 2012, at 10:59, Han-Wen Nienhuys wrote:
> On Wed, Sep 26, 2012 at 10:40 PM, David Kastrup wrote:
>> Han-Wen Nienhuys writes:
>>
>>> In order to do cache invalidation, you will have to construct the
>>> reverse graph. If A.x depends on B.y, now A points to B. For proper
>>> cache invalidation, if B.y changes, then A.x becomes invalid. This
>>> means that A has to store a back-reference to B. Hence all pointers
>>> have to be stored both ways (including inverting 1-N relations into
>>> N-1 relations), and the both-way links have to be rewritten correctly
>>> during line breaking.
>>
>> You can assign a generational count to properties. If the generational
>> count of any dependency is higher than that of the dependent property,
>> it needs to get regenerated. As long as the dependencies don't get lost
>> (and we use arbitrary size integers, resetting for each session), this
>> should be pretty straightforward and not require backwards links. It
>> "just" requires double-checking your dependencies for change.
>
> But since the dependencies are also properties that could be
> invalidated, you'd have to recurse , so each property access would
> potentially expand into an almost infinite number of get_property
> calls.
>
> I think it is a much clearer abstraction to decide that each property
> can only be evaluated once, and that everything should be driven by
> callbacks. In fact, one thing I would suggest looking at is removing
> {before,after}_line_breaking which breaks this model somewhat.
>
I agree 110%. The only corollary I'd add, which comes from my recent work, is
that pure properties be re-evaluatable all the time (meaning that one should be
allowed to arbitrarily flush the cache) to store better and better
approximations of things. For example, if one wants the pure heights of
cross-staff beamed stems, the approximation one can get before line breaking is
worse than that which one can get after. After line breaking, one could
theoretically run beam quanting using the pure heights and actual X positions,
whereas before, these X positions don't exist. So, pure properties in LilyPond
become progressively more accurate as they go downstream, and once someone is
positive that all the information is there to evaluate the actual property,
get_property (or get_extent or whatever) is called.
I agree about (before,after)_line_breaking.
The single biggest offenders of this model, in my mind, are to be found in the
engraver stage. More specifically, I think that if we can get rid of the
Tweak_engraver such that every property is initialized via the Grob::Grob (SCM
basicprops) constructor (like in engraver.cc, for example) and not via
set_property at the engraver stage, everything else will be easier.
Cheers,
MS
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On Wed, Sep 26, 2012 at 10:40 PM, David Kastrup wrote:
> Han-Wen Nienhuys writes:
>
>> In order to do cache invalidation, you will have to construct the
>> reverse graph. If A.x depends on B.y, now A points to B. For proper
>> cache invalidation, if B.y changes, then A.x becomes invalid. This
>> means that A has to store a back-reference to B. Hence all pointers
>> have to be stored both ways (including inverting 1-N relations into
>> N-1 relations), and the both-way links have to be rewritten correctly
>> during line breaking.
>
> You can assign a generational count to properties. If the generational
> count of any dependency is higher than that of the dependent property,
> it needs to get regenerated. As long as the dependencies don't get lost
> (and we use arbitrary size integers, resetting for each session), this
> should be pretty straightforward and not require backwards links. It
> "just" requires double-checking your dependencies for change.
But since the dependencies are also properties that could be
invalidated, you'd have to recurse , so each property access would
potentially expand into an almost infinite number of get_property
calls.
I think it is a much clearer abstraction to decide that each property
can only be evaluated once, and that everything should be driven by
callbacks. In fact, one thing I would suggest looking at is removing
{before,after}_line_breaking which breaks this model somewhat.
--
Han-Wen Nienhuys - han...@xs4all.nl - http://www.xs4all.nl/~hanwen
___
lilypond-devel mailing list
lilypond-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and, outside-staff-priority
Mats Bengtsson writes: > On 09/27/2012 08:36 AM, lilypond-devel-requ...@gnu.org wrote: >>> A typical example of this is NoteCollision of N NoteColumns. The >>> >NoteColumns have to all move in a coordinated way, and the easiest way >>> >is to have a function (with local variables) that determines what has >>> >to happen. You might get around it, by having a bunch of properties >>> >instead, but you'd still have to store those somewhere, ie in the >>> >NoteCollision grob. >> Not necessarily, it'd just make computation time longer. If each >> note column had other concurrent note columns in its >> side-position-elements grob-array and we kept the same function from >> note-column.cc but rewrote it such that instead of translating axes >> by values it returned the offset value for a given note column, the >> function would be called N times for N note columns. It's a >> tradeoff between efficiency and consistency - I'm not sure which one >> is better, but I'm sure it's possible to eliminate the NoteCollision >> grob at the cost of redundancy. >> > The main issue is which solution is easiest to maintain and extend for > future LilyPond developers. To me, it seems like it's easier to get an > overview of an implementation where a single centralized entity > collects all the necessary information and takes the decisions, > compared to a decentralized implementation where the information and > logic is distributed over a number of different objects. There is not actually much of a difference regarding the maintenance level here as long as the information and logic is not distributed over a number of different _code_ passages. What we need is "to do x with y, you call z". z may be an API function, it may be a method of y. What we don't need is "to do x with y, you fiddle with y.z, try keeping w in sync by adding y.v here, and if there is a w.g that has a common q with y.t, you need to make sure that the pure callback of q.r is updated along with ..." You get the drift. -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and, outside-staff-priority
On 09/27/2012 08:36 AM, lilypond-devel-requ...@gnu.org wrote: A typical example of this is NoteCollision of N NoteColumns. The >NoteColumns have to all move in a coordinated way, and the easiest way >is to have a function (with local variables) that determines what has >to happen. You might get around it, by having a bunch of properties >instead, but you'd still have to store those somewhere, ie in the >NoteCollision grob. Not necessarily, it'd just make computation time longer. If each note column had other concurrent note columns in its side-position-elements grob-array and we kept the same function from note-column.cc but rewrote it such that instead of translating axes by values it returned the offset value for a given note column, the function would be called N times for N note columns. It's a tradeoff between efficiency and consistency - I'm not sure which one is better, but I'm sure it's possible to eliminate the NoteCollision grob at the cost of redundancy. The main issue is which solution is easiest to maintain and extend for future LilyPond developers. To me, it seems like it's easier to get an overview of an implementation where a single centralized entity collects all the necessary information and takes the decisions, compared to a decentralized implementation where the information and logic is distributed over a number of different objects. Admittedly, we already have many examples of the latter strategy in the current LilyPond implementation and I'm sure that it had contributed to the flexibility and power of the general framework. Whatever solution is selected, please don't forget to keep maintainability and generality as the main guiding principle. This seems to be sometimes missing from the discussions on the mailing list. /Mats ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 26 sept. 2012, at 21:51, Han-Wen Nienhuys wrote: > On Wed, Sep 26, 2012 at 9:17 PM, m...@mikesolomon.org > wrote: > >> 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. > > The reason for trafic-coppery is that for many positioning schemes, > there is no inherent order that can determine how two objects of the > same type (and hence, with the same set of callbacks) should be > typeset. > > A typical example of this is NoteCollision of N NoteColumns. The > NoteColumns have to all move in a coordinated way, and the easiest way > is to have a function (with local variables) that determines what has > to happen. You might get around it, by having a bunch of properties > instead, but you'd still have to store those somewhere, ie in the > NoteCollision grob. Not necessarily, it'd just make computation time longer. If each note column had other concurrent note columns in its side-position-elements grob-array and we kept the same function from note-column.cc but rewrote it such that instead of translating axes by values it returned the offset value for a given note column, the function would be called N times for N note columns. It's a tradeoff between efficiency and consistency - I'm not sure which one is better, but I'm sure it's possible to eliminate the NoteCollision grob at the cost of redundancy. > >> 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. > > I'm all for removing side effects, but you can pursue that separately > without trying to rewrite the backend. My goal is not to rewrite the backend. My goal is to come up with a generalized way to do multiple passes at many places in the compilation process, and the best way seems to be deleting certain cached properties. I'm all for other ideas, though. > > >> 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. > > Have you thought this through? > > In order to do cache invalidation, you will have to construct the > reverse graph. If A.x depends on B.y, now A points to B. For proper > cache invalidation, if B.y changes, then A.x becomes invalid. This > means that A has to store a back-reference to B. Hence all pointers > have to be stored both ways (including inverting 1-N relations into > N-1 relations), and the both-way links have to be rewritten correctly > during line breaking. I'm sure this is doable - it'd just be a royal pain. It'd meant that get_property would have to take the "me" grob as an argument and somehow make the grobs aware of each other. Cheers, MS ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
Han-Wen Nienhuys writes: > In order to do cache invalidation, you will have to construct the > reverse graph. If A.x depends on B.y, now A points to B. For proper > cache invalidation, if B.y changes, then A.x becomes invalid. This > means that A has to store a back-reference to B. Hence all pointers > have to be stored both ways (including inverting 1-N relations into > N-1 relations), and the both-way links have to be rewritten correctly > during line breaking. You can assign a generational count to properties. If the generational count of any dependency is higher than that of the dependent property, it needs to get regenerated. As long as the dependencies don't get lost (and we use arbitrary size integers, resetting for each session), this should be pretty straightforward and not require backwards links. It "just" requires double-checking your dependencies for change. -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On Wed, Sep 26, 2012 at 12:17 PM, m...@mikesolomon.org wrote: > On 26 sept. 2012, at 17:38, Joe Neeman wrote: > > On Wed, Sep 26, 2012 at 4:15 AM, m...@mikesolomon.org < > m...@mikesolomon.org> wrote: > > > 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. > If you want to construct one skyline for all the elements in that array, you need some way of finding their offsets relative to each other. How do you propose to do that without some notion of a common refpoint? 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. > For outside-staff positioning, I think you could achieve the same effect. For something more complicated, like TieColumn or AccidentalPlacement, I think it would be much more difficult (and more obfuscated) to do it with callbacks. > >> 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. > I gave this some thought a while ago, and concluded that it isn't possible to get rid of the traffic cops (however, I'd be happy to be proven wrong). My eventual decision was to have them everywhere. A grob could suggest its own position using a callback, and if no other grob wanted to override that, then the System grob would take the traffic cop role and set the grob's position to whatever its suggestion was. That way you could write a lot of the positioning code as callbacks, and the cops would only kick in where necessary. There were also explicit dependencies so you could figure out which grob was in charge of positioning for which other grob. Cheers, Joe ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On Wed, Sep 26, 2012 at 9:17 PM, m...@mikesolomon.org wrote: > 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. The reason for trafic-coppery is that for many positioning schemes, there is no inherent order that can determine how two objects of the same type (and hence, with the same set of callbacks) should be typeset. A typical example of this is NoteCollision of N NoteColumns. The NoteColumns have to all move in a coordinated way, and the easiest way is to have a function (with local variables) that determines what has to happen. You might get around it, by having a bunch of properties instead, but you'd still have to store those somewhere, ie in the NoteCollision grob. > 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. I'm all for removing side effects, but you can pursue that separately without trying to rewrite the backend. > 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. Have you thought this through? In order to do cache invalidation, you will have to construct the reverse graph. If A.x depends on B.y, now A points to B. For proper cache invalidation, if B.y changes, then A.x becomes invalid. This means that A has to store a back-reference to B. Hence all pointers have to be stored both ways (including inverting 1-N relations into N-1 relations), and the both-way links have to be rewritten correctly during line breaking. -- Han-Wen Nienhuys - han...@xs4all.nl - http://www.xs4all.nl/~hanwen ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 26 sept. 2012, at 17:38, Joe Neeman wrote: > On Wed, Sep 26, 2012 at 4:15 AM, m...@mikesolomon.org > 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
Re: Project - Eliminating grob parents and outside-staff-priority
On Wed, Sep 26, 2012 at 4:15 AM, m...@mikesolomon.org 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. 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). 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? 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. 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... > 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. 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? 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. Cheers, Joe ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
2012/9/26 m...@mikesolomon.org : > > On 26 sept. 2012, at 14:13, David Kastrup wrote: >> Conceptually simple problems need to map to conceptually simple >> solutions. If they don't, our APIs suck. > > We don't have APIs, Sounds like we found the reason they suck. Couldn't reseist, sorry. -- Francisco Vila. Badajoz (Spain) www.paconet.org , www.csmbadajoz.com ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 26 sept. 2012, at 14:13, David Kastrup wrote: >> What we need to arrive at is a situation where somebody without a clue > starting to write stuff will more likely than not get a whole lot of > things working right without realizing it, rather than getting a whole > lot of things working wrong without realizing it. I completely agree. > > Which apparently is what is happening to Marc right now. He is working > on a simple problem, and it fails for complex reasons. And that means > the current design of our backend is bad. > > Conceptually simple problems need to map to conceptually simple > solutions. If they don't, our APIs suck. We don't have APIs, which is a separate but equally problematic issue. The conceptually simple problem is that grobs are positioned with respect to other grobs. The conceptually simple solution is that grobs contain arrays of these other grobs and use them for the positioning. That's why I want to make this change - it provides one-stop-shopping for positioning changes. > >> I think the change decreases complexity as it makes LilyPond more >> predictable and boring - objects side position based off of other >> objects and that's it. No need for side-position, parents and >> outside-staff-priority. > > parents are used for a _lot_ of positioning, and for example the > determination of a common grob parent is an _efficient_ operation. So > it might make sense to solve the problem you are thinking of via > artificial/grouping parents. This is totally possible - you check the side-position-elements array, and if it has multiple members, you find their common refpoint. This can go all the way up to System and VerticalAlignment, both of which will have side-position-element arrays of size 0 for both the X and Y axes. Cheers, MS ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
"m...@mikesolomon.org" writes: > On 26 sept. 2012, at 13:39, David Kastrup wrote: > >> It sounds to me like it would make more sense that we improve our >> cache invalidation strategy where it goes wrong > > There is currently no cache invalidation strategy. Sounds like we found the place where it goes wrong. >> rather than shifting the >> problem around in increasingly complex manners. > > There is currently no way in LilyPond to trace what properties depend > on what properties. So if we want to invalidate the cache of property > X, it is very difficult to invalidate the caches of properties that > depend on it. This is made considerably easier if side-positioning is > streamlined. When a grob X's side position changes for a given axis, > iterate over its side-position elements and recalculate their offsets. > That's one of the main reasons I want to make this change. What we need to arrive at is a situation where somebody without a clue starting to write stuff will more likely than not get a whole lot of things working right without realizing it, rather than getting a whole lot of things working wrong without realizing it. Which apparently is what is happening to Marc right now. He is working on a simple problem, and it fails for complex reasons. And that means the current design of our backend is bad. Conceptually simple problems need to map to conceptually simple solutions. If they don't, our APIs suck. > I think the change decreases complexity as it makes LilyPond more > predictable and boring - objects side position based off of other > objects and that's it. No need for side-position, parents and > outside-staff-priority. parents are used for a _lot_ of positioning, and for example the determination of a common grob parent is an _efficient_ operation. So it might make sense to solve the problem you are thinking of via artificial/grouping parents. I can't vouch for it, obviously, as the backend is mostly opaque to me right now. But it is a possibility. -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
On 26 sept. 2012, at 13:39, David Kastrup wrote: > "m...@mikesolomon.org" writes: > >> 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. > > [...] > >> performance is uncertain, but it'd probably require more optimization >> in skyline.cc and/or caching of skylines. > > It sounds to me like you consider caching a bad idea so you want to > remove it, and to make this removal feasible you think you will be > required to do caching. > You're right - I explained myself poorly. The caching of skylines would come from similar content. i.e. if Skyline X == Skyline A and Skyline Y == Skyline B and we have already measured the distance between A and B, use that as the distance between X and Y. Here, equality is defined as having buildings with the same start_, end_, slope_ and y_offset_. So it's a different type of caching than the caching of grob properties. > It sounds to me like it would make more sense that we improve our cache > invalidation strategy where it goes wrong There is currently no cache invalidation strategy. > rather than shifting the > problem around in increasingly complex manners. > There is currently no way in LilyPond to trace what properties depend on what properties. So if we want to invalidate the cache of property X, it is very difficult to invalidate the caches of properties that depend on it. This is made considerably easier if side-positioning is streamlined. When a grob X's side position changes for a given axis, iterate over its side-position elements and recalculate their offsets. That's one of the main reasons I want to make this change. I think the change decreases complexity as it makes LilyPond more predictable and boring - objects side position based off of other objects and that's it. No need for side-position, parents and outside-staff-priority. Cheers, MS ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Re: Project - Eliminating grob parents and outside-staff-priority
"m...@mikesolomon.org" writes: > 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. [...] > performance is uncertain, but it'd probably require more optimization > in skyline.cc and/or caching of skylines. It sounds to me like you consider caching a bad idea so you want to remove it, and to make this removal feasible you think you will be required to do caching. It sounds to me like it would make more sense that we improve our cache invalidation strategy where it goes wrong rather than shifting the problem around in increasingly complex manners. -- David Kastrup ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
Project - Eliminating grob parents and outside-staff-priority
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. 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. 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. 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. 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. 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. Before I do this, which will take me several months, does anyone have any objections? Do people think it's a good idea? Cheers, MS ___ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
