[PATCH 3/4] Backport 56f47169dc09cfd6ed13a24cb9752050ecb66d6f.

[k***@rockbox.org]

From: Juan Pablo Ugarte <***@gmail.com>

GladeProject: Changed the way we calculate graph dependencies.
Instead of using glade_widget_depends() which implied N^2 invocations/iterations
(where N is the numbers of objects in the project) we now calcualte
dependencies based on property references.
This way we only have to iterace over every object once to check the list
of properties that constitute a reference to them.

In a real world example, sorting objects in geany.glade decreased from 120ms to just 1ms

plugins/gtk+/gtk+.xml.in, plugins/gtk+/glade-gtk-widget.c:
Removed unused glade_gtk_widget_depends()
---
gladeui/glade-project.c | 117 ++++++++++++++++++++++++++--------------
plugins/gtk+/glade-gtk-widget.c | 14 -----
plugins/gtk+/gtk+.xml.in | 1 -
3 files changed, 76 insertions(+), 56 deletions(-)

diff --git a/gladeui/glade-project.c b/gladeui/glade-project.c
index e75d502..6f2b202 100644
--- a/gladeui/glade-project.c
+++ b/gladeui/glade-project.c
@@ -2431,7 +2431,16 @@ glade_project_verify_adaptor (GladeProject *project,
static gint
glade_widgets_name_cmp (gconstpointer ga, gconstpointer gb)
{
- return g_strcmp0 (glade_widget_get_name ((gpointer)ga), glade_widget_get_name ((gpointer)gb));
+ return g_strcmp0 (glade_widget_get_name ((gpointer)ga),
+ glade_widget_get_name ((gpointer)gb));
+}
+
+static gint
+glade_node_edge_name_cmp (gconstpointer ga, gconstpointer gb)
+{
+ _NodeEdge *na = (gpointer)ga, *nb = (gpointer)gb;
+ return g_strcmp0 (glade_widget_get_name (nb->successor),
+ glade_widget_get_name (na->successor));
}

static inline gboolean
@@ -2455,64 +2464,47 @@ glade_project_widget_hard_depends (GladeWidget *widget, GladeWidget *another)
return FALSE;
}

-static _NodeEdge *
+static GList *
glade_project_get_graph_deps (GladeProject *project)
{
GladeProjectPrivate *priv = project->priv;
- GList *l, *objects = NULL;
- _NodeEdge *edges = NULL;
-
- /* Create list of GladeWidgets */
- for (l = priv->objects; l; l = g_list_next (l))
- objects = g_list_prepend (objects, glade_widget_get_from_gobject (l->data));
-
- /* Sort objects alphabetically */
- objects = g_list_sort (objects, glade_widgets_name_cmp);
+ GList *l, *edges = NULL;

/* Create edges of the directed graph */
- for (l = objects; l; l = g_list_next (l))
+ for (l = priv->objects; l; l = g_list_next (l))
{
- GladeWidget *predecessor = l->data;
+ GladeWidget *predecessor = glade_widget_get_from_gobject (l->data);
GladeWidget *predecessor_top;
GList *ll;

predecessor_top = glade_widget_get_toplevel (predecessor);

- for (ll = objects; ll; ll = g_list_next (ll))
+ /* Adds dependencies based on properties refs */
+ for (ll = _glade_widget_peek_prop_refs (predecessor); ll; ll = g_list_next (ll))
{
- GladeWidget *successor = ll->data;
- GladeWidget *successor_top;
+ GladeWidget *successor = glade_property_get_widget (ll->data);
+ GladeWidget *successor_top = glade_widget_get_toplevel (successor);

- successor_top = glade_widget_get_toplevel (successor);
-
- /* Ignore object within the same toplevel */
- if (predecessor_top == successor_top)
- continue;
-
- /* Check if succesor depends on predecessor and add a corresponding
- * edge to the dependency graph.
- * Note that we add the implicit dependency on their respective
- * toplevels because that is what we care!
- */
- if (glade_widget_depends (successor, predecessor))
+ /* Ignore objects within the same toplevel */
+ if (predecessor_top != successor_top)
edges = _node_edge_prepend (edges, predecessor_top, successor_top);
}
}

- g_list_free (objects);
-
return edges;
}

