If Your Version Control System Could Talk (cid:2)(cid:2)(cid:2)
`
`Thomas Ball
`Bell Laboratories
`Lucent Technologies
`tball(cid:4)research(cid:3)bell(cid:2)labs(cid:3)com
`
`Jung(cid:2)Min Kim Adam A(cid:3) Porter
`Dept(cid:3) of Computer Sciences
`University of Maryland
`aporter(cid:4)cs(cid:3)umd(cid:3)edu
`
`Harvey P(cid:3) Siy
`Bell Laboratories
`Lucent Technologies
`hpsiy(cid:4)research(cid:3)bell(cid:2)labs(cid:3)com
`
`Abstract
`
`Version control systems VCSs are used to store and
`reconstruct past versions of program source code(cid:4) As a
`by(cid:5)product they also capture a great deal of contextual
`information about each change(cid:4) We will illustrate some
`ways to use this information to better understand a
`program(cid:6)s development history(cid:4)
`
`
`
`Introduction
`
`There are many software(cid:5)based metrics that one may
`use to assess the state of a software system(cid:4) For ex(cid:5)
`ample(cid:7) the McCabe and Halstead software com(cid:5)
`plexity metrics measure aspects of the structure of a
`static snapshot of source code to estimate its complex(cid:5)
`ity(cid:4) By measuring how these metrics change over time(cid:7)
`the hope is that one can identify decaying(cid:13) compo(cid:5)
`nents of a software system that(cid:7) if restructured(cid:7) may
`reduce the development eort needed to maintain and
`extend the system(cid:4)
`Such analyses depend on the ability to recreate snap(cid:5)
`shots of the software at dierent points in time(cid:4) A ver(cid:5)
`sion control system VCS tracks each change a devel(cid:5)
`oper makes to the system and(cid:7) as a result(cid:7) can recreate
`a consistent snapshot at any point in time(cid:4) Examples
`of VCSs include RCS  and SCCS (cid:4) While this basic
`functionality of VCSs is essential for version control and
`measuring the evolution of metrics over time(cid:7) there is
`much data in a VCS that is ignored when simply using
`it to extract snapshots of source code(cid:4)
`In this paper(cid:7) we will examine some of the rich struc(cid:5)
`ture in version control data and show how analysis of
`version control data can illuminate the software devel(cid:5)
`opment process in new ways(cid:4) A VCS tags each change
`with a substantial amount of additional contextual in(cid:5)
`formation(cid:4) Knowing what code was changed(cid:7) when it
`was changed(cid:7) who made the change(cid:7) and so on(cid:7) can
`yield valuable insights into what actually went on in
`the course of code development(cid:7) sometimes better than
`
`Software
`Process
`
`Requirements
`
`Version
`Control
`History
`
`Developers
`
`Implementation
` Technology
`
`Figure (cid:18) Version control history captures interactions
`between various aspects of software development(cid:4)
`
`developers(cid:6) memories(cid:4) VCS data is amenable to com(cid:5)
`pletely automated analysis(cid:7) just as a snapshot of source
`code is amenable to metric analysis(cid:4) Most software
`development organizations employ some form of VCS(cid:4)
`Thus the methods we will outline here have wide appli(cid:5)
`cability to many software projects(cid:4)
`Our framework is to use the data in a VCS referred
`to as the version control history(cid:7) in addition to the
`source code itself(cid:7) to explore the relationships between
`various aspects of software development(cid:4) For example(cid:7)
`the requirements of the software(cid:7) the implementation
`technology used(cid:7) development process followed(cid:7) and the
`organization of the developers have some eect on how
`the software evolved(cid:4) Figure illustrates the idea(cid:4)
`Each of these characteristics is a particular view of
`software development(cid:7) with its own constraints and im(cid:5)
`pact(cid:4) Our thesis is that interactions between these
`views can impact the ecient production of software
`and that the version history data captured in a VCS
`provides a good starting point for exploring many of
`these relationships(cid:4) In our particular example(cid:7) we will
`examine some interesting relationships between the re(cid:5)
`quirements of an optimizing compiler(cid:7) the implementa(cid:5)
`tion technology of C(cid:20)(cid:20)(cid:7) and the desire to have devel(cid:5)
`opers work in parallel(cid:4) We will examine these relation(cid:5)
`ships using visualizations automatically generated from
`the VCS data(cid:4)
`
`GOOGLE EX. 1032
`Google v. Philips
`
`

