Jacob Kjome wrote:
At 05:22 PM 1/22/2007, you wrote:
>
>It's not a solvable problem. How do you resolve this:
>
><element a="${element.b}" b="${element.a}"/>
>
I would argue that's not a relevant problem. First of all, no one would
write that because it is meaningless. Secondly, it might go like this...
1. parse 'a'
2. can't resolve 'a' value. Defer it for later processing to see if
it's resolvable after other attributes are processed
3. parse 'b'
4. 'a' is available, but I've recorded that it's an unresolved value,
so defer until 'a' is resolved
5. all attributes have been processed, so let's go back and try to
resolve unresolved values
6. attempt 'a' value property resolution: 'b' exists, but 'b' refers
back to 'a'. Detected circular reference. Resolve 'a' as literal
unresolved value of 'b' and vice-versa.
Now lets try something realistic...
<element a="${element.b} bar" b="foo"/>
1. parse 'a'
2. can't resolve 'a' value. Defer it for later processing to see if
it's resolvable after other attributes are processed
3. parse 'b'
4. all attributes have been processed, so let's go back and try to
resolve unresolved values
5. attempt 'a' value property resolution: 'b' exists so resolve
property. Final value "foo bar"
While the code might be a little difficult/complex, I don't think it is
properly characterized as "not a solvable problem".
Oh, I agree, it's not unsolvable, is just hard work.
There's two algorithms for resolving such things
Iteration
=====
-walk the graph (and it is now a graph, not a tree)
-if all references are resolved, exit w/ success
-if something can be resolved, resolve it and update that node, marking
the graph as changed
-complete doing so until the graph is finished
-if you do walk of the graph and make no changes, yet the graph is
unresolved, you have an unresolvable graph. fail with an error.
this can be quite inefficient as you have to walk the graph [an O(n)
operation] for every iteration. In the worst case, you'd only resolve
one thing per iteration, so its an O(n*u) process; where n:=number of
elements in the tree, u:=number of unresolved. Best case: O(n)
-everything resolves in one run. It can take a lot of iterations to
decide that something doesnt resolve.
directed
=====
-pick an unresolved node
-push its xpath on the stack
-locate its references (i.e. walk the tree to them)
-recursively resolve them.
The cost of this is one is trickier to guess. its an O(n) walk of the
graph to find unresolved nodes, followed by O(u) resolutions.
test cases would include chaining
<a a1="${b.a2}" />
<b a2="${c.a2}" />
<c a2="${a.a1}" />
and double expansion. This one is probably trickiest, You have to deal
with things like
<a a1="${b.a2}:${c.a2}" />
<b a2="${c.a2}" />
<c a2="success" />
where the result is al.a1=> success:success
And reject stuff like
<a a1="${b.a2}:${c.a2}" />
<b a2="${c.a2}" />
<c a2="${b.a2}" />
Its not clear this algorithm is cheaper; you end up walking the graph a
lot either way. Where it is efficient is if you dont want to resolve the
entire tree, but only a subset of it, and the rest is just abstract
stuff you dont need to instantiate. The other algorithm is still kind of
handy to have around to verify that you are resolving everything, and
that the results are the same.
You need a big number of test cases to resolve all this stuff, esp. if
you allow more complex references (like .. and other bits of xpath) or
lazy references whose resolution can be deferred until runtime, at which
point the graph and its xmlns nodes have moved around a fair bit. We
ended up writing our own test runner that would take input and output
elements and check the output matched the input, as this was the only
way to do the large number of tests required:
Here, for example, is one to check that qnames are expanded in the
original xmlns context:
http://deployment.cvs.sourceforge.net/deployment/deployment/test/org/ggf/cddlm/files/cdl/valid/set_02_references/cddlm-cdl-2005-02-0016.xml?view=markup
I then had to hack junit so that it would run these files from a
manifest, working with the three different java implementations that
were done
http://deployment.cvs.sourceforge.net/deployment/deployment/src/java/org/ggf/cddlm/cdl/test/
Then there was the XSL transforms to take the test cases and produce
HTML docs that can be submitted as part of the compliance results for
the standard.
So no, not impossible. Just not, something I feel that XmlProperty needs.
-steve
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
