nodes: 0, module; 1, function_definition; 2, function_name:sort_dependencies; 3, parameters; 4, block; 5, identifier:objects; 6, expression_statement; 7, import_from_statement; 8, comment:# Process the list of models, and get the list of dependencies; 9, expression_statement; 10, expression_statement; 11, expression_statement; 12, expression_statement; 13, for_statement; 14, for_statement; 15, expression_statement; 16, comment:# Now sort the models to ensure that dependencies are met. This; 17, comment:# is done by repeatedly iterating over the input list of models.; 18, comment:# If all the dependencies of a given model are in the final list,; 19, comment:# that model is promoted to the end of the final list. This process; 20, comment:# continues until the input list is empty, or we do a full iteration; 21, comment:# over the input models without promoting a model to the final list.; 22, comment:# If we do a full iteration without a promotion, that means there are; 23, comment:# circular dependencies in the list.; 24, expression_statement; 25, while_statement; 26, expression_statement; 27, for_statement; 28, return_statement; 29, comment:"""
      Sort a list of instances by their model dependancy graph.
  
      This is very similar to Django's sort_dependencies method except
      for two big differences:
  
      1. We graph dependencies unrelated to natural_key.
      2. We take a list of objects, and return a sorted list of objects.
      """; 30, dotted_name; 31, dotted_name; 32, assignment; 33, assignment; 34, assignment; 35, assignment; 36, identifier:o; 37, identifier:objects; 38, block; 39, identifier:model; 40, identifier:model_list; 41, block; 42, call; 43, assignment; 44, identifier:model_dependencies; 45, block; 46, assignment; 47, identifier:model; 48, identifier:model_list; 49, block; 50, identifier:sorted_results; 51, identifier:django; 52, identifier:db; 53, identifier:models; 54, identifier:get_model; 55, identifier:model_dependencies; 56, list; 57, identifier:models; 58, call; 59, identifier:model_list; 60, call; 61, identifier:objs_by_model; 62, call; 63, expression_statement; 64, expression_statement; 65, expression_statement; 66, expression_statement; 67, comment:# Add any explicitly defined dependencies; 68, if_statement; 69, comment:# Now add a dependency for any FK or M2M relation with; 70, comment:# a model that defines a natural key; 71, for_statement; 72, expression_statement; 73, attribute; 74, argument_list; 75, identifier:model_list; 76, list; 77, expression_statement; 78, expression_statement; 79, while_statement; 80, if_statement; 81, expression_statement; 82, identifier:sorted_results; 83, list; 84, expression_statement; 85, identifier:set; 86, argument_list; 87, identifier:set; 88, argument_list; 89, identifier:defaultdict; 90, argument_list; 91, assignment; 92, call; 93, call; 94, call; 95, call; 96, block; 97, else_clause; 98, identifier:field; 99, call; 100, block; 101, call; 102, identifier:model_dependencies; 103, identifier:reverse; 104, assignment; 105, assignment; 106, identifier:model_dependencies; 107, block; 108, not_operator; 109, block; 110, assignment; 111, call; 112, identifier:list; 113, identifier:model; 114, attribute; 115, attribute; 116, argument_list; 117, attribute; 118, argument_list; 119, attribute; 120, argument_list; 121, identifier:hasattr; 122, argument_list; 123, expression_statement; 124, if_statement; 125, block; 126, attribute; 127, argument_list; 128, if_statement; 129, attribute; 130, argument_list; 131, identifier:skipped; 132, list; 133, identifier:changed; 134, False; 135, expression_statement; 136, comment:# If all of the models in the dependency list are either already; 137, comment:# on the final model list, or not on the original serialization list,; 138, comment:# then we've found another model with all it's dependencies satisfied.; 139, expression_statement; 140, for_statement; 141, if_statement; 142, identifier:changed; 143, raise_statement; 144, identifier:model_dependencies; 145, identifier:skipped; 146, attribute; 147, argument_list; 148, identifier:o; 149, identifier:__class__; 150, subscript; 151, identifier:append; 152, identifier:o; 153, identifier:model_list; 154, identifier:add; 155, identifier:model; 156, identifier:models; 157, identifier:add; 158, identifier:model; 159, identifier:model; 160, string; 161, assignment; 162, identifier:deps; 163, block; 164, expression_statement; 165, identifier:itertools; 166, identifier:chain; 167, attribute; 168, attribute; 169, boolean_operator; 170, block; 171, identifier:model_dependencies; 172, identifier:append; 173, tuple; 174, assignment; 175, assignment; 176, identifier:candidate; 177, generator_expression; 178, block; 179, identifier:found; 180, block; 181, else_clause; 182, call; 183, identifier:sorted_results; 184, identifier:extend; 185, subscript; 186, identifier:objs_by_model; 187, identifier:model; 188, string_content:natural_key; 189, identifier:deps; 190, call; 191, expression_statement; 192, assignment; 193, attribute; 194, identifier:fields; 195, attribute; 196, identifier:many_to_many; 197, call; 198, comparison_operator:field.rel.to != model; 199, expression_statement; 200, identifier:model; 201, identifier:deps; 202, pattern_list; 203, call; 204, identifier:found; 205, True; 206, parenthesized_expression; 207, for_in_clause; 208, if_statement; 209, expression_statement; 210, expression_statement; 211, block; 212, identifier:CommandError; 213, argument_list; 214, identifier:objs_by_model; 215, identifier:model; 216, identifier:getattr; 217, argument_list; 218, assignment; 219, identifier:deps; 220, list; 221, identifier:model; 222, identifier:_meta; 223, identifier:model; 224, identifier:_meta; 225, identifier:hasattr; 226, argument_list; 227, attribute; 228, identifier:model; 229, call; 230, identifier:model; 231, identifier:deps; 232, attribute; 233, argument_list; 234, boolean_operator; 235, identifier:d; 236, identifier:deps; 237, not_operator; 238, block; 239, call; 240, assignment; 241, expression_statement; 242, binary_operator:"Can't resolve dependencies for %s in serialized app list." %
                  ', '.join('%s.%s' % (model._meta.app_label, model._meta.object_name)
                  for model, deps in sorted(skipped, key=lambda obj: obj[0].__name__)); 243, attribute; 244, string; 245, list; 246, identifier:deps; 247, list_comprehension; 248, attribute; 249, string; 250, attribute; 251, identifier:to; 252, attribute; 253, argument_list; 254, identifier:model_dependencies; 255, identifier:pop; 256, comparison_operator:d not in models; 257, comparison_operator:d in model_list; 258, identifier:candidate; 259, expression_statement; 260, attribute; 261, argument_list; 262, identifier:changed; 263, True; 264, call; 265, string:"Can't resolve dependencies for %s in serialized app list."; 266, call; 267, identifier:model; 268, identifier:natural_key; 269, string_content:dependencies; 270, call; 271, for_in_clause; 272, identifier:field; 273, identifier:rel; 274, string_content:to; 275, identifier:field; 276, identifier:rel; 277, identifier:deps; 278, identifier:append; 279, attribute; 280, identifier:d; 281, identifier:models; 282, identifier:d; 283, identifier:model_list; 284, assignment; 285, identifier:model_list; 286, identifier:append; 287, identifier:model; 288, attribute; 289, argument_list; 290, attribute; 291, generator_expression; 292, identifier:get_model; 293, argument_list; 294, identifier:d; 295, identifier:deps; 296, attribute; 297, identifier:to; 298, identifier:found; 299, False; 300, identifier:skipped; 301, identifier:append; 302, tuple; 303, string; 304, identifier:join; 305, binary_operator:'%s.%s' % (model._meta.app_label, model._meta.object_name); 306, for_in_clause; 307, list_splat; 308, identifier:field; 309, identifier:rel; 310, identifier:model; 311, identifier:deps; 312, string_content:,; 313, string; 314, tuple; 315, pattern_list; 316, call; 317, call; 318, string_content:%s.%s; 319, attribute; 320, attribute; 321, identifier:model; 322, identifier:deps; 323, identifier:sorted; 324, argument_list; 325, attribute; 326, argument_list; 327, attribute; 328, identifier:app_label; 329, attribute; 330, identifier:object_name; 331, identifier:skipped; 332, keyword_argument; 333, identifier:d; 334, identifier:split; 335, string; 336, identifier:model; 337, identifier:_meta; 338, identifier:model; 339, identifier:_meta; 340, identifier:key; 341, lambda; 342, string_content:.; 343, lambda_parameters; 344, attribute; 345, identifier:obj; 346, subscript; 347, identifier:__name__; 348, identifier:obj; 349, integer:0
code: def sort_dependencies(objects):
      """
      Sort a list of instances by their model dependancy graph.
  
      This is very similar to Django's sort_dependencies method except
      for two big differences:
  
      1. We graph dependencies unrelated to natural_key.
      2. We take a list of objects, and return a sorted list of objects.
      """
      from django.db.models import get_model
      # Process the list of models, and get the list of dependencies
      model_dependencies = []
      models = set()
      model_list = set()
      objs_by_model = defaultdict(list)
      for o in objects:
          model = o.__class__
          objs_by_model[model].append(o)
          model_list.add(model)
  
      for model in model_list:
          models.add(model)
          # Add any explicitly defined dependencies
          if hasattr(model, 'natural_key'):
              deps = getattr(model.natural_key, 'dependencies', [])
              if deps:
                  deps = [get_model(*d.split('.')) for d in deps]
          else:
              deps = []
  
          # Now add a dependency for any FK or M2M relation with
          # a model that defines a natural key
          for field in itertools.chain(model._meta.fields, model._meta.many_to_many):
              if hasattr(field.rel, 'to') and field.rel.to != model:
                  deps.append(field.rel.to)
          model_dependencies.append((model, deps))
  
      model_dependencies.reverse()
      # Now sort the models to ensure that dependencies are met. This
      # is done by repeatedly iterating over the input list of models.
      # If all the dependencies of a given model are in the final list,
      # that model is promoted to the end of the final list. This process
      # continues until the input list is empty, or we do a full iteration
      # over the input models without promoting a model to the final list.
      # If we do a full iteration without a promotion, that means there are
      # circular dependencies in the list.
      model_list = []
      while model_dependencies:
          skipped = []
          changed = False
          while model_dependencies:
              model, deps = model_dependencies.pop()
  
              # If all of the models in the dependency list are either already
              # on the final model list, or not on the original serialization list,
              # then we've found another model with all it's dependencies satisfied.
              found = True
              for candidate in ((d not in models or d in model_list) for d in deps):
                  if not candidate:
                      found = False
              if found:
                  model_list.append(model)
                  changed = True
              else:
                  skipped.append((model, deps))
          if not changed:
              raise CommandError("Can't resolve dependencies for %s in serialized app list." %
                  ', '.join('%s.%s' % (model._meta.app_label, model._meta.object_name)
                  for model, deps in sorted(skipped, key=lambda obj: obj[0].__name__))
              )
          model_dependencies = skipped
  
      sorted_results = []
      for model in model_list:
          sorted_results.extend(objs_by_model[model])
  
      return sorted_results