FR version is available. Content is displayed in original English for accuracy.
Advertisement
Advertisement
⚡ Community Insights
Discussion Sentiment
59% Positive
Analyzed from 1869 words in the discussion.
Trending Topics
#parser#error#hashmap#parsing#rwlock#value#rust#code#default#line
Discussion (36 Comments)Read Original on HackerNews
One common way to test it is just to pass ipv6 url: http://[f021:d981:b487:e57d:193e:550e::]/
RFC 3986 Appendix B [1] "Parsing a URI Reference with a Regular Expression":
The following line is the regular expression for breaking-down a well-formed URI reference into its components.
Let's test your URI with this regex, shall we? [2]
Seems correct to me.[1] https://datatracker.ietf.org/doc/html/rfc3986#appendix-B
[2] https://regexr.com/8nqop
https://github.com/bkaradzic/bx/blob/0b001f5f36579e8aea07efa...
That's a problem orthogonal to URI parsing.
You parse the URI with the RFC 3986 regex, which gives you the components: scheme, authority, path, query, fragment.
You're then free to parse any of the components according to your own bespoke rules, e.g. the query string often follows the key=value&key=value&... pattern.
Does it need to be human readable, does it need to work across all platforms. Does the it need to be secure. These things change everything. Speed, reliability, security pick one.
Your point about being compliant with the real spec is the difference between a 20 line scannf and and a 1000 line function. Yeah. Ha.
Famous examples: despite so many initial good intentions, html tags don’t need to be closed, JSON numbers are too often encoded as strings, YAML can look like what most people expect or it can look progressively more like JSON… and on and on.
If what you're parsing is within the capacity of humans to interact with (so in the range of tens of kilobytes), a grammar that requires an O(N^2) parser is totally fine.
We spend years learning basic arithmetic like the addition of integers. You could very well argue that there is no need for that either because everyone has a calculator app on their phone. This is how dark ages begin.
If someone is taking malicious stabs at your API then you have a problem
A simple recursive-descent parser is easy to write by hand and runs in linear time.
In the face of backtracking the time depends on the complexity of the grammar, since it's basically a brute force search through all the rules.
Looking at the linked URL parser, why doesn't it look like
It looks totally ad-hoc.Is there a common source of extra \r in malformed inputs, beyond those existing as part of \r\n? Or is this just a dig at Windows-style line endings? If there's something weird going on I think I'd rather fail loudly.
> Bounding the inner scanner to a single line makes “run past the end of a malformed line” unrepresentable rather than merely unlikely.
I don't really see what makes it "unrepresentable", and this reads more like "if you used the right scanning logic, you can't have used the wrong scanning logic".
handles all EOL sequences without backtracking. Or write a non-regex equivalent of that.
Is this really ergonomic?
https://github.com/rust-bakery/nom
No codegen, just function calling.
Maybe you don't care? Fair enough.
The Rust compiler is a common example of a compiler that does a good job here, and I think it is one of only a few.
Built-in line and column tracking. Any movement across a newline updates the line number, including a backwards seek. getLine and getColumn are always available and both are one-based, which makes decent error messages nearly free.
That doesn't sound like much, but having hand-written plenty of recursive descent parsers, it's most of what you need for good error messages. Just being able to pinpoint where the error occurred is usually 80% of the battle; but keeping track of lines and columns in a hand-written parser is a pain.
Sure, for something like Rust, you need vastly more than that, but parsing is a tiny fraction of what the Rust compiler is doing -- type-checking and borrow checking is much more complicated and much more important.
A tiny library like this is a great fit for something like an INI file parser.
I say it like this because to me the only valid way to come to the latter class of error messages (containing constructive suggestions) is by first coming up with possible edits and then checking whether they make the whole parse and compile.
The Rust grammar is actually quite regular, that's why we have things like the turbofish for type parameters (`binding.method::<Type>()`): it makes the grammar unambiguous (a naïve parser would with a complicated grammar that accepts chained comparisons would have to deal with differentiating between `binding.method < value > ()` and `binding.method<Type>()`). But that doesn't mean the rustc parser doesn't do the work of supporting some the more complex grammar in order to provide better diagnostics. I like to say that rustc actually knows about meta-Rust, a daughter language that goes crazier in its features. I also joke that rustc isn't done until you can paste code from another language and following the suggestions you end up with valid Rust code without loss of the user's intent.
Part of the problem is that the places where incorrect code can fail is in more places than the parser. The chained comparisons example is one that is easy for Rust (as it doesn't support them), so the parser itself can produce a "missing turbofish" suggestion with high certainty, but for truly ambiguous expressions, the errors will happen later, during name resolution ("expected a value and found a type") or when checking the number of arguments. A production compiler needs to account for not only the original error, but also silence every knock-down error too. The simplest strategies are to just stop if at the end of a given stage there are errors (which leads to the "wave of errors" experience of fixing the "last" error leading to a ton of new ones) or fully replacing entire blocks of code that had a parse error with an AST node that acts as a tombstone marking that that later stages need to ignore it. The first option leads to a bad experience, and the latter is insufficient. A recent example of looking at this is https://github.com/rust-lang/rust/pull/159689, where `Arc::new(RwLock::new(HashMap<i32, i64>::default()));` currently produces
This is because the expression is syntactically correct as but after that PR it would only be the following, even though the parser hasn't changed: I think that there's a lot of work needed in the parser itself to produce good diagnostics. There are other strategies, like performing multiple parses at a given point when you've reached a known bad state (you've seen a flag-post that shouldn't be there, but that is a signal for a handful of other known cases), or fully consuming the rest of a block when an unrecoverable parse occurred (we're half-way through parsing function arguments, but failed? consume the rest of the statement or of the parent block, accounting for sub-scopes). The latter can cause the rest of the file to be consumed, but that's an edge-case that in practice is much better than a deluge of irrelevant errors.Another added complexity is how some easy-to-hit errors occur during lexing, which means the compiler has barely any information about the user's code. Mismatched braces/parens is one of those. rustc tries to provide context by keeping a queue of seen open delimiters to point at, and explicitly checking for their indentation level as a heuristic to detect where the user's intent diverged from the code, but that's overly reliant on the code being sanely formatted (thanks to rustfmt-on-save, that's a good bet for many users). For an example of the things rustc can do even in the lexer, you can look at https://github.com/rust-lang/rust/pull/160592.