Abstract
In many projects, lexical preprocessors are used to manage different variants of the project (using conditional compilation) and to define compile-time code transformations (using macros). Unfortunately, while being a simple way to implement variability, conditional compilation and lexical macros hinder automatic analysis, even though such analysis is urgently needed to combat variability-induced complexity. To analyze code with its variability, we need to parse it without preprocessing it. However, current parsing solutions use unsound heuristics, support only a subset of the language, or suffer from exponential explosion. As part of the TypeChef project, we contribute a novel variability-aware parser that can parse almost all unpreprocessed code without heuristics in practicable time. Beyond the obvious task of detecting syntax errors, our parser paves the road for further analysis, such as variability-aware type checking. We implement variability-aware parsers for Java and GNU C and demonstrate practicability by parsing the product line MobileMedia and the entire X86 architecture of the Linux kernel with 6065 variable features.
- B. Adams, W. De Meuter, H. Tromp, and A. E. Hassan. Can we refactor conditional compilation into aspects? In Proc. Int'l Conf. Aspect-Oriented Software Development (AOSD), pages 243--254. ACM Press, 2009. Google ScholarDigital Library
- S. Apel and C. Kästner. An overview of feature-oriented software development. Journal of Object Technology (JOT), 8(5):49--84, 2009.Google Scholar
- S. Apel, C. Kästner, A. Größlinger, and C. Lengauer. Type safety for feature-oriented product lines. Automated Software Engineering, 17(3):251--300, 2010. Google ScholarDigital Library
- L. Aversano, M. D. Penta, and I. D. Baxter. Handling preprocessor-conditioned declarations. In Proc. Int'l Workshop Source Code Analysis and Manipulation (SCAM), pages 83--92. IEEE Computer Society, 2002. Google ScholarDigital Library
- G. J. Badros and D. Notkin. A framework for preprocessor-aware C source code analysis. Software: Practice and Experience, 30(8):907--924, 2000. Google ScholarDigital Library
- I. Baxter and M. Mehlich. Preprocessor conditional removal by simple partial evaluation. In Proc. Working Conf. Reverse Engineering (WCRE), pages 281--290. IEEE Computer Society, 2001. Google ScholarDigital Library
- D. Benavides, S. Seguraa, and A. Ruiz-Cortés. Automated analysis of feature models 20 years later: A literature review. Information Systems, 35(6):615--636, 2010. Google ScholarDigital Library
- T. Berger, S. She, K. Czarnecki, and A. Wasowski. Feature-to-code mapping in two large product lines. In Proc. Int'l Software Product Line Conference (SPLC), pages 498--499. Springer-Verlag, 2010. Google ScholarDigital Library
- T. Berger, S. She, R. Lotufo, A. Wa (sowski, and K. Czarnecki. Variability modeling in the real: A perspective from the operating systems domain. In Proc. Int'l Conf. Automated Software Engineering (ASE), pages 73--82. ACM Press, 2010. Google ScholarDigital Library
- D. Beuche, H. Papajewski, and W. Schröder-Preikschat. Variability management with feature models. Sci. Comput. Program., 53(3):333--352, 2004. Google ScholarDigital Library
- BigLevel Software, Inc., Austin, TX. BigLever Software Gears: User's Guide, version 5.5.2 edition, 2008.Google Scholar
- A. Classen, P. Heymans, P.-Y. Schobbens, A. Legay, and J.-F. Raskin. Model checking lots of systems: Efficient verification of temporal properties in software product lines. In Proc. Int'l Conf. Software Engineering (ICSE), pages 335--344. ACM Press, 2010. Google ScholarDigital Library
- K. Czarnecki and M. Antkiewicz. Mapping features to models: A template approach based on superimposed variants. In Proc. Int'l Conf. Generative Programming and Component Engineering (GPCE), volume 3676 of Lecture Notes in Computer Science, pages 422--437. Springer-Verlag, 2005. Google ScholarDigital Library
- K. Czarnecki and K. Pietroszek. Verifying feature-based model templates against well-formedness OCL constraints. In Proc. Int'l Conf. Generative Programming and Component Engineering (GPCE), pages 211--220. ACM Press, 2006. Google ScholarDigital Library
- S. Ducasse and D. Pollet. Software architecture reconstruction: A process-oriented taxonomy. IEEE Trans. Softw. Eng. (TSE), 35:573--591, 2009. Google ScholarDigital Library
- M. Ernst, G. Badros, and D. Notkin. An empirical analysis of C preprocessor use. IEEE Trans. Softw. Eng. (TSE), 28(12):1146-- 1170, 2002. Google ScholarDigital Library
- M. Erwig and E. Walkingshaw. The choice calculus: A representation for software variation. ACM Trans. Softw. Eng. Methodol. (TOSEM), 21(1), 2011. to appear. Google ScholarDigital Library
- J.-M. Favre. Understanding-in-the-large. In Proc. Int'l Workshop on Program Comprehension, page 29. IEEE Computer Society, 1997. Google ScholarDigital Library
- E. Figueiredo et al. Evolving software product lines with aspects: An empirical study on design stability. In Proc. Int'l Conf. Software Engineering (ICSE), pages 261--270. ACM Press, 2008. Google ScholarDigital Library
- B. Ford. Packrat parsing: Simple, powerful, lazy, linear (functional pearl). In Proc. Int'l Conf. Functional Programming (ICFP), pages 36--47. ACM Press, 2002. Google ScholarDigital Library
- D. Ganesan, M. Lindvall, C. Ackermann, D. McComas, and M. Bartholomew. Verifying architectural design rules of the flight software product line. In Proc. Int'l Software Product Line Conference (SPLC), pages 161--170. Carnegie Mellon University, 2009. Google ScholarDigital Library
- A. Garrido. Program Refactoring in the Presence of Preprocessor Directives. PhD thesis, University of Illinois at Urbana-Champaign, 2005. Google ScholarDigital Library
- A. Garrido and R. Johnson. Analyzing multiple configurations of a C program. In Proc. Int'l Conf. Software Maintenance (ICSM), pages 379--388. IEEE Computer Society, 2005. Google ScholarDigital Library
- P. Gazzillo and R. Grimm. Parsing all of C by taming the preprocessor. Technical Report TR2011-939, Computer Science Department, New York University, 2011.Google Scholar
- P. G. Giarrusso. TypeChef: Towards correct variability analysis of unpreprocessed C code for software product lines. Master's thesis (tesi di diploma di licenza di 2° livello), Scuola Superiore di Catania, 2011.Google Scholar
- F. Heidenreich, J. Kopcsek, and C. Wende. FeatureMapper: Mapping features to models. In Comp. Int'l Conf. Software Engineering (ICSE), pages 943--944. ACM Press, 2008. Google ScholarDigital Library
- Y. Hu, E. Merlo, M. Dagenais, and B. Laguë. C/C++ conditional compilation analysis using symbolic execution. In Proc. Int'l Conf. Software Maintenance (ICSM), pages 196-- 206. IEEE Computer Society, 2000. Google ScholarDigital Library
- G. Hutton and E. Meijer. Monadic parsing in Haskell. J. Functional Programming, 8(4):437--444, July 1998. Google ScholarDigital Library
- International Organization for Standardization. ISO/IEC 9899-1999: Programming Languages--C, 1999.Google Scholar
- C. Kästner, S. Apel, and M. Kuhlemann. Granularity in software product lines. In Proc. Int'l Conf. Software Engineering (ICSE), pages 311--320. ACM Press, 2008. Google ScholarDigital Library
- C. Kästner, S. Apel, and M. Kuhlemann. A model of refactoring physically and virtually separated features. In Proc. Int'l Conf. Generative Programming and Component Engineering (GPCE), pages 157--166. ACM Press, 2009. Google ScholarDigital Library
- C. Kästner, S. Apel, T. Thüm, and G. Saake. Type checking annotation-based product lines. ACM Trans. Softw. Eng. Methodol. (TOSEM), 2011. accepted for publication. Google ScholarDigital Library
- C. Kästner, P. G. Giarrusso, and K. Ostermann. Partial preprocessing of C code for variability analysis. In Proc. Int'l Workshop on Variability Modelling of Software-intensive Systems (VaMoS), pages 137--140. ACM Press, 2011. Google ScholarDigital Library
- G. Kiczales, J. Lamping, A. Menhdhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In Proc. Europ. Conf. Object-Oriented Programming (ECOOP), volume 1241 of Lecture Notes in Computer Science, pages 220--242. Springer-Verlag, 1997.Google ScholarCross Ref
- M. Krone and G. Snelting. On the inference of configuration structures from source code. In Proc. Int'l Conf. Software Engineering (ICSE), pages 49--57. IEEE Computer Society, 1994. Google ScholarDigital Library
- B. Kullbach and V. Riediger. Folding: An approach to enable program understanding of preprocessed languages. In Proc. Working Conf. Reverse Engineering (WCRE), page 3. IEEE Computer Society, 2001. Google ScholarDigital Library
- M. Latendresse. Rewrite systems for symbolic evaluation of C-like preprocessing. In Proc. European Conf. on Software Maintenance and Reengineering (CSMR), pages 165--173. IEEE Computer Society, 2004. Google ScholarDigital Library
- D. Le Berre, A. Parrain, O. Roussel, and L. Sais. SAT4J: A satisfiability library for Java, 2011. http://www.sat4j. org.Google Scholar
- J. Liebig, S. Apel, C. Lengauer, C. Kästner, and M. Schulze. An analysis of the variability in forty preprocessor-based software product lines. In Proc. Int'l Conf. Software Engineering (ICSE), pages 105--114. ACM Press, 2010. Google ScholarDigital Library
- J. Liebig, C. Kästner, and S. Apel. Analyzing the discipline of preprocessor annotations in 30 million lines of C code. In Proc. Int'l Conf. Aspect-Oriented Software Development (AOSD), 2011. Google ScholarDigital Library
- J. I. Maletic, M. L. Collard, and A. Marcus. Source code files as structured documents. In Proc. Int'l Workshop on Program Comprehension (IWPC), page 289. IEEE Computer Society, 2002. Google ScholarDigital Library
- B. McCloskey and E. Brewer. ASTEC: A new approach to refactoring C. In Proc. Europ. Software Engineering Conf./Foundations of Software Engineering (ESEC/FSE), pages 21--30. ACM Press, 2005. Google ScholarDigital Library
- M. Mendonça, A. Wa (sowski, and K. Czarnecki. SAT-based analysis of feature models is easy. In Proc. Int'l Software Product Line Conference (SPLC), pages 231--240. Carnegie Mellon University, 2009. Google ScholarDigital Library
- M. Odersky, L. Spoon, and B. Venners. Programming in Scala. Artima Press, Mountain View, CA, 2008. Google ScholarDigital Library
- J. Overbey and R. Johnson. Generating rewritable abstract syntax trees. In Proc. Int'l Conf. Software Language Engineering (SLE), volume 5452 of Lecture Notes in Computer Science, pages 114--133. Springer-Verlag, 2008.Google Scholar
- Y. Padioleau. Parsing C/C++ code without pre-processing. In Proc. Int'l Conf. Compiler Construction (CC), pages 109--125. Springer-Verlag, 2009. Google ScholarDigital Library
- Y. Padioleau, J. Lawall, R. R. Hansen, and G. Muller. Documenting and automating collateral evolutions in Linux device drivers. In Proc. European Conference on Computer Systems (EuroSys), pages 247--260. ACM Press, 2008. Google ScholarDigital Library
- N. Palix, G. Thomas, S. Saha, C. Calvès, J. Lawall, and G. Muller. Faults in Linux: Ten years later. In Proc. Int'l Conf. Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 305--318. ACM Press, 2011. Google ScholarDigital Library
- T. T. Pearse and P. W. Oman. Experiences developing and maintaining software in a multi-platform environment. In Proc. Int'l Conf. Software Maintenance (ICSM), pages 270-- 277. IEEE Computer Society, 1997. Google ScholarDigital Library
- M. Platoff, M. Wagner, and J. Camaratta. An integrated program representation and toolkit for the maintenance of C programs. In Proc. Int'l Conf. Software Maintenance (ICSM), pages 192--137. IEEE Computer Society, 1991.Google ScholarCross Ref
- K. Pohl, G. Böckle, and F. J. van der Linden. Software Product Line Engineering: Foundations, Principles and Techniques. Springer-Verlag, Berlin/Heidelberg, 2005. Google ScholarDigital Library
- H. Post and C. Sinz. Configuration lifting: Verification meets software configuration. In Proc. Int'l Conf. Automated Software Engineering (ASE), pages 347--350. IEEE Computer Society, 2008. Google ScholarDigital Library
- pure-systems GmbH, Magdeburg. pure::variants User's Guide, version 3.0 edition, 2009.Google Scholar
- S. She, R. Lotufo, T. Berger, A. Wa (sowski, and K. Czarnecki. Reverse engineering feature models. In Proc. Int'l Conf. Software Engineering (ICSE). ACM Press, 2011. to appear. Google ScholarDigital Library
- S. She, R. Lotufo, T. Berger, A. Wa (sowski, and K. Czarnecki. The variability model of the Linux kernel. In Proc. Int'l Workshop on Variability Modelling of Software-intensive Systems (VaMoS), pages 45--51. University of Duisburg-Essen, 2010.Google Scholar
- C. Simonyi. The death of computer languages, the birth of intentional programming. In NATO Science Committee Conference, 1995.Google Scholar
- J. Sincero, R. Tartler, D. Lohmann, and W. Schröder-Preikschat. Efficient extraction and analysis of preprocessor-based variability. In Proc. Int'l Conf. Generative Programming and Component Engineering (GPCE), pages 33--42. ACM Press, 2010. Google ScholarDigital Library
- S. S. Somé and T. C. Lethbridge. Parsing minimization when extracting information from code in the presence of conditional compilation. In Proc. Int'l Workshop on Program Comprehension (IWPC), pages 118--125. IEEE Computer Society, 1998. Google ScholarDigital Library
- H. Spencer and G. Collyer. #ifdef considered harmful or portability experience with C news. In Proc. USENIX Conf., pages 185--198. USENIX Association, 1992.Google Scholar
- D. Spinellis. Global analysis and transformations in preprocessed languages. IEEE Trans. Softw. Eng. (TSE), 29(11):1019-- 1030, 2003. Google ScholarDigital Library
- R. Tartler, D. Lohmann, J. Sincero, and W. Schröder-Preikschat. Feature consistency in compile-time-configurable system software: Facing the Linux 10,000 feature problem. In Proc. European Conference on Computer Systems (EuroSys), pages 47--60. ACM Press, 2011. Google ScholarDigital Library
- S. Thaker, D. Batory, D. Kitchin, and W. Cook. Safe composition of product lines. In Proc. Int'l Conf. Generative Programming and Component Engineering (GPCE), pages 95--104. ACM Press, 2007. Google ScholarDigital Library
- M. Tomita. An efficient context-free parsing algorithm for natural languages. In Proc. Int'l Joint Conf. on Artificial Intelligence (IJCAI), pages 756--764. Morgan Kaufmann, 1985. Google ScholarDigital Library
- M. Vittek. Refactoring browser with preprocessor. In Proc. European Conf. on Software Maintenance and Reengineering (CSMR), pages 101--110. IEEE Computer Society, 2003. Google ScholarDigital Library
- K. Vo and Y. Chen. Incl: A tool to analyze include files. In Proc. USENIX Conference, pages 199--208. USENIX Association, 1992.Google Scholar
- M. Voelter. Embedded software development with projectional language workbenches. In Proc. Int'l Conf. Model Driven Engineering Languages and Systems (MoDELS), volume 6395 of Lecture Notes in Computer Science, pages 32--46. Springer-Verlag, 2010. Google ScholarDigital Library
- P. Wadler. How to replace failure by a list of successes. In Proc. Conf. Functional Programming Languages and Computer Architecture (FPCA), pages 113--128. Springer-Verlag, 1985. Google ScholarDigital Library
- D. Weise and R. Crew. Programmable syntax macros. In Proc. Conf. Programming Language Design and Implementation (PLDI), pages 156--165. ACM Press, 1993. Google ScholarDigital Library
Index Terms
- Variability-aware parsing in the presence of lexical macros and conditional compilation
Recommendations
Variability-aware parsing in the presence of lexical macros and conditional compilation
OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applicationsIn many projects, lexical preprocessors are used to manage different variants of the project (using conditional compilation) and to define compile-time code transformations (using macros). Unfortunately, while being a simple way to implement variability,...
A variability-aware module system
OOPSLA '12: Proceedings of the ACM international conference on Object oriented programming systems languages and applicationsModule systems enable a divide and conquer strategy to software development. To implement compile-time variability in software product lines, modules can be composed in different combinations. However, this way, variability dictates a dominant ...
A variability-aware module system
OOPSLA '12Module systems enable a divide and conquer strategy to software development. To implement compile-time variability in software product lines, modules can be composed in different combinations. However, this way, variability dictates a dominant ...
Comments