Merge branch 'nd/index-pack-no-recurse'

* nd/index-pack-no-recurse:
  index-pack: eliminate unlimited recursion in get_base_data()
  index-pack: eliminate recursion in find_unresolved_deltas
  Eliminate recursion in setting/clearing marks in commit list

diff --combined commit.c
index 35af4988f0ff83c6a3379ea9f6de4e4e1568c39f,c7aefbfd2868deddb1dc80a5a110f785b1289b7e..4b39c19123c7fa8584a67d5fd91e11f89e5816e4
--- 1/commit.c
--- 2/commit.c
+++ b/commit.c
@@@ -6,7 -6,6 +6,7 @@@
  #include "diff.h"
  #include "revision.h"
  #include "notes.h"
 +#include "gpg-interface.h"
  
  int save_commit_buffer = 1;
  
@@@ -422,7 -421,8 +422,8 @@@ struct commit *pop_most_recent_commit(s
        return ret;
  }
  
- void clear_commit_marks(struct commit *commit, unsigned int mark)
+ static void clear_commit_marks_1(struct commit_list **plist,
+                                struct commit *commit, unsigned int mark)
  {
        while (commit) {
                struct commit_list *parents;
@@@ -437,12 -437,20 +438,20 @@@
                        return;
  
                while ((parents = parents->next))
-                       clear_commit_marks(parents->item, mark);
+                       commit_list_insert(parents->item, plist);
  
                commit = commit->parents->item;
        }
  }
  
