Merge topic 'extract-cmLinkedTree'

4e5c70ab cmState: Extract a cmLinkedTree container adaptor.
7b9c7586 cmState: Group BuildsystemDirectory state together in a struct.
1b323949 cmState: Extend Snapshot concept with a SnapshotType.

4 files changed, 250 insertions, 88 deletions

diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt
index a7adb51..e8d5107 100644
--- a/Source/CMakeLists.txt
+++ b/Source/CMakeLists.txt
@@ -281,6 +281,7 @@ set(SRCS
   cmInstallTargetGenerator.cxx
   cmInstallDirectoryGenerator.h
   cmInstallDirectoryGenerator.cxx
+  cmLinkedTree.h
   cmListFileCache.cxx
   cmListFileCache.h
   cmListFileLexer.c
diff --git a/Source/cmLinkedTree.h b/Source/cmLinkedTree.h
new file mode 100644
index 0000000..d2339c4
--- /dev/null
+++ b/Source/cmLinkedTree.h
@@ -0,0 +1,164 @@
+/*============================================================================
+  CMake - Cross Platform Makefile Generator
+  Copyright 2015 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 cmLinkedTree_h
+#define cmLinkedTree_h
+
+#include "cmStandardIncludes.h"
+
+#include <assert.h>
+
+/**
+  @brief A adaptor for traversing a tree structure in a vector
+
+  This class is not intended to be wholly generic like a standard library
+  container adaptor.  Mostly it exists to facilitate code sharing for the
+  needs of the cmState.  For example, the Truncate() method is a specific
+  requirement of the cmState.
+
+  An empty cmLinkedTree provides a Root() method, and an Extend() method,
+  each of which return iterators.  A Tree can be built up by extending
+  from the root, and then extending from any other iterator.
+
+  An iterator resulting from this tree construction can be
+  forward-only-iterated toward the root.  Extending the tree never
+  invalidates existing iterators.
+ */
+template<typename T>
+class cmLinkedTree
+{
+  typedef typename std::vector<T>::size_type PositionType;
+  typedef T* PointerType;
+  typedef T& ReferenceType;
+public:
+  class iterator : public std::iterator<std::forward_iterator_tag, T>
+  {
+    friend class cmLinkedTree;
+    cmLinkedTree* Tree;
+
+    // The Position is always 'one past the end'.
+    PositionType Position;
+
+    iterator(cmLinkedTree* tree, PositionType pos)
+      : Tree(tree), Position(pos)
+    {
+
+    }
+
+  public:
+    iterator()
+      : Tree(0), Position(0)
+    {
+
+    }
+
+    void operator++()
+    {
+      assert(this->Tree);
+      assert(this->Tree->UpPositions.size() == this->Tree->Data.size());
+      assert(this->Position <= this->Tree->Data.size());
+      assert(this->Position > 0);
+      this->Position = this->Tree->UpPositions[this->Position - 1];
+    }
+
+    PointerType operator->() const
+    {
+      assert(this->Tree);
+      assert(this->Tree->UpPositions.size() == this->Tree->Data.size());
+      assert(this->Position <= this->Tree->Data.size());
+      assert(this->Position > 0);
+      return this->Tree->GetPointer(this->Position - 1);
+    }
+
+    PointerType operator->()
+    {
+      assert(this->Tree);
+      assert(this->Tree->UpPositions.size() == this->Tree->Data.size());
+      assert(this->Position <= this->Tree->Data.size());
+      assert(this->Position > 0);
+      return this->Tree->GetPointer(this->Position - 1);
+    }
+
+    bool operator==(iterator other) const
+    {
+      assert(this->Tree);
+      assert(this->Tree->UpPositions.size() == this->Tree->Data.size());
+      assert(this->Tree == other.Tree);
+      return this->Position == other.Position;
+    }
+
+    bool operator!=(iterator other) const
+    {
+      assert(this->Tree);
+      assert(this->Tree->UpPositions.size() == this->Tree->Data.size());
+      return !(*this == other);
+    }
+
+    bool IsValid() const
+    {
+      if (!this->Tree)
+        {
+        return false;
+        }
+      return this->Position <= this->Tree->Data.size();
+    }
+  };
+
+  iterator Root() const
+  {
+    return iterator(const_cast<cmLinkedTree*>(this), 0);
+  }
+
+  iterator Extend(iterator it)
+  {
+    return Extend_impl(it, T());
+  }
+
+  iterator Extend(iterator it, T t)
+  {
+    return Extend_impl(it, t);
+  }
+
+  iterator Truncate()
+  {
+    assert(this->UpPositions.size() > 0);
+    this->UpPositions.erase(this->UpPositions.begin() + 1,
+                            this->UpPositions.end());
+    assert(this->Data.size() > 0);
+    this->Data.erase(this->Data.begin() + 1, this->Data.end());
+    return iterator(this, 1);
+  }
+
+private:
+  T& GetReference(PositionType pos)
+  {
+    return this->Data[pos];
+  }
+
+  T* GetPointer(PositionType pos)
+  {
+    return &this->Data[pos];
+  }
+
+  iterator Extend_impl(iterator it, T t)
+  {
+    assert(this->UpPositions.size() == this->Data.size());
+    assert(it.Position <= this->UpPositions.size());
+    this->UpPositions.push_back(it.Position);
+    this->Data.push_back(t);
+    return iterator(this, this->UpPositions.size());
+  }
+
+  std::vector<T> Data;
+  std::vector<PositionType> UpPositions;
+};
+
+#endif
diff --git a/Source/cmState.cxx b/Source/cmState.cxx
index c6fb299..a2ebb24 100644
--- a/Source/cmState.cxx
+++ b/Source/cmState.cxx
@@ -18,6 +18,30 @@
 
 #include <assert.h>
 
+struct cmState::SnapshotDataType
+{
+  cmState::PositionType DirectoryParent;
+  cmState::SnapshotType SnapshotType;
+  cmLinkedTree<cmState::BuildsystemDirectoryStateType>::iterator
+                                                          BuildSystemDirectory;
+};
+
+struct cmState::BuildsystemDirectoryStateType
+{
+  std::string Location;
+  std::string OutputLocation;
+
+  std::vector<std::string> CurrentSourceDirectoryComponents;
+  std::vector<std::string> CurrentBinaryDirectoryComponents;
+  // The top-most directories for relative path conversion.  Both the
+  // source and destination location of a relative path conversion
+  // must be underneath one of these directories (both under source or
+  // both under binary) in order for the relative path to be evaluated
+  // safely by the build tools.
+  std::string RelativePathTopSource;
+  std::string RelativePathTopBinary;
+};
+
 cmState::cmState(cmake* cm)
   : CMakeInstance(cm),
     IsInTryCompile(false),
@@ -200,29 +224,8 @@ void cmState::Reset()
   this->GlobalProperties.clear();
   this->PropertyDefinitions.clear();
 
-  assert(this->Locations.size() > 0);
-  assert(this->OutputLocations.size() > 0);
-  assert(this->ParentPositions.size() > 0);
-  assert(this->CurrentSourceDirectoryComponents.size() > 0);
-  assert(this->CurrentBinaryDirectoryComponents.size() > 0);
-  assert(this->RelativePathTopSource.size() > 0);
-  assert(this->RelativePathTopBinary.size() > 0);
-
-  this->Locations.erase(this->Locations.begin() + 1, this->Locations.end());
-  this->OutputLocations.erase(this->OutputLocations.begin() + 1,
-                              this->OutputLocations.end());
-  this->ParentPositions.erase(this->ParentPositions.begin() + 1,
-                              this->ParentPositions.end());
-  this->CurrentSourceDirectoryComponents.erase(
-        this->CurrentSourceDirectoryComponents.begin() + 1,
-        this->CurrentSourceDirectoryComponents.end());
-  this->CurrentBinaryDirectoryComponents.erase(
-        this->CurrentBinaryDirectoryComponents.begin() + 1,
-        this->CurrentBinaryDirectoryComponents.end());
-  this->RelativePathTopSource.erase(this->RelativePathTopSource.begin() + 1,
-                                    this->RelativePathTopSource.end());
-  this->RelativePathTopBinary.erase(this->RelativePathTopBinary.begin() + 1,
-                                    this->RelativePathTopBinary.end());
+  this->BuildsystemDirectory.Truncate();
+  this->SnapshotData.Truncate();
 
   this->DefineProperty
     ("RULE_LAUNCH_COMPILE", cmProperty::DIRECTORY,
@@ -612,7 +615,7 @@ void cmState::Snapshot::ComputeRelativePathTopSource()
       result = currentSource;
       }
     }
