Make json_schema_compiler output types in their dependency order.

tools/json_schema_compiler/h_generator.py

 # Copyright (c) 2012 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.
 
 from model import PropertyType
 import code
 import cpp_util
 import model
 import os
 
@@ skipping 47 matching lines @@
       )
 
     c.Concat(self._cpp_type_generator.GetNamespaceStart())
     c.Append()
     if self._namespace.types:
       (c.Append('//')
         .Append('// Types')
         .Append('//')
         .Append()
       )
-      for type_ in self._namespace.types.values():
+      for type_ in self._FieldDependencyOrder():
         (c.Concat(self._GenerateType(type_))
           .Append()
         )
     if self._namespace.functions:
       (c.Append('//')
         .Append('// Functions')
         .Append('//')
         .Append()
       )
       for function in self._namespace.functions.values():
         (c.Concat(self._GenerateFunction(function))
           .Append()
         )
     (c.Concat(self._cpp_type_generator.GetNamespaceEnd())
       .Concat(self._cpp_type_generator.GetRootNamespaceEnd())
       .Append()
       .Append('#endif  // %s' % ifndef_name)
       .Append()
     )
     return c
 
+  def _FieldDependencyOrder(self):
+    """Generates the list of types in the current namespace in an order in which
+    depended-upon types appear before types which depend on them.
+    """
+    dependency_order = []
+
+    def ExpandType(path, type_):
+      if type_ in path:
+        raise ValueError("Illegal circular dependency via cycle " +
+                         ", ".join(map(lambda x: x.name, path + [type_])))
+      for prop in type_.properties.values():
+        if not prop.optional and prop.type_ == PropertyType.REF:
+          ExpandType(path + [type_], self._namespace.types[prop.ref_type])
+      if not type_ in dependency_order:
+        dependency_order.append(type_)
+
+    for type_ in self._namespace.types.values():
+      ExpandType([], type_)
+    return dependency_order
+
   def _GenerateEnumDeclaration(self, enum_name, prop, values):
     """Generate the declaration of a C++ enum for the given property and
     values.
     """
     c = code.Code()
     c.Sblock('enum %s {' % enum_name)
     if prop.optional:
       c.Append(self._cpp_type_generator.GetEnumNoneValue(prop) + ',')
     for value in values:
       c.Append(self._cpp_type_generator.GetEnumValue(prop, value) + ',')
@@ skipping 157 matching lines @@
           c.Comment(param.description)
         if param.type_ == PropertyType.ANY:
           c.Comment("Value* Result::Create(Value*) not generated "
                     "because it's redundant.")
           continue
         c.Append('Value* Create(const %s);' % cpp_util.GetParameterDeclaration(
             param, self._cpp_type_generator.GetType(param)))
     c.Eblock('};')
 
     return c