domain: spi phys math info

text:
Michael Lienhardt
email: michael.lienhardt@onera.fr

Ferruccio Damiani
email: ferruccio.damiani@unito.it

Einar Broch Johnsen
email: einarj@ifi.uio.no

Jacopo Mauro
email: mauro@sdu.dk

Lazy Product Discovery in Huge Configuration Spaces

Keywords: Software and its engineering → Software product lines, Feature interaction, Abstraction, modeling and modularity, Software libraries and repositories, Software creation and management, Software Product Lines, Configurable Software, Variability Modeling, Feature Models, Composition, Linux Distribution

Highly-configurable software systems can have thousands of interdependent configuration options across different subsystems. In the resulting configuration space, discovering a valid product configuration for some selected options can be complex and error prone. The configuration space can be organized using a feature model, fragmented into smaller interdependent feature models reflecting the configuration options of each subsystem.

We propose a method for lazy product discovery in large fragmented feature models with interdependent features. We formalize the method and prove its soundness and completeness. The evaluation explores an industrial-size configuration space. The results show that lazy product discovery has significant performance benefits compared to standard product discovery, which in contrast to our method requires all fragments to be composed to analyze the feature model. Furthermore, the method succeeds when more efficient, heuristics-based engines fail to find a valid configuration.

INTRODUCTION

Highly-configurable software systems can have thousands of interdependent configuration options across different subsystems. In the resulting configuration space, different software variants can be obtained by selecting among these configuration options. The interdependencies between options are typically caused by interaction in the resulting software system. Constructing a well-functioning software variant can be a complex and error-prone process [START_REF] Apel | Feature-Oriented Software Product Lines: Concepts and Implementation[END_REF].

Feature models [START_REF] Batory | Feature Models, Grammars, and Propositional Formulas[END_REF] allow us to organize the configuration space and facilitate the construction of software variants by describing configuration options using interdependent features [START_REF] Kang | Feature-Oriented Domain Analysis (FODA) Feasibility Study[END_REF]: a feature is a name representing some functionality, a set of features is called a configuration, and each software variant is identified by a valid configuration (called a product, for short).

Highly-configurable software systems can consist of thousands of features and combine several subsystems [START_REF] Berger | A survey of variability modeling in industrial practice[END_REF][START_REF] Berger | Variability modeling in the real: a perspective from the operating systems domain[END_REF][START_REF] Lienhardt | Multi Software Product Lines in the Wild[END_REF][START_REF] Tartler | Feature consistency in compile-time-configurable system software: facing the linux 10, 000 feature problem[END_REF], each with different features. The construction and maintenance of feature models with thousands of features for such highly-configurable systems, can be simplified by representing large feature models as sets of smaller interdependent feature models [START_REF] Berger | A survey of variability modeling in industrial practice[END_REF][START_REF] Rosenmüller | Multi-dimensional Variability Modeling[END_REF] which we call fragments. However, the analysis of such fragmented feature models usually requires the fragments to be composed, to enable the application of existing analysis techniques [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF][START_REF] Benavides | FAMA: Tooling a framework for the automated analysis of feature models[END_REF][START_REF] Mendonça | software product lines online tools[END_REF][START_REF] Segura | BeTTy: Benchmarking and Testing on the Automated Analysis of Feature Models[END_REF][START_REF] Thüm | A Classification and Survey of Analysis Strategies for Software Product Lines[END_REF][START_REF] Thüm | FeatureIDE: An extensible framework for featureoriented software development[END_REF]. To this aim, many approaches for composing feature models from fragments have been investigated [START_REF] Mathieu Acher | Comparing Approaches to Implement Feature Model Composition[END_REF][START_REF] Mathieu Acher | Composing Your Compositions of Variability Models[END_REF][START_REF] Bošković | Aspect-Oriented Feature Models[END_REF][START_REF] Classen | A text-based approach to feature modelling: Syntax and semantics of TVL[END_REF][START_REF] Rosenmüller | Modeling Dependent Software Product Lines[END_REF][START_REF] Schröter | Automated Analysis of Dependent Feature Models[END_REF].

The analysis of fragmented feature models can be simplified if suitable abstractions can safely replace some of the feature model fragments in the analysis. This simplification can be realized by means of feature-model interfaces [START_REF] Schröter | Feature-Model Interfaces: The Highway to Compositional Analyses of Highly-Configurable Systems[END_REF]. A feature-model interface is a feature model that hides some of the features and dependencies of another feature model (thus, interfaces are closely related to feature-model slicing [START_REF] Mathieu Acher | Slicing feature models[END_REF]). An interface can be used instead of a feature model fragment to simplify the overall feature model. For certain analyses, working on the simplified feature model produces results that also hold for the original feature model and for any feature model where the interface is replaced by a fragment compatible with the interface.

This paper addresses automated product discovery in large configuration spaces represented as sets of interdependent feature models. Product discovery (sometimes called product configuration) is a particular analysis for finding a product which includes a desired set of features [START_REF] José | Automated analysis of feature models: Quo vadis?[END_REF]. We aim at automatically discovering a product that contains a given set of features from the feature model fragments, without having to compose all the fragments to apply the analysis. This work is motivated by our recent experiences in applying techniques for variability modeling to automated product discovery in industrial use cases such as Gentoo [START_REF]Gentoo Linux[END_REF], a sourcebased Linux distribution that consists of many highly-configurable packages. The March 1st 2019 version of the Gentoo distribution comprises 671617 features spread across 36197 feature models. Gentoo's huge configuration space can be seen as the composition of the feature models for all its packages, where package interdependencies are modeled as shared features. Gentoo's official package manager and distribution system Portage [START_REF]Portage -Gentoo Wiki[END_REF] achieves (via its emerge tool) efficiency at the expense of completeness; i.e., in some cases this tool fails to discover a product that contains a given set of features, although such a product exists. We show that feature model interfaces [START_REF] Schröter | Feature-Model Interfaces: The Highway to Compositional Analyses of Highly-Configurable Systems[END_REF], which were developed to support analysis reuse for feature model evolution in fragmented feature models, do not allow us to reach our aim of complete and efficient automated product discovery.

We propose a novel method for product discovery in sets of interdependent feature models. The proposed method is lazy in the sense that features are added incrementally to the analysis until a product is found. We provide a formal account of the method and evaluate it by implementing an efficient and complete dependency solver for Gentoo. In short, our contributions are:

(1) we strengthen feature model interfaces to enable lazy product discovery in sets of interdependent feature models; [START_REF] Acher | Extraction and Evolution of Architectural Variability Models in Plugin-based Systems[END_REF] we propose an efficient and complete algorithm for lazy product discovery in huge configuration spaces; [START_REF] Mathieu Acher | Comparing Approaches to Implement Feature Model Composition[END_REF] we provide an open-source implementation of the proposed algorithm; 1 and (4) we evaluate the potential of lazy product discovery in terms of experiments on an industrial-size configuration space. 2

MOTIVATION AND OVERALL CONCEPT

A software system like the Gentoo distribution comprises 36197 configurable packages, as of its March 1st 2019 version. The configuration space of each package can be represented by a feature model; the overall configuration space of Gentoo can then be represented by a feature model that is the composition of the feature models of the 36197 packages. The resulting feature model has 671617 features, and thus a configuration space with up to 2 671617 solutions. Gentoo's official package manager Portage implements an optimized, heuristics-based product-discovery algorithm to find products in this configuration space. This algorithm is not complete; i.e., it fails to solve some product-discovery problems that have solutions. To the best of our knowledge, existing complete productdiscovery approaches need to load the entire feature model to find products. Consequently, they do not scale to product-discovery problems of the size of Gentoo's configuration space. 1 The lazy product-discovery tool is available at https://github.com/gzoumix/pdepa and at archive.softwareheritage.org/browse/origin/https://github.com/gzoumix/pdepa.git 2 The evaluation artifact is available at https://doi.org/10.6084/m9.figshare.11728914.v4 and https://doi.org/10.5281/zenodo.3633643

Listing 1: Lazy product-discovery algorithm

1 input S: set of feature models 2 input c: configuration 3 var Y = c 4 var M ′ = compose({pick_cut(M, Y ) | M ∈ S }) 5 var solution = select(M ′ , c) 6 while (solution None ∧ solution Y ): 7 Y = Y ∪ solution 8 M ′ = compose({pick_cut(M, Y ) | M ∈ S }) 9 solution = select(M ′ , c) 10 return solution
In this paper we target product discovery in huge configuration spaces, such as for Gentoo, that can be described by a feature model represented as a set S of feature models with shared features, where loading the overall feature model (i.e., the whole set S) is too expensive. We propose lazy product discovery, a product-discovery method that loads the elements of S incrementally, until it finds a product of the overall feature model. The method relies on the notion of a cut of a feature model M for a set of features Y . This is a feature model M ′ whose products are products of M and include all the products of M that contain a feature in Y .

The proposed algorithm, shown in Listing 1, takes as input a set S of feature models with shared features and a set c of features to be included in the discovered product. After initialization, the algorithm incrementally loads cuts until a solution has been found. Let M 0 denote the composition of the feature models in S. The algorithm returns a (not necessarily minimal) product of M 0 which includes all features in c, whenever such a product exists; otherwise, it returns the special value None. The algorithm relies on the following three auxiliary functions: Assuming that the auxiliary functions (1), ( 2) and ( 3) work, we have that on Line 6 the following loop invariants hold:

Inv1: c ⊆ Y . Inv2: solution is a product of M ′ which includes all features in
c, whenever such a product exists; otherwise solution is the special value None. Inv3: if solution is a product of M ′ and solution ⊆ Y , then solution is also a product of M 0 . Inv4: If M ′ has no product which includes all features in c, then neither does M 0 . Checking that Inv1 holds is straightforward: just observe that on Line 3 the variable Y is initialized to c and that at each iteration of the while loop new features are added to Y on Line 7. Checking that Inv2 holds is equally straightforward: according to the description of the auxiliary functions (1), ( 2) and (3), the invariant is established on Lines 4 and 5 as well as on Lines 8 and 9. The fact that Inv3 and Inv4 hold is shown in the proof of Theorem 4 in Section 5. The algorithm terminates because at each iteration of the while loop, the size of the set Y (which, by construction, only contains features from the features models in S) increases. When the algorithm terminates we have that either solution = None or None solution ⊆ Y . In the first case (by Inv4) we have that M 0 has no product that contains all the features in c, while in the second case (by Inv3) we have that solution is a product of M 0 that contains all the features in c.

