Grade merging algorithm is still incorrect - accumulative linearisation must be abandoned
Description
Environment
is depended on by
Activity

Antranig BasmanSeptember 23, 2020 at 3:26 PM
We must indeed do something about this since it is still extremely easy to get into situations where weak defaults from parent grades end up overriding apparent direct dependencies. Example from KETTLE-55:
and then we use the nutty grade linkage system to produce writability:
The user then writes:
The poor sap then ends up with a grade list as follows:
In which "fluid.dataSource" has obliterated their subcomponent definition with the JSON encoding. There's no decent way out of this without a C3-like system that guarantees never to move grades to the right. Even if we write empty mixin grades for all the writable grades (which is already a bit of an annoyance) we lose the ability for there to be a one-stop-shop "kettle.dataSource.file.writable" grade which is actually usable. We will need to go back to the old funky `writable:true` system which at least is overridable back and forth.
The time to address this is with when we abolish the old annoyance caused by the "grade cache" - note that the worry in the original "accumulative" JIRA won't be valid because the grade resolver will be constantly retargetting itself as fresh grades are discovered.

Antranig BasmanApril 24, 2016 at 5:17 PMEdited
This has become topical again with the discovery of - we should really do something about this now. Studying the C3 paper and the "pedalo" sample in the C3 paper at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.3910&rep=rep1&type=pdf suggests that we may still not want this after all - or at least not yet. It looks like rewriting our existing algorithm to no longer be accumulative (that is, based on caches of fully merged defaults of parent grades) will fix the most blatant problems that we observe (this was only ever an optimisation in the ancient CSpace days anyway), as well as recasting it in a form which will allow for an easy move to C3 later if we think it is justified. C3 is "nice" but the problem with it is that it is, not to misuse an already overloaded term, "non-accumulative". That is, compositing a fresh grade onto an existing structure will have an effect that is hard to predict - as well as raising the possibility that the grade resolution process will throw in the case it produces an "inconsistent hierarchy". Although our current algorithm, which simply represents an in-order traversal of ancestors plus culling any already visited grades, is rather dumb and can lead to peculiar results (for example, the possibility for material in very deeply derived grades such as fluid.viewComponent to end up overriding top-level user grades if they appear earlier in the list of parents), at least its action is utterly simple and comprehensible, and it's very obvious what an author has to do if they want to re-override some hidden material by adding more grades.
It's possible that an argument could be made against C3-like and similar "clever" hierarchy resolution algorithms based on our "open graph of authors" model, although this is far from clear. The C3 paper is based on a huge amount of experience with complex hierarchies in large codebases and it would be hard to gainsay this evidence without a similar breadth of experience under our own authorial model. However, for the medium term it looks like preserving our existing algorithm with a more civilised implementation is a reasonable thing to do, especially since we are coming close to a 2.0 release - our previous tinkering with the grade hiearchy semantics in "arabic grades" in was quite expensive in its fallout and was the only really substantive failure of backwards compatibility we've had for some years.

Antranig BasmanNovember 3, 2015 at 4:09 PM
Interestingly, after putting in a "quick fix" which eliminates the use of the uncomprehended use of "fluid.model.mergeModel", the failure leading to this report is no longer observable in a live component. As soon as we put in the grade "fluid.component", the hierarchy traversal reacquires each individual grade's raw defaults and remerges them into the concrete grade's options correctly. It appears that we only use the accumulated cache when compositing multiple dynamic grades. We still need to rewrite this algorithm completely, but it seems that there aren't any easily characterisable cases of faulty behaviour which we can patch up before then.
We still have the offputting phenomenon that the corruptly merged version of the options are visible in the defaults cache for the abstract grades - e.g. fluid.tests.FLUID5800mid in the test case. We need to rewrite the default computation algorithm so that it is more similar to the live component option merging algorithm (as well as being more C3-like) - in particular, that it makes the very earliest attempt to compute the component's gradeName list. Without this, we can't interpret properly any of the other options, even to the extent of determining whether the grade is a function or a component grade. Right now we blindly apply the pre-processing in rawDefaults (compact notation expansion, listener annotation) to every grade. This is "mostly hamless" since function grades are unlikely to use the top-level paths "listeners" and "invokers" for any purpose, but obviously unsatisfactory and a long-term risk.
Moving all of this pathway (unifying the static and dynamic parts of merging) to a unified, ginger, async system based on immutable data structures will make all of these requirements far more easy to meet in a performant and easy to understand way.

