[PATCH 0/5] Modernize read_graft_line implementation

I experimented with using a different hash algorithm (I am aware of
existing "Git hash function transition plan", I just want to push
things forward a bit) - and immediately hit a small issue - changing
the size of object_id hash buffer leads to compilation issues and
breaks graft-related tests.

I am sending patch 1 only to show a modification, that I did to
increase buffer size - it's not intended to be merged.

Patch 2 fixes trivial compilation issue.

Patches 3, 4, and 5 touch graft implementation to remove calculations
using GIT_SHA1_*, that lead to broken tests. I replaced FLEX_ARRAY of
object_id's representing parents with oid_array. New implementation
should be more future-proof, I think.

New implementation has tiny behaviour change: previously parents in
graft line needed to be separated with single space - now any number
of whitespace characters will do.

Alternative implementation approaches
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Strbuf could be replaced with string_list with
string_list_split_in_place instead of while loop in read_graft_line.
I didn't implement it this way because I learned
about string_list_split_in_place after finishing this implementation
draft. Right now I'm not sure which approach is better.

Another possibility is dropping graft feature altogether - that would
mean removing code for parsing grafts and 'parent' field in the struct,
but preserving the struct itself as a shallow clone marker. Grafts are
a little-known feature with modern replacement, but this seems like
bigger task and rather out of the scope of transition to the new
hashing algorithm.

I considered making function read_graft_line a static one and
read_graft_file non-static, but read_graft_line is used in
'builtin/blame.c' in function read_ancestry, which is almost a copy of
read_graft_file (difference of single boolean flag passed to
register_commit_graft). Removal of this duplication may be worthwhile,
but I think it's out of scope.

Patryk Obara (5):
  cache: extend object_id size to sha3-256
  sha1_file: fix hardcoded size in null_sha1
  commit: replace the raw buffer with strbuf in read_graft_line
  commit: implement free_commit_graft
  commit: rewrite read_graft_line

 builtin/blame.c |  2 +-
 cache.h         |  8 ++++++--
 commit.c        | 55 ++++++++++++++++++++++++++++++++-----------------------
 commit.h        |  5 +++--
 sha1_file.c     |  2 +-
 shallow.c       |  1 +
 6 files changed, 44 insertions(+), 29 deletions(-)

-- 
2.9.5

This commit is not intended to be merged - it serves only as context for
next patches in this thread.

Signed-off-by: Patryk Obara <redacted>
---
 cache.h | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/cache.h b/cache.h
index 1c69d2a..ad8a57c 100644
--- a/cache.h
+++ b/cache.h

@@ -68,9 +68,13 @@ unsigned long git_deflate_bound(git_zstream *, unsigned long);
 #define GIT_SHA1_RAWSZ 20
 #define GIT_SHA1_HEXSZ (2 * GIT_SHA1_RAWSZ)
 
+/* The length in bytes and in hex digits of an object name (SHA3-256 value). */
+#define GIT_SHA3_256_RAWSZ 32
+#define GIT_SHA3_256_HEXSZ (2 * GIT_SHA3_256_RAWSZ)
+
 /* The length in byte and in hex digits of the largest possible hash value. */
-#define GIT_MAX_RAWSZ GIT_SHA1_RAWSZ
-#define GIT_MAX_HEXSZ GIT_SHA1_HEXSZ
+#define GIT_MAX_RAWSZ GIT_SHA3_256_RAWSZ
+#define GIT_MAX_HEXSZ GIT_SHA3_256_HEXSZ
 
 struct object_id {
 	unsigned char hash[GIT_MAX_RAWSZ];

-- 
2.9.5

This prevents compilation error if GIT_MAX_RAWSZ is different than 20.

Signed-off-by: Patryk Obara <redacted>
---
 sha1_file.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sha1_file.c b/sha1_file.c
index b60ae15..f5b5bec 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -32,7 +32,7 @@
 #define SZ_FMT PRIuMAX
 static inline uintmax_t sz_fmt(size_t s) { return s; }
 
-const unsigned char null_sha1[20];
+const unsigned char null_sha1[GIT_MAX_RAWSZ];
 const struct object_id null_oid;
 const struct object_id empty_tree_oid = {
 	EMPTY_TREE_SHA1_BIN_LITERAL

-- 
2.9.5

Signed-off-by: Patryk Obara <redacted>
---
 commit.c | 11 ++++++++---
 commit.h |  1 +
 2 files changed, 9 insertions(+), 3 deletions(-)

diff --git a/commit.c b/commit.c
index 499fb14..6a145f1 100644
--- a/commit.c
+++ b/commit.c

@@ -109,15 +109,20 @@ static int commit_graft_pos(const unsigned char *sha1)
 			commit_graft_sha1_access);
 }
 
+void free_commit_graft(struct commit_graft *graft)
+{
+	free(graft);
+}
+
 int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 {
 	int pos = commit_graft_pos(graft->oid.hash);
 
 	if (0 <= pos) {
 		if (ignore_dups)
-			free(graft);
+			free_commit_graft(graft);
 		else {
-			free(commit_graft[pos]);
+			free_commit_graft(commit_graft[pos]);
 			commit_graft[pos] = graft;
 		}
 		return 1;

@@ -163,7 +168,7 @@ struct commit_graft *read_graft_line(struct strbuf *line)
 
 bad_graft_data:
 	error("bad graft data: %s", buf);
-	free(graft);
+	free_commit_graft(graft);
 	return NULL;
 }
 

diff --git a/commit.h b/commit.h
index baecc0a..c1b319f 100644
--- a/commit.h
+++ b/commit.h

@@ -247,6 +247,7 @@ struct commit_graft {
 };
 typedef int (*each_commit_graft_fn)(const struct commit_graft *, void *);
 
+void free_commit_graft(struct commit_graft *);
 struct commit_graft *read_graft_line(struct strbuf *line);
 int register_commit_graft(struct commit_graft *, int);
 struct commit_graft *lookup_commit_graft(const struct object_id *oid);

-- 
2.9.5

This simplifies function declaration and allows for use of strbuf_rtrim
instead of modifying buffer directly.

Signed-off-by: Patryk Obara <redacted>
---
 builtin/blame.c |  2 +-
 commit.c        | 11 ++++++-----
 commit.h        |  2 +-
 3 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/builtin/blame.c b/builtin/blame.c
index bda1a78..d4472e9 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c

@@ -488,7 +488,7 @@ static int read_ancestry(const char *graft_file)
 		return -1;
 	while (!strbuf_getwholeline(&buf, fp, '\n')) {
 		/* The format is just "Commit Parent1 Parent2 ...\n" */
-		struct commit_graft *graft = read_graft_line(buf.buf, buf.len);
+		struct commit_graft *graft = read_graft_line(&buf);
 		if (graft)
 			register_commit_graft(graft, 0);
 	}

diff --git a/commit.c b/commit.c
index 8b28415..499fb14 100644
--- a/commit.c
+++ b/commit.c

@@ -134,15 +134,16 @@ int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 	return 0;
 }
 
