make_ext_dependency.py
1 #!/usr/bin/env python3 2 # 3 # Copyright (c) 2017-2019 The Khronos Group Inc. 4 # 5 # Licensed under the Apache License, Version 2.0 (the "License"); 6 # you may not use this file except in compliance with the License. 7 # You may obtain a copy of the License at 8 # 9 # http://www.apache.org/licenses/LICENSE-2.0 10 # 11 # Unless required by applicable law or agreed to in writing, software 12 # distributed under the License is distributed on an "AS IS" BASIS, 13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 # See the License for the specific language governing permissions and 15 # limitations under the License. 16 17 # make_ext_dependency.py - generate a mapping of extension name -> all 18 # required extension names for that extension. 19 20 # This script generates a list of all extensions, and of just KHR 21 # extensions, that are placed into a Bash script and/or Python script. This 22 # script can then be sources or executed to set a variable (e.g., khrExts), 23 # Frontend scripts such as 'makeAllExts' and 'makeKHR' use this information 24 # to set the EXTENSIONS Makefile variable when building the spec. 25 # 26 # Sample Usage: 27 # 28 # python3 scripts/make_ext_dependency.py -outscript=temp.sh 29 # source temp.sh 30 # make EXTENSIONS="$khrExts" html 31 # rm temp.sh 32 33 import argparse 34 import xml.etree.ElementTree as etree 35 from vkconventions import VulkanConventions as APIConventions 36 37 def enQuote(key): 38 return "'" + str(key) + "'" 39 40 # Return a sortable (list or set) of names as a string encoding 41 # of a Bash or Python list, sorted on the names. 42 43 def shList(names): 44 s = ('"' + 45 ' '.join(str(key) for key in sorted(names)) + 46 '"') 47 return s 48 49 def pyList(names): 50 s = ('[ ' + 51 ', '.join(enQuote(key) for key in sorted(names)) + 52 ' ]') 53 return s 54 55 class DiGraph: 56 """A directed graph. 57 58 The implementation and API mimic that of networkx.DiGraph in networkx-1.11. 59 networkx implements graphs as nested dicts; it's dicts all the way down, no 60 lists. 61 62 Some major differences between this implementation and that of 63 networkx-1.11 are: 64 65 * This omits edge and node attribute data, because we never use them 66 yet they add additional code complexity. 67 68 * This returns iterator objects when possible instead of collection 69 objects, because it simplifies the implementation and should provide 70 better performance. 71 """ 72 73 def __init__(self): 74 self.__nodes = {} 75 76 def add_node(self, node): 77 if node not in self.__nodes: 78 self.__nodes[node] = DiGraphNode() 79 80 def add_edge(self, src, dest): 81 self.add_node(src) 82 self.add_node(dest) 83 self.__nodes[src].adj.add(dest) 84 85 def nodes(self): 86 """Iterate over the nodes in the graph.""" 87 return self.__nodes.keys() 88 89 def descendants(self, node): 90 """ 91 Iterate over the nodes reachable from the given start node, excluding 92 the start node itself. Each node in the graph is yielded at most once. 93 """ 94 95 # Implementation detail: Do a breadth-first traversal because it's 96 # easier than depth-first. 97 98 # All nodes seen during traversal. 99 seen = set() 100 101 # The stack of nodes that need visiting. 102 visit_me = [] 103 104 # Bootstrap the traversal. 105 seen.add(node) 106 for x in self.__nodes[node].adj: 107 if x not in seen: 108 seen.add(x) 109 visit_me.append(x) 110 111 while visit_me: 112 x = visit_me.pop() 113 assert x in seen 114 yield x 115 116 for y in self.__nodes[x].adj: 117 if y not in seen: 118 seen.add(y) 119 visit_me.append(y) 120 121 class DiGraphNode: 122 123 def __init__(self): 124 # Set of adjacent of nodes. 125 self.adj = set() 126 127 # API conventions object 128 conventions = APIConventions() 129 130 # -extension name - may be a single extension name, a space-separated list 131 # of names, or a regular expression. 132 if __name__ == '__main__': 133 parser = argparse.ArgumentParser() 134 135 parser.add_argument('-registry', action='store', 136 default=conventions.registry_path, 137 help='Use specified registry file instead of ' + conventions.registry_path) 138 parser.add_argument('-outscript', action='store', 139 default=None, 140 help='Shell script to create') 141 parser.add_argument('-outpy', action='store', 142 default=None, 143 help='Python script to create') 144 parser.add_argument('-test', action='store', 145 default=None, 146 help='Specify extension to find dependencies of') 147 parser.add_argument('-quiet', action='store_true', default=False, 148 help='Suppress script output during normal execution.') 149 150 args = parser.parse_args() 151 152 tree = etree.parse(args.registry) 153 154 # Loop over all supported extensions, creating a digraph of the 155 # extension dependencies in the 'requires' attribute, which is a 156 # comma-separated list of extension names. Also track lists of 157 # all extensions and all KHR extensions. 158 159 allExts = set() 160 khrExts = set() 161 g = DiGraph() 162 163 for elem in tree.findall('extensions/extension'): 164 name = elem.get('name') 165 supported = elem.get('supported') 166 167 if supported == conventions.xml_api_name: 168 allExts.add(name) 169 170 if 'KHR' in name: 171 khrExts.add(name) 172 173 deps = elem.get('requires') 174 if deps: 175 deps = deps.split(',') 176 177 for dep in deps: 178 g.add_edge(name, dep) 179 else: 180 g.add_node(name) 181 else: 182 # Skip unsupported extensions 183 pass 184 185 if args.outscript: 186 fp = open(args.outscript, 'w', encoding='utf-8') 187 188 print('#!/bin/bash', file=fp) 189 print('# Generated from make_ext_dependency.py', file=fp) 190 print('# Specify maps of all extensions required by an enabled extension', file=fp) 191 print('', file=fp) 192 print('declare -A extensions', file=fp) 193 194 # When printing lists of extensions, sort them so that the output script 195 # remains as stable as possible as extensions are added to the API XML. 196 197 for ext in sorted(g.nodes()): 198 children = list(g.descendants(ext)) 199 200 # Only emit an ifdef block if an extension has dependencies 201 if children: 202 print('extensions[' + ext + ']=' + shList(children), file=fp) 203 204 print('', file=fp) 205 print('# Define lists of all extensions and KHR extensions', file=fp) 206 print('allExts=' + shList(allExts), file=fp) 207 print('khrExts=' + shList(khrExts), file=fp) 208 209 fp.close() 210 211 if args.outpy: 212 fp = open(args.outpy, 'w', encoding='utf-8') 213 214 print('#!/usr/bin/env python', file=fp) 215 print('# Generated from make_ext_dependency.py', file=fp) 216 print('# Specify maps of all extensions required by an enabled extension', file=fp) 217 print('', file=fp) 218 print('extensions = {}', file=fp) 219 220 # When printing lists of extensions, sort them so that the output script 221 # remains as stable as possible as extensions are added to the API XML. 222 223 for ext in sorted(g.nodes()): 224 children = list(g.descendants(ext)) 225 226 # Only emit an ifdef block if an extension has dependencies 227 if children: 228 print("extensions['" + ext + "'] = " + pyList(children), file=fp) 229 230 print('', file=fp) 231 print('# Define lists of all extensions and KHR extensions', file=fp) 232 print('allExts = ' + pyList(allExts), file=fp) 233 print('khrExts = ' + pyList(khrExts), file=fp) 234 235 fp.close()