8
\$\begingroup\$

As part of my stupidly large project Concaten, I'm writing a string escaper. It's the majority of the part that turns string tokens (like "hello world" or "buncha\n\n\n\n\n\nnewlines") into the string data that they represent. It's part of the token-to-object module, hence the prefix.

The code that calls the function below is intentionally not in the question, since it relies very heavily on some other components that deserve their own questions, but it's available here -- though keep in mind that my GitHub is subject to change.

A few important things, first:

  • ERROR is defined with typedef unsigned long long ERROR; everything that ends with _ERROR or _FAIL is of that type.
  • val_len is intentionally one more than the result strlen would give you; it's the amount of memory needed, not the result of strlen. This is a convention I have across my codebase, and I'm not going to change it.

Code

#include <stdlib.h>
#include <string.h>

const ERROR NO_ERROR = 0;
const ERROR TTO_WORDS_VALUELESS_FAIL = 9000;
const ERROR TTO_UNKNOWN_TYPE_FAIL = 9001;
const ERROR TTO_NOT_IMPLEMENTED_FAIL = 9002;
const ERROR TTO_CREATE_OBJ_FAIL = 9003;
const ERROR TTO_STRING_ESCAPE_FAIL = 9004;
const ERROR TTO_ESCAPE_END_FAIL = 9005;
const ERROR TTO_MALLOC_FAIL = 9006;
const ERROR TTO_ESCAPE_BAD_HEX_FAIL = 9007;
const ERROR TTO_INVALID_NUM_FAIL = 9008;

char tto_hexchar_to_val(const char c) {
    switch (c) {
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        case 'a': case 'A': return 10;
        case 'b': case 'B': return 11;
        case 'c': case 'C': return 12;
        case 'd': case 'D': return 13;
        case 'e': case 'E': return 14;
        case 'f': case 'F': return 15;
        default: return 16;
    }
}

ERROR tto_escape_hex(const char **pos, char **ret_pos, const char *const end) {
    char x_val;
    int t;
    x_val = 0;
    ++(*pos);
    if (*pos == end) {
        return TTO_ESCAPE_END_FAIL;
    }
    t = tto_hexchar_to_val(**pos);
    if (t > 15) {
        return TTO_ESCAPE_BAD_HEX_FAIL;
    }
    x_val |= t << 4;
    ++(*pos);
    if (*pos == end) {
        return TTO_ESCAPE_END_FAIL;
    }
    t = tto_hexchar_to_val(**pos);
    if (t > 15) {
        return TTO_ESCAPE_BAD_HEX_FAIL;
    }
    x_val |= t;
    **ret_pos = x_val;
    return NO_ERROR;
}

ERROR tto_escape_string(const char *const str, size_t val_len, char **out) {
    ERROR err;
    char *ret = malloc(val_len);
    if (!ret) return TTO_MALLOC_FAIL;
    char *ret_pos = ret;
    const char *const end_null = str + val_len - 1;
    for (const char *pos = str; pos < end_null; ++pos, ++ret_pos) {
        if (*pos == '\\') {
            ++pos;
            if (pos == end_null) {
                err = TTO_ESCAPE_END_FAIL;
                goto error_handler;
            }
            switch (*pos) {
                case '0': *ret_pos = '\0'; break;
                case 'a': *ret_pos = '\a'; break;
                case 'b': *ret_pos = '\b'; break;
                case 'e': *ret_pos = '\x1B'; break;
                case 'f': *ret_pos = '\f'; break;
                case 'n': *ret_pos = '\n'; break;
                case 'r': *ret_pos = '\r'; break;
                case 't': *ret_pos = '\t'; break;
                case 'v': *ret_pos = '\v'; break;
                case 'x':
                    err = tto_escape_hex(&pos, &ret_pos, end_null);
                    if (err != NO_ERROR) goto error_handler;
                    break;
                default:
                    *ret_pos = *pos;
            }
        } else {
            *ret_pos = *pos;
        }
    }
    *ret_pos = 0;
    ++ret_pos;
    char *new_ret = realloc(ret, ret_pos - ret);
    if (!new_ret) {
        *out = ret;
    } else {
        *out = new_ret;
    }
    return NO_ERROR;
error_handler:;
    free(ret);
    return err;
}

Example input/output

Both input and output are escaped according to C rules (since I took them from my test suite, which is written in C)

