/*

 * Copyright (C) 2011 Colin Walters <walters@verbum.org>

 *

 * SPDX-License-Identifier: LGPL-2.0+

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2 of the License, or (at your option) any later version.

 *

 * This library is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with this library; if not, write to the

 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

 * Boston, MA 02111-1307, USA.

 *

 * Author: Colin Walters <walters@verbum.org>

 */

#include "config.h"

#include "libglnx.h"

#include "ostree.h"

#include "otutil.h"

struct _OstreeRepoRealCommitTraverseIter {

  gboolean initialized;

  OstreeRepo *repo;

  GVariant *commit;

  GVariant *current_dir;

  const char *name;

  OstreeRepoCommitIterResult state;

  guint idx;

  char checksum_content[OSTREE_SHA256_STRING_LEN+1];

  char checksum_meta[OSTREE_SHA256_STRING_LEN+1];

};

/**

 * ostree_repo_commit_traverse_iter_init_commit:

 * @iter: An iter

 * @repo: A repo

 * @commit: Variant of type %OSTREE_OBJECT_TYPE_COMMIT

 * @flags: Flags

 * @error: Error

 *

 * Initialize (in place) an iterator over the root of a commit object.

 */

gboolean

ostree_repo_commit_traverse_iter_init_commit (OstreeRepoCommitTraverseIter   *iter,

                                              OstreeRepo                     *repo,

                                              GVariant                       *commit,

                                              OstreeRepoCommitTraverseFlags   flags,

                                              GError                        **error)

{

  struct _OstreeRepoRealCommitTraverseIter *real =

    (struct _OstreeRepoRealCommitTraverseIter*)iter;

  memset (real, 0, sizeof (*real));

  real->initialized = TRUE;

  real->repo = g_object_ref (repo);

  real->commit = g_variant_ref (commit);

  real->current_dir = NULL;

  real->idx = 0;

  g_autoptr(GVariant) content_csum_bytes = NULL;

  g_variant_get_child (commit, 6, "@ay", &content_csum_bytes);

  const guchar *csum = ostree_checksum_bytes_peek_validate (content_csum_bytes, error);

  if (!csum)

    return FALSE;

  ostree_checksum_inplace_from_bytes (csum, real->checksum_content);

  g_autoptr(GVariant) meta_csum_bytes = NULL;

  g_variant_get_child (commit, 7, "@ay", &meta_csum_bytes);

  csum = ostree_checksum_bytes_peek_validate (meta_csum_bytes, error);

  if (!csum)

    return FALSE;

  ostree_checksum_inplace_from_bytes (csum, real->checksum_meta);

  return TRUE;

}

/**

 * ostree_repo_commit_traverse_iter_init_dirtree:

 * @iter: An iter

 * @repo: A repo

 * @dirtree: Variant of type %OSTREE_OBJECT_TYPE_DIR_TREE

 * @flags: Flags

 * @error: Error

 *

 * Initialize (in place) an iterator over a directory tree.

 */

gboolean

ostree_repo_commit_traverse_iter_init_dirtree (OstreeRepoCommitTraverseIter   *iter,

                                               OstreeRepo                     *repo,

                                               GVariant                       *dirtree,

                                               OstreeRepoCommitTraverseFlags   flags,

                                               GError                        **error)

{

  struct _OstreeRepoRealCommitTraverseIter *real =

    (struct _OstreeRepoRealCommitTraverseIter*)iter;

  memset (real, 0, sizeof (*real));

  real->initialized = TRUE;

  real->repo = g_object_ref (repo);

  real->current_dir = g_variant_ref (dirtree);

  real->idx = 0;

  return TRUE;

}

/**

 * ostree_repo_commit_traverse_iter_next:

 * @iter: An iter

 * @cancellable: Cancellable

 * @error: Error

 *

 * Step the interator to the next item.  Files will be returned first,

 * then subdirectories.  Call this in a loop; upon encountering

 * %OSTREE_REPO_COMMIT_ITER_RESULT_END, there will be no more files or

 * directories.  If %OSTREE_REPO_COMMIT_ITER_RESULT_DIR is returned,

 * then call ostree_repo_commit_traverse_iter_get_dir() to retrieve

 * data for that directory.  Similarly, if

 * %OSTREE_REPO_COMMIT_ITER_RESULT_FILE is returned, call

 * ostree_repo_commit_traverse_iter_get_file().

 * 

 * If %OSTREE_REPO_COMMIT_ITER_RESULT_ERROR is returned, it is a

 * program error to call any further API on @iter except for

 * ostree_repo_commit_traverse_iter_clear().

 */

