Jannik Laval

Simon Denier

Stéphane Ducasse

Andy Kellens
email: akellens@vub.ac.be

Supporting Incremental Change in Large System Models

Keywords: D.2.7 [Software Engineering]: Distribution, Maintenance, and Enhancement-Restructuring, reverse engineering, and reengineering; D.3.2 [Programming Languages]: Smalltalk design, model, version, software analysis, object-oriented language, Smalltalk

When reengineering large systems, software developers would like to assess and compare the impact of multiple change scenarios without actually performing these changes. A change can be effected by applying a tool to the source code, or by a manual refactoring. In addition, tools run over a model are costly to redevelop. It raises an interesting challenge for tools implementors: how to support modification of large source code models to enable comparison of multiple versions. One naive approach is to copy the entire model after each modification. However, such an approach is too expensive in memory and execution time. In this paper we explore different implementations that source code metamodels support multiple versions of a system. We propose a solution based on dynamic binding of entities between multiple versions, providing good access performance while minimizing memory consumption.

INTRODUCTION

Software architecture evolution, change impact analysis, software quality prediction, remodularisation and so on, are important tasks in a reengineering process. They often require developers to be able to compare different versions of a system to pick the most adequate path of changes.

Let us consider a typical reengineering session: the reengineer might apply a visualization, then perform an analysis, apply other analyses or visualizations, then perform some refactorings. Afterwards, the reengineer would like to reapply the original visualization to assess whether the proposed changes had a positive impact on the system. While iterating several times, he may pick one version and roll-back to the previous one, reapply some changes and finally apply the changes to the actual software.

All these operations should be performed on the model of the source code. If we step back from this scenario we see that we must have a model of the software. It must allow one to compare different versions of a model and branch, modify, and navigate through these different versions.

The question is: how do we support these model manipulations (editing, comparison...) for large source code models and many small modifications? A naive idea is to make a copy of the original model and to modify it for each version. However, a lot of memory is wasted by copying non-modified elements. For example, modifying one package in a system with 100 packages requires make 99 useless copies.

In this paper, we present several possible high approaches to support simultaneous multiple versions of models. We discuss the pros and cons of each approach. As a compromise between memory consumption and the time needed to access elements within model versions, we have implemented an approach based on dynamic binding of entities across a tree of shared models.

This paper is organized as follows. Section 2 presents the running example used throughout the paper. Section 3 presents the chosen source code metamodel. Section 4 presents the design space we explored to keep track of multiple versions of a source code model, along with the pros and cons of each possible solution. Section 5 presents our solution. Section 6 discusses about our solution and future work. Finally, we conclude this paper in section Section 8.

RUNNING EXAMPLE

presents an example system, which contains one package containing three classes (ClassA, ClassB and ClassC). Within the example we have four methods, such that method mA2() invokes mA1() and method mB2() invokes mB1(). Suppose we evolve the example system into a new version by applying the following changes: method mB1() is moved to ClassA; ClassC is removed. Note that these modifications also have an impact on the other entities in the model: ClassA needs to be aware that a new method was added; ClassB needs to know that method mB1() was removed and package Pack1 has to be notified that it no longer contains Class C.

We present in Section 4 a number of approaches that enable keeping track of versions of a source code model. Based on the above example we discuss the pros and cons of each of these ap-proaches.

FAMIX

FAMIX is a language independent metamodel. It describes the static structure of software systems, particularly object-oriented software systems. A class-diagram representation is available at http: //moose.unibe.ch/docs/famix/famix3.0.

FAMIX is based on the meta-metamodel FM3 (Fame Meta-metamodel) which is a superset of a subset of EMOF [START_REF] Kuhn | FAME, a polyglot library for metamodeling at runtime[END_REF]. Since a discussion of the FAMIX metamodel lies outside the scope of this paper, we refer the interested reader to [START_REF] Demeyer | FAMIX 2.1 -The FAMOOS Information Exchange Model[END_REF].

FAMIX has a lot of analysis tools thanks to the Moose Framework and Mondrian visualization tools. It allows us to build visualization, compute metrics and provides some more complex tools as Hismo ([G 05]) or Dynamix [START_REF] Greevy | Dynamix -a meta-model to support feature-centric analysis[END_REF]).

Since we place our work in the context of the FAMIX metamodel, we apply the following constraints:

• We need a change model which does not impact other aspects of the FAMIX metamodel such as metrics, relationships, and so on. Each version of a model should be usable with any tool based on FAMIX, in order to maximize the reuse of existing tools.

• It should also allow reengineers to compare versions.

Figure 2 represents a FAMIX model of Figure 1 example. All classes and methods have a parent package. Associations between entities (invocations, variable accesses, inheritance links and class references) are reified and are explicitly known by the two entities involved.

An important feature of FAMIX 3.0 is that all relationships are bidirectional. So, attribute automatically updates the other side of the relationship (opposite) entities. For example, when mB1() is moved from ClassB to ClassA, this information is propagated in mB1(), ClassA and ClassB.

In Figure 2, the dotted line represents the link between mB1() and ClassB in the left of Figure 1. The bold lines represent modifications done in the second version: mB1() is now in ClassA and ClassC is removed. There are multiple ways of representing different versions of a particular FAMIX model. Four naive approach are presented in this section:

APPROACHES FOR MODELING MUL-TIPLE MODIFICATIONS OF A FAMIX MODEL

• Copy Approach, where the entire model is copied to a new model.

• Delta Approach, which keeps track of the delta (changes) between the original and the new model.

• a LookUp Approach based on creating a partial copy of the model.

• a mixed LookUp/Copy Approach also based on creating a partial copy of the model.

We now present each approach and analyze its performance. This analysis is based on three important criteria: (1) creation time of a version, (2) access time to a versioned entity, and (3) memory usage.

All these approaches have to work with Famix tools. So, an analysis of the integration of each approach is made.

For our analysis, we consider the following parameters:

• m, the number of entities in the original model;

• v, the total number of versions between the original model and the version of model that is being accessed;

• d, the average number of modifications in a version including the impacted elements.

For all of these possible approaches, we consider three types of modifications: removing an entity or an association, adding an entity or an association, and moving an entity between containers (class, package...).

Copy Approach

The Copy Approach approach is the most intuitive and straightforward. For each version of the model, a copy of the previous model is created and the modifications are applied to this copy (Figure 3). In other words, each version is a complete model and is totally autonomous.

With Copy Approach, each version is represented by a model that is independent of previous versions and from the history of changes. This implies that it can be used regardless of the change history and it can be used by all tools that are based on FAMIX. This independence of the history hides the modifications that were applied to the model. Since a version is a complete model, the modifications that were made are no longer visible, so to to know them, it is necessary to add a marker as a set of change for each version as in Section 4.2.

The most important problem of this approach is the duplication of entities that are not modified. In Figure 3, all entities are copied whereas only three entities are modified by the changed link (ClassA, ClassB and mB1()). This has a negative impact on both the time needed to create the model and the memory consumption of various versions of the model.

Performance analysis.

• Creation time: O(m + d). Each version is created with n

entities of the previous version and d modifications.

• Access time: O(1). To access an element, this approach is fast. It can immediately access any entity in any version of the model.

• Memory usage: O(m * v).
Each version is complete and the n elements are duplicated in all m versions. This represents a high overhead if only a small number of changes were made.

• Famix integration: Copy Approach will work with all Famix tools, because each model is a Famix Model.

Delta Approach

The Delta Approach uses a list of changes that are applied to a Famix model (Figure 4). Consequently, a version is either a Famix model, or a list of changes to the previous version of the model.

In Figure 4 we see the Delta Approach applied to our running example. Model1 is the original model, Model2 is represented by a list of changes. There are three modifications which remove the link between mB1() and ClassB, create the link between mB1() and ClassA, and remove ClassC. The major advantage of this approach is that it keeps track of the history of changes. Only one model is stored in the system, and changes are applied on it. For the first couple of versions, this method is fast because the set of modifications remains relatively small. But the larger the number of version is, the slower the access of the entities in a later version will be since all previous changes starting from the original model need to be applied.

For example, when comparing two versions this can become a problem. As there is only one full model of the system (the others are represented as lists of changes), the comparison of two versions is an expensive operation: all the changes must be replayed. A possible solution to bypass this is to make and cache a copy of the model on demand for the situations that we want to compare. This solution is interesting when there are more modifications than versions we want to compare, otherwise the same problems occur as in the Copy Approach.

Performance analysis.

• Creation time: O(d). A version is a list of changes, thus creating a model simply means keeping track of these changes.

• Access time:

O(n + m * d).
To access to a version, it is necessary to build all versions in between the original version up to the requested version using the changes. This is an expensive operation.

• Memory usage: O(n + m * d). Each version contains only a list of changes. This result is small in memory consumption since only the necessary information is stored.

• Famix integration: Each time a version should be accessed, a Famix Model is created based on the original model and changes. So Famix tools works by default on a version.

LookUp Approach

The objective of the LookUp approach is to avoid copying the entire model for each version and thus providing support for incremental models.

The LookUp approach copies entities only if they were changed between versions. Each version keeps a pointer to the previous version. This pointer is necessary to ensure that information is retrieved with respect to the current version that is being queried.

In Figure 5, Model2 is defined as all elements that were altered in Model1. All other elements are retrieved via the lookup mechanism. Each time a request for information is being handled, the lookup of the entity is performed starting at the current version. If that entity is not present in the current version, it will be requested from the parent version and so on. For example, if we request mB2'().parentClass, the result is ClassB': method mB2() is not part of Model2 and will be retrieved via the pointer to the previous version from Model1. However when asking method mB2() for its parent class, this lookup will start again in Model2, thus returning the correct class. The semantics is similar to the one of self in Object-Oriented language since the lookup always starts from the current model. Two problems however appear in this approach: the first one is the cost of performing a lookup. The larger the number of versions is, the slower the lookup possibly becomes because in the worst case the lookup must traverse the entire set of models. The second problem is the case of deletion of an entity: if an entity is removed from a version, the lookup will check in the previous version. To remedy this problem, we must create an entity which represent such a special case and stop or adapt the lookup when such an entity is encountered. For example, Figure 5 shows that for our running example, we have to provide a special entity removed-ClassC in Model2 in order to ensure that performing a lookup for class C does not return the version of the class from the previous model.

Performance analysis.

• Creation time: O(d). As with all the partial copy approaches, only modified elements are stored in a version.

• Access time: O(v). An entity is accessed by searching from the most recent version up to the first version of the system.

• Memory usage:

O(m + d * v).
As with the previous two approaches, the memory usage of LookUp is small as only modified entities and these containers are stored.

• Famix integration: This approach implies more complexity and time than the previous. When some requests are made, this approach switches between several versions. So a modification of accessing methods of Famix is necessary to have correct information related to a specific version.

Hybrid approaches

Each of previous approaches exhibits a number of flaws with regards to the requirements we set forth. Copy Approach requires a copy of all (non-modified) elements, thus resulting in excessive memory usage. While Delta Approach minimizes the memory usage, it requires a version to be generated by applying an entire change history, which is an expensive operation. The Lookup approach resolves this flaw, but has a poor time complexity for looking up an entity.

In this section, we propose a number of hybrid approaches to bypass these problems. Two such approaches seem valuable and are introduced here, namely Lookup/Copy and Lookup/Pointer.

Lookup/copy approach.. In this approach, each changed element along with all the elements it is related to are completely copied when creating a new version of the model. This approach allows one to make partial copies of impacted elements and to perform a lookup with nonmodified elements. In our example (Figure 2), ClassA, ClassB and mB1() are copied, along with all linked elements. This represents a complete copy of the model.

