CN107203468B - AST-based software version evolution comparative analysis method - Google Patents

Abstract

The invention provides an AST-based software version evolution comparative analysis method. Compare and analyze the source code of the two software versions through the Diff command of Unix, and divide the changed source code into three source code blocks; obtain the AST information of the source code of the two software versions through a syntax analyzer, and analyze and obtain each source code block The AST information corresponding to a line of code; by combining the acquired syntax node information into one combination information, the adjacent code lines with the same identification are combined into modules; by comparing and analyzing the identification information of the two source blocks in units of modules, according to the module The evolution situation is classified and analyzed, and various evolution situations are processed by preprocessing and secondary processing methods, and the evolution information is stored in the database and converted into HTML code. Compared with other software version evolution comparative analysis methods, the present invention can improve the accuracy of acquiring evolution information and improve the efficiency of software version evolution analysis.

Description

A comparative analysis method of software version evolution based on AST

technical field

The invention relates to a comparative analysis method for software version evolution, in particular to a Diff-based AST software version evolution comparative analysis method.

Background technique

The essence of software version evolution analysis is to perform difference analysis on software source code, and the technical background of the present invention is introduced for the method of software evolution analysis and source code difference analysis method.

Software evolution is divided into dynamic evolution and static evolution. Dynamic evolution, also known as online evolution, refers to evolution during software execution. Static evolution is more about an understanding and display of the differences in the source code of software versions. The software version evolution explained next Just for static evolution. It mainly introduces the software version evolution analysis method related to the source code difference analysis method and static evolution.

At present, in terms of software version evolution analysis, it is mainly divided into four categories for research according to the granularity of its analysis. The first category is further research on the addition, deletion, modification and unmodified lines of code of source code. The second category is to further study the grammatical structures such as added, deleted, modified and unchanged class functions. By dividing the changes of software versions into 47 types to understand the process of software evolution, what determines the direction of software evolution? The classification of its types is based on the attribute parameters of grammatical structures such as functions and the types of statements. For example, if the parameters of a function change, it is a type of change, and statements include conditionals, loops, and else statements. One of the more representative ones is an improved AST-based software evolution analysis method, which is an improvement of the method based on AST edit distance (Levenshtein Distance, LD). The method based on AST edit distance (Levenshtein Distance, LD) is usually It is a classic and widely used method for fast fuzzy matching of input strings, English assistance, writing and other fields. As early as 1996, some people migrated the idea of LD algorithm to the source code comparison, Chawathe proposed the shortest edit distance algorithm based on AST to analyze hierarchically structured code, assuming that the hierarchically structured code is symmetrical, and the modules such as class functions The syntax nodes are the same, but the specific properties have changed. Based on this method idea, an improved AST-based software evolution analysis method is proposed, which improves the efficiency and accuracy of the algorithm, and broadens the scope of application of the algorithm, which is not limited to hierarchical structured codes.

The third category is to display the changed and unchanged code in view, and then conduct further research, analyze from the perspective of text and software engineering, and construct a VCN (Visual CodeNavigator) by improving the work of Diff, and display the evolution through the view. Information, visual understanding of version evolution rules, but VCN only supports C/C++. The fourth category is to study the model of software source code. Model mapping and comparison can be used for software reuse and software version evolution analysis. Although it can well meet the needs of software developers, it is necessary to obtain the model of the software version. Analysis, some software versions cannot obtain the model, in general, this method is difficult to operate. There are various implementation methods for each direction, and each method also has its own advantages and disadvantages.

From the research content of these researchers, although there are many kinds of software version evolution analysis algorithms and source code difference analysis algorithms, most of them are from the perspective of semantics. AST-based version evolution comparative analysis has become a hot spot in source code analysis. Compared with the original static source code analysis, the analysis algorithm for the overall structure of the entire source code version, the accuracy and efficiency of evolution analysis are not high.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide an AST-based software version evolution comparison analysis method that can improve the accuracy of acquiring evolution information and improve the software version evolution analysis efficiency.

The object of the present invention is achieved in this way:

Step 1: Compare and analyze the source code of the two software versions through the Diff command of Unix, and obtain the addition, deletion and change of code lines according to the analysis result file Patch, and divide the changed source code into three source code blocks;

