blink_gc_plugin: Make RecordInfo::Get{Fields,Bases} return deterministic order

tools/clang/blink_gc_plugin/RecordInfo.h

 // Copyright 2014 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.
 
 // This file provides a wrapper for CXXRecordDecl that accumulates GC related
 // information about a class. Accumulated information is memoized and the info
 // objects are stored in a RecordCache.
 
 #ifndef TOOLS_BLINK_GC_PLUGIN_RECORD_INFO_H_
 #define TOOLS_BLINK_GC_PLUGIN_RECORD_INFO_H_
@@ skipping 51 matching lines @@
   clang::FieldDecl* field_;
   Edge* edge_;
 
   friend class RecordCache;
   void deleteEdge() { delete edge_; }
 };
 
 // Wrapper class to lazily collect information about a C++ record.
 class RecordInfo {
  public:
-  typedef std::map<clang::CXXRecordDecl*, BasePoint> Bases;

[Nico, 2016/01/29 03:10:08]

would giving the map a custom comparator that compares on something more
deterministic that the pointer address help as well?

[hans, 2016/01/29 04:49:14]

For Bases, a map doesn't seem to buy as anything at all, since the callers of
GetBases() just want to iterate over all of them anyway. A vector is more
efficient for that.

For Fields, a map with a comparator that compares the Decls' SourceLocations
would work. I suppose the best solution depends on what the primary use is of
the data structure. Is it to iterate over all the fields, or to look up a
specific one? The code does both, but I don't know it well enough to say what's
more important.

Using LLVM's MapVector could also be a good alternative.

I don't care much how we solve this, as long as the iteration order is
deterministic. I suppose it's up to sof :-)

[sof, 2016/01/29 09:00:19]

What you propose makes the most sense to me, use a std::vector for bases, but a
map with a Compare that orders on getLocStart(), or something. Not a very
expensive node comparison nor will the underlying tree come out the worse for
it.

-  typedef std::map<clang::FieldDecl*, FieldPoint> Fields;
+  typedef std::pair<clang::CXXRecordDecl*, BasePoint> Base;
+  typedef std::vector<Base> Bases;
+  typedef std::pair<clang::FieldDecl*, FieldPoint> Field;
+  typedef std::vector<Field> Fields;
   typedef std::vector<const clang::Type*> TemplateArgs;
 
   ~RecordInfo();
 
   clang::CXXRecordDecl* record() const { return record_; }
   const std::string& name() const { return name_; }
+
   Fields& GetFields();
+  bool HasField(clang::FieldDecl*);
+  Field& GetField(clang::FieldDecl*);
   Bases& GetBases();
+
   clang::CXXMethodDecl* GetTraceMethod();
   clang::CXXMethodDecl* GetTraceDispatchMethod();
   clang::CXXMethodDecl* GetFinalizeDispatchMethod();
 
   bool GetTemplateArgs(size_t count, TemplateArgs* output_args);
 
   bool IsHeapAllocatedCollection();
   bool IsGCDerived();
   bool IsGCAllocated();
   bool IsGCFinalized();
@@ skipping 16 matching lines @@
   clang::CXXMethodDecl* InheritsNonVirtualTrace();
   bool IsConsideredAbstract();
 
   static clang::CXXRecordDecl* GetDependentTemplatedDecl(const clang::Type&);
 
  private:
   RecordInfo(clang::CXXRecordDecl* record, RecordCache* cache);
 
   void walkBases();
 
-  Fields* CollectFields();
-  Bases* CollectBases();
+  void CollectFields();
+  void CollectBases();
   void DetermineTracingMethods();
   bool InheritsTrace();
 
   Edge* CreateEdge(const clang::Type* type);
 
   RecordCache* cache_;
   clang::CXXRecordDecl* record_;
   const std::string name_;
   TracingStatus fields_need_tracing_;
   Bases* bases_;
   Fields* fields_;
+  std::map<clang::FieldDecl*, size_t>* field_map_;
 
   enum CachedBool { kFalse = 0, kTrue = 1, kNotComputed = 2 };
   CachedBool is_stack_allocated_;
   CachedBool is_non_newable_;
   CachedBool is_only_placement_newable_;
   CachedBool does_need_finalization_;
   CachedBool has_gc_mixin_methods_;
   CachedBool is_declaring_local_trace_;
   CachedBool is_eagerly_finalized_;
 
@@ skipping 40 matching lines @@
       }
     }
   }
 
  private:
   typedef std::map<clang::CXXRecordDecl*, RecordInfo> Cache;
   Cache cache_;
 };
 
 #endif  // TOOLS_BLINK_GC_PLUGIN_RECORD_INFO_H_