1 Introduction
-
Composition of product variants based on feature revisions: We present an approach for composing variants and provide further details of the feature revision location. We include an illustrative example to show how our approach supports system evolution in space and time and how it is implemented in ECCO2. Additionally, we further extended our approach with hints showing possible conflicts and interactions between feature revisions when composing new configurations.
-
Support for C language artifacts: We developed a new adapter, i.e., a new ECCO plug-in, using a fine-grained tree structure to perform feature revision location, while our previous work (Michelon et al. 2020d) was using a text plug-in. Our new plug-in improves the analysis of artifact equivalence when computing traces by analyzing differences in the abstract syntax tree (AST) of feature revisions. Thus, it also enables the evaluation of the evolution of C source code. Although our approach is independent of artifact type, the new plug-in makes our approach easily adoptable in practice, given the high number of SPLs implemented in C.
-
Evaluation with additional systems and more feature revisions: We extended our empirical evaluation by applying our approach to more systems from different domains. We now locate feature revisions and compose new configurations with the located feature revisions from six systems. Our analysis includes more points in time, leading to more feature revisions and more product variants. We thus mined more Git commits of more C preprocessor-based systems and included more system variants in our replication package3.
-
Enhanced analysis: To evaluate the approach of this extended work, we now compute the runtime performance of composing variants with feature revisions besides precision, recall, and extraction time. Further, we computed new metrics for the hints retrieved when composing new products. These metrics indicate conflicts and interactions when composing product variants with different combinations of feature revisions. We computed further metrics allowing an in-depth analysis of feature evolution at the implementation level. These metrics count the different AST nodes used by our plug-in to store the artifacts of feature revisions.
2 Background
3 Motivation
SQLITE_TEST
was modified for the release branch-3.95. The same set of changes, i.e., the feature revision SQLITE_TEST
committed in the release branch-3.9, had to be propagated to three newer releases: branch-3.18, branch-3.19, and branch-3.22. This example confirms that features have different implementations, with different behaviors at different points in time, which is of interest for developers combining different revisions of a feature in existing configurations.WITH_SERVER
changed in 21 releases, resulting in a total number of 241 feature revisions. In this case, 21 system releases contain this feature, i.e., each possible configuration including this feature could have 241 different implementations, if we consider all commits of its development. However, even if a developer has to analyze a smaller number of feature revisions, the code has to be manually analyzed and retrieved. We analyzed some of the commits changing WITH_SERVER
: usually multiple files and lines of source code changed in a single commit and also between releases of the system, thus resulting in different implementations of the feature at different points in time. Some of the changes represent bug fixes, e.g., commits 3b8c4dc77 and 9546b20d8, some represent new system functionality, e.g., commits b9b7174d9 and 9b2eefe610, implemented by this feature, some represent deletions of functionality of this feature, e.g., commits 55846a4c11 and 636432e412. Furthermore, we analyzed how many files and lines were part of the feature implementation in the first and last releases of the system. The feature was first added in two source code files and comprised 119 lines, while it covered 30 source code files and 4734 lines in the last release.WITH_SERVER
. If the SPL is implemented in a VCS, a developer may have to rely on documentation describing the kinds of changes performed in different commits of the feature WITH_SERVER
, which is usually not available. Thus, the developer would have to manually select the feature code, then, copy and paste it to specific configuration releases. To retrieve another feature, for instance the feature HAVE_SSH1
at a specific point in time from commit 5f7c84f913, the developer would need to analyze 29 files, 1339 additions, and 188 deletions. Thus, this manual task is very time-consuming, even more so if multiple features are committed at a single point in time, which is common in practice: for instance, the revisions of the feature HAVE_SSH1
in the first 50 commits happened together with revisions of 13 other features impacting 73 source code files. Therefore, in this context, ECSEST aids maintenance and evolution tasks in annotation-based SPLs in VCSs by retrieving information of the system evolution in space and time at the feature granularity (Michelon et al. 2021c).4 ECSEST Approach
4.1 Data Structures
4.2 Feature Revision Location
FeatY
), which already existed at T1. Thus, the revision number of the feature was incremented to 2.
BASE
, which represents the common code of the variants and represents the core of an SPL, i.e., parts of the system not related to features of the SPL. However, the core of the system is subject to frequent changes, and thus knowing the versions of the common code is also important for managing and evolving the system artifacts. Therefore, the core of the system is also mapped to a feature revision, which can have any name, but is represented here as the feature BASE
. The feature revision location then analyzes in how many variants a feature revision appears, in how many variants a (set of) artifact(s) appears, and in how many variants a pair of feature revision(s) and a (set of) artifact(s) appear together. In this way, all artifacts are mapped to feature revisions.
4.2.1 Trace Computation
BASE
and HAVE_POLL
(Lines 1, 2, 4, 8, 9, 11, 12 and 23 from Listing 1) at point T1. Listing 3 shows the code of a variant v2 containing BASE
and absence of the features HAVE_SELECT
and HAVE_POLL
(Lines 1, 2, 6, 8, 9, 20, 21 and 23 from Listing 1) at point T1. Listing 4 shows the code of a variant v3 containing the features BASE
and HAVE_SELECT
(Lines 1, 2, 6, 8, 9, 14-18 and 23 from Listing 1 at point T1). Listing 5 shows the code of a variant v4 containing BASE
at point T1 and HAVE_SELECT
at point T2, where the Line 15 from Listing 1 changed.
Variant vi | Feature revisions vi.F | Artifacts vi.A |
---|---|---|
v1 | {HAVE_POLL1,BASE1} | Listing 2 |
v2 | {BASE1} | Listing 3 |
v3 | {HAVE_SELECT1,BASE1} | Listing 4 |
v4 | {HAVE_SELECT2,BASE1} | Listing 5 |
ssh_fd_poll(SSH_SESSION ⋆session)
. When the variant is used as input, the comparison for artifacts equivalence is performed between the Lines from Listings 4 and 5. Then, as feature revision location is an incremental process, the existing traces in the repository from the equivalent artifacts have to be updated. The updated traces thus include this new feature revision in the clauses of the traces containing the equivalent artifacts. In the incremental feature revision location, after input variant v4, the old artifact in Line 7 from variant v3 is traced solely to the feature revision HAVE_SELECT
1. Also, a new trace is created for the new code in Line 7 from Listing 5 to the new feature revision HAVE_SELECT
2.HAVE_SELECT
and HAVE_POLL
with a logical negation (¬) in an input configuration of a variant (such as variant v2), as including BASE
in the configuration is sufficient. However, when preprocessing the variant, our approach computes traces for the specific artifacts that do not belong to the feature BASE
, i.e., the core of the system, but are part of a variant when a specific feature is not part of the configuration. For example, in an #if
and #else
conditional compilation, the #else
block artifacts of a system will be part of a variant only when a feature of the #if
is absent in the configuration, similar to an #if !(Feature)
. However, including BASE
in the configuration cannot guarantee that the #else
part will be in the variant as the feature from the #if
part also has to be absent in the configuration. This is why only adding positive feature revisions in clauses is not sufficient for creating traces to artifacts that are part of a variant only when specific features are present and specific features are absent. In such cases, different possible traces can affect the variants created in the future.Trace ti | Presence condition ti.C | Artifacts ti.A |
---|---|---|
t1 | F31 ∨ (F31 ∧ F11) ∨ (F31 ∧ ¬ F2 ) ∨ (F31 ∧ F11 ∧ ¬F2 ) | Lines 4,11-12 (L 1) |
t2 | F21 ∨ (F21 ∧ ¬ F3 ) ∨ (F21 ∧ F11) ∨ (F21 ∧ F11 ∧ ¬F3 ) | Line 15 (L 1) |
t3 | F11 ∧ ¬ F2 ∧ ¬F3 | Lines 20-21 (L 1) |
t4 | F21∨2 ∨ (F21∨2 ∧ ¬ F3 ) ∨ (F21∨2 ∧ F11) ∨ (F21∨2 ∧ F11 ∧ ¬F3 ) | Lines 14,16-18 (L 1) |
t5 | F11 | Lines 1-2,8-9,23 (L 1) |
t6 | F11 ∧ ¬ F3 | Line 6 (L 1) |
t7 | F22 ∨ (F22 ∧ ¬ F3 ) ∨ (F22 ∧ F11) ∨ (F22 ∧ F11 ∧ ¬F3 ) | Line 7 (L 5) |
4.2.2 Optimization Aspects
BASE
, also appears in four variants. Finally, the artifacts and the clause appear together also in four variants. Therefore, the criterion for likely clauses (2) is satisfied. The cells in Table 3 highlighted with gray color indicate pairs of feature revision(s) and artifact(s) that always appear together in input variant(s).
HAVE_POLL
1) ∨ (HAVE_POLL
1 ∧¬ HAVE_SELECT
) ∨ (BASE
∧ HAVE_POLL
1) ∨ (BASE
∧ HAVE_POLL
1 ∧¬ HAVE_SELECT
). The first clause is obtained by the criterion for likely clause because artifacts from Lines 4,11-12 in Listing 1 are contained in every variant that contains the feature HAVE_POLL
1 and all variants that have artifacts from Lines 4,11-12 in Listing 1 also have the feature HAVE_POLL
1. The second clause is also created with the criterion for likely clause, where all variants that have artifacts from Lines 4,11-12 in Listing 1 also have feature BASE
1. Although artifacts from Lines 4,11-12 are not from BASE
1, BASE
1 was present in the variants containing these artifacts. That is what we show in the counter table for storing this information (Table 3), while the third clause is created because all absent features for a specific artifact are negated in our approach. Thus the third clause (HAVE_POLL
1 ∧¬ HAVE_SELECT
) has the feature HAVE_SELECT
negated because this feature does not appear in variants with the artifacts from Lines 4,11-12 in Listing 1. The fourth clause is the most restrictive condition, combining the previous clauses.BASE
1 is present. However, BASE
1 is present in four variants. When looking at the other columns of the second row of the Table 3, we can see that the feature revision HAVE_POLL
1 is also present in one variant, only in the one containing the artifacts from Lines 4, 11-12 from Listing 1. Therefore, we know the feature revision HAVE_POLL
1 must be traced to Line 4 and our final presence condition contains the feature revision BASE
1, as Line 4 appears only once and in a variant containing also the feature BASE
1 in its configuration. Thus, the first clause is less restrictive and the fourth clause is the most restrictive condition of the presence condition of the trace t1. If another input variant would exist with only the feature revision HAVE_POLL
1, and containing Lines 4, 11-12 from Listing 1, the trace t1 would be refined and its presence condition would be (HAVE_POLL
1) ∨ (HAVE_POLL
1 ∧¬HAVE_SELECT
) ∨ (HAVE_POLL
1 ∧¬BASE
) ∨ (HAVE_POLL
1 ∧¬HAVE_SELECT
∧¬BASE
). Having a clause in a presence condition with ¬BASE does not mean that this feature must not exist in the configuration of a variant containing the respective trace artifact, but that BASE
was absent in a variant where the respective trace artifact appears and was thus not mapped to the artifact. Hence, BASE
would not be a mandatory feature for having these artifacts in a variant.4.3 Variant Composition
HAVE_POLL
1, HAVE_SELECT
1 and BASE
1 to compose a variant. The traces t1, t2, t4, t5 (Table 2) corresponding to these feature revisions will be retrieved from the repository and their artifacts will be joined in order to create a variant. These traces are considered in the set of traces \(T^{\prime }\) because at least one clause of the presence condition is satisfied (clauses are split with the ∨ logical operator). For example, t1 contains a clause with F31, which represents the feature HAVE_POLL
and is one of the features of the configuration. However, this combination of feature revisions has feature interactions, as we can see in Listing 1. Then, when composing the variant we also get the hints, which we will explain next.HAVE_SELECT
2, HAVE_POLL
1, BASE
1) to compose a variant, used as example, contains some of the clauses of the trace t1 and t4 as Surplus Clauses. Trace t1 is selected to compose the variant because it contains a clause with HAVE_POLL
1 and another with BASE
1 ∧ HAVE_POLL
1 from the existing ones in the presence condition of t1. However, two clauses are Surplus Clauses: (HAVE_POLL
1 ∧ ¬HAVE_SELECT
) and (BASE
1 ∧ HAVE_POLL
1 ∧ ¬HAVE_SELECT
), as they correspond to artifacts that never appear together within the artifacts of all existing revisions of the feature HAVE_SELECT
. The same happens with trace t4, which results in hints for possible surplus artifacts, because some of the artifacts of the input variant containing the feature revision HAVE_SELECT
2 did not appear with some artifacts of the input variant containing the feature revision HAVE_POLL
1. The hints can help developers that need to manually remove part of the artifacts of a specific trace from the composed variant, if the new combination of feature revisions has conflicts when used together.5 Evaluation
5.1 Research Questions
5.2 Method
5.3 Dataset
System | Since | LoC | Commits | Features | Feature revisions | Input variants |
---|---|---|---|---|---|---|
Marlin | 2011 | 281355 | 52 | 151 | 106 | 191 |
LibSSH | 2005 | 110590 | 400 | 44 | 538 | 577 |
SQLite | 2000 | 173714 | 337 | 36 | 388 | 424 |
Irssi | 2007 | 85325 | 400 | 30 | 414 | 441 |
Bison | 2002 | 39904 | 240 | 134 | 272 | 310 |
Curl | 1999 | 22490 | 350 | 84 | 422 | 485 |
5.4 Mining Ground Truth Variants from Evolution in Space and Time
BASE
, A
, Y
) and one existing feature changed in point T2 (Y
revision 2). Based on that, the mining process is as follows.
A
and Y
are external. Internal feature literals are defined at some point in the code via a #define
directive. Thus, we can see in Fig. 6, that the feature literals B
and C
defined in main.c as well as the feature literals X
and Z
defined in header.h are internal.#define
and #include
statements and conditional blocks remained in the code, as they can modify the resulting code of the variants. On the right of Fig. 6, we see that the highlighted Line 11 is the only one that changed after this step replacing #if X(B,C) > Z
with #if 2 + 9 > Z
..c/.cpp
. A SourceNode has as a root node BASE
that emulates the feature BASE
, which contains ConditionalNodes as much as needed to represent each #ifdef
in a file. DefineNodes represent the location in a file of #define
and #undef
preprocessor statements, while IncludeNodes represent the #include
preprocessor statements in a file. The tree nodes are used to determine the differences between an actual commit and its previous one according to Git-diff21. The adopted tree structure has a higher level of abstraction, i.e., for every annotated block, a child stores its content in its respective node category, e.g., conditional nodes, define nodes, and include nodes. This makes our mining process computationally less expensive. We adopted the changes at Git-diff granularity, i.e., files and lines, to be able to easily inspect the correctness of the generated ground truth variants according to changes of features annotated in Git VCS.BASE
is considered the changed feature, i.e., for every code added/removed in the body of the project that does not belong to an external feature the root feature, i.e., BASE
is considered as the changed node. Figure 6 shows two files, the header file (on top of the figure indicated by an arrow) and the file containing 14 lines on the bottom of the figure. At point T1 we have these two files, and at point T2 the main file (the file on the bottom of the Fig. 6) has been changed in Line 12.
A
defines B = 2
(Line 3, main.c) and C = 9
(Line 4, main.c), and BASE
defines Z = 3
as there is no conditional block wrapping Line 1 in the file header.h. Thus, BASE
implies header.h and the features that activate the code block that changed (Line 12) are X
, B
, C
, and Z
, which are defined by features A
and BASE
. Still, when walking up the file we see that there is an outermost code block with a condition expression involving the feature Y
(Lines 9-14), which wraps the changed block. The feature implications are mathematically defined as follows: (A ⇒ (B = 2)) ∧ (A ⇒ (C = 9)) ∧ (BASE ⇒ (Z = 3)). The conjunction of all these parts, local and global condition and implications, are the logic expression to the problem constraint that can be handed to the solver: (A ⇒ (B = 2)) ∧ (A ⇒ (C = 9)) ∧ (BASE ⇒ (Z = 3)) ∧ Y ∧ (2 + 9 > Z). The solution assigned that satisfies this formula is then: BASE = TRUE ∧ Y = TRUE ∧ A = TRUE. We thus know that these features must be selected to include the changed block of code in a variant.BASE
, which is trivially a positive solution.5.5 Metrics
-
FeaturesIntroduced. Number of new features introduced over the Git commits analyzed.
-
FeaturesChanged. Number of features changed over the Git commits analyzed.
-
Header. Number of header files.
-
Define. Number of defines.
-
Field. Number of field/struct declarations.
-
Function. Number of functions.
-
If. Number of if conditions.
-
For. Number of for loops.
-
Do. Number of do loops.
-
Switch. Number of switch conditions.
-
Case. Number of case statements.
-
While. Number of while loops.
-
Problem. Number of problem blocks not recognized in the C AST.
-
PrecisionFileLevel. The percentage of correctly retrieved files in relation to the total retrieved.
-
RecallFileLevel. The percentage of correctly retrieved files in relation to the total ground truth ones.
-
F1ScoreFileLevel. The percentage of the weighted average of Precision and Recall at the file level.
-
PrecisionLineLevel. The percentage of correctly retrieved lines in relation to the total retrieved.
-
RecallLineLevel. The percentage of correctly retrieved lines in relation to the total ground truth ones.
-
F1ScoreLineLevel. The percentage of the weighted average of Precision and Recall at the line level.
-
ArtifactsRatio. The percentage of the number of new variants composed with hints that have artifacts missing/surplus in relation to the total of new variants with hints.
-
InteractionsRatio. The percentage of the number of new variants composed with hints that have feature interactions and retrieved missing/surplus artifacts in relation to the total number of new variants.
-
ExtractionTime. The time in seconds for locating feature revisions, i.e., for extraction of mappings of feature revisions to artifacts from a variant.
-
CompositionTime. The time in seconds for composing a new variant, i.e., the time needed to retrieve traces from a set of feature revisions and compose their artifacts in order to generate a variant.
5.6 Implementation Aspects
6 Results and Discussion
6.1 Feature evolution in space and time
BASE
, the second commit introduced 16 new features. Then, later in Git commit 51, 109 new features were introduced. Furthermore, additional new features were included in four Git commits.
BASE
, four features were added in the second commit. Along the commits analyzed, within 11 commits 33 new features introduced. Regarding the evolution over time, there were 29 Git commits with feature revisions.BASE
. For Marlin, 22 different features changed in the Git commits analyzed. In the LibSSH and Curl systems, 30 features evolved over their Git commits analyzed. For the SQLite system, 24 features changed, and for the commits analyzed in the Irssi and Bison systems, 12 and 13 different features changed, respectively.YYDEBUG
from the Curl system (shown in Fig. 9f), indirectly realize customer requirements. An interesting example of a feature revision that have to be reused in previous revisions of the SQLite system can be seen in the feature SQLITE_TEST
24, which evolved meaning that its change had to be applied in four releases of the system: branch-3.9, branch-3.18, branch-3.19 and branch-3.22.BASE
feature. The number of AST nodes of the feature HAVE_SSH1
from the LibSSH system (Fig. 9b) has constant changes, but the number of fields increased significantly in its second revision. This is also the case for the feature SQLITE_TEST
from SQLite and the feature MSDOS
from the Bison system in revision 6 (Fig. 9c and e), and for the feature ADVANCE
from Marlin in revision 4 (Fig. 9a). The evolution over time of the feature SQLITE_TEST
from the SQLite system (Fig. 9c) shows an increasing number of AST nodes up to its sixth revision. After that, the AST nodes remain constant in terms of numbers per node type, and in case of field nodes, the number decreases in the twelfth revision of the feature SQLITE_TEST
. The feature __GNUC__
from the Irssi system (Fig. 9d) has not been changed regarding the number of AST nodes over the three revisions, with the exception of the number of problem statements/blocks and defines AST nodes, which increased during the second revision. For example, for the feature YYDEBUG
from the Curl system (Fig. 9f) the number of header files, define, field, if, and for AST nodes increased in its fourth revision. In the fifth revision, for example, 14 header files were removed from its implementation.
ADVANCE
from the Marlin system substantially changed compared to its predecessor. We analyzed the Git commit https://github.com/MarlinFirmware/Marlin/commit/094afe7c1065d5663628b389f27687a5f465abb825 and saw from the commit message that a merge was performed. A developer added 12 new files, changed eight, and removed two files that affected the source code of the feature ADVANCE
, and hence, the behavior of how the movement of the printer is done with linear acceleration. For every new revision of this feature, the movement is affected. In the ninth revision (Git commit https://github.com/MarlinFirmware/Marlin/commit/65934eee9c6ae792c708bc1cea9996c8a5df67f526) many changes were performed in the planner source code, which influences the buffers movement commands and manages the acceleration profile plan.YYDEBUG
from the Curl system as an example. The revisions of this feature are from five different releases of the system. This feature is used for debugging purposes and contains many fprintf calls to print the debug messages in a file. Thus, depending on the revision selected, different debug messages are printed. If developers want to use the revision of this feature to get more debug messages and combine it with features of another release, it can be supported with ECSEST instead of manually retrieving the Git commits of the feature revision and release. Besides that, developers will need to work manually copy, paste and modify the code of the release with the code of the desired feature revision.6.2 Locating feature revisions
Subject system | Granularity | Precision | Recall | F1 − Score |
---|---|---|---|---|
Marlin | FileLevel | 1.00 | 0.95 | 0.98 |
LineLevel | 0.99 | 0.99 | 0.99 | |
LibSSH | FileLevel | 1.00 | 0.99 | 0.99 |
LineLevel | 0.99 | 0.99 | 0.99 | |
SQLite | FileLevel | 1.00 | 0.97 | 0.98 |
LineLevel | 0.99 | 0.99 | 0.99 | |
Bison | FileLevel | 1.00 | 0.99 | 0.99 |
LineLevel | 1.00 | 0.99 | 0.99 | |
Curl | FileLevel | 1.00 | 0.92 | 0.96 |
LineLevel | 0.99 | 0.99 | 0.99 | |
Irssi | FileLevel | 1.00 | 0.99 | 0.99 |
LineLevel | 0.99 | 0.99 | 0.99 | |
All | FileLevel | 1.00 | 0.97 | 0.99 |
LineLevel | 0.99 | 0.99 | 0.99 |
6.3 Composing variants with new configurations of existing feature revisions
Subject system | Granularity | Precision | Recall | F1 − Score |
---|---|---|---|---|
Marlin | FileLevel | 1.00 | 0.96 | 0.98 |
LineLevel | 0.99 | 0.99 | 0.99 | |
LibSSH | FileLevel | 1.00 | 0.99 | 0.99 |
LineLevel | 0.99 | 0.99 | 0.99 | |
SQLite | FileLevel | 1.00 | 0.99 | 0.99 |
LineLevel | 0.99 | 0.99 | 0.99 | |
Bison | FileLevel | 1.00 | 0.99 | 0.99 |
LineLevel | 0.99 | 1.00 | 0.99 | |
Curl | FileLevel | 1.00 | 0.92 | 0.96 |
LineLevel | 0.99 | 0.99 | 0.99 | |
Irssi | FileLevel | 1.00 | 0.99 | 0.99 |
LineLevel | 0.99 | 0.99 | 0.99 | |
All | FileLevel | 1.00 | 0.97 | 0.99 |
LineLevel | 0.99 | 0.99 | 0.99 |
HAVE_SSH1
, DEBUG_CRYPTO
, HAVE_PTY_H
and BASE
.HAVE_SSH1
defined, the ground truth variant will contain Line 2 and not Line 4. Only when this feature is not defined Line 4 will be present in the variant. Our feature revision location approach correctly mapped the artifact from Line 2 to presence conditions containing feature HAVE_SSH1
and Line 4 to presence conditions containing BASE
and other features from the respective point in time. However, the ground truth variant does not contain artifacts of both #ifdefs
and #else
blocks, hence, not matching with the composed variant. Curl random variants were composed with 208 inserted lines and 3,787 deleted lines among a total of 3,266,773 relevant lines. The randomly composed variants from the Bison system retrieved 54 inserted lines and no deleted lines from a total of 1,412,709 relevant lines. From a total of 6,972,575 relevant lines in the Irssi system, 786 lines were inserted in the randomly composed variants and 1,017 lines were deleted.
Subject system | ArtifactsRatio | InteractionsRatio |
---|---|---|
Marlin | 88% | 90% |
LibSSH | 38% | 88% |
SQLite | 75% | 37% |
Bison | 2% | 66% |
Curl | 100% | 100% |
Irssi | 60% | 83% |
All | 60.5% | 77% |
6.4 Performance of ECSEST to locate feature revisions and compose variants
BASE
for every input variant. In addition, it takes a long time for every new input variant to extract what is new and update from what is already in the repository. For SQLite the longer extraction time compared to Irssi is probably caused by the huge number of artifacts that had to be compared.