Adding some dependency analysis scripts
authorJames Aley <jamesa@symbian.org>
Wed, 04 Nov 2009 17:40:17 +0000
changeset 5 842a773e65f2
parent 4 60053dab7e2a
child 202 f6ae410bd493
Adding some dependency analysis scripts
jamesa/_common.py
jamesa/build_graph.py
jamesa/generate_oby.py
jamesa/get_deps.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jamesa/_common.py	Wed Nov 04 17:40:17 2009 +0000
@@ -0,0 +1,64 @@
+# Copyright (c) 2009 Symbian Foundation Ltd
+# This component and the accompanying materials are made available
+# under the terms of the License "Eclipse Public License v1.0"
+# which accompanies this distribution, and is available
+# at the URL "http://www.eclipse.org/legal/epl-v10.html".
+#
+# Initial Contributors:
+# Symbian Foundation Ltd - initial contribution.
+# 
+# Contributors:
+#
+# Description:
+# Data structure code used by dependency analysis scripts.
+
+"""Common data structure code for build_graph.py and tools.
+"""
+
+__author__ = 'James Aley'
+__email__ = 'jamesa@symbian.org'
+__version__ = '1.0'
+
+class Node:
+    """Node objects are similar to the Symbian notion of a Component, but
+    they are defined in a practical way for ROM building with less intuitive meaning.
+
+    A Node object is identified by:
+      - the path to bld.inf
+      where by:
+        - the bld.inf file contains a PRJ_MMPFILES section with a least one MMP file.
+    """
+ 
+    def __str__(self):
+        """Represent node as string, using node_path
+        """
+        return self.node_path
+
+    def __init__(self, path):
+        """Initialize new Node with given path to bld.inf
+        """
+        # path to the bld.inf file associating these mmp components
+        self.node_path = ''
+
+        # list of node_path values for Node objects owning referenced from
+        # the MMP files
+        self.dependencies = []
+
+        # contents of this Node, likely not used algorithmically but might
+        # be useful later for reporting.
+        self.mmp_components = []
+
+        # the following are nodes that also satisfy the dependencies (in part), and may
+        # be of interest when building a ROM.
+        self.interesting = []
+
+        # dependencies that were not linked to another component in the source tree
+        self.unresolved = []
+
+        self.node_path = path
+
+    def add_deps(self, deps):
+        """Add dependencies to the list, filtering duplicates
+        """
+        self.dependencies.extend(filter(lambda x: x not in self.dependencies, deps))
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jamesa/build_graph.py	Wed Nov 04 17:40:17 2009 +0000
@@ -0,0 +1,343 @@
+# Copyright (c) 2009 Symbian Foundation Ltd
+# This component and the accompanying materials are made available
+# under the terms of the License "Eclipse Public License v1.0"
+# which accompanies this distribution, and is available
+# at the URL "http://www.eclipse.org/legal/epl-v10.html".
+#
+# Initial Contributors:
+# Symbian Foundation Ltd - initial contribution.
+# 
+# Contributors:
+#
+# Description:
+# Generates a dependency graph of the Symbian source tree.
+
+"""Build a graph of component dependencies from Symbian OS source code.
+The graph is serialized to a file, which can then be used by other scripts to extract data.
+
+The script works by recursing over the directory structure from the specified root and then
+analyzing all bld.inf files to locate referenced production MMP files. These are then processed
+for target and dependency information.
+
+You can use the supplementary scripts to then extract useful information from the generated graph
+file.
+"""
+
+from optparse import OptionParser
+from _common import Node
+
+import re
+import os
+import sys
+import pickle
+import logging
+
+__author__ = 'James Aley'
+__email__ = 'jamesa@symbian.org'
+__version__ = '1.0'
+
+# Constants for various default config
+_LOG_FORMAT = '%(levelname)s: %(message)s'
+_MAX_PATH = 260
+
+# Precompile regexes for better performance
+# - Comment filtering
+_RE_CLEAN_INLINE = '^(.*)//.*$'
+_RE_MULTILINE_OPEN = '^(.*)/\\*.*$'
+_RE_MULTILINE_CLOSE = '^.*\\*/(.*)$'
+_p_clean_inline = re.compile(_RE_CLEAN_INLINE)
+_p_multiline_open = re.compile(_RE_MULTILINE_OPEN)
+_p_multiline_close = re.compile(_RE_MULTILINE_CLOSE)
+
+# - MMP file Parsing
+_RE_TARGET = '^\\s*TARGET\\s+([^\\s]+).*$'
+_RE_PLAIN_TARGET = '^\\s*([^\\s\\.]+)\\.?[^\\s]?\\s*'
+_RE_COMPLEX_TARGET = '.*\\((.+),.+\\).*'
+_RE_LIBRARY = '^\\s*[^\\s]*LIBRARY.*\\s+([^\\s]+.*)$'
+_RE_START = '^\\s*START.*$'
+_RE_END = '\\s*END.*$'
+_p_target = re.compile(_RE_TARGET, re.I)
+_p_plain_target = re.compile(_RE_PLAIN_TARGET)
+_p_complex_target = re.compile(_RE_COMPLEX_TARGET)
+_p_library = re.compile(_RE_LIBRARY, re.I)
+_p_start = re.compile(_RE_START)
+_p_end = re.compile(_RE_END)
+
+# - BLD.INF file parsing
+_RE_PRJ_MMPFILES = '^\\s*PRJ_MMPFILES\\s*$'
+_RE_OTHER_SECTION = '^\\s*PRJ_[a-z]+\\s*$'
+_p_prj_mmpfiles = re.compile(_RE_PRJ_MMPFILES, re.I)
+_p_other_section = re.compile(_RE_OTHER_SECTION, re.I)
+
+# Set up a logging instance for output
+logging.basicConfig(format=_LOG_FORMAT, level=logging.WARNING, stream=sys.stdout)
+
+# Cache dictionary to marry Nodes to eachother
+node_cache = {}
+
+# Dictionary representing the dependency graph.
+# Each key identifies the node in the graph, where the value is the node
+# object itself including the arcs to other node_path keys that it requires.
+graph = {}
+
+def rstrip(string, suffix):
+    """Like Python's __str__.rstrip(chars), but it treats the chars as
+    a contiguous string and only strips that complete ending.
+    """
+    if string.endswith(suffix):
+        string = string[:len(string) - len(suffix)]
+    return string
+
+def clean_binary_name(binary_name):
+    """Strips the extension off of binary names so that references to .lib
+    are associated with the correct binaries.
+    """
+    match_complex_target = _p_complex_target.match(binary_name)
+    if match_complex_target:
+        binary_name = match_complex_target.groups()[0].lower().strip()
+    else:
+        match_plain_target = _p_plain_target.match(binary_name)
+        if match_plain_target:
+            binary_name = match_plain_target.groups()[0].lower().strip()
+    return binary_name
+
+def looks_like_test(path):
+    """Returns true if a path looks like it refers to test components.
+    The script does its best to filter test components, as many are missing
+    from the source tree and they're not interesting with respect to building
+    production ROM images anyway.
+    """
+    conventions = ['tsrc', 'test']
+    for convention in conventions:
+        # Iterate through likely test component conventions, if
+        # we match one, return True now
+        if os.path.sep + convention + os.path.sep in path.lower():
+            return True
+    # Otherwise, nothing found, so return False
+    return False
+
+def without_comments(source_file):
+    """Generator function, will yield lines of the source_file object (iterable)
+    with commented regions removed.
+    """
+    multiline_region = False
+    for line in source_file:
+        match_multiline_close = _p_multiline_close.match(line)
+        if match_multiline_close:
+            # Close Comments, strip to the left of the comment
+            multiline_region = False
+            line = match_multiline_close.groups()[0]
+        if multiline_region:
+            # Skip the line if we're in a commented region
+            continue
+        match_multiline_open = _p_multiline_open.match(line)
+        if match_multiline_open:
+            # Open comments, strip to the right of the comment
+            multiline_region = True
+            line = match_multiline_open.groups()[0]
+        match_inline = _p_clean_inline.match(line)
+        if match_inline:
+            # Strip the line to only the left of the comment
+            line = match_inline.groups()[0]
+        if line:
+            yield line
+
+def parse_mmp(mmp_path):
+    """Read an mmp file, return a tuple of the form:
+        (target, required_target_list)
+    """
+    logging.debug('parse_mmp(%s)' % (mmp_path, ))
+    
+    mmp_file = None
+    try:
+        mmp_file = open(mmp_path)
+    except IOError, e:
+        logging.error('Unable to open: %s' % (mmp_path, ))
+        return
+
+    # Iterate through MMP file lines to find the TARGET and LIBRARY statements
+    # Note that Symbian projects can compile to different TARGET objects depending on
+    # precompiler macros, so we must index all possible target names.
+    targets = []
+    libs = []
+    resource_block = False
+    for line in without_comments(mmp_file):
+        match_start = _p_start.match(line)
+        if match_start:
+            resource_block = True
+        match_end = _p_end.match(line)
+        if match_end:
+            resource_block = False
+        if resource_block:
+            # need to avoid resource target sections
+            continue
+        match_target = _p_target.match(line)
+        match_library = _p_library.match(line)
+        if match_target:
+            clean_target = clean_binary_name(match_target.groups()[0])
+            targets.append(clean_target)
+        elif match_library:
+            libs_on_line = match_library.groups()[0].split()
+            for lib in libs_on_line:
+                clean_lib = clean_binary_name(lib)
+                libs.append(clean_lib)
+    mmp_file.close()
+
+    return (targets, libs)
+
+def new_node(path, ref_mmps, ref_testmmps):
+    """Construct a new node in the graph with the provided content.
+    """
+    logging.debug('new_node(%s, ref_mmps(%d), ref_testmmps(%d))' % (path, len(ref_mmps), len(ref_testmmps)))
+    node = Node(path)
+    
+    # Iterate the MMPs, read dependency and target information
+    for mmp in ref_mmps:
+        (targets, dependencies) = parse_mmp(mmp)
+        if len(targets) > 0:
+            for target in targets:
+                node.mmp_components.append(target)
+            node.add_deps(dependencies)
+
+    # Register the components in the cache, as later we will
+    # join the graph nodes by referring to this cache
+    for c in node.mmp_components:
+        if c in node_cache.keys():
+            existing = node_cache[c]
+            node_cache[c] = existing + [path]
+        else:
+            node_cache[c] = [path]
+
+    # Add this node to the graph
+    graph[path] = node
+
+def parse_bld_inf(path):
+    """Parse a bld.inf file to check to see if references MMP files.
+    For those MMP files included, parse them to build the node object.
+    """
+    logging.debug('parse_bld_inf(%s)' % (path, ))
+    
+    # List the files referenced from this bld.inf
+    ref_mmp = []
+    ref_testmmp = []
+    
+    bld_inf = None
+    try:
+        bld_inf = open(path, 'r')
+    except IOError, e:
+        logging.error('Unable to open: %s' % (path, ))
+        return
+
+    # Parse the bld_inf file, adding references MMP files to appropriate lists
+    projects_flag = False
+    for line in without_comments(bld_inf):
+        match_projects = _p_prj_mmpfiles.match(line)
+        match_other_section = _p_other_section.match(line)
+        if match_projects:
+            projects_flag = True
+        elif match_other_section:
+            projects_flag = False
+        if projects_flag and len(line) <= _MAX_PATH:
+            rel_name = rstrip(line.lower().strip(), '.mmp')
+            bld_inf_path = os.path.dirname(path)
+            test_path = os.path.join(bld_inf_path, rel_name + '.mmp')
+            test_path = os.path.realpath(test_path)
+            if os.path.exists(test_path):
+                ref_mmp.append(test_path)
+            else:
+                logging.warning('%s refers to %s but it does not exist!' % (path, test_path))
+    bld_inf.close()
+
+    # If we found some MMP files, then this is a new node
+    if len(ref_mmp) > 0:
+        new_node(path, ref_mmp, ref_testmmp)
+
+def make_nodes(not_used, dir_name, file_names):
+    """Call back function for os.path.walk: will analyse the file names, if
+    there are any bld.inf files, it will open them to see if they identify a
+    Node object and create them as appropriate
+    """
+    logging.debug('make_nodes(%s, %s)' % (dir_name, file_names))
+    if looks_like_test(dir_name):
+        return
+    for file_name in file_names:
+        if file_name.lower().endswith('.inf'):
+            abs_path = os.path.join(dir_name, file_name)
+            assert(os.path.exists(abs_path))
+            parse_bld_inf(abs_path)
+
+def connect_nodes():
+    """Walk through the graph and substute the contents of the dependency
+    list members at each node with references to the node_path of that which
+    builds the referenced component.
+
+    There will be instances where multiple graph nodes build overlapping
+    components. This will, in practice, mean that there are many ways of
+    building a suitable ROM for dependencies of one of these nodes.
+    """
+    unresolved_deps = []
+    for node_path in graph.keys():
+        node = graph[node_path]
+        resolved = []
+        for dep in node.dependencies:
+            if dep not in node_cache.keys():
+                logging.warning('Could not resolve %s for %s' % (dep, node.node_path))
+                if dep not in unresolved_deps:
+                    unresolved_deps.append(dep)
+                node.unresolved.append(dep)
+            else:
+                solutions = node_cache[dep]
+                proposed = solutions[0]
+                if proposed not in resolved:
+                    resolved.append(proposed)
+                node.interesting += filter(lambda x: x not in node.interesting, solutions[1:])
+        node.dependencies = resolved
+        graph[node_path] = node
+    if len(unresolved_deps) > 0:
+        logging.warning('There were %d unresolved dependencies.' % (len(unresolved_deps), ))
+
+def build_graph(root):
+    """Walk nodes from the directory root provided looking for bld.inf files.
+    Graph will be built from the referened production MMP files.
+    """
+    if not os.path.isdir(root):
+        logging.fatal('%s is not a directory, aborting...' % (root, ))
+        exit(1)
+    os.path.walk(root, make_nodes, None)
+    connect_nodes()
+
+def save_graph(path):
+    """Serialize the graph object to path. This will be a Python object pickle at
+    the highest available protocol version for this Python install.
+    """
+    graph_file = None
+    try:
+        graph_file = open(path, 'wb')
+    except IOError, e:
+        logging.error('Could not write graph to file: %s' % (repr(e), ))
+        exit(1)
+    pickle.dump(graph, graph_file, pickle.HIGHEST_PROTOCOL)
+    graph_file.close()
+
+# Main:
+if __name__ == '__main__':
+    parser = OptionParser()
+    parser.set_description(__doc__)
+    parser.add_option('-g', '--graph', dest='graph_file', 
+                      help='File name to write the graph to.', 
+                      metavar='GRAPH_FILE', default='dependencies.graph')
+    parser.add_option('-r', '--root', dest='graph_root',
+                      help='Directory to recursively build a graph from, usually root of source tree.',
+                      metavar='SOURCE_ROOT', default='.')
+    parser.add_option('-v', '--verbose', dest='verbose',
+                      help='Verbose logging, will show all warnings as graph is generated. Recommend redirect!',
+                      action='store_true', default=False)
+    (options, args) = parser.parse_args()
+    if not options.verbose:
+        logging.disable(logging.ERROR)
+    print 'Walking source from "%s"\nThis can take some time with large source trees...' % (options.graph_root, )
+    build_graph(options.graph_root)
+    print 'Found %d components consisting of %d binaries.' % (len(graph), len(node_cache))
+    print 'Wriing graph to %s' % (options.graph_file)
+    save_graph(options.graph_file)
+    print '...done!'
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jamesa/generate_oby.py	Wed Nov 04 17:40:17 2009 +0000
@@ -0,0 +1,212 @@
+# Copyright (c) 2009 Symbian Foundation Ltd
+# This component and the accompanying materials are made available
+# under the terms of the License "Eclipse Public License v1.0"
+# which accompanies this distribution, and is available
+# at the URL "http://www.eclipse.org/legal/epl-v10.html".
+#
+# Initial Contributors:
+# Symbian Foundation Ltd - initial contribution.
+# 
+# Contributors:
+#
+# Description:
+# Create a barebones OBY file from a dependency report text file.
+
+"""Take a report generated by get_deps.py and attempt to create an OBY
+file to build a ROM with the dependency list.
+"""
+
+from build_graph import without_comments
+from optparse import OptionParser
+
+import os
+import re
+import sys
+import logging
+
+__author__ = 'James Aley'
+__email__ = 'jamesa@symbian.org'
+__version__ = '1.0'
+
+# Logging config
+_LOG_FORMAT = '%(levelname)s: %(message)s'
+logging.basicConfig(format=_LOG_FORMAT, level=logging.WARNING, stream=sys.stdout)
+
+# Regexes for bld.inf parsing
+_RE_EXPORT_SECTION = '\\s*PRJ_EXPORTS\\s*'
+_RE_OTHER_SECTION = '\\s*PRJ_[a-z]+\\s*'
+_RE_IBY_OBY = '\\s*([^\\s]+\\.[oi]by)\\s+.*'
+_p_export_section = re.compile(_RE_EXPORT_SECTION, re.I)
+_p_other_section = re.compile(_RE_OTHER_SECTION, re.I)
+_p_iby_oby = re.compile(_RE_IBY_OBY, re.I)
+
+# OBY output templates
+_OBY_HEADER = """// OBY file generated by genereate_oby.py.
+// The following includes are derived from the dependency report: %s
+
+"""
+
+_OBY_INCLUDE = """
+// Required for: %s
+%s
+"""
+
+_OBY_UNRESOLVED = """
+
+// The following appear to be exported by this component, 
+// but were not found under the include directory:
+%s
+"""
+
+_OBY_NO_EXPORTS = """
+
+// The following components are required in your dependency graph, but
+// they appear not to export an IBY/OBY file. Your ROM will likely not
+// build until you locate the correct include files for these.
+%s
+"""
+
+_INCLUDE_TEMPLATE = '#include <%s>'
+
+def bld_inf_list(report_path):
+    """Returna list of bld.inf files from the report
+    """
+    bld_list = []
+    report_file = None
+    try:
+        report_file = open(report_path)
+    except IOError, e:
+        logging.critical('Could not open report: %s' % (repr(e), ))
+        exit(1)
+    return filter(lambda x: x and not x.isspace(), [line.strip() for line in without_comments(report_file)])
+
+def get_paths(bld_inf_file):
+    """Returns a list of referenced OBY or IBY files from a bld.inf file.
+    bld_inf_file is an open file handle, which will not be closed by this
+    function.
+    """
+    oby_iby = []
+    export_section = False
+    for line in without_comments(bld_inf_file):
+        if export_section:
+            match_iby_oby = _p_iby_oby.search(line)
+            if match_iby_oby:
+                file_name = match_iby_oby.groups()[0].strip()
+                oby_iby.append(file_name)
+            else:
+                match_other_section = _p_other_section.search(line)
+                if match_other_section:
+                    export_section = False
+        else:
+            match_export_section = _p_export_section.search(line)
+            if match_export_section:
+                export_section = True
+    obys = filter(lambda x: x.lower().endswith('.oby'), oby_iby)
+    if len(obys) > 0:
+        return obys
+    return oby_iby
+
+def rom_file_list(bld_inf_paths):
+    """Iterate through a list of bld.inf file paths and extra the references
+    to OBY or IBY files where appropriate (OBY takes precedence). Return a
+    dictionary of relevant files in the format:
+        { 'component_bld_inf' : [ iby_file_list] }
+    """
+    obys_ibys = {}
+    for path in bld_inf_paths:
+        bld_inf_file = None
+        try:
+            bld_inf_file = open(path)
+        except IOError, e:
+            logging.error('Unable to open bld.inf file: %s' % (repr(e), ))
+            continue
+        rom_file_paths = get_paths(bld_inf_file)
+        obys_ibys[path] = rom_file_paths
+        bld_inf_file.close()
+    return obys_ibys
+
+def iby_map(iby_dict, dir_name, file_names):
+     """Searches for the specified IBY/OBY file under the include_root path.
+     Returns the absolute path to the IBY/OBY if it was found, otherwise a blank string.
+     """
+     for component in iby_dict.keys():
+         # Map the file names for each component IBY file to a matching
+         # file name under the export directory, if it exists, otherwise
+         # keep the existing name for now - it might be matched later.
+         file_names = map(lambda x: x.lower(), file_names)
+         component_ibys = map(lambda x: os.path.basename(x).lower() in file_names \
+                                  and os.path.join(dir_name, os.path.basename(x)) \
+                                  or x, \
+                                  iby_dict[component])
+         iby_dict[component] = component_ibys
+
+def write_oby(out_path, iby_map, input_path, include_root):
+    """Write an OBY file to include the required IBY and OBY files for this
+    ROM specification, given by iby_map.
+    """
+    out_file = None
+    try:
+        out_file = open(out_path, 'w')
+    except IOError, e:
+        logging.critical('Unable to write OBY file: %s' % repr(e))
+        exit(1)
+
+    # Write the header with the input file name included
+    out_file.write(_OBY_HEADER % (input_path, ))
+
+    exports = filter(lambda x: len(iby_map[x]) > 0, iby_map.keys())
+    no_exports = filter(lambda x: len(iby_map[x]) == 0, iby_map.keys())
+
+    # Write the includes and missing exports
+    for component in exports:
+        iby_list = iby_map[component]
+        exported = filter(lambda x: x.startswith(include_root), iby_list)
+        # Need relative paths for include, but os.path.relpath is added
+        # in Python 2.6, which isn't supported by other Symbian tools
+        # at present :-(
+        exported = map(lambda x: x[len(include_root) + 1:], exported)
+        exported.sort()
+        
+        missing = filter(lambda x: not x.startswith(include_root), iby_list)
+        missing = map(lambda x: os.path.basename(x), missing)
+        missing.sort()
+        
+        # Write the IBY file includes for this component
+        out_file.write(_OBY_INCLUDE % (component, '\n'.join([_INCLUDE_TEMPLATE % (iby, ) for iby in exported]), ))
+        
+        # Write the missing IBY reports
+        if len(missing) > 0:
+            out_file.write(_OBY_UNRESOLVED % ('\n'.join(['// %s' % (missed, ) for missed in missing]), ))
+
+    # Write report for the IBY that appear not to export any ROM include files
+    out_file.write(_OBY_NO_EXPORTS % ('\n'.join(['// %s' % (path,) for path in no_exports]), ))
+    out_file.close()
+
+# Main
+if __name__ == '__main__':
+    # Options config
+    parser = OptionParser()
+    parser.set_description(__doc__)
+    parser.add_option('-r', '--report', dest='report_path', 
+                      help='File name for the report generated by get_deps.py', 
+                      metavar='INPUT_FILE', default='dependencies.txt')
+    parser.add_option('-o', '--output', dest='output_file',
+                      help='OBY ouput file to write to.',
+                      metavar='OUT_FILE', default='generated.oby')
+    parser.add_option('-i', '--include_root', dest='include_root',
+                      help='Environment ROM inlcude root.',
+                      metavar='INCLUDE_ROOT', 
+                      default=os.path.sep.join(['epoc32', 'rom']))
+    (options, args) = parser.parse_args()
+
+    # Read the report and get a list of bld.inf files, then convert to
+    # a dictionary of bld_inf -> [IBY file list] mappings.
+    bld_infs = bld_inf_list(options.report_path)
+    bld_iby_map = rom_file_list(bld_infs)
+
+    # Walk the include tree to find the exported IBYs.
+    os.path.walk(options.include_root, iby_map, bld_iby_map)
+
+    # Write the OBY file
+    write_oby(options.output_file, bld_iby_map, options.report_path, options.include_root)
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jamesa/get_deps.py	Wed Nov 04 17:40:17 2009 +0000
@@ -0,0 +1,174 @@
+# Copyright (c) 2009 Symbian Foundation Ltd
+# This component and the accompanying materials are made available
+# under the terms of the License "Eclipse Public License v1.0"
+# which accompanies this distribution, and is available
+# at the URL "http://www.eclipse.org/legal/epl-v10.html".
+#
+# Initial Contributors:
+# Symbian Foundation Ltd - initial contribution.
+# 
+# Contributors:
+#
+# Description:
+# Walk all nodes in the dependency graph to create a dependency report.
+
+"""Walk a dependency graph to find dependencies for a particular set of
+components. This script uses the output of build_graph.py to trace
+dependencies.
+
+The directory_list refer to diretories in the source tree for which
+you wish to trace dependencies. The script will find all components
+in the graph file under these directories and trace dependencies from
+that point.
+"""
+
+from optparse import OptionParser
+from _common import Node
+
+import sys
+import pickle
+import logging
+
+__author__ = 'James Aley'
+__email__ = 'jamesa@symbian.org'
+__version__ = '1.0'
+
+_LOG_FORMAT = '%(levelname)s: %(message)s'
+logging.basicConfig(format=_LOG_FORMAT, level=logging.WARNING, stream=sys.stdout)
+
+# Internalized graph object
+graph = {}
+
+# Report formatting
+_REPORT_HEADER = """// Generated by get_deps.py
+//
+// Dependency information for:
+//
+%s
+
+"""
+
+_DEPENDENCY_FORMAT = """
+// Required components:
+
+%s
+
+"""
+
+_MISSING_FORMAT = """
+// The following binary objects were referenced from the build files for
+// components required by your specified root components. However, there
+// were no build files for these objects found in the source tree parsing,
+// so dependencies for them may be missing in the above listing.
+
+%s
+
+"""
+
+def load_graph(path):
+    """Return the internalized graph dictionary object.
+    """
+    graph_file = None
+    graph_loaded = {}
+
+    try:
+        graph_file = open(path, 'rb')
+    except IOError, e:
+        logging.critical('Unable to open graph from file: %s: %s' % (path, repr(e)))
+        exit(1)
+    try:
+        graph_loaded = pickle.load(graph_file)
+    except Exception, e:
+        logging.critical('File %s does not contain a valid graph: %s' % (path, repr(e)))
+    return graph_loaded
+
+def find_roots(root_dirs):
+    """Return a list of root nodes from the graph for tracing, based on
+    the specified component directories in the root_dirs list.
+    """
+    roots = []
+    for root in root_dirs:
+        for node in graph.keys():
+            if node.startswith(root.lower()):
+                if node not in roots:
+                    roots.append(node)
+    return roots
+
+def trace(root, visited = set()):
+    """Return a list of components required to support root.
+    """
+    node = graph[root]
+    visited |= set([node.node_path]) | set(node.dependencies)
+    for dep in node.dependencies:
+        if dep not in visited:
+            return trace(dep, visited)
+    return visited
+
+def unresolved(deps):
+    """Return a set of components with unknown dependencies from a 
+    provided list of node names.
+    """
+    unresolved = set()
+    for dep in deps:
+        node = graph[dep]
+        unresolved |= set(node.unresolved)
+    return unresolved
+
+def report(out_path, roots, dependencies, missing):
+    """Output the dependency information to file.
+    """
+    # open report file
+    out_file = None
+    try:
+        out_file = open(out_path, 'w')
+    except IOError, e:
+        logging.critical('Unable to write report: %s' % (repr(e)))
+        exit(1)
+
+    # easier to read report with these sorted
+    roots.sort()
+    dependencies.sort()
+    missing.sort()
+
+    # format report
+    formatted_header = _REPORT_HEADER % ('\n'.join(['// %s' % (line, ) for line in roots]), )
+    formatted_body = _DEPENDENCY_FORMAT % ('\n'.join(dependencies))
+    formatted_missing = _MISSING_FORMAT % ('\n'.join(['// %s' % (line, ) for line in missing]), )
+
+    # write report
+    out_file.write(formatted_header)
+    out_file.write(formatted_body)
+    out_file.write(formatted_missing)
+
+    out_file.close()
+
+if __name__ == '__main__':
+    # Options config
+    parser = OptionParser()
+    parser.set_description(__doc__)
+    parser.set_usage('python get_deps.py [options] directory_list')
+    parser.add_option('-g', '--graph', dest='graph_file', 
+                      help='File name to write the graph to.', 
+                      metavar='GRAPH_FILE', default='dependencies.graph')
+    parser.add_option('-o', '--output', dest='output_file',
+                      help='File to write the dependency report to.',
+                      metavar='OUT_FILE', default='dependencies.txt')
+    (options, args) = parser.parse_args()
+
+    # Intenalize the graph file
+    print 'Loading graph from %s' % (options.graph_file, )
+    graph = load_graph(options.graph_file)
+
+    # Extract relevant slices and merge dependencies
+    roots = find_roots(args)
+    print 'Tracing dependencies for %d components under %s' % (len(roots), ', '.join(args))
+    deps = set()
+    for root in roots:
+        deps |= trace(root)
+    print 'Dependency graph slice yields %d of %d components.' % (len(deps), len(graph))
+    unresolved_deps = unresolved(deps)
+    print 'Component dependencies for %d binaries are unresolved' % (len(unresolved_deps, ))
+
+    # Write the report to the output file
+    report(options.output_file, roots, list(deps), list(unresolved_deps))
+    print 'Report written to: %s' % (options.output_file, )