libctf: new enum-related API functions: request for better names

[Stephen Brennan]

Hi Nick,

I'm not subscribed here but found the mailto: link with In-Reply-To
header set on the archive page; hopefully this reply works as expected.

Nick Alcock writes:
> So Stephen Brennan pointed out many years ago that libctf's handling of
> enumeration constants is needlessly unhelpful: it treats them as if they
> are scoped within a given enum: you can only query from constant name ->
> value and back within a given enum's scope, so if you don't already know
> what enum something is part of you have to walk over every enum in the
> dict hunting for it.
>
> Worse yet, we do not consider enum constants with clashing values to be
> a sign of a type conflict, so can easily end up with multiple distinct
> enums containing enumeration constants with the *same name* appearing
> in the shared dict. This definitely violates the principle of least
> surprise and the (largely unstated) assumption that the shared dict
> should be "as if" the entire C program's non-conflicting types were
> declared in a single giant file which was compiled with -gctf: you can't
> write a C file that declares the same enumeration constant twice!
>
> Half of this is easy to fix: libctf, and in particular the deduplicator,
> should track enumeration constant names just like it does all other
> identifiers, and push enums with clashing names into child dicts. (This
> might eat a lot of space when the enums have many other enumerators, but
> most of that space is identical strings, which means we can win nearly
> all the space back in v4 via the string-saving trick that is the second
> entry in <https://sourceware.org/binutils/wiki/CTF/Todo/Compactness>.)
>
> But I'm having trouble figuring out names for the new API functions
> we'll need for the rest.  Right now libctf has these:
>
> /* Convert the specified value to the corresponding enum tag name, if a
>    matching name can be found.  Otherwise NULL is returned.  */
>
> const char *ctf_enum_name (ctf_dict_t *fp, ctf_id_t type, int value);
>
> /* Convert the specified enum tag name to the corresponding value, if a
>    matching name can be found.  Otherwise CTF_ERR is returned.  */
>
> int ctf_enum_value (ctf_dict_t *fp, ctf_id_t type, const char *name,
> 		    int *valp);
>
> /* Iterate over the members of an ENUM.  We pass the string name and
>    associated integer value of each enum element to the specified callback
>    function.  */
>
> int ctf_enum_iter (ctf_dict_t *fp, ctf_id_t type, ctf_enum_f *func, void *arg);
>
> /* Iterate over the members of an enum TYPE, returning each enumerand's NAME or
>    NULL at end of iteration or error, and optionally passing back the
>    enumerand's integer VALue.  */
>
> const char *ctf_enum_next (ctf_dict_t *fp, ctf_id_t type, ctf_next_t **it,
>     	                   int *val);
>
> At the very least we want something like dict-wide equivalents of the
> first two: but ctf_enum_name has the very annoying behaviour of just
> picking the first name if there are multiple conflicting ones with the
> same value, and on a dict-wide basis there will be huge numbers of these
> (can you imagine how many enumeration constants have the value 1? :) )

I've never personally had a use-case for ctf_enum_name(), looking up an
enumerator by the integer value. However, I can understand why you might
want to do it if you know the type ID already (e.g. a debugger may want
to represent an enum variable with the symbolic name).

But I can't imagine a case where:

  a. I have an integer value, and I know it's an enum, but
  b. I don't know which enum type it belongs to, and yet
  c. I *do* know which CTF dictionary it belongs to...
  d. And I want to get the list of all possible enumerators it could be

Maybe I'm deficient in imagination. I'm sure this use case could come
up, but is it something that libctf really ought to optimize for?  I'd
argue that there are only two use cases that really ought to be
supported at the dict-wide level:

1. Lookup an enumerator by name. This is something that users of C do
constantly, implicitly, just by using the constant name in their source
code. So libctf really ought to support it efficiently with some sort of
string index. (IMO, it should be supported at the dict and archive
level).

2. Iterate over all enumerators. This one is already supported quite
well in with libctf today:

ctf_next_t *next = NULL, *enum_next;
ctf_id_t id;
int isroot, enum_value;
const char *enum_name;
while ((id = ctf_type_next(dict, &next, &isroot, 1)) != CTF_ERR) {
    if (ctf_type_kind(dict, id) != CTF_K_ENUM)
        continue;
    enum_next = NULL;
    while ((enum_name = ctf_enum_next(dict, id, &enum_next, &enum_value))) {
        /* do something with (dict, id, enum_name, enum_value, isroot) */
    }
}

You could introduce an API to eliminate some of the boilerplate, which
could be nice enough. As an existing user, I probably wouldn't take
advantage of the new function, since I need to support older libctf
versions. New users might appreciate not needing to write this
function. However, a new API for this would be much less flexible... The
above function allows me to run code for each enum type, before and
after handling all of the enumerators for that type. A
ctf_enumerator_next() function cannot really give me that information.
I'd argue it would be better to let users manually do their own
iteration. Especially since they could combine all their iteration needs
into a single ctf_type_next() loop.

So in my humble opinion, there's really only one function which needs
to be added, handling use case #1.

