Summary: | TreeWalker with sparse filter works in exponential time | ||
---|---|---|---|
Product: | Xerces-J | Reporter: | Anthony Roy <aroy> |
Component: | DOM | Assignee: | Xerces-J Developers Mailing List <xerces-j-dev> |
Status: | REOPENED --- | ||
Severity: | major | CC: | elena |
Priority: | P1 | ||
Version: | 1.3.1 | ||
Target Milestone: | --- | ||
Hardware: | PC | ||
OS: | All | ||
Attachments: |
Revised test case showing new failure modes and unresolved failures
Patch to resolve problems illustrated by TestWalker.java |
Description
Anthony Roy
2001-04-26 11:10:38 UTC
Fixed in CVS today. Can you pick up latest Xerces and try it out? Created attachment 250 [details]
Revised test case showing new failure modes and unresolved failures
Created attachment 251 [details]
Patch to resolve problems illustrated by TestWalker.java
Unfortunately, Elena's fix created a new problem. Specifically, TreeWalker.firstChild() now returns the nextSibling() of the current node if the current node is a leaf node. I attached a test case (id=250) to illustrate. The test case also takes forever when traversing backwards (eg via previousNode()). The cause of the original problem (and the remaining problem with previousNode()) is that getNextSibling(Node) and getPreviousSibling(Node) can traverse all the way up the tree, even when they are called from getFirstChild(Node) and getLastChild(Node). I've attached a patch (id=251) which solves the problem by allowing getFirstChild(Node) and getLastChild(Node) to specify the parent node above which getNextSibling(Node) and getPreviousSibling(Node) should not traverse. Even with my patch, there is still a problem with running out of stack space when traversing very large documents. I see this if I set NUM_BRANCH = 10000 in the test case. To solve this the class would need to be rewritten to not use recursion. Dean thank you for testing the code and submitting the patch: I did not realize that getFirstChild() is also used in DOM firstChild() method.. I will take a look at your patch. Applied the patch. Might need to revisit in the future. |