The laziness of this algorithm stems from the fact that it does not need to consider M 0 at once. Instead, the algorithm starts by considering the composition of the cuts of the feature models for Y = c and then iterates by considering bigger and bigger cuts until the candidate solution is contained in the set Y . When this happens we know, for the properties of the cut, that the found solution is also a solution for M 0 .

The algorithm's efficiency in finding a product with the features in c (see Lines 4, 5 and 8, 9 of Listing 1) compared to executing select(M 0 , c), depends on the degree to which the feature models in S are such that:

-computing pick_cut(M, Y ) is efficient, -the feature models M ′ are small compared to M 0 , select(M ′ , c) performs better than select(M 0 , c), and -a small number of iterations of the while-loop is required.

For the Gentoo distribution, each feature model M i in S has a distinguished feature f i such that the constraints expressed by M i are enabled only if f i is selected (see Section 6.1). This reflects that each M i corresponds to a Gentoo package that is installed if and only if f i is selected. Therefore, the function pick_cut(M, Y ) can be efficiently implemented by returning M i if f i ∈ Y , and by returning a feature model that expresses no constraints (and can, therefore, be ignored by the composition that builds M ′ ) otherwise.

The rest of this paper is organized as follows: Sections 3-5 provide a formal account of the lazy product-discovery method that culminates in the proof that Inv3 and Inv4 hold, Section 6 evaluates the performance of the lazy product-discovery algorithm by means of experiments, and Sections 7 and 8 discuss related work and conclude the paper, respectively.

A FORMALIZATION OF FEATURE MODELS

This section presents a formalization of feature models (FM) and related notions, including feature model interfaces and composition.

Feature Model Representations

Different representations of feature models are discussed, e.g., by Batory [START_REF] Batory | Feature Models, Grammars, and Propositional Formulas[END_REF]. In this paper, we will rely on the propositional formula representation of feature models. In this representation, a feature model is given by a pair (F , ϕ) where:

-F is a set of features, and ϕ is a propositional formula where the variables x are feature names:

