TL;DR
This paper introduces a novel multi-view graph clustering approach to decompose "God Header Files" – large, complex header files that hinder code maintenance and slow down compilation. Their method achieves higher accuracy and better architectural quality than existing techniques, significantly reducing recompilation times by up to 60%.
What Problem Does This Paper Address?
In large C/C++ projects, "God Header Files" are a significant pain point. These are header files that grow to encompass a vast number of declarations, macros, and data structures. When such a file is modified, it triggers recompilation of a huge portion of the codebase, leading to unbearable build times and making code maintenance a chore. Existing "God Class" refactoring methods aren't suitable because they don't account for the crucial build dependencies across the entire system, nor do they adequately handle the potential for cyclic dependencies that can arise when breaking down header files. This paper aims to solve this by proposing a method to intelligently decompose these monolithic header files into smaller, more manageable units.
Methods
The core of the proposed solution is a multi-view graph clustering approach. Here's a breakdown:
- Code Element Graph Construction: They first parse the God Header File to extract code elements (macros, types, functions) and represent their relationships as a graph. Three types of relationships are considered:
- Dependency: One element uses another.
- Semantic: Textual similarity of identifiers.
- Co-usage: How often elements appear together across source files, reflecting build dependencies.
- Dependency-Based Graph Coarsening: To preserve strong structural relationships, they merge code elements that have high dependency weights, creating a "coarsened" graph. This ensures tightly coupled elements stay together.
- Multi-View Graph Clustering: They then apply a novel algorithm called DuaLGR to cluster the coarsened graph. This algorithm leverages both semantic and co-usage views (representing different aspects of code relationships) and adaptively weights them to create a consensus graph for clustering. This is key to handling the diverse nature of code relationships.
- Cyclic Dependency Fixing: A crucial step is to ensure the resulting sub-header files have acyclic dependencies. They employ a heuristic algorithm, extending a two-node cycle fixing method, to iteratively resolve any cycles by strategically moving code elements between proposed sub-header files, optimizing for minimal disruption and maximum gain.
Datasets
The authors created two datasets for evaluation:
- Synthetic God Header Files: Artificially generated by merging smaller header files from open-source projects (PolarDB, fontforge, FreeRDP). This dataset is used to evaluate the accuracy of their decomposition against a known ground truth.
- Real-world God Header Files: A collection of 649 God Header Files identified from 203 open-source C projects on GitHub. These files were selected based on having a large number of code elements and a significant file impact, and they come with rich commit histories.
They also built a publicly available benchmark dataset for God Header File decomposition [14].
Key Insights and Ideas
- Build Dependencies Matter: Unlike God Class refactoring, decomposing header files must consider how changes propagate through the build system (co-usage relationships). This is a critical insight that existing methods miss.
- Multi-View Clustering is Key: Different code relationships (dependency, semantic, co-usage) offer complementary information. A multi-view approach, especially one that can adaptively weight these views (like DuaLGR), is more robust than simply combining them with fixed weights.
- Acyclic Dependencies are Non-Negotiable: Cyclic dependencies in header files can lead to compilation errors. A dedicated step to fix these cycles is essential for practical decomposition.
- God Header Files are Widespread: Their preliminary study found that at least 37.5% of analyzed C projects contain God Header Files, highlighting the prevalence and importance of this problem.
Key Results
- Accuracy: Their approach achieved 11.5% higher accuracy (measured by MoJoFM) on synthetic datasets compared to state-of-the-art God Class refactoring methods. It also demonstrated more consistent performance across different projects.
- Architectural Quality: For real-world God Header Files, their decomposition resulted in higher modularity (average improvement of 9.1%) and acyclic dependencies, leading to a simpler and clearer architecture.
- Recompilation Time Reduction: The decomposition significantly reduced recompilation times for historical commits, ranging from 15% to 60%. For one file (extern.h), this translated to saving approximately 60 hours of recompilation over its evolution.
Limitations and Future Work
- Automatic Naming: The current approach doesn't automatically generate descriptive names for the decomposed sub-header files, which would aid comprehension.
- Optimal Subfile Count: While they allow users to specify the number of subfiles, they plan to investigate how to automatically suggest an optimal number.
- Integrating Acyclic Constraint: The current method fixes cycles after clustering. Future work aims to integrate this constraint directly into the clustering process.
- Generalization: While evaluated on diverse datasets, the results might vary for different types of files or algorithms.
- Expert Involvement: For highly complex God Header Files, expert intervention might still be necessary for optimal redesign.
Summary updated