"abc"         => "abc"
"ab\\c"       => "abc"
"ab\\x63"     => "abc"
"ab\\tc"      => "ab\tc"
"ab\\t\\x21c" => "ab\t!c"
"ab\\\\c"     => "ab\\c"
"\\\\abc"     => "\\abc"
"ab\\\\"      => "ab\\"
"\\x456"      => "E6"
"abc\\0def"   => "abc\0def"
"abc\\"       => error 9005
"abc\\x"      => error 9005
"abc\\x0"     => error 9005
"abc\\xO"     => error 9007

A simplistic test suite is here.

Things I'm concerned about:

  • Performance. This is called for every single string in the source. I'm pretty sure I've got it as optimized as it's gonna get, but I'm happy to be proven wrong. I also want to have as little memory used as possible, though if it comes down to it, an extra few bytes isn't enough to make me worry.
  • Bugs. I'm pretty sure I've tested all the edge-cases, but not totally sure. If you can think of any, please let me know, and let me know if they cause bugs. Along the same lines, Valgrind reports no leaks, but it won't report leaks through code paths that aren't reached.
  • Extensibility. If I decide I want more escapes, will they be reasonably easy to add? My gut tells me yes, but I've also been working on this for a day or two, so I'm probably biased.
  • Least surprise. Currently, I have it inserting any unnecessarily escaped characters as they are (minus the \). Is this the best thing to do? It wouldn't be difficult to cause an error instead, and only allow the few characters that make sense to insert as they are (\ and ").

    Relatedly, is it reasonable to expect the caller to free the result? This is another project-wide convention, so I'm not too concerned about it, but maybe I should be.

And, of course, anything else worth mentioning.

\$\endgroup\$
  • \$\begingroup\$ By the way, are the strings in source going to be enclosed in quotes? If yes, and you want to support the \" escape, you will have to incorporate this "escaper" within your lexical analyzer. Or make your lexical analyzer and this escaper recognize that escape. \$\endgroup\$ – kyrill Mar 30 '17 at 0:59
  • \$\begingroup\$ @kyrill They are, and the lexical analyzer keeps an eye out for this particular case, and ignores it (in terms of deciding whether the string should end, that is). I've put the tokenizer up for review here. \$\endgroup\$ – Fund Monica's Lawsuit Mar 30 '17 at 1:00
4
\$\begingroup\$

I will only address the issue of performance.

  • You might want to use strchr to find occurrences of \ and just memcpy everything in between. It's highly probable that these are optimized by SSE or AVX.

  • If you can (I suspect you cannot), don't allocate memory for each string separately, and if you do, don't reallocate, it's probably not worth the overhead.

  • To kill two birds with one stone, you can allocate an array where you save the positions of \ in the string. Then you allocate exactly as much memory as needed, and do the memcpy and parsing of escape sequences. EDIT To deal with escape sequences of variable length, you can parse and store the escape sequences as you scan the string for \s. Store them in another array, along with their positions, and then do memcpy of plain text plus individually copy the parsed characters.

  • Preferably put the most common branch first, eg. if (*pos!='\\'). Although the branch prediction buffer will probably alleviate the negative effects of doing it the way you do it now. You can take a look at the macros __builtin_expect and likely / unlikely.

  • In function tto_escape_hex, save *pos into a variable instead of using it directly. The way you do it now, you dereference a pointer on every access. That, if your compiler didn't optimize it, would be slow. Allocating an extra variable is worth it and if you have optimizations turned on (or maybe even if you don't), the compiler probably stores the value in a register anyway.

  • If you are serious about this, you can take inspiration from some reference-grade compilers such as GCC (although that one might be a bit too heavyweight).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The tip about "skipping ahead" is a good one; it didn't occur to me that memcpy might be optimized by the compiler more easily than what's basically a for (...) { *foo = *bar; }. WRT "exactly as much memory as needed" -- x "takes arguments", and u (which I haven't added yet, but follows the same pattern) will too. How would you recommend dealing with that? \$\endgroup\$ – Fund Monica's Lawsuit Mar 29 '17 at 23:28
  • \$\begingroup\$ I added a remark about branch (mis)prediction. Regarding x and u, I personally would probably just allocate the extra space for the sake of performance, if that's what I wanted the most. Other way would be to parse and store the escape sequences as you scan the string for '\'s. Store them in another array, along with their positions, then memcpy of plain text plus copy the parsed characters. \$\endgroup\$ – kyrill Mar 29 '17 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.