ϕ ::= x | ϕ ∧ ϕ | ϕ ∨ ϕ | ϕ → ϕ | ¬ϕ.
A propositional formula ϕ over a set of features F represents the feature models whose products are configurations {x 1 , ..., x n } ⊆ F (n ≥ 0) such that ϕ is satisfied by assigning value true to the variables x i (1 ≤ i ≤ n) and false to all other variables. E 1 (A FM). Gentoo packages can be configured by selecting features (called use flags in Gentoo), which may trigger dependencies or conflicts between packages. Version 2.29 of the glibc library, that contains the core functionalities of most Linux systems, is provided by the package sys-libs/glibc-2.29-r2 (abbreviated to glibc in the sequel). This package has many dependencies, including (as expressed in Gentoo's notation):

doc? ( sys-apps/texinfo ) vanilla?( !sys-libs/timezone-data )

This dependency expresses that glibc requires the texinfo documentation generator (provided by any version of the sys-apps/texinfo package) whenever the feature doc is selected and if the feature vanilla is selected, then glibc conflicts with any version of the time zone database (as stated with the !sys-libs/timezone-data constraint). These dependencies and conflicts can be expressed by a feature model (F glibc , ϕ glibc ) where F glibc = {glibc, txinfo, tzdata, glibc:doc, glibc:v}, and

ϕ glibc = glibc → ((glibc:doc → txinfo) ∧ (glibc:v → (¬tzdata)).
Here, the feature glibc represents the glibc package; txinfo represents any sys-apps/texinfo package; tzdata represents any version of the sys-libs/timezone-data package; and glibc:doc (resp. glibc:v) represents the glibc's doc (resp. vanilla) use flag.

The propositional representation of feature models works well in practice [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF][START_REF] Mendonça | SATbased Analysis of Feature Models is Easy[END_REF][START_REF] Thüm | A Classification and Survey of Analysis Strategies for Software Product Lines[END_REF] and we shall use it for the evaluation of the proposed method (in Section 6). In contrast, to simplify the proofs, we follow Schröter et al. [START_REF] Schröter | Feature-Model Interfaces: The Highway to Compositional Analyses of Highly-Configurable Systems[END_REF] in using an extensional representation of feature models to present our theory.

D 1 (F , ).

A Feature Model M is a pair (F , P) where F is a set of features and P ⊆ 2 F a set of products. E 2 (A FM). Let 2 X denote the powerset of X . The feature model of Example 1 can be given an extensional representation M glibc = (F glibc , P glibc ) where F glibc is the same as in Example 1 and P glibc ={ {glibc}, {glibc, txinfo}, {glibc, tzdata}, {glibc, txinfo, tzdata} } ∪ { {glibc, glibc:doc, txinfo}, {glibc, glibc:doc, txinfo, tzdata} } ∪ { {glibc, glibc:v}, {glibc, glibc:v, txinfo} } ∪ { {glibc, glibc:doc, glibc:v, txinfo} } ∪ 2 {txinfo, tzdata, glibc:doc, glibc:v} .

In the description of P glibc , the first line contains products with glibc but none of its use flags are selected, so texinfo and tzdata can be freely installed; the second line contains products with the use flag doc selected in glibc, so a package of sys-apps/texinfo is always required; the third line contains products with the use flag vanilla selected in glibc, so no package of sys-libs/timezone-data is allowed; the forth line contains products with both glibc's use flags selected, so sys-apps/texinfo is mandatory and sys-libs/timezone-data forbidden; finally, the fifth line represents products without glibc, so all combinations of other features are possible, including the empty set.

D 2 (E FM, FM ,

). The empty feature model, denoted M ∅ = (∅, {∅}), has no features and has just the empty product ∅. A void feature model is a feature model that has no products, i.e., it has the form (F , ∅) for some F . A preproduct of a feature model M is a configuration c that can be extended to a product of M (more formally, c ⊆ p for some product p of M).

Based on the above definition of a pre-product, we identify two related search problems.

D 3 (F ,

). Consider a feature model M and a set of features c in M. The featurecompatibility problem for c in M is the problem of determining whether c is a pre-product of M (i.e., whether the features in c are compatible with the products in M). The product-discovery problem for c in M is the problem of finding a product of M that extends c.

Clearly, the feature-compatibility problem for c in M has a positive answer if and only if the product-discovery problem for c in M has a solution.

Feature Model Interfaces

Feature model interfaces were defined by Schröter et al. [START_REF] Schröter | Feature-Model Interfaces: The Highway to Compositional Analyses of Highly-Configurable Systems[END_REF] as a binary relation , expressing that a feature model M ′ is an interface of a feature model M if M ′ ignores some features of M.

D 4 (FM ).

A feature model M ′ = (F ′ , P ′ ) is an interface of feature model M = (F , P), denoted as

M ′ M, iff F ′ ⊆ F and P ′ = {p ∩ F ′ | p ∈ P}.
Note that, for all feature models M ′ = (F ′ , P ′ ) and M, if M ′ M then (i) all products of M ′ are pre-products of M and (ii) M ′ is the only interface of M which has exactly the features F ′ (i.e., M ′ is completely determined by F ′ ).

E 3 (A FM). The feature model

F ={glibc, glibc:v}

P ={ ∅, {glibc}, {glibc, glibc:v} }
is the interface of the feature model M glibc from Example 2 that is determined by the features glibc and glibc:v.

The interface relation for feature models is a partial order (i.e., it is reflexive, transitive and anti-symmetric) and the empty feature model M ∅ is an interface of every non-void feature model M. Moreover, M is void if and only if (∅, ∅) M.

The notion of a feature model interface is closely related to that of a feature model slice, which was defined by Acher et al. [START_REF] Mathieu Acher | Slicing feature models[END_REF] as a unary operator Π Y restricting a feature model to a set Y of features. Given a feature model M, Π Y (M) is the feature model obtained from M by removing the features not in Y .

D 5 (FM ).

The slice operator Π Y on feature models, where Y is a set of features, is defined by:

Π Y ((F , P)) = (F ∩ Y , {p ∩ Y | p ∈ P}).
Note that, for every feature model M = (F , P) and set of features Y , the feature model

Π Y (M) = (F ′ , P ′ ) is the unique inter- face of M such that F ′ = F ∩ Y . Moreover, for every interface M 1 = (F 1 , P 1 ) of M it holds that M 1 = Π F 1 (M).

Feature Model Composition

Highly-configurable software systems often consist of many interdependent, configurable packages [START_REF]Gentoo Linux[END_REF][START_REF] Lienhardt | Multi Software Product Lines in the Wild[END_REF][START_REF] Lotufo | Evolution of the Linux Kernel Variability Model[END_REF]. The variability constraints of each of these packages can be represented by a feature model. Therefore, configuring two (or more packages) in such a way that they can be installed together corresponds to identifying a product in a suitable composition of their associated feature models. In the propositional representation of feature models, such composition corresponds to logical conjunction; i.e., the composition of two feature models (F 1 , ϕ 1 ) and (F 2 , ϕ 2 ) is the feature model

(F 1 ∪ F 2 , ϕ 1 ∧ ϕ 2 ).
In the extensional representation of feature models, this form of composition corresponds to the binary operator • of Schröter et al. [START_REF] Schröter | Feature-Model Interfaces: The Highway to Compositional Analyses of Highly-Configurable Systems[END_REF], which is similar to the join operator from relational algebra [START_REF] Codd | A Relational Model of Data for Large Shared Data Banks[END_REF].

D 6 (FM ). The composition of two fea- ture models M 1 = (F 1 , P 1 ) and M 2 = (F 2 , P 2 ), denoted M 1 • M 2 ,
is the feature model defined by:

M 1 • M 2 = (F 1 ∪ F 2 , {p ∪ q | p ∈ P 1 , q ∈ P 2 , p ∩ F 2 = q ∩ F 1 }).
The composition operator • is associative and commutative, with M ∅ as identity element (i.e., M • M ∅ = M). Composing a feature model with a void feature model yields a void feature model:

(F 1 , P 1 ) • (F 2 , ∅) = (F 1 ∪ F 2 , ∅). E 5 (C FM ).
Let us consider another important package of the Gentoo distribution: gnomeshell, a core component of the Gnome Desktop environment. Version 3.30.2 of gnome-shell is provided by the package gnome-base/gnomeshell-3.30.2-r2 (abbreviated to g-shell in the sequel), and its dependencies include the following statement: networkmanager?( sys-libs/timezone-data ).

This dependency expresses that g-shell requires any version of the time zone database when the feature networkmanager is selected.

The propositional representation of this dependency can be captured by the feature model (F g-shell , ϕ g-shell ), where F g-shell = {g-shell, tzdata, g-shell:nm}, and

ϕ g-shell = g-shell → (g-shell:nm → tzdata).
The corresponding extensional representation of this feature model is M g-shell = (F g-shell , P g-shell ), where:

P g-shell ={ {g-shell}, {g-shell, tzdata} }∪ { {g-shell, tzdata, g-shell:nm} }∪ 2 {tzdata, g-shell:nm} .
Here, the first line contains products with g-shell but none of its use flags are selected: tzdata can be freely selected; the second line is the product where g-shell:nm is also selected and tzdata becomes mandatory; finally, the third line represents products without g-shell.

The propositional representation of the composition is the feature model (F full , ϕ full ), where

F full = F glibc ∪ F g-shell
= {glibc, txinfo, tzdata, g-shell, glibc:doc, glibc:v, g-shell:nm}, and

ϕ full = ϕ glibc ∧ ϕ g-shell = (glibc → ((glibc:doc → txinfo) ∧ (glibc:v → (¬tzdata)))∧ (g-shell → (g-shell:nm → tzdata)).
The extensional representation of the composition is the feature model M full = M glibc •M g-shell = (F full , P full ) where

P full = P glibc ∪ P g-shell ∪ 2 {txinfo, tzdata, glibc:doc, glibc:v, g-shell:nm} ∪ { {glibc, g-shell} ∪ p | p ∈ 2 {txinfo, tzdata} } ∪ { {glibc, glibc:doc, txinfo, g-shell} ∪ p | p ∈ 2 {tzdata} } ∪ { {glibc, glibc:v, g-shell} ∪ p | p ∈ 2 {txinfo} } ∪ { {glibc, g-shell, g-shell:nm, tzdata} ∪ p | p ∈ 2 {txinfo} } ∪
{ {glibc, glibc:doc, glibc:v, txinfo, g-shell} } ∪ { {glibc, glibc:doc, txinfo, g-shell, g-shell:nm, tzdata} }.

Here, the first line contains the products where glibc and g-shell do not interact, i.e., either when they are not installed, or only one of them is installed; the second line contains the products where both glibc and g-shell are installed, but without use flags selected, so all optional package can be freely selected; the third line contains the products with the glibc's use flag doc selected, so sys-apps/texinfo becomes mandatory; the fourth line contains the products with the glibc's use flag vanilla selected, so sys-libs/timezone-data is forbidden; the fifth line contains the products with the g-shell's use flag vanilla network manager, so sys-libs/timezone-data is mandatory; the sixth line contains the product with glibc's both use flags selected and the seventh line contains the product with glibc's use flag doc and g-shell's use flag networkmanager are selected.

PROBLEM STATEMENT

Many case studies show that the size of feature models used to model real configuration spaces can be challenging for both humans and machines [START_REF] Berger | A survey of variability modeling in industrial practice[END_REF][START_REF] Schröter | Feature-Model Interfaces: The Highway to Compositional Analyses of Highly-Configurable Systems[END_REF][START_REF] Tartler | Configuration coverage in the analysis of large-scale system software[END_REF][START_REF] Thüm | FeatureIDE: An extensible framework for featureoriented software development[END_REF], including the feature model for the source-based Linux distribution Gentoo [START_REF]Gentoo Linux[END_REF] mentioned above. The state-of-the-art strategy used to address this challenge is to represent large feature models by sets of smaller interdependent feature models [START_REF] Berger | A survey of variability modeling in industrial practice[END_REF][START_REF] Rosenmüller | Multi-dimensional Variability Modeling[END_REF]. The resulting interdependencies between different feature models can be expressed using shared features [START_REF] Schröter | Feature-Model Interfaces: The Highway to Compositional Analyses of Highly-Configurable Systems[END_REF].

The feature compatibility problem for a given set of features (see Definition 3) can be decided without first composing the considered feature models when the feature models are disjoint, as it suffices to inspect each feature model independently. Namely, featuremodel slices can be used to formulate a feature-compatibility criterion for the case with no shared features between the feature models, as shown by the following theorem:

T 1 (F FM ). Consider the feature models M i = (F i , P i ) (1 ≤ i ≤ n) with pairwise no shared features (i.e., 1 ≤ i j ≤ n implies F i ∩ F j = ∅).
Then a configuration c is a pre-product of the feature model M =

• 1≤i ≤n M i if and only if c is a subset of 1≤i ≤n F i and for all M i the configuration c ∩ F i is a product of Π c (M i ).

P

. Let M = (F , P). Case ⇒. Since c is a pre-product of M, by definition there exist p ∈ P such that c ⊆ p. Hence c ⊆ F = 1≤i ≤n F i . Let now consider Π c (M i ) for any 1 ≤ i ≤ n: by definition p ∩ c ∩ F i is a product of this feature model, and by construction,

p ∩ c ∩ F i = c ∩ F i . Hence, c ∩ F i is a product of Π c (M i ) for any 1 ≤ i ≤ n.
Case ⇐. Since for any 1 ≤ i ≤ n, c ∩ F i is a product of Π c (M i ), there exist p i ∈ P i such that c ∩ F i = p i ∩ c. Let consider the configuration p = 1≤i ≤n p i . Since the feature models M i do not share features, we have

p i ∩ F j = ∅ = p j ∩ F i for all 1 ≤ i j ≤ n.
Hence p is a product of M. Moreover, we have that:

p ∩ c = 1≤i ≤n (p i ∩ c) = 1≤i ≤n (c ∩ F i ) = c ∩ 1≤i ≤n F i = c.
Hence c ⊆ p holds, which means that c is a pre-product of M.

Unfortunately, the feature compatibility criterion of Theorem 1 does not work for feature models with shared features. The problem can be illustrated by the following example.

E 6 (F ).

Consider the two feature models M glibc and M g-shell from Examples 2 and 5, and the configuration c = {glibc, glibc:v, g-shell, g-shell:nm}. We have Π c (M glibc ) = ({glibc, glibc:v}, 2 {glibc, glibc:v} ), and

Π c (M g-shell ) = ({g-shell, g-shell:nm}, 2 {g-shell, g-shell:nm} ).
Here, we have that c ⊆ F glibc ∪ F g-shell and it is clear from the previous equation that c ∩ F glibc = {glibc, glibc:v} is a product of Π c (M glibc ) and that c ∩ F g-shell = {g-shell, g-shell:nm} is a product of Π c (M g-shell ). However, c is not a pre-product of M glibc • M g-shell , since the use flag g-shell:nm requires a timezone database to be installed while the use flag glibc:v forbids it.

In this paper we address complete and efficient product discovery in sets of interdependent feature models. To this aim, we define a novel criterion which, given some selected features, enables solving the product-discovery problem for a set of feature model fragments with shared features, without composing all the fragments.

LAZY PRODUCT DISCOVERY

We are looking for a product-discovery criterion which works for interdependent feature models, similar to how the feature-compatibility criterion given in Theorem 1 works for disjoint feature models. The solution lies in a novel criterion based on strengthening the feature model interfaces. Given feature models with shared features M i = (F i , P i ) and a set of selected features c, we need feature model interfaces M ′ i that reflect how c is related to other features in M i in order to guarantee that the interface behaves similarly to M i with respect to the feature-compatibility problem for c. More formally, the interface M ′ i must satisfy the following conditions: (1) Π c (M i ) M ′ i ; and (2) the products of M ′ i are among the products of M i . E 7 (F ). Consider feature models M glibc and M g-shell and configuration c, as discussed in Example 6. Let c 1 = {glibc, glibc:v} and c 2 = {glibc, tzdata, glibc:v}. We can see that the interface M ′ glibc = Π c 2 (M glibc ) of M glibc satisfies (with i = glibc) conditions ( 1) and ( 2) above. Since Π c (M glibc ) = Π c 1 (M glibc ) and c 2 \ c 1 = {tzdata}, this shows that it is important to consider the feature tzdata when checking whether c is a pre-product of a composed feature model including M glibc .

Let us now introduce terminology for different restrictions to the interface relation that satisfy one or both of the conditions (1) and ( 2) given above, and investigate some of their properties.

D

7 (FM , , ). Given a set of features Y and two feature models M ′ = (F ′ , P ′ ) and M = (F , P), we say that (1)

M ′ is an extended slice for Y of M, denoted M ′ Y M, iff Π Y (M) M ′ M holds; (2) M ′ is a conservative interface of M, denoted M ′ M, iff
both M ′ M and P ′ ⊆ P hold; and

(3) M ′ is a cut for Y of M, denoted M ′ Y M, iff M ′ is both
an extended slice for Y and a conservative interface.

Note that ∅ = . The relation is a partial order; the feature model (∅, ∅) is the minimum (i.e., the smallest w.r.t. both and ) conservative interface of every void feature model; and the empty feature model M ∅ is the minimum conservative interface of every feature model that has the empty product.

The following theorem proves, in a constructive way, the existence of the minimum cut of M for Y , for any feature model M = (F , P). Let the minimal products of M be the products that are not included in other products, and let Y ′ = (F ∩ Y ) be the set of features of M that occur in Y . Intuitively, the minimum cut of M for Y is the feature model obtained from (Y ′ , ∅) by incrementally adding all the minimal products of M (and their features) that contain a feature occurring in the feature model, until a fixed point is reached.

T 2 (C

). For all sets Y of features and all feature models M = (F , P), let ⊥ Y (M) be the minimum cut of M for Y , i.e.,

⊥ Y (M) = min {M ′ | M ′ Y M}. Then ⊥ Y (M) = f ∞ (((F ∩ Y ), ∅))
, where f is the function between feature models defined by

f ((F 1 , P 1 )) = (F 1 ∪ ( p ∈P 2 p), P 1 ∪ P 2 ) with P 2 = {p ∈ P | ∀p ′ ∈ P, (p ′ p) ⇒ ((p \ p ′ ) ∩ F 1 ∅)}.

P

. Let M ′ = ((F ∩Y ), ∅) and consider the partially ordered set of feature models (S, ≤), defined by -S = {(F ′′ , P ′′ ) | (F ∩ Y ) ⊆ F ′′ ⊆ F ∧ P ′′ ⊆ P}, and -(F 1 , P 1 ) ≤ (F 2 , P 2 ) iff (F 1 ⊆ F 2 ) and (P 1 ⊆ P 2 ). It is straightforward to see that (S, ≤) is a complete lattice (with minimum M ′ and maximum M) and that f is monotonic increasing for ≤. Hence, by [START_REF] Kleene | On notation for ordinal numbers[END_REF], f ∞ (M ′ ) exists and is the minimum fixpoint of f . We prove that the fixpoints of f are exactly the cuts of M for Y . Let us first consider a feature model

M Y = (F Y , P Y ) that is a cut of M for Y . Since M Y = Π F Y (M
) and P Y ⊆ P for all p ∈ P, we have p ∩ F Y ∈ P. This implies that for any p ∈ P \ P Y , there exists p ′ ∈ P with p ′ p such that (p \p ′ ) ∩ F Y = ∅. By definition, we have f

(M Y ) = ( p ∈P 2 p ∪ F Y , P Y ∪ P 2 ) with P 2 = {p ∈ P | ∀p ′ ∈ P, (p ′ p) ⇒ ((p \ p ′ ) ∩ F Y ∅)} ⊆ P Y . Hence f (M Y ) = M Y .
Let us now consider a feature model

M ′ Y = (F ′ Y , P ′ Y ) in S such that f (M ′ Y ) = M ′ Y . First,
\ p ′ ) ∩ F ′ Y ∅) holds. It follows that M ′ Y is not a fixpoint of f (since applying f to M ′
Y would add the product p 1 ), which contradicts the hypothesis. Hence for all p ∈ P,

p ∩ F ′ Y ∈ P ′ Y , this means that M ′ Y = Π F ′ Y (M). Since by construction Y ∩ F ⊆ F ′ Y , we have Π Y (M) M ′ Y M: M ′
Y is a cut of M for Y . To conclude, observe that the orders and ≤ are equal on the set of cuts of M for Y . Since f (M ′ ) is the minimum fixpoint of f w.r.t. ≤, it is also the minimum cut of M for Y . ,∅) and then applying f . In the first application of f , the set P 2 collects the products ∅, {glibc}, {glibc:doc}, and {glibc,glibc:doc,txinfo}. The set F 1 after the first application becomes {glibc,glibc:doc,txinfo} and therefore, in the second application of f , the products {txinfo}, {glibc, txinfo}, and {glibc:doc, txinfo} are added to P 2 . At this point, further applications of f do not add further products.

