Fix select command list for the curses version

[fstj]

The current implementation of the select command list accessible with the Ctrl+P key binding is broken for the curses version of Textadept. For some of the available locale simply starting textadept-curses and hitting Ctrl+P results in a crash of the application on Manjaro Linux. You can reproduce this crash with any of the following commands:

LANG=fr_FR.UTF-8 textadept-curses
LANG=ar_SA.UTF-8 textadept-curses
LANG=pl_PL.UTF-8 textadept-curses
LANG=zh_CN.UTF-8 textadept-curses

This crash is due to read and write access to data outside of the allocated memory, which can be seen for example using Valgrind.

The origin of this bug is the wrong computation of the maximum row length in bytes stored in the row_len variable, as the computation doesn't take into account the padding added in each column when creating the command list as it should.

This pull request corrects this bug and fixes the crash.

[orbitalquark]

Thanks for the detailed report and patch. I've applied what I think is a fix for this in https://github.com/orbitalquark/textadept/commit/de7ad7d18fa0b271150c4bac0aefca8c7aa9391f. I'd like to avoid another iteration over the entire item list because it slows things down for really large lists (e.g. quickly open a large project), so only realloc to a larger row size if the estimated size is too small.

[fstj]

Thanks for taking into account this pull request and correcting the bug.

I didn't notice that the displayed list could be big in some cases and I agree that it can be better to avoid a new iteration over the entire list in this case, but I'm surprised by the solution that you implemented as I find it odd.

As I see the problem, the implementation somehow has to choose a compromise between minimizing the extra memory used and avoiding reallocations, while trying to minimize the overall computation done. And I see the two extreme cases of the compromise as the more suitable solutions for the problem.

If you want to minimize the extra memory used, with your current implementation, you could simply estimate row_len like that:

    size_t *column_widths = malloc(num_columns * sizeof(size_t)), row_len = 0;
    for (int i = 1; i <= num_columns; i++) {
        const char *column = opts.columns ? (lua_rawgeti(L, opts.columns, i), lua_tostring(L, -1)) : "";
        size_t utf8max = utf8strlen(column);
        for (int j = i - 1; j < num_items; j += num_columns) {
            size_t utf8len = utf8strlen(items[j]);
            if (utf8len > utf8max) utf8max = utf8len;
        }
        column_widths[i - 1] = utf8max, row_len += utf8max + 1; // include space for '|' separator or '\0'
    }

and the reallocation that you added in the loop that follows will take care to allocate extra memory when needed.

Compared to the current implementation, notice that with this solution you avoid the computation of max and the associated call to strlen(), reducing the computation done in the loop (at the cost of possibly more reallocations in the loop that follows).

If you don't mind using a bit more memory than strictly needed, but want to avoid the reallocations, you could compute an upper bound of row_len by considering the worst case that can happen in each column like that:

    size_t *column_widths = malloc(num_columns * sizeof(size_t)), row_len = 0;
    for (int i = 1; i <= num_columns; i++) {
        const char *column = opts.columns ? (lua_rawgeti(L, opts.columns, i), lua_tostring(L, -1)) : "";
        size_t utf8max = utf8strlen(column), extra_max = strlen(column) - utf8max;
        for (int j = i - 1; j < num_items; j += num_columns) {
            size_t utf8len = utf8strlen(items[j]), extra_len = strlen(items[j]) - utf8len;
            if (utf8len > utf8max) utf8max = utf8len;
            if (extra_len > extra_max) extra_max = extra_len;
        }
        column_widths[i - 1] = utf8max, row_len += utf8max + extra_max + 1; // include space for '|' separator or '\0'
    }

You can then switch back the loop that follows to the implementation without reallocation that was used before.

Compared to the current implementation, notice that the computation needed is almost unchanged as the computation of extra_max replaces the computation of max with the same calls to strlen() and just an added difference (but you avoid all the reallocations that come after).

The solution that you implemented for the computation of row_len places you somewhere between this two solutions, but where you exactly are between the two extreme cases completely depends on the data in the list. So with your solution, the compromise between memory usage and reallocations depends on the content of the list and extra computation or extra reallocations are needed compared to the two solutions given above.

So I'd propose to modify the current code with one of the solutions above, depending on the compromise that you want to make. I guess that the second solution should generally provide the fastest execution time, but at the cost of a (reasonably) heavier temporary use of memory.

[orbitalquark]

Thanks again for the detailed write-up. You are correct. For some reason, I didn't realize all of the information needed to avoid realloc was available. I've committed this in https://github.com/orbitalquark/textadept/commit/52eadb9769f92a2c3213713b7e2136da9792166d.

[fstj]

That's great, thank you. And more generally thank you for your work on Textadept and for sharing Textadept as free and open source software.