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

#ifndef BUILD2_TARGET
#define BUILD2_TARGET

#include <iterator>     // tags, etc.
#include <type_traits>  // aligned_storage
#include <unordered_map>

#include <butl/multi-index> // map_iterator_adapter

#include <build2/types>
#include <build2/utility>

#include <build2/scope>
#include <build2/variable>
#include <build2/operation>
#include <build2/target-type>
#include <build2/target-key>
#include <build2/prerequisite>

namespace build2
{
  class scope;
  class target;

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

  // Target state.
  //
  enum class target_state: uint8_t
  {
    // The order of the enumerators is arranged so that their integral values
    // indicate whether one "overrides" the other in the "merge" operator|
    // (see below).
    //
    // Note that postponed is "greater" than unchanged since it may result in
    // the changed state.
    //
    unknown,
    unchanged,
    postponed,
    busy,
    changed,
    failed,
    group       // Target's state is the group's state.
  };

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

  inline target_state&
  operator |= (target_state& l, target_state r)
  {
    if (static_cast<uint8_t> (r) > static_cast<uint8_t> (l))
      l = r;

    return l;
  }

  // Recipe.
  //
  // The returned target state should be changed, unchanged, or postponed,
  // though you shouldn't be returning postponed directly. If there is an
  // error, then the recipe should throw rather than returning failed.
  //
  // The return value of the recipe is used to update the target state. If it
  // is target_state::group then the target's state is the group's state.
  //
  // Note that max size for the "small capture optimization" in std::function
  // ranges (in pointer sizes) from 0 (GCC prior to 5) to 2 (GCC 5) to 6 (VC
  // 14u2). With the size ranging (in bytes for 64-bit target) from 32 (GCC)
  // to 64 (VC).
  //
  using recipe_function = target_state (action, const target&);
  using recipe = function<recipe_function>;

  // Commonly-used recipes. The default recipe executes the action on
  // all the prerequisites in a loop, skipping ignored. Specifically,
  // for actions with the "first" execution mode, it calls
  // execute_prerequisites() while for those with the "last" mode --
  // reverse_execute_prerequisites(); see <build2/operation>,
  // <build2/algorithm> for details. The group recipe call's 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, const target&); // Defined in <build2/algorithm>.

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

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

  // Target.
  //
  class target
  {
    optional<string>* ext_; // Reference to value in target_key.

  public:
    // For targets that are in the src tree of a project we also keep the
    // corresponding out directory. As a result we may end up with multiple
    // targets for the same file if we are building multiple configurations of
    // the same project at once. We do it this way because, in a sense, a
    // target's out directory is its "configuration" (in terms of variables).
    // As an example, consider installing the same README file (src) but for
    // two different project configurations at once. Which installation
    // directory should we use? The answer depends on which configuration you
    // ask.
    //
    // Empty out directory indicates this target is in the out tree (including
    // when src == out). We also treat out of project targets as being in the
    // out tree.
    //
    const dir_path   dir;  // Absolute and normalized.
    const dir_path   out;  // Empty or absolute and normalized.
    const string     name;

    const string* ext () const; // Return NULL if not specified.
    const string& ext (string);

    const dir_path&
    out_dir () const {return out.empty () ? dir : out;}

    // 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 (with a small
    // exception for ad hoc groups; see below).
    //
    // The semantics of the interaction between the group and its members and
    // what it means to, say, update the group, is unspecified and is
    // 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 alternatives 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.
    //
    // In a combination group we usually want the state (and timestamp; see
    // mtime()) for members to come from the group. This is achieved with the
    // special target_state::group state. You would normally also use the
    // group_recipe for group members.
    //
    const_ptr<target> group = nullptr;


