[glade] GladeCatalog: implemented catalog dependency sorting using _glade_tsort() Now we detect circular dep

[Juan Pablo Ugarte <jpu src gnome org>]

commit 44566c5f3d8c14d01408e8043bd946cac3d877ee
Author: Juan Pablo Ugarte <juanpablougarte gmail com>
Date:   Wed Dec 4 21:00:14 2013 -0300

    GladeCatalog: implemented catalog dependency sorting using _glade_tsort()
    Now we detect circular dependencies!
    
    Added private functions _glade_catalog_get_catalog() and _glade_catalog_tsort()

 gladeui/glade-catalog.c |  146 ++++++++++++++++++++++++++++-------------------
 gladeui/glade-private.h |    5 ++
 2 files changed, 93 insertions(+), 58 deletions(-)
---
diff --git a/gladeui/glade-catalog.c b/gladeui/glade-catalog.c
index 0be542e..39fa24a 100644
--- a/gladeui/glade-catalog.c
+++ b/gladeui/glade-catalog.c
@@ -25,6 +25,8 @@
 #include "glade.h"
 #include "glade-catalog.h"
 #include "glade-widget-adaptor.h"
+#include "glade-private.h"
+#include "glade-tsort.h"
 
 #include <string.h>
 #include <sys/types.h>
@@ -171,6 +173,7 @@ catalog_open (const gchar *filename)
   GladeXmlContext *context;
   GladeXmlDoc *doc;
   GladeXmlNode *root;
+  gchar *name;
 
   /* get the context & root node of the catalog file */
   context = glade_xml_context_new_from_path (filename,
@@ -192,17 +195,12 @@ catalog_open (const gchar *filename)
       return NULL;
     }
 
+  if (!(name = glade_xml_get_property_string_required (root, GLADE_TAG_NAME, NULL)))
+    return NULL;
+
   catalog = catalog_allocate ();
   catalog->context = context;
-  catalog->name = glade_xml_get_property_string (root, GLADE_TAG_NAME);
-
-  if (!catalog->name)
-    {
-      g_warning ("Couldn't find required property 'name' in catalog root node");
-      catalog_destroy (catalog);
-      return NULL;
-    }
-
+  catalog->name = name;
 
   glade_xml_get_property_version (root, GLADE_TAG_VERSION,
                                   &catalog->major_version,
@@ -426,54 +424,80 @@ catalog_load (GladeCatalog *catalog)
   return;
 }
 
+static GladeCatalog *
+catalog_find_by_name (GList *catalogs, const gchar *name)
+{
+  if (name)
+    {
+      GList *l;
+      for (l = catalogs; l; l = g_list_next (l))
+        {
+          GladeCatalog *catalog = l->data;
+          if (g_strcmp0 (catalog->name, name) == 0)
+            return catalog;
+        }
+    }
+  
+  return NULL;
+}
+
 static gint
-catalog_find_by_name (GladeCatalog *catalog, const gchar *name)
+catalog_name_cmp (gconstpointer a, gconstpointer b)
 {
-  return strcmp (catalog->name, name);
+  return (a && b) ? g_strcmp0 (GLADE_CATALOG(a)->name, GLADE_CATALOG(b)->name) : 0;
 }
 
 static GList *
