Created attachment 256685 [details] [review]
Equivalent patch for 3.8

This patch adds the same change to the 3.8 branch

Created attachment 256686 [details] [review]
Patch for 3.16

Patch for 3.16. Seems to have gone lost when creating this task

With out going into much detail, it does seems better to sort it alphabetically first.

Implementation wise I think it is probably a good idea to keep the toplevel list sorted but this will make adding a new toplevel appear in the right order instead of the end which is what the user is used to.
I tried it and it does not look bad, besides once you save and reopen the file again the initial order is going to be lost

Nice to here you generally like. I did not fully understand your second paragraph. Do you like my implementation better or one that sorts on insertion?

I also thought about it but didn't want t change too much. With git head the XML output is very unstable so the order is always different on save&reopen.

If you merge a sort on insertion solutions I'm fine with that.

(In reply to comment #4)
> Nice to here you generally like. I did not fully understand your second
> paragraph. Do you like my implementation better or one that sorts on insertion?

If we have to sort by name/dep I prefer (as a user) to do it at insertion and keep view and save order consistent.
It will obviously make the order change when the name is changed but IMO that would be a fair trade off.

> I also thought about it but didn't want t change too much. With git head the
> XML output is very unstable so the order is always different on save&reopen.

Could you attach the offending file?

> If you merge a sort on insertion solutions I'm fine with that.

Well it will take more time since we would have to sort the list on name changes

(In reply to comment #5)> 
> If we have to sort by name/dep I prefer (as a user) to do it at insertion and
> keep view and save order consistent.
> It will obviously make the order change when the name is changed but IMO that
> would be a fair trade off.


Makes sense.

> 
> Could you attach the offending file?
> 

Sure.

> > If you merge a sort on insertion solutions I'm fine with that.
> 
> Well it will take more time since we would have to sort the list on name
> changes

If you say it requires more time could you consider merging my patch in the meantime as a bug fix? It does fix bugs because the widget dependencies are not properly considered by the final sorting routine (as I tried to explain in the commit message).

It's gonna be hard for me to make the changes you propose since I'm still mostly lost in the glade code base.

Created attachment 256887 [details]
Geany's glade file, upstream version

FWIW: I did improve this particular feature a lot in Glade master while
doing the composite templates feature for GTK+, it was one of my own 
priorities to be damn sure that all of GTK+'s .ui files dont get
unrelated changes at save time.

So, I only ask that while fixing this bug, we do our best to not regress
what we already have.

It would be nice, before committing, to use the patched Glade to open
every single .ui file (there are around 25 of them) in GTK+ and save
them, and see if our patches cause any difference.

This can be done easily like so:
   o git checkout gtk+
   o cd gtk+
   o glade ./gtk/*.ui
   o Glade will load all of the files, save each one of them one by one
     and close the tab in Glade until there are no tabs open again
   o git diff -a

Ideally, 'git diff -a' in this case produces no output.

If there are some small changes resulting from these patches, and
they cannot be easily avoided, then so be it, just please try to
keep it the same as it currently is.

Thanks.

(In reply to comment #6)
> If you say it requires more time could you consider merging my patch in the
> meantime as a bug fix? It does fix bugs because the widget dependencies are not
> properly considered by the final sorting routine (as I tried to explain in the
> commit message).

Yeah, I will probably commit your patch first and then work from there.
I found another related bug with this file and glade 3.16, for some reason it gets stuck in an infinite loop while trying to save geany.glade

Does it work for you?

Actually I only tried saving this very file in Glade 3.8.4, as Geany still supports GTK2 I didn't try to use it with a GTK3-only glade.

Is it caused by my patch?

(In reply to comment #8)
> 
> This can be done easily like so:
>    o git checkout gtk+
>    o cd gtk+
>    o glade ./gtk/*.ui
>    o Glade will load all of the files, save each one of them one by one
>      and close the tab in Glade until there are no tabs open again
>    o git diff -a
> 
> Ideally, 'git diff -a' in this case produces no output.
> 
> If there are some small changes resulting from these patches, and
> they cannot be easily avoided, then so be it, just please try to
> keep it the same as it currently is.
> 
> Thanks.

I've done that. I attached the files.

These files reported errors in glade, so i did not save them:
gtkscalebutton.ui
gtkprintunixdialog.ui
gtkfilechooserdefault.ui
gtkcoloreditor.ui
gtkaboutdialog.ui

The only difference between the diffs is gtkpagesetupunixdialog.ui where there was a single object reordered after saving it with patched glade. It was stable after the initial save, i.e. it didn't fluctuate further. I guess this is the only file where the split-sort makes a difference because there are dependencies between the top level widgets.

But these files show no regressions as such. I would be very surprised if there are regression because the change only affects sorting, it doesn't affect the contents of the toplevel widget list.

Created attachment 257045 [details] [review]
git diff for git+.git; patched glade

Created attachment 257046 [details] [review]
git diff for git+.git; unpatched glade

(In reply to comment #10)
> Actually I only tried saving this very file in Glade 3.8.4, as Geany still
> supports GTK2 I didn't try to use it with a GTK3-only glade.
> 
> Is it caused by my patch?

No, its not your patch, and its seems its not stuck in a infinite loop, it just takes too long to be usable (several minutes)

So before rushing this in I want to explore the possibility of using some graph theory to see if we can solve this problem.

My guess is that what we really need to resolve dependencies is tsort

http://en.wikipedia.org/wiki/Topological_sorting 

Then we need a clever implementation that updates the list of "edges" when we add or remove an object from the project and obviously when a dependency changes (widget prop referencing another object)

(In reply to comment #11)
> (In reply to comment #8)
> > 
> > This can be done easily like so:
> >    o git checkout gtk+
> >    o cd gtk+
> >    o glade ./gtk/*.ui
> >    o Glade will load all of the files, save each one of them one by one
> >      and close the tab in Glade until there are no tabs open again
> >    o git diff -a
> > 
> > Ideally, 'git diff -a' in this case produces no output.
> > 
> > If there are some small changes resulting from these patches, and
> > they cannot be easily avoided, then so be it, just please try to
> > keep it the same as it currently is.
> > 
> > Thanks.
> 
> I've done that. I attached the files.
> 
> These files reported errors in glade, so i did not save them:

What kind of errors ? The .UI files wont load ?

> gtkscalebutton.ui
> gtkprintunixdialog.ui
> gtkfilechooserdefault.ui
> gtkcoloreditor.ui
> gtkaboutdialog.ui

To edit GTK+'s own .ui files, you need to use GTK+'s private
widget catalog (to load internal thingamajigies like GtkColorEditor
and the like).

This should help loading files in GTK+:
   https://git.gnome.org/browse/gtk+/tree/gtk/glade/README.glade

If Glade cannot load the basic files in GTK+, then we will put all
patches and enhancements on hold until we fix that first.

> The only difference between the diffs is gtkpagesetupunixdialog.ui where there
> was a single object reordered after saving it with patched glade. It was stable
> after the initial save, i.e. it didn't fluctuate further.

That sounds about reasonable, please try again using GTK+'s private
widget catalog and see if that single change is indeed the only one.

> I guess this is the
> only file where the split-sort makes a difference because there are
> dependencies between the top level widgets.
> 
> But these files show no regressions as such. I would be very surprised if there
> are regression because the change only affects sorting, it doesn't affect the
> contents of the toplevel widget list.

If it effects the *order* of the toplevel widget list then your patch is
definitely dangerous ;-)

Even if you are playing with the order in which child nodes are saved
by parents, that's really dangerous, as the order a GtkBox or GtkNotebook
saves it's children is part of the semantic used to load that widget
by GtkBuilder, and the order of children has significance.

Also, one more thing.

Reading through this bug description and initial comments diagonally,
it's hard to see what problem exactly this patch tries to address, it reads
a lot like:
 "Lets sort in a new way, because I dunno... wouldnt that be cool"

While I think the real issue here is that for some particular data/widget
type that Geany uses, Glade saves things in an alternating order (meaning
somewhere there may be a g_list_append() needs to be replaced by
g_list_prepend(), or similar).

Can somebody please update the bug title to reflect what the bug
actually is ?

(In reply to comment #15)
> (In reply to comment #11)
> > (In reply to comment #8)
> > > 
> > > This can be done easily like so:
> > >    o git checkout gtk+
> > >    o cd gtk+
> > >    o glade ./gtk/*.ui
> > >    o Glade will load all of the files, save each one of them one by one
> > >      and close the tab in Glade until there are no tabs open again
> > >    o git diff -a
> > > 
> > > Ideally, 'git diff -a' in this case produces no output.
> > > 
> > > If there are some small changes resulting from these patches, and
> > > they cannot be easily avoided, then so be it, just please try to
> > > keep it the same as it currently is.
> > > 
> > > Thanks.
> > 
> > I've done that. I attached the files.
> > 
> > These files reported errors in glade, so i did not save them:
> 
> What kind of errors ? The .UI files wont load ?
> 
> > gtkscalebutton.ui
> > gtkprintunixdialog.ui
> > gtkfilechooserdefault.ui
> > gtkcoloreditor.ui
> > gtkaboutdialog.ui
> 
> To edit GTK+'s own .ui files, you need to use GTK+'s private
> widget catalog (to load internal thingamajigies like GtkColorEditor
> and the like).
> 
> This should help loading files in GTK+:
>    https://git.gnome.org/browse/gtk+/tree/gtk/glade/README.glade
> 
> If Glade cannot load the basic files in GTK+, then we will put all
> patches and enhancements on hold until we fix that first.
> 
> > The only difference between the diffs is gtkpagesetupunixdialog.ui where there
> > was a single object reordered after saving it with patched glade. It was stable
> > after the initial save, i.e. it didn't fluctuate further.
> 
> That sounds about reasonable, please try again using GTK+'s private
> widget catalog and see if that single change is indeed the only one.
> 
> > I guess this is the
> > only file where the split-sort makes a difference because there are
> > dependencies between the top level widgets.
> > 
> > But these files show no regressions as such. I would be very surprised if there
> > are regression because the change only affects sorting, it doesn't affect the
> > contents of the toplevel widget list.
> 
> If it effects the *order* of the toplevel widget list then your patch is
> definitely dangerous ;-)
> 

Yes, the top level order is important, because there may be interdependencies. These dependencies are not currently handled by git master and this patch addresses this (see commit message and text below).

I worded my sentence badly. I meant "I would be surprised if there are regressions because only the toplevel order is affected while toplevel dependency is enforced".

> Even if you are playing with the order in which child nodes are saved
> by parents, that's really dangerous, as the order a GtkBox or GtkNotebook
> saves it's children is part of the semantic used to load that widget
> by GtkBuilder, and the order of children has significance.
> 

No, this change doesn't affect children. I'm aware of the implications. This change only affects the toplevel list, nothing else.

> Also, one more thing.
> 
> Reading through this bug description and initial comments diagonally,
> it's hard to see what problem exactly this patch tries to address, it reads
> a lot like:
>  "Lets sort in a new way, because I dunno... wouldnt that be cool"
> 
> While I think the real issue here is that for some particular data/widget
> type that Geany uses, Glade saves things in an alternating order (meaning
> somewhere there may be a g_list_append() needs to be replaced by
> g_list_prepend(), or similar).
> 
> Can somebody please update the bug title to reflect what the bug
> actually is ?

The bug is that current Glade uses a compare function that sorts by two different keys at the same time. This doesn't work correctly. The dependencies of two toplevel widgets are potentially not considered because alphabetic sorting took already place.

Using my ABC example from the first message: The compare function will not be called for A and C because C is already sorted after B (and A sorted before B). But if A depends on C, then C must come first. As the compare function is not called this is missed.

To resolve this you must sort separately, by each key at a time. As sort-by-dependency is more important (for correct XML output) it must be done last.

This is not about alternating order of saved geany.glade. But this change makes it more stable as a _side effect_. I didn't mean to report bugs with or about geany.glade.

Created attachment 257061 [details] [review]
Toplevel sorting using topology algorithm

Hi, so I did a quick implementation of the topology sorting (actually a literal implementation)

the algorithm I used to create the edges is

for every object P in project
    for every object S in project
        if P == parent of S
            add edge (P,S)
        else if glade_widget_adaptor_depends (S, P)
            add edge (P,S)

(In reply to comment #17)
> Created an attachment (id=257061) [details] [review]
> Toplevel sorting using topology algorithm
> 
> Hi, so I did a quick implementation of the topology sorting (actually a literal
> implementation)
> 
> the algorithm I used to create the edges is
> 
> for every object P in project
>     for every object S in project
>         if P == parent of S
>             add edge (P,S)
>         else if glade_widget_adaptor_depends (S, P)
>             add edge (P,S)

Juan, looking at your patch, this is not done
exactly correctly, unless I'm missing something
sneaky...

The toplevels need to be sorted... not the full object
list of the project, I can see that you are building the
dependency list, or edges, by comparing each object
individually, and then trying to sort the toplevel list
using those 'edges'.

Will 'tsort' work like this ?

Or will tsort expect that all of your edges can be found
in the list you want to sort ?

This is likely the wrong approach, otherwise it's quite
unclear reading the code why it is the correct approach.

(In reply to comment #18)
[...] 
> The toplevels need to be sorted... not the full object
> list of the project, I can see that you are building the
> dependency list, or edges, by comparing each object
> individually, and then trying to sort the toplevel list
> using those 'edges'.

True, but we need the full dependency tree because of children objects depend on their parents.

> Will 'tsort' work like this ?
> 
> Or will tsort expect that all of your edges can be found
> in the list you want to sort ?

that is a really good question!
I did not had time to actually understand the whole algorithm.
I want to make some test cases first to make sure the implementation is correct.

If it happens that tsort needs all the nodes in the list, then it wont be a problem, we can filter it later.

> This is likely the wrong approach, otherwise it's quite
> unclear reading the code why it is the correct approach.

yeah I know, I just implemented the algorithm I need to do more testing.

The children are subtrees of their parent and already ordered according to their appearance within the parent. They must not be considered in the overall sorting. Only toplevel widgets must be considered, i.e. children should not be shuffled around in their parent.

However, sorting of toplevel widgets must consider that children (and subchildren) depend on other toplevel widgets (such as GtkImage) but the current sorting does that already if I understood this correctly.

Or am I understanding this wrong?

If not I would think my patch should be optimal for sort-on-save. Only sort-on-insert would be even better.

(In reply to comment #20)
> However, sorting of toplevel widgets must consider that children (and
> subchildren) depend on other toplevel widgets (such as GtkImage) but the
> current sorting does that already if I understood this correctly.

Correction: The current sorting after applying my patch does this. As I have mentioned the upstream sorting is slightly broken because of sorting by two separate keys in a single compare function.

(In reply to comment #20)
[...]
> However, sorting of toplevel widgets must consider that children (and
> subchildren) depend on other toplevel widgets (such as GtkImage) but the
> current sorting does that already if I understood this correctly.
> 
> Or am I understanding this wrong?

We where talking about my tsort patch and which are the correct parameters to pass.

(In reply to comment #21)
[...]
> Correction: The current sorting after applying my patch does this. As I have
> mentioned the upstream sorting is slightly broken because of sorting by two
> separate keys in a single compare function.

Yes I know, I am still not convinced using two keys in qsort is wrong.
irrc as long as the comparison if constant qsort should work.

in any case I found that glade_widget_depends() is too slow to be used for sorting the list of widgets at save time. (geany.glade gtk2 version) takes several minutes on glade 3.16 while tsort takes a few ms

BTW, do you have a glade file that triggers the two key problemi qsort?

I am surprised that glade_widget_depends() is so slow on glade 3.16, in 3.8 saving (and thus, sorting) is instant with geany.glade. Can this be a regression? In gdb I see it's called recursively, perhaps there is something fishy?

I'm also confused why you question my patch now. You have already mentioned that you would merge it.

As two why sorting with two keys is wrong (btw, glib does not use qsort as it's not stable; instead it uses mergesort. anyway, this is an implementation detail of glib). As I don't have a glade file that exposes the problem but I'll show the problem with a sample program. You can find it in the attachment. It implements is written in analogy to the current glade git master and uses my above example. The items A, B and C which are to be sorted lexically, except that A depends on C (realized via the second order key), so the correct order would be "C, B, A"

The output of the program is

> Compare B to C
> Compare A to B
> A
> B
> C

I.e. post-sort order is (still) "A, B, C". The output also shows that the dependency of A to C is not even considered (=> the compare function is not called for these two) because it already found that A sorts before B and B sorts before C. As a proper sorting algorithm it concludes that A must also sort before C and doesn't call the compare function: the dependency is missed.

Interdependencies in the toplevel widget are missed in the same way. Therefore you need to sort by separate keys separately.

Created attachment 257658 [details]
Compile with: gcc $(pkg-config glib-2.0 --cflags) test.c -o test $(pkg-config glib-2.0 --libs)

(In reply to comment #23)
> I am surprised that glade_widget_depends() is so slow on glade 3.16, in 3.8
> saving (and thus, sorting) is instant with geany.glade. Can this be a
> regression? In gdb I see it's called recursively, perhaps there is something
> fishy?
> 
> I'm also confused why you question my patch now. You have already mentioned
> that you would merge it.

Because I do not want to apply a patch that might change the current sorting order if I will have to fix it again anyways (because of how slow glade_widget_depends() is on 3.16)

Well, this contradicts your earlier statement "Yeah, I will probably commit your patch first and then work from there."

But anyway, I'm happy if you find a solution. But I hope it doesn't mean that glade git master and 3.8.x remains buggy for much longer. The current sorting solution *is bugged* and may result in incorrect .xml. I would prefer to merge a solution now if the better fix takes longer, especially since the it also has the nice side effect of making the generated xml more stable.

Created attachment 257672 [details] [review]
Same patch, added two pass implementation

As you can see, trying to sort it in two passes does not help either.
The problem is even more fundamental!

Dependency is not a transitive property so we can not use a comparison sort algorithm.

Are you sure you added the right file?

Aynway, yes you are right. When I apply my patch to my test program then it still sorts wrong. Something more sophisticated is needed to make the sort right.

So what's left from my patch is that it makes XML output more stable (less diff noise between two saved files) but I guess you won't consider it for merging anymore?

Created attachment 257737 [details] [review]
Same patch, added two pass implementation

Yeah I attached a different test.c file :)
I am afraid applying your patch is pointless since we will have to fix it properly anyways changing once again the output.

yeah what we need is topological sort, I am working on it, its almost finished it just need some testing.

btw if you have time to create test cases, including circular dependencies and such I will appreciate :)

Created attachment 257980 [details] [review]
_glade_tsort() implementation

This is my latest patch, I added a test application but we need to add more cases!
And eventually make runtime insert new object ordered

Created attachment 258741 [details] [review]
_glade_tsort() implementation

Ok I think now I am getting closer...

I fixed the way I generate the dependencies graph, the new algorithm is

for every object P in project
    for every object S in project
        if glade_widget_depends (S, P)
            add edge (P toplevel, S toplevel)

This way dependencies on children reflect on the toplevels properly.

I also removed all widget adaptor depends() implementation except
glade_gtk_widget_depends() which I left it just because of GtkIconFactory.

GtkIconFactory seems to be the only case where an object depends on another without a reference.
This could be handled differently if we choose to serialize non widgets first or if we add a weight property on the class we can use when doing the initial sort.

Anyways this patch order toplevels alphabetically first, then by dependencies, then if there is any circular dependency it repeats the process by sorting them alphabetically and by hard dependency (by hard dependency I mean a dependency on a construct-only property)
And in the case it finds a hard circular dependency, it simply break it by resetting one of the properties.

If it find a hard circular dependency it will popup a warning and will let you see the dependency if you have installed xdot.
This is just for debug see comment in glade_project_cycles_nodes_message()

So the only thing left for me to do about dependency ordering is make sure I do not add soft circular dependencies in the graph so those toplevel can keep the original alphabetical order

Created attachment 258742 [details] [review]
_glade_tsort() implementation

Ops, I forgot to include new files glade-tsort.[ch]

Ok so after lot of work on this I pushed this fix to master and glade-3-16 branch
I will have to backport it to 3.8

I made a few optimizations to the functions most used while creating the dependency graph

glade_widget_get_toplevel() now caches its value so its fast to call it in the nested for statements.
I also added _glade_widget_peek_prop_refs() to avoid creating a new list of properties each time we want to know if a widget depends on another.

With all these changes I was able to reduce executing time of sorting geany.glade from 250ms to 135ms on average, btw 99% of the time is spent building the dependency graph

Anyways toplevel order from now on should be alphabetical except when there is a dependency on other object.

Object with circular dependencies will be appended at the end in alphabetical order unless there is a hard dependency (a dependency on a construct only prop)
and at last if there are objects with hard circular dependencies they are simply appended to the end in alphabetical order.

Sounds awesome! I'm sorry that I didn't get to test it yet but I would have done so with geany.glade too, anyway.

Will this be backported to 3.8

I request to re-open as the fix hasn't been backported to 3.8 yet (as promised).

Hi Thomas, I never got time to back port it, if you are blocked on this I recommend you to dig into it, it should not be hard.

In any case I opened a new bug to track this issue #723714