Compact (Canonical) Serialized Form

[nebneb0703]

There exists a specification RFC 8785 for serializing JSON in a compact and consistent way. This is useful for reproducability in cryptographic applications (e.g. hashing, signing). It may be useful to design such a standard for KDL documents as well.

I am starting a discussion to collect thoughts and help inform the design for the implementation I plan to use in my project. This may not end up being made into an official specification, but opinions from KDL experts may be useful for my project. For context, I will be using kdl-rs and its public API.

My initial ideas are this:

• Nodes must be separated by semicolons rather than newlines, and with no other unnecessary whitespace or comments.
• Node children (including of the root document) must be sorted according to their UTF-8 names.
• Node properties must be sorted according to their UTF-8 names, and serialized after all positional arguments. There must not be any duplicate properties serialized.
• Strings must be serialized as identifiers if possible, or quoted with escapes otherwise.
• Numbers must:
  • not contain + or _.
  • be (ASCII) lowercase.

Unanswered questions:

• What ordering should be forced on sibling nodes if they have the same name but different entries or children?
• What to do about type annotations?

Rules for compact serialization could be independent from the rules of a canonical ordering, and form two different specifications. A canonical ordering used without compact serialization could simply be a recommended (auto) format for KDL documents.

[zkat]

This sounds like a great thing to put together!

I'll note that you shouldn't restrict node children in the ways you're thinking, as ordering matters in many cases, and even duplicates are perfectly legitimate.

As far as other compactness measures: converting multi line strings to regular strings might be a good idea since they tend to take up a lot of unneeded whitespace. For type annotations I don't think there's much you need to do besides not having unnecessary whitespace and doing the usual string-to-identifier transform.

Then there's small details like being explicit that the last child should not have a semicolon. Also that curly braces should be flush with surrounding tokens (foo{bar} is legal)

Thinking about it I actually kinda wonder if we can get more compact than JSON because there's fewer required separators in KDL

[nebneb0703]

I'll note that you shouldn't restrict node children in the ways you're thinking, as ordering matters in many cases, and even duplicates are perfectly legitimate.

You're right that it doesn't make sense to include ordering requirements for a compact form spec to be used for any arbitrary KDL document.

In a typical usecase, for example when representing nodes/documents as structs, the application does not utilise duplicate children and ignores order. In cases where duplicate children (names) are used, it may be treated by the application as an unordered set with unique elements (with respect to the positional arguments, properties and its own children).

In order for such data to be encoded as KDL documents for usage in cryptographic applications, I need a transformation for KDL documents such that the emitted (compact) KDL string is byte-for-byte equal if and only if the data is equal according to the typical usecase. I'm unsure if this can be encoded in a function that takes in arbitrary KDL documents without an understanding of the application's particular ordering requirements (or lack of).

Such a function (whether general-purpose or application-specific) would need to define:

• Ordering of a node with name N and X positional arguments with respect to a node with name N but Y positional arguments
• Ordering of a node with name N and set {p} of named properties with respect to a node with name N but a set {q} of named properties
• Ordering of a node with name N and set {c} of children with respect to a node with name N but a set {d} of children
• Ordering of nodes with the same name but different type annotations
• Ordering of combinations of the above

The purpose of a consistent ordering scheme is that an arbitrarily formatted KDL document can be sorted according to this scheme and then satisfy the equality requirement. The hash of a KDL document that represents the same information but contains different formatting would be equivalent after going through this process.

A naive solution would be to slap #[derive(serde::Serialize) on it and just use whatever output it gives. Maintaining semver compatibility becomes more complicated. It may also not be compatible with the special behaviour of kdl-rs's deserializer, maybe if you use alias instead of rename for the special keys?

[zkat]

According to the KDL data model, two different KDL documents with children in different order are, in fact, different documents regardless of how the consuming applications choose to interpret them. If you want this level of additional sorting for comparison, it has to be done at the application level.

For example, you wouldn't sort every <ol> in an HTML document alphabetically because that wouldn't make sense, and the same applies here. Even sorting <dl> would be considered a mistake if you're talking about a standard document

[tabatkins]

What to do about type annotations?

Annotations are part of the data model and necessary to retain. There's no default annotations or anything, so it's quite straightforward - it a node or value has an annotation, preserve it. As Kat said, they're just strings, so they serialize with the compact string rules (prefer idents, etc).

[bgotink]

I think it would make sense to create a separate sub-spec for JiK, since in JiK

• we can sort the children (JSON says "[a]n object is an unordered collection of zero or more name/value pairs" (emphasis mine));
• non-complex values should be passed as property rather than children; and
• tags are only required in certain otherwise ambiguous cases, and should be removed everywhere else.

[tabatkins]

