diff options
author | Juggls <mattlee446@gmail.com> | 2016-07-29 11:58:24 -0400 |
---|---|---|
committer | Juggls <mattlee446@gmail.com> | 2016-07-29 13:43:09 -0400 |
commit | 3a25e6f73c4b740b088e95b804df3aab6f7564c3 (patch) | |
tree | 01eba58b457e98f26aae9002ccd6ae4044181090 /site_scons | |
parent | e6793022c2bbc3bcda7356f183ce007592b4aefc (diff) | |
download | mongo-3a25e6f73c4b740b088e95b804df3aab6f7564c3.tar.gz |
SERVER-24838: add scons tool for capturing dependency graph
Diffstat (limited to 'site_scons')
-rw-r--r-- | site_scons/site_tools/dagger/__init__.py | 42 | ||||
-rw-r--r-- | site_scons/site_tools/dagger/dagger.py | 256 | ||||
-rw-r--r-- | site_scons/site_tools/dagger/export_test.json | 272 | ||||
-rw-r--r-- | site_scons/site_tools/dagger/graph.py | 546 | ||||
-rw-r--r-- | site_scons/site_tools/dagger/graph_consts.py | 15 | ||||
-rw-r--r-- | site_scons/site_tools/dagger/graph_test.py | 212 | ||||
-rw-r--r-- | site_scons/site_tools/dagger/test_graph.json | 272 |
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 |