Re: [RFC] Submodules in GIT

I am currently working on adding submodule support to GIT. Here I am presenting some prototyping work to show how submodules could be implemented in GIT.

What is a submodule -------------------

A submodule in a GIT repository which is managed by another higher-layer parent repository. Both the submodule and the parent repository can be used as a normal GIT repository but there are links between them. That means that you can merge, push and pull both on the parent and on individual submodule level.

The parent repository is special in that it does not only hold individual files but also complete submodule trees, complete with their own history. The history of the parent and the submodule are independent, but each version of the parent is linked to exactly one version of the submodule.

The submodule is special in that it has one special branch which is tracked by the parent. Each time something is commited to this branch, this automatically changes the parent, just like modifying normal files. Each time the parent gets updated, this submodule branch gets updated automatically.

As a submodule has all the properties of a normal GIT repository, it can also contain submodules itself.

Previous submodule proposal ---------------------------

My first experiment in implementing submodules was a very simple one: Store the submodule refs in the working directory of the parent repository and include them in the version control.

This way the most important properties of submodules are easily to obtain. Each version of the parent stores the exact version of all submodules and with the help of some shell scripts it is easily possible to update the submodule when there are updates to the parent repository.

However, this easy approach has several drawbacks. The most important one is that the GIT core does not know about submodules, they are only built on top of them. For this reason it is difficult to support fsck-objects and prune in such a setup.

In order to permanently keep all previous stages of the parent, there is the need to also keep all versions of the submodules which have been linked to the parent. All operations which have to walk the entire object database have to know all possible references of the submodule. This is easy if the submodule is only fast-forwarded, without switching branches and without removing the submodule. Under these conditions it is enough to walk the current reference of the submodule which is stored in its parent. But if there are past versions of the submodule which are not reachable by the current submodule commit then it is difficult to keep them in the database when the submodule is handled by a standard GIT core. This could only be solved by creating fake references for all possible versions of the submodule.

New approach ------------

In order to make the GIT core know about all possible versions of the submodule it is not enough to store one reference in the parent working directory. The GIT core has to be changed so that it knows about all submodule references while traversing the parent repository. This means that both the submodule and the parent repository have to use the same object database. (I already did this for my first experiment, but it was not really neccessary at that time.)

A submodule really is part of the parent tree, so it is very natural to add the link to the submodule commit into the GIT tree data structure. In addition to links to blobs and other trees, they can now also hold a link to a commit, which in turn has the pointers to the submodule tree and its history. In order to differenciate a submodule entry with normal file or directory entries, they get a special file mode.

Directly including the submodules in the object database allows the traversal of the entire repository, together with the parent and all submodules. In this way it is possible to support fsck-objects and prune when they are executed in the parent repository. However, submodules can contain branches which are independent from the one stored in the parent. So all references and the working directory index of the submodules have to be made available to the parent, too.

When a parent containing submodules is checked out, the submodul entry is stored in the index, just like it is done for all normal files. But instead of writing one file to the working directory, a complete GIT repository is created (with the object database linked to the parent one). This submodule gets a reference "refs/heads/module" from the parent's index entry. The index entry in the parent can be updated with update-index just like other entries.

When a merge in the parent has to resolve changes in the submodule, then it does exactly the same as for files: at first it is tried to resolve it in the index and if this is not possible it will have store stages 1-3 in the index and tries a content merge. The only difference with submodules is that the content merge is not possible with a simple diff3 call, but that the GIT merge machinery has to recurse into the submodule.

Implementation --------------

Obviously, all the tree traversal routines have to be modified to recognize a submodule and to correctly traverse it. The submodule entry gets a special S_IFSOCK file mode to distinguish it from other entries. This special file mode is used for both the tree entries in the object database and for the index entries of the submodule in the parent index.

Some basic low-level commands now (more or less) cope with submodules. Merging of submodules has not yet been implemented.

The current status can be viewed in http://git.admingilde.org/tali/git.git/module2 (on top of next)

The code now passes the small test-script so at least a little bit of it must be working ;-). Please feel free to give it a try and complain that it does not work the way you expect it.

What's next? ------------

The most important next step is to commit to some object database format for submodules. So please, do give feedback about the proposed changes to the tree object.

The second most important step is to make it possible to merge submodules.