Antranig BasmanNovember 1, 2015 at 12:43 AM
Investigation of original exception - this was hard to characterise for a while, since the code failed in node.js but not in the browser. This was eventually tracked down to the fact that, since the violating code was actually within jQuery.extend, which was not in STRICT MODE, the assignment to the frozen member of fluid.NO_VALUE named "member" (by the bizarrely broken-looking "mergeModel" implementation) went into the behaviour of "silently failing" rather than raising a TypeError. Running with our jQuery.standalone instead, which is in strict mode, allowed the same behaviour to be seen in the browser and node.js.
This excursion reveals still a further flaw - that our "fluid.annotateListeners" function is operating even for non-component grades. It is the insertion of its information (fluid.NO_VALUE) together with the operation of the non-component-aware mergePolicy PLUS the faulty action of fluid.mergeModel that enables this problem.

Antranig BasmanOctober 31, 2015 at 4:07 PM
Note that ANY situation in which the reordering of grade parents creates a change in the merged output reflects a potential design error. The ideal solution would be to refactor all of the involved grades so that the result becomes order-independent - by removing overridden material from base grades and pushing it down to derived ones. Therefore, the behaviour of our "ultimately evolved IDE" would be to flag the MRO failure case as "just another" case in which a grade hierarchy can be improved by eliminating overriden material from bases. In the meantime the system should continue to work - after all, if there is NO conflicting material in the MRO rejection case, it is not a failure after all - a rejection is only meaningful with respect to a particular set of grade contents.
Details
Assignee
Antranig BasmanAntranig BasmanReporter
Antranig BasmanAntranig BasmanComponents
Fix versions
Priority
Major
Details
Details
Assignee

Reporter

Despite the work in , our grade merging algorithm still has serious flaws. The following set of grades:
(abridged and simplified from recent work on the GPII's "untrusted local FlowManager) triggers an exception in the merging pipeline -
This code reads:
Note that the use of "mergeModel" already has a hazard warning here - we've lost grasp of why this in our workflow, but it is clearly some attempt at base object reference preservation.
We have two serious problems here:
i) The merging algorithm should never throw - it's unclear even where this property named "value" has appeared from but the result of merging should be well-defined in every case - even in light of ii) the system should proceed to a "sensible" merged result even if it will be the wrong one
ii) The result of our new "best practice" on mixin grades has exposed a serious flaw in the basic strategy of merging. We have always assumed that merging can be "accumulative" - that is, that the result of merging a derived grade onto a base grade can be expressed in terms of some cached, fully accumulated material associated with the base grade plus the derived grade material. It's clear that in this case this is impossible - since we have not yet seen the grade "fluid.component" which contains the mergePolicy for the listeners, which occurs only in the 2nd derived grade, we can only ever attach a structure to gpii.flowManager.userLogonStateChange.matchMakingStateChangeHandler which has faultily destroyed information about listeners.
This problem generalises more widely, at least in terms of mergePolicies which have not so far led to more widespread problems since their awkward usability has led them to be used pretty conservatively. But it's obvious that we need to return to a more "linear" algorithm that performs defaults merging in a manner more similar to live options merging (and, doubtless, in the end, unify these processes) since we need to wait for the complete information about mergePolicies throughout the hierarchy to be completely available before we begin any kind of merging.
This suggests that we have dismissed the C3 family unfairly and need to spend more time understanding what regularities they try to respect. The idea that "overriding must always be effective" could perhaps be related to the algorithm's concept of "local precedence order".
The original C3 paper is at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.3910&rep=rep1&type=pdf
It would seem that we would like an algorithm which is both monotonic and "observes local precedence order". Certainly we need a system which produces stable results on both the "confused-grid" and "pedalo" examples. But going further, it seems that even C3 will sometimes reject a hierarchy as inconsistent, which must never happen. As part of our general requirements, although reworking our algorithm from its "accumulative" form is going to make it more inefficient, we certainly want a system which (morally, assuming suitable data structures) does no more work than O(n log n) on a hierarchy with n elements.
Some prior JavaScript art is in "ring.js" whose algorithm is here: https://github.com/nicolas-van/ring.js/blob/master/ring.js - as we can see, this algorithm is capable of rejecting, which must not happen. Unfortunately the paper discussion does not include an example which it will reject, nor any discussion on this. The Wikipedia article on the algorithm does have a brief characterisation of the rejection scenario.