Issue 5344: Avoid repeated calculation of accepted contexts

https://sourceforge.net/p/testlilyissues/issues/5344/

Encapsulate the list of accepted contexts into Acceptance_set, which
is owned by both Context_def and Context.  The merging of context mods
that used to occur anew for every path_to_acceptable_context () call
now occurs once when a context is instantiated.

The aspect of this change most in need of review is probably garbage
collection.  Thanks in advance.

[dak, 2018-06-14 22:53:58]

https://codereview.appspot.com/346080043/diff/1/lily/acceptance-set.cc
File lily/acceptance-set.cc (right):

https://codereview.appspot.com/346080043/diff/1/lily/acceptance-set.cc#newcode34
lily/acceptance-set.cc:34: if (!scm_is_null (default_))
Why do you prioritize the default child?

The only purpose of the defaultchild is to provide a default path for reaching a
Bottom context via the creation of implicit contexts.  You are mashing up
several semantics here in something that feels like a handwavy "do-what-I-mean"
scheme rather than a well-confined notion of defaultchild.  I actually invested
quite a bit of work to get rid of that so I'd like to know what advantage you
see in adding additional semantics to defaultchild.

https://codereview.appspot.com/346080043/diff/1/lily/acceptance-set.cc#newcode50
lily/acceptance-set.cc:50: accepted_ = scm_cons(item, scm_delete_x (item,
accepted_));
I'm not overly happy with this kind of O(n^2) behavior.  Most of the context
definitions will be done in engraver-init.ly where duplication is not an issue
because it has been taken care of manually.

https://codereview.appspot.com/346080043/diff/1/lily/context-def.cc
File lily/context-def.cc (right):

https://codereview.appspot.com/346080043/diff/1/lily/context-def.cc#newcode330
lily/context-def.cc:330: Acceptance_set& acc = context->acceptance_;
This is a bloody mess.  You take the original list without copying and call
acc.accept and acc.deny and similar on it, operations which use scm_delete_x and
similar for _destructively_ changing the lists in question.  Previously,
\accept/\denies/\defaultchild for better or worse were not interpreted in \with
blocks (which is where ops comes from if I remember correctly).

So you do several changes in semantics in a combination that wreaks havoc and
lets \with blocks destructively change global context defs.

Very much a showstopper.

[Dan Eble, 2018-06-15 02:36:40]

Thank you for your review.  I disagree with some of your conclusions.

https://codereview.appspot.com/346080043/diff/1/lily/acceptance-set.cc
File lily/acceptance-set.cc (right):

https://codereview.appspot.com/346080043/diff/1/lily/acceptance-set.cc#newcode34
lily/acceptance-set.cc:34: if (!scm_is_null (default_))
On 2018/06/14 22:53:58, dak wrote:
> Why do you prioritize the default child?

I don't think I can take credit for that, though maybe I can take blame for
misunderstanding Context_def::get_accepted in the old code.  Doesn't it place
the default child at the front of the list that
Context_def::internal_path_to_acceptable_context () considers?  That would make
the default child the preferred alternative when \context searches for an
instantiable child.  At least, that is how I read it.

https://codereview.appspot.com/346080043/diff/1/lily/acceptance-set.cc#newcode50
lily/acceptance-set.cc:50: accepted_ = scm_cons(item, scm_delete_x (item,
accepted_));
On 2018/06/14 22:53:58, dak wrote:
> I'm not overly happy with this kind of O(n^2) behavior.  Most of the context
> definitions will be done in engraver-init.ly where duplication is not an issue
> because it has been taken care of manually.

Seeing that engraver-init.ly had at most a couple dozen accepts in a
context definition, my gut feeling was that it would be better to
default to cleanliness rather than worry about scaling, but I have no
problem with going back to allowing duplicate entries and mentioning
it in a comment to discourage the next person who comes along.

https://codereview.appspot.com/346080043/diff/1/lily/context-def.cc
File lily/context-def.cc (right):

https://codereview.appspot.com/346080043/diff/1/lily/context-def.cc#newcode330
lily/context-def.cc:330: Acceptance_set& acc = context->acceptance_;
On 2018/06/14 22:53:58, dak wrote:
> You take the original list without copying and call

context->acceptance_ = acceptance_ (line 328) copies the acceptance set from the
Context_def to the Context and then the following code modifies the Context's
acceptance set.  I could use a named method instead of the assignment operator
to make this clearer.

> Previously,
> \accept/\denies/\defaultchild for better or worse were not interpreted in
\with
> blocks (which is where ops comes from if I remember correctly).

