Towards a time-e±cient algorithm to calculate the total number of products of a Software Product Line

Abstract

Feature Diagrams (FDs) are widely used to scope the domain of Software Product Lines (SPLs). In addition, valuable information can be inferred from FDs; for instance, the total number of possible products of a SPL. A common approach to calculate the number of products is translating FDs into propositional logic formulas, which are processed by o®-the-shelf tools, such as SAT solvers. However, this approach only works for small FDs. We think more scalable solutions can be reached avoiding the diagram-to-logic transformation and taking advantage of the tree organization of FDs. Due to the profusion of feature modeling notations, this paper formally de¯nes a pivot language, named Neutral Feature Tree (NFT), where FDs are restricted to be trees. Most popular FD notations can be easily and e±ciently translated to NFT. The paper also proposes a general and time-e±cient algorithm to calculate the number of products without considering crosstree constraints.

-

Software Product Line (SPL) practice has become an important and widely used approach for the e±cient development of complete portfolios of software products [ 17 ]. The domain of a SPL must be carefully scoped, identifying the common and variable requirements of its products and the interdependencies between requirements. In a bad scoped domain, relevant requirements may not be implemented, and some implemented requirements may never be used, causing unnecessary complexity and both development and maintenance costs [ 6 ]. To avoid these serious problems, SPL domains are usually modeled with variability languages.

Since FODA's feature modeling language was proposed in 1990 [ 14 ], a number of extensions and alternative languages have been devised to model variability in families of related systems: 1. As part of the following methods: FORM [ 15 ], FeatureRSEB [ 11 ], Generative

Programming [ 6 ], Software Product Line Engineering [ 17 ], PLUSS [ 7 ]. 2. In the work of the following authors: M. Riebisch et al. [ 19 ], J. van Gurp et al. [ 24 ], A. van Deursen et al. [ 23 ], H. Gomaa [ 9 ]. 3. As part of the following tools: Gears [ 3 ] and pure::variants [ 18 ].

Unfortunately, this profusion of languages hinders the e±cient communication among specialists and the portability of variability models between tools. In order to face this problem, P. Schobbens et al. [ 20, 13, 16 ] propose the Varied Feature Diagram+ (VFD+) as a pivot notation for variability languages. VFD+ is expressively complete and many variability languages can be easily and e±ciently translated into it.

D. Benavides [ 2 ] has surveyed a number of analysis operations that infer valuable information from feature diagrams. One these operations is calculating the total number of products of a SPL. This value is used by economic models, such as the Structured Intuitive Model for Product Line Economics (SIMPLE)[ 5 ] and the Constructive Product Line Investment Model (COPLIMO)[ 4 ], to estimate the SPL costs and bene¯ts. For instance, SIMPLE estimates the cost of building a SPL using equation 1, where: Corg expresses how much it costs for an organization to adopt the SPL approach, Ccab is the cost of developing the SPL core asset base3, n is the number of products of the SPL, Cunique(producti) is the cost of developing the unique parts of a product, and Creuse(producti) is the development cost of reusing core assets to build a product.

CSPL = Corg + Ccab + n X(Cunique(producti) + Creuse(producti)) i=1 (1)

The importance of knowing the number of products of a feature diagram is recognized by many commercial tools for SPL development, such as Gears and pure::variants, which provide the calculation without considering textual constraints between features 4. On the other hand, some researchers have proposed a full calculation, that includes textual constraints, by translating feature diagrams d into some kind of logic. For instance: { D. Batory [ 1 ] proposes a translation of d into propositional logic. Resulted formulas are processed by o®-the-shelf Logic-Truth Maintenance Systems and Boolean Satis¯ability (SAT) solvers. { D. Benavides [ 2 ] provides an abstract conversion of d into Constraint Satisfaction Problems (CSP). FaMa Tool Suite [ 22 ] adapts this abstract conversion to general CSP solvers, SAT solvers and Binary Decision Diagrams (BDD) solvers. 3 According to the SPL approach, products are built from a core asset base, a collection of artifacts that have been designed speci¯cally for reuse across the SPL. 4 Textual constraints will be explained in section 2.2. { Gheyi et al. [ 8 ] provides a translation of d into Alloy's logic. Internally, Alloy checks models by converting them into propositional logic and using o®-theshelf SAT solvers.

Unfortunately, the diagram-to-logic approach is only scalable for small feature diagrams. However, in SPLs with complex domains, companies have reported feature models with over 1000 features (e.g., M. Steger et al. [ 21 ] present a case study with 5200 features).

This paper proposes a time-e±cient algorithm to calculate the SPL number of products without considering textual constraints. Thus, we provide an upper bound for the number of products. In contrast with evaluated commercial tools, the algorithm is fully general and deals with a VFD+ subset, named Neutral Feature Tree (NFT), where diagrams are restricted to be trees5. This paper formally de¯nes NFT and demonstrates that NFT and VFD+ are completely equivalent. We think NFT is a good starting point for future implementations of analysis operations which take advantage of feature diagrams structured as trees.

The remainder of this paper is structured as follows. Section 2 formally de¯nes the abstract syntax and semantics of NFT. Section 3 presents the sketch of our algorithm6. Finally, section 4 summarizes the paper and outlines directions for future work. 2

An abstract notation for modeling SPL variability Section 2.1 outlines the main parts of a formal language; sections 2.2 and 2.3 de¯ne the abstract syntax and semantics of NFT, respectively; and ¯nally, section 2.4 demonstrates the equivalence between NFT and VFD+.

We emphasize NFT is not meant as a user language, but only as a formal \back-end" language used to de¯ne semantics and allow for automated processing. 2.1

Anatomy of a formal language

According to J. Green¯eld et al. [ 10 ], the anatomy of a formal language includes an abstract syntax, a semantics and one or more concrete syntaxes. 1. The abstract syntax of a language characterizes, in an abstract form, the kinds of elements that make up the language, and the rules for how those elements may be combined. All valid element combinations supported by an abstract syntax conform the syntactic domain L of a language.

5 VFD+ diagrams are single-rooted Directed Acyclic Graphs.

6 There is available an implementation of the algorithm on http://www.issi.uned.es/miembros/pagpersonales/ruben heradio/rheradio english.html 2. The semantics of a language de¯ne its meaning. According to D. Harel et al. [ 12 ], a semantic de¯nition consists of two parts: a semantic domain S and a semantic mapping M from the syntactic domain to the semantic domain.

That is, M : L ! S. 3. A concrete syntax de¯nes how the language elements appear in a concrete, human-usable form.

Following sections de¯ne NFT abstract syntax and semantics. Most variability languages may be considered as concrete syntaxes or \views" of NFT. 2.2 A NFT diagram d 2 LNFT is a tuple (N; §; r; DE; ¸; Á), where: 1. N is the set of nodes of d, among r is the root. Nodes are meant to represent features. The idea of feature is of widespread usage in domain engineering and it has been de¯ned as a \distinguishable characteristic of a concept (e.g., system, component and so on) that is relevant to some stakeholder of the concept" [ 6 ]. 2. § ½ N is the set of terminal nodes (i.e., the leaves of d). 3. DE µ N £N is the set of decomposition edges; (n1; n2) 2 DE is alternatively denoted n1 ! n2. If n1 ! n2; n1 is the parent of n2, and n2 is a child of n1. 4. ¸ : (N ¡§) ! card labels each non-leaf node n with a card boolean operator.

If n has children n1; :::; ns, cards[i::j](n1; :::; ns) evaluates to true if at least i and at most j of the s children of n evaluate to true. Regarding the card operator, the following points should be taken into account7: (a) whereas many variability notations distinguish between mandatory, optional, or and xor dependencies, card operator generalizes these categories. For instance, ¯gure 1 depicts equivalences between the feature notation proposed by K. Czarnecki et al. [ 6 ] and NFT. (b) whereas, in many variability notations, children nodes may have di®erent types of dependencies on their parent, in NFT all children must have the same type of dependency. This apparent limitation can be easily overcome by introducing auxiliary nodes. For instance, ¯gure 2 depicts the equivalence between a feature model and a NFT diagram. Node A has three children and two types of dependencies: A ! B is mandatory and (A ! C, A ! D) is a xor -group. In the NFT diagram, the di®erent types of dependencies are modeled by introducing the auxiliary node aux. 5. Á8 are additional textual constraints written in propositional logic over any type of node (Á 2 B(N )).

Additionally, d must satisfy the following constraints:

1. Only r has no parent: 8n 2 N ¢ (9n0 2 N ¢ n0 ! n) , n 6= r.

7 The same considerations are valid for VFD+. 8 also named cross-tree constraints [2].

2. d is a tree. Therefore,

(a) a node may have at most one parent:

8n 2 N ¢ (9n0; n00 2 N ¢ ((n0 ! n) ^ (n00 ! n) ) n0 = n00)) (b) DE is acyclic: @n1; n2 : : : ; nk 2 N ¢ n1 ! n2 ! : : : ! nk ! n1. 3. card operators are of adequate arities: 8n 2 N ¢(9n0 2 N ¢n ! n0) ) (¸(n) = cards)^(s = kf(n; n0)j(n; n0) 2 DEgk) Feature diagrams are meant to represent sets of products, and each product is seen as a combination of terminal features. Hence, the semantic domain of NFT is P(P(§)), i.e., a set of sets of terminal nodes.

The semantic mapping of NFT (MNFT : LNFT ! P(P(§))) assigns to every feature diagram d, a product line SPL, according to the next de¯nitions: 1. A con¯guration is a set of features, that is, any element of P(N ). A con¯guration c is valid for a d 2 LNFT, i®: (a) The root is in c (r 2 c). (b) The boolean value associated to the root is true. Given a con¯guration, any node of a diagram has associated a boolean value according to the following rules: i. A terminal node t 2 § evaluates to true if it is included in the con¯guration (t 2 c), else evaluates to false. ii. A non-terminal node n 2 (N ¡ §) is labeled with a card operator.

If n has children n1; :::; ns, cards[i::j](n1; :::; ns) evaluates to true if at least i and at most j of the s children of n evaluate to true. (c) The con¯guration must satisfy all textual constraints Á. (d) If a non-root node s(s 6= r) is in the con¯guration, one of its parents n, called its justi¯cation, must be too: 8s 2 N ¢ s 2 c ^ s 6= r ¢ 9n 2 N ¢ n 2 c ^ (n; s) 2 DE. 2. A product p, named by a valid con¯guration c, is the set of terminal features of c: p = c \ §. 3. The product line SPL represented by d 2 LNFT consists of the products named by its valid con¯gurations (SPL 2 P(P(§))). 2.4

Equivalence between NFT and VFD+ NFT di®erentiates from VFD+ in the following points: 1. Terminal nodes vs. primitive nodes. As noted by some authors [ 1 ], there is currently no agreement on the following question: are all features equally relevant to de¯ne the set of possible products that a feature diagram stands for? In VFD+, P. Schobbens et al. have adopted a neutral formalization: the modeler is responsible for specifying which nodes represent features that will in°uence the ¯nal product (the primitive nodes P ) and which nodes are just used for decomposition (N ¡ P ). P. Schobbens points that primitive nodes are not necessarily equivalent to leaves, though it is the most common case. However, a primitive node p 2 P , labeled with cards[i::j](n1; :::; ns), can always become a leaf (p 2 §) according to the following transformation TP !§ : (a) p is substituted by an auxiliary node aux1. (b) the children of aux1 are p and a new auxiliary node aux2. (c) aux1 is labeled with card2[2::2](p; aux2). (d) p becomes a leaf. aux2's children are the former children of p. (e) aux2 is labeled with the former cards[i::j](n1; :::; ns) of p.

Figure 3 depicts the conversion of a primitive non-leaf node B into a leaf node. 2. DAGs vs. trees. Whereas diagrams are trees in NFT, in VFD+ are DAGs.

Therefore, a node n with s parents (n1; :::; ns) can be translated into a node n with one parent n1 according to the following transformation TDAG!tree: (a) s ¡ 1 auxiliary nodes aux2; :::; auxs are added to the diagram. (b) edges n2 ! n; :::; ns ! n are replaced by new edges n2 ! aux2; :::; ns ! auxs. (c) D. Batory [ 1 ] demonstrated how to translate any edge a ! b into a propositional logic formula Áa;b. Using Batory's equivalences, implicit edges aux2 ! n; :::; auxs ! n are converted into textual constraints Áaux2;n:::Áauxs;n and are added to Á (Á0 ´ Á ^ Áaux2;n ^ ::: ^ Áauxs;n). Figure 4 depicts the conversion of a node D with two parents B and C into a node with a single parent.

In order to identify when a transformation on a diagram keeps (1) the diagram semantics and (2) the diagram structure, P. Schobbens [ 20 ] de¯nes the notion of graphical embedding. A graphical embedding is a translation T : L ! L0 that preserves the semantics of L and is node-controlled, i.e., T is expressed as a set of rules of the form d ! d0, where d is a diagram containing a de¯ned node or edge n, and all possible connections with this node or edge. Its translation d0 is a subgraph in L0, plus how the existing relations should be connected to nodes of this new subgraph. According to this de¯nition, TP !§ and TDAG!tree are graphical embeddings that guarantee the equivalency between NFT and VFD+. 3

Calculating the total number of products represented by an NFT diagram without considering textual constraints This section presents how to calculate the total number of products of a SPL modeled by a NFT diagram without considering textual constraints.

The number of products of a node n is denoted as P (n). Thus, the total number of products represented by a NFT diagram is P (r), where r is the root. For a leaf node l, P (l) = 1. Table 3 includes equations to calculate P (n) for a non-leaf node n that has s children ni of type mandatory (i.e., n is labeled with cards[s::s]), optional (cards[0::s]), xor (cards[1::1]) and or (cards[0::s]). Hence, time-complexity for calculating P (n) in these cases is O(s). Therefore, timecomplexity for computing P (r) is quadratic on the diagram number of nodes, i.e., O(N 2).

type of relationship equation mandatory (cards[s::s]) P (n) = Qs

i=1 P (ni) optional (cards[0::s]) P (n) = Qs

i=1 (P (ni) + 1) or (cards[1::s]) P (n) = (Qis=1 (P (ni) + 1)) ¡ 1 xor (cards[1::1]) P (n) = Ps i=1 P (ni) In general, when a node n has s children and is labeled with cards[low::high], P (n) is calculated by equation 2, where Sk is the number of products choosing any combination of k children from s. For the sake of clarity, let us denote P (n1); P (n2); : : : P (ns) as p1; p2; : : : ; ps. In a straightforward approach, Sk can be calculated by summing the number of products of all possible kcombinations (see equation 3). Unfortunately, this calculation has the following time-complexity C for P(r): O(N 2N ) µ C µ O(N 22N ). k=low

Sk (2)

Sk =

X pi1 pi2 : : : pik

A better time-complexity can be reached by using recurrent equations. The base case is S0 = 1. According to equation 3, S1 = Pis=1 pi. Calculating S2, the number of products for combinations of 2 siblings that include n1 is p1p2 + p1p3::: + p1ps = p1(p2 + p3 + ::: + ps) = p1(S1 ¡ p1). Similarly, the number of products of 2-combinations that include n2 is p2(S1 ¡ p2). Adding up every 2combinations, we get Ps

i=1 pi(S1 ¡ pi). However, in the sum each term pipj is being accounted for twice; once in the round for i and another in the round for j. Thus, removing the redundant calculus: (3) S2 == 1122 (PS1is=P1 spi(Sp1 ¡ pPi)is=1 pi2)

= 12 (S12 ¡ iP=1is=1i ¡pi2)

Calculating S3, the number of products for combinations of 3 siblings that include n1 is p1 multiplied by the number of products for 2-combinations that do not contain n1, i.e., p1(S2 ¡ p1(S1 ¡ p1)). Adding up every 3-combinations, we get:

s s s X pi(S2 ¡ pi(S1 ¡ pi)) = S2S1 ¡ S1 X pi2 + X pi3 i=1 1 Pik=¡01 ((¡1)iSk¡i¡1 Pjs=1 pij+1) if 1 · k · s k if k = 0 (4) 3.1

Supporting the calculus for an extension of card As pointed in ¯gure 1, an important contribution of VFD+ is the card generalization of the di®erent kinds of relations between features (i.e., mandatory, optional...). At the moment, VFD+ (and NFT) card syntax is:

Nevertheless, our proposed calculus for the total number of products supports the following more general syntax:

cardshlisti(children)

Where list is a non-void list which may include one or more: 1. index i 2 N ¢ 0 · i · s 2. range [low::high] ¢ 0 · low < high · s

Broadly speaking, list provides an easy way to express the selection of more than one range of node sons. For instance, cardsh[0::1]; 3; [5::6]i(n1; :::; ns) expresses the selection of: { zero to one of n1; :::; ns

or { three of n1; :::; ns

or { ¯ve to six of n1; :::; ns

Formally de¯ning the list extension semantics: in a valid con¯guration c, all non-terminal nodes n 2 (N ¡§) are labeled with the operator cardshlisti(n1; :::; ns) and the operator always evaluates to true for some e 2 list, according to the following rules: { if e is an index, exactly e of the s children of n evaluate to true. { if e is a range [low::high], at least low and at most high of the s children of n evaluate to true.

To calculate the total number of products using cardhlisti, equation 2 should be substituted by equation 5. Variability notations are widely used to scope the domain of a SPL. Unfortunately, there is a profusion of notations that hinders the e±cient communication among specialists and the portability of variability models between tools. P. Schobbens et al. have faced this problem by proposing the pivot notation VFD+ and demonstrating that many kinds of variability diagrams can be easily and e±ciently translated into VFD+ diagrams. Valuable information can be inferred from VFD+ diagrams; for instance, the total number of products of a SPL, that is used by economic models to predict SPL costs and bene¯ts. A common approach to infer the SPL number of products is translating diagrams into propositional logic formulas, which are processed by o®-the-self tools, such as SAT solvers. However, this approach only works for small diagrams.

We think more scalable solutions can be reached avoiding the diagram-tologic transformation and taking advantage of the tree organization of diagrams. Since VFD+ diagrams are single-rooted directed acyclic graphs, we have formally de¯ned a VFD+ subset, named NFT, where diagrams are restricted to be trees. We have also demonstrated that NFT and VFD+ are completely equivalent. We have proposed a time-e±cient algorithm to calculate the number of products of a SPL from a NFT diagram, without considering textual constraints among nodes. The algorithm has quadratic complexity if the diagram only includes mandatory, optional, or and xor relations, and, in general, has cubic complexity for any value of VFD+'s card operator. In fact, we have demonstrated that the algorithm also supports an extension of card to express disjunction of ranges. For future work, we plan to extend the algorithm to compute textual constraints.

References

1. Batory , D. Feature models, grammars, and propositional formulas . Proc. 9th Int. Conf. Software Product Lines , 2005 .

2. Benavides , D. On the automated analysis of software product lines using feature models. a framework for developing automated tool support . PhD Dissertation . University of Seville, Spain, June 2007 .

3. BigLever Software , Inc. Gears. http://www.biglever.com/index.html

4. Boehm , B. ; Brown , A.; Madachy , R.; Ye Yang . A software product line life cycle cost estimation model . International Symposium on Empirical Software Engineering , 2004 , page(s): 156 - 164 .

5. Clements , P. C. ; McGregor , J. D. ; Cohen, S. G. The Structured Intuitive Model for Product Line Economics (SIMPLE) (CMU /SEI-2005 - TR- 003 ).

6. Czarnecki , K. ; Eisenecker , U. Generative Programming: Methods, Tools, and Applications . Addison-Wesley, 2000 .

7. Eriksson , M. ; Borstler , J. ; Borg , K. The PLUSS Approach - Domain Modeling with Features , Use Cases and Use Case Realizations. Software Product Lines, 9th International Conference, SPLC 2005 , pp. 3344 .

8. Gheyi , R.; Massoni, T. ; Borba , P. A Theory for Feature Models in Alloy . First Alloy Workshop, colocated with the Fourteenth ACM SIGSOFT Symposium on Foundations of Software Engineering , 2006 , pages: 71 - 80 .

9. Gomaa , H. Designing Software Product Lines with UML: From Use Cases to Pattern-Based Software Architectures . Addison-Wesley 2004 .

10. Green ¯eld , J.; Short , K. Software Factories: Assembling Applications with Patterns, Models, Framworks, and Tools . Wiley, 2004 .

11. Griss , M. ; Favaro , J.; dAlessandro, M. Integrating feature modeling with the RSEB . Proceedings of the Fifth International Conference on Software Reuse , Vancouver, BC, Canada, June 1998 , pp. 7685 .

12. Harel , D. Rumpe , B. Modeling languages: Syntax, semantics and all that stu® - part I: The basic stu® . Technical Report MCS00-16, Faculty of Mathematics and Computer . The Weizmann Institute of Science , 2000 .

13. Heymans , P. ; Schobbens, P. ; Trigaux , J. ; Bontemps, Y. ; Matulevicius , R. ; Classen , A. Evaluating formal properties of feature diagram languages . Software, IET . Volume: 2 , Issue: 3. June 2008, pp: 281 - 302 .

14. Kang , K. ; Cohen , S. ; Hess , K. ; Novak , W. ;Peterson, S. Feature-Oriented Domain Analysis (FODA) Feasibility Study. Technical Report CMU /SEI - 90- TR- 21 , Software Engineering Institute, Carnegie Mellon University, November 1990 .

15. Kang , K. C. ; Kim , S. ; Lee , J. ; Kim , K. FORM: a feature-oriented reuse method . Annals of Software Engineering 5 ( 1998 ) 143168 .

16. Metzger , A. ; Pohl , K. ; Heymans , P. ; Schobbens, P. ; Saval, G. Disambiguating the Documentation of Variability in Software Product Lines: A Separation of Concerns, Formalization and Automated Analysis . Requirements Engineering Conference , 2007 . RE' 07 . 15th IEEE International ( 2007 ), pp. 243 - 253 .

17. Pohl , K. ; Bockle , G ,; Linden , F. Software Product Line Engineering: Foundations, Principles and Techniques. Springer, 2005 .

18. Pure Systems. pure::variants. http://www.pure-systems.com/

19. Riebisch , M. ; Bollert , K. ; Streitferdt , D ; Philippow, I. Extending feature diagrams with UML multiplicities . Sixth Conference on Integrated Design and Process Technology (IDPT' 2002 ), Pasadena, CA, June 2002 .

20. Schobbens , P. ; Heymans, P. ; Trigaux , J. ; Bontemps, Y. Generic semantics of feature diagrams . Computer Networks 51 ( 2 ): 456 - 479 ( 2007 ).

21. Steger , M. ; Tischer , C. ; Boss , B. ; Muller , A. ; Pertler , O. ; Stolz , W. ; Ferber, S. Introducing PLA at Bosch Gasoline Systems . Software Product Line Conferences 2004 , Boston, MA, Aug/Sep 2004, Springer-Verlag LNCS 3154, pp 34 - 50 .

22. Trinidad , P. ; Ruiz-Cortes , A. ; Benavides , D. ; Segura , S. ; Jimenez , A. FAMA Framework . 12th International Software Product Line Conference (SPLC 2008 ).

23. van Deursen , A. ; Klint , P. Domain-speci¯c language design requires feature descriptions . Journal of Computing and Information Technology ( 2001 ).

24. van Gurp, J. ; Bosch , J. ; Svahnberg, M. On the notion of variability in software product lines . Working IEEE/IFIP Conference on Software Architecture (WICSA 01) , 2001 .