# TIP 649: Expose additional list functionality in the C API
	Author:		Ashok P. Nadkarni <apnmbx-public@yahoo.com>
	State:		Draft
	Type:		Project
	Vote:		Pending
	Created:	14-Nov-2022
	Tcl-Version:	9.1
	Tcl-Branch:	tip-649
	Keywords:	list
-----
<!-- TOC BEGIN (auto generated with tiptoc) -->
* <a href='#Abstract'>Abstract</a>
* <a href='#Rationale'>Rationale</a>
    * <a href='#Efficiencyoflistmanipulation'>Efficiency of list manipulation</a>
    * <a href='#Efficiencyoflistaccess'>Efficiency of list access</a>
* <a href='#Specification'>Specification</a>
* <a href='#Discussion'>Discussion</a>
* <a href='#Implementation'>Implementation</a>
* <a href='#Copyright'>Copyright</a>

<!-- TOC END -->

# <a id='Abstract'></a>Abstract

**Although not directly dependent on it, this TIP is not being implemented
unless TIP 636 is passed.**

The list implementation has functionality that is available at the script
level but not in the C API. This TIP proposes to expose the same as a C
API as well. The benefits include

- convenience for extension and application writers that need to manipulate
lists at the C level by voiding the need to implement the same functionality
themselves
- significantly better performance as the currently defined list related C
API is implicitly built around the 8.6 list internal representation and does
not allow callers to benefit from implementation of more efficient higher
level operations.
- prevention of shimmering from the more efficient list representations made
possible by TIP 636 (for example, arithmetic series) to the memory intensive
8.6 implementation.

# <a id='Rationale'></a>Rationale

## <a id='Efficiencyoflistmanipulation'></a>Efficiency of list manipulation
Many applications and extensions for Tcl as well as Tk use Tcl's C API to
manipulate Tcl list values. For example, reversing or extracting a range of
elements is accomplished through a combination of
`Tcl_ListObjGetElements`/`Tcl_NewListObj` or a loop involving
`Tcl_ListObjIndex`/`Tcl_ListObjAppendElement`. Given the internal
representation of lists in Tcl 8.6, this was also how the Tcl core would
implement these operations and thus there were no significant efficiency
gains that would result from exposing the higher level operations as a C API.

This has changed with Tcl 9.0 where list internal representation may take
one of several forms (see TIP's 625, 629, 636). For many of these, some list
operations may be done more efficiently than allowed by the restrictive Tcl
8.6 list C API. For example, range and list reversal can now be faster and
more memory efficient by orders of magnitude for large lists.

The script level list commands benefit from these and it makes sense to
extend the same to C applications and extensions as well.

## <a id='Efficiencyoflistaccess'></a>Efficiency of list access

While the above pertain to list manipulation, the list accessor functions
`Tcl_ListObjGetElements` and `Tcl_ListObjIndex` also have their own issues
arising from an implicit assumption about the list internals.
`Tcl_ListObjGetElements` works well when the list internal representation
stores elements as an array of `Tcl_Obj *` pointer values.
`Tcl_ListObjIndex` assumes that the list implementation holds a reference to
the returned `Tcl_Obj *` element so the caller does not need to do any
explicit reference management with the returned pointer. Neither of these
assumptions necessarily hold true with newer list representations. For
example, the arithmetic series stores the list in compact (start, end, step)
form and generates a `Tcl_Obj` only when required. However, because of
`Tcl_ListObjIndex` semantics, the list implementation has to hold on to a
reference to the returned element `Tcl_Obj` essentially shimmering to the
equivalent `Tcl_Obj *` array at a cost in memory and efficiency.

For this reason, the TIP proposes an accessor function that is almost
identical to `Tcl_ListObjIndex` but requires the caller to release
the returned `Tcl_Obj` by calling `Tcl_DecrRefCount`. The list
implementation does not then need to artificially hold on to a reference
to the returned `Tcl_Obj** just in order to free it later.

**As an aside, note that the above drawbacks do not apply to the Tcl core
implementation itself, including implementation of script commands, as
Brian has already taken care to compensate appropriately. This is not
possible for extension writers as they do not have access to internal Tcl
list type information.**

# <a id='Specification'></a>Specification

The following functions will be added along with corresponding entries
in the stubs table. (Names all subject to change)

```
int Tcl_ListObjRange(
    Tcl_Interp *interp, /* Interpreter for error messages */
    Tcl_Obj *listPtr,   /* Unshared list object */
    Tcl_Size first,     /* Index of first element of range */
    Tcl_Size last);     /* Index of last element of range */
int Tcl_ListObjReverse(
    Tcl_Interp *interp, /* Interpreter for error messages */
    Tcl_Obj *listPtr);  /* Unshared list object */
int Tcl_ListObjRepeat(
    Tcl_Interp *interp, /* Interpreter for error messages */
    Tcl_Obj *srcListPtr,  /* List object containing elements to repeat */
    Tcl_Size repeatCount, /* Number of times to repeat */
    Tcl_Obj **newListPtr) /* Where to store the new list */
int Tcl_ListObjSort(
    Tcl_Interp *interp, /* Interpreter for error messages */
    Tcl_Obj *listPtr,   /* Unshared list object */
    TBD);
int Tcl_ListObjIndexWithRef(
    Tcl_Interp *interp, /* Interpreter for error messages */
    Tcl_Obj *listPtr,   /* Shared or unshared list object */
    Tcl_Size index,     /* Index of element to retrieve */
    Tcl_Obj **elementObjPtr) /* Where to store the element. Caller
                                needs to free it */
```

All functions return TCL_OK on success and TCL_ERROR on failure.
Functionality should be obvious.

# <a id='Discussion'></a>Discussion

The functions could be slightly altered to return a new `Tcl_Obj` and
allow `listPtr` to be a shared object. However, that would be inconsistent
with the current `Tcl_ListObjReplace` definition.

Applications should be encouraged to use `Tcl_ListObjIndexWithRef` to
avoid shimmering.

# <a id='Implementation'></a>Implementation

Pending until TIP 636 passes.

# <a id='Copyright'></a>Copyright

This document has been placed in the public domain.

