Namespace prefix inheritance produces inefficient output

[danieldulaney]

It looks like prefix handling is slightly off when children use a prefix mapping inherited from an ancestor. For example, take the XML document:

<?xml version='1.0'?>
<root xmlns:x='urn:very-long-urn'>
  <x:child/>
  <x:child/>
  <x:child/>
</root>

If you parse and output the document with default writer settings, you end up with something like this:

<?xml version='1.0'?>
<root>
  <x:child xmlns:x='urn:very-long-urn'/>
  <x:child xmlns:x='urn:very-long-urn'/>
  <x:child xmlns:x='urn:very-long-urn'/>
</root>

This output seems sub-optimal. First, it's longer than the input. Second, it is more difficult to edit later because the prefixes all refer to different URN mappings. It would be better to maintain the single URN mapping wherever it is defined.

Additionally, it is difficult to see what is happening because Element doesn't have any way to see existing prefix-to-namespace mappings.

I propose two separate changes:

• Add a method on Element to see what prefixes have already been mapped there
• Always put the prefix definition on the element it was originally defined, even if it is only used in ancestor nodes

If there's buy-in, I'm happy to work on PRs that address both issues.

Example code (fails assertion):

let xml = "<?xml version='1.0'?><root xmlns:x='urn:very-long-urn'><x:child/><x:child/><x:child/></root>";

let package = sxd_document::parser::parse(xml).unwrap();
let doc = package.as_document();

let mut output = Vec::new();
sxd_document::writer::Writer::new().format_document(&doc, &mut output).unwrap();
let output_str = String::from_utf8(output).unwrap();

assert_eq!(output_str, xml);

[shepmaster]

• Always put the prefix definition on the element it was originally defined

It seems like this wouldn't catch the case of (pseudocode)

let a = make_element(URI_A, "a");
let b = make_element(URI_A, "b");
let c = make_element(NULL, "c", [a, b]);

This would ideally output as

<c xmlns:x="...URI_A...">
  <x:a />
  <x:b />
</c>

Even though the namespace was never defined on the parent (c).

Additionally, if the parent were in the URI:

let a = make_element(URI_A, "a");
let b = make_element(URI_A, "b");
let c = make_element(URI_A, "c", [a, b]);

Then we could just do:

<c xmlns="...URI_A...">
  <a />
  <b />
</c>

Doing the most space-efficient output is fairly complicated; it may be easier to aim for "source reproducibility" (which is what your test does).

Space-efficiency may be better viewed as some other function that a user could call before outputting the document (either on the Writer or the Document itself?).

Additionally, it is difficult to see what is happening because Element doesn't have any way to see existing prefix-to-namespace mappings.

• Add a method on Element to see what prefixes have already been mapped there

Is this method needed for the functionality or just as a debugging aid?

[shepmaster]

Overall I'm in favor of the direction!

[danieldulaney]

I think "source-reproducibility" is the way to go. It definitely makes sense about minimizing size being tough (might even be NP-complete? I wonder if there's a paper out there).

I was mostly thinking of trying to mimic the XML document as closely as possible within the data structures. This gives the consumer of the library lots of control over exactly where prefixes are defined. Also, I think it might also simplify some of the scoping code in writer.rs.

Is this method needed for the functionality or just as a debugging aid?

It would actually be useful for my current project, a Rust implementation of RFC 5261. Also, just for completeness -- it's a part of the XML document on disk, so it would be unusual that it isn't visible from inside the library. That said, I know I have a niche use-case, and most people are just trying to parse or generate some XML without worrying about the namespaces too much.

[kmkaplan]

I am not convinced that source-reproducibility is a good target. It offers little actual use but opens many difficulties with respect to the XML data model. This is because the XML data model is defined in terms of its infoset, not of its concrete (textual) representation. Namespace prefixes is a pain but not the only one if you aim for source-reproducibility. I can also think of

• Characters or external entities or entity references,
• CData or text,
• attributes order,
• single or double quoted attributes,
• <foo></foo> or <foo/>,
• white spaces inside tags,
• encoding

A more interesting feature would be Canonical XML

[shepmaster]

trying to mimic the XML document as closely as possible within the data structures.

We should definitely add functionality first, but the back of my mind worries about performance. Tracking everything about the document in the data structures would probably be overly expensive and/or annoying to deal with.

I also want to ensure that XML generated from pure code doesn't have a disadvantage compared to XML read from a file (or vice versa!).

This gives the consumer of the library lots of control over exactly where prefixes are defined

most people are just trying to parse or generate some XML without worrying about the namespaces too much.

My main concern with this is to avoid requiring users to deal with namespaces when they don't care do. This is why most things take a string (no namespace) or a tuple of strings (namespace). So long as we can keep the "typical" path straightforward, I'm pretty happy.

I can also think of

What's interesting here is that (almost?) all of the things you list are what I would consider output options, along the lines of the Writer that @danieldulaney just introduced. While it's true that conceptually each of those settings could be changed on a per-element basis, my gut says that in practice most XML processors have a single uniform mode that they default to (or accept, in some sad cases).

more interesting feature would be Canonical XML

It certainly seems like that it might be a better first target, especially since it's somewhat defined and standardized.

[shepmaster]

Thank you both for your contributions! This is the most activity that this repo has seen in a while and it's exhilarating. ❤️

[danieldulaney]

(almost?) all of the things you list are what I would consider output options

Single-vs-double quotes already are an output option, and there's a pretty clear path to implementation of the others in #70 (with the possible exceptions of CDATA and the definite exception of external entities).

Canonical XML

This seems like a really great additional feature. I think it might work best as a standalone transformation operating on a Document object, though I could also potentially see it also working as an output option.

Tracking everything about the document

I think namespace prefix declarations are worth tracking (unlike attribute order, quoting style, etc) because prefix declarations are attributes. Automatically generating prefix declarations for unknown elements makes sense, but it is also important to expose the location of explicit prefix declarations to the user, along with the ability to create new mappings (exists) and remove existing mappings (doesn't exist). Having control over which attributes (including prefix declarations) are present on every element is an important feature. For example, I'm not sure how I could use this library to transform this:

<root xmlns:n="namespace">
  <child>
    <n:grandchild/>
  </child>
</root>

into this:

<root>
  <child xmlns:n="namespace">
    <n:grandchild/>
  </child>
</root>

and back again.

Also, if all prefix declarations are visible on a particular element, it enables a fast, stack-based write implementation. You can maintain a stack holding the ancestor elements, and when you encounter a QName you check back through the stack for any prefix declarations (or a default namespace declaration) that match, falling back to generating a new prefix declaration on the current item (which gets used if any children use that namespace). I have a hunch (but would need to benchmark) that this faster than the current approach of keeping a stack of PrefixScope structures. It would definitely be cleaner code to reason about.