5 ms·

An alternative approach might be to use an existing popular serialization format such as Protocol Buffers, Apache Thrift, or Cap'N'Proto and create or improve t

• kstenerud 5y ago
  Yes, I had a look at these formats before embarking on my venture. I listed the things I found important in the comparison matrix: https://github.com/kstenerud/concise-encoding#-compared-to-other-formats https://github.com/kstenerud/concise-encoding#-compared-to-o... To your points: - Protobufs is not an ad-hoc format, which is a big reason why low-friction formats like JSON are popular. There are many use cases where formats like protobufs are clearly the superior choice, but CE doesn't target those. This is a fundamental trade-off so you can't have both. - readable-thrift is a diagnostic tool. You wouldn't want to be inputting data like that. I want the text format to be fully usable by non-technical people, like JSON is. - the capn proto tool page doesn't seem to document how the text format works (or at least I couldn't find any examples). It looks more like a diagnostic tool, not a first-class citizen. I felt that there were enough pain points, missing types, and missing security features (for example versioning) to warrant a fresh start.
  • minhmeoke 5y ago
    Thank you for the clarification! Perhaps a better example would have been Apache Avro (still has a schema, though): https://en.wikipedia.org/wiki/Apache_Avro https://en.wikipedia.org/wiki/Apache_Avro This looks like a very ambitious project, and I can see that you've put a lot of thought, time, and effort into it! You clearly have a lot of interesting ideas (the graph idea is really cool) and significant experience with data formats. If this is a security-oriented application, then with cyclic data structures there is the risk of blowing out your server's memory using something like a fork bomb when processing untrusted user input (https://en.wikipedia.org/wiki/Fork_bomb https://en.wikipedia.org/wiki/Fork_bomb). There are some systems like DHall that guarantee termination by putting upper bounds on computation: https://dhall-lang.org/ https://dhall-lang.org/ I'm also a bit concerned with how the different features can interact, for example it's not super clear how to distinguish between UTC offset (-130, or do these always have to be 4 digits?) and global coordinates (-130/-172). An attacker could specify a comment inside the media type (eg: application/* which would require special logic to filter out). My concern is that the parser will become extremely complicated and require a lot of special-case logic and validation (eg: there must be at least one digit on each side of a radix point) which is more prone to errors and unexpected behaviors. Rather than using slash delimiters, I'd recommend splitting the time formats into subfields, eg: { date: "2022-01-01" time: "21:14:10" offset_is_negative: true offset: "10:30" } This does make the text format more verbose, but it reduces ambiguity and makes the parsing faster as well since you don't need to descend into branches and backtrack when they don't match, and also might permit more code/logic reuse. It's also not clear how easy it is to add new data types to the grammar. Based on the project description, it seems like you're using ANTLDR parser. Since you seem to be quite interested in parsing, you might also be interested in parser combinators which are a somewhat different approach with different tradeoffs: - https://softwareengineering.stackexchange.com/questions/338665/when-to-use-a-parser-combinator-when-to-use-a-parser-generator https://softwareengineering.stackexchange.com/questions/3386... - https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/ https://fsharpforfunandprofit.com/posts/understanding-parser...
    • kstenerud 5y ago
      Yes, I had a look at avro as well. I've been following all of the established and nascant formats over a number of years, hoping for one that addresses my concerns, but unfortunately nothing emerged. My ambitions are actually at a much higher level; this is just to set a solid foundation for them. Cyclic bombs are but one security concern... There are actually a LOT of them, which I try to cover cover in the security section ( https://github.com/kstenerud/concise-encoding/blob/master/ce-structure.md#security-and-limits https://github.com/kstenerud/concise-encoding/blob/master/ce... ). The security space is of course wider and more nuanced than this, but I didn't want to turn it into an entire tome so I tried to cover the basic philosophical problems. At the end of the day, you must treat data crossing boundaries as hostile, and build your ingestors with that in mind. Sane defaults can avoid the worst of them (and CE actually REQUIRES sane defaults for a lot of things in order to be compliant), but no format can protect you completely. A "fork bomb" using cyclic data is unlikely, unless your application code is really naive (if you're using cyclic data, you need to have a well-reasoned purpose for it, and are likely just using pointers internally - which won't blow out your memory unless you're doing something foolish when processing the resulting structs). Actually, this does give me an idea... make cyclic data disallowed by default, just to cover the common case where people don't use it and don't even want to think about it. Re time formats: global coordinates will always start with a slash, so 12:00:00/-130/-172. UTC offsets will always start with + or -, and be 4 digits long, so 12:00:00+0130 or 12:00:00-0130. The validation rules are very specific, and that does complicate the text format a bit, but this drives to the central purpose of it: The text format is for the USER, and is not what you send to other machines or foreign systems. It's for a user to edit or inspect or otherwise interact with the data on the RARE occasions where that is necessary. So the text format doesn't need to be fast or efficient, only unambiguous and easy for a human to read. You certainly shouldn't open an internet connected service that accepts the text format as input (except maybe during development and debugging...) In fact, I would expect a number of CE implementations (such as for embedded systems) to only include CBE support, since you could just use a standalone command-line tool or the like to analyze the data in most cases. Re: subfields. That would make it harder for a human to read. The text format sacrifices some efficiency for human friendliness and better UX. Parser logic re-use isn't really a priority (other than making sure it's not OBVIOUSLY bad for the parser), because text parsing/encoding is supposed to be the 0.0001% use case. It's not super easy to add new types to the text format grammar, but that's fine because human friendliness trumps almost all, and adding new types should be done with EXTREME CARE. I've lost count of all the types I've added and then scrapped over the years. It's really hard to come up with these AND justify them! The ANTLR grammar is actually more of a documentation thing. I've verified it in a toy parser but it's not actually tied to the reference implementation (yet). The reference implementation currently is similar to a parser combinator, with a lot of inspiration from the golang team's JSON parser (I watched a talk by the guy some time ago and was impressed). But at the same time I'm starting to wonder if it might have been better to implement the reference implementation as just an ANTLR parser after all... leave the optimizations and ensuing complications to other implementations and keep the reference implementation readable and understandable. The binary format code is super simple, and about 1/3 the size of the text format code. The major downside of ANTLR of course is the terrible error reporting.