Re: [PATCH v3 4/8] reftable: ensure tables in a stack use sequential update indices

[Junio C Hamano <gitster@pobox.com>]

Karthik Nayak <karthik.188@gmail.com> writes:

> Patrick Steinhardt <ps@pks.im> writes:
>
>> On Thu, Sep 18, 2025 at 10:11:45AM +0200, Karthik Nayak wrote:
>>> diff --git a/reftable/stack.c b/reftable/stack.c
>>> index 955be1edb6..a458f5a4c5 100644
>>> --- a/reftable/stack.c
>>> +++ b/reftable/stack.c
>>> @@ -317,6 +318,14 @@ static int reftable_stack_reload_once(struct reftable_stack *st,
>>>
>>>  		new_tables[new_tables_len] = table;
>>>  		new_tables_len++;
>>> +
>>> +		/* table's update indices must be sequential */
>>
>> Let's make this a full sentence starting with an upper-case letter and a
>> period.
>>
>>> +		if (prev_table && (prev_table->max_update_index != table->min_update_index - 1)) {
>>
>> I wonder whether this check is too strict. It _must_ be true that the
>> new table's minimum update index is greater than the previous table's
>> maximum update index. But in theory, there is no reason why there cannot
>> be a gap between those.
>>
>> The reason why this makes me a bit uneasy is stack compaction. Say we
>> have three different tables:
>>
>>   - A base table with record r1 with update index 1.
>>   - A second table with record r2 with update index 2.
>>   - A third table with a deletion record d(r2) and a new record r3 with
>>     update index 3.
>>
>> Now if we compact the second and the third table, the compaction will
>> realize that r2 is deleted and thus no longer needs to be part of the
>> compacted table. So the new state is:
>>
>>   - A base table with record r1 and update index r1.
>>   - The compacted table with record r3 with update index 3.
> ...
> However, I think your point  holds. I do think eventually we could
> optimize this to ensure that we do something like you described.
>
> I will make changes accordingly.

If you allow gaps in the indices, it is a bit confusing to call them
"sequential"; "monotonically increasing" is less confusing and it
conveys the author's intention to allow gaps clear (otherwise the
author wouldn't be using such an awkward two-word phrase instead of
"sequencial").