-struct commit_graft *read_graft_line(char *buf, int len)
+struct commit_graft *read_graft_line(struct strbuf *line)
 {
 	/* The format is just "Commit Parent1 Parent2 ...\n" */
-	int i;
+	int i, len;
+	char *buf = line->buf;
 	struct commit_graft *graft = NULL;
 	const int entry_size = GIT_SHA1_HEXSZ + 1;
 
-	while (len && isspace(buf[len-1]))
-		buf[--len] = '\0';
+	strbuf_rtrim(line);
+	len = line->len;
 	if (buf[0] == '#' || buf[0] == '\0')
 		return NULL;
 	if ((len + 1) % entry_size)

@@ -174,7 +175,7 @@ static int read_graft_file(const char *graft_file)
 		return -1;
 	while (!strbuf_getwholeline(&buf, fp, '\n')) {
 		/* The format is just "Commit Parent1 Parent2 ...\n" */
-		struct commit_graft *graft = read_graft_line(buf.buf, buf.len);
+		struct commit_graft *graft = read_graft_line(&buf);
 		if (!graft)
 			continue;
 		if (register_commit_graft(graft, 1))

diff --git a/commit.h b/commit.h
index 6d857f0..baecc0a 100644
--- a/commit.h
+++ b/commit.h

@@ -247,7 +247,7 @@ struct commit_graft {
 };
 typedef int (*each_commit_graft_fn)(const struct commit_graft *, void *);
 
-struct commit_graft *read_graft_line(char *buf, int len);
+struct commit_graft *read_graft_line(struct strbuf *line);
 int register_commit_graft(struct commit_graft *, int);
 struct commit_graft *lookup_commit_graft(const struct object_id *oid);
 

-- 
2.9.5

The previous implementation of read_graft_line used calculations based
on GIT_SHA1_RAWSZ and GIT_SHA1_HEXSZ to determine the number of commit
ids in a single graft line.  New implementation does not depend on these
constants, so it adapts to any object_id buffer size.

To make this possible, FLEX_ARRAY of object_id in struct was replaced
by an oid_array.

Code allocating graft now needs to use memset to zero the memory before
use to start with oid_array in a consistent state.

Updates free_graft function implemented in the previous patch to
properly cleanup an oid_array storing parents.

Signed-off-by: Patryk Obara <redacted>
---
 commit.c  | 39 +++++++++++++++++++++------------------
 commit.h  |  2 +-
 shallow.c |  1 +
 3 files changed, 23 insertions(+), 19 deletions(-)

diff --git a/commit.c b/commit.c
index 6a145f1..75dd45d 100644
--- a/commit.c
+++ b/commit.c

@@ -111,6 +111,7 @@ static int commit_graft_pos(const unsigned char *sha1)
 
 void free_commit_graft(struct commit_graft *graft)
 {
+	oid_array_clear(&graft->parents);
 	free(graft);
 }
 

@@ -139,35 +140,37 @@ int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 	return 0;
 }
 
+static int parse_next_oid_hex(const char *buf, struct object_id *oid, const char **end)
+{
+	while (isspace(buf[0]))
+		buf++;
+	return parse_oid_hex(buf, oid, end);
+}
+
 struct commit_graft *read_graft_line(struct strbuf *line)
 {
 	/* The format is just "Commit Parent1 Parent2 ...\n" */
-	int i, len;
-	char *buf = line->buf;
 	struct commit_graft *graft = NULL;
-	const int entry_size = GIT_SHA1_HEXSZ + 1;
+	struct object_id oid;
+	const char *tail = NULL;
 
 	strbuf_rtrim(line);
-	len = line->len;
-	if (buf[0] == '#' || buf[0] == '\0')
+	if (line->buf[0] == '#' || line->len == 0)
 		return NULL;
-	if ((len + 1) % entry_size)
+	graft = xmalloc(sizeof(*graft));
+	memset(graft, 0, sizeof(*graft));
+	if (parse_oid_hex(line->buf, &graft->oid, &tail))
 		goto bad_graft_data;
-	i = (len + 1) / entry_size - 1;
-	graft = xmalloc(st_add(sizeof(*graft), st_mult(GIT_SHA1_RAWSZ, i)));
-	graft->nr_parent = i;
-	if (get_oid_hex(buf, &graft->oid))
+	while (!parse_next_oid_hex(tail, &oid, &tail))
+		oid_array_append(&graft->parents, &oid);
+	if (tail[0] != '\0')
 		goto bad_graft_data;
-	for (i = GIT_SHA1_HEXSZ; i < len; i += entry_size) {
-		if (buf[i] != ' ')
-			goto bad_graft_data;
-		if (get_sha1_hex(buf + i + 1, graft->parent[i/entry_size].hash))
-			goto bad_graft_data;
-	}
+	graft->nr_parent = graft->parents.nr;
+
 	return graft;
 
 bad_graft_data:
-	error("bad graft data: %s", buf);
+	error("bad graft data: %s", line->buf);
 	free_commit_graft(graft);
 	return NULL;
 }

@@ -363,7 +366,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 		int i;
 		struct commit *new_parent;
 		for (i = 0; i < graft->nr_parent; i++) {
-			new_parent = lookup_commit(&graft->parent[i]);
+			new_parent = lookup_commit(&graft->parents.oid[i]);
 			if (!new_parent)
 				continue;
 			pptr = &commit_list_insert(new_parent, pptr)->next;

diff --git a/commit.h b/commit.h
index c1b319f..070d45d 100644
--- a/commit.h
+++ b/commit.h

@@ -243,7 +243,7 @@ void sort_in_topological_order(struct commit_list **, enum rev_sort_order);
 struct commit_graft {
 	struct object_id oid;
 	int nr_parent; /* < 0 if shallow commit */
-	struct object_id parent[FLEX_ARRAY]; /* more */
+	struct oid_array parents;
 };
 typedef int (*each_commit_graft_fn)(const struct commit_graft *, void *);
 

diff --git a/shallow.c b/shallow.c
index f5591e5..892cd90 100644
--- a/shallow.c
+++ b/shallow.c

@@ -33,6 +33,7 @@ int register_shallow(const struct object_id *oid)
 		xmalloc(sizeof(struct commit_graft));
 	struct commit *commit = lookup_commit(oid);
 
+	memset(graft, 0, sizeof(*graft));
 	oidcpy(&graft->oid, oid);
 	graft->nr_parent = -1;
 	if (commit && commit->object.parsed)

-- 
2.9.5

On Tue, Aug 15, 2017 at 4:49 AM, Patryk Obara [off-list ref] wrote:

outside the scope of this patch:
Is GIT_SHA1_HEXSZ or GIT_MAX_HEXSZ the right call here?

On Tue, Aug 15, 2017 at 4:49 AM, Patryk Obara [off-list ref] wrote:

Here is a good place to explain why this is a good patch,
(which is not immediately obvious to me at least).

On Tue, Aug 15, 2017 at 4:49 AM, Patryk Obara [off-list ref] wrote:

Oh patch 4/5 could just say it's in preparation of this patch.
Nevermind the comment on patch 4.

On Tue, Aug 15, 2017 at 4:49 AM, Patryk Obara [off-list ref] wrote:

Welcome (back?) to the git mailing list!

I experimented with using a different hash algorithm (I am aware of
existing "Git hash function transition plan", I just want to push
things forward a bit) - and immediately hit a small issue - changing
the size of object_id hash buffer leads to compilation issues and
breaks graft-related tests.

Thanks for advancing this frontier. :)

I am sending patch 1 only to show a modification, that I did to
increase buffer size - it's not intended to be merged.

Patch 2 fixes trivial compilation issue.

Patches 3, 4, and 5 touch graft implementation to remove calculations
using GIT_SHA1_*, that lead to broken tests. I replaced FLEX_ARRAY of
object_id's representing parents with oid_array. New implementation
should be more future-proof, I think.

I would think so, too.

parse_oid_hex currently only reads sha1, but once it can read a new
hash (or both old and new hash), it would solve the graft problems.

New implementation has tiny behaviour change: previously parents in
graft line needed to be separated with single space - now any number
of whitespace characters will do.

Yeah that is because of parse_next_oid_hex in patch 5 is pretty smart
(and if we'd want to preserve behavior we'd need to just skip one SP
and in case of more SP "goto bad_graft_data" that is in the
caller function.

Alternative implementation approaches
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Strbuf could be replaced with string_list with
string_list_split_in_place instead of while loop in read_graft_line.
I didn't implement it this way because I learned
about string_list_split_in_place after finishing this implementation
draft. Right now I'm not sure which approach is better.

Another possibility is dropping graft feature altogether - that would
mean removing code for parsing grafts and 'parent' field in the struct,
but preserving the struct itself as a shallow clone marker. Grafts are
a little-known feature with modern replacement, but this seems like
bigger task and rather out of the scope of transition to the new
hashing algorithm.

I considered making function read_graft_line a static one and
read_graft_file non-static, but read_graft_line is used in
'builtin/blame.c' in function read_ancestry, which is almost a copy of
read_graft_file (difference of single boolean flag passed to
register_commit_graft). Removal of this duplication may be worthwhile,
but I think it's out of scope.

I think the grafts may be still in use in Linux, to fault in the
history before git was used, which cannot be replaced by the
shallow mechanism.

Thanks for the patches 2-5!

Stefan

On Tue, Aug 15, 2017 at 7:02 PM, Stefan Beller [off-list ref] wrote:

quoted

        const int entry_size = GIT_SHA1_HEXSZ + 1;

outside the scope of this patch:
Is GIT_SHA1_HEXSZ or GIT_MAX_HEXSZ the right call here?

I think neither one. In my opinion, this code should not be so closely
coupled to hash parsing code - it should be tasked with parsing
whitespace separated list of commit ids without relying on specific
commit id length or format.

-- 
| ← Ceci n'est pas une pipe
Patryk Obara

Compared to v1:
- the first patch is dropped to make it easier to merge
- free_graft is now static function in commit.c

I don't know, what are exact rules about adding Reviewed-by footer, so
I didn't add any.


Patryk Obara (4):
  sha1_file: fix hardcoded size in null_sha1
  commit: replace the raw buffer with strbuf in read_graft_line
  commit: implement free_commit_graft
  commit: rewrite read_graft_line

 builtin/blame.c |  2 +-
 commit.c        | 55 ++++++++++++++++++++++++++++++++-----------------------
 commit.h        |  4 ++--
 sha1_file.c     |  2 +-
 shallow.c       |  1 +
 5 files changed, 37 insertions(+), 27 deletions(-)

-- 
2.9.5

This prevents compilation error if GIT_MAX_RAWSZ is different than 20.

Signed-off-by: Patryk Obara <redacted>
---
 sha1_file.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sha1_file.c b/sha1_file.c
index b60ae15..f5b5bec 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -32,7 +32,7 @@
 #define SZ_FMT PRIuMAX
 static inline uintmax_t sz_fmt(size_t s) { return s; }
 
-const unsigned char null_sha1[20];
+const unsigned char null_sha1[GIT_MAX_RAWSZ];
 const struct object_id null_oid;
 const struct object_id empty_tree_oid = {
 	EMPTY_TREE_SHA1_BIN_LITERAL

-- 
2.9.5

In preparation for new graft struct version introduced in next commit.

Signed-off-by: Patryk Obara <redacted>
---
 commit.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/commit.c b/commit.c
index 499fb14..4d23e72 100644
--- a/commit.c
+++ b/commit.c

@@ -109,15 +109,20 @@ static int commit_graft_pos(const unsigned char *sha1)
 			commit_graft_sha1_access);
 }
 
+static void free_commit_graft(struct commit_graft *graft)
+{
+	free(graft);
+}
+
 int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 {
 	int pos = commit_graft_pos(graft->oid.hash);
 
 	if (0 <= pos) {
 		if (ignore_dups)
-			free(graft);
+			free_commit_graft(graft);
 		else {
-			free(commit_graft[pos]);
+			free_commit_graft(commit_graft[pos]);
 			commit_graft[pos] = graft;
 		}
 		return 1;

@@ -163,7 +168,7 @@ struct commit_graft *read_graft_line(struct strbuf *line)
 
 bad_graft_data:
 	error("bad graft data: %s", buf);
-	free(graft);
+	free_commit_graft(graft);
 	return NULL;
 }
 

-- 
2.9.5

This simplifies function declaration and allows for use of strbuf_rtrim
instead of modifying buffer directly.

Signed-off-by: Patryk Obara <redacted>
---
 builtin/blame.c |  2 +-
 commit.c        | 11 ++++++-----
 commit.h        |  2 +-
 3 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/builtin/blame.c b/builtin/blame.c
index bda1a78..d4472e9 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c

@@ -488,7 +488,7 @@ static int read_ancestry(const char *graft_file)
 		return -1;
 	while (!strbuf_getwholeline(&buf, fp, '\n')) {
 		/* The format is just "Commit Parent1 Parent2 ...\n" */
-		struct commit_graft *graft = read_graft_line(buf.buf, buf.len);
+		struct commit_graft *graft = read_graft_line(&buf);
 		if (graft)
 			register_commit_graft(graft, 0);
 	}

diff --git a/commit.c b/commit.c
index 8b28415..499fb14 100644
--- a/commit.c
+++ b/commit.c

@@ -134,15 +134,16 @@ int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 	return 0;
 }
 
-struct commit_graft *read_graft_line(char *buf, int len)
+struct commit_graft *read_graft_line(struct strbuf *line)
 {
 	/* The format is just "Commit Parent1 Parent2 ...\n" */
-	int i;
+	int i, len;
+	char *buf = line->buf;
 	struct commit_graft *graft = NULL;
 	const int entry_size = GIT_SHA1_HEXSZ + 1;
 
-	while (len && isspace(buf[len-1]))
-		buf[--len] = '\0';
+	strbuf_rtrim(line);
+	len = line->len;
 	if (buf[0] == '#' || buf[0] == '\0')
 		return NULL;
 	if ((len + 1) % entry_size)

@@ -174,7 +175,7 @@ static int read_graft_file(const char *graft_file)
 		return -1;
 	while (!strbuf_getwholeline(&buf, fp, '\n')) {
 		/* The format is just "Commit Parent1 Parent2 ...\n" */
-		struct commit_graft *graft = read_graft_line(buf.buf, buf.len);
+		struct commit_graft *graft = read_graft_line(&buf);
 		if (!graft)
 			continue;
 		if (register_commit_graft(graft, 1))

diff --git a/commit.h b/commit.h
index 6d857f0..baecc0a 100644
--- a/commit.h
+++ b/commit.h

@@ -247,7 +247,7 @@ struct commit_graft {
 };
 typedef int (*each_commit_graft_fn)(const struct commit_graft *, void *);
 
-struct commit_graft *read_graft_line(char *buf, int len);
+struct commit_graft *read_graft_line(struct strbuf *line);
 int register_commit_graft(struct commit_graft *, int);
 struct commit_graft *lookup_commit_graft(const struct object_id *oid);
 

-- 
2.9.5

The previous implementation of read_graft_line used calculations based
on GIT_SHA1_RAWSZ and GIT_SHA1_HEXSZ to determine the number of commit
ids in a single graft line.  New implementation does not depend on these
constants, so it adapts to any object_id buffer size.

To make this possible, FLEX_ARRAY of object_id in struct was replaced
by an oid_array.

Code allocating graft now needs to use memset to zero the memory before
use to start with oid_array in a consistent state.

Updates free_graft function implemented in the previous patch to
properly cleanup an oid_array storing parents.

Signed-off-by: Patryk Obara <redacted>
---
 commit.c  | 39 +++++++++++++++++++++------------------
 commit.h  |  2 +-
 shallow.c |  1 +
 3 files changed, 23 insertions(+), 19 deletions(-)

diff --git a/commit.c b/commit.c
index 4d23e72..8bdce36 100644
--- a/commit.c
+++ b/commit.c

@@ -111,6 +111,7 @@ static int commit_graft_pos(const unsigned char *sha1)
 
 static void free_commit_graft(struct commit_graft *graft)
 {
+	oid_array_clear(&graft->parents);
 	free(graft);
 }
 

@@ -139,35 +140,37 @@ int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 	return 0;
 }
 
+static int parse_next_oid_hex(const char *buf, struct object_id *oid, const char **end)
+{
+	while (isspace(buf[0]))
+		buf++;
+	return parse_oid_hex(buf, oid, end);
+}
+
 struct commit_graft *read_graft_line(struct strbuf *line)
 {
 	/* The format is just "Commit Parent1 Parent2 ...\n" */
-	int i, len;
-	char *buf = line->buf;
 	struct commit_graft *graft = NULL;
-	const int entry_size = GIT_SHA1_HEXSZ + 1;
+	struct object_id oid;
+	const char *tail = NULL;
 
 	strbuf_rtrim(line);
-	len = line->len;
-	if (buf[0] == '#' || buf[0] == '\0')
+	if (line->buf[0] == '#' || line->len == 0)
 		return NULL;
-	if ((len + 1) % entry_size)
+	graft = xmalloc(sizeof(*graft));
+	memset(graft, 0, sizeof(*graft));
+	if (parse_oid_hex(line->buf, &graft->oid, &tail))
 		goto bad_graft_data;
-	i = (len + 1) / entry_size - 1;
-	graft = xmalloc(st_add(sizeof(*graft), st_mult(GIT_SHA1_RAWSZ, i)));
-	graft->nr_parent = i;
-	if (get_oid_hex(buf, &graft->oid))
+	while (!parse_next_oid_hex(tail, &oid, &tail))
+		oid_array_append(&graft->parents, &oid);
+	if (tail[0] != '\0')
 		goto bad_graft_data;
-	for (i = GIT_SHA1_HEXSZ; i < len; i += entry_size) {
-		if (buf[i] != ' ')
-			goto bad_graft_data;
-		if (get_sha1_hex(buf + i + 1, graft->parent[i/entry_size].hash))
-			goto bad_graft_data;
-	}
+	graft->nr_parent = graft->parents.nr;
+
 	return graft;
 
 bad_graft_data:
-	error("bad graft data: %s", buf);
+	error("bad graft data: %s", line->buf);
 	free_commit_graft(graft);
 	return NULL;
 }

@@ -363,7 +366,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 		int i;
 		struct commit *new_parent;
 		for (i = 0; i < graft->nr_parent; i++) {
-			new_parent = lookup_commit(&graft->parent[i]);
+			new_parent = lookup_commit(&graft->parents.oid[i]);
 			if (!new_parent)
 				continue;
 			pptr = &commit_list_insert(new_parent, pptr)->next;

diff --git a/commit.h b/commit.h
index baecc0a..96ff375 100644
--- a/commit.h
+++ b/commit.h

@@ -243,7 +243,7 @@ void sort_in_topological_order(struct commit_list **, enum rev_sort_order);
 struct commit_graft {
 	struct object_id oid;
 	int nr_parent; /* < 0 if shallow commit */
-	struct object_id parent[FLEX_ARRAY]; /* more */
+	struct oid_array parents;
 };
 typedef int (*each_commit_graft_fn)(const struct commit_graft *, void *);
 

diff --git a/shallow.c b/shallow.c
index f5591e5..892cd90 100644
--- a/shallow.c
+++ b/shallow.c

@@ -33,6 +33,7 @@ int register_shallow(const struct object_id *oid)
 		xmalloc(sizeof(struct commit_graft));
 	struct commit *commit = lookup_commit(oid);
 
+	memset(graft, 0, sizeof(*graft));
 	oidcpy(&graft->oid, oid);
 	graft->nr_parent = -1;
 	if (commit && commit->object.parsed)

-- 
2.9.5

On Wed, Aug 16, 2017 at 02:24:27PM +0200, Patryk Obara wrote:

On Tue, Aug 15, 2017 at 7:02 PM, Stefan Beller [off-list ref] wrote:

quoted

quoted

        const int entry_size = GIT_SHA1_HEXSZ + 1;

outside the scope of this patch:
Is GIT_SHA1_HEXSZ or GIT_MAX_HEXSZ the right call here?

I think neither one. In my opinion, this code should not be so closely
coupled to hash parsing code - it should be tasked with parsing
whitespace separated list of commit ids without relying on specific
commit id length or format.

What I had intended, although maybe I have not explained this well, was
that we would have one binary that set up hash functionality as part of
early setup.  GIT_SHA1_RAWSZ and GIT_SHA1_HEXSZ would turn into
something like current_hash->rawsz and current_hash->hexsz at that
point.  The reason I introduced the GIT_MAX constants was to allocate
memory suitable for whatever hash we picked.

However, this is only what I had considered for design, and others might
have different views going forward.  I have, however, based my patches
on that assumption, and responded to others' comments with those
statements.

I agree that ideally we should make as much of the code as possible
ignorant of the hash size, because that will generally result in more
robust, less brittle code.  I've noticed in this series the use of
parse_oid_hex, and I agree that's one tool we can use to accomplish that
goal.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

On Wed, Aug 16, 2017 at 10:59:02PM +0000, brian m. carlson wrote:

On Wed, Aug 16, 2017 at 02:24:27PM +0200, Patryk Obara wrote:

quoted

On Tue, Aug 15, 2017 at 7:02 PM, Stefan Beller [off-list ref] wrote:

quoted

quoted

        const int entry_size = GIT_SHA1_HEXSZ + 1;

outside the scope of this patch:
Is GIT_SHA1_HEXSZ or GIT_MAX_HEXSZ the right call here?

I think neither one. In my opinion, this code should not be so closely
coupled to hash parsing code - it should be tasked with parsing
whitespace separated list of commit ids without relying on specific
commit id length or format.

What I had intended, although maybe I have not explained this well, was
that we would have one binary that set up hash functionality as part of
early setup.  GIT_SHA1_RAWSZ and GIT_SHA1_HEXSZ would turn into
something like current_hash->rawsz and current_hash->hexsz at that
point.  The reason I introduced the GIT_MAX constants was to allocate
memory suitable for whatever hash we picked.

However, this is only what I had considered for design, and others might
have different views going forward.  I have, however, based my patches
on that assumption, and responded to others' comments with those
statements.

What you wrote here matches my understanding of the general plan. IOW,
we'd expect to "waste" 12 bytes when dealing with a 160-bit sha1 in a
Git binary that's aware of 256-bit hashes. But that seems like a small
price to pay to be able to continue using automatic allocations, versus
rewriting each site to call xmalloc(current_hash->rawsz).

I'd expect most of the GIT_MAX constants to eventually go away in favor
of "struct object_id", but that will still be using the same "big enough
to hold any hash" size under the hood.

I agree that ideally we should make as much of the code as possible
ignorant of the hash size, because that will generally result in more
robust, less brittle code.  I've noticed in this series the use of
parse_oid_hex, and I agree that's one tool we can use to accomplish that
goal.

Agreed. Most code should be dealing with the abstract concept of a hash
and shouldn't have to care about the size. I really like parse_oid_hex()
for that reason (and I think parsing is the main place we've found that
needs to care).

-Peff

Changes since v2:
- commit implementing free_graft dropped (no longer needed)
- several more lines moved from last commit to commit replacing
  raw buffer with strbuf
- fix for memory allocation separated from change in hash
  parsing
- commit_graft struct uses FLEX_ARRAY again, meaning free_graft,
  memset, nor oid_array were not needed after all

Patryk Obara (4):
  sha1_file: fix definition of null_sha1
  commit: replace the raw buffer with strbuf in read_graft_line
  commit: allocate array using object_id size
  commit: rewrite read_graft_line

 builtin/blame.c |  2 +-
 commit.c        | 38 +++++++++++++++++++-------------------
 commit.h        |  2 +-
 sha1_file.c     |  2 +-
 4 files changed, 22 insertions(+), 22 deletions(-)

-- 
2.9.5

base-commit: b3622a4ee94e4916cd05e6d96e41eeb36b941182

This simplifies function declaration and allows for use of strbuf_rtrim
instead of modifying buffer directly.

Signed-off-by: Patryk Obara <redacted>
---
 builtin/blame.c |  2 +-
 commit.c        | 15 ++++++++-------
 commit.h        |  2 +-
 3 files changed, 10 insertions(+), 9 deletions(-)

diff --git a/builtin/blame.c b/builtin/blame.c
index bda1a78..d4472e9 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c

@@ -488,7 +488,7 @@ static int read_ancestry(const char *graft_file)
 		return -1;
 	while (!strbuf_getwholeline(&buf, fp, '\n')) {
 		/* The format is just "Commit Parent1 Parent2 ...\n" */
-		struct commit_graft *graft = read_graft_line(buf.buf, buf.len);
+		struct commit_graft *graft = read_graft_line(&buf);
 		if (graft)
 			register_commit_graft(graft, 0);
 	}

diff --git a/commit.c b/commit.c
index 8b28415..019e733 100644
--- a/commit.c
+++ b/commit.c

@@ -134,17 +134,18 @@ int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 	return 0;
 }
 
-struct commit_graft *read_graft_line(char *buf, int len)
+struct commit_graft *read_graft_line(struct strbuf *line)
 {
 	/* The format is just "Commit Parent1 Parent2 ...\n" */
-	int i;
+	int i, len;
+	char *buf = line->buf;
 	struct commit_graft *graft = NULL;
 	const int entry_size = GIT_SHA1_HEXSZ + 1;
 
-	while (len && isspace(buf[len-1]))
-		buf[--len] = '\0';
-	if (buf[0] == '#' || buf[0] == '\0')
+	strbuf_rtrim(line);
+	if (line->buf[0] == '#' || line->len == 0)
 		return NULL;
+	len = line->len;
 	if ((len + 1) % entry_size)
 		goto bad_graft_data;
 	i = (len + 1) / entry_size - 1;

@@ -161,7 +162,7 @@ struct commit_graft *read_graft_line(char *buf, int len)
 	return graft;
 
 bad_graft_data:
-	error("bad graft data: %s", buf);
+	error("bad graft data: %s", line->buf);
 	free(graft);
 	return NULL;
 }

@@ -174,7 +175,7 @@ static int read_graft_file(const char *graft_file)
 		return -1;
 	while (!strbuf_getwholeline(&buf, fp, '\n')) {
 		/* The format is just "Commit Parent1 Parent2 ...\n" */
-		struct commit_graft *graft = read_graft_line(buf.buf, buf.len);
+		struct commit_graft *graft = read_graft_line(&buf);
 		if (!graft)
 			continue;
 		if (register_commit_graft(graft, 1))

diff --git a/commit.h b/commit.h
index 6d857f0..baecc0a 100644
--- a/commit.h
+++ b/commit.h

@@ -247,7 +247,7 @@ struct commit_graft {
 };
 typedef int (*each_commit_graft_fn)(const struct commit_graft *, void *);
 
-struct commit_graft *read_graft_line(char *buf, int len);
+struct commit_graft *read_graft_line(struct strbuf *line);
 int register_commit_graft(struct commit_graft *, int);
 struct commit_graft *lookup_commit_graft(const struct object_id *oid);
 

-- 
2.9.5

The array is declared in cache.h as:

  extern const unsigned char null_sha1[GIT_MAX_RAWSZ];

Definition in sha1_file.c must match.

Signed-off-by: Patryk Obara <redacted>
---
 sha1_file.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sha1_file.c b/sha1_file.c
index b60ae15..f5b5bec 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -32,7 +32,7 @@
 #define SZ_FMT PRIuMAX
 static inline uintmax_t sz_fmt(size_t s) { return s; }
 
-const unsigned char null_sha1[20];
+const unsigned char null_sha1[GIT_MAX_RAWSZ];
 const struct object_id null_oid;
 const struct object_id empty_tree_oid = {
 	EMPTY_TREE_SHA1_BIN_LITERAL

-- 
2.9.5

Determine the number of object_id's to parse in a single graft line by
counting separators (whitespace characters) instead of dividing by
length of hash representation.

This way graft parsing code can support different sizes of hashes
without any further code adaptations.

Signed-off-by: Patryk Obara <redacted>
---
 commit.c | 28 +++++++++++++---------------
 1 file changed, 13 insertions(+), 15 deletions(-)

diff --git a/commit.c b/commit.c
index 61528a5..46ee2db 100644
--- a/commit.c
+++ b/commit.c

@@ -137,29 +137,27 @@ int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 struct commit_graft *read_graft_line(struct strbuf *line)
 {
 	/* The format is just "Commit Parent1 Parent2 ...\n" */
-	int i, len;
-	char *buf = line->buf;
+	int i, n;
+	const char *tail = NULL;
 	struct commit_graft *graft = NULL;
-	const int entry_size = GIT_SHA1_HEXSZ + 1;
 
 	strbuf_rtrim(line);
 	if (line->buf[0] == '#' || line->len == 0)
 		return NULL;
-	len = line->len;
-	if ((len + 1) % entry_size)
-		goto bad_graft_data;
-	i = (len + 1) / entry_size - 1;
+	/* count number of blanks to determine size of array to allocate */
+	for (i = 0, n = 0; i < line->len; i++)
+		if (isspace(line->buf[i]))
+			n++;
 	graft = xmalloc(st_add(sizeof(*graft),
-	                       st_mult(sizeof(struct object_id), i)));
-	graft->nr_parent = i;
-	if (get_oid_hex(buf, &graft->oid))
+	                       st_mult(sizeof(struct object_id), n)));
+	graft->nr_parent = n;
+	if (parse_oid_hex(line->buf, &graft->oid, &tail))
 		goto bad_graft_data;
-	for (i = GIT_SHA1_HEXSZ; i < len; i += entry_size) {
-		if (buf[i] != ' ')
-			goto bad_graft_data;
-		if (get_sha1_hex(buf + i + 1, graft->parent[i/entry_size].hash))
+	for (i = 0; i < graft->nr_parent; i++)
+		if (!isspace(*tail++) || parse_oid_hex(tail, &graft->parent[i], &tail))
 			goto bad_graft_data;
-	}
+	if (tail[0] != '\0')
+		goto bad_graft_data;
 	return graft;
 
 bad_graft_data:

-- 
2.9.5

struct commit_graft aggregates an array of object_id's, which have
size >= GIT_MAX_RAWSZ bytes. This change prevents memory allocation
error when size of object_id is larger than GIT_SHA1_RAWSZ.

Signed-off-by: Patryk Obara <redacted>
---
 commit.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/commit.c b/commit.c
index 019e733..61528a5 100644
--- a/commit.c
+++ b/commit.c

@@ -149,7 +149,8 @@ struct commit_graft *read_graft_line(struct strbuf *line)
 	if ((len + 1) % entry_size)
 		goto bad_graft_data;
 	i = (len + 1) / entry_size - 1;
-	graft = xmalloc(st_add(sizeof(*graft), st_mult(GIT_SHA1_RAWSZ, i)));
+	graft = xmalloc(st_add(sizeof(*graft),
+	                       st_mult(sizeof(struct object_id), i)));
 	graft->nr_parent = i;
 	if (get_oid_hex(buf, &graft->oid))
 		goto bad_graft_data;

-- 
2.9.5

On Fri, Aug 18, 2017 at 03:59:36AM +0200, Patryk Obara wrote:

Copying a pointer to a strbuf's buffer is a dangerous habit. The strbuf
is free to re-allocate the buffer under the hood during any operation it
likes, potentially leaving you pointing to freed memory.

In this case it's OK because the only function you call is
strbuf_rtrim(), which never reallocates. But I feel like this is setting
up a maintenance trap for the next person to touch the function.

AFAICT this is only here to avoid having to s/buf/line->buf/ in the rest
of the function. But I think we should just make that change (you
already did in some of the spots). And IMHO we should do the same for
line->len. When there are two names for the same value, it increases the
chances of a bug where the two end up diverging.

-	while (len && isspace(buf[len-1]))
-		buf[--len] = '\0';
-	if (buf[0] == '#' || buf[0] == '\0')
+	strbuf_rtrim(line);
+	if (line->buf[0] == '#' || line->len == 0)
 		return NULL;

I find it funny to look at line->buf[0] before line->len, because it
means we're reading pas the end of the buffer. It's OK here because we
know there's a NUL terminator, but I think short-circuiting like:

  if (!line->len || line->buf[0] == '#')

is better (I also think "!" instead of "== 0" is our usual style, but
that's much less important).

-Peff

On Fri, Aug 18, 2017 at 03:59:38AM +0200, Patryk Obara wrote:

Determine the number of object_id's to parse in a single graft line by
counting separators (whitespace characters) instead of dividing by
length of hash representation.

This way graft parsing code can support different sizes of hashes
without any further code adaptations.

Sounds like a reasonable approach, though I wonder what happens if our
counting pass differs in its behavior from the actual parse.

E.g., here:

+	/* count number of blanks to determine size of array to allocate */
+	for (i = 0, n = 0; i < line->len; i++)
+		if (isspace(line->buf[i]))
+			n++;

If we see multiple spaces like "1234abcd     5678abcd" we'll allocate a
slot for each. I think that's OK because here:

+	for (i = 0; i < graft->nr_parent; i++)
+		if (!isspace(*tail++) || parse_oid_hex(tail, &graft->parent[i], &tail))
 			goto bad_graft_data;

We'd reject such an input totally (though as an interesting side effect,
you can convince the parser to allocate 20x as much RAM as you send it;
one oid for each space).

So we're probably fine. The two parsing passes are right next to each
other and are sufficiently simple and strict that we don't have to
worry about them diverging.

The single-pass alternative would probably be to read into a dynamic
structure like an oid_array, and then copy the result into the flex
structure.

Or of course to stop using a flex structure, as your original pass did.
I agree with Junio that the use of object_id's is orthogonal to using a
FLEX_ARRAY. But I could also see an argument that the complexity the
flex array adds here isn't worth the savings. The main benefits of a
flex array are:

  1. Less memory used. But we don't expect to see a large enough number
     of grafts for this to matter.

  2. A more compact memory representation, which can be faster. But
     accessing the parent list of a graft isn't going to be the hot code
     path. It probably only happens once in a program run when we
     rewrite the parents (versus checking the grafted commit, which is
     looked up once per commit we access).

  3. It's easier to free the struct and its associated resources in a
     single free(). But we never free the graft list.

Reading your original, my thought was "why _not_ keep doing it as a
FLEX_ARRAY, as it saves a little memory, which can't hurt". But seeing
this pre-counting phase, I think it does make the code a little more
complicated. But I'd be OK with doing it either way.

-Peff

Jeff King [off-list ref] wrote:

AFAICT this is only here to avoid having to s/buf/line->buf/ in the rest
of the function. But I think we should just make that change (you
already did in some of the spots). And IMHO we should do the same for
line->len. When there are two names for the same value, it increases the
chances of a bug where the two end up diverging.

My motivation was rather to keep patch(es) as small as possible because every
line using buf will be replaced in a later patch in series. But it will make
commit better (it will stand on its own), so why not to do it? :)

(…) I think short-circuiting like:

  if (!line->len || line->buf[0] == '#')

is better (I also think "!" instead of "== 0" is our usual style, but
that's much less important).

Ah, I only replaced comparison to NULL terminator with length check because
I thought it better shows intention of the code and I didn't notice, that
reversing order will result in better code overall.

I will include both changes in v4.

-- 
| ← Ceci n'est pas une pipe
Patryk Obara

On Fri, Aug 18, 2017 at 12:12:37PM +0200, Patryk Obara wrote:

Jeff King [off-list ref] wrote:

quoted

AFAICT this is only here to avoid having to s/buf/line->buf/ in the rest
of the function. But I think we should just make that change (you
already did in some of the spots). And IMHO we should do the same for
line->len. When there are two names for the same value, it increases the
chances of a bug where the two end up diverging.

My motivation was rather to keep patch(es) as small as possible because every
line using buf will be replaced in a later patch in series. But it will make
commit better (it will stand on its own), so why not to do it? :)

Ah, I didn't notice those lines went away. That does make it less bad,
but I do think it's easier to review if each commit stands on its own.

In some cases, if it's really painful to do the intermediate cleanup, I
might say something in the commit message like "this leaves X that is
not ideal, but we'll be getting rid of it soon anyway". But in this case
I think just creating that intermediate state is simple enough.

Ah, I only replaced comparison to NULL terminator with length check because
I thought it better shows intention of the code and I didn't notice, that
reversing order will result in better code overall.

I will include both changes in v4.

Thanks.

-Peff

Changes since v3:

- Commit replacing raw buffer does not store temporary pointer to
  strbuf internals any more.

- Commit message of patch 4 explains all alternative approaches
  considered so far.

- Patch 4 uses two-phases to parse graft line, without code repetition.

I have my reservations about patch 4 from readability standpoint
(it's not immediately clear why parsing code can skip freeing of graft
in phase 2), but this implementation seems to address every issue raised
in review so far. If you'll prefer me to go back to impementation
from v3, I have it prepared ;)


Patryk Obara (4):
  sha1_file: fix definition of null_sha1
  commit: replace the raw buffer with strbuf in read_graft_line
  commit: allocate array using object_id size
  commit: rewrite read_graft_line

 builtin/blame.c |  2 +-
 commit.c        | 45 +++++++++++++++++++++++++--------------------
 commit.h        |  2 +-
 sha1_file.c     |  2 +-
 4 files changed, 28 insertions(+), 23 deletions(-)

-- 
2.9.5

This simplifies function declaration and allows for use of strbuf_rtrim
instead of modifying buffer directly.

Signed-off-by: Patryk Obara <redacted>
---
 builtin/blame.c |  2 +-
 commit.c        | 23 +++++++++++------------
 commit.h        |  2 +-
 3 files changed, 13 insertions(+), 14 deletions(-)

diff --git a/builtin/blame.c b/builtin/blame.c
index bda1a78..d4472e9 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c

@@ -488,7 +488,7 @@ static int read_ancestry(const char *graft_file)
 		return -1;
 	while (!strbuf_getwholeline(&buf, fp, '\n')) {
 		/* The format is just "Commit Parent1 Parent2 ...\n" */
-		struct commit_graft *graft = read_graft_line(buf.buf, buf.len);
+		struct commit_graft *graft = read_graft_line(&buf);
 		if (graft)
 			register_commit_graft(graft, 0);
 	}

diff --git a/commit.c b/commit.c
index 8b28415..1a0a9f2 100644
--- a/commit.c
+++ b/commit.c

@@ -134,34 +134,33 @@ int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 	return 0;
 }
 