In this case, the minimum cut ⊥ Y (M glibc ) is different from the slice Π Y (M glibc ), since the cut keeps the information that when glibc and glibc:doc are selected, then txinfo also has to be selected.

The following theorem proves sufficient criteria to guarantee that a product of the composition of cuts is also a product of the composition of the original feature models and, conversely, that the original feature model does not have a product that contains a given set of features. Intuitively, given a set of features Y and a product p of the composition of cuts for Y , if p is a subset of Y we have that p is also a product of the composition of the original feature models. Moreover, if the composition of cuts for Y has no products with the features in a set c ⊆ Y , then neither does the the original feature model.

T 3 (P FM )

. Consider a set Y of features, a finite set I of indices, and two sets of feature models

{M i = (F i , P i ) | i ∈ I } and {M ′ i = (F ′ i , P ′ i ) | i ∈ I } such that for all i ∈ I , M ′ i Y M i . Let M = (F , P) = • i ∈I M i and M ′ = (F ′ , P ′ ) = • i ∈I M ′ i .
Then (1) each product p of M ′ such that p ⊆ Y is a product of M, and (2) for each set of features c ⊆ Y and for each product p of M such that c ⊆ p, there exists a product q of M ′ such that c ⊆ q ⊆ p.

P .

(1) Consider a product p ∈ P ′ . By construction, for every i ∈ I , there exists p i ∈ P ′ i such that p = i ∈I p i and, for all i, j ∈ I , p j ∩F ′ i = p i ∩F ′ i . By Definition 7, for all i ∈ I , since p i ∈ P ′ i , we have that p i ∈ P i . Let us now consider i, j ∈ I . We have that

p i ∩ F j = p i ∩ Y ∩ F j = p i ∩ F ′ j = p j ∩ F ′ i = p j ∩ Y ∩ F i = p j ∩ F i . Hence, p = i ∈I p i ∈ P.
(2) By Definition 7, since

M ′ i Y M i , we have Π Y (M i ) M ′ i . Then, for all i ∈ I , there exists Y i such that c ⊆ Y ⊆ Y i and Π Y i (M i ) = M ′
i . Consider a product p ∈ P such that c ⊆ p. By definition, for all i ∈ I , there exists p i ∈ P i such that p = i ∈I p i and for all i, j ∈ I , we have

p i ∩ F j = p j ∩ F i . Let q = i ∈I (p i ∩ Y i ).
Clearly c ⊆ q ⊆ p. Moreover, consider i, j ∈ I ; since p i ∩F j = p j ∩F i holds, we have:

(p i ∩ Y i ) ∩ (F j ∩ Y j ) = (p i ∩ F j ) ∩ (Y i ∩ Y j ) = (p j ∩ F i ) ∩ (Y i ∩ Y j ) = (p j ∩ Y j ) ∩ (F i ∩ Y i ). Hence q ∈ P ′ . E 9 (U glibc g-shell FM ).
Consider the packages glibc and g-shell of Example 5 and the set Y = {glibc, glibc:v, tzdata}. It is easy to see that the minimum cut of

M glibc for Y is ⊥ Y (M glibc ) = (Y , 2 Y \ Y )
because tzdata can not be selected when glibc and glibc:v are selected. Now consider the package g-shell instead. The minimum cut of

M g-shell for Y is ⊥ Y (M g-shell ) = (Y , 2 Y ). By the definition of fea- ture model composition, we have that ⊥ Y (M glibc )•⊥ Y (M g-shell ) is the same as ⊥ Y (M glibc ).
Now, due to Theorem 3, we can for example derive that the product {glibc, tzdata} that contains the shared feature tzdata is also a product of the composition of M glibc and M g-shell . Note that to discover this fact, we avoided computing the composition of the entire feature models and could ignore, e.g., features such as glibc:doc and g-shell.

The criteria provided by Theorem 3 allow us to prove that the lazy product-discovery algorithm (Listing 1 in Section 2) is correct and complete.

T 4 (S ).

Given a finite set I of indices, a set of feature models S = {M i = (F i , P i ) | i ∈ I } such that all products of M i are finite, and a finite configuration c, the lazy product-discovery algorithm (Listing 1) applied to S and c always finishes and returns a product of • i ∈I M i that contains c if and only if such a product exists.

P

. Recall the definitions of auxiliary functions (Section 2):

(1) pick_cut(M, Y ) = M ′ for some M ′ s.t. M ′ Y M, (2) compose({M 1 , . . . , M n }) = M 1 • • • • • M n , (3) select(M, c
) is a product of M containing all the features in c if such a product exists, None otherwise; and the loop invariants Inv1-Inv4 on Line 6. In Section 2 we have already shown that the invariants Inv1 and Inv2 hold, and that the algorithm always finishes (because the set of examined features Y , which strictly increases during each traversal of the while loop, is bounded by ( i ∈I p ∈P i p) ∪ c, which is finite by hypothesis). We can now conclude the proof by observing that the invariants Inv3 and Inv4 follow straightforwardly from Theorem 3(1) and Theorem 3(2), respectively.

It is worth observing that a suitable structure of the feature models can enable a particular efficient implementation of the function pick_cut(M, Y ). For instance, if the feature-model M is propositionally represented with a pair of the form (F , f → ψ ) (for some set of features F , feature f ∈ F and formula ψ ) then, whenever f Y , pick_cut(M, Y ) can return the feature model (Y ′ , 2 Y ′ ) with Y ′ = Y ∩ F , which corresponds to the pair (Y ′ , true) in propositional representation. Therefore, feature models of the form (F , f → ψ ) such that f Y can be filtered away before computing the composition compose({pick_cut(M, Y )|M ∈ S }) in Lines 4 and 8 of the algorithm.

EVALUATION

With lazy product discovery, we aim to efficiently address the productdiscovery problem in huge configuration spaces, consisting of hundreds of thousands of features in tens of thousands of feature models. Therefore, we evaluate the performance of the lazy productdiscovery algorithm introduced in Section 2. The proposed algorithm loads feature model fragments by need to examine specific features. A feature is loaded during a configuration process if it occurs in one of the loaded feature model fragments. In contrast, standard product-discovery algorithms (e.g., [START_REF] Mauro | Context-aware reconfiguration in evolving software product lines[END_REF][START_REF] Mendonça | software product lines online tools[END_REF][START_REF] Thüm | FeatureIDE: An extensible framework for featureoriented software development[END_REF]) load all the feature models before the product-discovery process starts.

We compare the number of loaded features, the time, and the memory needed to solve a product-discovery problem using a lazy and a standard product-discovery algorithm. In detail, we investigate the following research questions: RQ 1. How is the number of loaded features affected by the choice of a lazy or a standard product-discovery algorithm? RQ 2. How are the speed and memory consumption of product discovery affected by the choice of a lazy or a standard product-discovery algorithm?