Yeah, JiK can canonicalize much more aggressively than arbitrary KDL. Similarly, XiK can canonicalize slightly more aggressively than arbitrary KDL. (Moving lone text children into attribute position, etc.)

[shimeoki]

i done something like this for both testing and fun while i was implementing my own library to just save the documents i needed later, and it's much simpler than making a proper formatter.

first of all, i want to disagree about making this as a sub-spec for jik or xik. if you want json or xml, then just use these languages. i think it should be a requirement that a single canonical compact form exists for any valid kdl document. you have a kdl document? then this form exists, and you can get it with a command like kdlc doc.kdl (kdl compiler, kdl compacter, which you like more).

as a second point, my opinion is that this form should be also a valid kdl document and have the same semantics as the original document. no separate specification to implement - just kdl. and you can get the same values from reading this document back.

and as the last requirement, i think this form should be a single line. all valid kdl documents are able to fit in a single line, and this allows usage, for example, in logging: one line in a file is one entry in the log. this gives a funny and actually great side-effect that the file from these lines is also a valid kdl document, because the newlines separate the last node on the previous line from the next.

therefore, this form comes mostly to these statements (i hope i didn't forget anything):

• all single- and multi-line comments are stripped (you don't need these for serialization)
• all slashdashed elements are skipped (as they are counted as whitespace)
• whitespace around = in properties is removed
• whitespace in type annotations and after them is removed
• whitespace after opening braces and before closing braces is removed
• keep a single space before the first entry and after every entry except the last one
• keep node terminators as semicolons for all nodes except the last one
• remove all properties with the same key except for the last one and sort them by keys
• place properties before/after (pick one, i choose the former) arguments

we cannot do much more than that, because kdl is a node-based language and every node counts as unique, and their order also matters. the same goes for arguments. properties, however, are a special case, because the specification says that latter properties override the former. and to keep the result deterministic, they should be sorted and placed in a fixed place like before the arguments.

but there is still a matter of values: strings, numbers and others. booleans and other keywords are simple: they are kept as is. for numbers and strings the situation is a bit more complex.

i advocate that numbers should also be kept as-is. while 100000 can be represented as 1e5, which is shorter, there are just too many edge cases and they are dependent on the target language. and i can argue that different writing of numbers in the document (even as in the obvious example with 100000 above) means that these are two different documents. therefore, it doesn't contradict that there is a single form for every document.

strings, on the other hand, are able to be "compressed". to keep them in a single line, all strings should be converted to identifier, single-line or raw single-line strings (all strings can be represented in at least one of these forms). if string is able to be represented as an identifier (not looks like a keyword or a number, no spaces, etc.), then it is done so. all other strings are single-line quoted (not raw) strings.

it can be argued that raw strings can be more compact - it is true: strings with many quotes and escapes. however, not all strings can be put in a raw string as-is: it requires the implementation to count the needed amount of hashes. i think it's more pragmatic to keep only quoted strings and keep the implementation trivial.

if that goes (not essentially in this form) into the set of official specifications, then i will probably pretty easy make an implementation and a program for this (but no promises about the date). i reserve the kdlc name for myself :)

[zkat]

this all looks great and concurs with my understanding of what this format would look like. Additionally, I'll note that you can also omit whitespace before opening child blocks, so foo{bar} is fine.

[tabatkins]

Same, this matches my understanding of how a compact form would work!

[shimeoki]

while OP mentioned that they want to make their own implementation, i still made my own program - kdlc - to play around. for example, it gives this document from the first example in readme:

package{name my-pkg;version "1.2.3";dependencies{lodash alias=underscore optional=#true ^3.2.1};scripts{message "hello\nworld";build "echo \"foo\"\nnode -c \"console.log('hello, world!');\"\necho \"foo\" > some-file.txt"};the-matrix 1 2 3 4 5 6 7 8 9}

[shimeoki]

after testing kdlc a bit, i think two additional clauses are needed:

1. if a children block doesn't have any nodes, then the braces are skipped
2. in a number, all letters are converted to lowercase
3. in a number, all plus signs and underscores are skipped

for the first point, while it can be argued that presence of a children block can mean something for the document (otherwise, why it is not commented via a slashdash?), kdl doesn't define any semantics for the presence of a block. therefore, it acts just as an element of the syntax to combine different nodes together on the same level. no nodes - no syntax.

for the last two points, while it may seem that they contradict my initial rules, they are not. letters in numbers are used only in hex literals and exponents, and uppercase variants are purely visual. the same goes for plus signs (numbers are positive by default) and underscores. these changes do not interact with a value (like converting 10000 to scientific notation and vice versa) directly and only change the representation.

[shimeoki]

also, for some reason only now another point for making this an official specification came to my mind: testing.

right now official kdl tests expect a specific notation for some elements, and this was mentioned before. while kdl-test exists and it's a pretty clever solution, it requires the implementer to satisfy the json encoding.

this can be solved with a compact format: doing this logic is much easier than doing a formatter with indentations. it requires the implementer to have an ability to output the minimal document for the users (which is a good thing) and allows to run the tests, if this format will really be used in tests. also the whitespace is skipped, so you don't need format-preserving parser, right?

but that's not the case: it still expects a format-preserving parser. while comments and whitespace are discarded, numbers are still a problem. if an implementation reads a number and it stores the number not as a string or raw bytes from the input to preserve formatting, but instead in a number type (int, float, etc.), then the initial format is lost.

right now, according to my own rules, this leads to this compressed format be essentially unavailable to these implementations. if a number was written as hex in source, but the implementation converted it to int and wrote the int back, you are unable to know whether it was a hex in the first place or not.

at this point, it's pretty weird. if you have a format-preserving parser, then you probably need tests to ensure that the format is really preserved, so you are going to write your own tests for that. and if you don't have format-preserving parser, then you can't satisfy the compact form and you cannot pass the official tests. it becomes kinda pointless.

so even if i tried to avoid it, it's probably inevitable that the compact form should convert the numbers to a specific format, that can be satisfied even if the implementation doesn't know about the source format of the number. and kdl specification has a statement that there is no logical distinction between number types, so it makes sense.

if it came to this, then probably something like that is okay:

• all numbers are converted to a float format like x.y
• all leading zeros in x are removed except if it is the last digit in x
• all trailing zeros in y are removed. if no zeros remain, then dot is also removed (essentially an integer)
• if a number is negative, then x has a leading -

exponents and scientific notation shenanigans are debatable. it will save some symbols in the output, but making a specific algorithm for this seems like a huge pain.

[nebneb0703]

I wrote a basic formatter utilising kdl-rs which passes a simple test but is still unused in my application so hasn't been thoroughly tested. Most of the complicated formatting is simply delegated to kdl-rs. I would have liked to test equality of the original vs compacted form after being deserialized but kdl-rs compares formatting unhelpfully (effectively None vs Some("")).

Details

use std::{
    fmt,
    cmp::Ordering,
};

#[derive(Debug, Clone)]
pub struct Compact<'a> {
    pub document: &'a kdl::KdlDocument,
}

impl<'a> Compact<'a> {
    pub fn new(document: &'a kdl::KdlDocument) -> Self {
        Self {
            document,
        }
    }
}

impl<'a> fmt::Display for Compact<'a> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        format_document(self.document, f)
    }
}

