Difference between pages "Membership in Goal" and "Migration to Git"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Laurent
 
imported>Laurent
m (→‎Writing Rules: Add link to rules file)
 
Line 1: Line 1:
−
= Objective =
+
{{TOCright}}
  
−
This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.
+
The source files of the Rodin platform and associated plug-ins are under
 +
version control on SourceForge.  Initially, we used CVS and we migrated to
 +
Subversion in March 2009.  This page describes the migration to another
 +
version control system: Git.
  
−
This reasoner discharges sequents whose goal denotes a membership which can be inferred from hypotheses, such as the following:
+
The migration from CVS to Subversion was far from perfect.  But then, there
−
<math>H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash\quad x\in U</math>
+
was not much time available for polishing it. In this new migration to Git,
 +
we would like to start again from scratch and first migrate the CVS repository
 +
to Git, then all the subsequent commits in Subversion.
  
−
= Analysis =
+
Another concern is that the Subversion repository has grown very large.  We
 +
would like to split it in several smaller repositories, which is now possible
 +
with Git.  The new repositories should each correspond to a set of plug-ins
 +
which are delivered together.
  
−
Usually, such sequents are proved by the external provers PP or ML. But, these provers have several drawbacks :
+
<strong>Important Note:</strong> Make sure that all conversions are performed in a case sensitive filesystem. For instance, on Mac OS X, create a special Volume with a different filesystem than the default (which is case insensitive).
−
* They do not report needed hypotheses, so that a conservative choice is made to depend on all hypotheses.
 
−
* They take substantial time to prove them (even with the basic example given above, the difference in time execution is noticeable).
 
−
* If there are too many hypotheses, or if the expression of the <math>x</math> or the intermediate sets <math>S, T, \dots</math> is too complicated, they may get lost into details and not discharge.
 
  
−
This is particularly true when in the set expressions of each side of relations are not equal, such as in:
+
==Migration of the SMT plug-in==
−
<math>H,\quad a\in S,\quad S\subset T_1\cap T_2,\quad T_1\cup T_3\subseteq  U\quad\vdash a\in U</math>
 
−
<p>
 
