Source code for jasy.abstract.Sorter

#
# Jasy - Web Tooling Framework
# Copyright 2010-2012 Zynga Inc.
# Copyright 2013-2014 Sebastian Werner
#

import jasy.core.Console as Console


[docs]class SorterError(Exception): """Error which is throws when sorting could not be done because of circular dependencies.""" pass
[docs]class AbstractSorter: """ Sorts a final list of items according to their requirements. This class is not type depended e.g. is used for both scripts and styles. """ def __init__(self, resolver): # Shorthand references self.resolver = resolver self.profile = resolver.profile self.permutation = resolver.permutation # Build item name dict (id => item) items = self.resolver.getIncluded() self.items = dict([(item.getId(), item) for item in items]) # Initialize fields self.__loadDeps = {} self.__circularDeps = {} self.__sorted = []
[docs] def getSorted(self): """Returns the sorted item list (caches result)""" if not self.__sorted: Console.debug("Sorting items...") Console.indent() for itemId in self.items: self.__getLoadDeps(self.items[itemId]) result = [] required = self.resolver.getRequired() for item in required: if item not in result: # Console.debug("Start adding with: %s", item) self.__addSorted(item, result) Console.outdent() self.__sorted = result return self.__sorted
def __addSorted(self, item, result, postponed=False): """Adds a single item and its dependencies to the sorted result list.""" loadDeps = self.__getLoadDeps(item) for depObj in loadDeps: if depObj not in result: self.__addSorted(depObj, result) if item in result: return # Console.debug("Adding item: %s", item) result.append(item) # Insert circular dependencies as soon as possible if item in self.__circularDeps: circularDeps = self.__circularDeps[item] for depObj in circularDeps: if depObj not in result: self.__addSorted(depObj, result, True) def __getLoadDeps(self, item): """Returns load time dependencies of given item.""" if not item in self.__loadDeps: self.__getLoadDepsRecurser(item, []) return self.__loadDeps[item] def __getLoadDepsRecurser(self, item, stack): """ This is the main routine which tries to control over a system of unsorted items. It directly tries to fullfil every dependency a item have, but has some kind of exception based loop protection to prevent circular dependencies from breaking the build. It respects break information given by file specific meta data, but also adds custom hints where it found recursions. This lead to a valid sort, but might lead to problems between exeactly the two affected items. Without doing an exact execution it's not possible to whether found out which of two each-other referencing items needs to be loaded first. This is basically only interesting in cases where one item needs another during the definition phase which is not the case that often. """ if item in stack: stack.append(item) msg = " >> ".join([x.getId() for x in stack[stack.index(item):]]) raise SorterError("Circular Dependency: %s" % msg) stack.append(item) itemDeps = self.getItemDependencies(item) itemBreaks = self.getItemBreaks(item) result = set() circular = set() # Respect manually defined breaks # Breaks are dependencies which are down-priorized to break # circular dependencies between items. for breakObj in itemBreaks: if breakObj.getId() in self.items: circular.add(breakObj) # Now process the deps of the given item loadDeps = self.__loadDeps for depObj in itemDeps: if depObj is item: continue depName = depObj.getId() if depObj in itemBreaks: Console.debug("Manual Break: %s => %s" % (item, depObj)) pass elif depObj in loadDeps: result.update(loadDeps[depObj]) result.add(depObj) else: current = self.__getLoadDepsRecurser(depObj, stack[:]) result.update(current) result.add(depObj) # Sort dependencies by number of other dependencies # For performance reasions we access the __loadDeps # dict directly as this data is already stored result = sorted(result, key=lambda depObj: len(self.__loadDeps[depObj])) loadDeps[item] = result if circular: self.__circularDeps[item] = circular return result