/**

 * This file is part of the CernVM File System.

 */

#ifndef CVMFS_CATALOG_TRAVERSAL_H_

#define CVMFS_CATALOG_TRAVERSAL_H_

#include <cassert>

#include <limits>

#include <set>

#include <stack>

#include <string>

#include <vector>

#include "catalog.h"

#include "compression.h"

#include "history_sqlite.h"

#include "logging.h"

#include "manifest.h"

#include "object_fetcher.h"

#include "signature.h"

#include "util_concurrency.h"

namespace catalog {

class Catalog;

class WritableCatalog;

}

namespace swissknife {

/**

 * Callback data which has to be implemented by the registered callback

 * functions/methods (see Observable<> for further details)

 * @param catalog             the catalog object which needs to be processed

 * @param catalog_hash        the content hash of the catalog

 * @param tree_level          the depth in the nested catalog tree

 *                            (starting at zero)

 * @param file_size           the size of the downloaded catalog database file

 * @param history_depth       the distance from the current HEAD revision

 *                            (current HEAD has history_depth 0)

 */

template <class CatalogT>

struct CatalogTraversalData {

                       const shash::Any   &catalog_hash,

                       const unsigned      tree_level,

                       const size_t        file_size,

                       const unsigned int  history_depth)

  : catalog(catalog)

  , catalog_hash(catalog_hash)

  , tree_level(tree_level)

  , file_size(file_size)

  const CatalogT     *catalog;

  const shash::Any    catalog_hash;

  const unsigned int  tree_level;

  const size_t        file_size;

  const unsigned int  history_depth;

};

/**

 * A layer to extract information from a catalog.  Users of the catalog

 * traversal can provide derived classes to overwrite behavior.  Currently used

 * to get the last-modified timestamp in configurable manner: for the garbage

 * collection, the timestamp of the catalog hash in the reflog counts, which

 * is the same or newer than the one stored in the catalog.

 */

template <class CatalogT>

 public:

  // Default implementation: use the catalog's timestamp

  }

};

/**

 * This class traverses the catalog hierarchy of a CVMFS repository recursively.

 * Also historic catalog trees can be traversed. The user needs to specify a

 * callback which is called for each catalog on the way.

 *

 * CatalogTraversal<> can be configured and used in various ways:

 *   -> Historic catalog traversal

 *   -> Prune catalogs below a certain history level

 *   -> Prune catalogs older than a certain threshold timestamp

 *   -> Never traverse a certain catalog twice

 *   -> Breadth First Traversal or Depth First Traversal

 *   -> Optional catalog memory management (no_close)

 *   -> Use all Named Snapshots of a repository as traversal entry point

 *   -> Traverse starting from a provided catalog

 *   -> Traverse catalogs that were previously skipped

 *   -> Produce various flavours of catalogs (writable, mocked, ...)

 *

 * Breadth First Traversal Strategy

 *   Catalogs are handed out to the user identical as they are traversed.

 *   Say: From top to buttom. When you would simply print each received catalog

 *        the result would be a nice representation of the catalog tree.

 *   This method is more efficient, because catalogs are opened, processed and

 *   thrown away directly afterwards.

 *

 * Depth First Traversal Strategy

 *   The user gets the catalog tree starting from the leaf nodes.

 *   Say: From bottom to top. A user can assume that he got all children or

 *        historical ancestors of a catalog before.

 *   This method climbs down the full catalog tree and hands it out 'in reverse

 *   order'. Thus, catalogs on the way are opened, checked for their descendants

 *   and closed. Once all children and historical ancestors are processed, it is

 *   re-opened and handed out to the user.

 *   Note: This method needs more disk space to temporarily store downloaded but

 *         not yet processed catalogs.

 *

 * Note: Since all CVMFS catalog files together can grow to several gigabytes in

 *       file size, each catalog is loaded, processed and removed immediately

 *       afterwards. Except if no_close is specified, which allows the user to

 *       choose when a catalog should be closed. Keep in mind, that a user is

 *       responsible for both deletion of the delivered catalog objects as well

 *       as unlinking of the catalog database file.

 *

 *

 * @param ObjectFetcherT  Strategy Pattern implementation that defines how to

 *                        retrieve catalogs from various backend storage types.

 *                        Furthermore the ObjectFetcherT::CatalogTN is the type

 *                        of catalog to be instantiated by CatalogTraversal<>.

 *

 * CAUTION: the CatalogTN* pointer passed into the callback becomes invalid

 *          directly after the callback method returns, unless you create the

 *          CatalogTraversal object with no_close = true.

 */