In industrial practice, product-discovery tools are often optimized for efficiency at the expense of completeness. As a consequence, there may be product-discovery problems for which solutions exist but no solution is found by the tool. We compare the lazy productdiscovery algorithm to one such state-of-the-art tool by looking at the percentage of cases in which no product is found by the stateof-the-art tool (although products exists), and at the difference in performance for cases when the state-of-the-art product-discovery tool return a correct answer (that is, it either discovers a product or fails when there are no products). For this purpose, we investigate the following research questions: RQ 3. How often does a state-of-the-art product-discovery tool fail because of its incompleteness (i.e., the tool does not discover any product, although there is at least one product)? RQ 4. Is lazy product discovery a feasible alternative to state-of-theart product-discovery tools in terms of execution time and memory consumption?

Experimental Design and Subject

To answer these research questions, we performed experiments on an industrial system with a huge configuration space. We chose Gentoo, a source-based Linux distribution with highly-configurable packages [START_REF]Gentoo Linux[END_REF], which is among the largest fragmented feature models studied in the literature [START_REF] Lienhardt | Multi Software Product Lines in the Wild[END_REF]. The experiments were performed on the March 1st 2019 version of the distribution, that contained 36197 feature models with 671617 features overall.

There are no standard benchmarks for product reconfiguration requests. Therefore, we constructed a set of 1000 product-discovery problems for the evaluation. The problems were generated by randomly selected a set of features (between one and ten) such that each of these features requires the installation of a different package. Solving a product-discovery problem c in this context amounts to computing a Gentoo product that includes any version of the packages associated to the features in c and of other packages such that that all dependencies are fulfilled.

We implemented the algorithm of Listing 1 as a tool. This tool, called pdepa, targets Gentoo's package dependencies, which are defined using an ad-hoc syntax [START_REF]Package Manager Specification[END_REF]. As shown in Example 1, Gentoo's dependencies can be encoded into feature models where features represent both packages and configuration options (called use flags in Gentoo). pdepa parses a package dependency and generates the equivalent propositional formula representing the package feature model. A particularity of Gentoo is that the feature model of a package f can be translated into a propositional representation of the form (F , f → ψ ), where a package selection feature f represents the package f . The pdepa tool exploits this structure of the feature model in the implementation of the key functions pick_cut and compose by using the optimization discussed at the end of Section 5. Specifically, pdepa can avoid loading the feature models of packages whose package selection feature is not in the set Y of required features, when composing cuts (Listing 1, Lines 4 and 8).

As its solving engine, pdepa uses the state-of-the-art SMT solver Z3 [START_REF] Mendonça De Moura | Z3: An Efficient SMT Solver[END_REF], known for its performance and expressivity. Solvers such as Z3 allow constraints to be added incrementally, reusing part of the search done previously without always restarting the search from scratch. This is extremely useful for composing cuts (Listing 1, Lines 4 and 8) since the existing constraints can be reused, only adding incrementally the new constraints not implied by the existing ones. Although this does not formally reduce the complexity of the algorithm, which is NP-hard in the worst case, 3 in practice these optimizations enable a significant speed-up.

To investigate the research question RQ 2, we need to compare pdepa to a standard product-discovery algorithm. Unfortunately, there is no off-the-shelf complete product-discovery tool for Gentoo and therefore we implemented one to establish a baseline for our experiments. We constructed a software that loads all the feature models of all the Gentoo packages and then, as done by pdepa, calls the SMT solver Z3 [START_REF] Mendonça De Moura | Z3: An Efficient SMT Solver[END_REF] to solve the configuration problem. We then compared the results of pdepa to the corresponding results of this baseline tool (baseline for short) in terms of computation time and memory consumption. To ensure a fair comparison, we employ a white-box evaluation, and both pdepa and the baseline use the same implementation for translating the Gentoo dependencies and for loading the feature models.

For research questions RQ 3 and RQ 4, we compare the results of pdepa to the corresponding results of optimized, heuristics-based product-discovery with emerge, the command-line interface to Gentoo's official package manager and distribution system Portage, which is not complete (i.e., it fails to solve some product-discovery problems that have solutions).

All experiments were performed on virtual machines provided by the IaaS OpenStack cloud of the University of Oslo. 4 Every virtual machine had 8 GB of RAM, 2 vCSPUs (2.5 GHz Intel Haswell processors), and was running an Ubuntu 19.04 operating system. The Gentoo operating system was virtualized by running Docker and the image used for the experiments is publicly available. 5

Results and Discussion

This section is organized according to research questions RQ1-RQ4. To facilitate the discussion of the experiments, the figures presenting the different results use a fixed ordering of the 1000 product-discovery problems we considered along the x-axis; this ordering is determined by the number of features loaded by pdepa during its computation for a given problem. Each of the 1000 experiments was repeated 5 times for pdepa, for emerge and for the baseline; Figures 12345report the mean values for each experiment. RQ 1. Figure 1 shows the results of the experiments for research question RQ 1 and reports on the number of features loaded by pdepa to solve each product-discovery problem. To highlight how lazy product discovery performs compared to standard product discovery, which needs to load all features before the analysis can start, these numbers are shown as the percentage of features from the full feature model, for each of the product discovery problems. The product-discovery problems have been sorted along the x-axis according to this percentage. The figure shows the loaded features as a full line, the mean number for all the product discovery problems as a dashed line, and the standard deviation (abbreviated to SD in the figures) as a the bar. We see that for the considered product-discovery problems, the mean number of loaded features is only 1.53% of the overall number of features. In summary, the gain in loaded features when solving each of the considered 1000 product-discovery problems using lazy product discovery over standard product discovery is significant. RQ 2. For research question RQ 2, we compared the speed and memory consumption of product discovery when using pdepa and the baseline on the defined product-discovery problems. For each problem, pdepa loads parts of the FM and calls Z3 incrementally (until a valid product for the whole FM is found), while the baseline first loads the whole FM and then calls Z3.

Figure 2 shows the computation time for product discovery using pdepa (green line) and Figure 3 shows the computation time for product discovery using the baseline. The mean execution time for the baseline is 949 seconds, compared to 78 seconds for pdepa. The minimum and maximum execution times of the baseline are 861.9 and 1222.6 seconds, respectively. The standard deviation for the baseline is negligible (around 35 seconds). It is worth mentioning that about one third of the execution time is devoted to loading the overall feature model, while the remaining time is taken by Z3. The minimum and maximum execution time of pdepa are 1.7 and 155.22 seconds, respectively. The standard deviation is lower than the one for the baseline, about 18 seconds. The maximum computation time of pdepa is less than one third of the computation time used by the baseline to simply load the overall feature model, and it is about the 16% of the minimum execution time of the baseline.

Figure 4 shows the memory consumption for product discovery using pdepa (green line) and Figure 5 shows the memory consumption for the baseline. The mean memory consumption for the baseline is 3,919.4 MB, compared to 400.715 MB for pdepa. The minimum and maximum memory consumption of the baseline are 3016 and 3980 MB, respectively. About 1 GB of the used memory here is for the feature model itself. The standard deviation for the baseline is negligible (about 70.84 MB). The 7 memory consumption values that fall outside the standard deviation correspond to the product discovery problems that have no solution. The minimum and maximum memory consumption of pdepa are 73 and 620 MB, respectively. The standard deviation, 67.38 MB, is about the same as for the baseline. The maximum memory consumption of pdepa is about 19.62% of the minimum memory consumption of the baseline.

The experiments show a clear correlation between the time and the memory taken by pdepa to solve a product-discovery problem and the number of features loaded by pdepa (cf. Figure 1).

In summary, the experiments clearly demonstrate that lazy product discovery allows significant speed-up and significant reduction of memory consumption, compared to standard product discovery. RQ 3. We investigated the failures of a heuristics-based incomplete product-discovery tool (emerge) compared to the cases when the complete lazy product discovery algorithm showed that no solution exists, for the 1000 considered product-discovery problems. Figure 6 shows the product-discovery problems for which emerge does not find a product (red and blue bars). For the considered product-discovery problems, emerge fails to find a valid configuration in 26.7% of the cases. In 0,7% of the cases (red bars), no solution exists. Therefore, in 26% of the cases, emerge fails to solve a product-discovery problem that has a solution. The experiments show an interesting correlation between the failures of emerge observed in Figure 6 and the number of features loaded by pdepa during the product-discovery process: the failures of emerge occur more frequently as the number of loaded features needed for lazy product discovery increases. This can be seen since the sorting of the x-axis is the same in Figures 1 and6. In summary, on 1000 randomly selected product-discovery problems, emerge fails to find a solution that exists in around 26% of the cases. RQ 4. For research question RQ 4, we investigated how well pdepa performs as an alternative to the state-of-the-art configuration tool emerge. Figure 2 shows the time for product discovery using pdepa (green line) and emerge (blue line). The light green and the light blue bars show the standard deviations and the correspondingly colored dashed lines show the mean times in seconds for pdepa and emerge, respectively. The difference in mean times suggests that pdepa is 11.29 times slower than emerge in average, which corresponds to 70 additional seconds. However, as the results for RQ 3 above shows that emerge fails for a significant number of the considered product-discovery problems, lazy product discovery appears to be a feasible alternative to emerge. Figure 4 shows the memory consumption for product discovery using pdepa (green line) and emerge (blue line). The light green and the light blue bars show the standard deviations and the corresponding colored dashed lines show the mean memory consumption in MB for pdepa and emerge, respectively. The difference in mean times suggests that pdepa consumes four times more memory than emerge in average (which amounts to around 300 MB).

In summary, lazy product discovery appears as a feasible alternative to emerge if around one order of magnitude additional computation time and four times additional memory consumption are acceptable to always find products when these exist. problems that were randomly selected from the 671617 features of the March 1st 2019 version of the Gentoo distribution. The random selection used the standard random python library [START_REF]random -Generate pseudo-random numbers[END_REF], that allows to get a set of elements uniformly chosen from a given set. Different product-discovery problems could potentially lead to different results. We plan to investigate other product-discovery problems for Gentoo and for other domains to get more insights. In particular, it would be interesting to investigate how lazy product discovery performs when varying both the size and the amount of interdependencies of the feature models (see Section 2).