OstreeRepoCommitIterResult

ostree_repo_commit_traverse_iter_next (OstreeRepoCommitTraverseIter *iter,

                                       GCancellable                 *cancellable,

                                       GError                      **error)

{

  struct _OstreeRepoRealCommitTraverseIter *real =

    (struct _OstreeRepoRealCommitTraverseIter*)iter;

  OstreeRepoCommitIterResult res = OSTREE_REPO_COMMIT_ITER_RESULT_ERROR;

  if (!real->current_dir)

    {

      if (!ostree_repo_load_variant (real->repo, OSTREE_OBJECT_TYPE_DIR_TREE,

                                     real->checksum_content,

                                     &real->current_dir,

                                     error))

        goto out;

      res = OSTREE_REPO_COMMIT_ITER_RESULT_DIR;

    }

  else

    {

      guint nfiles;

      guint ndirs;

      guint idx;

      const guchar *csum;

      g_autoptr(GVariant) content_csum_v = NULL;

      g_autoptr(GVariant) meta_csum_v = NULL;

      g_autoptr(GVariant) files_variant = NULL;

      g_autoptr(GVariant) dirs_variant = NULL;

      files_variant = g_variant_get_child_value (real->current_dir, 0);

      dirs_variant = g_variant_get_child_value (real->current_dir, 1);

      nfiles = g_variant_n_children (files_variant);

      ndirs = g_variant_n_children (dirs_variant);

      if (real->idx < nfiles)

        {

          idx = real->idx;

          g_variant_get_child (files_variant, idx, "(&s@ay)",

                               &real->name,

                               &content_csum_v);

          csum = ostree_checksum_bytes_peek_validate (content_csum_v, error);

          if (!csum)

            goto out;

          ostree_checksum_inplace_from_bytes (csum, real->checksum_content);

          res = OSTREE_REPO_COMMIT_ITER_RESULT_FILE;

          real->idx++;

        }

      else if (real->idx < nfiles + ndirs)

        {

          idx = real->idx - nfiles;

          g_variant_get_child (dirs_variant, idx, "(&s@ay@ay)",

                               &real->name, &content_csum_v, &meta_csum_v);

          csum = ostree_checksum_bytes_peek_validate (content_csum_v, error);

          if (!csum)

            goto out;

          ostree_checksum_inplace_from_bytes (csum, real->checksum_content);

          csum = ostree_checksum_bytes_peek_validate (meta_csum_v, error);

          if (!csum)

            goto out;

          ostree_checksum_inplace_from_bytes (csum, real->checksum_meta);

          res = OSTREE_REPO_COMMIT_ITER_RESULT_DIR;

          real->idx++;

        }

      else

        res = OSTREE_REPO_COMMIT_ITER_RESULT_END;

    }

  real->state = res;

 out:

  return res;

}

/**

 * ostree_repo_commit_traverse_iter_get_file:

 * @iter: An iter

 * @out_name: (out) (transfer none): Name of current file

 * @out_checksum: (out) (transfer none): Checksum of current file

 *

 * Return information on the current file.  This function may only be

 * called if %OSTREE_REPO_COMMIT_ITER_RESULT_FILE was returned from

 * ostree_repo_commit_traverse_iter_next().

 */

void

ostree_repo_commit_traverse_iter_get_file (OstreeRepoCommitTraverseIter *iter,

                                           char                        **out_name,

                                           char                        **out_checksum)

{

  struct _OstreeRepoRealCommitTraverseIter *real =

    (struct _OstreeRepoRealCommitTraverseIter*)iter;

  *out_name = (char*)real->name;

  *out_checksum = (char*)real->checksum_content;

}