template<class ObjectFetcherT>

class CatalogTraversal

  : public Observable<CatalogTraversalData<typename ObjectFetcherT::CatalogTN> >

 public:

  typedef ObjectFetcherT                      ObjectFetcherTN;

  typedef typename ObjectFetcherT::CatalogTN  CatalogTN;

  typedef typename ObjectFetcherT::HistoryTN  HistoryTN;

  typedef CatalogTraversalData<CatalogTN>     CallbackDataTN;

  /**

   * @param repo_url             the path to the repository to be traversed:

   *                             -> either absolute path to the local catalogs

   *                             -> or an URL to a remote repository

   * @param repo_name            fully qualified repository name (used for remote

   *                             repository signature check) (optional)

   * @param repo_keys            a comma separated list of public key file

   *                             locations to verify the repository manifest file

   * @param history              depth of the desired catalog history traversal

   *                             (default: 0 - only HEAD catalogs are traversed)

   * @param timestamp            timestamp of history traversal threshold

   *                             (default: 0 - no threshold, traverse everything)

   * @param no_repeat_history    keep track of visited catalogs and don't re-visit

   *                             them in previous revisions

   * @param no_close             do not close catalogs after they were attached

   *                             (catalogs retain their parent/child pointers)

   * @param ignore_load_failure  suppressed an error message if a catalog file

   *                             could not be loaded (i.e. was sweeped before by

   *                             a garbage collection run)

   * @param quiet                silence messages that would go to stderr

   * @param tmp_dir              path to the temporary directory to be used

   *                             (default: /tmp)

   */

  struct Parameters {

      : object_fetcher(NULL)

      , history(kNoHistory)

      , timestamp(kNoTimestampThreshold)

      , no_repeat_history(false)

      , no_close(false)

      , ignore_load_failure(false)

    static const unsigned int kFullHistory;

    static const unsigned int kNoHistory;

    static const time_t       kNoTimestampThreshold;

    ObjectFetcherT *object_fetcher;

    unsigned int    history;

    time_t          timestamp;

    bool            no_repeat_history;

    bool            no_close;

    bool            ignore_load_failure;

    bool            quiet;

  };

 public:

  enum TraversalType {

    kBreadthFirstTraversal,

    kDepthFirstTraversal

  };

 protected:

  typedef std::set<shash::Any> HashSet;

 protected:

  /**

   * This struct keeps information about a catalog that still needs to be

   * traversed by a currently running catalog traversal process.

   */

               const shash::Any   &hash,

               const unsigned      tree_level,

               const unsigned      history_depth,

                     CatalogTN    *parent = NULL) :

      path(path),

      hash(hash),

      tree_level(tree_level),

      history_depth(history_depth),

      parent(parent),

      catalog_file_size(0),

      ignore(false),

      catalog(NULL),

      referenced_catalogs(0),

      return CallbackDataTN(catalog, hash, tree_level,

    }

    // initial state description

    const std::string   path;

    const shash::Any    hash;

    const unsigned      tree_level;

    const unsigned      history_depth;

          CatalogTN    *parent;

    // dynamic processing state (used internally)

    std::string   catalog_file_path;

    size_t        catalog_file_size;

    bool          ignore;

    CatalogTN    *catalog;

    unsigned int  referenced_catalogs;

    bool          postponed;

  };

  typedef std::stack<CatalogJob> CatalogJobStack;

  /**

   * This struct represents a catalog traversal context. It needs to be re-

   * created for each catalog traversal process and contains information to this

   * specific catalog traversal run.

   *

   * @param history_depth   the history traversal threshold

   * @param traversal_type  either breadth or depth first traversal strategy

   * @param catalog_stack   the call stack for catalogs to be traversed

   * @param callback_stack  used in depth first traversal for deferred yielding

   */

                     const time_t         timestamp_threshold,

                     const TraversalType  traversal_type) :

      history_depth(history_depth),

      timestamp_threshold(timestamp_threshold),

    const unsigned       history_depth;

    const time_t         timestamp_threshold;

    const TraversalType  traversal_type;

    CatalogJobStack      catalog_stack;

    CatalogJobStack      callback_stack;

  };

 public:

  /**

   * Constructs a new catalog traversal engine based on the construction

   * parameters described in struct ConstructionParams.

   */

    : object_fetcher_(params.object_fetcher)

    , catalog_info_shim_(&catalog_info_default_shim_)

    , no_close_(params.no_close)

    , ignore_load_failure_(params.ignore_load_failure)

    , no_repeat_history_(params.no_repeat_history)

    , default_history_depth_(params.history)

    , default_timestamp_threshold_(params.timestamp)

  {

  /**

   * Starts the traversal process.

   * After calling this methods CatalogTraversal will go through all catalogs

   * and call the registered callback methods for each found catalog.

   * If something goes wrong in the process, the traversal will be cancelled.

   *

   * @param type   breadths or depth first traversal

   * @return       true, when all catalogs were successfully processed. On

   *               failure the traversal is cancelled and false is returned.

   */

    TraversalContext ctx(default_history_depth_,

                         default_timestamp_threshold_,

    }

  }

  /**

   * Starts the traversal process at the catalog pointed to by the given hash

   *

   * @param root_catalog_hash  the entry point into the catalog traversal

   * @param type               breadths or depth first traversal

   * @return                   true when catalogs were successfully traversed

   */

                const TraversalType   type = kBreadthFirstTraversal) {

    // add the root catalog of the repository as the first element on the job

    // stack

    TraversalContext ctx(default_history_depth_,

                         default_timestamp_threshold_,

  }

  /**

   * Starts the traversal process at the catalog pointed to by the given hash

   * but doesn't traverse into predecessor catalog revisions. This overrides the

   * TraversalParameter settings provided at construction.

   *

   * @param root_catalog_hash  the entry point into the catalog traversal

   * @param type               breadths or depth first traversal

   * @return                   true when catalogs were successfully traversed

   */

                        const TraversalType   type = kBreadthFirstTraversal) {

    // add the given root catalog as the first element on the job stack

    TraversalContext ctx(Parameters::kNoHistory,

                         Parameters::kNoTimestampThreshold,

  }

  /**

   * Figures out all named tags in a repository and uses all of them as entry

   * points into the traversal process.

   *

   * @param type  breadths or depth first traversal

   * @return      true when catalog traversal successfully finished

   */

    const TraversalType type = kBreadthFirstTraversal)

  {

    typedef std::vector<shash::Any> HashList;

    TraversalContext ctx(Parameters::kNoHistory,

                         Parameters::kNoTimestampThreshold,

    const typename ObjectFetcherT::Failures retval =

      case ObjectFetcherT::kFailOk:

      case ObjectFetcherT::kFailNotFound:

                 "didn't find a history database to traverse");

      default:

                 "failed to download history database (%d - %s)",

                 retval, Code2Ascii(retval));

    }

    // traversing referenced named root hashes in reverse chronological order

    // to make sure that overlapping history traversals don't leave out catalog

    // revisions accidentially

    }

  }

 protected:

  /**

   * This controls the actual traversal. Using a stack to traverse down the

   * catalog hierarchy. This method implements the traversal itself, but not

   * in which way catalogs are handed out to the user code.

   *

   * Each catalog is processed in these steps:

   *  1.) Pop the next catalog from the stack

   *        Catalogs are always traversed from latest to oldest revision and

   *        from root to leaf nested catalogs

   *  2.) Prepare the catalog for traversing

   *    2.1.) Check if it was visited before

   *    2.2.) Fetch the catalog database from the backend storage

   *            This might fail and produce an error. For root catalogs this

   *            error can be ignored (might be garbage collected before)

   *    2.3.) Open the catalog database

   *    2.4.) Check if the catalog is older than the timestamp threshold

   *        After these steps the catalog is opened either opened and ready for

   *        the traversal to continue, or it was marked for ignore (job.ignore)

   *  3.) Check if the catalog is marked to be ignored

   *        Catalog might not be loadable (sweeped root catalog) or is too old

   *        Note: ignored catalogs can still trigger postponed yields

   *  4.) Mark the catalog as visited to be able to skip it later on

   *  5.) Find and push referencing catalogs

   *        This pushes all descendents of the current catalog onto the stack.

   *        Note that this is dependent on the strategy (depth or breadth first)

   *        and on the history threshold (see history_depth).

   *  6.) Hand the catalog out to the user code

   *        Depending on the traversal strategy (depth of breadths first) this

   *        might immediately yield zero to N catalogs to the user code.

   *

   * Note: If anything unexpected goes wrong during the traversal process, it

   *       is aborted immediately.

   *

   * @param ctx   the traversal context that steers the whole traversal process

   * @return      true on successful traversal and false on abort

   */

      // Get the top most catalog for the next processing step

      // download and open the catalog for processing

      }

      // ignored catalogs don't need to be processed anymore but they might

      // release postponed yields

        }

      }

      // push catalogs referenced by the current catalog (onto stack)

      // notify listeners

      }

    }

    // invariant: after the traversal finshed, there should be no more catalogs

    //            to traverse or to yield!

  }

    // skipping duplicate catalogs might also yield postponed catalogs

    }

    const typename ObjectFetcherT::Failures retval =

      object_fetcher_->FetchCatalog(job->hash,

                                    job->path,

                                    &job->catalog,

                                    !job->IsRootCatalog(),

      case ObjectFetcherT::kFailOk:

      case ObjectFetcherT::kFailNotFound:

                                                    "%s (swept before?)",

                   job->hash.ToString().c_str());

        }

      default:

                                                    "(%d - %s)",

                 job->hash.ToStringWithSuffix().c_str(),

                 retval, Code2Ascii(retval));

    }

    // catalogs returned by ObjectFetcher<> are managing their database files by

    // default... we need to manage this file manually here

  }

                                           job->catalog_file_path,

                                           job->hash,

                                           job->parent,

                                           !job->IsRootCatalog());

               "failed to re-open catalog %s", job->hash.ToString().c_str());

    }

  }

                 job->catalog_file_path.c_str(), errno);

      }

    }

  }

  /**

   * Checks if a root catalog is below one of the pruning thresholds.

   * Pruning thesholds can be either the catalog's history depth or a timestamp

   * threshold applied to the last modified timestamp of the catalog.

   *

   * @param ctx  traversal context for traversal-specific state

   * @param job  the job defining the current catalog

   * @return     true if either history or timestamp threshold are satisfied

   */

    const CatalogJob &job,

    const TraversalContext &ctx

  ) {

    const bool t =

      catalog_info_shim_->GetLastModified(job.catalog) <

  }

           ctx->traversal_type == kDepthFirstTraversal);

    // this differs, depending on the traversal strategy.

    //

    // Breadths First Traversal

    //   Catalogs are traversed from top (root catalog) to bottom (leaf

    //   catalogs) and from more recent (HEAD revision) to older (historic

    //   revisions)

    //

    // Depth First Traversal

    //   Catalogs are traversed from oldest revision (depends on the configured

    //   maximal history depth) to the HEAD revision and from bottom (leafs) to

    //   top (root catalogs)

      ? PushPreviousRevision(*job, ctx) + PushNestedCatalogs(*job, ctx)

      : PushNestedCatalogs(*job, ctx) + PushPreviousRevision(*job, ctx);

  /**

   * Pushes the previous revision of a (root) catalog.

   * @return  the number of catalogs pushed on the processing stack

   */

    const CatalogJob &job,

    TraversalContext *ctx

  ) {

    // only root catalogs are used for entering a previous revision (graph)

    }

    }

    // check if the next deeper history level is actually requested

    // Note: if the current catalog is below the timestamp threshold it will be

    //       traversed and only its ancestor revision will not be pushed anymore

    }

         ctx);

  }

  /**

   * Pushes all the referenced nested catalogs.

   * @return  the number of catalogs pushed on the processing stack

   */

    const CatalogJob &job,

    TraversalContext *ctx

  ) {

    typedef typename CatalogTN::NestedCatalogList NestedCatalogList;

      const CatalogJob new_job(i->mountpoint.ToString(),

                               i->hash,

                               job.tree_level + 1,

                               job.history_depth,

    }

  }

           ctx->traversal_type == kDepthFirstTraversal);

    // in breadth first search mode, every catalog is simply handed out once

    // it is visited. No extra magic required...

    }

    // in depth first search mode, catalogs might need to wait until all of

    // their referenced catalogs are yielded (ctx.callback_stack)...

    }

    // this catalog can be yielded

  }

 private:

  /**

   * This actually hands out a catalog to the user code

   * It is not called by DoTraversa() directly but by wrapper functions in order

   * to provide higher level yielding behaviour.

   */

    // catalog was pushed on ctx.callback_stack before, it might need to be re-

    // opened. If CatalogTraversal<> is configured with no_close, it was not

    // closed before, hence does not need a re-open.

    }

    // hand the catalog out to the user code (see Observable<>)

    // skip the catalog closing procedure if asked for

    // Note: In this case it is the user's responsibility to both delete the

    //       yielded catalog object and the underlying database temp file

    }

    // we can close the catalog here and delete the temporary file

  }

  /**

   * Pushes a catalog to the callback_stack for later yielding

   * Note: this is only used for the Depth First Traversal strategy!

   */

    }

  /**

   * Determines if there are postponed yields that can be set free based on

   * the catalog currently being yielded

   *

   * Note: the CatalogJob being handed into this method does not necessarily

   *       have an open Catalog attached to it.

   *

   * @param ctx   the TraversalContext

   * @param job   the catalog job that was just yielded

   * @return      true on successful execution

   */

    }

    // walk through the callback_stack and yield all catalogs that have no un-

    // yielded referenced_catalogs anymore. Every time a CatalogJob in the

    // callback_stack gets yielded it decrements the referenced_catalogs of the

    // next top of the stack (it's parent CatalogJob waiting for yielding)

      }

      }

    }

  }

  }

    }

  /**

   * Checks the traversal history if the given catalog was traversed or at least

   * seen before. If 'no_repeat_history' is not set this is always 'false'.

   *

   * @param job   the job to be checked against the traversal history

   * @return      true if the specified catalog was hit before

   */

  }

    // get the manifest of the repository to learn about the entry point or the

    // root catalog of the repository to be traversed

    const typename ObjectFetcherT::Failures retval =

                                                 "(%d - %s)",

                                                 retval, Code2Ascii(retval));

    }

  }

 private:

  ObjectFetcherT         *object_fetcher_;

  CatalogTraversalInfoShim<CatalogTN> catalog_info_default_shim_;

  CatalogTraversalInfoShim<CatalogTN> *catalog_info_shim_;

  const bool              no_close_;

  const bool              ignore_load_failure_;

  const bool              no_repeat_history_;

  const unsigned int      default_history_depth_;

  const time_t            default_timestamp_threshold_;

  HashSet                 visited_catalogs_;

  LogFacilities           error_sink_;

};

template <class ObjectFetcherT>

const unsigned int

    std::numeric_limits<unsigned int>::max();

template <class ObjectFetcherT>

const unsigned int

  CatalogTraversal<ObjectFetcherT>::Parameters::kNoHistory = 0;

template <class ObjectFetcherT>

const time_t

  CatalogTraversal<ObjectFetcherT>::Parameters::kNoTimestampThreshold = 0;

}  // namespace swissknife

#endif  // CVMFS_CATALOG_TRAVERSAL_H_