+ void clear_commit_marks(struct commit *commit, unsigned int mark)
+ {
+       struct commit_list *list = NULL;
+       commit_list_insert(commit, &list);
+       while (list)
+               clear_commit_marks_1(&list, pop_commit(&list), mark);
+ }
+ 
  void clear_commit_marks_for_object_array(struct object_array *a, unsigned mark)
  {
        struct object *object;
@@@ -841,86 -849,6 +850,86 @@@ struct commit_list *reduce_heads(struc
        return result;
  }
  
 +static const char gpg_sig_header[] = "gpgsig";
 +static const int gpg_sig_header_len = sizeof(gpg_sig_header) - 1;
 +
 +static int do_sign_commit(struct strbuf *buf, const char *keyid)
 +{
 +      struct strbuf sig = STRBUF_INIT;
 +      int inspos, copypos;
 +
 +      /* find the end of the header */
 +      inspos = strstr(buf->buf, "\n\n") - buf->buf + 1;
 +
 +      if (!keyid || !*keyid)
 +              keyid = get_signing_key();
 +      if (sign_buffer(buf, &sig, keyid)) {
 +              strbuf_release(&sig);
 +              return -1;
 +      }
 +
 +      for (copypos = 0; sig.buf[copypos]; ) {
 +              const char *bol = sig.buf + copypos;
 +              const char *eol = strchrnul(bol, '\n');
 +              int len = (eol - bol) + !!*eol;
 +
 +              if (!copypos) {
 +                      strbuf_insert(buf, inspos, gpg_sig_header, gpg_sig_header_len);
 +                      inspos += gpg_sig_header_len;
 +              }
 +              strbuf_insert(buf, inspos++, " ", 1);
 +              strbuf_insert(buf, inspos, bol, len);
 +              inspos += len;
 +              copypos += len;
 +      }
 +      strbuf_release(&sig);
 +      return 0;
 +}
 +
 +int parse_signed_commit(const unsigned char *sha1,
 +                      struct strbuf *payload, struct strbuf *signature)
 +{
 +      unsigned long size;
 +      enum object_type type;
 +      char *buffer = read_sha1_file(sha1, &type, &size);
 +      int in_signature, saw_signature = -1;
 +      char *line, *tail;
 +
 +      if (!buffer || type != OBJ_COMMIT)
 +              goto cleanup;
 +
 +      line = buffer;
 +      tail = buffer + size;
 +      in_signature = 0;
 +      saw_signature = 0;
 +      while (line < tail) {
 +              const char *sig = NULL;
 +              char *next = memchr(line, '\n', tail - line);
 +
 +              next = next ? next + 1 : tail;
 +              if (in_signature && line[0] == ' ')
 +                      sig = line + 1;
 +              else if (!prefixcmp(line, gpg_sig_header) &&
 +                       line[gpg_sig_header_len] == ' ')
 +                      sig = line + gpg_sig_header_len + 1;
 +              if (sig) {
 +                      strbuf_add(signature, sig, next - sig);
 +                      saw_signature = 1;
 +                      in_signature = 1;
 +              } else {
 +                      if (*line == '\n')
 +                              /* dump the whole remainder of the buffer */
 +                              next = tail;
 +                      strbuf_add(payload, line, next - line);
 +                      in_signature = 0;
 +              }
 +              line = next;
 +      }
 + cleanup:
 +      free(buffer);
 +      return saw_signature;
 +}
 +
  static void handle_signed_tag(struct commit *parent, struct commit_extra_header ***tail)
  {
        struct merge_remote_desc *desc;
@@@ -981,15 -909,14 +990,15 @@@ static void add_extra_header(struct str
                strbuf_addch(buffer, '\n');
  }
  
 -struct commit_extra_header *read_commit_extra_headers(struct commit *commit)
 +struct commit_extra_header *read_commit_extra_headers(struct commit *commit,
 +                                                    const char **exclude)
  {
        struct commit_extra_header *extra = NULL;
        unsigned long size;
        enum object_type type;
        char *buffer = read_sha1_file(commit->object.sha1, &type, &size);
        if (buffer && type == OBJ_COMMIT)
 -              extra = read_commit_extra_header_lines(buffer, size);
 +              extra = read_commit_extra_header_lines(buffer, size, exclude);
        free(buffer);
        return extra;
  }
@@@ -1003,23 -930,7 +1012,23 @@@ static inline int standard_header_field
                (len == 8 && !memcmp(field, "encoding ", 9)));
  }
  
 -struct commit_extra_header *read_commit_extra_header_lines(const char *buffer, size_t size)
 +static int excluded_header_field(const char *field, size_t len, const char **exclude)
 +{
 +      if (!exclude)
 +              return 0;
 +
 +      while (*exclude) {
 +              size_t xlen = strlen(*exclude);
 +              if (len == xlen &&
 +                  !memcmp(field, *exclude, xlen) && field[xlen] == ' ')
 +                      return 1;
 +              exclude++;
 +      }
 +      return 0;
 +}
 +
 +struct commit_extra_header *read_commit_extra_header_lines(const char *buffer, size_t size,
 +                                                         const char **exclude)
  {
        struct commit_extra_header *extra = NULL, **tail = &extra, *it = NULL;
        const char *line, *next, *eof, *eob;
@@@ -1045,8 -956,7 +1054,8 @@@
                if (next <= eof)
                        eof = next;
  
 -              if (standard_header_field(line, eof - line))
 +              if (standard_header_field(line, eof - line) ||
 +                  excluded_header_field(line, eof - line, exclude))
                        continue;
  
                it = xcalloc(1, sizeof(*it));
@@@ -1074,14 -984,13 +1083,14 @@@ void free_commit_extra_headers(struct c
  
  int commit_tree(const struct strbuf *msg, unsigned char *tree,
                struct commit_list *parents, unsigned char *ret,
 -              const char *author)
 +              const char *author, const char *sign_commit)
  {
        struct commit_extra_header *extra = NULL, **tail = &extra;
        int result;
  
        append_merge_tag_headers(parents, &tail);
 -      result = commit_tree_extended(msg, tree, parents, ret, author, extra);
 +      result = commit_tree_extended(msg, tree, parents, ret,
 +                                    author, sign_commit, extra);
        free_commit_extra_headers(extra);
        return result;
  }
@@@ -1093,8 -1002,7 +1102,8 @@@ static const char commit_utf8_warn[] 
  
  int commit_tree_extended(const struct strbuf *msg, unsigned char *tree,
                         struct commit_list *parents, unsigned char *ret,
 -                       const char *author, struct commit_extra_header *extra)
 +                       const char *author, const char *sign_commit,
 +                       struct commit_extra_header *extra)
  {
        int result;
        int encoding_is_utf8;
@@@ -1147,9 -1055,6 +1156,9 @@@
        if (encoding_is_utf8 && !is_utf8(buffer.buf))
                fprintf(stderr, commit_utf8_warn);
  
 +      if (sign_commit && do_sign_commit(&buffer, sign_commit))
 +              return -1;
 +
        result = write_sha1_file(buffer.buf, buffer.len, commit_type, ret);
        strbuf_release(&buffer);
        return result;

diff --combined revision.c
index eb0be4206d2772e4d8eb11bfd164725529f915e7,7cc72fc02dede723f4a8d994cc7b813b08232a39..c97d83448426c317d82c08faf6150b8fe3bd4326
--- 1/revision.c
--- 2/revision.c
+++ b/revision.c
@@@ -139,11 -139,32 +139,32 @@@ void mark_tree_uninteresting(struct tre
  
  void mark_parents_uninteresting(struct commit *commit)
  {
-       struct commit_list *parents = commit->parents;
+       struct commit_list *parents = NULL, *l;
+ 
+       for (l = commit->parents; l; l = l->next)
+               commit_list_insert(l->item, &parents);
  
        while (parents) {
                struct commit *commit = parents->item;
-               if (!(commit->object.flags & UNINTERESTING)) {
+               l = parents;
+               parents = parents->next;
+               free(l);
+ 
+               while (commit) {
+                       /*
+                        * A missing commit is ok iff its parent is marked
+                        * uninteresting.
+                        *
+                        * We just mark such a thing parsed, so that when
+                        * it is popped next time around, we won't be trying
+                        * to parse it and get an error.
+                        */
+                       if (!has_sha1_file(commit->object.sha1))
+                               commit->object.parsed = 1;
+ 
+                       if (commit->object.flags & UNINTERESTING)
+                               break;
+ 
                        commit->object.flags |= UNINTERESTING;
  
                        /*
@@@ -154,21 -175,13 +175,13 @@@
                         * wasn't uninteresting), in which case we need
                         * to mark its parents recursively too..
                         */
-                       if (commit->parents)
-                               mark_parents_uninteresting(commit);
-               }
+                       if (!commit->parents)
+                               break;
  
-               /*
-                * A missing commit is ok iff its parent is marked
-                * uninteresting.
-                *
-                * We just mark such a thing parsed, so that when
-                * it is popped next time around, we won't be trying
-                * to parse it and get an error.
-                */
-               if (!has_sha1_file(commit->object.sha1))
-                       commit->object.parsed = 1;
-               parents = parents->next;
+                       for (l = commit->parents->next; l; l = l->next)
+                               commit_list_insert(l->item, &parents);
+                       commit = commit->parents->item;
+               }
        }
  }
  
@@@ -416,7 -429,7 +429,7 @@@ static int rev_same_tree_as_empty(struc
  static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
  {
        struct commit_list **pp, *parent;
 -      int tree_changed = 0, tree_same = 0;
 +      int tree_changed = 0, tree_same = 0, nth_parent = 0;
  
        /*
         * If we don't do pruning, everything is interesting
@@@ -444,14 -457,6 +457,14 @@@
        while ((parent = *pp) != NULL) {
                struct commit *p = parent->item;
  
 +              /*
 +               * Do not compare with later parents when we care only about
 +               * the first parent chain, in order to avoid derailing the
 +               * traversal to follow a side branch that brought everything
 +               * in the path we are limited to by the pathspec.
 +               */
 +              if (revs->first_parent_only && nth_parent++)
 +                      break;
                if (parse_commit(p) < 0)
                        die("cannot simplify commit %s (because of %s)",
                            sha1_to_hex(commit->object.sha1),
@@@ -1477,8 -1482,6 +1490,8 @@@ static int handle_revision_opt(struct r
                revs->show_notes = 1;
                revs->show_notes_given = 1;
                revs->notes_opt.use_default_notes = 1;
 +      } else if (!strcmp(arg, "--show-signature")) {
 +              revs->show_signature = 1;
        } else if (!prefixcmp(arg, "--show-notes=") ||
                   !prefixcmp(arg, "--notes=")) {
                struct strbuf buf = STRBUF_INIT;