/**

 * ostree_repo_commit_traverse_iter_get_dir:

 * @iter: An iter

 * @out_name: (out) (transfer none): Name of current dir

 * @out_content_checksum: (out) (transfer none): Checksum of current content

 * @out_meta_checksum: (out) (transfer none): Checksum of current metadata

 *

 * Return information on the current directory.  This function may

 * only be called if %OSTREE_REPO_COMMIT_ITER_RESULT_DIR was returned

 * from ostree_repo_commit_traverse_iter_next().

 */

void

ostree_repo_commit_traverse_iter_get_dir (OstreeRepoCommitTraverseIter *iter,

                                          char                        **out_name,

                                          char                        **out_content_checksum,

                                          char                        **out_meta_checksum)

{

  struct _OstreeRepoRealCommitTraverseIter *real =

    (struct _OstreeRepoRealCommitTraverseIter*)iter;

  *out_name = (char*)real->name;

  *out_content_checksum = (char*)real->checksum_content;

  *out_meta_checksum = (char*)real->checksum_meta;

}

void

ostree_repo_commit_traverse_iter_clear (OstreeRepoCommitTraverseIter *iter)

{

  struct _OstreeRepoRealCommitTraverseIter *real =

    (struct _OstreeRepoRealCommitTraverseIter*)iter;

  g_clear_object (&real->repo);

  g_clear_pointer (&real->commit, g_variant_unref);

  g_clear_pointer (&real->current_dir, g_variant_unref);

}

void

ostree_repo_commit_traverse_iter_cleanup (void *p)

{

  OstreeRepoCommitTraverseIter *iter = p;

  struct _OstreeRepoRealCommitTraverseIter *real =

    (struct _OstreeRepoRealCommitTraverseIter*)iter;

  if (real->initialized)

    {

      ostree_repo_commit_traverse_iter_clear (iter);

      real->initialized = FALSE;

    }

}

/**

 * ostree_repo_traverse_new_reachable:

 *

 * This hash table is a set of #GVariant which can be accessed via

 * ostree_object_name_deserialize().

 *

 * Returns: (transfer container) (element-type GVariant GVariant): A new hash table

 */

GHashTable *

ostree_repo_traverse_new_reachable (void)

{

  return g_hash_table_new_full (ostree_hash_object_name, g_variant_equal,

                                NULL, (GDestroyNotify)g_variant_unref);

}

/**

 * ostree_repo_traverse_new_parents:

 *

 * This hash table is a mapping from #GVariant which can be accessed

 * via ostree_object_name_deserialize() to a #GVariant containing either

 * a similar #GVariant or and array of them, listing the parents of the key.

 *

 * Returns: (transfer container) (element-type GVariant GVariant): A new hash table

 *

 * Since: 2018.5

 */

GHashTable *

ostree_repo_traverse_new_parents (void)

{

  return g_hash_table_new_full (ostree_hash_object_name, g_variant_equal,

                                (GDestroyNotify)g_variant_unref, (GDestroyNotify)g_variant_unref);

}

static void

parents_get_commits (GHashTable *parents_ht, GVariant *object, GHashTable *res)

{

  const char *checksum;

  OstreeObjectType type;

  if (object == NULL)

    return;

  ostree_object_name_deserialize (object, &checksum, &type);

  if (type == OSTREE_OBJECT_TYPE_COMMIT)

    g_hash_table_add (res, g_strdup (checksum));

  else

    {

      GVariant *parents = g_hash_table_lookup (parents_ht, object);

      if (parents == NULL)

        g_debug ("Unexpected NULL parent");

      else if (g_variant_is_of_type (parents, G_VARIANT_TYPE_ARRAY))

        {

          gsize i, len = g_variant_n_children (parents);

          for (i = 0; i < len; i++)

            {

              g_autoptr(GVariant) parent = g_variant_get_child_value (parents, i);

              parents_get_commits (parents_ht, parent, res);

            }

        }

      else

        parents_get_commits (parents_ht, parents, res);

    }

}

/**

 * ostree_repo_traverse_parents_get_commits:

 *

 * Gets all the commits that a certain object belongs to, as recorded

 * by a parents table gotten from ostree_repo_traverse_commit_union_with_parents.

 *

 * Returns: (transfer full) (array zero-terminated=1): An array of checksums for

 * the commits the key belongs to.

 *

 * Since: 2018.5

 */