Threats to Validity

Internal

Validity. We used prototype implementations of the lazy product-discovery algorithm and of the standard productdiscovery algorithm. Both implementations rely on the Z3 solver [START_REF] Mendonça De Moura | Z3: An Efficient SMT Solver[END_REF]. Z3 was chosen because it is a mature solver and freely available. The standard product-discovery algorithm just performs a call to the Z3 solver. The lazy product-discovery algorithm calls the Z3 solver whenever a new feature fragment is loaded. Using a different solver than Z3 may affect the execution time and memory consumption of both the standard and the lazy product-discovery algorithms. We plan to repeat the experiments using another solver.

Introducing optimizations in the lazy product-discovery algorithm could potentially reduce the number of loaded features, the execution time, and the memory consumption for the algorithm. One possible optimization could be to pre-compute at compile time the modal implication graphs [START_REF] Di | On software component coinstallability[END_REF][START_REF] Krieter | Propagating Configuration Decisions with Modal Implication Graphs[END_REF] of features, which could potentially avoid loading feature models that, e.g., are found to be conflicting in the pre-analysis. Another possible optimization could be the definition and usage of an ad-hoc search strategy for the back-end solver, instead of using solver's default search strategy.

Another threat to validity is that Gentoo's package dependencies are not formally specified, but only given in a textual representation. To reduce the probability of errors in the implementation of the lazy product-discovery algorithm, we have used unit tests to compare the results of pdepa with known correct products. These unit tests were performed by extending the package repository of portage with custom testing and interdependent packages.

Possible bugs in Gentoo's package manager may also be considered a threat to validity. When performing the experiments, we identified the following surprising behavior in emerge:

(1) For some sets of packages 6 , emerge implements a heuristic that only considers the feature model of the most recent package in the set, thus forgetting possible solutions. (2) For emerge to consider a package, some part of its feature model must be configured. Specifically, some of its features must be selected or deselected such that the constraint identified by the variable REQUIRED_USE [START_REF]Package Manager Specification[END_REF] evaluates to true. (3) For a given product-discovery problem, the dependency analysis of emerge considers each package individually. This can trigger the installation of a package in conflict with the rest of the product-discovery problem, thus preventing the product-discovery problem to be solved even if it has a solution.

We reported these issues to the Gentoo developer community, which replied that they could be considered as bugs of emerge.

We were not able to install the Gentoo variants corresponding to the products discovered by pdepa because of Bug (3) above. Indeed, in many cases, emerge's dependency solver triggers the installation of packages that conflict with pdepa's solution. We plan to overcome this limitation by extending pdepa into a complete package installation tool for Gentoo.

RELATED WORK

We discuss related work on interfaces, composition, and configuration of feature models.

Interfaces of Feature Models. The feature-model cut in this paper strengthens the feature-model interfaces introduced by Schröter et al. [START_REF] Schröter | Feature-Model Interfaces: The Highway to Compositional Analyses of Highly-Configurable Systems[END_REF], which, as pointed out in Section 3.2, are closely related to feature model slices introduced by Acher et al. [START_REF] Mathieu Acher | Slicing feature models[END_REF]. In the work of Acher et al. [START_REF] Mathieu Acher | Slicing feature models[END_REF], the focus is on feature model decomposition. In subsequent work [START_REF] Acher | Extraction and Evolution of Architectural Variability Models in Plugin-based Systems[END_REF], Acher et al.address evolutionary changes for extracted variability models by using the slice operator in combination with a merge operator, and focus on detecting differences between feature-model versions during evolution. Instead, Schröter et al. [START_REF] Schröter | Feature-Model Interfaces: The Highway to Compositional Analyses of Highly-Configurable Systems[END_REF] study how feature model interfaces can be used to support evolution for a feature model composed from feature models fragments. Changes to fragments which do not affect their interfaces do not require the overall feature model to be rebuilt (by composing the fragments) in order to reanalyze it. Challenges encountered to support evolution in software product line engineering have previously been studied by Dhungana et al. [START_REF] Dhungana | Structuring the modeling space and supporting evolution in software product line engineering[END_REF]. They use interfaces to hide information in feature model fragments and save a merge history of fragments to give feedback and facilitate fragment maintenance. No automated analysis is considered. In contrast to this work on feature model interfaces for evolution, the cut in our work is for efficient automated product discovery in huge feature models represented as interdependent feature model fragments.

Feature-model views [START_REF] Hubaux | Towards Multi-view Feature-Based Configuration[END_REF][START_REF] Mannion | Viewpoint-Oriented Variability Modeling[END_REF][START_REF] Schroeter | Multi-perspectives on Feature Models[END_REF] focus on a subset of the relevant features of a given feature model, similarly to feature-model interfaces. Different views regarding one master feature model are used to capture the needs of different stakeholders, so that a product of the master feature model can be identified based on the views' partial configurations. This work on multiple views to a product in a feature model is orthogonal to our work on feature-model cuts, which targets the efficient configuration of systems comprising many interdependent configurable packages.

Composition of Feature Models. Feature-model composition is often used for multi software product lines (i.e., sets of interdependent product lines) [START_REF] Holl | A systematic review and an expert survey on capabilities supporting multi product lines[END_REF][START_REF] Krueger | New Methods in Software Product Line Development[END_REF][START_REF] Lienhardt | Multi Software Product Lines in the Wild[END_REF][START_REF] Rosenmüller | Automating the Configuration of Multi Software Product Lines[END_REF]. Eichelberger and Schmid [START_REF] Eichelberger | A Systematic Analysis of Textual Variability Modeling Languages[END_REF] provide an overview of textual-modeling languages which support variability-model composition (like FAMILIAR [START_REF] Mathieu Acher | FAMILIAR: A domain-specific language for large scale management of feature models[END_REF], VELVET [START_REF] Rosenmüller | Multi-dimensional Variability Modeling[END_REF], TVL [START_REF] Classen | A text-based approach to feature modelling: Syntax and semantics of TVL[END_REF], VSL [START_REF] Abele | The CVM Framework -A Prototype Tool for Compositional Variability Management[END_REF]) and compare how they support composition, modularity, and evolution. Acher et al. [START_REF] Mathieu Acher | Composing Your Compositions of Variability Models[END_REF] compare different featuremodel composition operators by considering possible implementations and discuss advantages and drawbacks. For the investigation of efficient automated configuration of huge feature models in this paper, we use the propositional representation of feature models and a composition operator that corresponds to logical conjunction.

Configuration of Feature Models. Product discovery (also called product configuration or product derivation) is the process of selecting and deselecting features in a feature model in order to obtain a product [START_REF] José | Automated analysis of feature models: Quo vadis?[END_REF]. This is a central and widely studied problem in the field of automated reasoning [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF]; e.g., more than 50 different methods for product discovery are discussed in a recent survey [START_REF] José | Automated analysis of feature models: Quo vadis?[END_REF].

We are not aware of any method that addresses how complete and efficient product-discovery can be achieved in configuration spaces comprising different interdependent feature model fragments without composing all the fragments. The tool for lazy product discovery is in the class of product discovery tools which automatically produce valid configurations.

Automated configuration is supported by a number of tools, including FeatureIDE [START_REF] Thüm | FeatureIDE: An extensible framework for featureoriented software development[END_REF], GEARS [START_REF] Krueger | Feature-based systems and software product line engineering with gears from BigLever[END_REF], GUIDSL [START_REF] Batory | Feature Models, Grammars, and Propositional Formulas[END_REF], IBED [START_REF] Xue | IBED: Combining IBEA and DE for optimal feature selection in software product line engineering[END_REF], Hy-VarRec [START_REF] Mauro | Context Aware Reconfiguration in Software Product Lines[END_REF], SATIBEA [START_REF] Henard | Combining Multi-Objective Search and Constraint Solving for Configuring Large Software Product Lines[END_REF] S2T2 Configurator [START_REF] Botterweck | A Design of a Configurable Feature Model Configurator[END_REF], SIP [START_REF] Hierons | SIP: Optimal Product Selection from Feature Models Using Many-Objective Evolutionary Optimization[END_REF], SPL Conqueror [START_REF] Siegmund | SPL Conqueror: Toward optimization of non-functional properties in software product lines[END_REF], S.P.L.O.T. [START_REF] Mendonça | software product lines online tools[END_REF], and VariaMos [START_REF] Mazo | VariaMos: a Tool for Product Line Driven Systems Engineering with a Constraint Based Approach[END_REF]. However, in contrast to our work, all these tools are eager and require the building of the global feature model by composing all its fragments. As such, these tools are in line with the standard product discovery algorithm, as discussed in Section 6.

Some of these standard product discovery tools are interactive, i.e., they support and interact with the user by guiding her in producing a valid configuration or finding one that maximizes her preferences [START_REF] Batory | Feature Models, Grammars, and Propositional Formulas[END_REF][START_REF] Botterweck | A Design of a Configurable Feature Model Configurator[END_REF][START_REF] Mazo | VariaMos: a Tool for Product Line Driven Systems Engineering with a Constraint Based Approach[END_REF][START_REF] Mendonça | software product lines online tools[END_REF]. Our method for lazy product discovery can be exploited to support interactive product discovery either (i) by requiring the user to enter preferences over different configurations or (ii) by interacting with the user when deciding what partial configuration should be extended (i.e., when the select function of the algorithm in Listing 1 is performed). An extension of the lazy product discovery algorithm in this direction is left as future work.