-  this->State->RelativePathTopSource[this->Position] = result;
+  this->Position->BuildSystemDirectory->RelativePathTopSource = result;
 }
 
 void cmState::Snapshot::ComputeRelativePathTopBinary()
@@ -651,24 +654,21 @@ void cmState::Snapshot::ComputeRelativePathTopBinary()
   // is a network path.
   if(result.size() < 2 || result.substr(0, 2) != "//")
     {
-    this->State->RelativePathTopBinary[this->Position] = result;
+    this->Position->BuildSystemDirectory->RelativePathTopBinary = result;
     }
   else
     {
-    this->State->RelativePathTopBinary[this->Position] = "";
+    this->Position->BuildSystemDirectory->RelativePathTopBinary = "";
     }
 }
 
 cmState::Snapshot cmState::CreateBaseSnapshot()
 {
-  PositionType pos = 0;
-  this->ParentPositions.push_back(pos);
-  this->Locations.resize(1);
-  this->OutputLocations.resize(1);
-  this->CurrentSourceDirectoryComponents.resize(1);
-  this->CurrentBinaryDirectoryComponents.resize(1);
-  this->RelativePathTopSource.resize(1);
-  this->RelativePathTopBinary.resize(1);
+  PositionType pos = this->SnapshotData.Extend(this->SnapshotData.Root());
+  pos->DirectoryParent = this->SnapshotData.Root();
+  pos->SnapshotType = BuildsystemDirectoryType;
+  pos->BuildSystemDirectory =
+      this->BuildsystemDirectory.Extend(this->BuildsystemDirectory.Root());
   return cmState::Snapshot(this, pos);
 }
 
@@ -676,16 +676,12 @@ cmState::Snapshot
 cmState::CreateBuildsystemDirectorySnapshot(Snapshot originSnapshot)
 {
   assert(originSnapshot.IsValid());
-  PositionType pos = this->ParentPositions.size();
-  this->ParentPositions.push_back(originSnapshot.Position);
-  this->Locations.resize(this->Locations.size() + 1);
-  this->OutputLocations.resize(this->OutputLocations.size() + 1);
-  this->CurrentSourceDirectoryComponents.resize(
-      this->CurrentSourceDirectoryComponents.size() + 1);
-  this->CurrentBinaryDirectoryComponents.resize(
-      this->CurrentBinaryDirectoryComponents.size() + 1);
-  this->RelativePathTopSource.resize(this->RelativePathTopSource.size() + 1);
-  this->RelativePathTopBinary.resize(this->RelativePathTopBinary.size() + 1);
+  PositionType pos = this->SnapshotData.Extend(originSnapshot.Position);
+  pos->DirectoryParent = originSnapshot.Position;
+  pos->SnapshotType = BuildsystemDirectoryType;
+  pos->BuildSystemDirectory =
+      this->BuildsystemDirectory.Extend(
+        originSnapshot.Position->BuildSystemDirectory);
   return cmState::Snapshot(this, pos);
 }
 
@@ -698,92 +694,94 @@ cmState::Snapshot::Snapshot(cmState* state, PositionType position)
 
 const char* cmState::Snapshot::GetCurrentSourceDirectory() const
 {
-  return this->State->Locations[this->Position].c_str();
+  return this->Position->BuildSystemDirectory->Location.c_str();
 }
 
 void cmState::Snapshot::SetCurrentSourceDirectory(std::string const& dir)
 {
   assert(this->State);
-  assert(this->State->Locations.size() > this->Position);
-  this->State->Locations[this->Position] = dir;
-  cmSystemTools::ConvertToUnixSlashes(
-      this->State->Locations[this->Position]);
-  this->State->Locations[this->Position] =
-    cmSystemTools::CollapseFullPath(this->State->Locations[this->Position]);
+  std::string& loc = this->Position->BuildSystemDirectory->Location;
+  loc = dir;
+  cmSystemTools::ConvertToUnixSlashes(loc);
+  loc = cmSystemTools::CollapseFullPath(loc);
 
   cmSystemTools::SplitPath(
-      this->State->Locations[this->Position],
-      this->State->CurrentSourceDirectoryComponents[this->Position]);
+      loc,
+      this->Position->BuildSystemDirectory->CurrentSourceDirectoryComponents);
   this->ComputeRelativePathTopSource();
 }
 
 const char* cmState::Snapshot::GetCurrentBinaryDirectory() const
 {
-  return this->State->OutputLocations[this->Position].c_str();
+  return this->Position->BuildSystemDirectory->OutputLocation.c_str();
 }
 
 void cmState::Snapshot::SetCurrentBinaryDirectory(std::string const& dir)
 {
-  assert(this->State->OutputLocations.size() > this->Position);
-  this->State->OutputLocations[this->Position] = dir;
-  cmSystemTools::ConvertToUnixSlashes(
-      this->State->OutputLocations[this->Position]);
-  this->State->OutputLocations[this->Position] =
-    cmSystemTools::CollapseFullPath(
-        this->State->OutputLocations[this->Position]);
+  std::string& loc = this->Position->BuildSystemDirectory->OutputLocation;
+  loc = dir;
+  cmSystemTools::ConvertToUnixSlashes(loc);
+  loc = cmSystemTools::CollapseFullPath(loc);
 
   cmSystemTools::SplitPath(
-      this->State->OutputLocations[this->Position],
-      this->State->CurrentBinaryDirectoryComponents[this->Position]);
+      loc,
+      this->Position->BuildSystemDirectory->CurrentBinaryDirectoryComponents);
   this->ComputeRelativePathTopBinary();
 }
 
 std::vector<std::string> const&
 cmState::Snapshot::GetCurrentSourceDirectoryComponents()
 {
-  return this->State->CurrentSourceDirectoryComponents[this->Position];
+  return this->Position->BuildSystemDirectory
+      ->CurrentSourceDirectoryComponents;
 }
 
 std::vector<std::string> const&
 cmState::Snapshot::GetCurrentBinaryDirectoryComponents()
 {
-  return this->State->CurrentBinaryDirectoryComponents[this->Position];
+  return this->Position->BuildSystemDirectory
+      ->CurrentBinaryDirectoryComponents;
 }
 
 const char* cmState::Snapshot::GetRelativePathTopSource() const
 {
-  return this->State->RelativePathTopSource[this->Position].c_str();
+  return this->Position->BuildSystemDirectory->RelativePathTopSource.c_str();
 }
 
 const char* cmState::Snapshot::GetRelativePathTopBinary() const
 {
-  return this->State->RelativePathTopBinary[this->Position].c_str();
+  return this->Position->BuildSystemDirectory->RelativePathTopBinary.c_str();
 }
 
 void cmState::Snapshot::SetRelativePathTopSource(const char* dir)
 {
-  this->State->RelativePathTopSource[this->Position] = dir;
+  this->Position->BuildSystemDirectory->RelativePathTopSource = dir;
 }
 
 void cmState::Snapshot::SetRelativePathTopBinary(const char* dir)
 {
-  this->State->RelativePathTopBinary[this->Position] = dir;
+  this->Position->BuildSystemDirectory->RelativePathTopBinary = dir;
 }
 
 bool cmState::Snapshot::IsValid() const
 {
-  return this->State ? true : false;
+  return this->State && this->Position.IsValid()
+      ? this->Position != this->State->SnapshotData.Root()
+      : false;
 }
 
 cmState::Snapshot cmState::Snapshot::GetBuildsystemDirectoryParent() const
 {
   Snapshot snapshot;
-  if (!this->State || this->Position == 0)
+  if (!this->State || this->Position == this->State->SnapshotData.Root())
     {
     return snapshot;
     }
-  PositionType parentPos = this->State->ParentPositions[this->Position];
-  snapshot = Snapshot(this->State, parentPos);
+  PositionType parentPos = this->Position->DirectoryParent;
+  if (parentPos != this->State->SnapshotData.Root())
+    {
+    snapshot = Snapshot(this->State, parentPos);
+    }
 
   return snapshot;
 }