Step 2: Obtain the AST information of the source code of the two software versions through the syntax analyzer, and analyze and obtain the AST information corresponding to each line of code of each source block for the three source code blocks analyzed in the first step;

Step 3: by combining the acquired syntax node information into a combination information, using the combination information to identify the corresponding line, and combining the adjacent code lines with the same identification into a module;

Step 4: By comparing and analyzing the identification information of the two source code blocks in units of modules, classifying and analyzing the evolution of the modules, using preprocessing and secondary processing methods to process various evolutionary situations, and storing the evolution information in the database, and Convert to HTML code.

The present invention can also include:

1. Dividing the changed source code into three source code blocks described in step 1 specifically includes: adding, deleting, and changing, and classifying the changed source code into added source code blocks, deleted source code blocks, and changed source code blocks. This is the basis for further analysis.

2. The analysis described in step 2 obtains the AST information corresponding to each line of code of each source block specifically including:

1) Use the breadth-first search algorithm to match the abstract syntax tree nodes generated by ANTLR one by one according to the line number;

2) If the line number is within the range of the node, match the child nodes of this node one by one until a completely matching line number node is found;

3) Use the syntax analyzer to obtain the syntax elements of the current line and the upper-level syntax elements, up to the top-level classes or functions, structures, enumeration classes and unions of the source code file.

3. The acquisition of the combination information described in step 3 is to use the label system identification, which is a unique identification of the class, function, structure, enumeration class and common body module, and uses multiple identifications to combine into one identification code line. Combining information, the approach to labeling system design is:

a) The keyword of the module is the name of the module plus the corresponding attribute information characters;

b) The identification of the module is composed of multiple word-value pairs, and each two word-value pairs are separated by an "@" character;

c) Use "#" to separate the level identifiers of modules;

d) The keyword for global variables, precompiled processing and normal code lines is stmSource, and the value is tempty.

4. The combination module described in step 3 is the source block divided by the Diff according to the labeling system, and the modules are further subdivided. The specific steps of dividing the modules are as follows:

1) For the changed source block analyzed by Diff, obtain the label information of each line of code according to the line number;

2) Compare the label information of adjacent lines of code. According to the comparison, there are two cases. One is a complete module. The starting line of this module must be different from the label of the previous line, and each line of code in the middle of the module must be different. The label is the same, and the end line of this module must be different from the label of the line after it, otherwise it is not a complete module;

3) Fill in the module information data structure according to the two situations analyzed, the information data structure includes the start line of the module, the end line, the type of the module, and the label information of the module.

5. The classification analysis according to the evolution of the module described in step 4 specifically includes: performing in-depth matching analysis of class and function information, and comparing the corresponding information of two different versions with the fixed format of the information, if both exist, And there is a change, that is, change evolution. If the old version does not have it, there is an incremental evolution. If the new version does not, there is a deletion evolution, such as the function parameter evolution of the function module, and the return value evolution of the function module.

6. The use of preprocessing and secondary processing methods to process various evolution situations described in step 4 is a recursive process, that is, preprocessing is required for each processing, and the preprocessing is a normal process for different versions of source code files of the same name. Changes are analyzed and the results of the analysis are stored. If the analysis finds that the Diff analysis is incorrect, it will enter the secondary processing. If the secondary processing also encounters Diff analysis errors, then pre-processing and secondary processing will be performed until the analysis is correct. .

With the vigorous development of the software industry, the software is becoming more and more complex, the number of software version iterations is increasing, and developers are exposed to more and more source codes. At the same time, these software architectures are becoming more and more complex, and the laws of software evolution are also It becomes more obscure, which increases the difficulty for developers to understand and maintain the software. The invention proposes a Diff-based AST software version evolution comparative analysis method, which obtains the evolution information of modules such as class functions, provides a basis for the understanding of the software version evolution, and improves the accuracy and efficiency of the software version evolution analysis. The core of the present invention is the source code facing the software version change, which more accurately and efficiently reflects the level and relationship of the source code at the change place, and migrates to the software version evolution, and is committed to providing a guide for users and reducing software version understanding and maintenance. difficulty.

