summaryrefslogtreecommitdiff
path: root/revision.c
AgeCommit message (Collapse)AuthorFilesLines
2016-05-06Merge branch 'bc/object-id'Libravatar Junio C Hamano1-2/+2
Move from unsigned char[20] to struct object_id continues. * bc/object-id: match-trees: convert several leaf functions to use struct object_id tree-walk: convert tree_entry_extract() to use struct object_id struct name_entry: use struct object_id instead of unsigned char sha1[20] match-trees: convert shift_tree() and shift_tree_by() to use object_id test-match-trees: convert to use struct object_id sha1-name: introduce a get_oid() function
2016-04-25struct name_entry: use struct object_id instead of unsigned char sha1[20]Libravatar brian m. carlson1-2/+2
Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-04-13Merge branch 'lt/pretty-expand-tabs'Libravatar Junio C Hamano1-0/+14
When "git log" shows the log message indented by 4-spaces, the remainder of a line after a HT does not align in the way the author originally intended. The command now expands tabs by default in such a case, and allows the users to override it with a new option, '--no-expand-tabs'. * lt/pretty-expand-tabs: pretty: test --expand-tabs pretty: allow tweaking tabwidth in --expand-tabs pretty: enable --expand-tabs by default for selected pretty formats pretty: expand tabs in indented logs to make things line up properly
2016-03-30pretty: allow tweaking tabwidth in --expand-tabsLibravatar Junio C Hamano1-2/+7
When the local convention of the project is to use tab width that is not 8, it may make sense to allow "git log --expand-tabs=<n>" to tweak the output to match it. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-03-30pretty: enable --expand-tabs by default for selected pretty formatsLibravatar Junio C Hamano1-0/+7
"git log --pretty={medium,full,fuller}" and "git log" by default prepend 4 spaces to the log message, so it makes sense to enable the new "expand-tabs" facility by default for these formats. Add --no-expand-tabs option to override the new default. The change alone breaks a test in t4201 that runs "git shortlog" on the output from "git log", and expects that the output from "git log" does not do such a tab expansion. Adjust the test to explicitly disable expand-tabs with --no-expand-tabs. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-03-30pretty: expand tabs in indented logs to make things line up properlyLibravatar Linus Torvalds1-0/+2
A commit log message sometimes tries to line things up using tabs, assuming fixed-width font with the standard 8-place tab settings. Viewing such a commit however does not work well in "git log", as we indent the lines by prefixing 4 spaces in front of them. This should all line up: Column 1 Column 2 -------- -------- A B ABCD EFGH SPACES Instead of Tabs Even with multi-byte UTF8 characters: Column 1 Column 2 -------- -------- Ä B åäö 100 A Møøse once bit my sister.. Tab-expand the lines in "git log --expand-tabs" output before prefixing 4 spaces. This is based on the patch by Linus Torvalds, but at this step, we require an explicit command line option to enable the behaviour. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-02-26Merge branch 'jk/tighten-alloc'Libravatar Junio C Hamano1-1/+1
Update various codepaths to avoid manually-counted malloc(). * jk/tighten-alloc: (22 commits) ewah: convert to REALLOC_ARRAY, etc convert ewah/bitmap code to use xmalloc diff_populate_gitlink: use a strbuf transport_anonymize_url: use xstrfmt git-compat-util: drop mempcpy compat code sequencer: simplify memory allocation of get_message test-path-utils: fix normalize_path_copy output buffer size fetch-pack: simplify add_sought_entry fast-import: simplify allocation in start_packfile write_untracked_extension: use FLEX_ALLOC helper prepare_{git,shell}_cmd: use argv_array use st_add and st_mult for allocation size computation convert trivial cases to FLEX_ARRAY macros use xmallocz to avoid size arithmetic convert trivial cases to ALLOC_ARRAY convert manual allocations to argv_array argv-array: add detach function add helpers for allocating flex-array structs harden REALLOC_ARRAY and xcalloc against size_t overflow tree-diff: catch integer overflow in combine_diff_path allocation ...
2016-02-22use st_add and st_mult for allocation size computationLibravatar Jeff King1-1/+1
If our size computation overflows size_t, we may allocate a much smaller buffer than we expected and overflow it. It's probably impossible to trigger an overflow in most of these sites in practice, but it is easy enough convert their additions and multiplications into overflow-checking variants. This may be fixing real bugs, and it makes auditing the code easier. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-02-12list-objects: pass full pathname to callbacksLibravatar Jeff King1-15/+2
When we find a blob at "a/b/c", we currently pass this to our show_object_fn callbacks as two components: "a/b/" and "c". Callbacks which want the full value then call path_name(), which concatenates the two. But this is an inefficient interface; the path is a strbuf, and we could simply append "c" to it temporarily, then roll back the length, without creating a new copy. So we could improve this by teaching the callsites of path_name() this trick (and there are only 3). But we can also notice that no callback actually cares about the broken-down representation, and simply pass each callback the full path "a/b/c" as a string. The callback code becomes even simpler, then, as we do not have to worry about freeing an allocated buffer, nor rolling back our modification to the strbuf. This is theoretically less efficient, as some callbacks would not bother to format the final path component. But in practice this is not measurable. Since we use the same strbuf over and over, our work to grow it is amortized, and we really only pay to memcpy a few bytes. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-02-12list-objects: drop name_path entirelyLibravatar Jeff King1-3/+3
In the previous commit, we left name_path as a thin wrapper around a strbuf. This patch drops it entirely. As a result, every show_object_fn callback needs to be adjusted. However, none of their code needs to be changed at all, because the only use was to pass it to path_name(), which now handles the bare strbuf. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-02-12list-objects: convert name_path to a strbufLibravatar Jeff King1-20/+5
The "struct name_path" data is examined in only two places: we generate it in process_tree(), and we convert it to a single string in path_name(). Everyone else just passes it through to those functions. We can further note that process_tree() already keeps a single strbuf with the leading tree path, for use with tree_entry_interesting(). Instead of building a separate name_path linked list, let's just use the one we already build in "base". This reduces the amount of code (especially tricky code in path_name() which did not check for integer overflows caused by deep or large pathnames). It is also more efficient in some instances. Any time we were using tree_entry_interesting, we were building up the strbuf anyway, so this is an immediate and obvious win there. In cases where we were not, we trade off storing "pathname/" in a strbuf on the heap for each level of the path, instead of two pointers and an int on the stack (with one pointer into the tree object). On a 64-bit system, the latter is 20 bytes; so if path components are less than that on average, this has lower peak memory usage. In practice it probably doesn't matter either way; we are already holding in memory all of the tree objects leading up to each pathname, and for normal-depth pathnames, we are only talking about hundreds of bytes. This patch leaves "struct name_path" as a thin wrapper around the strbuf, to avoid disrupting callbacks. We should fix them, but leaving it out makes this diff easier to view. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-02-12show_object_with_name: simplify by using path_name()Libravatar Jeff King1-34/+6
When "git rev-list" shows an object with its associated path name, it does so by walking the name_path linked list and printing each component (stopping at any embedded NULs or newlines). We'd like to eventually get rid of name_path entirely in favor of a single buffer, and dropping this custom printing code is part of that. As a first step, let's use path_name() to format the list into a single buffer, and print that. This is strictly less efficient than the original, but it's a temporary step in the refactoring; our end game will be to get the fully formatted name in the first place. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-02-05Merge branch 'nd/diff-with-path-params' into maintLibravatar Junio C Hamano1-1/+1
A few options of "git diff" did not work well when the command was run from a subdirectory. * nd/diff-with-path-params: diff: make -O and --output work in subdirectory diff-no-index: do not take a redundant prefix argument
2016-02-03Merge branch 'nd/diff-with-path-params'Libravatar Junio C Hamano1-1/+1
A few options of "git diff" did not work well when the command was run from a subdirectory. * nd/diff-with-path-params: diff: make -O and --output work in subdirectory diff-no-index: do not take a redundant prefix argument
2016-01-21diff: make -O and --output work in subdirectoryLibravatar Duy Nguyen1-1/+1
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-01-15revision: read --stdin with strbuf_getline()Libravatar Junio C Hamano1-7/+2
Reading with getwholeline() and manually stripping the terminating '\n' would leave CR at the end of the line if the input comes from a DOS editor. Constrasting this with the other changes around "--stdin" in this series, one may realize that the way "log" family of commands read the paths with "--stdin" looks inconsistent and sloppy. It does not allow us to C-quote a textual input, neither does it accept records that are NUL-terminated. These are unfortunately way too late to fix X-<. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-01-04Merge branch 'jk/pending-keep-tag-name' into maintLibravatar Junio C Hamano1-2/+1
History traversal with "git log --source" that starts with an annotated tag failed to report the tag as "source", due to an old regression in the command line parser back in v2.2 days. * jk/pending-keep-tag-name: revision.c: propagate tag names from pending array
2015-12-28Merge branch 'jk/pending-keep-tag-name'Libravatar Junio C Hamano1-2/+1
History traversal with "git log --source" that starts with an annotated tag failed to report the tag as "source", due to an old regression in the command line parser back in v2.2 days. * jk/pending-keep-tag-name: revision.c: propagate tag names from pending array
2015-12-17revision.c: propagate tag names from pending arrayLibravatar Jeff King1-2/+1
When we unwrap a tag to find its commit for a traversal, we do not propagate the "name" field of the tag in the pending array (i.e., the ref name the user gave us in the first place) to the commit (instead, we use an empty string). This means that "git log --source" will never show the tag-name for commits we reach through it. This was broken in 2073949 (traverse_commit_list: support pending blobs/trees with paths, 2014-10-15). That commit tried to be careful and avoid propagating the path information for a tag (which would be nonsensical) to trees and blobs. But it should not have cut off the "name" field, which should carry forward to children. Note that this does mean that the "name" field will carry forward to blobs and trees, too. Whereas prior to 2073949, we always gave them an empty string. This is the right thing to do, but in practice no callers probably use it (since now we have an explicit separate "path" field, which was the point of 2073949). We add tests here not only for the broken case, but also a basic sanity test of "log --source" in general, which did not have any coverage in the test suite. Reported-by: Raymundo <gypark@gmail.com> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-12-11Merge branch 'sn/null-pointer-arith-in-mark-tree-uninteresting' into maintLibravatar Junio C Hamano1-1/+3
mark_tree_uninteresting() has code to handle the case where it gets passed a NULL pointer in its 'tree' parameter, but the function had 'object = &tree->object' assignment before checking if tree is NULL. This gives a compiler an excuse to declare that tree will never be NULL and apply a wrong optimization. Avoid it. * sn/null-pointer-arith-in-mark-tree-uninteresting: revision.c: fix possible null pointer arithmetic
2015-12-11Merge branch 'rs/pop-commit' into maintLibravatar Junio C Hamano1-22/+5
Code simplification. * rs/pop-commit: use pop_commit() for consuming the first entry of a struct commit_list
2015-12-11Merge branch 'sn/null-pointer-arith-in-mark-tree-uninteresting'Libravatar Junio C Hamano1-1/+3
mark_tree_uninteresting() has code to handle the case where it gets passed a NULL pointer in its 'tree' parameter, but the function had 'object = &tree->object' assignment before checking if tree is NULL. This gives a compiler an excuse to declare that tree will never be NULL and apply a wrong optimization. Avoid it. * sn/null-pointer-arith-in-mark-tree-uninteresting: revision.c: fix possible null pointer arithmetic
2015-12-07revision.c: fix possible null pointer arithmeticLibravatar Stefan Naewe1-1/+3
mark_tree_uninteresting() dereferences a tree pointer before checking if the pointer is valid. Fix that by doing the check first. Signed-off-by: Stefan Naewe <stefan.naewe@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-11-20Remove get_object_hash.Libravatar brian m. carlson1-8/+8
Convert all instances of get_object_hash to use an appropriate reference to the hash member of the oid member of struct object. This provides no functional change, as it is essentially a macro substitution. Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Jeff King <peff@peff.net>
2015-11-20Convert struct object to object_idLibravatar brian m. carlson1-16/+16
struct object is one of the major data structures dealing with object IDs. Convert it to use struct object_id instead of an unsigned char array. Convert get_object_hash to refer to the new member as well. Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Jeff King <peff@peff.net>
2015-11-20Add several uses of get_object_hash.Libravatar brian m. carlson1-8/+8
Convert most instances where the sha1 member of struct object is dereferenced to use get_object_hash. Most instances that are passed to functions that have versions taking struct object_id, such as get_sha1_hex/get_oid_hex, or instances that can be trivially converted to use struct object_id instead, are not converted. Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Jeff King <peff@peff.net>
2015-10-30Merge branch 'rs/pop-commit'Libravatar Junio C Hamano1-22/+5
Code simplification. * rs/pop-commit: use pop_commit() for consuming the first entry of a struct commit_list
2015-10-26use pop_commit() for consuming the first entry of a struct commit_listLibravatar René Scharfe1-22/+5
Instead of open-coding the function pop_commit() just call it. This makes the intent clearer and reduces code size. Signed-off-by: Rene Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-10-05prefer memcpy to strcpyLibravatar Jeff King1-1/+1
When we already know the length of a string (e.g., because we just malloc'd to fit it), it's nicer to use memcpy than strcpy, as it makes it more obvious that we are not going to overflow the buffer (because the size we pass matches the size in the allocation). This also eliminates calls to strcpy, which make auditing the code base harder. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-09-03Merge branch 'jk/log-missing-default-HEAD' into maintLibravatar Junio C Hamano1-1/+16
"git init empty && git -C empty log" said "bad default revision 'HEAD'", which was found to be a bit confusing to new users. * jk/log-missing-default-HEAD: log: diagnose empty HEAD more clearly
2015-09-02Merge branch 'jk/log-missing-default-HEAD'Libravatar Junio C Hamano1-1/+16
"git init empty && git -C empty log" said "bad default revision 'HEAD'", which was found to be a bit confusing to new users. * jk/log-missing-default-HEAD: log: diagnose empty HEAD more clearly
2015-08-31log: diagnose empty HEAD more clearlyLibravatar Jeff King1-1/+16
If you init or clone an empty repository, the initial message from running "git log" is not very friendly: $ git init Initialized empty Git repository in /home/peff/foo/.git/ $ git log fatal: bad default revision 'HEAD' Let's detect this situation and write a more friendly message: $ git log fatal: your current branch 'master' does not have any commits yet We also detect the case that 'HEAD' points to a broken ref; this should be even less common, but is easy to see. Note that we do not diagnose all possible cases. We rely on resolve_ref, which means we do not get information about complex cases. E.g., "--default master" would use dwim_ref to find "refs/heads/master", but we notice only that "master" does not exist. Similarly, a complex sha1 expression like "--default HEAD^2" will not resolve as a ref. But that's OK. We fall back to a generic error message in those cases, and they are unlikely to be used anyway. Catching an empty or broken "HEAD" improves the common case, and the other cases are not regressed. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-08-12Merge branch 'ad/bisect-cleanup'Libravatar Junio C Hamano1-2/+16
Code and documentation clean-up to "git bisect". * ad/bisect-cleanup: bisect: don't mix option parsing and non-trivial code bisect: simplify the addition of new bisect terms bisect: replace hardcoded "bad|good" by variables Documentation/bisect: revise overall content Documentation/bisect: move getting help section to the end bisect: correction of typo
2015-08-03bisect: simplify the addition of new bisect termsLibravatar Antoine Delaite1-2/+16
We create a file BISECT_TERMS in the repository .git to be read during a bisection. There's no user-interface yet, but "git bisect" works if terms other than old/new or bad/good are set in .git/BISECT_TERMS. The fonctions to be changed if we add new terms are quite few. In git-bisect.sh: check_and_set_terms bisect_voc Co-authored-by: Louis Stuber <stuberl@ensimag.grenoble-inp.fr> Tweaked-by: Matthieu Moy <Matthieu.Moy@imag.fr> Signed-off-by: Antoine Delaite <antoine.delaite@ensimag.grenoble-inp.fr> Signed-off-by: Louis Stuber <stuberl@ensimag.grenoble-inp.fr> Signed-off-by: Valentin Duperray <Valentin.Duperray@ensimag.imag.fr> Signed-off-by: Franck Jonas <Franck.Jonas@ensimag.imag.fr> Signed-off-by: Lucien Kong <Lucien.Kong@ensimag.imag.fr> Signed-off-by: Thomas Nguy <Thomas.Nguy@ensimag.imag.fr> Signed-off-by: Huynh Khoi Nguyen Nguyen <Huynh-Khoi-Nguyen.Nguyen@ensimag.imag.fr> Signed-off-by: Matthieu Moy <Matthieu.Moy@imag.fr> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-08-03Merge branch 'jk/date-mode-format'Libravatar Junio C Hamano1-2/+2
Teach "git log" and friends a new "--date=format:..." option to format timestamps using system's strftime(3). * jk/date-mode-format: strbuf: make strbuf_addftime more robust introduce "format" date-mode convert "enum date_mode" into a struct show-branch: use DATE_RELATIVE instead of magic number
2015-07-17Merge branch 'jk/still-interesting'Libravatar Junio C Hamano1-2/+2
Code clean-up. * jk/still-interesting: revision.c: remove unneeded check for NULL
2015-06-29convert "enum date_mode" into a structLibravatar Jeff King1-2/+2
In preparation for adding date modes that may carry extra information beyond the mode itself, this patch converts the date_mode enum into a struct. Most of the conversion is fairly straightforward; we pass the struct as a pointer and dereference the type field where necessary. Locations that declare a date_mode can use a "{}" constructor. However, the tricky case is where we use the enum labels as constants, like: show_date(t, tz, DATE_NORMAL); Ideally we could say: show_date(t, tz, &{ DATE_NORMAL }); but of course C does not allow that. Likewise, we cannot cast the constant to a struct, because we need to pass an actual address. Our options are basically: 1. Manually add a "struct date_mode d = { DATE_NORMAL }" definition to each caller, and pass "&d". This makes the callers uglier, because they sometimes do not even have their own scope (e.g., they are inside a switch statement). 2. Provide a pre-made global "date_normal" struct that can be passed by address. We'd also need "date_rfc2822", "date_iso8601", and so forth. But at least the ugliness is defined in one place. 3. Provide a wrapper that generates the correct struct on the fly. The big downside is that we end up pointing to a single global, which makes our wrapper non-reentrant. But show_date is already not reentrant, so it does not matter. This patch implements 3, along with a minor macro to keep the size of the callers sane. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-06-29revision.c: remove unneeded check for NULLLibravatar Stefan Beller1-2/+2
The function is called only from one place, which makes sure to have `interesting_cache` not NULL. Additionally the variable is a dereferenced a few lines before unconditionally, which would have resulted in a segmentation fault before hitting this check. Signed-off-by: Stefan Beller <sbeller@google.com> Acked-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-06-11Merge branch 'jk/squelch-missing-link-warning-for-unreachable'Libravatar Junio C Hamano1-2/+2
Recent "git prune" traverses young unreachable objects to safekeep old objects in the reachability chain from them, which sometimes caused error messages that are unnecessarily alarming. * jk/squelch-missing-link-warning-for-unreachable: suppress errors on missing UNINTERESTING links silence broken link warnings with revs->ignore_missing_links add quieter versions of parse_{tree,commit}
2015-06-01suppress errors on missing UNINTERESTING linksLibravatar Jeff King1-1/+1
When we are traversing commit parents along the UNINTERESTING side of a revision walk, we do not care if the parent turns out to be missing. That lets us limit traversals using unreachable and possibly incomplete sections of history. However, we do still print error messages about the missing commits; this patch suppresses the error, as well. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-06-01silence broken link warnings with revs->ignore_missing_linksLibravatar Jeff King1-1/+1
We set revs->ignore_missing_links to instruct the revision-walking machinery that we know the history graph may be incomplete. For example, we use it when walking unreachable but recent objects; we want to add what we can, but it's OK if the history is incomplete. However, we still print error messages for the missing objects, which can be confusing. This is not an error, but just a normal situation when transitioning from a repository last pruned by an older git (which can leave broken segments of history) to a more recent one (where we try to preserve whole reachable segments). Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-05-25handle_one_reflog(): rewrite to take an object_id argumentLibravatar Michael Haggerty1-4/+3
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu> Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-05-25handle_one_ref(): rewrite to take an object_id argumentLibravatar Michael Haggerty1-26/+9
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu> Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-05-25each_ref_fn: change to take an object_id parameterLibravatar Michael Haggerty1-6/+27
Change typedef each_ref_fn to take a "const struct object_id *oid" parameter instead of "const unsigned char *sha1". To aid this transition, implement an adapter that can be used to wrap old-style functions matching the old typedef, which is now called "each_ref_sha1_fn"), and make such functions callable via the new interface. This requires the old function and its cb_data to be wrapped in a "struct each_ref_fn_sha1_adapter", and that object to be used as the cb_data for an adapter function, each_ref_fn_adapter(). This is an enormous diff, but most of it consists of simple, mechanical changes to the sites that call any of the "for_each_ref" family of functions. Subsequent to this change, the call sites can be rewritten one by one to use the new interface. Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu> Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-05-11Merge branch 'jk/still-interesting'Libravatar Junio C Hamano1-4/+19
"git rev-list --objects $old --not --all" to see if everything that is reachable from $old is already connected to the existing refs was very inefficient. * jk/still-interesting: limit_list: avoid quadratic behavior from still_interesting
2015-04-17limit_list: avoid quadratic behavior from still_interestingLibravatar Jeff King1-4/+19
When we are limiting a rev-list traversal due to UNINTERESTING refs, we have to walk down the tips (both interesting and uninteresting) to find where they intersect. We keep a queue of commits to examine, pop commits off the queue one by one, and potentially add their parents. The size of the queue will naturally fluctuate based on the "width" of the history graph; i.e., the number of simultaneous lines of development. But for the most part it will stay in the same ballpark as the initial number of tips we fed, shrinking over time (as we hit common ancestors of the tips). So roughly speaking, if we start with `N` tips, we'll spend much of the time with a queue around `N` items. For each UNINTERESTING commit we pop, we call still_interesting to check whether marking its parents as UNINTERESTING has made the whole queue uninteresting (in which case we can quit early). Because the queue is stored as a linked list, this is `O(N)`, where `N` is the number of items in the queue. So processing a queue with `N` commits marked UNINTERESTING (and one or more interesting commits) will take `O(N^2)`. If you feed a lot of positive tips, this isn't a problem. They aren't UNINTERESTING, so they don't incur the still_interesting check. It also isn't a problem if you traverse from an interesting tip to some UNINTERESTING bases. We order the queue by recency, so the interesting commits stay at the front of the queue as we walk down them. The linear check can exit early as soon as it sees one interesting commit left in the queue. But if you want to know whether an older commit is reachable from a set of newer tips, we end up processing in the opposite direction: from the UNINTERESTING ones down to the interesting one. This may happen when we call: git rev-list $commits --not --all in check_everything_connected after a fetch. If we fetched something much older than most of our refs, and if we have a large number of refs, the traversal cost is dominated by the quadratic behavior. These commands simulate the connectivity check of such a fetch, when you have `$n` distinct refs in the receiver: # positive ref is 100,000 commits deep git rev-list --all | head -100000 | tail -1 >input # huge number of more recent negative refs git rev-list --all | head -$n | sed s/^/^/ >>input time git rev-list --stdin <input Here are timings for various `n` on the linux.git repository. The `n=1` case provides a baseline for just walking the commits, which lets us see the still_interesting overhead. The times marked with `+` subtract that baseline to show just the extra time growth due to the large number of refs. The `x` numbers show the slowdown of the adjusted time versus the prior trial. n | before | after -------------------------------------------------------- 1 | 0.991s | 0.848s 10000 | 1.120s (+0.129s) | 0.885s (+0.037s) 20000 | 1.451s (+0.460s, 3.5x) | 0.923s (+0.075s, 2.0x) 40000 | 2.731s (+1.740s, 3.8x) | 0.994s (+0.146s, 1.9x) 80000 | 8.235s (+7.244s, 4.2x) | 1.123s (+0.275s, 1.9x) Each trial doubles `n`, so you can see the quadratic (`4x`) behavior before this patch. Afterwards, we have a roughly linear relationship. The implementation is fairly straightforward. Whenever we do the linear search, we cache the interesting commit we find, and next time check it before doing another linear search. If that commit is removed from the list or becomes UNINTERESTING itself, then we fall back to the linear search. This is very similar to the trick used by fce87ae (Fix quadratic performance in rewrite_one., 2008-07-12). I considered and rejected several possible alternatives: 1. Keep a count of UNINTERESTING commits in the queue. This requires managing the count not only when removing an item from the queue, but also when marking an item as UNINTERESTING. That requires touching the other functions which mark commits, and would require knowing quickly which commits are in the queue (lookup in the queue is linear, so we would need an auxiliary structure or to also maintain an IN_QUEUE flag in each commit object). 2. Keep a separate list of interesting commits. Drop items from it when they are dropped from the queue, or if they become UNINTERESTING. This again suffers from extra complexity to maintain the list, not to mention CPU and memory. 3. Use a better data structure for the queue. This is something that could help the fix in fce87ae, because we order the queue by recency, and it is about inserting quickly in recency order. So a normal priority queue would help there. But here, we cannot disturb the order of the queue, which makes things harder. We really do need an auxiliary index to track the flag we care about, which is basically option (2) above. The "cache" trick is simple, and the numbers above show that it works well in practice. This is because the length of time it takes to find an interesting commit is proportional to the length of time it will remain cached (i.e., if we have to walk a long way to find it, it also means we have to pop a lot of elements in the queue until we get rid of it and have to find another interesting commit). The worst case is still quadratic, though. We could have `N` uninteresting commits at the front of the queue, followed by `N` interesting commits, where commit `i` has parent `i+N`. When we pop commit `i`, we will notice that the parent of the next commit, `i+1+N` is still interesting and cache it. But then handling commit `i+1`, we will mark its parent `i+1+N` uninteresting, and immediately invalidate our cache. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-03-25Merge branch 'dj/log-graph-with-no-walk'Libravatar Junio C Hamano1-0/+2
"git log --graph --no-walk A B..." is a otcnflicting request that asks nonsense; no-walk tells us show discrete points in the history, while graph asks to draw connections between these discrete points. Forbid the combination. * dj/log-graph-with-no-walk: revision: forbid combining --graph and --no-walk
2015-03-25Merge branch 'kd/rev-list-bisect-first-parent'Libravatar Junio C Hamano1-0/+3
"git rev-list --bisect --first-parent" does not work (yet) and can even cause SEGV; forbid it. "git log --bisect --first-parent" would not be useful until "git bisect --first-parent" materializes, so it is also forbidden for now. * kd/rev-list-bisect-first-parent: rev-list: refuse --first-parent combined with --bisect
2015-03-19rev-list: refuse --first-parent combined with --bisectLibravatar Kevin Daudt1-0/+3
rev-list --bisect is used by git bisect, but never together with --first-parent. Because rev-list --bisect together with --first-parent is not handled currently, and even leads to segfaults, refuse to use both options together. Because this is not supported, it makes little sense to use git log --bisect --first parent either, because refs/heads/bad is not limited to the first parent chain. Helped-by: Junio C. Hamano <gitster@pobox.com> Helped-by: Eric Sunshine <sunshine@sunshineco.com> Signed-off-by: Kevin Daudt <me@ikke.info> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2015-03-19revision: forbid combining --graph and --no-walkLibravatar Dongcan Jiang1-0/+2
Because "--graph" is about connected history while --no-walk is about discrete points, it does not make sense to allow these two options at the same time. [1] This change makes a few calls to "show --graph" fail in t4052, but asking to show one commit with graph is a nonsensical thing to do. Thus, tests on "show --graph" in t4052 have been removed [2,3]. Same tests on "show" without --graph option have already been tested in 4052. 3 testcases have been added to test this patch. [1]: http://article.gmane.org/gmane.comp.version-control.git/216083 [2]: http://article.gmane.org/gmane.comp.version-control.git/264950 [3]: http://article.gmane.org/gmane.comp.version-control.git/265107 Helped-By: Eric Sunshine <sunshine@sunshineco.com> Helped-By: René Scharfe <l.s.r@web.de> Helped-By: Junio C Hamano <gitster@pobox.com> Signed-off-by: Dongcan Jiang <dongcan.jiang@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>