[RFD PATCH 00/32] subtree clone v2

This is a follow-up from the subtree clone proof of concept [1] I posted a few weeks ago. I think it's getting closer to an acceptable design. Hence the purpose of this post: to ask for opinions about the design issues I'm facing.

The good news is that tree rewrite/replace has gone. The repo now is perfectly "normal". Git client has to be modified to live peacefully within a narrow tree. How much modification is still a question ahead.

Other things from the previous series are pretty much unchanged: single narrow tree, only send necessary trees, can be used together with shallow clone, can't be fetch source.

A new thing is the index is now narrowed down, because I don't have all trees to fully populate it, and tree rewrite mechanism is now gone. One item for RFD.

Another major thing (you guys are going to hate me) is merge could not always be done locally. So I introduce "trivial 3-way remote merge". RFD material (any other aproaches?). More details in commit messages.

Is there any other full-tree operations, like merge, that I should pay attention to? What commands can be troublesome?

Last note, please don't look too closely. The code is full of bugs :-)

Patches 1..7
  add const to ce_write()
  cache-tree: abstract out write_sha1_file from cache_tree_update()
  cache-tree: ignore CE_REMOVE entries in verify_cache()
  move do_compress() from pack-objects.c to pack-write.c
  pack-write: add functions for creating simple packs
  tree.c: Add {set,clear}_tree_marks
  tree.c: find_subtree() to search for a tree

Helper patches. You can skip these if you are only interested in the narrow ideas.

Patches 8..14
  Add $GIT_DIR/narrow check
  index: make narrow index incompatible with older git
  rev-list: support traversing in narrow repository mode
  rev-list: support --narrow-tree
  pack-objects: support --narrow-tree
  upload-pack: support narrow-tree capability
  fetch-pack: support --narrow-tree

Narrow clone. traverse_commit_list() does not change much since the last series.

Patches 15..19
  unpack_trees: only unpack $GIT_DIR/narrow subtree in narrow
    repository
  cache-tree: only cache tree within narrow area
  tree-diff: add narrow versions of diff_{root_,}tree_sha1
  log-tree: use narrow version of diff_tree_sha1
  clone: support --narrow option

Client support so that you can check files out, diff them... This is WIP. Basically if you stay inside narrow tree, you'd be safe :-) Elijah may want to reuse some of these code in his sparse clone, if he can extend it to support multiple narrow trees, I think.

Patches 20..25
  narrow-tree: add join_narrow_tree to do tree fixup for commits
  commit: add narrow's commit_tree version
  commit: use commit_narrow_tree() to support narrow repo
  commit-tree: require --narrow-base in narrow repo
  merge: refuse to merge if narrow bases are different
  merge: prepare commit properly in narrow mode

Commit part, how to use narrow index and make proper commits. This is where merge issue arises. Because a merge can have many parents, which parent can be used as a base to create new commits?

Patches 26..30
  Add upload-narrow-base command
  rev-list: traverse some more trees to make upload-narrow-base happy
  narrow-tree: add oldest_narrow_base()
  Add command fetch-narrow-base
  merge: support merging when narrow bases are different

Remote merge part.

Split a merge operation into two parts, the real merge will be done within narrow tree. Conflicts can happen and be resolved in the narrow index, locally.

Everything outside narrow tree will be merged (trivially) by server. Then server sends the base tree back, so join_narrow_tree() in patch 20 can be used to create proper commit.

Server can disable this remote merge feature, which means users are forced to do rebase/fast-forward. Not too bad.

Patches 31..32
  send-pack: do not use thin pack in narrow mode
  daemon: support upload-narrow-base

Misc stuff..

[1] http://mid.gmane.org/1280593105-22015-1-git-send-email-pclouds@gmail.com

 Makefile                     |    4 +
 builtin.h                    |    2 +
 builtin/clone.c              |   15 +++-
 builtin/commit-tree.c        |   20 ++++-
 builtin/commit.c             |   10 ++-
 builtin/fetch-narrow-base.c  |   89 +++++++++++++++++
 builtin/fetch-pack.c         |   11 ++
 builtin/merge.c              |   45 +++++++++-
 builtin/pack-objects.c       |   33 +++----
 builtin/send-pack.c          |    4 +
 builtin/upload-narrow-base.c |  215 ++++++++++++++++++++++++++++++++++++++++++
 cache-tree.c                 |   37 ++++++--
 cache-tree.h                 |    3 +
 cache.h                      |    4 +
 commit.c                     |   21 ++++
 commit.h                     |    5 +
 daemon.c                     |    7 ++
 diff.h                       |    5 +
 environment.c                |    2 +
 git.c                        |    2 +
 list-objects.c               |   91 +++++++++++++++++-
 log-tree.c                   |   23 ++++-
 narrow-tree.c                |  200 +++++++++++++++++++++++++++++++++++++++
 narrow-tree.h                |    9 ++
 pack-write.c                 |  112 ++++++++++++++++++++++
 pack.h                       |   18 ++++
 read-cache.c                 |   37 ++++++-
 revision.c                   |    5 +
 revision.h                   |    4 +-
 t/t1013-read-tree-narrow.sh  |   72 ++++++++++++++
 t/t6060-narrow-tree.sh       |   28 ++++++
 t/t6061-rev-list-narrow.sh   |  185 ++++++++++++++++++++++++++++++++++++
 tree-diff.c                  |   74 ++++++++++++++
 tree.c                       |   79 +++++++++++++++
 tree.h                       |    4 +
 unpack-trees.c               |   70 ++++++++++++++-
 upload-pack.c                |   31 ++++++-
 37 files changed, 1528 insertions(+), 48 deletions(-)
 create mode 100644 builtin/fetch-narrow-base.c
 create mode 100644 builtin/upload-narrow-base.c
 create mode 100644 narrow-tree.c
 create mode 100644 narrow-tree.h
 create mode 100755 t/t1013-read-tree-narrow.sh
 create mode 100755 t/t6060-narrow-tree.sh
 create mode 100755 t/t6061-rev-list-narrow.sh