summaryrefslogtreecommitdiff
path: root/bisect.c
AgeCommit message (Collapse)AuthorFilesLines
2021-01-04hash-lookup: rename from sha1-lookupLibravatar Martin Ågren1-1/+1
Change all remnants of "sha1" in hash-lookup.c and .h and rename them to reflect that we're not just able to handle SHA-1 these days. Signed-off-by: Martin Ågren <martin.agren@gmail.com> Reviewed-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-11-25Merge branch 'sg/bisect-approximately-halfway'Libravatar Junio C Hamano1-7/+20
"git bisect start/next" in a large span of history spends a lot of time trying to come up with exactly the half-way point; this can be optimized by stopping when we see a commit that is close enough to the half-way point. * sg/bisect-approximately-halfway: bisect: loosen halfway() check for a large number of commits
2020-11-12bisect: loosen halfway() check for a large number of commitsLibravatar SZEDER Gábor1-7/+20
'git bisect start ...' and subsequent 'git bisect (good|bad)' commands can take quite a while when the given/remaining revision range between good and bad commits is big and contains a lot of merge commits, e.g. in git.git: $ git rev-list --count v1.6.0..v2.28.0 44284 $ time git bisect start v2.28.0 v1.6.0 Bisecting: 22141 revisions left to test after this (roughly 15 steps) [e197c21807dacadc8305250baa0b9228819189d4] unable_to_lock_die(): rename function from unable_to_lock_index_die() real 0m15.472s user 0m15.220s sys 0m0.255s The majority of the runtime is spent in do_find_bisection(), where we try to find a commit as close as possible to the halfway point between the bad and good revisions, i.e. a commit from which the number of reachable commits that are in the good-bad range is half the total number of commits in that range. So we count how many commits are reachable in the good-bad range for each commit in that range, which is quick and easy for a linear history, even over 300k commits in a linear range are handled in ~0.3s on my machine. Alas, handling merge commits is non-trivial and quite expensive as the algorithm used seems to be quadratic, causing the long runtime shown above. Interestingly, look at what a big difference one additional commit can make: $ git rev-list --count v1.6.0^..v2.28.0 44285 $ time git bisect start v2.28.0 v1.6.0^ Bisecting: 22142 revisions left to test after this (roughly 15 steps) [565301e41670825ceedf75220f2918ae76831240] Sync with 2.1.2 real 0m5.848s user 0m5.600s sys 0m0.252s The difference is caused by one of the optimizations attempting to cut down the runtime added in 1c4fea3a40 (git-rev-list --bisect: optimization, 2007-03-21): Another small optimization is whenever we find a half-way commit (that is, a commit that can reach exactly half of the commits), we stop giving counts to remaining commits, as we will not find any better commit than we just found. In this second 'git bisect start' command we happen to find a commit exactly at the halfway point and can return early, but in the first case there is no such commit, so we can't return early and end up counting the number of reachable commits from all commits in the good-bad range. However, when we have thousands of commits it's not all that important to find the _exact_ halfway point, a few commits more or less doesn't make any real difference for the bisection. So let's loosen the check in the halfway() helper to consider commits within about 0.1% of the exact halfway point as halfway as well, and rename the function to approx_halfway() accordingly. This will allow us to return early on a bigger good-bad range, even when there is no commit exactly at the halfway point, thereby reducing the runtime of the first command above considerably, from ~15s to 4.901s. Furthermore, even if there is a commit exactly at the halfway point, we might still stumble upon a commit within that 0.1% range before finding the exact halfway point, allowing us to return a bit earlier, slightly reducing the runtime of the second command from 5.848s to 5.058s. Note that this change doesn't affect good-bad ranges containing ~2000 commits or less, because that 0.1% tolerance becomes zero due to integer arithmetic; however, if the range is that small then counting the reachable commits for all commits is already fast enough anyway. Naturally, this will likely change which commits get picked at each bisection step, and, in turn, might change how many bisection steps are necessary to find the first bad commit. If the number of necessary bisection steps were to increase often, then this change could backfire, because building and testing at each step might take much longer than the time spared. OTOH, if the number of steps were to decrease, then it would be a double win. So I ran some tests to see how often that happens: picked random good and bad starting revisions at least 50k commits apart and a random first bad commit in between in git.git, and used 'git bisect run git merge-base --is-ancestor HEAD $first_bad_commit' to check the number of necessary bisection steps. After repeating all this 1000 times both with and without this patch I found that: - 146 cases needed one more bisection step than before, 149 cases needed one less step, while in the remaining 705 cases the number of steps didn't change. So the number of bisection steps does indeed change in a non-negligible number of cases, but it seems that the average number of steps doesn't change in the long run. - The first 'git bisect start' command got over 3x faster in 456 cases, so this "no commit at the exact halfway point" case seems to be common enough to care about. Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-10-31bisect: clear flags in passed repositoryLibravatar René Scharfe1-1/+1
69d2cfe6e8 (bisect.c: remove the_repository reference, 2018-11-10) kept the implicit the_repository reference in clear_commit_marks_all, which was made explicit by the previous commit (and which also renamed it to repo_clear_commit_marks). Replace it as well. Signed-off-by: René Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-10-31object: allow clear_commit_marks_all to handle any repoLibravatar René Scharfe1-1/+1
Allow callers to specify the repository to use. Rename the function to repo_clear_commit_marks to document its new scope. No functional change intended. Signed-off-by: René Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-09-24bisect--helper: reimplement `bisect_next` and `bisect_auto_next` shell ↵Libravatar Pranit Bauva1-2/+9
functions in C Reimplement the `bisect_next()` and the `bisect_auto_next()` shell functions in C and add the subcommands to `git bisect--helper` to call them from git-bisect.sh . bisect_auto_next() function returns an enum bisect_error type as whole `git bisect` can exit with an error code when bisect_next() does. Return an error when `bisect_next()` fails, that fix a bug on shell script version. Using `--bisect-next` and `--bisect-auto-next` subcommands is a temporary measure to port shell function to C so as to use the existing test suite. As more functions are ported, `--bisect-auto-next` subcommand will be retired and will be called by some other methods. Mentored-by: Lars Schneider <larsxschneider@gmail.com> Mentored-by: Christian Couder <chriscool@tuxfamily.org> Mentored-by: Johannes Schindelin <Johannes.Schindelin@gmx.de> Signed-off-by: Pranit Bauva <pranit.bauva@gmail.com> Signed-off-by: Tanushree Tumane <tanushreetumane@gmail.com> Signed-off-by: Miriam Rubio <mirucam@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-09-24bisect: call 'clear_commit_marks_all()' in 'bisect_next_all()'Libravatar Miriam Rubio1-0/+2
As there can be other revision walks after bisect_next_all(), let's add a call to a function to clear all the marks at the end of bisect_next_all(). Mentored-by: Christian Couder <chriscool@tuxfamily.org> Signed-off-by: Miriam Rubio <mirucam@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-08-17Merge branch 'al/bisect-first-parent'Libravatar Junio C Hamano1-30/+49
"git bisect" learns the "--first-parent" option to find the first breakage along the first-parent chain. * al/bisect-first-parent: bisect: combine args passed to find_bisection() bisect: introduce first-parent flag cmd_bisect__helper: defer parsing no-checkout flag rev-list: allow bisect and first-parent flags t6030: modernize "git bisect run" tests
2020-08-10Merge branch 'rs/bisect-oid-to-hex-fix'Libravatar Junio C Hamano1-1/+1
Code cleanup. * rs/bisect-oid-to-hex-fix: bisect: use oid_to_hex_r() instead of memcpy()+oid_to_hex()
2020-08-07bisect: combine args passed to find_bisection()Libravatar Aaron Lipman1-30/+37
Now that find_bisection() accepts multiple boolean arguments, these may be combined into a single unsigned integer in order to declutter some of the code in bisect.c Also, rename the existing "flags" bitfield to "commit_flags", to explicitly differentiate it from the new "bisect_flags" bitfield. Based-on-patch-by: Harald Nordgren <haraldnordgren@gmail.com> Signed-off-by: Aaron Lipman <alipman88@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-08-07bisect: introduce first-parent flagLibravatar Aaron Lipman1-1/+4
Upon seeing a merge commit when bisecting, this option may be used to follow only the first parent. In detecting regressions introduced through the merging of a branch, the merge commit will be identified as introduction of the bug and its ancestors will be ignored. This option is particularly useful in avoiding false positives when a merged branch contained broken or non-buildable commits, but the merge itself was OK. Signed-off-by: Aaron Lipman <alipman88@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-08-07cmd_bisect__helper: defer parsing no-checkout flagLibravatar Aaron Lipman1-1/+2
cmd_bisect__helper() is intended as a temporary shim layer serving as an interface for git-bisect.sh. This function and git-bisect.sh should eventually be replaced by a C implementation, cmd_bisect(), serving as an entrypoint for all "git bisect ..." shell commands: cmd_bisect() will only parse the first token following "git bisect", and dispatch the remaining args to the appropriate function ["bisect_start()", "bisect_next()", etc.]. Thus, cmd_bisect__helper() should not be responsible for parsing flags like --no-checkout. Instead, let the --no-checkout flag remain in the argv array, so it may be evaluated alongside the other options already parsed by bisect_start(). Signed-off-by: Aaron Lipman <alipman88@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-08-07rev-list: allow bisect and first-parent flagsLibravatar Aaron Lipman1-10/+18
Add first_parent_only parameter to find_bisection(), removing the barrier that prevented combining the --bisect and --first-parent flags when using git rev-list Based-on-patch-by: Tiago Botelho <tiagonbotelho@hotmail.com> Signed-off-by: Aaron Lipman <alipman88@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-08-02bisect: use oid_to_hex_r() instead of memcpy()+oid_to_hex()Libravatar René Scharfe1-1/+1
Write the hexadecimal object ID directly into the destination buffer using oid_to_hex_r() instead of writing it into a static buffer first using oid_to_hex() and then copying it from there using memcpy(). This is shorter, simpler and a bit more efficient. Reviewed-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: René Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-07-30strvec: rename struct fieldsLibravatar Jeff King1-1/+1
The "argc" and "argv" names made sense when the struct was argv_array, but now they're just confusing. Let's rename them to "nr" (which we use for counts elsewhere) and "v" (which is rather terse, but reads well when combined with typical variable names like "args.v"). Note that we have to update all of the callers immediately. Playing tricks with the preprocessor is hard here, because we wouldn't want to rewrite unrelated tokens. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-07-28strvec: fix indentation in renamed callsLibravatar Jeff King1-1/+1
Code which split an argv_array call across multiple lines, like: argv_array_pushl(&args, "one argument", "another argument", "and more", NULL); was recently mechanically renamed to use strvec, which results in mis-matched indentation like: strvec_pushl(&args, "one argument", "another argument", "and more", NULL); Let's fix these up to align the arguments with the opening paren. I did this manually by sifting through the results of: git jump grep 'strvec_.*,$' and liberally applying my editor's auto-format. Most of the changes are of the form shown above, though I also normalized a few that had originally used a single-tab indentation (rather than our usual style of aligning with the open paren). I also rewrapped a couple of obvious cases (e.g., where previously too-long lines became short enough to fit on one), but I wasn't aggressive about it. In cases broken to three or more lines, the grouping of arguments is sometimes meaningful, and it wasn't worth my time or reviewer time to ponder each case individually. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-07-28strvec: convert more callers away from argv_array nameLibravatar Jeff King1-6/+6
We eventually want to drop the argv_array name and just use strvec consistently. There's no particular reason we have to do it all at once, or care about interactions between converted and unconverted bits. Because of our preprocessor compat layer, the names are interchangeable to the compiler (so even a definition and declaration using different names is OK). This patch converts remaining files from the first half of the alphabet, to keep the diff to a manageable size. The conversion was done purely mechanically with: git ls-files '*.c' '*.h' | xargs perl -i -pe ' s/ARGV_ARRAY/STRVEC/g; s/argv_array/strvec/g; ' and then selectively staging files with "git add '[abcdefghjkl]*'". We'll deal with any indentation/style fallouts separately. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-07-28quote: rename sq_dequote_to_argv_array to mention strvecLibravatar Jeff King1-1/+1
We want to eventually drop the use of the "argv_array" name in favor of "strvec." Unlike most other uses of the name, this one is embedded in a function name, so the definition and all of the callers need to be updated at the same time. We don't technically need to update the parameter types here (our preprocessor compat macros make the two names interchangeable), but let's do so to keep the site consistent for now. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-07-28strvec: rename files from argv-array to strvecLibravatar Jeff King1-1/+1
This requires updating #include lines across the code-base, but that's all fairly mechanical, and was done with: git ls-files '*.c' '*.h' | xargs perl -i -pe 's/argv-array.h/strvec.h/' Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-03-30bisect: stop referring to sha1_arrayLibravatar Jeff King1-3/+3
Our join_sha1_array_hex() function long ago switched to using an oid_array; let's change the name to match. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-03-30oid_array: rename source file from sha1-arrayLibravatar Jeff King1-1/+1
We renamed the actual data structure in 910650d2f8 (Rename sha1_array to oid_array, 2017-03-31), but the file is still called sha1-array. Besides being slightly confusing, it makes it more annoying to grep for leftover occurrences of "sha1" in various files, because the header is included in so many places. Let's complete the transition by renaming the source and header files (and fixing up a few comment references). I kept the "-" in the name, as that seems to be our style; cf. fc1395f4a4 (sha1_file.c: rename to use dash in file name, 2018-04-10). We also have oidmap.h and oidset.h without any punctuation, but those are "struct oidmap" and "struct oidset" in the code. We _could_ make this "oidarray" to match, but somehow it looks uglier to me because of the length of "array" (plus it would be a very invasive patch for little gain). Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-02-19bisect: libify `bisect_next_all`Libravatar Pranit Bauva1-10/+19
Since we want to get rid of git-bisect.sh, it would be necessary to convert those exit() calls to return statements so that errors can be reported. Emulate try catch in C by converting `exit(<positive-value>)` to `return <negative-value>`. Follow POSIX conventions to return <negative-value> to indicate error. All the functions calling `bisect_next_all()` are already able to handle return values from it. Mentored-by: Christian Couder <chriscool@tuxfamily.org> Mentored-by: Johannes Schindelin <Johannes.Schindelin@gmx.de> Signed-off-by: Pranit Bauva <pranit.bauva@gmail.com> Signed-off-by: Tanushree Tumane <tanushreetumane@gmail.com> Signed-off-by: Miriam Rubio <mirucam@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-02-19bisect: libify `handle_bad_merge_base` and its dependentsLibravatar Pranit Bauva1-4/+5
Since we want to get rid of git-bisect.sh, it would be necessary to convert those exit() calls to return statements so that errors can be reported. Emulate try catch in C by converting `exit(<positive-value>)` to `return <negative-value>`. Follow POSIX conventions to return <negative-value> to indicate error. Update all callers to handle the error returns. Mentored-by: Christian Couder <chriscool@tuxfamily.org> Mentored-by: Johannes Schindelin <Johannes.Schindelin@gmx.de> Signed-off-by: Pranit Bauva <pranit.bauva@gmail.com> Signed-off-by: Tanushree Tumane <tanushreetumane@gmail.com> Signed-off-by: Miriam Rubio <mirucam@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-02-19bisect: libify `check_good_are_ancestors_of_bad` and its dependentsLibravatar Pranit Bauva1-14/+27
Since we want to get rid of git-bisect.sh, it would be necessary to convert those exit() calls to return statements so that errors can be reported. Emulate try catch in C by converting `exit(<positive-value>)` to `return <negative-value>`. Follow POSIX conventions to return <negative-value> to indicate error. Code that turns BISECT_INTERNAL_SUCCESS_MERGE_BASE (-11) to BISECT_OK (0) from `check_good_are_ancestors_of_bad()` has been moved to `cmd_bisect__helper()`. Update all callers to handle the error returns. Mentored-by: Christian Couder <chriscool@tuxfamily.org> Mentored by: Johannes Schindelin <Johannes.Schindelin@gmx.de> Signed-off-by: Pranit Bauva <pranit.bauva@gmail.com> Signed-off-by: Tanushree Tumane <tanushreetumane@gmail.com> Signed-off-by: Miriam Rubio <mirucam@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-02-19bisect: libify `check_merge_bases` and its dependentsLibravatar Pranit Bauva1-4/+18
Since we want to get rid of git-bisect.sh, it would be necessary to convert those exit() calls to return statements so that errors can be reported. Emulate try catch in C by converting `exit(<positive-value>)` to `return <negative-value>`. Follow POSIX conventions to return <negative-value> to indicate error. In `check_merge_bases()` there is an early success special case, so we have introduced special error code BISECT_INTERNAL_SUCCESS_MERGE_BASE (-11) which indicates early success. This BISECT_INTERNAL_SUCCESS_MERGE_BASE is converted back to BISECT_OK (0) in `check_good_are_ancestors_of_bad()`. Update all callers to handle the error returns. Mentored-by: Christian Couder <chriscool@tuxfamily.org> Mentored by: Johannes Schindelin <Johannes.Schindelin@gmx.de> Signed-off-by: Pranit Bauva <pranit.bauva@gmail.com> Signed-off-by: Tanushree Tumane <tanushreetumane@gmail.com> Signed-off-by: Miriam Rubio <mirucam@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-02-19bisect: libify `bisect_checkout`Libravatar Pranit Bauva1-4/+15
Since we want to get rid of git-bisect.sh, it would be necessary to convert those exit() calls to return statements so that errors can be reported. Emulate try catch in C by converting `exit(<positive-value>)` to `return <negative-value>`. Follow POSIX conventions to return <negative-value> to indicate error. Turn `exit()` to `return` calls in `bisect_checkout()`. Changes related to return values have no bad side effects on the code that calls `bisect_checkout()`. Mentored-by: Christian Couder <chriscool@tuxfamily.org> Mentored-by: Johannes Schindelin <Johannes.Schindelin@gmx.de> Signed-off-by: Pranit Bauva <pranit.bauva@gmail.com> Signed-off-by: Tanushree Tumane <tanushreetumane@gmail.com> Signed-off-by: Miriam Rubio <mirucam@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-02-19bisect: libify `exit_if_skipped_commits` to `error_if_skipped*` and its ↵Libravatar Pranit Bauva1-6/+11
dependents Since we want to get rid of git-bisect.sh, it would be necessary to convert those exit() calls to return statements so that errors can be reported. Emulate try catch in C by converting `exit(<positive-value>)` to `return <negative-value>`. Follow POSIX conventions to return <negative-value> to indicate error. Update all callers to handle the error returns. Mentored-by: Christian Couder <chriscool@tuxfamily.org> Mentored-by: Johannes Schindelin <Johannes.Schindelin@gmx.de> Signed-off-by: Pranit Bauva <pranit.bauva@gmail.com> Signed-off-by: Tanushree Tumane <tanushreetumane@gmail.com> Signed-off-by: Miriam Rubio <mirucam@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-02-19bisect: add enum to represent bisect returning codesLibravatar Miriam Rubio1-1/+1
Since we want to get rid of git-bisect.sh, it would be necessary to convert those exit() calls to return statements so that errors can be reported. Create an enum called `bisect_error` with the bisecting return codes to use in `bisect.c` libification process. Change bisect_next_all() to make it return this enum. Mentored-by: Christian Couder <chriscool@tuxfamily.org> Signed-off-by: Miriam Rubio <mirucam@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-02-19bisect: use the standard 'if (!var)' way to check for 0Libravatar Miriam Rubio1-2/+2
Instead of using 'var == 0' in an if condition, let's use '!var' and make 'bisect.c' more consistent with the rest of the code. Mentored-by: Christian Couder <chriscool@tuxfamily.org> Signed-off-by: Miriam Rubio <mirucam@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-08-19bisect: switch to using the_hash_algoLibravatar brian m. carlson1-1/+1
Instead of using GIT_SHA1_HEXSZ, use the_hash_algo so that the code is hash size independent. Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-03-01bisect: make diff-tree output prettierLibravatar Jeff King1-2/+2
After completing a bisection, we print out the commit we found using an internal version of diff-tree. The result is aesthetically lacking: - it shows a raw diff, which is generally less informative for human readers than "--stat --summary" (which we already decided was nice for humans in format-patch's output). - by not abbreviating hashes, the result is likely to wrap on most people's terminals - we don't use "-r", so if the commit touched files in a directory, you only get to see the top-level directory mentioned - we don't specify "--cc" or similar, so merges print nothing (not even the commit message!) Even though bisect might be driven by scripts, there's no reason to consider this part of the output as machine-readable (if anything, the initial "$hash is the first bad commit" might be parsed, but we won't touch that here). Let's make it prettier and more informative for a human reading the output. While we're tweaking the options, let's also switch to using the diff "ui" config. If we're accepting that this is human-readable output, then we should respect the user's options for how to display it. Note that we have to touch a few tests in t6030. These check bisection in a corrupted repository (it's missing a subtree). They didn't fail with the previous code, because it didn't actually recurse far enough in the diff to find the broken tree. But now we'll see the corruption and complain. Adjusting the tests to expect the die() is the best fix. We still confirm that we're able to bisect within the broken repo. And we'll still print "$hash is the first bad commit" as usual before dying; showing that is a reasonable outcome in a corrupt repository (and was what might happen already, if the root tree was corrupt). Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-03-01bisect: fix internal diff-tree config loadingLibravatar Jeff King1-1/+1
When we run our internal diff-tree to show the bisected commit, we call init_revisions(), then load config, then setup_revisions(). But that order is wrong: we copy the configured defaults into the rev_info struct during the init_revisions step, so our config load wasn't actually doing anything. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-03-01bisect: use string arguments to feed internal diff-treeLibravatar Jeff King1-13/+4
Commit e22278c0a0 (bisect: display first bad commit without forking a new process, 2009-05-28) converted our external call to diff-tree to an internal use of the log_tree_commit(). But rather than individually setting options in the rev_info struct (and explaining in comments how they map to command-line options), we can just pass the command-line options to setup_revisions(). This is shorter, easier to change, and less likely to break if revision.c internals change. Note that we unconditionally set the output format to "raw". The conditional in the original code didn't actually do anything useful, since nobody had an opportunity to set the format to anything. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-02-06Merge branch 'ds/push-sparse-tree-walk'Libravatar Junio C Hamano1-1/+1
"git pack-objects" learned another algorithm to compute the set of objects to send, that trades the resulting packfile off to save traversal cost to favor small pushes. * ds/push-sparse-tree-walk: pack-objects: create GIT_TEST_PACK_SPARSE pack-objects: create pack.useSparse setting revision: implement sparse algorithm list-objects: consume sparse tree walk revision: add mark_tree_uninteresting_sparse
2019-01-18Merge branch 'nd/style-opening-brace'Libravatar Junio C Hamano1-1/+2
Code clean-up. * nd/style-opening-brace: style: the opening '{' of a function is in a separate line
2019-01-17list-objects: consume sparse tree walkLibravatar Derrick Stolee1-1/+1
When creating a pack-file using 'git pack-objects --revs' we provide a list of interesting and uninteresting commits. For example, a push operation would make the local topic branch be interesting and the known remote refs as uninteresting. We want to discover the set of new objects to send to the server as a thin pack. We walk these commits until we discover a frontier of commits such that every commit walk starting at interesting commits ends in a root commit or unintersting commit. We then need to discover which non-commit objects are reachable from uninteresting commits. This commit walk is not changing during this series. The mark_edges_uninteresting() method in list-objects.c iterates on the commit list and does the following: * If the commit is UNINTERSTING, then mark its root tree and every object it can reach as UNINTERESTING. * If the commit is interesting, then mark the root tree of every UNINTERSTING parent (and all objects that tree can reach) as UNINTERSTING. At the very end, we repeat the process on every commit directly given to the revision walk from stdin. This helps ensure we properly cover shallow commits that otherwise were not included in the frontier. The logic to recursively follow trees is in the mark_tree_uninteresting() method in revision.c. The algorithm avoids duplicate work by not recursing into trees that are already marked UNINTERSTING. Add a new 'sparse' option to the mark_edges_uninteresting() method that performs this logic in a slightly different way. As we iterate over the commits, we add all of the root trees to an oidset. Then, call mark_trees_uninteresting_sparse() on that oidset. Note that we include interesting trees in this process. The current implementation of mark_trees_unintersting_sparse() will walk the same trees as the old logic, but this will be replaced in a later change. Add a '--sparse' flag in 'git pack-objects' to call this new logic. Add a new test script t/t5322-pack-objects-sparse.sh that tests this option. The tests currently demonstrate that the resulting object list is the same as the old algorithm. This includes a case where both algorithms pack an object that is not needed by a remote due to limits on the explored set of trees. When the sparse algorithm is changed in a later commit, we will add a test that demonstrates a change of behavior in some cases. Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-12-10style: the opening '{' of a function is in a separate lineLibravatar Nguyễn Thái Ngọc Duy1-1/+2
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-11-12bisect.c: remove the_repository referenceLibravatar Nguyễn Thái Ngọc Duy1-20/+28
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-10-19Merge branch 'nd/the-index'Libravatar Junio C Hamano1-2/+2
Various codepaths in the core-ish part learn to work on an arbitrary in-core index structure, not necessarily the default instance "the_index". * nd/the-index: (23 commits) revision.c: reduce implicit dependency the_repository revision.c: remove implicit dependency on the_index ws.c: remove implicit dependency on the_index tree-diff.c: remove implicit dependency on the_index submodule.c: remove implicit dependency on the_index line-range.c: remove implicit dependency on the_index userdiff.c: remove implicit dependency on the_index rerere.c: remove implicit dependency on the_index sha1-file.c: remove implicit dependency on the_index patch-ids.c: remove implicit dependency on the_index merge.c: remove implicit dependency on the_index merge-blobs.c: remove implicit dependency on the_index ll-merge.c: remove implicit dependency on the_index diff-lib.c: remove implicit dependency on the_index read-cache.c: remove implicit dependency on the_index diff.c: remove implicit dependency on the_index grep.c: remove implicit dependency on the_index diff.c: remove the_index dependency in textconv() functions blame.c: rename "repo" argument to "r" combine-diff.c: remove implicit dependency on the_index ...
2018-09-21revision.c: remove implicit dependency on the_indexLibravatar Nguyễn Thái Ngọc Duy1-2/+2
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-09-17Merge branch 'nd/bisect-show-list-fix'Libravatar Junio C Hamano1-5/+5
Debugging aid update. * nd/bisect-show-list-fix: bisect.c: make show_list() build again
2018-09-17Merge branch 'jk/cocci'Libravatar Junio C Hamano1-3/+3
spatch transformation to replace boolean uses of !hashcmp() to newly introduced oideq() is added, and applied, to regain performance lost due to support of multiple hash algorithms. * jk/cocci: show_dirstat: simplify same-content check read-cache: use oideq() in ce_compare functions convert hashmap comparison functions to oideq() convert "hashcmp() != 0" to "!hasheq()" convert "oidcmp() != 0" to "!oideq()" convert "hashcmp() == 0" to hasheq() convert "oidcmp() == 0" to oideq() introduce hasheq() and oideq() coccinelle: use <...> for function exclusion
2018-09-04bisect.c: make show_list() build againLibravatar Nguyễn Thái Ngọc Duy1-5/+5
This function only compiles when DEBUG_BISECT is 1, which is often not the case. As a result there are two commits [1] [2] that break it but the breakages went unnoticed because the code did not compile by default. Update the function and include the new header file to make this function build again. In order to stop this from happening again, the function is now compiled unconditionally but exits early unless DEBUG_BISECT is non-zero. A smart compiler generates no extra code (not even a function call). But even if it does not, this function does not seem to be in a hot path that the extra cost becomes a big problem. [1] bb408ac95d (bisect.c: use commit-slab for commit weight instead of commit->util - 2018-05-19) [2] cbd53a2193 (object-store: move object access functions to object-store.h - 2018-05-15) Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-08-29convert "oidcmp() != 0" to "!oideq()"Libravatar Jeff King1-1/+1
This is the flip side of the previous two patches: checking for a non-zero oidcmp() can be more strictly expressed as inequality. Like those patches, we write "!= 0" in the coccinelle transformation, which covers by isomorphism the more common: if (oidcmp(E1, E2)) As with the previous two patches, this patch can be achieved almost entirely by running "make coccicheck"; the only differences are manual line-wrap fixes to match the original code. There is one thing to note for anybody replicating this, though: coccinelle 1.0.4 seems to miss the case in builtin/tag.c, even though it's basically the same as all the others. Running with 1.0.7 does catch this, so presumably it's just a coccinelle bug that was fixed in the interim. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-08-29convert "oidcmp() == 0" to oideq()Libravatar Jeff King1-2/+2
Using the more restrictive oideq() should, in the long run, give the compiler more opportunities to optimize these callsites. For now, this conversion should be a complete noop with respect to the generated code. The result is also perhaps a little more readable, as it avoids the "zero is equal" idiom. Since it's so prevalent in C, I think seasoned programmers tend not to even notice it anymore, but it can sometimes make for awkward double negations (e.g., we can drop a few !!oidcmp() instances here). This patch was generated almost entirely by the included coccinelle patch. This mechanical conversion should be completely safe, because we check explicitly for cases where oidcmp() is compared to 0, which is what oideq() is doing under the hood. Note that we don't have to catch "!oidcmp()" separately; coccinelle's standard isomorphisms make sure the two are treated equivalently. I say "almost" because I did hand-edit the coccinelle output to fix up a few style violations (it mostly keeps the original formatting, but sometimes unwraps long lines). Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-07-20commit.h: remove method declarationsLibravatar Derrick Stolee1-0/+1
These methods are now declared in commit-reach.h. Remove them from commit.h and add new include statements in all files that require these declarations. Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-06-29commit: add repository argument to lookup_commit_referenceLibravatar Stefan Beller1-1/+1
Add a repository argument to allow callers of lookup_commit_reference to be more specific about which repository to handle. This is a small mechanical change; it doesn't change the implementation to handle repositories other than the_repository yet. As with the previous commits, use a macro to catch callers passing a repository other than the_repository at compile time. Signed-off-by: Stefan Beller <sbeller@google.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-05-21bisect.c: use commit-slab for commit weight instead of commit->utilLibravatar Nguyễn Thái Ngọc Duy1-3/+9
It's done so that commit->util can be removed. See more explanation in the commit that removes commit->util. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-04-10Merge branch 'ys/bisect-object-id-missing-conversion-fix'Libravatar Junio C Hamano1-2/+2
Code clean-up. * ys/bisect-object-id-missing-conversion-fix: bisect: use oid_to_hex() for converting object_id hashes to hex strings
2018-03-25bisect: use oid_to_hex() for converting object_id hashes to hex stringsLibravatar René Scharfe1-2/+2
Patch generated with Coccinelle and contrib/coccinelle/object_id.cocci. Signed-off-by: Rene Scharfe <l.s.r@web.de> Reviewed-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>