Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

String tokenization in C

onebyezero.blogspot.com

Post reply on HN
Print view View original

61–70 of 117 posts

Re: String tokenization in C

#61

Post by jstimpfle »

tptacek wrote: post #56
jstimpfle wrote: post #53

Earlier quoted context omitted.

I'd say just use memcpy.

How does that help? You have the same bookkeeping problem with memcpy as you do with strncat.

str[ln]cat is like memcpy, but it does unnecessary work (search for the end of the string which the caller should long have figured out). It's like memcpy but less general and more confusing to use due to the implicit string length of the target operand. It's a completely unnecessary API, likely a remainder from the times when people used C for scripting.

It's also a complete idiocy to possibly not copy everything. I've never wanted that. It's begging for bugs. If there's not enough room to copy all the source bytes, you either know that in advance or you want to crash hard.

Even memcpy itself is hardly necessary as a library function. It's a simple loop. But at least it's what you would write anyway, and in some cases compilers are able to optimize it (with questionable benefits).

Re: String tokenization in C

#62

Post by torstenvl »

jstimpfle wrote: post #37
fanf2 wrote: post #35

Earlier quoted context omitted.

Use strcspn() instead

Token tok; start_token(&tok); for (;;) { int c = look_next_char(); if (('A' Done. There's no point in going through a weird API.

You've not only hard-coded your tokenization rules inside your logic, but you've managed to make it break on anything non-ASCII. I suppose you consider isalpha() to have a weird API?

Re: String tokenization in C

#63

Post by jstimpfle »

torstenvl wrote: post #62
jstimpfle wrote: post #37

Earlier quoted context omitted.

Token tok; start_token(&tok); for (;;) { int c = look_next_char(); if (('A' Done. There's no point in going through a weird API.

You've not only hard-coded your tokenization rules inside your logic, but you've managed to make it break on anything non-ASCII. I suppose you consider isalpha() to have a weird API?

I look at it the other way: I've hard coded the reading and writing routines inside the tokenization logic.

Being able to do that is exactly the point why it's so much simpler to avoid a silly API such as strcspn (or, god forbid, strtok).

> non-ASCII

yeah i know... Do you prefer strcspn("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVXYZ")? Do you think it's faster?

If you're pedantic, you could lex (0x41 > I suppose you consider isalpha() to have a weird API?

Yes. I do not even understand what it does.

>> isalpha() checks for an alphabetic character; in the standard "C" locale, it is equivalent to (isupper(c) || islower(c)). In some locales, there may be additional characters for which isalpha() is true-letters which are neither upper case nor lower case.

Well in any case I'm sure that's not what I wanted... By the way locale is super hard to use as well. Locale is a process global property. I'm not aware of any way to pass explicit locales to library functions.

Re: String tokenization in C

#64

Post by simias »

jstimpfle wrote: post #12

strtok is one of the silliest parts of the standard library. (And there are many bad ones). It's broken. It's not thread safe (yes there is strtok_r). It's needlessly hard to use. And it writes zeros to the input array. The latter means it's unfit for most use cases, including non-trivial tokenization where you want e.g. to split "a+1" into three tokens. If you program in C please just write those four obvious lines…

I use strtok_r from time to time, it does the job if you have a mutable input. Of course having to write zeroes is a bit cumbersome but it's one of the drawbacks of C-style strings.

The plain truth is that string handling in C is a huge pain in the ass no matter how you look at it. Splitting, concatenating, regex-ing... All of that is a huge pain in C. If you need to write a high-performance parser then it might be worth it but if you're just parsing a fancy command line format and performances don't matter it's just incredibly frustrating and error prone.

Rust fares better here because its str type is not NUL-terminated but actually keeps track of the length separately which makes it significantly more flexible and versatile. Of course you could do that in C but you'll be incompatible with any code dealing with native C-strings.

And of course you make one mistake and you have a buffer overflow vulnerability...

So yeah, if you program in C please use strtok_r if applicable, otherwise considering offloading the parsing to an other part of your application written in a language better suited for that and hand over binary data to the C library. If everything else fails then consider handwriting your parser and may god be with you. Oh and if your grammar is complex enough to warrant it, there's always lex/yacc.

Re: String tokenization in C

#65

Post by repiret »

jstimpfle wrote: post #61
tptacek wrote: post #56

Earlier quoted context omitted.

How does that help? You have the same bookkeeping problem with memcpy as you do with strncat.

str[ln]cat is like memcpy, but it does unnecessary work (search for the end of the string which the caller should long have figured out). It's like memcpy but less general and more confusing to use due to the implicit string length of the target operand. It's a completely unnecessary API, likely a remainder from the times when people used C for scripting. It's also a complete idiocy to possibly not copy everything. I…

If you use memcpy and your destination buffer is too small you don’t crash hard with any certainty, your program might even appear to work.

Moreover, most of the time I’m either certain the output buffer is large enough (maybe because I just allocated it) or I really do want the output buffer to have a truncated string. Strncpy’s two dumb behaviors that I almost never want is to pad the destination buffer with zeros if the source string is smaller and to leave the destination I terminated if the source is longer.

Re: String tokenization in C

#66

Post by mcguire »

jstimpfle wrote: post #50
barrkel wrote: post #49

Earlier quoted context omitted.

Most lexers are state machines, either explicit with tables (like you get from lex) or implicit with program counter (with loops and switches). Those state machines implement matchers for regular languages; they're effectively hand-coded implementations of regular expression matching. Regular expressions don't show up outside the spec, sure; but if you're writing the code (for implicit state machine), you need to kno…

Yes. I don't think anyone is disagreeing here. If you're implying that we should then use a regex implementation instead: Coding up a lexer (for a mainstream programming language) using simple counter increments and such is not a lot of work. It has the advantage that it results in faster code (unless you're going for real heavy machinery) and that you can easily code up additional transformations. For example, how w…

"(.|\.)*"

Re: String tokenization in C

#67

Post by jstimpfle »

mcguire wrote: post #66
jstimpfle wrote: post #50

Earlier quoted context omitted.

Yes. I don't think anyone is disagreeing here. If you're implying that we should then use a regex implementation instead: Coding up a lexer (for a mainstream programming language) using simple counter increments and such is not a lot of work. It has the advantage that it results in faster code (unless you're going for real heavy machinery) and that you can easily code up additional transformations. For example, how w…

"(.|\.)*"

"Evaluation:\tWrong!\x07\x07\x07\r\n"

You want to convert the string literal to an internal buffer, interpreting the escape sequences. In the same way, you want to parse integers. You cannot really do that with a regular expression. RE is for matching, not for transforming.

Re: String tokenization in C

#68

Post by kahirsch »

jstimpfle wrote: post #48
dahart wrote: post #46

Earlier quoted context omitted.

> Yout don’t really use regex in C. Speak for yourself. There’s a POSIX standard for regex that is more than 30 years old & a GNU implementation that comes with gcc. C++ has regex in the standard library.

"You" used like "one", or "in common practice it isn't really used". It's just not in C's spirit to use canned libraries. Such use cases have long been transferred to Python and other languages. Sure, there is a regex API in the C standard library. I'd bet not even grep uses it. The one use-case I'm envisioning is quickly exposing POSIX conformant regexen to the command-line.

GNU grep uses the regex library in Gnulib. It can also use the Perl-compatible pcre library.

I am finding it hard to believe that you think it's "just not in C's spirit to use canned libraries."

Re: String tokenization in C

#69

Post by paavoova »

simias wrote: post #64
jstimpfle wrote: post #12

strtok is one of the silliest parts of the standard library. (And there are many bad ones). It's broken. It's not thread safe (yes there is strtok_r). It's needlessly hard to use. And it writes zeros to the input array. The latter means it's unfit for most use cases, including non-trivial tokenization where you want e.g. to split "a+1" into three tokens. If you program in C please just write those four obvious lines…

I use strtok_r from time to time, it does the job if you have a mutable input. Of course having to write zeroes is a bit cumbersome but it's one of the drawbacks of C-style strings. The plain truth is that string handling in C is a huge pain in the ass no matter how you look at it. Splitting, concatenating, regex-ing... All of that is a huge pain in C. If you need to write a high-performance parser then it might be w…

> but you'll be incompatible with any code dealing with native C-strings

Not entirely, see https://github.com/antirez/sds

Basically, you have a header storing length, etc, but still null terminate, so library functions like strlen are none the wiser.

Re: String tokenization in C

#70

Post by Matthias247 »

simias wrote: post #64
jstimpfle wrote: post #12

strtok is one of the silliest parts of the standard library. (And there are many bad ones). It's broken. It's not thread safe (yes there is strtok_r). It's needlessly hard to use. And it writes zeros to the input array. The latter means it's unfit for most use cases, including non-trivial tokenization where you want e.g. to split "a+1" into three tokens. If you program in C please just write those four obvious lines…

I use strtok_r from time to time, it does the job if you have a mutable input. Of course having to write zeroes is a bit cumbersome but it's one of the drawbacks of C-style strings. The plain truth is that string handling in C is a huge pain in the ass no matter how you look at it. Splitting, concatenating, regex-ing... All of that is a huge pain in C. If you need to write a high-performance parser then it might be w…

> The plain truth is that string handling in C is a huge pain in the ass no matter how you look at it.

It is. And it’s not even only Cs fault. 80% of it is bad API Design. Strings could be accepted as a struct consisting of a pointer and a length, aka string_view. And there could be some manipulation functions around it. That would make those APIs a lot more flexible (one no longer needs to care whether things are null terminated and there would be less pointless copies).

For these reasons my estimate in the meantime is that the average C program which uses stdlib functions is less efficient than an implementation in another language, even though the authors would claim otherwise (its C, it must be fast).

Post reply on HN