https://doi.org/10.31449/inf.v44i2.2452 Informatica 44 (2020) 199–224 199 Computing Dynamic Slices of Feature-Oriented Programs with Aspect-Oriented Extensions Madhusmita Sahu and Durga Prasad Mohapatra Department of Computer Science and Engineering National Institute of Technology, Rourkela-769008 Rourkela, Odisha, India E-mail: madhu_sahu@yahoo.com and durga@nitrkl.ac.in Keywords: feature-oriented programming (FOP), aspect-oriented programming (AOP), composite feature-aspect depen- dence graph (CFADG), mixin layer, refinement chain Received: September 10, 2018 This paper proposes a technique to compute dynamic slices of feature-oriented programs with aspect- oriented extensions. The technique uses a dependence based intermediate program representation called composite feature-aspect dependence graph (CFADG) to represent feature-oriented software that contain aspects. The CFADG of a feature-oriented program is based on the selected features that are composed to form a software product and the selected aspects to be weaved. The proposed dynamic slicing tech- nique has been named feature-aspect node-marking dynamic slicing (FANMDS) algorithm. The proposed feature-aspect node marking dynamic slicing algorithm is based on marking and unmarking the executed nodes in the CFADG suitably during run-time. The advantage of the proposed approach is that no trace file is used to store the execution history. Also, the approach does not create any additional nodes during run-time. Povzetek: Prispevek predstavlja izvirni pristop pri programiranju na osnovi sprejemljivk z aspektno orien- tiranimi podaljški. Gre za raˇ cunanje dinamiˇ cnih odsekov omenjenih programov. 1 Introduction Weiser [33] first introduced the concept of a program slice. Program slicing decomposes a program into different parts related to a particular computation. A slicing criterion is used to construct a program slice. A slicing criterion is a tu- ple,, consisting of a statements, in a program and a variablev, used or defined at that statements. Program slicing technique is employed in many areas of software engineering including debugging, program understanding, testing, reverse engineering, etc. Feature-oriented programming (FOP) is concerned with the separate definition of individual features and the com- position of required features to build varieties of a partic- ular software product. The functionalities of a software product are identified as features in FOP paradigm. FOP is used to implement software product lines and incremental designs. A family of software systems constitutes a soft- ware product line [20]. Motivation: Today, the variability of software products is crucial for successful software development. One mech- anism to provide the required variability is through Soft- ware Product Lines, which is inspired by product lines used in the industry, like product lines used in the pro- duction of a car or a meal at some fast-food restaurant. Feature-Oriented Programming (FOP) approach is used to implement software product lines. Despite the advan- tages, feature-oriented programming (FOP) yields some problems in expressing features such as lack of express- ing crosscutting modularity. During software evolution, a software should adapt the unanticipated requirements and circumstances. This leads to modifications and ex- tensions that crosscut many existing implementation units. The problem of crosscutting modularity is solved by us- ing aspect-oriented programming (AOP). Kiczales et al. [8] proposed AOP paradigm to separate and modularize the crosscutting concerns like exception handling, synchro- nization, logging, security, resource sharing, etc. The mod- ularity of crosscutting concerns in FOP can be improved by integrating AOP paradigm into FOP paradigm. In dy- namic slicing techniques, first an intermediate representa- tion of the program is statically created in the form of a dependence graph. Then, the dynamic slice is computed by traversing the graph, starting from the point specified in the slicing criterion, using an algorithm. For the pro- grams in general languages like C/C++, Java etc., a sin- gle dependence graph is created. There is no composition of features in these languages. FOP is used to develop a family of software products. In FOP (with AOP exten- sions), multiple dependence graphs are created depending upon the composition of features and aspects. For exam- ple, if there are four features and two aspects in a product line out of which two features and one aspect are manda- tory, then there are eight possible combinations of features 200 Informatica 44 (2020) 199–224 M. Sahu et al. and aspects. Each possible combination of features and as- pects creates a different product. Thus, there are eight soft- ware products in the product line. Accordingly, there are eight dependence graphs, one graph for each product. Dy- namic slice for each possible combination of features and aspects is computed using the corresponding dependence graph. The dynamic slice consists of statements from the composed program that is generated after composition of features and aspects. These statements are again mapped back to the program used for composition. This mapping is not required in general languages like C/C++, Java etc. Again, feature-oriented programs have some special char- acteristics such as mixins, mixin layers, refinements etc. which are not present in case of general languages like C/C++, Java etc. These characteristics of feature-oriented programs require inclusion of some new nodes/edges in the dependence graph. Similarly, these characteristics require introduction of some new steps/phases in the slicing algo- rithm (e.g., the handling mixins, the handling of mixin lay- ers, etc.), which are not required in the case of general lan- guages like C/C++, Java, etc. The existing dynamic slic- ing algorithms for aspect-oriented programs cannot be di- rectly applied for slicing of feature-oriented programs with aspect-oriented extensions due to the specific features of feature-oriented programs such as the presence of mixin layers, refinements of classes, refinements of constructors etc. These characteristics of feature-oriented programs re- quires inclusion of some new nodes/edges in the depen- dence graph. Similarly, these characteristics require the introduction of some new steps/phases in the slicing algo- rithm. Although FOP is an extension of OOP, the existing dynamic slicing algorithms for C/C++, Java cannot be di- rectly applied for slicing of feature-oriented programs due to the presence of aforementioned specific features. Since, program slicing has many applications including testing, software maintenance etc., there is an increasing demand for slicing of feature-oriented programs. Objective: The main objectives of this work are to develop a suitable intermediate representation of feature-oriented programs with aspect-oriented extension and to propose an efficient slicing algorithm to compute dynamic slices for the above types of programs using the developed interme- diate representation. A dependence graph is used to sig- nify the intermediate representation. For a single feature- oriented program, more than one dependence graph can be obtained depending on the number of features to be com- posed and the number of aspects to be captured. We also aim at calculating the slice computation time for different compositions of features and different aspects captured. Organization: The organization of rest of the paper is as follows. Section 2 provides a brief introduction to feature- oriented programming (FOP) and program slicing. Section 3 discusses the construction of composite feature-aspect dependence graph (CFADG), which is a dependence based intermediate representation of feature-oriented programs containing aspects. In Section 4, the details of our pro- posed algorithm named feature-aspect node marking dy- namic slicing (FANMDS) algorithm, is discussed. This section also presents the space and time complexity of FANMDS algorithm. Section 5 furnishes a brief overview of the implementation of FANMDS algorithm along with experimental results. A brief comparison of the proposed work with some other related work is furnished in Section 6. Section 7 concludes the paper along with some possible future work. 2 Basic concepts In this Section, we provide some basic concepts of feature- oriented programming and outline the features of Jak lan- guage, which is a feature-oriented programming language. We also discuss the problems of feature-oriented pro- gramming and solutions to these problems through aspect- oriented programming extensions. 2.1 Feature-oriented programming (FOP) Prehofer [1] was the pioneer to coin the term feature- oriented programming (FOP). The key idea behind FOP is to build the software by composing features. Features are the basic building blocks that are used to satisfy user re- quirements on a software system. The step-wise refinement where features incrementally refine other features leads to a stack of features that are arranged in layers. One suitable technique to implement the features is through the use of Mixin Layers. A Mixin Layer is a static component that encapsulates fragments of several different classes (Mix- ins) to compose all fragments consistently. Several lan- guages like Jak [2], 1 , Fuji 2 , FeatureHouse 3 , FeatureRuby [40, 41], FeatureC++ [5, 3, 4] support the concept of fea- tures explicitly. FeatureIDE [6] 4 is a tool that supports Feature-Oriented Software Development (FOSD) in many languages. We have taken Jak program as input in our pro- posed approach as it is supported by Algebraic Hierarchi- cal Equations for Application Design (AHEAD) tool suite, which is a composer. AHEAD tool suite is a group of tools to work with Jak language. Other languages have their own composers, and those composers are not a group of tools. Jak (short for Jakarta) is a language that extends Java by in- corporating feature-oriented mechanisms [2]. Jak-specific tools like jampack and mixin are invoked to compose Jak files. A Jak file is translated to its Java counterpart using another tool called jak2java. The different features sup- ported by Jak language are Super() references, an extension of constructors, declaration of local identifiers, etc. The de- tails of Jak language and its features can be found in [2]. 1 https://juliank.files.wordpress.com/2012/04/ jlang1.pdf 2 http://www.infosun.fim.uni-passsau.de/spl/ apel/fuji 3 http://www.fosd.de/fh 4 http://wwwiti.cs.uni-magdeburg.de/iti\_db/ research/featureide/deploy Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 201 Figure 1: Features supported by Calculator Product Line (CPL) Figure 2: Aspects captured in Calculator Product Line (CPL) Example 2.1. Calculator Product Line (CPL) [45]: This program calculates the factorial, square root and logarith- mic value with base 10 of a number. This program is re- ferred to as Calculator Product Line (CPL). A feature-tree depicts various features supported by a product line in a hierarchical manner. The feature-tree for Example 2.1 is given in Figure 1. The various aspects that are captured for Example 2.1 are given in Figure 2. Figure 3 depicts the source code for each feature given in Figure 1 and each aspect given in Figure 2. Figure 4(a) – Figure 4(b) show the resultant files generated after the composition of all features. 2.2 Problems in feature-oriented programming (FOP) Feature-oriented programming (FOP) suffers from many problems in modularization of crosscutting concerns [3, 4, 5]. The presence of these problems leads to degradation in modularity of program family members and also decrease in maintainability, customizability, and evolvability. Some of the problems of FOP are discussed below. 1. FOP is unable to express dynamic crosscutting con- cerns that affect the control flow of a program. It can only express static crosscutting concerns that affect the structure of the program. AOP languages can han- dle dynamic crosscutting concerns in an efficient man- ner through the use of pointcuts, advices etc. 2. FOP languages support only heterogeneous crosscut- ting concerns where different join points are provided with different pieces of codes. In contrast, AOP lan- guages support homogeneous crosscutting concerns where different join points are provided with the same piece of code. 3. FOP suffers from excessive method extension prob- lem when a feature crosscuts a large fraction of exist- ing classes because of refinements. A lot of methods are to be overridden for each method on which a cross- cut depends. This is because FOP is unable to modu- larize homogeneous crosscutting concerns. AOP uses wildcards in pointcuts to deal with this problem. 2.3 AOP extensions to FOP AOP can be used to solve the above problems of FOP by in- tegrating AOP language features like wildcards, pointcuts, and advices into FOP languages. The different approaches used for integrating AOP language features into FOP lan- guages are Multi Mixins, Aspectual Mixin Layers, Aspec- tual Mixins. More details about these approaches can be found in [5, 3, 4]. The Aspectual Mixin Layers approach is a popular one amongst all the approaches since this ap- proach overcomes all the aforementioned problems. Other approaches overcome some of the problems. We have used the approach of aspectual mixin layers in our work. We have separated the aspects from mixin layers for easy un- derstanding of our approach. Our mixin layers contain only a set of classes. Aspects are designed as different layers. 2.4 Program slicing Program slicing is a technique which is employed to ana- lyze the behavior of a program on the basis of dependencies that exist between various statements. It takes out state- ments from a program related to a specific computation. The extracted statements constitute a slice. Thus, a slicing criterion is employed to compute a slice. A slicing crite- rion consists of a statements (or location in the program) and a variablev (or set of variables), and it is represented as a tuple< s;v >. Program slicing technique can be ei- ther static or dynamic based on the input to the program. A program slicing technique is said to be static when it ex- tracts all the statements from a program with respect to a slicing criterion irrespective of the input to the program. On the other hand, a program slicing technique is said to be dynamic when all the statements from a program are ex- tracted with respect to a slicing criterion for a specific input to the program. The difference between static slicing and dynamic slic- ing can be understood by taking an example. Let us con- sider the example C program given in Figure 5. The static slice with respect to slicing criterion< 11;y> is depicted as the bold italic statements in Figure 6. It includes state- ments 1, 2, 3, 4, 6, 7, 9, and 11. The dynamic slice with respect to slicing criterion < fx = 10g; 11;y > is de- picted as the bold italic statements in Figure 7. It includes statements 1, 2, 3, 6, 9, and 11. For finding the slices of a program, first an intermediate representation of the pro- gram is constructed. Then, the slices are found out by using some algorithm on the intermediate representation. There are many slicing algorithms found in the literature 202 Informatica 44 (2020) 199–224 M. Sahu et al. (a) Base/calc.jak (b) Base/test.jak (c) sqrt/calc.jak (d) sqrt/test.jak (e) log/calc.jak (f) fact/calc.jak (g) log/test.jak (h) fact/test.jak (i) Print/test.jak (j) error.aj (k) print.aj Figure 3: Jak program for Calculator Product Line (CPL) along with aspect code. Figure 3(a)–Figure 3(i) represent base code or non-aspect code written in Jak language and Figure 3(j)–Figure 3(k) represent aspect code written in AspectJ Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 203 (a) calc.java (b) test.java (c) error.aj (d) print.aj Figure 4: Java codes generated (Figure 4(a)–Figure 4(b)) after the composition of all features depicted in Figure 1. Figure 4(c)–Figure 4(d) are the AspectJ codes for the aspects captured. 204 Informatica 44 (2020) 199–224 M. Sahu et al. Figure 5: An example C program Figure 6: Static slice with respect to slicing criterion < 11;y> Figure 7: Dynamic slice with respect to slicing criterion [10, 11, 12, 14, 15, 16, 17, 19, 21, 25, 26, 37, 38, 42]. For the details of the intermediate program representations and different slicing algorithms, the readers may refer to [10, 11, 12, 14, 15, 16, 17, 19, 21, 25, 26, 37, 38, 42]. In the next section, we propose an intermediate program representation for feature-oriented programs, on which our slicing algorithm can be applied. 3 Composite feature-aspect dependence graph (CFADG): an intermediate representation for feature-oriented programs We have proposed an intermediate representation for feature-oriented programs, called Composite Feature- Aspect Dependence Graph (CFADG). CFADG is an arc- classified digraph,G = (N;E), whereN is the set of ver- tices depicting the statements andE is the set of edges sym- bolizing the dependence relationships between the state- ments. The set E captures various dependencies that ex- ist between the statements in various mixin layers and as- pects in a feature-oriented program. CFADG is constructed based on the composition of different features and aspects captured. Thus, there will be different types of CFADGs according to the features composed and aspects captured. Figure 8 shows the CFADG for the composition given in Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 205 Figure 3. The square box with a1_in: n_in=n etc. speci- fies the actual and formal parameters. For example: a1_in: n_in=n specifies that n is an actual-in parameter. Simi- larly, a2_in: b_in=b specifies thatb is an actual-in param- eter, f1_in: x=n_in specifies thatx is a formal-in parame- ter, f2_in: b=b_in specifies thatb is a formal-in parameter. These notations are adopted from Horwitz et al. [47]. The construction of CFADG consists of the following steps: – Constructing Procedure Dependence Graph (PDG) for each method in a mixin. – Constructing Mixin Dependence Graph (MxDG) for each mixin. – Constructing System Dependence Graph (SDG) for each mixin layer. – Constructing Advice Dependence Graph (ADG) for each advice. – Constructing Introduction Dependence Graph (IDG) for each introduction. – Constructing Pointcut Dependence Graph (PtDG) for each pointcut. – Constructing Aspect Dependence Graph (AsDG) for each aspect. – Constructing Composite Feature Aspect Dependence Graph (CFADG) by combining all the SDGs and As- DGs. Below, we briefly explain the steps for constructing the CFADG and the pseudocode. (1) Construction of Procedure Dependence Graph (PDG) A procedure dependence graph (PDG) depicts the control and data dependence relationships that exist between the statements in a program with only one function/method/procedure. The nodes in the graph correspond to the program statements and edges cor- respond to the dependence relationships between the statements. (2) Construction of Mixin Dependence Graph (MxDG) A mixin dependence graph (MxDG) is used to cap- ture all dependencies within a mixin. A MxDG has a mixin entry vertex that connects the method entry vertex of each method in the mixin by a mixin mem- bership edge. Each method entry in the MxDG is associated with formal-in and formal-out parameter nodes. The interactions among methods in a mixin occur by calling each other. This effect of method calls is symbolized by a call node in a MxDG. Actual- in and actual-out parameter nodes are created at each call node corresponding to formal-in and formal-out parameter nodes. The effect of return statements in a MxDG is represented by joining each return node to its corresponding call node through a return depen- dence edge. (3) Construction of System Dependence Graph (SDG) for each Mixin Layer A single mixin layer may contain more than one mixin. A mixin may derive another mixin through inheritance. The MxDG for the derived class is con- structed. The mixin membership edges connect the mixin entry vertex of derived class to the method en- try vertices of all those methods that are defined and inherited in the derived class. The SDG for a mixin layer is constructed by joining all the mixin depen- dence graphs for that mixin layer through parameter edges, call edges and summary edges. (4) Construction of Advice Dependence Graph (ADG) An advice dependence graph (ADG) represents an ad- vice in an aspect. The statements or predicates in the advice are represented as vertices and dependen- cies amongst statements are represented as edges in an ADG. Each ADG is associated with a unique ver- tex called advice start vertex to signify entry into the advice. (5) Construction of Introduction Dependence Graph (IDG) An introduction dependence graph (IDG) represents an introduction in an aspect. If an introduction is a method or constructor, then its IDG is similar to PDG of a method. A unique vertex, called introduction start vertex, is used in IDG to signify the entry into the in- troduction. (6) Construction of Pointcut Dependence Graph (PtDG) Pointcuts in an aspect contain no body. Therefore, to represent pointcuts, only a pointcut start vertex is cre- ated to denote the entry into the pointcut. (7) Construction of Aspect Dependence Graph (AsDG) An aspect dependence graph (AsDG) is used to rep- resent a single aspect. It consists of a collection of ADGs, IDGs, PtDGs that are connected by some spe- cial kinds of edges. Each AsDG is associated with a unique vertex called aspect start vertex, to repre- sent entry into the aspect. An aspect membership edge is used to represent the membership relationships be- tween an aspect and its members. This edge connects the aspect start vertex to each start vertex of an ADG, IDG or PtDG. Each pointcut start vertex is connected to its corresponding advice start vertex by call edges. (8) Construction of Composite Feature-Aspect Depen- dence Graph (CFADG) 206 Informatica 44 (2020) 199–224 M. Sahu et al. The CFADG is constructed by combining the SDGs for all mixin layers present in the composition and the AsDGs through special kinds of edges. The SDGs for all mixin layers in a composition are connected us- ing refinement edges, mixin call edges, mixin data de- pendence edges, and mixin return dependence edges. The AsDGs are connected to all the SDGs through weaving edges and aspect data dependence edges. The mixin membership edges and aspect membership edges along with mixin start vertices and aspect start vertices are removed during construction of CFADG. The CFADG for the program given in Figure 3 is shown in Figure 8. A CFADG contains the following types of edges: (a) Control dependence edge: A control depen- dence edge in a CFADG from a node n 1 to a node n 2 indicates that either node n 2 is under the scope of noden 1 or noden 1 controls the ex- ecution of noden 2 where noden 1 is a predicate node. In Figure 8, edge (m20;s21) is a control depen- dence edge. (b) Data dependence edge: A data dependence edge in a CFADG from a noden 1 to a noden 2 indicates that noden 2 uses a variable that is as- signed a value at noden 1 orn 1 creates an object o ando is used atn 2 . In Figure 8, edges (s21;s22), (s39;s41), (p72;a73) are data dependence edges. (c) Mixin data dependence edge: A mixin data de- pendence edge in a CFADG from a noden 1 to a noden 2 indicates that noden 2 in a mixin layer defines a variable which is used at noden 1 in an- other mixin layer. In Figure 8, edges (s5;s16) and (s39;s54) are mixin data dependence edges. (d) Aspect data dependence edge: An aspect data dependence edge in a CFADG from a node n 1 to a noden 2 indicates that noden 2 in an aspect uses the value of a variable and that variable is defined at noden 1 in a mixin. In Figure 8, edge (s5;a1_in) is an aspect data dependence edge. (e) Call edge: A call edge in CFADG from a node n 1 to a node n 2 indicates that node n 1 calls a method defined at noden 2 . Both the nodes n 1 andn 2 are in same mixin layer. In Figure 8, edge (s41;m2) is a call edge. (f) Mixin call edge: A mixin call edge in CFADG from a noden 1 to a noden 2 indicates that node n 1 in a mixin layer calls a method that is defined in a different mixin layer at noden 2 . In Figure 8, edge (s28;m7) is a mixin call edge. (g) Return dependence edge: A return dependence edge in a CFADG from noden 1 to noden 2 in- dicates that node n 1 in a mixin layer returns a value to node n 2 in the same mixin layer and noden 2 calls a method where noden 1 is present. In Figure 8, edge (s18;s46) is a return depen- dence edge. (h) Mixin return dependence edge: A mixin re- turn dependence edge in a CFADG from noden 1 to noden 2 indicates that noden 1 in one mixin layer returns a value to noden 2 in another mixin layer and noden 2 calls a method where noden 1 is present. In Figure 8, edge (s11;s21) is a mixin return de- pendence edge. (i) Parameter-in edge: Parameter-in edge in CFADG is added from actual-in parameters to corresponding formal-in parameters to indicate the receipt of values from the calling method to the called method. In Figure 8, edges (s14 ! a1_in;m7 ! f1_in), (s21 ! a1_in;m7 ! f1_in), and (s28! a1_in;m7! f1_in) are parameter- in edges. (j) Parameter-out edge: Parameter-out edge is added from formal-out parameters to corre- sponding actual-out parameters to indicate the return of values from the called method to the calling method. If an actual parameter is mod- ified inside a method, then the modified value becomes an actual-out parameter and the origi- nal value becomes an actual-in parameter. The parameter used to hold the value of actual-in pa- rameter in method definition becomes a formal- in parameter and the parameter used to hold the modified value becomes a formal-out parameter. In Figure 8, there are no parameter-out edges, since, in our example, no parameter is modified inside a method. (k) Summary edge: The summary edge is used to represent the transitive flow of dependence be- tween an actual-in parameter node and an actual- out parameter node if the value of the actual-in parameter node affects the value of the corre- sponding actual-out vertex. In Figure 8, edges (s14!a1_in;s14), (s21! a1_in;s21), and (s28! a1_in;s28) are sum- mary edges. (l) Message dependence edge: A message depen- dence edge from a noden 1 to another noden 2 in a dependency graph signifies that noden 1 repre- sents a statement outputting some message with- out using any variable and node n 2 represents an input statement, a computation statement, a method call statement, or a predicate statement. In Figure 8, there exists a message dependence edge (s3;s4). Similarly, edges (s45;s46), (s53;s54), and (s61;s62) are message depen- dence edges. Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 207 (m) Refinement edge: A refinement edge in a CFADG from a noden 1 to a noden 2 indicates that noden 1 in child mixin layer calls a method k() by prefacing Super() call andk() is defined at noden 2 in parent mixin layer. In Figure 8, the edge (s44;m40) is a refinement edge. Similarly, edges (s68;m59), (s60;m51), and (s52;m43) are refinement edges. (n) Weaving edge: A weaving edge from a noden 1 to noden 2 indicates that – node n 1 is a method call node and node n 2 is a before advice node capturing the method called at n 1 and node n 2 executes before the method called by n 1 executes. OR – node n 1 is the last statement in before ad- vice and noden 2 is the method entry node of the method captured by the advice and node n 2 executes after node n 1 executes. OR – noden 2 is an after advice node and noden 1 is the last statement in the method captured by noden 2 and noden 2 executes after node n 1 executes. OR – noden 1 is the last statement in an after ad- vice and noden 2 is the statement followed by method call node and the method is cap- tured by the advice and node n 1 executes before noden 2 executes. In Figure 8, edge (s14;a73) is a weaving edge. The brief pseudocode for constructing the CFADG for a feature-oriented program is given below, and the complete algorithm is given in Algorithm 8 in Appendix A. CFADG construction Algorithm (1) For each mixin layer (a) For each mixin i. Create mixin entry vertex ii. For each method A. Compute control and data dependences. B. Construct PDG using control & data dependence edges. iii. For each method call A. Create actual parameter vertices. iv. For each method definition A. Create method entry vertex. B. Create formal parameter vertices. v. Construct MxDG by connecting all PDGs through method call edges, parameter edges and summary edges and connecting each method vertex to mixin start vertex through mixin membership edges. (b) Construct SDG by connecting all MxDGs through method call edges, parameter edges. (2) For each aspect (a) Create aspect entry vertex. (b) For each advice i. Create advice start vertex. ii. Compute control and data dependences. iii. Construct ADG using control & data dependence edges. (c) For each introduction i. Create introduction start vertex. ii. If introduction is a field then Do not create any dependence graph. Else if introduction is a method then Construct IDG using control and data dependence edges. (d) For each pointcut i. Create pointcut start vertex. ii. Construct PtDG. (e) Construct AsDG by connecting advice start vertices, intro- duction start vertices, pointcut start vertices to aspect start vertex through aspect membership edges. (3) Remove mixin membership edges, aspect membership edges, mixin start vertices, and aspect start vertices. (4) Connect all SDGs through refinement edges, mixin call edges, mixin data dependence edges, and mixin return dependence edges. (5) Connect all AsDGs to all SDGs through weaving and aspect data dependence edges. 4 Feature-aspect node-marking dynamic slicing (FANMDS) algorithm In this section, we present our proposed algorithm for com- puting dynamic slices of feature-oriented programs using CFADG. We have named our algorithm Feature-Aspect Node-Marking Dynamic Slicing (FANMDS) algorithm as it is based on marking and unmarking the nodes of CFADG. Before presenting our FANMDS algorithm, we first intro- duce some definitions which will be used in our algorithm. 4.1 Definitions Definition 1: Defn(v): Letv be a variable or an object in programP . A nodeu in the CFADG is said to beDefn(v) node ifu corresponds to a definition statement that defines a value to variablev oru represents a statement that creates objectv. In the CFADG given in Figure 8, nodess23, ands24 rep- resent Defn(answer) nodes in the method logten() in mixin calc in log mixin layer. Definition 2: DefnSet(v): The set of allDefn(v) nodes is referred to asDefnSet(v). In the CFADG given in Figure 8, DefnSet(answer) = fs23;s24g in the method logten() in mixin calc in log mixin layer. Definition 3: RecDefn(v): For each variablev, RecDefn(v) represents the node corresponding to the most recent definition of v with respect to some point s in an execution. 208 Informatica 44 (2020) 199–224 M. Sahu et al. Figure 8: Composite Feature-Aspect Dependence Graph (CFADG) for the program given in Figure 4 Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 209 In the CFADG of Figure 8, RecDefn(i) is at statement s32 before while loop and it is at statements35 during ex- ecution of while loop. Definition 4: Usage(v): Letv be a variable or an object in programP . A nodeu in the CFADG is said to beUsage(v) node if u represents a statement that uses the variable v oru represents a statement that uses the objectv to call a method on that object or to assign the objectv with another object. In the CFADG given in Figure 8, nodess47, ands49 rep- resentUsage(r) nodes. Similarly, nodes77, ands78 are Usage(n) nodes. Definition 5: UsageSet(v): The set of allUse(v) nodes is referred to asUsageSet(v). In the CFADG given in Figure 8, and UsageSet(r) = fs47;s49g,UsageSet(n) =fs77;s78g. 4.2 Overview of FANMDS algorithm Before execution of a feature-oriented program FP , the features required for composition and the aspects to be cap- tured are selected. Then, the selected features are com- posed and selected aspects are weaved. The CFADG is constructed statically only once based on the composition of selected features and weaving of selected aspects. The program is executed for a specified input. The executed nodes in CFADG are marked and unmarked during pro- gram execution depending upon the arise and cease of de- pendences respectively. When a statement executes a Su- per() node, it is marked by the algorithm. Also the cor- responding method entry node, the associated actual and formal parameter nodes are marked. When there is an invo- cation of a method, the corresponding call node, the corre- sponding method entry node, the associated actual and for- mal parameter nodes are also marked. Whenever a pointcut is executed, the corresponding advice nodes are marked. When an advice is executed, the corresponding formal pa- rameter nodes are marked. During execution, the dynamic slice of each executed statement is computed. After execu- tion of each node and computation of dynamic slice at that node, the algorithm unmarks it. Letdyn_slice(u) denote the dynamic slice with respect to the most recent execution of nodeu. Let (e 1 ;u); (e 2 ;u);:::; (e k ;u) be all the marked predecessor nodes of u in the CFADG after execution of nodeu. The dynamic slice with respect to the present execution of nodeu is com- puted as dyn_slice(u) =fu;e 1 ;e 2 ;:::;e k g[dyn_slice(e 1 )[ dyn_slice(e 2 )[:::[dyn_slice(e k ). Our FANMDS algorithm computes the dynamic slice with respect to the specified slicing criterion by simply looking up the corresponding dyn_slice computed dur- ing run-time. Below, we present the pseudocode of our FANMDS algorithm in brief. Algorithm 9 in Appendix B presents our FANMDS algorithm in detail. Feature-Aspect Node-Marking Dynamic Slicing (FAN- MDS) Algorithm (1) CFADG Construction: Construct the CFADG for the given feature-oriented program with aspect-oriented extensions, statically only once. (2) Initialization: Do the followings before each execution ofFP . (a) Unmark all nodes of CFADG. (b) Setdyn_slice(u) = for every nodeu. (c) Set RecDefn(v) = NULL for every variable v of the programFP . (3) Run time updations: Execute the program for the given set of in- put values and carry out the followings after each statements of the programFP is executed. Let nodeu in CFADG corresponds to the statements in the programFP . (a) For every variablev used at nodeu, Update dyn_slice(u) = fu;e 1 ;e 2 ;:::;e k g [ dyn_slice(e 1 )[dyn_slice(e 2 )[:::[dyn_slice(x k ) wheree 1 ,e 2 , . . . ,e k are the marked predecessor nodes ofu in CFADG. (b) Ifu isdefn(v) node, then i. Unmark the nodeRecDefn(v). ii. UpdateRecDefn(v) =u. (c) Mark nodeu. (d) Ifu is a method call node ornew operator node or polymor- phic node or mixin call node, then i. Mark nodeu. ii. Mark the associated actual-in and actual-out nodes corresponding to the present execution ofu. iii. Mark the corresponding method entry node for the present execution ofu. iv. Mark the associated formal-in and formal-out parame- ter nodes. (e) Ifu is a Super() method node i. Mark nodeu. ii. Mark the associated actual-in and actual-out nodes corresponding to the present execution ofu. iii. Mark the corresponding method entry node present in the parent mixin layer for the present execution ofu. iv. Mark the formal-in and formal-out parameter nodes as- sociated with the method entry node. (f) Ifu is a pointcut node i. Mark nodeu. ii. Mark the corresponding advice nodes for present exe- cution ofu. (g) Ifu is an advice node i. Mark nodeu. ii. Mark the formal-in and formal-out parameter nodes as- sociated with the advice node. (h) Ifu is an introduction node such thatu is a method i. Mark nodeu. ii. Mark the formal-in and formal-out parameter nodes. (i) Ifu is an introduction node such thatu is a field i. Mark nodeu. ii. Mark the node that defines a value tou for the current execution ofu. iii. Mark the node that uses the value ofu for the current execution ofu. (4) Slice Look Up (a) For a given slicing command , do 210 Informatica 44 (2020) 199–224 M. Sahu et al. i. Look updyn_slice(u) for variablev for the content of the slice. ii. Map the Java statements included in the computed dy- namic slice to the corresponding composed Jak state- ments to get the final dynamic slice iii. Display the resulting slice. (b) If the program has not terminated, go to Step 3. Working of the Algorithm The working of FANMDS algorithm is illustrated through an example. Consider the feature-oriented pro- gram given in Figure 3 and the selected features for com- position and aspects given in Figure 1 and Figure 2 respec- tively. After the composition of the selected features, the files that are generated are depicted in Figure 4. The corre- sponding CFADG is shown in Figure 8. During the initial- ization step, our algorithm first unmarks all the nodes of the CFADG and setsdyn_slice(u) = for every nodeu of the CFADG. Now, for the input datan = 5, the program will execute the statementsm69,s70,p81,a82,s83,m67,s68, a82,s83,m59,s60,a82,s83,m51,s52,a82,s83,m43, s44, a82, s83, s39, m40, s41, m2, s3, s4, s5, s6, a84, s85,s45,s46,m13,s14,p72,a73,s74,m7,s8,s10,s11, a75,s76,a78,s79,s15,s16,s18,s47,s49,a84,s85,s53, s54,m20,s21,a73,s74,m7,s8,s10,s11,a75,s76,s78, s79,s22,s23,s25,s55,s57,a84,s85,s61,s62,m27,s28, a73,s74,m7,s8,s10,s11,a75,s76,s78,s79,s29,s30, s31,s32,s33,s34,s35,s37,s63,s65,a84,s85,a84,s85 in order. So, our FANMDS algorithm marks these nodes. Our algorithm also marks the associated actual parameter vertices at the calling method and the formal parameter ver- tices at the called method. Now, the dynamic slice is to be computed with respect to variablen at statements78, i.e., with respect to slicing criterion by traversing the CFADG in backward manner. According to the FANMDS algorithm, the dynamic slice with respect to variable n at statement s78 is given by the expression dyn_slice(s78) = fs78;s76;a75 ! f1_ing [ dyn_slice(s76) [dyn_slice(a75!f1_in). By evaluating the above expression in a recursive manner, we get the final dynamic slice consisting of the statements corresponding to the nodes m2, s3, s4, s5, m7, s8, s10, s11,m13,s14,m20,s21,m27,s28,s39,m40,s41,m43, s44, s45, s46, s47, s49, m51, s52, s53, s54, s55, s57, m59,s60,s61,s62,m67,s68,m69,s70,p72,a73,s74, a75, s76, s78, p81, a82, s83, a84, s85. These are indi- cated as bold vertices in Figure 9 and the corresponding statements are indicated in rectangular boxes in Figure 10. Similarly, dynamic slice with respect to any slicing crite- rion can be computed using FANMDS algorithm. 5 Implementation This section briefly describes the implementation of FAN- MDS algorithm. A dynamic slicing tool has been devel- oped to implement the algorithm which has been named feature-aspect dynamic slicing tool (FADST). Figure 11 depicts the architectural design of the slicing tool FADST. The working of our slicing tool is depicted in Figure 12, through a flow chart. In Figure 11, the executable components are depicted in rectangular boxes and the passive components are de- picted in ellipses. First, the features required to compose and aspects to be captured are selected. The selected fea- tures, the selected aspects, and the slicing criterion con- sisting of input, line number, and variable are provided to FADST through the Graphical User Interface (GUI) com- ponent. The Dynamic Slicer component interacts with the GUI component and produces the required result as output back to GUI. The AHEAD composer [2] composes the se- lected features to generate a set of Java programs. These Java programs and the selected aspects are fed to AspectJ composer. AspectJ composer weaves the aspects at the ap- propriate join points, and the result is a composed AspectJ program. The lexical analyzer component reads the com- posed AspectJ program and generates tokens from these programs. Upon encountering a useful token, the lexical analyzer component returns the token along with its type to the parser and semantic analyzer component. The parser and semantic analyzer component takes the token and ana- lyzes it using the grammatical rules designed for the input programs. The code instrumentor component instruments the com- posed AspectJ programs. The classes are instrumented with line numbers prefixed with c, the aspects are instru- mented with line numbers prefixed with as, the methods are instrumented with line numbers prefixed with m, the pointcuts are instrumented with line numbers prefixed with p, the advices are instrumented with line numbers prefixed with a, and the statements containing assignments, com- putations, predicates are instrumented with line numbers prefixed withs. The CFADG constructor component constructs the CFADG using the required program analysis information such as type of statement, sets of variables defined or used at a statement etc. The dynamic slicer component imple- ments the FANMDS algorithm. We have used Java lan- guage for our implementation. A compiler writing tool, ANTLR (Another Tool for Language Recognition) 5 , has been used for lexical analyzer, parser and semantic ana- lyzer components of FADST. An adjacency matrix adj[][] has been used for stor- ing the CFADG with respect to a selected composition of features of the given feature-oriented program. Arrays are used to store the sets Defn(v), Usage(v), RecDefn(v), and dyn_slice(u). 5 www.antlr.org Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 211 Figure 9: CFADG showing statements included in dynamic slice as bold nodes 212 Informatica 44 (2020) 199–224 M. Sahu et al. (a) calc.jak (b) test.jak (c) error.aj (d) print.aj Figure 10: Dynamic slice with respect to slicing criterion depicted as statements in rectangular boxes Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 213 Figure 11: Architecture of the slicing tool Figure 12: Flowchart for working of the slicing tool given in Figure 11 Figure 13: CFADG generation time and Average slice com- putation time for Calculator Product Line 5.1 Case studies and experimental results We have applied our algorithm to some product lines 6,7 . We have also taken some open-source Java programs 8 9 10 . We have developed few product lines by identifying vari- ous features and converting these available Java programs into corresponding Jak programs. It may be noted that Jak is one of the feature-oriented programming languages. We have also taken the models of few product lines (such as calculator product line, stack product line, graph product line) from the work of different researchers [45, 44, 43, 46] and developed the corresponding Jak programs. These may be considered as representative feature-oriented programs with aspect-oriented extensions. In all the product lines, we have identified the aspects that are scattered through- out the program. The product lines we have taken as our case studies have various features and aspects which can be used for composing a variety of software product lines. We have taken fifteen product lines as our case studies. The characteristics of our software product lines are depicted in Table 1. These programs are executed for different compo- sitions of features with different aspects weaved for differ- ent inputs. Also, the algorithm has been tested for different slicing criteria for different compositions of features and different inputs. The CFADG generation time and average slice compu- tation time for various compositions of features in different product lines are depicted in Figures 13–27. It can be inferred from Figures 13–27 that different com- positions of features result in different slice computation times. The aspects weaved at more number of join points take more time than the aspects weaved at less number of join points. For example, in Calculator Product Line (CPL), the number of join points where the aspect Print is weaved is more than that of aspect Error. That’s why the slice computation time for the program where Print aspect 6 http://spl2go.cs.ovgu.de/projects 7 http://www.infosun.fim.uni-passau.de/spl/ apel/fh 8 http://www.sanfoundry.com/ java-program-implement-avl-tree/ 9 http://www.geeksforgeeks.org/ avl-tree-set-2-deletion/ 10 https://ankurm.com/implementing-singly-linked-list-in-java/ 214 Informatica 44 (2020) 199–224 M. Sahu et al. Table 1: List of Case Study Software Product Lines Sl. No. Name of Product Line Description Total No. of Features Supported Total No. of Aspects weaved Total No. of lines in composed AspectJ file Mandatory Optional Mandatory Optional 1 Calculator Product Line (CPL) Calculates the factorial, square root and logarithmic value with base 10 of a num- ber. 2 (Base, Print) 3 (sqrt, log, fact) 1 (Error) 1 (Print) 85 2 Stack Product Line (SPL) Models variations of stacks. 1 (Stack) 3 (Counter, Lock, Undo) 1 (Size) 1 (Top) 130 3 Graph Product Line Models variability for different types of graphs such as colored, weighted etc. 1 (Base) 4 (Weight, Color, Re- cursive, PrintHeader) 1 (Print) 1 (AddNode) 150 4 A VL Tree Product Line (A VLTPL) Simulates the various operations on an A VL tree. 2 (Base, Display) 4 (Insert, Delete, Count, Search) 1 (ComputeHeight 1 (Rotate) 315 5 Single Linked List Product Line (SLLPL) Simulates the various operations on a sin- gle linked list. 2 (Base, Display) 7 (InsertBegin, In- sertEnd, InsertAfter, DeleteBegin, Dele- teEnd, DeleteAfter, Count) 2 (Insert) 0 195 6 DesktopSearcher Program for indexing and content based searching in files 7 9 3 4 2516 7 TankWar A Game 12 19 6 7 3746 8 GPL Graph and algorithm library 12 24 5 12 801 9 MobileMedia MobileMedia is a Software Product Line (SPL) that manipulates photo, music, and video on mobile devices. It is a multimedia management for phones 10 37 5 10 4669 10 Digraph A library for representing and manipulat- ing directed graph structures. Beside ba- sic graphs, it supports various operations such as removal, traversal, and transposi- tion, implemented as optional features. 1 3 1 2 1733 11 Elevator Simulates various operations of an Elevator 3 3 2 1 873 12 Vistex VisTex is a product line that features graph- ical manipulation of graphs and their tex- tual representation. It is designed to be eas- ily extendible for specific graph-based ap- plications such as UML. 5 11 2 3 1890 13 Violet Graphical model editor 15 73 6 9 9203 14 Notepad Graphical text editor 6 7 3 3 1672 15 PkJab Instant messaging client for Jabber. 3 5 2 2 3963 Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 215 Figure 14: CFADG generation time and Average slice com- putation time for Stack Product Line Figure 15: CFADG generation time and Average slice com- putation time for Graph Product Line Figure 16: CFADG generation time and Average slice com- putation time for A VL Tree Product Line Figure 17: CFADG generation time and Average slice computation time for Single Linked List Product Line 216 Informatica 44 (2020) 199–224 M. Sahu et al. Figure 18: CFADG generation time and Average slice com- putation time for DesktopSearcher Figure 19: CFADG generation time and Average slice com- putation time for TankWar Figure 20: CFADG generation time and Average slice com- putation time for GPL Figure 21: CFADG generation time and Average slice com- putation time for MobileMedia Figure 22: CFADG generation time and Average slice com- putation time for Digraph Figure 23: CFADG generation time and Average slice com- putation time for Elevator Figure 24: CFADG generation time and Average slice com- putation time for Vistex Figure 25: CFADG generation time and Average slice com- putation time for Violet Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 217 Figure 26: CFADG generation time and Average slice com- putation time for Notepad Figure 27: CFADG generation time and Average slice com- putation time for PkJab is weaved is more than that of the program where Error as- pect is weaved. The features containing more number of loops take more time. The composed features containing less number of executable statements take less time com- pared to those containing more number of executable state- ments. 6 Comparison with related work Several works have been carried out on slicing of procedure-oriented programs [34, 32, 33, 30, 47], object- oriented programs [11, 21, 39, 22, 15], aspect-oriented pro- grams [37, 9, 10, 16, 18, 23]. But very, few work have been carried out on slicing of feature-oriented programs [35]. Zhao [9] was the first to develop a two-phase slicing algorithm to compute static slices of aspect-oriented pro- grams. Later, Zhao et al. [10] developed an efficient algo- rithm for constructing system dependence graph for aspect- oriented programs. Ray et al. [16] developed an algo- rithm to compute dynamic slices of aspect-oriented pro- grams by constructing Aspect System Dependence Graph (AOSG). They had introduced a new logical node called C- node to capture communication dependencies among the non-aspect code and aspect code. They had also intro- duced a new arc called aspect-membership arc to connect the dependence graphs of the non-aspect code and aspect code. They had not shown the actual parameters in the pointcuts. Singh et al. [18] proposed a method to com- pute slices depending upon the slice point location in the program. Their computed slice was an executable slice. Munjal et al. [23] automated the generation of system de- pendence graphs (SDG) for aspect-oriented programs by analysing the bytecode of aspect-oriented programs. Then, they proposed a three-phase slicing algorithm to compute static slices using the intermediate graph for a given aspect- oriented program. All the above works [9, 15, 16, 18, 23] have not considered feature-oriented programs. Apel et al. [3] presented a novel language for FOP in C++ namely FeatureC++. They also mentioned few prob- lems of FOP languages. Apel et al. [4] demonstrated FeatureC++ along with its adaptation to Aspect-Oriented Programming (AOP) concepts. They discussed the use of FeatureC++ in solving various problems related to incre- mental software development using AOP concepts. They also discussed the weaknesses of FOP for modularization of crosscutting concerns. Apel et al. [5] discussed the lim- itations of crosscutting modularity and the missing support of C++. They also focused on solutions for ease evolv- ability of software. Batory [2] presented basic concepts of FOP and a subset of the tools of the Algebraic Hier- archical Equations for Application Design (AHEAD) tool suite. Apel et al. [7] presented an overview of feature- oriented software development (FOSD) process. They had identified various key issues in different phases of FOSD. Thum et al. [6] developed an open source framework for FOSD namely FeatureIDE that supported all phases of FOSD along with support for feature-oriented pro- gramming languages, and delta-oriented programming lan- guages, aspect-oriented programming languages. Pereira et al. [20] discussed the findings of SPL management tools from a Systematic Literature Review (SLR). These works [7, 5, 3, 4, 2, 20, 6] discussed only the programming and development aspects of FOP and did not consider the slic- ing aspects. We have presented a technique for dynamic slicing of feature-oriented programs with aspect-oriented extensions using Jak as the FOP language. Very few work have been carried out on slicing of feature-oriented programs [35]. Sahu et al. [35] suggested a technique to compute dynamic slices of feature-oriented programs. Their technique first composed the selected fea- tures of feature-oriented programs. Then, they used an exe- cution trace file and a dependence-based program represen- tation namely dynamic feature-oriented dependence graph (DFDG). The dynamic slice was computed by traversing DFDG in breadth-first or depth-first manner and mapping the traversed vertices to the program statements. They had missed some of the dependences such as mixn call edge, re- finement edge, and mixin return dependence edge, etc. that might arise in feature-oriented programs. The drawback of their approach is the use of execution trace file which may lead to more slice computation time. They had not consid- ered the aspect-oriented extensions of feature-oriented pro- grams. In our approach, we have not used any execution trace file. Usually, the execution trace file is used to store the execution history of each executed statement for a given input. Much time is required to store and retrieve the exe- cuted statements. The statements are then used for calcula- tion of dynamic slice for each statement. Thus, extra time is required to perform I/O operations on an execution trace 218 Informatica 44 (2020) 199–224 M. Sahu et al. file. We do not use any execution trace file. During exe- cution of the program for a given input, the dynamic slice for each statement is computed by marking and unmarking process. Thus, there is no requirement of any execution trace file for storing the executed statements. So, our pro- posed approach does not take any extra time to read from or write into the execution trace file, thereby reducing the slice extraction time. Also, we have considered the aspects that are scattered throughout the code. Our algorithm does not create any new node in the intermediate representation CFADG during runtime. This results in faster computation of slices. 7 Conclusion and future work We have presented an approach to compute dynamic slices of feature-oriented programs with aspect-oriented exten- sions. The features required for composition are first se- lected and composed using Algebraic Hierarchical Equa- tions for Application Design (AHEAD) composer. Then, the aspects are weaved into the generated composed Java program using AspectJ composer to produce the resultant AspectJ program. The intermediate dependence based rep- resentation of the program containing Jak code and AspectJ code is constructed and it is called Composite Feature- Aspect Dependence Graph (CFADG). The program is exe- cuted for an input. During execution, the nodes of CFADG are marked and unmarked according to our feature-aspect node marking dynamic slicing (FANMDS) algorithm. We have developed a tool to implement our FANMDS algo- rithm and named it FADST. Our tool FADST computes the dynamic slices and the average slice extraction times for various compositions of features and aspects weaved for various product lines. Currently, our tool is able to han- dle various compositions for few product lines with few aspects captured. Also, current evaluation only uses prim- itive feature-oriented programs. In future, we will extend our tool to handle more number of product lines with more number of compositions. Our algorithm may easily be extended to compute dy- namic slices of other feature-oriented languages like Fea- tureC++, FeatureRuby, FeatureHouse, Fuji, etc. Also, the extension of the algorithm can be used to compute con- ditioned slices, amorphous slices for feature-oriented pro- grams with various aspects captured. We will also find out the differences in the performance of different aspects. References [1] Christian Prehofer (1997) Feature-Oriented Program- ming: A Fresh Look at Objects, Proceedings of 11th European Conference on Object-Oriented Programming (ECOOP), Springer, Berlin, Hei- delberg, pp. 419–443. https://doi.org/10. 1007/bfb0053389 [2] Don Batory (2006) A Tutorial on Feature–Oriented Programming and the AHEAD Tool Suite, Proceed- ings of the 2005 International Conference on Gen- erative and Transformational Techniques in Software Engineering (GTTSE’05), Springer–Verlag, Berlin, Heidelberg, pp. 3–35. https://doi.org/10. 1007/11877028_1 [3] Sven Apel and Thomas Leich and Marko Rosen- muller and Gunter Saake (2005) FeatureC++: Feature-Oriented and Aspect-Oriented Programming in C++, Tech. rep., Department of Computer Science, Otto-von-Guericke University, Magdeburg, Germany. [4] Sven Apel and Thomas Leich and Marko Rosen- muller and Gunter Saake (2005) FeatureC++: On the Symbiosis of Feature-Oriented and Aspect-Oriented Programming Proceedings of the International Con- ference on Generative Programming and Compo- nent Engineering (GPCE’05), Springer, pp. 125–140. https://doi.org/10.1007/11561347_10 [5] Sven Apel and Thomas Leich and Marko Rosen- muller and Gunter Saake (2005) Combining Feature- Oriented and Aspect-Oriented Programming to Sup- port Software Evolution, Proceedings of the 2nd ECOOP Workshop on Reflection, AOP and Meta- Data for Software Evolution (RAM-SE), School of Computer Science, University of Magdeburg, July, pp. 3–16. [6] Thomas Thum and Christian Kastner and Fabian Benduhn and Jens Meinicke and Gunter Saake and Thomas Leich (2014) FeatureIDE: An ex- tensible framework for feature-oriented software development, Science of Computer Programming, 79, pp. 70–85. https://doi.org/10.1016/ j.scico.2012.06.002 [7] Sven Apel and Christian Kastner (2009) An Overview of Feature-Oriented Software Develop- ment. Journal of Object Technology, 8(5), pp. 49–84, July–August. https://doi.org/10. 5381/jot.2009.8.5.c5 [8] Gregor Kiczales and John Irwin and John Lamp- ing and Jean Marc Loingtier and Cristiana Videira Lopes and Chris Maeda and Anurag Mendhekar (1997) Aspect-Oriented Programming, Proceedings of the European Conference on Object-Oriented Pro- gramming (ECOOP), Finland, June, pp. 220–242. https://doi.org/10.1007/bfb0053381 [9] Jianjun Zhao (2002) Slicing Aspect-Oriented Soft- ware, Proceedings of 10th International Workshop on Program Comprehension, pp. 251–260, June. https://doi.org/10.1109/wpc.2002. 1021346 Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 219 [10] Jianjun Zhao and Martin Rinard (2003) System De- pendence Graph Construction for Aspect-Oriented Programs. Technical report, Laboratory for Com- puter Science, Massachusetts Institute of Technology, USA, March. [11] Loren Larsen and Mary Jean Harrold (1996) Slic- ing Object-Oriented Software, Proceedings of 18th International Conference on Software Engineering, pp. 495–505, March. https://doi.org/10. 1109/icse.1996.493444 [12] Timon Ter Braak (2006) Extending Program Slicing in Aspect–Oriented Programming With Inter–Type Declarations, 5th TSConIT Program, June. [13] Aspect Oriented Programming. www.wikipedia.org. [14] Hiralal Agrawal and Joseph R. Horgan (1990) Dy- namic Program Slicing, ACM SIGPLAN Notices, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementa- tion PLDI’90, 25(6), pp. 246–256, June. https: //doi.org/10.1145/93542.93576 [15] Durga Prasad Mohapatra and Rajib Mall and Rajeev Kumar (2004) An Edge Marking Tech- nique for Dynamic Slicing of Object-Oriented Pro- grams, Proceedings of the 28th Annual Interna- tional Computer Software and Applications Confer- ence (COMPSAC’04). https://doi.org/10. 1109/cmpsac.2004.1342806 [16] Abhisek Ray and Siba Mishra and Durga Prasad Mo- hapatra (2012) A Novel Approach for Computing Dynamic Slices of Aspect-Oriented Programs, Inter- national Journal of Computer Information Systems, 5(3),pp. 6–12, September. [17] Abhisek Ray and Siba Mishra and Durga Prasad Mo- hapatra (2013) An Approach for Computing Dynamic Slice of Concurrent Aspect-Oriented Programs Inter- national Journal of Software Engineering and Its Ap- plications, 7(1), pp. 13–32, January. [18] Jagannath Singh and Durga Prasad Mohapatra (2013) A Unique Aspect-Oriented Program Slicing Tech- nique, Proceedings of International Conference on Advances in Computing, Communications and Infor- matics (ICACCI’13), pp. 159–164.https://doi. org/10.1109/icacci.2013.6637164 [19] Jagannath Singh and Dishant Munjal and Durga Prasad Mohapatra (2014) Context Sensitive Dynamic slicing of Concurrent Aspect-Oriented Programs, Proceedings of 21st Asia-Pacific Software Engineer- ing Conference (APSEC’14), pp. 167–174. https: //doi.org/10.1109/apsec.2014.35 [20] Juliana Alves Pereira and Kattiana Constantino and Eduardo Figueiredo (2015) A Systematic Litera- ture Review of Software Product Line Management Tools, Proceeddings of 14th International Confer- ence on Software Reuse (ICSR’15), Berlin Heidel- berg, pp. 73–89.https://doi.org/10.1007/ 978-3-319-14130-5_6 [21] Durga Prasad Mohapatra and Rajeev Kumar and Rajib Mall and D. S. Kumar and Mayank Bhasin (2006) Distributed dynamic slicing of Java pro- grams, Journal of Systems and Software, 79(12), pp. 1661–1678. https://doi.org/10.1016/ j.jss.2006.01.009 [22] Durga Prasad Mohapatra and Rajib Mall and Ra- jeev Kumar (2005) Computing dynamic slices of concurrent object-oriented programs, Information & Software Technology, 47(12), pp. 805–817. https://doi.org/10.1016/j.infsof. 2005.02.002 [23] Dishant Munjal and Jagannath Singh and Subhrakanta Panda and Durga Prasad Moha- patra (2015) Automated Slicing of Aspect- Oriented Programs using Bytecode Analysis, Proceedings of IEEE 39th Annual International Computers, Software & Applications Confer- ence (COMPSAC 2015), pp. 191–199. https: //doi.org/10.1109/compsac.2015.98 [24] Madhusmita Sahu and Durga Prasad Mohapatra (2007) A Node-Marking Technique for Dynamic Slicing of Aspect-Oriented Programs, Proceedings of 10th International Conference on Information Tech- nology (ICIT 2007), pp. 155–160. https://doi. org/10.1109/icit.2007.70 [25] Diganta Goswami and Rajib Mall (1999) Fast Slicing of Concurrent Programs, Proceedings of 6th Inter- national Conference on High Performance Comput- ing (HiPC 1999), pp. 38–42.https://doi.org/ 10.1007/978-3-540-46642-0_6 [26] Diganta Goswami and Rajib Mall (2000) Dynamic Slicing of Concurrent Programs, Proceedings of 7th International Conference on High Performance Com- puting (HiPC 2000), pp. 15–26. https://doi. org/10.1007/3-540-44467-x_2 [27] Jaiprakash T. Lallchandani and Rajib Mall (2011) A Dynamic Slicing Technique for UML Architectural Models, IEEE Transactions on Software Engineer- ing, 37(6), pp. 737–771.https://doi.org/10. 1109/tse.2010.112 [28] Philip Samuel and Rajib Mall (2009) Slicing- based test case generation from UML activity dia- grams, ACM SIGSOFT Software Engineering Notes, 34(6), pp. 1–14. https://doi.org/10.1145/ 1640162.1666579 220 Informatica 44 (2020) 199–224 M. Sahu et al. [29] Jaiprakash T. Lallchandani and Rajib Mall (2010) Integrated state-based dynamic slicing technique for UML models, IET Software, 4(1), pp. 55– 78. https://doi.org/10.1049/iet-sen. 2009.0080 [30] G. B. Mund and Rajib Mall (2006) An efficient in- terprocedural dynamic slicing method, The Journal of Systems and Software, 79, pp. 791–806. https: //doi.org/10.1016/j.jss.2005.07.024 [31] Diganta Goswami and Rajib Mall (2004) A parallel algorithm for static slicing of concurrent programs, Concurrency – Practice and Experience, 16(8), pp. 751–769. https://doi.org/10.1002/cpe. 789 [32] G. B. Mund and R. Mall and S. Sarkar (2003) Computation of intraprocedural dynamic program slices, Information and Software Technology, 45 (8), pp. 499–512. https://doi.org/10.1016/ S0950-5849(03)00029-6 [33] G. B. Mund and R. Mall and S. Sarkar (2002) An efficient dynamic program slicing technique, Information and Software Technology, 44 (2), pp. 123–132. https://doi.org/10.1016/ s0950-5849(01)00224-5 [34] Diganta Goswami and Rajib Mall (2002) An ef- ficient method for computing dynamic program slices, Information Processing Letters, 81(2), pp. 111–117. https://doi.org/10.1016/ s0020-0190(01)00202-2 [35] Madhusmita Sahu and Durga Prasad Mohapatra (2016) Dynamic Slicing of Feature-Oriented Pro- grams, Proceedings of 3rd International Conference on Advanced Computing, Networking and Informat- ics (ICACNI 2015), pp. 381–388. https://doi. org/10.1007/978-81-322-2529-4_40 [36] Mark Weiser (1981) Program Slicing, Proceedings of the 5th International Conference on Software Engi- neering (ICSE), pp. 439–449. IEEE Computer Soci- ety, March. [37] Durga Prasad Mohapatra and Madhusmita Sahu and Rajib Mall and Rajeev Kumar (2008) Dynamic Slicing of Aspect–Oriented Programs, Informatica, 32(3), pp. 261–274. [38] Jaiprakash T. Lallchandani and Rajib Mall (2005) Computation of Dynamic Slices for Object-Oriented Concurrent Programs, Proceedings of Asia Pa- cific Software Engineering Conference (APSEC 2005), pp. 341–350. https://doi.org/10. 1109/apsec.2005.51 [39] Jianjum Zhao (1998) Dynamic Slicing of Object– Oriented Programs, Technical report, Information Processing Society of Japan, pp. 1–7, May. [40] Sebastian Gunther and Sagar Sunkle (2009) Feature- Oriented Programming with Ruby. In Proceedings of the First International Workshop on Feature-Oriented Software Development (FOSD’09), pp. 11–18, Octo- ber. https://doi.org/10.1145/1629716. 1629721 [41] Sebastian Gunther and Sagar Sunkle (2012) rbFea- tures: Feature-oriented programming with Ruby, Sci- ence of Computer Programming, 77(3), pp. 152– 173, March. https://doi.org/10.1016/j. scico.2010.12.007 [42] Bogdan Korel and Satish Yalamanchili (1994) For- ward Computation Of Dynamic Program Slices, Proceedings of the 1994 ACM SIGSOFT interna- tional symposium on Software testing and analy- sis(ISSTA’94), pp. 66–79, August. https://doi. org/10.1145/186258.186514 [43] Sven Apel and Thomas Leich and Gunter Saake(2008) Aspectual Feature Modules, IEEE Transactions On Software Engineer- ing, 34(2),pp. 162–180, March/April. https: //doi.org/10.1109/tse.2007.70770 [44] Jia Liu and Don Batory and Srinivas Nedunuri (2005) Modeling Interactions in Feature-Oriented Software Designs, Proceedings of International Conference on Feature Interactions in Telecommunications and Soft- ware Systems (ICFI 2005), pp. 178–197. [45] Ian Adams and Sigmon Myers (2009) FOP and AOP: Benefits, Pitfalls and Potential for Interaction, pp. 1– 7. [46] Sagar Sunkle and Marko Rosenmuller and Norbert Siegmund and Syed Saif ur Rahman and Gunter Saake and Sven Apel (2008) Features as First-class Entities-Toward a Better Representation of Features. Proceedings of Workshop on Modularization, Com- position, and Generative Techniques for Product Line Engineering, pp. 27–34, October. [47] Susan Horwitz and Thomas Reps and David Bink- ley (1990) Inter-Procedural Slicing Using Depen- dence Graphs, ACM Transactions on Program- ming Languages and Systems, vol. 12, no. 1, pp. 26–60, January. https://doi.org/10.1145/ 77606.77608 Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 221 8 Appendices A Construction of CFADG Algorithm 8 Construction of CFADG Input: The feature-oriented program containing aspects with selected required features and weaved aspects. Output: The composite feature-aspect dependence graph (CFADG). 1: procedure CONSTRUCTPDG() 2: for start of a method do 3: Create method entry node. 4: for each executable statement in the program do 5: Create a node. 6: for all nodes created do 7: if noden 2 is under the scope of noden 1 then 8: Add control dependence edge fromn 1 ton 2 ,n 1 !n 2 . 9: if noden 1 controls the execution of noden 2 then 10: Add control dependence edge fromn 1 ton 2 ,n 1 !n 2 . 11: if noden 2 uses the value of a variable that is defined at node n 1 then 12: Add data dependence edge fromn 1 ton 2 ,n 1 !n 2 . 13: procedure CONSTRUCTMXDG() 14: for all methods in a mixin do 15: Call ConstructPDG(). 16: for entry of a mixin do 17: Create mixin entry node. 18: for each parameter present in the method call do 19: Create an actual-in parameter node. 20: for each parameter present in the method definition do 21: Create a formal-in parameter node. 22: for each parameter in the method call that is modified inside the method do 23: Create an actual-out parameter node. 24: for each actual-out parameter node do 25: Create corresponding formal-out parameter node. 26: for all nodes created do 27: if node x corresponds to mixin entry node and node y is a method entry node then 28: Add mixin membership edge fromx toy,x!y. 29: if noden 1 returns a value to the calling method at noden 2 within a mixin layer then 30: Add return dependence edge fromn 1 ton 2 ,n 1 !n 2 . 31: if noden 1 calls a method that is defined at noden 2 within a mixin layer then 32: Add call edge fromn 1 ton 2 ,n 1 !n 2 . 33: if noden 1 calls a method that is defined at noden 2 within a mixin layer by passing parameters then 34: Add call edge fromn 1 ton 2 ,n 1 !n 2 . 35: Add parameter-in edge from actual-in parameter node to corresponding formal-in parameter node. 36: Add parameter-out edge from formal-out parameter node to corresponding actual-out parameter node. 37: if noden 1 is an actual-in parameter node and noden 2 is an actual-out parameter node such that the value at noden 1 affects the value at noden 2 then 38: Add summary edge fromn 1 ton 2 ,n 1 !n 2 . 39: procedure CONSTRUCTSDG() 40: for all mixins within a mixin layer do 41: Call ConstructMxDG. 42: for all nodes created do 43: if nodex is a polymorphic method call then 44: Create polymorphic choice vertex. 45: if nodey is a polymorphic choice vertex then 46: Add a call edge fromx toy,x!y 47: if nodex is a new operator node and nodey is the correspond- ing constructor node then 48: Add call edge fromn 1 ton 2 ,n 1 !n 2 . 49: Add parameter-in edge from actual-in parameter node to corresponding formal-in parameter node. 50: Add parameter-out edge from formal-out parameter node to corresponding actual-out parameter node. 222 Informatica 44 (2020) 199–224 M. Sahu et al. 51: Remove mixin membership edges. 52: Remove mixin entry nodes. 53: procedure CONSTRUCTADG() 54: for start of an advice do 55: Create advice start vertex. 56: if advice contains parameters then 57: Create formal-in and formal-out parameter nodes. 58: for all nodes created do 59: if noden 2 is under the scope of noden 1 then 60: Add control dependence edge fromn 1 ton 2 ,n 1 !n 2 . 61: if noden 1 controls the execution of noden 2 then 62: Add control dependence edge fromn 1 ton 2 ,n 1 !n 2 . 63: if noden 2 uses the value of a variable that is defined at node n 1 then 64: Add data dependence edge fromn 1 ton 2 ,n 1 !n 2 . 65: procedure CONSTRUCTIDG() 66: for entry of introduction do 67: Create introduction start vertex. 68: if introduction is a method or constructor then 69: Call ConstructPDG. 70: if introduction is a field then 71: Do nothing. 72: procedure CONSTRUCTPTDG() 73: for entry of pointcut do 74: Create pointcut start vertex. 75: if pointcut contains parameters then 76: Create actual-in and actual-out parameter nodes. 77: procedure CONSTRUCTASDG() 78: for entry of an aspect do 79: Create aspect start vertex. 80: for all advices in an aspect do 81: Call ConstructADG(). 82: for all pointcuts in an aspect do 83: Call ConstructPtDG(). 84: for all introductions in an aspect do 85: Call ConstructIDG(). 86: for all nodes created do 87: if nodex is aspect start vertex then 88: if nodey is advice start vertex then 89: Create aspect membership edge fromx toy,x!y. 90: if nodey is pointcut start vertex then 91: Create aspect membership edge fromx toy,x!y. 92: if nodey is introduction start vertex then 93: Create aspect membership edge fromx toy,x!y. 94: if nodex is pointcut start node and nodey is advice start node then 95: Create data dependence edge fromx toy,x!y. 96: Add parameter-in edge from actual-in parameter node to corresponding formal-in parameter node. 97: Add parameter-out edge from formal-out parameter node to corresponding actual-out parameter node. 98: procedure CONSTRUCTCFADG() 99: for each mixin layer do 100: Call ConstructSDG(). 101: for each aspect do 102: Call ConstructAsDG. 103: for all nodes created do 104: if noden 2 in one mixin layer uses the value of a variable that is defined at noden 1 in different mixin layer then 105: Add mixin data dependence edge fromn 1 ton 2 ,n 1 ! n 2 . 106: if noden 2 in an aspect uses the value of a variable that is defined at noden 1 in a mixin then 107: Add aspect data dependence edge fromn 1 ton 2 ,n 1 ! n 2 . 108: if noden 1 in one mixin layer returns a value to the calling method at noden 2 in different mixin layer then 109: Add mixin return dependence edge fromn 1 ton 2 ,n 1 ! n 2 . 110: if noden 1 in one mixin layer calls a method that is defined at noden 2 in different mixin layer then 111: Add mixin call edge fromn 1 ton 2 ,n 1 !n 2 . 112: Add parameter-in and parameter-out edges. 113: if noden 1 calls a method that is defined at noden 2 using Super() method then 114: Add refinement edge fromn 1 ton 2 ,n 1 !n 2 . 115: if noden 1 is an output statement followed by noden 2 and node n 2 is an input, a computation, a predicate, or a method call statement then 116: Add message dependence edge from n 1 to n 2 , n 1 ! n 2 . 117: if node n 1 is a method call node and node n 2 is a before advice node capturing the method called atn 1 then 118: Add weaving edge fromn 1 ton 2 ,n 1 !n 2 . 119: if noden 1 is the last statement in a before advice and node n 2 is the method entry node of the method captured by the advice then 120: Add weaving edge fromn 1 ton 2 ,n 1 !n 2 . 121: if node y is an after advice node and node n 1 is the last statement in the method captured by noden 2 then 122: Add weaving edge fromn 1 ton 2 ,n 1 !n 2 . 123: if noden 1 is the last statement in an after advice and node n 2 is the statement followed by method call node and the method is captured by the advice then 124: Add weaving edge fromn 1 ton 2 ,n 1 !n 2 . 125: Remove aspect membership edges. 126: Remove aspect entry vertices. Computing Dynamic Slices of Feature-Oriented Programs with. . . Informatica 44 (2020) 199–224 223 B Feature-aspect node-marking dynamic slicing (FANMDS) algorithm Algorithm 9 Feature-Aspect Node Marking Dynamic Slic- ing (FANMDS) Algorithm INPUT: Composite Feature-Aspect Dependence Graph (CFADG) of the programFP , Slicing criterion. OUTPUT: List of nodes contained in required dynamic slice. 1: Marked = . Initially, unmark all nodes of CFADG. 2: Setdyn_slice(u) = .u is a node in CFADG. 3: SetRecDefn(v) =NULL . v is a variable. 4: Execute the programFP for inputi. 5: whileFP does not terminate do 6: Updatedyn_slice(u) =fu;e 1 ;e 2 ;:::;e k g[dyn_slice(e 1 )[ dyn_slice(e 2 )[:::[dyn_slice(e k ) 7: Marked =Marked[fug. . Mark node u. 8: ifu is aDefn(v) node then 9: Marked =MarkednfRecDefn(v)g. . Unmark the node RecDefn(v). 10: RecDefn(v) =u. . Update RecDefn(v). 11: ifu is a method call node for a methodM then 12: panode M =f(M;panode). 13: Me M =g(M;Me). 14: pfnode M =h(M;pfnode). 15: Marked =Marked[fug. . Mark node u. 16: Marked =Marked[panode M . . Mark associated actual parameter nodes. 17: Marked =Marked[fMe M g. . Mark corresponding method entry node. 18: Marked =Marked[pfnode M . . Mark associated formal parameter nodes. 19: ifu is anew operator node for a constructorM then 20: panode M =f(M;panode). 21: Me M =g(M;Me). 22: pfnode M =h(M;pfnode). 23: Marked =Marked[fug. . Mark node u. 24: Marked =Marked[panode M . . Mark associated actual parameter nodes. 25: Marked =Marked[fMe M g. . Mark corresponding method entry node. 26: Marked =Marked[pfnode M . . Mark associated formal parameter nodes. 27: ifu is a polymorphic node for a virtual methodM then 28: panode M =f(M;panode). 29: Me M =g(M;Me). 30: pfnode M =h(M;pfnode). 31: Marked =Marked[fug. . Mark nodeu. 32: Marked =Marked[panode M . . Mark associated actual parameter nodes. 33: Marked =Marked[fMe M g. . Mark corresponding method entry node. 34: Marked =Marked[pfnode M . . Mark associated formal parameter nodes. 35: ifu is a mixin call node for a methodM then 36: panode M =f(M;panode). 37: Me M =g(M;Me). 38: pfnode M =h(M;pfnode). 39: Marked =Marked[fug. . Mark node u. 40: Marked =Marked[panode M . . Mark associated actual parameter nodes. 41: Marked =Marked[fMe M g. . Mark corresponding method entry node. 42: Marked =Marked[pfnode M . . Mark associated formal parameter nodes. 43: ifu is aSuper() method call node for a methodM then 44: Me M =h(M;Me). 45: Marked =Marked[fug. . Mark node u. 46: Marked =Marked[fMe M g. . Mark corresponding method entry node. 47: ifu is a pointcut node then 48: badv P =x(P;badv). 49: aadv P =y(P;aadv). 50: panode P =f(P;panode). 51: pfnode M =g(M;pfnode). 52: Marked =Marked[fug. . Mark node u. 53: Marked =Marked[panode M . . Mark corresponding actual parameter nodes. 54: Marked =Marked[pfnode M . . Mark corresponding formal parameter nodes. 55: Marked =Marked[badv P . . Mark the corresponding before advice entry node. 56: Marked =Marked[aadv P . . Mark the corresponding after advice entry node. 57: if u is an advice entry node for an advice A corresponding to pointcutP then 58: bbadv A =z(A;badv P ). 59: baadv A =z(A;aadv P ). 60: Marked =Markednbbadv A . 61: Marked =Markednbaadv A . . Unmark all nodes in body of advice corresponding to previous execution of u. 62: pfnode M =g(M;pfnode). 63: Marked =Markednpfnode M . . Unmark all the formal parameter nodes associated withu corresponding to previous execution of u. 224 Informatica 44 (2020) 199–224 M. Sahu et al. 64: ifu is an introduction node such thatu is a method then 65: Mb M =k(M;Mb). 66: Marked =MarkednMb M . . Unmark all the nodes in the method body corresponding to previous execution of u. 67: pfnode M =g(M;pfnode). 68: Marked =Markednpfnode M . . Unmark all the formal parameter nodes associated withu corresponding to previous execution of u. 69: ifv is method call node corresponding to previous execution ofu then 70: Marked =Markednv. . Unmark the method call node corresponding to previous execution of u. 71: panodev =f(v;panode). 72: Marked =Markednpanodev . . Unmark the asso- ciated actual parameter nodes for a method call node corresponding to previous execution of u. 73: pfnode M =h(M;pfnode). 74: Marked =Marked[fug. . Mark node u. 75: Marked =Marked[pfnode M . . Mark associated formal parameter nodes. 76: ifu is an introduction node such thatu is a field then 77: Marked =Marked[fDefn(v)g.. Mark Defn(v) node. 78: Marked =Marked[fUsage(v)g. . Mark Usage(v) node. 79: ifu is a method entry node for a methodM then 80: Mb M =k(M;Mb). 81: Marked =MarkednMb M . . Unmark all the nodes in the method body corresponding to previous execution of u. 82: pfnode M =g(M;pfnode). 83: Marked =Markednpfnode M . . Unmark all the formal parameter nodes associated withu corresponding to previous execution of u. 84: ifv is method call node corresponding to previous execution ofu then 85: Marked =Markednv. . Unmark the method call node corresponding to previous execution of u. 86: panodev =f(v;panode). 87: Marked =Markednpanodev . . Unmark the asso- ciated actual parameter nodes for a method call node corresponding to previous execution of u. 88: ifu is a mixin entry node for a methodM then 89: Mb M =k(M;Mb). 90: Marked =MarkednMb M . . Unmark all the nodes in the method body corresponding to previous execution of u. 91: pfnode M =g(M;pfnode). 92: Marked =Markednpfnode M . . Unmark all the formal parameter nodes associated withu corresponding to previous execution of u. 93: ifv is method call node corresponding to previous execution ofu then 94: Marked =Markednv. . Unmark the method call node corresponding to previous execution of u. 95: panodev =f(v;panode). 96: Marked =Markednpanodev . . Unmark the asso- ciated actual parameter nodes for a method call node corresponding to previous execution of u. 97: ifu isnew operator entry node for a constructorM then 98: Mb M =k(M;Mb). 99: Marked =MarkednMb M . . Unmark all the nodes in the method body corresponding to previous execution of u. 100: pfnode M =g(M;pfnode). 101: Marked =Markednpfnode M . . Unmark all the formal parameter nodes associated withu corresponding to previous execution of u. 102: ifv is method call node corresponding to previous execution ofu then 103: Marked =Markednv. . Unmark the method call node corresponding to previous execution of u. 104: panodev =f(v;panode). 105: Marked =Markednpanodev . . Unmark the asso- ciated actual parameter nodes for a method call node corresponding to previous execution of u. 106: for a given slicing command do 107: Look updyn_slice(u) for variablev. 108: Displaydyn_slice(u). 109: Map nodes indyn_slice(u) to corresponding statements in composed Java program. 110: Map statements included indyn_slice(u) in composed Java program to corresponding statements in composed Jak program. 111: Display statements included in dyn_slice(u) from com- posed Jak program.