On Sat, Jul 16, 2022 at 3:45 AM Taylor Blau <me@xxxxxxxxxxxx> wrote:
>
> On Fri, Jul 15, 2022 at 09:28:25PM +0530, Abhradeep Chakraborty wrote:
> > > If that's the case, then I'd expect that printing `index[table[j]]` for
> > > increasing `j` would output OIDs in increasing lexical order. But that
> > > doesn't quite seem to be the case. From a debugger session that has a
> > > breakpoint after computing and sorting table, along with building
> > > `table_inv`:
> > >
> > > (gdb) p oid_to_hex(&index[table[0]]->oid)
> > > $17 = 0x555555983ea0 <hexbuffer> "0006763074748d43b539c1c8e8882c08034ab178"
> > > (gdb) p oid_to_hex(&index[table[1]]->oid)
> > > $18 = 0x555555983ee1 <hexbuffer+65> "001ce83dd43f03dcfc67f29d38922e4a9682aab0"
> > > (gdb) p oid_to_hex(&index[table[2]]->oid)
> > > $19 = 0x555555983f22 <hexbuffer+130> "002db882ece2ab6a240e495a169c6e06422289c8"
> > > (gdb) p oid_to_hex(&index[table[3]]->oid)
> > > $20 = 0x555555983f63 <hexbuffer+195> "0007a5feb040e1ff704f3ad636619ddca3e7382b"
> > >
> > > that doesn't look like the OIDs are increasing in lexical order.
> > >
> > > I'm not quite sure if I'm even looking at the right thing, or if this is
> > > to be expected, or if the comment isn't quite accurate. If you could
> > > help clarify what's going on here, that would be great.
> >
> > I think you're not looking at the right thing. you should look at
> > `writer.selected[table[i]].commit->object.oid` instead. I think the
> > order of `index[]`
> > is not the same as the pack index (or midx).
> >
> > I am saying this because if we use the `pos` variable (that we get
> > from `commit_bitmap_writer_pos(&writer.selected[table[i]].commit->object.oid,
> > index, index_nr)`) in `fprintf(stderr, "commit hex: %s\n",
> > &index[pos]->oid);`, you'll see that `&index[pos]->oid` and
> > `&writer.selected[table[i]].commit->object.oid` are not same. So, If
> > you do -
> >
> > int spos = commit_bitmap_writer_pos(&index[pos]->oid, index, index_nr);
> >
> > you'll see `spos` is not equal to `pos`.
>
> `index` there comes from the list of objects that `pack-objects` or the
> MIDX told us about, and it's sorted in lexical order (via
> `write_pack_file()` -> `stage_tmp_packfiles()` -> `write_idx_file()`).
This was a bit strange for me because all the tests were passing. But
now I find the reason why your results were not in lexical order. you
were doing `oid_to_hex(&index[table[i]]->oid)` which is not what you
intended to do. Let me explain it with a simple workflow -
Suppose 12 commits are selected for bitmaps and are sorted by their
date. I will now use their index numbers to denote those commits
(i.e. `0` denotes the most recent commit, `1` denotes the second
commit in this order and so on..).
So, before that quick sort, `table` = {0,1, 2, 3, 4, ...,11}. Now
suppose, `11`th commit is lexically smallest among all the selected
commits, `5`th commit is the second smallest commit and so on. So,
after that quick sort, `table` array now contains the following - {11,
5, 9, 4,0, 3, ...}.
So, when you do `&index[table[0]]->oid`, it becomes `&index[11]->oid`.
Similarly, `&index[table[1]]->oid` becomes `&index[5]->oid` and so on.
That's why you're not getting the oids in lexical order -
`&index[11]->oid` gives the 11th oid in the pack-index and
`&index[5]->oid` gives the 5th oid in the pack-index.
So, the right thing would be to do
`&index[commit_positions[table[0]]]->oid`,
`&index[commit_positions[table[1]]]->oid` ...
Here `&index[commit_positions[table[0]]]->oid` becomes
`&index[commit_positions[11]]->oid` =>
`&index[pos_of_11_commit_with_respect_to_pack_index]->oid` which
ultimately prints the oid of 11th commit ( among the selected bitmap
commits IN THE SELECTED BITMAP COMMIT ORDER) .
I think the comment I added is not that good. The following might be better -
At the end of this sort table[j] = i means that the i'th
bitmap corresponds to j'th bitmapped commit (among the selected commits)
in lex order of OIDs.
> Thanks,
> Taylor