As a downside, this model introduces a high probability that the whole model will get copied. Since FAMIX uses bi-directional links between elements, modifying one element modifies also all linked elements, which can result in a cascade of necessary copy operations. If there are groups of entities without connection, which happens rarely in a software, the model is not completely copied. So when a copy of an entity is done, this approach is slower than the copy approach because the process collect entities in relation with the copied one and make the same process for these entities, etc.

Lookup/Pointer approach..

The second hybrid approach is Lookup/Pointer. As in Section 4.3, this approach is based on copying only the changed entities.

The unchanged elements are represented by pointers on the previous version. The lookup is used to get the version of an entity in the current model.

For example, in Figure 6:

• In Model1, ClassB.allMethods returns #(mB1() mB2()).

• In Model2, ClassB'.allMethods returns #(mB2()).

• In Model1, mB1().parentClass returns ClassB.

• In Model2, mB1'().parentClass returns ClassA'.

• In Model2, mB2'().parentClass returns ClassB', which is the version of ClassB in Model2.

In fact, in the case of indirect request, the approach tests if the requested entity is in the current model. An indirect request is a request made through another element of the model. This is a request of entities in relation with the entry entity. For example "FamixMethod.parentClass" goes through a FamixMethod to give its parent class. In Figure 6, mB2().parentClass represent mB2() as the entry entity and return the result of parentClass as an indirect request. Indirect request is problematic because the returned result can be entities in a previous model, which must be updated to the current version. In the case of direct request, there is no problem because in a model, if the entity exists, it is in the correct version, and if it does not exist (no entity, no pointer), this is a removed entity. Performance analysis.

• Creation time: O(d). The creation time is the same as lookUp approach.

• Access time: O(v). While the access time is not as good as a Copy of the entire model (which was O(1)), it is considerably better than the worst case scenario that is offered by the Lookup approach (O(m)).

• Memory usage: O(m + d * v). This is the minimum size necessary for keeping track of all versions.

• Famix integration: The integration with Famix tools has the same problems than lookUp approach. A modification of accessing method is necessary.

ORION

Based on our assessment, the Lookup/Pointer approach seems to best satisfy the requirements we put forward before. As a proofof-concept, we have implemented such a scheme for keeping track of multiple versions of a model by means of an extension to the FAMIX metamodel. This section explains this proof-of-concept named Orion. We explain how it works and what are the benefits of the approach.

Presentation

The Orion metamodel is an extension of FAMIX metamodel. All elements used in Orion are inherited from FAMIX. To make it easy to distinguish between Orion elements and FAMIX elements, we use the following naming convention: FAMIX entities are prefixed 'FAMIX' while Orion entities are prefixed 'Orion'. e.g., the Orion version of the FamixClass class is called OrionClass. For now, only a subset of elements are implemented: OrionPackage, Ori-onNamespace, OrionClass, and OrionMethod.

Orion differs from the FAMIX metamodel in two ways. First, in order to ensure that when creating a new version of a model the old version remains consistent, Orion entities do not automatically update their link to other entities as is the case with the FAMIX3.0 model (explained in Section 3). In our example, the replacement of ClassA by ClassA' in Model2 should not modify Pack1, mA1() and mA2(). In FAMIX3.0, these elements would have been automatically updated, resulting in an inconsistent model. The second difference is that in contrast to FAMIX3.0, accessing entities in a model is not done directly, but via a binding process. This process is explained in Section 5.3.

Orion metamodel

Since Orion is an extension of Famix, OrionElement inherits from FamixEntity and OrionModel inherits from MooseModel. The metamodel in Figure 7 is simplified, in the complete one Orion-Package inherits from FamixPackage, OrionClass from FamixClass, etc.

OrionElement has two subclasses: OrionEntity and OrionAssociation. OrionEntity represents structural entities in the model. Currently, we support four such entities: OrionClass, OrionMethod, OrionPackage, OrionNamespace. OrionAssociation represents reified associations between OrionEntities. Yet again, we support for such associations: OrionReference, OrionInvocation, OrionInheritance, OrionAccess. All OrionElements have a OrionID which is a unique identifier for an entity. It is used in the binding process (Section 5.3).

OrionModel inherits from MooseModel, it represents a version of model, so it contains Orion elements and has a pointer to the previous version from which it was derived. Note that the first Ori-onModel does not have such a parent pointer (as it is the model containing all entities belonging to the initial model).

The class Action and its subclasses represents changes that can be applied to a model. It is possible to compose some actions to make a complex one. Actions are stored in the OrionModel to keep an history of changes, as in a Delta Approach (Section 4.2). Note that this allows us to not only keep track of the various versions of a model, but also gives us access to a full history of the changes between models, expressed in terms of Actions.

Binding process

Each OrionElement contains an OrionID. It represents the unique identifier for an entity in a model, but is the same for all versions of an entity. In Orion, we use this identification to trace versions of an element in different model versions. If a new entity is added to a model, a new OrionID will be created for this entity. However, in the case an existing entity is altered between versions of a model, then the altered version of the entity will share the same OrionID as the original entity that was altered. This usage of the OrionID lies at the core of the binding process.

The binding process itself is fairly simple. When looking for a particular entity in a version, there are two possibilities. Either the entity is present in the model. This is the case when a new entity was added to a model, or an entity was altered between two versions of the model and the altered version is added in the (derived) model. Looking up such an entity is simple: the entity can directly be returned from the model. If the entity is not present in the model that is being searched, a binding between the entity and its version in the correct version is initiated. In this version, the entity is looked up using the OrionID that serves as the unique identifier for the entity that is being retrieved. Similarly, when querying a particular entity, the same binding mechanism is used to ensure that the right version of an entity is returned. For example, in Figure 6 requesting mB2().parentClass() in Model2, a binding must be made to have the latest version of the resulted entity. The aim is to obtain ClassB', not ClassB. The approach takes the OrionID of the entity and check it in the current version.

Using the same identification for all versions of an entity allows us to have history of an entity when this identification is coupled with the suite of versions.

Performance analysis of Orion

• Creation time: O(d). When creating a new model, only the delta with respect to the previous version is calculated. As in lookup approach, the creation time is minimal.

• Access time: O(1 + δ). If an entity is in the current version it returns the result in O(1). If not, it retrieves the updated entity with the corresponding OrionID. This may take a little more time because the process concerns two versions of an entity: the old and the updated.

• Memory usage: O(m + d * v). If we would like to have possible accesses to all version, it is necessary to have the original model and all modifications.

• Famix integration: As all approaches which partially copy models, this approach requires some modifications some accessing methods of Famix. As this approach is an extension of Famix, these methods has been written in OrionElements and take into account the binding process. So Famix tools works with a version of this approach like with a Famix Model.

The theoretical evaluation above shows that in comparison to the other (Table 1) approaches, Orion provides an interesting trade-off between model creation time, access time and memory consumption. While the binding of an entity is not performed in constant time, our implementation does outperform all other approaches exceptionally for the cost of access which is slower than the copy approach. Furthermore, our approach minimizes the amount of memory that is necessary to keep track of the evolution of a model.

DISCUSSION

Orion approach has been implemented above Famix Metamodel on Pharo Smalltalk. All tools of Moose platform work with Orion. It includes metrics, visualization and browser. For each visualization, we could make some new feature interact with the visualization to change the model. As in eDSM [LBD09], we could see the impact when a cycle between packages is broken.

The analysis of cost made in this paper is theoretical. The first future work will be a case study to validate these values. We must compare the different approaches on a complex software model. A second case study should be made to analyze the usefulness of comparing multiple versions. We think that when a software reengineer works, he should have several possibilities of future structure and makes choice based on the comparison of versions. We want to know in average how many versions a software engineer in practice needs. We expect to get less than 10 versions.

The use of algorithms for optimizing the software structure can be implemented with Orion. A lot of algorithms makes structure changes, but they provide only the final result model. Coupled with Orion, a scenario could produce several versions, stressing the problems presented in this paper.

RELATED WORKS

In [G 05], a meta-model for software evolution is proposed. This approach is based on the notion of history as a sequence of versions. A version is a snapshot taken at a particular moment. It makes version from the past based on a copy approach: each version is a Famix model. It has some similarity with our idea. The main difference is that our idea is based on what we would do in the futur, not a study of the past. Some other approaches make prediction of change impact. These approaches use graph analysis (like [START_REF] Badri | Supporting predictive change impact analysis: A control call graph based technique[END_REF] which use call graphs) or metrics comparison (like [START_REF] Antoniol | Estimating the size of changes for evolving object oriented systems: A case study[END_REF]), but they do not provide the possibility to compare some versions and to choose one.

In [BMZ + 05], authors propose a taxonomy of software evolution. In this paper, the aspect of version is reach for the source code. So, the aspect of impact analysis on a model before changing source code is not studied.

CONCLUSION

In this paper, we have compared several ways of supporting simultaneous versions of a model. We showed that naive approaches as copy or delta are expensive in creation time, in memory or in time to access an entity. The Lookup Approach appears not adapted to Famix. But each of these approaches has some benefits. Based on this analysis, we developed mixed approach based on dynamic bindings.

The Orion approach, which uses pointers and bindings, offers a good compromise between memory consumption and access time at execution. This approach, supporting Famix metamodel, can build multiple versions of a software model with a limited computing cost.

This approach can be used to support tools that analyze several versions of possible future system. Coupled with manual or automatic change recommendation system, it can offer a new tool for choosing how to modify a system. Future improvements will go in this direction with possibilities to analyze impacts of changes proposed by Moose tools and optimization algorithms.

Figure 1 :

 1 Figure 1: On the left is the original model; on the right a new version cred by moving mB1() and deleting classC.

Figure 2 :

 2 Figure 2: Famix representation of Figure 1.

Figure 3 :

 3 Figure 3: The example represented in the Copy Approach

Model 1 -Figure 4 :

 14 Figure 4: The example represented in Delta Approach

  Figure 5: LookUp Method

Figure 6 :

 6 Figure 6: LookUp/Pointer Approach

Figure 7 :

 7 Figure 7: the Orion Metamodel, extension of Famix

Table 1 :

 1 Performance of approaches

	Approach	cost of creation	cost of access	memory cost
	Copy	O(m+d)	O(1)	O(m*v)
	Delta	O(d)	O(m + v*d)	O(m + v*d)
	Lookup	O(d)	O(v)	O(m + v*d)
	Lookup/pointer	O(d)	O(v)	O(m + v*d)
	Orion	O(d)	O(1 + δ)	O(m + v*d)

Acknowledgement.. we gratefully thank Andrew P. Black for his deep review.


Stéphanie Topoliantz
email: stephanie.topoliantz@wanadoo.fr

Jean-François Ponge

Burrowing activity of the geophagous earthworm Pontoscolex corethrurus (Oligochaeta: Glossoscolecidae) in the presence of charcoal

Keywords: Burrows, casts, charcoal, Pontoscolex corethrurus

The geophagous earthworm Pontoscolex corethrurus is frequently found in burnt tropical soils where charcoal plays an important role in soil fertility. We studied the burrowing activity of this species in two-dimensional microcosms with one half filled with soil and the other with a 3:2 (w:w) mixture of charcoal and soil (CHAR+soil). We measured the volume of empty burrows and those filled with black or brown casts in both substrates, as well as the initial and final fresh weights of the worms. The correlation between brown cast production and both initial and final fresh weights of the worms, reinforced by the presence of feeding cavities in soil but not in CHAR+soil, suggests that P. corethrurus would ingest soil to fulfill its nutrient requirements, in contrast to charcoal which was ingested for other purposes. We observed that at equal burrow volume created in the two substrates, P. corethrurus produced smaller black casts than brown casts, suggesting that burrows were created in CHAR+soil mainly by pushing aside the particles of this lighter substrate.

