All your magic on format string doesn't change that poor behavior unless you manually add '\0' somewhere to null-terminate the input string early.
If you parse the year-month-day in 100 places of that input string, it will strlen 100 times. And now replace the "100 places" to a linear function of the input string length (strlen(input) / 11?), that is quadratic.
As someone who's been learning some C, I wonder if you have a recommendation for a guide on how to handle strings properly.
There are at least a few libs like sds that store the length information in various ways, which solves at least this kind of problem.
(Languages with more advanced string types and slicing mechanics are not impacted; C++, Rust, Go, etc. They do have their own issues of course.)
It's almost like JSON and XML were invented so people didn't have to understand lex/yacc.
And behold... they don't.
So in other words, it's completely useless?
> This is not an intended use case for sscanf.
Then what is?
In the entire TXR project, I used sscanf in one function: a floating to integer conversion routine. The context is that integers can be bignums, so we can't just rely on ordinary conversion, except in the fixnum range.
http://www.kylheku.com/cgit/txr/tree/arith.c?h=txr-252#n2912
The approach taken is to sprintf the double value into a generous buffer, with a generous precision, using the %g format which will automatically use the e notation if necessary.
We detect whether the e notation was produced, and other characteristics, and then proceed accordingly.
I see that an impossible case is being tested for; since values with a small magnitude are handled via the fixnum route, we will never hit the case where we can short-circuit to zero.
Can anyone see a bug here, by the way? :)
My guess at the historical intention of *scanf is that it was meant for parsing tab-delimited and fixed-width records from old-school data files.
CSVs are such a pain if you have freeform text (in which you have to handle newlines and escaped quotes).
It seems like using FS/GS/RS/US from the C0 control codes would be divine (provided there was implicit support for viewing/editing them in a simple text editor). I get that it's a non-printable control character, and thus not traditionally rendered... but that latter point could have been done ages ago as a standard convention in editors (enter VIM et. al., as they will indeed allow you to see them).
* I find dead keys irritating beyond reason, so I do not count them as an option
TSV also works more reliably than CSV, because most people don't put tab characters in the data in these kinds of records. Tab is even the default field delimiter for cut. But everybody uses CSV, because again it's easier to reason about the above. (shrug)
most parts
Why can't you be normal? https://commons.wikimedia.org/wiki/File:DecimalSeparator.svg
Rob Pike politely declined the patch, commenting "I might prefer to leave it unaddressed for the moment. Proper locale treatment is coming (I hope soon) and this seems like the wrong place to start insinuating special locale handling into the standard library."
Three years later another Go team member commented that "Date localization is definitely still in the planning."
We're in year 8 now. The issue is still open. Rob Pike is still hoping.
№ of countries ≠ № of people though. ⅘ of the 5 most populous countries¹ use decimal points, and together they alone² have ~42½% of the world’s people. Do all decimal point countries together have ≤50%? (Edit: Is it really not “normal” to do things the Anglophone way?)
¹According to https://en.wikipedia.org/wiki/List_of_countries_and_dependen...
²Not counting territories
https://github.com/golang/go/issues/6189
https://github.com/golang/go/issues/26002
Then why does it support the "%n" specifier? Isn't it exactly for that use case?
the sum of all scanned bytes is quadratic to the length of the huge input string.
?
edit: oh the autocorrect...
> extract a small token from the beginning of a large string, and then skip past it to do the same thing again after that small token: essentially, build a lexical analyzer in which the pattern matcher consists of calls to scanf.
Scanning floats with sscanf means undefined behavior on a datum like 1.0E999 against a %lf (double), where the exponent is out of range. IEEEE double goes to E308, if I recall.
C99 says "Unless assignment suppression was indicated by a[n asterisk], the result of the conversion is placed in the object pointed to by the first argument following the format argument that has not already received a conversion result. If this object does not have an appropriate type, or if the result of the conversion cannot be represented in the object, the behavior is undefined."
I'm seeing that on glibc, 1E999 scans to an Inf, but that is not a requirement.
This problem could be solved with sscanf, too, while maintaining the degenerate quadratic behavior. sscanf patterns could be used to destructure a floating-point number textually into pieces like the whole part, fractional part and exponent after the E, which could then be validated separately, like that the E part is between -308 and 308 and so forth. Someone could still do this in a loop over a string with millions of floats. I'd say though that you're way past the point of needing a real lexical analyzer, and not multiple passes through scanf.
Do I need a full fledged parser for that? No. Does it have to traverse the whole string every time? No, because I’m being very clear about the maximum length of the thing I’m trying to parse.
You cannot not conclude that it’s a bug.
A mechanism for turning a string in memory into a string should not be taking its length.
GBLIC has an extension called fmemopen. The API is:
FILE *fmemopen(void *buf, size_t size, const char *mode);
This interface smells like it might have the flaw that if someone wants "buf" to come from a null-terminated string, they must measure that string in order to supply the size parameter.I.e. the underlying mechanism is binary, and does not stop at null characters.
There needs to be a separate mechanism with a different underlying stream implementation:
FILE *fstropen(const char *str); // mode implied: "r"
This doesn't require a size.That fmemopen extension points to a solution to the original problem, though non-portable: open the entire buffer of numbers as a stream in one fmemopen call, and then use fscanf to march through it.
https://pubs.opengroup.org/onlinepubs/9699919799/functions/f...
char * start = data;
char * next = strchr(data,'\n');
while(next)
{
*next=0;
sscanf(start, ...)
start=next+1;
char * next = strchr(start,'\n');
}But we are not continuing to scan into the junk here to get more tokens here; we don't have a loop that will cause O(N*N) behavior.
E.g. this could be user input from a form field where they are expected to type a date, and we want to reject that if there is trailing junk. At that point, the user gets an error, and has to fix the input. We don't look for anything in the trailing junk.
It's not about "scanning into junk". The problem would happen if you used scanf to extract integers from a string of `' '.join([1]*1000000)`. Because you would make 1,000,000 scanf calls, and _each_ of those calls would call strlen on the string, quadratically scanning over the string to repeatedly find the end.
In fact, every sscanf is O(size of the string) even when the string is well formed. This is not a well behaved function.
> It looks like the problem is that reading floats is done using c4::from_chars -> c4::atof -> sscanf which ultimately calls _IO_str_init_static_internal in the glibc implementation. As far as I understand, this essentially causes strlen to be called on the string that rapidyaml passes to it, essentially causing strlen to be called O(n^2) times.
As such, this doesn't follow. Just because sscanf takes the length of the entire source string doesn't mean will get N^2 behavior, unless you do silly things with sscanf, like extract a small token from the beginning of a large string, and then skip past it to do the same thing again after that small token: essentially, build a lexical analyzer in which the pattern matcher consists of calls to scanf. This is not an intended use case for sscanf. No self-respecting language parser designer would do such a thing in a non-throwaway, production program.
sscanf has undefined behaviors for out-of-range numeric values, so you can't use it for just blindly extracting numeric tokens at all, regardless of any other issues.
sscanf should only be used on a string that your program has either prepared itself, or carefully delimited by some other means.
For instance, suppose we have a string which holds a date (could be an input to the program). We can test whether it's in the YYYY-MM-DD format, and get those values out:
The purpose of junk is to test that there is no trailing garbage character. If there is, it will be scanned and the return value will be 4. If we don't care about that, we can just omit that argument and conversion specifier.This will accept inputs like 01-1-1. Worse, it will scan leading signs!
If you wan to insist on nothing but digits, and exact digit counts, you can break it up as string tokens first:
atoi is safe here, by the way, because we know that the integers are decimal strings no more than four digits.This is the sort of thing where sscanf comes in very handy. If you know how to use it, it solves these sorts of things nicely, and the performance is probably okay. At least not degenerately bad.
Complete sample with all the validation:
Some tests: