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

#ifndef BUILD_TARGET
#define BUILD_TARGET

#include <map>
#include <string>
#include <vector>
#include <memory>      // unique_ptr
#include <cstddef>     // size_t
#include <functional>  // function, reference_wrapper
#include <ostream>
#include <cassert>
#include <utility>     // move(), forward(), declval()
#include <iterator>
#include <type_traits>

#include <butl/utility>     // compare_c_string, reverse_iterate()
#include <butl/multi-index> // map_iterator_adapter

#include <build/types>
#include <build/variable>
#include <build/operation>
#include <build/target-key>
#include <build/prerequisite>

namespace build
{
  class scope;
  class target;

  target&
  search (prerequisite&); // From <build/algorithm>.

  // Target state.
  //
  enum class target_state
  {
    group,           // Target's state is the group's state.
    unknown,
    postponed,
    unchanged,
    changed,
    failed
  };

  std::ostream&
  operator<< (std::ostream&, target_state);

  // Recipe.
  //
  // The returned target state should be changed, unchanged, or
  // postponed. If there is an error, then the recipe should throw
  // rather than returning failed.
  //
  // The recipe execution protocol is as follows: before executing
  // the recipe, the caller sets the target's state to failed. If
  // the recipe returns normally and the target's state is still
  // failed, then the caller sets it to the returned value. This
  // means that the recipe can set the target's state manually to
  // some other value. For example, setting it to unknown will
  // result in the recipe to be executed again if this target is a
  // prerequisite of another target. Note that in this case the
  // returned by the recipe value is still used (by the caller) as
  // the resulting target state for this execution of the recipe.
  // Returning postponed from the last call to the recipe means
  // that the action could not be executed at this time (see fsdir
  // clean for an example).
  //
  using recipe_function = target_state (action, target&);
  using recipe = std::function<recipe_function>;

  // Commonly-used recipes. The default recipe executes the action
  // on all the prerequisites in a loop, skipping ignored. Specially,
  // for actions with the "first" execution mode, it calls
  // execute_prerequisites() while for those with the "last" mode --
  // reverse_execute_prerequisites(); see <build/operation>,
  // <build/algorithm> for details. The group recipe calls the group's
  // recipe.
  //
  extern const recipe empty_recipe;
  extern const recipe noop_recipe;
  extern const recipe default_recipe;
  extern const recipe group_recipe;

  target_state
  noop_action (action, target&); // Defined in <build/algorithm>.

  target_state
  group_action (action, target&); // Defined in <build/algorithm>.

  // Prerequisite references as used in the target::prerequisites list
  // below.
  //
  struct prerequisite_ref: std::reference_wrapper<prerequisite>
  {
    typedef std::reference_wrapper<prerequisite> base;

    using base::base;

    // Return true if this reference belongs to the target's prerequisite
    // list. Note that this test only works if you use references to
    // the container elements and the container hasn't been resized
    // since such a reference was obtained. Normally this function is
    // used when iterating over a combined prerequisites range (see
    // group_prerequisites below).
    //
    bool
    belongs (const target&) const;
  };

  // A view of target group members.
  //
  struct group_view
  {
    target* const* members; // NULL means not yet known.
    std::size_t count;
  };

  // Target.
  //
  class target
  {
  public:
    virtual
    ~target () = default;

    target (const target&) = delete;
    target& operator= (const target&) = delete;

    target (dir_path d, std::string n, const std::string* e)
        : dir (std::move (d)), name (std::move (n)), ext (e) {}

    const dir_path dir;      // Absolute and normalized.
    const std::string name;
    const std::string* ext;  // Extension, NULL means unspecified,
                             // empty means no extension.

    // Target group to which this target belongs, if any. Note that
    // we assume that the group and all its members are in the same
    // scope (for example, in variable lookup). We also don't support
    // nested groups.
    //
    // The semantics of the interaction between the group and its
    // members and what it means to, say, update the group, is
    // unspecified and determined by the group's type. In particular,
    // a group can be created out of member types that have no idea
    // they are part of this group (e.g., cli.cxx{}).
    //
    // Normally, however, there are two kinds of groups: "alternatives"
    // and "combination". In an alternatives group, normally one of the
    // members is selected when the group is mentioned as a prerequisite
    // with, perhaps, an exception for special rules, like aliases, where
    // it makes more sense to treat the group as a whole. In this case we
    // say that the rule "semantically recognizes" the group and picks
    // some of its members.
    //
    // Updating an alternative group as a whole can mean updating some
    // subset of its members (e.g., lib{}). Or the group may not support
    // this at all (e.g., obj{}).
    //
    // In a combination group, when a group is updated, normally all
    // members are updates (and usually with a single command), though
    // there could be some members that are omitted, depending on the
    // configuration (e.g., an inline file not/being generated). When
    // a combination group is mentioned as a prerequisite, the rule
    // is usually interested in the individual members rather than
    // the whole group. For example, a C++ compile rule would like to
    // "see" the ?xx{} members when it gets a cli.cxx{} group.
    //
    // Which brings us to the group iteration mode. The target type
    // contains a member called see_through that indicates whether the
    // default iteration mode for the group should be "see through";
    // that is, whether we see the members or the group itself. For
    // the iteration support itself, see the *_prerequisite_members()
    // machinery below.
    //
    target* group {nullptr};

    // You should not call this function directly; rather use
    // resolve_group_members() from <build/algorithm>.
    //
    virtual group_view
    group_members (action) const;

    target_key
    key () const {return target_key {&type (), &dir, &name, &ext};}

   public:
    // Most qualified scope that contains this target.
    //
    scope&
    base_scope () const;

    // Root scope of a project that contains this target. Note that
    // a target can be out of any (known) project root in which case
    // this function asserts. If you need to detect this situation,
    // then use base_scope().root_scope() expression instead.
    //
    scope&
    root_scope () const;

    // Prerequisites.
    //
  public:
    typedef std::vector<prerequisite_ref> prerequisites_type;
    prerequisites_type prerequisites;

    // Targets to which prerequisites resolve for this recipe. Note
    // that unlike prerequisite::target, these can be resolved to
    // group members. NULL means the target should be skipped (or
    // the rule may simply not add such a target to the list).
    //
    // Note also that it is possible the target can vary from
    // action to action, just like recipes. We don't need to keep
    // track of the action here since the targets will be updated
    // if the recipe is updated, normally as part of rule::apply().
    //
    typedef std::vector<target*> prerequisite_targets_type;
    prerequisite_targets_type prerequisite_targets;

    // Check if there are any prerequisites, taking into account
    // group prerequisites.
    //
    bool
    has_prerequisites () const
    {
      return !prerequisites.empty () ||
        (group != nullptr && !group->prerequisites.empty ());
    }

    // Target-specific variables.
    //
  public:
    variable_map vars;

    // Lookup, including in groups to which this target belongs and
    // then in outer scopes. If you only want to lookup in this target,
    // do it on the the variables map directly.
    //
    value_proxy
    operator[] (const variable&) const;

    value_proxy
    operator[] (const std::string& name) const
    {
      return operator[] (variable_pool.find (name));
    }

    // Return a value_proxy suitable for assignment. See class scope
    // for details.
    //
    value_proxy
    assign (const variable& var)
    {
      return vars.assign (var);
    }

    value_proxy
    assign (const std::string& name)
    {
      return assign (variable_pool.find (name));
    }

    // Return a value_proxy suitable for appending. See class scope
    // for details.
    //
    value_proxy
    append (const variable&);

    value_proxy
    append (const std::string& name)
    {
      return append (variable_pool.find (name));
    }

  public:
    target_state raw_state;

    target_state
    state () const
    {
      return raw_state != target_state::group ? raw_state : group->raw_state;
    }

    // Number of direct targets that depend on this target in the current
    // action. It is incremented during the match phase and then decremented
    // during execution, before running the recipe. As a result, the recipe
    // can detect the last chance (i.e., last dependent) to execute the
    // command (see also the first/last execution modes in <operation>).
    //
    // Note that setting a new recipe (which happens when we match the rule
    // and which in turn is triggered by the first dependent) clears this
    // counter. However, if the previous action was the same as the current,
    // then the existing recipe is reused. In this case, however, the counter
    // should have been decremented to 0 naturally, as part of the previous
    // action execution.
    //
    std::size_t dependents;

