Infinite loop when walking recursively through DOM nodes

7

I have div with contenteditable=true in my document and want to highlight certain parts of the text as the user types (add spans). For this I first need to extract the text typed by the user in the form of a simple string, without tags, and preserving line breaks. This way <p>aa</p><p>bb</p> would generate "aa\nbb" and <div>aaa</div><div><br></div> would generate "aaa\n" . For this I created a function that is called in oninput of div and should return an array with each line of text ( ["aa", "bb"] and ["aaa", ""] for the examples above).

Initially I did just focusing on chrome. It creates the contents of the div as the user types producing internal divs for each row. In some cases divs can be generated one inside the other. Ex: (indentation has been added for readability)

<div contenteditable=true>
  primeira linha
  <div>segunda linha</div>
  <div><br></div>
  <div>
    quarta linha
    <div>quinta linha</div>
  </div>
</div>

I made the following code to get the resulting array:

function extractLines(elem) {
    var nodes = elem.childNodes;
    var lines = [];
    for (i = 0; i < nodes.length; ++i) {
        var node = nodes[i];
        if (node.nodeName == "#text") {
            lines.push(node.nodeValue);
        }
        else if (node.nodeName == "BR") {
            lines.push("");
        }
        else { // DIV ou P
            lines.push.apply(lines, extractLines(node));
        }
    }
    return lines;
}

The idea is quite simple:

  • For each subnode of the div:

  • If it is a text node, it is a line. Include in array.
  • If it is a <br> , it is a blank line. Include "" in array.
  • If it is a <div> or <p> , run this algorithm recursively and insert the result at the end of the array.

But that same code generates an endless loop in some of my tests, I do not understand why.

  • <div>aa<div><br></div></div> = > ["aa", ""]
  • <div>aa<div><br></div><div><br></div></div> = > infinite loop

Why does this infinite loop happen? Is there something wrong with my code? How to implement this same algorithm without this problem?

    
asked by anonymous 10.01.2014 / 14:38

2 answers

6

I spent a good few minutes debugging the code on a fiddle, until I realized a very, very subtle nuance.

The control variable of your for loop is declared as a global variable without var , so it is getting dirty with every recursion.

Change the code as follows:

...
for (var i = 0; i < nodes.length; ++i) {
...
    
10.01.2014 / 15:17
7

You forgot to declare the variable i using var , which made it become a global variable. The recursive call overrides its value, so when it returns it it iterates over already existing elements (by entering recursion again and returning again).

Add var and the function will be correct:

for (var i = 0; i < nodes.length; ++i) {
    
10.01.2014 / 15:18