funcs.py

Go to the documentation of this file.

#................................................................................
# Copyright (c) 2009,2010,2011 David Car, david.car7@gmail.com
# Copyright (c) 2009,2010,2011 Michael List, michael.list@gmail.com
#
# This program is free software; you can redistribute it and/or modify it under
# the terms of the GNU General Public License as published by the Free Software
# Foundation; either version 2 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, write to the Free Software Foundation, Inc., 59 Temple
# Place, Suite 330, Boston, MA 02111-1307 USA
#..........................................................................
__all__=['pack',
         'tab',
         'indent', 'indentNoStrip',
         'And', 'Or', 'Not', 'isLeaf', 'startsWith', 'endsWith',
         'genBlockGraph',
         'depGraph',
         'topoSort']

from sets import ASet
import copy
import os

#................................................................................
# Global functions and defs
#................................................................................
#.................... Lambda Function defintions ................................
# Remove all white space from a string
pack = lambda x: x.strip().replace(' ','')

# Determine indentation of a line
tab = lambda x: len(x)-len(x.lstrip(' '))

#................................................................................
def indent(nspaces, s):
    '''Function padding a string with leading spaces.  Existing leading spaces
    of string are removed prior to padding.

    '''
    return ' '*nspaces+s.lstrip(' ')

def indentNoStrip(nspaces, s):
    '''Function padding a string with leading spaces.

    '''
    return ' '*nspaces+s

#................................................................................
# Filter function (return True/False given a pair) Combinators
#................................................................................

# Returns filter function of logical AND of two filter functions
def And(f1, f2):
    return lambda (x,v): f1((x,v)) and f2((x,v))

# Returns filter function of logical OR of two filter functions
def Or(f1, f2):
    return lambda (x,v): f1((x,v)) or f2((x,v))

# Returns filter function of logical NOT of filter function
def Not(f1):
    return lambda (x,v): (not f1((x,v)))

#................................................................................
# Filter functions
#................................................................................
isLeaf = lambda (x,v): v.children().isEmpty()

def startsWith(s):
    return lambda (x,v): x.startswith(s)

def endsWith(s):
    return lambda (x,v): x.endswith(s)

#................................................................................
# Generate a graphviz graph of a block tree
#................................................................................
def genBlockGraph(blk):
    '''Generate a graphviz graph of the given block and return it.

    blk : a Block instance

    '''

    try:
        import pygraphviz as gv
    except:
        print "You need the pygraphviz module for this function"
        return

    def _makeName(blk):
        return ' '.join([blk._blockType,blk.name()])

    def _traverse(gph, blk):
        _name = _makeName(blk)
        gph.add_node(_name)
        for c in blk.children().values():
            _cname = _makeName(c)
            gph.add_edge(_name, _cname)
            _traverse(gph, c)
        
        return gph

    gph = gv.AGraph(directed=False)
    gph.graph_attr['orientation']='portrait'
    gph.node_attr['shape'] = 'box'
    gph.node_attr['margin'] = '0.,0.'
    gph.node_attr['fontsize'] = '8'

    return _traverse(gph, blk)
    