> But also we want to not completely fail when faced with existing shared
> dicts that have many enumeration constants, in different enums, with
> thee same name. (These will still be able to happen even in the future,
> albeit rarely, because when using custom linkers like the one I'm hoping
> to upstream into the Linux kernel, CTF child dicts are not always the
> same as C translation units: you can have two enumeration constantss FOO
> that are in different translation units in the same kernel module, and
> the kernel CTF linker will combine them into the same CTF dict. One enum
> will be marked hidden/non-root, but both will be there.)
> 
> So functions to iterate over all enumeration constants with a given
> value are obviously necessary, but we probably want a non-iterator to
> just return the specific enum value that a given name expands to: maybe
> we want to just pick one if this is ambiguous (as ctf_enum_value already
> does). Below I have the maximally general approach, controlled by a
> flag, but this is probably total overkill. I suspect
> ctf_enumerator_name_next may still be necessary for existing dicts, but
> probably not the flag to ctf_enumerator_value -- but I'm not sure.
>
> For now, I've got this (using int64_t for enum values -- I'm not sure
> how to migrate the other enum functions that way in future, but we
> clearly have to *somehow*).
>
>
> I'm very unsatisfied with the naming: to me, ctf_enumerator_* does not
> read "like ctf_enum_* but dict-wide": but ctf_dict_enum_* feels wrong
> too, as if it were dealing with enums *of* dicts. Suggestions?

Given my (maybe not so humble) opinion above, I think that naming can
become a bit clearer if you don't try to handle so many use cases. To
me, this is a clear case of a "lookup". The word "lookup" to me implies
a wide search, not simply within a single enum type. And if you only
support name lookup, then the functions can be called:

ctf_id_t ctf_lookup_enumerator(ctf_dict_t *, const char *, int64_t *enum_value);
ctf_id_t ctf_lookup_enumerator_next(ctf_dict_t *, const char *,
                                    int64_t *enum_value, ctf_next_t **next);

This would also make it easier to perform the (in my opinion, equally
important) archive-level lookup:

ctf_id_t ctf_arc_lookup_enumerator_next(ctf_archive_t *, const char *,
                                        int64_t *enum_value, ctf_dict_t **dict,
                                        ctf_next_t **next);

The reason this feels so important for me is that, from a debugger's
perspective, we don't frequently know which dictionary to search.
Frequently a user is just saying "give me the constant FOO", with no
scope or anything to give a hint. Looking up a constant at the dict
level is good enough for the 95% of the time when the constant lives in
the parent dict. But in the remaining 5% it really stinks that you would
need to go through each dict and re-do the search (which would likely
repeat the failed search in the parent dict).

 => Note: with these archive-level lookups, though, it would be really
 nice to avoid returning a brand new ctf_dict_t *. I don't know how the
 semantics would work: only search dictionaries that already have an
 open handle? Reference count the dictionaries and simply return the
 same one if it's already open?

If you do stick with your proposed API, which is good too, then I
suppose I have a slight preference for "ctf_dict_enum_*". It doesn't
make my mind jump to "enums of dicts", it just sounds like it's a
function/method of a dict dealing with enums.

Hopefully something in my ramblings above proves helpful!

Thanks for taking a great stab at this and the documentation efforts too,

Stephen

> /* ... _CTF_ERRORS ... */
>   _CTF_ITEM (ECTF_ENUM_NAME_CONFLICT, "Multiple enumeration constants exist with this name.")
>
> /* Flags for ctf_enumerator_value.  */
>
> #define CTF_ENUM_UNIQUE 0x1
>
> /* Get the value of a given named enumerator, dict-wide: also optionally return
>    the associated enum type.  It is possible, but rare, for dicts to have
>    multiple values for some names, or the same values in multiple distinct enum
>    types: if the flags include CTF_ENUM_UNIQUE, fail with
>    ECTF_ENUM_NAME_CONFLICT in this case.  Otherwise, return the first
>    found.
>
>    There is no function that maps the other way because it is downright common
>    (and legal C) to have a single value that many enum constants are defined as
>    across an entire dict.  Use ctf_enumerator_name_next instead.  */
>
> int64_t ctf_enumerator_value (ctf_dict_t *fp, const char *name, int flags);
>
> /* Iterate over all enumeration constants with a given value in one
>     enum.  */
>
> const char *ctf_enum_name_next (ctf_dict_t *fp, ctf_id_t type, ctf_next_t **it,
>                                 int64_t value);
>
> /* Iterate over all enumerands in a dict.  The enum TYPE and the
>    enumerand VALUE may optionally be returned as well.  */
> const char *ctf_enumerator_next (ctf_dict_t *fp, ctf_next_t **it, ctf_id_t *type,
>                                 int64_t *value);
>
> /* Iterate over the values of all enumeration constants in a dict with a given
>    name.  The enum TYPE may optionally be returned as well.  */
> int64_t ctf_enumerator_value_next (ctf_dict_t *fp, const char *name,
>                                    ctf_next_t **it, ctf_id_t *type);
>
> /* Iterate over the names of all enumeration constants in a dict with a given
>    value.  The enum TYPE may optionally be returned as well.  */
> const char *ctf_enumerator_name_next (ctf_dict_t *, int64_t value,
>                                       ctf_next_t **, ctf_id_t *type);