find_used_refs (FlatpakDir         *self,
                FlatpakDir         *shadowing_dir, /* nullable */
                const char         *arch,
                GHashTable         *metadata_injection,
                GHashTable         *refs_to_exclude,
                GHashTable         *used_refs, /* This is filled in */
                GCancellable       *cancellable,
                GError            **error)
{
  g_autoptr(GPtrArray) root_app_refs = NULL;
  g_autoptr(GPtrArray) root_runtime_refs = NULL;
  g_autoptr(GHashTable) analyzed_refs = NULL;
  g_autoptr(GQueue) refs_to_analyze = NULL;
  FlatpakDir *root_ref_dir;
  FlatpakDecomposed *ref_to_analyze;

  refs_to_analyze = g_queue_new ();
  analyzed_refs = g_hash_table_new_full ((GHashFunc)flatpak_decomposed_hash, (GEqualFunc)flatpak_decomposed_equal, (GDestroyNotify)flatpak_decomposed_unref, NULL);

  if (shadowing_dir)
    root_ref_dir = shadowing_dir;
  else
    root_ref_dir = self;

  root_app_refs = flatpak_dir_list_refs (root_ref_dir, FLATPAK_KINDS_APP, cancellable, error);
  if (root_app_refs == NULL)
    return NULL;

  for (int i = 0; i < root_app_refs->len; i++)
    {
      FlatpakDecomposed *root_app_ref = g_ptr_array_index (root_app_refs, i);
      queue_ref_for_analysis (root_app_ref, arch, analyzed_refs, refs_to_analyze);
    }

  root_runtime_refs = flatpak_dir_list_refs (root_ref_dir, FLATPAK_KINDS_RUNTIME, cancellable, error);
  if (root_runtime_refs == NULL)
    return NULL;

  for (int i = 0; i < root_runtime_refs->len; i++)
    {
      FlatpakDecomposed *root_runtime_ref = g_ptr_array_index (root_runtime_refs, i);
      /* Consider all shadow dir runtimes as roots because we don't really do full analysis for shadowing_dir.
       * For example a system installed app could end up using the user version of a runtime, which in turn
       * uses a system gl extension.
       *
       * However, for non-shadowed runtime refs, only pinned ones are roots */
      if (root_ref_dir == shadowing_dir ||
          flatpak_dir_ref_is_pinned (root_ref_dir, flatpak_decomposed_get_ref (root_runtime_ref)))
        queue_ref_for_analysis (root_runtime_ref, arch, analyzed_refs, refs_to_analyze);
    }

  /* Any injected refs are considered used, because this is used by transaction
   * to emulate installing a new ref, and we never want the new ref:s dependencies
   * seem ununsed. */
  if (metadata_injection)
    {
      GLNX_HASH_TABLE_FOREACH (metadata_injection, const char *, injected_ref)
        {
          g_autoptr(FlatpakDecomposed) injected = flatpak_decomposed_new_from_ref (injected_ref, NULL);
          if (injected)
            queue_ref_for_analysis (injected, arch, analyzed_refs, refs_to_analyze);
        }
    }

  while ((ref_to_analyze = g_queue_pop_head (refs_to_analyze)) != NULL)
    {
      g_autoptr(GKeyFile) metakey = NULL;
      gboolean ref_is_shadowed;
      gboolean is_app;
      g_autoptr(GPtrArray) related = NULL;
      g_autofree char *sdk = NULL;

      if (!maybe_get_metakey (self, shadowing_dir, ref_to_analyze, metadata_injection,
                              &metakey, &ref_is_shadowed))
        continue; /* Something used something we could not find, that is fine and happens for instance with sdk dependencies */

      if (!ref_is_shadowed)
        {
          /* Mark the analyzed ref used as it wasn't shadowed */
          if (!g_hash_table_contains (used_refs, ref_to_analyze))
            g_hash_table_add (used_refs, flatpak_decomposed_ref (ref_to_analyze));

          /* For excluded refs we mark them as used (above) so that they don't get listed as
           * unused, but we don't analyze them for any dependencies. Note that refs_to_exclude only
           * affects the base dir, so does not affect shadowed refs */
          if (refs_to_exclude != NULL && g_hash_table_contains (refs_to_exclude, ref_to_analyze))
            continue;
        }

      /************************************************
       * Find all dependencies and queue for analysis *
       ***********************************************/

      is_app = flatpak_decomposed_is_app (ref_to_analyze);

      /* App directly depends on its runtime */
      if (is_app)
        {
          g_autofree char *runtime = g_key_file_get_string (metakey, "Application", "runtime", NULL);
          if (runtime)
            {
              g_autoptr(FlatpakDecomposed) runtime_ref = flatpak_decomposed_new_from_pref (FLATPAK_KINDS_RUNTIME, runtime, NULL);
              if (runtime_ref && !flatpak_decomposed_equal (runtime_ref, ref_to_analyze))
                queue_ref_for_analysis (runtime_ref, arch, analyzed_refs, refs_to_analyze);
            }
        }

      /* Both apps and runtims directly depends on its sdk, to avoid suddenly uninstalling something you use to develop the app */
      sdk = g_key_file_get_string (metakey, is_app ? "Application" : "Runtime", "sdk", NULL);
      if (sdk)
        {
          g_autoptr(FlatpakDecomposed) sdk_ref = flatpak_decomposed_new_from_pref (FLATPAK_KINDS_RUNTIME, sdk, NULL);
          if (sdk_ref && !flatpak_decomposed_equal (sdk_ref, ref_to_analyze))
            queue_ref_for_analysis (sdk_ref, arch, analyzed_refs, refs_to_analyze);
        }

      /* Extensions with extra data, that are not specially marked NoRuntime needs the runtime at install.
       * Lets keep it around to not re-download it next update */
      if (!is_app &&
          g_key_file_has_group (metakey, "Extra Data") &&
          !g_key_file_get_boolean (metakey, "Extra Data", "NoRuntime", NULL))
        {
          g_autofree char *extension_runtime_ref = g_key_file_get_string (metakey, "ExtensionOf", "runtime", NULL);
          if (extension_runtime_ref != NULL)
            {
              g_autoptr(FlatpakDecomposed) d = flatpak_decomposed_new_from_ref (extension_runtime_ref, NULL);
              if (d)
                queue_ref_for_analysis (d, arch, analyzed_refs, refs_to_analyze);
            }
        }

      /* We pass NULL for remote-name here, because we want to consider related refs from all remotes */
      related = flatpak_dir_find_local_related_for_metadata (self, ref_to_analyze,
                                                             NULL, metakey, NULL, NULL);
      for (int i = 0; related != NULL && i < related->len; i++)
        {
          FlatpakRelated *rel = g_ptr_array_index (related, i);

          if (!rel->auto_prune)
            {
              queue_ref_for_analysis (rel->ref, arch, analyzed_refs, refs_to_analyze);
            }
        }
    }

  return g_steal_pointer (&used_refs);
}