-struct commit_graft *read_graft_line(char *buf, int len)
+struct commit_graft *read_graft_line(struct strbuf *line)
 {
 	/* The format is just "Commit Parent1 Parent2 ...\n" */
 	int i;
 	struct commit_graft *graft = NULL;
 	const int entry_size = GIT_SHA1_HEXSZ + 1;
 
-	while (len && isspace(buf[len-1]))
-		buf[--len] = '\0';
-	if (buf[0] == '#' || buf[0] == '\0')
+	strbuf_rtrim(line);
+	if (!line->len || line->buf[0] == '#')
 		return NULL;
-	if ((len + 1) % entry_size)
+	if ((line->len + 1) % entry_size)
 		goto bad_graft_data;
-	i = (len + 1) / entry_size - 1;
+	i = (line->len + 1) / entry_size - 1;
 	graft = xmalloc(st_add(sizeof(*graft), st_mult(GIT_SHA1_RAWSZ, i)));
 	graft->nr_parent = i;
-	if (get_oid_hex(buf, &graft->oid))
+	if (get_oid_hex(line->buf, &graft->oid))
 		goto bad_graft_data;
-	for (i = GIT_SHA1_HEXSZ; i < len; i += entry_size) {
-		if (buf[i] != ' ')
+	for (i = GIT_SHA1_HEXSZ; i < line->len; i += entry_size) {
+		if (line->buf[i] != ' ')
 			goto bad_graft_data;
-		if (get_sha1_hex(buf + i + 1, graft->parent[i/entry_size].hash))
+		if (get_sha1_hex(line->buf + i + 1, graft->parent[i/entry_size].hash))
 			goto bad_graft_data;
 	}
 	return graft;
 
 bad_graft_data:
-	error("bad graft data: %s", buf);
+	error("bad graft data: %s", line->buf);
 	free(graft);
 	return NULL;
 }

@@ -174,7 +173,7 @@ static int read_graft_file(const char *graft_file)
 		return -1;
 	while (!strbuf_getwholeline(&buf, fp, '\n')) {
 		/* The format is just "Commit Parent1 Parent2 ...\n" */
-		struct commit_graft *graft = read_graft_line(buf.buf, buf.len);
+		struct commit_graft *graft = read_graft_line(&buf);
 		if (!graft)
 			continue;
 		if (register_commit_graft(graft, 1))

diff --git a/commit.h b/commit.h
index 6d857f0..baecc0a 100644
--- a/commit.h
+++ b/commit.h

@@ -247,7 +247,7 @@ struct commit_graft {
 };
 typedef int (*each_commit_graft_fn)(const struct commit_graft *, void *);
 
-struct commit_graft *read_graft_line(char *buf, int len);
+struct commit_graft *read_graft_line(struct strbuf *line);
 int register_commit_graft(struct commit_graft *, int);
 struct commit_graft *lookup_commit_graft(const struct object_id *oid);
 

-- 
2.9.5

Old implementation determined number of hashes by dividing length of
line by length of hash, which works only if all hash representations
have same length.

New graft line parser works in two phases:

  1. In first phase line is scanned to verify correctness and compute
     number of hashes, then graft struct is allocated.

  2. In second phase line is scanned again to fill up already allocated
     graft struct.

This way graft parsing code can support different sizes of hashes
without any further code adaptations.

A number of alternative implementations were considered and discarded:

  - Modifying graft structure to store oid_array instead of FLEXI_ARRAY
    indicates undesirable usage of struct to readers.

  - Parsing into temporary string_list or oid_array complicates code
    by adding more return paths, as these structures needs to be
    cleared before returning from function.

  - Determining number of hashes by counting separators might cause
    maintenance issues, if this function needs to be modified in future
    again.

Signed-off-by: Patryk Obara <redacted>
---
 commit.c | 35 ++++++++++++++++++++---------------
 1 file changed, 20 insertions(+), 15 deletions(-)

diff --git a/commit.c b/commit.c
index 436eb34..3eefd9d 100644
--- a/commit.c
+++ b/commit.c

@@ -137,32 +137,37 @@ int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 struct commit_graft *read_graft_line(struct strbuf *line)
 {
 	/* The format is just "Commit Parent1 Parent2 ...\n" */
-	int i;
+	int i, phase;
+	const char *tail = NULL;
 	struct commit_graft *graft = NULL;
-	const int entry_size = GIT_SHA1_HEXSZ + 1;
+	struct object_id dummy_oid, *oid;
 
 	strbuf_rtrim(line);
 	if (!line->len || line->buf[0] == '#')
 		return NULL;
-	if ((line->len + 1) % entry_size)
-		goto bad_graft_data;
-	i = (line->len + 1) / entry_size - 1;
-	graft = xmalloc(st_add(sizeof(*graft),
-	                       st_mult(sizeof(struct object_id), i)));
-	graft->nr_parent = i;
-	if (get_oid_hex(line->buf, &graft->oid))
-		goto bad_graft_data;
-	for (i = GIT_SHA1_HEXSZ; i < line->len; i += entry_size) {
-		if (line->buf[i] != ' ')
-			goto bad_graft_data;
-		if (get_sha1_hex(line->buf + i + 1, graft->parent[i/entry_size].hash))
+	/*
+	 * phase 0 verifies line, counts hashes in line and allocates graft
+	 * phase 1 fills graft
+	 */
+	for (phase = 0; phase < 2; phase++) {
+		oid = graft ? &graft->oid : &dummy_oid;
+		if (parse_oid_hex(line->buf, oid, &tail))
 			goto bad_graft_data;
+		for (i = 0; *tail != '\0'; i++) {
+			oid = graft ? &graft->parent[i] : &dummy_oid;
+			if (!isspace(*tail++) || parse_oid_hex(tail, oid, &tail))
+				goto bad_graft_data;
+		}
+		if (!graft) {
+			graft = xmalloc(st_add(sizeof(*graft),
+			                       st_mult(sizeof(struct object_id), i)));
+			graft->nr_parent = i;
+		}
 	}
 	return graft;
 
 bad_graft_data:
 	error("bad graft data: %s", line->buf);
-	free(graft);
 	return NULL;
 }
 

-- 
2.9.5

The array is declared in cache.h as:

  extern const unsigned char null_sha1[GIT_MAX_RAWSZ];

Definition in sha1_file.c must match.

Signed-off-by: Patryk Obara <redacted>
---
 sha1_file.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sha1_file.c b/sha1_file.c
index b60ae15..f5b5bec 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -32,7 +32,7 @@
 #define SZ_FMT PRIuMAX
 static inline uintmax_t sz_fmt(size_t s) { return s; }
 
-const unsigned char null_sha1[20];
+const unsigned char null_sha1[GIT_MAX_RAWSZ];
 const struct object_id null_oid;
 const struct object_id empty_tree_oid = {
 	EMPTY_TREE_SHA1_BIN_LITERAL

-- 
2.9.5

struct commit_graft aggregates an array of object_id's, which have
size >= GIT_MAX_RAWSZ bytes. This change prevents memory allocation
error when size of object_id is larger than GIT_SHA1_RAWSZ.

Signed-off-by: Patryk Obara <redacted>
---
 commit.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/commit.c b/commit.c
index 1a0a9f2..436eb34 100644
--- a/commit.c
+++ b/commit.c

@@ -147,7 +147,8 @@ struct commit_graft *read_graft_line(struct strbuf *line)
 	if ((line->len + 1) % entry_size)
 		goto bad_graft_data;
 	i = (line->len + 1) / entry_size - 1;
-	graft = xmalloc(st_add(sizeof(*graft), st_mult(GIT_SHA1_RAWSZ, i)));
+	graft = xmalloc(st_add(sizeof(*graft),
+	                       st_mult(sizeof(struct object_id), i)));
 	graft->nr_parent = i;
 	if (get_oid_hex(line->buf, &graft->oid))
 		goto bad_graft_data;

-- 
2.9.5

Actually, I don't think I needed to remove free(graft) line, but I don't
know if freeing NULL is considered ok in git code. Let me know if I
should bring it back, please.

-- 
| ← Ceci n'est pas une pipe
Patryk Obara