pub fn format_document(
    document: &kdl::KdlDocument,
    f: &mut fmt::Formatter,
) -> fmt::Result {
    let len = document.nodes().len();

    for (index, node) in document.nodes().iter().enumerate() {
        format_node(node, f)?;

        if index + 1 < len {
            f.write_str(";")?;
        }
    }

    Ok(())
}

pub fn format_node(
    node: &kdl::KdlNode,
    f: &mut fmt::Formatter,
) -> fmt::Result {
    if let Some(type_identifier) = node.ty() {
        format_type_identifier(type_identifier, f)?;
    }

    format_identifier(node.name(), f)?;

    let mut entries = Vec::from(node.entries());

    entries.sort_by(|a, b| {
        match (a.name(), b.name()) {
            // Preserve ordering
            (None, None) => Ordering::Equal,
            (Some(_), None) => Ordering::Greater,
            (None, Some(_)) => Ordering::Less,
            (Some(a_name), Some(b_name)) => {
                a_name.value().cmp(b_name.value())
            },
        }
    });

    for entry in entries {
        f.write_str(" ")?;

        if let Some(name) = entry.name() {
            format_identifier(name, f)?;
            f.write_str("=")?;
        }

        if let Some(type_identifier) = entry.ty() {
            format_type_identifier(type_identifier, f)?;
        }

        fmt::Display::fmt(entry.value(), f)?;
    }

    if let Some(children) = node.children() {
        f.write_str("{")?;
        format_document(children, f)?;
        f.write_str("}")?;
    }

    Ok(())
}

pub fn format_type_identifier(
    type_identifier: &kdl::KdlIdentifier,
    f: &mut fmt::Formatter,
) -> fmt::Result {
    f.write_str("(")?;
    format_identifier(type_identifier, f)?;
    f.write_str(")")?;

    Ok(())
}

pub fn format_identifier(
    identifier: &kdl::KdlIdentifier,
    f: &mut fmt::Formatter,
) -> fmt::Result {
    fmt::Display::fmt(&kdl::KdlValue::String(identifier.value().to_owned()), f)
}