After that, for sure there are enough bugs to fix to keep me busy for some time... ;-)

Could you please add to http://git.or.cz/gitwiki/SubprojectSupport (even if all it would be is a link to archive of this thread)? TIA.

Martin Waitz <tali@admingilde.org> wrote:

Aside from a GUI for Git that I can give to a non-technical
user and have them be productive with (and without getting "this
sucks!" complaints from them), submodule support is the next highest
priority feature for me in Git.  So as soon as I can get git-gui
to that point I'll probably redirect as much of my "Git time"
as I can to testing your submodule implementation.
 

Right.  And what's really cool about that is many times a subproject
merge will be trivial, so top level project merges will be still be
trivial in index merges.  But what's complicated about that is you
need to make sure the subproject working directory is fast-forwarded
to the new commit.  :)
 

I think the S_IFSOCK approach is the right way to go here, and thus I'm reasonably happy with this repository format. But Linus and Junio do tend to be better at this than I... :-)

On Mon, Nov 20, 2006 at 10:51:16PM CET, Martin Waitz wrote:

(For those wondering, a diff of the changes is at:

	http://git.admingilde.org/tali/git.git/?a=commitdiff;h=module2;hp=next

Any bright ideas on how to best make such diffs reachable in the UI?)

Few thoughts on this topic. Some of those are repeating what was said eaelier

1. Submodule (subproject) as commit-in-a-tree

Let's try to paint a little diagram (attribution missing):

belonging to: /--------- supermodule -------\ /---- submodule -------\

commit -> tree +-> blob
  |            +-> tree -> ...
  |            +-----------------> commit -> tree -> ...
  v                                  |
commit -> tree +-> ...               v
  |            +-----------------> commit -> ...
  v                        /         |
commit -> tree +-> ...    /          |
  |            +---------/           v
  |                                commit -> ...
  v                                  |
commit -> tree +-> ...               v
               +-----------------> commit

Both have their independent history, but they are linked as some submodule versions are part of the supermodule tree.

2. Working area for project with submodules

Submodule as separate repository model
supermodule
+ .git/  <------------------------.
  + HEAD                          |
  + index                         |
  + objects/                      |
  + objects/info/alternates ---.  |
+ subdir1/                     |  |
  + sub1file                   |  ^                   
+ submodule/                   |  |
  + .git                       v  |
    + HEAD                     |  |
    + index                    |  |
    + objects/  <--------------'  |
    +[objects/info/borrowers] ----'
  + subsubdir/
    + submfile
+ file

Embedded submodule model
supermodule
+ .git/
  + HEAD
  + index
  + objects/
  +[refs/submodules/submodule/HEAD]
  +[refs/submodules/submodule/index]
+ subdir1/
  + sub1file
+ submodule/
  + subsubdir/
    + submfile
+ file

The [fictional] borrowers file is for git-prune and friends (also git-repack with -d option) to not remove objects needed by supermodule (when for example submodule history got rewritten). But you can do without it, as long as you don't rewind or don't prune in supermodule.

The problem with submodule as separate git repository is that if you move submodule (subproject) somewhere else in the repository (or just rename it), you have to update alternates file... and this happens not only on move itself, but also on checkout and reset. But that can be managed by having in alternates all possible places the submodule ends into. I don't know if it is truly a problem.

Alternate solution would be to have submodule objects [also] in the main (superproject) object database (for example fetched from submodule object repository on supermodule commit with changing submodule).

Perhaps instead of objects/info/alternates we should use objects/info/modules, or even modules file (as top .git dir).

The problem with embedded submodule model is ensuring that changes in submodule go to submodule (using submodule refs; at least HEAD and submodule index). And there are troubles with treating submodule separately, for example cloning submodule only, or fetching from submodule only.

3. Output of git-ls-tree and git-ls-files (git-ls-index ;-) for
project with submodules.

$ git ls-tree HEAD 040000 tree 959dd5d97e665998eb26c764d3a889ae7903d9c2 subdir1 140000 subm ccddf1d4b0cf7fd3a699d8b33cf5bc4c5c4435b7 submodule 100644 blob a57a33b81ac6c9cb5ec0c833edc21bd66428d976 file

