use Perl

<foo>
  <foo>
    <foo/>
  </foo>
</foo>

Such a structure is validated with a schema like:

<schema>
  <element name="foo" type="foo_type"/>
  <complexType name="foo_type">
    <sequence>
      <element name="foo" type="foo_type" minOccurs="0"/>
    </sequence>
  </complexType>
</schema>

I already have named global complexTypes working, so the only problem now is that the complexType definition refers to itself. Thus, it can no longer be respresented as a finite tree.

I sulked for a while, thinking about how much I'd miss Tree::DAG_Node if I had to give it up. I even wrote to Sean Burke to ask him if he thought Tree::DAG_Node would break if I added a circular reference! (Sorry Sean, if you're out there.)

That's when it hit me - sure the schema specifies infinite recursion, but no instance document will actually be infinite. Therefore if I can just put off the work till I actually see a 'foo' element inside a 'foo' element I can still use a tree! All I have to do is dynamically grow the schema tree in response to events coming from the document stream. So I added a couple lines of code and the tests all passed. And it was good.

If I wasn't consciously focusing on just passing the next test I doubt I would ever have found this solution. Instead I would have invented a hulking recursive engine to handle complexTypes. I bet it would have taken me at least a day to complete. Plus, I'm pretty sure this solution will be faster in the average case of shallow recursion.

Coming soon to this space, the release of XML::Validator::Schema 1.0!

-sam