static GList *
-glade_project_get_nodes_from_edges (GladeProject *project, _NodeEdge *edges)
+glade_project_get_nodes_from_edges (GladeProject *project, GList *edges)
{
- _NodeEdge *edge, *hard_edges = NULL;
+ GList *l, *hard_edges = NULL;
GList *cycles = NULL;

/* Collect widgets with circular dependencies */
- for (edge = edges; edge; edge = edge->next)
+ for (l = edges; l; l = g_list_next (l))
{
+ _NodeEdge *edge = l->data;
+
if (glade_widget_get_parent (edge->successor) == edge->predecessor ||
glade_project_widget_hard_depends (edge->predecessor, edge->successor))
hard_edges = _node_edge_prepend (hard_edges, edge->predecessor, edge->successor);
@@ -2536,11 +2528,13 @@ glade_project_get_nodes_from_edges (GladeProject *project, _NodeEdge *edges)

if (hard_edges)
{
- GList *hard_cycles = NULL;
+ GList *l, *hard_cycles = NULL;

/* Collect widgets with hard circular dependencies */
- for (edge = hard_edges; edge; edge = edge->next)
+ for (l = hard_edges; l; l = g_list_next (l))
{
+ _NodeEdge *edge = l->data;
+
/* Just toplevels */
if (glade_widget_get_parent (edge->successor))
continue;
@@ -2556,27 +2550,69 @@ glade_project_get_nodes_from_edges (GladeProject *project, _NodeEdge *edges)
* GtkBuilder will fail to set one of the properties that create the cycle
*/

- _node_edge_free (hard_edges);
+ _node_edge_list_free (hard_edges);
}

return cycles;
}
-
+
+static GList *
+glade_project_add_hardcoded_dependencies (GList *edges, GladeProject *project)
+{
+ GList *l, *toplevels = project->priv->tree;
+
+ /* Iterate over every toplevel */
+ for (l = toplevels; l; l = g_list_next (l))
+ {
+ GObject *predecessor = l->data;
+
+ /* Looking for a GtkIconFactory */
+ if (GTK_IS_ICON_FACTORY (predecessor))
+ {
+ GladeWidget *predecessor_top = glade_widget_get_from_gobject (predecessor);
+ GList *ll;
+
+ /* add dependency on the GtkIconFactory on every toplevel */
+ for (ll = toplevels; ll; ll = g_list_next (ll))
+ {
+ GObject *successor = ll->data;
+
+ /* except for GtkIconFactory */
+ if (!GTK_IS_ICON_FACTORY (successor))
+ edges = _node_edge_prepend (edges, predecessor_top,
+ glade_widget_get_from_gobject (successor));
+ }
+ }
+ }
+
+ return edges;
+}
+
static GList *
glade_project_get_ordered_toplevels (GladeProject *project)
{
GladeProjectPrivate *priv = project->priv;
GList *l, *sorted_tree, *tree = NULL;
- _NodeEdge *edges;
+ GList *edges;

/* Create list of toplevels GladeWidgets */
for (l = priv->tree; l; l = g_list_next (l))
tree = g_list_prepend (tree, glade_widget_get_from_gobject (l->data));

+ /* Get dependency graph */
+ edges = glade_project_get_graph_deps (project);
+
+ /* Added hardcoded dependencies */
+ edges = glade_project_add_hardcoded_dependencies (edges, project);
+
/* Sort toplevels alphabetically */
tree = g_list_sort (tree, glade_widgets_name_cmp);

- edges = glade_project_get_graph_deps (project);
+ /* Sort dep graph alphabetically using successor name.
+ * _glade_tsort() is a stable sort algorithm so, output of nodes without
+ * dependency depends on the input order
+ */
+ edges = g_list_sort (edges, glade_node_edge_name_cmp);

/* Sort tree */
sorted_tree = _glade_tsort (&tree, &edges);
@@ -2588,11 +2624,10 @@ glade_project_get_ordered_toplevels (GladeProject *project)
/* And append to the end of the sorted list */
sorted_tree = g_list_concat (sorted_tree, cycles);

- _node_edge_free (edges);
+ _node_edge_list_free (edges);
}

/* No need to free tree as tsort will consume the list */
-
return sorted_tree;
}

diff --git a/plugins/gtk+/glade-gtk-widget.c b/plugins/gtk+/glade-gtk-widget.c
index 7806986..e4c25d0 100644
--- a/plugins/gtk+/glade-gtk-widget.c
+++ b/plugins/gtk+/glade-gtk-widget.c
@@ -83,20 +83,6 @@ glade_gtk_widget_destroy_object (GladeWidgetAdaptor * adaptor,
GWA_GET_CLASS (G_TYPE_OBJECT)->destroy_object (adaptor, object);
}

-gboolean
-glade_gtk_widget_depends (GladeWidgetAdaptor * adaptor,
- GladeWidget * widget, GladeWidget * another)
-{
- /* We want GtkIconFactory to be before any toplevels, just in case one of
- * the stock items defined in it are used.
- */
- if (!glade_widget_get_parent (widget) &&
- GTK_IS_ICON_FACTORY (glade_widget_get_object (another)))
- return TRUE;
-
- return GWA_GET_CLASS (G_TYPE_OBJECT)->depends (adaptor, widget, another);
-}
-
static void
glade_gtk_parse_atk_relation (GladeProperty * property, GladeXmlNode * node)
{
diff --git a/plugins/gtk+/gtk+.xml.in b/plugins/gtk+/gtk+.xml.in
index 56482f0..27cc395 100644
--- a/plugins/gtk+/gtk+.xml.in
+++ b/plugins/gtk+/gtk+.xml.in
@@ -16,7 +16,6 @@
<get-property-function>glade_gtk_widget_get_property</get-property-function>
<action-activate-function>glade_gtk_widget_action_activate</action-activate-function>
<action-submenu-function>glade_gtk_widget_action_submenu</action-submenu-function>
- <depends-function>glade_gtk_widget_depends</depends-function>
<read-widget-function>glade_gtk_widget_read_widget</read-widget-function>
<write-widget-function>glade_gtk_widget_write_widget</write-widget-function>
<create-editor-property-function>glade_gtk_widget_create_eprop</create-editor-property-function>

[k***@rockbox.org]

From: Juan Pablo Ugarte <***@gmail.com>

Ignore widgets that are not part of the project when generating edges
of directed graph used to sort objects by topological order.

Fixes bug 727992 "Editing UI and saving does not remove deleted Combo with Entry"
---
gladeui/glade-project.c | 8 +++++++-
1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/gladeui/glade-project.c b/gladeui/glade-project.c
index 6f2b202..904af00 100644
--- a/gladeui/glade-project.c
+++ b/gladeui/glade-project.c
@@ -2483,7 +2483,13 @@ glade_project_get_graph_deps (GladeProject *project)
for (ll = _glade_widget_peek_prop_refs (predecessor); ll; ll = g_list_next (ll))
{
GladeWidget *successor = glade_property_get_widget (ll->data);
- GladeWidget *successor_top = glade_widget_get_toplevel (successor);
+ GladeWidget *successor_top;
+
+ /* Ignore widgets that are not part of this project. (ie removed ones) */
+ if (glade_widget_get_project (successor) != project)
+ continue;
+
+ successor_top = glade_widget_get_toplevel (successor);

/* Ignore objects within the same toplevel */
if (predecessor_top != successor_top)

[k***@rockbox.org]

From: Juan Pablo Ugarte <***@gmail.com>

_glade_tsort() simplyfied api by using a GList for edges instead of a
custom linked struct since we do not need the marginal speedup
now that dependencies are only between toplevels.
This allow us to easily sort edges alphabetically.

tests/toplevel-order: Updated to new _glade_tsort() api

Conflicts:
tests/toplevel-order.c
tests/toplevel_order_test6.glade
---
gladeui/glade-tsort.c | 62 ++++++++++++++++++++++++++-------------------------
gladeui/glade-tsort.h | 13 +++++------
2 files changed, 38 insertions(+), 37 deletions(-)

diff --git a/gladeui/glade-tsort.c b/gladeui/glade-tsort.c
index 439da33..5d43f70 100644
--- a/gladeui/glade-tsort.c
+++ b/gladeui/glade-tsort.c
@@ -34,8 +34,8 @@
*
* Returns: the new start of the node list.
*/
-_NodeEdge *
-_node_edge_prepend (_NodeEdge *node,
+GList *
+_node_edge_prepend (GList *list,
gpointer predecessor,
gpointer successor)
{
@@ -43,34 +43,44 @@ _node_edge_prepend (_NodeEdge *node,

edge->predecessor = predecessor;
edge->successor = successor;
- edge->next = node;

- return edge;
+ return g_list_prepend (list, edge);
+}
+
+static void
+_node_edge_free (gpointer data)
+{
+ g_slice_free (_NodeEdge, data);
}

void
-_node_edge_free (_NodeEdge *node)
+_node_edge_list_free (GList *list)
{
- g_slice_free_chain (_NodeEdge, node, next);
+ g_list_free_full (list, _node_edge_free);
}

static inline void
-tsort_remove_non_start_nodes (GList **nodes, _NodeEdge *edges)
+tsort_remove_non_start_nodes (GList **nodes, GList *edges)
{
- _NodeEdge *edge;
+ GList *l;

- for (edge = edges; edge; edge = edge->next)
- *nodes = g_list_remove (*nodes, edge->successor);
+ for (l = edges; l; l = g_list_next (l))
+ {
+ _NodeEdge *edge = l->data;
+ *nodes = g_list_remove (*nodes, edge->successor);
+ }
}


static inline gboolean
-tsort_node_has_no_incoming_edge (gpointer node, _NodeEdge *edges)
+tsort_node_has_no_incoming_edge (gpointer node, GList *edges)
{
- _NodeEdge *edge;
+ GList *l;

- for (edge = edges; edge; edge = edge->next)
+ for (l = edges; l; l = g_list_next (l))
{
+ _NodeEdge *edge = l->data;
+
if (node == edge->successor)
return FALSE;
}
@@ -106,7 +116,7 @@ tsort_node_has_no_incoming_edge (gpointer node, _NodeEdge *edges)
* Returns: a new list sorted by dependency including nodes only present in @edges
*/
GList *
-_glade_tsort (GList **nodes, _NodeEdge **edges)
+_glade_tsort (GList **nodes, GList **edges)
{
GList *sorted_nodes;

@@ -119,7 +129,7 @@ _glade_tsort (GList **nodes, _NodeEdge **edges)
/* while S is non-empty do */
while (*nodes)
{
- _NodeEdge *edge, *next, *prev = NULL;
+ GList *l, *next;
gpointer n;

/* remove a node n from S */
@@ -128,23 +138,20 @@ _glade_tsort (GList **nodes, _NodeEdge **edges)

/* insert n into L */
/*if (!glade_widget_get_parent (n)) this would be a specific optimization */
- sorted_nodes = g_list_prepend (sorted_nodes, n);
+ sorted_nodes = g_list_prepend (sorted_nodes, n);

/* for each node m ... */
- for (edge = *edges; edge; edge = next)
+ for (l = *edges; l; l = next)
{
- next = edge->next;
+ _NodeEdge *edge = l->data;
+
+ next = g_list_next (l);

/* ... with an edge e from n to m do */
if (edge->predecessor == n)
{
/* remove edge e from the graph */
- if (prev)
- prev->next = (prev->next) ? prev->next->next : NULL;
- else
- /* edge is the first element in the list so we only need to
- * change the start of the list */
- *edges = next;
+ *edges = g_list_delete_link (*edges, l);

/* if m has no other incoming edges then */
if (tsort_node_has_no_incoming_edge (edge->successor, *edges))
@@ -153,11 +160,6 @@ _glade_tsort (GList **nodes, _NodeEdge **edges)

g_slice_free (_NodeEdge, edge);
}
- else
- /* Keep a pointer to the previous node in the iteration to make
- * things easier when removing a node
- */
- prev = edge;
}
}

@@ -166,7 +168,7 @@ _glade_tsort (GList **nodes, _NodeEdge **edges)
if (*edges)
{
g_list_free (sorted_nodes);
- g_slice_free_chain (_NodeEdge, *edges, next);
+ _node_edge_list_free (*edges);
*edges = NULL;
return NULL;
}
diff --git a/gladeui/glade-tsort.h b/gladeui/glade-tsort.h
index 3026e2d..28ed6e4 100644
--- a/gladeui/glade-tsort.h
+++ b/gladeui/glade-tsort.h
@@ -34,17 +34,16 @@ struct __NodeEdge
{
gpointer predecessor;
gpointer successor;
- _NodeEdge *next;
};

-_NodeEdge *_node_edge_prepend (_NodeEdge *node,
- gpointer predecessor,
- gpointer successor);
+GList *_node_edge_prepend (GList *list,
+ gpointer predecessor,
+ gpointer successor);

-void _node_edge_free (_NodeEdge *node);
+void _node_edge_list_free (GList *list);

-GList *_glade_tsort (GList **nodes,
- _NodeEdge **edges);
+GList *_glade_tsort (GList **nodes,
+ GList **edges);

G_END_DECLS