char **

ostree_repo_traverse_parents_get_commits (GHashTable *parents, GVariant *object)

{

  g_autoptr(GHashTable) res = g_hash_table_new (g_str_hash, g_str_equal);

  parents_get_commits (parents, object, res);

  return (char **)g_hash_table_get_keys_as_array (res, NULL);

}

static gboolean

traverse_dirtree (OstreeRepo           *repo,

                  const char           *checksum,

                  GVariant             *parent_key,

                  GHashTable           *inout_reachable,

                  GHashTable           *inout_parents,

                  gboolean              ignore_missing_dirs,

                  GCancellable         *cancellable,

                  GError              **error);

static void

add_parent_ref (GHashTable  *inout_parents,

                GVariant    *key,

                GVariant    *parent_key)

{

  GVariant *old_parents;

  if (inout_parents == NULL)

    return;

  old_parents = g_hash_table_lookup (inout_parents, key);

  if (old_parents == NULL)

    {

      /* For the common case of a single pointer we skip using an array to save memory. */

      g_hash_table_insert (inout_parents, g_variant_ref (key), g_variant_ref (parent_key));

    }

  else

    {

      g_autofree GVariant **new_parents = NULL;

      gsize i, len = 0;

      if (g_variant_is_of_type (old_parents, G_VARIANT_TYPE_ARRAY))

        {

          gsize old_parents_len = g_variant_n_children (old_parents);

          new_parents = g_new (GVariant *,  old_parents_len + 1);

          for (i = 0; i < old_parents_len ; i++)

            {

              g_autoptr(GVariant) old_parent = g_variant_get_child_value (old_parents, i);

              if (!g_variant_equal (old_parent, parent_key))

                new_parents[len++] = g_steal_pointer (&old_parent);

            }

        }

      else

        {

          new_parents = g_new (GVariant *, 2);

          if (!g_variant_equal (old_parents, parent_key))

            new_parents[len++] = g_variant_ref (old_parents);

        }

      new_parents[len++] = g_variant_ref (parent_key);

      g_hash_table_insert (inout_parents, g_variant_ref (key),

                           g_variant_ref_sink (g_variant_new_array (G_VARIANT_TYPE ("(su)"), new_parents , len)));

      for (i = 0; i < len; i++)

        g_variant_unref (new_parents[i]);

    }

}

static gboolean

traverse_iter (OstreeRepo                          *repo,

               OstreeRepoCommitTraverseIter        *iter,

               GVariant                            *parent_key,

               GHashTable                          *inout_reachable,

               GHashTable                          *inout_parents,

               gboolean                             ignore_missing_dirs,

               GCancellable                        *cancellable,

               GError                             **error)

{

  while (TRUE)

    {

      g_autoptr(GVariant) key = NULL;

      g_autoptr(GError) local_error = NULL;

      OstreeRepoCommitIterResult iterres =

        ostree_repo_commit_traverse_iter_next (iter, cancellable, &local_error);

      if (iterres == OSTREE_REPO_COMMIT_ITER_RESULT_ERROR)

        {

          /* There is only one kind of not-found error, which is

             failing to load the dirmeta itself, if so, we ignore that

             (and the whole subtree) if told to. */

          if (ignore_missing_dirs &&

              g_error_matches (local_error, G_IO_ERROR, G_IO_ERROR_NOT_FOUND))

            {

              g_debug ("Ignoring not-found dirmeta");

              return TRUE;  /* Note early return */

            }

          g_propagate_error (error, g_steal_pointer (&local_error));

          return FALSE;

        }

      else if (iterres == OSTREE_REPO_COMMIT_ITER_RESULT_END)

        break;

      else if (iterres == OSTREE_REPO_COMMIT_ITER_RESULT_FILE)

        {

          char *name;

          char *checksum;

          ostree_repo_commit_traverse_iter_get_file (iter, &name, &checksum);

          g_debug ("Found file object %s", checksum);

          key = g_variant_ref_sink (ostree_object_name_serialize (checksum, OSTREE_OBJECT_TYPE_FILE));

          add_parent_ref (inout_parents, key, parent_key);

          g_hash_table_add (inout_reachable, g_steal_pointer (&key));

        }

      else if (iterres == OSTREE_REPO_COMMIT_ITER_RESULT_DIR)

        {

          char *name;

          char *content_checksum;

          char *meta_checksum;

          ostree_repo_commit_traverse_iter_get_dir (iter, &name, &content_checksum,

                                                    &meta_checksum);

          g_debug ("Found dirtree object %s", content_checksum);

          g_debug ("Found dirmeta object %s", meta_checksum);

          key = g_variant_ref_sink (ostree_object_name_serialize (meta_checksum, OSTREE_OBJECT_TYPE_DIR_META));

          add_parent_ref (inout_parents, key, parent_key);

          g_hash_table_add (inout_reachable, g_steal_pointer (&key));

          key = g_variant_ref_sink (ostree_object_name_serialize (content_checksum, OSTREE_OBJECT_TYPE_DIR_TREE));

          add_parent_ref (inout_parents, key, parent_key);

          if (!g_hash_table_lookup (inout_reachable, key))

            {

              if (!traverse_dirtree (repo, content_checksum, key, inout_reachable, inout_parents,

                                     ignore_missing_dirs, cancellable, error))

                return FALSE;

              g_hash_table_add (inout_reachable, g_steal_pointer (&key));

            }

        }

      else

        g_assert_not_reached ();

    }

  return TRUE;

}

static gboolean

traverse_dirtree (OstreeRepo           *repo,

                  const char           *checksum,

                  GVariant             *parent_key,

                  GHashTable           *inout_reachable,

                  GHashTable           *inout_parents,

                  gboolean              ignore_missing_dirs,

                  GCancellable         *cancellable,

                  GError              **error)

{

  g_autoptr(GError) local_error = NULL;

  g_autoptr(GVariant) dirtree = NULL;

  if (!ostree_repo_load_variant (repo, OSTREE_OBJECT_TYPE_DIR_TREE, checksum,

                                 &dirtree, &local_error))

    {

      if (ignore_missing_dirs &&

          g_error_matches (local_error, G_IO_ERROR, G_IO_ERROR_NOT_FOUND))

        {

          g_debug ("Ignoring not-found dirmeta %s", checksum);

          return TRUE; /* Early return */

        }

      g_propagate_error (error, g_steal_pointer (&local_error));

      return FALSE;

    }

  g_debug ("Traversing dirtree %s", checksum);

  ostree_cleanup_repo_commit_traverse_iter

    OstreeRepoCommitTraverseIter iter = { 0, };

  if (!ostree_repo_commit_traverse_iter_init_dirtree (&iter, repo, dirtree,

                                                      OSTREE_REPO_COMMIT_TRAVERSE_FLAG_NONE,

                                                      error))

    return FALSE;

  if (!traverse_iter (repo, &iter, parent_key, inout_reachable, inout_parents, ignore_missing_dirs, cancellable, error))

    return FALSE;

  return TRUE;

}

/**

 * ostree_repo_traverse_commit_union_with_parents: (skip)

 * @repo: Repo

 * @commit_checksum: ASCII SHA256 checksum

 * @maxdepth: Traverse this many parent commits, -1 for unlimited

 * @inout_reachable: Set of reachable objects

 * @inout_parents: Map from object to parent object

 * @cancellable: Cancellable

 * @error: Error

 *

 * Update the set @inout_reachable containing all objects reachable

 * from @commit_checksum, traversing @maxdepth parent commits.

 *

 * Additionally this constructs a mapping from each object to the parents

 * of the object, which can be used to track which commits an object

 * belongs to.

 *

 * Since: 2018.5

 */

gboolean

ostree_repo_traverse_commit_union_with_parents (OstreeRepo      *repo,

                                                const char      *commit_checksum,

                                                int              maxdepth,

                                                GHashTable      *inout_reachable,

                                                GHashTable      *inout_parents,

                                                GCancellable    *cancellable,

                                                GError         **error)

