File indexing completed on 2023-03-17 11:26:48
0001
0002
0003
0004 import collections
0005
0006 class Graph(object):
0007 def __init__(self, edges):
0008 self.edges = edges
0009
0010 @staticmethod
0011 def _build_adjacency_list(edges):
0012 adj = collections.defaultdict(list)
0013 for edge in edges:
0014 adj[edge[0]].append(edge[1])
0015 return adj
0016
0017 def addEdge(self,edge):
0018 self.edges.append(edge)
0019
0020 def build_adjacency_list(self):
0021 self.adj = Graph._build_adjacency_list(self.edges)
0022
0023
0024 def dfs(G):
0025 discovered = set()
0026 finished = set()
0027 for u in G.adj:
0028 if u not in discovered and u not in finished:
0029 discovered, finished = dfs_visit(G, u, discovered, finished)
0030
0031 def dfs_visit(G, u, discovered, finished):
0032 if u not in G.adj:
0033 finished.add(u)
0034 return discovered, finished
0035
0036 discovered.add(u)
0037
0038 for v in G.adj[u]:
0039
0040 if v in discovered:
0041 print(f"Cycle detected: found a back edge from {u} to {v}. It involves")
0042 for i,d in enumerate(discovered):
0043 if i != len(discovered)-1:
0044 print(d,end=', ')
0045 else:
0046 print(d)
0047
0048
0049 else:
0050 if v not in finished:
0051 dfs_visit(G, v, discovered, finished)
0052
0053 discovered.remove(u)
0054 finished.add(u)
0055
0056 return discovered, finished
0057
0058 import subprocess
0059 def run_command(comm):
0060 encoding = 'utf-8'
0061 proc = subprocess.Popen(comm, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, shell=True)
0062 stdout, stderr = proc.communicate()
0063 stdout = stdout.decode(encoding)
0064 if stderr is not None:
0065 stderr= stderr.decode(encoding)
0066 return proc.returncode, stdout, stderr
0067
0068
0069 import os
0070 def get_pack_list():
0071 src_base = os.environ.get('CMSSW_RELEASE_BASE')
0072 src_path = os.path.join(src_base,"src")
0073 comm = "ls -d "+src_path+"/*/*/interface"
0074 c_rt,c_out,c_err = run_command(comm)
0075
0076 ret_val=[]
0077 for l in c_out.split():
0078 sp=l.split('/')
0079 ret_val.append('/'.join(sp[-3:-1]))
0080
0081 return ret_val
0082
0083 def get_files(pack,subdir,file_types):
0084 src_base = os.environ.get('CMSSW_RELEASE_BASE')
0085 pack_path = os.path.join(src_base,"src",pack,subdir)
0086 if not os.path.exists(pack_path): return []
0087 ret_val=[]
0088 for root, dirs, files in os.walk(pack_path, topdown=False):
0089 for name in files:
0090 for t in file_types:
0091 if name.endswith(t):
0092 ret_val.append(os.path.join(root,name))
0093
0094 return ret_val
0095
0096 def get_lib_deps(lib_info):
0097 lib_path = lib_info[1]
0098 comm = "ldd "+lib_path+"| grep cms | grep -v \"/external\" | grep -v \"/lcg/\" | awk '{print $3}'"
0099 c_rt,c_out,c_err = run_command(comm)
0100 ret_val=[]
0101 for l in c_out.split():
0102 lib = l.strip()
0103 ret_val.append( (lib.split('/')[-1],lib))
0104 return ret_val
0105
0106 def get_include_packages(file_list,package=None,is_cuda=False):
0107 incs={}
0108 pack_incs={}
0109 if is_cuda:
0110 comm= "gcc -fpreprocessed -dD -E "
0111 else:
0112 comm= "nvcc --compiler-options -fpreprocessed -dD -E "
0113 for f in file_list:
0114 comm=comm+f+" "
0115 comm=comm+" | grep \"#include\""
0116 c_rt,c_out,c_err = run_command(comm)
0117 for l in c_out.split():
0118 inc = l.strip().split()[-1][1:-1]
0119 if '/' in inc:
0120 incs['/'.join(inc.split('/')[0:2])]=1
0121 if package is not None and package in inc and "interface" in inc:
0122 pack_incs[os.path.join('/'.join(file_list[0].split('/')[0:-4]),inc)]=1
0123 if package is None:
0124 return list(incs.keys())
0125 else:
0126 return list(incs.keys()),list(pack_incs.keys())
0127
0128
0129
0130 import sys
0131
0132 if __name__ == "__main__":
0133
0134
0135 import argparse
0136 parser=argparse.ArgumentParser(description="CMSSW Cyclic dependency finder")
0137 parser.add_argument("--omit_header_only",dest="omit_header_only",
0138 action="store_false", default=True,
0139 help="Ignore cycles due to header only dependencies"
0140 )
0141 parser.add_argument("--status_bar",dest="status_bar",
0142 action="store_true", default=False,
0143 help="Show progress bar when running"
0144 )
0145
0146 args = parser.parse_args()
0147 omit_header_only=args.omit_header_only
0148 show_status_bar=args.status_bar
0149 print(omit_header_only,show_status_bar)
0150 if 'CMSSW_RELEASE_BASE' not in os.environ:
0151 print("Execute within a cmssw environment")
0152 sys.exit(1)
0153
0154 G = Graph([])
0155
0156 lib_list = get_pack_list()
0157
0158 if show_status_bar:
0159 import tqdm
0160 iter_lib = tqdm.tqdm(lib_list)
0161 else:
0162 iter_lib = lib_list
0163 for lib in iter_lib:
0164 header_list = get_files(lib,"interface",[".h",".hpp"])
0165 source_list = get_files(lib,"src",[".cc",".cpp",".cxx"])
0166 cuda_source_list = get_files(lib,"src",[".cu"])
0167
0168 cpp_incs_packages, cpp_self_headers = get_include_packages(source_list,lib)
0169 cuda_incs_packages, cuda_self_headers = get_include_packages(cuda_source_list,lib,is_cuda=True)
0170
0171 source_incs_packages = list(cpp_incs_packages)
0172 source_incs_packages.extend(x for x in cuda_incs_packages if x not in source_incs_packages)
0173 self_headers = list(cpp_self_headers)
0174 self_headers.extend(x for x in cuda_self_headers if x not in self_headers)
0175
0176 if not omit_header_only:
0177 header_incs_packages = get_include_packages(header_list)
0178 else:
0179 header_incs_packages = get_include_packages(self_headers)
0180
0181 for dep in header_incs_packages:
0182 if dep != lib:
0183 G.addEdge( (lib,dep) )
0184 for dep in source_incs_packages:
0185 if dep != lib and dep not in header_incs_packages:
0186 G.addEdge( (lib,dep) )
0187
0188 print("Building adjacency graph")
0189 G.build_adjacency_list()
0190 print("Looking for cycles")
0191 dfs(G)
0192
