Revamp the SourceManager to separate the representation of parsed

source locations from source locations loaded from an AST/PCH file.

Previously, loading an AST/PCH file involved carefully pre-allocating
space at the beginning of the source manager for the source locations
and FileIDs that correspond to the prefix, and then appending the
source locations/FileIDs used for parsing the remaining translation
unit. This design forced us into loading PCH files early, as a prefix,
whic has become a rather significant limitation.

This patch splits the SourceManager space into two parts: for source
location "addresses", the lower values (growing upward) are used to
describe parsed code, while upper values (growing downward) are used
for source locations loaded from AST/PCH files. Similarly, positive
FileIDs are used to describe parsed code while negative FileIDs are
used to file/macro locations loaded from AST/PCH files. As a result,
we can load PCH/AST files even during parsing, making various
improvemnts in the future possible, e.g., teaching #include <foo.h> to
look for and load <foo.h.gch> if it happens to be already available.

This patch was originally written by Sebastian Redl, then brought
forward to the modern age by Jonathan Turner, and finally
polished/finished by me to be committed.




git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@135484 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 90 insertions, 0 deletions

diff --git a/include/clang/Serialization/ContinuousRangeMap.h b/include/clang/Serialization/ContinuousRangeMap.h
new file mode 100644
index 0000000000..2a27b9115b
--- /dev/null
+++ b/include/clang/Serialization/ContinuousRangeMap.h
@@ -0,0 +1,90 @@
+//===--- ContinuousRangeMap.h - Map with int range as key -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the ContinuousRangeMap class, which is a highly
+//  specialized container used by serialization.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUS_RANGE_MAP_H
+#define LLVM_CLANG_SERIALIZATION_CONTINUOUS_RANGE_MAP_H
+
+#include "llvm/ADT/SmallVector.h"
+#include <algorithm>
+#include <utility>
+
+namespace clang {
+
+/// \brief A map from continuous integer ranges to some value, with a very
+/// specialized interface.
+///
+/// CRM maps from integer ranges to values. The ranges are continuous, i.e.
+/// where one ends, the next one begins. So if the map contains the stops I0-3,
+/// the first range is from I0 to I1, the second from I1 to I2, the third from
+/// I2 to I3 and the last from I3 to infinity.
+///
+/// Ranges must be inserted in order. Inserting a new stop I4 into the map will
+/// shrink the fourth range to I3 to I4 and add the new range I4 to inf.
+template <typename Int, typename V, unsigned InitialCapacity>
+class ContinuousRangeMap {
+public:
+  typedef std::pair<const Int, V> value_type;
+  typedef value_type &reference;
+  typedef const value_type &const_reference;
+  typedef value_type *pointer;
+  typedef const value_type *const_pointer;
+
+private:
+  typedef llvm::SmallVector<value_type, InitialCapacity> Representation;
+  Representation Rep;
+
+  struct Compare {
+    bool operator ()(const_reference L, Int R) const {
+      return L.first < R;
+    }
+    bool operator ()(Int L, const_reference R) const {
+      return L < R.first;
+    }
+  };
+
+public:
+  void insert(const value_type &Val) {
+    assert((Rep.empty() || Rep.back().first < Val.first) &&
+           "Must insert keys in order.");
+    Rep.push_back(Val);
+  }
+
+  typedef typename Representation::iterator iterator;
+  typedef typename Representation::const_iterator const_iterator;
+
+  iterator begin() { return Rep.begin(); }
+  iterator end() { return Rep.end(); }
+  const_iterator begin() const { return Rep.begin(); }
+  const_iterator end() const { return Rep.end(); }
+
+  iterator find(Int K) {
+    iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare());
+    // I points to the first entry with a key > K, which is the range that
+    // follows the one containing K.
+    if (I == Rep.begin())
+      return Rep.end();
+    --I;
+    return I;
+  }
+  const_iterator find(Int K) const {
+    return const_cast<ContinuousRangeMap*>(this)->find(K);
+  }
+
+  reference back() { return Rep.back(); }
+  const_reference back() const { return Rep.back(); }
+};
+
+}
+
+#endif