Different computational techniques can be used to solve the product discovery problem: satisfiability solvers, constraint programming, evolutionary algorithms, stochastic algorithms, or binary decision diagrams [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF][START_REF] Benavides | FAMA: Tooling a framework for the automated analysis of feature models[END_REF][START_REF] Ochoa | A survey on scalability and performance concerns in extended product lines configuration[END_REF]. Due to the NP-hardness of the configuration problem itself, most complete approaches rely on SAT solvers [START_REF] Janota | Do SAT Solvers Make Good Configurators?[END_REF][START_REF] Mendonça | SATbased Analysis of Feature Models is Easy[END_REF], but more recently, the use of more powerful backend solvers, such as constraint solvers and SMT solvers, are starting to be explored for automatic configuration of feature models [START_REF] Benavides | Using Constraint Programming to Reason on Feature Models[END_REF][START_REF] Mauro | Context-aware reconfiguration in evolving software product lines[END_REF][START_REF] Michel | An SMT-based approach to automated configuration[END_REF][START_REF] Thüm | [END_REF]. In our work, we have used Z3 [START_REF] Mendonça De Moura | Z3: An Efficient SMT Solver[END_REF] which is one of the most powerful and mature SMT solvers available today. We would like to remark, however, that the lazy product discovery method itself is orthogonal to the tool chosen, as long as the backend solver allows to implement the pick_cut, compose, and select operations of Listing 1.

CONCLUSION AND FUTURE WORK

Product discovery in huge configuration spaces represented as sets of interdependent feature models is challenging. Standard analysis techniques for fragmented feature models require all the feature models to be composed in order to apply the analysis. Recent work has shown that several analyses of fragmented feature models can be simplified using techniques such as feature model interfaces and slicing, however these techniques do not work for product discovery in sets of interdependent feature models.

In this paper, we introduce a method for automated product discovery in configuration spaces represented as sets of interdependent feature models. The method is lazy as features are added incrementally to the analysis until a product is found. We introduce and formalize the feature model cut, and leverage this concept to define a product-discovery criterion. We exploit this criterion to define a complete and efficient algorithm for lazy product discovery in sets of interdependent feature models. We have evaluated the potential of lazy product discovery on randomly constructed configuration problems for the configuration space of the source-based Linux distribution Gentoo, with 36197 interdependent feature models and a total of 671617 features. The evaluation has demonstrated significant gains compared to standard product discovery and that the trade-off of performance for completeness is reasonable compared to the heuristics-based product-discovery with emerge, the command-line interface to Gentoo's official package manager and distribution system Portage.

We are now investigating different optimizations of the current prototype, such as the exploitation of modal implication graphs pre-computed at compile time and the usage of ad-hoc SMT search strategies. In future work we plan to investigate other productdiscovery problems for Gentoo as well as for other domains, to gain more insights into lazy product discovery. While our results make us confident that lazy product discovery is a viable method for product discovery in huge configuration spaces, we believe that it may also be used to complement optimized but incomplete algorithms when these fail, such as emerge for Gentoo. We also plan to investigate how lazy product discovery can be combined with interactive product discovery.

( 1 )

 1 pick_cut(M, Y ): a function that, given a feature model M and a set of features Y , returns a cut of M for Y ; (2) compose({M 1 , . . . , M n }): a function that, given a set of feature models M 1 , . . . , M n , returns the composition of the feature models in the set; and (3) select(M, c): a function that, given a feature model M and a set of features c, returns a product of M containing all the features in c if it exists, and None otherwise.

  The feature model interface in Example 3 can be obtained by applying Π {glibc, glibc:v} to the feature model M glibc of Example 2.