`

` Version Control Data
`
`We present a very simplied description of some ba(cid:3)
`sic data collected by a VCS(cid:4) Most VCSs operate over
`a set of les containing the text lines of source code(cid:4)
`An atomic change to the program text is captured by
`recording the lines that were deleted and those that
`were added in order to make the change(cid:4) This informa(cid:3)
`tion is usually computed by a le dierencing algorithm
`such as Unix di(cid:8) which compares the previous ver(cid:3)
`sion of a le with the current version(cid:4) Each change has
`associated with it the le that was changed(cid:8) the time
`the change was recorded by the VCS(cid:8) and the name and
`login id of the programmer who made it(cid:8) at a minimum(cid:4)
`In order to make a change to a software system(cid:8) a
`developer may have to modify many program entities
`in many les(cid:4) Most VCSs have the ability to track a
`group of related changes via a modication record MR(cid:8)
`which captures the fact that these changes were made
`for a specic purpose and are thus semantically related(cid:4)
`An MR may have an English abstract associated with
`it that the developer provides(cid:8) describing the purpose
`of the change(cid:4) An MR also may have other data(cid:8) such
`as it(cid:9)s opening time(cid:8) closing time(cid:8) and other status in(cid:3)
`formation approved(cid:8) rejected(cid:4)
`An MR is a set of atomic changes and every atomic
`change has some MR associated with it(cid:4) Thus(cid:8) every
`line of text in any source code snapshot has associated
`with it(cid:10) time of change(cid:8) developer name and login(cid:8) MR
`and related data(cid:4) By analyzing the source code to iden(cid:3)
`tify functions(cid:8) classes or other program entities(cid:8) we can
`then associate the VCS data with these entities as well
`as with source lines(cid:4)
`
` The Project Under Study
`
`We present a brief overview of the project under study(cid:4)
`More details may be found in Ladd and Ramming(cid:4)
`The ESSTM is Lucent Technologies(cid:9) agship localtoll
`switching system(cid:8) containing an estimated million
`lines of code in product and support tools(cid:4) At the
`heart of the ESS software is a distributed relational
`database with information about hardware connections(cid:8)
`software conguration(cid:8) and customers(cid:4) For the switch
`to function properly(cid:8) this data must conform to cer(cid:3)
`tain integrity constraints(cid:4) Some of these are logical
`constraints(cid:19) for example(cid:8) call waiting and call forward(cid:3)
`ingbusy should never be active on the same line(cid:4)(cid:21) Other
`constraints exist to document data design choices re(cid:3)
`dundancy(cid:8) functional dependencies(cid:8) distribution rules
`that support ecient ESS operation and call process(cid:3)
`ing(cid:4)
`PRL is a declarative SQL(cid:3)like language(cid:8) created
`to specify these data integrity constraints(cid:4) PRL spec(cid:3)
`
`ications are translated automatically into data audits
`and transaction guards in C(cid:8) which is then compiled
`on multiple platforms(cid:4) Due to the constantly changing
`integrity constraints to be provided to dierent commu(cid:3)
`nication service providers worldwide(cid:8) compilation speed
`was crucial(cid:4) The generated C code also had to be opti(cid:3)
`mized to make as few disk accesses as possible(cid:4)
`A compiler for PRL called PCC PRL to C Com(cid:3)
`piler was developed in C(cid:23)(cid:23)(cid:4) The compiler follows
`traditional compiler structure and includes lexing(cid:8) pars(cid:3)
`ing(cid:8) semantic and type checking(cid:8) optimization(cid:8) and code
`generation phases(cid:4) The lexing and parsing phases pro(cid:3)
`duce an abstract syntax tree AST over which the other
`phases operate(cid:4)
`For this compiler project(cid:8) we have chosen to study
`the following views(cid:10)
`
` Requirements(cid:3) Build an optimizing compiler for a
`declarative SQL(cid:3)like language
`
` Developers(cid:3) Team of  developers who have to
`coordinate with each other
`
` Implementation technology(cid:3) The C(cid:23)(cid:23) language
`
` Software process(cid:3) Many(cid:8) but not all components
`built in parallel(cid:4)
`
`
`
`Insights Into Compiler Development
`
`The PCC compiler is written in C(cid:23)(cid:23)(cid:8) using approxi(cid:3)
`mately  classes(cid:4) Multiple inheritance is not used(cid:8) so
`the class inheritance relationship is tree structured(cid:4) Ap(cid:3)
`proximately(cid:8)  of these classes are small stub classes
`generated via macros(cid:4) We partitioned the classes into 
`basic groups excluding miscellaneous support classes(cid:10)
`
` Top(cid:10) the top level classes(cid:4) That is(cid:8) the classes not
`directly related to any language entity(cid:8) but used
`primarily as base classes(cid:19)
`
` SymTab(cid:10) symbol table classes representing a PRL
`language construct or type(cid:19)
`
` AST(cid:10) abstract syntax tree AST classes(cid:19)
`
` Optim(cid:10) classes that apply optimization transfor(cid:3)
`mations to the abstract syntax tree(cid:19)
`
` Quads(cid:10) code generation classes(cid:19)
`
`Each modication to the PCC compiler is recorded
`in a VCS known as ECMS the Extended Change Man(cid:3)
`agement System(cid:4) Our analysis is based on  MR(cid:9)s(cid:4)
`For each class(cid:8) we computed how many MRs modied it(cid:4)
`Figure  shows the inheritance hierarchy of the PCC
`classes(cid:4) The area of a node is proportional to the log
`of the number of MRs that modied the corresponding
`class(cid:4) A node is only shown if there was an MR touching
`
`GOOGLE EX. 1032
`Google v. Philips
`
`

`

`PrimaryExprNode
`
`StatementNode
`TreeNode
`
`DescriptorRep
`
`Quad
`
`TreeFunc
`
`Indirect
`
`Figure (cid:3) The class inheritance hierarchy of the PCC com(cid:3)
`piler(cid:4) where the size of a node is proportional to the log of the
`
`number of MRs that touch the class(cid:5) The shape of the node
`
`represents its class group as follow(cid:6) Top  diamonds(cid:4) SymTab 
`
`unlled square(cid:4) AST  lled circle(cid:4) Optim  unlled circle(cid:4) Quads
`
` lled squares(cid:5)
`
`it(cid:4) this is the reason that the number of Quads classes
`is so smallmost of the classes are generated by macros
`and are never modied by hand(cid:7)
`It is clear from this gure that most of the change
`activity was related to the AST(cid:7) Keep in mind that the
`AST code does much more than simply maintain a tree
`data structure(cid:7) Member functions of the AST classes
`are responsible for many compilation phases(cid:8) such as
`type checking(cid:8) code generation(cid:8) etc(cid:7) In an imperative
`language such as C(cid:8) one might encapsulate type check(cid:9)
`ing in a module that takes an AST as input and tra(cid:9)
`verses it to perform the type checking(cid:7) However(cid:8) in an
`object(cid:9)oriented language such as C(cid:10)(cid:10)(cid:8) the function of
`type checking is more naturally expressed as a method
`of the AST classes(cid:7)
`In the PCC compiler(cid:8) the member functions of the
`AST classes are divided among les according to their
`functionality(cid:7) For example(cid:8) all the member functions
`for type checking can be found in a particular set of
`les(cid:8) while member functions for code generation can
`be found in another le set(cid:7) The left panel in Fig(cid:9)
`ure makes this clear(cid:8) using the SeeSoft code visualiza(cid:9)
`tion  (cid:7) Each rectangle represents a le from the com(cid:9)
`piler(cid:7) Only les containing code from the AST classes
`are shown(cid:7) Each class is given a level of gray from
`the gray scale spectrum on the left(cid:8) and each line of
`
`a le is colored to show which class it belongs to(cid:7) As
`is clear from the picture(cid:8) each le contains code from
`many classes(cid:7) Note(cid:8) for example(cid:8) the les containing a
`gray scale spectrum(cid:7) These les group members func(cid:9)
`tions from many dierent classes in the AST that con(cid:9)
`stitute a particular phase of the compiler such as type
`checking or code generation(cid:7)
`There is a very good reason to divide classes into les
`by functionality(cid:7) Centralizing too much functionality in
`one set of classes can impede concurrent development(cid:7)
`By splitting member functions of the same class across
`dierent les(cid:8) dierent programmers can work on dier(cid:9)
`ent aspects of the compiler(cid:7) The right panel in Figure
`shows which programmers worked on which les(cid:7) This
`data is derived from ECMS(cid:3) every MR is owned by ex(cid:9)
`actly one programmer(cid:8) so the code for that MR can be
`traced to an individual(cid:7) It is clear that certain program(cid:9)
`mers had ownership of particular aspects of the compiler
`and AST classes(cid:8) although most les have accumulated
`modications by several programmers(cid:7)
`This partitioning illustrates the complex relation(cid:9)
`ships among the views we are examining(cid:7) For example(cid:8)
`compiler literature suggests that when prototyping
`a new programming language(cid:8) it is useful to implement
`compiler phases as member functions of each AST class(cid:7)
`To add new language constructs(cid:8) one simply adds new
`classes to the set of AST classes(cid:7) On the other hand(cid:8) for
`a mature language(cid:8) it is useful to implement compiler
`phases as modules that transform or operate over an
`abstract data type representing an AST(cid:7) This makes it
`easier to add new optimizing passes to the compiler(cid:7)
`Since PRL was changing during the compiler(cid:20)s de(cid:9)
`velopment(cid:8) an OO approach would appear to make sense
`the inheritance hierarchy acts as a built(cid:9)in switch state(cid:9)
`ment and virtual functions help avoid writing identical
`functions in all classes within a inheritance hierarchy(cid:7)
`However(cid:8) the developers(cid:20) work assignments mimic(cid:20)d the
`second approach(cid:7) That is(cid:8) each developer implemented
`a specic compiler phase for all AST classes(cid:7) In the end(cid:8)
`the compiler phases were incorporated into the mem(cid:9)
`ber functions of the AST classes(cid:8) but(cid:8) during develop(cid:9)
`ment(cid:8) member functions with similar functionality were
`grouped together into separate les(cid:7)
`One goal of our research is to better understand the
`eect that development decisions(cid:8) such as these(cid:8) have on
`the evolution of software systems(cid:7) In the next section
`we discuss some preliminary approaches for analyzing
`the relationship between development approaches and
`a system(cid:20)s change history(cid:7)
`
`GOOGLE EX. 1032
`Google v. Philips
`
`