    // What has been described above is a "normal" group. That is, there is
    // a dedicated target type that explicitly serves as a group and there
    // is an explicit mechanism for discovering the group's members.
    //
    // However, sometimes, we may want to create a group on the fly out of a
    // normal target type. For example, we have the libs{} target type. But
    // on Windows a shared library consist of (at least) two files: the import
    // library and the DLL itself. So we somehow need to be able to capture
    // that. One approach would be to imply the presence of the second file.
    // However, that means that a lot of generic rules (e.g., clean, install,
    // etc) will need to know about this special semantics on Windows. Also,
    // there would be no convenient way to customize things like extensions,
    // etc (for which we use target-specific variables). In other words, it
    // would be much easier and more consistent to make these extra files
    // proper targets.
    //
    // So to support this requirement we have "ad hoc" groups. The idea is
    // that any target can be turned (by the rule that matched it) into an ad
    // hoc group by chaining several targets. Ad hoc groups have a more
    // restricted semantics compared to the normal groups. In particular:
    //
    // - The ad hoc group itself is in a sense its first/primary target.
    //
    // - Group member's recipes should be set to group_recipe by the group's
    //   rule.
    //
    // - Members are discovered lazily, they are only known after the group's
    //   rule's apply() call.
    //
    // - Members cannot be used as prerequisites but can be used as targets
    // - (e.g., to set variables, etc).
    //
    // - Members don't have prerequisites.
    //
    // - Ad hoc group cannot have sub group (of any kind) though an ad hoc
    //   group can be a sub-group of a normal group.
    //
    // - Member variable lookup skips the ad hoc group (since the group is
    //   the first member, this is normally what we want).
    //
    const_ptr<target> member = nullptr;

    bool
    adhoc_group () const
    {
      // An ad hoc group can be a member of a normal group.
      //
      return member != nullptr &&
        (group == nullptr || group->member == nullptr);
    }

    bool
    adhoc_member () const
    {
      return group != nullptr && group->member != nullptr;
    }

  public:
    using action_type = build2::action;

    // Reset the target before matching it to a rule. The default
    // implementation clears the auxilary data and prerequisite_targets.
    //
    virtual void
    reset (action_type);

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

    // Note that the returned key "tracks" the target (except for the
    // extension).
    //
    target_key
    key () const;

    // Scoping.
    //
   public:
    // Most qualified scope that contains this target.
    //
    const 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.
    //
    const scope&
    root_scope () const;

    // Root scope of a strong amalgamation that contains this target.
    // The same notes as to root_scope() apply.
    //
    const scope&
    strong_scope () const {return *root_scope ().strong_scope ();}

    // Root scope of the outermost amalgamation that contains this target.
    // The same notes as to root_scope() apply.
    //
    const scope&
    weak_scope () const {return *root_scope ().weak_scope ();}

    bool
    in (const scope& s) const
    {
      return out_dir ().sub (s.out_path ());
    }

    // Prerequisites.
    //
  public:
    using prerequisites_type = small_vector<prerequisite, 4>;
    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().
    //
    // Note that the recipe may modify (mutable) this list.
    //
    using prerequisite_targets_type = vector<const target*>;
    mutable 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 (including target type/pattern-specific variables). If you
    // only want to lookup in this target, do it on the variable map directly
    // (and note that there will be no overrides).
    //
    lookup
    operator[] (const variable& var) const
    {
      return find (var).first;
    }

    lookup
    operator[] (const variable* var) const // For cached variables.
    {
      assert (var != nullptr);
      return operator[] (*var);
    }

    lookup
    operator[] (const string& name) const
    {
      const variable* var (var_pool.find (name));
      return var != nullptr ? operator[] (*var) : lookup ();
    }

    // As above but also return the depth at which the value is found. The
    // depth is calculated by adding 1 for each test performed. So a value
    // that is from the target will have depth 1. That from the group -- 2.
    // From the innermost scope's target type/patter-specific variables --
    // 3. From the innermost scope's variables -- 4. And so on.  The idea is
    // that given two lookups from the same target, we can say which one came
    // earlier. If no value is found, then the depth is set to ~0.
    //
    //
    pair<lookup, size_t>
    find (const variable& var) const
    {
      auto p (find_original (var));
      return var.override == nullptr
        ? p
        : base_scope ().find_override (var, move (p), true);
    }