diff --git a/Source/cmState.h b/Source/cmState.h
index 60b024f..1411e2f 100644
--- a/Source/cmState.h
+++ b/Source/cmState.h
@@ -15,21 +15,28 @@
 #include "cmStandardIncludes.h"
 #include "cmPropertyDefinitionMap.h"
 #include "cmPropertyMap.h"
+#include "cmLinkedTree.h"
 
 class cmake;
 class cmCommand;
 
 class cmState
 {
-  typedef std::vector<std::string>::size_type PositionType;
+  struct SnapshotDataType;
+  typedef cmLinkedTree<SnapshotDataType>::iterator PositionType;
   friend class Snapshot;
 public:
   cmState(cmake* cm);
   ~cmState();
 
+  enum SnapshotType
+  {
+    BuildsystemDirectoryType
+  };
+
   class Snapshot {
   public:
-    Snapshot(cmState* state = 0, PositionType position = 0);
+    Snapshot(cmState* state = 0, PositionType position = PositionType());
 
     const char* GetCurrentSourceDirectory() const;
     void SetCurrentSourceDirectory(std::string const& dir);
@@ -158,19 +165,11 @@ private:
   std::map<std::string, cmCommand*> Commands;
   cmPropertyMap GlobalProperties;
   cmake* CMakeInstance;
-  std::vector<std::string> Locations;
-  std::vector<std::string> OutputLocations;
-  std::vector<PositionType> ParentPositions;
-
-  std::vector<std::vector<std::string> > CurrentSourceDirectoryComponents;
-  std::vector<std::vector<std::string> > CurrentBinaryDirectoryComponents;
-  // The top-most directories for relative path conversion.  Both the
-  // source and destination location of a relative path conversion
-  // must be underneath one of these directories (both under source or
-  // both under binary) in order for the relative path to be evaluated
-  // safely by the build tools.
-  std::vector<std::string> RelativePathTopSource;
-  std::vector<std::string> RelativePathTopBinary;
+
+  struct BuildsystemDirectoryStateType;
+  cmLinkedTree<BuildsystemDirectoryStateType> BuildsystemDirectory;
+
+  cmLinkedTree<SnapshotDataType> SnapshotData;
 
   std::vector<std::string> SourceDirectoryComponents;
   std::vector<std::string> BinaryDirectoryComponents;