Array enumeration

AMG: Tcl arrays are enumerated via the [array names] or [array get] commands or by the (virtually obsolete) combination of [array startsearch], [array nextelement], [array anymore], and [array donesearch]. At present, they cannot be enumerated via the Tcl C API. The FlightAware Tcl bounty programme [1] seeks to address this and other Tcl shortcomings.

I have implemented a Tcl C API for enumerating array elements, patterned after the Tcl API listed above and on the C API for accessing variables. The starting point for the implementation was had by rearranging existing code as much as possible to minimize the inadvertent introduction of new bugs. All [array] commands have been reimplemented as calls into the new C API so it can be tested by the existing Tcl test suite.

This will be my first Tcl Improvement Proposal and my first case of Tcl core programming. Outside of random bug and documentation fixes, my Tcl C experience is writing proprietary Tcl extensions over the last 10-15 years, and my Tcl scripting experience goes back to 1999.

Code edit

http://core.tcl.tk/tcl/timeline?r=amg-array-enum-c-api

API edit

Here is my working API design. Please share any comments or questions you may have. I welcome opinions about the alternatives and wishes I outline below, and please feel free to add your own ideas.

Types

typedef struct ArraySearch *Tcl_ArraySearch

Tcl_ArraySearch is an opaque pointer to struct ArraySearch which has the search internals.

Arguments

Tcl_Interp *interp (in)

Interpreter containing array variable.

Tcl_Obj *part1Ptr (in)

Points to a Tcl object containing the variable's name. The name may include a series of :: namespace qualifiers to specify an array variable in a particular namespace.

Tcl_Obj *part2Ptr (in)

Points to a Tcl object containing the element name filter. If NULL, no filtering is applied.

Tcl_Obj *listPtr (in/out)

Tcl list object to which array names are appended.

Tcl_Obj *dictPtr (in/out)

Tcl dict object from/to which array names and values are read/written.

Tcl_Obj *stringPtr (in/out

Tcl string object to which hash table statistics information is appended.

Tcl_ArraySearch search (in)

Search token obtained from Tcl_ArraySearchStart().

int flags (in)

OR-ed combination of zero or more of the following bit values providing additional information:

TCL_GLOBAL_ONLY: The variable is looked up only in the global namespace even if there is a procedure call active.
TCL_NAMESPACE_ONLY: The variable is looked up only in the current namespace; if a procedure is active its variables are ignored, and the global namespace is also ignored unless it is the current namespace

OR-ed with zero or one of the following values:

TCL_MATCH_EXACT: The filter accepts only the element whose name exactly matches part2Ptr. This is the default.
TCL_MATCH_GLOB: The filter interprets part2Ptr as a [string match]-style glob expression.
TCL_MATCH_REGEXP: The filter interprets part2Ptr as a regular expression.

Functions

int Tcl_ArraySet(interp, part1Ptr, dictPtr, flags)

Set the elements of an array. If there are no elements to set, create an empty array.

int Tcl_ArrayUnset(interp, part1Ptr, part2Ptr, flags)

Unsets array elements.

int Tcl_ArrayGet(interp, part1Ptr, part2Ptr, dictPtr, flags)

Loads the elements of an array into a dict. The dict need not be empty before calling this function, in which case the array elements are merged with (and supersede) the original contents of the dict.

int Tcl_ArrayNames(interp, part1Ptr, part2Ptr, listPtr, flags)

Appends array element names to the listPtr list object. part2Ptr can be used to specify an element filter.

The reason listPtr is not created or reinitialized but rather appended to is so Tcl_ArrayNames() can be called multiple times on a single list object, with a different filter each time, to build a list of all elements matching any one of the filters. In this usage, elements matching multiple filters will be listed multiple times. To reset listPtr before calling Tcl_ArrayNames(), truncate it by calling Tcl_SetListObj(listPtr, 0, NULL).

int Tcl_ArraySize(interp, part1Ptr, part2Ptr, intPtr, flags)

Obtains the array size. part2Ptr can be used to specify an element filter, in which case the return value is the number of array elements matching the filter.

int Tcl_ArrayExists(interp, part1Ptr, part2Ptr, intPtr, flags)

Checks if an array exists or if at least one array element matches an optional filter.

Tcl_ArraySearch Tcl_ArraySearchStart(interp, part1Ptr, part2Ptr, flags)

Returns a Tcl_ArraySearch on success or NULL on error. part2Ptr can be used to specify an element filter.

Tcl_Obj *Tcl_ArraySearchPeek(search)

Returns name of next element or NULL if finished.

Tcl_Obj *Tcl_ArraySearchNext(search)

Returns name of next element or NULL if finished. The search state is updated so successive calls to Tcl_ArraySearchNext() will return successive array element names.

void Tcl_ArraySearchDone(search)

Cleans up array search internals.

int Tcl_ArrayStatistics(interp, part1Ptr, stringPtr, flags)

Obtains array hash table statistics.

Scope creep edit

The baseline [array names] supports filtering by exact, glob, and regular expression matches. The baseline [array get], [array set], and [array unset] support filtering only by glob matches. The baseline [array exists], [array size], and [array startsearch] don't support filtering at all. Because I implemented a common infrastructure for the array enumeration commands, I need to support the general case: filtering by exact, glob, and regular expression matches. In order to properly test this functionality, I need to expose it to the script level via options to all the commands listed in this paragraph.

Even though exposing [array get] at the C level was not part of my original plan, it's arguably part of array enumeration. Furthermore, it should be able to benefit from the new common infrastructure. Thus I added a function for it as well.

Since I did that much, I went ahead and completed the set by providing C interfaces to [array exists], [array set], [array unset], and even [array statistics]. All of [array] is now C-callable.

Now that I have multiple kinds of changes (new C API functions, new Tcl command arguments), do I need to write multiple TIPs? Or is the fact that they are closely and usefully related mean a single TIP will suffice?

Lastly, I am considering changing [array unset] to start by making a list of elements it intends to unset before it actually unsets them. This works around various pathological trace problems and is in accordance with DKF's recommendation found at [2], dated 2010-02-03 16:46:16. It's now easy to do this. Just look at Tcl_ArrayGet() which already does this. Would this have to be a third TIP? It is a potential incompatibility in case any scripts actually depend on the current ill-defined interaction between [array unset] and traces.

Filtering in C API not required

DKF: Strictly, the enumeration API itself does not need to support name filtering. That's trivially implementable by the client of the enumeration engine.

AMG: True, the caller can indeed apply its own filtering. I decided to provide it anyway in the C API for a number of reasons:

I wanted the C API be as functional as the Tcl API. FlightAware expressed dissatisfaction with having to evaluate Tcl code from C in order to enumerate an array, and I took that as a request for the full Tcl capability to be directly exposed to C.
Performance is degraded when the entire element list must always be built even if the caller then has to chuck out the elements it doesn't want. If FlightAware weren't concerned with performance, they'd accept evaluating Tcl from C, and they wouldn't be buying [clock] and general speedups.
Filtering was already implemented to support [array get], [array names], and [array unset]. I find it to be poor form to hide easily-exposed functionality in favor of requiring each caller to reimplement it, provided that the cost of exposure isn't too great. I should note that this would not be an issue if [lsearch] were part of the C API.

I additionally decided to provide the same style of filtering on all C functions and Tcl commands which could usefully benefit from filtering. The aforementioned [array] commands each implemented their own filtering, albeit with differing capabilities. Consolidating the filtering functionality into common routines yielded the superset, and I was loathe to hide that expanded capability simply because it was not previously available. Furthermore, having the same level of capability across all functions and commands reduces the burden on the user to remember each function and command as a special case since they all have essentially the same interface. One demonstration of this benefit is my updated man pages which describe filtering in one place which is referenced (not repeated) by the per-function and per-command sections. Another is my test suite which exhaustively loops over multiple commands without having to test each combination of command and mode as a distinct special case.

All that being said, yes, it is possible to make the C API not provide access to filtering. This would be accomplished by removing the filter parameters. But as an immediate example of the increased burden on the user should they desire filtering, I would have to restore the separate and unequal implementations of filtering within each Tcl command, with the attendant performance reduction relative to the baseline which had no need to build a complete enumeration then discard elements. I don't think FlightAware would welcome slowing down Tcl script in the name of increasing the performance of their C extensions. Alternately, I could merge the current versions of the C API functions into the Tcl commands, then chop down the C API. But that would result in duplicated code plus would incentivize continuing to call the Tcl commands from C because Tcl would remain the faster and easier way to do filtering. I could then hide the Tcl commands' expanded filtering options to once again make the C API more attractive by comparison, but there's no value added for anyone in doing that.

Such was the reasoning for my design decisions.

Crash during iterative enumeration with C API edit

(Credit goes to BLL for the original bug report.)

Okay, I now have a good idea what is going wrong with array searches. The root of the problem is my failure to notice the documented, intended behavior of terminating searches when any elements are added to or removed from the array. Thus I did not incorporate proper handling of same into my design.

When an element is added to or removed from an array, all pending searches on the array are terminated, and the search structures are all freed. This includes ArraySearch structures which escaped the control of tclVar.c because they were the return value of Tcl_ArraySearchStart(). Unsurprisingly, a crash results when the C API is asked to use a freed search structure to continue a terminated search. There is no way to notify the caller that a search has been completed and its structure freed, so it can't avoid it. Thanks to traces, it can't even be sure it's avoiding inadvertently causing the search to terminate.

What to do? I think the intended approach is to not let the ArraySearch pointer escape tclVar.c. Instead, do exactly what the Tcl API does: reference in-progress searches by tokens contained in Tcl_Objs. Should a search unexpectedly terminate, the ArraySearch lookup will fail and can be handled.

There are costs. One, this is slower because a hash table lookup must be performed every time a search function is called, though it won't be any slower than the Tcl equivalent. Two, every search function will be more complicated to use due to taking interpreter and array name arguments and returning error codes which must be checked. Together, these two issues make the iterative search functions less attractive than the total enumeration functions, much like the case in Tcl scripts.

Another approach is to leave things as they are and update the documentation. State that the iterative search functions are only to be used in cases where array elements are guaranteed to not be added or removed. This includes not only direct attempts to add or remove elements but also anything that can possibly enter the script engine, for example modifying array elements since that might trigger traces.

On the subject of traces, all array commands, including array anymore and array donesearch, trigger array traces. Other than Tcl_ArraySearchStart(), my new C API search functions don't do this: Tcl_ArraySearchPeek(), Tcl_ArraySearchNext(), Tcl_ArraySearchDone(). This is because they do not call ArrayVar() since the array variable is referenced by the ArraySearch argument. While this inconsistency may seem bad, it does at least make the approach described by my previous paragraph possible.

Ultimately, I think I will need to change my Tcl_ArraySearch*() functions to work exactly like their Tcl counterparts, termination and traces and errors and all. But this will also make them less attractive.

A third approach is to admit that the concept of Tcl_ArraySearch*() is fundamentally hampered by the issues described above and to eliminate it outright due to being some combination of slow, inconvenient, unsafe, and inferior.

Thoughts? Preferences? Jokes? Criticisms?

Progress edit

20 November 2016: Began work, implemented Tcl_ArraySize().
24 November 2016: Published commits, fixed [array size] reporting of trace errors, improved Wiki page, added filtering. Implementation of above-listed functions is complete.
25 November 2016: Implemented Tcl_ArrayExists(), Tcl_ArraySet(), Tcl_ArrayUnset(), and Tcl_ArrayGet().
27 November 2016: Implemented Tcl_ArrayStatistics(), refined API, added man page for C API.
28 November 2016: Updated [array] man page, added filtering to [array exists] and Tcl_ArrayExists().
29 November 2016: Test suite, work proceeding gradually.
10 December 2016: Fixed panic in [array anymore], test suite complete unless I want to more thoroughly test interactions with [trace].
19 December 2016: Investigated crash due to adding or removing array elements in the middle of a search performed using the C API.

Remaining work edit

Write TIP, respond to comments and any other issues that may arise.

I should help merge the recent [array for] work, though one of these two projects will have to be accepted first.

Also I am interested in using this work as a platform from which to implement the per-array default value feature requested by FlightAware. Is it too soon to claim this? I'm not trying to be greedy here, I just think I'm in a good position to get it done because of the rest of my array work.

I need to correct a crash due to adding or removing array elements in the middle of a search performed using the C API. The Tcl API does not crash, although it did not seem to terminate as expected. I will have to investigate that as well. This is all due to a design problem rather than a simple bug.

Request for comments edit

As of 10 December 2016, I have had exactly zero response to any of the work I've done on this project, not from the Tcl community, not from FlightAware. I would very much appreciate any level of review or acknowledgement. One of the TIP requirements is that I get some community involvement and buy-in, but that's not happened yet, not in the slightest. Somebody please try building my code, running my tests, making sure your existing programs still work, trying out the new array filtering options, maybe even writing some C code that uses the new API, then commenting on your experiences.

In the time since, I have had feedback from DKF, BLL, and Karl Lehenbauer. Thank you for your input.

Category Tcl Library