/[meta-cvs]/meta-cvs/F-54B5FF01DC6392F28A104A8A58761CB6
ViewVC logotype

Diff of /meta-cvs/F-54B5FF01DC6392F28A104A8A58761CB6

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.4 by kaz, Sun Jan 27 16:49:51 2002 UTC revision 1.5 by kaz, Thu Jan 31 05:35:02 2002 UTC
# Line 1  Line 1 
1                              MCVS---Meta CVS                    Meta-CVS --- A Directory Structure
2                A Directory Structure Versioning Layer Over                           Versioning Layer Over
3                       The Concurrent Version System.                       The Concurrent Versions System.
4    
5                                Kaz Kylheku                                Kaz Kylheku
6                              January 25, 2002                              January 25, 2002
# Line 13  Line 13 
13    
14    Abstract    Abstract
15    
16      This is MCVS, Meta-(Concurrent Versions System), a front end for      This is Meta-CVS, Meta-(Concurrent Versions System), a front end for
17      CVS.  It supports the concurrent and independent versioning of      CVS.  It supports the concurrent and independent versioning of
18      files, as well as a directory structure, by several people.  I have      files, as well as a directory structure, by several people.  I have
19      it been using it for a few weeks now, mostly just to version the      it been using it for a few weeks now, mostly just to version the
20      MCVS sources themselves.  It uses the cvs program in such a way that      Meta-CVS sources themselves.  It uses the cvs program in such a way that
21      you can not only version the file contents, but you can move and      you can not only version the file contents, but you can move and
22      rename files.  These changes are committed to the repository, and      rename files.  These changes are committed to the repository, and
23      can be picked up by an update, which will incorporate them by      can be picked up by an update, which will incorporate them by
# Line 48  Line 48 
48        1.11, it still has annoying quirks and some serious limitations.        1.11, it still has annoying quirks and some serious limitations.
49    
50        One of the biggest limitations of CVS is it does not treat the        One of the biggest limitations of CVS is it does not treat the
51        directory structure of a module as a versioned object. MCVS solves        directory structure of a module as a versioned object. Meta-CVS
52        this problem not by intruding in any way into the well-debugged        solves this problem not by intruding in any way into the
53        and time-tested CVS code, but by introducing a layer of        well-debugged and time-tested CVS code, but by introducing a layer
54        indirection.  MCVS retains the fundamental capabilites of CVS: the        of indirection.  Meta-CVS retains the fundamental capabilites of
55        ability to branch and merge, to work in parallel, to work over a        CVS: the ability to branch and merge, to work in parallel, to work
56        variety of network transports and so on. CVS worked as a front end        over a variety of network transports and so on. CVS worked as a
57        for RCS; similarly, MCVS is a front end for CVS.        front end for RCS; similarly, Meta-CVS is a front end for CVS.
58    
59        It turns out that MCVS solves a few other infelicities in CVS as        It turns out that Meta-CVS solves a few other infelicities in CVS
60        well. A few tricky scenarios that cause grief in CVS are no        as well. A few tricky scenarios that cause grief in CVS are no
61        longer problems in MCVS, such as: two developers concurrently        longer problems in Meta-CVS, such as: two developers concurrently
62        adding the same file, or one developer removing a file that        adding the same file, or one developer removing a file that
63        another is working on.        another is working on.
64    
65        MCVS works by creating a special representation of the versioned        Meta-CVS works by creating a special representation of the
66        file tree, and this special representation is what is stored in        versioned file tree, and this special representation is what is
67        CVS. Thus the naive direct mapping between the versioned tree and        stored in CVS. Thus the naive direct mapping between the versioned
68        the tree in the repository is avoided.        tree and the tree in the repository is avoided.
69    
70        The aim of this paper is to document this simple representation        The aim of this paper is to document this simple representation
71        and explain how it supports the directory versioning operation.        and explain how it supports the directory versioning operation.
# Line 78  Line 78 
78        object as a text file. This is a given. CVS can effectively handle        object as a text file. This is a given. CVS can effectively handle
79        only text input in its merging and conflict identification        only text input in its merging and conflict identification
80        algorithms. A critical non-functional constraint in the        algorithms. A critical non-functional constraint in the
81        requirements of MCVS is that CVS is not to be modified in any way;        requirements of Meta-CVS is that CVS is not to be modified in any
82        nobody should have to to install new CVS code on a client or        way; nobody should have to to install new CVS code on a client or
83        server machine to use MCVS. Morever, the CVS code is fragile C        server machine to use Meta-CVS. Morever, the CVS code is fragile C
84        that has been debugged for over a decade (and counting).        that has been debugged for over a decade (and counting).
85    
86        To treat the file structure as a versioned entity, therefore, it        To treat the file structure as a versioned entity, therefore, it
# Line 99  Line 99 
99        when its path name changes. This means that we must never change        when its path name changes. This means that we must never change
100        the name of the file, at least not the name which is known to CVS.        the name of the file, at least not the name which is known to CVS.
101    
102        MCVS represents the file structure of a project as a simple entity        Meta-CVS represents the file structure of a project as a simple
103        called a ``file mapping''. The file mapping associates path names        entity called a ``file mapping''. The file mapping associates path
104        with a flat database of files.  Both the mapping and the files are        names with a flat database of files.  Both the mapping and the
105        stored in CVS. The files have machine-generated names; only        files are stored in CVS. The files have machine-generated names;
106        through the mapping are they given actual names as they appear to        only through the mapping are they given actual names as they
107        the users. The names known to CVS are called ``F- files''.        appear to the users. The names known to CVS are called ``F-
108          files''.
109    
110        MCVS manipulates the mapping as a simple data structure in the        Meta-CVS manipulates the mapping as a simple data structure in the
111        Lisp language. Lisp has a built-in parser and formatter for        Lisp language. Lisp has a built-in parser and formatter for
112        reading a printed representation of a List object and producing a        reading a printed representation of a List object and producing a
113        printed representation. Thus the text file format for the MCVS        printed representation. Thus the text file format for the Meta-CVS
114        mapping is simply a file containing a Lisp association list, with        mapping is simply a file containing a Lisp association list, with
115        special care taken to print each element of the association on a        special care taken to print each element of the association on a
116        separate line of text, and maintaining a consistently sorted order        separate line of text, and maintaining a consistently sorted order
# Line 124  Line 125 
125          foo/src/Makefile          foo/src/Makefile
126          foo/src/foo.c          foo/src/foo.c
127    
128        what does a MCVS representation look like? This is best        what does a Meta-CVS representation look like? This is best
129        understood in terms of the working copy checked out from CVS        understood in terms of the working copy checked out from CVS via
130        via MCVS, which contains these things:        Meta-CVS, which contains these things:
131    
132          foo/MCVS/CVS/Entries          foo/MCVS/CVS/Entries
133          foo/MCVS/CVS/... other CVS metadata ...          foo/MCVS/CVS/... other CVS metadata ...
# Line 146  Line 147 
147        There is a subdirectory called MCVS, which contains a CVS        There is a subdirectory called MCVS, which contains a CVS
148        subdirectory. This MCVS subdirectory is in fact the CVS        subdirectory. This MCVS subdirectory is in fact the CVS
149        ``sandbox''. Everything else under foo are the working files.        ``sandbox''. Everything else under foo are the working files.
150        Thus every MCVS working copy is just an ordinary file tree, except        Thus every Meta-CVS working copy is just an ordinary file tree,
151        that the top level directory contains a MCVS subdirectory with        except that the top level directory contains a MCVS subdirectory
152        interesting contents.        with interesting contents.
153    
154        What are these files under MCVS? There are some files with cryptic        What are these files under MCVS? There are some files with cryptic
155        names like F-123D...438. Then there are two files MAP and        names like F-123D...438. Then there are two files MAP and
# Line 156  Line 157 
157    
158        Firstly, it should be understood that the F- files and MAP are        Firstly, it should be understood that the F- files and MAP are
159        versioned in CVS. On the other hand, MAP-LOCAL is a file that is        versioned in CVS. On the other hand, MAP-LOCAL is a file that is
160        not known to CVS, but important to the functioning of MCVS.        not known to CVS, but important to the functioning of Meta-CVS.
161    
162        The four F- files are the actual CVS representations of        The four F- files are the actual CVS representations of
163        foo/README, foo/src/foo.c, foo/src/Makefile and foo/inc/foo.h.        foo/README, foo/src/foo.c, foo/src/Makefile and foo/inc/foo.h.
# Line 180  Line 181 
181        operation is performed, it may incorporate changes from the        operation is performed, it may incorporate changes from the
182        repository into MAP, causing the MAP to no longer reflect the        repository into MAP, causing the MAP to no longer reflect the
183        local file structure. In fact MAP can at that point contain        local file structure. In fact MAP can at that point contain
184        unresolved conflicts, so that it is not usable by MCVS, requiring        unresolved conflicts, so that it is not usable by Meta-CVS,
185        manual intervention. The MAP-LOCAL copy, however, remains        requiring manual intervention. The MAP-LOCAL copy, however,
186        untouched and consistent.        remains untouched and consistent.
187    
188        Because MCVS maintains a local copy of the mapping, the MCVS        Because Meta-CVS maintains a local copy of the mapping, the
189        update operation can compute the differences between the new        Meta-CVS update operation can compute the differences between the
190        mapping coming from the repository and the local mapping.  These        new mapping coming from the repository and the local mapping.
191        differences can then be translated into filesystem-rearranging        These differences can then be translated into
192        actions that change the shape of the working copy to bring it up        filesystem-rearranging actions that change the shape of the
193        to date. Then MAP and MAP-LOCAL are once again identical.        working copy to bring it up to date. Then MAP and MAP-LOCAL are
194          once again identical.
195    
196        This rearranging is the heart of the MCVS system. Everything else        This rearranging is the heart of the Meta-CVS system. Everything
197        is largely just manipulations of the mappings. For example,        else is largely just manipulations of the mappings. For example,
198        renaming a file is simple. Open up MCVS/MAP in a text editor, and        renaming a file is simple. Open up MCVS/MAP in a text editor, and
199        change a path (taking care not to create a duplicate, or otherwise        change a path (taking care not to create a duplicate, or otherwise
200        corrupt the mapping). Then save it and run the mcvs update.  MCVS        corrupt the mapping). Then save it and run the mcvs update.
201        will propagate the change you made by physically relocating that        Meta-CVS will propagate the change you made by physically
202        file. If you like what you have done, simply commit. You can        relocating that file. If you like what you have done, simply
203        commit at the CVS level within the MCVS directory. But of course,        commit. You can commit at the CVS level within the MCVS
204        a front end MCVS file renaming operation is provided, and so is a        directory. But of course, a Meta-CVS file renaming operation is
205        commit operation, which in addition to running CVS also ensures        provided, and so is a commit operation, which in addition to
206        that the F- files are properly synchronized with their unfolded        running CVS also ensures that the F- files are properly
207        counterparts.        synchronized with their unfolded counterparts.
208    
209    2.2 Synchronization    2.2 Synchronization
210    
211        The next problem to tackle is how to establish the correspondence        The next problem to tackle is how to establish the correspondence
212        between the F- files and the working files. MCVS does this in a        between the F- files and the working files. Meta-CVS does this in a
213        platform-specific way, namely by relying on Unix hard links.        platform-specific way, namely by relying on Unix hard links.
214    
215        When MCVS checks out a sandbox, it creates hard links, so that a        When Meta-CVS checks out a sandbox, it creates hard links, so that
216        F- file and its corresponding working file are in fact the same        a F- file and its corresponding working file are in fact the same
217        filesystem object. Thus ``unpacking'' the F- files through the        filesystem object. Thus ``unpacking'' the F- files through the
218        mapping does not require the mass duplication of of file data,        mapping does not require the mass duplication of of file data,
219        only the creation of directories and links.        only the creation of directories and links.
# Line 222  Line 224 
224        instance. If cvs up creates a new F- file, that file is no longer        instance. If cvs up creates a new F- file, that file is no longer
225        connected with the working file.        connected with the working file.
226    
227        To keep the two synchronized, MCVS performs a synchronization        To keep the two synchronized, Meta-CVS performs a synchronization
228        operation. This operation sweeps over the file map, and repairs        operation. This operation sweeps over the file map, and repairs
229        any broken links. If either of the two files is missing, then a        any broken links. If either of the two files is missing, then a
230        link is created. If both are present, but are distinct objects,        link is created. If both are present, but are distinct objects,
231        then the one with the most recent modification timestamp supersedes;        then the one with the most recent modification timestamp
232        the other is unlinked and replaced with a link to the newer one.        supersedes; the other is unlinked and replaced with a link to the
233          newer one.
234    
235        A synchronization must be done before any operation which can        A synchronization must be done before any operation which can
236        cause a file to be moved, removed, or to be committed to the CVS        cause a file to be moved, removed, or to be committed to the CVS
237        repository. In all these situations, the F- files must have        repository. In all these situations, the F- files must have
238        the correct contents.        the correct contents.
239    
240        The MCVS update operation must perform synchronization twice:        The Meta-CVS update operation must perform synchronization twice:
241        before the CVS update to ensure that the F- files carry all of the        before the CVS update to ensure that the F- files carry all of the
242        local changes; then after the CVS update to make sure that any        local changes; then after the CVS update to make sure that any
243        newly incorporated changes propagate back to the working copy.        newly incorporated changes propagate back to the working copy.
# Line 242  Line 245 
245    
246    3. Surprising Advantages    3. Surprising Advantages
247    
248        The MCVS representation brings with it a few advantages which were        The Meta-CVS representation brings with it a few advantages which
249        not immediately obvious in the design stages, but came to light        were not immediately obvious in the design stages, but came to
250        during development. In addition to the lack of directory structure        light during development. In addition to the lack of directory
251        versioning, CVS has a few other infelicities which go away under        structure versioning, CVS has a few other infelicities which go
252        MCVS. Also, bringing in the capability to version directory        away under Meta-CVS. Also, bringing in the capability to version
253        structure also brings in a new concern. Free software developers        directory structure also brings in a new concern. Free software
254        uses patches to communicate code changes to each other.  The        developers uses patches to communicate code changes to each other.
255        traditional tools for producing and applying patches, like CVS, do        The traditional tools for producing and applying patches, like
256        not handle directory versioning. MCVS has some answers to these        CVS, do not handle directory versioning. Meta-CVS has some answers
257        problems.        to these problems.
258    
259    3.1 File Adding Conflicts    3.1 File Adding Conflicts
260    
# Line 262  Line 265 
265        CVS complains that the file was independently added by a second        CVS complains that the file was independently added by a second
266        party, and not allow the commit to proceed.        party, and not allow the commit to proceed.
267    
268        In MCVS, this cannot happen. MCVS recognizes that if two people        In Meta-CVS, this cannot happen. Meta-CVS recognizes that if two
269        add a file, it is not the same file. Names do not determine        people add a file, it is not the same file. Names do not determine
270        equivalence, semantics does! When a file is added to MCVS, a F- file        equivalence, semantics does! When a file is added to Meta-CVS, a
271        is created to represent it. That F- file name contains a randomly        F- file is created to represent it. That F- file name contains a
272        chosen 128-bit number, expressed in hexadecimal.  It is extremely        randomly chosen 128-bit number, expressed in hexadecimal.  It is
273        unlikely that two such numbers will collide, so in practice, one        extremely unlikely that two such numbers will collide, so in
274        will ``never'' see the aforementioned CVS error message.        practice, one will ``never'' see the aforementioned CVS error
275          message.
276    
277        Instead, what will happen when developers choose the same path        Instead, what will happen when developers choose the same path
278        name for a file is that either a conflict will arise in the MAP        name for a file is that either a conflict will arise in the MAP
279        file, which will have to be resolved, or else the mapping will        file, which will have to be resolved, or else the mapping will
280        contain a duplicate path name, which can be detected by MCVS as an        contain a duplicate path name, which can be detected by Meta-CVS
281        error which again, the users must resolve. Each file is a separate        as an error which again, the users must resolve. Each file is a
282        object with its own version history; that two objects accidentally        separate object with its own version history; that two objects
283        map to the same name is a minor, correctable problem.        accidentally map to the same name is a minor, correctable problem.
284    
285    3.2 File Removal Conflicts    3.2 File Removal Conflicts
286    
# Line 292  Line 296 
296        still be used, it persists, and thereafter, it is automatically        still be used, it persists, and thereafter, it is automatically
297        removed when the system finds it necessary or convenient to do so.        removed when the system finds it necessary or convenient to do so.
298    
299        It turns out that MCVS supports a kind of garbage collection        It turns out that Meta-CVS supports a kind of garbage collection
300        concept. When a file is removed, it does not have to be subject to        concept. When a file is removed, it does not have to be subject to
301        ``cvs remove''. It only has to be removed from the file mapping,        ``cvs remove''. It only has to be removed from the file mapping,
302        but the F- file can remain unremoved. What this means is that the        but the F- file can remain unremoved. What this means is that the
303        F- file contines to be checked out, so it occupies bandwidth and        F- file contines to be checked out, so it occupies bandwidth and
304        space. What happens if a user has outstanding changes, and        space. What happens if a user has outstanding changes, and
305        performs an MCVS update which removes the file? The link        performs an Meta-CVS update which removes the file? The link
306        synchronization ensures that the outstanding changes are        synchronization ensures that the outstanding changes are
307        transferred to the F- file before the update. So the changes are        transferred to the F- file before the update. So the changes are
308        not lost!  It is possible to manually restore that F- file in the        not lost!  It is possible to manually restore that F- file in the
# Line 307  Line 311 
311        again. And, of course, the F- file can be committed to CVS whether        again. And, of course, the F- file can be committed to CVS whether
312        or not it is reentered into the map.        or not it is reentered into the map.
313    
314        The space problem can be dealt with by a MCVS ``garbage        The space problem can be dealt with by a Meta-CVS ``garbage
315        collection'' routine that can be invoked administratively.  This        collection'' routine that can be invoked administratively.  This
316        will sweep through the F- files, identify any which have no        will sweep through the F- files, identify any which have no
317        mapping, and ``cvs remove'' these.        mapping, and ``cvs remove'' these.
318    
319    3.3 Diffing and Patching    3.3 Diffing and Patching
320    
321        Another surprising advantage of MCVS is that it addresses the        Another surprising advantage of Meta-CVS is that it addresses the
322        problem of distributing patches which patch the file system        problem of distributing patches which patch the file system
323        structure as well as contents.        structure as well as contents.
324    
# Line 323  Line 327 
327        the capabilities of any change management tools that are based on        the capabilities of any change management tools that are based on
328        flat files.        flat files.
329    
330        A developer can obtain a copy of a project in MCVS form, then work        A developer can obtain a copy of a project in Meta-CVS form, then
331        on making changes, including the renaming of paths. These changes        work on making changes, including the renaming of paths. These
332        are represented in a new MCVS file set. A diff is computed between        changes are represented in a new Meta-CVS file set. A diff is
333        the new and the old. Someone with a copy of the original can patch        computed between the new and the old. Someone with a copy of the
334        it, to reproduce the changes.  All that is needed is the MCVS        original can patch it, to reproduce the changes.  All that is
335        software to realize the rearrangements.        needed is the Meta-CVS software to realize the rearrangements.

Legend:
Removed from v.1.4  
changed lines
  Added in v.1.5

  ViewVC Help
Powered by ViewVC 1.1.5