ant-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Steve Loughran <ste...@apache.org>
Subject Re: <xmlproperty> intra-element attribute property resolution issue
Date Tue, 23 Jan 2007 11:42:43 GMT
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: user-unsubscribe@ant.apache.org
For additional commands, e-mail: user-help@ant.apache.org


Mime
View raw message