The effect of the present invention is mainly reflected in:

The existing mainstream software version evolution comparative analysis methods are all based on AST, and the traditional software evolution analysis is mostly based on the similarity matching of abstract syntax trees, and based on this, the analysis of syntax and semantic information is carried out. However, there are errors in similarity, and the matching of similarity needs to be matched with all similar objects, which is not efficient.

An existing relatively efficient software version evolution analysis method is an improved AST-based software evolution analysis method based on the edit distance (Levenshtein Distance, LD) algorithm. LD is usually used for fast fuzzy matching of input strings, English assistance, writing and other fields. It is a classic and widely used method. Migrate the idea of LD algorithm to the comparison of source code, and analyze hierarchically structured code based on the shortest edit distance algorithm of AST. It is assumed that the hierarchically structured code is symmetrical, and the syntax nodes of modules such as class functions are the same, but Specific properties vary. Based on this method idea, an improved AST-based software evolution analysis method is proposed, which improves the efficiency and accuracy of the algorithm, and broadens the scope of application of the algorithm, which is not limited to hierarchical structured codes.

Applying the LD algorithm from string matching to AST, the basic idea is the same. The AST-based shortest edit distance algorithm divides the problem into three steps:

1) Convert the AST into the required tree according to the custom rules.

2) Find a suitable set of matches between the nodes of trees T1 and T2.

3) According to the matching set, find the minimum edit distance to convert the tree T1 to T2.

The first step is to convert the AST into the tree required for your own analysis, then all the module information in the source code must be stored according to the information of the tree, and the matching of each node needs to traverse the corresponding storage information, which is a lot of work. , which is expensive in the evolutionary analysis of large-scale software releases. Some researchers also map each node into a Hash value, and then perform matching. Although the matching process of each node will be optimized to a certain extent, the shortest editing example algorithm based on AST still must map each node. Storage and analysis determine the evolution of each node according to the edit distance of the tree. The more information that is naturally stored, the less efficient the comparative analysis will be when traversing the AST. In the present invention, the AST information is obtained according to the location of the changed code lines, without traversing the entire AST tree.

The second step is to match two nodes according to the distance between the nodes. The distance between the nodes is analyzed by the structure of the node and the type of the node, and the distance value between the nodes is calculated by combining the distance formula between the nodes. , and finally determine whether the nodes are matched according to the threshold, in which the distance formula and the threshold are unstable factors, which are likely to lead to false matching and missing matching.

According to the change of Diff analysis source code, the present invention uses the source code AST information obtained by the syntax analyzer to correct the result of Diff analysis, and analyzes and corrects the error analysis of Diff from semantics, such as analyzing a changed code situation into addition and deletion. Using Diff analysis can accurately analyze the changes in the text, making the subsequent analysis basis very efficient and accurate. Combined with AST analysis, a tag system is designed and used, which can efficiently identify module information such as class functions, and can efficiently analyze the evolution information of module structures such as classes, functions, structures, and unions according to the method used in the present invention.

According to the above analysis and experiments, the present invention can improve the accuracy of acquiring evolution information and improve the efficiency of software version evolution analysis compared with other software version evolution comparative analysis methods. It can effectively analyze the evolution information of module structure such as class functions, make up for the lack of Diff analysis, and provide more detailed guidance for source code version management tools such as git and cvs, and has a good guiding role in reading source code and maintaining the system. . Developers can use this method to guide early exploration, speed up understanding of engineering, and improve development efficiency. In further development, the reuse of functional modules can be completed by this method.

Description of drawings

Figure 1 is a comparison example of the Diff source code version of the system architecture diagram;

Figure 2 shows the normal format result of Diff analysis of source code versions V1 and V2;

Figure 3 is the source code diagram of the add function;

Figure 4 is the AST diagram corresponding to the source code;

Fig. 5 is the line number diagram corresponding to the syntax tree node;

Fig. 6 is the acquisition flow chart of module label information such as class function;

Fig. 7 is the module information table diagram;

Figure 8 is a flowchart of software version evolution difference analysis;

Figure 9 is the content diagram of the configuration file configure.txt;