  public:
    typedef build::recipe recipe_type;

    const recipe_type&
    recipe (action_id a) const {return action_ == a ? recipe_ : empty_recipe;}

    void
    recipe (action_id a, recipe_type r)
    {
      assert (action_ != a || !recipe_);
      action_ = a;
      recipe_ = std::move (r);

      // Also reset the target state. If this is a noop recipe, then
      // mark the target unchanged so that we don't waste time executing
      // the recipe. If this is a group recipe, then mark the state as
      // coming from the group.
      //
      raw_state = target_state::unknown;

      if (recipe_function** f = recipe_.target<recipe_function*> ())
      {
        if (*f == &noop_action)
          raw_state = target_state::unchanged;
        else if (*f == &group_action)
          raw_state = target_state::group;
      }

      dependents = 0;
    }

    // Target type info.
    //
  public:
    template <typename T>
    T*
    is_a () {return dynamic_cast<T*> (this);}

    template <typename T>
    const T*
    is_a () const {return dynamic_cast<const T*> (this);}

    virtual const target_type& type () const = 0;
    static const target_type static_type;

  private:
    action_id action_ {0}; // Action id of this recipe.
    recipe_type recipe_;
  };

  std::ostream&
  operator<< (std::ostream&, const target&);

  // A "range" that presents the prerequisites of a group and one of
  // its members as one continuous sequence, or, in other words, as
  // if they were in a single container. The group's prerequisites
  // come first followed by the member's. If you need to see them
  // in the other direction, iterate in reverse, for example:
  //
  // for (prerequisite_ref& pr: group_prerequisites (t))
  //
  // for (prerequisite_ref& pr: reverse_iterate (group_prerequisites (t))
  //
  // Note that in this case the individual elements of each list will
  // also be traversed in reverse, but that's what you usually want,
  // anyway.
  //
  class group_prerequisites
  {
  public:
    typedef target::prerequisites_type prerequisites_type;

    explicit
    group_prerequisites (target& t): t_ (t) {}

    struct iterator
    {
      typedef prerequisites_type::iterator base_iterator;

      typedef base_iterator::value_type value_type;
      typedef base_iterator::pointer pointer;
      typedef base_iterator::reference reference;
      typedef base_iterator::difference_type difference_type;
      typedef std::bidirectional_iterator_tag iterator_category;

      iterator () {}
      iterator (target* t, prerequisites_type* c, base_iterator i)
          : t_ (t), c_ (c), i_ (i) {}

      iterator&
      operator++ ()
      {
        if (++i_ == c_->end () && c_ != &t_->prerequisites)
        {
          c_ = &t_->prerequisites;
          i_ = c_->begin ();
        }
        return *this;
      }

      iterator
      operator++ (int) {iterator r (*this); return ++r;}

      iterator&
      operator-- ()
      {
        if (i_ == c_->begin () && c_ == &t_->prerequisites)
        {
          c_ = &t_->group->prerequisites;
          i_ = c_->end ();
        }

        --i_;
        return *this;
      }

      iterator
      operator-- (int) {iterator r (*this); return --r;}

      reference operator* () const {return *i_;}
      pointer operator-> () const {return i_.operator -> ();}

      friend bool
      operator== (const iterator& x, const iterator& y)
      {
        return x.t_ == y.t_ && x.c_ == y.c_ && x.i_ == y.i_;
      }

      friend bool
      operator!= (const iterator& x, const iterator& y) {return !(x == y);}

    private:
      target* t_ {nullptr};
      prerequisites_type* c_ {nullptr};
      base_iterator i_;
    };

    typedef std::reverse_iterator<iterator> reverse_iterator;

    iterator
    begin () const
    {
      auto& c ((t_.group != nullptr && !t_.group->prerequisites.empty ()
                ? *t_.group : t_).prerequisites);
      return iterator (&t_, &c, c.begin ());
    }

    iterator
    end () const
    {
      auto& c (t_.prerequisites);
      return iterator (&t_, &c, c.end ());
    }

    reverse_iterator
    rbegin () const {return reverse_iterator (end ());}

    reverse_iterator
    rend () const {return reverse_iterator (begin ());}

