[refactor] Initial support for refactoring action rules

[arphaman]

Summary

This patch implements a couple of functions that were described in my RFC from last week that’s available at http://lists.llvm.org/pipermail/cfe-dev/2017-July/054831.html. This patch adds the following pieces: apply function, requiredSelection function, and the selection::SourceSelectionRange constraint.

This code will be used as a base to start moving the functionality and tests for clang-rename over to clang-refactor.

[arphaman]

• Simplify error/diagnostic handling. Use DiagnosticOr instead of DiagOr<Expected>.
• Simplify the code for the selection requirements by removing lambda deducers and instead using special classes for requirements instead of lambdas/functions.
• Rename selectionRequirement to requiredSelection

[arphaman]

+ Introduce refactoring diagnostics.

[arphaman]

Ping.

[ioeric]

This is great work and definitely a lot to digest! ;) Some high-level comments for the first round.

In general, I really appreciate the high-level interfaces; I am just a bit concerned about the implementation which is a bit hard to follow at this point, especially with all the template magics. I left some suggestions in the comments; hopefully they would help.

I would also appreciate more detailed high-level comments on the major classes and their relationships - I found myself constantly going back to the RFC to understand their intentions.

include/clang/Basic/DiagnosticOr.h

1 ↗

(On Diff #110563)

Could you please split changes related to DiagnosticOr into a separate patch and have owners of clang/Basic/ directory review it? ;)

include/clang/Tooling/Refactoring/RefactoringActionRules.h

2

Code in this file is a bit hard to follow, especially with so many classes and template magics :P

Is it possible to split them into smaller modules, and ideally with more detailed documentation for each?

It seems to me that the following logics could live in their own headers:

• RefactoringActionRule interface.
• Base classes for requirements.
• SourceSlection-related requirements.
• Derived/specialized rules.

228

Why is this called apply? I feel something like createAction or generateAction would be more intuitive.

include/clang/Tooling/Refactoring/RefactoringOperationController.h

20

What are all the possible states, for example?

23

Maybe I am missing too much context, but I found it hard to understand the comment and couldn't relate the comment to the public interfaces. Could you elaborate more?

It is also unclear to me if this is specific to the source selection.

41

It's unclear to me what the intentions of these members are. Could you add some comments for these members?

include/clang/Tooling/Refactoring/RefactoringResult.h

36

Do we expect the result changes to be modified? Why?

include/clang/Tooling/Refactoring/SourceSelectionConstraints.h

22

nit: redundant be used.

36

It might worth explaining the relationship between this and the RequirementBase.

[alexander-shaposhnikov]

include/clang/Basic/DiagnosticOr.h

40 ↗

(On Diff #110563)

explicit ?

49 ↗

(On Diff #110563)

but probably it would be a bit cleaner to enable SFINAE via a template parameter (http://en.cppreference.com/w/cpp/types/enable_if , option #4) rather than via extra argument.

include/clang/Tooling/Refactoring/RefactoringResult.h

28

explicit ?

[arphaman]

Extracted DiagnosticOr to a separate patch at https://reviews.llvm.org/D36969.

I will update this patch tomorrow.

[arphaman]

• Split the header
• Remove DiagnosticOr in favour of Expected that will use a DiagnosticError that was proposed in the other patch.
• Address the other review comments

include/clang/Tooling/Refactoring/RefactoringOperationController.h

20

Bad comment. I think inputs is more descriptive.

include/clang/Tooling/Refactoring/RefactoringResult.h

28

Nah, it's more convenient to be able to return a single AtomicChanges without an explicit initializer I think.

36

No, that was a workaround for a non-const member use. I'll use a const cast instead.

include/clang/Tooling/Refactoring/SourceSelectionConstraints.h

36

This class is not related to RequirementBase though. Were you talking about another class?

[ioeric]

Thanks for the changes! The code is much clearer.

I am wondering if the current design could be extended to support tools (or rules) that use AST matchers? Or is the selection expected to be powerful enough to replace AST matchers?

We have a few tools in clang-tools-extra (e.g. clang-move and change-namespace) and many internal tools that are based on AST matchers, but we would really like to move them into clang-refactor in the future :)

include/clang/Tooling/Refactoring/RefactoringActionRuleRequirements.h

26 ↗

(On Diff #112195)

Could you help me understand this class?

This seems to be a selection-specific requirement and should live in selection. It is also used in BaseSpecializedRule which seems to be a higher level of abstraction.

include/clang/Tooling/Refactoring/RefactoringResult.h

22

I'm a bit unsure about the abstraction of the refactoring result. I would expected refactoring results to be source changes always. Do you have any refactoring tool that outputs occurrences in mind?

28

+1 to explicit which could prevent unintentional conversion. RefactoringResult(Change); isn't too bad IMO.

include/clang/Tooling/Refactoring/SourceSelectionConstraints.h

56

Does detail mean internal implementation? Maybe use internal which is more commonly used for this?

[arphaman]

include/clang/Tooling/Refactoring/RefactoringResult.h

22

In Xcode we require rename to return symbol occurrences because the IDE is responsible for figuring out:

1. The new name. Thus we can't produce replacements when renaming because we don't know what the new name is when gathering the occurrences.
2. Whether these occurrences should be actually applied. Thus we can't produce replacements because it's up to the user to decide if they want to rename some occurrence in a comment for example.

In general 2) can be applied to tools like clang-refactor that could allow users to select occurrences that don't guarantee a direct semantic match (comments, etc.) in an interactive manner.

I think clangd has a rather naive rename support, so these points may not apply, but we may want to extend clangd's support for rename in the future as well.

[arphaman]

In D36075#851278, @ioeric wrote:

Thanks for the changes! The code is much clearer.

I am wondering if the current design could be extended to support tools (or rules) that use AST matchers? Or is the selection expected to be powerful enough to replace AST matchers?

We have a few tools in clang-tools-extra (e.g. clang-move and change-namespace) and many internal tools that are based on AST matchers, but we would really like to move them into clang-refactor in the future :)

The selection requirement is supposed to be orthogonal to AST matchers, not a replacement. It should be used when working with source selection in editors.

I did mess around with moving over clang-reorder-fields using this kind of model and didn't see any issues when using AST matchers. Essentially I used the requiredOption requirements and mapped them to run my matching code instead of using the selection requirement. Thus this requirement was satisfied only when the AST matchers were successful. It might be possible to simplify that pattern even further to make it simpler.

In D36075#851278, @ioeric wrote:

Thanks for the changes! The code is much clearer.

I am wondering if the current design could be extended to support tools (or rules) that use AST matchers? Or is the selection expected to be powerful enough to replace AST matchers?

We have a few tools in clang-tools-extra (e.g. clang-move and change-namespace) and many internal tools that are based on AST matchers, but we would really like to move them into clang-refactor in the future :)