Figure 10 is a structural diagram of the test environment.

Detailed ways

The present invention will be described in more detail with examples below.

The AST-based software version evolution comparative analysis method of the present invention mainly includes the following steps:

Step 1: Compare and analyze the source code of the two software versions through the Diff command of Unix. According to the analysis result file Patch, obtain the addition, deletion and change of the code line, and divide the changed source code into three source code blocks.

Step 2: Obtain the AST information of the source code of the two software versions through the syntax analyzer, and analyze and obtain the AST information corresponding to each line of code of each source code block for the three source code blocks analyzed in the first step.

Step 3: Combine the acquired syntax node information into one piece of information, use the combined information to identify corresponding lines, and combine adjacent code lines with the same identification into modules.

Step 4: Compare and analyze the identification information of the two source code blocks by module, classify and analyze the evolution of the modules, use preprocessing, secondary processing and other methods to flexibly handle various evolutions, and store the evolution information in the database. , and convert it into HTML code;

Step 1 Divide the changed source code into three source code blocks, add, delete, and change, and classify the changed source code into added source code blocks, deleted source code blocks and changed source code blocks. , to make the processing flow more reasonable and clear.

The AST information corresponding to each line of code obtained in step 2, the method of the present invention for obtaining the AST information corresponding to the code line will remove the redundant information of the AST of the source code obtained by using the syntax analyzer, without traversing the entire abstract syntax tree .

The specific acquisition steps are as follows:

1) Use the breadth-first search algorithm to match the abstract syntax tree nodes generated by ANTLR one by one according to the line number;

2) If the line number is within the range of the node, the child nodes of this node will be matched one by one until a completely matching line number node is found;

3) Use the syntax analyzer to obtain the syntax elements of the current line and the upper-level syntax elements, up to the top-level class or function class, function, structure, enumeration class and union of the source file.

In step 3, the combination information of identifying code lines is obtained by using the label system identification designed by the present invention, which is a unique identification of class, function, structure, enumeration class and common body module. Using multiple identifiers to combine information into a single identifier code line, the labeling system is a standard for further subdividing modules, and the design principles are:

1) The keyword of the module is the name of the module plus the corresponding attribute information characters, such as the name of the class, using the "className" keyword.

2) The identification of the module is composed of multiple word-value pairs (keyword + "@" + value), and each two word-value pairs are separated by an "@" character.

3) Use "#" to separate the hierarchical identifiers of modules, such as functions in a class, className@math#function Name@add.

4) Global variables, the keyword for precompiled processing and ordinary code lines is stmSource, and the value is tempty

The modules formed in the third step are the source blocks divided by the Diff according to the labeling system, and the modules are further subdivided, such as class modules and function modules. The specific steps of dividing the modules are as follows:

1) For the changed source block analyzed by Diff, the label information of each line of code is obtained according to the line number.

2) Compare the label information of adjacent lines of code. According to the comparison, there are two cases. One is a complete module. The starting line of this module must be different from the label of the previous line, and each line of code in the middle of the module must be different. The label is the same, and the end line of this module must be different from the label of the line after it, otherwise it is not a complete module.

3) Fill in the module information data structure according to the two situations analyzed in the second step, such as the start line of the module, the end line, the type of the module, and the label information of the module.

Step 4: Carry out in-depth matching analysis of information such as classes and functions, and compare the corresponding information of two different versions with the fixed format of the information. If both exist and have changed, it is a change and evolution. If the old version does not, There is incremental evolution, if there is no new version, there is deletion evolution, such as function parameter evolution of function modules, and return value evolution of function modules.

The preprocessing and secondary processing described in step 4 is a recursive process, that is, each processing requires preprocessing. The preprocessing is a normal analysis of all changes in the source code files of the same name of different versions and the analysis results are stored. If the analysis finds that the Diff analysis is wrong, it will enter the secondary processing, and the secondary processing may also encounter Diff analysis errors, and then perform preprocessing and secondary processing until the analysis is correct. The preprocessing needs to store the analyzed data separately. .

Since many file comparison software can only distinguish coarse-grained information about changes in folders and files, and show which lines have been added, deleted, or modified, in view of this situation, the present invention focuses on the research on AST-based software version evolution analysis algorithm. The content is to accurately locate the AST nodes with evolution information, analyze and obtain the attribute information of modules such as class functions, classify the evolution situation, analyze various evolution situations, and improve the accuracy and efficiency of evolution analysis. The research of the present invention consists of the following parts:

1) How to accurately locate the AST node with evolution information, the present invention can accurately locate the changed line number through Diff, and can accurately locate the evolution node of the source code AST according to the line number, but the result analyzed by Diff has errors and needs to be corrected , such as analyzing a changed code situation into additions and deletions.

2) How to analyze and obtain the attribute information of modules such as class functions, the present invention analyzes the node characteristics of each type of module according to the AST node information of the source code, and obtains the attribute information.

3) Classification and analysis of the evolution situation, the present invention classifies the evolution situation according to the attribute information of the module, and then designs a corresponding method according to its characteristics.

Due to the variety of evolution situations, specific methods are realized by a combination of specific methods that solve multiple specific problems. The whole method process mainly involves the following parts:

1) Division of Diff analysis results

Diff is implemented based on the LCS algorithm and is used to compare and analyze the similarities and differences between the old and new versions of the files. The operation method is to enter: $Diff<old version file><new version file> in the system terminal interface. The text display of Diff is not very friendly. For the convenience of explanation, an example C++ file is shown in Figure 1.

Diff has three display formats: normal format, contextual format and merged format. The normal format used in the present invention will be introduced below.

Now compare V1 and V2: $Diff V1 V2, at this point, Diff will display the result in normal format as shown in Figure 2.

Each display part is divided into three parts: the first line is a prompt to explain the change position, the first "3" means that the third line of V1 has changed; "c" (change) is a change mode The abbreviation of , and there are two other modes, namely "a" (addition) for increase and "d" (deletion) for deletion; the second "3" means that the 3rd line of V1 shown earlier becomes V2's Line 3. The second line is divided into two parts. The less than sign at the beginning indicates that the fourth line should be deleted from V1, and "return 0;" indicates the content of this line. The third line is used to separate V1 and V2. The fourth line is similar to the second line. The greater-than sign in front means that V2 has added the line, and the following "return 1;" means the content of the line.

Diffing the two source code versions once will generate a Patch file, and the Patch file contains the corresponding line numbers of the old and new source code changes, and the line numbers here are corresponding to a source code block in the present invention. According to the corresponding addition, deletion and change of the line number analyzed by Diff, there are three kinds of source blocks in total, the first is the deleted source block, the second is the added source block, and the third is the changed source block. Since Diff is LCS processing for text lines, there is no semantic information, and the division of this module will not contain any semantic information. In addition, for the position change of a module, most of them will be analyzed as changes in addition and deletion. Therefore, it is necessary to propose a new module division method, which needs to reflect semantic information, and can carry out higher-level evolution analysis, for example, the parameters of functions have changed, and the inheritance relationship of classes has changed.

2) Label system design

The labeling system is a unique identification of classes, functions, structures, enumeration classes and common body modules. According to the source blocks divided by the labeling system for Diff, modules are further subdivided, such as class modules and function modules. Therefore, the labeling system is the standard for further subdividing modules. The principles of this labeling system design are:

(1) The keyword of the module is the name of the module plus the corresponding attribute information characters, such as the name of the class, using the "className" keyword.

(2) The identification of the module is composed of multiple word-value pairs (keyword + "@" + value), and each two word-value pairs are separated by an "@" character.

(3) Use "#" to separate the hierarchical identifiers of modules, such as functions in a class, className@math#function Name@add.

The keyword for global variables, precompiled processing and normal code lines is stmSource, and the value is tempty

Next is the introduction of each keyword of each module, as follows:

(1) Keywords of the class

Class template: classTemplate@template, the template here is to make up word-value pairs and has no actual value.

Class template parameter: classTemplateParameter@(typenameT), the template parameter is T.

Class name: className@Math, a class named Math.

Class inheritance: classRelation@public Circle, this class inherits from the Circle class.

(2) Keyword of function

Function template: functionTemplate@template, the template here is to make up word-value pairs and has no actual value.

Function template parameter: functionTemplateParameter@(typenameT), the template parameter is T.

Inline function: inlineFunction@inline, the inline here is to make up word value pairs, there is no actual value.

The return value of the function: functionReturn@int, the return value of this function is int.

Function name: functionName@Add, a function named Add.

Function parameters: functionParameters@(inta), the parameter of this function is an int type named a.

The identification of other modules, such as structures, enumeration classes and unions, is relatively simple, so I won't go into details here.

3) Acquisition of AST-based labeling system information

The present invention is based on Diff analysis, the changes analyzed by Diff are for specific lines of source code, and the present invention is to mark each line of code with labels of modules such as class functions, and the acquisition of its keyword information value is the key . The present invention is different from other evolution analysis based on AST because the present invention locates the keyword information of AST according to the line number, without traversing the entire abstract syntax tree. efficiency and accuracy. Each node of the abstract syntax tree analyzed by ANTLR has corresponding line number information. As shown in Figure 3, the AST generated by ANTLR corresponding to the source code in Figure 3 is shown in Figure 4. There is a lot of redundant information in this figure, especially are specific variables and statements. The redundant information of the AST is removed, and the line number information of the processed syntax tree is shown in FIG. 5 .

The invention uses the breadth-first search algorithm to match the abstract syntax tree nodes generated by ANTLR one by one according to the line number. If the line number is within the range of the node, it will match the child nodes of this node one by one until a complete match is found. line number node. In this example, if you want to find the label information corresponding to line number 2, start the match from the root node. The node of line number 2 is in the range 1 to 3 to which the root node belongs, and will continue to search for the children of the root node. Node, starting from the first child node on the left, until the node of the function body is completely matched. Then obtain the first child node information of the parent node of the function body node, such as function name, function return value type, and function parameters. Finally, the obtained information is added with the label information of the pre-defined keywords. The complete information is as follows:

functionReturn@int@functionName@add@functionParameters@(inta,intb)

The syntax tree node information of the above example is processed, and the actual node information is relatively complex. The specific process of obtaining the key node information of the AST information is shown in FIG. 6 .

The node names are all expressions in the AST, which correspond one-to-one with the actual module node information. The invention needs to obtain the AST information of the class, function, structure, enumeration class and common body module, and then the label system can be used. The present invention only introduces the acquisition of the detailed label information of the class function by example, and the acquisition of the label information of other modules is similar. The flowchart in the accompanying drawing 6 first obtains the node information of the code line according to the above-mentioned method of locating the node information of the code line, then obtains the specific information of the class function module according to the name information of the node and the content of the child node information, and finally follows The parent node of the AST tree is traversed all the way to the root node, and the traversed module information is combined into label information.

4) Sub-module processing based on label system

After the label of each line of code can be obtained, the present invention can classify each line of code according to the label and divide it into modules. For this reason, the present invention designs a data structure to store module information. The specific module information is shown in Figure 7. The name tag is the result of removing some syntax information from the syntax tag. Only the name tag of each module is combined in the strings together. The Type information indicates the type of the entire complete module, such as a complete function, and the label 7 indicates that the code of this block is only a part of the module. For example, only a certain block of the function has evolved. It may be that a line has been added to the function. code. After the module information is available, it can be processed in modules. The specific steps are as follows:

The first step is to obtain the label information of each line of code according to the line number of the changed source block analyzed by Diff. There are two kinds of labels, one is the name label, and the other is the syntax label.

The second step is to compare the two label information of adjacent lines of code. According to the comparison, it is divided into two cases. One is the complete module, which is the information of the entire module whose Type is 1-5 in Figure 7. This module The start line must be different from the label of the line before it, and the label of each line of code in the middle of the module must be the same, and the end line of this module must be different from the label of the line after it, otherwise it is not a complete module , which is the type of Type 7.

The third step is to fill in the module information data structure according to the two situations analyzed in the second step, such as the start line of the module, the end line, the type of the module, the name tag of the module and the syntax tag.

5) Evolutionary classification steps

