class PGTrunk::DependenciesResolver

@private Resolve dependencies between inter-dependent objects, identified by database ‘#oid` and comparable to each other.

The method builds the sorted list:

We have no expectations about the natural order here. @see [PGTrunk::ObjectDefinitions::Operation]

Attributes

objects[R]
parents[R]

Public Class Methods

new(objects, parents) click to toggle source

@param [Array<Comparable, oid>] objects Objects to sort @param [Hash<{Integer => Array<Integer>}] parents Dependencies between oid-s

# File lib/pg_trunk/core/dependencies_resolver.rb, line 59
def initialize(objects, parents)
  @objects = objects
  @parents = parents.transform_values do |oids|
    # preserve the original order of objects
    objects.each_with_object([]) do |obj, list|
      list << obj if oids.include?(obj.oid)
    end
  end
end
resolve(objects) click to toggle source

Resolve dependencies between objects @param [Array<Enumerable, oid>] objects The list of objects @return [Array<#oid>] The sorted list of objects @raise [Dependencies::CycleError] if dependencies contain a cycle

# File lib/pg_trunk/core/dependencies_resolver.rb, line 20
def resolve(objects)
  new(objects, dependencies).send(:sorted)
end

Private Class Methods

dependencies() click to toggle source

Extract dependencies between given oids from the database

# File lib/pg_trunk/core/dependencies_resolver.rb, line 43
def dependencies
  ActiveRecord::Base
    .connection
    .execute(query)
    .each_with_object({}) do |i, obj|
      child = i["child"].to_i
      parents = i["parents"].scan(/\d+/).map(&:to_i)
      obj[child] = parents.uniq
    end
end
query() click to toggle source
# File lib/pg_trunk/core/dependencies_resolver.rb, line 26
      def query
        <<~SQL.squish
          SELECT child, array_agg(parent) AS parents
          FROM (
            SELECT
              d.objid AS child,
              d.refobjid AS parent
            FROM pg_depend d
              JOIN pg_trunk e1 ON d.objid = e1.oid
              JOIN pg_trunk e2 ON d.refobjid = e2.oid
            WHERE d.objsubid IS NULL
          ) dependencies
          GROUP BY child;
        SQL
      end

Private Instance Methods

index() click to toggle source
# File lib/pg_trunk/core/dependencies_resolver.rb, line 75
def index
  @index ||= objects.each_with_object({}) { |obj, idx| idx[obj.oid] = obj }
end
next_unvisited() click to toggle source
# File lib/pg_trunk/core/dependencies_resolver.rb, line 89
def next_unvisited
  objects.find { |object| !visited[object.oid] }
end
sorted() click to toggle source

Use topological sorting algorithm to resolve dependencies @return [Array<#oid>]

# File lib/pg_trunk/core/dependencies_resolver.rb, line 81
def sorted
  @sorted ||= [].tap do |output|
    while (object = next_unvisited)
      visit(object, output)
    end
  end
end
visit(object, output) click to toggle source
# File lib/pg_trunk/core/dependencies_resolver.rb, line 93
def visit(object, output)
  return if visited[object.oid]

  parents[object.oid]&.each { |parent| visit(parent, output) }
  visited[object.oid] = true
  output << object
end
visited() click to toggle source
# File lib/pg_trunk/core/dependencies_resolver.rb, line 71
def visited
  @visited ||= {}
end