Abstract
Source code querying tools allow programmers to explore relations between different parts of the code base. This paper describes such a tool, named codeQuest. It combines two previous proposals, namely the use of logic programming and database systems.
As the query language we use safe Datalog, which was originally introduced in the theory of databases. That provides just the right level of expressiveness; in particular recursion is indispensable for source code queries. Safe Datalog is like Prolog, but all queries are guaranteed to terminate, and there is no need for extra-logical annotations.
Our implementation of Datalog maps queries to a relational database system. We are thus able to capitalise on the query optimiser provided by such a system. For recursive queries we implement our own optimisations in the translation from Datalog to SQL. Experiments confirm that this strategy yields an efficient, scalable code querying system.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Eclipse, http://www.eclipse.org
The TyRuBa metaprogramming system, http://tyruba.sourceforge.net/
codequesta, http://progtools.comlab.ox.ac.uk/projects/codequest/
Abiteboul, S., Buneman, P., Suciu, D.: Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann Publishers, San Francisco (2000)
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Abraido-Fandino, L.: An overview of Refine 2.0. In: Procs. of the Second International Symposium on Knowledge Engineering and Software Engineering (1987)
Apt, K.R., Bol, R.N.: Logic programming and negation: A survey. Journal of Logic Programming 19/20, 9–71 (1994)
Avgustinov, P., Christensen, A.S., Hendren, L., Kuzins, S., Lhoták, J., Lhoták, O., de Moor, O., Sereni, D., Sittampalam, G., Tibble, J.: abc: An extensible AspectJ compiler. In: Aspect-Oriented Software Development (AOSD), pp. 87–98. ACM Press, New York (2005)
Backhouse, R., Hoogendijk, P.: Elements of a relational theory of datatypes. In: Möller, B., Schuman, S., Partsch, H. (eds.) Formal Program Development. LNCS, vol. 755, pp. 7–42. Springer, Heidelberg (1993)
Bancilhon, F., Maier, D., Sagiv, Y., Ullman, J.D.: Magic sets and other strange ways to implement logic programs. In: Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Cambridge, Massachusetts, March 24-26, pp. 1–16. ACM, New York (1986)
Cast. Company website at: http://www.castsoftware.com
Chen, Y., Nishimoto, M., Ramamoorthy, C.V.: The C information abstraction system. IEEE Transactions on Software Engineering 16(3), 325–334 (1990)
Consens, M., Mendelzon, A., Ryman, A.: Visualizing and querying software structures. In: ICSE 1992: Proceedings of the 14th international conference on Software engineering, pp. 138–156. ACM Press, New York (1992)
Crew, R.F.: ASTLOG: A language for examining abstract syntax trees. In: USENIX Conference on Domain-Specific Languages, pp. 229–242 (1997)
Dawson, S., Ramakrishnan, C.R., Warren, D.S.: Practical program analysis using general purpose logic programming systems. In: ACM Symposium on Programming Language Design and Implementation, pp. 117–126. ACM Press, New York (1996)
Doornbos, H., Backhouse, R.C., van der Woude, J.: A calculational approach to mathematical induction. Theoretical Computer Science 179(1–2), 103–135 (1997)
Eichberg, M., Haupt, M., Mezini, M., Schäfer, T.: Comprehensive software understanding with sextant. In: ICSM 2005: Proceedings of the 21st IEEE International Conference on Software Maintenance (ICSM 2005), Washington, DC, USA, September 2005, pp. 315–324. IEEE Computer Society Press, Los Alamitos (2005)
Gallaire, H., Minker, J.: Logic and Databases. Plenum Press, New York (1978)
Hanenberg, S., Kniesel, G., Rho, T.: Evolvable pattern implementations need generic aspects. In: Proc. of ECOOP 2004 Workshop on Reflection, AOP and Meta-Data for Software Evolution, June 2004, pp. 116–126 (2004)
Gybels, K., Brichau, J.: Arranging language features for more robust pattern-based crosscuts. In: 2nd International Conference on Aspect-oriented Software Development, pp. 60–69. ACM Press, New York (2003)
Hajiyev, E.: CodeQuest: Source Code Querying with Datalog. MSc Thesis, Oxford University Computing Laboratory (September 2005), Available at http://progtools.comlab.ox.ac.uk/projects/codequest/
Janzen, D., de Volder, K.: Navigating and querying code without getting lost. In: 2nd International Conference on Aspect-Oriented Software Development, pp. 178–187 (2003)
Jarzabek, S.: Design of flexible static program analyzers with PQL. IEEE Transactions on Software Engineering 24(3), 197–215 (1998)
Javey, S., Mitsui, K., Nakamura, H., Ohira, T., Yasuda, K., Kuse, K., Kamimura, T., Helm, R.: Architecture of the XL C++ browser. In: CASCON 1992: Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, pp. 369–379. IBM Press (1992)
Ježek, K., Toncar, V.: Experimental deductive database. In: Workshop on Information Systems Modelling, pp. 83–90 (1998)
Kiczales, G., Hilsdale, E., Hugunin, J., Kersten, M., Palm, J., Griswold, W.G.: An Overview of AspectJ. In: Knudsen, J.L. (ed.) ECOOP 2001. LNCS, vol. 2072, pp. 327–353. Springer, Heidelberg (2001)
Knaster, B.: Un théorème sur les fonctions d’ensembles. Annales de la Societé Polonaise de Mathematique 6, 133–134 (1928)
Koymen, K.: A datalog interface for SQL (abstract). In: CSC 1990: Proceedings of the 1990 ACM annual conference on Cooperation, p. 422. ACM Press, New York (1990)
Lam, M.S., Whaley, J., Livshits, V.B., Martin, M.C., Avots, D., Carbin, M., Unkel, C.: Context-sensitive program analysis as database queries. In: Monica, S. (ed.) PODS 2005: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 1–12. ACM Press, New York (2005)
Linton, M.A.: Implementing relational views of programs. In: Henderson, P.B. (ed.) Software Development Environments (SDE), pp. 132–140 (1984)
Martin, M., Livshits, B., Lam, M.S.: Finding application errors using PQL: a program query language. In: Proceedings of the 20th annual ACM SIGPLAN OOPSLA Conference, pp. 365–383 (2005)
McCormick, E., De Volder, K.: JQuery: finding your way through tangled code. In: OOPSLA 2004: Companion to the 19th annual ACM SIGPLAN OOPSLA conference, pp. 9–10. ACM Press, New York (2004)
Nystrom, N., Clarkson, M.R., Myers, A.C.: Polyglot: An Extensible Compiler Framework for Java. In: Hedin, G. (ed.) CC 2003 and ETAPS 2003. LNCS, vol. 2622, pp. 138–152. Springer, Heidelberg (2003)
Paul, S., Prakash, A.: Querying source code using an algebraic query language. IEEE Transactions on Software Engineering 22(3), 202–217 (1996)
Magellan Project (2005) Web page at: http://www.st.informatik.tu-darmstadt.de/static/pages/projects/Magellan/XIRC.html
Reps, T.W.: Demand interprocedural program analysis using logic databases. In: Workshop on Programming with Logic Databases, ILPS, pp. 163–196 (1993)
Sagonas, K., Swift, T., Warren, D.S.: XSB as an efficient deductive database engine. In: SIGMOD 1994: Proceedings of the 1994 ACM SIGMOD international conference on Management of data, pp. 442–453. ACM Press, New York (1994)
Sword, E.: Create a root. combinedplot interface. JFreeChart feature request (2005), http://sourceforge.net/tracker/index.php?func=detail&aid=1234995&group_id=15494&atid=365494
Tarr, P., Harrison, W., Ossher, H.: Pervasive query support in the concern manipulation environment. Technical Report RC23343, IBM Research Division, Thomas J. Watson Research Center (2004)
M. Thompson. Bluephoenix: Application modernization technology audit (2004) Available at: http://www.bitpipe.com/detail/RES/1080665824_99.html
Whaley, J., Avots, D., Carbin, M., Lam, M.S.: Using Datalog with Binary Decision Diagrams for Program Analysis. In: Yi, K. (ed.) APLAS 2005. LNCS, vol. 3780, pp. 97–118. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hajiyev, E., Verbaere, M., de Moor, O. (2006). codeQuest: Scalable Source Code Queries with Datalog. In: Thomas, D. (eds) ECOOP 2006 – Object-Oriented Programming. ECOOP 2006. Lecture Notes in Computer Science, vol 4067. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11785477_2
Download citation
DOI: https://doi.org/10.1007/11785477_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35726-1
Online ISBN: 978-3-540-35727-8
eBook Packages: Computer ScienceComputer Science (R0)