`

`Subject 1
`
`Subject 2
`
`Subject 3
`
`Subject 4
`
`Subject 5
`
`Subject 6
`
` 93/93/93
`
`
` 29482/29482/29482
`
`
`
`
` 45/45/45
`
`umberChanges
`MR
`Date
`NestingLevel
`Subject
`Inspect
`Class ReturnNode
`
`values
`lines
`files
`
`6/6/6
` 29482/29482/29482
`
`
`
`
` 45/45/45
`
`umberChanges
`MR
`Date
`NestingLevel
`Subject Subject 4
`Inspect
`Class
`
`values
`lines
`files
`
`Figure (cid:3) Two SeeSoft views of the les comprising the abstract syntax tree classes of the PCC compiler(cid:4) In the view to the left(cid:5)
`each class maps to a level of gray in the gray scale spectrum on the left and each line of a le is colored with the class it belongs to(cid:4) The
`view on the right shows the same set of les(cid:5) where each line of a le is colored by programmer there are six programmers(cid:4)
`
` Cluster Analysis of Classes by Modica(cid:3)
`
`tion
`
`One way to help understand the eects of a develop(cid:6)
`ment decision on system evolution is to examine the
`system(cid:7)s change history(cid:8)
`In this example we describe
`initial explorations of how the class structure of this
`system encapsulated changes to it(cid:8)
`For each class C(cid:9) let Cmr be the number of MRs that
`touch class C(cid:8) If C and D are two unique classes(cid:9) let
`CDmr be the number of MRs that touch both classes
`C and D(cid:8) CDmr denes a relationship between the two
`classes(cid:9) which translates to a link in a graph where the
`nodes are classes(cid:8) A probability measure can also be
`associated with the link(cid:3)
`
`DescriptorRep
`
`CDmr(cid:2)pCmrDmr
`
`Quad
`
`TreeNode
`
`Figure (cid:3) Cluster analysis of classes based on MR relationships(cid:4)
`Each node representing a class is colored by the group of the class
`same color and shape as in Figure (cid:4) Nodes closer together are
`joined by links of higher probability(cid:4) The clustering analysis has
`dened the ve class groups(cid:4)
`
`If the classes C and D are always modied together(cid:9) the
`link probability will be (cid:9) since Cmr (cid:12) Dmr (cid:12) CDmr
`in this case(cid:8) However(cid:9) if C and D are rarely modied
`together in comparison to the total number of modi(cid:6)
`cations to C or D(cid:9) then the link probability will be
`low(cid:8)
`We generated this data for the current version of
`the PCC compiler and ran it through a graph cluster(cid:6)
`ing algorithm which places nodes connected by links of
`higher weight closer together(cid:8) We used the probabil(cid:6)
`ity measure described above for the link weighting(cid:8) For
`details on this algorithm(cid:9) see  (cid:8)
`Figure  shows the resulting graph(cid:8) Each node rep(cid:6)
`
`GOOGLE EX. 1032
`Google v. Philips
`
`

`

