GN: Makes GN output deterministic

tools/gn/pointer_set.h

Index: tools/gn/pointer_set.h
diff --git a/tools/gn/pointer_set.h b/tools/gn/pointer_set.h
new file mode 100644
index 0000000000000000000000000000000000000000..826dc3469428123f0724b28211d838fe2b589085
--- /dev/null
+++ b/tools/gn/pointer_set.h
@@ -0,0 +1,130 @@
+// Copyright (c) 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef TOOLS_GN_POINTER_SET_H_
+#define TOOLS_GN_POINTER_SET_H_
+
+#include <functional>
+#include <set>
+
+namespace internal {
+
+// Comparator that dereferences the pointers before comparing them.
+template <typename T, typename Comparator>
+class DereferenceComparator {

[mithro-old, 2015/12/03 05:20:31]

Does something like this already exist in stl at all? It feels like it might?

[Zachary Forman, 2015/12/03 07:27:02]

Nope. Which is a shame as it's sometimes useful.

+ public:
+  // Constructs a DereferenceComparator that uses the provided comparator.
+  DereferenceComparator(Comparator comparator) : comparator(comparator) {}
+
+  // Compares the values pointed to by a and b with the comparator.
+  bool operator()(const T* a, const T* b) const { return comparator(*a, *b); }
+
+ private:
+  Comparator comparator;
+};
+
+}  // namespace internal
+
+// A set of pointers that are ordered by what they point at.
+// Takes the type that is pointed to as its first template parameter,
+// and optionally a second template parameter to define the ordering,
+// which is - by default - the class's operator<.
+// The comparator should be default constructible.
+// In most ways, matches the interface of a std::set.
+template <typename T, typename Comparator = std::less<T>>

[mithro-old, 2015/12/03 05:20:31]

Do we actually need a full wrapper class here? Could we get away with a
templated typedef or macro?

Do we need this to be templated? The only type we seem to use is a `const
Target*` object. Should we have a TargetPtrSet type?

[Zachary Forman, 2015/12/03 07:27:02]

Yep - I've factored it down to a much smaller thing. I think templating makes
sense given my rewrite,
if only because std::set is also templated. I'd not typedef to TargetPtrSet;
callers either used std::set or typedef'd
to something else themselves.

+class PointerSet {
+ public:
+  // Convenience typedefs.
+  typedef internal::DereferenceComparator<T, Comparator> DereferenceComparator;
+  typedef std::set<T*, DereferenceComparator> Set;
+  typedef typename Set::iterator iterator;
+  typedef typename Set::const_iterator const_iterator;
+
+  explicit PointerSet(const Comparator& comparator = Comparator())
+      : set_(comparator) {}
+
+  template <typename InputIterator>
+  PointerSet(InputIterator first,
+             InputIterator last,
+             const Comparator& comparator = Comparator())
+      : set_(first, last, comparator) {}
+
+  PointerSet(const PointerSet& set) : set_(set.set()) {}
+
+  PointerSet(PointerSet&& set) : set_(set.set()) {}
+
+  const Set& set() const { return set_; }
+  Set&& set() { return std::move(set_); }
+
+  // Forward most of the std::set's methods.
+  const_iterator cbegin() const { return set_.cbegin(); }
+  const_iterator begin() const { return set_.cbegin(); }
+  iterator begin() { return set_.begin(); }
+  const_iterator cend() const { return set_.cend(); }
+  const_iterator end() const { return set_.cend(); }
+  iterator end() { return set_.end(); }
+  const_iterator crbegin() const { return set_.crbegin(); }
+  const_iterator rbegin() const { return set_.crbegin(); }
+  iterator rbegin() { return set_.rbegin(); }
+  const_iterator crend() const { return set_.crend(); }
+  const_iterator rend() const { return set_.crend(); }
+  iterator rend() { return set_.rend(); }
+
+  bool empty() const { return set_.empty(); }
+  size_t size() const { return set_.size(); }
+  size_t max_size() const { return set_.max_size(); }
+
+  std::pair<iterator, bool> insert(T* val) { return set_.insert(val); }
+
+  iterator insert(const_iterator position, T* val) {
+    return set_.insert(position, val);
+  }
+
+  template <typename InputIterator>
+  void insert(InputIterator first, InputIterator last) {
+    set_.insert(first, last);
+  }
+
+  iterator erase(const_iterator position) { return set_.erase(position); }
+
+  size_t erase(const T* val) { return set_.erase(val); }
+
+  iterator erase(const_iterator first, const_iterator last) {
+    return set_.erase(first, last);
+  }
+
+  void swap(PointerSet& s) { set_.swap(s.set()); }
+  void clear() noexcept { set_.clear(); }
+
+  const_iterator find(const T* val) const { return set_.find(val); }
+  iterator find(const T* val) { return set_.find(val); }
+
+  size_t count(const T* val) const { return set_.count(val); }
+
+  const_iterator lower_bound(const T* val) const {
+    return set_.lower_bound(val);
+  }
+
+  iterator lower_bound(const T* val) { return set_.lower_bound(val); }
+
+  const_iterator upper_bound(const T* val) const {
+    return set_.upper_bound(val);
+  }
+
+  iterator upper_bound(const T* val) { return set_.upper_bound(val); }
+
+  std::pair<const_iterator, const_iterator> equal_range(const T* val) const {
+    return set_.equal_range(val);
+  }
+
+  std::pair<iterator, iterator> equal_range(const T* val) {
+    return set_.equal_range(val);
+  }
+
+ private:
+  // The underlying std::set that this class references.
+  std::set<T*, DereferenceComparator> set_;
+};
+
+#endif  // TOOLS_GN_POINTER_SET_H_