On Thu, Jul 06, 2017 at 03:16:06AM -0400, Jeff King wrote:
> If we think it's buggy, we can fix it now. But I'm not convinced that
> sequential iteration is that bad. It's at least _simple_ and easy to
> explain. The only other thing that would make sense to me is sorting the
> entries by date (reflog date, not commit date) and showing them in that
> order. But that gives rise to some funny corner cases.
>
> What do we do if there's clock skew within the reflog (e.g., somebody
> fixed their skewed clock such that HEAD@{5} is less recent than
> HEAD@{6}). Do we show them out of order then (even if only a single
> reflog is being shown?).
>
> Or do we try some complicated sort where entries compare sequentially
> within a given reflog, but use date comparisons between different logs?
> I don't think that can work with a normal comparison sort, as it makes
> the comparison non-transitive.
>
> But maybe we could do a pseudo-list-merge, where we treat the reflogs as
> queues and always pick from the queue with the most recent timestamp.
>
> That would probably be pretty easy to retrofit on the iteration from the
> current series.
Something like the patch below. Looking over the output, the
interleaving makes it look confusing (especially if you don't use
--date, since then the interleaved numbers have no relation to each
other).
It would help if we actually had a use case where somebody really did
want to show two reflogs from a single command. Then we'd know what they
were expecting and which output would be most useful, at least for that
case. But I can't really think of why you'd want to do so (which is
probably why nobody noticed for years that the current behavior is so
broken).
---
diff --git a/reflog-walk.c b/reflog-walk.c
index a7644d944e..6cdf7bfb0f 100644
--- a/reflog-walk.c
+++ b/reflog-walk.c
@@ -90,7 +90,7 @@ struct commit_reflog {
struct reflog_walk_info {
struct commit_reflog **logs;
- size_t nr, alloc, cur;
+ size_t nr, alloc;
struct string_list complete_reflogs;
struct commit_reflog *last_commit_reflog;
};
@@ -284,26 +284,43 @@ int reflog_walk_empty(struct reflog_walk_info *info)
return !info || !info->nr;
}
-struct commit *next_entry_in_log(struct commit_reflog *log)
+static void skip_unusable_entries(struct commit_reflog *log)
{
while (log->recno >= 0) {
- struct reflog_info *entry = &log->reflogs->items[log->recno--];
+ struct reflog_info *entry = &log->reflogs->items[log->recno];
struct object *obj = parse_object(&entry->noid);
if (obj && obj->type == OBJ_COMMIT)
- return (struct commit *)obj;
+ return;
+ log->recno--;
}
- return NULL;
+}
+
+static timestamp_t next_timestamp(struct commit_reflog *log)
+{
+ return log->reflogs->items[log->recno].timestamp;
}
struct commit *next_reflog_entry(struct reflog_walk_info *walk)
{
- for (; walk->cur < walk->nr; walk->cur++) {
- struct commit *ret = next_entry_in_log(walk->logs[walk->cur]);
- if (ret) {
- walk->last_commit_reflog = walk->logs[walk->cur];
- return ret;
- }
+ struct commit_reflog *best = NULL;
+ size_t i;
+
+ for (i = 0; i < walk->nr; i++) {
+ struct commit_reflog *log = walk->logs[i];
+
+ skip_unusable_entries(log);
+ if (log->recno < 0)
+ continue;
+
+ if (!best || next_timestamp(log) > next_timestamp(best))
+ best = log;
}
+
+ if (best) {
+ walk->last_commit_reflog = best;
+ return lookup_commit(&best->reflogs->items[best->recno--].noid);
+ }
+
return NULL;
}
The implementation is fairly naive. It would be O(nr_reflogs *
nr_entries) in the worst case. I wouldn't expect nr_reflogs to get
large. But if we cared, we could fix it by keeping the reflogs in a
heap.
-Peff