`resents a class(cid:2) The shape of a node denotes the group
`that the class belongs to(cid:3) as in Figure (cid:2) Note that
`the clustering algorithm has identied clusters of se(cid:6)
`mantically related classes(cid:2) In fact(cid:3) it identied the ve
`basic partitions described earlier(cid:7) The cluster of round
`lled nodes on the lower left are the AST classes(cid:3) while
`the cluster of white square nodes on the right are the
`SymTab classes(cid:2) The cluster on the upper left is the
`Optim group(cid:2) The group of lled square nodes above
`the symbol table cluster represents the Quads group(cid:2)
`In this example(cid:3) all links between classes of dierent
`groups had probabilities less than the same group had
`higher probability(cid:2)
`This gure shows that changes to the AST classes
`often involved other changes to the Optim and SymTab
`groups(cid:2) However(cid:3) as expected(cid:3) there are very few links
`between the Optim and SymTab groups(cid:2)
`Based on this initial analysis(cid:3) we are currently ex(cid:6)
`amining the types of changes that are made between
`classes within the same hierarchy(cid:2) If they are mainly
`changes involving the same member function across dif(cid:6)
`ferent classes(cid:3) then it argues that the class partitioning
`was not eective(cid:2) In addition(cid:3) we are examining similar
`views for le partitioning(cid:2)
`
` Summary
`
`The thesis of this research is that version control sys(cid:6)
`tems contain signicant amounts of data that could be
`exploited in the study of system evolution(cid:2) We have il(cid:6)
`lustrated some ways to use this information(cid:2) In partic(cid:6)
`ular we have derived VCS(cid:6)related metrics(cid:3) like connec(cid:6)
`tion strength based on the probability that two classes
`are modied together(cid:2) We used this metric to assess
`the eect of implementation decisions on the evolution
`of the resulting software(cid:2)
`Clearly(cid:3) this work is in its initial stages(cid:2) We are
`currently exploring several extensions to it(cid:2)
`
` Time(cid:6)series analysis(cid:2) Most metric work is based
`on a single snapshot of a system(cid:2) Little work has
`explored metrics to capture how structure changes
`over long periods of time(cid:2)
`
` Improved analysis models(cid:2) This work implicitly
`treats aspects of the change history as dependent
`variables and aspects of development history as in(cid:6)
`dependent variables(cid:2) Our initial work has looked
`at only a few variables(cid:2) For example(cid:3) we have
`looked at number of changes per class as a de(cid:6)
`pendent variable(cid:2) In our ongoing work we will re(cid:6)
`ne this variable(cid:3) looking at the type of changes(cid:3)
`change eort(cid:3) and whether the change was actu(cid:6)
`ally approved or had to be reworked(cid:2) We will also
`examine complex changes(cid:3) i(cid:2)e(cid:2)(cid:3) those that involve
`
`multiple developers(cid:3) multiple classes(cid:3) and multiple
`functions(cid:2)
`
` Examining development processes(cid:2) We can also
`examine issues related to the development process(cid:2)
`For example(cid:3) are defects discovered during inspec(cid:6)
`tion dierent in nature than those discovered dur(cid:6)
`ing testing(cid:11) We can also look at the eect of devel(cid:6)
`opment decisions on criteria such as development
`interval(cid:2)
`
` Improved visualization techniques(cid:2) The visualiza(cid:6)
`tions we show in this paper are obviously static(cid:2)
`Since we are inherently interested in system behav(cid:6)
`ior over time we expect that visualizations must
`improve to capture this(cid:2) Some possibilities include
`Trellis displays and animation(cid:2)
`
` Static program analysis(cid:2) The change history pro(cid:6)
`vides information about how dierent parts of a
`system are related(cid:2) This information may be use(cid:6)
`ful for automatic restructuring(cid:2)
`
`References
`
`  T(cid:4) Ball and S(cid:4) G(cid:4) Eick(cid:4) Software visualization in the large(cid:4) IEEE
`Computer(cid:5)  (cid:11)  (cid:5) April (cid:4)
`
` William S(cid:4) Cleveland(cid:4) Visualizing Data(cid:4) Hobart Press(cid:5) (cid:4)
`
`  Stephen G(cid:4) Eick and Graham J(cid:4) Wills(cid:4) Navigating large networks
`with hierarchies(cid:4) In Visualization (cid:2) Conference Proceedings(cid:5)
`pages  (cid:5) San Jose(cid:5) California(cid:5) Oct(cid:4) (cid:4)
`
` Maurice H(cid:4) Halstead(cid:4) Elements of Software Science(cid:4) Elsevier 
`North Holland(cid:5)  (cid:4)
`
` David A(cid:4) Ladd and J(cid:4) Christopher Ramming(cid:4) Software research
`and switch software(cid:4) In International Conference on Commu(cid:5)
`nications Technology(cid:5) Beijing(cid:5) China(cid:5) (cid:4)
`
` David A(cid:4) Ladd and J(cid:4) Christopher Ramming(cid:4) Two application
`languages in software production(cid:4) In USENIX Symposium on
`Very(cid:5)High(cid:5)Level Languages(cid:5) Oct(cid:4) (cid:4)
`
` Thomas J(cid:4) McCabe(cid:4) A complexity measure(cid:4) IEEE Trans(cid:6) on
`Software Engineering(cid:5) (cid:11)  (cid:5) Dec(cid:4) (cid:4)
`
` Martin Odersky and Philip Wadler(cid:4) Pizza into Java(cid:11) Translat(cid:19)
`ing theory into practice(cid:4) In Conference Record of  ACM
`Symposium on Principles of Programming Languages(cid:5) pages
`   (cid:5) Paris(cid:5) France(cid:5) Jan(cid:4) (cid:4)
`
`  Marc J(cid:4) Rochkind(cid:4) The Source Code Control System(cid:4)
`IEEE
`Trans(cid:6) on Software Engineering(cid:5) SE(cid:19) (cid:11)  (cid:5) December
` (cid:4)
`
`  Walter Tichy(cid:4) Design(cid:5) implementation and evaluation of a revi(cid:19)
`sion control system(cid:4)
`In Proceedings of the th International
`Conference on Software Engineering(cid:5) pages (cid:5) Tokyo(cid:5)
`Japan(cid:5) Sept(cid:4) (cid:4)
`
`GOOGLE EX. 1032
`Google v. Philips
`
`