Add API to check that dependent target properties form a DAG.

Initially this will only be used to check for self-references, but
can be extended to check for cycles when chaining properties of other
targets.

7 files changed, 203 insertions, 26 deletions

diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt
index 354f123..5a3e7d1 100644
--- a/Source/CMakeLists.txt
+++ b/Source/CMakeLists.txt
@@ -183,6 +183,8 @@ set(SRCS
   cmFileTimeComparison.cxx
   cmFileTimeComparison.h
   cmGeneratedFileStream.cxx
+  cmGeneratorExpressionDAGChecker.cxx
+  cmGeneratorExpressionDAGChecker.h
   cmGeneratorExpressionEvaluator.cxx
   cmGeneratorExpressionEvaluator.h
   cmGeneratorExpressionLexer.cxx
diff --git a/Source/cmGeneratorExpression.cxx b/Source/cmGeneratorExpression.cxx
index 55a1e3e..3f8e962 100644
--- a/Source/cmGeneratorExpression.cxx
+++ b/Source/cmGeneratorExpression.cxx
@@ -19,6 +19,7 @@
 #include "cmGeneratorExpressionEvaluator.h"
 #include "cmGeneratorExpressionLexer.h"
 #include "cmGeneratorExpressionParser.h"
+#include "cmGeneratorExpressionDAGChecker.h"
 
 //----------------------------------------------------------------------------
 cmGeneratorExpression::cmGeneratorExpression(
@@ -66,7 +67,8 @@ cmGeneratorExpression::~cmGeneratorExpression()
 //----------------------------------------------------------------------------
 const char *cmCompiledGeneratorExpression::Evaluate(
   cmMakefile* mf, const char* config, bool quiet,
-  cmGeneratorTarget *target) const
+  cmGeneratorTarget *target,
+  cmGeneratorExpressionDAGChecker *dagChecker) const
 {
   if (!this->NeedsParsing)
     {
@@ -90,7 +92,7 @@ const char *cmCompiledGeneratorExpression::Evaluate(
 
   for ( ; it != end; ++it)
     {
-    this->Output += (*it)->Evaluate(&context);
+    this->Output += (*it)->Evaluate(&context, dagChecker);
     if (context.HadError)
       {
       this->Output = "";
diff --git a/Source/cmGeneratorExpression.h b/Source/cmGeneratorExpression.h
index fdf45a1..d37ce97 100644
--- a/Source/cmGeneratorExpression.h
+++ b/Source/cmGeneratorExpression.h
@@ -25,6 +25,7 @@ class cmMakefile;
 class cmListFileBacktrace;
 
 struct cmGeneratorExpressionEvaluator;
+struct cmGeneratorExpressionDAGChecker;
 
 class cmCompiledGeneratorExpression;
 
@@ -60,7 +61,8 @@ class cmCompiledGeneratorExpression
 public:
   const char* Evaluate(cmMakefile* mf, const char* config,
                        bool quiet = false,
-                       cmGeneratorTarget *target = 0) const;
+                       cmGeneratorTarget *target = 0,
+                       cmGeneratorExpressionDAGChecker *dagChecker = 0) const;
 
   /** Get set of targets found during evaluations.  */
   std::set<cmTarget*> const& GetTargets() const
diff --git a/Source/cmGeneratorExpressionDAGChecker.cxx b/Source/cmGeneratorExpressionDAGChecker.cxx
new file mode 100644
index 0000000..bfb0ddf
--- /dev/null
+++ b/Source/cmGeneratorExpressionDAGChecker.cxx
@@ -0,0 +1,106 @@
+/*============================================================================
+  CMake - Cross Platform Makefile Generator
+  Copyright 2012 Stephen Kelly <steveire@gmail.com>
+
+  Distributed under the OSI-approved BSD License (the "License");
+  see accompanying file Copyright.txt for details.
+
+  This software is distributed WITHOUT ANY WARRANTY; without even the
+  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+  See the License for more information.
+============================================================================*/
+
+#include "cmGeneratorExpressionDAGChecker.h"
+
+#include "cmMakefile.h"
+
+//----------------------------------------------------------------------------
+cmGeneratorExpressionDAGChecker::cmGeneratorExpressionDAGChecker(
+                const cmListFileBacktrace &backtrace,
+                const std::string &target,
+                const std::string &property,
+                const GeneratorExpressionContent *content,
+                cmGeneratorExpressionDAGChecker *parent)
+  : Parent(parent), Target(target), Property(property),
+    Content(content), Backtrace(backtrace)
+{
+  this->IsDAG = this->isDAG();
+}
+
+//----------------------------------------------------------------------------
+bool cmGeneratorExpressionDAGChecker::check() const
+{
+  return this->IsDAG;
+}
+
+//----------------------------------------------------------------------------
+void cmGeneratorExpressionDAGChecker::reportError(
+                  cmGeneratorExpressionContext *context,
+                  const std::string &expr)
+{
+  if (this->IsDAG)
+    {
+    return;
+    }
+
+  context->HadError = true;
+  if (context->Quiet)
+    {
+    return;
+    }
+
+  const cmGeneratorExpressionDAGChecker *parent = this->Parent;
+
+  if (parent && !parent->Parent)
+    {
+    cmOStringStream e;
+    e << "Error evaluating generator expression:\n"
+      << "  " << expr << "\n"
+      << "Self reference on target \""
+      << context->Target->GetName() << "\".\n";
+    context->Makefile->GetCMakeInstance()
+      ->IssueMessage(cmake::FATAL_ERROR, e.str().c_str(),
+                      parent->Backtrace);
+    return;
+    }
+
+  {
+  cmOStringStream e;
+  e << "Error evaluating generator expression:\n"
+    << "  " << expr << "\n"
+    << "Dependency loop found.";
+  context->Makefile->GetCMakeInstance()
+    ->IssueMessage(cmake::FATAL_ERROR, e.str().c_str(),
+                    context->Backtrace);
+  }
+
+  int loopStep = 1;
+  while (parent)
+    {
+    cmOStringStream e;
+    e << "Loop step " << loopStep << "\n"
+      << "  "
+      << (parent->Content ? parent->Content->GetOriginalExpression() : expr)
+      << "\n";
+    context->Makefile->GetCMakeInstance()
+      ->IssueMessage(cmake::FATAL_ERROR, e.str().c_str(),
+                      parent->Backtrace);
+    parent = parent->Parent;
+    ++loopStep;
+    }
+}
+
+//----------------------------------------------------------------------------
+bool cmGeneratorExpressionDAGChecker::isDAG() const
+{
+  const cmGeneratorExpressionDAGChecker *parent = this->Parent;
+  while (parent)
+    {
+    if (this->Target == parent->Target && this->Property == parent->Property)
+      {
+      return false;
+      }
+    parent = parent->Parent;
+    }
+  return true;
+}
diff --git a/Source/cmGeneratorExpressionDAGChecker.h b/Source/cmGeneratorExpressionDAGChecker.h
new file mode 100644
index 0000000..ffc84f8
--- /dev/null
+++ b/Source/cmGeneratorExpressionDAGChecker.h
@@ -0,0 +1,44 @@
+/*============================================================================
+  CMake - Cross Platform Makefile Generator
+  Copyright 2012 Stephen Kelly <steveire@gmail.com>
+
+  Distributed under the OSI-approved BSD License (the "License");
+  see accompanying file Copyright.txt for details.
+
+  This software is distributed WITHOUT ANY WARRANTY; without even the
+  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+  See the License for more information.
+============================================================================*/
+#ifndef cmGeneratorExpressionDAGChecker_h
+#define cmGeneratorExpressionDAGChecker_h
+
+#include "cmStandardIncludes.h"
+
+#include "cmGeneratorExpressionEvaluator.h"
+
+//----------------------------------------------------------------------------
+struct cmGeneratorExpressionDAGChecker
+{
+  cmGeneratorExpressionDAGChecker(const cmListFileBacktrace &backtrace,
+                                  const std::string &target,
+                                  const std::string &property,
+                                  const GeneratorExpressionContent *content,
+                                  cmGeneratorExpressionDAGChecker *parent);
+
+  bool check() const;
+
+  void reportError(cmGeneratorExpressionContext *context,
+                   const std::string &expr);
+private:
+  bool isDAG() const;
+
+private:
+  const cmGeneratorExpressionDAGChecker * const Parent;
+  const std::string Target;
+  const std::string Property;
+  const GeneratorExpressionContent * const Content;
+  const cmListFileBacktrace Backtrace;
+  bool IsDAG;
+};
+
+#endif
diff --git a/Source/cmGeneratorExpressionEvaluator.cxx b/Source/cmGeneratorExpressionEvaluator.cxx
index 1583270..a9e28c3 100644
--- a/Source/cmGeneratorExpressionEvaluator.cxx
+++ b/Source/cmGeneratorExpressionEvaluator.cxx
@@ -13,6 +13,7 @@
 
 #include "cmGeneratorExpressionEvaluator.h"
 #include "cmGeneratorExpressionParser.h"
+#include "cmGeneratorExpressionDAGChecker.h"
 
 //----------------------------------------------------------------------------
 static void reportError(cmGeneratorExpressionContext *context,
@@ -47,7 +48,8 @@ struct cmGeneratorExpressionNode
 
   virtual std::string Evaluate(const std::vector<std::string> &parameters,
                                cmGeneratorExpressionContext *context,
-                               const GeneratorExpressionContent *content
+                               const GeneratorExpressionContent *content,
+                               cmGeneratorExpressionDAGChecker *dagChecker
                               ) const = 0;
 };
 
@@ -60,7 +62,8 @@ static const struct ZeroNode : public cmGeneratorExpressionNode
 
   std::string Evaluate(const std::vector<std::string> &,
                        cmGeneratorExpressionContext *,
-                       const GeneratorExpressionContent *) const
+                       const GeneratorExpressionContent *,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     // Unreachable
     return std::string();
@@ -76,7 +79,8 @@ static const struct OneNode : public cmGeneratorExpressionNode
 
   std::string Evaluate(const std::vector<std::string> &,
                        cmGeneratorExpressionContext *,
-                       const GeneratorExpressionContent *) const
+                       const GeneratorExpressionContent *,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     // Unreachable
     return std::string();
@@ -93,7 +97,8 @@ static const struct OP ## Node : public cmGeneratorExpressionNode \
  \
   std::string Evaluate(const std::vector<std::string> &parameters, \
                        cmGeneratorExpressionContext *context, \
-                       const GeneratorExpressionContent *content) const \
+                       const GeneratorExpressionContent *content, \
+                       cmGeneratorExpressionDAGChecker *) const \
   { \
     std::vector<std::string>::const_iterator it = parameters.begin(); \
     const std::vector<std::string>::const_iterator end = parameters.end(); \
@@ -123,9 +128,11 @@ BOOLEAN_OP_NODE(orNode, OR, 0, 1)
 static const struct NotNode : public cmGeneratorExpressionNode
 {
   NotNode() {}
+
   std::string Evaluate(const std::vector<std::string> &parameters,
                        cmGeneratorExpressionContext *context,
-                       const GeneratorExpressionContent *content) const
+                       const GeneratorExpressionContent *content,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     if (*parameters.begin() != "0" && *parameters.begin() != "1")
       {
@@ -146,7 +153,8 @@ static const struct BoolNode : public cmGeneratorExpressionNode
 
   std::string Evaluate(const std::vector<std::string> &parameters,
                        cmGeneratorExpressionContext *,
-                       const GeneratorExpressionContent *) const
+                       const GeneratorExpressionContent *,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     return !cmSystemTools::IsOff(parameters.begin()->c_str()) ? "1" : "0";
   }
@@ -161,7 +169,8 @@ static const struct StrEqualNode : public cmGeneratorExpressionNode
 
   std::string Evaluate(const std::vector<std::string> &parameters,
                        cmGeneratorExpressionContext *,
-                       const GeneratorExpressionContent *) const
+                       const GeneratorExpressionContent *,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     return *parameters.begin() == parameters.at(1) ? "1" : "0";
   }
@@ -176,7 +185,8 @@ static const struct Angle_RNode : public cmGeneratorExpressionNode
 
   std::string Evaluate(const std::vector<std::string> &,
                        cmGeneratorExpressionContext *,
-                       const GeneratorExpressionContent *) const
+                       const GeneratorExpressionContent *,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     return ">";
   }
@@ -191,7 +201,8 @@ static const struct CommaNode : public cmGeneratorExpressionNode
 
   std::string Evaluate(const std::vector<std::string> &,
                        cmGeneratorExpressionContext *,
-                       const GeneratorExpressionContent *) const
+                       const GeneratorExpressionContent *,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     return ",";
   }
@@ -201,11 +212,13 @@ static const struct CommaNode : public cmGeneratorExpressionNode
 static const struct ConfigurationNode : public cmGeneratorExpressionNode
 {
   ConfigurationNode() {}
+
   virtual int NumExpectedParameters() const { return 0; }
 
   std::string Evaluate(const std::vector<std::string> &,
                        cmGeneratorExpressionContext *context,
-                       const GeneratorExpressionContent *) const
+                       const GeneratorExpressionContent *,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     return context->Config ? context->Config : "";
   }
@@ -220,7 +233,8 @@ static const struct ConfigurationTestNode : public cmGeneratorExpressionNode
 
   std::string Evaluate(const std::vector<std::string> &parameters,
                        cmGeneratorExpressionContext *context,
-                       const GeneratorExpressionContent *content) const
+                       const GeneratorExpressionContent *content,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     if (!context->Config)
       {
@@ -240,7 +254,7 @@ static const struct ConfigurationTestNode : public cmGeneratorExpressionNode
 } configurationTestNode;
 
 //----------------------------------------------------------------------------
-static const struct TargetPropertyNode: public cmGeneratorExpressionNode
+static const struct TargetPropertyNode : public cmGeneratorExpressionNode
 {
   TargetPropertyNode() {}
 
@@ -249,7 +263,8 @@ static const struct TargetPropertyNode: public cmGeneratorExpressionNode
 
   std::string Evaluate(const std::vector<std::string> &parameters,
                        cmGeneratorExpressionContext *context,
-                       const GeneratorExpressionContent *content) const
+                       const GeneratorExpressionContent *content,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     if (parameters.size() != 1 && parameters.size() != 2)
       {
@@ -393,7 +408,8 @@ struct TargetFilesystemArtifact : public cmGeneratorExpressionNode
 
   std::string Evaluate(const std::vector<std::string> &parameters,
                        cmGeneratorExpressionContext *context,
-                       const GeneratorExpressionContent *content) const
+                       const GeneratorExpressionContent *content,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     // Lookup the referenced target.
     std::string name = *parameters.begin();
@@ -523,7 +539,8 @@ std::string GeneratorExpressionContent::GetOriginalExpression() const
 
 //----------------------------------------------------------------------------
 std::string GeneratorExpressionContent::Evaluate(
-                                  cmGeneratorExpressionContext *context) const
+                            cmGeneratorExpressionContext *context,
+                            cmGeneratorExpressionDAGChecker *dagChecker) const
 {
   std::string identifier;
   {
@@ -533,7 +550,7 @@ std::string GeneratorExpressionContent::Evaluate(
                                           = this->IdentifierChildren.end();
   for ( ; it != end; ++it)
     {
-    identifier += (*it)->Evaluate(context);
+    identifier += (*it)->Evaluate(context, dagChecker);
     if (context->HadError)
       {
       return std::string();
@@ -576,7 +593,7 @@ std::string GeneratorExpressionContent::Evaluate(
                                                                 = pit->end();
       for ( ; it != end; ++it)
         {
-        result += (*it)->Evaluate(context);
+        result += (*it)->Evaluate(context, dagChecker);
         if (context->HadError)
           {
           return std::string();
@@ -602,7 +619,7 @@ std::string GeneratorExpressionContent::Evaluate(
                                                               pit->end();
     for ( ; it != end; ++it)
       {
-      parameter += (*it)->Evaluate(context);
+      parameter += (*it)->Evaluate(context, dagChecker);
       if (context->HadError)
         {
         return std::string();
@@ -645,7 +662,7 @@ std::string GeneratorExpressionContent::Evaluate(
     return std::string();
     }
 
-  return node->Evaluate(parameters, context, this);
+  return node->Evaluate(parameters, context, this, dagChecker);
 }
 
 //----------------------------------------------------------------------------
diff --git a/Source/cmGeneratorExpressionEvaluator.h b/Source/cmGeneratorExpressionEvaluator.h
index 4086e8e..04a2acd 100644
--- a/Source/cmGeneratorExpressionEvaluator.h
+++ b/Source/cmGeneratorExpressionEvaluator.h
@@ -32,6 +32,8 @@ struct cmGeneratorExpressionContext
   bool HadError;
 };
 
+struct cmGeneratorExpressionDAGChecker;
+
 //----------------------------------------------------------------------------
 struct cmGeneratorExpressionEvaluator
 {
@@ -46,8 +48,8 @@ struct cmGeneratorExpressionEvaluator
 
   virtual Type GetType() const = 0;
 
-  virtual std::string Evaluate(cmGeneratorExpressionContext *context
-                              ) const = 0;
+  virtual std::string Evaluate(cmGeneratorExpressionContext *context,
+                              cmGeneratorExpressionDAGChecker *) const = 0;
 
 private:
   cmGeneratorExpressionEvaluator(const cmGeneratorExpressionEvaluator &);
@@ -62,7 +64,8 @@ struct TextContent : public cmGeneratorExpressionEvaluator
 
   }
 
-  std::string Evaluate(cmGeneratorExpressionContext *) const
+  std::string Evaluate(cmGeneratorExpressionContext *,
+                       cmGeneratorExpressionDAGChecker *) const
   {
     return std::string(this->Content, this->Length);
   }
@@ -107,7 +110,8 @@ struct GeneratorExpressionContent : public cmGeneratorExpressionEvaluator
     return cmGeneratorExpressionEvaluator::Generator;
   }
 
-  std::string Evaluate(cmGeneratorExpressionContext *context) const;
+  std::string Evaluate(cmGeneratorExpressionContext *context,
+                       cmGeneratorExpressionDAGChecker *) const;
 
   std::string GetOriginalExpression() const;