backport from gnome-menus

6 files changed, 1793 insertions, 1160 deletions

diff --git a/libmenu/desktop-entries.c b/libmenu/desktop-entries.c
index c9fcc0f..4793bdd 100644
--- a/libmenu/desktop-entries.c
+++ b/libmenu/desktop-entries.c
@@ -20,39 +20,49 @@
 #include <config.h>
 
 #include "desktop-entries.h"
+#include <gio/gdesktopappinfo.h>
 
 #include <string.h>
 
 #include "menu-util.h"
 
 #define DESKTOP_ENTRY_GROUP     "Desktop Entry"
-#define KDE_DESKTOP_ENTRY_GROUP "KDE Desktop Entry"
 
-enum {
-	DESKTOP_ENTRY_NO_DISPLAY     = 1 << 0,
-	DESKTOP_ENTRY_HIDDEN         = 1 << 1,
-	DESKTOP_ENTRY_SHOW_IN_MATE   = 1 << 2,
-	DESKTOP_ENTRY_TRYEXEC_FAILED = 1 << 3
+struct DesktopEntry
+{
+  guint       refcount;
+
+  char       *path;
+  const char *basename;
+
+  guint       type      : 2;
+  guint       reserved  : 30;
 };
 
-struct DesktopEntry {
-	char* path;
-	char* basename;
+typedef struct
+{
+  DesktopEntry     base;
+
+  GDesktopAppInfo *appinfo;
+  GQuark          *categories;
+} DesktopEntryDesktop;
 
-	GQuark* categories;
+typedef struct
+{
+  DesktopEntry base;
 
-	char* name;
-	char* generic_name;
+  char     *name;
+  char     *generic_name;
+  char     *comment;
+  GIcon    *icon;
 	char* full_name;
-	char* comment;
-	char* icon;
 	char* exec;
-	gboolean terminal;
 
-	guint type: 2;
-	guint flags: 4;
-	guint refcount: 24;
-};
+  guint     nodisplay   : 1;
+  guint     hidden      : 1;
+  guint     showin      : 1;
+	guint terminal:1;
+} DesktopEntryDirectory;
 
 struct DesktopEntrySet {
 	int refcount;
@@ -63,54 +73,110 @@ struct DesktopEntrySet {
  * Desktop entries
  */
 
-static guint get_flags_from_key_file(DesktopEntry* entry, GKeyFile* key_file, const char* desktop_entry_group)
-{
-  GError    *error;
-  char     **strv;
-  gboolean   no_display;
-  gboolean   hidden;
-  gboolean   show_in_mate;
-  gboolean   tryexec_failed;
-  char      *tryexec;
-  guint      flags;
-  int        i;
-
-  error = NULL;
-  no_display = g_key_file_get_boolean (key_file,
-                                       desktop_entry_group,
-                                       "NoDisplay",
-                                       &error);
-  if (error)
-    {
-      no_display = FALSE;
-      g_error_free (error);
-    }
+/**
+ * unix_basename_from_path:
+ * @path: Path string
+ *
+ * Returns: A constant pointer into the basename of @path
+ */
+static const char *
+unix_basename_from_path (const char *path)
+{
+  const char *basename = g_strrstr (path, "/");
+  if (basename)
+    return basename + 1;
+  else
+    return path;
+}
+
+static const char *
+get_current_desktop (void)
+{
+  static char *current_desktop = NULL;
 
-  error = NULL;
-  hidden = g_key_file_get_boolean (key_file,
-                                   desktop_entry_group,
-                                   "Hidden",
-                                   &error);
-  if (error)
+  /* Support XDG_CURRENT_DESKTOP environment variable; this can be used
+   * to abuse mate-menus in non-MATE desktops. */
+  if (!current_desktop)
     {
-      hidden = FALSE;
-      g_error_free (error);
+      const char *desktop;
+
+      desktop = g_getenv ("XDG_CURRENT_DESKTOP");
+
+      /* Note: if XDG_CURRENT_DESKTOP is set but empty, do as if it
+       * was not set */
+      if (!desktop || desktop[0] == '\0')
+        current_desktop = g_strdup ("MATE");
+      else
+        current_desktop = g_strdup (desktop);
     }
 
-  show_in_mate = TRUE;
+  /* Using "*" means skipping desktop-related checks */
+  if (g_strcmp0 (current_desktop, "*") == 0)
+    return NULL;
+
+  return current_desktop;
+}
+
+static GIcon *
+key_file_get_icon (GKeyFile *key_file)
+{
+  GIcon *icon = NULL;
+  gchar *icon_name;
+
+  icon_name = g_key_file_get_locale_string (key_file, DESKTOP_ENTRY_GROUP,
+                                            "Icon", NULL, NULL);
+  if (!icon_name)
+    return NULL;
+
+  if (g_path_is_absolute (icon_name)) {
+    GFile *file;
+
+    file = g_file_new_for_path (icon_name);
+    icon = g_file_icon_new (file);
+    g_object_unref (file);
+  } else {
+    char *p;
+
+    /* Work around a common mistake in desktop files */
+    if ((p = strrchr (icon_name, '.')) != NULL &&
+        (strcmp (p, ".png") == 0 ||
+         strcmp (p, ".xpm") == 0 ||
+         strcmp (p, ".svg") == 0))
+      *p = 0;
+
+    icon = g_themed_icon_new (icon_name);
+  }
+
+  g_free (icon_name);
+
+  return icon;
+}
+
+static gboolean
+key_file_get_show_in (GKeyFile *key_file)
+{
+  const gchar *current_desktop;
+  gchar **strv;
+  gboolean show_in = TRUE;
+  int i;
+
+  current_desktop = get_current_desktop ();
+  if (!current_desktop)
+    return TRUE;
+
   strv = g_key_file_get_string_list (key_file,
-                                     desktop_entry_group,
+                                     DESKTOP_ENTRY_GROUP,
                                      "OnlyShowIn",
                                      NULL,
                                      NULL);
   if (strv)
     {
-      show_in_mate = FALSE;
+      show_in = FALSE;
       for (i = 0; strv[i]; i++)
         {
-          if (!strcmp (strv[i], "MATE"))
+          if (!strcmp (strv[i], current_desktop))
             {
-              show_in_mate = TRUE;
+              show_in = TRUE;
               break;
             }
         }
@@ -118,198 +184,141 @@ static guint get_flags_from_key_file(DesktopEntry* entry, GKeyFile* key_file, co
   else
     {
       strv = g_key_file_get_string_list (key_file,
-                                         desktop_entry_group,
+                                         DESKTOP_ENTRY_GROUP,
                                          "NotShowIn",
                                          NULL,
                                          NULL);
       if (strv)
         {
-          show_in_mate = TRUE;
+          show_in = TRUE;
           for (i = 0; strv[i]; i++)
             {
-              if (!strcmp (strv[i], "MATE"))
+              if (!strcmp (strv[i], current_desktop))
                 {
-                  show_in_mate = FALSE;
+                  show_in = FALSE;
                 }
             }
         }
     }
   g_strfreev (strv);
 
-  tryexec_failed = FALSE;
-  tryexec = g_key_file_get_string (key_file,
-                                   desktop_entry_group,
-                                   "TryExec",
-                                   NULL);
-  if (tryexec)
-    {
-      char *path;
-
-      path = g_find_program_in_path (g_strstrip (tryexec));
-
-      tryexec_failed = (path == NULL);
-
-      g_free (path);
-      g_free (tryexec);
-    }
-
-  flags = 0;
-  if (no_display)
-    flags |= DESKTOP_ENTRY_NO_DISPLAY;
-  if (hidden)
-    flags |= DESKTOP_ENTRY_HIDDEN;
-  if (show_in_mate)
-    flags |= DESKTOP_ENTRY_SHOW_IN_MATE;
-  if (tryexec_failed)
-    flags |= DESKTOP_ENTRY_TRYEXEC_FAILED;
-
-  return flags;
+  return show_in;
 }
 
-static GQuark* get_categories_from_key_file (DesktopEntry* entry, GKeyFile* key_file, const char* desktop_entry_group)
+static gboolean
+desktop_entry_load_directory (DesktopEntry  *entry,
+                              GKeyFile      *key_file,
+                              GError       **error)
 {
-  GQuark  *retval;
-  char   **strv;
-  gsize    len;
-  int      i;
+  DesktopEntryDirectory *entry_directory = (DesktopEntryDirectory*)entry;
+  char *type_str;
 
-  strv = g_key_file_get_string_list (key_file,
-                                     desktop_entry_group,
-                                     "Categories",
-                                     &len,
-                                     NULL);
-  if (!strv)
-    return NULL;
+  type_str = g_key_file_get_string (key_file, DESKTOP_ENTRY_GROUP, "Type", error);
+  if (!type_str)
+    return FALSE;
 
-  retval = g_new0 (GQuark, len + 1);
+  if (strcmp (type_str, "Directory") != 0)
+    {
+      g_set_error (error,
+                   G_KEY_FILE_ERROR,
+                   G_KEY_FILE_ERROR_INVALID_VALUE,
+                   "\"%s\" does not contain the correct \"Type\" value\n", entry->path);
+      g_free (type_str);
+      return FALSE;
+    }
 
-  for (i = 0; strv[i]; i++)
-    retval[i] = g_quark_from_string (strv[i]);
+  g_free (type_str);
 
-  g_strfreev (strv);
+  entry_directory->name = g_key_file_get_locale_string (key_file, DESKTOP_ENTRY_GROUP, "Name", NULL, error);
+  if (entry_directory->name == NULL)
+    return FALSE;
 
-  return retval;
+  entry_directory->generic_name = g_key_file_get_locale_string (key_file, DESKTOP_ENTRY_GROUP, "GenericName", NULL, NULL);
+  entry_directory->comment      = g_key_file_get_locale_string (key_file, DESKTOP_ENTRY_GROUP, "Comment", NULL, NULL);
+  entry_directory->icon         = key_file_get_icon (key_file);
+  entry_directory->nodisplay    = g_key_file_get_boolean (key_file,
+                                                          DESKTOP_ENTRY_GROUP,
+                                                          "NoDisplay",
+                                                          NULL);
+  entry_directory->hidden       = g_key_file_get_boolean (key_file,
+                                                          DESKTOP_ENTRY_GROUP,
+                                                          "Hidden",
+                                                          NULL);
+  entry_directory->showin       = key_file_get_show_in (key_file);
+
+  return TRUE;
 }
 
-static DesktopEntry* desktop_entry_load(DesktopEntry* entry)
+static gboolean
+desktop_entry_load (DesktopEntry *entry)
 {
-  DesktopEntry *retval = NULL;
-  GKeyFile     *key_file;
-  GError       *error;
-  const char   *desktop_entry_group;
-  char         *name_str;
-  char         *type_str;
-
-  key_file = g_key_file_new ();
-
-  error = NULL;
-  if (!g_key_file_load_from_file (key_file, entry->path, 0, &error))
-    {
-      menu_verbose ("Failed to load \"%s\": %s\n",
-                    entry->path, error->message);
-      g_error_free (error);
-      goto out;
-    }
-
-  if (g_key_file_has_group (key_file, DESKTOP_ENTRY_GROUP))
-    {
-      desktop_entry_group = DESKTOP_ENTRY_GROUP;
-    }
-  else
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
     {
-      menu_verbose ("\"%s\" contains no \"" DESKTOP_ENTRY_GROUP "\" group\n",
-                    entry->path);
+      DesktopEntryDesktop *entry_desktop = (DesktopEntryDesktop*)entry;
+      const char *categories_str;
 
-      if (g_key_file_has_group (key_file, KDE_DESKTOP_ENTRY_GROUP))
-        {
-          desktop_entry_group = KDE_DESKTOP_ENTRY_GROUP;
-          menu_verbose ("\"%s\" contains deprecated \"" KDE_DESKTOP_ENTRY_GROUP "\" group\n",
-                        entry->path);
-        }
-      else
+      entry_desktop->appinfo = g_desktop_app_info_new_from_filename (entry->path);
+      if (!entry_desktop->appinfo ||
+          !g_app_info_get_name (G_APP_INFO (entry_desktop->appinfo)) ||
+          !g_app_info_get_executable (G_APP_INFO (entry_desktop->appinfo)))
         {
-          goto out;
+          menu_verbose ("Failed to load \"%s\"\n", entry->path);
+          return FALSE;
         }
-    }
 
-  if (!g_key_file_has_key (key_file, desktop_entry_group, "Name", NULL))
-    {
-      menu_verbose ("\"%s\" contains no \"Name\" key\n", entry->path);
-      goto out;
-    }
+      categories_str = g_desktop_app_info_get_categories (entry_desktop->appinfo);
+      if (categories_str)
+        {
+          char **categories;
+          int i;
 
-  name_str = g_key_file_get_locale_string (key_file, desktop_entry_group, "Name", NULL, NULL);
-  if (!name_str)
-    {
-      menu_verbose ("\"%s\" contains an invalid \"Name\" key\n", entry->path);
-      goto out;
-    }
+          categories = g_strsplit (categories_str, ";", -1);
+          entry_desktop->categories = g_new0 (GQuark, g_strv_length (categories) + 1);
 
-  g_free (name_str);
+          for (i = 0; categories[i]; i++)
+            entry_desktop->categories[i] = g_quark_from_string (categories[i]);
 
-  type_str = g_key_file_get_string (key_file, desktop_entry_group, "Type", NULL);
-  if (!type_str)
-    {
-      menu_verbose ("\"%s\" contains no \"Type\" key\n", entry->path);
-      goto out;
-    }
+          g_strfreev (categories);
+        }
 
-  if ((entry->type == DESKTOP_ENTRY_DESKTOP && strcmp (type_str, "Application") != 0) ||
-      (entry->type == DESKTOP_ENTRY_DIRECTORY && strcmp (type_str, "Directory") != 0))
-    {
-      menu_verbose ("\"%s\" does not contain the correct \"Type\" value\n", entry->path);
-      g_free (type_str);
-      goto out;
+      return TRUE;
     }
-
-  g_free (type_str);
-
-  if (entry->type == DESKTOP_ENTRY_DESKTOP &&
-      !g_key_file_has_key (key_file, desktop_entry_group, "Exec", NULL))
+  else if (entry->type == DESKTOP_ENTRY_DIRECTORY)
     {
-      menu_verbose ("\"%s\" does not contain an \"Exec\" key\n", entry->path);
-      goto out;
-    }
-
-  retval = entry;
+      GKeyFile *key_file = NULL;
+      GError   *error = NULL;
+      gboolean  retval = FALSE;
 
-#define GET_LOCALE_STRING(n) g_key_file_get_locale_string (key_file, desktop_entry_group, (n), NULL, NULL)
+      key_file = g_key_file_new ();
 
-  retval->name         = GET_LOCALE_STRING ("Name");
-  retval->generic_name = GET_LOCALE_STRING ("GenericName");
-  retval->full_name    = GET_LOCALE_STRING ("X-MATE-FullName");
-  retval->comment      = GET_LOCALE_STRING ("Comment");
-  retval->icon         = GET_LOCALE_STRING ("Icon");
-  retval->flags        = get_flags_from_key_file (retval, key_file, desktop_entry_group);
-  retval->categories   = get_categories_from_key_file (retval, key_file, desktop_entry_group);
+      if (!g_key_file_load_from_file (key_file, entry->path, 0, &error))
+        goto out;
 
-  if (entry->type == DESKTOP_ENTRY_DESKTOP)
-    {
-      retval->exec = g_key_file_get_string (key_file, desktop_entry_group, "Exec", NULL);
-      retval->terminal = g_key_file_get_boolean (key_file, desktop_entry_group, "Terminal", NULL);
-    }
+      if (!desktop_entry_load_directory (entry, key_file, &error))
+        goto out;
 
-#undef GET_LOCALE_STRING
+      retval = TRUE;
 
-  menu_verbose ("Desktop entry \"%s\" (%s, %s, %s, %s, %s) flags: NoDisplay=%s, Hidden=%s, ShowInMATE=%s, TryExecFailed=%s\n",
-                retval->basename,
-                retval->name,
-                retval->generic_name ? retval->generic_name : "(null)",
-                retval->full_name ? retval->full_name : "(null)",
-                retval->comment ? retval->comment : "(null)",
-                retval->icon ? retval->icon : "(null)",
-                retval->flags & DESKTOP_ENTRY_NO_DISPLAY     ? "(true)" : "(false)",
-                retval->flags & DESKTOP_ENTRY_HIDDEN         ? "(true)" : "(false)",
-                retval->flags & DESKTOP_ENTRY_SHOW_IN_MATE  ? "(true)" : "(false)",
-                retval->flags & DESKTOP_ENTRY_TRYEXEC_FAILED ? "(true)" : "(false)");
+    out:
+      g_key_file_free (key_file);
 
- out:
-  g_key_file_free (key_file);
+      if (!retval)
+        {
+          if (error)
+            {
+              menu_verbose ("Failed to load \"%s\": %s\n", entry->path, error->message);
+              g_error_free (error);
+            }
+          else
+            menu_verbose ("Failed to load \"%s\"\n", entry->path);
+        }
 
-  if (!retval)
-    desktop_entry_unref (entry);
+      return retval;
+    }
+  else
+    g_assert_not_reached ();
 
-  return retval;
+  return FALSE;
 }
 
 DesktopEntry* desktop_entry_new(const char* path)
@@ -322,10 +331,12 @@ DesktopEntry* desktop_entry_new(const char* path)
   if (g_str_has_suffix (path, ".desktop"))
     {
       type = DESKTOP_ENTRY_DESKTOP;
+      retval = (DesktopEntry*)g_new0 (DesktopEntryDesktop, 1);
     }
   else if (g_str_has_suffix (path, ".directory"))
     {
       type = DESKTOP_ENTRY_DIRECTORY;
+      retval = (DesktopEntry*)g_new0 (DesktopEntryDirectory, 1);
     }
   else
     {
@@ -334,14 +345,18 @@ DesktopEntry* desktop_entry_new(const char* path)
       return NULL;
     }
 
-  retval = g_new0 (DesktopEntry, 1);
-
   retval->refcount = 1;
   retval->type     = type;
-  retval->basename = g_path_get_basename (path);
   retval->path     = g_strdup (path);
+  retval->basename = unix_basename_from_path (retval->path);
+
+  if (!desktop_entry_load (retval))
+    {
+      desktop_entry_unref (retval);
+      return NULL;
+    }
 
-  return desktop_entry_load (retval);
+  return retval;
 }
 
 DesktopEntry* desktop_entry_reload(DesktopEntry* entry)
@@ -350,31 +365,39 @@ DesktopEntry* desktop_entry_reload(DesktopEntry* entry)
 
   menu_verbose ("Re-loading desktop entry \"%s\"\n", entry->path);
 
-  g_free (entry->categories);
-  entry->categories = NULL;
-
-  g_free (entry->name);
-  entry->name = NULL;
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
+    {
+      DesktopEntryDesktop *entry_desktop = (DesktopEntryDesktop *) entry;
 
-  g_free (entry->generic_name);
-  entry->generic_name = NULL;
+      g_object_unref (entry_desktop->appinfo);
+      entry_desktop->appinfo = NULL;
 
-  g_free (entry->full_name);
-  entry->full_name = NULL;
+      g_free (entry_desktop->categories);
+      entry_desktop->categories = NULL;
+    }
+  else if (entry->type == DESKTOP_ENTRY_DIRECTORY)
+    {
+      DesktopEntryDirectory *entry_directory = (DesktopEntryDirectory*) entry;
 
-  g_free (entry->comment);
-  entry->comment = NULL;
+      g_free (entry_directory->name);
+      entry_directory->name = NULL;
 
-  g_free (entry->icon);
-  entry->icon = NULL;
+      g_free (entry_directory->comment);
+      entry_directory->comment = NULL;
 
-  g_free (entry->exec);
-  entry->exec = NULL;
+      g_object_unref (entry_directory->icon);
+      entry_directory->icon = NULL;
+    }
+  else
+    g_assert_not_reached ();
 
-  entry->terminal = 0;
-  entry->flags = 0;
+  if (!desktop_entry_load (entry))
+    {
+      desktop_entry_unref (entry);
+      return NULL;
+    }
 
-  return desktop_entry_load (entry);
+  return entry;
 }
 
 DesktopEntry* desktop_entry_ref(DesktopEntry* entry)
@@ -390,39 +413,55 @@ DesktopEntry* desktop_entry_ref(DesktopEntry* entry)
 DesktopEntry* desktop_entry_copy(DesktopEntry* entry)
 {
   DesktopEntry *retval;
-  int           i;
 
   menu_verbose ("Copying desktop entry \"%s\"\n",
                 entry->basename);
 
-  retval = g_new0 (DesktopEntry, 1);
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
+    retval = (DesktopEntry*)g_new0 (DesktopEntryDesktop, 1);
+  else if (entry->type == DESKTOP_ENTRY_DIRECTORY)
+    retval = (DesktopEntry*)g_new0 (DesktopEntryDirectory, 1);
+  else
+    g_assert_not_reached ();
 
   retval->refcount     = 1;
   retval->type         = entry->type;
-  retval->basename     = g_strdup (entry->basename);
   retval->path         = g_strdup (entry->path);
-  retval->name         = g_strdup (entry->name);
-  retval->generic_name = g_strdup (entry->generic_name);
-  retval->full_name    = g_strdup (entry->full_name);
-  retval->comment      = g_strdup (entry->comment);
-  retval->icon         = g_strdup (entry->icon);
-  retval->exec         = g_strdup (entry->exec);
-  retval->terminal     = entry->terminal;
-  retval->flags        = entry->flags;
-
-  i = 0;
-  if (entry->categories != NULL)
+  retval->basename     = unix_basename_from_path (retval->path);
+
+  if (retval->type == DESKTOP_ENTRY_DESKTOP)
     {
-      for (; entry->categories[i]; i++);
-    }
+      DesktopEntryDesktop *desktop_entry = (DesktopEntryDesktop*) entry;
+      DesktopEntryDesktop *retval_desktop_entry = (DesktopEntryDesktop*) retval;
+      int i;
+
+      retval_desktop_entry->appinfo = g_object_ref (desktop_entry->appinfo);
+
+      if (desktop_entry->categories != NULL)
+        {
+          i = 0;
+          for (; desktop_entry->categories[i]; i++);
 
-  retval->categories = g_new0 (GQuark, i + 1);
+          retval_desktop_entry->categories = g_new0 (GQuark, i + 1);
 
-  i = 0;
-  if (entry->categories != NULL)
+          i = 0;
+          for (; desktop_entry->categories[i]; i++)
+            retval_desktop_entry->categories[i] = desktop_entry->categories[i];
+        }
+      else
+        retval_desktop_entry->categories = NULL;
+    }
+  else if (entry->type == DESKTOP_ENTRY_DIRECTORY)
     {
-      for (; entry->categories[i]; i++)
-        retval->categories[i] = entry->categories[i];
+      DesktopEntryDirectory *entry_directory = (DesktopEntryDirectory*)entry;
+      DesktopEntryDirectory *retval_directory = (DesktopEntryDirectory*)retval;
+
+      retval_directory->name         = g_strdup (entry_directory->name);
+      retval_directory->comment      = g_strdup (entry_directory->comment);
+      retval_directory->icon         = g_object_ref (entry_directory->icon);
+      retval_directory->nodisplay    = entry_directory->nodisplay;
+      retval_directory->hidden       = entry_directory->hidden;
+      retval_directory->showin       = entry_directory->showin;
     }
 
   return retval;
@@ -434,37 +473,39 @@ void desktop_entry_unref(DesktopEntry* entry)
   g_return_if_fail (entry->refcount > 0);
 
   entry->refcount -= 1;
-  if (entry->refcount == 0)
-    {
-      g_free (entry->categories);
-      entry->categories = NULL;
+  if (entry->refcount != 0)
+    return;
 
-      g_free (entry->name);
-      entry->name = NULL;
+  g_free (entry->path);
+  entry->path = NULL;
 
-      g_free (entry->generic_name);
-      entry->generic_name = NULL;
-
-      g_free (entry->full_name);
-      entry->full_name = NULL;
-
-      g_free (entry->comment);
-      entry->comment = NULL;
-
-      g_free (entry->icon);
-      entry->icon = NULL;
-
-      g_free (entry->exec);
-      entry->exec = NULL;
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
+    {
+      DesktopEntryDesktop *desktop_entry = (DesktopEntryDesktop*) entry;
+      g_free (desktop_entry->categories);
+      if (desktop_entry->appinfo)
+        g_object_unref (desktop_entry->appinfo);
+    }
+  else if (entry->type == DESKTOP_ENTRY_DIRECTORY)
+    {
+      DesktopEntryDirectory *entry_directory = (DesktopEntryDirectory*) entry;
 
-      g_free (entry->basename);
-      entry->basename = NULL;
+      g_free (entry_directory->name);
+      entry_directory->name = NULL;
 
-      g_free (entry->path);
-      entry->path = NULL;
+      g_free (entry_directory->comment);
+      entry_directory->comment = NULL;
 
-      g_free (entry);
+      if (entry_directory->icon != NULL)
+        {
+          g_object_unref (entry_directory->icon);
+          entry_directory->icon = NULL;
+        }
     }
+  else
+    g_assert_not_reached ();
+
+  g_free (entry);
 }
 
 DesktopEntryType desktop_entry_get_type(DesktopEntry* entry)
@@ -485,78 +526,99 @@ desktop_entry_get_basename (DesktopEntry *entry)
 
 const char* desktop_entry_get_name(DesktopEntry* entry)
 {
-	return entry->name;
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
+    return g_app_info_get_name (G_APP_INFO (((DesktopEntryDesktop*)entry)->appinfo));
+  return ((DesktopEntryDirectory*)entry)->name;
 }
 
 const char* desktop_entry_get_generic_name(DesktopEntry* entry)
 {
-	return entry->generic_name;
-}
-
-const char* desktop_entry_get_full_name(DesktopEntry* entry)
-{
-  return entry->full_name;
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
+    return g_desktop_app_info_get_generic_name (((DesktopEntryDesktop*)entry)->appinfo);
+  return ((DesktopEntryDirectory*)entry)->generic_name;
 }
 
 const char* desktop_entry_get_comment(DesktopEntry* entry)
 {
-	return entry->comment;
-}
-
-const char* desktop_entry_get_icon(DesktopEntry* entry)
-{
-	return entry->icon;
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
+    return g_app_info_get_description (G_APP_INFO (((DesktopEntryDesktop*)entry)->appinfo));
+  return ((DesktopEntryDirectory*)entry)->comment;
 }
 
-const char* desktop_entry_get_exec(DesktopEntry* entry)
+GIcon *
+desktop_entry_get_icon (DesktopEntry *entry)
 {
-	return entry->exec;
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
+    return g_app_info_get_icon (G_APP_INFO (((DesktopEntryDesktop*)entry)->appinfo));
+  return ((DesktopEntryDirectory*)entry)->icon;
 }
 
-gboolean desktop_entry_get_launch_in_terminal(DesktopEntry* entry)
+gboolean desktop_entry_get_no_display (DesktopEntry *entry)
 {
-	return entry->terminal;
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
+    return g_desktop_app_info_get_nodisplay (((DesktopEntryDesktop*)entry)->appinfo);
+  return ((DesktopEntryDirectory*)entry)->nodisplay;
 }
 
 gboolean desktop_entry_get_hidden(DesktopEntry* entry)
 {
-	return (entry->flags & DESKTOP_ENTRY_HIDDEN) != 0;
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
+    return g_desktop_app_info_get_is_hidden (((DesktopEntryDesktop*)entry)->appinfo);
+  return ((DesktopEntryDirectory*)entry)->hidden;
 }
 
-gboolean desktop_entry_get_no_display(DesktopEntry* entry)
+gboolean
+desktop_entry_get_show_in (DesktopEntry *entry)
 {
-	return (entry->flags & DESKTOP_ENTRY_NO_DISPLAY) != 0;
-}
+  if (entry->type == DESKTOP_ENTRY_DESKTOP)
+    {
+      const char *current_desktop = get_current_desktop ();
 
-gboolean desktop_entry_get_show_in_mate(DesktopEntry* entry)
-{
-	return (entry->flags & DESKTOP_ENTRY_SHOW_IN_MATE) != 0;
+      if (current_desktop == NULL)
+        return TRUE;
+      else
+        return g_desktop_app_info_get_show_in (((DesktopEntryDesktop*)entry)->appinfo, current_desktop);
+    }
+  return ((DesktopEntryDirectory*)entry)->showin;
 }
 
-gboolean desktop_entry_get_tryexec_failed(DesktopEntry* entry)
+GDesktopAppInfo  *
+desktop_entry_get_app_info (DesktopEntry *entry)
 {
-	return (entry->flags & DESKTOP_ENTRY_TRYEXEC_FAILED) != 0;
+  g_return_val_if_fail (entry->type == DESKTOP_ENTRY_DESKTOP, NULL);
+  return ((DesktopEntryDesktop*)entry)->appinfo;
 }
 
 gboolean desktop_entry_has_categories(DesktopEntry* entry)
 {
-	return (entry->categories != NULL && entry->categories[0] != 0);
+  DesktopEntryDesktop *desktop_entry;
+  if (entry->type != DESKTOP_ENTRY_DESKTOP)
+    return FALSE;
+
+  desktop_entry = (DesktopEntryDesktop*) entry;
+  return (desktop_entry->categories != NULL && desktop_entry->categories[0] != 0);
 }
 
 gboolean desktop_entry_has_category(DesktopEntry* entry, const char* category)
 {
   GQuark quark;
   int    i;
+  DesktopEntryDesktop *desktop_entry;
+
+  if (entry->type != DESKTOP_ENTRY_DESKTOP)
+    return FALSE;
+
+  desktop_entry = (DesktopEntryDesktop*) entry;
 
-  if (entry->categories == NULL)
+  if (desktop_entry->categories == NULL)
     return FALSE;
 
   if (!(quark = g_quark_try_string (category)))
     return FALSE;
 
-  for (i = 0; entry->categories[i]; i++)
+  for (i = 0; desktop_entry->categories[i]; i++)
     {
-      if (quark == entry->categories[i])
+      if (quark == desktop_entry->categories[i])
         return TRUE;
     }
 
@@ -567,29 +629,36 @@ void desktop_entry_add_legacy_category(DesktopEntry* entry)
 {
   GQuark *categories;
   int     i;
+  DesktopEntryDesktop *desktop_entry;
+
+  g_return_if_fail (entry->type == DESKTOP_ENTRY_DESKTOP);
+
+  desktop_entry = (DesktopEntryDesktop*) entry;
 
   menu_verbose ("Adding Legacy category to \"%s\"\n",
                 entry->basename);
 
-  i = 0;
-  if (entry->categories != NULL)
+  if (desktop_entry->categories != NULL)
     {
-      for (; entry->categories[i]; i++);
-    }
+      i = 0;
+      for (; desktop_entry->categories[i]; i++);
 
-  categories = g_new0 (GQuark, i + 2);
+      categories = g_new0 (GQuark, i + 2);
 
-  i = 0;
-  if (entry->categories != NULL)
+      i = 0;
+      for (; desktop_entry->categories[i]; i++)
+        categories[i] = desktop_entry->categories[i];
+    }
+  else
     {
-      for (; entry->categories[i]; i++)
-        categories[i] = entry->categories[i];
+      categories = g_new0 (GQuark, 2);
+      i = 0;
     }
 
   categories[i] = g_quark_from_string ("Legacy");
 
-  g_free (entry->categories);
-  entry->categories = categories;
+  g_free (desktop_entry->categories);
+  desktop_entry->categories = categories;
 }
 
 /*
diff --git a/libmenu/desktop-entries.h b/libmenu/desktop-entries.h
index a67cc9f..4c86b4c 100644
--- a/libmenu/desktop-entries.h
+++ b/libmenu/desktop-entries.h
@@ -20,11 +20,9 @@
 #ifndef __DESKTOP_ENTRIES_H__
 #define __DESKTOP_ENTRIES_H__
 
-#include <glib.h>
+#include <gio/gdesktopappinfo.h>
 
-#ifdef __cplusplus
-extern "C" {
-#endif
+G_BEGIN_DECLS
 
 typedef enum {
 	DESKTOP_ENTRY_INVALID = 0,
@@ -41,29 +39,25 @@ DesktopEntry* desktop_entry_copy(DesktopEntry* entry);
 DesktopEntry* desktop_entry_reload(DesktopEntry* entry);
 void desktop_entry_unref(DesktopEntry* entry);
 
-DesktopEntryType desktop_entry_get_type(DesktopEntry* entry);
-const char* desktop_entry_get_path(DesktopEntry* entry);
-const char* desktop_entry_get_basename(DesktopEntry* entry);
-
-const char* desktop_entry_get_name(DesktopEntry* entry);
-const char* desktop_entry_get_generic_name(DesktopEntry* entry);
-const char* desktop_entry_get_full_name(DesktopEntry* entry);
-const char* desktop_entry_get_comment(DesktopEntry* entry);
-const char* desktop_entry_get_icon(DesktopEntry* entry);
-const char* desktop_entry_get_exec(DesktopEntry* entry);
-gboolean desktop_entry_get_launch_in_terminal(DesktopEntry* entry);
-
-gboolean desktop_entry_get_hidden(DesktopEntry* entry);
-gboolean desktop_entry_get_no_display(DesktopEntry* entry);
-gboolean desktop_entry_get_show_in_mate(DesktopEntry* entry);
-gboolean desktop_entry_get_tryexec_failed(DesktopEntry* entry);
-
-gboolean desktop_entry_has_categories(DesktopEntry* entry);
-gboolean desktop_entry_has_category(DesktopEntry* entry, const char* category);
+DesktopEntryType  desktop_entry_get_type     (DesktopEntry *entry);
+const char       *desktop_entry_get_path     (DesktopEntry *entry);
+const char       *desktop_entry_get_basename (DesktopEntry *entry);
+const char       *desktop_entry_get_name     (DesktopEntry *entry);
+const char       *desktop_entry_get_generic_name (DesktopEntry *entry);
+const char       *desktop_entry_get_comment  (DesktopEntry *entry);
+GIcon            *desktop_entry_get_icon     (DesktopEntry *entry);
+gboolean          desktop_entry_get_hidden   (DesktopEntry *entry);
+gboolean          desktop_entry_get_no_display (DesktopEntry *entry);
+gboolean          desktop_entry_get_show_in  (DesktopEntry *entry);
+
+/* Only valid for DESKTOP_ENTRY_DESKTOP */
+GDesktopAppInfo  *desktop_entry_get_app_info (DesktopEntry *entry);
+gboolean desktop_entry_has_categories (DesktopEntry *entry);
+gboolean desktop_entry_has_category   (DesktopEntry *entry,
+                                       const char   *category);
 
 void desktop_entry_add_legacy_category(DesktopEntry* src);
 
-
 typedef struct DesktopEntrySet DesktopEntrySet;
 
 DesktopEntrySet* desktop_entry_set_new(void);
@@ -83,8 +77,6 @@ typedef void (*DesktopEntrySetForeachFunc) (const char* file_id, DesktopEntry* e
 
 void desktop_entry_set_foreach(DesktopEntrySet* set, DesktopEntrySetForeachFunc func, gpointer user_data);
 
-#ifdef __cplusplus
-}
-#endif
+G_END_DECLS
 
 #endif /* __DESKTOP_ENTRIES_H__ */
diff --git a/libmenu/entry-directories.c b/libmenu/entry-directories.c
index 2b59b37..2a21807 100644
--- a/libmenu/entry-directories.c
+++ b/libmenu/entry-directories.c
@@ -61,7 +61,10 @@ struct CachedDir {
 	guint have_read_entries: 1;
 	guint deleted: 1;
 
-	guint references: 28;
+  guint references;
+
+  GFunc    notify;
+  gpointer notify_data;
 };
 
 struct CachedDirMonitor {
@@ -70,10 +73,23 @@ struct CachedDirMonitor {
 	gpointer user_data;
 };
 
-static void cached_dir_free(CachedDir* dir);
-static gboolean cached_dir_load_entries_recursive(CachedDir* dir, const char* dirname);
-
-static void handle_cached_dir_changed(MenuMonitor* monitor, MenuMonitorEvent event, const char* path, CachedDir* dir);
+static void     cached_dir_add_reference          (CachedDir *dir);
+static void     cached_dir_remove_reference       (CachedDir *dir);
+static void     cached_dir_free                   (CachedDir  *dir);
+static gboolean cached_dir_load_entries_recursive (CachedDir  *dir,
+                                                   const char *dirname);
+static void     cached_dir_unref                  (CachedDir *dir);
+static void     cached_dir_unref_noparent         (CachedDir *dir);
+static CachedDir * cached_dir_add_subdir          (CachedDir  *dir,
+                                                   const char *basename,
+                                                   const char *path);
+static gboolean cached_dir_remove_subdir          (CachedDir  *dir,
+                                                   const char *basename);
+
+static void handle_cached_dir_changed (MenuMonitor      *monitor,
+				       MenuMonitorEvent  event,
+				       const char       *path,
+				       CachedDir        *dir);
 
 /*
  * Entry directory cache
@@ -81,18 +97,41 @@ static void handle_cached_dir_changed(MenuMonitor* monitor, MenuMonitorEvent eve
 
 static CachedDir* dir_cache = NULL;
 
-static CachedDir* cached_dir_new(const char *name)
+static void
+clear_cache (CachedDir *dir,
+             gpointer  *cache)
 {
-	CachedDir* dir;
+  *cache = NULL;
+}
 
-	dir = g_new0(CachedDir, 1);
+static CachedDir *
+cached_dir_new (const char *name)
+{
+	CachedDir* dir;
 
-	dir->name = g_strdup(name);
+  dir = g_new0 (CachedDir, 1);
+  dir->name = g_strdup (name);
 
 	return dir;
 }
 
-static void cached_dir_free(CachedDir* dir)
+static CachedDir *
+cached_dir_new_full (const char *name,
+                     GFunc       notify,
+                     gpointer    notify_data)
+{
+  CachedDir *dir;
+
+  dir = cached_dir_new (name);
+
+  dir->notify = notify;
+  dir->notify_data = notify_data;
+
+  return dir;
+}
+
+static void
+cached_dir_free (CachedDir *dir)
 {
   if (dir->dir_monitor)
     {
@@ -114,7 +153,7 @@ static void cached_dir_free(CachedDir* dir)
   dir->entries = NULL;
 
   g_slist_foreach (dir->subdirs,
-                   (GFunc) cached_dir_free,
+                   (GFunc) cached_dir_unref_noparent,
                    NULL);
   g_slist_free (dir->subdirs);
   dir->subdirs = NULL;
@@ -123,6 +162,44 @@ static void cached_dir_free(CachedDir* dir)
   g_free (dir);
 }
 
+static CachedDir *
+cached_dir_ref (CachedDir *dir)
+{
+  dir->references++;
+  return dir;
+}
+
+static void
+cached_dir_unref (CachedDir *dir)
+{
+  if (--dir->references == 0)
+    {
+      CachedDir *parent;
+
+      parent = dir->parent;
+
+      if (parent != NULL)
+        cached_dir_remove_subdir (parent, dir->name);
+
+      if (dir->notify)
+        dir->notify (dir, dir->notify_data);
+
+      cached_dir_free (dir);
+    }
+}
+
+static void
+cached_dir_unref_noparent (CachedDir *dir)
+{
+  if (--dir->references == 0)
+    {
+      if (dir->notify)
+        dir->notify (dir, dir->notify_data);
+
+      cached_dir_free (dir);
+    }
+}
+
 static inline CachedDir* find_subdir(CachedDir* dir, const char* subdir)
 {
   GSList *tmp;
@@ -194,7 +271,9 @@ static CachedDir* cached_dir_lookup(const char* canonical)
   int         i;
 
   if (dir_cache == NULL)
-    dir_cache = cached_dir_new ("/");
+    dir_cache = cached_dir_new_full ("/",
+                                     (GFunc) clear_cache,
+                                     &dir_cache);
   dir = dir_cache;
 
   g_assert (canonical != NULL && canonical[0] == G_DIR_SEPARATOR);
@@ -208,12 +287,7 @@ static CachedDir* cached_dir_lookup(const char* canonical)
     {
       CachedDir *subdir;
 
-      if ((subdir = find_subdir (dir, split[i])) == NULL)
-        {
-          subdir = cached_dir_new (split[i]);
-          dir->subdirs = g_slist_prepend (dir->subdirs, subdir);
-          subdir->parent = dir;
-        }
+      subdir = cached_dir_add_subdir (dir, split[i], NULL);
 
       dir = subdir;
 
@@ -283,7 +357,10 @@ static gboolean cached_dir_remove_entry(CachedDir* dir, const char* basename)
   return FALSE;
 }
 
-static gboolean cached_dir_add_subdir(CachedDir* dir, const char* basename, const char* path)
+static CachedDir *
+cached_dir_add_subdir (CachedDir  *dir,
+                       const char *basename,
+                       const char *path)
 {
   CachedDir *subdir;
 
@@ -292,23 +369,23 @@ static gboolean cached_dir_add_subdir(CachedDir* dir, const char* basename, cons
   if (subdir != NULL)
     {
       subdir->deleted = FALSE;
-      return TRUE;
+      return subdir;
     }
 
   subdir = cached_dir_new (basename);
 
-  if (!cached_dir_load_entries_recursive (subdir, path))
+  if (path != NULL && !cached_dir_load_entries_recursive (subdir, path))
     {
       cached_dir_free (subdir);
-      return FALSE;
+      return NULL;
     }
 
   menu_verbose ("Caching dir \"%s\"\n", basename);
 
   subdir->parent = dir;
-  dir->subdirs = g_slist_prepend (dir->subdirs, subdir);
+  dir->subdirs = g_slist_prepend (dir->subdirs, cached_dir_ref (subdir));
 
-  return TRUE;
+  return subdir;
 }
 
 static gboolean cached_dir_remove_subdir(CachedDir* dir, const char* basename)
@@ -321,11 +398,8 @@ static gboolean cached_dir_remove_subdir(CachedDir* dir, const char* basename)
     {
       subdir->deleted = TRUE;
 
-      if (subdir->references == 0)
-        {
-          cached_dir_free (subdir);
-          dir->subdirs = g_slist_remove (dir->subdirs, subdir);
-        }
+      cached_dir_unref (subdir);
+      dir->subdirs = g_slist_remove (dir->subdirs, subdir);
 
       return TRUE;
     }
@@ -333,7 +407,11 @@ static gboolean cached_dir_remove_subdir(CachedDir* dir, const char* basename)
   return FALSE;
 }
 
-static void cached_dir_invoke_monitors(CachedDir* dir)
+static guint   monitors_idle_handler = 0;
+static GSList *pending_monitors_dirs = NULL;
+
+static void
+cached_dir_invoke_monitors (CachedDir *dir)
 {
   GSList *tmp;
 
@@ -348,9 +426,70 @@ static void cached_dir_invoke_monitors(CachedDir* dir)
       tmp = next;
     }
 
+  /* we explicitly don't invoke monitors of the parent since an
+   * event has been queued for it too */
+}
+
+static gboolean
+emit_monitors_in_idle (void)
+{
+  GSList *monitors_to_emit;
+  GSList *tmp;
+
+  monitors_to_emit = pending_monitors_dirs;
+
+  pending_monitors_dirs = NULL;
+  monitors_idle_handler = 0;
+
+  tmp = monitors_to_emit;
+  while (tmp != NULL)
+    {
+      CachedDir *dir = tmp->data;
+
+      cached_dir_invoke_monitors (dir);
+      cached_dir_remove_reference (dir);
+
+      tmp = tmp->next;
+    }
+
+  g_slist_free (monitors_to_emit);
+
+  return FALSE;
+}
+
+static void
+cached_dir_queue_monitor_event (CachedDir *dir)
+{
+  GSList *tmp;
+
+  tmp = pending_monitors_dirs;
+  while (tmp != NULL)
+    {
+      CachedDir *d    = tmp->data;
+      GSList    *next = tmp->next;
+
+      if (dir->parent == d->parent &&
+          g_strcmp0 (dir->name, d->name) == 0)
+        break;
+
+      tmp = next;
+    }
+
+  /* not found, so let's queue it */
+  if (tmp == NULL)
+    {
+      cached_dir_add_reference (dir);
+      pending_monitors_dirs = g_slist_append (pending_monitors_dirs, dir);
+    }
+
   if (dir->parent)
     {
-      cached_dir_invoke_monitors (dir->parent);
+      cached_dir_queue_monitor_event (dir->parent);
+    }
+
+  if (monitors_idle_handler == 0)
+    {
+      monitors_idle_handler = g_idle_add ((GSourceFunc) emit_monitors_in_idle, NULL);
     }
 }
 
@@ -360,16 +499,11 @@ static void handle_cached_dir_changed (MenuMonitor* monitor, MenuMonitorEvent ev
   char     *basename;
   char     *dirname;
 
-  menu_verbose ("'%s' notified of '%s' %s - invalidating cache\n",
-		dir->name,
-                path,
-                event == MENU_MONITOR_EVENT_CREATED ? ("created") :
-                event == MENU_MONITOR_EVENT_DELETED ? ("deleted") : ("changed"));
-
   dirname  = g_path_get_dirname  (path);
   basename = g_path_get_basename (path);
 
   dir = cached_dir_lookup (dirname);
+  cached_dir_add_reference (dir);
 
   if (g_str_has_suffix (basename, ".desktop") ||
       g_str_has_suffix (basename, ".directory"))
@@ -390,12 +524,12 @@ static void handle_cached_dir_changed (MenuMonitor* monitor, MenuMonitorEvent ev
           break;
         }
     }
-  else /* Try recursing */
+  else if (g_file_test (path, G_FILE_TEST_IS_DIR)) /* Try recursing */
     {
       switch (event)
         {
         case MENU_MONITOR_EVENT_CREATED:
-          handled = cached_dir_add_subdir (dir, basename, path);
+          handled = cached_dir_add_subdir (dir, basename, path) != NULL;
           break;
 
         case MENU_MONITOR_EVENT_CHANGED:
@@ -416,14 +550,22 @@ static void handle_cached_dir_changed (MenuMonitor* monitor, MenuMonitorEvent ev
 
   if (handled)
     {
+      menu_verbose ("'%s' notified of '%s' %s - invalidating cache\n",
+                    dir->name,
+                    path,
+                    event == MENU_MONITOR_EVENT_CREATED ? ("created") :
+                    event == MENU_MONITOR_EVENT_DELETED ? ("deleted") : ("changed"));
+
       /* CHANGED events don't change the set of desktop entries */
       if (event == MENU_MONITOR_EVENT_CREATED || event == MENU_MONITOR_EVENT_DELETED)
         {
           _entry_directory_list_empty_desktop_cache ();
         }
 
-      cached_dir_invoke_monitors (dir);
+      cached_dir_queue_monitor_event (dir);
     }
+
+  cached_dir_remove_reference (dir);
 }
 
 static void cached_dir_ensure_monitor(CachedDir* dir, const char* dirname)
@@ -554,7 +696,7 @@ static void cached_dir_remove_monitor(CachedDir* dir, EntryDirectory* ed, EntryD
 
 static void cached_dir_add_reference(CachedDir* dir)
 {
-  dir->references++;
+  cached_dir_ref (dir);
 
   if (dir->parent != NULL)
     {
@@ -568,29 +710,7 @@ static void cached_dir_remove_reference(CachedDir* dir)
 
   parent = dir->parent;
 
-  if (--dir->references == 0 && dir->deleted)
-    {
-      if (dir->parent != NULL)
-	{
-	  GSList *tmp;
-
-	  tmp = parent->subdirs;
-	  while (tmp != NULL)
-	    {
-	      CachedDir *subdir = tmp->data;
-
-	      if (!strcmp (subdir->name, dir->name))
-		{
-		  parent->subdirs = g_slist_delete_link (parent->subdirs, tmp);
-		  break;
-		}
-
-	      tmp = tmp->next;
-	    }
-	}
-
-      cached_dir_free (dir);
-    }
+  cached_dir_unref (dir);
 
   if (parent != NULL)
     {
diff --git a/libmenu/matemenu-tree.c b/libmenu/matemenu-tree.c
index 31623cf..4ce4d55 100644
--- a/libmenu/matemenu-tree.c
+++ b/libmenu/matemenu-tree.c
@@ -30,59 +30,72 @@
 #include "menu-util.h"
 #include "canonicalize.h"
 
-/*
- * FIXME: it might be useful to be able to construct a menu
- * tree from a traditional directory based menu hierarchy
- * too.
- */
+/* private */
+typedef struct MateMenuTreeItem MateMenuTreeItem;
+#define MATEMENU_TREE_ITEM(i)      ((MateMenuTreeItem *)(i))
+#define MATEMENU_TREE_DIRECTORY(i) ((MateMenuTreeDirectory *)(i))
+#define MATEMENU_TREE_ENTRY(i)     ((MateMenuTreeEntry *)(i))
+#define MATEMENU_TREE_SEPARATOR(i) ((MateMenuTreeSeparator *)(i))
+#define MATEMENU_TREE_HEADER(i)    ((MateMenuTreeHeader *)(i))
+#define MATEMENU_TREE_ALIAS(i)     ((MateMenuTreeAlias *)(i))
+
+enum {
+  PROP_0,
+
+  PROP_MENU_BASENAME,
+  PROP_MENU_PATH,
+  PROP_FLAGS
+};
 
-typedef enum
+/* Signals */
+enum
 {
-  MATEMENU_TREE_ABSOLUTE = 0,
-  MATEMENU_TREE_BASENAME = 1
-} MateMenuTreeType;
+  CHANGED,
+  LAST_SIGNAL
+};
 
-struct MateMenuTree
+static guint matemenu_tree_signals [LAST_SIGNAL] = { 0 };
+
+struct _MateMenuTree
 {
-  MateMenuTreeType type;
-  guint         refcount;
+  GObject       parent_instance;
 
   char *basename;
-  char *absolute_path;
+  char *non_prefixed_basename;
+  char *path;
   char *canonical_path;
 
   MateMenuTreeFlags flags;
-  MateMenuTreeSortKey sort_key;
 
   GSList *menu_file_monitors;
 
   MenuLayoutNode *layout;
   MateMenuTreeDirectory *root;
-
-  GSList *monitors;
-
-  gpointer       user_data;
-  GDestroyNotify dnotify;
+  GHashTable *entries_by_id;
 
   guint canonical : 1;
+  guint loaded    : 1;
 };
 
-typedef struct
-{
-  MateMenuTreeChangedFunc callback;
-  gpointer             user_data;
-} MateMenuTreeMonitor;
+G_DEFINE_TYPE (MateMenuTree, matemenu_tree, G_TYPE_OBJECT)
 
 struct MateMenuTreeItem
 {
+  volatile gint refcount;
+
   MateMenuTreeItemType type;
 
   MateMenuTreeDirectory *parent;
+  MateMenuTree *tree;
+};
 
-  gpointer       user_data;
-  GDestroyNotify dnotify;
+struct MateMenuTreeIter
+{
+  volatile gint refcount;
 
-  guint refcount;
+  MateMenuTreeItem *item;
+  GSList        *contents;
+  GSList        *contents_iter;
 };
 
 struct MateMenuTreeDirectory
@@ -100,23 +113,15 @@ struct MateMenuTreeDirectory
 	GSList           *layout_info;
 	GSList           *contents;
 
-	guint only_unallocated : 1;
-	guint is_root : 1;
-	guint is_nodisplay : 1;
-	guint layout_pending_separator : 1;
-	guint preprocessed : 1;
+  guint only_unallocated : 1;
+  guint is_nodisplay : 1;
+  guint layout_pending_separator : 1;
+  guint preprocessed : 1;
 
 	/* 16 bits should be more than enough; G_MAXUINT16 means no inline header */
 	guint will_inline_header : 16;
 };
 
-typedef struct
-{
-  MateMenuTreeDirectory directory;
-
-  MateMenuTree *tree;
-} MateMenuTreeDirectoryRoot;
-
 struct MateMenuTreeEntry
 {
   MateMenuTreeItem item;
@@ -125,7 +130,7 @@ struct MateMenuTreeEntry
   char         *desktop_file_id;
 
   guint is_excluded : 1;
-  guint is_nodisplay : 1;
+  guint is_unallocated : 1;
 };
 
 struct MateMenuTreeSeparator
@@ -148,13 +153,11 @@ struct MateMenuTreeAlias
   MateMenuTreeItem      *aliased_item;
 };
 
-static MateMenuTree *matemenu_tree_new                 (MateMenuTreeType    type,
-						  const char      *menu_file,
-						  gboolean         canonical,
-						  MateMenuTreeFlags   flags);
-static void      matemenu_tree_load_layout          (MateMenuTree       *tree);
+static gboolean  matemenu_tree_load_layout          (MateMenuTree       *tree,
+                                                  GError         **error);
 static void      matemenu_tree_force_reload         (MateMenuTree       *tree);
-static void      matemenu_tree_build_from_layout    (MateMenuTree       *tree);
+static gboolean  matemenu_tree_build_from_layout    (MateMenuTree       *tree,
+                                                  GError         **error);
 static void      matemenu_tree_force_rebuild        (MateMenuTree       *tree);
 static void      matemenu_tree_resolve_files        (MateMenuTree       *tree,
 						  GHashTable      *loaded_menu_files,
@@ -164,106 +167,6 @@ static void      matemenu_tree_invoke_monitors      (MateMenuTree       *tree);
 
 static void matemenu_tree_item_unref_and_unset_parent (gpointer itemp);
 
-/*
- * The idea is that we cache the menu tree for either a given
- * menu basename or an absolute menu path.
- * If no files exist in $XDG_DATA_DIRS for the basename or the
- * absolute path doesn't exist we just return (and cache) the
- * empty menu tree.
- * We also add a file monitor for the basename in each dir in
- * $XDG_DATA_DIRS, or the absolute path to the menu file, and
- * re-compute if there are any changes.
- */
-
-static GHashTable *matemenu_tree_cache = NULL;
-
-static inline char *
-get_cache_key (MateMenuTree      *tree,
-	       MateMenuTreeFlags  flags)
-{
-  const char *tree_name;
-
-  switch (tree->type)
-    {
-    case MATEMENU_TREE_ABSOLUTE:
-      tree_name = tree->canonical ? tree->canonical_path : tree->absolute_path;
-      break;
-
-    case MATEMENU_TREE_BASENAME:
-      tree_name = tree->basename;
-      break;
-
-    default:
-      g_assert_not_reached ();
-      break;
-    }
-
-  return g_strdup_printf ("%s:0x%x", tree_name, flags);
-}
-
-static void
-matemenu_tree_add_to_cache (MateMenuTree      *tree,
-			 MateMenuTreeFlags  flags)
-{
-  char *cache_key;
-
-  if (matemenu_tree_cache == NULL)
-    {
-      matemenu_tree_cache =
-        g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
-    }
-
-  cache_key = get_cache_key (tree, flags);
-
-  menu_verbose ("Adding menu tree to cache: %s\n", cache_key);
-
-  g_hash_table_replace (matemenu_tree_cache, cache_key, tree);
-}
-
-static void
-matemenu_tree_remove_from_cache (MateMenuTree      *tree,
-			      MateMenuTreeFlags  flags)
-{
-  char *cache_key;
-
-  cache_key = get_cache_key (tree, flags);
-
-  menu_verbose ("Removing menu tree from cache: %s\n", cache_key);
-
-  g_hash_table_remove (matemenu_tree_cache, cache_key);
-
-  g_free (cache_key);
-
-  if (g_hash_table_size (matemenu_tree_cache) == 0)
-    {
-      g_hash_table_destroy (matemenu_tree_cache);
-      matemenu_tree_cache = NULL;
-
-      _entry_directory_list_empty_desktop_cache ();
-    }
-}
-
-static MateMenuTree *
-matemenu_tree_lookup_from_cache (const char    *tree_name,
-			      MateMenuTreeFlags  flags)
-{
-  MateMenuTree *retval;
-  char     *cache_key;
-
-  if (matemenu_tree_cache == NULL)
-    return NULL;
-
-  cache_key = g_strdup_printf ("%s:0x%x", tree_name, flags);
-
-  menu_verbose ("Looking up '%s' from menu cache\n", cache_key);
-
-  retval = g_hash_table_lookup (matemenu_tree_cache, cache_key);
-
-  g_free (cache_key);
-
-  return retval ? matemenu_tree_ref (retval) : NULL;
-}
-
 typedef enum
 {
   MENU_FILE_MONITOR_INVALID = 0,
@@ -336,7 +239,7 @@ matemenu_tree_add_menu_file_monitor (MateMenuTree           *tree,
 {
   MenuFileMonitor *monitor;
 
-  monitor = g_new0 (MenuFileMonitor, 1);
+  monitor = g_slice_new0 (MenuFileMonitor);
 
   monitor->type = type;
 
@@ -411,7 +314,7 @@ remove_menu_file_monitor (MenuFileMonitor *monitor,
 
   monitor->type = MENU_FILE_MONITOR_INVALID;
 
-  g_free (monitor);
+  g_slice_free (MenuFileMonitor, monitor);
 }
 
 static void
@@ -426,63 +329,10 @@ matemenu_tree_remove_menu_file_monitors (MateMenuTree *tree)
   tree->menu_file_monitors = NULL;
 }
 
-static MateMenuTree *
-matemenu_tree_lookup_absolute (const char    *absolute,
-			    MateMenuTreeFlags  flags)
-{
-  MateMenuTree  *tree;
-  gboolean    canonical;
-  const char *canonical_path;
-  char       *freeme;
-
-  menu_verbose ("Looking up absolute path in tree cache: \"%s\"\n", absolute);
-
-  if ((tree = matemenu_tree_lookup_from_cache (absolute, flags)) != NULL)
-    return tree;
-
-  canonical = TRUE;
-  canonical_path = freeme = menu_canonicalize_file_name (absolute, FALSE);
-  if (canonical_path == NULL)
-    {
-      menu_verbose ("Failed to canonicalize absolute menu path \"%s\": %s\n",
-                    absolute, g_strerror (errno));
-      canonical = FALSE;
-      canonical_path = absolute;
-    }
-
-  if ((tree = matemenu_tree_lookup_from_cache (canonical_path, flags)) != NULL)
-    return tree;
-
-  tree = matemenu_tree_new (MATEMENU_TREE_ABSOLUTE, canonical_path, canonical, flags);
-
-  g_free (freeme);
-
-  return tree;
-}
-
-static MateMenuTree *
-matemenu_tree_lookup_basename (const char    *basename,
-			    MateMenuTreeFlags  flags)
-{
-  MateMenuTree *tree;
-
-  menu_verbose ("Looking up menu file in tree cache: \"%s\"\n", basename);
-
-  if ((tree = matemenu_tree_lookup_from_cache (basename, flags)) != NULL)
-    return tree;
-
-  return matemenu_tree_new (MATEMENU_TREE_BASENAME, basename, FALSE, flags);
-}
-
 static gboolean
-canonicalize_basename_with_config_dir (MateMenuTree   *tree,
-                                       const char *basename,
-                                       const char *config_dir)
+canonicalize_path (MateMenuTree  *tree,
+                   const char *path)
 {
-  char *path;
-
-  path = g_build_filename (config_dir, "menus",  basename,  NULL);
-
   tree->canonical_path = menu_canonicalize_file_name (path, FALSE);
   if (tree->canonical_path)
     {
@@ -498,9 +348,22 @@ canonicalize_basename_with_config_dir (MateMenuTree   *tree,
 					MENU_FILE_MONITOR_NONEXISTENT_FILE);
     }
 
+  return tree->canonical;
+}
+
+static gboolean
+canonicalize_basename_with_config_dir (MateMenuTree   *tree,
+                                       const char *basename,
+                                       const char *config_dir)
+{
+  gboolean  ret;
+  char     *path;
+
+  path = g_build_filename (config_dir, "menus",  basename,  NULL);
+  ret = canonicalize_path (tree, path);
   g_free (path);
 
-  return tree->canonical;
+  return ret;
 }
 
 static void
@@ -529,60 +392,75 @@ canonicalize_basename (MateMenuTree  *tree,
     }
 }
 
-static gboolean matemenu_tree_canonicalize_path(MateMenuTree* tree)
+static gboolean matemenu_tree_canonicalize_path(MateMenuTree* tree,
+                              GError   **error)
 {
-	if (tree->canonical)
-		return TRUE;
-
-	g_assert(tree->canonical_path == NULL);
+  const char *menu_file = NULL;
 
-	if (tree->type == MATEMENU_TREE_BASENAME)
-	{
-		matemenu_tree_remove_menu_file_monitors (tree);
-
-		if (strcmp(tree->basename, "mate-applications.menu") == 0 && g_getenv("XDG_MENU_PREFIX"))
-		{
-			char* prefixed_basename;
-			prefixed_basename = g_strdup_printf("%s%s", g_getenv("XDG_MENU_PREFIX"), tree->basename);
-			canonicalize_basename(tree, prefixed_basename);
-			g_free(prefixed_basename);
-		}
-
-		if (!tree->canonical)
-			canonicalize_basename(tree, tree->basename);
+  if (tree->canonical)
+    return TRUE;
 
-		if (tree->canonical)
-			menu_verbose("Successfully looked up menu_file for \"%s\": %s\n", tree->basename, tree->canonical_path);
-		else
-			menu_verbose("Failed to look up menu_file for \"%s\"\n", tree->basename);
-	}
-	else /* if (tree->type == MATEMENU_TREE_ABSOLUTE) */
-	{
-		tree->canonical_path = menu_canonicalize_file_name(tree->absolute_path, FALSE);
+	g_assert(tree->canonical_path == NULL);
 
-		if (tree->canonical_path != NULL)
-		{
-			menu_verbose("Successfully looked up menu_file for \"%s\": %s\n", tree->absolute_path, tree->canonical_path);
+  matemenu_tree_remove_menu_file_monitors (tree);
 
-			/*
-			* Replace the cache entry with the canonicalized version
-			*/
-			matemenu_tree_remove_from_cache (tree, tree->flags);
+  if (tree->path)
+    {
+      menu_file = tree->path;
+      canonicalize_path (tree, tree->path);
+    }
+  else
+    {
+      const gchar *xdg_menu_prefix;
 
-			matemenu_tree_remove_menu_file_monitors(tree);
-			matemenu_tree_add_menu_file_monitor(tree, tree->canonical_path, MENU_FILE_MONITOR_FILE);
+      menu_file = tree->basename;
+      xdg_menu_prefix = g_getenv ("XDG_MENU_PREFIX");
 
-			tree->canonical = TRUE;
+      if (xdg_menu_prefix != NULL)
+        {
+          gchar *prefixed_basename;
+
+          prefixed_basename = g_strdup_printf ("%sapplications.menu",
+                                               xdg_menu_prefix);
+
+          /* Some gnome-menus using applications just use "applications.menu"
+           * as the basename and expect gnome-menus to prefix it. Others (e.g.
+           * Alacarte) explicitly use "${XDG_MENU_PREFIX}applications.menu" as
+           * the basename, because they want to save changes to the right files
+           * in ~. In both cases, we want to use "applications-merged" as the
+           * merge directory (as required by the fd.o menu spec), so we save
+           * the non-prefixed basename and use it later when calling
+           * menu_layout_load().
+           */
+          if (!g_strcmp0 (tree->basename, "mate-applications.menu") ||
+              !g_strcmp0 (tree->basename, prefixed_basename))
+            {
+              canonicalize_basename (tree, prefixed_basename);
+              g_free (tree->non_prefixed_basename);
+              tree->non_prefixed_basename = g_strdup ("mate-applications.menu");
+            }
+          g_free (prefixed_basename);
+        }
 
-			matemenu_tree_add_to_cache (tree, tree->flags);
-		}
-		else
-		{
-			menu_verbose("Failed to look up menu_file for \"%s\"\n", tree->absolute_path);
-		}
-	}
+      if (!tree->canonical)
+        canonicalize_basename (tree, tree->basename);
+    }
 
-	return tree->canonical;
+  if (tree->canonical)
+    {
+      menu_verbose ("Successfully looked up menu_file for \"%s\": %s\n",
+                    menu_file, tree->canonical_path);
+      return TRUE;
+    }
+  else
+    {
+      g_set_error (error,
+                   G_IO_ERROR,
+                   G_IO_ERROR_FAILED,
+                   "Failed to look up menu_file for \"%s\"\n",
+                   menu_file);
+      return FALSE;
+    }
 }
 
 static void
@@ -601,96 +479,126 @@ matemenu_tree_force_recanonicalize (MateMenuTree *tree)
     }
 }
 
-MateMenuTree* matemenu_tree_lookup(const char* menu_file, MateMenuTreeFlags flags)
+/**
+ * matemenu_tree_new:
+ * @menu_basename: Basename of menu file
+ * @flags: Flags controlling menu content
+ *
+ * Returns: (transfer full): A new #MateMenuTree instance
+ */
+MateMenuTree *
+matemenu_tree_new (const char     *menu_basename,
+                MateMenuTreeFlags  flags)
 {
-  MateMenuTree *retval;
-
-  g_return_val_if_fail (menu_file != NULL, NULL);
-
-  flags &= MATEMENU_TREE_FLAGS_MASK;
-
-  if (g_path_is_absolute (menu_file))
-    retval = matemenu_tree_lookup_absolute (menu_file, flags);
-  else
-    retval = matemenu_tree_lookup_basename (menu_file, flags);
+  g_return_val_if_fail (menu_basename != NULL, NULL);
 
-  g_assert (retval != NULL);
-
-  return retval;
+  return g_object_new (MATEMENU_TYPE_TREE,
+                       "menu-basename", menu_basename,
+                       "flags", flags,
+                       NULL);
 }
 
-static MateMenuTree *
-matemenu_tree_new (MateMenuTreeType   type,
-		const char     *menu_file,
-		gboolean        canonical,
-		MateMenuTreeFlags  flags)
+/**
+ * matemenu_tree_new_fo_path:
+ * @menu_path: Path of menu file
+ * @flags: Flags controlling menu content
+ *
+ * Returns: (transfer full): A new #MateMenuTree instance
+ */
+MateMenuTree *
+matemenu_tree_new_for_path (const char     *menu_path,
+                         MateMenuTreeFlags  flags)
 {
-  MateMenuTree *tree;
+  g_return_val_if_fail (menu_path != NULL, NULL);
 
-  tree = g_new0 (MateMenuTree, 1);
+  return g_object_new (MATEMENU_TYPE_TREE,
+                       "menu-path", menu_path,
+                       "flags", flags,
+                       NULL);
+}
 
-  tree->type     = type;
-  tree->flags    = flags;
-  tree->refcount = 1;
+static GObject *
+matemenu_tree_constructor (GType                  type,
+                        guint                  n_construct_properties,
+                        GObjectConstructParam *construct_properties)
+{
+	GObject   *obj;
+	MateMenuTree *self;
 
-  tree->sort_key = MATEMENU_TREE_SORT_NAME;
+	obj = G_OBJECT_CLASS (matemenu_tree_parent_class)->constructor (type,
+                                                                     n_construct_properties,
+                                                                     construct_properties);
 
-  if (tree->type == MATEMENU_TREE_BASENAME)
-    {
-      g_assert (canonical == FALSE);
-      tree->basename = g_strdup (menu_file);
-    }
-  else
-    {
-      tree->canonical     = canonical != FALSE;
-      tree->absolute_path = g_strdup (menu_file);
+        /* If MateMenuTree:menu-path is set, then we should make sure that
+         * MateMenuTree:menu-basename is unset (especially as it has a default
+         * value). This has to be done here, in the constructor, since the
+         * properties are construct-only. */
 
-      if (tree->canonical)
-	{
-	  tree->canonical_path = g_strdup (menu_file);
-	  matemenu_tree_add_menu_file_monitor (tree,
-					    tree->canonical_path,
-					    MENU_FILE_MONITOR_FILE);
-	}
-      else
-	{
-	  matemenu_tree_add_menu_file_monitor (tree,
-					    tree->absolute_path,
-					    MENU_FILE_MONITOR_NONEXISTENT_FILE);
-	}
-    }
+	self = MATEMENU_TREE (obj);
 
-  matemenu_tree_add_to_cache (tree, tree->flags);
+        if (self->path != NULL)
+          g_object_set (self, "menu-basename", NULL, NULL);
 
-  return tree;
+	return obj;
 }
 
-MateMenuTree *
-matemenu_tree_ref (MateMenuTree *tree)
+static void
+matemenu_tree_set_property (GObject         *object,
+                         guint            prop_id,
+                         const GValue    *value,
+                         GParamSpec      *pspec)
 {
-  g_return_val_if_fail (tree != NULL, NULL);
-  g_return_val_if_fail (tree->refcount > 0, NULL);
+  MateMenuTree *self = MATEMENU_TREE (object);
+
+  switch (prop_id)
+    {
+    case PROP_MENU_BASENAME:
+      self->basename = g_value_dup_string (value);
+      break;
 
-  tree->refcount++;
+    case PROP_MENU_PATH:
+      self->path = g_value_dup_string (value);
+      break;
+
+    case PROP_FLAGS:
+      self->flags = g_value_get_flags (value);
+      break;
 
-  return tree;
+    default:
+      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+      break;
+    }
 }
 
-void
-matemenu_tree_unref (MateMenuTree *tree)
+static void
+matemenu_tree_get_property (GObject         *object,
+                         guint            prop_id,
+                         GValue          *value,
+                         GParamSpec      *pspec)
 {
-  g_return_if_fail (tree != NULL);
-  g_return_if_fail (tree->refcount >= 1);
-
-  if (--tree->refcount > 0)
-    return;
+  MateMenuTree *self = MATEMENU_TREE (object);
 
-  if (tree->dnotify)
-    tree->dnotify (tree->user_data);
-  tree->user_data = NULL;
-  tree->dnotify   = NULL;
+  switch (prop_id)
+    {
+    case PROP_MENU_BASENAME:
+      g_value_set_string (value, self->basename);
+      break;
+    case PROP_MENU_PATH:
+      g_value_set_string (value, self->path);
+      break;
+    case PROP_FLAGS:
+      g_value_set_flags (value, self->flags);
+      break;
+    default:
+      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+      break;
+    }
+}
 
-  matemenu_tree_remove_from_cache (tree, tree->flags);
+static void
+matemenu_tree_finalize (GObject *object)
+{
+  MateMenuTree *tree = MATEMENU_TREE (object);
 
   matemenu_tree_force_recanonicalize (tree);
 
@@ -698,81 +606,155 @@ matemenu_tree_unref (MateMenuTree *tree)
     g_free (tree->basename);
   tree->basename = NULL;
 
-  if (tree->absolute_path != NULL)
-    g_free (tree->absolute_path);
-  tree->absolute_path = NULL;
+  g_free (tree->non_prefixed_basename);
+  tree->non_prefixed_basename = NULL;
 
-  g_slist_foreach (tree->monitors, (GFunc) g_free, NULL);
-  g_slist_free (tree->monitors);
-  tree->monitors = NULL;
+  if (tree->path != NULL)
+    g_free (tree->path);
+  tree->path = NULL;
 
-  g_free (tree);
-}
+  if (tree->canonical_path != NULL)
+    g_free (tree->canonical_path);
+  tree->canonical_path = NULL;
 
-void
-matemenu_tree_set_user_data (MateMenuTree       *tree,
-			  gpointer        user_data,
-			  GDestroyNotify  dnotify)
-{
-  g_return_if_fail (tree != NULL);
+  g_hash_table_destroy (tree->entries_by_id);
+  tree->entries_by_id = NULL;
 
-  if (tree->dnotify != NULL)
-    tree->dnotify (tree->user_data);
+  G_OBJECT_CLASS (matemenu_tree_parent_class)->finalize (object);
+}
 
-  tree->dnotify   = dnotify;
-  tree->user_data = user_data;
+static void
+matemenu_tree_init (MateMenuTree *self)
+{
+  self->entries_by_id = g_hash_table_new (g_str_hash, g_str_equal);
 }
 
-gpointer
-matemenu_tree_get_user_data (MateMenuTree *tree)
+static void
+matemenu_tree_class_init (MateMenuTreeClass *klass)
 {
-  g_return_val_if_fail (tree != NULL, NULL);
+  GObjectClass *gobject_class = G_OBJECT_CLASS (klass);
 
-  return tree->user_data;
-}
+  gobject_class->constructor = matemenu_tree_constructor;
+  gobject_class->get_property = matemenu_tree_get_property;
+  gobject_class->set_property = matemenu_tree_set_property;
+  gobject_class->finalize = matemenu_tree_finalize;
 
+  /**
+   * MateMenuTree:menu-basename:
+   *
+   * The name of the menu file; must be a basename or a relative path. The file
+   * will be looked up in $XDG_CONFIG_DIRS/menus/. See the Desktop Menu
+   * specification.
+   */
+  g_object_class_install_property (gobject_class,
+                                   PROP_MENU_BASENAME,
+                                   g_param_spec_string ("menu-basename", "", "",
+                                                        "applications.menu",
+                                                        G_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
+  /**
+   * MateMenuTree:menu-path:
+   *
+   * The full path of the menu file. If set, MateMenuTree:menu-basename will get
+   * ignored.
+   */
+  g_object_class_install_property (gobject_class,
+                                   PROP_MENU_PATH,
+                                   g_param_spec_string ("menu-path", "", "",
+                                                        NULL,
+                                                        G_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
+  /**
+   * MateMenuTree:flags:
+   *
+   * Flags controlling the content of the menu.
+   */
+  g_object_class_install_property (gobject_class,
+                                   PROP_FLAGS,
+                                   g_param_spec_flags ("flags", "", "",
+                                                       MATEMENU_TYPE_TREE_FLAGS,
+                                                       MATEMENU_TREE_FLAGS_NONE,
+                                                       G_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
+
+  /**
+   * MateMenuTree:changed:
+   *
+   * This signal is emitted when applications are added, removed, or
+   * upgraded.  But note the new data will only be visible after
+   * matemenu_tree_load_sync() or a variant thereof is invoked.
+   */
+  matemenu_tree_signals[CHANGED] =
+      g_signal_new ("changed",
+                    G_TYPE_FROM_CLASS (klass),
+                    G_SIGNAL_RUN_LAST,
+                    0,
+                    NULL, NULL,
+                    g_cclosure_marshal_VOID__VOID,
+                    G_TYPE_NONE, 0);
+}
+
+/**
+ * matemenu_tree_get_canonical_menu_path:
+ * @tree: a #MateMenuTree
+ *
+ * This function is only available if the tree has been loaded via
+ * matemenu_tree_load_sync() or a variant thereof.
+ *
+ * Returns: The absolute and canonicalized path to the loaded menu file
+ */
 const char *
-matemenu_tree_get_menu_file (MateMenuTree *tree)
+matemenu_tree_get_canonical_menu_path (MateMenuTree *tree)
 {
-  /* FIXME: this is horribly ugly. But it's done to keep the API. Would be bad
-   * to break the API only for a "const char *" => "char *" change. The other
-   * alternative is to leak the memory, which is bad too. */
-  static char *ugly_result_cache = NULL;
+  g_return_val_if_fail (MATEMENU_IS_TREE (tree), NULL);
+  g_return_val_if_fail (tree->loaded, NULL);
 
-  g_return_val_if_fail (tree != NULL, NULL);
+  return tree->canonical_path;
+}
 
-  /* we need to canonicalize the path so we actually find out the real menu
-   * file that is being used -- and take into account XDG_MENU_PREFIX */
-  if (!matemenu_tree_canonicalize_path (tree))
-    return NULL;
+/**
+ * matemenu_tree_load_sync:
+ * @tree: a #MateMenuTree
+ * @error: a #GError
+ *
+ * Synchronously load the menu contents.  This function
+ * performs a significant amount of blocking I/O if the
+ * tree has not been loaded yet.
+ *
+ * Returns: %TRUE on success, %FALSE on error
+ */
+gboolean
+matemenu_tree_load_sync (MateMenuTree  *tree,
+                      GError    **error)
+{
+  GError *local_error = NULL;
 
-  if (ugly_result_cache != NULL)
-    {
-      g_free (ugly_result_cache);
-      ugly_result_cache = NULL;
-    }
+  if (tree->loaded)
+    return TRUE;
 
-  if (tree->type == MATEMENU_TREE_BASENAME)
+  if (!matemenu_tree_build_from_layout (tree, &local_error))
     {
-      ugly_result_cache = g_path_get_basename (tree->canonical_path);
-      return ugly_result_cache;
+      if (local_error)
+        g_propagate_error (error, local_error);
+      return FALSE;
     }
-  else
-    return tree->absolute_path;
+
+  tree->loaded = TRUE;
+
+  return TRUE;
 }
 
+/**
+ * matemenu_tree_get_root_directory:
+ * @tree: a #MateMenuTree
+ *
+ * Get the root directory; you must have loaded the tree first (at
+ * least once) via matemenu_tree_load_sync() or a variant thereof.
+ *
+ * Returns: (transfer full): Root of the tree
+ */
 MateMenuTreeDirectory *
 matemenu_tree_get_root_directory (MateMenuTree *tree)
 {
   g_return_val_if_fail (tree != NULL, NULL);
-
-  if (!tree->root)
-    {
-      matemenu_tree_build_from_layout (tree);
-
-      if (!tree->root)
-        return NULL;
-    }
+  g_return_val_if_fail (tree->loaded, NULL);
 
   return matemenu_tree_item_ref (tree->root);
 }
@@ -809,7 +791,7 @@ find_path (MateMenuTreeDirectory *directory,
     {
       MateMenuTreeItem *item = tmp->data;
 
-      if (matemenu_tree_item_get_type (item) != MATEMENU_TREE_ITEM_DIRECTORY)
+      if (item->type != MATEMENU_TREE_ITEM_DIRECTORY)
         {
           tmp = tmp->next;
           continue;
@@ -856,154 +838,283 @@ matemenu_tree_get_directory_from_path (MateMenuTree  *tree,
   return directory ? matemenu_tree_item_ref (directory) : NULL;
 }
 
-MateMenuTreeSortKey
-matemenu_tree_get_sort_key (MateMenuTree *tree)
+/**
+ * matemenu_tree_get_entry_by_id:
+ * @tree: a #MateMenuTree
+ * @id: a desktop file ID
+ * 
+ * Look up the entry corresponding to the given "desktop file id".
+ *
+ * Returns: (transfer full): A newly referenced #MateMenuTreeEntry, or %NULL if none
+ */
+MateMenuTreeEntry     *
+matemenu_tree_get_entry_by_id (MateMenuTree  *tree,
+			    const char *id)
 {
-  g_return_val_if_fail (tree != NULL, MATEMENU_TREE_SORT_NAME);
-  g_return_val_if_fail (tree->refcount > 0, MATEMENU_TREE_SORT_NAME);
+  MateMenuTreeEntry *entry;
+
+  g_return_val_if_fail (tree->loaded, NULL);
+
+  entry = g_hash_table_lookup (tree->entries_by_id, id);
+  if (entry != NULL)
+    matemenu_tree_item_ref (entry);
 
-  return tree->sort_key;
+  return entry;
 }
 
-void
-matemenu_tree_set_sort_key (MateMenuTree        *tree,
-			 MateMenuTreeSortKey  sort_key)
+static void
+matemenu_tree_invoke_monitors (MateMenuTree *tree)
 {
-  g_return_if_fail (tree != NULL);
-  g_return_if_fail (tree->refcount > 0);
-  g_return_if_fail (sort_key >= MATEMENU_TREE_SORT_FIRST);
-  g_return_if_fail (sort_key <= MATEMENU_TREE_SORT_LAST);
-
-  if (sort_key == tree->sort_key)
-    return;
+  g_signal_emit (tree, matemenu_tree_signals[CHANGED], 0);
+}
 
-  tree->sort_key = sort_key;
-  matemenu_tree_force_rebuild (tree);
+static MateMenuTreeDirectory *
+get_parent (MateMenuTreeItem *item)
+{
+  g_return_val_if_fail (item != NULL, NULL);
+  return item->parent ? matemenu_tree_item_ref (item->parent) : NULL;
 }
 
-void
-matemenu_tree_add_monitor (MateMenuTree            *tree,
-                       MateMenuTreeChangedFunc   callback,
-                       gpointer               user_data)
+/**
+ * matemenu_tree_directory_get_parent:
+ * @directory: a #MateMenuTreeDirectory
+ *
+ * Returns: (transfer full): The parent directory, or %NULL if none
+ */
+MateMenuTreeDirectory *
+matemenu_tree_directory_get_parent (MateMenuTreeDirectory *directory)
 {
-  MateMenuTreeMonitor *monitor;
-  GSList           *tmp;
+  return get_parent ((MateMenuTreeItem *)directory);
+}
 
-  g_return_if_fail (tree != NULL);
-  g_return_if_fail (callback != NULL);
+/**
+ * matemenu_tree_entry_get_parent:
+ * @entry: a #MateMenuTreeEntry
+ *
+ * Returns: (transfer full): The parent directory, or %NULL if none
+ */
+MateMenuTreeDirectory *
+matemenu_tree_entry_get_parent (MateMenuTreeEntry *entry)
+{
+  return get_parent ((MateMenuTreeItem *)entry);
+}
 
-  tmp = tree->monitors;
-  while (tmp != NULL)
-    {
-      monitor = tmp->data;
+/**
+ * matemenu_tree_alias_get_parent:
+ * @alias: a #MateMenuTreeAlias
+ *
+ * Returns: (transfer full): The parent directory, or %NULL if none
+ */
+MateMenuTreeDirectory *
+matemenu_tree_alias_get_parent (MateMenuTreeAlias *alias)
+{
+  return get_parent ((MateMenuTreeItem *)alias);
+}
 
-      if (monitor->callback  == callback &&
-          monitor->user_data == user_data)
-        break;
+/**
+ * matemenu_tree_header_get_parent:
+ * @header: a #MateMenuTreeHeader
+ *
+ * Returns: (transfer full): The parent directory, or %NULL if none
+ */
+MateMenuTreeDirectory *
+matemenu_tree_header_get_parent (MateMenuTreeHeader *header)
+{
+  return get_parent ((MateMenuTreeItem *)header);
+}
 
-      tmp = tmp->next;
-    }
+/**
+ * matemenu_tree_separator_get_parent:
+ * @separator: a #MateMenuTreeSeparator
+ *
+ * Returns: (transfer full): The parent directory, or %NULL if none
+ */
+MateMenuTreeDirectory *
+matemenu_tree_separator_get_parent (MateMenuTreeSeparator *separator)
+{
+  return get_parent ((MateMenuTreeItem *)separator);
+}
 
-  if (tmp == NULL)
-    {
-      monitor = g_new0 (MateMenuTreeMonitor, 1);
+static void
+matemenu_tree_item_set_parent (MateMenuTreeItem      *item,
+			    MateMenuTreeDirectory *parent)
+{
+  g_return_if_fail (item != NULL);
 
-      monitor->callback  = callback;
-      monitor->user_data = user_data;
+  item->parent = parent;
+}
 
-      tree->monitors = g_slist_append (tree->monitors, monitor);
-    }
+/**
+ * matemenu_tree_iter_ref: (skip)
+ * @iter: iter
+ *
+ * Increment the reference count of @iter
+ */
+MateMenuTreeIter *
+matemenu_tree_iter_ref (MateMenuTreeIter *iter)
+{
+  g_atomic_int_inc (&iter->refcount);
+  return iter;
 }
 
+/**
+ * matemenu_tree_iter_unref: (skip)
+ * @iter: iter
+ *
+ * Decrement the reference count of @iter
+ */
 void
-matemenu_tree_remove_monitor (MateMenuTree            *tree,
-			   MateMenuTreeChangedFunc  callback,
-			   gpointer              user_data)
+matemenu_tree_iter_unref (MateMenuTreeIter *iter)
 {
-  GSList *tmp;
-
-  g_return_if_fail (tree != NULL);
-  g_return_if_fail (callback != NULL);
-
-  tmp = tree->monitors;
-  while (tmp != NULL)
-    {
-      MateMenuTreeMonitor *monitor = tmp->data;
-      GSList          *next = tmp->next;
+  if (!g_atomic_int_dec_and_test (&iter->refcount))
+    return;
 
-      if (monitor->callback  == callback &&
-          monitor->user_data == user_data)
-        {
-          tree->monitors = g_slist_delete_link (tree->monitors, tmp);
-          g_free (monitor);
-        }
+  g_slist_foreach (iter->contents, (GFunc)matemenu_tree_item_unref, NULL);
+  g_slist_free (iter->contents);
 
-      tmp = next;
-    }
+  g_slice_free (MateMenuTreeIter, iter);
 }
 
-static void
-matemenu_tree_invoke_monitors (MateMenuTree *tree)
+/**
+ * matemenu_tree_directory_iter:
+ * @directory: directory
+ *
+ * Returns: (transfer full): A new iterator over the directory contents
+ */
+MateMenuTreeIter *
+matemenu_tree_directory_iter (MateMenuTreeDirectory *directory)
 {
-  GSList *tmp;
+  MateMenuTreeIter *iter;
 
-  tmp = tree->monitors;
-  while (tmp != NULL)
-    {
-      MateMenuTreeMonitor *monitor = tmp->data;
-      GSList           *next    = tmp->next;
+  g_return_val_if_fail (directory != NULL, NULL);
 
-      monitor->callback (tree, monitor->user_data);
+  iter = g_slice_new0 (MateMenuTreeIter);
+  iter->refcount = 1;
 
-      tmp = next;
-    }
+  iter->contents = g_slist_copy (directory->contents);
+  iter->contents_iter = iter->contents;
+  g_slist_foreach (iter->contents, (GFunc) matemenu_tree_item_ref, NULL);
+
+  return iter;
 }
 
+/**
+ * matemenu_tree_iter_next:
+ * @iter: iter
+ *
+ * Change the iterator to the next item, and return its type.  If
+ * there are no more items, %MATEMENU_TREE_ITEM_INVALID is returned.
+ *
+ * Returns: The type of the next item that can be retrived from the iterator
+ */
 MateMenuTreeItemType
-matemenu_tree_item_get_type (MateMenuTreeItem *item)
+matemenu_tree_iter_next (MateMenuTreeIter *iter)
 {
-  g_return_val_if_fail (item != NULL, 0);
+  g_return_val_if_fail (iter != NULL, MATEMENU_TREE_ITEM_INVALID);
 
-  return item->type;
+  if (iter->contents_iter)
+    {
+      iter->item = iter->contents_iter->data;
+      iter->contents_iter = iter->contents_iter->next;
+      return iter->item->type;
+    }
+  else
+    return MATEMENU_TREE_ITEM_INVALID;
 }
 
+/**
+ * matemenu_tree_iter_get_directory:
+ * @iter: iter
+ *
+ * This method may only be called if matemenu_tree_iter_next()
+ * returned MATEMENU_TREE_ITEM_DIRECTORY.
+ *
+ * Returns: (transfer full): A directory
+ */
 MateMenuTreeDirectory *
-matemenu_tree_item_get_parent (MateMenuTreeItem *item)
+matemenu_tree_iter_get_directory (MateMenuTreeIter *iter)
 {
-  g_return_val_if_fail (item != NULL, NULL);
+  g_return_val_if_fail (iter != NULL, NULL);
+  g_return_val_if_fail (iter->item != NULL, NULL);
+  g_return_val_if_fail (iter->item->type == MATEMENU_TREE_ITEM_DIRECTORY, NULL);
 
-  return item->parent ? matemenu_tree_item_ref (item->parent) : NULL;
+  return (MateMenuTreeDirectory*)matemenu_tree_item_ref (iter->item);
 }
 
-static void
-matemenu_tree_item_set_parent (MateMenuTreeItem      *item,
-			    MateMenuTreeDirectory *parent)
+/**
+ * matemenu_tree_iter_get_entry:
+ * @iter: iter
+ *
+ * This method may only be called if matemenu_tree_iter_next()
+ * returned MATEMENU_TREE_ITEM_ENTRY.
+ *
+ * Returns: (transfer full): An entry
+ */
+MateMenuTreeEntry *
+matemenu_tree_iter_get_entry (MateMenuTreeIter *iter)
 {
-  g_return_if_fail (item != NULL);
+  g_return_val_if_fail (iter != NULL, NULL);
+  g_return_val_if_fail (iter->item != NULL, NULL);
+  g_return_val_if_fail (iter->item->type == MATEMENU_TREE_ITEM_ENTRY, NULL);
 
-  item->parent = parent;
+  return (MateMenuTreeEntry*)matemenu_tree_item_ref (iter->item);
 }
 
-GSList *
-matemenu_tree_directory_get_contents (MateMenuTreeDirectory *directory)
+/**
+ * matemenu_tree_iter_get_header:
+ * @iter: iter
+ *
+ * This method may only be called if matemenu_tree_iter_next()
+ * returned MATEMENU_TREE_ITEM_HEADER.
+ *
+ * Returns: (transfer full): A header
+ */
+MateMenuTreeHeader *
+matemenu_tree_iter_get_header (MateMenuTreeIter *iter)
 {
-  GSList *retval;
-  GSList *tmp;
+  g_return_val_if_fail (iter != NULL, NULL);
+  g_return_val_if_fail (iter->item != NULL, NULL);
+  g_return_val_if_fail (iter->item->type == MATEMENU_TREE_ITEM_HEADER, NULL);
 
-  g_return_val_if_fail (directory != NULL, NULL);
+  return (MateMenuTreeHeader*)matemenu_tree_item_ref (iter->item);
+}
 
-  retval = NULL;
+/**
+ * matemenu_tree_iter_get_alias:
+ * @iter: iter
+ *
+ * This method may only be called if matemenu_tree_iter_next()
+ * returned MATEMENU_TREE_ITEM_ALIAS.
+ *
+ * Returns: (transfer full): An alias
+ */
+MateMenuTreeAlias *
+matemenu_tree_iter_get_alias (MateMenuTreeIter *iter)
+{
+  g_return_val_if_fail (iter != NULL, NULL);
+  g_return_val_if_fail (iter->item != NULL, NULL);
+  g_return_val_if_fail (iter->item->type == MATEMENU_TREE_ITEM_ALIAS, NULL);
 
-  tmp = directory->contents;
-  while (tmp != NULL)
-    {
-      retval = g_slist_prepend (retval,
-                                matemenu_tree_item_ref (tmp->data));
+  return (MateMenuTreeAlias*)matemenu_tree_item_ref (iter->item);
+}
 
-      tmp = tmp->next;
-    }
+/**
+ * matemenu_tree_iter_get_separator:
+ * @iter: iter
+ *
+ * This method may only be called if matemenu_tree_iter_next()
+ * returned #MATEMENU_TREE_ITEM_SEPARATOR.
+ *
+ * Returns: (transfer full): A separator
+ */
+MateMenuTreeSeparator *
+matemenu_tree_iter_get_separator (MateMenuTreeIter *iter)
+{
+  g_return_val_if_fail (iter != NULL, NULL);
+  g_return_val_if_fail (iter->item != NULL, NULL);
+  g_return_val_if_fail (iter->item->type == MATEMENU_TREE_ITEM_SEPARATOR, NULL);
 
-  return g_slist_reverse (retval);
+  return (MateMenuTreeSeparator*)matemenu_tree_item_ref (iter->item);
 }
 
 const char *
@@ -1018,6 +1129,17 @@ matemenu_tree_directory_get_name (MateMenuTreeDirectory *directory)
 }
 
 const char *
+matemenu_tree_directory_get_generic_name (MateMenuTreeDirectory *directory)
+{
+  g_return_val_if_fail (directory != NULL, NULL);
+
+  if (!directory->directory_entry)
+    return NULL;
+
+  return desktop_entry_get_generic_name (directory->directory_entry);
+}
+
+const char *
 matemenu_tree_directory_get_comment (MateMenuTreeDirectory *directory)
 {
   g_return_val_if_fail (directory != NULL, NULL);
@@ -1028,7 +1150,16 @@ matemenu_tree_directory_get_comment (MateMenuTreeDirectory *directory)
   return desktop_entry_get_comment (directory->directory_entry);
 }
 
-const char* matemenu_tree_directory_get_icon(MateMenuTreeDirectory* directory)
+/**
+ * matemenu_tree_directory_get_icon:
+ * @directory: a #MateMenuTreeDirectory
+ *
+ * Gets the icon for the directory.
+ *
+ * Returns: (transfer none): The #GIcon for this directory
+ */
+GIcon *
+matemenu_tree_directory_get_icon (MateMenuTreeDirectory *directory)
 {
 	g_return_val_if_fail(directory != NULL, NULL);
 
@@ -1057,47 +1188,28 @@ matemenu_tree_directory_get_menu_id (MateMenuTreeDirectory *directory)
   return directory->name;
 }
 
-static void
-matemenu_tree_directory_set_tree (MateMenuTreeDirectory *directory,
-			       MateMenuTree          *tree)
+gboolean
+matemenu_tree_directory_get_is_nodisplay (MateMenuTreeDirectory *directory)
 {
-  MateMenuTreeDirectoryRoot *root;
-
-  g_assert (directory != NULL);
-  g_assert (directory->is_root);
-
-  root = (MateMenuTreeDirectoryRoot *) directory;
+  g_return_val_if_fail (directory != NULL, FALSE);
 
-  root->tree = tree;
+  return directory->is_nodisplay;
 }
 
+/**
+ * matemenu_tree_directory_get_tree:
+ * @directory: A #MateMenuTreeDirectory
+ *
+ * Grab the tree associated with a #MateMenuTreeItem.
+ *
+ * Returns: (transfer full): The #MateMenuTree
+ */
 MateMenuTree *
 matemenu_tree_directory_get_tree (MateMenuTreeDirectory *directory)
 {
-  MateMenuTreeDirectoryRoot *root;
-
   g_return_val_if_fail (directory != NULL, NULL);
 
-  while (MATEMENU_TREE_ITEM (directory)->parent != NULL)
-    directory = MATEMENU_TREE_DIRECTORY (MATEMENU_TREE_ITEM (directory)->parent);
-
-  if (!directory->is_root)
-    return NULL;
-
-  root = (MateMenuTreeDirectoryRoot *) directory;
-
-  if (root->tree)
-    matemenu_tree_ref (root->tree);
-
-  return root->tree;
-}
-
-gboolean
-matemenu_tree_directory_get_is_nodisplay (MateMenuTreeDirectory *directory)
-{
-  g_return_val_if_fail (directory != NULL, FALSE);
-
-  return directory->is_nodisplay;
+  return g_object_ref (directory->item.tree);
 }
 
 static void
@@ -1136,98 +1248,124 @@ matemenu_tree_directory_make_path (MateMenuTreeDirectory *directory,
   return g_string_free (path, FALSE);
 }
 
-const char *
-matemenu_tree_entry_get_name (MateMenuTreeEntry *entry)
+/**
+ * matemenu_tree_entry_get_app_info:
+ * @entry: a #MateMenuTreeEntry
+ *
+ * Returns: (transfer none): The #GDesktopAppInfo for this entry
+ */
+GDesktopAppInfo *
+matemenu_tree_entry_get_app_info (MateMenuTreeEntry *entry)
 {
   g_return_val_if_fail (entry != NULL, NULL);
 
-  return desktop_entry_get_name (entry->desktop_entry);
+  return desktop_entry_get_app_info (entry->desktop_entry);
 }
 
 const char *
-matemenu_tree_entry_get_generic_name (MateMenuTreeEntry *entry)
+matemenu_tree_entry_get_desktop_file_path (MateMenuTreeEntry *entry)
 {
   g_return_val_if_fail (entry != NULL, NULL);
 
-  return desktop_entry_get_generic_name (entry->desktop_entry);
+  return desktop_entry_get_path (entry->desktop_entry);
 }
 
 const char *
-matemenu_tree_entry_get_display_name (MateMenuTreeEntry *entry)
+matemenu_tree_entry_get_desktop_file_id (MateMenuTreeEntry *entry)
 {
-  const char *display_name;
-
   g_return_val_if_fail (entry != NULL, NULL);
 
-  display_name = desktop_entry_get_full_name (entry->desktop_entry);
-  if (!display_name || display_name[0] == '\0')
-    display_name = desktop_entry_get_name (entry->desktop_entry);
-
-  return display_name;
+  return entry->desktop_file_id;
 }
 
-const char *
-matemenu_tree_entry_get_comment (MateMenuTreeEntry *entry)
+gboolean
+matemenu_tree_entry_get_is_nodisplay_recurse (MateMenuTreeEntry *entry)
 {
-  g_return_val_if_fail (entry != NULL, NULL);
+  MateMenuTreeDirectory *directory;
+  GDesktopAppInfo *app_info;
 
-  return desktop_entry_get_comment (entry->desktop_entry);
-}
+  g_return_val_if_fail (entry != NULL, FALSE);
 
-const char* matemenu_tree_entry_get_icon(MateMenuTreeEntry *entry)
-{
-	g_return_val_if_fail (entry != NULL, NULL);
+  app_info = matemenu_tree_entry_get_app_info (entry);
 
-	return desktop_entry_get_icon(entry->desktop_entry);
-}
+  if (g_desktop_app_info_get_nodisplay (app_info))
+    return TRUE;
 
-const char* matemenu_tree_entry_get_exec(MateMenuTreeEntry* entry)
-{
-	g_return_val_if_fail(entry != NULL, NULL);
+  directory = entry->item.parent;
+  while (directory != NULL)
+    {
+      if (directory->is_nodisplay)
+        return TRUE;
+
+      directory = directory->item.parent;
+    }
 
-	return desktop_entry_get_exec(entry->desktop_entry);
+  return FALSE;
 }
 
-gboolean matemenu_tree_entry_get_launch_in_terminal(MateMenuTreeEntry* entry)
+gboolean
+matemenu_tree_entry_get_is_excluded (MateMenuTreeEntry *entry)
 {
   g_return_val_if_fail(entry != NULL, FALSE);
 
-  return desktop_entry_get_launch_in_terminal(entry->desktop_entry);
+  return entry->is_excluded;
 }
 
-const char* matemenu_tree_entry_get_desktop_file_path(MateMenuTreeEntry* entry)
+gboolean
+matemenu_tree_entry_get_is_unallocated (MateMenuTreeEntry *entry)
 {
-	g_return_val_if_fail(entry != NULL, NULL);
+  g_return_val_if_fail (entry != NULL, FALSE);
 
-	return desktop_entry_get_path(entry->desktop_entry);
+  return entry->is_unallocated;
 }
 
-const char* matemenu_tree_entry_get_desktop_file_id(MateMenuTreeEntry* entry)
+/**
+ * matemenu_tree_entry_get_tree:
+ * @entry: A #MateMenuTreeEntry
+ *
+ * Grab the tree associated with a #MateMenuTreeEntry.
+ *
+ * Returns: (transfer full): The #MateMenuTree
+ */
+MateMenuTree *
+matemenu_tree_entry_get_tree (MateMenuTreeEntry *entry)
 {
 	g_return_val_if_fail(entry != NULL, NULL);
 
-	return entry->desktop_file_id;
+  return g_object_ref (entry->item.tree);
 }
 
-gboolean matemenu_tree_entry_get_is_excluded(MateMenuTreeEntry* entry)
+MateMenuTreeDirectory *
+matemenu_tree_header_get_directory (MateMenuTreeHeader *header)
 {
-	g_return_val_if_fail(entry != NULL, FALSE);
+  g_return_val_if_fail (header != NULL, NULL);
 
-	return entry->is_excluded;
+  return matemenu_tree_item_ref (header->directory);
 }
 
-gboolean matemenu_tree_entry_get_is_nodisplay(MateMenuTreeEntry* entry)
+/**
+ * matemenu_tree_header_get_tree:
+ * @header: A #MateMenuTreeHeader
+ *
+ * Grab the tree associated with a #MateMenuTreeHeader.
+ *
+ * Returns: (transfer full): The #MateMenuTree
+ */
+MateMenuTree *
+matemenu_tree_header_get_tree (MateMenuTreeHeader *header)
 {
-	g_return_val_if_fail(entry != NULL, FALSE);
+  g_return_val_if_fail (header != NULL, NULL);
 
-	return entry->is_nodisplay;
+  return g_object_ref (header->item.tree);
 }
 
-MateMenuTreeDirectory* matemenu_tree_header_get_directory(MateMenuTreeHeader* header)
+MateMenuTreeItemType
+matemenu_tree_alias_get_aliased_item_type (MateMenuTreeAlias *alias)
 {
-	g_return_val_if_fail (header != NULL, NULL);
+  g_return_val_if_fail (alias != NULL, MATEMENU_TREE_ITEM_INVALID);
 
-	return matemenu_tree_item_ref(header->directory);
+  g_assert (alias->aliased_item != NULL);
+  return alias->aliased_item->type;
 }
 
 MateMenuTreeDirectory* matemenu_tree_alias_get_directory(MateMenuTreeAlias* alias)
@@ -1237,40 +1375,81 @@ MateMenuTreeDirectory* matemenu_tree_alias_get_directory(MateMenuTreeAlias* alia
 	return matemenu_tree_item_ref(alias->directory);
 }
 
-MateMenuTreeItem *
-matemenu_tree_alias_get_item (MateMenuTreeAlias *alias)
+/**
+ * matemenu_tree_alias_get_tree:
+ * @alias: A #MateMenuTreeAlias
+ *
+ * Grab the tree associated with a #MateMenuTreeAlias.
+ *
+ * Returns: (transfer full): The #MateMenuTree
+ */
+MateMenuTree *
+matemenu_tree_alias_get_tree (MateMenuTreeAlias *alias)
 {
   g_return_val_if_fail (alias != NULL, NULL);
 
-  return matemenu_tree_item_ref (alias->aliased_item);
+  return g_object_ref (alias->item.tree);
 }
 
-static MateMenuTreeDirectory *
-matemenu_tree_directory_new (MateMenuTreeDirectory *parent,
-			  const char         *name,
-			  gboolean            is_root)
+/**
+ * matemenu_tree_separator_get_tree:
+ * @separator: A #MateMenuTreeSeparator
+ *
+ * Grab the tree associated with a #MateMenuTreeSeparator.
+ *
+ * Returns: (transfer full): The #MateMenuTree
+ */
+MateMenuTree *
+matemenu_tree_separator_get_tree (MateMenuTreeSeparator *separator)
 {
-  MateMenuTreeDirectory *retval;
+  g_return_val_if_fail (separator != NULL, NULL);
 
-  if (!is_root)
-    {
-      retval = g_new0 (MateMenuTreeDirectory, 1);
-    }
-  else
-    {
-      MateMenuTreeDirectoryRoot *root;
+  return g_object_ref (separator->item.tree);
+}
+
+/**
+ * matemenu_tree_alias_get_aliased_directory:
+ * @alias: alias
+ *
+ * Returns: (transfer full): The aliased directory entry
+ */
+MateMenuTreeDirectory *
+matemenu_tree_alias_get_aliased_directory (MateMenuTreeAlias *alias)
+{
+  g_return_val_if_fail (alias != NULL, NULL);
+  g_return_val_if_fail (alias->aliased_item->type == MATEMENU_TREE_ITEM_DIRECTORY, NULL);
 
-      root = g_new0 (MateMenuTreeDirectoryRoot, 1);
+  return (MateMenuTreeDirectory *) matemenu_tree_item_ref (alias->aliased_item);
+}
 
-      retval = MATEMENU_TREE_DIRECTORY (root);
+/**
+ * matemenu_tree_alias_get_aliased_entry:
+ * @alias: alias
+ *
+ * Returns: (transfer full): The aliased entry
+ */
+MateMenuTreeEntry *
+matemenu_tree_alias_get_aliased_entry (MateMenuTreeAlias *alias)
+{
+  g_return_val_if_fail (alias != NULL, NULL);
+  g_return_val_if_fail (alias->aliased_item->type == MATEMENU_TREE_ITEM_ENTRY, NULL);
 
-      retval->is_root = TRUE;
-    }
+  return (MateMenuTreeEntry *) matemenu_tree_item_ref (alias->aliased_item);
+}
 
+static MateMenuTreeDirectory *
+matemenu_tree_directory_new (MateMenuTree          *tree,
+                          MateMenuTreeDirectory *parent,
+			  const char         *name)
+{
+  MateMenuTreeDirectory *retval;
+
+  retval = g_slice_new0 (MateMenuTreeDirectory);
 
   retval->item.type     = MATEMENU_TREE_ITEM_DIRECTORY;
   retval->item.parent   = parent;
   retval->item.refcount = 1;
+  retval->item.tree     = tree;
 
   retval->name                = g_strdup (name);
   retval->directory_entry     = NULL;
@@ -1336,6 +1515,8 @@ matemenu_tree_directory_finalize (MateMenuTreeDirectory *directory)
 
   g_free (directory->name);
   directory->name = NULL;
+
+  g_slice_free (MateMenuTreeDirectory, directory);
 }
 
 static MateMenuTreeSeparator *
@@ -1343,26 +1524,36 @@ matemenu_tree_separator_new (MateMenuTreeDirectory *parent)
 {
   MateMenuTreeSeparator *retval;
 
-  retval = g_new0 (MateMenuTreeSeparator, 1);
+  retval = g_slice_new0 (MateMenuTreeSeparator);
 
   retval->item.type     = MATEMENU_TREE_ITEM_SEPARATOR;
   retval->item.parent   = parent;
   retval->item.refcount = 1;
+  retval->item.tree     = parent->item.tree;
 
   return retval;
 }
 
+static void
+matemenu_tree_separator_finalize (MateMenuTreeSeparator *separator)
+{
+  g_assert (separator->item.refcount == 0);
+
+  g_slice_free (MateMenuTreeSeparator, separator);
+}
+
 static MateMenuTreeHeader *
 matemenu_tree_header_new (MateMenuTreeDirectory *parent,
 		       MateMenuTreeDirectory *directory)
 {
   MateMenuTreeHeader *retval;
 
-  retval = g_new0 (MateMenuTreeHeader, 1);
+  retval = g_slice_new0 (MateMenuTreeHeader);
 
   retval->item.type     = MATEMENU_TREE_ITEM_HEADER;
   retval->item.parent   = parent;
   retval->item.refcount = 1;
+  retval->item.tree     = parent->item.tree;
 
   retval->directory = matemenu_tree_item_ref (directory);
 
@@ -1379,6 +1570,8 @@ matemenu_tree_header_finalize (MateMenuTreeHeader *header)
   if (header->directory != NULL)
     matemenu_tree_item_unref (header->directory);
   header->directory = NULL;
+
+  g_slice_free (MateMenuTreeHeader, header);
 }
 
 static MateMenuTreeAlias *
@@ -1388,17 +1581,21 @@ matemenu_tree_alias_new (MateMenuTreeDirectory *parent,
 {
   MateMenuTreeAlias *retval;
 
-  retval = g_new0 (MateMenuTreeAlias, 1);
+  retval = g_slice_new0 (MateMenuTreeAlias);
 
   retval->item.type     = MATEMENU_TREE_ITEM_ALIAS;
   retval->item.parent   = parent;
   retval->item.refcount = 1;
+  retval->item.tree     = parent->item.tree;
 
   retval->directory    = matemenu_tree_item_ref (directory);
   if (item->type != MATEMENU_TREE_ITEM_ALIAS)
     retval->aliased_item = matemenu_tree_item_ref (item);
   else
-    retval->aliased_item = matemenu_tree_item_ref (matemenu_tree_alias_get_item (MATEMENU_TREE_ALIAS (item)));
+    {
+      MateMenuTreeAlias *alias = MATEMENU_TREE_ALIAS (item);
+      retval->aliased_item = matemenu_tree_item_ref (alias->aliased_item);
+    }
 
   matemenu_tree_item_set_parent (MATEMENU_TREE_ITEM (retval->directory), NULL);
   matemenu_tree_item_set_parent (retval->aliased_item, NULL);
@@ -1418,6 +1615,8 @@ matemenu_tree_alias_finalize (MateMenuTreeAlias *alias)
   if (alias->aliased_item != NULL)
     matemenu_tree_item_unref (alias->aliased_item);
   alias->aliased_item = NULL;
+
+  g_slice_free (MateMenuTreeAlias, alias);
 }
 
 static MateMenuTreeEntry *
@@ -1425,20 +1624,21 @@ matemenu_tree_entry_new (MateMenuTreeDirectory *parent,
 		      DesktopEntry       *desktop_entry,
 		      const char         *desktop_file_id,
 		      gboolean            is_excluded,
-                      gboolean            is_nodisplay)
+                      gboolean            is_unallocated)
 {
   MateMenuTreeEntry *retval;
 
-  retval = g_new0 (MateMenuTreeEntry, 1);
+  retval = g_slice_new0 (MateMenuTreeEntry);
 
   retval->item.type     = MATEMENU_TREE_ITEM_ENTRY;
   retval->item.parent   = parent;
   retval->item.refcount = 1;
+  retval->item.tree     = parent->item.tree;
 
   retval->desktop_entry   = desktop_entry_ref (desktop_entry);
   retval->desktop_file_id = g_strdup (desktop_file_id);
   retval->is_excluded     = is_excluded != FALSE;
-  retval->is_nodisplay    = is_nodisplay != FALSE;
+  retval->is_unallocated  = is_unallocated != FALSE;
 
   return retval;
 }
@@ -1454,6 +1654,8 @@ matemenu_tree_entry_finalize (MateMenuTreeEntry *entry)
   if (entry->desktop_entry)
     desktop_entry_unref (entry->desktop_entry);
   entry->desktop_entry = NULL;
+
+  g_slice_free (MateMenuTreeEntry, entry);
 }
 
 static int
@@ -1470,14 +1672,21 @@ matemenu_tree_entry_compare_by_id (MateMenuTreeItem *a,
                  MATEMENU_TREE_ENTRY (b)->desktop_file_id);
 }
 
-gpointer matemenu_tree_item_ref(gpointer itemp)
+/**
+ * matemenu_tree_item_ref:
+ * @item: a #MateMenuTreeItem
+ *
+ * Returns: (transfer full): The same @item, or %NULL if @item is not a valid #MateMenuTreeItem
+ */
+gpointer
+matemenu_tree_item_ref (gpointer itemp)
 {
 	MateMenuTreeItem* item = (MateMenuTreeItem*) itemp;
 
 	g_return_val_if_fail(item != NULL, NULL);
 	g_return_val_if_fail(item->refcount > 0, NULL);
 
-	item->refcount++;
+  g_atomic_int_inc (&item->refcount);
 
 	return item;
 }
@@ -1492,7 +1701,7 @@ matemenu_tree_item_unref (gpointer itemp)
   g_return_if_fail (item != NULL);
   g_return_if_fail (item->refcount > 0);
 
-  if (--item->refcount == 0)
+  if (g_atomic_int_dec_and_test (&(item->refcount)))
     {
       switch (item->type)
 	{
@@ -1505,6 +1714,7 @@ matemenu_tree_item_unref (gpointer itemp)
 	  break;
 
 	case MATEMENU_TREE_ITEM_SEPARATOR:
+	  matemenu_tree_separator_finalize (MATEMENU_TREE_SEPARATOR (item));
 	  break;
 
 	case MATEMENU_TREE_ITEM_HEADER:
@@ -1519,15 +1729,6 @@ matemenu_tree_item_unref (gpointer itemp)
 	  g_assert_not_reached ();
 	  break;
 	}
-
-      if (item->dnotify)
-	item->dnotify (item->user_data);
-      item->user_data = NULL;
-      item->dnotify   = NULL;
-
-      item->parent = NULL;
-
-      g_free (item);
     }
 }
 
@@ -1544,31 +1745,9 @@ matemenu_tree_item_unref_and_unset_parent (gpointer itemp)
   matemenu_tree_item_unref (item);
 }
 
-void
-matemenu_tree_item_set_user_data (MateMenuTreeItem  *item,
-			       gpointer        user_data,
-			       GDestroyNotify  dnotify)
-{
-  g_return_if_fail (item != NULL);
-
-  if (item->dnotify != NULL)
-    item->dnotify (item->user_data);
-
-  item->dnotify   = dnotify;
-  item->user_data = user_data;
-}
-
-gpointer
-matemenu_tree_item_get_user_data (MateMenuTreeItem *item)
-{
-  g_return_val_if_fail (item != NULL, NULL);
-
-  return item->user_data;
-}
-
 static inline const char *
 matemenu_tree_item_compare_get_name_helper (MateMenuTreeItem    *item,
-					 MateMenuTreeSortKey  sort_key)
+					 MateMenuTreeFlags    flags)
 {
   const char *name;
 
@@ -1584,25 +1763,17 @@ matemenu_tree_item_compare_get_name_helper (MateMenuTreeItem    *item,
       break;
 
     case MATEMENU_TREE_ITEM_ENTRY:
-      switch (sort_key)
-	{
-	case MATEMENU_TREE_SORT_NAME:
-	  name = desktop_entry_get_name (MATEMENU_TREE_ENTRY (item)->desktop_entry);
-	  break;
-	case MATEMENU_TREE_SORT_DISPLAY_NAME:
-	  name = matemenu_tree_entry_get_display_name (MATEMENU_TREE_ENTRY (item));
-	  break;
-	default:
-	  g_assert_not_reached ();
-	  break;
-	}
+      if (flags & MATEMENU_TREE_FLAGS_SORT_DISPLAY_NAME)
+        name = g_app_info_get_display_name (G_APP_INFO (matemenu_tree_entry_get_app_info (MATEMENU_TREE_ENTRY (item))));
+      else
+        name = desktop_entry_get_name (MATEMENU_TREE_ENTRY (item)->desktop_entry);
       break;
 
     case MATEMENU_TREE_ITEM_ALIAS:
       {
         MateMenuTreeItem *dir;
         dir = MATEMENU_TREE_ITEM (MATEMENU_TREE_ALIAS (item)->directory);
-        name = matemenu_tree_item_compare_get_name_helper (dir, sort_key);
+        name = matemenu_tree_item_compare_get_name_helper (dir, flags);
       }
       break;
 
@@ -1619,16 +1790,16 @@ matemenu_tree_item_compare_get_name_helper (MateMenuTreeItem    *item,
 static int
 matemenu_tree_item_compare (MateMenuTreeItem *a,
 			 MateMenuTreeItem *b,
-			 gpointer       sort_key_p)
+			 gpointer       flags_p)
 {
   const char       *name_a;
   const char       *name_b;
-  MateMenuTreeSortKey  sort_key;
+  MateMenuTreeFlags    flags;
 
-  sort_key = GPOINTER_TO_INT (sort_key_p);
+  flags = GPOINTER_TO_INT (flags_p);
 
-  name_a = matemenu_tree_item_compare_get_name_helper (a, sort_key);
-  name_b = matemenu_tree_item_compare_get_name_helper (b, sort_key);
+  name_a = matemenu_tree_item_compare_get_name_helper (a, flags);
+  name_b = matemenu_tree_item_compare_get_name_helper (b, flags);
 
   return g_utf8_collate (name_a, name_b);
 }
@@ -1744,7 +1915,7 @@ load_merge_file (MateMenuTree      *tree,
 
   menu_verbose ("Merging file \"%s\"\n", canonical);
 
-  to_merge = menu_layout_load (canonical, NULL, NULL);
+  to_merge = menu_layout_load (canonical, tree->non_prefixed_basename, NULL);
   if (to_merge == NULL)
     {
       menu_verbose ("No menu for file \"%s\" found when merging\n",
@@ -2906,33 +3077,26 @@ matemenu_tree_execute_moves (MateMenuTree      *tree,
     matemenu_tree_strip_duplicate_children (tree, layout);
 }
 
-static void
-matemenu_tree_load_layout (MateMenuTree *tree)
+static gboolean
+matemenu_tree_load_layout (MateMenuTree  *tree,
+                        GError    **error)
 {
   GHashTable *loaded_menu_files;
-  GError     *error;
 
   if (tree->layout)
-    return;
+    return TRUE;
 
-  if (!matemenu_tree_canonicalize_path (tree))
-    return;
+  if (!matemenu_tree_canonicalize_path (tree, error))
+    return FALSE;
 
   menu_verbose ("Loading menu layout from \"%s\"\n",
                 tree->canonical_path);
 
-  error = NULL;
   tree->layout = menu_layout_load (tree->canonical_path,
-                                   tree->type == MATEMENU_TREE_BASENAME ?
-                                        tree->basename : NULL,
-                                   &error);
-  if (tree->layout == NULL)
-    {
-      g_warning ("Error loading menu layout from \"%s\": %s",
-                 tree->canonical_path, error->message);
-      g_error_free (error);
-      return;
-    }
+                                   tree->non_prefixed_basename,
+                                   error);
+  if (!tree->layout)
+    return FALSE;
 
   loaded_menu_files = g_hash_table_new (g_str_hash, g_str_equal);
   g_hash_table_insert (loaded_menu_files, tree->canonical_path, GUINT_TO_POINTER (TRUE));
@@ -2941,6 +3105,8 @@ matemenu_tree_load_layout (MateMenuTree *tree)
 
   matemenu_tree_strip_duplicate_children (tree, tree->layout);
   matemenu_tree_execute_moves (tree, tree->layout, NULL);
+
+  return TRUE;
 }
 
 static void
@@ -3192,7 +3358,7 @@ entries_listify_foreach (const char         *desktop_file_id,
                                            desktop_entry,
                                            desktop_file_id,
                                            FALSE,
-                                           desktop_entry_get_no_display (desktop_entry)));
+                                           FALSE));
 }
 
 static void
@@ -3206,7 +3372,21 @@ excluded_entries_listify_foreach (const char         *desktop_file_id,
 					   desktop_entry,
 					   desktop_file_id,
 					   TRUE,
-                                           desktop_entry_get_no_display (desktop_entry)));
+                                           FALSE));
+}
+
+static void
+unallocated_entries_listify_foreach (const char         *desktop_file_id,
+                                     DesktopEntry       *desktop_entry,
+                                     MateMenuTreeDirectory *directory)
+{
+  directory->entries =
+    g_slist_prepend (directory->entries,
+		     matemenu_tree_entry_new (directory,
+                                           desktop_entry,
+                                           desktop_file_id,
+                                           FALSE,
+                                           TRUE));
 }
 
 static void
@@ -3256,9 +3436,8 @@ process_layout (MateMenuTree          *tree,
   g_assert (menu_layout_node_get_type (layout) == MENU_LAYOUT_NODE_MENU);
   g_assert (menu_layout_node_menu_get_name (layout) != NULL);
 
-  directory = matemenu_tree_directory_new (parent,
-					menu_layout_node_menu_get_name (layout),
-					parent == NULL);
+  directory = matemenu_tree_directory_new (tree, parent,
+					menu_layout_node_menu_get_name (layout));
 
   menu_verbose ("=== Menu name = %s ===\n", directory->name);
 
@@ -3462,9 +3641,9 @@ process_layout (MateMenuTree          *tree,
             }
         }
 
-      if (!desktop_entry_get_show_in_mate (directory->directory_entry))
+      if (!desktop_entry_get_show_in (directory->directory_entry))
         {
-          menu_verbose ("Not showing menu %s because OnlyShowIn!=MATE or NotShowIn=MATE\n",
+          menu_verbose ("Not showing menu %s because OnlyShowIn!=$DESKTOP or NotShowIn=$DESKTOP (with $DESKTOP=${XDG_CURRENT_DESKTOP:-GNOME})\n",
                         desktop_entry_get_name (directory->directory_entry));
           deleted = TRUE;
         }
@@ -3509,6 +3688,9 @@ process_layout (MateMenuTree          *tree,
       GSList         *next  = tmp->next;
       gboolean        delete = FALSE;
 
+      /* If adding a new condition to delete here, it has to be added to
+       * get_still_unallocated_foreach() too */
+
       if (desktop_entry_get_hidden (entry->desktop_entry))
         {
           menu_verbose ("Deleting %s because Hidden=true\n",
@@ -3524,19 +3706,15 @@ process_layout (MateMenuTree          *tree,
           delete = TRUE;
         }
 
-      if (!desktop_entry_get_show_in_mate (entry->desktop_entry))
+      if (!desktop_entry_get_show_in (entry->desktop_entry))
         {
-          menu_verbose ("Deleting %s because OnlyShowIn!=MATE or NotShowIn=MATE\n",
+          menu_verbose ("Deleting %s because OnlyShowIn!=$DESKTOP or NotShowIn=$DESKTOP (with $DESKTOP=${XDG_CURRENT_DESKTOP:-GNOME})\n",
                         desktop_entry_get_name (entry->desktop_entry));
           delete = TRUE;
         }
 
-      if (desktop_entry_get_tryexec_failed (entry->desktop_entry))
-        {
-          menu_verbose ("Deleting %s because TryExec failed\n",
-                        desktop_entry_get_name (entry->desktop_entry));
-          delete = TRUE;
-        }
+      /* No need to filter out based on TryExec since GDesktopAppInfo cannot
+       * deal with .desktop files with a failed TryExec. */
 
       if (delete)
         {
@@ -3556,7 +3734,8 @@ process_layout (MateMenuTree          *tree,
 static void
 process_only_unallocated (MateMenuTree          *tree,
 			  MateMenuTreeDirectory *directory,
-			  DesktopEntrySet    *allocated)
+			  DesktopEntrySet    *allocated,
+			  DesktopEntrySet    *unallocated_used)
 {
   GSList *tmp;
 
@@ -3578,6 +3757,10 @@ process_only_unallocated (MateMenuTree          *tree,
                                                         tmp);
               matemenu_tree_item_unref_and_unset_parent (entry);
             }
+          else
+            {
+              desktop_entry_set_add_entry (unallocated_used, entry->desktop_entry, entry->desktop_file_id);
+            }
 
           tmp = next;
         }
@@ -3588,12 +3771,45 @@ process_only_unallocated (MateMenuTree          *tree,
     {
       MateMenuTreeDirectory *subdir = tmp->data;
 
-      process_only_unallocated (tree, subdir, allocated);
+      process_only_unallocated (tree, subdir, allocated, unallocated_used);
 
       tmp = tmp->next;
    }
 }
 
+typedef struct
+{
+  MateMenuTree *tree;
+  DesktopEntrySet *allocated;
+  DesktopEntrySet *unallocated_used;
+  DesktopEntrySet *still_unallocated;
+} GetStillUnallocatedForeachData;
+
+static void
+get_still_unallocated_foreach (const char                     *file_id,
+                               DesktopEntry                   *entry,
+                               GetStillUnallocatedForeachData *data)
+{
+  if (desktop_entry_set_lookup (data->allocated, file_id))
+    return;
+
+  if (desktop_entry_set_lookup (data->unallocated_used, file_id))
+    return;
+
+  /* Same rules than at the end of process_layout() */
+  if (desktop_entry_get_hidden (entry))
+    return;
+
+  if (!(data->tree->flags & MATEMENU_TREE_FLAGS_INCLUDE_NODISPLAY) &&
+      desktop_entry_get_no_display (entry))
+    return;
+
+  if (!desktop_entry_get_show_in (entry))
+    return;
+
+  desktop_entry_set_add_entry (data->still_unallocated, entry, file_id);
+}
+
 static void preprocess_layout_info (MateMenuTree          *tree,
                                     MateMenuTreeDirectory *directory);
 
@@ -3729,7 +3945,7 @@ preprocess_layout_info_subdir_helper (MateMenuTree          *tree,
 
           menu_verbose ("Inline aliasing '%s' to '%s'\n",
                         item->type == MATEMENU_TREE_ITEM_ENTRY ?
-                          matemenu_tree_entry_get_name (MATEMENU_TREE_ENTRY (item)) :
+                          g_app_info_get_name (G_APP_INFO (matemenu_tree_entry_get_app_info (MATEMENU_TREE_ENTRY (item)))) :
                           (item->type == MATEMENU_TREE_ITEM_DIRECTORY ?
                              matemenu_tree_directory_get_name (MATEMENU_TREE_DIRECTORY (item)) :
                              matemenu_tree_directory_get_name (MATEMENU_TREE_ALIAS (item)->directory)),
@@ -4148,7 +4364,7 @@ merge_subdirs (MateMenuTree          *tree,
 
   subdirs = g_slist_sort_with_data (subdirs,
 				    (GCompareDataFunc) matemenu_tree_item_compare,
-				     GINT_TO_POINTER (MATEMENU_TREE_SORT_NAME));
+                                    GINT_TO_POINTER (MATEMENU_TREE_FLAGS_NONE));
 
   tmp = subdirs;
   while (tmp != NULL)
@@ -4193,7 +4409,7 @@ merge_entries (MateMenuTree          *tree,
 
   entries = g_slist_sort_with_data (entries,
 				    (GCompareDataFunc) matemenu_tree_item_compare,
-				    GINT_TO_POINTER (tree->sort_key));
+                                    GINT_TO_POINTER (tree->flags));
 
   tmp = entries;
   while (tmp != NULL)
@@ -4242,7 +4458,7 @@ merge_subdirs_and_entries (MateMenuTree          *tree,
 
   items = g_slist_sort_with_data (items,
 				  (GCompareDataFunc) matemenu_tree_item_compare,
-				  GINT_TO_POINTER (tree->sort_key));
+                                  GINT_TO_POINTER (tree->flags));
 
   tmp = items;
   while (tmp != NULL)
@@ -4250,7 +4466,7 @@ merge_subdirs_and_entries (MateMenuTree          *tree,
       MateMenuTreeItem     *item = tmp->data;
       MateMenuTreeItemType  type;
 
-      type = matemenu_tree_item_get_type (item);
+      type = item->type;
 
       if (type == MATEMENU_TREE_ITEM_ALIAS)
         {
@@ -4497,16 +4713,55 @@ handle_entries_changed (MenuLayoutNode *layout,
 }
 
 static void
-matemenu_tree_build_from_layout (MateMenuTree *tree)
+update_entry_index (MateMenuTree           *tree,
+		    MateMenuTreeDirectory  *dir)
+{
+  MateMenuTreeIter *iter = matemenu_tree_directory_iter (dir);
+  MateMenuTreeItemType next_type;
+
+  while ((next_type = matemenu_tree_iter_next (iter)) != MATEMENU_TREE_ITEM_INVALID)
+    {
+      gpointer item = NULL;
+
+      switch (next_type)
+        {
+        case MATEMENU_TREE_ITEM_ENTRY:
+          {
+	    const char *id;
+
+            item = matemenu_tree_iter_get_entry (iter);
+            id = matemenu_tree_entry_get_desktop_file_id (item);
+            if (id != NULL)
+              g_hash_table_insert (tree->entries_by_id, (char*)id, item);
+          }
+          break;
+        case MATEMENU_TREE_ITEM_DIRECTORY:
+          {
+            item = matemenu_tree_iter_get_directory (iter);
+            update_entry_index (tree, (MateMenuTreeDirectory*)item);
+          }
+          break;
+        default:
+          break;
+        }
+      if (item != NULL)
+        matemenu_tree_item_unref (item);
+    }
+
+  matemenu_tree_iter_unref (iter);
+}
+
+static gboolean
+matemenu_tree_build_from_layout (MateMenuTree  *tree,
+                              GError    **error)
 {
   DesktopEntrySet *allocated;
 
   if (tree->root)
-    return;
+    return TRUE;
 
-  matemenu_tree_load_layout (tree);
-  if (!tree->layout)
-    return;
+  if (!matemenu_tree_load_layout (tree, error))
+    return FALSE;
 
   menu_verbose ("Building menu tree from layout\n");
 
@@ -4519,9 +4774,39 @@ matemenu_tree_build_from_layout (MateMenuTree *tree)
                                allocated);
   if (tree->root)
     {
-      matemenu_tree_directory_set_tree (tree->root, tree);
+      DesktopEntrySet *unallocated_used;
+
+      unallocated_used = desktop_entry_set_new ();
+
+      process_only_unallocated (tree, tree->root, allocated, unallocated_used);
+      if (tree->flags & MATEMENU_TREE_FLAGS_INCLUDE_UNALLOCATED)
+        {
+          DesktopEntrySet *entry_pool;
+          DesktopEntrySet *still_unallocated;
+          GetStillUnallocatedForeachData data;
+
+          entry_pool = _entry_directory_list_get_all_desktops (menu_layout_node_menu_get_app_dirs (find_menu_child (tree->layout)));
+          still_unallocated = desktop_entry_set_new ();
+
+          data.tree = tree;
+          data.allocated = allocated;
+          data.unallocated_used = unallocated_used;
+          data.still_unallocated = still_unallocated;
+
+          desktop_entry_set_foreach (entry_pool,
+                                     (DesktopEntrySetForeachFunc) get_still_unallocated_foreach,
+                                     &data);
+
+          desktop_entry_set_unref (entry_pool);
+
+          desktop_entry_set_foreach (still_unallocated,
+                                     (DesktopEntrySetForeachFunc) unallocated_entries_listify_foreach,
+                                     tree->root);
+
+          desktop_entry_set_unref (still_unallocated);
+        }
 
-      process_only_unallocated (tree, tree->root, allocated);
+      desktop_entry_set_unref (unallocated_used);
 
       /* process the layout info part that can move/remove items:
        * inline, show_empty, etc. */
@@ -4530,12 +4815,16 @@ matemenu_tree_build_from_layout (MateMenuTree *tree)
        * according to the layout info */
       process_layout_info (tree, tree->root);
 
+      update_entry_index (tree, tree->root);
+
       menu_layout_node_root_add_entries_monitor (tree->layout,
                                                  (MenuLayoutNodeEntriesChangedFunc) handle_entries_changed,
                                                  tree);
     }
 
   desktop_entry_set_unref (allocated);
+
+  return TRUE;
 }
 
 static void
@@ -4543,9 +4832,10 @@ matemenu_tree_force_rebuild (MateMenuTree *tree)
 {
   if (tree->root)
     {
-      matemenu_tree_directory_set_tree (tree->root, NULL);
+      g_hash_table_remove_all (tree->entries_by_id);
       matemenu_tree_item_unref (tree->root);
       tree->root = NULL;
+      tree->loaded = FALSE;
 
       g_assert (tree->layout != NULL);
 
@@ -4554,3 +4844,102 @@ matemenu_tree_force_rebuild (MateMenuTree *tree)
                                                     tree);
     }
 }
+
+GType
+matemenu_tree_iter_get_type (void)
+{
+  static GType gtype = G_TYPE_INVALID;
+  if (gtype == G_TYPE_INVALID)
+    {
+      gtype = g_boxed_type_register_static ("MateMenuTreeIter",
+          (GBoxedCopyFunc)matemenu_tree_iter_ref,
+          (GBoxedFreeFunc)matemenu_tree_iter_unref);
+    }
+  return gtype;
+}
+
+GType
+matemenu_tree_directory_get_type (void)
+{
+  static GType gtype = G_TYPE_INVALID;
+  if (gtype == G_TYPE_INVALID)
+    {
+      gtype = g_boxed_type_register_static ("MateMenuTreeDirectory",
+          (GBoxedCopyFunc)matemenu_tree_item_ref,
+          (GBoxedFreeFunc)matemenu_tree_item_unref);
+    }
+  return gtype;
+}
+
+GType
+matemenu_tree_entry_get_type (void)
+{
+  static GType gtype = G_TYPE_INVALID;
+  if (gtype == G_TYPE_INVALID)
+    {
+      gtype = g_boxed_type_register_static ("MateMenuTreeEntry",
+          (GBoxedCopyFunc)matemenu_tree_item_ref,
+          (GBoxedFreeFunc)matemenu_tree_item_unref);
+    }
+  return gtype;
+}
+
+GType
+matemenu_tree_separator_get_type (void)
+{
+  static GType gtype = G_TYPE_INVALID;
+  if (gtype == G_TYPE_INVALID)
+    {
+      gtype = g_boxed_type_register_static ("MateMenuTreeSeparator",
+          (GBoxedCopyFunc)matemenu_tree_item_ref,
+          (GBoxedFreeFunc)matemenu_tree_item_unref);
+    }
+  return gtype;
+}
+
+GType
+matemenu_tree_header_get_type (void)
+{
+  static GType gtype = G_TYPE_INVALID;
+  if (gtype == G_TYPE_INVALID)
+    {
+      gtype = g_boxed_type_register_static ("MateMenuTreeHeader",
+          (GBoxedCopyFunc)matemenu_tree_item_ref,
+          (GBoxedFreeFunc)matemenu_tree_item_unref);
+    }
+  return gtype;
+}
+
+GType
+matemenu_tree_alias_get_type (void)
+{
+  static GType gtype = G_TYPE_INVALID;
+  if (gtype == G_TYPE_INVALID)
+    {
+      gtype = g_boxed_type_register_static ("MateMenuTreeAlias",
+          (GBoxedCopyFunc)matemenu_tree_item_ref,
+          (GBoxedFreeFunc)matemenu_tree_item_unref);
+    }
+  return gtype;
+}
+
+GType
+matemenu_tree_flags_get_type (void)
+{
+  static GType enum_type_id = 0;
+  if (G_UNLIKELY (!enum_type_id))
+    {
+      static const GFlagsValue values[] = {
+        { MATEMENU_TREE_FLAGS_NONE, "MATEMENU_TREE_FLAGS_NONE", "none" },
+        { MATEMENU_TREE_FLAGS_INCLUDE_EXCLUDED, "MATEMENU_TREE_FLAGS_INCLUDE_EXCLUDED", "include-excluded" },
+        { MATEMENU_TREE_FLAGS_SHOW_EMPTY, "MATEMENU_TREE_FLAGS_SHOW_EMPTY", "show-empty" },
+        { MATEMENU_TREE_FLAGS_INCLUDE_NODISPLAY, "MATEMENU_TREE_FLAGS_INCLUDE_NODISPLAY", "include-nodisplay" },
+        { MATEMENU_TREE_FLAGS_SHOW_ALL_SEPARATORS, "MATEMENU_TREE_FLAGS_SHOW_ALL_SEPARATORS", "show-all-separators" },
+        { MATEMENU_TREE_FLAGS_SORT_DISPLAY_NAME, "MATEMENU_TREE_FLAGS_SORT_DISPLAY_NAME", "sort-display-name" },
+        { MATEMENU_TREE_FLAGS_INCLUDE_UNALLOCATED, "MATEMENU_TREE_FLAGS_INCLUDE_UNALLOCATED,", "include-unallocated" },
+        { 0, NULL, NULL }
+      };
+      enum_type_id = g_flags_register_static ("MateMenuTreeFlags", values);
+    }
+  return enum_type_id;
+}
diff --git a/libmenu/matemenu-tree.h b/libmenu/matemenu-tree.h
index cd3e45b..3fd3260 100644
--- a/libmenu/matemenu-tree.h
+++ b/libmenu/matemenu-tree.h
@@ -20,116 +20,143 @@
 #ifndef __MATEMENU_TREE_H__
 #define __MATEMENU_TREE_H__
 
-#include <glib.h>
-
-#ifdef __cplusplus
-extern "C" {
+#ifndef MATEMENU_I_KNOW_THIS_IS_UNSTABLE
+#error "libmate-menu should only be used if you understand that it's subject to frequent change, and is not supported as a fixed API/ABI or as part of the platform"
 #endif
 
-typedef struct MateMenuTree          MateMenuTree;
-typedef struct MateMenuTreeItem      MateMenuTreeItem;
+#include <gio/gdesktopappinfo.h>
+
+G_BEGIN_DECLS
+
+#define MATEMENU_TYPE_TREE         (matemenu_tree_get_type ())
+#define MATEMENU_TREE(o)           (G_TYPE_CHECK_INSTANCE_CAST ((o), MATEMENU_TYPE_TREE, MateMenuTree))
+#define MATEMENU_TREE_CLASS(k)     (G_TYPE_CHECK_CLASS_CAST((k), MATEMENU_TYPE_TREE, MateMenuTreeClass))
+#define MATEMENU_IS_TREE(o)        (G_TYPE_CHECK_INSTANCE_TYPE ((o), MATEMENU_TYPE_TREE))
+#define MATEMENU_IS_TREE_CLASS(k)  (G_TYPE_CHECK_CLASS_TYPE ((k), MATEMENU_TYPE_TREE))
+#define MATEMENU_TREE_GET_CLASS(o) (G_TYPE_INSTANCE_GET_CLASS ((o), G_TYPE_DESKTOP_APP_INFO, MateMenuTreeClass))
+
+typedef struct _MateMenuTree        MateMenuTree;
+typedef struct _MateMenuTreeClass   MateMenuTreeClass;
+
+struct _MateMenuTreeClass
+{
+  GObjectClass parent_class;
+};
+
+GType matemenu_tree_get_type (void) G_GNUC_CONST;
+
+typedef struct MateMenuTreeIter      MateMenuTreeIter;
 typedef struct MateMenuTreeDirectory MateMenuTreeDirectory;
 typedef struct MateMenuTreeEntry     MateMenuTreeEntry;
 typedef struct MateMenuTreeSeparator MateMenuTreeSeparator;
 typedef struct MateMenuTreeHeader    MateMenuTreeHeader;
 typedef struct MateMenuTreeAlias     MateMenuTreeAlias;
 
-typedef void (*MateMenuTreeChangedFunc) (MateMenuTree* tree, gpointer user_data);
-
-typedef enum {
-	MATEMENU_TREE_ITEM_INVALID = 0,
-	MATEMENU_TREE_ITEM_DIRECTORY,
-	MATEMENU_TREE_ITEM_ENTRY,
-	MATEMENU_TREE_ITEM_SEPARATOR,
-	MATEMENU_TREE_ITEM_HEADER,
-	MATEMENU_TREE_ITEM_ALIAS
+typedef enum
+{
+  MATEMENU_TREE_ITEM_INVALID = 0,
+  MATEMENU_TREE_ITEM_DIRECTORY,
+  MATEMENU_TREE_ITEM_ENTRY,
+  MATEMENU_TREE_ITEM_SEPARATOR,
+  MATEMENU_TREE_ITEM_HEADER,
+  MATEMENU_TREE_ITEM_ALIAS
 } MateMenuTreeItemType;
 
-#define MATEMENU_TREE_ITEM(i)      ((MateMenuTreeItem*)(i))
-#define MATEMENU_TREE_DIRECTORY(i) ((MateMenuTreeDirectory*)(i))
-#define MATEMENU_TREE_ENTRY(i)     ((MateMenuTreeEntry*)(i))
-#define MATEMENU_TREE_SEPARATOR(i) ((MateMenuTreeSeparator*)(i))
-#define MATEMENU_TREE_HEADER(i)    ((MateMenuTreeHeader*)(i))
-#define MATEMENU_TREE_ALIAS(i)     ((MateMenuTreeAlias*)(i))
-
-typedef enum {
-	MATEMENU_TREE_FLAGS_NONE                = 0,
-	MATEMENU_TREE_FLAGS_INCLUDE_EXCLUDED    = 1 << 0,
-	MATEMENU_TREE_FLAGS_SHOW_EMPTY          = 1 << 1,
-	MATEMENU_TREE_FLAGS_INCLUDE_NODISPLAY   = 1 << 2,
-	MATEMENU_TREE_FLAGS_SHOW_ALL_SEPARATORS = 1 << 3,
-	MATEMENU_TREE_FLAGS_MASK                = 0x0f
+GType matemenu_tree_iter_get_type (void);
+
+/* Explicitly skip item, it's a "hidden" base class */
+GType matemenu_tree_directory_get_type (void);
+GType matemenu_tree_entry_get_type (void);
+GType matemenu_tree_separator_get_type (void);
+GType matemenu_tree_header_get_type (void);
+GType matemenu_tree_alias_get_type (void);
+
+typedef enum
+{
+  MATEMENU_TREE_FLAGS_NONE                = 0,
+  MATEMENU_TREE_FLAGS_INCLUDE_EXCLUDED    = 1 << 0,
+  MATEMENU_TREE_FLAGS_INCLUDE_NODISPLAY   = 1 << 1,
+  MATEMENU_TREE_FLAGS_INCLUDE_UNALLOCATED = 1 << 2,
+  /* leave some space for more include flags */
+  MATEMENU_TREE_FLAGS_SHOW_EMPTY          = 1 << 8,
+  MATEMENU_TREE_FLAGS_SHOW_ALL_SEPARATORS = 1 << 9,
+  /* leave some space for more show flags */
+  MATEMENU_TREE_FLAGS_SORT_DISPLAY_NAME   = 1 << 16
 } MateMenuTreeFlags;
+GType matemenu_tree_flags_get_type (void);
+#define MATEMENU_TYPE_TREE_FLAGS (matemenu_tree_flags_get_type ())
 
-typedef enum {
-	#define MATEMENU_TREE_SORT_FIRST MATEMENU_TREE_SORT_NAME
-	MATEMENU_TREE_SORT_NAME = 0,
-	MATEMENU_TREE_SORT_DISPLAY_NAME
-	#define MATEMENU_TREE_SORT_LAST MATEMENU_TREE_SORT_DISPLAY_NAME
-} MateMenuTreeSortKey;
-
-MateMenuTree* matemenu_tree_lookup(const char* menu_file, MateMenuTreeFlags flags);
+MateMenuTree *matemenu_tree_new (const char     *menu_basename,
+                           MateMenuTreeFlags  flags);
 
-MateMenuTree* matemenu_tree_ref(MateMenuTree* tree);
-void matemenu_tree_unref(MateMenuTree* tree);
+MateMenuTree *matemenu_tree_new_for_path (const char     *menu_path,
+                                    MateMenuTreeFlags  flags);
 
-void matemenu_tree_set_user_data(MateMenuTree* tree, gpointer user_data, GDestroyNotify dnotify);
-gpointer matemenu_tree_get_user_data(MateMenuTree* tree);
+gboolean   matemenu_tree_load_sync (MateMenuTree  *tree,
+                                 GError    **error);
 
-const char* matemenu_tree_get_menu_file(MateMenuTree* tree);
-MateMenuTreeDirectory* matemenu_tree_get_root_directory(MateMenuTree* tree);
-MateMenuTreeDirectory* matemenu_tree_get_directory_from_path(MateMenuTree* tree, const char* path);
+const char         *matemenu_tree_get_canonical_menu_path (MateMenuTree  *tree);
+MateMenuTreeDirectory *matemenu_tree_get_root_directory      (MateMenuTree  *tree);
+MateMenuTreeDirectory *matemenu_tree_get_directory_from_path (MateMenuTree  *tree,
+							const char *path);
+MateMenuTreeEntry     *matemenu_tree_get_entry_by_id         (MateMenuTree  *tree,
+							const char *id);
 
-MateMenuTreeSortKey matemenu_tree_get_sort_key(MateMenuTree* tree);
-void matemenu_tree_set_sort_key(MateMenuTree* tree, MateMenuTreeSortKey sort_key);
+gpointer matemenu_tree_item_ref   (gpointer item);
+void     matemenu_tree_item_unref (gpointer item);
 
+MateMenuTreeDirectory *matemenu_tree_directory_get_parent    (MateMenuTreeDirectory *directory);
+const char *matemenu_tree_directory_get_name              (MateMenuTreeDirectory *directory);
+const char *matemenu_tree_directory_get_generic_name      (MateMenuTreeDirectory *directory);
+const char *matemenu_tree_directory_get_comment           (MateMenuTreeDirectory *directory);
+GIcon      *matemenu_tree_directory_get_icon              (MateMenuTreeDirectory *directory);
+const char *matemenu_tree_directory_get_desktop_file_path (MateMenuTreeDirectory *directory);
+const char *matemenu_tree_directory_get_menu_id           (MateMenuTreeDirectory *directory);
+MateMenuTree  *matemenu_tree_directory_get_tree              (MateMenuTreeDirectory *directory);
 
+gboolean matemenu_tree_directory_get_is_nodisplay (MateMenuTreeDirectory *directory);
 
-gpointer matemenu_tree_item_ref(gpointer item);
-void matemenu_tree_item_unref(gpointer item);
+MateMenuTreeIter      *matemenu_tree_directory_iter            (MateMenuTreeDirectory *directory);
 
-void matemenu_tree_item_set_user_data(MateMenuTreeItem* item, gpointer user_data, GDestroyNotify dnotify);
-gpointer matemenu_tree_item_get_user_data(MateMenuTreeItem* item);
+MateMenuTreeIter      *matemenu_tree_iter_ref                  (MateMenuTreeIter *iter);
+void                matemenu_tree_iter_unref                (MateMenuTreeIter *iter);
 
-MateMenuTreeItemType matemenu_tree_item_get_type(MateMenuTreeItem* item);
-MateMenuTreeDirectory* matemenu_tree_item_get_parent(MateMenuTreeItem* item);
+MateMenuTreeItemType   matemenu_tree_iter_next                 (MateMenuTreeIter *iter);
+MateMenuTreeDirectory *matemenu_tree_iter_get_directory        (MateMenuTreeIter *iter);
+MateMenuTreeEntry     *matemenu_tree_iter_get_entry            (MateMenuTreeIter *iter);
+MateMenuTreeHeader    *matemenu_tree_iter_get_header           (MateMenuTreeIter *iter);
+MateMenuTreeAlias     *matemenu_tree_iter_get_alias            (MateMenuTreeIter *iter);
+MateMenuTreeSeparator *matemenu_tree_iter_get_separator        (MateMenuTreeIter *iter);
 
+char *matemenu_tree_directory_make_path (MateMenuTreeDirectory *directory,
+				      MateMenuTreeEntry     *entry);
 
-GSList* matemenu_tree_directory_get_contents(MateMenuTreeDirectory* directory);
-const char* matemenu_tree_directory_get_name(MateMenuTreeDirectory* directory);
-const char* matemenu_tree_directory_get_comment(MateMenuTreeDirectory* directory);
-const char* matemenu_tree_directory_get_icon(MateMenuTreeDirectory* directory);
-const char* matemenu_tree_directory_get_desktop_file_path(MateMenuTreeDirectory* directory);
-const char* matemenu_tree_directory_get_menu_id(MateMenuTreeDirectory* directory);
-MateMenuTree* matemenu_tree_directory_get_tree(MateMenuTreeDirectory* directory);
 
-gboolean matemenu_tree_directory_get_is_nodisplay(MateMenuTreeDirectory* directory);
+GDesktopAppInfo    *matemenu_tree_entry_get_app_info       (MateMenuTreeEntry *entry);
+MateMenuTreeDirectory *matemenu_tree_entry_get_parent         (MateMenuTreeEntry *entry);
+MateMenuTree          *matemenu_tree_entry_get_tree           (MateMenuTreeEntry *entry);
 
-char* matemenu_tree_directory_make_path(MateMenuTreeDirectory* directory, MateMenuTreeEntry* entry);
+const char *matemenu_tree_entry_get_desktop_file_path (MateMenuTreeEntry *entry);
+const char *matemenu_tree_entry_get_desktop_file_id   (MateMenuTreeEntry *entry);
 
+gboolean matemenu_tree_entry_get_is_nodisplay_recurse  (MateMenuTreeEntry *entry);
+gboolean matemenu_tree_entry_get_is_excluded  (MateMenuTreeEntry *entry);
+gboolean matemenu_tree_entry_get_is_unallocated  (MateMenuTreeEntry *entry);
 
-const char* matemenu_tree_entry_get_name(MateMenuTreeEntry* entry);
-const char* matemenu_tree_entry_get_generic_name(MateMenuTreeEntry* entry);
-const char* matemenu_tree_entry_get_display_name(MateMenuTreeEntry* entry);
-const char* matemenu_tree_entry_get_comment(MateMenuTreeEntry* entry);
-const char* matemenu_tree_entry_get_icon(MateMenuTreeEntry* entry);
-const char* matemenu_tree_entry_get_exec(MateMenuTreeEntry* entry);
-gboolean matemenu_tree_entry_get_launch_in_terminal(MateMenuTreeEntry* entry);
-const char* matemenu_tree_entry_get_desktop_file_path(MateMenuTreeEntry* entry);
-const char* matemenu_tree_entry_get_desktop_file_id(MateMenuTreeEntry* entry);
-gboolean matemenu_tree_entry_get_is_excluded(MateMenuTreeEntry* entry);
-gboolean matemenu_tree_entry_get_is_nodisplay(MateMenuTreeEntry* entry);
+MateMenuTreeDirectory *matemenu_tree_header_get_directory (MateMenuTreeHeader *header);
+MateMenuTree          *matemenu_tree_header_get_tree      (MateMenuTreeHeader *header);
+MateMenuTreeDirectory *matemenu_tree_header_get_parent    (MateMenuTreeHeader *header);
 
-MateMenuTreeDirectory* matemenu_tree_header_get_directory(MateMenuTreeHeader* header);
+MateMenuTreeDirectory *matemenu_tree_alias_get_directory         (MateMenuTreeAlias *alias);
+MateMenuTreeItemType   matemenu_tree_alias_get_aliased_item_type (MateMenuTreeAlias *alias);
+MateMenuTreeDirectory *matemenu_tree_alias_get_aliased_directory (MateMenuTreeAlias *alias);
+MateMenuTreeEntry     *matemenu_tree_alias_get_aliased_entry     (MateMenuTreeAlias *alias);
+MateMenuTree          *matemenu_tree_alias_get_tree              (MateMenuTreeAlias *alias);
+MateMenuTreeDirectory *matemenu_tree_alias_get_parent            (MateMenuTreeAlias *alias);
 
-MateMenuTreeDirectory* matemenu_tree_alias_get_directory(MateMenuTreeAlias* alias);
-MateMenuTreeItem* matemenu_tree_alias_get_item(MateMenuTreeAlias* alias);
+MateMenuTree          *matemenu_tree_separator_get_tree (MateMenuTreeSeparator *separator);
+MateMenuTreeDirectory *matemenu_tree_separator_get_parent (MateMenuTreeSeparator *separator);
 
-void matemenu_tree_add_monitor(MateMenuTree* tree, MateMenuTreeChangedFunc callback, gpointer user_data);
-void matemenu_tree_remove_monitor(MateMenuTree* tree, MateMenuTreeChangedFunc callback, gpointer user_data);
-
-#ifdef __cplusplus
-}
-#endif
+G_END_DECLS
 
 #endif /* __MATEMENU_TREE_H__ */
diff --git a/libmenu/menu-layout.c b/libmenu/menu-layout.c
index 89e9752..30d11b3 100644
--- a/libmenu/menu-layout.c
+++ b/libmenu/menu-layout.c
@@ -64,7 +64,10 @@ struct MenuLayoutNodeRoot
   char *basedir;
   char *name;
 
+  GMainContext *main_context;
+
   GSList *monitors;
+  GSource *monitors_idle_handler;
 };
 
 struct MenuLayoutNodeMenu
@@ -133,16 +136,14 @@ node_next (MenuLayoutNode *node)
   return node->next;
 }
 
-static void
-handle_entry_directory_changed (EntryDirectory *dir,
-                                MenuLayoutNode *node)
+static gboolean
+menu_layout_invoke_monitors (MenuLayoutNodeRoot *nr)
 {
-  MenuLayoutNodeRoot *nr;
-  GSList             *tmp;
+  GSList *tmp;
 
-  g_assert (node->type == MENU_LAYOUT_NODE_MENU);
+  g_assert (nr->node.type == MENU_LAYOUT_NODE_ROOT);
 
-  nr = (MenuLayoutNodeRoot *) menu_layout_node_get_root (node);
+  nr->monitors_idle_handler = NULL;
 
   tmp = nr->monitors;
   while (tmp != NULL)
@@ -154,6 +155,28 @@ handle_entry_directory_changed (EntryDirectory *dir,
 
       tmp = next;
     }
+
+  return FALSE;
+}
+
+static void
+handle_entry_directory_changed (EntryDirectory *dir,
+                                MenuLayoutNode *node)
+{
+  MenuLayoutNodeRoot *nr;
+
+  g_assert (node->type == MENU_LAYOUT_NODE_MENU);
+
+  nr = (MenuLayoutNodeRoot *) menu_layout_node_get_root (node);
+
+  if (nr->monitors_idle_handler == NULL)
+    {
+      nr->monitors_idle_handler = g_idle_source_new ();
+      g_source_set_callback (nr->monitors_idle_handler,
+                             (GSourceFunc) menu_layout_invoke_monitors, nr, NULL);
+      g_source_attach (nr->monitors_idle_handler, nr->main_context);
+      g_source_unref (nr->monitors_idle_handler);
+    }
 }
 
 static void
@@ -224,6 +247,14 @@ menu_layout_node_unref (MenuLayoutNode *node)
           g_slist_foreach (nr->monitors, (GFunc) g_free, NULL);
           g_slist_free (nr->monitors);
 
+          if (nr->monitors_idle_handler != NULL)
+            g_source_destroy (nr->monitors_idle_handler);
+          nr->monitors_idle_handler = NULL;
+
+          if (nr->main_context != NULL)
+            g_main_context_unref (nr->main_context);
+          nr->main_context = NULL;
+
           g_free (nr->basedir);
           g_free (nr->name);
         }
@@ -2266,6 +2297,7 @@ menu_layout_load (const char  *filename,
                   const char  *non_prefixed_basename,
                   GError     **err)
 {
+  GMainContext        *main_context;
   GMarkupParseContext *context;
   MenuLayoutNodeRoot  *root;
   MenuLayoutNode      *retval;
@@ -2281,6 +2313,8 @@ menu_layout_load (const char  *filename,
   retval = NULL;
   context = NULL;
 
+  main_context = g_main_context_get_thread_default ();
+
   menu_verbose ("Loading \"%s\" from disk\n", filename);
 
   if (!g_file_get_contents (filename,
@@ -2328,6 +2362,8 @@ menu_layout_load (const char  *filename,
   error = NULL;
   g_markup_parse_context_end_parse (context, &error);
 
+  root->main_context = main_context ? g_main_context_ref (main_context) : NULL;
+
  out:
   if (context)
     g_markup_parse_context_free (context);