{"thread":{"id":"44259","subject":"[PATCH v1 2/2] convert.c: stream and early out","startedAt":"2016-10-09T09:57:47Z","lastAt":"2016-10-10T20:19:22Z","messageCount":2,"participants":["tboegi@web.de","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"303662","messageId":"20161009095654.1964-1-tboegi@web.de","threadId":"44259","inReplyTo":null,"subject":"[PATCH v1 2/2] convert.c: stream and early out","fromName":"","fromEmail":"tboegi@web.de","sentAt":"2016-10-09T09:56:54Z","receivedAt":"2016-10-09T09:57:47Z","isPatch":true,"sender":{"key":"tboegi@web.de","avatar":"https://avatars.githubusercontent.com/u/7138363?v=4"},"body":"From: Torsten Bögershausen <tboegi@web.de>\n\nWhen statistics are done for the autocrlf handling, the search in\nthe content can be stopped, if e.g\n- a search for binary is done, and a NUL character is found\n- a search for CRLF is done, and the first CRLF is found.\n\nSimilar when statistics for binary vs non-binary are gathered:\nWhenever a lone CR or NUL is found, the search can be aborted.\n\nWhen checking out files in \"auto\" mode, any file that has a \"lone CR\"\nor a CRLF will not be converted, so the search can be aborted early.\n\nAdd the new bit, CONVERT_STAT_BITS_ANY_CR,\nwhich is set for either lone CR or CRLF.\n\nMany binary files have a NUL very early (within the first few bytes,\nlatest within the first 1..2K).\nIt is often not necessary to load the whole content of a file or blob\ninto memory.\n\nUse a streaming handling for blobs and files in the worktree.\n---\n convert.c | 195 +++++++++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 130 insertions(+), 65 deletions(-)\n\ndiff --git a/convert.c b/convert.c\nindex 077f5e6..6a625e5 100644\n--- a/convert.c\n+++ b/convert.c\n@@ -3,6 +3,7 @@\n #include \"run-command.h\"\n #include \"quote.h\"\n #include \"sigchain.h\"\n+#include \"streaming.h\"\n \n /*\n  * convert.c - convert a file when checking it out and checking it in.\n@@ -13,10 +14,10 @@\n  * translation when the \"text\" attribute or \"auto_crlf\" option is set.\n  */\n \n-/* Stat bits: When BIN is set, the txt bits are unset */\n #define CONVERT_STAT_BITS_TXT_LF    0x1\n #define CONVERT_STAT_BITS_TXT_CRLF  0x2\n #define CONVERT_STAT_BITS_BIN       0x4\n+#define CONVERT_STAT_BITS_ANY_CR    0x8\n \n enum crlf_action {\n \tCRLF_UNDEFINED,\n@@ -31,30 +32,36 @@ enum crlf_action {\n \n struct text_stat {\n \t/* NUL, CR, LF and CRLF counts */\n-\tunsigned nul, lonecr, lonelf, crlf;\n+\tunsigned stat_bits, lonecr, lonelf, crlf;\n \n \t/* These are just approximations! */\n \tunsigned printable, nonprintable;\n };\n \n-static void gather_stats(const char *buf, unsigned long size, struct text_stat *stats)\n+static void gather_stats_partly(const char *buf, unsigned long len,\n+\t\t\t\tstruct text_stat *stats, unsigned earlyout)\n {\n \tunsigned long i;\n \n-\tmemset(stats, 0, sizeof(*stats));\n-\n-\tfor (i = 0; i < size; i++) {\n+\tif (!buf || !len)\n+\t\treturn;\n+\tfor (i = 0; i < len; i++) {\n \t\tunsigned char c = buf[i];\n \t\tif (c == '\\r') {\n-\t\t\tif (i+1 < size && buf[i+1] == '\\n') {\n+\t\t\tstats->stat_bits |= CONVERT_STAT_BITS_ANY_CR;\n+\t\t\tif (i+1 < len && buf[i+1] == '\\n') {\n \t\t\t\tstats->crlf++;\n \t\t\t\ti++;\n-\t\t\t} else\n+\t\t\t\tstats->stat_bits |= CONVERT_STAT_BITS_TXT_CRLF;\n+\t\t\t} else {\n \t\t\t\tstats->lonecr++;\n+\t\t\t\tstats->stat_bits |= CONVERT_STAT_BITS_BIN;\n+\t\t\t}\n \t\t\tcontinue;\n \t\t}\n \t\tif (c == '\\n') {\n \t\t\tstats->lonelf++;\n+\t\t\tstats->stat_bits |= CONVERT_STAT_BITS_TXT_LF;\n \t\t\tcontinue;\n \t\t}\n \t\tif (c == 127)\n@@ -67,7 +74,7 @@ static void gather_stats(const char *buf, unsigned long size, struct text_stat *\n \t\t\t\tstats->printable++;\n \t\t\t\tbreak;\n \t\t\tcase 0:\n-\t\t\t\tstats->nul++;\n+\t\t\t\tstats->stat_bits |= CONVERT_STAT_BITS_BIN;\n \t\t\t\t/* fall through */\n \t\t\tdefault:\n \t\t\t\tstats->nonprintable++;\n@@ -75,10 +82,12 @@ static void gather_stats(const char *buf, unsigned long size, struct text_stat *\n \t\t}\n \t\telse\n \t\t\tstats->printable++;\n+\t\tif (stats->stat_bits & earlyout)\n+\t\t\tbreak; /* We found what we have been searching for */\n \t}\n \n \t/* If file ends with EOF then don't count this EOF as non-printable. */\n-\tif (size >= 1 && buf[size-1] == '\\032')\n+\tif (len >= 1 && buf[len-1] == '\\032')\n \t\tstats->nonprintable--;\n }\n \n@@ -86,41 +95,62 @@ static void gather_stats(const char *buf, unsigned long size, struct text_stat *\n  * The same heuristics as diff.c::mmfile_is_binary()\n  * We treat files with bare CR as binary\n  */\n-static int convert_is_binary(unsigned long size, const struct text_stat *stats)\n+static void convert_nonprintable(struct text_stat *stats)\n {\n-\tif (stats->lonecr)\n-\t\treturn 1;\n-\tif (stats->nul)\n-\t\treturn 1;\n \tif ((stats->printable >> 7) < stats->nonprintable)\n-\t\treturn 1;\n-\treturn 0;\n+\t\tstats->stat_bits |= CONVERT_STAT_BITS_BIN;\n }\n \n-static unsigned int gather_convert_stats(const char *data, unsigned long size)\n+static void gather_stats(const char *buf, unsigned long size,\n+\t\t\t struct text_stat *stats, unsigned earlyout)\n {\n+\tmemset(stats, 0, sizeof(*stats));\n+\tgather_stats_partly(buf, size, stats, earlyout);\n+\tconvert_nonprintable(stats);\n+}\n+\n+\n+static unsigned get_convert_stats_sha1(unsigned const char *sha1,\n+\t\t\t\t       unsigned earlyout)\n+{\n+\tstruct git_istream *st;\n \tstruct text_stat stats;\n-\tint ret = 0;\n-\tif (!data || !size)\n-\t\treturn 0;\n-\tgather_stats(data, size, &stats);\n-\tif (convert_is_binary(size, &stats))\n-\t\tret |= CONVERT_STAT_BITS_BIN;\n-\tif (stats.crlf)\n-\t\tret |= CONVERT_STAT_BITS_TXT_CRLF;\n-\tif (stats.lonelf)\n-\t\tret |=  CONVERT_STAT_BITS_TXT_LF;\n+\tenum object_type type;\n+\tunsigned long sz;\n \n-\treturn ret;\n+\tif (!sha1)\n+\t\treturn 0;\n+\tmemset(&stats, 0, sizeof(stats));\n+\tst = open_istream(sha1, &type, &sz, NULL);\n+\tif (!st) {\n+\t\treturn 0;\n+\t}\n+\tif (type != OBJ_BLOB)\n+\t\tgoto close_and_exit_i;\n+\tfor (;;) {\n+\t\tchar buf[2*1024];\n+\t\tssize_t readlen = read_istream(st, buf, sizeof(buf));\n+\t\tif (readlen < 0)\n+\t\t\tbreak;\n+\t\tif (!readlen)\n+\t\t\tbreak;\n+\t\tgather_stats_partly(buf, (unsigned long)readlen, &stats, earlyout);\n+\t\tif (stats.stat_bits & earlyout)\n+\t\t\tbreak; /* We found what we have been searching for */\n+\t}\n+close_and_exit_i:\n+\tclose_istream(st);\n+\tconvert_nonprintable(&stats);\n+\treturn stats.stat_bits;\n }\n \n-static const char *gather_convert_stats_ascii(const char *data, unsigned long size)\n+static const char *convert_stats_ascii(unsigned convert_stats)\n {\n-\tunsigned int convert_stats = gather_convert_stats(data, size);\n-\n+\tconst unsigned mask = CONVERT_STAT_BITS_TXT_LF |\n+\t\tCONVERT_STAT_BITS_TXT_CRLF;\n \tif (convert_stats & CONVERT_STAT_BITS_BIN)\n \t\treturn \"-text\";\n-\tswitch (convert_stats) {\n+\tswitch (convert_stats & mask) {\n \tcase CONVERT_STAT_BITS_TXT_LF:\n \t\treturn \"lf\";\n \tcase CONVERT_STAT_BITS_TXT_CRLF:\n@@ -132,24 +162,45 @@ static const char *gather_convert_stats_ascii(const char *data, unsigned long si\n \t}\n }\n \n+static unsigned get_convert_stats_wt(const char *path)\n+{\n+\tstruct text_stat stats;\n+\tunsigned earlyout = CONVERT_STAT_BITS_BIN;\n+\tint fd;\n+\tmemset(&stats, 0, sizeof(stats));\n+\tfd = open(path, O_RDONLY);\n+\tif (fd < 0)\n+\t\treturn 0;\n+\tfor (;;) {\n+\t\tchar buf[2*1024];\n+\t\tssize_t readlen = read(fd, buf, sizeof(buf));\n+\t\tif (readlen < 0)\n+\t\t\tbreak;\n+\t\tif (!readlen)\n+\t\t\tbreak;\n+\t\tgather_stats_partly(buf, (unsigned long)readlen, &stats, earlyout);\n+\t\tif (stats.stat_bits & earlyout)\n+\t\t\tbreak; /* We found what we have been searching for */\n+\t}\n+\tclose(fd);\n+\tconvert_nonprintable(&stats);\n+\treturn stats.stat_bits;\n+}\n+\n const char *get_cached_convert_stats_ascii(const char *path)\n {\n-\tconst char *ret;\n-\tunsigned long sz;\n-\tvoid *data = read_blob_data_from_cache(path, &sz);\n-\tret = gather_convert_stats_ascii(data, sz);\n-\tfree(data);\n-\treturn ret;\n+\tunsigned convert_stats;\n+\tunsigned earlyout = CONVERT_STAT_BITS_BIN;\n+\tconvert_stats = get_convert_stats_sha1(get_sha1_from_cache(path),\n+\t\t\t\t\t       earlyout);\n+\treturn convert_stats_ascii(convert_stats);\n }\n \n const char *get_wt_convert_stats_ascii(const char *path)\n {\n-\tconst char *ret = \"\";\n-\tstruct strbuf sb = STRBUF_INIT;\n-\tif (strbuf_read_file(&sb, path, 0) >= 0)\n-\t\tret = gather_convert_stats_ascii(sb.buf, sb.len);\n-\tstrbuf_release(&sb);\n-\treturn ret;\n+\tunsigned convert_stats;\n+\tconvert_stats = get_convert_stats_wt(path);\n+\treturn convert_stats_ascii(convert_stats);\n }\n \n static int text_eol_is_crlf(void)\n@@ -213,16 +264,10 @@ static void check_safe_crlf(const char *path, enum crlf_action crlf_action,\n \n static int has_cr_in_index(const char *path)\n {\n-\tunsigned long sz;\n-\tvoid *data;\n-\tint has_cr;\n-\n-\tdata = read_blob_data_from_cache(path, &sz);\n-\tif (!data)\n-\t\treturn 0;\n-\thas_cr = memchr(data, '\\r', sz) != NULL;\n-\tfree(data);\n-\treturn has_cr;\n+\tunsigned convert_stats;\n+\tconvert_stats = get_convert_stats_sha1(get_sha1_from_cache(path),\n+\t\t\t\t\t       CONVERT_STAT_BITS_ANY_CR);\n+\treturn convert_stats & CONVERT_STAT_BITS_ANY_CR;\n }\n \n static int will_convert_lf_to_crlf(size_t len, struct text_stat *stats,\n@@ -234,13 +279,13 @@ static int will_convert_lf_to_crlf(size_t len, struct text_stat *stats,\n \tif (!stats->lonelf)\n \t\treturn 0;\n \n-\tif (crlf_action == CRLF_AUTO || crlf_action == CRLF_AUTO_INPUT || crlf_action == CRLF_AUTO_CRLF) {\n+\tif (crlf_action == CRLF_AUTO || crlf_action == CRLF_AUTO_CRLF) {\n \t\t/* If we have any CR or CRLF line endings, we do not touch it */\n \t\t/* This is the new safer autocrlf-handling */\n \t\tif (stats->lonecr || stats->crlf)\n \t\t\treturn 0;\n \n-\t\tif (convert_is_binary(len, stats))\n+\t\tif (stats->stat_bits & CONVERT_STAT_BITS_BIN)\n \t\t\treturn 0;\n \t}\n \treturn 1;\n@@ -253,7 +298,8 @@ static int crlf_to_git(const char *path, const char *src, size_t len,\n {\n \tstruct text_stat stats;\n \tchar *dst;\n-\tint convert_crlf_into_lf;\n+\tint has_crlf_to_convert;\n+\tunsigned earlyout = 0;\n \n \tif (crlf_action == CRLF_BINARY ||\n \t    (src && !len))\n@@ -266,12 +312,16 @@ static int crlf_to_git(const char *path, const char *src, size_t len,\n \tif (!buf && !src)\n \t\treturn 1;\n \n-\tgather_stats(src, len, &stats);\n+\tif (crlf_action == CRLF_AUTO || crlf_action == CRLF_AUTO_INPUT || crlf_action == CRLF_AUTO_CRLF)\n+\t\tearlyout = CONVERT_STAT_BITS_BIN;\n+\n+\tgather_stats(src, len, &stats, earlyout);\n+\n \t/* Optimization: No CRLF? Nothing to convert, regardless. */\n-\tconvert_crlf_into_lf = !!stats.crlf;\n+\thas_crlf_to_convert = !!stats.crlf;\n \n \tif (crlf_action == CRLF_AUTO || crlf_action == CRLF_AUTO_INPUT || crlf_action == CRLF_AUTO_CRLF) {\n-\t\tif (convert_is_binary(len, &stats))\n+\t\tif (stats.stat_bits & CONVERT_STAT_BITS_BIN)\n \t\t\treturn 0;\n \t\t/*\n \t\t * If the file in the index has any CR in it, do not convert.\n@@ -280,24 +330,35 @@ static int crlf_to_git(const char *path, const char *src, size_t len,\n \t\tif (checksafe == SAFE_CRLF_RENORMALIZE)\n \t\t\tchecksafe = SAFE_CRLF_FALSE;\n \t\telse if (has_cr_in_index(path))\n-\t\t\tconvert_crlf_into_lf = 0;\n+\t\t\thas_crlf_to_convert = 0;\n \t}\n \tif (checksafe && len) {\n \t\tstruct text_stat new_stats;\n \t\tmemcpy(&new_stats, &stats, sizeof(new_stats));\n \t\t/* simulate \"git add\" */\n-\t\tif (convert_crlf_into_lf) {\n+\t\tif (has_crlf_to_convert) {\n \t\t\tnew_stats.lonelf += new_stats.crlf;\n \t\t\tnew_stats.crlf = 0;\n+\t\t\t/* all crlf, if any, are gone. Update the bits */\n+\t\t\tnew_stats.stat_bits = stats.stat_bits & CONVERT_STAT_BITS_BIN;\n+\t\t\tif (new_stats.lonelf)\n+\t\t\t\tnew_stats.stat_bits |= CONVERT_STAT_BITS_TXT_LF;\n+\t\t\tif (new_stats.lonecr)\n+\t\t\t\tnew_stats.stat_bits |= CONVERT_STAT_BITS_ANY_CR;\n \t\t}\n \t\t/* simulate \"git checkout\" */\n \t\tif (will_convert_lf_to_crlf(len, &new_stats, crlf_action)) {\n \t\t\tnew_stats.crlf += new_stats.lonelf;\n \t\t\tnew_stats.lonelf = 0;\n+\t\t\tnew_stats.stat_bits = stats.stat_bits & CONVERT_STAT_BITS_BIN;\n+\t\t\tif (new_stats.crlf)\n+\t\t\t\tnew_stats.stat_bits |= CONVERT_STAT_BITS_TXT_CRLF | CONVERT_STAT_BITS_ANY_CR;\n+\t\t\tif (new_stats.lonecr)\n+\t\t\t\tnew_stats.stat_bits |= CONVERT_STAT_BITS_ANY_CR;\n \t\t}\n \t\tcheck_safe_crlf(path, crlf_action, &stats, &new_stats, checksafe);\n \t}\n-\tif (!convert_crlf_into_lf)\n+\tif (!has_crlf_to_convert)\n \t\treturn 0;\n \n \t/*\n@@ -338,11 +399,15 @@ static int crlf_to_worktree(const char *path, const char *src, size_t len,\n {\n \tchar *to_free = NULL;\n \tstruct text_stat stats;\n+\tunsigned earlyout = 0;\n \n \tif (!len || output_eol(crlf_action) != EOL_CRLF)\n \t\treturn 0;\n \n-\tgather_stats(src, len, &stats);\n+\tif (crlf_action == CRLF_AUTO || crlf_action == CRLF_AUTO_CRLF)\n+\t\tearlyout = CONVERT_STAT_BITS_ANY_CR | CONVERT_STAT_BITS_BIN;\n+\n+\tgather_stats(src, len, &stats, earlyout);\n \tif (!will_convert_lf_to_crlf(len, &stats, crlf_action))\n \t\treturn 0;\n \n-- \n2.10.0\n\n"},{"id":"303798","messageId":"xmqqd1j8dkjj.fsf@gitster.mtv.corp.google.com","threadId":"44259","inReplyTo":"20161009095654.1964-1-tboegi@web.de","subject":"Re: [PATCH v1 2/2] convert.c: stream and early out","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-10T20:19:12Z","receivedAt":"2016-10-10T20:19:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"tboegi@web.de writes:\n\n> -static void gather_stats(const char *buf, unsigned long size, struct text_stat *stats)\n> +static void gather_stats_partly(const char *buf, unsigned long len,\n> +\t\t\t\tstruct text_stat *stats, unsigned earlyout)\n>  {\n\nI think it is OK not to rename the function (you'd be passing earlyout=0\nfor callers that want exact stat, right?).\n\n>  \tunsigned long i;\n>  \n> -\tmemset(stats, 0, sizeof(*stats));\n> -\n> -\tfor (i = 0; i < size; i++) {\n> +\tif (!buf || !len)\n> +\t\treturn;\n> +\tfor (i = 0; i < len; i++) {\n>  \t\tunsigned char c = buf[i];\n>  \t\tif (c == '\\r') {\n> -\t\t\tif (i+1 < size && buf[i+1] == '\\n') {\n> +\t\t\tstats->stat_bits |= CONVERT_STAT_BITS_ANY_CR;\n> +\t\t\tif (i+1 < len && buf[i+1] == '\\n') {\n>  \t\t\t\tstats->crlf++;\n>  \t\t\t\ti++;\n> -\t\t\t} else\n> +\t\t\t\tstats->stat_bits |= CONVERT_STAT_BITS_TXT_CRLF;\n> +\t\t\t} else {\n>  \t\t\t\tstats->lonecr++;\n> +\t\t\t\tstats->stat_bits |= CONVERT_STAT_BITS_BIN;\n> +\t\t\t}\n>  \t\t\tcontinue;\n>  \t\t}\n>  \t\tif (c == '\\n') {\n>  \t\t\tstats->lonelf++;\n> +\t\t\tstats->stat_bits |= CONVERT_STAT_BITS_TXT_LF;\n>  \t\t\tcontinue;\n>  \t\t}\n>  \t\tif (c == 127)\n> @@ -67,7 +74,7 @@ static void gather_stats(const char *buf, unsigned long size, struct text_stat *\n>  \t\t\t\tstats->printable++;\n>  \t\t\t\tbreak;\n>  \t\t\tcase 0:\n> -\t\t\t\tstats->nul++;\n> +\t\t\t\tstats->stat_bits |= CONVERT_STAT_BITS_BIN;\n>  \t\t\t\t/* fall through */\n>  \t\t\tdefault:\n>  \t\t\t\tstats->nonprintable++;\n\n\nSo depending on the distribution of the bytes in the file, the\nbitfields in stats->stat_bits will be filled one bit at a time in\nrandom order.\n\n> @@ -75,10 +82,12 @@ static void gather_stats(const char *buf, unsigned long size, struct text_stat *\n>  \t\t}\n>  \t\telse\n>  \t\t\tstats->printable++;\n> +\t\tif (stats->stat_bits & earlyout)\n> +\t\t\tbreak; /* We found what we have been searching for */\n\nBut an \"earlyout\" says that if \"any\" of the earlyout bit is seen, we\ncan return.\n\nIt somehow felt a bit too limited to me in my initial reading, but I\nguess I shouldn't be surprised to see that such a limited interface\nis sufficient for a file-local helper function ;-).  \n\nThe only caller that the semantics of this exit condition matters is\nthe one that wants to know \"do we have NUL or CR anywhere?\", so I\nguess this should be sufficient.\n\n>  \t}\n>  \n>  \t/* If file ends with EOF then don't count this EOF as non-printable. */\n> -\tif (size >= 1 && buf[size-1] == '\\032')\n> +\tif (len >= 1 && buf[len-1] == '\\032')\n>  \t\tstats->nonprintable--;\n\nThis noise is somewhat irritating.  Was there a reason why size was\na bad name for the variable?\n\n> +static const char *convert_stats_ascii(unsigned convert_stats)\n>  {\n> -\tunsigned int convert_stats = gather_convert_stats(data, size);\n> -\n> +\tconst unsigned mask = CONVERT_STAT_BITS_TXT_LF |\n> +\t\tCONVERT_STAT_BITS_TXT_CRLF;\n>  \tif (convert_stats & CONVERT_STAT_BITS_BIN)\n>  \t\treturn \"-text\";\n> -\tswitch (convert_stats) {\n> +\tswitch (convert_stats & mask) {\n>  \tcase CONVERT_STAT_BITS_TXT_LF:\n>  \t\treturn \"lf\";\n>  \tcase CONVERT_STAT_BITS_TXT_CRLF:\n\nSubtle.  The caller runs the stat colllection with early-out set to\nBITS_BIN, so that this can set \"-text\" early.  It knows that without\nBITS_BIN, the stat was taken for the whole contents and the check lf\nor crlf can be reliable.\n\nI wonder if we can/need to do something to remove this subtleness\nout of this callchain, which could be a source of confusion.\n\n> @@ -132,24 +162,45 @@ static const char *gather_convert_stats_ascii(const char *data, unsigned long si\n>  \t}\n>  }\n>  \n> +static unsigned get_convert_stats_wt(const char *path)\n> +{\n> +\tstruct text_stat stats;\n> +\tunsigned earlyout = CONVERT_STAT_BITS_BIN;\n> +\tint fd;\n> +\tmemset(&stats, 0, sizeof(stats));\n> +\tfd = open(path, O_RDONLY);\n> +\tif (fd < 0)\n> +\t\treturn 0;\n> +\tfor (;;) {\n> +\t\tchar buf[2*1024];\n\nWhere is this 2kB come from?  Out of thin air?\n\n"}]}