Re: Equality of YAML nodes

On Fri, 2009-09-18 at 21:33 +0900, Osamu TAKEUCHI wrote:
> Hi all,
> 
> I have some questions and opinions on the definition of
> YAML data node's equality..
>
> 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."

Yes, it is an if-and-only-if, at least as far as the spec is concerned.

> Then, I start the discussion with the equality of recursive 
> collection nodes.

The problem you describe is widely discussed in literaturem as the
(directed) graph isomorphism problem, and it occurs in many fields -
type systems for functional languages (close to YAML's case), chemistry
(are two molecules the same?), Prolog (unification algorithms), etc.

The general problem may be exponential (it is NP, maybe even
NP-complete). However, even naive algorithms do extremely well in
practice, and only get exponential on very pathological cases (your
examples aren't tricky enough to cause problems to a naive algorithm:-).

> Let me confirm that the following two nodes 
> are not equal to each other.
> 
> %YAML 1.2
> ---
> &A { *A }
> ---
> &A { { *A } }
> ...

No, they are not equal; one is a single mapping that contains a key
pointing to itself and a null value. The other has two mappings: the
first contains a key that is a second mapping that contains a key
pointing to the first, both keys having null values. There's no 1-1
mapping between them (the first has only one mappings, the second has
two distinct ones).

> 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.

Mapping two global (directed) graphs (that contain cycles) to each other
can be done without infinite cycles. 

> Next, I thought the following two are equal to each other.
> 
> %YAML 1.2
> ---
> &A{ *A, { *A } }
> ---
> &A{ { *A }, *A }
> ...

Yes, these are equal, because (as you point out) order of keys does not
matter, you can construct a 1-1 mapping between them.

> 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.

Yes, they are the same.

> If this 
> understanding is correct, a YAML parser should reject the 
> above input because a mapping can only contain unique keys 
> in YAML.

Yes.

> Note that such an example can be easily expanded 
> into further complex forms.

Oh yes. The graph theory people can show you examples that will curl
your hair. Of course these are "pathological" YAML, since (1) using
mapping for keys is not very common, (2) having cycles in mappings is
not very common, and (3) having both at once is even less common.

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

I wouldn't try to reinvent the wheel here. You can easily adapt one of
the simple but effective algorithms already developed for this (google
is your friend). Again, these will do the job quickly 99.9999% of the
time, unless someone invest a lot of effort in creating truly
pathological mapping keys.

> So, I wondered if such a complicated comparison is 
> really implemented in other libraries... 
> Obviously, the answer was no.

Alas...

> 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.

Yes.

> So, my first several questions are:
>  Is there any YAML library that employs the strict node 
>  comparison that is defined in the specification?

Probably not :-(

>  Must I implement such a comarison for my library 
>  if I want to support YAML 1.2 specification?

Technically, yes... but it is Ok for a library to punt and pass the
burden to the native data type implementation (which most YAML libraries
do).

>  In which application, is such a strict comparison valuable?

Yes, it ensures portability between different platforms. We do not want
to tie YAML data to a specific platform or application.

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

Great!

> But then, another concern arose. With such an equality 
> evaluation, it is tricky to build a node tree defined 
> in the next YAML
> ...
> I have no idea to avoid this problem, do you?

I didn't understand the problem. You have shown intermediate steps that
have duplicate keys; but the final result is OK, which is all that
matters. Can you clarify?

> 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.

As opposed to YAML, yes, which will cause problems when dumping it.
Consider what would happen if the data would be loaded by a language
that compares the content by default... Anything based on Prolog and/or
LISP for example.
 
>  # 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!

Well, technically, the author of the Test class has a bug. If he's
comparing test objects based on their identity, he should serialize this
identity somehow to make it explicit (!ruby/object:Test { !
ruby/MagicDefaultIdentityUniqueHash Hash: 0x7ff2c9f0 } or whatever).
Objects with the same hash should be serialized as anchors and
references. You may even justify loading the "UniqueHash" tag into
whatever the default unique identity hash would be for calling "new
Test" instead of preserving it exactly.

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

I'd say "yes", and even for practical reasons. First, like I said,
languages that take a more "data oriented" view of the world (say,
Haskell, LISP, Prolog) will cheerfully consider these keys equal, so
loading this data to them will fail. Second, in languages that do this
sort of thing, the typical pattern is to say something like:

   a = new Test
   b = new Test
   mapping[a] = valueForA
   mapping[b] = valueForB
   c = someCondition ? a : b
   v = mapping[c]

That is, the keys are kept _in addition_ to the mapping and are then
used to locate values. However, this idiom does not translate to
dumping/loading the mapping to a file:

   a = new Test
   mapping[a] = valueForA
   yamlText = dumpToYaml(mapping)
   mapping = loadFromYaml(yamlText)
   v = mapping[a] # Fails!

Or, in a different program (or instance):

   mapping = loadFromYaml(yamlText)
   a = ... # How do I find 'a'? Maybe:
   a = mapping.findAKeyForTheValue(valueForA) # Hope there's only one...

So this mapping is *practically* unusable as it is, once it is
de/serialized to YAML. Having the YAML library reject the file is
better, as it forces the author to consider what he is trying to achieve
and do _that_.

> 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. 

Right.

> Another purpose is for allowing a library to represent some 
> equal schalar nodes by an single identical node, as is written 
> in the specification.

Yes.

> > A YAML processor may treat equal scalars as if they were 
> > identical.
> I have not understood the importance of this description, though.

It is useful to declare that scalars don't have "identity" as such, but
"objects" do. That is, "objects" have identity, but scalars don't -
e.g., the number 4 has no "identity", but the "!!point { x: 4 }" does.
This maps to the way 99% of the programs model their data (you can
change the 'x' coordinate of the point and it will remain the "same"
point, but you can't change the number 4 to the number 5, ever).

In practical terms this allows YAML libraries to avoid having to
re-serialize large scalars (e.g., binary data, texts, etc.). Not the
_most_ useful thing in the world, but it does have its place.

> 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?

After composing native objects, YAML has no say at all about anything.
The application may wreak whatever havoc it wants on these structures;
that's its job after all.

> If we take the definition of nodes' equality 
> strictly, we can never construct native objects from YAML nodes. 

I fail to see how that follows. The YAML document is intended to
represent a stand-alone object. If you do "b = YAML.load(YAML.dump(a))"
you do _not_ expect that "b" and "a" would have the same memory address
(that is, have the same identity). You _do_ expected them to have the
same content (that is, be equal).

> 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. 

In order for YAML to work, the representation of the object to YAML must
follow YAML's rules. The representation of "Test" objects as YAML did
_not_ follow these rules. The author of the Test class should have
overriden the default serialization-to-YAML to resolve it. As long as he
hasn't, he has a bug, and this isn't YAML's fault.

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

I am unconvinced...

> My opinion is as following.
[Basically make equality be defined on a per-tag basis, using the native implementation if needed]

This would greatly weaken portability of YAML data between systems.
Basically, each file would be tied to the specific platform and even
specific application. A YAML library on a different platform or using a
different application would have no way of knowing what the semantics
is. Writing "generic" YAML tools (that know nothing about the tags)
would become much more difficult, at times impossible.

We'd rather not go down this road. The use case you demonstrated (using
"Test" instances as keys) is pathological; I would be greatly suspicious
of a system that used such a method, and I definitely wouldn't want to
bend YAML out of shape to handle it.

On the other hand, the following is a very reasonable practice, and much
more common than your (IMO unreasonable) "Test" case:

---
calendar:
{ year: 2009, month: 12, day: 1 }: ...
{ year: 2009, month: 12, day: 2 }: ...
cars:
{ manufacturer: ford, model: gt }: ...
{ manufacturer: jaguar, model: xk }: ...

I definitely would be surprised to learn it is OK to see two different
ford GT entries in this mapping!

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

YAML libraries may rely on the implementation of the native data type to
do the right thing. They also typically provide a way for the author of
the native data type to override the way it is de/serialized from/to
YAML. It isn't the job of the library to ensure the right thing is done
in this case (except for the common standard types provided by the
platform/language). It is the responsibility of the author of the data
type to ensure that the de/serialization to YAML correctly follows YAML
rules.

YAML libraries may also do all the heavy lifting themselves. As you
point out, this isn't as easy as it seems on first sight; but there's
plenty of code/algorithms/libraries out there that can help.

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

Just like it is right now :-)

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

Not at all; clarifying these issues is what this list is for. I hope I
did manage to clarify the issue.

Oren.


------------------------------------------------------------------------------
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