#### libremiliacr
#### Copyright(C) 2020-2024 Remilia Scarlet <remilia@posteo.jp>
####
#### This program is free software: you can redistribute it and/or modify
#### it under the terms of the GNU General Public License as published
#### the Free Software Foundation, either version 3 of the License, or
#### (at your option) any later version.
####
#### This program is distributed in the hope that it will be useful,
#### but WITHOUT ANY WARRANTY; without even the implied warranty of
#### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the
#### GNU General Public License for more details.
####
#### You should have received a copy of the GNU General Public License
#### along with this program.If not, see<http:####www.gnu.org/licenses/.>
module RemiLib
# A simple way to specify dependencies between items. This particular
# implementation does not support circular references.
module DependencyGraph
class CircularDependencyError < Exception
end
# A single item within a `DependencyGraph`. This wraps a single data item
# of type `T`, associating it with a particular name of type `N`.
#
# When resolving dependencies, for each item of type `T`, a procedure of
# type `Proc(N, T, Nil)` will be called.
class Node(N, T)
# The name associated with this dependency.
getter name : N
# The data associated with this dependency.
getter data : T
# The other things that this node depends on.
getter deps : Array(Node(N, T)) = [] of Node(N, T)
# Creates a new `Node`.
def initialize(@name : N, @data : T)
end
# Adds a new dependency for this node. Returns `self`.
def <<(dep : Node(N, T))
@deps << dep
self
end
# Resolves the dependencies for this node, then runs `fn`.
def resolve(fn : Proc(N, T, Nil), resolved : Array(Node(N, T)), seen : Array(Node(N, T))) : Nil
# Mark this as seen
seen << self
# Loop through this node's dependencies
@deps.each do |dep|
# Only process nodes that are unresolved
unless resolved.includes?(dep)
# Check for circular dependencies
if seen.includes?(dep)
raise CircularDependencyError.new("Circular dependency: #{self.name} => #{dep.name}")
end
# Resolve the dependency
dep.resolve(fn, resolved, seen)
end
end
# This node is now resolved
resolved << self
# Call the function for processing this node
fn.call(@name, @data)
end
# Resolves the dependencies for this node. Unlike `#resolve`, this
# doesn't run anything, and instead is used simply to determine the order
# of dependency resolution.
def dryRun(resolved : Array(Node(N, T)), seen : Array(Node(N, T))) : Nil
# Mark this as seen
seen << self
# Loop through this node's dependencies
@deps.each do |dep|
# Only process nodes that are unresolved
unless resolved.includes?(dep)
# Check for circular dependencies
if seen.includes?(dep)
raise CircularDependencyError.new("Circular dependency: #{self.name} => #{dep.name}")
end
# Resolve the dependency
dep.dryRun(resolved, seen)
end
end
# This node is now resolved
resolved << self
end
end
# Resolves the dependency graph, calling `fn` for each item in the graph in
# the order of their dependencies. Returns the number of dependencies that
# were resolved.
def self.run(root : Node(N, T), fn : Proc(N, T, Nil)) : Int forall N, T
seen = [] of Node(N, T)
resolved = [] of Node(N, T)
root.resolve(fn, resolved, seen)
end
# Resolves the dependency graph, calling `fn` for each item in the graph in
# the order of their dependencies. Returns the number of dependencies that
# were resolved.
def self.run(fn : Proc(N, T, Nil), *deps : Node(N, T)) : Nil forall N, T
seen = [] of Node(N, T)
resolved = [] of Node(N, T)
deps.each do |dep|
dep.resolve(fn, resolved, seen)
end
end
# Resolves the dependency graph, calling `fn` for each item in the graph in
# the order of their dependencies. Returns the number of dependencies that
# were resolved.
def self.run(fn : Proc(N, T, Nil), deps : Array(Node(N, T))) : Nil forall N, T
seen = [] of Node(N, T)
resolved = [] of Node(N, T)
deps.each do |dep|
dep.resolve(fn, resolved, seen)
end
end
# Resolves the dependency graph, then returns the order for the dependencies
# as an array of `N`. Essentially, a dry run.
def self.getOrder(*deps : Node(N, T)) : Array(N) forall N, T
seen = [] of Node(N, T)
resolved = [] of Node(N, T)
deps.each do |dep|
dep.dryRun(resolved, seen)
end
resolved.map &.name
end
# Resolves the dependency graph, then returns the order for the dependencies
# as an array of `N`. Essentially, a dry run.
def self.getOrder(deps : Array(Node(N, T))) : Array(N) forall N, T
seen = [] of Node(N, T)
resolved = [] of Node(N, T)
deps.each do |dep|
dep.dryRun(resolved, seen)
end
resolved.map &.name
end
end
end