−
Such a reasoner thus increases the rate of automated proof, faster and with fewer needed hypotheses which makes proof rules more legible and proof replay less sensitive to modifications of the models.
 
  
−
= Design Decision =
+
To begin the migration to Git, I started with a very simple set of plug-ins: the SMT Solver plug-ins. Their history is linear, with just some renaming from time to time. All the development was performed in Subversion.  The conversion was performed with <tt>git-svn</tt> with no special constraint using [https://sourceforge.net/p/rodin-b-sharp/rodincore/ci/master/tree/org.rodinp.releng/gitMigration/migrate-svn-smt.sh migrate-svn-smt.sh].
  
−
== Tactic ==
+
==Migration of the Core Platform==
  
−
This part explains how the tactic (MembershipGoalTac) associated to the reasoner MembershipGoal is working.
+
For the Core Platform, the migration is more intricate. As stated in the introduction, the initial conversion from CVS to Subversion was of average quality. Moreover, when one includes the sources in the <tt>_exploratory</tt> directory, the files to migrate are a bit scattered all over the place.
−
=== Goal ===
 
−
The tactic (as the reasoner) should works only on goals such as :
 
−
*<math>\cdots~\in~\cdots</math>
 
−
For examples :
 
−
*<math>f(x)\in g\otimes h</math>
 
−
*<math>x\in A\cprod\left(B\cup C\right)</math>
 
−
*<math>x\mapsto y\in A\cprod B</math>
 
−
In the last example, the reasoner will not try to prove that <math>x</math> belongs to <math>A</math> and <math>y</math> belongs to <math>B</math>, but that the maplet <math>x\mapsto y</math> belongs to the Cartesian product <math>A\cprod B</math>.
 
  
−
=== Hypotheses ===
+
The migration is then performed in three steps:
−
Now we have to find hypotheses leading to discharge the sequent. To do so, the tactic recovers two kinds of hypotheses :
+
- Migrate the CVS repository
−
#the ones related to the left member of the goal <math>\left( x\in S\right)</math> (this is the start point):
+
- Migrate the Subversion repository
−
#*<math>x\in \cdots</math>
+
- Merge the two together
−
#*<math>\cdots\mapsto x\mapsto\cdots\in\cdots</math>
 
−
#*<math>\left\{\cdots, x,\cdots\right\}=/\subset/\subseteq\cdots</math>
 
−
#*<math>\left\{\cdots, \cdots\mapsto x\mapsto\cdots,\cdots\right\}=/\subset/\subseteq\cdots</math>
 
−
#*<math>f\ovl\left\{\cdots, x, \cdots\right\}=/\subset/\subseteq\cdots</math>
 
−
#the ones denoting inclusion (all but the ones matching the description of the first point) :
 
−
#*<math>\cdots\subset\cdots</math>
 
−
#*<math>\cdots\subseteq\cdots</math>
 
−
#*<math>\cdots=\cdots</math>
 
−
Then, it will search a link between those hypotheses so that the sequent can be discharged.
 
  
−
=== Find a path ===
+
===From CVS===
−
Now that we recovered all the hypotheses that could be useful for the reasoner, it remains to find a path among the hypotheses leading to discharge the sequent. Depending on the relations on each side of the inclusion, we will act differently. <math>f</math> always represent an expression (may be a domain, a range, etc.).
 
−
#The following sequent is provable because <math>f\subseteq \varphi (f)</math>.
 
−
#*<math>x\in f,\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g</math>
 
−
#*<math>\varphi (f) = f\quad\mid\quad f\cup h \quad\mid\quad h\cup f \quad\mid\quad h\ovl f</math>
 
−
#*<math>f=g\bunion h\quad\mid\quad \varphi(f)=g\bunion k\bunion h\bunion l</math>
 
−
#*<math>f=i\ovl j\quad\mid\quad\varphi(f)=g\ovl h\ovl i\ovl j</math>
 
−
#The following sequent is provable because <math>\psi (f)\subseteq f</math>.
 
−
#*<math>x\in \psi (f),\quad f\subseteq g\quad\vdash\quad x\in g</math>
 
−
#*<math>\psi (f) = f\quad\mid\quad f\cap h \quad\mid\quad h\cap f \quad\mid\quad f\setminus h \quad\mid\quad f\ransub A \quad\mid\quad f\ranres A \quad\mid\quad A\domsub f \quad\mid\quad A\domres f</math>
 
−
#*<math>\psi(f)=g\binter h\binter k\binter l\quad\mid\quad f=g\binter k</math>
 
−
#By keeping the notation <math>\psi(f)\subseteq f\subseteq\varphi(f)</math> we also deduce that :
 
−
#*<math>\psi(A)\domres\psi(f)\subseteq\varphi(A)\domres\varphi(f)</math>
 
−
#*<math>\psi(f)\ranres\psi(A)\subseteq\varphi(f)\ranres\varphi(A)</math>
 
−
#*<math>\varphi(A)\domsub\psi(f)\subseteq\psi(A)\domres\varphi(f)</math>
 
−
#*<math>\psi(f)\ransub\varphi(A)\subseteq\varphi(f)\ransub\psi(A)</math>
 
−
#*<math>\psi(f)\setminus\varphi(g)\subseteq\varphi(f)\setminus\psi(g)</math>
 
−
#For some relations, [[#positions|positions]] are needed to be known to continue to find hypotheses, but it is not always necessary.
 
−
#*<math>x\mapsto y\in f,\quad f\subseteq A\cprod B\quad\vdash\quad x\in A</math>
 
−
#*<math>x\in dom(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in A</math>
 
−
#*<math>x\in ran(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in B</math>
 
  
−
By using these inclusions the tactic tries to find a path among the recovered hypotheses. Every one of them should only be used once, avoiding possible infinite loop <math>\left(A\subseteq B,\; B\subseteq A\right)</math>.
+
This is done with the ZSH script [https://sourceforge.net/p/rodin-b-sharp/rodincore/ci/master/tree/org.rodinp.releng/gitMigration/migrate-core-from-cvs.sh migrate-core-from-cvs.sh].  This script
 +
creates a fresh Git repository from a CVS archive (67 MB). To run it, one
 +
needs the CVS archive be named <tt>cvs-Rodin-b-sharp.tgz</tt> and
 +
an author-mapping file named [https://sourceforge.net/p/rodin-b-sharp/rodincore/ci/master/tree/org.rodinp.releng/gitMigration/Authors.txt Authors.txt].
  
−
Since Rodin 3.0, the path search is delegated to the [http://www.sat4j.org Sat4j] solver. The problem encoding to SAT is done by representing each inclusion of the form <math>A\subseteq B</math> into the clause <math>\{\lnot x\in A,\; x\in B\}</math> and feeding the solver with all clauses that derive from the hypotheses and the negation of the goal. As soon as the solver reports the problem as unsatisfiable, the tactic obtains an unsat core and traces it back to the corresponding hypotheses.
+
After running the script, the git repository needs some massaging:
 +
* Fix three commit messages that are not UTF-8:
 +
      939bacf56436084c5fb58b041a26c9fe4dd7d876 (2008-01-16T18:57:44Z)
 +
      d2eca7a9ec561c2c7bfbc9c5d57ca9558964ee87 (2008-10-02T16:46:07Z)
 +
      dccf0b77d7d20538a44df5aac719646eb2b62fa4 (2008-10-09T13:06:44Z)
 +
* Merge the branch UNDO_DEV back into <tt>master</tt> as described below.
 +
* Rename tags into a hierarchy.
  
−
== Reasoner ==
+
====Merging a Branch Back in Main Branch====
  
−
This part describe how the reasoner MembershipGoal works.
+
After importation from CVS, some development branches are dangling.  To make history easier to browse, one needs to merge them back into the main development branch. This is done by grafting.
  
−
==== Goal ====
+
Suppose that the development branch <tt>mybranch</tt> needs to be merged back into the main development. First, identify the commit where the branch has ceased to be useful. Let's name this commit <tt>mergepoint</tt>. Then, type:
 +
      echo $(git log -1 --format=format:'%H %P' mergepoint) \
 +
            $(git show-ref -s branch) >> .git/info/grafts
  
−
First, it checks that the goal matches the description made in the part [[#Tactic|tactic]] : <math>x\in S</math>. Thus, we record the member ''x'' as well as the set ''S''
+
Then check that this change works fine and type the following command to make it permanent:
 +
      git filter-branch -- --all
  
−
==== Input ====
+
The branch names can now be removed with
 +
      git branch -d branch
 +
      git branch -d mergepoint
  
−
Then, it checks that the input is a hypothesesReasonerInput (an input with an array of predicates). Every given predicates must be a hypothesis of the sequent. Only one must be a membership with the same member as the goal so that there are no ambiguity. All the other ones must denote set inclusion or equality.
+
====Renaming Tags into a Hierarchy====
  
−
==== Find a path ====
+
After importation from CVS, the tags were named:
 +
I20060720
 +
…
 +
fr.systerel.explorer-0.0.1
 +
fr.systerel.explorer-1.0.0
 +
org.eventb.core-0.5.1
 +
org.eventb.core-0.5.3
  
−
With the same reasoning as for the tactic, we try to find a path leading to discharge the goal.
+
This is a long list and it is not very practical. However, Git supports hierarchical tags, like a filesystem. To benefit from this, type the following commands:
 +
cd .git/refs/tags
 +
mkdir RodinCore
 +
mv I* RodinCore/
 +
ls | grep -e '-' | cut -d- -f1 | sort -u |
 +
    for f in $(cat /tmp/a); do
 +
        mkdir $f
 +
        for g in ${f}-*; do
 +
            mv $g $f/$(echo $g | sed "s:^${f}-::")
 +
        done
 +
    done
  
−
==== Trusted Base ====
+
The list of tags becomes much shorter, as they are now neatly organized by plug-ins.
  
−
At that point, the reasoner performs the same jobs as the tactic which is quite complicated. That poses one problem : it is hard to prove the reasoner to be sound (only doing what it was meant to, not discharging sequents that cannot be proved). Because the reasoner is in the trusted base, we should be absolutely sure of what it performs. How to validate the found path ?
+
===From Subversion===
  
−
As we know, the reasoner condense several inferences rules in only one proof rule. To validate the found path, we have to validate every single inference rule. To achieve it, we create, internally to the reasoner, a small proof tree built from internal proof rules (implemented in class Rules). Each rule contains one predicate and an array of rules (its antecedents). When the path is searched, the corresponding rule is created. When the path is found, we check that the predicate of the root rule is the same as the goal. If not, it means the found path was incorrect, so the reasoner fails, else the sequent is discharged.
+
The Subversion commit that corresponds to the last commit done in CVS is <tt>r6896</tt>. However, the first interesting Subversion commit is <tt>r6903</tt>. In between, lie some Subversion commits for massaging the result of porting from CVS, which can be ignored.
  
−
Example of rules :
+
====Extracting All Paths====
−
:<math>name\;of\;the\;rule\quad\frac{predicate\;of\;first\;antecedent\cdots predicate\;of\;last\;antecedent}{consequent\;of\;that\;rule}\left[parameters\right]</math>
 
−
:<math>Hypothesis\quad\frac{}{predicate}\left[predicate\right]</math>
 
−
:<math>IncludeBunion\quad\frac{A\bunion B\bunion C\bunion D\subseteq Z}{B\bunion C\subseteq Z}\left[B,~C\right]</math>
 
−
:<math>Composition\quad\frac{x\in A,~A\subseteq B}{x\in B}\left[~\right]</math>
 
  
−
= Implementation =
+
The first task is to identify the interesting paths in the Subversion repository, that is the ones to extract to the new Git repository.  For this, I have installed the tool [git://git.goodpoint.de/svneverever.git svneverever] and run it like that (assuming that I have a full copy of the Subversion repository from SourceForge in <tt>/tmp/svn</tt>):
 +
    svneverever --tags --branches --no-dots file:///tmp/svn > svn-paths.txt
  
−
This section explain how the tactic has been implemented.
+
The resulting file contains all the directory that have ever been committed to the Subversion repository.
  
−
=== Positions ===
+
====Writing Rules====
−
As it was said, we may sometimes need the position. It is represented by an array of integer. Here are the possible values the array contains (atomic positions) :
 
−
* '''''kdom''''' : it corresponds to the domain.
 
−
**<math>\left[A\cprod B\right]_{pos\;=\;kdom} = A</math>
 
−
**<math>\left[x\mapsto y\right]_{pos\;=\;kdom} = x</math>
 
−
**<math>\left[g\right]_{pos\;=\;kdom} = dom(g)</math>
 
−
* '''''kran''''' : it corresponds to the domain.
 
−
**<math>\left[A\cprod B\right]_{pos\;=\;kran} = B</math>
 
−
**<math>\left[x\mapsto y\right]_{pos\;=\;kran} = y</math>
 
−
**<math>\left[g\right]_{pos\;=\;kran} = ran(g)</math>
 
−
* '''''converse''''' : it corresponds to the child of an inverse
 
−
**<math>\left[f^{-1}\right]_{pos\;=\;converse}=f</math>
 
−
**<math>\left[A\cprod B\right]_{pos\;=\;converse} = B\cprod A</math>
 
−
For example, the following expressions at the given positions are equivalent.
 
−
:<math>\left[ran(dom(g))\right]_{pos\;=\;\left[\right]} = \left[dom(g)\right]_{pos\;=\;\left[kran\right]} = \left[g\right]_{pos\;=\;\left[kdom,\; kran\right]}</math>
 
  
−
Some combinations of atomic positions are equivalent. In order to simplify comparison between positions, they are normalized :
+
From the contents of the previous file, I have written rules for [git://gitorious.org/svn2git/svn2git.git svn2git from KDE]. They are available in file [https://sourceforge.net/p/rodin-b-sharp/rodincore/ci/master/tree/org.rodinp.releng/gitMigration/RodinCore.rules RodinCore.rules].
−
*<math>ran(f^{-1}) = dom(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kran\right]} = \left[f\right]_{pos\;=\;\left[kdom\right]}</math>
 
−
*<math>dom(f^{-1}) = ran(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kdom\right]} = \left[f\right]_{pos\;=\;\left[kran\right]}</math>
 
−
*<math>\left(f^{-1}\right)^{-1} = f\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~converse\right]} = \left[f\right]_{pos\;=\;\left[~\right]}</math>
 
  
−
=== Goal ===
 
  
−
A pair (expression ; position) <math>\left(exp\mapsto pos\right)</math> is said to be contained in the goal if and only if ''exp'' is contained in the goal, and if the position matched of ''exp'' in the goal is equal to ''pos''. For examples, let's see the [[#Annexe|annexe]]
 
  
−
=== Hypotheses ===
+
[[Category:Developer documentation]]
−
 
+
[[Category:Rodin Platform]]
−
As explained in the design decision part, there are two kinds of hypotheses which are recovered. But when hypotheses related to the left member of the goal <math>\left(x\in S\right)</math> are stored, the position of ''x'' is also record. Then, if there is an hypothesis such as <math>\left\{\cdots\;,\;y\mapsto x\mapsto z\;,\;m\mapsto x\;,\;\cdots\right\} = A</math>, then this hypothesis is mapped to the positions <math>\left\{\left[kdom,~kran\right],~\left[kran\right]\right\}</math>.
 
−
 
 
−
=== Find a path ===
 
−
 
 
−
Let's consider that following sequent : <math>x\in B,\quad dom(m\setminus n)\binter f = \left\{x\mapsto y,\;y\mapsto x\right\},\quad dom(p\ovl m)\subset g,\quad ran(g\bunion h)\bunion B\subseteq A\quad\vdash\quad x\in A</math>.
 
−
 
 
−
#From the goal we get two informations : the member which is ''x'' as well as the set we try to prove it belongs to which is ''A''.
 
−
#By knowing ''x'' we recover hypothesis giving informations about it. In our study case, from the hypothesis <math>dom(m\setminus n)\binter f = \left\{x\mapsto y,\;y\mapsto x\right\}</math> we infer that ''x'' belong to <math>\left(dom(m\setminus n)\binter f\right)</math> at those possible positions <math>\left[\;\left[kran\right],~\left[kdom\right]\;\right]</math>
 
−
#*'''Tactic :''' record all these informations <math>\left\{x\in B\mapsto B\mapsto\left[\;\right]\;,\;\left(dom(m\setminus n)\binter f = \left\{x\mapsto y,\;y\mapsto x\right\}\right)\mapsto\left(dom(m\setminus n)\binter f\right)\mapsto\left[\;\left[kran\right],\;\left[kdom\right]\;\right]\right\}</math>
 
−
#*'''Reasoner :''' We consider that the tactic will found the most complicated path. For each positions, we make the associated rule, which give in our example <math>\left\{dom(m\setminus n)\binter f\;\mapsto\;\left[kdom\right]\;\mapsto\;x\in dom(dom(m\setminus n)\binter f),~~~dom(m\setminus n)\binter f\;\mapsto\;\left[kran\right]\;\mapsto\;x\in ran(dom(m\setminus n)\binter f)\right\}</math>.
 
−
#Now, that we have a set to start the search of a path <math>\left(dom(m\setminus n)\binter f\right)</math>, we get all the expression containing it : <math>\left\{\;dom(m\setminus n)\binter f,~dom(m\setminus n),~ dom(m),~f\;\right\}</math>. As  we don't want to have expression such as ''dom(...)'', we modify the position.
 
−
#*'''Tactic :''' Here, there are only the mapping between the positions and the expression : <math>\left\{\;dom(m\setminus n)\binter f\;\mapsto\;\left[kran\right],~~~f\;\mapsto\;\left[kran\right],~~~m\;\mapsto\;\left[kdom,\;kran\right],~~~m\setminus n\;\mapsto\;\left[kdom,\;kran\right]\;\right\}</math>
 
−
#*'''Reasoner :''' we generate the rule corresponding to the computed sets : <math>\left\{~\cdots~m\;\mapsto\;\left[kdom,\;kran\right]\;\mapsto\;x\in ran(dom(m))~\cdots~\right\}</math>
 
−
#We test if one of these pair is contained in the goal. If so, we move to the step 5. But it clearly appears that it is not the case. So, we try to find hypotheses among the one denoting inclusion which are related to that pair. We clearly see that the expression <math>dom(m)\subseteq dom(p\ovl m)</math>. Actually, we search every expressions containing ''m'' using that mapping <math>m\;\mapsto\;\left[kdom,\;kran\right]</math>. From <math>dom(p\ovl m)</math> we can say that only the domain of ''m'' is contained in it. Then it ensures this position is part of the position of ''m'' in which ''x'' belongs to. If so we remove that position and obtain a new mapping <math>g\;\mapsto\;\left[kran\right]</math> (more details [[#Annexe|here]]) and we step back to 3 with that new pair.
 
−
#*'''Reasoner :''' the rule corresponding is generated <math>g\;\mapsto\;\left[kran\right]\;\mapsto\;x\in ran(g)</math>
 
−
#We find a path, the works is done.
 
−
#*'''Tactic :''' If a path has been found, then we call the reasoner with all the used predicates as input.
 
−
#*'''Reasoner :'''At the end, we check that the generated rule is equal to the goal. If so, the sequent is discharged. Else, a failure is returned.
 
−
 
 
−
We see that the tactic may not find the most simple path to discharge the sequent. Moreover, there are some cases where the tactic is able to find a path but the reasoner is unable to prove it due to a weakness in the rules (see [[#Untreated|all the untreated cases]]). Example :
 
−
:<math>x\in dom(f\bunion g)\binter A,~A\subseteq B,~dom(f)\bunion dom(g)\subseteq B~\vdash~x\in B</math>
 
−
Depending on whether the tactic returns <math>\left\{x\in dom(f\bunion g)\binter A,~dom(f)\bunion dom(g)\subseteq B\right\}</math> or <math>\left\{x\in dom(f\bunion g)\binter A,~A\subseteq B\right\}</math>, the reasoner will fail or succeed. To prevent such hazardous behavior, re-writing should be proceeded.
 
−
 
 
−
 
 
−
===== Annexe =====
 
−
 
 
−
{| class="wikitable" style="text-align:center; width:80%;"
 
−
|+ Examples. All the following positions are contained in this one <math>\left[kdom,\;kdom,\;kran\right]</math> <math>\left(x\in ran(dom(dom(g)))\right)</math>
 
−
|-
 
−
! scope=col | Predicate
 
−
! scope=col | Position of ''g'' matched
 
−
! scope=col | Inferred predicate
 
−
! scope=col | Position in ''h''
 
−
|-
 
−
|<math>g\subseteq h</math>
 
−
|<math>\left[\;\right]</math>
 
−
|<math>x\in ran(dom(dom(h)))</math>
 
−
|<math>\left[kdom,\;kdom,\;kran\right]</math>
 
−
|-
 
−
|<math>dom(g)\subseteq h</math>
 
−
|<math>\left[kdom\right]</math>
 
−
|<math>x\in ran(dom(h))</math>
 
−
|<math>\left[kdom,\;kran\right]</math>
 
−
|-
 
−
|<math>dom(dom(g))\subseteq h</math>
 
−
|<math>\left[kdom,\;kdom\right]</math>
 
−
|<math>x\in ran(h)</math>
 
−
|<math>\left[kran\right]</math>
 
−
|-
 
−
|<math>ran(dom(dom(g)))\subseteq h</math>
 
−
|<math>\left[kdom,\;kdom,\;kran\right]</math>
 
−
|<math>x\in h</math>
 
−
|<math>\left[~\right]</math>
 
−
|-
 
−
|<math>g^{-1}\subseteq h</math>
 
−
|<math>\left[conv\right]</math>
 
−
|<math>x\in ran(dom(ran(h)))</math>
 
−
|<math>\left[kran,\;kdom,\;kran\right]</math>
 
−
|-
 
−
|<math>dom(g)^{-1}\subseteq h</math>
 
−
|<math>\left[kdom,\;conv\right]</math>
 
−
|<math>x\in ran(ran(h))</math>
 
−
|<math>\left[kran,\;kran\right]</math>
 
−
|-
 
−
|<math>dom(dom(g))^{-1}\subseteq h</math>
 
−
|<math>\left[kdom,\;kdom,\;conv\right]</math>
 
−
|<math>x\in dom(h)</math>
 
−
|<math>\left[kdom\right]</math>
 
−
|-
 
−
|<math> ran(dom(dom(g)))^{-1}\subseteq h</math>
 
−
|<math>\left[kdom,\;kdom,\;kran,\;conv\right]</math>
 
−
|<math>x\in h^{-1}</math>
 
−
|<math>\left[conv\right]</math>
 
−
|}
 
−
 
 
−
In the case a converse appears at the end of the position of ''g'' matched, it is removed, then, we test if the position is part of the position. If so, it is removed and converse is added at the beginning of the array (which is automatically normalized).
 
−
 
 
−
= Untreated cases =
 
−
 
 
−
Some cases are not treated. Further enhancement may be provided for some.
 
−
*<math>x\in f,\quad f\in A\;op\;B\quad\vdash\quad x\in A\cprod B</math>
 
−
*<math>x\in f\otimes g,\quad f\subseteq A\cprod B,\quad g\subseteq C\cprod D\quad\vdash\quad x\in (A\cprod C)\cprod(B\cprod D)</math> as well as all the possibles re-writing.
 
−
*<math>x\in f\otimes g,\quad f\subseteq h\quad\vdash\quad x\in h\otimes g</math>
 
−
*<math>x\in \left\{a,~b,~c\right\},\quad\left\{a,~b,~c,~d,~e,~f\right\}\subseteq D\quad\vdash\quad x\in D</math>
 
−
*<math>x\in A\cprod B,\quad A\subseteq C\quad\vdash\quad x\in C\cprod B</math>
 
−
*<math>x\in dom(f)\cap A\quad\vdash\quad x\in dom(A\domres f)</math>
 
−
*<math>x\in ran(f)\cap A\quad\vdash\quad x\in ran(f\ranres A)</math>
 
−
*<math>x\in dom(A\domres f)\quad\vdash\quad x\in dom(f)\cap A</math>
 
−
*<math>x\in ran(f\ranres A)\quad\vdash\quad x\in ran(f)\cap A</math>
 
−
*<math>x\in dom(f\bunion g)\quad\vdash\quad x\in dom(f)\bunion dom(g)</math>
 
−
*<math>x\in dom(f)\bunion dom(g)\quad\vdash\quad x\in dom(f\bunion g)</math>
 
−
*<math>x\in dom(f\binter g)\quad\vdash\quad x\in dom(f)\binter dom(g)</math>
 
−
*<math>x\in dom(f)\binter dom(g)\quad\vdash\quad x\in dom(f\binter g)</math>
 
−
*<math>x\in ran(f\bunion g)\quad\vdash\quad x\in ran(f)\bunion ran(g)</math>
 
−
*<math>x\in ran(f)\bunion ran(g)\quad\vdash\quad x\in ran(f\bunion g)</math>
 
−
*<math>x\in ran(f\binter g)\quad\vdash\quad x\in ran(f)\binter ran(g)</math>
 
−
*<math>x\in ran(f)\binter ran(g)\quad\vdash\quad x\in ran(f\binter g)</math>
 
−
*<math>x\in (f\bunion g)^{-1}\quad\vdash\quad x\in f^{-1}\bunion g^{-1}</math>
 
−
*<math>x\in f^{-1}\bunion g^{-1}\quad\vdash\quad x\in (f\bunion g)^{-1}</math>
 
−
*<math>x\in (f\binter g)^{-1}\quad\vdash\quad x\in f^{-1}\binter g^{-1}</math>
 
−
*<math>x\in f^{-1}\binter g^{-1}\quad\vdash\quad x\in (f\binter g)^{-1}</math>
 
−
*:the last 12 examples fails because the Rules have some weakness. This show that some re-writing should be performed.
 
−
*<math>x\in A\bunion dom(f\binter g),A\bunion dom(f)\subseteq B\quad\vdash\quad x\in B</math>
 
−
*<math>x\in A\binter dom(f),A\binter dom(f\bunion g)\subseteq B\quad\vdash\quad x\in B</math>
 
−
*:the reason for the failure of the two last examples is that when union or intersection are compared, we should take all the expression containing each member, but we don't.
 
−
*<math>x\in A\cprod dom(B\cprod C)\quad\vdash\quad x\in A\cprod B</math>
 
−
*:it fails because when we get equivalent expression of the Cartesian product, we don't go further enough.
 
−
*:<math>\bigl(</math> where <math>op_1</math> and <math>op_2</math> are ones of :<math>\quad\rel, \trel, \srel, \strel, \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij\bigr)</math>
 
−
 
 
−
[[Category:Design proposal]]
 

Revision as of 10:25, 20 November 2013

The source files of the Rodin platform and associated plug-ins are under version control on SourceForge. Initially, we used CVS and we migrated to Subversion in March 2009. This page describes the migration to another version control system: Git.

The migration from CVS to Subversion was far from perfect. But then, there was not much time available for polishing it. In this new migration to Git, we would like to start again from scratch and first migrate the CVS repository to Git, then all the subsequent commits in Subversion.

Another concern is that the Subversion repository has grown very large. We would like to split it in several smaller repositories, which is now possible with Git. The new repositories should each correspond to a set of plug-ins which are delivered together.

Important Note: Make sure that all conversions are performed in a case sensitive filesystem. For instance, on Mac OS X, create a special Volume with a different filesystem than the default (which is case insensitive).

Migration of the SMT plug-in

To begin the migration to Git, I started with a very simple set of plug-ins: the SMT Solver plug-ins. Their history is linear, with just some renaming from time to time. All the development was performed in Subversion. The conversion was performed with git-svn with no special constraint using migrate-svn-smt.sh.

Migration of the Core Platform

For the Core Platform, the migration is more intricate. As stated in the introduction, the initial conversion from CVS to Subversion was of average quality. Moreover, when one includes the sources in the _exploratory directory, the files to migrate are a bit scattered all over the place.

The migration is then performed in three steps: - Migrate the CVS repository - Migrate the Subversion repository - Merge the two together

From CVS

This is done with the ZSH script migrate-core-from-cvs.sh. This script creates a fresh Git repository from a CVS archive (67 MB). To run it, one needs the CVS archive be named cvs-Rodin-b-sharp.tgz and an author-mapping file named Authors.txt.

After running the script, the git repository needs some massaging:

  • Fix three commit messages that are not UTF-8:
     939bacf56436084c5fb58b041a26c9fe4dd7d876 (2008-01-16T18:57:44Z)
     d2eca7a9ec561c2c7bfbc9c5d57ca9558964ee87 (2008-10-02T16:46:07Z)
     dccf0b77d7d20538a44df5aac719646eb2b62fa4 (2008-10-09T13:06:44Z)
  • Merge the branch UNDO_DEV back into master as described below.
  • Rename tags into a hierarchy.

Merging a Branch Back in Main Branch

After importation from CVS, some development branches are dangling. To make history easier to browse, one needs to merge them back into the main development branch. This is done by grafting.

Suppose that the development branch mybranch needs to be merged back into the main development. First, identify the commit where the branch has ceased to be useful. Let's name this commit mergepoint. Then, type: 

     echo $(git log -1 --format=format:'%H %P' mergepoint) \
           $(git show-ref -s branch) >> .git/info/grafts

Then check that this change works fine and type the following command to make it permanent: 

     git filter-branch -- --all

The branch names can now be removed with 

     git branch -d branch
     git branch -d mergepoint

Renaming Tags into a Hierarchy

After importation from CVS, the tags were named: 

I20060720
…
fr.systerel.explorer-0.0.1
fr.systerel.explorer-1.0.0
org.eventb.core-0.5.1
org.eventb.core-0.5.3

This is a long list and it is not very practical. However, Git supports hierarchical tags, like a filesystem. To benefit from this, type the following commands: 

cd .git/refs/tags
mkdir RodinCore
mv I* RodinCore/
ls | grep -e '-' | cut -d- -f1 | sort -u |
    for f in $(cat /tmp/a); do
        mkdir $f
        for g in ${f}-*; do
            mv $g $f/$(echo $g | sed "s:^${f}-::")
        done
    done

The list of tags becomes much shorter, as they are now neatly organized by plug-ins.

From Subversion

The Subversion commit that corresponds to the last commit done in CVS is r6896. However, the first interesting Subversion commit is r6903. In between, lie some Subversion commits for massaging the result of porting from CVS, which can be ignored.

Extracting All Paths

The first task is to identify the interesting paths in the Subversion repository, that is the ones to extract to the new Git repository. For this, I have installed the tool svneverever and run it like that (assuming that I have a full copy of the Subversion repository from SourceForge in /tmp/svn): 

   svneverever --tags --branches --no-dots file:///tmp/svn > svn-paths.txt

The resulting file contains all the directory that have ever been committed to the Subversion repository.

Writing Rules

From the contents of the previous file, I have written rules for svn2git from KDE. They are available in file RodinCore.rules.

Retrieved from ‘https://wiki.event-b.org/index.php?title=Membership_in_Goal&oldid=6116’