Skip to content

Instantly share code, notes, and snippets.

@urban-1
Last active February 17, 2021 08:06
Show Gist options
  • Save urban-1/ae42dd6a7c5c0deef8bc9a6906d2bcb0 to your computer and use it in GitHub Desktop.
Save urban-1/ae42dd6a7c5c0deef8bc9a6906d2bcb0 to your computer and use it in GitHub Desktop.
PUBLIC: Software Version Dependency Resolution
#!/usr/bin/env python
import logging as lg
import re
from random import randint, choice
from distutils.version import LooseVersion as Version
from collections import OrderedDict
lg.basicConfig(level=lg.DEBUG)
#
# Exceptions
#
class Restart(Exception):
pass
class Deadlock(Exception):
def __init__(self, message, node):
self.message = message
self.node = node
class CircularDeadlock(Deadlock):
"""
A circular dependency that does not satisfy the
requirements
"""
def __init__(self, message, node, new_version):
self.message = message
self.node = node
self.new_version = new_version
#
# Data structures
#
class Dependency(object):
def __init__(self, node, criteria=None):
# Points to a node
self.node = node
# Requires the following criteria
if criteria is None:
self.criteria = {}
else:
self.criteria = criteria
def toString(self, source=None):
"""
Debug print
"""
sname = "User"
if source is not None:
sname = source.name
ret = "%s->%s(%s)" % (sname, self.node.name,
self.criteria['version'] if 'version' in self.criteria else '-')
return ret
class Node(object):
def __init__(self, name, data=None):
self.name = name
# Versions in data, Each version has dependencies
if data is None:
self.data = OrderedDict()
else:
self.data = OrderedDict(data)
self.deps = []
def has(self, dependency):
self.deps.append(dependency)
def resetDeps(self):
self.deps = []
self.selected_version = None
def toString(self):
"""
Debug print
"""
ret = "%s(%s)" % (self.name,
self.data['selected_version'] if 'selected_version' in self.data else '?')
return ret
class VersionNode(Node):
"""
A node that supports versions - application specific
"""
def addVersion(self, version, dependencies):
if "versions" not in self.data:
self.data['versions'] = OrderedDict()
self.data['versions'][version] = dependencies
def addDep2Version(self, version, dependency):
if "versions" not in self.data:
self.data['versions'] = OrderedDict()
if version not in self.data['versions']:
self.data['versions'][version] = [ dependency ]
else:
self.data['versions'][version].append(dependency)
class DepRes(object):
def __init__(self):
self.clean()
def clean(self):
self.done = []
self.proc = []
self.tab = ''
def resolve(self, dependency, fromNode=None):
"""
Public interface/API
"""
run = True
self.circular = []
self.rounds = 0
while run:
self.rounds += 1
try:
self.clean()
self._resolve(dependency, fromNode)
run = False
except CircularDeadlock as e:
# Check if we have seen this node and version...
if (e.node, e.new_version) in self.circular:
msg = "No solution! Node %s is flapping between versions" % e.node.name
lg.error(msg)
lg.debug(self.circular)
raise Deadlock(msg, e.node)
# if not, update and go again...
self.circular.append((e.node, e.new_version))
for n in self.proc:
n.data['invalid'] = []
n.data['invalid_by'] = []
for n in self.done:
n.data['invalid'] = []
n.data['invalid_by'] = []
run = True
def satisfy_criteria(self, dependency, fromNode=None, read_only=False):
"""
Satisfy the given criteria for a dependency detween:
fromNode ---> dependency.node (dependency.criteria)
"""
# If there are no criteria, mark as OK and use the first version
if 'version' not in dependency.criteria:
lg.debug("%sVersion not required ..." % (self.tab))
# No available versions
if 'versions' not in dependency.node.data:
lg.debug("%sNo version" % self.tab)
return
node = dependency.node
# already one selected - stay there
if 'selected_version' in node.data:
lg.debug("%sAlready selected version %s" % (self.tab, node.data['selected_version']))
return
old_version = None
selected = next(iter(dependency.node.data['versions'].keys()))
lg.debug("%sSelecting First version %s" % (self.tab, selected))
else:
# we have criteria (in this case version requirements)
node = dependency.node
old_version = None
if 'selected_version' in node.data:
old_version = node.data['selected_version']
# Get all available versions of this node
available = [ i for i in node.data['versions'] ] if 'versions' in node.data else []
valid = dependency.criteria['version']
if 'invalid' not in node.data:
node.data['invalid'] = []
if 'invalid_by' not in node.data:
node.data['invalid_by'] = []
# Hack! Give preference to the currently selected if any
if old_version is not None:
available.remove(old_version)
available.insert(0, old_version)
# For every allowed version TODO: separate function?
selected = False
for a in available:
# Skip invalid ones
if a in node.data['invalid']:
continue
lg.debug("%sChecking Version %s" % (self.tab, a))
aver = Version(a)
found = True
for v in valid:
lg.debug("%s Checking Rule %s" % (self.tab, v))
m = re.search("^(?P<op>[^0-9]*)(?P<ver>.*)", v)
m = m.groupdict()
vver = Version(m['ver'])
op = m ['op']
lg.debug("%s Checking %s%s%s" % (self.tab, aver, op, vver))
if op == "<":
result = aver < vver
elif op == ">":
result = aver > vver
elif op == "<=" or op == "=<":
result = aver <= vver
elif op == ">=" or op == "=>":
result = aver >= vver
elif op == "!":
result = aver != vver
else:
result = aver == vver
# Mark invalid ones
if result is False:
lg.debug("%s - INVALID %s" % (self.tab, a))
node.data['invalid'].append(a)
node.data['invalid_by'].append("%s(%s%s)" % (fromNode, op, v))
if selected == a:
selected = False
# No need to continue on validity rulez. This is INVALID
found = False
break
# END OF For inner
# If we have a selection, use it
if found and selected is False:
lg.debug("%sSelecting version %s" % (self.tab, a))
selected = a
# END OF For outer
# Check if we failed
if selected is False:
msg = "Could not find appropriate version for %s" % (node.name)
lg.critical(msg)
raise Deadlock(msg, node)
# Uncomment to block on CDs that need to modify versions
#if read_only is True and selected != old_version:
#msg = "Could not set version from %s to %s for %s" % (old_version, selected, node.name)
## TODO: Remove
#if old_version is None:
#raise RuntimeError("WTF??? THIS DOES NOT MAKE SENSE")
#raise CircularDeadlock(msg, node, selected)
# We got a version
# Check with the old one
lg.debug("%sChecking %s (new) == %s (old)" % (self.tab, selected, old_version))
if selected == old_version:
lg.debug("%sStaying on the same version" % self.tab)
return False
# Update version!
lg.debug("%sSetting version %s to %s" % (self.tab, selected, node.name))
dependency.node.data["selected_version"] = selected
# If here we have a new version! With new version we have new
# dependencies for that node.
#
#
# Brain-storming:
#
# - This does not affect Nodes already accepted since they only left
# valid versions and thus the one we choose is valid
# - Future nodes have not yet been parsed in the recursion
# - Circular Dependencies (CD) should not affect this change. A CD is not
# allowed to change versions (read_only). We know that previous nodes
# will not be affected but what about the new dependencies?
#
newVerDeps = node.data['versions'][selected]
lg.debug("%sSetting new dependencies %s" % (self.tab, [i.toString(node) for i in newVerDeps]))
node.resetDeps()
dependency.node.deps = newVerDeps
# Notify for circular successful change to RE-START with the
# current node in the required version!
if read_only is True and selected != old_version:
raise CircularDeadlock("circular successful change", node, selected)
# We have changed version and dependencies
return True
def _resolve(self, dependency, fromNode=None):
if dependency.node in self.done:
lg.debug("%sSkipping already done %s" % (self.tab, dependency.toString(fromNode)))
return
lg.debug("%sGoing for %s" % (self.tab, dependency.toString(fromNode)))
self.proc.append(dependency.node)
# Set a version for this node if not set (based on the
# given criteria)
changed = self.satisfy_criteria(dependency, fromNode)
# for every dependency of the current node/version
for req in dependency.node.deps:
# handle new nodes (new to the recursion)
if req.node not in self.proc:
self.tab = self.tab+' '*4
self._resolve(req, dependency.node)
self.tab = self.tab[:-4]
continue
# handle Circular Deps (CDs)
lg.debug("%sCircular dependency %s" % (self.tab, req.toString(fromNode)))
# See if we can satisfy without changing
# If we can modify, we will do so but the read_only flag will raise
# a CircularDeadlock Exception which will cause a partial clean up
# and restart
self.satisfy_criteria(req, dependency.node, read_only=True)
lg.debug("%sCircular dependency already resolved %s" % (self.tab, req.toString(fromNode)))
# Done with this node!
lg.debug("%sResolved %s" % (self.tab, dependency.toString(fromNode)))
# Not processing anymore
self.proc.remove(dependency.node)
# Update or store "final" version
if dependency.node in self.done:
lg.debug("%sUpdating %s" % (self.tab, dependency.node.name))
self.done[self.done.index(dependency.node)] = dependency.node
else:
lg.debug("%sStoring %s" % (self.tab, dependency.node.name))
self.done.append(dependency.node)
def simple(deadlock=False):
# Create version nodes
a = VersionNode("a")
b = VersionNode("b")
c = VersionNode("c")
d = VersionNode("d")
e = VersionNode("e")
f = VersionNode("f")
# Add dependencies on versions
a.addDep2Version("1.4", Dependency(b, {"version": [">=0.1"]}))
a.addDep2Version("1.4", Dependency(d))
b.addVersion("0.1", [Dependency(e, {"version": [">=0.2", "!0.2"]}),
Dependency(c)])
b.addVersion("0.4", [Dependency(e, {"version": [">=0.2", "!0.3"]}),
Dependency(c)])
c.addDep2Version("15.1.100", Dependency(d, {"version": ["!1.2"]}))
# Circular
d.addVersion("1.2", [Dependency(b)] )
d.addVersion("1.3", [Dependency(b, {"version": ["=>0.2"]})])
e.addVersion("0.1", []) # No deps
e.addVersion("0.2", [Dependency(f)]) # No deps
e.addVersion("0.3", []) # No deps
# Fake deadlock on circular dependency
if deadlock:
f.addVersion("4.1", [Dependency(b, {"version": ["<0.2"]})])
else:
f.addVersion("4.1", [])
dr = DepRes()
try:
dr.resolve(Dependency(a))
except Deadlock as d:
lg.error(d.message)
return
lg.debug("DONE: %s" % (','.join([i.toString() for i in dr.done]) ) )
def get_version():
version = ""
for d in range(0,3):
if version != "":
version += '.'
version += str(randint(0,10))
return version
def choose_version(node):
return choice(node.data["versions"].keys())
def random():
nodes = []
# Create nodes!
for i in range(0,1000):
job="job_%d" % i
lg.debug("Adding node %s" % job)
nodes.append(VersionNode(job))
for v in range(0,3):
version = get_version()
lg.debug(" Adding version %s" % version)
nodes[-1].addVersion(version, [])
# Mess them up
for n in nodes:
for m in nodes:
if n==m:
continue
# Random probability they are n requires m
prob=randint(0,1000)
prob2=randint(0,1000)
# connected but no version restrictions
if prob2 < 3: # 2
nver = choose_version(n)
#lg.debug ("%s version %s depends on %s" % (n.name, nver, m.name))
n.addDep2Version(nver, Dependency(m))
continue
if prob < 1:
nver = choose_version(n)
mver = choose_version(m)
# Add operation ?
op = choice(["!", "<=", ">="]) # removed "<", ">", "="
#lg.debug ("%s version %s depends on %s version %s%s" % (n.name, nver, m.name, op, v))
n.addDep2Version(nver, Dependency(m, {"version": [op+mver]}))
continue
# ...
dr = DepRes()
j = choice(nodes)
v = choice(j.data['versions'].keys())
try:
lg.debug("Checking %s:%s" % (j.name,v))
dr.resolve(Dependency(j,{"version": [v]}))
lg.info("DONE: %s" % (','.join([i.toString() for i in dr.done]) ) )
lg.info("Nodes Count %d" % len(dr.done))
except Deadlock as d:
lg.error("Cannot match version")
#lg.error(d.node.data)
lg.error(d.message)
lg.info("In %d rounds..." % dr.rounds)
if __name__ == "__main__":
#simple(True)
random()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment