Browse Prior Art Database

Tool to Measure the Size of Program Change

IP.com Disclosure Number: IPCOM000174496D
Original Publication Date: 2008-Sep-10
Included in the Prior Art Database: 2008-Sep-10
Document File: 2 page(s) / 28K

Publishing Venue

IBM

Abstract

To accurately size a software project, one requires a method for measuring the complexity (usually understood in terms of "size") of the software project. For making modifications in existing software, one requires a way to measure the complexity of the modification. It is typical for developers to estimate the time required for a new project based on the time required for previous projects of similar complexity. To measure change, developers often use "lines of code," but this is known to be an inaccurate measure and the number of lines of code are not directly related to program complexity.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 2

Tool to Measure the Size of Program Change

Roughly, the procedure to compare two ASTs works in a top-down fashion by comparing first the root of each tree and then the subtrees. Also, during the comparison the invention constructs correspondence between the symbol tables for the two trees. The end result is that invention shows the total size complexity of the difference between the two programs, in terms of actual logic and not merely lines of code. The process is insensitive to comments, formatting changes, and other non-logical changes to the source code file.

The algorithm has a recursive step which is:

RECURSIVE

_

STEP(SCT, AST

_

1, AST

_2)

Here AST

_1 and AST

_2 are the 2 syntax trees that will be compared.

The argument "SCT" is the "symbol correspondence table," which is a list of pairs. The first element from each pair is a symbol from AST

_1, and the second is the

corresponding symbol from AST

_

2. RECURSIVE

_STEP proceeds by comparing the

root node of AST

_1 and AST

_2. If the root nodes are equal, then the result of

RECURSIVE STEP is:

RECURSIVE

STEP(SCT, left

_subtree(AST

1), left

_subtree(AST

1)) +

RECURSIVE

_

_STEP(SCT, right

_subtree(AST

_

_1), right(subtree(AST

_

_2))

If the root nodes are not equal and both root nodes are not symbols, then the result of RECURSIVE

_STEP is one more than the above quantity.

If the root notes are both symbols (even if they are equal) then check SCT to see if there is a correspondence between the two symbols. If there is not (and if neither symbol is in the list of pairs already), then add it, so that from now on consider both of these symbols to be "the same." This prevents confusion based on variable names, rather than actual program structure.

The entire algorithm is:

RECURSIVE

_STEP(null

_set, AST1, AST2), where AST1 and AST2 are the abs...