    std::size_t
    size () const
    {
      return t_.prerequisites.size () +
        (t_.group != nullptr ? t_.group->prerequisites.size () : 0);
    }

  private:
    target& t_;
  };

  // A member of a prerequisite. If 'target' is NULL, then this is the
  // prerequisite itself. Otherwise, it is its member. In this case
  // 'prerequisite' still refers to the prerequisite.
  //
  struct prerequisite_member
  {
    typedef build::target target_type;
    typedef build::prerequisite prerequisite_type;

    prerequisite_ref& prerequisite;
    target_type* target;

    template <typename T>
    bool
    is_a () const
    {
      return target != nullptr
        ? target->is_a<T> () != nullptr
        : prerequisite.get ().is_a<T> ();
    }

    prerequisite_key
    key () const
    {
      return target != nullptr
        ? prerequisite_key {target->key (), nullptr}
        : prerequisite.get ().key ();
    }

    const build::target_type&
    type () const
    {
      return target != nullptr ? target->type () : prerequisite.get ().type;
    }

    const std::string&
    name () const
    {
      return target != nullptr ? target->name : prerequisite.get ().name;
    }

    target_type&
    search () const
    {
      return target != nullptr ? *target : build::search (prerequisite);
    }

    prerequisite_type&
    as_prerequisite (tracer&) const;
  };

  inline std::ostream&
  operator<< (std::ostream& os, const prerequisite_member& pm)
  {
    return os << pm.key ();
  }

  // A "range" that presents a sequence of prerequisites (e.g., from
  // group_prerequisites()) as a sequence of prerequisite_member's. For
  // each group prerequisite you will "see" either the prerequisite
  // itself or all its members, depending on the default iteration
  // mode of the target group type. You can skip the rest of the
  // group members with leave_group() and you can force iteration
  // over the members with enter_group(). Usage:
  //
  // for (prerequisite_member pm: prerequisite_members (a, ...))
  //
  // Where ... can be:
  //
  //   t.prerequisites
  //   reverse_iterate(t.prerequisites)
  //   group_prerequisites (t)
  //   reverse_iterate (group_prerequisites (t))
  //
  // But use shortcuts instead:
  //
  // prerequisite_members (a, t)
  // reverse_prerequisite_members (a, t)
  // group_prerequisite_members (a, t)
  // reverse_group_prerequisite_members (a, t)
  //
  template <typename T>
  class prerequisite_members_range;

  template <typename T>
  inline prerequisite_members_range<T>
  prerequisite_members (action a, T&& x)
  {
    return prerequisite_members_range<T> (a, std::forward<T> (x));
  }

  template <typename T>
  class prerequisite_members_range
  {
  public:
    prerequisite_members_range (action a, T&& r)
        : a_ (a), r_ (std::forward<T> (r)), e_ (r_.end ()) {}

    using base_iterator = decltype (std::declval<T> ().begin ());

    struct iterator
    {
      typedef prerequisite_member value_type;
      typedef const value_type* pointer;
      typedef const value_type& reference;
      typedef typename base_iterator::difference_type difference_type;
      typedef std::forward_iterator_tag iterator_category;

      iterator (): r_ (nullptr) {}
      iterator (const prerequisite_members_range* r, const base_iterator& i)
          : r_ (r), i_ (i), g_ {nullptr, 0}
      {
        if (i_ != r_->e_ && i_->get ().type.see_through)
          switch_members ();
      }

      iterator& operator++ ();
      iterator  operator++ (int) {iterator r (*this); return ++r;}

      // Skip iterating over the rest of this group's members, if any.
      // Note that the only valid operation after this call is to
      // increment the iterator.
      //
      void
      leave_group ()
      {
        // Pretend we are on the last member of some group.
        //
        j_ = 0;
        g_.count = 1;
      }

      // Iterate over this group's members. Similar to leave_group(),
      // you should increment the iterator after calling this function.
      //
      void
      enter_group ()
      {
        switch_members ();
        --j_; // Compensate for the increment that will follow.
      }

      value_type operator* () const
      {
        return value_type {*i_, g_.count != 0 ? g_.members[j_ - 1] : nullptr};
      }