E 8 (

 8 A glibc FM). Consider the feature model M glibc of Example 2 and Y = {glibc, glibc:doc}. The minimal cut ⊥ Y (M glibc ) can be computed by starting with the feature model (Y

Figure 3 :

 3 Figure 3: Baseline execution time.

6. 3 . 1 Figure 4 :Figure 5 :

 3145 Figure 4: Memory consumption for pdepa and emerge.

Figure 6 :

 6 Figure 6: Product-discovery problems with no solution and emerge failures.

  it is clear by construction that P ′ Y ⊆ P. Moreover, if we write P ′ = {p ∈ P | ∀p ′ ∈ P \ {p},p ′ p}, it is clear from the definition of f that P ′ ⊆ P ′ Y . Suppose that the set M = {p ∈ P | p ∩ F ′ Y P ′ Y } is not empty and consider p 1 a minimal element of M w.r.t. ⊆. Since p 1 F ′ Y , by definition of P ′ , the set N = {p ′ ∈ P ′ Y | p ′ ⊆ p 1 } is not empty. Consider any maximal element p 2 of N w.r.t. ⊆. Since p 1 ∩ F ′

	(p 1 \ p 2 ) ∩ F ′ Y ((p 1	Y ∅, and so the condition ∀p ′ ∈ P, (p ′ p 1 ) ⇒ P ′ Y , we have

The NP-hardness derives immediately from the NP-hardness of the problem of finding a valid model for a propositional formula.

https://www.uio.no/english/services/it/hosting/iaas/

https://hub.docker.com/r/gzoumix/pdepa

These sets consisted of packages with an identical SLOT[START_REF]Package Manager Specification[END_REF]. SLOTs are used in portage to identify which versions of the same package can coexist in one system.

ACKNOWLEDGMENTS

This work is partially funded by the Sirius Center for Scalable Data Access and the Compagnia di San Paolo. We thank the reviewers for constructive feedback, Thomas Thüm, Andrzej Wasowski and Sven Apel for useful discussions on the topic of this paper, and Simone Donetti for testing the publicly available artifact.


Daniel Bosmans

AND COGNITIVE PRESENCE OF THE STUDENT TEACHER IN THEIR LX ONLINE CLASSROOM

Keywords: Foreign Language Anxiety (FLA), Virtual Learning Environment (VLE), Community of Inquiry (CoI), Online presence

d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

The health crisis of 2020 has been the cause of many changes in human activity and the world of education has not been spared. Not only have courses at many institutions switched from face-to-face to virtual mode, but end-of-year evaluations have also been modified in this way. At HEP-BEJUNE1 , students in their 3 rd year of initial teacher training had to take their English micro-teaching exam in June 2020 in a virtual environment. Did they feel more comfortable during their evaluation of teaching English online or, on the contrary, would they have preferred to take their exam face-to-face? What impact has the virtual learning environment (VLE) had on the emotional aspect of their online social presence? The 1 st year students, on the other hand, had to present a cultural element of the Englishspeaking world in groups of three in the same environment and similar questions about their experience can also be asked, which brings us to the research question of the present study: Does the student teacher perceive the virtual context in their online L3 classroom as helping or inhibiting their social, teaching and cognitive presence?

1. What indicators of the three kinds of virtual presence of the CoI model can be observed during an online assessment? 2. What impact has the virtual learning environment (VLE) on the emotion indicator of their online social presence? 3. When the level of anxiety fluctuates between face-to-face and VLE evaluations, what is the most prominent cause?

LITERATURE REVIEW

The Community of Inquiry (CoI) model originally created by [START_REF] Lipman | Thinking in Education[END_REF][START_REF] Lipman | Thinking in Education[END_REF] is a framework that has already been used in several studies exploring the experience of online learning [START_REF] Annand | Social Presence within the Community of Inquiry Framework[END_REF][START_REF] Garrison | Exploring causal relationships among teaching, cognitive and social presence: Student perceptions of the community of inquiry framework[END_REF]. In this model, the teacher takes on several roles as defined in [START_REF] Garrison | Critical Inquiry in a Text-Based Environment: Computer Conferencing in Higher Education[END_REF]. They categorize the e-learning experience and subdivide it into the cognitive, social and teaching presence for the practitioner as well as the students (see Fig. 1). These three presences all interact to "improve the practice of using online conferencing in university education" (Garrison, Anderson & Archer, 2001, p.8). Annand (2011, p.1) helps us situate the CoI framework which "has transformed from describing a learning process in a socio-constructivist paradigm to a concept that can be tested empirically in an objectivist paradigm". We therefore no longer look at the process of co-construction which according to some critics of the CoI [START_REF] Annand | Social Presence within the Community of Inquiry Framework[END_REF] is not the most effective to describe learning in a virtual environment but we are moving here towards an objectivist epistemology, given that this study explores how students felt during their final assessment.

As mentioned above, the CoI is not without its critics [START_REF] Annand | Social Presence within the Community of Inquiry Framework[END_REF][START_REF] Rourke | Learning in communities of inquiry: A review of the literature[END_REF]. These claim that the learning does not happen according to the constituents of the model and that it does not go as deep as it should. Naturally, the model focuses on the learning process and not on its object whose evaluation can be measured. Although part of an objectivist epistemology, this project also succeeds in deepening our knowledge of the learning process by exploring more closely one of the more neglected aspects of social presence, emotions, as well as language anxiety, a phenomenon otherwise well documented in foreign language research. Social presence is only one of the three kinds of presence that support successful online learning, as shown in fig. 1, and this presence can be uniquely altered when the object is the teaching of a foreign language.

Fig. 1: Elements of an educational experience [START_REF] Garrison | Critical thinking, cognitive presence, and computer conferencing in distance education[END_REF] According to the CoI model, "social presence is indicated by the subcategories of emotional expression, open communication and group cohesion" (Cleveland-Innes & Campbell, 2012, p. 281).

We will focus a little more on social presence in this project in terms of emotions and more particularly language anxiety (explained below), one of the emotions that has the greatest impact on the performance of students who will soon teach an L3. The development of new skills when transitioning to online education may itself elicit an emotional response [START_REF] Cleveland-Innes | Emotional Presence, Learning, and the Online Learning Environment[END_REF]. This can often prove to be debilitating for the trainee (as well as the experienced practitioner) initially but become empowering when these skills are better mastered over time and use. Trying to introduce innovations in teaching without taking emotion into account is a mistake because it must be seen as part of the learning context [START_REF] Lipman | Thinking in Education[END_REF]. Cleveland-Innes and Campbell (2012) note that emotion plays a much more dynamic role in learning than simply hindering rational thinking. It can also help in the formation of explicit memories [START_REF] Ledoux | The emotional brain: The mysterious underpinnings of emotional life[END_REF] and this is even more the case when the object of learning is a foreign language. [START_REF] Lipman | Thinking in Education[END_REF] mentions the emotion related to critical thinking within the CoI and shows that it cannot be dissociated from learning. Garrison, Anderson and Archer (1999, p. 99), on the other hand, speak of "the expression of emotion as one of the indicators of social presence". According to them, it is not only having the skill but also the self-confidence to be able to "express the emotions of the learning experience" as this can directly influence one's success. The loss of physical presence when teaching and learning online can then take the form of emoticons during messages exchanged in written conversations (chat box). In the present study, this feeling of social and emotional connection was mentioned in the testimonies collected from the participants.

Turning now to the second aspect of our problem, several studies in research on language acquisition have shown that anxiety is probably the affective factor that most influences the learning of a foreign language, the other factor being motivation [START_REF] Arnold | A map of the terrain[END_REF][START_REF] Bosmans | Phonological attainment and foreign language anxiety in distance language learning: a quantitative approach[END_REF][START_REF] Dörnyei | The psychology of the language learner -Individual differences in second language acquisition[END_REF][START_REF] Horwitz | Foreign language classroom anxiety[END_REF]. This is the reason why this emotion has taken on more and more importance in the literature on foreign language acquisition (for a review of this literature, see Al-Shboul, Ahmad, Nordin, & Rahman, 2013). Several data collection instruments have also been developed and used extensively and we will use one of them in this project, the Foreign Language Classroom Anxiety Scale (FLCAS) by Horwitz et al. (1986, p. 129).

From an L3 student to a trainee teacher, there is only one step, and this emotion is always present in future general practitioners who continue to work on their mastery of their L2 and L3 throughout their teacher training. This is therefore an essential variable to highlight and to confront with a potential increase or decrease in stress or anxiety due to the new virtual context. [START_REF] Conrad | Engagement, excitement, anxiety, and fear: Learners' experience of starting an online course[END_REF] notes that anxiety is part of online learning, general anxiety coming here in addition to language anxiety. Fear and anxiety about the new learning environment is real [START_REF] Zembylas | Adult learners' emotions in online learning[END_REF], but the VLE can sometimes be an enabling rather than a debilitating factor when it comes to language anxiety, as explained below.

According to MacIntyre and Gregersen (2012), negative emotions such as worry and fear are included in language anxiety and are triggered by the simple fact of having to speak in the foreign language. If this anxiety is accompanied by a specific situation such as an exam or oral presentation, the effects can be cumulative (Ellis, 2008, p.691). Hurd (2007, p. 500) found in her study that studying a foreign language at a distance could, for some students (27%, so almost a third of the participants in her study) be less anxiety-provoking than having to speak the language in a traditional classroom in front of other people. However, it should not be deduced from this that language anxiety is always a negative emotion. Although most studies have found the debilitating effects of anxiety on language performance (see [START_REF] Horwitz | Language anxiety and achievement[END_REF] for a summary of the literature on these negative effects), some researchers such as Dörnyei (2005, p. 198) have found positive effects and have therefore called this anxiety 'facilitating'.

If we now want to bring these two aspects of our discussion together, Cleveland-Innes and Campbell (2012) argue that emotional presence is not just one of the indicators of social presence in the CoI model but that it underpins all online learning and could therefore be considered a presence in its own right. It may be premature to assert this emotional presence as a separate category for all online learning, but it may well be observable for foreign language learning, given the affective and emotional nature of the field which presents its own emotions such as enjoyment, motivation and anxiety. Lehman (2006, p.13) tells us about presence as "the dynamic interplay between emotion, behaviour, cognition and the environment". This will certainly be the case in the language classroom where emotion can positively or negatively influence other variables. Annand (2011, p. 13) notes that "research based on the CoI model has so far not incorporated or sufficiently investigated student-initiated unstructured efforts on social presence". He adds that there is therefore a need to determine more precisely the relative influence of subcategories of the group's social presence on the learning process. We believe that exploring here one of the indicators of social presence, i.e., emotion, is a step towards this objective, all the more appropriate since it refers to an emotion well referenced in literature on foreign language acquisition. Garrison, Anderson and Archer (1999) themselves include the expression of emotions in their indicators of social presence and maintain that this can be a factor which directly contributes to the success of learning since participants are invited to project themselves as real people, both socially and emotionally during these online interactions.

METHODOLOGY

According to Annand (2011, pp. 1-2), "one of the means of research in tertiary distance education remains the CoI proposed by [START_REF] Garrison | Critical Inquiry in a Text-Based Environment: Computer Conferencing in Higher Education[END_REF]". He adds that the social presence category (see fig. 1) is the "projection of the learner's personal characteristics into a community of inquiry (CoI) by, among other things, the expression of emotions". It is therefore a coding scheme inspired by [START_REF] Garrison | Critical Inquiry in a Text-Based Environment: Computer Conferencing in Higher Education[END_REF] that was used to analyze students'

Mooc2Move Conference on "MOOCs, Language learning and Mobility: design, integration, reuse" 9 -10 April 2021 feelings during their online assessment and to establish the resulting taxonomy and thus address our first research question. This scheme incorporates elements from the Foreign Language Classroom Anxiety Scale (FLCAS) developed by Horwitz et al. (1986, p. 129) to anchor the project in a language context, but not only. It is also a question of eliminating from the anxiety indicator a linguistic origin rather than a cause due to the virtual context, in order to better isolate this variable.

The data were obtained through four online questionnaires (SurveyMonkey) sent to all 1 st and 3 rd -year students who took the English option at HEP BEJUNE (two questionnaires per level), accompanied by the consent form and an information sheet about the project. Participants had the choice of responding in English or French, which is reflected in the quotes below which have been reproduced as is, without making any lexical or syntactic corrections.

The qualitative data were coded according to pre-established themes and a classification was then carried out by type of presence (social, cognitive or Perceptions and feelings about the virtual context are indicated through positive or negative indicators summarizing the participants' comments. Quantitative FLA data was then calculated, simply adding up the Likert scale scores for each participant and categorizing them into three anxiety levels, just as [START_REF] Cheng | The relationship of foreign language anxiety of oral performance achievement, teacher characteristics and in-class activities[END_REF] reported: low anxiety level of 10 % to 25%, moderate from 26% to 75% and high from 76% to 100%. As two of the FLCAS items were written negatively to avoid automated responses, these scores were reversed.

RESULTS

The 1 st -year students were assessed on the quality and content of a presentation that did not require interaction. For the 3 rd -year students, the evaluation being carried out in the form of a micro-teaching session, and therefore including an interactive element, we obtained much more negative results in terms of feelings towards the VLE. In general, the FLA level is moderate for all groups, with a slightly higher number of 3 rd -year students experiencing language anxiety (see table 1). This is perhaps due to their mastery of L3 which is generally lower than in their 1 st year; indeed, the B2 exam is far behind them, and the demands of their curriculum may prevent them from practicing their L3 as much as they would like or should do. Another reason may also be the greater difficulty of the oral production genre.

It is indeed more difficult to interact (such as in a micro-teaching task for 3 rd -year students) in an L3 than to speak continuously (such as in a presentation of a cultural aspect for the 1 st -year students). The second part of the questionnaire included a question requiring the listing of all possible causes of anxiety in descending order. For the 1 st years, the level of language anxiety only came in second place among the sources of stress cited, coming directly after the exam situation which was the main source of anxiety for both groups. The use of technology came third and the format of the review (the fact that it is a presentation) last. Third-year students found online education more unsettling than their language anxiety, which shares third place with the use of technology. In order to synthesize the results of the qualitative data in the light of the CoI model, it is now essential to establish a taxonomy by kind of presence that the indicators describe. 'Pas vraiment besoin de faire attention à notre posture si on est assis.' (voir aussi l'indicateur commode ci-dessus qui pourrait être interprété comme manque de professionnalisme) 'J'aime bien présenter en face-à-face car il est plus simple de rendre la présentation intéressante et dynamique.' 'I don't like it because it's hard to think of way to make the students be actives and work together.' 'but they create "fake" learning conditions: I don't teach using these tools, not do I intend to (at least not as a primary environment).' 'I couldn't do exactly the exercise as I would have done it I was in a classroom (using the blackboard, make the students work in pair, etc)' 'And it removes one of the main canals: movement. Adults need it less, children can't learn without it.' 'because you are very limited (work in pairs, games, material, etc.)' Pour 60% des 3ème années 'I'm not used to teach online and I find it difficult to change our habits.' 'c'est difficile de connaître les besoins des élèves.' '[teaching f2f] also allows a global view on the children, and the ability to analyze their attitudes and moods to offer interactive and efficient regulations.' 'teaching is a social skill. It implies too many physical communication to be rendered efficiently online.' 'My keyword is "efficiency", I think face-to-face teaching is more efficient. Online teaching is not inefficient, but requires a lot more time to bring anything worth it (for the teacher AND the student both).'

Positive Indicators Citations

CONCLUSION

The present study answered several questions. The increased anxiety of students in assessment situations is partly due to the object of learning and teaching, at least in a more visible way for the third-year students. However, the root cause of stress remains the assessment situation, which is somewhat exacerbated by the context in which it takes place. A taxonomy of indicators shedding light on the three sorts of teacher presences was also established, especially for the emotional indicator of social presence, both in negative and positive terms. This allowed us to ascertain a more balanced view of the impact of the virtual context on the evaluation of teachers in training. Our knowledge of online social presence indicators has therefore increased thanks to the testimonials collected for this project.

The pandemic has created new challenges, both for teachers and their students. One of these challenges is to help our students control their emotions during online assessments and therefore to integrate learning strategies for this purpose. We need to think urgently about our reaction as educators. This involves building assessment strategies that will not exacerbate the problem, but which will take into account the negative emotions impacting their performance.

Table 1 :

 1 Language Anxiety Levels (FLA)

	FLA Level	1st Years	3rd Years	All Groups
	Low	0%	0%	0%
	Moderate	92%	83%	89%
	High	8%	17%	11%

Haute Ecole Pédagogique des Cantons de Berne, Jura et Neuchâtel, Switzerland, a teacher education university, part of swissuniversities

ACKNOWLEDGEMENTS

I should like to thank students at the Haute Ecole Pédagogique for taking part in this project.