The whole profile.
| 253 | |
| 254 | |
| 255 | class Profile(Object): |
| 256 | """The whole profile.""" |
| 257 | |
| 258 | def __init__(self): |
| 259 | Object.__init__(self) |
| 260 | self.functions = {} |
| 261 | self.cycles = [] |
| 262 | |
| 263 | def add_function(self, function): |
| 264 | if function.id in self.functions: |
| 265 | sys.stderr.write('warning: overwriting function %s (id %s)\n' % (function.name, str(function.id))) |
| 266 | self.functions[function.id] = function |
| 267 | |
| 268 | def add_cycle(self, cycle): |
| 269 | self.cycles.append(cycle) |
| 270 | |
| 271 | def validate(self): |
| 272 | """Validate the edges.""" |
| 273 | |
| 274 | for function in self.functions.values(): |
| 275 | for callee_id in list(function.calls.keys()): |
| 276 | assert function.calls[callee_id].callee_id == callee_id |
| 277 | if callee_id not in self.functions: |
| 278 | sys.stderr.write('warning: call to undefined function %s from function %s\n' % (str(callee_id), function.name)) |
| 279 | del function.calls[callee_id] |
| 280 | |
| 281 | def find_cycles(self): |
| 282 | """Find cycles using Tarjan's strongly connected components algorithm.""" |
| 283 | |
| 284 | # Apply the Tarjan's algorithm successively until all functions are visited |
| 285 | visited = set() |
| 286 | for function in self.functions.values(): |
| 287 | if function not in visited: |
| 288 | self._tarjan(function, 0, [], {}, {}, visited) |
| 289 | cycles = [] |
| 290 | for function in self.functions.values(): |
| 291 | if function.cycle is not None and function.cycle not in cycles: |
| 292 | cycles.append(function.cycle) |
| 293 | self.cycles = cycles |
| 294 | if 0: |
| 295 | for cycle in cycles: |
| 296 | sys.stderr.write("Cycle:\n") |
| 297 | for member in cycle.functions: |
| 298 | sys.stderr.write("\tFunction %s\n" % member.name) |
| 299 | |
| 300 | def _tarjan(self, function, order, stack, orders, lowlinks, visited): |
| 301 | """Tarjan's strongly connected components algorithm. |
| 302 | |
| 303 | See also: |
| 304 | - http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm |
| 305 | """ |
| 306 | |
| 307 | visited.add(function) |
| 308 | orders[function] = order |
| 309 | lowlinks[function] = order |
| 310 | order += 1 |
| 311 | pos = len(stack) |
| 312 | stack.append(function) |