      pointer operator-> () const
      {
        static_assert (
          std::is_trivially_destructible<prerequisite_member>::value,
          "prerequisite_member is not trivially destructible");

        return new (&m_)
          value_type {*i_, g_.count != 0 ? g_.members[j_ - 1] : nullptr};
      }

      friend bool
      operator== (const iterator& x, const iterator& y)
      {
        return x.i_ == y.i_ &&
          x.g_.count == y.g_.count &&
          (x.g_.count == 0 || x.j_ == y.j_);
      }

      friend bool
      operator!= (const iterator& x, const iterator& y) {return !(x == y);}

    private:
      void
      switch_members ();

    private:
      const prerequisite_members_range* r_;
      base_iterator i_;
      group_view g_;
      std::size_t j_; // 1-based index, to support enter_group().
      mutable std::aligned_storage<sizeof (prerequisite_member),
                                   alignof (prerequisite_member)>::type m_;
    };

    iterator
    begin () const {return iterator (this, r_.begin ());}

    iterator
    end () const {return iterator (this, e_);}

  private:
    action a_;
    T r_;
    base_iterator e_;
  };

  // prerequisite_members(t.prerequisites)
  //
  inline auto
  prerequisite_members (action a, target& t)
  {
    return prerequisite_members (a, t.prerequisites);
  }

  // prerequisite_members(reverse_iterate(t.prerequisites))
  //
  inline auto
  reverse_prerequisite_members (action a, target& t)
  {
    return prerequisite_members (a, butl::reverse_iterate (t.prerequisites));
  }

  // prerequisite_members(group_prerequisites (t))
  //
  inline auto
  group_prerequisite_members (action a, target& t)
  {
    return prerequisite_members (a, group_prerequisites (t));
  }

  // prerequisite_members(reverse_iterate (group_prerequisites (t)))
  //
  inline auto
  reverse_group_prerequisite_members (action a, target& t)
  {
    return prerequisite_members (
      a, butl::reverse_iterate (group_prerequisites (t)));
  }

  //
  //
  struct target_set
  {
    typedef std::map<target_key, std::unique_ptr<target>> map;
    typedef butl::map_iterator_adapter<map::const_iterator> iterator;

    iterator
    find (const target_key& k, tracer& trace) const;

    iterator
    find (const target_type& type,
          const dir_path& dir,
          const std::string& name,
          const std::string* ext,
          tracer& trace) const
    {
      return find (target_key {&type, &dir, &name, &ext}, trace);
    }

    // As above but ignore the extension and return the target or
    // nullptr instead of the iterator.
    //
    template <typename T>
    T*
    find (const dir_path& dir, const std::string& name) const
    {
      const std::string* e (nullptr);
      auto i (map_.find (target_key {&T::static_type, &dir, &name, &e}));
      return i != map_.end () ? static_cast<T*> (i->second.get ()) : nullptr;
    }

    iterator begin () const {return map_.begin ();}
    iterator end () const {return map_.end ();}

    std::pair<target&, bool>
    insert (const target_type&,
            dir_path dir,
            std::string name,
            const std::string* ext,
            tracer&);

    template <typename T>
    T&
    insert (const dir_path& dir, const std::string& name, tracer& t)
    {
      return static_cast<T&> (
        insert (T::static_type, dir, name, nullptr, t).first);
    }

    void
    clear () {map_.clear ();}

  private:
    map map_;
  };

  extern target_set targets;

  using target_type_map_base = std::map<
    const char*,
    std::reference_wrapper<const target_type>,
    butl::compare_c_string>;

  class target_type_map: public target_type_map_base
  {
  public:
    void
    insert (const target_type& tt) {emplace (tt.name, tt);}

    using target_type_map_base::find;

    // Given a name, figure out its type, taking into account extensions,
    // special names (e.g., '.' and '..'), or anything else that might be
    // relevant. Also process the name (in place) by extracting the
    // extension, adjusting dir/value, etc (note that the dir is not
    // necessarily normalized). Return NULL if not found.
    //
    const target_type*
    find (name&, const std::string*& ext) const;
  };

  extern target_type_map target_types;

  // Modification time-based target.
  //
  class mtime_target: public target
  {
  public:
    using target::target;