The observed transport of charcoal to soil points to the importance of P. corethrurus in the incorporation of charcoal particles into organic-poor soil.

Introduction

The geophagous earthworm Pontoscolex corethrurus, an endogeic species feeding on soil with a low content of organic matter [START_REF] Lavelle | Adaptive strategies of Pontoscolex corethrurus (Glossoscolecidae, Oligochaeta), a peregrine geophagous earthworm of the humid tropics[END_REF], exerts an important effect on the soil structure in the upper 10 cm through its burrowing and casting activity. While it has been reported to increase the porosity of compacted soil (Zund et al., 1997), P. corethrurus is classified as a "soil compacting" earthworm species [START_REF] Lavelle | Large-scale effects of earthworms on soil organic matter and nutrient dynamics[END_REF] because it produces large coalescent aggregates [START_REF] Barois | Transformation of the soil structure through Pontoscolex corethrurus (Oligochaeta) intestinal tract[END_REF]. The production of these macroaggregates (>1 cm) increases bulk density and decreases water infiltration [START_REF] Alegre | Dynamics of soil physical properties in Amazonian agroecosystems inoculated with earthworms[END_REF], thus causing a strong compaction of the soil surface. This detrimental effect of earthworm activity occurs at a high density of P. corethrurus and in the absence of other earthworm species reducing aggregate size [START_REF] Barros | The role of macrofauna in the transformation and reversibility of soil structure of an oxisol in the process of forest to pasture conversion[END_REF][START_REF] Chauvel | Pasture damage by an Amazonian earthworm[END_REF].

Whereas the importance of charcoal in soil fertility has often been reported (Tryon, 1948;[START_REF] Glaser | The 'Terra Preta' phenomenon: a model for sustainable agriculture in the humid tropics[END_REF][START_REF] Lehmann | Slash-and-char: a feasible alternative for soil fertility management in the Central Amazon? In: Soil Science: Confronting New realities in the 21 st Century[END_REF]Topoliantz et al., 2002), no published study has yet dealt with its possible incorporation into the soil by P. corethrurus individuals living in burnt areas (Standen, 1988;personal observation) or by other soil fauna. In the present study, we investigated the subterranean activity of P. corethrurus and its growth in the presence of soil and charcoal.

Material and methods

We studied the burrowing activity of P. corethrurus in the presence of native soil and charcoal in two-dimensional microcosms [START_REF] Evans | A method of studying the burrowing activities of earthworms[END_REF][START_REF] Grant | An ecological study of the peregrine earthworm Pheretima hypeiensis in the eastern United States[END_REF], made of two parallel transparent plastic sheets each 20 cm high x 25 cm wide x 2 mm thick.

Bottom and side edges were sealed with 2 mm thick wooden strips, thus allowing earthworm movement and observation of their burrow system and cast deposition.

The microcosms were filled with 80 g dry weight of soil on one side; the other half side was filled with 40 g dry weight of a 3:2 (w:w) mixture of charcoal and soil (CHAR+soil). The soil was taken from the upper 10 cm of an oxisol (65% sand, 12% silt and 23% clay content) in a slash-and-burn field in maripasoula (French Guiana).

Charcoal was collected on the ground in a recently burnt field. Both substrates were sieved at 2 mm mesh size. Physical and chemical properties of the substrates are given in Table 1. Both substrates were moistened from the top edge by adding water to 50-55 % substrate weight. Sub-adult P. corethrurus were obtained from a nearby experimental area. In each microcosm, one individual (initial fresh weight from 209 to 591 mg) was inserted from the top edge at the border between the two substrates.

The top edges of the microcosms were closed with Parafilm® to avoid desiccation and earthworm escape. Ten replicates were established and placed for two weeks in a dark chamber with controlled temperature at 25°C. At the end of the experiment, the surface of burrows and casts visible through the two transparent walls (planes 1 and 2) were drawn on a transparent film and measured with a surface integrator (Numonics 1224®, resolution 0.1 mm). Casts were classified according to their colour, as brown (soil) and black (mixture of charcoal andsoil) casts. Very dark grey casts were pooled with black ones because of their high content of charcoal. The Mean surface area and the volume of empty and cast-filled burrows were calculated from the following equations:

Mean surface area = (area on plane 1 + area on plane 2)/2 Volume = Mean surface area x substrate thickness (2 mm)

The burrow length was not measured because a high number of burrows could not be considered as typical linear galleries (see Fig 1 as an example of the burrow system). The final fresh weight of individuals was measured after rinsing earthworms in water and gently blotting them with absorbent paper.

The volume of burrows, the volume of casts filling the burrow system and the growth rate of earthworms were statistically analysed using only nine replicates, one earthworm having died during the experiment. Initial and final fresh weights of worms were compared using paired t-tests. The volumes of casts and burrows in soil, CHAR+soil and both substrates pooled, were compared using t-tests or Mann-Whitney rank tests when data were not normally distributed. Relationships between growth rate, cast and burrow volume were tested by Bravais-Pearson correlation coefficients. The coefficient of variation (SD/mean x 100) was calculated for each variable (Sokal and Rohlf, 1995).

Results

During the experiment, the earthworm weight increased by 36 ± 17 % (mean ± S.D.) and the mean growth increment was 0.13 ± 0.06 g. The final fresh weight (0.49 ± 0.15 g, mean ± S.D.) was significantly higher than the initial weight (0.36 ± 0.11 g, mean ± S.D.) at the 0.001 level (t = -6.12). No significant correlation was found between the growth rate and other variables such as initial fresh weight or burrow and cast volume, whether substrates were pooled or not. The initial fresh weight of worms was positively correlated with the volume of total burrows calculated when both substrates were pooled (r =0.736, P<0.05) and with the total volume of brown casts deposited (r = 0.82, P<0.01). The final fresh weight of worms was positively correlated with the total brown cast volume (r = 0.83, P<0.01) and with the total brown cast / soil burrow volume ratio (r = 0.695, P<0.05). Initial and final fresh weights were not correlated with either black cast deposition or with burrowing activity in CHAR+soil.