-catalog_sort (GList *catalogs)
+glade_catalog_tsort (GList *catalogs, gboolean loading)
 {
-  GList *l, *node, *sorted = NULL, *sort;
-  GladeCatalog *catalog, *cat;
+  GList *l, *sorted = NULL;
+  GList *deps = NULL;
+
+  /* Sort alphabetically first */
+  catalogs = g_list_sort (catalogs, catalog_name_cmp);
 
-  /* Add all dependant catalogs to the sorted list first */
-  for (l = catalogs; l; l = l->next)
+  /* Generate dependency graph edges */
+  for (l = catalogs; l; l = g_list_next (l))
     {
-      catalog = l->data;
-      sort = NULL;
+      GladeCatalog *catalog = l->data, *dep;
 
-      /* itterate ascending through dependancy hierarchy */
-      while (catalog->dep_catalog)
-        {
-          node = g_list_find_custom
-              (catalogs, catalog->dep_catalog,
-               (GCompareFunc) catalog_find_by_name);
+      if (!catalog->dep_catalog)
+        continue;
 
-          if (!node || (cat = node->data) == NULL)
-            {
-              g_critical ("Catalog %s depends on catalog %s, not found",
-                          catalog->name, catalog->dep_catalog);
-              break;
-            }
+      if ((dep = catalog_find_by_name ((loading) ? catalogs : loaded_catalogs,
+                                       catalog->dep_catalog)))
+        deps = _node_edge_prepend (deps, dep, catalog);
+      else
+        g_critical ("Catalog %s depends on catalog %s, not found",
+                    catalog->name, catalog->dep_catalog);
+    }
 
-          /* Prepend to sort list */
-          if (g_list_find (sort, cat) == NULL &&
-              g_list_find (sorted, cat) == NULL)
-            sort = g_list_prepend (sort, cat);
+  sorted = _glade_tsort (&catalogs, &deps);
 
-          catalog = cat;
+  if (deps)
+    {
+      GList *l, *cycles = NULL;
+      
+      g_warning ("Circular dependency detected loading catalogs, they will be ignored");
+
+      for (l = deps; l; l = g_list_next (l))
+        {
+          _NodeEdge *edge = l->data;
+
+          g_message ("\t%s depends on %s",
+                     GLADE_CATALOG (edge->successor)->name,
+                     GLADE_CATALOG (edge->successor)->dep_catalog);
+          
+          if (loading && !g_list_find (cycles, edge->successor))
+            cycles = g_list_prepend (cycles, edge->successor);
         }
-      sorted = g_list_concat (sorted, sort);
-    }
 
-  /* Append all independant catalogs after */
-  for (l = catalogs; l; l = l->next)
-    if (g_list_find (sorted, l->data) == NULL)
-      sorted = g_list_append (sorted, l->data);
+      if (cycles)
+        g_list_free_full (cycles, (GDestroyNotify) catalog_destroy);
+
+      _node_edge_list_free (deps);
+    }
 
-  g_list_free (catalogs);
   return sorted;
 }
 
@@ -515,11 +539,10 @@ catalogs_from_path (GList *catalogs, const gchar *path)
             {
               /* Verify that we are not loading the same catalog twice !
                */
-              if (!g_list_find_custom (catalogs, catalog->name,
-                                       (GCompareFunc) catalog_find_by_name))
-                catalogs = g_list_prepend (catalogs, catalog);
-              else
+              if (catalog_find_by_name (catalogs, catalog->name))
                 catalog_destroy (catalog);
+              else
+                catalogs = g_list_prepend (catalogs, catalog);
             }
           else
             g_warning ("Unable to open the catalog file %s.\n", filename);
@@ -622,7 +645,7 @@ glade_catalog_load_all (void)
    * the gtk+ catalog, but some custom toolkits may depend
    * on the gnome catalog for instance.
    */
-  catalogs = catalog_sort (catalogs);
+  catalogs = glade_catalog_tsort (catalogs, TRUE);
 
   /* After sorting, execute init function and then load */
   for (l = catalogs; l; l = g_list_next (l))
@@ -809,19 +832,9 @@ glade_catalog_get_adaptors (GladeCatalog *catalog)
 gboolean
 glade_catalog_is_loaded (const gchar *name)
 {
-  GList *l;
-
   g_return_val_if_fail (name != NULL, FALSE);
   g_assert (loaded_catalogs != NULL);
-
-  for (l = loaded_catalogs; l; l = l->next)
-    {
-      GladeCatalog *catalog = GLADE_CATALOG (l->data);
-      if (strcmp (catalog->name, name) == 0)
-        return TRUE;
-    }
-
-  return FALSE;
+  return catalog_find_by_name (loaded_catalogs, name) != NULL;
 }
 
 /**
@@ -905,3 +918,20 @@ glade_widget_group_get_adaptors (GladeWidgetGroup *group)
 
   return group->adaptors;
 }
+
+/* Private API */
+
+GladeCatalog *
+_glade_catalog_get_catalog (const gchar *name)
+{
+  g_return_val_if_fail (name != NULL, NULL);
+  g_assert (loaded_catalogs != NULL);
+
+  return catalog_find_by_name (loaded_catalogs, name);
+}
+
+GList *
+_glade_catalog_tsort (GList *catalogs)
+{
+  return glade_catalog_tsort (catalogs, FALSE);
+}
diff --git a/gladeui/glade-private.h b/gladeui/glade-private.h
index ea35011..0de48b2 100644
--- a/gladeui/glade-private.h
+++ b/gladeui/glade-private.h
@@ -30,6 +30,11 @@
 
 G_BEGIN_DECLS
 
+/* glade-catalog.c */
+
+GladeCatalog *_glade_catalog_get_catalog (const gchar *name);
+GList        *_glade_catalog_tsort       (GList *catalogs);
+
 /* glade-xml-utils.c */
 
 /* GladeXml Error handling */