[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... ;-)

-- 
Martin Waitz

Robin Rosenberg wrote:

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

quoted

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.

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. 

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.
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Martin Waitz [off-list ref] wrote:

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.

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.
 

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.

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.  :)
 

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.

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... :-)

-- 

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.

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

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

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

(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?)

-- 
				Petr "Pasky" Baudis
Stuff: http://pasky.or.cz/
The meaning of Stonehenge in Traflamadorian, when viewed from above, is:
"Replacement part being rushed with all possible speed."

Martin Waitz wrote:

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.

Erm... isn't a _type_ of tree entry saved somewhere? Currently it can
be only 'tree' or 'blob', what you do is adding 'commit' (then permissions
are permissions of top tree of module, of course).

By the way, in todo branch, in Subpro.txt, there is talk about adding
link to submodule trees in _commit object_... well link to submodule tree
or commit, with the "mount point".
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

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

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

quoted

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.

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. 

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

-- 
Jakub Narebski

hoi :)

On Mon, Nov 20, 2006 at 11:16:45PM +0100, Jakub Narebski wrote:

Martin Waitz wrote:

quoted

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.

Erm... isn't a _type_ of tree entry saved somewhere? Currently it can
be only 'tree' or 'blob', what you do is adding 'commit' (then permissions
are permissions of top tree of module, of course).

It is saved inside the object which is being refered to.
Right now tree objects are also identified by their file mode and not
by the type of object which is referenced.

By the way, in todo branch, in Subpro.txt, there is talk about adding
link to submodule trees in _commit object_... well link to submodule tree
or commit, with the "mount point".

But isn't the submodule really part of the tree?
Right now the commit is used to construct the history of one project.
And a submodule is not part of the history of the parent, it is part
of the parent's tree.

-- 
Martin Waitz

Robin Rosenberg wrote:

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

quoted

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

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.

$ 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 '..'
-- 
Jakub Narebski

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


-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

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

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.

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. 

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

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

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.