GN: Makes GN output deterministic

tools/gn/dereference_comparator.h

Index: tools/gn/dereference_comparator.h
diff --git a/tools/gn/dereference_comparator.h b/tools/gn/dereference_comparator.h
new file mode 100644
index 0000000000000000000000000000000000000000..47108c90939d71764613c4b3b7c61ebe1466ef0f
--- /dev/null
+++ b/tools/gn/dereference_comparator.h
@@ -0,0 +1,36 @@
+// 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_DEREFERENCE_COMPARATOR_H_
+#define TOOLS_GN_DEREFERENCE_COMPARATOR_H_
+
+#include <functional>
+#include <set>
+
+// Comparator that dereferences the pointers before comparing them.
+template <typename T, typename Comparator = std::less<T>>
+class DereferenceComparator {
+ public:
+  // Constructs a DereferenceComparator that uses the provided comparator.
+  DereferenceComparator(const Comparator& 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 {
+    DCHECK(a != nullptr);
+    DCHECK(b != nullptr);
+    return comparator(*a, *b);
+  }
+
+ private:
+  Comparator comparator;
+};
+
+// Typedefs for convenience.
+
+// A set of pointers that are ordered by what they point at.
+template <typename T, typename Comparator = std::less<T>>
+using PointerSet = std::set<T*, DereferenceComparator<T, Comparator>>;

[M-A Ruel, 2015/12/07 00:20:16]

AFAIK, that's what std::set<> already does (?)

Otherwise this would mean the set never worked in GN, which I would be surprised
that it is the case.

--- CUT HERE ---
#include <iostream>
#include <set>

struct A {
  A(int v) : x(v) {}
  int x;
  bool operator<(const A& that) const {
    return x < that.x;
  }         
};

int main() {
  std::set<A*> set_of_numbers;
  set_of_numbers.insert(new A(1));
  set_of_numbers.insert(new A(2)); 
  set_of_numbers.insert(new A(1));
  for (const auto& itr : set_of_numbers) {
    std::cout << itr->x << std::endl;
  }
  return 0;
}
--- CUT HERE ---

$ .../src/third_party/llvm-build/Release+Asserts/bin/clang++ a.cc -o a.out
-std=c++11 && ./a.out
1
2
1


/me is puzzled.

[Zachary Forman, 2015/12/07 03:18:17]

So the Target*s are 'unique' in that there is a 1:1 matching between pointer and
target name.
It's more a situation where we have deps1 = {&target1, &target2}, deps2 =
{&target3, &target2}, deps3 = {&target4, &target5, &target1}.
The set prevents us from 'double including' a target, but it doesn't order our
targets deterministically; it orders them by pointer order.

My previous CL (now replaced with std::sorts) used the DereferenceOperator to
directly compare the actual underlying targets, as opposed to just the pointers.
This is more expensive (strcmp vs integer compare) but also gives deterministic
ordering.

+
+#endif  // TOOLS_GN_DEREFERENCE_COMPARATOR_H_