    // If target_only is true, then only look in target and its target group
    // without continuing in scopes.
    //
    pair<lookup, size_t>
    find_original (const variable&, bool target_only = false) const;

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

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

    // A target that is not (yet) entered as part of a real dependency
    // declaration (for example, that is entered as part of a target-specific
    // variable assignment, dependency extraction, etc) is called implied.
    //
    // The implied flag should only be cleared during the load phase via the
    // target_set::insert().
    //
  public:
    bool implied;

    // Target state.
    //
  protected:
    friend target_state execute_impl (action, target&);

    target_state state_;

  public:

    // Atomic task count that is used during execution to (atomically) track a
    // subset of the target's state as well as the number of its sub-tasks
    // (execution of prerequisites).
    //
    // The count starts unexecuted and can then transition to postponed or
    // executing. Postponed can transition to executing. And executing
    // transitions (via a decrement) to executed. Once it is executed, then
    // state_ becomes immutable.
    //
    // The target is said to be synchronized (in this thread) if we have
    // either observed the task count to reach count_executed or we have
    // successfully changed it (via compare_exchange) to count_executing.
    // If the target is synchronized, then we can access and modify (second
    // case) its state, mtime, etc.
    //
    static const size_t count_unexecuted = 0;
    static const size_t count_postponed  = 1;
    static const size_t count_executed   = 2;
    static const size_t count_executing  = 3;

    mutable atomic_count task_count;

    // Return the "stapshot" of the target state. That is, unless the target
    // has been executed, its state can change asynchronously.
    //
    target_state
    atomic_state () const;

    // During execution this function can only be called if we have observed
    // (synchronization-wise) that this target has been executed.
    //
    target_state
    synchronized_state () const;

    // 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.
    //
    atomic_count dependents;

    // Auxilary data storage.
    //
  public:
    // A rule that matches (i.e., returns true from its match() function) may
    // use this pad to pass data between its match and apply functions as well
    // as the recipe. After the recipe is executed, the data is destroyed by
    // calling data_dtor (if not NULL). The rule should static assert that the
    // size of the pad is sufficient for its needs.
    //
    // Note also that normally at least 2 extra pointers may be stored without
    // a dynamic allocation in the returned recipe (small object optimization
    // in std::function). So if you need to pass data only between apply() and
    // the recipe, then this might be a more convenient way.
    //
    // Note also that a rule that delegates to another rule may not be able to
    // use this mechanism fully since the delegated-to rule may also need the
    // data pad.
    //
    // Currenly the data is not destroyed until the next match.
    //
    // Note that the recipe may modify (mutable) the data.
    //
    static constexpr size_t data_size = sizeof (string) * 4;
    mutable std::aligned_storage<data_size>::type data_pad;
    mutable void (*data_dtor) (void*) = nullptr;

    template <typename R,
              typename T = typename std::remove_cv<
                typename std::remove_reference<R>::type>::type>
    typename std::enable_if<std::is_trivially_destructible<T>::value,T&>::type
    data (R&& d)
    {
      assert (sizeof (T) <= data_size && data_dtor == nullptr);
      return *new (&data_pad) T (forward<R> (d));
    }

    template <typename R,
              typename T = typename std::remove_cv<
                typename std::remove_reference<R>::type>::type>
    typename std::enable_if<!std::is_trivially_destructible<T>::value,T&>::type
    data (R&& d)
    {
      assert (sizeof (T) <= data_size && data_dtor == nullptr);
      T& r (*new (&data_pad) T (forward<R> (d)));
      data_dtor = [] (void* p) {static_cast<T*> (p)->~T ();};
      return r;
    }

    template <typename T>
    T&
    data () const {return *reinterpret_cast<T*> (&data_pad);}

    void
    clear_data () const
    {
      if (data_dtor != nullptr)
      {
        data_dtor (&data_pad);
        data_dtor = nullptr;
      }
    }

    // Recipe.
    //
  public:
    using recipe_type = build2::recipe;

