Created
April 15, 2025 04:27
-
-
Save EliteMasterEric/4bef1727015afaf3dffaca9b0b2b8d59 to your computer and use it in GitHub Desktop.
Sort dependencies generated by Haxe compiler (-D dump-dependencies)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import os | |
| from collections import defaultdict | |
| def is_core_file(file): | |
| """Determine if a file is a core file that should be prioritized in dependency resolution.""" | |
| core_indicators = ['StdTypes.hx', 'String.hx', 'Array.hx'] | |
| return any(indicator in file for indicator in core_indicators) | |
| def find_strongly_connected_components(graph): | |
| """Find all strongly connected components in the graph using Tarjan's algorithm.""" | |
| index = 0 | |
| indices = {} | |
| lowlinks = {} | |
| on_stack = set() | |
| stack = [] | |
| components = [] | |
| def strongconnect(node): | |
| nonlocal index | |
| indices[node] = index | |
| lowlinks[node] = index | |
| index += 1 | |
| stack.append(node) | |
| on_stack.add(node) | |
| for neighbor in graph[node]: | |
| if neighbor not in indices: | |
| strongconnect(neighbor) | |
| lowlinks[node] = min(lowlinks[node], lowlinks[neighbor]) | |
| elif neighbor in on_stack: | |
| lowlinks[node] = min(lowlinks[node], indices[neighbor]) | |
| if lowlinks[node] == indices[node]: | |
| component = [] | |
| while True: | |
| w = stack.pop() | |
| on_stack.remove(w) | |
| component.append(w) | |
| if w == node: | |
| break | |
| if len(component) > 1: | |
| components.append(component) | |
| for node in graph: | |
| if node not in indices: | |
| strongconnect(node) | |
| return components | |
| def break_cycles(graph, components): | |
| """Break cycles by removing edges that connect components.""" | |
| edges_to_remove = set() | |
| for component in components: | |
| # Find the node with the most dependencies within the component | |
| max_deps = -1 | |
| node_to_break = None | |
| for node in component: | |
| deps_in_component = sum(1 for dep in graph[node] if dep in component) | |
| if deps_in_component > max_deps: | |
| max_deps = deps_in_component | |
| node_to_break = node | |
| if node_to_break: | |
| # Remove all dependencies of this node that are within the component | |
| for dep in list(graph[node_to_break]): | |
| if dep in component: | |
| edges_to_remove.add((node_to_break, dep)) | |
| graph[node_to_break].remove(dep) | |
| return edges_to_remove | |
| def process_dependencies(input_file, output_file): | |
| # Dictionary to store which files are needed by each file | |
| # graph[file] = set of files that file depends on | |
| graph = defaultdict(set) | |
| # Set to store all unique files | |
| all_files = set() | |
| with open(input_file, 'r', encoding='utf-8') as f: | |
| current_file = None | |
| for line in f: | |
| line = line.rstrip('\n') # Remove trailing newline but keep tabs | |
| if not line: | |
| continue | |
| # If line starts with a tab, it's a dependency | |
| if line.startswith('\t'): | |
| if current_file: | |
| # Remove tab and any trailing whitespace | |
| dep = line.lstrip('\t').rstrip() | |
| # Add dependency: current_file depends on dep | |
| graph[current_file].add(dep) | |
| all_files.add(dep) | |
| else: | |
| # New file found (remove trailing colon) | |
| current_file = line.rstrip(':') | |
| all_files.add(current_file) | |
| # Initialize empty dependency set if not already present | |
| if current_file not in graph: | |
| graph[current_file] = set() | |
| # Debug: Print dependencies for a few key files | |
| print("\nDependency Graph (sample):") | |
| for file in sorted(list(all_files))[:5]: | |
| print(f"{file} depends on: {sorted(graph[file])}") | |
| # Ensure all referenced files are in the graph | |
| for file in list(all_files): | |
| if file not in graph: | |
| graph[file] = set() | |
| # Find and break cycles | |
| components = find_strongly_connected_components(graph) | |
| if components: | |
| print(f"\nFound {len(components)} strongly connected components (cycles):") | |
| for i, component in enumerate(components, 1): | |
| print(f"Cycle {i}: {sorted(component)}") | |
| edges_removed = break_cycles(graph, components) | |
| print(f"\nRemoved {len(edges_removed)} edges to break cycles:") | |
| for src, dst in sorted(edges_removed): | |
| print(f" {src} -> {dst}") | |
| # Topological sort using Kahn's algorithm | |
| # Count incoming edges for each node | |
| in_degree = defaultdict(int) | |
| for file in all_files: | |
| for dep in graph[file]: | |
| in_degree[dep] += 1 | |
| # Debug: Print in-degrees | |
| print("\nIn-degrees (sample):") | |
| for file in sorted(list(all_files))[:5]: | |
| print(f"{file}: {in_degree[file]}") | |
| # First process core files | |
| sorted_files = [] | |
| core_files = sorted([f for f in all_files if is_core_file(f)]) | |
| for core in core_files: | |
| if core in all_files: | |
| sorted_files.append(core) | |
| all_files.remove(core) | |
| # Update in-degrees | |
| for file in all_files: | |
| if core in graph[file]: | |
| in_degree[core] -= 1 | |
| # Queue for files with no incoming edges (no dependencies) | |
| queue = [file for file in all_files if in_degree[file] == 0] | |
| print("\nInitial files with no dependencies:") | |
| print(sorted(queue)[:5]) | |
| while queue: | |
| # Sort the queue alphabetically within the same dependency level | |
| queue.sort() | |
| file = queue.pop(0) | |
| sorted_files.append(file) | |
| # For each file that depends on the current file | |
| for dependent in sorted([f for f in all_files if file in graph[f]]): | |
| in_degree[dependent] -= 1 | |
| if in_degree[dependent] == 0: | |
| queue.append(dependent) | |
| # Check for remaining files (possible cycles) | |
| remaining = all_files - set(sorted_files) | |
| if remaining: | |
| print("\nWarning: Some files could not be sorted due to circular dependencies") | |
| print("Adding remaining files in alphabetical order...") | |
| sorted_files.extend(sorted(remaining)) | |
| # Write sorted files to output | |
| with open(output_file, 'w', encoding='utf-8') as f: | |
| for file in sorted_files: | |
| f.write(f"{file}\n") | |
| if __name__ == "__main__": | |
| input_file = "dump/cpp/dependencies.dump" | |
| output_file = "sorted_dependencies.txt" | |
| if not os.path.exists(input_file): | |
| print(f"Error: Input file '{input_file}' not found!") | |
| exit(1) | |
| process_dependencies(input_file, output_file) | |
| print(f"\nSuccessfully processed dependencies. Output written to {output_file}") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment