Equality of YAML nodes

Hi all,

I have some questions and opinions on the definition of
YAML data node's equality. It became a very long email.
I'm sorry about it.


The current specification defines the YAML node's equality 
as the folowing:

> Two nodes must have the same tag and content to be equal. 
> Since each tag applies to exactly one kind, this implies 
> that the two nodes must have the same kind to be equal. 
> Two scalars are equal only when their tags and canonical 
> forms are equal character-by-character. Equality of 
> collections is defined recursively. Two sequences are equal 
> only when they have the same tag and length, and each node 
> in one sequence is equal to the corresponding node in the 
> other sequence. Two mappings are equal only when they have 
> the same tag and an equal set of keys, and each key in this 
> set is associated with equal values in both mappings. 

For the first glance, this definition of equality seemed 
to be completely reasonable for me. 

But with implementing a YAML library, I now have some 
questions, especially for the equality of collection nodes 
and that of the nodes which represent some native data 
object that have their own equality evaluation schemes.


At first, I want to confirm that, a description 
"two nodes are equal only when some condition is met" means
"two nodes are not equal when some condition is not met."
If not, I want to know the exact meaning.


Then, I start the discussion with the equality of recursive 
collection nodes. Let me confirm that the following two nodes 
are not equal to each other.

%YAML 1.2
---
&A { *A }
---
&A { { *A } }
...

I thought so, because their node graph topologies are 
different even though the Tags and the contents are the 
same if we compare the nodes one by one, without looking 
at the global graph structures. 

Another reason is that if they should be equal, I can not 
find a good way to compare such recursive nodes without 
causing an infinite loop in my library.


Next, I thought the following two are equal to each other.

%YAML 1.2
---
&A{ *A, { *A } }
---
&A{ { *A }, *A }
...

The reason is, the order of mapping key does not affect 
its content.


Then, what do you think about the next YAML document?

%YAML 1.2
---
&A { &B { *B, *A }, *A }
...

I thought the mapping *A and mapping *B are equal to each 
other because their graph topologies are the same, except 
for the order of appearance in the document. If this 
understanding is correct, a YAML parser should reject the 
above input because a mapping can only contain unique keys 
in YAML. Note that such an example can be easily expanded 
into further complex forms.

%YAML 1.2
---
&A { &B { *B: *A, *A: *B }: *A, *A: *B }
---
&A { &B { *A, *B, &C { *A, *C, *B } }, *C, *A }
---
&A { &B { *A, &C { *B, *A } }, *C }
...

When I started implementing an equality evaluator that 
works with such complicated cases, I found it is a 
quite tough work.


So, I wondered if such a complicated comparison is 
really implemented in other libraries. 
I tested ruby 1.8.7's YAML library. 

  require 'yaml'
  
  p YAML.load("{ 3, 3 }") #1
  # {3=>nil}
  
  p YAML.load("{ { foo }, { foo } }") #2
  # {{"foo"=>nil}=>nil}
  
  p YAML.load("{ &A { *A }, *A }") #3
  # {{{...}=>nil}=>nil}
  
  p YAML.load("{ &A { *A }, &B { *B } }") #4
  # {{{...}=>nil}=>nil, {{...}=>nil}=>nil}
  
  p YAML.load("&A { &B { *B, *A }, *A }") #5
  # {{{...}=>nil, {...}=>nil}=>nil, {...}=>nil}

Obviously, the answer was no. 
Anyway, let me dig into the examples for some degree. 

The example #1 shows that this library does not 
reject a mapping with duplicated keys. Instead, 
it silently overwrites the entries. As discussed 
in the thread 
  [Yaml-core] YAML ain't a superset of JSON 
  From: Jakob Voss <jakob.voss@ni...> - 2009-06-06 14:05,
this is not an official behavior of a YAML parser, 
though most of JSON parsers go that way. 

>From these examples, we can see how the library evaluates 
the equality.
Example #2 and #3 show that the library is aware of equality 
if they are not recursive or are the same instance.
Example #4 and #5 show that the library is not aware of
equality if they are recursive and are not the same instance.

I guess these results are not necessarily intended by the 
library's implementer but just due to the way on which 
ruby runtime compares two instances of ruby's Hash class.

So, my first several questions are:
 Is there any YAML library that employs the strict node 
 comparison that is defined in the specification?
 Must I implement such a comarison for my library 
 if I want to support YAML 1.2 specification?
 In which application, is such a strict comparison valuable?


I move on to the next issue. 

Ok, I have implemented an equality evaluator that works 
correctly for all cases I have tested, after quite a bit 
of struggling.

But then, another concern arose. With such an equality 
evaluation, it is tricky to build a node tree defined 
in the next YAML. 

%YAML 1.2
---
&A { &B { *B, *A }, *A, null }
...

This document expresses a valid node tree without any
duplicated keys. However, it is almost impossible to 
avoid duplicated keys from appearing while composing
the mapping node.

ok: &A { }
ok: &A { &B { } }
ok: &A { &B { *B } }
ok: &A { &B { *B, *A } }
NG: &A { &B { *B, *A }, *A }
ok: &A { &B { *B, *A }, *A, null }

I have no idea to avoid this problem, do you?


The last issue is related to the way the libraries 
use YAML. Often in YAML libraries, a native object 
of some class or structure is represented by a YAML's 
mapping node, whose keys represent the names of the 
properties or fields and the correspoinding values 
hold their values.

