[glade/glade-3-16] GladeProject: Changed the way we calculate graph dependencies. Instead of using glade_widget_depends

[Juan Pablo Ugarte <jpu src gnome org>]

commit e8156d281d0275b8fd10f47d15eb43f87e6277d4
Author: Juan Pablo Ugarte <juanpablougarte gmail com>
Date:   Wed Dec 11 17:40:55 2013 -0300

    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 953bf38..4febc3c 100644
--- a/gladeui/glade-project.c
+++ b/gladeui/glade-project.c
@@ -2110,7 +2110,16 @@ glade_project_write_resource_path (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
@@ -2134,64 +2143,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;
-
-          successor_top = glade_widget_get_toplevel (successor);
+          GladeWidget *successor = glade_property_get_widget (ll->data);
+          GladeWidget *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);
@@ -2215,11 +2207,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;
@@ -2235,27 +2229,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);
@@ -2267,11 +2303,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 ce03ad1..601a396 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 273076b..b385bd1 100644
--- a/plugins/gtk+/gtk+.xml.in
+++ b/plugins/gtk+/gtk+.xml.in
@@ -15,7 +15,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>