So I'm working on XML::Validator::Schema and I decide my next test will be to validate a recursive document like:
Such a structure is validated with a schema like:
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