The following example is again from ruby 1.8.7's 
YAML library.

 require 'yaml'
 
 # A class with no members
 class Test
 end
 
 # Create a hash with instances of Test
 p hash = { Test.new => 1, Test.new => 2 }
 
 # {#<Test:0x7ff2d60c>=>1, #<Test:0x7ff2d5f8>=>2}
 
 # Note that two instances of Test class are not
 # equal to each other, because ruby compares 
 # class instances, by default, by their identity.
 
 # Convert the hash into YAML.
 print yaml = YAML.dump(hash)
 
 # ---
 # !ruby/object:Test ? {}
 # : 1
 # 
 # !ruby/object:Test ? {}
 # : 2
 
 ### Oops, this library has such an obvious bug!
 ### I guess it should have been as the following.
 
 p yaml = <<EOS
 ---
 ? !ruby/object:Test {}
 : 1
 ? !ruby/object:Test {}
 : 2
 EOS
 
 # Convert YAML back to the hash
 p YAML.load(yaml)
 
 # {#<Test:0x7ff2c9f0>=>2, #<Test:0x7ff2cbf8>=>1}
 
This behavior (without the obvious bug) is not surprising 
for most of users of the library. A hash is stored and 
restored successfully. 

But, as studied above, this behavior violates the YAML's 
specification, because the two keys in the mapping node 
are not unique in the YAML node representation. YAML
forces a library to compare two mappings always by the Tags 
and their contents, even when the nodes represent some 
instances of classes that have their own equality comparison 
operators.

Should the spec really force a library to reject such an
input, even though that will not be expected by most of
users?


At this point, I started considering the purpose of defining
YAML node's equality in the specification. In my opinion, the
purpose is mainly for rejecting a mapping node because of its 
duplicated keys, or silently neglects the new entry when a 
!!merge key is processed. 

Another purpose is for allowing a library to represent some 
equal schalar nodes by an single identical node, as is written 
in the specification.
> A YAML processor may treat equal scalars as if they were 
> identical.
I have not understood the importance of this description, though.

I can not think of any other meaning of nodes equality in the 
parsing and composition stages. Then, how about the meaning after 
the composition? If we take the definition of nodes' equality 
strictly, we can never construct native objects from YAML nodes. 
Note that, as seen above, constructing a ruby's hash or an 
instance of Test class from a YAML mapping node did not preserve 
the data equality. So, the YAML spec determins the node's equality
after the composition stage, there will be very little application 
where one can make use of YAML. So, I think the definition of data 
equality after composition stage should be put beyond the scope of 
YAML specification. 


Consequently, I feel the current definition of node's equality
is not suited to the real applications.

My opinion is as following.

1. When a node has a Tag that is not a YAML's standard tag, the YAML 
 parser and composer should evaluate nodes' equality only from the 
 identity of the nodes, because the parser and composer do not know 
 how to compare the data correctly. If the equality in their native 
 data form matters, it should be checked at the construction stage,
 where the library has full access to the native object and  to its 
 equality operator.

2. For scalars with YAML's standard tags, the equality can be 
 safely evaluated by their canonical forms as defined by the 
 current specification. 

3. For !!seq and !!map, the YAML parser and composer should evaluate 
 the equality only from the identity of the nodes. This means, even 
 if a mapping node has two collection nodes that have same content,
 the library should not reject such an input, instead, they should 
 pass through it to the constructor. 
 
 In most of cases, these collection classes are mapped into the 
 arrays and hashes at the construction stage. The equality of the
 collection objects are evaluated by the system default equality 
 operators. 
 
 When the language does not have such array or hash classes,
 the YAML library might implement a collection classes to express 
 those nodes. In such cases, the equality should be evaluated 
 as the following. If two nodes are identical, they are equal. 
 If two nodes have different Tag, they are not equal. If nodes 
 are not recursive, their contents are compared one by one to 
 judge equality. If nodes are recursive, the result can be the 
 library dependent. Note that in any cases, the equality evaluation 
 is done at the construction stage. a parser and a composer should 
 not evaluate such content based equality.

For the second one, I'm not sure if a parser and a composer must 
be aware of equality just to detect the duplicated keys or not.

For the third one, I came to this conclusion because of the 
following reasons.

At first, I considered the usage of !!seq and !!map nodes as 
map keys, which is the only case the equality matters in the 
parsing and composing stages. I did not think of many use cases 
where different instances of collections with same contents should 
be evaluated to be equal (to have the mapping to be rejected by the
YAML processor?). At the same time, the definition given in the 
current specification seems to cause difficult issues as pointed 
out above for the recursive nodes. In addition, if we want to 
express some equal keys in a simgle mapping (again, for what?), 
we can always use anchors and aliases.

Secondly, as same as the cases where a node has some non standard
tag to be mapped into some native data, !!seq and !!map nodes are 
used as almost always the representations of the instances of array 
and hash. Even when the YAML specification defines their equality, 
it is meaningless unless the specification forbids such mapping. 

My opinion might be due to the lack of case studies of mine. 
If there is any library that deals with the collection nodes' 
equality strictly along with the specification and someone is 
making use of the definition, I want to learn about the case.


I know this suggestion is very much controversial and probably 
contains misunderstandings of mine. So, I would like to listen 
to the opinions of yours.

What do you expect to a YAML library for nodes' equality?
What do you expect to the YAML specification for nodes' equality?

Thank you for reading my long-long email and for your possible 
response to it.

Best,
Osamu TAKEUCHI


------------------------------------------------------------------------------
Come build with us! The BlackBerry&reg; Developer Conference in SF, CA
is the only developer event you need to attend this year. Jumpstart your
developing skills, take BlackBerry mobile applications to market and stay 
ahead of the curve. Join us from November 9&#45;12, 2009. Register now&#33;
http://p.sf.net/sfu/devconf