Recursively finding dependencies in Python
Here is how you can find a list of dependencies of Python classes, given that a class has an
attribute depends. This list is not topologically sorted, but it is very easy to use with a topological sort algorithm.
Using recursion and generator it is possible to get a complete list of dependecies given that
start_dependecie = {'A': 'B'}This means that class A depends on class B. But what if class B depends on N other classes?
The following will do the job:
#!/usr/bin/env python
def _yield_name_dep(rules_deps):
# yield all rules by their name and dependencies
for rule, dep in rules_deps.items():
if not dep:
yield rule, dep
continue
else:
yield rule, dep
for ii in dep:
i = getattr(rules, ii)
instance = i()
if instance.depends:
new_dep={str(instance): instance.depends}
for dep in _yield_name_dep(new_dep):
yield dep
else:
yield str(instance), instance.dependsHere is how you can easily test the above method:
demo_class_content ="""
class A(object):
depends = 'B'
def __str__(self):
return self.__class__.__name__
class B(object):
depends = ('C','F')
def __str__(self):
return self.__class__.__name__
class C(object):
depends = ('D', 'E')
def __str__(self):
return self.__class__.__name__
class D(object):
depends = None
def __str__(self):
return self.__class__.__name__
class F(object):
depends = 'E'
def __str__(self):
return self.__class__.__name__
class E(object):
depends = None
def __str__(self):
return self.__class__.__name__
"""
with open('demo_classes.py', 'w') as clsdemo:
clsdemo.write(demo_class_content)
import demo_classes as rules
rule_start={'A': 'B'}
recursion_counter = 0
def _yield_name_dep(rules_deps):
global recursion_counter
recursion_counter = recursion_counter +1
# yield all rules by their named and dependencies
for rule, dep in rules_deps.items():
if not dep:
yield rule, dep
continue
else:
yield rule, dep
for ii in dep:
i = getattr(rules, ii)
instance = i()
if instance.depends:
new_dep={str(instance): instance.depends}
for dep in _yield_name_dep(new_dep):
yield dep
else:
yield str(instance), instance.depends
if __name__ == '__main__':
rule_dependencies = list(set(_yield_name_dep(rule_start)))
print recursion_counter
print rule_dependenciesThe output should be:
4
[('B', ('C', 'F')), ('C', ('D', 'E')), ('E', None), ('F', 'E'), ('D', None), ('A', 'B')]Written by Oz
Related protips
4 Responses
If your only requirement here is to get a full list of dependencies, why not use inspect.getmro? For example: http://codepad.org/k7iGWYFf
Although I might be off with what your requirements are because I noticed there isn't any actual inheritance going on in your example.
Hi Demian,
First of all, I didn't know about ìnspect.mro. Thanks for that one. Second, yep, my idea was that these class can represent anything (e.g. rules, package dependencies) so they don't necessarily inherit like Python objects, but the have a dependencies. Kind of like decencies solving in packages. So, it was done for the exercise, and I wanted to share my experience and see if I get some feedback.
No worries, always happy to share the knowledge of the Python stdlib :)
I'm still at a bit of a loss as to how this can't be solved by common Python functions. i.e. if your requirements are to add package dependencies, that should be solved by pip/setuptools (requirements.txt or setup.py or a combination of). Python has introspection capabilities second to none. If you need to look up the inheritance tree of a class, you can easily do so (although I understand that this isn't your particular use case).
Here are the major flaws I see with your solution (of course, just IMHO, so take it with a grain of salt :)):
- It doesn't conform to standards. Someone looking at this (especially one who has spent quite a bit of time with Python) is likely to to say "wat?". The stdlib and supporting cast should /always/ be exhausted prior to rolling your own solution. Not only will you benefit from a solution that's thoroughly tested (and reviewed by core devs), but you'll also benefit from learning about areas of the stdlib that you were previously unaware.
- Huge margin for human error. At any point, a programmer can forget to add a dependency. As your code base grows, I'd imagine that the problems would be more and more difficult to track down.
- The attribute name is confusing. "Dependencies" in OO-land (not saying that Python is strictly OO, I'm simply referring to your examples) means "base classes that this class depends on". Introducing a "depends" attribute to a class that has a different function would likely be confusing to those reading your code. (I also realize that this can be trivially changed, just calling it out as it's in your example)
With all three arguments you are right.
I would always opt for stdlib. However, with packages I didn't necessarily mean Python packages.
The idea was to write a code that should work on similar cases. Not always on classes.
Imagine you wrote your own package manager (for Distro X) then you will need something.
Yep, you are right dependencies are forgotten. This is the case with RPMs or DEBs. Package x gets dependency y and the maintainer forgets to add it.
This code was not meant to conform to standard.
It was slightly altered from a project I worked for which something similar to package management. In order not complicate stuff and make it clear for fellow programmers, I chose to talk about classes. It was a wrong choice.
Never the less, I find the discussion, interesting and I learned already a lot just from the discussion with you. Therefore thank you for the discussion and extended comments.
