blog draft

gistfile1.md

layout	title
post	Validating acyclic graphs

Alexis King and I were building an inventory management system for a Widget factory. In the warehouse they have a variety of containers that can hold either widgets or other containers. We needed to provide an inventory management system for the warehouse manager to keep track of the whereabouts of each container and widget. Here's how it needed to work:

1. Manager logs into the inventory management system
2. Manager navigates to the show view for an Inventory Location (i.e. a warehouse)
3. Manager clicks on manage containers
4. From this form the Manager can specify the location of Containers using a drag and drop style interface.

So based on these requirements we know that a Container should belong_to :parent_container and inversely have_many :child_containers:

class Container < ActiveRecord::Base
  belongs_to :inventory_location
  belongs_to :parent_container, class_name: 'Container', foreign_key: :container_id
  has_many :child_containers, class_name: 'Container', foreign_key: :container_id
end

Sounds great so far! Wait, one problem is we want to make sure that a warehouse manager can't define a cyclic relationship of containers. Container A can not be inside of container B if container B is already inside of container A. Sounds obvious but finding a way to validate that for any case turns out to be a little complicated. Luckily we don't need to figure that out because Robert Tarjan already did and Ruby makes it available in the TSort module. This is the same module that Bundler uses to resolve dependancies in a Gemfile. If it's good enough for Bundler it should be good enough for this!

We don't really need all the functionality of the TSort module but if we include it in our model and call it's #tsort method, we'll conveniently raise a TSort::Cyclic error if any closed loops exist in the tree! Great.

class InventoryLocation < ActiveRecord::Base
  include TSort

  has_many :containers

  validate :acyclic

  private

  def acyclic
    tsort
  rescue TSort::Cyclic
    errors.add(:base, 'Creates cyclic container relationship')
  end

  def tsort_each_node(&block)
    containers.each(&block)
  end

  def tsort_each_child(container, &block)
    container.child_containers.each(&block)
  end
end

Now the problem is we want to interact with a tree of Containers but when we modify their relationship we need to check if the validity of the change through the InventoryLocation and it has to be checked after the update. We can solve part of the problem by wrapping the update and the check for validity in a transaction. I would be pretty essential that we enforce that that transaction happen anytime someone tries to add a container to another container. We can accomplish that with an extension to the collection proxy like so:

module ValidateAcyclicInventoryLocation
  def with_location_validation
    transaction do
      yield
      owner = proxy_association.owner
      location = owner.inventory_location.reload
      return true if location.valid?

      location.errors.full_messages_for(:base).each do |error|
        owner.errors.add(:base, error)
      end
    end
  end

  def <<(value)
    with_location_validation { super(value) }
  end
end

Then we can mix that extension into the has_many relationship on Container:

class Container < ActiveRecord::Base
  belongs_to :inventory_location
  belongs_to :parent_container, class_name: 'Container', foreign_key: :container_id
  has_many(
    :child_containers,
    (-> { extending ValidateAcyclicInventoryLocation }),
    class_name: 'Container',
    foreign_key: :container_id
  )
end

We needed to provide a CMS for the warehouse manager

Maybe an inventory management system?

class Container < ActiveRecord::Base
  belongs_to :inventory_location
  belong_to :parent_container
  has_many :child_containers
end

You don't need to specify class_name: on parent_container and child_containers?

If it's good enough for Bundler it should be good enough for this! 👍 that's what I always say 😆

belongs_to(
    :root_container,
    class_name: 'Container',
    foreign_key: :container_id
  )

Seems weird from a modeling perspective that an InventoryLocation belongs_to a :root_container, especially since Container belongs_to :inventory_location

@jdwolk thanks! took your changes

class Container < ActiveRecord::Base
  belongs_to :inventory_location
  belong_to :parent_container
  has_many :child_containers
end

You don't need to specify class_name: on parent_container and child_containers?

Now the problem is we want to interact with a tree of Containers but when we modify their relationship we need to check if the validity of the change through the InventoryLocation and it has to be checked after the update.

A little hard to parse this sentence

has_many(
    :child_containers,
    (-> { extending ValidateAcyclicInventoryLocation }),
    class_name: 'Container',
    foreign_key: :container_id
  )

Huh didn't know extending was a thing

K now I'm done commenting 😝

@jdwolk ok I'll make the rest of changes in my repo thanks