Identifying the semantic and textual differences between two versions of a program

Abstract

Text-based file comparators (e.g., the Unix utility diff), are very general tools that can be applied to arbitrary files. However, using such tools to compare programs can be unsatisfactory because their only notion of change is based on program text rather than program behavior. This paper describes a technique for comparing two versions of a program, determining which program components represents changes, and classifying each changed component as representing either a semantic or a textual change.

References

1. Aho74 Aho, A., E:opcroft, J.E., and Ullman, J., The Design and Analysis of ffompater Algorithms, Addison-Wesley, Reading, MA (1974).
2. Aho86 Aho, A., Sethi, R., and Ullman, J., Compilers: Principles, Techniques and Tools, Addison-Wesley, Reading, MA (1986).
3. Alpern88 Alpem, B., Wegman, M3q., and Zadeck, F.K., "Detecting equality of variables in programs," pp. 1-11 in Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages, (San Diego, CA, Januaxy 13-15, 1988), AC/v{, New York (1988).
4. Cytron89 Cytron, R., Ferrante, j., Rosen, B.K., Wegman, M.N., and Zadeck, K., "An efficient method of computing static single assignment form," pp. 25-35 in Conference Record of the Sixteenth ACM Symposium on Principles of Programming Languages, (Austin, TX, Jan. l 1-13, 1989), ACM, New York, NY (1989).
5. Ferrante87 Ferrante, I., Ottenstem, K., and Warren, J., "The program dependence graph and its use in optimization," ACM Transactions on Progranunmg Languages and Systems, (1987).
6. Hopcroft71 Hopcroft, J.E., "An n log n algorithm for minimizing the states of a finite automaton," The Theory of Machines and C omputat/ons, pp. 189-196 ( 1971).
7. Horwitz89a Horwitz, S., "Identifying the semantic and textual differences between two versions of a program," Technical Report 895, Department of Computer Sciences, University of Wisconsin---Madison (November, 1989).
8. Horwitz89 Horwitz, S., Prim, l., and Reps, T., "Integrating noninterfering versions of programs," ACM Transactions on Programming Languages and Systems 11(3)pp. 345-387 (July, 1989).
9. Horwitz90 Horwitz, S. and Reps, T., "Efficient comparison of program slices," Report in preparation. (1990).
10. Kuck81 Kuck, DJ., Kuhn, R.H., Leasure, B., Padua, D.A., and Wolfe, M., "Dependence graphs and compiler optimizations," pp. 207-218 in Conference Record of the Eighth ACM Symposium on Principles of Programming Languages, (Williamsburg, VA, January 26-28, 1981), ACM, New York (198D.
11. Lu79 Lu, S.Y., "A tree-to-tree distance and its application to cluster analysis," IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-i(2) pp. 219-224 (April, 1979).
12. Miller85 Miller, W. and Myers, E.W., "A file comparison program," Software- Practice and Experience 15(ll)pp. 1025-1040 (November, 1985).
13. Nakatsu82 Nakatsu, N., Kambayashi, Y., and Yajima, S., "A longest common subsequence algorithm suitable for similar text strings," Acta lnformatica 18 pp. 171-179 (1982). (as cited in {Miller85})
14. Ottenstein84 Ottenstein, KJ. and Ottenstein, L.M., "rhe program dependence graph in a software development environment," Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, (Pittsburgh, PA, April 23-25, 1984), ACM SIGPLAN Notices 19(5) pp. 177-184 (May, 1984).
15. Rosen88 Rosen, B., Wcgman, M.N., and Zadeck, F.K., "Global value numbers and redundant computations," pp. 12-27 in Confer. ence Record of the Fifteenth ACM Symposium on Principles of Progranvning languages, (San Diego, CA, January 13-15, 1988), ACM, New York (1988).
16. Sankoff72 Sankoff, D., "Matching sequences under deletionfmsertion constraints," Proc. Nat. Acad. Sci. 69(1)pp. 4-6 (January, 1972).
17. Selkow77 Selkow, S.M., "The tree-to-tree editing problem," Information Processing Letters 6(6) pp. 184-186 (December, 1977).
18. Shapiro70 Shapiro, R. M. and Saint, H., "Ttte representation of algo. rithms," Technical Reprot CA-7002-1432, Massachusetts Computer Associates (February, 1970). (as cited in {Alpem88, Roson88})
19. Tai79 Tai, K.C., "The tree-to-tree correction problem," JACM 260) pp. 422-433 (July, 1979).
20. Tichy84 Tichy, W., 'Whe string-to-string correction problem with block moves," ACM Trtmsactions on Computer Systems 2(4) pp. 309-321 (November, 1984).
21. Wagner74 Wagner, R.A. and Fischer, M.J., "The string-to-string correction problem," JACM 21(1)pp. 168-173 (January, 1974).
22. Weiser84 Weiser, M., "Program slicing," IEEE Transactions on Software Engineering SE-10(4) pp. 352-357 (July, 1984).
23. Yang89 Yang, W., Horwitz, S., and Reps, T., "Detecting program components with equivalent behaviors," Technical Report 840, Department of Computer Sciences, University of Wisconsin, Madison, WI (April, 1989).
24. Zhang89 Zhang, K. and Shasha, D., "Simple fast algorithms for the editing distance between trees and related problems," to appear in SIAM J. of Computing, (1989).

Index Terms

• Information systems

  • Information storage systems

    • Storage management

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Software and its engineering

  • Software creation and management

    • Designing software

      • Software implementation planning

        • Software design techniques

    • Software development process management

  • Software notations and tools

    • Formal language definitions

      • Semantics

    • General programming languages

      • Language features

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • File systems management

        • Memory management

• Theory of computation

  • Randomness, geometry and discrete structures

  • Semantics and reasoning

    • Program constructs

    • Program semantics