    // Target mtime is only available after a rule has been matched
    // (because this is when we know if we should get our mtime from
    // the group and where the path which we need to load mtime is
    // normally assigned). The mtime is also unavailable while the
    // execution of the target is postponed (because we temporarily
    // loose our group state).
    //
    // The rule for groups that utilize the group state is as follows:
    // if it has any members that are mtime_targets, then the group
    // should be mtime_target and the members get the mtime from it.
    //
    timestamp
    mtime () const
    {
      assert (raw_state != target_state::postponed);

      const mtime_target* t (raw_state == target_state::group
                             ? static_cast<const mtime_target*> (group)
                             : this);

      if (t->mtime_ == timestamp_unknown)
        t->mtime_ = t->load_mtime ();

      return t->mtime_;
    }

    void
    mtime (timestamp mt)
    {
      // While we can cache the mtime at any time, it may be ignored
      // if the target state is group (see the mtime() accessor).
      //
      mtime_ = mt;
    }

  protected:
    virtual timestamp
    load_mtime () const = 0;

  public:
    static const target_type static_type;

  private:
    mutable timestamp mtime_ {timestamp_unknown};
  };

  // Filesystem path-based target.
  //
  class path_target: public mtime_target
  {
  public:
    using mtime_target::mtime_target;

    typedef build::path path_type;

    const path_type&
    path () const {return path_;}

    void
    path (path_type p) {assert (path_.empty ()); path_ = std::move (p);}

    // Derive a path from target's dir, name, and, if specified, ext.
    // If ext is not specified, then use default_ext and also update
    // the target's extension (this becomes important if later we need
    // to reliably determine whether this file has an extension; think
    // hxx{foo.bar.} and hxx.ext is empty).
    //
    // If name_prefix is not NULL, add it before the name part and after
    // the directory. Similarly, if name_suffix is not NULL, add it after
    // the name part and before the extension.
    //
    // Finally, if the path was already assigned to this target, then
    // this function verifies that the two are the same.
    //
    void
    derive_path (const char* default_ext = nullptr,
                 const char* name_prefix = nullptr,
                 const char* name_suffix = nullptr);

  public:
    static const target_type static_type;

  private:
    path_type path_;
  };

  // File target.
  //
  class file: public path_target
  {
  public:
    using path_target::path_target;

  protected:
    // Note that it is final in order to be consistent with file_rule,
    // search_existing_file().
    //
    virtual timestamp
    load_mtime () const final;

  public:
    virtual const target_type& type () const {return static_type;}
    static const target_type static_type;
  };

  // Directory alias/action target. Note that it is not mtime-based.
  // Rather it is meant to represent a group of targets. For actual
  // filesystem directory (creation), see fsdir.
  //
  class dir: public target
  {
  public:
    using target::target;

  public:
    virtual const target_type& type () const {return static_type;}
    static const target_type static_type;
  };

  // While a filesystem directory is mtime-based, the semantics is
  // not very useful in our case. In particular, if another target
  // depends on fsdir{}, then all that's desired is the creation of
  // the directory if it doesn't already exist. In particular, we
  // don't want to update the target just because some unrelated
  // entry was created in that directory.
  //
  class fsdir: public target
  {
  public:
    using target::target;

  public:
    virtual const target_type& type () const {return static_type;}
    static const target_type static_type;
  };

  // Common implementation of the target factory, extension, and
  // search functions.
  //
  template <typename T>
  target*
  target_factory (dir_path d, std::string n, const std::string* e)
  {
    return new T (std::move (d), std::move (n), e);
  }

  // Return fixed target extension.
  //
  template <const char* ext>
  const std::string&
  target_extension_fix (const target_key&, scope&);

  // Get the extension from the variable.
  //
  template <const char* var>
  const std::string&
  target_extension_var (const target_key&, scope&);

  // The default behavior, that is, look for an existing target in the
  // prerequisite's directory scope.
  //
  target*
  search_target (const prerequisite_key&);

  // First look for an existing target as above. If not found, then look
  // for an existing file in the target-type-specific list of paths.
  //
  target*
  search_file (const prerequisite_key&);

}

#include <build/target.ixx>
#include <build/target.txx>

#endif // BUILD_TARGET