Merge branch 'jc/cache-tree' into jc/dirwalk-n-cache-tree
authorJunio C Hamano <junkio@cox.net>
Sat, 20 May 2006 07:56:11 +0000 (00:56 -0700)
committerJunio C Hamano <junkio@cox.net>
Sat, 20 May 2006 07:56:11 +0000 (00:56 -0700)
* jc/cache-tree: (24 commits)
  Fix crash when reading the empty tree
  fsck-objects: do not segfault on missing tree in cache-tree
  cache-tree: a bit more debugging support.
  read-tree: invalidate cache-tree entry when a new index entry is added.
  Fix test-dump-cache-tree in one-tree disappeared case.
  fsck-objects: mark objects reachable from cache-tree
  cache-tree: replace a sscanf() by two strtol() calls
  cache-tree.c: typefix
  test-dump-cache-tree: validate the cached data as well.
  cache_tree_update: give an option to update cache-tree only.
  read-tree: teach 1-way merege and plain read to prime cache-tree.
  read-tree: teach 1 and 2 way merges about cache-tree.
  update-index: when --unresolve, smudge the relevant cache-tree entries.
  test-dump-cache-tree: report number of subtrees.
  cache-tree: sort the subtree entries.
  Teach fsck-objects about cache-tree.
  index: make the index file format extensible.
  cache-tree: protect against "git prune".
  Add test-dump-cache-tree
  Use cache-tree in update-index.
  ...

1  2 
Makefile
apply.c
cache.h
checkout-index.c
read-cache.c
read-tree.c
update-index.c

diff --combined Makefile
+++ b/Makefile
@@@ -28,8 -28,8 +28,8 @@@ all
  #
  # Define NO_SETENV if you don't have setenv in the C library.
  #
 -# Define USE_SYMLINK_HEAD if you want .git/HEAD to be a symbolic link.
 -# Don't enable it on Windows.
 +# Define NO_SYMLINK_HEAD if you never want .git/HEAD to be a symbolic link.
 +# Enable it on Windows.  By default, symrefs are still used.
  #
  # Define PPC_SHA1 environment variable when running make to make use of
  # a bundled SHA1 routine optimized for PowerPC.
@@@ -115,24 -115,23 +115,24 @@@ SPARSE_FLAGS = -D__BIG_ENDIAN__ -D__pow
  SCRIPT_SH = \
        git-add.sh git-bisect.sh git-branch.sh git-checkout.sh \
        git-cherry.sh git-clean.sh git-clone.sh git-commit.sh \
 -      git-count-objects.sh git-diff.sh git-fetch.sh \
 +      git-fetch.sh \
        git-format-patch.sh git-ls-remote.sh \
        git-merge-one-file.sh git-parse-remote.sh \
 -      git-prune.sh git-pull.sh git-push.sh git-rebase.sh \
 +      git-prune.sh git-pull.sh git-rebase.sh \
        git-repack.sh git-request-pull.sh git-reset.sh \
        git-resolve.sh git-revert.sh git-rm.sh git-sh-setup.sh \
 -      git-tag.sh git-verify-tag.sh git-whatchanged.sh \
 +      git-tag.sh git-verify-tag.sh \
        git-applymbox.sh git-applypatch.sh git-am.sh \
        git-merge.sh git-merge-stupid.sh git-merge-octopus.sh \
 -      git-merge-resolve.sh git-merge-ours.sh git-grep.sh \
 -      git-lost-found.sh
 +      git-merge-resolve.sh git-merge-ours.sh \
 +      git-lost-found.sh git-quiltimport.sh
  
  SCRIPT_PERL = \
        git-archimport.perl git-cvsimport.perl git-relink.perl \
        git-shortlog.perl git-fmt-merge-msg.perl git-rerere.perl \
        git-annotate.perl git-cvsserver.perl \
 -      git-svnimport.perl git-mv.perl git-cvsexportcommit.perl
 +      git-svnimport.perl git-mv.perl git-cvsexportcommit.perl \
 +      git-send-email.perl
  
  SCRIPT_PYTHON = \
        git-merge-recursive.py
  SCRIPTS = $(patsubst %.sh,%,$(SCRIPT_SH)) \
          $(patsubst %.perl,%,$(SCRIPT_PERL)) \
          $(patsubst %.py,%,$(SCRIPT_PYTHON)) \
 -        git-cherry-pick git-show git-status
 +        git-cherry-pick git-status
  
  # The ones that do not have to link with lcrypto, lz nor xdiff.
  SIMPLE_PROGRAMS = \
@@@ -154,24 -153,21 +154,24 @@@ PROGRAMS = 
        git-convert-objects$X git-diff-files$X \
        git-diff-index$X git-diff-stages$X \
        git-diff-tree$X git-fetch-pack$X git-fsck-objects$X \
 -      git-hash-object$X git-index-pack$X git-init-db$X git-local-fetch$X \
 +      git-hash-object$X git-index-pack$X git-local-fetch$X \
        git-ls-files$X git-ls-tree$X git-mailinfo$X git-merge-base$X \
        git-merge-index$X git-mktag$X git-mktree$X git-pack-objects$X git-patch-id$X \
        git-peek-remote$X git-prune-packed$X git-read-tree$X \
 -      git-receive-pack$X git-rev-list$X git-rev-parse$X \
 +      git-receive-pack$X git-rev-parse$X \
        git-send-pack$X git-show-branch$X git-shell$X \
        git-show-index$X git-ssh-fetch$X \
        git-ssh-upload$X git-tar-tree$X git-unpack-file$X \
        git-unpack-objects$X git-update-index$X git-update-server-info$X \
        git-upload-pack$X git-verify-pack$X git-write-tree$X \
 -      git-update-ref$X git-symbolic-ref$X git-check-ref-format$X \
 +      git-update-ref$X git-symbolic-ref$X \
        git-name-rev$X git-pack-redundant$X git-repo-config$X git-var$X \
        git-describe$X git-merge-tree$X git-blame$X git-imap-send$X
  
 -BUILT_INS = git-log$X
 +BUILT_INS = git-log$X git-whatchanged$X git-show$X \
 +      git-count-objects$X git-diff$X git-push$X \
 +      git-grep$X git-rev-list$X git-check-ref-format$X \
 +      git-init-db$X
  
  # what 'all' will build and 'install' will install, in gitexecdir
  ALL_PROGRAMS = $(PROGRAMS) $(SIMPLE_PROGRAMS) $(SCRIPTS)
@@@ -208,7 -204,7 +208,7 @@@ DIFF_OBJS = 
        diffcore-delta.o log-tree.o
  
  LIB_OBJS = \
-       blob.o commit.o connect.o csum-file.o base85.o \
 -      blob.o commit.o connect.o csum-file.o cache-tree.o \
++      blob.o commit.o connect.o csum-file.o cache-tree.o base85.o \
        date.o diff-delta.o entry.o exec_cmd.o ident.o index.o \
        object.o pack-check.o patch-delta.o path.o pkt-line.o \
        quote.o read-cache.o refs.o run-command.o \
        $(DIFF_OBJS)
  
  BUILTIN_OBJS = \
 -      builtin-log.o builtin-help.o
 +      builtin-log.o builtin-help.o builtin-count.o builtin-diff.o builtin-push.o \
 +      builtin-grep.o builtin-rev-list.o builtin-check-ref-format.o \
 +      builtin-init-db.o
  
  GITLIBS = $(LIB_FILE) $(XDIFF_LIB)
  LIBS = $(GITLIBS) -lz
