// file      : build/utility -*- C++ -*-
// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
// license   : MIT; see accompanying LICENSE file

#ifndef BUILD_UTILITY
#define BUILD_UTILITY

#include <tuple>
#include <limits> // numeric_limits
#include <string>
#include <vector>
#include <utility>
#include <cstring> // strcmp()
#include <cassert>
#include <exception>
#include <unordered_set>
#include <unordered_map>

#include <build/key-set>
#include <build/path>

namespace build
{
  // Empty string and path.
  //
  extern const std::string empty_string;
  extern const path empty_path;

  // Comparators.
  //
  struct compare_c_string
  {
    bool operator() (const char* x, const char* y) const
    {
      return std::strcmp (x, y) < 0;
    }
  };

  struct compare_pointer_target
  {
    template <typename P>
    bool operator() (const P& x, const P& y) const {return *x < *y;}
  };

  // Support for reverse iteration using range-based for-loop:
  //
  // for (... : reverse_iterate (x)) ...
  //
  template <typename T>
  class reverse_range
  {
    T& x_;

  public:
    reverse_range (T& x): x_ (x) {}

    auto begin () const -> decltype (this->x_.rbegin ())
    {
      return x_.rbegin ();
    }

    auto end () const -> decltype (this->x_.rend ())
    {
      return x_.rend ();
    }
  };

  template <typename T>
  inline reverse_range<T>
  reverse_iterate (T& x)
  {
    return reverse_range<T> (x);
  }

  // Call a function if there is an exception.
  //

  // Means we are in the body of a destructor that is being called
  // as part of the exception stack unwindining. Used to compensate
  // for the deficiencies of uncaught_exception() until C++17
  // uncaught_exceptions() becomes available.
  //
  // @@ MT: will have to be TLS.
  //
  extern bool exception_unwinding_dtor;

  template <typename F, typename T>
  struct exception_guard;

  template <typename F, typename... A>
  inline exception_guard<F, std::tuple<A&&...>>
  make_exception_guard (F f, A&&... a)
  {
    return exception_guard<F, std::tuple<A&&...>> (
      std::move (f), std::forward_as_tuple (a...));
  }

  template <typename F, typename... A>
  struct exception_guard<F, std::tuple<A...>>
  {
    typedef std::tuple<A...> T;

    exception_guard (F f, T a): f_ (std::move (f)), a_ (std::move (a)) {}
    ~exception_guard ()
    {
      if (std::uncaught_exception ())
      {
        exception_unwinding_dtor = true;
        call (std::index_sequence_for<A...> ());
        exception_unwinding_dtor = false;
      }
    }

  private:
    template <std::size_t... I>
    void
    call (std::index_sequence<I...>) {f_ (std::get<I> (a_)...);}

    F f_;
    T a_;
  };

  // Pools (@@ perhaps move into a separate header).
  //
  struct string_pool: std::unordered_set<std::string>
  {
    const std::string&
    find (const char* s) {return *emplace (s).first;}
  };

  extern string_pool extension_pool;

  // A pool of strings and, optionally, other accompanying data in which
  // each entry is assigned an individual index (or id) of type I (e.g.,
  // uint8_t, uint16_t, etc., depending on how many entries are expected).
  // Index value 0 is reserved to indicate the no entry condition.
  //
  template <typename I, typename D>
  struct string_table_element
  {
    const I i;
    const D d;
  };

  template <typename I>
  struct string_table_element<I, std::string>
  {
    const I i;
    const std::string d;
  };

  template <typename D>
  struct string_table_traits
  {
    // By default, look for the key() function in D. But you can
    // also specialize this class template.
    //
    static const std::string&
    key (const D& d) {return d.key ();}
  };

  template <>
  struct string_table_traits<std::string>
  {
    static const std::string&
    key (const std::string& d) {return d;}
  };

  template <typename I, typename D = std::string>
  struct string_table
  {
    // Insert new entry unless one already exists.
    //
    I
    insert (const D& d)
    {
      std::size_t i (vec_.size () + 1);

      // Note: move(d) would be tricky since key still points to it.
      //
      auto r (map_.emplace (
                key_type (&traits::key (d)),
                value_type {static_cast<I> (i), d}));

      if (r.second)
      {
        assert (i <= std::numeric_limits<I>::max ());

        r.first->first.p = &traits::key (r.first->second.d); // Update key.
        vec_.push_back (r.first);
      }

      return r.first->second.i;
    }

    // Find existing.
    //
    I
    find (const std::string& k) const
    {
      auto i (map_.find (key_type (&k)));
      return i != map_.end () ? i->second.i : 0;
    }

    // Reverse lookup.
    //
    const D&
    operator[] (I i) const {assert (i > 0); return vec_[i - 1]->second.d;}

    I
    size () const {return static_cast<I> (vec_.size ());}

  private:
    using key_type = set_key<std::string>;
    using value_type = string_table_element<I, D>;
    using map_type = std::unordered_map<key_type, value_type>;
    using traits = string_table_traits<D>;

    map_type map_;
    std::vector<typename map_type::const_iterator> vec_;
  };
}

#endif // BUILD_UTILITY