On average, in the total substrate, P. corethrurus created burrows of 3.34 ± 0.74 cm 3 (mean ± S.D.) per g of earthworm biomass and per day. After 14 days, the burrow system in the soil substrate reached 32.4 ± 8.8 % (mean ± S.D.) of the total soil volume and the burrow system in CHAR+soil 3.9 ± 2.4 % (mean ± S.D.) of the total CHAR+soil volume. Total brown casts deposited on both sides (soil and CHAR+soil) and burrows in the soil half side were strongly correlated (r = 0.92, P<0.001), as were total black casts and burrows in CHAR+soil (r = 0.95, P<0.001).

The total volume of brown casts amounted to 37.3 % of the burrow system on the soil half side and the total volume of black casts 10.6 % of the burrow system in CHAR+soil (Table 2).

Comparisons of burrow systems and cast deposition between soil and

CHAR+soil are summarised in Table 2. The initial volumes of soil and CHAR+soil were not significantly different. The volume of the burrow system in the soil half side was significantly higher than that in the CHAR+soil half side and the total volume of brown casts deposited on both sides was significantly higher than that of black casts.

The ratio of total brown casts to burrows in soil was higher than that of black casts to burrows in CHAR+soil. The percentage of burrows filled with casts (black and brown) in soil was not significantly different to that in CHAR+soil. Coefficients of variation were greater for black casts and CHAR+soil burrows than for brown casts and soil burrows, indicating that burrowing and cast production were more variable in CHAR+soil than in soil (Table 2). The ratio of black casts deposited in soil to total black casts was not different of that of brown casts deposited in CHAR+soil to total brown casts, both displaying a high coefficient of variation (Table 2).

Discussion

Heavier individuals of P. corethrurus constructed more channels, as [START_REF] Lavelle | Large-scale effects of earthworms on soil organic matter and nutrient dynamics[END_REF] found for immature individuals only (weighing less than 0.6 g fresh weight).

Bigger immature earthworms ingested more soil but not more charcoal-soil mixture than smaller ones, suggesting that, although no correlation between soil ingestion and earthworm growth was found, the soil constituted a nutrient source in contrast to charcoal. This result is reinforced by the presence of feeding cavities in soil only (Fig. 1), which are burrowed to exploit a food source (Martin, 1982). The mean growth rate of P. corethrurus appears lower (2.5 % per day) than that found by [START_REF] Lavelle | Adaptive strategies of Pontoscolex corethrurus (Glossoscolecidae, Oligochaeta), a peregrine geophagous earthworm of the humid tropics[END_REF] (5 to 6% per day) at the same soil moisture, despite a similar soil consumption (5.4 g soil per g earthworm fresh weight). We can attribute this difference to the estimating method of soil consumption, [START_REF] Lavelle | Adaptive strategies of Pontoscolex corethrurus (Glossoscolecidae, Oligochaeta), a peregrine geophagous earthworm of the humid tropics[END_REF] results being based on the weight of casts produced and ours on burrow volume and soil bulk density. In our 2D microcosms, the soil was poorly compacted and allowed channelling activity without necessariy ingestion of the substrate [START_REF] Buck | Influence of mulch and soil compaction on earthworm cast properties[END_REF].

If all the burrow volume had been ingested by the worms, the ratio of black cast/burrow volume in the charcoal/soil mixture (11%) and that of brown cast/burrow volume in soil (37%) would represent a compaction of the ingested substrate of 9.4 and 2.7 for charcoal/soil and soil respectively. This result cannot totally be explained by differences in bulk density (Table 1) and suggests that P. corethrurus may have created channels in the charcoal/soil substrate mainly by pushing aside charcoal particles and to a lesser extent by ingesting them. The microcosms being highly artificial, the worms could ingest charcoal by accident as Fig 1 shows. However, P. corethrurus, that selects particles before ingestion [START_REF] Lavelle | Faunal activities and soil processes: adaptive strategies that determine ecosystem function[END_REF], could ingest charcoal for its detoxifying and liming effects (Titoff, 1910;;Zackrisson et al., 1996) and its enhancment of microbial communities (Pietikainen et al., 2000) which could favour the production of earthworm's digestive enzymes of bacterial origin [START_REF] Lattaud | Enzymatic digestive capabilities in geophagous earthworms -origin and activities of cellulolytic enzymes[END_REF].

The transport of ingested matter, here demonstrated through black and brown cast deposition, underlines the importance of P. corethrurus for bioturbation [START_REF] Garcia | Growth, reproduction and activity of earthworms in degraded and amended tropical open mined soils: laboratory assays[END_REF]. More especially, by ingesting charcoal and incorporating it to the soil matrix, P. corethrurus could play an important role in burying this source of fertility in burnt soils used for slash-and-burn agriculture (Topoliantz et al., 2002). Only seven replicates used, due to the absence of black casts in the other two.

Comparison of burrowing actvity and cast deposition of Pontoscolex corethrurus after 2 weeks between soil and charcoal+soil (CHAR+soil), (n=9). Volumes and ratios (mean ± S.D.) were compaired by t-test (t) or Mann-Whitney rank test (T). Significant probability is indicated by *, **, *** for P<0.05, P<0.01 and P<0.001 respectively and no significant differences are abbreviated NS. CV (%) is the coefficient of variation.

Fig. 1 .

 1 Fig. 1. Example of a reconstructed burrow system in soil and charcoal / soil

  Fig. 1

Acknowledgements

