Lichen

Changeset

724:3d89317842b9
2017-03-13 Paul Boddie raw files shortlog changelog graph Made dependency ordering a generic function for possible use elsewhere.
common.py (file) importer.py (file)
     1.1 --- a/common.py	Mon Mar 13 01:49:11 2017 +0100
     1.2 +++ b/common.py	Mon Mar 13 14:47:44 2017 +0100
     1.3 @@ -987,6 +987,56 @@
     1.4  def same(s1, s2):
     1.5      return set(s1) == set(s2)
     1.6  
     1.7 +def order_dependencies(all_depends):
     1.8 +
     1.9 +    """
    1.10 +    Produce a dependency ordering for the 'all_depends' mapping. This mapping
    1.11 +    has the form "A depends on B, C...". The result will order A, B, C, and so
    1.12 +    on.
    1.13 +    """
    1.14 +
    1.15 +    # Record the reverse dependencies, making a mapping of the form
    1.16 +    # "B is needed by A", "C is needed by A", and so on.
    1.17 +
    1.18 +    usage = {}
    1.19 +
    1.20 +    # Record path-based dependencies.
    1.21 +
    1.22 +    for key in all_depends.keys():
    1.23 +        usage[key] = set()
    1.24 +
    1.25 +    for key, depends in all_depends.items():
    1.26 +        for depend in depends:
    1.27 +            init_item(usage, depend, set)
    1.28 +            usage[depend].add(key)
    1.29 +
    1.30 +    # Produce an ordering by obtaining exposed items (required by items already
    1.31 +    # processed) and putting them at the start of the list.
    1.32 +
    1.33 +    ordered = []
    1.34 +
    1.35 +    while usage:
    1.36 +        have_next = False
    1.37 +
    1.38 +        for path, n in usage.items():
    1.39 +            if not n:
    1.40 +                ordered.insert(0, path)
    1.41 +                depends = all_depends.get(path)
    1.42 +
    1.43 +                # Reduce usage of the referenced items.
    1.44 +
    1.45 +                if depends:
    1.46 +                    for depend in depends:
    1.47 +                        usage[depend].remove(path)
    1.48 +
    1.49 +                del usage[path]
    1.50 +                have_next = True
    1.51 +
    1.52 +        if not have_next:
    1.53 +            raise ValueError, usage
    1.54 +
    1.55 +    return ordered
    1.56 +
    1.57  # General input/output.
    1.58  
    1.59  def readfile(filename):
     2.1 --- a/importer.py	Mon Mar 13 01:49:11 2017 +0100
     2.2 +++ b/importer.py	Mon Mar 13 14:47:44 2017 +0100
     2.3 @@ -23,7 +23,7 @@
     2.4  from errors import ProgramError
     2.5  from os.path import exists, extsep, getmtime, join
     2.6  from os import listdir, makedirs, remove
     2.7 -from common import init_item, readfile, writefile
     2.8 +from common import init_item, order_dependencies, readfile, writefile
     2.9  from modules import CachedModule
    2.10  from referencing import Reference
    2.11  import inspector
    2.12 @@ -673,44 +673,10 @@
    2.13  
    2.14          self.condense_dependencies()
    2.15  
    2.16 -        # Record the number of modules using or depending on each module.
    2.17 -
    2.18 -        usage = {}
    2.19 -
    2.20 -        # Record path-based dependencies.
    2.21 -
    2.22 -        for path in self.depends.keys():
    2.23 -            usage[path] = set()
    2.24 -
    2.25 -        for path, depends in self.depends.items():
    2.26 -            for origin in depends:
    2.27 -                init_item(usage, origin, set)
    2.28 -                usage[origin].add(path)
    2.29 -
    2.30 -        # Produce an ordering by obtaining exposed modules (required by modules
    2.31 -        # already processed) and putting them at the start of the list.
    2.32 -
    2.33 -        ordered = []
    2.34 -
    2.35 -        while usage:
    2.36 -            have_next = False
    2.37 -
    2.38 -            for path, n in usage.items():
    2.39 -                if not n:
    2.40 -                    ordered.insert(0, path)
    2.41 -                    depends = self.depends.get(path)
    2.42 -
    2.43 -                    # Reduce usage of the referenced objects.
    2.44 -
    2.45 -                    if depends:
    2.46 -                        for origin in depends:
    2.47 -                            usage[origin].remove(path)
    2.48 -
    2.49 -                    del usage[path]
    2.50 -                    have_next = True
    2.51 -
    2.52 -            if not have_next:
    2.53 -                raise ProgramError("Modules with unresolvable dependencies exist: %s" % ", ".join(usage.keys()))
    2.54 +        try:
    2.55 +            ordered = order_dependencies(self.depends)
    2.56 +        except ValueError, exc:
    2.57 +            raise ProgramError("Modules with unresolvable dependencies exist: %s" % ", ".join(exc.args[0].keys()))
    2.58  
    2.59          if "__main__" in ordered:
    2.60              ordered.remove("__main__")