Recursive node traversal locks browser

[Ryan Stewart]

Putting the following code in a page seems to make it go into an infinite
loop unless you give it a very simple node to work with. Either that or it's
very very slow. I'm somewhat new to this, having limited experience with
hacking out JavaScript but no serious coding with it. I do have programming
experience though. The logic seems fine to me. Is there something I'm
missing?

<script type="text/javascript">
var out = "";

function listNodes(node) {
out += node + "\n";
for (i = 0; i < node.childNodes.length; i++) {
listNodes(node.childNodes[i]);
}
}

listNodes(document.getElementById("listMe"));
alert(out);
</script>

[RobG]

Ryan Stewart wrote:

experience though. The logic seems fine to me. Is there something I'm
missing?

<script type="text/javascript">
var out = "";
Does out need to be global? If not, put it inside the
function and keep it local
function listNodes(node) {
out += node + "\n";
This concatenates the value of "node" on the end of "out"
and appends a new line. If node is a HTML element, IE will
report it as [ojbect], other browsers may include more
information.
for (i = 0; i < node.childNodes.length; i++) {
listNodes(node.childNodes[i]);
Here you call the function "listNodes" but do not
define it (I think you tried but forgot the keyword
"function ",
listNodes(document.getElementById("listMe"));
alert(out);

You mean: function listNodes()...
It would help if you included a minimal implementation of
"node". The code below should do what you want.

There is no need for a function "listNodes"
since you are remembering them all in the variable "out".
You can call the alert directly from the onclick - this
makes the function more generic, all it will do is return
the list so you can do what you want with it (in this case,
display it).

<script type="text/javascript">
function listNodes(aNode) {
var out = '';
if(aNode.childNodes) {
for (var i = 0; i < aNode.childNodes.length; ++i) {
out += '\nNode ' + i + ': '
+ aNode.childNodes[i].nodeName;
}
}
return(out);
}
</script>

<table border="1" id="listMe">
<tr>
<td><form name="aForm" action="">
<input type="button" value="Table kids" onclick="
alert(listNodes(document.getElementById('listMe')) );
"><br>
<input type="button" value="Form kids" onclick="
alert(listNodes(this.form));
">
<p>a cell</p></td><td>a cell</td><td>a cell</td>
</tr><tr>
<td>a cell</td><td>a cell</td><td>a cell</td>
</tr><tr>
<td>a cell</td><td>a cell</td><td>a cell</td>
</tr>
</table>

[RobG]

RobG wrote:

[snip]

<table border="1" id="listMe">
<tr>
<td><form name="aForm" action="">
<input type="button" value="Table kids" onclick="
alert(listNodes(document.getElementById('listMe')) );
"><br>
<input type="button" value="Form kids" onclick="
alert(listNodes(this.form));
">
<p>a cell</p></td><td>a cell</td><td>a cell</td>
</tr><tr>
<td>a cell</td><td>a cell</td><td>a cell</td>
</tr><tr>
<td>a cell</td><td>a cell</td><td>a cell</td>
</tr>
</table>

Dang!! Forgot to close the <form>... Replace the table with
the following:

<table border="1" id="listMe">
<tr>
<td><form name="aForm" action="">
<input type="button" value="Table kids" onclick="
alert(listNodes(document.getElementById('listMe')) );
"><br>
<input type="button" value="Form kids" onclick="
alert(listNodes(this.form));
">
<p>a cell</p>
</form>
</td><td>a cell</td><td>a cell</td>
</tr><tr>
<td>a cell</td><td>a cell</td><td>a cell</td>
</tr><tr>
<td>a cell</td><td>a cell</td><td>a cell</td>
</tr>
</table>

Cheers, Rob.

[Ryan Stewart]

"RobG" <rg***@iinet.net.auau> wrote in message
news:Vd*****************@news.optus.net.au...

Ryan Stewart wrote:

experience though. The logic seems fine to me. Is there something I'm
missing?

<script type="text/javascript">
var out = "";
Does out need to be global? If not, put it inside the
function and keep it local

I'm fairly certain it needs to be global, though again I'm not intimately
familiar with the way JS handles variables. Besides which, keeping it global
simplifies things greatly.

function listNodes(node) {
out += node + "\n";

This concatenates the value of "node" on the end of "out"
and appends a new line. If node is a HTML element, IE will
report it as [ojbect], other browsers may include more
information.

I'm aware of this. FireFox includes more information in the form of what
type of object it is.

for (i = 0; i < node.childNodes.length; i++) {
listNodes(node.childNodes[i]);

Here you call the function "listNodes" but do not
define it (I think you tried but forgot the keyword
"function ",

Yes I do. It's the function that includes this code.

listNodes(document.getElementById("listMe"));
alert(out);

You mean: function listNodes()...

No, I mean a recursive function call.
It would help if you included a minimal implementation of
"node". The code below should do what you want.
A minimal implementation of node? Not following you. And the code doesn't do
what I need. Take another look at my code as I've described it. It's
intended to take any node and traverse all children to the bottom (or top,
depending on your perspective) of the tree. In your implementation, calling
the function for the table only gives one thing: tbody. I need it to list
tbody, the three tr's inside it, and each of the td's inside of them. This
isn't actually about listing the nodes. It's about traversing the tree to
find nodes with particular characteristics, like a particular class
attribute. I see being able to list all of them as the first step toward
this goal.
There is no need for a function "listNodes"
since you are remembering them all in the variable "out".
You can call the alert directly from the onclick - this
makes the function more generic, all it will do is return
the list so you can do what you want with it (in this case,
display it).

*snip code*

[Agent Smith]

>

function listNodes(node) {
out += node + "\n";
for (i = 0; i < node.childNodes.length; i++) {
listNodes(node.childNodes[i]);
}
}

Hey I think the problem is that you are not declaring a new variable i for
each recursive trip. There for as soon as you pass in a node with a child
node i is constantly reset to 0. Your for loop should look like this:

function listNodes(node) {
out += node + "\n";
for ( var i = 0; i < node.childNodes.length; i++) {
listNodes(node.childNodes[i]);
}
}

Now everytime the method is called a new instance of the variable i is
created and it's state is maintained. Another way of putting it is the
variable i in your existing for loop is a global variable, so its value is
common to all recursive calls.

-Smith

[RobG]

Ryan Stewart wrote:

[snip]

I'm fairly certain it needs to be global, though again I'm not intimately
familiar with the way JS handles variables. Besides which, keeping it global
simplifies things greatly.
Up to you :-)

[snip] I'm aware of this. FireFox includes more information in the form of what
type of object it is. Yes, but it lulls you into a false sense of security.
nodeName will return the proper HTML name of the node.

[snip]

Here you call the function "listNodes" but do not
define it (I think you tried but forgot the keyword
"function ",

[snip] Yes I do. It's the function that includes this code. [snip]

Quite right, sorry, a bit brain dead today. You are
recursively calling the function, which can be deadly if
you have no way of escaping.

[snip] No, I mean a recursive function call. [snip]
Yeah, I missed it but it's better to avoid recursion if you
can for the above reason - it can be very hard to debug
when your browser keeps locking up in enless loops because
of bugs in code.
A minimal implementation of node? Not following you. [snip]

A minimal bit of HTML and what you expect your function to
return. Your "function listNodes(node)" expects to be
given an argument to be put into the variable "node", but
you don't tell us what you are putting in there - I just
guessed that you are putting in a reference to a node (e.g.
this.form).
And the code doesn't do
what I need. Take another look at my code as I've described it. It's
intended to take any node and traverse all children to the bottom (or top, [snip]

Ah, but that that's not what childNodes gives you -
childNodes returns the direct children of the current node
(your "node"), not their children. That is, the firstChild
plus its siblings. Otherwise, body.childNodes would return
every single node in the document - it doesn't. In the
example I gave, body has a script and a table child
(Firefox adds in some extra text nodes too but IE doesn't)
and that's it. Firefox says 5 kids (there's an extra text
node after body, script and table), IE says 2 (script &
table).

If you'd given some code and what you wanted....
depending on your perspective) of the tree. In your implementation, calling
the function for the table only gives one thing: tbody. [snip]

because that is the only child of TABLE. The children of
TBODY are the TRs. The Children of the TRs are the TDs,
etc.
I need it to list tbody, the three tr's inside it, and each of the td's inside of them. This
isn't actually about listing the nodes. It's about traversing the tree to
find nodes with particular characteristics, like a particular class
attribute. I see being able to list all of them as the first step toward
this goal.

[snip]

There is no single function (AFAIK) that lists every single
node below the current one.

I have a script to do it, the algorithm is to find the
first child, then keep going down first kids till you hit
the end of the branch. Now go to nextSibling and try going
down further. Each time you hit the end, you look for more
siblings and children. When you can't go any deeper, you
start coming back up, all the time trying to traverse more
siblings and decend deeper into the tree. Eventually you
end up at the point you started (or the top of the document
if you miss your start...).

Code follows ... it was an early script, so not very good
but shows how to do it. Put the script into a .js file,
then call it from wherever.

*Check for wrapping*. I have tried to make sure it's OK
but may have missed some.

/* DOM Walk
* Author: RobG
* Date: September, 2004
* Description: Reports on nodes
* Call:
displayReport(<window_name>,reportDOM(<doc_referen ce>));">
* e.g. displayReport('A
Report',reportDOM(document.getElementById('aDiv')) ;
*/

// adds 1 to last number of index
// e.g. 1,1,2 becomes 1,1,3
function indexAdd(indexVal) {
var a = indexVal.split(',');
var c = '';
for (var i=0; i<a.length; ++i) {
var b = parseInt(a[i]);
if ( i == (a.length - 1)) {++b}
if ( c == '') {c = String(b);
} else {c += ',' + String(b);
} }
return c;
}

// indexTrim
// trims last value from index
// e.g. 1,0,1 becomes 1,0
function indexTrim(indexVal) {
var x = indexVal.split(',');
var z = x[0];
for (var i=1; i<x.length - 1; ++i){
z += ',' + x[i];
} return z;
}

// Navigates a DOM
// Walks down firstChild until the end, then
// retreats to the first nextSibling up the
// tree until it gets back to the start and
// there are not more nextSiblings
function reportDOM(startPoint) {
var idx = '0';
var keepGoing = 'yes';
var msg = '';

if (arguments.length == 0) startPoint = window.document;
if (startPoint) {
var thePoint = startPoint;
var count = 0;
msg = printDetail(count,idx,thePoint,msg);
} else {
alert('startPoint not valid');
keepGoing = 'no';
}

// Keep doing this till I say stop...
while (keepGoing == 'yes') {
// if there are kids
if (thePoint.firstChild) {
thePoint = thePoint.firstChild;
idx += ',' + 0;
++count;
msg = printDetail(count,idx,thePoint,msg);

// Not gone into kid loop, if sibs, do instead
} else if (thePoint.nextSibling) {
thePoint = thePoint.nextSibling;
idx = indexAdd(idx);
++count;
msg = printDetail(count,idx,thePoint,msg);

} else {

// If no kids or sibs, retreat up the tree until find
// a nextSibling. If get to the top without findng one,
// or if keepGoing has been set to no, we've finished
while (!thePoint.nextSibling && keepGoing == 'yes') {
thePoint = thePoint.parentNode;
idx = indexTrim(idx);

// If going up put us back to the top, that's it.
if (idx == '0') keepGoing = 'no';
}

// Have to test here as 'while' not evaluated yet - if
// thePoint.nextSibling undefined ('cos we're at top)
// script will crash
if (keepGoing == 'yes') {
thePoint = thePoint.nextSibling;
idx = indexAdd(idx);
++count;
msg = printDetail(count,idx,thePoint,msg);
} } }
return msg;
}

// printDetail
// Writes details of the point passed to it
// as HTML. Expects output to be put in a table
function printDetail(c,x,p,m){
m += '<tr><td class=\"count\">' + c + '</td>'
+ '<td class=\"idx\">' + x + '</td>'
+ '<td><span class=\"kind\">' + p.nodeName
if (p.type) {m += ' ' + p.type}
m += '</span></td>'
+ '<td><span class=\"name\">';
if (p.name) {m += p.name;}
if (p.id && p.name) {m += '/' + p.id;}
if (p.id && !p.name) {m += p.id;}
// else {m += '&nbsp;'}
m += '</span></td>'
+ '<td align=\"center\"><span class=\"type\">' +
p.nodeType + '</span></td>'
+ '<td align=\"center\"><span class=\"kids\">' +
p.childNodes.length + '</span></td></tr>';
return m;
}

// displayReport
// Opens a new window and writes the data to it
// thingName is a name of the thing being reported on
// content is the stuff to write
function displayReport(thingName,content) {
repWindow =
window.open('','result','width=550,height=700,menu bar=0'
+ ',toolbar=1'
+ ',status=0'
+ ',scrollbars=1'
+ ',resizable=1');
// Styles are here, but could use external sheet
repWindow.document.writeln(
'<html><head><title>Report for: '
+ thingName
+ '</title>'
+ '<style type=\"text/css\">'
+ '.plain, .count, .idx, .kind, .name, .type, .kids, .legend'
+ '{font-weight: normal; font-family: sans-serif; '
+ ' font-size: 12px; color: \#333333;} '
+ 'th'
+ '{border-bottom: 1px solid \#999999;}'
+ 'td'
+ '{border-bottom: 1px solid \#999999;}'
+ '.count'
+ '{padding-right: 15; text-align: right;}'
+ '.idx'
+ '{padding-right: 10;}'
+ '.name'
+ '{padding-left: 5;}'
+ '</style>'
+ '</head><body onLoad=\"self.focus()\">'
+ '<table border=\"0\" cellpadding=\"2\"
cellspacing=\"0\" width=\"100\%\">'
+ '<tr><td style=\"border-bottom: none;\">'
+ '<h2><span class=\"plain\">DOM Walk Report on:</span> '
+ thingName
+ '</h2>'
+ '</td><td style=\"padding: 0 20 0 0; text-align: right;
border-bottom: none;\">'
+ '<a href=\"#NTlegend\">Node Type Legend</a>&nbsp;|&nbsp;'
+ '<a href=\"javascript:window.close();\">Close</a></td>'
+ '</tr></table>'
+ '<table border=\"0\" cellpadding=\"2\" cellspacing=\"0\">'
+ '<tr><th>\#</th>'
+ '<th align=\"left\">Index</th>'
+ '<th align=\"left\">Kind</th>'
+ '<th align=\"left\">Name/id</th>'
+ '<th align=\"center\">Node Type</th>'
+ '<th align=\"center\">\# Kids</th></tr>'
+ content
+ '</table><br>'
+ '<table border=\"0\" cellpadding=\"2\" cellspacing=\"0\">'
+ '<tr><th colspan=\"2" align=\"left\">'
+ '<a name=\"NTlegend\">Node Type Legend</a></th></tr>'
+ '<tr><td class="count">1</td><td
class="legend">ELEMENT_NODE</td></tr>'
+ '<tr><td class="count">2</td><td
class="legend">ATTRIBUTE_NODE</td></tr>'
+ '<tr><td class="count">3</td><td
class="legend">TEXT_NODE</td></tr>'
+ '<tr><td class="count">4</td><td
class="legend">CDATA_SECTION_NODE</td></tr>'
+ '<tr><td class="count">5</td><td
class="legend">ENTITY_REFERENCE_NODE</td></tr>'
+ '<tr><td class="count">6</td><td
class="legend">ENTITY_NODE</td></tr>'
+ '<tr><td class="count">7</td><td
class="legend">PROCESSING_INSTRUCTION_NODE</td></tr>'
+ '<tr><td class="count">8</td><td
class="legend">COMMENT_NODE</td></tr>'
+ '<tr><td class="count">9</td><td
class="legend">DOCUMENT_NODE</td></tr>'
+ '<tr><td class="count">10</td><td
class="legend">DOCUMENT_TYPE_NODE</td></tr>'
+ '<tr><td class="count">11</td><td
class="legend">DOCUMENT_FRAGMENT_NODE</td></tr>'
+ '<tr><td class="count">12</td><td
class="legend">NOTATION_NODE</td></tr>'
+ '</table><br>'
+ '<div style=\"padding: 0 20 0 0; text-align: right;\">'
+ '<a href=\"\"
onclick=\"javascript:window.close();\">Close</a></div>'
+ '</body></html>'
);
repWindow.document.close();
}

[RobG]

Agent Smith wrote:

Hey I think the problem is that you are not declaring a new variable i for
each recursive trip. There for as soon as you pass in a node with a child
node i is constantly reset to 0. Your for loop should look like this:

You are perfectly correct... what was I thinking?

[Richard Cornford]

RobG wrote:
<snip>

Quite right, sorry, a bit brain dead today. You are
recursively calling the function, which can be deadly if
you have no way of escaping.

<snip>

Recursing through the childNodes of a DOM tree should be finite because
all the branches should eventually come to an end. However, invalid
mark-up can result in DOM structures that are not that tree-like, and
may even have child references that point to ancestors, which would
recurse for ever (though you really have to screw the HTML up to achieve
that).

Richard.

[Ryan Stewart]

"Agent Smith" <jo*******@hotmail.com> wrote in message
news:45********************@comcast.com...

for (i = 0; i < node.childNodes.length; i++) {

Hey I think the problem is that you are not declaring a new variable i for
each recursive trip. There for as soon as you pass in a node with a child
node i is constantly reset to 0. Your for loop should look like this:

Perfect. That's exactly what my problem was. Thanks very much. In
retrospect, it makes perfect sense.