We thank the SOFT Program of the French Ministry for the Environment, the PPF-Guyane of the Museum National d'Histoire Naturelle and the GIS-SILVOLAB of French Guiana for their financial support. We are grateful to our colleagues Dr Nicolas Bernier and Prof. Pierre Arpin for their technical help in drawing Figure 1.

 Martin, N.A., 1982.The interaction between organic matter in soil and the burrowing activity of three species of earthworms (Oligochaeta: Lumbricidae). Pedobiologia 24, 185-190. Pietikäinen, J., Kiikkilä, O., Fritze, H., 2000. Charcoal


Jannik Laval

Simon Denier

Stéphane Ducasse

Identifying cycle causes with CycleTable

Identifying and understanding cycles in large applications is a challenging task. In this paper we present Cy-cleTable which displays both direct and indirect references. It shows how minimal cycles are intertwined through shared edges and allows the reengineer to devise simple strategies to remove them.

Introduction

Understanding the structure of large applications is a challenging but important task. Several approaches provide information on packages and their relationships, by visualizing software artifacts, metrics, their structure and their evolution. Software metrics can be somehow difficult to understand since they are dependent on projects. Distribution Map [START_REF] Ducasse | Distribution map[END_REF] alleviates this problem by showing how properties are spread over an application. Lanza et al. [START_REF] Ducasse | The class blueprint: Visually supporting the understanding of classes[END_REF] propose to recover high level views by visualizing relationships. Package Surface Blueprint [START_REF] Ducasse | Package surface blueprints: Visually supporting the understanding of package relationships[END_REF] reveals the package internal structure and relationships among other packages.

In previous work, we enhanced Dependency Structure Matrix (eDSM) [START_REF] Laval | Identifying cycle causes with enriched dependency structural matrix[END_REF] to visualize dependencies between packages, showing in each matrix cell information about the dependencies at the fine grain of classes (inheritance, class references, invocations, referencing and referenced classes/methods). eDSM proved useful to provide an overview of dependencies, detect direct cycles (a cycle between two packages) and provide information to remove them. However, removing all direct cycles does not necessarily remove all cyclic dependencies because there could be indirect cycles (between more than two packages). Although indirect cycles are also displayed by eDSM, they are hard to read in the eDSM layout, making the task inefficient.

In this paper, we present a new visualization, called Cy-cleTable, entirely dedicated to cyclic dependencies assessment. CycleTable layout displays both direct and indirect cycles and shows how minimal cycles are intertwined through shared edges. CycleTable combines this layout with the enriched cells of eDSM to provide the details of dependencies at class level.

Next section introduces the challenges of cycle analysis with graph layout and eDSM. Section 3 explains Cy-cleTable layout and enriched cells. Section 4 presents a sample of cyclic dependencies displayed with CycleTable and discusses the criteria to break cycles as highlighted by the visualization.

Cycle Visualization

Figure 2 shows a sample graph with five nodes and three minimal cycles. Each edge is weighted. Notice that cycle A-B-C and A-B-E share a common edge (in yellow) from A to B. This shared edge is interesting to spot since it joins two cycles and by removing it we would break those cycles.

Graph layouts offer an intuitive representation of graphs, and some handle cyclic graph better than others. On large graphs, complex layouts may reduce the clutter but this is often not simple to achieve. In addition, in the context of DSM we enhanced the DSM cells to convey much more information about the strength, the nature and consequences of a cycle. Now it is difficult to combine a graph layout with enriched cells (see Figure 4 for a cell sample), as an enriched cell represents an edge in a graph. Enriched cell is an important asset of our work with eDSM as it provides fine-grained details of a dependency between two packages, and enables small multiples as well as micro-macro reading effects [START_REF] Tufte | Visual Explanations[END_REF].

In eDSM we used a matrix, the traditional support of DSM. It provides a regular structure which is the same at any scale: it handles the repetitive arrangement of enriched cells, enabling the above effects. It is a fundamental element of eDSM design. In Figure 1, four packages belonging to Pharo kernel (an open-source Smalltalk) are presented in a eDSM. It shows edges involved in direct cycles in red and pink cells, indirect cycles in yellow. More explanations about the design and usage of eDSM are available in [START_REF] Laval | Identifying cycle causes with enriched dependency structural matrix[END_REF].

While eDSM allows us to analyze direct cycles comfortably, we could not address the problem of indirect cycles left over after removal of direct cycles. The main reason for this problem is that it is difficult to read an indirect cycle in the matrix, i.e., to follow the sequence of cells representing the sequence of edges in the cycle. The order can appear quite arbitrary as one has to jump between different columns and rows (this problem does not exist with direct cycles as there is only two cells, mirroring each other along the diagonal). Cycles have been overlayed in Figure 1 to show the complexity of reading indirect cycles, intertwined with direct cycles.

CycleTable

We have built the CycleTable design with the single purpose of visualizing cycles. As a consequence, CycleTable does not show a complete overview of dependencies between packages as eDSM does. It complements eDSM. CycleTable is a rectangular matrix where nodes are placed in rows and cycles in columns. CycleTable (i) shows each minimal cycle clearly and independently, (ii) highlights shared edges between minimal cycles, and (iii) uses enriched cells [START_REF] Laval | Identifying cycle causes with enriched dependency structural matrix[END_REF] to provide information about edge internals, enabling small multiples and micro-macro reading [START_REF] Tufte | Visual Explanations[END_REF] i.e., variations of the same structure to reveal information. We detail each of these points now.

Minimal Cycle

A minimal cycle is a cycle with no repeated nodes other than the starting and ending nodes. For example, in Figure 2, A-B-E andA-B-C are two different minimal cycles, but A-B-C-D-C is not because C is present twice. With minimal cycles, the visualization provides all edges contains in cycles. Therefore it is not necessary to show complex (intertwined) cycles. In the CycleTable layout, each minimal cycle is represented directly and independently in its own column.

CycleTable Layout