#................................................................................
# Helper functions (not sure where these should go for the moment)
#................................................................................
def depGraph(blocks, table, silent=True):
    '''Generate dependency graph which is simply a dictionary where each entry is
    the node name and contains a list of sets.  The first set is the nodes
    connected to incoming edges, the second set is the nodes connected to
    outgoing edges.  The graph is generated for the dependencies of the types
    in the block list.  For example, if the list of blocks are of type AFile,
    then the dependencies found are between AFiles; if modules, then modules,
    etc...  Use the output of this function with topoSort() to get an
    non-unique ordering of dependencies.

    Input
    -----
    blocks : list of blocks to find the build order for
    table : global symbol table to use

    '''

    if len(blocks) == 0: return
    theType = type(blocks[0])
    diGraph = {}.fromkeys([blk.name() for blk in blocks])
    for blk in blocks:
        diGraph[blk.name()] = (ASet(),ASet())

    jc = table.joinCharacter()
    for blk in blocks:
        depList = copy.copy(blk.dependencies())
        visited = copy.copy(depList)
        while len(depList) > 0:
            dep = depList.pop()
            _dep = blk.resolveSymbol(dep)
            root = table.filter(startsWith(_dep+jc)).values()
                
            if len(root) > 1:
                msg = "Ambiguous dependency for "
                msg += "build order of %s%s"%(blk.name(), os.linesep)
                for x in root:
                    childName = str( x.name() )
                    parentName = str( x.parent().name() )
                    msg += "Found (%s) in (%s)%s"%( childName, parentName, 
                                                  os.linesep )
                    
                raise Exception(msg)
            elif len(root) == 0:
                if not silent:
                    print "Could not find symbol %s in table"%str(_dep,)
                continue

            # Add root's dependencies to depList and continue
            root = root[0].upTo(theType)

            if root is blk:
                if blk.contains(_dep) : continue
                msg = "Cyclic dependency detected:"+os.linesep
                msg += "%s <-> %s%s"%(blk.name(), _dep, os.linesep)
                msg += "%s%s"%(str(blk.dependencies()), os.linesep)
                print "%sWARNING!!!!! %s%s"%(5*os.linesep, msg, 5*os.linesep)
                raise Exception('Cyclic dependency!!!')
                
            # Dependency is not among group
            if root is None or root not in blocks: continue  

            # Add root's name to the blkSet and it's dependencies to the depList
            diGraph[blk.name()][0].add(root.name()) # incoming for blk
            diGraph[root.name()][1].add(blk.name()) # outgoing for root
            depList.update([x for x in root.dependencies()
                            if x not in visited])
            visited.update(root.dependencies())

            # Remove dep again just in case it also existed in root's
            # dependency list
            depList.discard(dep); depList.discard(_dep) 
        
    return diGraph

#................................................................................
def topoSort(diGraph, prune=True):
    '''Topological sort of a given diGraph.  The diGraph is represented as a
    dictionary whose keys are the node names and each key entry contains a
    2-tuple of lists/sets.  The first is the keys of nodes connected on
    incoming edges, the second is the keys of nodes connected on outgoing
    edges.
    
    Example:
    -------
    {'node1':(['a','b','c'],['r','s','t']}

    means 'node1' has nodes ['a','b','c','d'] connected on 'incoming' edges,
    i.e. 'node1' depends on these nodes.  Likewise, nodes ['r','s','t'] are
    dependent on 'node1' because they are connected on 'outgoing' edges.
    
    Input
    -----
    diGraph : the diGraph
    prune : boolean flag to prune isolated nodes from the list

    '''
    # Determine an order (not unique). Sort based on the digraph.  Filter out
    # isolated nodes on the graph if prune=True, i.e. nodes that do not have
    # any incoming or outgoing edges.
    noDeps = []
    orderList = []

    # Incoming edge counter
    diGraph_ = copy.deepcopy(diGraph)
    incoming = {}.fromkeys(diGraph.keys(),0)
    for name,pair in diGraph.items():
        incoming[name] = len(pair[0])

    for name,pair in diGraph.items():
        if len(pair[0]) == 0:
            if not prune:
                noDeps.append(name)
            elif len(pair[1]) != 0:
                noDeps.append(name)

    while len(noDeps) > 0:
        node = noDeps.pop()
        orderList.append(node)
        for other in diGraph[node][1]:
            # Decrement the incoming edge counter
            diGraph_[other][0].discard(node)
            incoming[other] -= 1
            if incoming[other] == 0:
                noDeps.append(other)

    #................................................................................
    # Sanity Check:  If the incoming edge entries do not sum to zero,
    # then we have some sort of cyclic dependency going on.  Display the nodes
    # that have this condition and throw a big fat WARNING!
    #................................................................................
    if sum(incoming.values()) != 0:
        print '*'*80
        print '*'+'WARNING!!!'.center(78)+'*'
        print '*'*80
        print 'You appear to have a cyclic dependency in your build'
        print 'Please look at the relationships between the following files:'
        for f,n in incoming.items():
            if n != 0:
                print ' '.join([f, 'has remaining connections:'])
                dep = diGraph_[f][0]
                for other in dep:
                    print '\t %s'%(other,)
        print '*'*80
    #................................................................................
                
    return orderList