{

  g_autofree char *tmp_checksum = NULL;

  while (TRUE)

    {

      g_autoptr(GVariant) key =

        g_variant_ref_sink (ostree_object_name_serialize (commit_checksum, OSTREE_OBJECT_TYPE_COMMIT));

      if (g_hash_table_contains (inout_reachable, key))

        break;

      g_autoptr(GVariant) commit = NULL;

      if (!ostree_repo_load_variant_if_exists (repo, OSTREE_OBJECT_TYPE_COMMIT,

                                               commit_checksum, &commit,

                                               error))

        return FALSE;

      /* Just return if the parent isn't found; we do expect most

       * people to have partial repositories.

       */

      if (!commit)

        break;

      /* See if the commit is partial, if so it's not an error to lack objects */

      OstreeRepoCommitState commitstate;

      if (!ostree_repo_load_commit (repo, commit_checksum, NULL, &commitstate,

                                    error))

        return FALSE;

      gboolean ignore_missing_dirs = FALSE;

      if ((commitstate & OSTREE_REPO_COMMIT_STATE_PARTIAL) != 0)

        ignore_missing_dirs = TRUE;

      g_hash_table_add (inout_reachable, g_variant_ref (key));

      g_debug ("Traversing commit %s", commit_checksum);

      ostree_cleanup_repo_commit_traverse_iter

        OstreeRepoCommitTraverseIter iter = { 0, };

      if (!ostree_repo_commit_traverse_iter_init_commit (&iter, repo, commit,

                                                         OSTREE_REPO_COMMIT_TRAVERSE_FLAG_NONE,

                                                         error))

        return FALSE;

      if (!traverse_iter (repo, &iter, key, inout_reachable, inout_parents, ignore_missing_dirs, cancellable, error))

        return FALSE;

      gboolean recurse = FALSE;

      if (maxdepth == -1 || maxdepth > 0)

        {

          g_free (tmp_checksum);

          tmp_checksum = ostree_commit_get_parent (commit);

          if (tmp_checksum)

            {

              commit_checksum = tmp_checksum;

              if (maxdepth > 0)

                maxdepth -= 1;

              recurse = TRUE;

            }

        }

      if (!recurse)

        break;

    }

  return TRUE;

}

/**

 * ostree_repo_traverse_commit_union: (skip)

 * @repo: Repo

 * @commit_checksum: ASCII SHA256 checksum

 * @maxdepth: Traverse this many parent commits, -1 for unlimited

 * @inout_reachable: Set of reachable objects

 * @cancellable: Cancellable

 * @error: Error

 *

 * Update the set @inout_reachable containing all objects reachable

 * from @commit_checksum, traversing @maxdepth parent commits.

 */

gboolean

ostree_repo_traverse_commit_union (OstreeRepo      *repo,

                                   const char      *commit_checksum,

                                   int              maxdepth,

                                   GHashTable      *inout_reachable,

                                   GCancellable    *cancellable,

                                   GError         **error)

{

  return

    ostree_repo_traverse_commit_union_with_parents (repo, commit_checksum, maxdepth,

                                                    inout_reachable, NULL,

                                                    cancellable, error);

}

/**

 * ostree_repo_traverse_commit:

 * @repo: Repo

 * @commit_checksum: ASCII SHA256 checksum

 * @maxdepth: Traverse this many parent commits, -1 for unlimited

 * @out_reachable: (out) (transfer container) (element-type GVariant GVariant): Set of reachable objects

 * @cancellable: Cancellable

 * @error: Error

 *

 * Create a new set @out_reachable containing all objects reachable

 * from @commit_checksum, traversing @maxdepth parent commits.

 */

gboolean

ostree_repo_traverse_commit (OstreeRepo      *repo,

                             const char      *commit_checksum,

                             int              maxdepth,

                             GHashTable     **out_reachable,

                             GCancellable    *cancellable,

                             GError         **error)

{

  g_autoptr(GHashTable) ret_reachable = ostree_repo_traverse_new_reachable ();

  if (!ostree_repo_traverse_commit_union (repo, commit_checksum, maxdepth,

                                          ret_reachable, cancellable, error))

    return FALSE;

  if (out_reachable)

    *out_reachable = g_steal_pointer (&ret_reachable);

  return TRUE;

}