@@@ -269,7 -263,6 +269,7 @@@ ifeq ($(uname_O),Cygwin
        NO_D_TYPE_IN_DIRENT = YesPlease
        NO_D_INO_IN_DIRENT = YesPlease
        NO_STRCASESTR = YesPlease
 +      NO_SYMLINK_HEAD = YesPlease
        NEEDS_LIBICONV = YesPlease
        # There are conflicting reports about this.
        # On some boxes NO_MMAP is needed, and not so elsewhere.
@@@ -290,9 -283,7 +290,9 @@@ ifeq ($(uname_S),OpenBSD
        ALL_LDFLAGS += -L/usr/local/lib
  endif
  ifeq ($(uname_S),NetBSD)
 -      NEEDS_LIBICONV = YesPlease
 +      ifeq ($(shell expr "$(uname_R)" : '[01]\.'),2)
 +              NEEDS_LIBICONV = YesPlease
 +      endif
        ALL_CFLAGS += -I/usr/pkg/include
        ALL_LDFLAGS += -L/usr/pkg/lib -Wl,-rpath,/usr/pkg/lib
  endif
@@@ -326,6 -317,10 +326,6 @@@ els
        endif
  endif
  
 -ifdef WITH_SEND_EMAIL
 -      SCRIPT_PERL += git-send-email.perl
 -endif
 -
  ifndef NO_CURL
        ifdef CURLDIR
                # This is still problematic -- gcc does not always want -R.
@@@ -391,9 -386,6 +391,9 @@@ endi
  ifdef NO_D_INO_IN_DIRENT
        ALL_CFLAGS += -DNO_D_INO_IN_DIRENT
  endif
 +ifdef NO_SYMLINK_HEAD
 +      ALL_CFLAGS += -DNO_SYMLINK_HEAD
 +endif
  ifdef NO_STRCASESTR
        COMPAT_CFLAGS += -DNO_STRCASESTR
        COMPAT_OBJS += compat/strcasestr.o
@@@ -461,7 -453,6 +461,7 @@@ PYTHON_PATH_SQ = $(subst ','\'',$(PYTHO
  GIT_PYTHON_DIR_SQ = $(subst ','\'',$(GIT_PYTHON_DIR))
  
  ALL_CFLAGS += -DSHA1_HEADER='$(SHA1_HEADER_SQ)' $(COMPAT_CFLAGS)
 +ALL_CFLAGS += -DDEFAULT_GIT_TEMPLATE_DIR='"$(template_dir_SQ)"'
  LIB_OBJS += $(COMPAT_OBJS)
  export prefix TAR INSTALL DESTDIR SHELL_PATH template_dir
  ### Build rules
@@@ -514,6 -505,9 +514,6 @@@ $(patsubst %.py,%,$(SCRIPT_PYTHON)) : 
  git-cherry-pick: git-revert
        cp $< $@
  
 -git-show: git-whatchanged
 -      cp $< $@
 -
  git-status: git-commit
        cp $< $@
  
@@@ -568,6 -562,14 +568,6 @@@ git-http-push$X: revision.o http.o http
        $(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) \
                $(LIBS) $(CURL_LIBCURL) $(EXPAT_LIBEXPAT)
  
 -git-rev-list$X: rev-list.o $(LIB_FILE)
 -      $(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) \
 -              $(LIBS) $(OPENSSL_LIBSSL)
 -
 -init-db.o: init-db.c
 -      $(CC) -c $(ALL_CFLAGS) \
 -              -DDEFAULT_GIT_TEMPLATE_DIR='"$(template_dir_SQ)"' $*.c
 -
  $(LIB_OBJS) $(BUILTIN_OBJS): $(LIB_H)
  $(patsubst git-%$X,%.o,$(PROGRAMS)): $(GITLIBS)
  $(DIFF_OBJS): diffcore.h
@@@ -607,8 -609,11 +607,11 @@@ test-date$X: test-date.c date.o ctype.
        $(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) test-date.c date.o ctype.o
  
  test-delta$X: test-delta.c diff-delta.o patch-delta.o
 -      $(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $^ -lz
 +      $(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $^
  
+ test-dump-cache-tree$X: dump-cache-tree.o $(GITLIBS)
+       $(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) $(LIBS)
  check:
        for i in *.c; do sparse $(ALL_CFLAGS) $(SPARSE_FLAGS) $$i || exit; done
  
@@@ -651,25 -656,6 +654,25 @@@ dist: git.spec git-tar-tre
  rpm: dist
        $(RPMBUILD) -ta $(GIT_TARNAME).tar.gz
  
 +htmldocs = git-htmldocs-$(GIT_VERSION)
 +manpages = git-manpages-$(GIT_VERSION)
 +dist-doc:
 +      rm -fr .doc-tmp-dir
 +      mkdir .doc-tmp-dir
 +      $(MAKE) -C Documentation WEBDOC_DEST=../.doc-tmp-dir install-webdoc
 +      cd .doc-tmp-dir && $(TAR) cf ../$(htmldocs).tar .
 +      gzip -n -9 -f $(htmldocs).tar
 +      :
 +      rm -fr .doc-tmp-dir
 +      mkdir .doc-tmp-dir .doc-tmp-dir/man1 .doc-tmp-dir/man7
 +      $(MAKE) -C Documentation DESTDIR=. \
 +              man1=../.doc-tmp-dir/man1 \
 +              man7=../.doc-tmp-dir/man7 \
 +              install
 +      cd .doc-tmp-dir && $(TAR) cf ../$(manpages).tar .
 +      gzip -n -9 -f $(manpages).tar
 +      rm -fr .doc-tmp-dir
 +
  ### Cleaning rules
  
  clean:
                $(LIB_FILE) $(XDIFF_LIB)
        rm -f $(ALL_PROGRAMS) $(BUILT_INS) git$X
        rm -f *.spec *.pyc *.pyo */*.pyc */*.pyo common-cmds.h TAGS tags
 -      rm -rf $(GIT_TARNAME)
 +      rm -rf $(GIT_TARNAME) .doc-tmp-dir
        rm -f $(GIT_TARNAME).tar.gz git-core_$(GIT_VERSION)-*.tar.gz
 +      rm -f $(htmldocs).tar $(manpages).tar
        $(MAKE) -C Documentation/ clean
        $(MAKE) -C templates clean
        $(MAKE) -C t/ clean
diff --combined apply.c
+++ b/apply.c
@@@ -8,27 -8,23 +8,28 @@@
   */
  #include <fnmatch.h>
  #include "cache.h"
+ #include "cache-tree.h"
  #include "quote.h"
  #include "blob.h"
 +#include "delta.h"
  
  //  --check turns on checking that the working tree matches the
  //    files that are being modified, but doesn't apply the patch
  //  --stat does just a diffstat, and doesn't actually apply
  //  --numstat does numeric diffstat, and doesn't actually apply
  //  --index-info shows the old and new index info for paths if available.
 +//  --index updates the cache as well.
 +//  --cached updates only the cache without ever touching the working tree.
  //
  static const char *prefix;
  static int prefix_length = -1;
 +static int newfd = -1;
  
  static int p_value = 1;
  static int allow_binary_replacement = 0;
  static int check_index = 0;
  static int write_index = 0;
 +static int cached = 0;
  static int diffstat = 0;
  static int numstat = 0;
  static int summary = 0;
@@@ -39,7 -35,7 +40,7 @@@ static int show_index_info = 0
  static int line_termination = '\n';
  static unsigned long p_context = -1;
  static const char apply_usage[] =
 -"git-apply [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--no-add] [--index-info] [--allow-binary-replacement] [-z] [-pNUM] [-CNUM] [--whitespace=<nowarn|warn|error|error-all|strip>] <patch>...";
 +"git-apply [--stat] [--numstat] [--summary] [--check] [--index] [--cached] [--apply] [--no-add] [--index-info] [--allow-binary-replacement] [-z] [-pNUM] [-CNUM] [--whitespace=<nowarn|warn|error|error-all|strip>] <patch>...";
  
  static enum whitespace_eol {
        nowarn_whitespace,
@@@ -118,9 -114,6 +119,9 @@@ struct patch 
        char *new_name, *old_name, *def_name;
        unsigned int old_mode, new_mode;
        int is_rename, is_copy, is_new, is_delete, is_binary;
 +#define BINARY_DELTA_DEFLATED 1
 +#define BINARY_LITERAL_DEFLATED 2
 +      unsigned long deflate_origlen;
        int lines_added, lines_deleted;
        int score;
        struct fragment *fragments;
@@@ -974,88 -967,6 +975,88 @@@ static inline int metadata_changes(stru
                 patch->old_mode != patch->new_mode);
  }
  
 +static int parse_binary(char *buffer, unsigned long size, struct patch *patch)
 +{
 +      /* We have read "GIT binary patch\n"; what follows is a line
 +       * that says the patch method (currently, either "deflated
 +       * literal" or "deflated delta") and the length of data before
 +       * deflating; a sequence of 'length-byte' followed by base-85
 +       * encoded data follows.
 +       *
 +       * Each 5-byte sequence of base-85 encodes up to 4 bytes,
 +       * and we would limit the patch line to 66 characters,
 +       * so one line can fit up to 13 groups that would decode
 +       * to 52 bytes max.  The length byte 'A'-'Z' corresponds
 +       * to 1-26 bytes, and 'a'-'z' corresponds to 27-52 bytes.
 +       * The end of binary is signalled with an empty line.
 +       */
 +      int llen, used;
 +      struct fragment *fragment;
 +      char *data = NULL;
 +
 +      patch->fragments = fragment = xcalloc(1, sizeof(*fragment));
 +
 +      /* Grab the type of patch */
 +      llen = linelen(buffer, size);
 +      used = llen;
 +      linenr++;
 +
 +      if (!strncmp(buffer, "delta ", 6)) {
 +              patch->is_binary = BINARY_DELTA_DEFLATED;
 +              patch->deflate_origlen = strtoul(buffer + 6, NULL, 10);
 +      }
 +      else if (!strncmp(buffer, "literal ", 8)) {
 +              patch->is_binary = BINARY_LITERAL_DEFLATED;
 +              patch->deflate_origlen = strtoul(buffer + 8, NULL, 10);
 +      }
 +      else
 +              return error("unrecognized binary patch at line %d: %.*s",
 +                           linenr-1, llen-1, buffer);
 +      buffer += llen;
 +      while (1) {
 +              int byte_length, max_byte_length, newsize;
 +              llen = linelen(buffer, size);
 +              used += llen;
 +              linenr++;
 +              if (llen == 1)
 +                      break;
 +              /* Minimum line is "A00000\n" which is 7-byte long,
 +               * and the line length must be multiple of 5 plus 2.
 +               */
 +              if ((llen < 7) || (llen-2) % 5)
 +                      goto corrupt;
 +              max_byte_length = (llen - 2) / 5 * 4;
 +              byte_length = *buffer;
 +              if ('A' <= byte_length && byte_length <= 'Z')
 +                      byte_length = byte_length - 'A' + 1;
 +              else if ('a' <= byte_length && byte_length <= 'z')
 +                      byte_length = byte_length - 'a' + 27;
 +              else
 +                      goto corrupt;
 +              /* if the input length was not multiple of 4, we would
 +               * have filler at the end but the filler should never
 +               * exceed 3 bytes
 +               */
 +              if (max_byte_length < byte_length ||
 +                  byte_length <= max_byte_length - 4)
 +                      goto corrupt;
 +              newsize = fragment->size + byte_length;
 +              data = xrealloc(data, newsize);
 +              if (decode_85(data + fragment->size,
 +                            buffer + 1,
 +                            byte_length))
 +                      goto corrupt;
 +              fragment->size = newsize;
 +              buffer += llen;
 +              size -= llen;
 +      }
 +      fragment->patch = data;
 +      return used;
 + corrupt:
 +      return error("corrupt binary patch at line %d: %.*s",
 +                   linenr-1, llen-1, buffer);
 +}
 +
  static int parse_chunk(char *buffer, unsigned long size, struct patch *patch)
  {
        int hdrsize, patchsize;
                        "Files ",
                        NULL,
                };
 +              static const char git_binary[] = "GIT binary patch\n";
                int i;
                int hd = hdrsize + offset;
                unsigned long llen = linelen(buffer + hd, size - hd);
  
 -              if (!memcmp(" differ\n", buffer + hd + llen - 8, 8))
 +              if (llen == sizeof(git_binary) - 1 &&
 +                  !memcmp(git_binary, buffer + hd, llen)) {
 +                      int used;
 +                      linenr++;
 +                      used = parse_binary(buffer + hd + llen,
 +                                          size - hd - llen, patch);
 +                      if (used)
 +                              patchsize = used + llen;
 +                      else
 +                              patchsize = 0;
 +              }
 +              else if (!memcmp(" differ\n", buffer + hd + llen - 8, 8)) {
                        for (i = 0; binhdr[i]; i++) {
                                int len = strlen(binhdr[i]);
                                if (len < size - hd &&
                                    !memcmp(binhdr[i], buffer + hd, len)) {
 +                                      linenr++;
                                        patch->is_binary = 1;
 +                                      patchsize = llen;
                                        break;
                                }
                        }
 +              }
  
                /* Empty patch cannot be applied if:
                 * - it is a binary patch and we do not do binary_replace, or
@@@ -1450,150 -1346,76 +1451,150 @@@ static int apply_one_fragment(struct bu
        return offset;
  }
  
 -static int apply_fragments(struct buffer_desc *desc, struct patch *patch)
 +static char *inflate_it(const void *data, unsigned long size,
 +                      unsigned long inflated_size)
 +{
 +      z_stream stream;
 +      void *out;
 +      int st;
 +
 +      memset(&stream, 0, sizeof(stream));
 +
 +      stream.next_in = (unsigned char *)data;
 +      stream.avail_in = size;
 +      stream.next_out = out = xmalloc(inflated_size);
 +      stream.avail_out = inflated_size;
 +      inflateInit(&stream);
 +      st = inflate(&stream, Z_FINISH);
 +      if ((st != Z_STREAM_END) || stream.total_out != inflated_size) {
 +              free(out);
 +              return NULL;
 +      }
 +      return out;
 +}
 +
 +static int apply_binary_fragment(struct buffer_desc *desc, struct patch *patch)
 +{
 +      unsigned long dst_size;
 +      struct fragment *fragment = patch->fragments;
 +      void *data;
 +      void *result;
 +
 +      data = inflate_it(fragment->patch, fragment->size,
 +                        patch->deflate_origlen);
 +      if (!data)
 +              return error("corrupt patch data");
 +      switch (patch->is_binary) {
 +      case BINARY_DELTA_DEFLATED:
 +              result = patch_delta(desc->buffer, desc->size,
 +                                   data,
 +                                   patch->deflate_origlen,
 +                                   &dst_size);
 +              free(desc->buffer);
 +              desc->buffer = result;
 +              free(data);
 +              break;
 +      case BINARY_LITERAL_DEFLATED:
 +              free(desc->buffer);
 +              desc->buffer = data;
 +              dst_size = patch->deflate_origlen;
 +              break;
 +      }
 +      if (!desc->buffer)
 +              return -1;
 +      desc->size = desc->alloc = dst_size;
 +      return 0;
 +}
 +
 +static int apply_binary(struct buffer_desc *desc, struct patch *patch)
  {
 -      struct fragment *frag = patch->fragments;
        const char *name = patch->old_name ? patch->old_name : patch->new_name;
 +      unsigned char sha1[20];
 +      unsigned char hdr[50];
 +      int hdrlen;
  
 -      if (patch->is_binary) {
 -              unsigned char sha1[20];
 +      if (!allow_binary_replacement)
 +              return error("cannot apply binary patch to '%s' "
 +                           "without --allow-binary-replacement",
 +                           name);
  
 -              if (!allow_binary_replacement)
 -                      return error("cannot apply binary patch to '%s' "
 -                                   "without --allow-binary-replacement",
 -                                   name);
 +      /* For safety, we require patch index line to contain
 +       * full 40-byte textual SHA1 for old and new, at least for now.
 +       */
 +      if (strlen(patch->old_sha1_prefix) != 40 ||
 +          strlen(patch->new_sha1_prefix) != 40 ||
 +          get_sha1_hex(patch->old_sha1_prefix, sha1) ||
 +          get_sha1_hex(patch->new_sha1_prefix, sha1))
 +              return error("cannot apply binary patch to '%s' "
 +                           "without full index line", name);
  
 -              /* For safety, we require patch index line to contain
 -               * full 40-byte textual SHA1 for old and new, at least for now.
 +      if (patch->old_name) {
 +              /* See if the old one matches what the patch
 +               * applies to.
                 */
 -              if (strlen(patch->old_sha1_prefix) != 40 ||
 -                  strlen(patch->new_sha1_prefix) != 40 ||
 -                  get_sha1_hex(patch->old_sha1_prefix, sha1) ||
 -                  get_sha1_hex(patch->new_sha1_prefix, sha1))
 -                      return error("cannot apply binary patch to '%s' "
 -                                   "without full index line", name);
 -
 -              if (patch->old_name) {
 -                      unsigned char hdr[50];
 -                      int hdrlen;
 -
 -                      /* See if the old one matches what the patch
 -                       * applies to.
 -                       */
 -                      write_sha1_file_prepare(desc->buffer, desc->size,
 -                                              blob_type, sha1, hdr, &hdrlen);
 -                      if (strcmp(sha1_to_hex(sha1), patch->old_sha1_prefix))
 -                              return error("the patch applies to '%s' (%s), "
 -                                           "which does not match the "
 -                                           "current contents.",
 -                                           name, sha1_to_hex(sha1));
 -              }
 -              else {
 -                      /* Otherwise, the old one must be empty. */
 -                      if (desc->size)
 -                              return error("the patch applies to an empty "
 -                                           "'%s' but it is not empty", name);
 -              }
 +              write_sha1_file_prepare(desc->buffer, desc->size,
 +                                      blob_type, sha1, hdr, &hdrlen);
 +              if (strcmp(sha1_to_hex(sha1), patch->old_sha1_prefix))
 +                      return error("the patch applies to '%s' (%s), "
 +                                   "which does not match the "
 +                                   "current contents.",
 +                                   name, sha1_to_hex(sha1));
 +      }
 +      else {
 +              /* Otherwise, the old one must be empty. */
 +              if (desc->size)
 +                      return error("the patch applies to an empty "
 +                                   "'%s' but it is not empty", name);
 +      }
 +
 +      get_sha1_hex(patch->new_sha1_prefix, sha1);
 +      if (!memcmp(sha1, null_sha1, 20)) {
 +              free(desc->buffer);
 +              desc->alloc = desc->size = 0;
 +              desc->buffer = NULL;
 +              return 0; /* deletion patch */
 +      }
 +
 +      if (has_sha1_file(sha1)) {
 +              /* We already have the postimage */
 +              char type[10];
 +              unsigned long size;
  
 -              /* For now, we do not record post-image data in the patch,
 -               * and require the object already present in the recipient's
 -               * object database.
 +              free(desc->buffer);
 +              desc->buffer = read_sha1_file(sha1, type, &size);
 +              if (!desc->buffer)
 +                      return error("the necessary postimage %s for "
 +                                   "'%s' cannot be read",
 +                                   patch->new_sha1_prefix, name);
 +              desc->alloc = desc->size = size;
 +      }
 +      else {
 +              /* We have verified desc matches the preimage;
 +               * apply the patch data to it, which is stored
 +               * in the patch->fragments->{patch,size}.
                 */
 -              if (desc->buffer) {
 -                      free(desc->buffer);
 -                      desc->alloc = desc->size = 0;
 -              }
 -              get_sha1_hex(patch->new_sha1_prefix, sha1);
 -
 -              if (memcmp(sha1, null_sha1, 20)) {
 -                      char type[10];
 -                      unsigned long size;
 -
 -                      desc->buffer = read_sha1_file(sha1, type, &size);
 -                      if (!desc->buffer)
 -                              return error("the necessary postimage %s for "
 -                                           "'%s' does not exist",
 -                                           patch->new_sha1_prefix, name);
 -                      desc->alloc = desc->size = size;
 -              }
 +              if (apply_binary_fragment(desc, patch))
 +                      return error("binary patch does not apply to '%s'",
 +                                   name);
  
 -              return 0;
 +              /* verify that the result matches */
 +              write_sha1_file_prepare(desc->buffer, desc->size, blob_type,
 +                                      sha1, hdr, &hdrlen);
 +              if (strcmp(sha1_to_hex(sha1), patch->new_sha1_prefix))
 +                      return error("binary patch to '%s' creates incorrect result", name);
        }
  
 +      return 0;
 +}
 +
 +static int apply_fragments(struct buffer_desc *desc, struct patch *patch)
 +{
 +      struct fragment *frag = patch->fragments;
 +      const char *name = patch->old_name ? patch->old_name : patch->new_name;
 +
 +      if (patch->is_binary)
 +              return apply_binary(desc, patch);
 +
        while (frag) {
                if (apply_one_fragment(desc, frag) < 0)
                        return error("patch failed: %s:%ld",
        return 0;
  }
  
 -static int apply_data(struct patch *patch, struct stat *st)
 +static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *ce)
  {
        char *buf;
        unsigned long size, alloc;
        size = 0;
        alloc = 0;
        buf = NULL;
 -      if (patch->old_name) {
 +      if (cached) {
 +              if (ce) {
 +                      char type[20];
 +                      buf = read_sha1_file(ce->sha1, type, &size);
 +                      if (!buf)
 +                              return error("read of %s failed",
 +                                           patch->old_name);
 +                      alloc = size;
 +              }
 +      }
 +      else if (patch->old_name) {
                size = st->st_size;
                alloc = size + 8192;
                buf = xmalloc(alloc);
@@@ -1650,21 -1462,16 +1651,21 @@@ static int check_patch(struct patch *pa
        const char *old_name = patch->old_name;
        const char *new_name = patch->new_name;
        const char *name = old_name ? old_name : new_name;
 +      struct cache_entry *ce = NULL;
  
        if (old_name) {
 -              int changed;
 -              int stat_ret = lstat(old_name, &st);
 +              int changed = 0;
 +              int stat_ret = 0;
 +              unsigned st_mode = 0;
  
 +              if (!cached)
 +                      stat_ret = lstat(old_name, &st);
                if (check_index) {
                        int pos = cache_name_pos(old_name, strlen(old_name));
                        if (pos < 0)
                                return error("%s: does not exist in index",
                                             old_name);
 +                      ce = active_cache[pos];
                        if (stat_ret < 0) {
                                struct checkout costate;
                                if (errno != ENOENT)
                                costate.quiet = 0;
                                costate.not_new = 0;
                                costate.refresh_cache = 1;
 -                              if (checkout_entry(active_cache[pos],
 +                              if (checkout_entry(ce,
                                                   &costate,
                                                   NULL) ||
                                    lstat(old_name, &st))
                                        return -1;
                        }
 -
 -                      changed = ce_match_stat(active_cache[pos], &st, 1);
 +                      if (!cached)
 +                              changed = ce_match_stat(ce, &st, 1);
                        if (changed)
                                return error("%s: does not match index",
                                             old_name);
 +                      if (cached)
 +                              st_mode = ntohl(ce->ce_mode);
                }
                else if (stat_ret < 0)
                        return error("%s: %s", old_name, strerror(errno));
  
 +              if (!cached)
 +                      st_mode = ntohl(create_ce_mode(st.st_mode));
 +
                if (patch->is_new < 0)
                        patch->is_new = 0;
 -              st.st_mode = ntohl(create_ce_mode(st.st_mode));
                if (!patch->old_mode)
 -                      patch->old_mode = st.st_mode;
 -              if ((st.st_mode ^ patch->old_mode) & S_IFMT)
 +                      patch->old_mode = st_mode;
 +              if ((st_mode ^ patch->old_mode) & S_IFMT)
                        return error("%s: wrong type", old_name);
 -              if (st.st_mode != patch->old_mode)
 +              if (st_mode != patch->old_mode)
                        fprintf(stderr, "warning: %s has type %o, expected %o\n",
 -                              old_name, st.st_mode, patch->old_mode);
 +                              old_name, st_mode, patch->old_mode);
        }
  
        if (new_name && (patch->is_new | patch->is_rename | patch->is_copy)) {
                if (check_index && cache_name_pos(new_name, strlen(new_name)) >= 0)
                        return error("%s: already exists in index", new_name);
 -              if (!lstat(new_name, &st))
 -                      return error("%s: already exists in working directory", new_name);
 -              if (errno != ENOENT)
 -                      return error("%s: %s", new_name, strerror(errno));
 +              if (!cached) {
 +                      if (!lstat(new_name, &st))
 +                              return error("%s: already exists in working directory", new_name);
 +                      if (errno != ENOENT)
 +                              return error("%s: %s", new_name, strerror(errno));
 +              }
                if (!patch->new_mode) {
                        if (patch->is_new)
                                patch->new_mode = S_IFREG | 0644;
                        return error("new mode (%o) of %s does not match old mode (%o)%s%s",
                                patch->new_mode, new_name, patch->old_mode,
                                same ? "" : " of ", same ? "" : old_name);
 -      }       
 +      }
  
 -      if (apply_data(patch, &st) < 0)
 +      if (apply_data(patch, &st, ce) < 0)
                return error("%s: patch does not apply", name);
        return 0;
  }
@@@ -1802,7 -1603,7 +1803,7 @@@ static void numstat_patch_list(struct p
  {
        for ( ; patch; patch = patch->next) {
                const char *name;
 -              name = patch->old_name ? patch->old_name : patch->new_name;
 +              name = patch->new_name ? patch->new_name : patch->old_name;
                printf("%d\t%d\t", patch->lines_added, patch->lines_deleted);
                if (line_termination && quote_c_style(name, NULL, NULL, 0))
                        quote_c_style(name, NULL, stdout, 0);
@@@ -1917,9 -1718,9 +1918,10 @@@ static void remove_file(struct patch *p
        if (write_index) {
                if (remove_file_from_cache(patch->old_name) < 0)
                        die("unable to remove %s from index", patch->old_name);
+               cache_tree_invalidate_path(active_cache_tree, patch->old_name);
        }
 -      unlink(patch->old_name);
 +      if (!cached)
 +              unlink(patch->old_name);
  }
  
  static void add_index_file(const char *path, unsigned mode, void *buf, unsigned long size)
        memcpy(ce->name, path, namelen);
        ce->ce_mode = create_ce_mode(mode);
        ce->ce_flags = htons(namelen);
 -      if (lstat(path, &st) < 0)
 -              die("unable to stat newly created file %s", path);
 -      fill_stat_cache_info(ce, &st);
 +      if (!cached) {
 +              if (lstat(path, &st) < 0)
 +                      die("unable to stat newly created file %s", path);
 +              fill_stat_cache_info(ce, &st);
 +      }
        if (write_sha1_file(buf, size, blob_type, ce->sha1) < 0)
                die("unable to create backing store for newly created file %s", path);
        if (add_cache_entry(ce, ADD_CACHE_OK_TO_ADD) < 0)
@@@ -1977,8 -1776,6 +1979,8 @@@ static int try_create_file(const char *
   */
  static void create_one_file(char *path, unsigned mode, const char *buf, unsigned long size)
  {
 +      if (cached)
 +              return;
        if (!try_create_file(path, mode, buf, size))
                return;
  
@@@ -2018,8 -1815,9 +2020,9 @@@ static void create_file(struct patch *p
  
        if (!mode)
                mode = S_IFREG | 0644;
-       create_one_file(path, mode, buf, size); 
+       create_one_file(path, mode, buf, size);
        add_index_file(path, mode, buf, size);
+       cache_tree_invalidate_path(active_cache_tree, path);
  }
  
  static void write_out_one_result(struct patch *patch)
@@@ -2078,6 -1876,7 +2081,6 @@@ static int use_patch(struct patch *p
  
  static int apply_patch(int fd, const char *filename)
  {
 -      int newfd;
        unsigned long offset, size;
        char *buffer = read_patch_file(fd, &size);
        struct patch *list = NULL, **listp = &list;
                size -= nr;
        }
  
 -      newfd = -1;
        if (whitespace_error && (new_whitespace == error_on_whitespace))
                apply = 0;
  
        write_index = check_index && apply;
 -      if (write_index)
 +      if (write_index && newfd < 0)
                newfd = hold_index_file_for_update(&cache_file, get_index_file());
        if (check_index) {
                if (read_cache() < 0)
        if (apply)
                write_out_results(list, skipped_patch);
  
 -      if (write_index) {
 -              if (write_cache(newfd, active_cache, active_nr) ||
 -                  commit_index_file(&cache_file))
 -                      die("Unable to write new cachefile");
 -      }
 -
        if (show_index_info)
                show_index_list(list);
  
@@@ -2187,8 -1993,7 +2190,8 @@@ int main(int argc, char **argv
                        diffstat = 1;
                        continue;
                }
 -              if (!strcmp(arg, "--allow-binary-replacement")) {
 +              if (!strcmp(arg, "--allow-binary-replacement") ||
 +                  !strcmp(arg, "--binary")) {
                        allow_binary_replacement = 1;
                        continue;
                }
                        check_index = 1;
                        continue;
                }
 +              if (!strcmp(arg, "--cached")) {
 +                      check_index = 1;
 +                      cached = 1;
 +                      continue;
 +              }
                if (!strcmp(arg, "--apply")) {
                        apply = 1;
                        continue;
                                whitespace_error == 1 ? "" : "s",
                                whitespace_error == 1 ? "s" : "");
        }
 +
 +      if (write_index) {
 +              if (write_cache(newfd, active_cache, active_nr) ||
 +                  commit_index_file(&cache_file))
 +                      die("Unable to write new cachefile");
 +      }
 +
        return 0;
  }
diff --combined cache.h
+++ b/cache.h
@@@ -114,6 -114,7 +114,7 @@@ static inline unsigned int create_ce_mo
  
  extern struct cache_entry **active_cache;
  extern unsigned int active_nr, active_alloc, active_cache_changed;
+ extern struct cache_tree *active_cache_tree;
  
  #define GIT_DIR_ENVIRONMENT "GIT_DIR"
  #define DEFAULT_GIT_DIR_ENVIRONMENT ".git"
@@@ -135,7 -136,6 +136,7 @@@ extern const char *setup_git_directory(
  extern const char *prefix_path(const char *prefix, int len, const char *path);
  extern const char *prefix_filename(const char *prefix, int len, const char *path);
  extern void verify_filename(const char *prefix, const char *name);
 +extern void verify_non_filename(const char *prefix, const char *name);
  
  #define alloc_nr(x) (((x)+16)*3/2)
  
@@@ -158,12 -158,6 +159,12 @@@ extern int index_pipe(unsigned char *sh
  extern int index_path(unsigned char *sha1, const char *path, struct stat *st, int write_object);
  extern void fill_stat_cache_info(struct cache_entry *ce, struct stat *st);
  
 +#define REFRESH_REALLY                0x0001  /* ignore_valid */
 +#define REFRESH_UNMERGED      0x0002  /* allow unmerged */
 +#define REFRESH_QUIET         0x0004  /* be quiet about it */
 +#define REFRESH_IGNORE_MISSING        0x0008  /* ignore non-existent */
 +extern int refresh_cache(unsigned int flags);
 +
  struct cache_file {
        struct cache_file *next;
        char lockfile[PATH_MAX];
@@@ -175,7 -169,7 +176,7 @@@ extern void rollback_index_file(struct 
  /* Environment bits from configuration mechanism */
  extern int trust_executable_bit;
  extern int assume_unchanged;
 -extern int only_use_symrefs;
 +extern int prefer_symlink_refs;
  extern int warn_ambiguous_refs;
  extern int diff_rename_limit_default;
  extern int shared_repository;
@@@ -369,8 -363,4 +370,8 @@@ extern int receive_keep_pack(int fd[2]
  /* pager.c */
  extern void setup_pager(void);
  
 +/* base85 */
 +int decode_85(char *dst, char *line, int linelen);
 +void encode_85(char *buf, unsigned char *data, int bytes);
 +
  #endif /* CACHE_H */
diff --combined checkout-index.c
@@@ -39,6 -39,7 +39,7 @@@
  #include "cache.h"
  #include "strbuf.h"
  #include "quote.h"
+ #include "cache-tree.h"
  
  #define CHECKOUT_ALL 4
  static const char *prefix;
@@@ -269,16 -270,12 +270,16 @@@ int main(int argc, char **argv
        /* Check out named files first */
        for ( ; i < argc; i++) {
                const char *arg = argv[i];
 +              const char *p;
  
                if (all)
                        die("git-checkout-index: don't mix '--all' and explicit filenames");
                if (read_from_stdin)
                        die("git-checkout-index: don't mix '--stdin' and explicit filenames");
 -              checkout_file(prefix_path(prefix, prefix_length, arg));
 +              p = prefix_path(prefix, prefix_length, arg);
 +              checkout_file(p);
 +              if (p < arg || p > arg + strlen(arg))
 +                      free((char*)p);
        }
  
        if (read_from_stdin) {
                strbuf_init(&buf);
                while (1) {
                        char *path_name;
 +                      const char *p;
 +
                        read_line(&buf, stdin, line_termination);
                        if (buf.eof)
                                break;
                                path_name = unquote_c_style(buf.buf, NULL);
                        else
                                path_name = buf.buf;
 -                      checkout_file(prefix_path(prefix, prefix_length, path_name));
 +                      p = prefix_path(prefix, prefix_length, path_name);
 +                      checkout_file(p);
 +                      if (p < path_name || p > path_name + strlen(path_name))
 +                              free((char *)p);
                        if (path_name != buf.buf)
                                free(path_name);
                }
diff --combined read-cache.c
@@@ -4,11 -4,26 +4,26 @@@
   * Copyright (C) Linus Torvalds, 2005
   */
  #include "cache.h"
+ #include "cache-tree.h"
+ /* Index extensions.
+  *
+  * The first letter should be 'A'..'Z' for extensions that are not
+  * necessary for a correct operation (i.e. optimization data).
+  * When new extensions are added that _needs_ to be understood in
+  * order to correctly interpret the index file, pick character that
+  * is outside the range, to cause the reader to abort.
+  */
+ #define CACHE_EXT(s) ( (s[0]<<24)|(s[1]<<16)|(s[2]<<8)|(s[3]) )
+ #define CACHE_EXT_TREE 0x54524545     /* "TREE" */
  
  struct cache_entry **active_cache = NULL;
  static time_t index_file_timestamp;
  unsigned int active_nr = 0, active_alloc = 0, active_cache_changed = 0;
  
+ struct cache_tree *active_cache_tree = NULL;
  /*
   * This only updates the "non-critical" parts of the directory
   * cache, ie the parts that aren't tracked by GIT, and only used
@@@ -496,123 -511,6 +511,123 @@@ int add_cache_entry(struct cache_entry 
        return 0;
  }
  
 +/* Three functions to allow overloaded pointer return; see linux/err.h */
 +static inline void *ERR_PTR(long error)
 +{
 +      return (void *) error;
 +}
 +
 +static inline long PTR_ERR(const void *ptr)
 +{
 +      return (long) ptr;
 +}
 +
 +static inline long IS_ERR(const void *ptr)
 +{
 +      return (unsigned long)ptr > (unsigned long)-1000L;
 +}
 +
 +/*
 + * "refresh" does not calculate a new sha1 file or bring the
 + * cache up-to-date for mode/content changes. But what it
 + * _does_ do is to "re-match" the stat information of a file
 + * with the cache, so that you can refresh the cache for a
 + * file that hasn't been changed but where the stat entry is
 + * out of date.
 + *
 + * For example, you'd want to do this after doing a "git-read-tree",
 + * to link up the stat cache details with the proper files.
 + */
 +static struct cache_entry *refresh_entry(struct cache_entry *ce, int really)
 +{
 +      struct stat st;
 +      struct cache_entry *updated;
 +      int changed, size;
 +
 +      if (lstat(ce->name, &st) < 0)
 +              return ERR_PTR(-errno);
 +
 +      changed = ce_match_stat(ce, &st, really);
 +      if (!changed) {
 +              if (really && assume_unchanged &&
 +                  !(ce->ce_flags & htons(CE_VALID)))
 +                      ; /* mark this one VALID again */
 +              else
 +                      return NULL;
 +      }
 +
 +      if (ce_modified(ce, &st, really))
 +              return ERR_PTR(-EINVAL);
 +
 +      size = ce_size(ce);
 +      updated = xmalloc(size);
 +      memcpy(updated, ce, size);
 +      fill_stat_cache_info(updated, &st);
 +
 +      /* In this case, if really is not set, we should leave
 +       * CE_VALID bit alone.  Otherwise, paths marked with
 +       * --no-assume-unchanged (i.e. things to be edited) will
 +       * reacquire CE_VALID bit automatically, which is not
 +       * really what we want.
 +       */
 +      if (!really && assume_unchanged && !(ce->ce_flags & htons(CE_VALID)))
 +              updated->ce_flags &= ~htons(CE_VALID);
 +
 +      return updated;
 +}
 +
 +int refresh_cache(unsigned int flags)
 +{
 +      int i;
 +      int has_errors = 0;
 +      int really = (flags & REFRESH_REALLY) != 0;
 +      int allow_unmerged = (flags & REFRESH_UNMERGED) != 0;
 +      int quiet = (flags & REFRESH_QUIET) != 0;
 +      int not_new = (flags & REFRESH_IGNORE_MISSING) != 0;
 +
 +      for (i = 0; i < active_nr; i++) {
 +              struct cache_entry *ce, *new;
 +              ce = active_cache[i];
 +              if (ce_stage(ce)) {
 +                      while ((i < active_nr) &&
 +                             ! strcmp(active_cache[i]->name, ce->name))
 +                              i++;
 +                      i--;
 +                      if (allow_unmerged)
 +                              continue;
 +                      printf("%s: needs merge\n", ce->name);
 +                      has_errors = 1;
 +                      continue;
 +              }
 +
 +              new = refresh_entry(ce, really);
 +              if (!new)
 +                      continue;
 +              if (IS_ERR(new)) {
 +                      if (not_new && PTR_ERR(new) == -ENOENT)
 +                              continue;
 +                      if (really && PTR_ERR(new) == -EINVAL) {
 +                              /* If we are doing --really-refresh that
 +                               * means the index is not valid anymore.
 +                               */
 +                              ce->ce_flags &= ~htons(CE_VALID);
 +                              active_cache_changed = 1;
 +                      }
 +                      if (quiet)
 +                              continue;
 +                      printf("%s: needs update\n", ce->name);
 +                      has_errors = 1;
 +                      continue;
 +              }
 +              active_cache_changed = 1;
 +              /* You can NOT just free active_cache[i] here, since it
 +               * might not be necessarily malloc()ed but can also come
 +               * from mmap(). */
 +              active_cache[i] = new;
 +      }
 +      return has_errors;
 +}
 +
  static int verify_hdr(struct cache_header *hdr, unsigned long size)
  {
        SHA_CTX c;
        return 0;
  }
  
+ static int read_index_extension(const char *ext, void *data, unsigned long sz)
+ {
+       switch (CACHE_EXT(ext)) {
+       case CACHE_EXT_TREE:
+               active_cache_tree = cache_tree_read(data, sz);
+               break;
+       default:
+               if (*ext < 'A' || 'Z' < *ext)
+                       return error("index uses %.4s extension, which we do not understand",
+                                    ext);
+               fprintf(stderr, "ignoring %.4s extension\n", ext);
+               break;
+       }
+       return 0;
+ }
  int read_cache(void)
  {
        int fd, i;
  
        active_nr = ntohl(hdr->hdr_entries);
        active_alloc = alloc_nr(active_nr);
 -      active_cache = calloc(active_alloc, sizeof(struct cache_entry *));
 +      active_cache = xcalloc(active_alloc, sizeof(struct cache_entry *));
  
        offset = sizeof(*hdr);
        for (i = 0; i < active_nr; i++) {
                active_cache[i] = ce;
        }
        index_file_timestamp = st.st_mtime;
+       while (offset <= size - 20 - 8) {
+               /* After an array of active_nr index entries,
+                * there can be arbitrary number of extended
+                * sections, each of which is prefixed with
+                * extension name (4-byte) and section length
+                * in 4-byte network byte order.
+                */
+               unsigned long extsize;
+               memcpy(&extsize, map + offset + 4, 4);
+               extsize = ntohl(extsize);
+               if (read_index_extension(map + offset,
+                                        map + offset + 8, extsize) < 0)
+                       goto unmap;
+               offset += 8;
+               offset += extsize;
+       }
        return active_nr;
  
  unmap:
@@@ -712,6 -642,17 +759,17 @@@ static int ce_write(SHA_CTX *context, i
        return 0;
  }
  
+ static int write_index_ext_header(SHA_CTX *context, int fd,
+                                 unsigned long ext, unsigned long sz)
+ {
+       ext = htonl(ext);
+       sz = htonl(sz);
+       if ((ce_write(context, fd, &ext, 4) < 0) ||
+           (ce_write(context, fd, &sz, 4) < 0))
+               return -1;
+       return 0;
+ }
  static int ce_flush(SHA_CTX *context, int fd)
  {
        unsigned int left = write_buffer_len;
@@@ -808,5 -749,19 +866,19 @@@ int write_cache(int newfd, struct cache
                if (ce_write(&c, newfd, ce, ce_size(ce)) < 0)
                        return -1;
        }
+       /* Write extension data here */
+       if (active_cache_tree) {
+               unsigned long sz;
+               void *data = cache_tree_write(active_cache_tree, &sz);
+               if (data &&
+                   !write_index_ext_header(&c, newfd, CACHE_EXT_TREE, sz) &&
+                   !ce_write(&c, newfd, data, sz))
+                       ;
+               else {
+                       free(data);
+                       return -1;
+               }
+       }
        return ce_flush(&c, newfd);
  }
diff --combined read-tree.c
@@@ -9,10 -9,10 +9,11 @@@
  
  #include "object.h"
  #include "tree.h"
+ #include "cache-tree.h"
  #include <sys/time.h>
  #include <signal.h>
  
 +static int reset = 0;
  static int merge = 0;
  static int update = 0;
  static int index_only = 0;
@@@ -408,7 -408,7 +409,7 @@@ static void verify_uptodate(struct cach
  {
        struct stat st;
  
 -      if (index_only)
 +      if (index_only || reset)
                return;
  
        if (!lstat(ce->name, &st)) {
                        return;
                errno = 0;
        }
 +      if (reset) {
 +              ce->ce_flags |= htons(CE_UPDATE);
 +              return;
 +      }
        if (errno == ENOENT)
                return;
        die("Entry '%s' not uptodate. Cannot merge.", ce->name);
  }
  
+ static void invalidate_ce_path(struct cache_entry *ce)
+ {
+       if (ce)
+               cache_tree_invalidate_path(active_cache_tree, ce->name);
+ }
 +/*
 + * We do not want to remove or overwrite a working tree file that
 + * is not tracked.
 + */
 +static void verify_absent(const char *path, const char *action)
 +{
 +      struct stat st;
 +
 +      if (index_only || reset || !update)
 +              return;
 +      if (!lstat(path, &st))
 +              die("Untracked working tree file '%s' "
 +                  "would be %s by merge.", path, action);
 +}
 +
  static int merged_entry(struct cache_entry *merge, struct cache_entry *old)
  {
        merge->ce_flags |= htons(CE_UPDATE);
                        *merge = *old;
                } else {
                        verify_uptodate(old);
+                       invalidate_ce_path(old);
                }
        }
--      else
++      else {
 +              verify_absent(merge->name, "overwritten");
+               invalidate_ce_path(merge);
++      }
 +
        merge->ce_flags &= ~htons(CE_STAGEMASK);
        add_cache_entry(merge, ADD_CACHE_OK_TO_ADD);
        return 1;
@@@ -470,10 -457,9 +480,11 @@@ static int deleted_entry(struct cache_e
  {
        if (old)
                verify_uptodate(old);
 +      else
 +              verify_absent(ce->name, "removed");
        ce->ce_mode = 0;
        add_cache_entry(ce, ADD_CACHE_OK_TO_ADD);
+       invalidate_ce_path(ce);
        return 1;
  }
  
@@@ -507,7 -493,6 +518,7 @@@ static int threeway_merge(struct cache_
        int count;
        int head_match = 0;
        int remote_match = 0;
 +      const char *path = NULL;
  
        int df_conflict_head = 0;
        int df_conflict_remote = 0;
        for (i = 1; i < head_idx; i++) {
                if (!stages[i])
                        any_anc_missing = 1;
 -              else
 +              else {
 +                      if (!path)
 +                              path = stages[i]->name;
                        no_anc_exists = 0;
 +              }
        }
  
        index = stages[0];
                remote = NULL;
        }
  
 +      if (!path && index)
 +              path = index->name;
 +      if (!path && head)
 +              path = head->name;
 +      if (!path && remote)
 +              path = remote->name;
 +
        /* First, if there's a #16 situation, note that to prevent #13
 -       * and #14. 
 +       * and #14.
         */
        if (!same(remote, head)) {
                for (i = 1; i < head_idx; i++) {
                    (remote_deleted && head && head_match)) {
                        if (index)
                                return deleted_entry(index, index);
 +                      else if (path)
 +                              verify_absent(path, "removed");
                        return 0;
                }
                /*
        if (index) {
                verify_uptodate(index);
        }
 +      else if (path)
 +              verify_absent(path, "overwritten");
  
        nontrivial_merge = 1;
  
@@@ -723,18 -694,14 +734,18 @@@ static int oneway_merge(struct cache_en
                return error("Cannot do a oneway merge of %d trees",
                             merge_size);
  
 -      if (!a) {
 -              invalidate_ce_path(old);
 -              return 0;
 -      }
 +      if (!a)
 +              return deleted_entry(old, old);
        if (old && same(old, a)) {
 +              if (reset) {
 +                      struct stat st;
 +                      if (lstat(old->name, &st) ||
 +                          ce_match_stat(old, &st, 1))
 +                              old->ce_flags |= htons(CE_UPDATE);
 +              }
                return keep_entry(old);
        }
 -      return merged_entry(a, NULL);
 +      return merged_entry(a, old);
  }
  
  static int read_cache_unmerged(void)
                struct cache_entry *ce = active_cache[i];
                if (ce_stage(ce)) {
                        deleted++;
+                       invalidate_ce_path(ce);
                        continue;
                }
                if (deleted)
        return deleted;
  }
  
 -      
+ static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)
+ {
+       struct tree_entry_list *ent;
+       int cnt;
++
+       memcpy(it->sha1, tree->object.sha1, 20);
+       for (cnt = 0, ent = tree->entries; ent; ent = ent->next) {
+               if (!ent->directory)
+                       cnt++;
+               else {
+                       struct cache_tree_sub *sub;
+                       struct tree *subtree = (struct tree *)ent->item.tree;
+                       if (!subtree->object.parsed)
+                               parse_tree(subtree);
+                       sub = cache_tree_sub(it, ent->name);
+                       sub->cache_tree = cache_tree();
+                       prime_cache_tree_rec(sub->cache_tree, subtree);
+                       cnt += sub->cache_tree->entry_count;
+               }
+       }
+       it->entry_count = cnt;
+ }
+ static void prime_cache_tree(void)
+ {
+       struct tree *tree = (struct tree *)trees->item;
+       if (!tree)
+               return;
+       active_cache_tree = cache_tree();
+       prime_cache_tree_rec(active_cache_tree, tree);
+ }
  static const char read_tree_usage[] = "git-read-tree (<sha> | -m [--aggressive] [-u | -i] <sha1> [<sha2> [<sha3>]])";
  
  static struct cache_file cache_file;
  
  int main(int argc, char **argv)
  {
 -      int i, newfd, reset, stage = 0;
 +      int i, newfd, stage = 0;
        unsigned char sha1[20];
        merge_fn_t fn = NULL;
  
                if (1 < index_only + update)
                        usage(read_tree_usage);
  
 -              if (get_sha1(arg, sha1) < 0)
 -                      usage(read_tree_usage);
 +              if (get_sha1(arg, sha1))
 +                      die("Not a valid object name %s", arg);
                if (list_tree(sha1) < 0)
                        die("failed to unpack tree object %s", arg);
                stage++;
                        fn = twoway_merge;
                        break;
                case 3:
-                       fn = threeway_merge;
-                       break;
                default:
                        fn = threeway_merge;
+                       cache_tree_free(&active_cache_tree);
                        break;
                }
  
        }
  
        unpack_trees(fn);
+       /*
+        * When reading only one tree (either the most basic form,
+        * "-m ent" or "--reset ent" form), we can obtain a fully
+        * valid cache-tree because the index must match exactly
+        * what came from the tree.
+        */
+       if (trees && trees->item && (!merge || (stage == 2))) {
+               cache_tree_free(&active_cache_tree);
+               prime_cache_tree();
+       }
        if (write_cache(newfd, active_cache, active_nr) ||
            commit_index_file(&cache_file))
                die("unable to write new index file");
diff --combined update-index.c
@@@ -6,6 -6,7 +6,7 @@@
  #include "cache.h"
  #include "strbuf.h"
  #include "quote.h"
+ #include "cache-tree.h"
  #include "tree-walk.h"
  
  /*
@@@ -18,6 -19,9 +19,6 @@@
  static int allow_add;
  static int allow_remove;
  static int allow_replace;
 -static int allow_unmerged; /* --refresh needing merge is not error */
 -static int not_new; /* --refresh not having working tree files is not error */
 -static int quiet; /* --refresh needing update is not error */
  static int info_only;
  static int force_remove;
  static int verbose;
@@@ -25,6 -29,23 +26,6 @@@ static int mark_valid_only = 0
  #define MARK_VALID 1
  #define UNMARK_VALID 2
  
 -
 -/* Three functions to allow overloaded pointer return; see linux/err.h */
 -static inline void *ERR_PTR(long error)
 -{
 -      return (void *) error;
 -}
 -
 -static inline long PTR_ERR(const void *ptr)
 -{
 -      return (long) ptr;
 -}
 -
 -static inline long IS_ERR(const void *ptr)
 -{
 -      return (unsigned long)ptr > (unsigned long)-1000L;
 -}
 -
  static void report(const char *fmt, ...)
  {
        va_list vp;
@@@ -51,6 -72,7 +52,7 @@@ static int mark_valid(const char *path
                        active_cache[pos]->ce_flags &= ~htons(CE_VALID);
                        break;
                }
+               cache_tree_invalidate_path(active_cache_tree, path);
                active_cache_changed = 1;
                return 0;
        }
@@@ -64,6 -86,12 +66,12 @@@ static int add_file_to_cache(const cha
        struct stat st;
  
        status = lstat(path, &st);
+       /* We probably want to do this in remove_file_from_cache() and
+        * add_cache_entry() instead...
+        */
+       cache_tree_invalidate_path(active_cache_tree, path);
        if (status < 0 || S_ISDIR(st.st_mode)) {
                /* When we used to have "path" and now we want to add
                 * "path/file", we need a way to remove "path" before
  }
  
  /*
 - * "refresh" does not calculate a new sha1 file or bring the
 - * cache up-to-date for mode/content changes. But what it
 - * _does_ do is to "re-match" the stat information of a file
 - * with the cache, so that you can refresh the cache for a
 - * file that hasn't been changed but where the stat entry is
 - * out of date.
 - *
 - * For example, you'd want to do this after doing a "git-read-tree",
 - * to link up the stat cache details with the proper files.
 - */
 -static struct cache_entry *refresh_entry(struct cache_entry *ce, int really)
 -{
 -      struct stat st;
 -      struct cache_entry *updated;
 -      int changed, size;
 -
 -      if (lstat(ce->name, &st) < 0)
 -              return ERR_PTR(-errno);
 -
 -      changed = ce_match_stat(ce, &st, really);
 -      if (!changed) {
 -              if (really && assume_unchanged &&
 -                  !(ce->ce_flags & htons(CE_VALID)))
 -                      ; /* mark this one VALID again */
 -              else
 -                      return NULL;
 -      }
 -
 -      if (ce_modified(ce, &st, really))
 -              return ERR_PTR(-EINVAL);
 -
 -      size = ce_size(ce);
 -      updated = xmalloc(size);
 -      memcpy(updated, ce, size);
 -      fill_stat_cache_info(updated, &st);
 -
 -      /* In this case, if really is not set, we should leave
 -       * CE_VALID bit alone.  Otherwise, paths marked with
 -       * --no-assume-unchanged (i.e. things to be edited) will
 -       * reacquire CE_VALID bit automatically, which is not
 -       * really what we want.
 -       */
 -      if (!really && assume_unchanged && !(ce->ce_flags & htons(CE_VALID)))
 -              updated->ce_flags &= ~htons(CE_VALID);
 -
 -      return updated;
 -}
 -
 -static int refresh_cache(int really)
 -{
 -      int i;
 -      int has_errors = 0;
 -
 -      for (i = 0; i < active_nr; i++) {
 -              struct cache_entry *ce, *new;
 -              ce = active_cache[i];
 -              if (ce_stage(ce)) {
 -                      while ((i < active_nr) &&
 -                             ! strcmp(active_cache[i]->name, ce->name))
 -                              i++;
 -                      i--;
 -                      if (allow_unmerged)
 -                              continue;
 -                      printf("%s: needs merge\n", ce->name);
 -                      has_errors = 1;
 -                      continue;
 -              }
 -
 -              new = refresh_entry(ce, really);
 -              if (!new)
 -                      continue;
 -              if (IS_ERR(new)) {
 -                      if (not_new && PTR_ERR(new) == -ENOENT)
 -                              continue;
 -                      if (really && PTR_ERR(new) == -EINVAL) {
 -                              /* If we are doing --really-refresh that
 -                               * means the index is not valid anymore.
 -                               */
 -                              ce->ce_flags &= ~htons(CE_VALID);
 -                              active_cache_changed = 1;
 -                      }
 -                      if (quiet)
 -                              continue;
 -                      printf("%s: needs update\n", ce->name);
 -                      has_errors = 1;
 -                      continue;
 -              }
 -              active_cache_changed = 1;
 -              /* You can NOT just free active_cache[i] here, since it
 -               * might not be necessarily malloc()ed but can also come
 -               * from mmap(). */
 -              active_cache[i] = new;
 -      }
 -      return has_errors;
 -}
 -
 -/*
   * We fundamentally don't like some paths: we don't want
   * dot or dot-dot anywhere, and for obvious reasons don't
   * want to recurse into ".git" either.
@@@ -209,6 -334,7 +217,7 @@@ static int add_cacheinfo(unsigned int m
                return error("%s: cannot add to the index - missing --add option?",
                             path);
        report("add '%s'", path);
+       cache_tree_invalidate_path(active_cache_tree, path);
        return 0;
  }
  
@@@ -233,6 -359,7 +242,7 @@@ static void chmod_path(int flip, const 
        default:
                goto fail;
        }
+       cache_tree_invalidate_path(active_cache_tree, path);
        active_cache_changed = 1;
        report("chmod %cx '%s'", flip, path);
        return;
@@@ -247,26 -374,24 +257,27 @@@ static void update_one(const char *path
        const char *p = prefix_path(prefix, prefix_length, path);
        if (!verify_path(p)) {
                fprintf(stderr, "Ignoring path %s\n", path);
 -              return;
 +              goto free_return;
        }
        if (mark_valid_only) {
                if (mark_valid(p))
                        die("Unable to mark file %s", path);
 -              return;
 +              goto free_return;
        }
+       cache_tree_invalidate_path(active_cache_tree, path);
  
        if (force_remove) {
                if (remove_file_from_cache(p))
                        die("git-update-index: unable to remove %s", path);
                report("remove '%s'", path);
 -              return;
 +              goto free_return;
        }
        if (add_file_to_cache(p))
                die("Unable to process file %s", path);
        report("add '%s'", path);
 + free_return:
 +      if (p < path || p > path + strlen(path))
 +              free((char*)p);
  }
  
  static void read_index_info(int line_termination)
                                free(path_name);
                        continue;
                }
+               cache_tree_invalidate_path(active_cache_tree, path_name);
  
                if (!mode) {
                        /* mode == 0 means there is no such path -- remove */
  }
  
  static const char update_index_usage[] =
 -"git-update-index [-q] [--add] [--replace] [--remove] [--unmerged] [--refresh] [--cacheinfo] [--chmod=(+|-)x] [--info-only] [--force-remove] [--stdin] [--index-info] [--ignore-missing] [-z] [--verbose] [--] <file>...";
 +"git-update-index [-q] [--add] [--replace] [--remove] [--unmerged] [--refresh] [--really-refresh] [--cacheinfo] [--chmod=(+|-)x] [--assume-unchanged] [--info-only] [--force-remove] [--stdin] [--index-info] [--unresolve] [--again] [--ignore-missing] [-z] [--verbose] [--] <file>...";
  
  static unsigned char head_sha1[20];
  static unsigned char merge_head_sha1[20];
@@@ -374,13 -500,11 +386,13 @@@ static struct cache_entry *read_one_ent
        struct cache_entry *ce;
  
        if (get_tree_entry(ent, path, sha1, &mode)) {
 -              error("%s: not in %s branch.", path, which);
 +              if (which)
 +                      error("%s: not in %s branch.", path, which);
                return NULL;
        }
        if (mode == S_IFDIR) {
 -              error("%s: not a blob in %s branch.", path, which);
 +              if (which)
 +                      error("%s: not a blob in %s branch.", path, which);
                return NULL;
        }
        size = cache_entry_size(namelen);
@@@ -438,6 -562,7 +450,7 @@@ static int unresolve_one(const char *pa
                goto free_return;
        }
  
+       cache_tree_invalidate_path(active_cache_tree, path);
        remove_file_from_cache(path);
        if (add_cache_entry(ce_2, ADD_CACHE_OK_TO_ADD)) {
                error("%s: cannot add our version to the index.", path);
@@@ -464,8 -589,7 +477,8 @@@ static void read_head_pointers(void
        }
  }
  
 -static int do_unresolve(int ac, const char **av)
 +static int do_unresolve(int ac, const char **av,
 +                      const char *prefix, int prefix_length)
  {
        int i;
        int err = 0;
  
        for (i = 1; i < ac; i++) {
                const char *arg = av[i];
 -              err |= unresolve_one(arg);
 +              const char *p = prefix_path(prefix, prefix_length, arg);
 +              err |= unresolve_one(p);
 +              if (p < arg || p > arg + strlen(arg))
 +                      free((char*)p);
        }
        return err;
  }
  
 +static int do_reupdate(int ac, const char **av,
 +                     const char *prefix, int prefix_length)
 +{
 +      /* Read HEAD and run update-index on paths that are
 +       * merged and already different between index and HEAD.
 +       */
 +      int pos;
 +      int has_head = 1;
 +      const char **pathspec = get_pathspec(prefix, av + 1);
 +
 +      if (read_ref(git_path("HEAD"), head_sha1))
 +              /* If there is no HEAD, that means it is an initial
 +               * commit.  Update everything in the index.
 +               */
 +              has_head = 0;
 + redo:
 +      for (pos = 0; pos < active_nr; pos++) {
 +              struct cache_entry *ce = active_cache[pos];
 +              struct cache_entry *old = NULL;
 +              int save_nr;
 +
 +              if (ce_stage(ce) || !ce_path_match(ce, pathspec))
 +                      continue;
 +              if (has_head)
 +                      old = read_one_ent(NULL, head_sha1,
 +                                         ce->name, ce_namelen(ce), 0);
 +              if (old && ce->ce_mode == old->ce_mode &&
 +                  !memcmp(ce->sha1, old->sha1, 20)) {
 +                      free(old);
 +                      continue; /* unchanged */
 +              }
 +              /* Be careful.  The working tree may not have the
 +               * path anymore, in which case, under 'allow_remove',
 +               * or worse yet 'allow_replace', active_nr may decrease.
 +               */
 +              save_nr = active_nr;
 +              update_one(ce->name + prefix_length, prefix, prefix_length);
 +              if (save_nr != active_nr)
 +                      goto redo;
 +      }
 +      return 0;
 +}
 +
  int main(int argc, const char **argv)
  {
        int i, newfd, entries, has_errors = 0, line_termination = '\n';
        const char *prefix = setup_git_directory();
        int prefix_length = prefix ? strlen(prefix) : 0;
        char set_executable_bit = 0;
 +      unsigned int refresh_flags = 0;
  
        git_config(git_default_config);
  
                                continue;
                        }
                        if (!strcmp(path, "-q")) {
 -                              quiet = 1;
 +                              refresh_flags |= REFRESH_QUIET;
                                continue;
                        }
                        if (!strcmp(path, "--add")) {
                                continue;
                        }
                        if (!strcmp(path, "--unmerged")) {
 -                              allow_unmerged = 1;
 +                              refresh_flags |= REFRESH_UNMERGED;
                                continue;
                        }
                        if (!strcmp(path, "--refresh")) {
 -                              has_errors |= refresh_cache(0);
 +                              has_errors |= refresh_cache(refresh_flags);
                                continue;
                        }
                        if (!strcmp(path, "--really-refresh")) {
 -                              has_errors |= refresh_cache(1);
 +                              has_errors |= refresh_cache(REFRESH_REALLY | refresh_flags);
                                continue;
                        }
                        if (!strcmp(path, "--cacheinfo")) {
                                break;
                        }
                        if (!strcmp(path, "--unresolve")) {
 -                              has_errors = do_unresolve(argc - i, argv + i);
 +                              has_errors = do_unresolve(argc - i, argv + i,
 +                                                        prefix, prefix_length);
 +                              if (has_errors)
 +                                      active_cache_changed = 0;
 +                              goto finish;
 +                      }
 +                      if (!strcmp(path, "--again")) {
 +                              has_errors = do_reupdate(argc - i, argv + i,
 +                                                       prefix, prefix_length);
                                if (has_errors)
                                        active_cache_changed = 0;
                                goto finish;
                        }
                        if (!strcmp(path, "--ignore-missing")) {
 -                              not_new = 1;
 +                              refresh_flags |= REFRESH_IGNORE_MISSING;
                                continue;
                        }
                        if (!strcmp(path, "--verbose")) {
                strbuf_init(&buf);
                while (1) {
                        char *path_name;
 +                      const char *p;
                        read_line(&buf, stdin, line_termination);
                        if (buf.eof)
                                break;
                                path_name = unquote_c_style(buf.buf, NULL);
                        else
                                path_name = buf.buf;
 -                      update_one(path_name, prefix, prefix_length);
 -                      if (set_executable_bit) {
 -                              const char *p = prefix_path(prefix, prefix_length, path_name);
 +                      p = prefix_path(prefix, prefix_length, path_name);
 +                      update_one(p, NULL, 0);
 +                      if (set_executable_bit)
                                chmod_path(set_executable_bit, p);
 -                      }
 +                      if (p < path_name || p > path_name + strlen(path_name))
 +                              free((char*) p);
                        if (path_name != buf.buf)
                                free(path_name);
                }