From the data structure information of class evolution, it can be seen that the evolution classification of modules is classified by the grammatical information of modules such as classes and functions, such as the evolution of modifiers of classes, the evolution of inheritance relationships of classes, and some internal modules and non-modules of classes. Some statistics on the number of evolutions. According to the additions, deletions and changes of the Diff analysis, the additions, deletions and changes here are not final, and need to be further analyzed after being corrected by sub-module processing. The classification processing process after sub-modules is as follows:

The first step, if a module is added, get the bottommost label of the new version of the software about the label of this module, such as className@class Sphere#functionName@add, where the bottommost label is the function add, just get the functionName value, it means that there is a function-added evolution information, and there is a function-added evolution information in the class Sphere. The statistical methods of these two evolutions are different. One is the statistical evolution relationship of the actual evolution module, and the other reflects the evolution relationship from the hierarchical attribution.

In the second step, if a module is deleted, the same as above, it is just to obtain the information of the old version of the software, and change it to delete.

In the third step, if the module body of a module changes, whether it is added, deleted, or changed, it is recorded as a content change of the bottom-level module. If a line is added to the function body, one more content change is recorded for this function.

The fourth step, if a module attribute is changed, the attribute here refers to the description of the module other than the name in the identification system, such as the return value of the function, the parameters, and whether it is inlined or not are the attributes of the function module. Here, it is necessary to compare the lowest-level label of this module between the old and new versions of the software. The method is to use a label composed of complete keywords about all the information about the underlying module, such as the function as follows: functionTemplate@functionParameter@inlineF-unction@functionReturn@functionName@f unctionParameters, assuming starting from the first tag keyword functionTemplate, if the tags of the old and new software versions have this keyword, compare the value of this keyword, if it is the same, it means that this attribute is the same, if not, then Record the change information of this attribute. If the old and new tags have one without this keyword, record the addition or deletion of the attribute once.

Two different software version source codes will be analyzed in the evolution process of the software version. The present invention marks the two software version source codes to be analyzed as VI and V2 respectively. Figure 8 describes the entire process of software version evolution analysis. The first block is to perform Diff analysis on source files with the same name and the same path, obtain Patch files, process Patch files line by line, classify each Diff change, and process the related evolution of modules such as class functions in modules. Through the processing of the Diff-AST algorithm, the analysis results are stored in the database and converted into HTML pages. The evolution information can be viewed through the database or through the browser. The second block is for the moving operation of files and folders, using MD5 encrypted label processing, and then converting the names and paths of the moved files and folders into an HTML table, and storing the data in the database.

The results of the Diff analysis are displayed in three ways. The present invention uses the normal format Diff, and the analysis results are stored in a patch file. The Diff-AST algorithm analyzes the patch file line by line, using the regular expression "[0-9]+(,[0-9]+)?a[0-9]+(,[0-9]+)?. *" matches add change, delete change and change change are similar. Next, it is necessary to obtain the AST of V1 and V2 through the open source parser ANTLR according to the line numbers of the analyzed V1 and V2 changes, analyze the syntax and semantic information of modules such as class functions based on the AST, and construct the label information of the module, and then according to the label Perform sub-module processing, and finally design and implement corresponding algorithms according to the characteristics of various evolution types, and store the data in the MySQL database through the Hibernate persistence technology. In order to view the software version evolution information intuitively, it will also analyze the The evolution information is converted into JSON-formatted information and stored into HTML page information.

This implementation can be performed either in Eclipse software or in a Linux terminal environment. In the Eclipse software, the source code of the project is used for analysis, and in the Linux terminal environment, the Diff-AST.jar package file generated by the project source code is analyzed by Eclispe. Only the situation in the Linux terminal environment is introduced here. In the current directory of the Linux terminal environment, a configuration file configure.txt and the software version evolution analysis tool Diff-AST.jar are required. The content in the configuration file configure.txt is as follows Figure 9 shows.

Lines 1 to 4 in configure.txt show the source code directory of the old and new versions of the software version evolution analysis and the output file patch and HTML directory, and lines 5 to 8 show the database connection information. The MySQL database is used in this implementation. The information includes the name of the database, the driver of the database, the user name and password of the database, and the design and use of the configuration file configure.txt improves the flexibility of using the software version evolution analysis tool.