$ git ls-tree -r -t HEAD 040000 tree 959dd5d97e665998eb26c764d3a889ae7903d9c2 subdir1 100644 blob 70d8b9838a7333bc5a1edb93cf0e9abdbcf146cc subdir1/sub1file 140000 subm ccddf1d4b0cf7fd3a699d8b33cf5bc4c5c4435b7 submodule 040000 tree 959dd5d97e665998eb26c764d3a889ae7903d9c2 submodule/subsubdir 100755 blob 6579f06b05c91f00f4f45015894f2bfab1076bf6 submodule/subsubdir/submfile 100644 blob a57a33b81ac6c9cb5ec0c833edc21bd66428d976 file

$ git ls-files --stages 100644 70d8b9838a7333bc5a1edb93cf0e9abdbcf146cc 0 subdir1/sub1file 140000 ccddf1d4b0cf7fd3a699d8b33cf5bc4c5c4435b7 0 submodule 100644 a57a33b81ac6c9cb5ec0c833edc21bd66428d976 0 file

4. Workflow(s) for project with submodules

$ cd submodule
submodule$ edit subsubdir/submfile
submodule$ git update-index subsubdir/submfile  # this updates submodule index
submodule$ git commit -m "Submodule change"     # this changes submodule HEAD
submodule$ cd ..
$ git update-index submodule                    # this updates index 
                                                  to submodule HEAD version
$ git commit -m "Change in submodule"           # this updates HEAD

Of course as usual you should be able to do "git commit -a" to skip "git update-index". One has to remember that "git update-index submodule" and "git commit submodule" uses HEAD version of submodule, not the working area version.

There was an idea to update superproject index not to HEAD version but to some specified branch version.

5. Extended sha1 syntax for submodules

For [almost] all commands the commit-in-tree should be viewed as tree-ish, for example in HEAD:submodule/subsubdir (is a tree), or HEAD:submodule/subsubdir/submfile (is a blob).

Currently a suffix ':' followed by a path names the blob or tree (or commit) at the given path in the tree-ish object named by the part before the colon. You cannot currently use it recirsively, i.e. use <tree-ish>:<path> to refer to tree (or commit), and use ':' after that, e.g. <tree-ish>:<path>:<subpath>... well, currently this has not much sense, as you can (and have to) use '/' as a separator.

There was proposal to use '//' as a way to force commit object in the tree to be treated as commit-ish, not as a tree, so you can apply all the extended sha1 machinery suitable for commits like ^, ^n, ~n and also probably ^@, but perhaps not @{n}. Then making ':' resursive would be useful, for example:

  HEAD^:submodule//~2:subsubdir/submfile

lördag 02 december 2006 21:16 skrev Jakub Narebski:

A nasty problem with separate repositories for submodules is that when you screw up and git complains about everything you try do do, you previously could do rm -rf *; git reset --hard and retry whatever you were trying to do. With separate repositories your submodules will be resting in /dev/null, unless you're very, very careful.

Dnia niedziela 3. grudnia 2006 02:24, Robin Rosenberg napisał:

Actually, rm -rf * is not needed for "git reset --hard" or "git checkout -f" to succeed.

söndag 03 december 2006 02:31 skrev Jakub Narebski:

True, but git reset --hard isn't always enough and rm -rf * is the good ol' way of resetting things. Typically this comes from make being upset (or too content) with something.

Robin Rosenberg wrote:

$ git clean -d -x -q $ git reset --hard

(or vice versa) then.

Besides, "rm -rf *" should not remove hidden files and hidden directories, including .git directory. And you should take great care with "rm -rf .*" if it doesn't follow '..'

Robin Rosenberg wrote:

The solution to this concern could be having GIT_DIR for submodule outside it's working area, for example somewhere in GIT_DIR of the supermodule, and use either symlink or (to be coded) .gitlink symbolic reference to GIT_DIR file. Disadvantage of that is that it moves troubles with moving subproject (although there are no troubles with simple subproject directory renaming) from alternates file to GIT_DIR link representation in submodule.

As Linus said, there are advantages to having submodule repository use separate object database (clone and other operation scaling, index size), and I think they outweight the troubles with moving/renaming the directory submodule resides in.

P.S. I think that the problem with bad performance of too large index is similar to the problems filesystems have with directories with large number of files; some filesystems solved this problem.