You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@myfaces.apache.org by Curtiss Howard <cu...@gmail.com> on 2010/02/04 14:58:36 UTC
[Core] FacesConfigurator.sortRelativeOrderingList() algorithm is
broken
Hi,
Our testers are currently running against Sun's CTS tests and the
relative ordering algorithm in
FacesConfigurator.sortRelativeOrderingList() is failing on a rather
simple case:
A after B
B before C
C before A
The expected faces-config ordering is B-C-A, but instead
sortRelativeOrderingList() is detecting a circularity.
I've looked at the code, and it seems like a very complicated
algorithm that attempts to sort the list elements in-place using
weighting. Honestly I'm not even sure where to begin modifying that
code.
Looking through the history, I can't determine who the original author
is, so if you're reading this, please let me know your thoughts. I'd
like to fix this problem, but instead I'd prefer to rewrite it using a
simpler and more reliable algorithm, which involves creating a tree
out of the "before/after" rules and using a bottom-up level order
traversal to trim duplicate nodes and finally reversing the resulting
list. Circularities can also be detected in the same pass. Is that a
less efficient algorithm? Most likely, but I'd argue its simplicity
and reliability, coupled with the fact that the data set should always
stay fairly small (after all, how many faces-configs can someone
possible use in an application...) would make up for that.
Thoughts?
Thanks,
Curtiss Howard
Re: [Core] FacesConfigurator.sortRelativeOrderingList() algorithm is
broken
Posted by Curtiss Howard <cu...@gmail.com>.
On Thu, Feb 4, 2010 at 10:26 PM, Leonardo Uribe <lu...@gmail.com> wrote:
> Hi
>
> I could not resist the temptation to try another algorithm. I committed an
> alternative using a topological sorting algorithm extracted from
>
> https://svn.apache.org/repos/asf/excalibur/trunk/fortress/container-api/src/java/org/apache/avalon/fortress/util/dag/
>
> Since this one is in apache codebase we can copy it to myfaces and customize
> it from our needs. It works in all examples including the one proposed.
>
> I open an issue to track this one:
>
> https://issues.apache.org/jira/browse/MYFACES-2537
>
> Suggestions are welcome.
>
> regards,
>
> Leonardo Uribe
>
Thanks Leonardo... we'll have our testers run against CTS as soon as possible.
Curtiss Howard
Re: [Core] FacesConfigurator.sortRelativeOrderingList() algorithm is
broken
Posted by Leonardo Uribe <lu...@gmail.com>.
Hi
I could not resist the temptation to try another algorithm. I committed an
alternative using a topological sorting algorithm extracted from
https://svn.apache.org/repos/asf/excalibur/trunk/fortress/container-api/src/java/org/apache/avalon/fortress/util/dag/
Since this one is in apache codebase we can copy it to myfaces and customize
it from our needs. It works in all examples including the one proposed.
I open an issue to track this one:
https://issues.apache.org/jira/browse/MYFACES-2537
Suggestions are welcome.
regards,
Leonardo Uribe
2010/2/4 Curtiss Howard <cu...@gmail.com>
> On Thu, Feb 4, 2010 at 12:08 PM, Leonardo Uribe <lu...@gmail.com> wrote:
> > Hi
> >
> > The algorithm proposed fails because it is not able to process the nodes
> in
> > the correct order (the algorithm assign a weight equal to all nodes, so
> it
> > fails when try to order them in a psedo "postorder" form). I don't see a
> > quick solution for that one, so I think is better and faster try another
> > algorithm.
> >
> > I have some junit tests here:
> >
> > org.apache.myfaces.config.OrderingFacesConfigTest
> >
> > The tests call OrderingFacesConfigTest.applyAlgorithm, so it is easy to
> try
> > another one.
> >
> > Note any algorithm is executed when the application is initialized, and
> the
> > possible number of application config resources is relatively small.
> >
> > Suggestions are welcome.
> >
> > regards,
> >
> > Leonardo Uribe
> >
>
> Thanks for looking into that Leonardo. I will go ahead and write a
> new implementation that uses a tree (as explained in the first email).
>
> Thanks,
>
>
> Curtiss Howard
>
Re: [Core] FacesConfigurator.sortRelativeOrderingList() algorithm is
broken
Posted by Curtiss Howard <cu...@gmail.com>.
On Thu, Feb 4, 2010 at 12:08 PM, Leonardo Uribe <lu...@gmail.com> wrote:
> Hi
>
> The algorithm proposed fails because it is not able to process the nodes in
> the correct order (the algorithm assign a weight equal to all nodes, so it
> fails when try to order them in a psedo "postorder" form). I don't see a
> quick solution for that one, so I think is better and faster try another
> algorithm.
>
> I have some junit tests here:
>
> org.apache.myfaces.config.OrderingFacesConfigTest
>
> The tests call OrderingFacesConfigTest.applyAlgorithm, so it is easy to try
> another one.
>
> Note any algorithm is executed when the application is initialized, and the
> possible number of application config resources is relatively small.
>
> Suggestions are welcome.
>
> regards,
>
> Leonardo Uribe
>
Thanks for looking into that Leonardo. I will go ahead and write a
new implementation that uses a tree (as explained in the first email).
Thanks,
Curtiss Howard
Re: [Core] FacesConfigurator.sortRelativeOrderingList() algorithm is
broken
Posted by Leonardo Uribe <lu...@gmail.com>.
Hi
The algorithm proposed fails because it is not able to process the nodes in
the correct order (the algorithm assign a weight equal to all nodes, so it
fails when try to order them in a psedo "postorder" form). I don't see a
quick solution for that one, so I think is better and faster try another
algorithm.
I have some junit tests here:
org.apache.myfaces.config.OrderingFacesConfigTest
The tests call OrderingFacesConfigTest.applyAlgorithm, so it is easy to try
another one.
Note any algorithm is executed when the application is initialized, and the
possible number of application config resources is relatively small.
Suggestions are welcome.
regards,
Leonardo Uribe
2010/2/4 Curtiss Howard <cu...@gmail.com>
> On Thu, Feb 4, 2010 at 11:06 AM, Leonardo Uribe <lu...@gmail.com> wrote:
> > Hi
> >
> > I did the algorithm proposed there. For me it is ok if we can find a
> simpler
> > one, as long as all tests proposed pass.
> >
> > Anyway, I'll check why it is failing.
> >
> > regards,
> >
> > Leonardo Uribe
> >
>
> Thanks Leonardo. If you're able to make a quick fix to the algorithm,
> that's always welcome :).
>
>
> Curtiss Howard
>
Re: [Core] FacesConfigurator.sortRelativeOrderingList() algorithm is
broken
Posted by Curtiss Howard <cu...@gmail.com>.
On Thu, Feb 4, 2010 at 11:06 AM, Leonardo Uribe <lu...@gmail.com> wrote:
> Hi
>
> I did the algorithm proposed there. For me it is ok if we can find a simpler
> one, as long as all tests proposed pass.
>
> Anyway, I'll check why it is failing.
>
> regards,
>
> Leonardo Uribe
>
Thanks Leonardo. If you're able to make a quick fix to the algorithm,
that's always welcome :).
Curtiss Howard
Re: [Core] FacesConfigurator.sortRelativeOrderingList() algorithm is
broken
Posted by Leonardo Uribe <lu...@gmail.com>.
Hi
I did the algorithm proposed there. For me it is ok if we can find a simpler
one, as long as all tests proposed pass.
Anyway, I'll check why it is failing.
regards,
Leonardo Uribe
2010/2/4 Curtiss Howard <cu...@gmail.com>
> Hi,
>
> Our testers are currently running against Sun's CTS tests and the
> relative ordering algorithm in
> FacesConfigurator.sortRelativeOrderingList() is failing on a rather
> simple case:
>
> A after B
> B before C
> C before A
>
> The expected faces-config ordering is B-C-A, but instead
> sortRelativeOrderingList() is detecting a circularity.
>
> I've looked at the code, and it seems like a very complicated
> algorithm that attempts to sort the list elements in-place using
> weighting. Honestly I'm not even sure where to begin modifying that
> code.
>
> Looking through the history, I can't determine who the original author
> is, so if you're reading this, please let me know your thoughts. I'd
> like to fix this problem, but instead I'd prefer to rewrite it using a
> simpler and more reliable algorithm, which involves creating a tree
> out of the "before/after" rules and using a bottom-up level order
> traversal to trim duplicate nodes and finally reversing the resulting
> list. Circularities can also be detected in the same pass. Is that a
> less efficient algorithm? Most likely, but I'd argue its simplicity
> and reliability, coupled with the fact that the data set should always
> stay fairly small (after all, how many faces-configs can someone
> possible use in an application...) would make up for that.
>
> Thoughts?
>
> Thanks,
>
>
> Curtiss Howard
>