The CycleTable layout is presented in Figure 3. This figure shows a sample CycleTable layout for the graph in Figure 2. The first column (header) contains the name of packages involved in cycles, then all minimal cycles are represented column by column. A box at the intersection of a row and a column indicates that the package is involved in the cycle.

One package per row. Each row contains dependencies (as boxes) from the package in the header. Number in each box represents the weight of the edge. In Figure 3, first row represents package A, which depends on package B with a weight of 10. Second row represents package B, which depends on E (weight 9) and C (weight 4).

One cycle per column. In the right part of the table, each column represents a cycle. In Figure 3, the first column involves packages A, B and E in a cycle. Each minimal cycle is represented independently. Shared edges. Cells with the same background color represent the same edge between two packages, shared by multiple cycles. In Figure 3, first row contains two boxes with a yellow background color. It represents the same edge from A to B, involved in the two distinct cycles A-B-E and A-B-C. It is a valuable information for reengineering cycles. Indeed, removing or reversing A-B would solve two cycles.

CycleTable Cell

Box content is customized to display enriched cells as in eDSM [START_REF] Laval | Identifying cycle causes with enriched dependency structural matrix[END_REF]. An enriched cell displays all dependencies at class level from one package to the other. A CycleTable cell is structured in three parts: (i) on top, position in the cycle, (ii) in center, an enriched cell as in DSM, and (iii) on right, a colored frame if the edge is shared by multiple cycles. Position in the cycle. The position in the cycle represents a relative order between edges. This number is sometimes necessary to retrieve the exact order of edges in indirect cycles. In Figure 5, numbers allow one to read indirect cycles in third and fifth columns.

Enriched cell. Cell contents gives a detailed overview of dependencies from the package in the header of the row (source package) to the next package in the cycle (target package). Each cell represents a small context, which enforces comparison with others. The objective is to create small multiples [START_REF] Tufte | Visual Explanations[END_REF]. An enriched cell is composed of three parts. The top row gives an overview of the strength and nature of the dependencies. The two large boxes detail dependencies going from the top box to the bottom box i.e., from the source package to the target package. Each box contains squares that represent involved classes: referencing classes in the source package and referenced classes in the target package. Edges between squares links each source class (in top box) to its target classes (in bottom box). As this structure is the same as in eDSM [START_REF] Laval | Identifying cycle causes with enriched dependency structural matrix[END_REF], we give no more explanation in this paper. An important asset of CycleTable is that it does not focus on a single solution to break cyclic dependencies. It rather highlights different options as there are many ways to resolve such cyclic dependencies. Only the reengineer can select what he thinks is the best solution based on a matter of criteria. We now discuss how CycleTable allows one to consider solutions for solving cycles in Figure 5.

Breaking Cycles with CycleTable

First things to consider in CycleTable are the shared edges, the number of cycles they are involved in, and their weight. For example, the blue cell linking System-FileRegistry to Kernel is in the two indirect cycles. Yet it has a weight of six dependencies and involves six classes as well, which can require some work to remove. Finally, from a semantic point of view, Kernel is at the root of many functions in the system so it seems difficult to remove such dependencies from System-FileRegistry.

Instead, we turn our focus to the red cells, linking Kernel to System-FilePackage. It has a very low weight and involves only two classes. This is the minimal dependency we can get between two packages and seems as a prime candidate for removal. Removing this dependency (by moving a class, changing the method, or making a class The third cycle links directly System-FilePackage and System-Support and is not intertwined with others. There is a weak link from the second package to the first which seems easy enough to remove.

Finally, the orange edge links the last two cycles.

However, it is obvious that it is too complex to be removed. The fourth cycle seems solvable by removing its last edge (from System-Support to System-FileRegistry). The last cycle, linking directly Kernel and System-Support is too complex so that a simple removal strategy can be devised with Cy-cleTable. Both packages are at the very core of Pharo system and are highly coupled together.

Conclusion

In this paper we presented CycleTable. This visualization shows cycles between packages in a system. Each cycle is presented in a separated column. A colored frame show which edge is shared by several cycles. To complete the visualization, enriched cells (proposed in [START_REF] Laval | Identifying cycle causes with enriched dependency structural matrix[END_REF]) have been adapted and integrated to represent each edge.

This visualization is for now a good complement of a DSM visualization. This visualization allows us to solve cycles separately or conjointly. Future work will focus on computing heuristics for highlighting interesting edges in cycles (either because of their low weight or because they are shared by many cycles), prone to removal by the reengineer.

Figure 1 .

 1 Figure 1. Some Pharo core packages in a eDSM (with cycles overlayed)

Figure 2 .Figure 3 .

 23 Figure 2. Sample graph with three cycles.

Figure 4 .

 4 Figure 4. Information in CycleTable cell.

Figure 5

 5 Figure5shows a CycleTable with the sample four packages of Pharo core presented in Figure1. Five minimal cycles are immediately made visible. It also appears that three edges are each involved in multiple cycles (with the red, blue, and orange frames).An important asset of CycleTable is that it does not focus on a single solution to break cyclic dependencies. It rather highlights different options as there are many ways to resolve such cyclic dependencies. Only the reengineer can select what he thinks is the best solution based on a matter of criteria. We now discuss how CycleTable allows one to consider solutions for solving cycles in Figure5.First things to consider in CycleTable are the shared edges, the number of cycles they are involved in, and their weight. For example, the blue cell linking System-FileRegistry to Kernel is in the two indirect cycles. Yet it has a weight of six dependencies and involves six classes as well, which can require some work to remove. Finally, from a semantic point of view, Kernel is at the root of many functions in the system so it seems difficult to remove such dependencies from System-FileRegistry.Instead, we turn our focus to the red cells, linking Kernel to System-FilePackage. It has a very low weight and involves only two classes. This is the minimal dependency we can get between two packages and seems as a prime candidate for removal. Removing this dependency (by moving a class, changing the method, or making a class

Figure 5 .

 5 Figure 5. Pharo core from Figure 1 in CycleTable.