Sort Your Rails Models By The Order of their Associations

I’m currently working on a new gem that should be able to run seeds in your Rails app efficiently. While creating the gem, I ran into an interesting problem.

I wanted to generate a seedie.yml file that generates seeds based on its config. A simple seedie.yml file looks like this:

default_count: 5
models:
  user:
    attributes:
      name: "name "
      email: "{{Faker::Internet.email}}"
      address: "{{Faker::Address.street_address}}"
    disabled_fields: [nickname password password_digest]
  post: &post
    count: 2
    attributes:
      title: "title "
    associations:
      has_many:
        comments: 4
      belongs_to:
        user: random
      has_one:
        post_metadatum: 
          attributes:
            seo_text: "{{Faker::Lorem.paragraph}}"
    disabled_fields: []
  comment:
    attributes:
      # title: "title "
    associations:
      belongs_to:
        post:
          attributes:
            title: "Comment Post "

The Problem

We can write this seedie.yml config from scratch and manually. However, I wanted to generate this config automatically from the Rails app.

It should be as simple as bin/rails g seedie:install.

So I wrote an install_generator that helps generate this seed file based on your ActiveRecord::Base.descendants.

EXCLUDED_MODELS = %w[
  ActiveRecord::SchemaMigration
  ActiveRecord::InternalMetadata
  ActiveStorage::Attachment
  ActiveStorage::Blob
  ActiveStorage::VariantRecord
  ActionText::RichText
  ActionMailbox::InboundEmail
  ActionText::EncryptedRichText
]

desc "Creates a seedie.yml for your application."
def copy_seedie_file
  generate_seedie_file
end

private

def generate_seedie_file
  Rails.application.eager_load! # Load all models. ITS IMPORTANT!
  
  @models_config = models_configuration
  template "seedie.yml", "config/seedie.yml"
end

def models_configuration
  models = ActiveRecord::Base.descendants.reject do |model|
    EXCLUDED_MODELS.include?(model.name) || # Excluded Reserved Models
    model.table_exists? == false || # Excluded Models without tables
    model.abstract_class? || # Excluded Abstract Models
    model.name.blank? || # Excluded Anonymous Models
    model.name.start_with?("HABTM_") # Excluded HABTM Models
  end

  # Some code to generate configurations that ultimately returns generates a similar config as below
  
  #  models:
  #     comment:
  #      attributes:
  #      associations:
  #      disabled_fields:
  #    post:
  #      attributes:
  #      associations:
  #      disabled_fields:
  #    user:
  #      attributes:
  #      associations:
  #      disabled_fields:
end

### REST OF THE CODE

There is a problem here!

Comment and Post both have a belongs_to association with User.

So, it cannot be created before User.

ActiveRecord does not know about the order of models, It doesn’t know that User needs to be created before Post and Post before Comment.

It just generates the config based on the order of the models in the ActiveRecord::Base.descendants array.

So I need to find a way to be able to sort these models based on their associations, particularly BelongsTo Associations.

The Solution

First, I need to decide a priority for each model.

Models with no associations will have the highest priority.
Models with 1 BelongsTo association will have a higher priority than models with 2 BelongsTo associations.
Models’ Associations needs to have a higher priority that the model itself

But how do I find associations for the model?

Reflection is the answer.

ActiveRecord has a very cool module called ActiveRecord::Reflection that helps us find associations for a model.

Let’s take a look at the following models:

class GameRoom < ApplicationRecord
  belongs_to :creator, class_name: "User", foreign_key: "user_id"
  belongs_to :current_issue, class_name: "Issue", optional: true
  
  has_many :issues
  has_many :pokers, through: :issues
  has_many :game_room_users
  has_many :users, through: :game_room_users
end

class User < ApplicationRecord
  has_many :pokers
  has_many :game_room_users
  has_many :game_rooms, through: :game_room_users
end

class Poker < ApplicationRecord
  belongs_to :user
  belongs_to :issue
end

class Issue < ApplicationRecord
  belongs_to :game_room
  has_many :pokers
end

We have these four models with different dependencies. (Taken from an opensource project of mine called SprintSpades)

