path: root/build/target

// 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()
#include <iterator>

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

#include <build/path>
#include <build/timestamp>
#include <build/name>
#include <build/variable>
#include <build/operation>
#include <build/target-key>
#include <build/prerequisite>
#include <build/utility>       // extension_pool

namespace build
{
  class scope;
  class target;

  // Target state.
  //
  enum class target_state {unknown, postponed, unchanged, changed, failed};

  // 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 <operation>, <algorithm>
  // for details.
  //
  extern const recipe empty_recipe;
  extern const recipe noop_recipe;
  extern const recipe default_recipe;

  target_state
  noop_action (action, target&); // Defined in <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;
  };

  // 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 {nullptr}; // 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
                             // (see, for example, variable lookup).
                             // We also currently assume that there are
                             // no multi-level groups.
   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
    // NULL is returned.
    //
    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 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.
      //
      recipe_function** f (recipe_.target<recipe_function*> ());
      state = (f == nullptr || *f != &noop_action)
        ? target_state::unknown
        : target_state::unchanged;

      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};
      prerequisites_type::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_;
  };

  //
  //
  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
    {
      const std::string* e (ext);
      return find (target_key {&type, &dir, &name, &e}, 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&);

    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;

    timestamp
    mtime () const
    {
      if (mtime_ == timestamp_unknown)
        mtime_ = load_mtime ();

      return mtime_;
    }

    void
    mtime (timestamp mt) {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);}

    // Return a path derived from target's dir, name, and, if specified,
    // ext. If ext is not specified, then use default_ext. If name_prefix
    // if not NULL, add it before the name part and after the directory.
    // Similarly, if name_suffix if not NULL, add it after the name part
    // and before the extension.
    //
    path_type
    derived_path (const char* default_ext = nullptr,
                  const char* name_prefix = nullptr,
                  const char* name_suffix = nullptr);

  protected:
    virtual timestamp
    load_mtime () const;

  public:
    static const target_type static_type;

  private:
    path_type path_;
  };

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

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

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

  // First lookfor 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>

#endif // BUILD_TARGET