Running the command $java-jar Diff-AST.jar configure.txt in the terminal will generate an HTML file in the corresponding reportPath directory. There is an index.html in the root directory of the HTML file, which can be opened with a browser to view the software version Detailed evolution information, such as the number of files added, deleted and modified, and detailed evolution information of source code, the specific implementation environment structure is shown in Figure 10.

Claims (4)

1. An AST-based software version evolution comparative analysis method is characterized in that:

the method comprises the following steps: comparing and analyzing two software version source codes through a Diff command of Unix, acquiring the conditions of addition, deletion and change of code lines according to an analysis result file Patch, and dividing the changed source codes into three source code blocks, namely an added source code block, a deleted source code block and a changed source code block;

step two: AST information of two software version source codes is obtained through a syntax analyzer, and the AST information corresponding to each line of codes of each source code block is obtained through analysis aiming at the three source code blocks analyzed in the first step;

step three: obtaining grammar node information by analyzing the AST information obtained in the second step to combine the grammar node information into a combined information, using the combined information to identify each line of the three source code blocks in the first step, and combining adjacent code lines with the same identification into a module; the acquisition of the combined information uses a label system identifier which is a unique identifier of a class, a function, a structural body, an enumeration class and a shared body module, and the combined information of an identification code line is formed by combining a plurality of identifiers, wherein the label system design method comprises the following steps:

a) the key words of the module are the name of the module plus corresponding attribute information characters;

b) the identification of the module is formed by combining a plurality of agreed word value pairs, and each two word value pairs are separated by an '@' character;

c) the hierarchy identification of modules are separated by "#";

d) the global variable, the key words of the precompiled processing and common code line are stmSource, and the value is tempty;

step four: comparing and analyzing the identification information of the two source code blocks by taking the module formed in the step three as a unit, performing classification analysis according to the module evolution condition, processing various evolution conditions by using a preprocessing method and a secondary processing method, storing the evolution information into a database, and converting the evolution information into an HTML code; the method for processing various evolution conditions by using the preprocessing and the secondary processing is a recursive process, namely, each processing needs preprocessing, the preprocessing is to analyze all changes of the homonymous source code files of different versions normally and store the analysis result, if the Diff analysis is analyzed to be wrong, secondary processing is carried out, if the secondary processing also encounters the Diff analysis error, then the preprocessing and the secondary processing are carried out until the analysis is correct.

2. The AST-based software version evolution comparative analysis method of claim 1, wherein the analyzing and obtaining AST information corresponding to each line of codes of each source block in the second step specifically comprises:

1) matching the abstract syntax tree nodes generated by the ANTLR one by one according to the line numbers by using a breadth-first search algorithm;

2) if the row number is in the range of the node, matching the sub-nodes of the node one by one until a completely matched row number node is found, otherwise, not matching;

3) and using a syntax analyzer to obtain syntax elements of the current line and upper-layer syntax elements until the top-layer class of the currently analyzed source code file or the function, the structure body, the enumerated class and the shared body.

3. The AST-based software version evolution comparative analysis method of claim 2, wherein the combination module in step three is a source code block divided by Diff according to a label system, and the module is further subdivided, and the specific division module comprises the following steps:

1) for the changed source code blocks analyzed by Diff, acquiring the label information of each line of codes according to the line number;

2) comparing the label information of the codes of the adjacent lines, and dividing the information into two conditions according to the comparison condition, wherein one condition is a complete module, the label of the starting line of the module is different from the label of the previous line, the label of each line of codes in the middle of the module is the same, and the label of the ending line of the module is different from the label of the next line; otherwise, the other is not a complete module;

3) and filling a module information data structure according to the two analyzed conditions, wherein the information data structure comprises a starting line and an ending line of the module, the type of the module and the label information of the module.

4. The AST-based software version evolution comparative analysis method as claimed in claim 1, wherein the classifying and analyzing according to the module evolution in step four specifically comprises: deep matching analysis of class and function information is carried out, corresponding information of two different versions is compared with a fixed format of the information, and if both versions exist and are changed, evolution is changed; if the old version does not exist, there is an incremental evolution; if the new version does not exist, there is a deletion evolution.

Images