\accepts was. \denies and \defaultchild were not until I added them a couple
weeks ago: https://codereview.appspot.com/346050043/  If any of that is a
problem, let me know and I will prepare a patch to revert what you please; I
don't understand why it would be a problem, though.

Anyway, in the old version of Context::path_to_acceptable_context, these mods
were explicitly looped over, converted from strings to symbols, passed into
Context_def::path_to_acceptable_context and merged into a fresh copy of the
Context_def's list of accepted contexts.  This was repeated for every call to
Context::path_to_acceptable_context, which occurred potentially multiple times
during a find-or-create walk of the context hierarchy.

In the new code, the Context's acceptance list is computed here, once, when the
context is instantiated.

> lets \with blocks destructively change global context defs.

I do not think this is the case, but I will verify it.

[Dan Eble, 2018-06-16 12:34:16]

https://codereview.appspot.com/346080043/diff/1/lily/acceptance-set.cc
File lily/acceptance-set.cc (right):

https://codereview.appspot.com/346080043/diff/1/lily/acceptance-set.cc#newcode50
lily/acceptance-set.cc:50: accepted_ = scm_cons(item, scm_delete_x (item,
accepted_));
On 2018/06/15 02:36:40, Dan Eble wrote:
> On 2018/06/14 22:53:58, dak wrote:
> > I'm not overly happy with this kind of O(n^2) behavior.  Most of the context
> > definitions will be done in engraver-init.ly where duplication is not an
issue
> > because it has been taken care of manually.

Let me also clarify that scm_delete_x was used in this way in the old
Context_def::get_accepted before the default was prepended to the list; what's
new in my patch is that it happens as the default child is defined rather than
as the definition is consulted (and that it happens when \accepts is defined,
which was the focus of my earlier reply).

[Dan Eble, 2018-06-17 12:52:01]

Stop uniquifying \accepts; clarify copying

[Dan Eble, 2018-06-17 13:27:39]

On 2018/06/17 12:52:01, Dan Eble wrote:
> Stop uniquifying \accepts; clarify copying

I also spent time trying to find input that would "let \with blocks
destructively change global context defs."  I was surprised that I couldn't make
it happen even after temporarily changing the Acceptance_set list copies to
plain old assignments of SCM values.  My approach was to instantiate two
contexts, with the first context having a \with ... \denies ... and the next
context using the defaults for its type.  Whether the contexts began
sequentially or simultaneously, the impact of \denies was limited to the first
context.  It's strange, but I'm reluctant to spend more time trying to discover
why I can't force a failure even with code that I'm not actually submitting.

[dak, 2018-06-17 13:52:55]

On 2018/06/17 13:27:39, Dan Eble wrote:
> On 2018/06/17 12:52:01, Dan Eble wrote:
> > Stop uniquifying \accepts; clarify copying
> 
> I also spent time trying to find input that would "let \with blocks
> destructively change global context defs."  I was surprised that I couldn't
make
> it happen even after temporarily changing the Acceptance_set list copies to
> plain old assignments of SCM values.  My approach was to instantiate two
> contexts, with the first context having a \with ... \denies ... and the next
> context using the defaults for its type.  Whether the contexts began
> sequentially or simultaneously, the impact of \denies was limited to the first
> context.  It's strange, but I'm reluctant to spend more time trying to
discover
> why I can't force a failure even with code that I'm not actually submitting.

For scm_delete_x or its Scheme equivalent of delete! to have an actually
destructive effect on other list copies, the removed element must not be the
first in the list.  That makes constructing failing examples a bit more complex
since you always have to add additional fluff before an effect may become
apparent.

[Dan Eble, 2018-06-17 17:51:34]

test that \with \denies ... has local effect

[Dan Eble, 2018-06-17 17:56:06]

On 2018/06/17 17:51:34, Dan Eble wrote:
> test that \with \denies ... has local effect

Thanks for the clue.  The new test passes with the code I've submitted and fails
if Acceptance_set::assign_copy is modified not to make a copy.

[dak, 2018-06-17 18:13:20]

On 2018/06/17 17:56:06, Dan Eble wrote:
> On 2018/06/17 17:51:34, Dan Eble wrote:
> > test that \with \denies ... has local effect
> 
> Thanks for the clue.  The new test passes with the code I've submitted and
fails
> if Acceptance_set::assign_copy is modified not to make a copy.

I must be getting senile.  I didn't spot where you make the copy.

[Dan Eble, 2018-06-17 18:47:54]

On 2018/06/17 18:13:20, dak wrote:
>
> I must be getting senile.  I didn't spot where you make the copy.

In fairness, the copy was not as obvious in patch set 1, though that's not proof
you're not getting senile.  :D