SERVER-24838: add scons tool for capturing dependency graph

7 files changed, 1615 insertions, 0 deletions

diff --git a/site_scons/site_tools/dagger/__init__.py b/site_scons/site_tools/dagger/__init__.py
new file mode 100644
index 00000000000..becf164c151
--- /dev/null
+++ b/site_scons/site_tools/dagger/__init__.py
@@ -0,0 +1,42 @@
+"""The initialization for the dagger tool. This file provides the initialization for the tool
+and attaches our custom builders and emitters to the build process"""
+
+import dagger
+import SCons
+
+
+def generate(env, **kwargs):
+    """The entry point for our tool. However, the builder for
+    the JSON file is not actually run until the Dagger method is called
+    in the environment. When we generate the tool we attach our emitters
+    to the native builders for object/libraries.
+    """
+    static_obj, shared_obj = SCons.Tool.createObjBuilders(env)
+    env.Replace(LIBEMITTER=SCons.Builder.ListEmitter([env['LIBEMITTER'],
+                                                      dagger.emit_lib_db_entry]))
+    suffixes = ['.c', '.cc', '.cxx', '.cpp']
+    obj_builders = [static_obj, shared_obj]
+    default_emitters = [SCons.Defaults.StaticObjectEmitter,
+                        SCons.Defaults.SharedObjectEmitter]
+
+    for suffix in suffixes:
+        for i in range(len(obj_builders)):
+            obj_builders[i].add_emitter(suffix, SCons.Builder.ListEmitter([
+                dagger.emit_obj_db_entry, default_emitters[i]
+            ]))
+
+    env['BUILDERS']['__OBJ_DATABASE'] = SCons.Builder.Builder(
+        action=SCons.Action.Action(dagger.write_obj_db, None))
+
+    def Dagger(env, target="library_dependency_graph.json"):
+        result = env.__OBJ_DATABASE(target=target, source=[])
+        env.AlwaysBuild(result)
+        env.NoCache(result)
+
+        return result
+
+    env.AddMethod(Dagger, 'Dagger')
+
+
+def exists(env):
+    return True
diff --git a/site_scons/site_tools/dagger/dagger.py b/site_scons/site_tools/dagger/dagger.py
new file mode 100644
index 00000000000..4a1fee2f33b
--- /dev/null
+++ b/site_scons/site_tools/dagger/dagger.py
@@ -0,0 +1,256 @@
+"""Dagger allows SCons to track it's internal build dependency data for the
+MongoDB project. The tool stores this information in a Graph object, which
+is then exported to a pickle/JSON file once the build is complete.
+
+This tool binds a method to the SCons Env, which can be executed by a call
+to env.BuildDeps(filename)
+
+To use this tool, add the following three lines to your SConstruct
+file, after all environment configuration has been completed.
+
+env.Tool("dagger")
+dependencyDb = env.Alias("dagger", env.BuildDeps(desiredpathtostoregraph))
+env.Requires(dependencyDb, desired alias)
+
+The desired path determines where the graph object is stored (which
+should be in the same directory as the accompanying command line tool)
+The desired alias determines what you are tracking build dependencies for is
+built before you try and extract the build dependency data.
+
+To generate the graph, run the command "SCons dagger"
+"""
+
+# Copyright 2016 MongoDB Inc.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+#     Unless required by applicable law or agreed to in writing, software
+#     distributed under the License is distributed on an "AS IS" BASIS,
+#     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#     See the License for the specific language governing permissions and
+#     limitations under the License.
+
+import logging
+import subprocess
+import sys
+
+import SCons
+
+import graph
+import graph_consts
+
+LIB_DB = []
+OBJ_DB = []
+
+
+class DependencyCycleError(SCons.Errors.UserError):
+    """Exception representing a cycle discovered in library dependencies."""
+
+    def __init__(self, first_node):
+        super(DependencyCycleError, self).__init__()
+        self.cycle_nodes = [first_node]
+
+    def __str__(self):
+        return "Library dependency cycle detected: " + " => ".join(
+            str(n) for n in self.cycle_nodes)
+
+
+def list_process(items):
+    """From WIL, converts lists generated from an NM command with unicode strings to lists
+    with ascii strings
+    """
+
+    r = []
+    for l in items:
+        if isinstance(l, list):
+            for i in l:
+                if i.startswith('.L'):
+                    continue
+                else:
+                    r.append(str(i))
+        else:
+            if l.startswith('.L'):
+                continue
+            else:
+                r.append(str(l))
+    return r
+
+
+# TODO: Use the python library to read elf files,
+# so we know the file exists at this point
+def get_symbol_worker(object_file, task):
+    """From WIL, launches a worker subprocess which collects either symbols defined
+    or symbols required by an object file"""
+
+    platform = 'linux' if sys.platform.startswith('linux') else 'darwin'
+
+    if platform == 'linux':
+        if task == 'used':
+            cmd = r'nm "' + object_file + r'" | grep -e "U " | c++filt'
+        elif task == 'defined':
+            cmd = r'nm "' + object_file + r'" | grep -v -e "U " | c++filt'
+    elif platform == 'darwin':
+        if task == 'used':
+            cmd = "nm -u " + object_file + " | c++filt"
+        elif task == 'defined':
+            cmd = "nm -jU " + object_file + " | c++filt"
+
+    p = subprocess.Popen(cmd, shell=True, stdout=subprocess.PIPE)
+    uses = p.communicate()[0].decode()
+
+    if platform == 'linux':
+        return list_process([use[19:] for use in uses.split('\n')
+                             if use != ''])
+    elif platform == 'darwin':
+        return list_process([use.strip() for use in uses.split('\n')
+                             if use != ''])
+
+
+def emit_obj_db_entry(target, source, env):
+    """Emitter for object files. We add each object file
+    built into a global variable for later use"""
+
+    for t in target:
+        if str(t) is None:
+            continue
+        OBJ_DB.append(t)
+    return target, source
+
+
+def emit_lib_db_entry(target, source, env):
+    """Emitter for libraries. We add each library
+    into our global variable"""
+    for t in target:
+        if str(t) is None:
+            continue
+        LIB_DB.append(t)
+    return target, source
+
+
+def __compute_libdeps(node):
+    """
+    Computes the direct library dependencies for a given SCons library node.
+    the attribute that it uses is populated by the Libdeps.py script
+    """
+
+    if getattr(node.attributes, 'libdeps_exploring', False):
+        raise DependencyCycleError(node)
+
+    env = node.get_env()
+    deps = set()
+    node.attributes.libdeps_exploring = True
+    try:
+        try:
+            for child in env.Flatten(getattr(node.attributes, 'libdeps_direct',
+                                             [])):
+                if not child:
+                    continue
+                deps.add(child)
+
+        except DependencyCycleError as e:
+            if len(e.cycle_nodes) == 1 or e.cycle_nodes[0] != e.cycle_nodes[
+                    -1]:
+                e.cycle_nodes.insert(0, node)
+
+            logging.error("Found a dependency cycle" + str(e.cycle_nodes))
+    finally:
+        node.attributes.libdeps_exploring = False
+
+    return deps
+
+
+def __generate_lib_rels(lib, g):
+    """Generate all library to library dependencies, and determine
+    for each library the object files it consists of."""
+
+    lib_node = g.find_node(lib.get_path(), graph_consts.NODE_LIB)
+
+    for child in __compute_libdeps(lib):
+        if child is None:
+            continue
+
+        lib_dep = g.find_node(str(child), graph_consts.NODE_LIB)
+        g.add_edge(graph_consts.LIB_LIB, lib_node.id, lib_dep.id)
+
+    object_files = lib.all_children()
+    for obj in object_files:
+        object_path = str(obj)
+        obj_node = g.find_node(object_path, graph_consts.NODE_FILE)
+        obj_node.library = lib_node.id
+        lib_node.add_defined_file(obj_node.id)
+
+
+def __generate_sym_rels(obj, g):
+    """Generate all to symbol dependency and definition location information
+    """
+
+    object_path = str(obj)
+    file_node = g.find_node(object_path, graph_consts.NODE_FILE)
+
+    symbols_used = get_symbol_worker(object_path, task="used")
+    symbols_defined = get_symbol_worker(object_path, task="defined")
+
+    for symbol in symbols_defined:
+        symbol_node = g.find_node(symbol, graph_consts.NODE_SYM)
+        symbol_node.add_library(file_node.library)
+        symbol_node.add_file(file_node.id)
+        file_node.add_defined_symbol(symbol_node.id)
+
+        lib_node = g.get_node(file_node.library)
+        if lib_node is not None:
+            lib_node.add_defined_symbol(symbol_node.id)
+
+    for symbol in symbols_used:
+        symbol_node = g.find_node(symbol, graph_consts.NODE_SYM)
+        g.add_edge(graph_consts.FIL_SYM, file_node.id, symbol_node.id)
+
+
+def __generate_file_rels(obj, g):
+    """Generate all file to file and by extension, file to library and library
+    to file relationships
+    """
+
+    file_node = g.get_node(str(obj))
+
+    if file_node is None:
+        return
+
+    if file_node.id not in g.get_edge_type(graph_consts.FIL_SYM):
+        return
+
+    for symbol in g.get_edge_type(graph_consts.FIL_SYM)[file_node.id]:
+        symbol = g.get_node(symbol)
+        objs = symbol.files
+        if objs is None:
+            continue
+
+        for obj in objs:
+            g.add_edge(graph_consts.FIL_FIL, file_node.id, obj)
+
+
+def write_obj_db(target, source, env):
+    """The bulk of the tool. This method takes all the objects and libraries
+    which we have stored in the global LIB_DB and OBJ_DB variables and
+    creates the build dependency graph. The graph is then exported to a JSON
+    file for use with the separate query tool/visualizer
+    """
+    g = graph.Graph()
+
+    for lib in LIB_DB:
+        __generate_lib_rels(lib, g)
+
+    for obj in OBJ_DB:
+        __generate_sym_rels(obj, g)
+
+    for obj in OBJ_DB:
+        __generate_file_rels(obj, g)
+
+    # target is given as a list of target SCons nodes - this builder is only responsible for
+    # building the json target, so this list is of length 1. export_to_json
+    # expects a filename, whereas target is a list of SCons nodes so we cast target[0] to str
+
+    g.export_to_json(str(target[0]))
diff --git a/site_scons/site_tools/dagger/export_test.json b/site_scons/site_tools/dagger/export_test.json
new file mode 100644
index 00000000000..78cfbb0ce7b
--- /dev/null
+++ b/site_scons/site_tools/dagger/export_test.json
@@ -0,0 +1,272 @@
+{
+    "nodes": [
+        {
+            "node": {
+                "_dependent_libs": [
+                    "lib2"
+                ], 
+                "_lib": "lib3", 
+                "_name": "file3", 
+                "_dependent_files": [
+                    "file2"
+                ], 
+                "_defined_symbols": [], 
+                "_id": "file3", 
+                "type": 3
+            }, 
+            "index": 0, 
+            "id": "file3"
+        }, 
+        {
+            "node": {
+                "_dependent_libs": [], 
+                "_lib": "lib2", 
+                "_name": "file2", 
+                "_dependent_files": [], 
+                "_defined_symbols": [], 
+                "_id": "file2", 
+                "type": 3
+            }, 
+            "index": 1, 
+            "id": "file2"
+        }, 
+        {
+            "node": {
+                "_dependent_libs": [], 
+                "_lib": "lib1", 
+                "_name": "file1", 
+                "_dependent_files": [], 
+                "_defined_symbols": [], 
+                "_id": "file1", 
+                "type": 3
+            }, 
+            "index": 2, 
+            "id": "file1"
+        }, 
+        {
+            "node": {
+                "_dependent_libs": [
+                    "lib1"
+                ], 
+                "_lib": null, 
+                "_name": "file_sym", 
+                "_dependent_files": [
+                    "file1"
+                ], 
+                "_defined_symbols": [
+                    "sym1"
+                ], 
+                "_id": "file_sym", 
+                "type": 3
+            }, 
+            "index": 3, 
+            "id": "file_sym"
+        }, 
+        {
+            "node": {
+                "_dependent_libs": [
+                    "lib1"
+                ], 
+                "_files": [
+                    "file_sym"
+                ], 
+                "_name": "sym1", 
+                "_dependent_files": [
+                    "file1"
+                ], 
+                "_libs": [
+                    "lib_sym"
+                ], 
+                "_id": "sym1", 
+                "type": 2
+            }, 
+            "index": 4, 
+            "id": "sym1"
+        }, 
+        {
+            "node": {
+                "_dependent_files": [
+                    "file2"
+                ], 
+                "_defined_files": [
+                    "file3"
+                ], 
+                "_name": "lib3", 
+                "_dependent_libs": [
+                    "lib2"
+                ], 
+                "_defined_symbols": [], 
+                "_id": "lib3", 
+                "type": 1
+            }, 
+            "index": 5, 
+            "id": "lib3"
+        }, 
+        {
+            "node": {
+                "_dependent_files": [], 
+                "_defined_files": [
+                    "file2"
+                ], 
+                "_name": "lib2", 
+                "_dependent_libs": [], 
+                "_defined_symbols": [], 
+                "_id": "lib2", 
+                "type": 1
+            }, 
+            "index": 6, 
+            "id": "lib2"
+        }, 
+        {
+            "node": {
+                "_dependent_files": [], 
+                "_defined_files": [
+                    "file1"
+                ], 
+                "_name": "lib1", 
+                "_dependent_libs": [], 
+                "_defined_symbols": [], 
+                "_id": "lib1", 
+                "type": 1
+            }, 
+            "index": 7, 
+            "id": "lib1"
+        }, 
+        {
+            "node": {
+                "_dependent_files": [], 
+                "_defined_files": [], 
+                "_name": "lib_sym", 
+                "_dependent_libs": [
+                    "lib1"
+                ], 
+                "_defined_symbols": [
+                    "sym1"
+                ], 
+                "_id": "lib_sym", 
+                "type": 1
+            }, 
+            "index": 8, 
+            "id": "lib_sym"
+        }
+    ], 
+    "edges": [
+        {
+            "type": 1, 
+            "to_node": [
+                {
+                    "index": 5, 
+                    "id": "lib3"
+                }
+            ], 
+            "from_node": {
+                "index": 6, 
+                "id": "lib2"
+            }
+        }, 
+        {
+            "type": 1, 
+            "to_node": [
+                {
+                    "index": 8, 
+                    "id": "lib_sym"
+                }
+            ], 
+            "from_node": {
+                "index": 7, 
+                "id": "lib1"
+            }
+        }, 
+        {
+            "type": 2, 
+            "to_node": [
+                {
+                    "index": 0, 
+                    "id": "file3"
+                }
+            ], 
+            "from_node": {
+                "index": 6, 
+                "id": "lib2"
+            }
+        }, 
+        {
+            "type": 2, 
+            "to_node": [
+                {
+                    "index": 3, 
+                    "id": "file_sym"
+                }
+            ], 
+            "from_node": {
+                "index": 7, 
+                "id": "lib1"
+            }
+        }, 
+        {
+            "type": 3, 
+            "to_node": [
+                {
+                    "index": 5, 
+                    "id": "lib3"
+                }
+            ], 
+            "from_node": {
+                "index": 1, 
+                "id": "file2"
+            }
+        }, 
+        {
+            "type": 4, 
+            "to_node": [
+                {
+                    "index": 0, 
+                    "id": "file3"
+                }
+            ], 
+            "from_node": {
+                "index": 1, 
+                "id": "file2"
+            }
+        }, 
+        {
+            "type": 4, 
+            "to_node": [
+                {
+                    "index": 3, 
+                    "id": "file_sym"
+                }
+            ], 
+            "from_node": {
+                "index": 2, 
+                "id": "file1"
+            }
+        }, 
+        {
+            "type": 5, 
+            "to_node": [
+                {
+                    "index": 4, 
+                    "id": "sym1"
+                }
+            ], 
+            "from_node": {
+                "index": 2, 
+                "id": "file1"
+            }
+        }, 
+        {
+            "type": 6, 
+            "to_node": [
+                {
+                    "index": 4, 
+                    "id": "sym1"
+                }
+            ], 
+            "from_node": {
+                "index": 7, 
+                "id": "lib1"
+            }
+        }
+    ]
+}
\ No newline at end of file
diff --git a/site_scons/site_tools/dagger/graph.py b/site_scons/site_tools/dagger/graph.py
new file mode 100644
index 00000000000..ca3815fc493
--- /dev/null
+++ b/site_scons/site_tools/dagger/graph.py
@@ -0,0 +1,546 @@
+import sys
+import logging
+import abc
+import json
+import copy
+
+import graph_consts
+
+if sys.version_info >= (3, 0):
+    basestring = str
+
+
+class Graph(object):
+    """Graph class for storing the build dependency graph. The graph stores the
+    directed edges as a nested dict of { RelationshipType: {From_Node: Set of
+    connected nodes}} and nodes as a dict of {nodeid : nodeobject}. Can be
+    imported from a pickle or JSON file.
+    """
+
+    def __init__(self, input=None):
+        """
+        A graph can be initialized with a .json file, graph object, or with no args
+        """
+        if isinstance(input, basestring):
+            if input.endswith('.json'):
+                with open(input, 'r') as f:
+                    data = json.load(f, encoding="ascii")
+                nodes = {}
+                should_fail = False
+
+                for node in data["nodes"]:
+                    id = str(node["id"])
+                    try:
+                        nodes[id] = node_factory(id, int(node["node"]["type"]),
+                                                 dict_source=node["node"])
+                    except Exception as e:
+                        logging.warning("Malformed Data: " + id)
+                        should_fail = True
+
+                if should_fail is True:
+                    raise ValueError("json nodes are malformed")
+
+                edges = {}
+
+                for edge in data["edges"]:
+                    if edge["type"] not in edges:
+                        edges[edge["type"]] = {}
+
+                    to_edges = set([e["id"] for e in edge["to_node"]])
+                    edges[edge["type"]][edge["from_node"]["id"]] = to_edges
+
+                self._nodes = nodes
+                self._edges = edges
+        elif isinstance(input, Graph):
+            self._nodes = input.nodes
+            self._edges = input.edges
+        else:
+            self._nodes = {}
+            self._edges = {}
+            for rel in graph_consts.RELATIONSHIP_TYPES:
+                self._edges[rel] = {}
+
+    @property
+    def nodes(self):
+        """We want to ensure that we are not able to mutate
+        the nodes or edges properties outside of the specified adder methods
+        """
+        return copy.deepcopy(self._nodes)
+
+    @property
+    def edges(self):
+        return copy.deepcopy(self._edges)
+
+    def get_node(self, id):
+        return self._nodes.get(id)
+
+    def find_node(self, id, type):
+        """returns the node if it exists, otherwise, generates
+        it"""
+        if self.get_node(id) is not None:
+            return self.get_node(id)
+        else:
+            node = node_factory(id, type)
+            self.add_node(node)
+            return node
+
+    def get_edge_type(self, edge_type):
+        return self._edges[edge_type]
+
+    def add_node(self, node):
+        if not isinstance(node, NodeInterface):
+            raise TypeError
+
+        if node.id in self._nodes:
+            raise ValueError
+
+        self._nodes[node.id] = node
+
+    def add_edge(self, relationship, from_node, to_node):
+        if relationship not in graph_consts.RELATIONSHIP_TYPES:
+            raise TypeError
+
+        from_node_obj = self.get_node(from_node)
+        to_node_obj = self.get_node(to_node)
+
+        if from_node not in self._edges[relationship]:
+            self._edges[relationship][from_node] = set()
+
+        if any(item is None for item in (from_node, to_node, from_node_obj, to_node_obj)):
+            raise ValueError
+
+        self._edges[relationship][from_node].add(to_node)
+
+        to_node_obj.add_incoming_edges(from_node_obj, self)
+
+    # JSON does not support python sets, so we need to convert each
+    # set of edges to lists
+    def export_to_json(self, filename="graph.json"):
+        node_index = {}
+
+        data = {"edges": [], "nodes": []}
+
+        for idx, id in enumerate(self._nodes.keys()):
+            node = self.get_node(id)
+            node_index[id] = idx
+            node_dict = {}
+            node_dict["index"] = idx
+            node_dict["id"] = id
+            node_dict["node"] = {}
+
+            for property, value in vars(node).iteritems():
+                if isinstance(value, set):
+                    node_dict["node"][property] = list(value)
+                else:
+                    node_dict["node"][property] = value
+
+            data["nodes"].append(node_dict)
+
+        for edge_type in graph_consts.RELATIONSHIP_TYPES:
+            edges_dict = self._edges[edge_type]
+            for node in edges_dict.keys():
+                to_nodes = list(self._edges[edge_type][node])
+                to_nodes_dicts = [{"index": node_index[to_node], "id": to_node}
+                                  for to_node in to_nodes]
+
+                data["edges"].append({"type": edge_type,
+                                      "from_node": {"id": node,
+                                                    "index": node_index[node]},
+                                      "to_node": to_nodes_dicts})
+
+        with open(filename, 'w') as outfile:
+            json.dump(data, outfile, indent=4, encoding="ascii")
+
+    def __str__(self):
+        return ("<Number of Nodes : {0}, Number of Edges : {1}, "
+                "Hash: {2}>").format(len(self._nodes.keys()),
+                sum(len(x) for x in self._edges.values()), hash(self))
+
+
+class NodeInterface(object):
+    """Abstract base class for all Node Objects - All nodes must have an id and name
+    """
+    __metaclass__ = abc.ABCMeta
+
+    @abc.abstractproperty
+    def id(self):
+        raise NotImplementedError()
+
+    @abc.abstractproperty
+    def name(self):
+        raise NotImplementedError()
+
+
+class NodeLib(NodeInterface):
+    """NodeLib class which represents a library within the graph
+    """
+    def __init__(self, id, name, input=None):
+        if isinstance(input, dict):
+            should_fail = False
+            for k, v in input.iteritems():
+                try:
+                    if isinstance(v, list):
+                        setattr(self, k, set(v))
+                    else:
+                        setattr(self, k, v)
+                except AttributeError as e:
+                    logging.error("found something bad, {0}, {1}", e, type(e))
+                    should_fail = True
+            if should_fail:
+                raise Exception("Problem setting attribute for NodeLib")
+        else:
+            self._id = id
+            self.type = graph_consts.NODE_LIB
+            self._name = name
+            self._defined_symbols = set()
+            self._defined_files = set()
+            self._dependent_files = set()
+            self._dependent_libs = set()
+
+    @property
+    def id(self):
+        return self._id
+
+    @property
+    def name(self):
+        return self._name
+
+    @property
+    def defined_symbols(self):
+        return self._defined_symbols
+
+    @defined_symbols.setter
+    def defined_symbols(self, value):
+        if isinstance(value, set):
+            self._defined_symbols = value
+        else:
+            raise TypeError("NodeLib.defined_symbols must be a set")
+
+    @property
+    def defined_files(self):
+        return self._defined_files
+
+    @defined_files.setter
+    def defined_files(self, value):
+        if isinstance(value, set):
+            self._defined_files = value
+        else:
+            raise TypeError("NodeLib.defined_files must be a set")
+
+    @property
+    def dependent_files(self):
+        return self._dependent_files
+
+    @dependent_files.setter
+    def dependent_files(self, value):
+        if isinstance(value, set):
+            self._dependent_files = value
+        else:
+            raise TypeError("NodeLib.dependent_files must be a set")
+
+    @property
+    def dependent_libs(self):
+        return self._dependent_libs
+
+    @dependent_libs.setter
+    def dependent_libs(self, value):
+        if isinstance(value, set):
+            self._defined_libs = value
+        else:
+            raise TypeError("NodeLib.defined_libs must be a set")
+
+    def add_defined_symbol(self, symbol):
+        if symbol is not None:
+            self._defined_symbols.add(symbol)
+
+    def add_defined_file(self, file):
+        if file is not None:
+            self._defined_files.add(file)
+
+    def add_dependent_file(self, file):
+        if file is not None:
+            self._dependent_files.add(file)
+
+    def add_dependent_lib(self, lib):
+        if lib is not None:
+            self._dependent_libs.add(lib)
+
+    def add_incoming_edges(self, from_node, g):
+        """Whenever you generate a LIB_LIB edge, you must add
+        the source lib to the dependent_lib field in the target lib
+        """
+        if from_node.type == graph_consts.NODE_LIB:
+            self.add_dependent_lib(from_node.id)
+
+    def __eq__(self, other):
+        if isinstance(other, NodeLib):
+            return (self._id == other._id and self._defined_symbols == other._defined_symbols and
+                    self._defined_files == other._defined_files and
+                    self._dependent_libs == other._dependent_libs and
+                    self._dependent_files == other._dependent_files)
+
+        else:
+            return False
+
+    def __ne__(self, other):
+        return not self.__eq__(other)
+
+    def __str__(self):
+        return self.id
+
+
+class NodeSymbol(NodeInterface):
+    """NodeSymbol class which represents a symbol within the dependency graph
+    """
+
+    def __init__(self, id, name, input=None):
+        if isinstance(input, dict):
+            should_fail = False
+
+            for k, v in input.iteritems():
+                try:
+                    if isinstance(v, list):
+                        setattr(self, k, set(v))
+                    else:
+                        setattr(self, k, v)
+                except AttributeError as e:
+                    logging.error("found something bad, {0}, {1}", e, type(e))
+                    should_fail = True
+
+            if should_fail:
+                raise Exception("Problem setting attribute for NodeLib")
+        else:
+            self._id = id
+            self.type = graph_consts.NODE_SYM
+            self._name = name
+            self._dependent_libs = set()
+            self._dependent_files = set()
+            self._libs = set()
+            self._files = set()
+
+    @property
+    def id(self):
+        return self._id
+
+    @property
+    def name(self):
+        return self._name
+
+    @property
+    def libs(self):
+        return self._libs
+
+    @libs.setter
+    def libs(self, value):
+        if isinstance(value, set):
+            self._libs = value
+        else:
+            raise TypeError("NodeSymbol.libs must be a set")
+
+    @property
+    def files(self):
+        return self._files
+
+    @files.setter
+    def files(self, value):
+        if isinstance(value, set):
+            self._files = value
+        else:
+            raise TypeError("NodeSymbol.files must be a set")
+
+    @property
+    def dependent_libs(self):
+        return self._dependent_libs
+
+    @dependent_libs.setter
+    def dependent_libs(self, value):
+        if isinstance(value, set):
+            self._dependent_libs = value
+        else:
+            raise TypeError("NodeSymbol.dependent_libs must be a set")
+
+    @property
+    def dependent_files(self):
+        return self._dependent_files
+
+    @dependent_files.setter
+    def dependent_files(self, value):
+        if isinstance(value, set):
+            self._dependent_files = value
+        else:
+            raise TypeError("NodeSymbol.dependent_files must be a set")
+
+    def add_library(self, library):
+        if library is not None:
+            self._libs.add(library)
+
+    def add_file(self, file):
+        if file is not None:
+            self._files.add(file)
+
+    def add_dependent_file(self, file):
+        if file is not None:
+            self._dependent_files.add(file)
+
+    def add_dependent_lib(self, library):
+        if library is not None:
+            self._dependent_libs.add(library)
+
+    def add_incoming_edges(self, from_node, g):
+        if from_node.type == graph_consts.NODE_FILE:
+            if from_node.library not in self.libs:
+                self.add_dependent_lib(from_node.library)
+
+            self.add_dependent_file(from_node.id)
+
+            lib_node = g.get_node(from_node.library)
+
+            if lib_node is not None and from_node.library not in self.libs:
+                g.add_edge(graph_consts.LIB_SYM, lib_node.id, self.id)
+
+    def __eq__(self, other):
+        if isinstance(other, NodeSymbol):
+            return (self.id == other.id and self._libs == other._libs and
+                    self._files == other._files and
+                    self._dependent_libs == other._dependent_libs and
+                    self._dependent_files == other._dependent_files
+                    )
+        else:
+            return False
+
+    def __ne__(self, other):
+        return not self.__eq__(other)
+
+    def __str__(self):
+        return self.id
+
+
+class NodeFile(NodeInterface):
+    """NodeFile class which represents an object file within the build dependency graph
+    """
+
+    def __init__(self, id, name, input=None):
+        if isinstance(input, dict):
+            should_fail = False
+            for k, v in input.iteritems():
+                try:
+                    if isinstance(v, list):
+                        setattr(self, k, set(v))
+                    else:
+                        setattr(self, k, v)
+                except AttributeError as e:
+                    logging.error("found something bad, {0}, {1}", e, type(e))
+                    should_fail = True
+            if should_fail:
+                raise Exception("Problem setting attribute for NodeLib")
+        else:
+            self._id = id
+            self.type = graph_consts.NODE_FILE
+            self._name = name
+            self._defined_symbols = set()
+            self._dependent_libs = set()
+            self._dependent_files = set()
+            self._lib = None
+
+    @property
+    def id(self):
+        return self._id
+
+    @property
+    def name(self):
+        return self._name
+
+    @property
+    def defined_symbols(self):
+        return self._defined_symbols
+
+    @defined_symbols.setter
+    def defined_symbols(self, value):
+        if isinstance(value, set):
+            self._defined_symbols = value
+        else:
+            raise TypeError("NodeFile.defined_symbols must be a set")
+
+    @property
+    def dependent_libs(self):
+        return self._dependent_libs
+
+    @dependent_libs.setter
+    def dependent_libs(self, value):
+        if isinstance(value, set):
+            self._dependent_libs = value
+        else:
+            raise TypeError("NodeFile.dependent_libs must be a set")
+
+    @property
+    def dependent_files(self):
+        return self._dependent_files
+
+    @dependent_files.setter
+    def dependent_files(self, value):
+        if isinstance(value, set):
+            self._dependent_files = value
+        else:
+            raise TypeError("NodeFile.dependent_files must be a set")
+
+    @property
+    def library(self):
+        return self._lib
+
+    @library.setter
+    def library(self, library):
+        if library is not None:
+            self._lib = library
+
+    def add_defined_symbol(self, symbol):
+        if symbol is not None:
+            self._defined_symbols.add(symbol)
+
+    def add_dependent_file(self, file):
+        if file is not None:
+            self._dependent_files.add(file)
+
+    def add_dependent_lib(self, library):
+        if library is not None:
+            self._dependent_libs.add(library)
+
+    def add_incoming_edges(self, from_node, g):
+        if from_node.type == graph_consts.NODE_FILE:
+            self.add_dependent_file(from_node.id)
+            lib_node = g.get_node(self.library)
+
+            if from_node.library is not None and from_node.library != self.library:
+                self.add_dependent_lib(from_node.library)
+                g.add_edge(graph_consts.LIB_FIL, from_node.library, self.id)
+                if lib_node is not None:
+                        lib_node.add_dependent_file(from_node.id)
+                        lib_node.add_dependent_lib(from_node.library)
+                        g.add_edge(graph_consts.FIL_LIB, from_node.id, lib_node.id)
+
+    def __eq__(self, other):
+        if isinstance(other, NodeSymbol):
+            return (self.id == other.id and self._lib == other._lib and
+                    self._dependent_libs == other._dependent_libs and
+                    self._dependent_files == other._dependent_files and
+                    self._defined_symbols == other._defined_symbols)
+
+        else:
+            return False
+
+    def __ne__(self, other):
+        return not self.__eq__(other)
+
+    def __str__(self):
+        return self.id
+
+
+types = {graph_consts.NODE_LIB: NodeLib,
+         graph_consts.NODE_SYM: NodeSymbol,
+         graph_consts.NODE_FILE: NodeFile}
+
+
+def node_factory(id, nodetype, dict_source=None):
+    if isinstance(dict_source, dict):
+        return types[nodetype](id, id, input=dict_source)
+    else:
+        return types[nodetype](id, id)
diff --git a/site_scons/site_tools/dagger/graph_consts.py b/site_scons/site_tools/dagger/graph_consts.py
new file mode 100644
index 00000000000..1d31bcbfa90
--- /dev/null
+++ b/site_scons/site_tools/dagger/graph_consts.py
@@ -0,0 +1,15 @@
+"""Constants for use in graph.py and dagger.py"""
+
+LIB_LIB = 1
+LIB_FIL = 2
+FIL_LIB = 3
+FIL_FIL = 4
+FIL_SYM = 5
+LIB_SYM = 6
+
+NODE_LIB = 1
+NODE_SYM = 2
+NODE_FILE = 3
+
+RELATIONSHIP_TYPES = range(1, 7)
+NODE_TYPES = range(1, 4)
diff --git a/site_scons/site_tools/dagger/graph_test.py b/site_scons/site_tools/dagger/graph_test.py
new file mode 100644
index 00000000000..bc84f5868c7
--- /dev/null
+++ b/site_scons/site_tools/dagger/graph_test.py
@@ -0,0 +1,212 @@
+"""Tests for the graph class used in the dagger tool. Tests the add_edge and
+add_node methods, along with the methods for exporting and importing the graph
+from JSON
+"""
+
+import json
+import unittest
+import graph
+import graph_consts
+
+
+def generate_graph():
+    """Generates our test graph"""
+
+    g = graph.Graph()
+    sym1 = graph.NodeSymbol("sym1", "sym1")
+
+    lib1 = graph.NodeLib("lib1", "lib1")
+    lib2 = graph.NodeLib("lib2", "lib2")
+    lib3 = graph.NodeLib("lib3", "lib3")
+
+    file1 = graph.NodeFile("file1", "file1")
+    file2 = graph.NodeFile("file2", "file2")
+    file3 = graph.NodeFile("file3", "file3")
+
+    lib_sym = graph.NodeLib("lib_sym", "lib_sym")
+    file_sym = graph.NodeFile("file_sym", "file_sym")
+
+    g.add_node(sym1)
+    g.add_node(lib1)
+    g.add_node(lib2)
+    g.add_node(lib3)
+    g.add_node(file1)
+    g.add_node(file2)
+    g.add_node(file3)
+    g.add_node(lib_sym)
+    g.add_node(file_sym)
+
+    sym1.add_file(file_sym.id)
+    sym1.add_library(lib_sym.id)
+    lib_sym.add_defined_symbol(sym1.id)
+    file_sym.add_defined_symbol(sym1.id)
+
+    file1.library = lib1.id
+    lib1.add_defined_file(file1.id)
+    g.add_edge(graph_consts.FIL_SYM, file1.id, sym1.id)
+    g.add_edge(graph_consts.LIB_SYM, lib1.id, sym1.id)
+    g.add_edge(graph_consts.FIL_FIL, file1.id, file_sym.id)
+    g.add_edge(graph_consts.LIB_LIB, lib1.id, lib_sym.id)
+
+    file3.library = lib3.id
+    lib3.add_defined_file(file3.id)
+
+    file2.library = lib2.id
+    lib2.add_defined_file(file2.id)
+
+    g.add_edge(graph_consts.LIB_LIB, lib2.id, lib3.id)
+    g.add_edge(graph_consts.LIB_FIL, lib2.id, file3.id)
+    g.add_edge(graph_consts.FIL_FIL, file2.id, file3.id)
+
+    lib3.add_dependent_file(file2.id)
+    file3.add_dependent_file(file2.id)
+    lib3.add_dependent_lib(lib2.id)
+
+    return g
+
+
+class CustomAssertions:
+    """Custom Assertion class for testing node equality"""
+
+    def assertNodeEquals(self, node1, node2):
+        if node1.type != node2.type:
+            raise AssertionError("Nodes not of same type")
+
+        if node1.type == graph_consts.NODE_LIB:
+            if (node1._defined_symbols != node2._defined_symbols or
+                    node1._defined_files != node2._defined_files or
+                    node1._dependent_libs != node2._dependent_libs or
+                    node1._dependent_files != node2._dependent_files or
+                    node1._id != node2._id):
+                raise AssertionError("Nodes not equal")
+
+        elif node1.type == graph_consts.NODE_SYM:
+            if (node1._libs != node2._libs or node1._files != node2._files or
+                    node1._dependent_libs != node2._dependent_libs or
+                    node1._dependent_files != node2._dependent_files or
+                    node1.id != node2.id):
+                raise AssertionError("Nodes not equal")
+
+        else:
+            if (node1._lib != node2._lib or
+                    node1._dependent_libs != node2._dependent_libs or
+                    node1._dependent_files != node2._dependent_files or
+                    node1.id != node2.id or
+                    node1._defined_symbols != node2._defined_symbols):
+                raise AssertionError("Nodes not equal")
+
+
+class TestGraphMethods(unittest.TestCase, CustomAssertions):
+    """Unit tests for graph methods"""
+
+    def setUp(self):
+        self.g = graph.Graph()
+
+        self.from_node_lib = graph.NodeLib("from_node_lib", "from_node_lib")
+        self.to_node_lib = graph.NodeLib("to_node_lib", "to_node_lib")
+        self.from_node_file = graph.NodeFile(
+            "from_node_file", "from_node_file")
+        self.to_node_file = graph.NodeFile("to_node_file", "to_node_file")
+        self.from_node_sym = graph.NodeSymbol(
+            "from_node_symbol", "from_node_symbol")
+        self.to_node_sym = graph.NodeSymbol("to_node_symbol", "to_node_symbol")
+
+        self.g.add_node(self.from_node_lib)
+        self.g.add_node(self.to_node_lib)
+        self.g.add_node(self.from_node_file)
+        self.g.add_node(self.to_node_file)
+        self.g.add_node(self.from_node_sym)
+        self.g.add_node(self.to_node_sym)
+
+    def test_get_node(self):
+        node = graph.NodeLib("test_node", "test_node")
+        self.g._nodes = {"test_node": node}
+
+        self.assertEquals(self.g.get_node("test_node"), node)
+
+        self.assertEquals(self.g.get_node("missing_node"), None)
+
+    def test_add_node(self):
+        node = graph.NodeLib("test_node", "test_node")
+        self.g.add_node(node)
+
+        self.assertEquals(self.g.get_node("test_node"), node)
+
+        self.assertRaises(ValueError, self.g.add_node, node)
+
+        self.assertRaises(TypeError, self.g.add_node, "not a node")
+
+    def test_add_edge_exceptions(self):
+        self.assertRaises(TypeError, self.g.add_edge, "NOT A RELATIONSHIP",
+                          self.from_node_lib.id, self.to_node_lib.id)
+
+        self.assertRaises(ValueError, self.g.add_edge,
+                          graph_consts.LIB_LIB, "not a node", "not a node")
+
+    def test_add_edge_libs(self):
+        self.g.add_edge(graph_consts.LIB_LIB, self.from_node_lib.id,
+                        self.to_node_lib.id)
+        self.g.add_edge(graph_consts.LIB_LIB, self.from_node_lib.id,
+                        self.to_node_lib.id)
+        self.g.add_edge(graph_consts.LIB_SYM, self.from_node_lib.id,
+                        self.to_node_sym.id)
+        self.g.add_edge(graph_consts.LIB_FIL, self.from_node_lib.id,
+                        self.to_node_file.id)
+
+        self.assertEquals(self.g.edges[graph_consts.LIB_LIB][
+            self.from_node_lib.id], set([self.to_node_lib.id]))
+
+        self.assertEquals(self.g.edges[graph_consts.LIB_SYM][
+            self.from_node_lib.id], set([self.to_node_sym.id]))
+
+        self.assertEquals(self.g.edges[graph_consts.LIB_FIL][
+            self.from_node_lib.id], set([self.to_node_file.id]))
+
+        self.assertEquals(self.to_node_lib.dependent_libs,
+                          set([self.from_node_lib.id]))
+
+    def test_add_edge_files(self):
+        self.g.add_edge(graph_consts.FIL_FIL, self.from_node_file.id,
+                        self.to_node_file.id)
+        self.g.add_edge(graph_consts.FIL_SYM, self.from_node_file.id,
+                        self.to_node_sym.id)
+        self.g.add_edge(graph_consts.FIL_LIB, self.from_node_file.id,
+                        self.to_node_lib.id)
+
+        self.assertEquals(self.g.edges[graph_consts.FIL_FIL][
+            self.from_node_file.id], set([self.to_node_file.id]))
+        self.assertEquals(self.g.edges[graph_consts.FIL_SYM][
+            self.from_node_file.id], set([self.to_node_sym.id]))
+        self.assertEquals(self.g.edges[graph_consts.FIL_LIB][
+            self.from_node_file.id], set([self.to_node_lib.id]))
+
+        self.assertEquals(self.to_node_file.dependent_files,
+                          set([self.from_node_file.id]))
+
+    def test_export_to_json(self):
+        generated_graph = generate_graph()
+        generated_graph.export_to_json("export_test.json")
+        generated = open("export_test.json", "r")
+        correct = open("test_graph.json", "r")
+        self.assertEquals(json.load(generated), json.load(correct))
+        generated.close()
+        correct.close()
+
+    def test_fromJSON(self):
+        graph_fromJSON = graph.Graph("test_graph.json")
+        correct_graph = generate_graph()
+
+        for id in graph_fromJSON.nodes.keys():
+            # for some reason, neither
+            # assertTrue(graph_fromJSON.get_node(id) == correct_graph.get_node(str(id)))
+            # nor assertEquals() seem to call the correct eq method here, hence
+            # the need for a custom assertion
+
+            self.assertNodeEquals(
+                graph_fromJSON.get_node(id), correct_graph.get_node(id))
+
+        self.assertEquals(graph_fromJSON.edges, correct_graph.edges)
+
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/site_scons/site_tools/dagger/test_graph.json b/site_scons/site_tools/dagger/test_graph.json
new file mode 100644
index 00000000000..78cfbb0ce7b
--- /dev/null
+++ b/site_scons/site_tools/dagger/test_graph.json
@@ -0,0 +1,272 @@
+{
+    "nodes": [
+        {
+            "node": {
+                "_dependent_libs": [
+                    "lib2"
+                ], 
+                "_lib": "lib3", 
+                "_name": "file3", 
+                "_dependent_files": [
+                    "file2"
+                ], 
+                "_defined_symbols": [], 
+                "_id": "file3", 
+                "type": 3
+            }, 
+            "index": 0, 
+            "id": "file3"
+        }, 
+        {
+            "node": {
+                "_dependent_libs": [], 
+                "_lib": "lib2", 
+                "_name": "file2", 
+                "_dependent_files": [], 
+                "_defined_symbols": [], 
+                "_id": "file2", 
+                "type": 3
+            }, 
+            "index": 1, 
+            "id": "file2"
+        }, 
+        {
+            "node": {
+                "_dependent_libs": [], 
+                "_lib": "lib1", 
+                "_name": "file1", 
+                "_dependent_files": [], 
+                "_defined_symbols": [], 
+                "_id": "file1", 
+                "type": 3
+            }, 
+            "index": 2, 
+            "id": "file1"
+        }, 
+        {
+            "node": {
+                "_dependent_libs": [
+                    "lib1"
+                ], 
+                "_lib": null, 
+                "_name": "file_sym", 
+                "_dependent_files": [
+                    "file1"
+                ], 
+                "_defined_symbols": [
+                    "sym1"
+                ], 
+                "_id": "file_sym", 
+                "type": 3
+            }, 
+            "index": 3, 
+            "id": "file_sym"
+        }, 
+        {
+            "node": {
+                "_dependent_libs": [
+                    "lib1"
+                ], 
+                "_files": [
+                    "file_sym"
+                ], 
+                "_name": "sym1", 
+                "_dependent_files": [
+                    "file1"
+                ], 
+                "_libs": [
+                    "lib_sym"
+                ], 
+                "_id": "sym1", 
+                "type": 2
+            }, 
+            "index": 4, 
+            "id": "sym1"
+        }, 
+        {
+            "node": {
+                "_dependent_files": [
+                    "file2"
+                ], 
+                "_defined_files": [
+                    "file3"
+                ], 
+                "_name": "lib3", 
+                "_dependent_libs": [
+                    "lib2"
+                ], 
+                "_defined_symbols": [], 
+                "_id": "lib3", 
+                "type": 1
+            }, 
+            "index": 5, 
+            "id": "lib3"
+        }, 
+        {
+            "node": {
+                "_dependent_files": [], 
+                "_defined_files": [
+                    "file2"
+                ], 
+                "_name": "lib2", 
+                "_dependent_libs": [], 
+                "_defined_symbols": [], 
+                "_id": "lib2", 
+                "type": 1
+            }, 
+            "index": 6, 
+            "id": "lib2"
+        }, 
+        {
+            "node": {
+                "_dependent_files": [], 
+                "_defined_files": [
+                    "file1"
+                ], 
+                "_name": "lib1", 
+                "_dependent_libs": [], 
+                "_defined_symbols": [], 
+                "_id": "lib1", 
+                "type": 1
+            }, 
+            "index": 7, 
+            "id": "lib1"
+        }, 
+        {
+            "node": {
+                "_dependent_files": [], 
+                "_defined_files": [], 
+                "_name": "lib_sym", 
+                "_dependent_libs": [
+                    "lib1"
+                ], 
+                "_defined_symbols": [
+                    "sym1"
+                ], 
+                "_id": "lib_sym", 
+                "type": 1
+            }, 
+            "index": 8, 
+            "id": "lib_sym"
+        }
+    ], 
+    "edges": [
+        {
+            "type": 1, 
+            "to_node": [
+                {
+                    "index": 5, 
+                    "id": "lib3"
+                }
+            ], 
+            "from_node": {
+                "index": 6, 
+                "id": "lib2"
+            }
+        }, 
+        {
+            "type": 1, 
+            "to_node": [
+                {
+                    "index": 8, 
+                    "id": "lib_sym"
+                }
+            ], 
+            "from_node": {
+                "index": 7, 
+                "id": "lib1"
+            }
+        }, 
+        {
+            "type": 2, 
+            "to_node": [
+                {
+                    "index": 0, 
+                    "id": "file3"
+                }
+            ], 
+            "from_node": {
+                "index": 6, 
+                "id": "lib2"
+            }
+        }, 
+        {
+            "type": 2, 
+            "to_node": [
+                {
+                    "index": 3, 
+                    "id": "file_sym"
+                }
+            ], 
+            "from_node": {
+                "index": 7, 
+                "id": "lib1"
+            }
+        }, 
+        {
+            "type": 3, 
+            "to_node": [
+                {
+                    "index": 5, 
+                    "id": "lib3"
+                }
+            ], 
+            "from_node": {
+                "index": 1, 
+                "id": "file2"
+            }
+        }, 
+        {
+            "type": 4, 
+            "to_node": [
+                {
+                    "index": 0, 
+                    "id": "file3"
+                }
+            ], 
+            "from_node": {
+                "index": 1, 
+                "id": "file2"
+            }
+        }, 
+        {
+            "type": 4, 
+            "to_node": [
+                {
+                    "index": 3, 
+                    "id": "file_sym"
+                }
+            ], 
+            "from_node": {
+                "index": 2, 
+                "id": "file1"
+            }
+        }, 
+        {
+            "type": 5, 
+            "to_node": [
+                {
+                    "index": 4, 
+                    "id": "sym1"
+                }
+            ], 
+            "from_node": {
+                "index": 2, 
+                "id": "file1"
+            }
+        }, 
+        {
+            "type": 6, 
+            "to_node": [
+                {
+                    "index": 4, 
+                    "id": "sym1"
+                }
+            ], 
+            "from_node": {
+                "index": 7, 
+                "id": "lib1"
+            }
+        }
+    ]
+}
\ No newline at end of file