Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Operation-Based, Fine-Grained Version Control Model for Tree-Based Representation

  • Conference paper

Abstract

Existing version control systems are often based on text line-oriented models for change representation, which do not facilitate software developers in understanding code evolution. Other advanced change representation models that encompass more program semantics and structures are still not quite practical due to their high computational complexity. This paper presents OperV, a novel operation-based version control model that is able to support both coarse and fine levels of granularity in program source code. In OperV, a software system is represented by a project tree whose nodes represent all program entities, such as packages, classes, methods, etc. The changes of the system are represented via edit operations on the tree. OperV also provides the algorithms to differ, store, and retrieve the versions of such entities. These algorithms are based on the mapping of the nodes between versions of the project tree. This mapping technique uses 1) divide-and-conquer technique to map coarse- and fine-grained entities separately, 2) unchanged text regions to map unchanged leaf nodes, and 3) structure-based similarity of the sub-trees to map their root nodes bottom-up and then top-down. The empirical evaluation of OperV has shown that it is scalable, efficient, and could be useful in understanding program evolution.

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

  1. Nguyen, H.A., Nguyen, T.T., Pham, N.H., Al-Kofahi, J.M., Nguyen, T.N.: Accurate and efficient structural characteristic feature extraction for clone detection. In: Chechik, M., Wirsing, M. (eds.) FASE 2009. LNCS, vol. 5503, pp. 440–455. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  2. Nguyen, T.N., Munson, E.V., Boyland, J.T., Thao, C.: An Infrastructure for Development of Multi-level, Object-Oriented Config. Management Services. In: ICSE 2005, pp. 215–224. ACM, New York (2005)

    Chapter  Google Scholar 

  3. Morse, T.: CVS. Linux Journal 1996(21es), 3 (1996)

    Google Scholar 

  4. Tichy, W.: RCS - A System for Version Control. Software - Practice and Experience 15(7), 637–654 (1985)

    Article  Google Scholar 

  5. Subversion.tigris.org.,http://subversion.tigris.org/

  6. Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest common subsequences. Communication of ACM 20(5), 350–353 (1977)

    Article MATH MathSciNet  Google Scholar 

  7. Canfora, G., Cerulo, L., Di Penta, M.: Ldiff: An enhanced line differencing tool. In: ICSE 2009, pp. 595–598. IEEE CS, Los Alamitos (2009)

    Google Scholar 

  8. Myers, E.W.: An O(nd) Difference Algorithm and Its Variations. Algorithmica 1, 251–266 (1986)

    Article MATH MathSciNet  Google Scholar 

  9. Tichy, W.F.: The string-to-string correction problem with block moves. ACM Trans. Comput. Syst. 2(4), 309–321 (1984)

    Article MathSciNet  Google Scholar 

  10. Wang, Y., DeWitt, D.J., Cai, J.Y.: X-Diff: An Effective Change Detection Algorithm for XML Documents. In: ICDE 2003, pp. 519–530. IEEE CS, Los Alamitos (2003)

    Google Scholar 

  11. Lin, Y., Reiss, S.: Configuration management with logical structures. In: ICSE 1996, pp. 298–307 (1996)

    Google Scholar 

  12. Magnusson, B., Asklund, U.: Fine-grained revision control of Configurations in COOP/Orm. In: 6th Software Configuration Management Workshop (SCM-6), pp. 31–47. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  13. Asklund, U., Bendix, L., Christensen, H., Magnusson, B.: The Unified Extensional Versioning Model. In: 9th Software Configuration Management Workshop (SCM-9). Springer, Heidelberg (1999)

    Google Scholar 

  14. Chu-Carroll, M.C., Wright, J., Shields, D.: Supporting aggregation in fine grained software configuration management. In: FSE 2002, pp. 99–108. ACM Press, New York (2002)

    Google Scholar 

  15. Ohst, D., Kelter, U.: A fine-grained version and configuration model in analysis and design. In: ICSM 2002. IEEE CS, Los Alamitos (2002)

    Google Scholar 

  16. Conradi, R., Westfechtel, B.: Version models for software configuration management. ACM Computing Surveys (CSUR) 30(2), 232–282 (1998)

    Article  Google Scholar 

  17. Fluri, B., Wuersch, M., Pinzger, M., Gall, H.: Change distilling: Tree differencing for fine-grained source code change extraction. IEEE Transactions on Software Engineering 33(11), 725–743 (2007)

    Article  Google Scholar 

  18. Chawathe, S.S., Rajaraman, A., Garcia-Molina, H., Widom, J.: Change detection in hierarchically structured information. In: SIGMOD 1996, pp. 493–504. ACM, New York (1996)

    Chapter  Google Scholar 

  19. Nguyen, T.T., Nguyen, H.A., Pham, N.H., Al-Kofahi, J.M., Nguyen, T.N.: Clone-aware Configuration Management. In: The 24th ACM/IEEE International Conference on Automated Software Engineering (ASE 2009). IEEE CS Press, Los Alamitos (2009)

    Google Scholar 

  20. Bille, P.: A survey on tree edit distance and related problems. Theor. Comput. Sci. 337(1-3), 217–239 (2005)

    Article MATH MathSciNet  Google Scholar 

  21. Zhang, K.: Algorithms for the constrained editing distance between ordered labeled trees and related problems. Pattern Recognition 28, 463–474 (1995)

    Article  Google Scholar 

  22. Selkow, S.: The tree-to-tree editing problem. Info. Processing Letters 6(6), 184–186 (1977)

    Article MATH MathSciNet  Google Scholar 

  23. Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal of Computing 18, 1245–1262 (1989)

    Article MATH MathSciNet  Google Scholar 

  24. Asklund, U.: Identifying conflicts during structural merge. In: Proceedings of the Nordic Workshop on Programming Environment Research (1994)

    Google Scholar 

  25. Westfechtel, B.: Structure-oriented merging of revisions of software documents. In: Proceedings of Workshop on Software Configuration Management, pp. 68–79. ACM, New York (1991)

    Chapter  Google Scholar 

  26. Robbes, R., Lanza, M., Lungu, M.: An Approach to Software Evolution Based on Semantic Change. In: Dwyer, M.B., Lopes, A. (eds.) FASE 2007. LNCS, vol. 4422, pp. 27–41. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  27. Lippe, E., van Oosterom, N.: Operation-based merging. In: SDE-5, pp. 78–87. ACM Press, New York (1992)

    Chapter  Google Scholar 

  28. Edwards, W.: Flexible Conflict Detection and Management in Collaborative Applications. In: Proceedings of UIST (1997)

    Google Scholar 

  29. Ekman, T., Asklund, U.: Refactoring-aware versioning in Eclipse. Electronic Notes in Theoretical Computer Science 107, 57–69 (2004)

    Article  Google Scholar 

  30. Gode, N., Koschke, R.: Incremental Clone Detection. In: CSMR 2009, pp. 219–228. IEEE CS, Los Alamitos (2009)

    Google Scholar 

  31. Sager, T., Bernstein, A., Pinzger, M., Kiefer, C.: Detecting similar Java classes using tree algorithms. In: MSR 2006, pp. 65–71. ACM, New York (2006)

    Chapter  Google Scholar 

  32. Baxter, I.D., Yahin, A., Moura, L., Sant’Anna, M., Bier, L.: Clone detection using abstract syntax trees. In: ICSM 1998, pp. 368–377. IEEE CS, Los Alamitos (1998)

    Google Scholar 

  33. Horwitz, S.: Identifying the semantic and textual differences between two versions of a program. In: PLDI 1990, pp. 234–245. ACM, New York (1990)

    Chapter  Google Scholar 

  34. Apiwattanapong, T., Orso, A., Harrold, M.J.: Jdiff: A differencing technique and tool for object-oriented programs. Automated Software Engg. 14(1), 3–36 (2007)

    Article  Google Scholar 

  35. Raghavan, S., Rohana, R., Leon, D., Podgurski, A., Augustine, V.: Dex: A semantic-graph differencing tool for studying changes in large code bases. In: ICSM 2004, pp. 188–197. IEEE, Los Alamitos (2004)

    Google Scholar 

  36. Lie, A., Conradi, R., Didriksen, T., Karlsson, E., Hallsteinsen, S., Holager, P.: Change oriented versioning. In: Proceedings of the Second European Software Engineering Conference (1989)

    Google Scholar 

  37. Cronk, R.: Tributaries and deltas. BYTE, pp. 177–186 (January 1992)

    Google Scholar 

  38. Zelller, A., Snelting, G.: Unified versioning through feature logic. ACM Transaction on Software Engineering and Methodology 6, 397–440 (1997)

    Google Scholar 

  39. Maletic, J., Collard, M.: Supporting Source Code Difference Analysis. In: ICSM 2004. IEEE CS, Los Alamitos (2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Electrical and Computer Engineering Department, Iowa State University, USA

    Tung Thanh Nguyen, Hoan Anh Nguyen, Nam H. Pham & Tien N. Nguyen

Authors
  1. Tung Thanh Nguyen

    You can also search for this author inPubMed Google Scholar

  2. Hoan Anh Nguyen

    You can also search for this author inPubMed Google Scholar

  3. Nam H. Pham

    You can also search for this author inPubMed Google Scholar

  4. Tien N. Nguyen

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University College London, WC1E 6BT, London, UK

    David S. Rosenblum

  2. Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, 35032, Marburg, Germany

    Gabriele Taentzer

Rights and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Nguyen, T.T., Nguyen, H.A., Pham, N.H., Nguyen, T.N. (2010). Operation-Based, Fine-Grained Version Control Model for Tree-Based Representation. In: Rosenblum, D.S., Taentzer, G. (eds) Fundamental Approaches to Software Engineering. FASE 2010. Lecture Notes in Computer Science, vol 6013. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12029-9_6

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp