Libelektra: keyIsBelow and friends

[kodebach]

A simple question: Should keyIsBelow and friends work, if the first argument is a cascading key?

[markus2330]

I think it safe to say "no" as it is not specified how it should work and there are hardly any tests for it. Some support was implemented by @tom-wa in 36e0ed568689a5e0f9778bb44d2c8621912a423f and 52db645bf456f15200a441a14aa0ec045c1799ef (iirc, the commit message does not say much). But as you know, the spec plugin is quite buggy and that keyIsBelow is not specified properly is one of the main reasons.

[kodebach]

Why is the code even so complicated? Shouldn't it be a simple memcmp for the non cascading case? After all we are just doing a prefix check. If key is cascading it should be enough to ignore the first part of both keys. So the following should work:

int keyIsBelow (const Key * key, const Key * check)
{
    const void * above = keyUnescapedName (key);
    const void * below = keyUnescapedName (check);

    size_t size1 = keyGetNamespace (key);
    size_t size2 = keyGetNamespace (check);

    size_t size = size1 < size2 ? size1 : size2;

    if(above[0] == '\0')
    {
        // cascading
        below = strchr (below, '\0');
    }

    return memcmp (above, below, size) == 0;
}

Or am I missing something here?

EDIT: just noticed the above code would be for keyIsBelowOrSame, the "same" case could just be strip out be checking wether the sizes are the same.

[markus2330]

Why is the code even so complicated?

It was written before unescaped names existed and it was not simplified after it was introduced.

I fully support your new implementation, please try in a PR if it works.

just noticed the above code would be for keyIsBelowOrSame

It does not matter: then simply call keyIsBelowOrSame within keyIsBelow.

[markus2330]

(In the PR it is also easier to give feedback to the individual lines.)

[kodebach]

I just found testabi_key.c, it seems the behaviour keyIsBelow is indirectly defined by those tests. But I am not sure these tests are correct. They contain for example:

https://github.com/ElektraInitiative/libelektra/blob/54a4c0194946917b7d093e0777f465619b2f3d6f/tests/abi/testabi_key.c#L1362-L1365

[markus2330]

But I am not sure these tests are correct.

Nobody is because there is no specification how it should be. (cascading as "match all" vs. cascading as normal namespace).

I am not sure what problems @tom-wa had with the "match all" semantics (indicated by this unit test) but it might be that the double-meaning of cascading keys are the problem (they might use to match a key of any namespace or they might be used as default keys). If we avoid cascading keys as default keys (and return the spec keys with the value instead), we should also avoid this double meaning.

If we really have to support both semantics, we could introduce a flag set as argument to keyBelow (because external functions make Elektra bigger), which could be:

• make cascading "match all" (how the unit test above is or the opposite if the flag is not set)
• equal matches (then we would not need keyIsBelowOrEqual)

But I would prefer to not do that.

In any case: If we do incompatible changes, we should also consider to remove keyRel (which is buggy and mostly unused). See also doc/todo/FUTURE for other candidates.

[kodebach]

I found the semantics of the current keyIsBelow and friends adequate for what I needed. There is one weird edge case (the cascading root key doesn't match other root keys, but otherwise cascading keys match all namespaces), but that didn't affect me.

Nonetheless, I reimplemented the functions using memcmp for performance reasons. I will also update the documentation of the functions to reflect what the ABI tests are testing.

[mpranj]

@kodebach thank you for this improvement! I actually did an informal benchmark where keyIsBelowOrSame / keyIsBelow (caused by ksCut in the spec plugin) took a considerable portion of the time (25% of kdbGet!).

[markus2330]

Very nice solution and great to have this performance improvement!