    action_type action; // Action this recipe is for.

    const recipe_type&
    recipe (action_type a) const {return a > action ? empty_recipe : recipe_;}

    void
    recipe (action_type, recipe_type);

  private:
    recipe_type recipe_;

    // Target type info and casting.
    //
  public:
    bool
    is_a (const target_type& tt) const {return type ().is_a (tt);}

    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);}

    // Unchecked cast.
    //
    template <typename T>
    T&
    as () {return static_cast<T&> (*this);}

    template <typename T>
    const T&
    as () const {return static_cast<const T&> (*this);}

    // Dynamic derivation to support define.
    //
    const target_type* derived_type = nullptr;

    const target_type&
    type () const
    {
      return derived_type != nullptr ? *derived_type : dynamic_type ();
    }

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

  public:
    virtual
    ~target ();

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

    // The only way to create a target should be via the targets set below.
    //
  public:
    friend class target_set;

    target (dir_path d, dir_path o, string n)
        : dir (move (d)), out (move (o)), name (move (n)),
          vars (false) // Note: not global.
    {}
  };

  // All targets are from the targets set below.
  //
  inline bool
  operator== (const target& x, const target& y) {return &x == &y;}

  inline bool
  operator!= (const target& x, const target& y) {return !(x == y);}

  inline ostream&
  operator<< (ostream& os, const target& t) {return os << t.key ();}


  // 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& p: group_prerequisites (t))
  //
  // for (prerequisite& p: 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.
  //
  // For constant iteration use const_group_prerequisites().
  //
  template <typename T, typename P, typename I>
  class group_prerequisites_impl
  {
  public:
    explicit
    group_prerequisites_impl (T& t)
        : t_ (t),
          g_ (t_.group == nullptr              ||
              t_.group->member != nullptr      || // Ad hoc group member.
              t_.group->prerequisites.empty ()
              ? nullptr : t_.group) {}

    struct iterator
    {
      using value_type        = typename I::value_type;
      using pointer           = typename I::pointer;
      using reference         = typename I::reference;
      using difference_type   = typename I::difference_type;
      using iterator_category = std::bidirectional_iterator_tag;

      iterator () {}
      iterator (T* t, T* g, P* c, I i): t_ (t), g_ (g), 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); operator++ (); return r;}

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

        --i_;
        return *this;
      }

      iterator
      operator-- (int) {iterator r (*this); operator-- (); 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.g_ == y.g_ && x.c_ == y.c_ && x.i_ == y.i_;
      }

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

    private:
      T* t_ = nullptr;
      T* g_ = nullptr;
      P* c_ = nullptr;
      I  i_;
    };

    using reverse_iterator = std::reverse_iterator<iterator>;

    iterator
    begin () const
    {
      P& c ((g_ != nullptr ? *g_ : t_).prerequisites);
      return iterator (&t_, g_, &c, c.begin ());
    }

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

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

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

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

  private:
    T& t_;
    T* g_;
  };

  using group_prerequisites = group_prerequisites_impl<
    target,
    target::prerequisites_type,
    target::prerequisites_type::iterator>;

  using const_group_prerequisites = group_prerequisites_impl<
    const target,
    const target::prerequisites_type,
    target::prerequisites_type::const_iterator>;

  // 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
  {
    using target_type = build2::target;
    using prerequisite_type = build2::prerequisite;
    using target_type_type = build2::target_type;

    prerequisite_type& prerequisite;
    target_type* target;

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

    bool
    is_a (const target_type_type& tt) const
    {
      return target != nullptr ? target->is_a (tt) : prerequisite.is_a (tt);
    }

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

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

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

    const optional<string>&
    proj () const
    {
      // Target cannot be project-qualified.
      //
      return target != nullptr
        ? prerequisite_key::nullproj
        : prerequisite.proj;
    }

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

    // Return as a new prerequisite instance.
    //
    prerequisite_type
    as_prerequisite () const;
  };

  // It is often stored as the target's auxiliary data so make sure there is
  // no destructor overhead.
  //
  static_assert (std::is_trivially_destructible<prerequisite_member>::value,
                 "prerequisite_member is not trivially destructible");

  inline ostream&
  operator<< (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 (ad hoc groups are always see through). 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 (slock& ml, action a, T&& x, bool members = true)
  {
    return prerequisite_members_range<T> (ml, a, forward<T> (x), members);
  }

  template <typename T>
  class prerequisite_members_range
  {
  public:
    prerequisite_members_range (slock& l, action a, T&& r, bool m)
        : l_ (l), a_ (a), members_ (m), r_ (forward<T> (r)), e_ (r_.end ()) {}

    using base_iterator = decltype (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}, k_ (nullptr)
      {
        if (r_->members_ && i_ != r_->e_ && i_->type.see_through)
          switch_mode ();
      }

      iterator& operator++ ();
      iterator operator++ (int) {iterator r (*this); operator++ (); 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. Note that it can be used on ad hoc groups.
      //
      void
      leave_group ();

      // Iterate over this group's members. Return false if the member
      // information is not available. Similar to leave_group(), you should
      // increment the iterator after calling this function (provided it
      // returned true). Note that it cannot be used on ad hoc groups (which
      // will be always be entered).
      //
      bool
      enter_group ();

      value_type operator* () const
      {
        target* t (k_ != nullptr ? k_:
                   g_.count != 0 ? g_.members[j_ - 1] : nullptr);

        return value_type {*i_, t};
      }

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

        target* t (k_ != nullptr ? k_:
                   g_.count != 0 ? g_.members[j_ - 1] : nullptr);

        return new (&m_) value_type {*i_, t};
      }

      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_) &&
          x.k_ == y.k_;
      }

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

      // What we have here is a state for three nested iteration modes (and
      // no, I am not proud of it). The innermost mode is iteration over an ad
      // hoc group (k_). Then we have iteration over a normal group (g_ and
      // j_). Finally, at the outer level, we have the range itself (i_).
      //
      // The ad hoc iteration is peculiar in that we only switch to this mode
      // once the caller tries to increment past the group itself (which is
      // the primary/first member). The reason for this is that the members
      // will normally only be known once the caller searched and matched
      // the group.
      //
      // Also, the enter/leave group support is full of ugly, special cases.
      //
    private:
      void
      switch_mode ();

    private:
      const prerequisite_members_range* r_;
      base_iterator i_;
      group_view g_;
      size_t j_; // 1-based index, to support enter_group().
      target* k_; // Current member of ad hoc group or NULL.
      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:
    slock& l_;
    action a_;
    bool members_; // Go into group members by default?
    T r_;
    base_iterator e_;
  };

  // prerequisite_members(t.prerequisites)
  //
  inline auto
  prerequisite_members (slock& ml, action a, target& t, bool members = true)
  {
    return prerequisite_members (ml, a, t.prerequisites, members);
  }

  // prerequisite_members(reverse_iterate(t.prerequisites))
  //
  inline auto
  reverse_prerequisite_members (
    slock& ml, action a, target& t, bool members = true)
  {
    return prerequisite_members (
      ml, a, reverse_iterate (t.prerequisites), members);
  }

  // prerequisite_members(group_prerequisites (t))
  //
  inline auto
  group_prerequisite_members (
    slock& ml, action a, target& t, bool members = true)
  {
    return prerequisite_members (ml, a, group_prerequisites (t), members);
  }

  // prerequisite_members(reverse_iterate (group_prerequisites (t)))
  //
  inline auto
  reverse_group_prerequisite_members (
    slock& ml, action a, target& t, bool members = true)
  {
    return prerequisite_members (
      ml, a, reverse_iterate (group_prerequisites (t)), members);
  }

  // A target with an unspecified extension is considered equal to the one
  // with the specified one. And when we find a target with an unspecified
  // extension via a key with the specified one, we update the extension,
  // essentially modifying the map's key. To make this work we use a hash
  // map. The key's hash ignores the extension, so the hash will stay stable
  // across extension updates.
  //
  // Note also that once the extension is specified, it becomes immutable.
  //
  class target_set
  {
  public:
    using map_type = std::unordered_map<target_key, unique_ptr<target>>;

    // Return existing target or NULL.
    //
    target*
    find (const target_key& k, tracer& trace) const;

    target*
    find (const target_type& type,
          const dir_path& dir,
          const dir_path& out,
          const string& name,
          const optional<string>& ext,
          tracer& trace) const
    {
      return find (target_key {&type, &dir, &out, &name, ext}, trace);
    }

    template <typename T>
    T*
    find (const target_type& type,
          const dir_path& dir,
          const dir_path& out,
          const string& name,
          const optional<string>& ext,
          tracer& trace) const
    {
      return static_cast<T*> (find (type, dir, out, name, ext, trace));
    }

    // As above but ignore the extension.
    //
    template <typename T>
    T*
    find (const dir_path& dir, const dir_path& out, const string& name) const
    {
      slock l (mutex_);
      auto i (
        map_.find (
          target_key {&T::static_type, &dir, &out, &name, nullopt}));
      return i != map_.end () ? static_cast<T*> (i->second.get ()) : nullptr;
    }

    pair<target&, bool>
    insert (const target_type&,
            dir_path dir,
            dir_path out,
            string name,
            optional<string> ext,
            bool implied,
            tracer&);

    // Note that the following versions always enter implied targets.
    //
    template <typename T>
    T&
    insert (const target_type& tt,
            dir_path dir,
            dir_path out,
            string name,
            optional<string> ext,
            tracer& t)
    {
      return insert (tt,
                     move (dir),
                     move (out),
                     move (name),
                     move (ext),
                     true,
                     t).first.template as<T> ();
    }

    template <typename T>
    T&
    insert (const dir_path& dir,
            const dir_path& out,
            const string& name,
            const optional<string>& ext,
            tracer& t)
    {
      return insert<T> (T::static_type, dir, out, name, ext, t);
    }

    template <typename T>
    T&
    insert (const dir_path& dir,
            const dir_path& out,
            const string& name,
            tracer& t)
    {
      return insert<T> (dir, out, name, nullopt, t);
    }

    // Note: not MT-safe so can only be used during serial execution.
    //
  public:
    using iterator = butl::map_iterator_adapter<map_type::const_iterator>;

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

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

  private:
    friend class target; // Access to mutex.

    mutable shared_mutex mutex_;
    map_type map_;
  };

  extern target_set targets;

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

    // Generally, modification time for a target can only be queried after a
    // rule has been matched since that's where the path is normally gets
    // assigned (if the path was not assigned and no timestamp was set
    // manually, this function will return timestamp_unknown). Normally,
    // however, it would make sense to first execute the rule to get the
    // "updated" timestamp.
    //
    // 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 (bool load = true) const
    {
      const mtime_target& t (state_ == target_state::group
                             ? group->as<mtime_target> ()
                             : *this);

      if (load && t.mtime_ == timestamp_unknown)
        t.mtime_ = t.load_mtime ();

      return t.mtime_;
    }

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

    // Return true if this target is newer than the specified timestamp.
    //
    // Note: can only be called on a synchronized target.
    //
    bool
    newer (timestamp mt) const
    {
      timestamp mp (mtime ());

      // What do we do if timestamps are equal? This can happen, for example,
      // on filesystems that don't have subsecond resolution. There is not
      // much we can do here except detect the case where the target was
      // changed on this run.
      //
      return mt < mp || (mt == mp &&
                         synchronized_state () == target_state::changed);
    }

  protected:
    // Return timestamp_unknown if the mtime cannot be loaded.
    //
    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 build2::path path_type;

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

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

    // Derive a path from target's dir, name, and, if set, ext. If ext is not
    // set, try to derive it using the target type extension function and
    // fallback to default_ext, if specified. In both cases 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{*}:extension 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.
    //
    const path_type&
    derive_path (const char* default_ext = nullptr,
                 const char* name_prefix = nullptr,
                 const char* name_suffix = nullptr);

    // This version can be used to derive the path from another target's path
    // by adding another extension.
    //
    const path_type&
    derive_path (path_type base, const char* default_ext = nullptr);

    // As above but only derives (and returns) the extension (empty means no
    // extension used). If search is true then look for the extension as if
    // it was a prerequisite, not a target.
    //
    const string&
    derive_extension (const char* default_ext = nullptr, bool search = false);

  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:
    static const target_type static_type;
    virtual const target_type& dynamic_type () const {return static_type;}
  };

  // Alias target. It represents a list of targets (its prerequisites)
  // as a single "name".
  //
  class alias: public target
  {
  public:
    using target::target;

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

  // Directory target. Note that this is not a filesystem directory
  // but rather an alias target with the directory name. For actual
  // filesystem directory (creation), see fsdir.
  //
  class dir: public alias
  {
  public:
    using alias::alias;

  public:
    static const target_type static_type;
    virtual const target_type& dynamic_type () const {return 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:
    static const target_type static_type;
    virtual const target_type& dynamic_type () const {return static_type;}
  };

  // Executable file.
  //
  class exe: public file
  {
  public:
    using file::file;

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

  class buildfile: public file
  {
  public:
    using file::file;

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

  // Common documentation file targets.
  //
  // @@ Maybe these should be in the built-in doc module?
  //
  class doc: public file
  {
  public:
    using file::file;

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

  // The problem with man pages is this: different platforms have
  // different sets of sections. What seems to be the "sane" set
  // is 1-9 (Linux and BSDs). SysV (e.g., Solaris) instead maps
  // 8 to 1M (system administration). The section determines two
  // things: the directory where the page is installed (e.g.,
  // /usr/share/man/man1) as well as the extension of the file
  // (e.g., test.1). Note also that there could be sub-sections,
  // e.g., 1p (for POSIX). Such a page would still go into man1
  // but will have the .1p extension (at least that's what happens
  // on Linux). The challenge is to somehow handle this in a
  // portable manner. So here is the plan:
  //
  // First of all, we have the man{} target type which can be used
  // for a custom man page. That is, you can have any extension and
  // install it anywhere you please:
  //
  // man{foo.X}: install = man/manX
  //
  // Then we have man1..9{} target types which model the "sane"
  // section set and that would be automatically installed into
  // correct locations on other platforms. In other words, the
  // idea is that you should be able to have the foo.8 file,
  // write man8{foo} and have it installed as man1m/foo.1m on
  // some SysV host.
  //
  // Re-mapping the installation directory is easy: to help with
  // that we have assigned install.man1..9 directory names. The
  // messy part is to change the extension. It seems the only
  // way to do that would be to have special logic for man pages
  // in the generic install rule. @@ This is still a TODO.
  //
  // Note that handling subsections with man1..9{} is easy, we
  // simply specify the extension explicitly, e.g., man{foo.1p}.
  //
  class man: public doc
  {
  public:
    using doc::doc;

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

  class man1: public man
  {
  public:
    using man::man;

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

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

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

  // Get the extension from the variable or use the default if none set. If
  // the default is NULL, then return NULL.
  //
  template <const char* var, const char* def>
  optional<string>
  target_extension_var (const target_key&, const scope&, bool);

  // Always return NULL extension.
  //
  optional<string>
  target_extension_null (const target_key&, const scope&, bool);

  // Assert if called.
  //
  optional<string>
  target_extension_assert (const target_key&, const scope&, bool);

  // Target print functions.
  //

  // Target type uses the extension but it is fixed and there is no use
  // printing it (e.g., man1{}).
  //
  void
  target_print_0_ext_verb (ostream&, const target_key&);

  // Target type uses the extension and there is normally no default so it
  // should be printed (e.g., file{}).
  //
  void
  target_print_1_ext_verb (ostream&, const target_key&);

  // 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 <build2/target.ixx>
#include <build2/target.txx>

#endif // BUILD2_TARGET