[arphaman]

include/clang/Tooling/Refactoring/RefactoringActionRuleRequirements.h

26 ↗

(On Diff #112195)

It's just a container class that stores all information about the requiredSelection requirement. I agree about BaseSpecializedRule, that connection should be chopped. I will move the evaluation code into the requirement itself when I update the patch.

I would tend to disagree about moving it though, as SourceSelectionRequirement is a requirement first and I think that's why it should live with other requirements. Yes, it's related to selections, but it uses them to implement the requirement. I think it's better to keep requirements together, as opposed to having option requirements close to options, selection requirements close to selection, and so on. WDYT?

[arphaman]

• Rename detail to internal.
• Remove the BaseSpecializedRule.
• Simplify selection requirement and constraint evaluation.

[ioeric]

include/clang/Tooling/Refactoring/RefactoringActionRuleRequirements.h

26 ↗

(On Diff #112195)

Thanks!

Makes sense. We might want to put individual requirements into their own headers so that this doesn't grow into a huge file when more requirements are supported.

include/clang/Tooling/Refactoring/RefactoringActionRuleRequirementsInternal.h

42 ↗

(On Diff #112566)

It might worth having a comment explaining why and how Expected<Optional> is wrapped and unwrapped during the evaluation.

include/clang/Tooling/Refactoring/RefactoringActionRules.h

34

We might want to document supported requirements somewhere else so that we don't need to update this file every time a new requirement is added.

include/clang/Tooling/Refactoring/RefactoringOperation.h

1 ↗

(On Diff #112566)

s/RefactoringOperationController.h/RefactoringOperation.h/ :)

29 ↗

(On Diff #112566)

I found the name a bit confusing - RefactoringOperation sounds a bit like RefactoringAction.

Would it make sense to call this RefactoringContext or RefactoringRuleContext, if this stores states of a refactoring rule?

include/clang/Tooling/Refactoring/RefactoringResult.h

22

I feel occurrences are more of an intermediate state of a refactoring action than a result. I'm wondering if it makes sense to introduce a separate class to represent such intermediate states? I am a bit nervous to fuse multiple classes into one; the interfaces can get pretty ugly when more result kinds are added.

lib/Tooling/Refactoring/SourceSelectionConstraints.cpp

13 ↗

(On Diff #112566)

We are tempted to avoid using namespace if possible.

[arphaman]

include/clang/Tooling/Refactoring/RefactoringResult.h

22

Good point. I agree.

I think it would be better to differentiate between RefactoringActionRules then. Ordinary rules return a set of AtomicChanges instead of RefactoringResult. But then we could also have "interactive" rules that return "partial" results like symbol occurrences.

I think I'll try the following approach:

class RefactoringActionRule {
  virtual ~RefactoringActionRule() {}
};

class RefactoringActionSourceChangeRule: public RefactoringActionRule {
public:
  virtual Expected<Optional<AtomicChanges>>
  createSourceReplacements(RefactoringOperation &Operation) = 0;
};

class RefactoringActionSymbolOccurrencesRule: public RefactoringActionRule {
public:
  virtual Expected<Optional<SymbolOccurrences>>
  findSymbolOccurrences(RefactoringOperation &Operation) = 0;
};

[arphaman]

lib/Tooling/Refactoring/SourceSelectionConstraints.cpp

13 ↗

(On Diff #112566)

Why? It's not in a header. using namespace clang is the common practice across all of Clang's sources.

[alexander-shaposhnikov]

@arphaman

The selection requirement is supposed to be orthogonal to AST matchers, not a replacement. It should be used when working with source selection in editors. 
I did mess around with moving over clang-reorder-fields using this kind of model and didn't see any issues when using AST matchers. Essentially I used the  requiredOption requirements and mapped them to run my 
matching code instead of using the selection requirement. Thus this requirement was satisfied only when the AST matchers were successful. 
It might be possible to simplify that pattern even further to make it simpler.

that's great, i'm interested in this too and would be happy to see clang-reorder-fields moving to clang-refactor (pls, let me know if i can help make this happen)

[arphaman]

include/clang/Tooling/Refactoring/RefactoringActionRules.h

34

Do you think it should be in Clang's documentation? I can start on a new document there but I'd prefer to do it in a separate patch. WDYT?

[arphaman]

• Get rid of RefactoringResult in favour of different rule types.
• Rename RefactoringOperation to RefactoringRuleContext.
• Address a couple more comments.

[ioeric]

Thanks for the changes! Lgtm with a few nits.

include/clang/Tooling/Refactoring/RefactoringActionRules.h

34

Sure, this is fine for now. It would be nice to have proper documentation in the future when pieces get into places.

include/clang/Tooling/Refactoring/RefactoringActionRulesInternal.h

33 ↗

(On Diff #112678)

Why isn't this a interface in SpecificRefactoringRuleAdapter with return type Expected<Optional<T>>?

unittests/Tooling/RefactoringActionRulesTest.cpp

68

It would be nice to also rename the variable from Operation to Context.

[arphaman]

Thanks,

I'll start working on the documentation patch and will split follow-up clang-refactor patch into one or two parts today.

include/clang/Tooling/Refactoring/RefactoringActionRulesInternal.h

33 ↗

(On Diff #112678)

A method declaration in SpecificRefactoringRuleAdapter won't work since it won't be available in either the template specialisation or the deriving class as the classes won't be directly related. I could use a separate parent class independent of SpecificRefactoringRuleAdapter that declares a generic interface though.

[klimek]

cfe/trunk/include/clang/Tooling/Refactoring/RefactoringActionRule.h

23–37 ↗

(On Diff #112879)

Sorry for being late, was out on vacation.
Generally, why do we need this tag-based abstraction here instead of using the more typical OO double-dispatch where necessary?
(We do this in the AST a lot, but the AST is special, because there we want to implement a lot of different algorithms that rely on the node type, while I don't see how that applies here)

[arphaman]

cfe/trunk/include/clang/Tooling/Refactoring/RefactoringActionRule.h

23–37 ↗

(On Diff #112879)

Generally the clients will have to somehow distinguish between the types of results that are produced by rules to figure out what to do (e.g. AtomicChanges -> apply, SymbolOccurrences -> ask user, Continuation -> look for more ASTs). So far I've thought that the LLVM based dynamic casts will work well for this, e.g.

if (auto *Action = dyn_cast<SourceChangeRefactoringRule>()) {
  Expected<Optional<AtomicChanges>> Changes = Action->createSourceReplacements();
  applyChanges(Changes);
} else if (...) {
  ...
} else (...) {
   ...
}

But you're probably right, there might be a better way to do this rather than the tag based approach. Something like a consumer class that clients can implement that provides consumer functions that take in the specific results. I reckon a single consumer will actually work better in the long-run when we might Continuations that both return changes in the first TU and information for searches in other TUs. I'll see if I can get a patch out that removes this tag and uses the consumer approach.

[klimek]

cfe/trunk/include/clang/Tooling/Refactoring/RefactoringActionRule.h

23–37 ↗

(On Diff #112879)

Cool, looking forward to it :)

include/clang/Basic/LLVM.h

namespace llvm {
   class Twine;
   template<typename T> class ArrayRef;
   template<typename T> class MutableArrayRef;
   template<typename T> class OwningArrayRef;
   template<unsigned InternalLen> class SmallString;
   template<typename T, unsigned N> class SmallVector;
   template<typename T> class SmallVectorImpl;
   template<typename T> class Optional;
+  template <class T> class Expected;
 
   template<typename T>
   struct SaveAndRestore;
 
   // Reference counting.
   template <typename T> class IntrusiveRefCntPtr;
   template <typename T> struct IntrusiveRefCntPtrInfo;
   template <class Derived> class RefCountedBase;
namespace clang {
   using llvm::ArrayRef;
   using llvm::MutableArrayRef;
   using llvm::OwningArrayRef;
   using llvm::SmallString;
   using llvm::SmallVector;
   using llvm::SmallVectorImpl;
   using llvm::SaveAndRestore;
 
+  // Error handling.
+  using llvm::Expected;
+
   // Reference counting.
   using llvm::IntrusiveRefCntPtr;
   using llvm::IntrusiveRefCntPtrInfo;
   using llvm::RefCountedBase;
 
   using llvm::raw_ostream;
   using llvm::raw_pwrite_stream;
 } // end namespace clang.
 
 #endif

include/clang/Tooling/Refactoring/AtomicChange.h

public:
   /// \p KeyPosition should be the location of the key syntactical element that
   /// is being changed, e.g. the call to a refactored method.
   AtomicChange(const SourceManager &SM, SourceLocation KeyPosition);
 
   /// \brief Creates an atomic change for \p FilePath with a customized key.
   AtomicChange(llvm::StringRef FilePath, llvm::StringRef Key)
       : Key(Key), FilePath(FilePath) {}
 
+  AtomicChange(AtomicChange &&) = default;
+  AtomicChange(const AtomicChange &) = default;
+
+  AtomicChange &operator=(AtomicChange &&) = default;
+  AtomicChange &operator=(const AtomicChange &) = default;
+
   /// \brief Returns the atomic change as a YAML string.
   std::string toYAMLString();
 
   /// \brief Converts a YAML-encoded automic change to AtomicChange.
   static AtomicChange convertFromYAML(llvm::StringRef YAMLContent);
 
   /// \brief Returns the key of this change, which is a concatenation of the
   /// file name and offset of the key position.

include/clang/Tooling/Refactoring/DiagOr.h

+//===--- DiagOr.h - Clang refactoring library -----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_DIAG_OR_H
+#define LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_DIAG_OR_H
+
+#include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/LLVM.h"
+
+namespace clang {
+namespace tooling {
+
+/// A variant that stores a value of given type or an optional diagnostic.
+template <typename T> struct DiagOr {
+  DiagOr(T &&Value) : Value(std::move(Value)) {}
+  DiagOr(llvm::NoneType) {}
+  DiagOr(Optional<StoredDiagnostic> &&Diag) : Diag(std::move(Diag)) {}
+
+  DiagOr(DiagOr<T> &&) = default;
+  DiagOr &operator=(DiagOr<T> &&) = default;
+
+  Optional<StoredDiagnostic> &getDiag() {
+    assert(!Value.hasValue() && "Diagnostic with a value");
+    return Diag;
+  }
+
+  explicit operator bool() const { return hasValue(); }
+  bool hasValue() const { return Value.hasValue(); }
+  const T &operator*() const {
+    assert(Value.hasValue() && "Dereference without a value");
+    return *Value;
+  }
+  T &operator*() {
+    assert(Value.hasValue() && "Dereference without a value");
+    return *Value;
+  }
+
+private:
+  Optional<StoredDiagnostic> Diag;
+  Optional<T> Value;
+};
+
+} // end namespace tooling
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_DIAG_OR_H

include/clang/Tooling/Refactoring/RefactoringActionRules.h

+//===--- RefactoringActionRules.h - Clang refactoring library -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_ACTION_RULES_H
+#define LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_ACTION_RULES_H
+
+#include "clang/Basic/LLVM.h"
+#include "clang/Tooling/Refactoring/DiagOr.h"
+#include "clang/Tooling/Refactoring/RefactoringOperationController.h"
+#include "clang/Tooling/Refactoring/RefactoringResult.h"
+#include "clang/Tooling/Refactoring/SourceSelectionConstraints.h"
+#include "llvm/Support/Error.h"
+#include <type_traits>
+
+namespace clang {
+namespace tooling {
+
+/// A common refactoring action rule interface.
+class RefactoringActionRule {
+public:
+  virtual ~RefactoringActionRule() {}
+
+  /// The refactoring engine calls this method when trying to perform a
+  /// refactoring operation. The specific rule must return a valid diagnostic
+  /// or \c None when the refactoring action couldn't be initiated, an error
+  /// when the rule fails after initiation, or a valid refactoring result when
+  /// the action runs successfully.
+  virtual DiagOr<Expected<RefactoringResult>>
+  perform(RefactoringOperationController &Controller) = 0;
+};
+
+/// A set of refactoring action rules that should have unique initiation
+/// requirements.
+using RefactoringActionRules =
+    std::vector<std::unique_ptr<RefactoringActionRule>>;
+
+namespace refactoring_action_rules {
+
+namespace detail {
+
+struct RequirementBase {};
+
+} // end namespace detail
+
+namespace traits {
+
+/// A type trait that returns true iff the given type is a valid rule
+/// requirement.
+template <typename First, typename... Rest>
+struct IsRequirement : std::conditional<IsRequirement<First>::value &&
+                                            IsRequirement<Rest...>::value,
+                                        std::true_type, std::false_type>::type {
+};
+
+template <typename T>
+struct IsRequirement<T>
+    : std::conditional<std::is_base_of<detail::RequirementBase, T>::value,
+                       std::true_type, std::false_type>::type {};
+
+} // end namespace traits
+
+namespace detail {
+
+/// Defines a type alias of type \T when given \c DiagOr<T>, or \c T otherwise.
+template <typename T> struct DropDiagOr { using Type = T; };
+
+template <typename T> struct DropDiagOr<DiagOr<T>> { using Type = T; };
+
+/// The \c requiredSelection refactoring action requirement is represented
+/// using this type.
+template <typename InputT, typename OutputT>
+struct SourceSelectionRequirement
+    : std::enable_if<selection::traits::IsConstraint<InputT>::value,
+                     RequirementBase>::type {
+  using OutputType = typename DropDiagOr<OutputT>::Type;
+  using FunctionType = OutputT (*)(InputT);
+
+  SourceSelectionRequirement(FunctionType Function) : Function(Function) {}
+
+private:
+  OutputT (*Function)(InputT);
+  friend class BaseSpecializedRule;
+};
+
+/// A wrapper class around \c RefactoringActionRule that defines some helper
+/// methods that are used by the subclasses.
+class BaseSpecializedRule : public RefactoringActionRule {
+protected:
+  /// Evaluates a source selection action rule requirement.
+  template <typename InputT, typename OutputT>
+  static DiagOr<typename DropDiagOr<OutputT>::Type> evaluate(
+      RefactoringOperationController &Controller,
+      const SourceSelectionRequirement<InputT, OutputT> &SelectionRequirement) {
+    Optional<InputT> Value = evalSelection<InputT>(Controller);
+    if (!Value)
+      return None;
+    return SelectionRequirement.Function(*Value);
+  }
+
+  /// Returns \c T when given \c DiagOr<T>, or \c T otherwise.
+  template <typename T> static T &&removeDiagOr(DiagOr<T> &&X) {
+    assert(X && "unexpected diagnostic!");
+    return std::move(*X);
+  }
+  template <typename T> static T &&removeDiagOr(T &&X) { return std::move(X); }
+
+  using OptionalDiagOrNone = Optional<Optional<StoredDiagnostic>>;
+
+  /// Scans the tuple and returns a \c StoredDiagnostic or an \c Optional<None>
+  /// from the first invalid \c DiagOr value. Returns \c None if all values
+  /// are valid.
+  template <typename FirstT, typename... RestT>
+  static OptionalDiagOrNone findDiagOrNone(FirstT &First, RestT &... Rest) {
+    OptionalDiagOrNone Result = takeDiagOrNone(First);
+    if (Result.hasValue())
+      return Result;
+    return findDiagOrNone(Rest...);
+  }
+
+private:
+  /// Evaluates a selection constraint.
+  template <typename T>
+  static typename std::enable_if<selection::traits::IsConstraint<T>::value,
+                                 llvm::Optional<T>>::type
+  evalSelection(RefactoringOperationController &Controller);
+
+  static OptionalDiagOrNone findDiagOrNone() { return OptionalDiagOrNone(); }
+  template <typename T> static OptionalDiagOrNone takeDiagOrNone(T &) {
+    return OptionalDiagOrNone();
+  }
+  template <typename T>
+  static OptionalDiagOrNone takeDiagOrNone(DiagOr<T> &Diag) {
+    return Diag.hasValue() ? OptionalDiagOrNone() : std::move(Diag.getDiag());
+  }
+};
+
+/// Evaluates the \c selection::SourceSelectionRange constraint.
+template <>
+llvm::Optional<selection::SourceSelectionRange>
+BaseSpecializedRule::evalSelection<selection::SourceSelectionRange>(
+    RefactoringOperationController &Controller) {
+  SourceRange R = Controller.getSelectionRange();
+  if (R.isInvalid())
+    return None;
+  return selection::SourceSelectionRange(Controller.getSources(), R);
+}
+
+/// A specialized refactoring action rule that calls the stored function once
+/// all the of the requirements are fullfilled. The values produced during the
+/// evaluation of requirements are passed to the stored function.
+template <typename FunctionType, typename... RequirementTypes>
+class PlainFunctionRule final : public BaseSpecializedRule {
+public:
+  PlainFunctionRule(FunctionType Function,
+                    std::tuple<RequirementTypes...> &&Requirements)
+      : Function(Function), Requirements(std::move(Requirements)) {}
+
+  DiagOr<Expected<RefactoringResult>>
+  perform(RefactoringOperationController &Controller) override {
+    return performImpl(Controller,
+                       llvm::index_sequence_for<RequirementTypes...>());
+  }
+
+private:
+  template <size_t... Is>
+  DiagOr<Expected<RefactoringResult>>
+  performImpl(RefactoringOperationController &Controller,
+              llvm::index_sequence<Is...>) {
+    // Initiate the operation.
+    auto Values =
+        std::make_tuple(evaluate(Controller, std::get<Is>(Requirements))...);
+    OptionalDiagOrNone InitiationFailure =
+        findDiagOrNone(std::get<Is>(Values)...);
+    if (InitiationFailure)
+      return std::move(*InitiationFailure);
+    // Perform the operation.
+    return Function(removeDiagOr(std::move(std::get<Is>(Values)))...);
+  }
+
+  FunctionType Function;
+  std::tuple<RequirementTypes...> Requirements;
+};
+
+} // end namespace detail
+
+/// Creates a new refactoring action rule that invokes the given function once
+/// all of the requirements are satisfied. The values produced during the
+/// evaluation of requirements are passed to the given function (in the order of
+/// requirements).
+///
+/// \param RefactoringFunction the function that will perform the refactoring
+/// once the requirements are satisfied.
+///
+/// \param Requirements a set of rule requirements that have to be satisfied.
+/// Each requirement must be a valid requirement, i.e. the value of
+/// \c traits::IsRequirement<T> must be true.
+template <typename... RequirementTypes>
+std::unique_ptr<RefactoringActionRule>
+apply(Expected<RefactoringResult> (*RefactoringFunction)(
+          typename RequirementTypes::OutputType...),
+      const RequirementTypes &... Requirements) {
+  static_assert(traits::IsRequirement<RequirementTypes...>::value,
+                "invalid refactoring action rule requirement");
+  return llvm::make_unique<detail::PlainFunctionRule<
+      decltype(RefactoringFunction), RequirementTypes...>>(
+      RefactoringFunction, std::make_tuple(Requirements...));
+}
+
+namespace detail {
+
+template <typename T> struct lambdaDeducer;
+
+template <typename T, typename R, typename A>
+struct lambdaDeducer<R (T::*)(A) const> {
+  using ReturnType = R;
+  using ArgType = A;
+};
+
+} // end namespace detail
+
+#define DEDUCE_LAMBDA_ARG(Callable)                                            \
+  typename detail::lambdaDeducer<decltype(&Callable::operator())>::ArgType
+#define DEDUCE_LAMBDA_RET(Callable)                                            \
+  typename detail::lambdaDeducer<decltype(&Callable::operator())>::ReturnType
+
+#ifdef _MSC_VER
+// MSVC is unable to deduce to the return type that depends on lambda's argument
+// and return types. Fallback to using a C++14's decltype(auto). Luckily
+// it's supported by the minimum version of MSVC compiler that's allowed
+// by LLVM.
+#define DEDUCE_LAMBDA_TYPE(T, Callable) decltype(auto)
+#define DEDUCE_LAMBDA_TYPE_WITH_ARGTYPE(T, Callable, Arg) decltype(auto)
+#else
+// C++11 compliant type deduction that works with other compilers.
+#define DEDUCE_LAMBDA_TYPE(T, Callable)                                        \
+  T<DEDUCE_LAMBDA_ARG(Callable), DEDUCE_LAMBDA_RET(Callable)>
+#define DEDUCE_LAMBDA_TYPE_WITH_ARGTYPE(T, Callable, Arg)                      \
+  T<Arg, DEDUCE_LAMBDA_RET(Callable)>
+#endif
+
+/// Creates a selection requirement from a function pointer.
+template <typename InputT, typename OutputT>
+detail::SourceSelectionRequirement<InputT, OutputT> selectionRequirement(
+    OutputT (*Constraint)(InputT),
+    typename std::enable_if<
+        selection::traits::IsConstraint<InputT>::value>::type * = nullptr) {
+  return detail::SourceSelectionRequirement<InputT, OutputT>(Constraint);
+}
+
+/// Create a selection requirement from a non-capturing lambda.
+template <typename Callable>
+auto selectionRequirement(
+    Callable Constraint,
+    typename std::enable_if<selection::traits::IsConstraint<
+        DEDUCE_LAMBDA_ARG(Callable)>::value>::type * = nullptr)
+    -> DEDUCE_LAMBDA_TYPE(detail::SourceSelectionRequirement, Callable) {
+  return detail::SourceSelectionRequirement<DEDUCE_LAMBDA_ARG(Callable),
+                                            DEDUCE_LAMBDA_RET(Callable)>(
+      Constraint);
+}
+
+// These overloads provide a helpful diagnostic when a lambda or a function that
+// takes an invalid selection constraint is given to selectionRequirement.
+template <typename Callable>
+auto selectionRequirement(
+    Callable C, typename std::enable_if<!selection::traits::IsConstraint<
+                    DEDUCE_LAMBDA_ARG(Callable)>::value>::type * = nullptr)
+    -> DEDUCE_LAMBDA_TYPE_WITH_ARGTYPE(detail::SourceSelectionRequirement,
+                                       Callable,
+                                       selection::SourceSelectionRange) {
+  using OutputT = DEDUCE_LAMBDA_RET(Callable);
+  static_assert(sizeof(OutputT) && false,
+                "The argument type of the function passed into "
+                "'selectionRequirement' must be a valid selection constraint");
+  return detail::SourceSelectionRequirement<selection::SourceSelectionRange,
+                                            OutputT>(nullptr);
+}
+template <typename InputT, typename OutputT>
+detail::SourceSelectionRequirement<selection::SourceSelectionRange, OutputT>
+selectionRequirement(
+    OutputT (*C)(InputT),
+    typename std::enable_if<
+        !selection::traits::IsConstraint<InputT>::value>::type * = nullptr) {
+  static_assert(sizeof(OutputT) && false,
+                "The argument type of the function passed into "
+                "'selectionRequirement' must be a valid selection constraint");
+  return detail::SourceSelectionRequirement<selection::SourceSelectionRange,
+                                            OutputT>(nullptr);
+}
+
+#undef DEDUCE_LAMBDA_ARG
+#undef DEDUCE_LAMBDA_RET
+#undef DEDUCE_LAMBDA_TYPE
+#undef DEDUCE_LAMBDA_TYPE_WITH_ARGTYPE
+
+} // end namespace refactoring_action_rules
+} // end namespace tooling
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_ACTION_RULES_H

include/clang/Tooling/Refactoring/RefactoringOperationController.h

+//===--- RefactoringOperationController.h - Clang refactoring library -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_OPERATION_CONTROLLER_H
+#define LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_OPERATION_CONTROLLER_H
+
+#include "clang/Basic/SourceManager.h"
+
+namespace clang {
+namespace tooling {
+
+/// Encapsulates all of the possible state that an individual refactoring
+/// operation might have. Controls the process of initiation of refactoring
+/// operations, by feeding the right information to the functions that
+/// evaluate the refactoring action rule requirements.
+class RefactoringOperationController {
+public:
+  RefactoringOperationController(const SourceManager &SM) : SM(SM) {}
+
+  const SourceManager &getSources() const { return SM; }
+
+  /// Returns the current source selection range as set by the
+  /// refactoring engine. Can be invalid.
+  SourceRange getSelectionRange() const { return SelectionRange; }
+
+  void setSelectionRange(SourceRange R) { SelectionRange = R; }
+
+private:
+  const SourceManager &SM;
+  SourceRange SelectionRange;
+};
+
+} // end namespace tooling
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_OPERATION_CONTROLLER_H

include/clang/Tooling/Refactoring/RefactoringResult.h

+//===--- RefactoringResult.h - Clang refactoring library ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_RESULT_H
+#define LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_RESULT_H
+
+#include "clang/Tooling/Refactoring/AtomicChange.h"
+
+namespace clang {
+namespace tooling {
+
+/// Refactoring result is a variant that stores a set of source changes or
+/// a set of found symbol occurrences.
+struct RefactoringResult {
+  enum ResultKind {
+    /// A set of source replacements represented using a vector of
+    /// \c AtomicChanges.
+    AtomicChanges
+  };
+
+  RefactoringResult(AtomicChange Change) : Kind(AtomicChanges) {
+    Changes.push_back(std::move(Change));
+  }
+  RefactoringResult(RefactoringResult &&Other) = default;
+  RefactoringResult &operator=(RefactoringResult &&Other) = default;
+
+  ResultKind getKind() const { return Kind; }
+
+  llvm::MutableArrayRef<AtomicChange> getChanges() {
+    assert(getKind() == AtomicChanges &&
+           "Refactoring didn't produce atomic changes");
+    return Changes;
+  }
+
+private:
+  ResultKind Kind;
+  std::vector<AtomicChange> Changes;
+};
+
+} // end namespace tooling
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_REFACTOR_REFACTORING_RESULT_H

include/clang/Tooling/Refactoring/SourceSelectionConstraints.h

+//===--- SourceSelectionConstraints.h - Clang refactoring library ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLING_REFACTOR_SOURCE_SELECTION_CONSTRAINTS_H
+#define LLVM_CLANG_TOOLING_REFACTOR_SOURCE_SELECTION_CONSTRAINTS_H
+
+#include "clang/Basic/SourceLocation.h"
+#include <type_traits>
+
+namespace clang {
+namespace tooling {
+namespace selection {
+
+/// This constraint is satisfied when any portion of the source text is
+/// selected. It can be used be used to obtain the raw source selection range.
+struct SourceSelectionRange {
+  SourceSelectionRange(const SourceManager &SM, SourceRange Range)
+      : SM(SM), Range(Range) {}
+
+  const SourceManager &getSources() const { return SM; }
+  SourceRange getRange() const { return Range; }
+
+private:
+  const SourceManager &SM;
+  SourceRange Range;
+};
+
+namespace traits {
+
+/// A type trait that returns true iff the given type is a valid selection
+/// constraint.
+template <typename T> struct IsConstraint : public std::false_type {};
+
+} // end namespace traits
+
+/// A identity function that returns the given selection constraint is provided
+/// for convenience, as it can be passed to \c requiredSelection directly.
+template <typename T> T (*identity())(T) {
+  static_assert(
+      traits::IsConstraint<T>::value,
+      "selection::identity can be used with selection constraints only");
+  return [](T Value) { return std::move(Value); };
+}
+
+namespace traits {
+
+template <>
+struct IsConstraint<SourceSelectionRange> : public std::true_type {};
+
+} // end namespace traits
+} // end namespace selection
+} // end namespace tooling
+} // end namespace clang
+
+#endif // LLVM_CLANG_TOOLING_REFACTOR_SOURCE_SELECTION_CONSTRAINTS_H

unittests/Tooling/CMakeLists.txt

add_clang_unittest(ToolingTests
   FixItTest.cpp
   LookupTest.cpp
   QualTypeNamesTest.cpp
   RecursiveASTVisitorTest.cpp
   RecursiveASTVisitorTestCallVisitor.cpp
   RecursiveASTVisitorTestDeclVisitor.cpp
   RecursiveASTVisitorTestExprVisitor.cpp
   RecursiveASTVisitorTestTypeLocVisitor.cpp
+  RefactoringActionRulesTest.cpp
   RefactoringCallbacksTest.cpp
   RefactoringTest.cpp
   ReplacementsYamlTest.cpp
   RewriterTest.cpp
   ToolingTest.cpp
   )
 
 target_link_libraries(ToolingTests

unittests/Tooling/RefactoringActionRulesTest.cpp

+//===- unittest/Tooling/RefactoringTestActionRulesTest.cpp ----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReplacementTest.h"
+#include "RewriterTestContext.h"
+#include "clang/Tooling/Refactoring.h"
+#include "clang/Tooling/Refactoring/RefactoringActionRules.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+
+using namespace clang;
+using namespace tooling;
+using namespace refactoring_action_rules;
+
+namespace {
+
+class RefactoringActionRulesTest : public ::testing::Test {
+protected:
+  void SetUp() override {
+    Context.Sources.setMainFileID(
+        Context.createInMemoryFile("input.cpp", DefaultCode));
+  }
+
+  RewriterTestContext Context;
+  std::string DefaultCode = std::string(100, 'a');
+};
+
+TEST_F(RefactoringActionRulesTest, MyFirstRefactoringRule) {
+  auto ReplaceAWithB =
+      [](std::pair<selection::SourceSelectionRange, int> Selection)
+      -> Expected<RefactoringResult> {
+    const SourceManager &SM = Selection.first.getSources();
+    SourceLocation Loc = Selection.first.getRange().getBegin().getLocWithOffset(
+        Selection.second);
+    AtomicChange Change(SM, Loc);
+    llvm::Error E = Change.replace(SM, Loc, 1, "b");
+    if (E)
+      return std::move(E);
+    return Change;
+  };
+  auto Rule =
+      apply(ReplaceAWithB,
+            selectionRequirement([](selection::SourceSelectionRange Selection) {
+              return std::make_pair(Selection, 20);
+            }));
+
+  // When the requirements are satisifed, the rule's function must be invoked.
+  {
+    RefactoringOperationController Operation(Context.Sources);
+    SourceLocation Cursor =
+        Context.Sources.getLocForStartOfFile(Context.Sources.getMainFileID())
+            .getLocWithOffset(10);
+    Operation.setSelectionRange({Cursor, Cursor});
+
+    DiagOr<Expected<RefactoringResult>> DiagOrResult = Rule->perform(Operation);
+    ASSERT_FALSE(!DiagOrResult);
+    Expected<RefactoringResult> Result = std::move(*DiagOrResult);
+    ASSERT_FALSE(!Result);
+    ASSERT_EQ(Result->getKind(), RefactoringResult::AtomicChanges);
+    ASSERT_EQ(Result->getChanges().size(), 1u);
+    std::string YAMLString = Result->getChanges()[0].toYAMLString();
+
+    ASSERT_STREQ("---\n"
+                 "Key:             'input.cpp:30'\n"
+                 "FilePath:        input.cpp\n"
+                 "Error:           ''\n"
+                 "InsertedHeaders: \n"
+                 "RemovedHeaders:  \n"
+                 "Replacements:    \n" // Extra whitespace here!
+                 "  - FilePath:        input.cpp\n"
+                 "    Offset:          30\n"
+                 "    Length:          1\n"
+                 "    ReplacementText: b\n"
+                 "...\n",
+                 YAMLString.c_str());
+  }
+
+  // When one of the requirements is not satisfied, perform should return either
+  // None or a valid diagnostic.
+  {
+    RefactoringOperationController Operation(Context.Sources);
+    DiagOr<Expected<RefactoringResult>> DiagOrResult = Rule->perform(Operation);
+
+    ASSERT_TRUE(!DiagOrResult);
+    auto DiagOrNone = DiagOrResult.getDiag();
+    ASSERT_TRUE(!DiagOrNone);
+  }
+}
+
+TEST_F(RefactoringActionRulesTest, ReturnError) {
+  Expected<RefactoringResult> (*Func)(selection::SourceSelectionRange) =
+      [](selection::SourceSelectionRange) -> Expected<RefactoringResult> {
+    return llvm::make_error<llvm::StringError>(
+        "Error", std::make_error_code(std::errc::bad_message));
+  };
+  auto Rule =
+      apply(Func, selectionRequirement(
+                      selection::identity<selection::SourceSelectionRange>()));
+
+  RefactoringOperationController Operation(Context.Sources);
+  SourceLocation Cursor =
+      Context.Sources.getLocForStartOfFile(Context.Sources.getMainFileID());
+  Operation.setSelectionRange({Cursor, Cursor});
+  DiagOr<Expected<RefactoringResult>> Result = Rule->perform(Operation);
+
+  ASSERT_FALSE(!Result);
+  ASSERT_TRUE(!*Result);
+  std::string Value;
+  llvm::handleAllErrors(
+      (*Result).takeError(),
+      [&](const llvm::StringError &Error) { Value = Error.getMessage(); });
+  EXPECT_EQ(Value, "Error");
+}
+
+TEST_F(RefactoringActionRulesTest, ReturnInitiationDiagnostic) {
+  DiagOr<int> (*SelectionConstraint)(selection::SourceSelectionRange) =
+      [](selection::SourceSelectionRange) -> DiagOr<int> {
+    return DiagOr<int>(
+        StoredDiagnostic(DiagnosticsEngine::Error, 0, "Diagnostic"));
+  };
+  auto Rule = apply(
+      [](int) -> Expected<RefactoringResult> {
+        llvm::report_fatal_error("Should not run!");
+      },
+      selectionRequirement(SelectionConstraint));
+
+  RefactoringOperationController Operation(Context.Sources);
+  SourceLocation Cursor =
+      Context.Sources.getLocForStartOfFile(Context.Sources.getMainFileID());
+  Operation.setSelectionRange({Cursor, Cursor});
+  DiagOr<Expected<RefactoringResult>> Result = Rule->perform(Operation);
+
+  ASSERT_TRUE(!Result);
+  auto DiagOrNone = Result.getDiag();
+  ASSERT_FALSE(!DiagOrNone);
+  StoredDiagnostic Diag = *DiagOrNone;
+  EXPECT_EQ(Diag.getLevel(), DiagnosticsEngine::Error);
+  EXPECT_EQ(Diag.getID(), 0u);
+  EXPECT_EQ(Diag.getMessage(), "Diagnostic");
+}
+
+} // end anonymous namespace