Now, let’s try and sort these models based on their dependencies.

To satisfy all the dependencies, the order should be:

User
GameRoom
GameRoomUser
Issue
Poker

For this I’m creating a new class called ModelSorter

class ModelSorter
  def initialize(models)
    @models = models
  end

  def sort_models_by_dependency
    sorted_models = []
    remaining_models = @models.dup

    while remaining_models.present?
      # Models without belongs_to associations or whose dependencies are already sorted
      sortable_models = remaining_models.select do |model|
        belongs_to_associations = model.reflect_on_all_associations(:belongs_to).map(&:klass)
        belongs_to_associations.all? { |assoc| sorted_models.include?(assoc) || remaining_models.exclude?(assoc) }
      end

      break if sortable_models.empty?

      sorted_models << sortable_models
      remaining_models -= sortable_models
    end

    if remaining_models.any?
      puts "Warning: The following models have circular dependencies or depend on models not included in the list: #{remaining_models.map(&:name).join(', ')}"
      sorted_models << remaining_models
    end

    sorted_models
  end
end

This is the first iteration so there are a lot of things that can be improved here. What am I doing here?

The sorted_models array will contain the models sorted by their dependencies.
remaining_models will contain the models that are yet to be sorted.
I’m looping through the remaining_models and sorting its dependencies by checking if the association exists in the sorted_models array.
I’m breaking the loop if there are no more models to sort.
Also checking for circular dependencies if any and adding a warning so that the user can fix it.

There are few problems with this:

Polymorphic association do not support (&:klass) method.
Associations shows circular dependency even if they are not.
The order is still wrong

After many iterations, I came up with this:

class ModelSorter
  def initialize(models)
    @models = models
    @model_dependencies = models.map {|m| [m, get_model_dependencies(m)]}.to_h
    @resolved_queue = []
    @unresolved = []
  end

  def sort_by_dependency
    @models.each do |model|
      resolve_dependencies(model) unless @resolved_queue.include?(model)
    end

    @resolved_queue
  end

  private

  def resolve_dependencies(model)
    raise "Circular dependency detected: #{model}" if @unresolved.include?(model)

    @unresolved << model
    dependencies = @model_dependencies[model]
    
    if dependencies
      dependencies.each do |dependency|
        resolve_dependencies(dependency) unless @resolved_queue.include?(dependency)
      end
    end

    @resolved_queue.unshift(model)
    @unresolved.delete(model)
  end

  def get_model_dependencies(model)
    associations = model.reflect_on_all_associations(:belongs_to).reject! do |association|
      association.options[:polymorphic] == true || # Excluded Polymorphic Associations
      association.options[:optional] == true # Excluded Optional Associations
    end

    return [] if associations.blank?

    associations.map do |association|
      if association.options[:class_name]
        association.options[:class_name].constantize
      else
        association.klass
      end
    end
  end
end

ModelSorter now does the following:

It maps the models with its dependencies.
It loops through the models and searches for its dependencies recursively using depth_first_search method.
Sets the associations first before the model itself.
Needed to reject optional associations to avoid circular dependencies and also it doesn’t matter right now.
Earlier, I used stack to store the resolved models but the order was wrong so used a queue instead.
Also, I’m using a @unresolved array to store the models that are yet to be resolved.

Using this now if I run rails g seedie:install , it will generate the following seedie.yml file:

default_count: 5
models:
  user:
    attributes:
    disabled_fields: []
  game_room:
    attributes:
    associations:
    disabled_fields: []
  game_room_user:
    attributes:
    associations:
      belongs_to:
        game_room: random
        user: random
    disabled_fields: []
  issue:
    attributes:
    associations:
      belongs_to:
        game_room: random
    disabled_fields: []
  poker:
    attributes:
    associations:
      belongs_to:
        user: random
        issue: random
    disabled_fields: []

It is not perfect yet, but it is a good start.

Conclusion

I’m still working on this gem and will be releasing it soon. I’ll be writing more about it in the future as well.

Follow me on Twitter for more updates.

You can also follow me on Github to see what I’m working on.