Avoid O(n^2) string concatenation in concatCharacterTokens()

gsnedders · gsnedders · commit 9b1096e9ba4e · 2015-04-15T00:49:27.000+01:00
diff --git a/html5lib/treewalkers/__init__.py b/html5lib/treewalkers/__init__.py
@@ -62,21 +62,18 @@ def getTreeWalker(treeType, implementation=None, **kwargs):
 
 
 def concatenateCharacterTokens(tokens):
-    charactersToken = None
+    pendingCharacters = []
     for token in tokens:
         type = token["type"]
         if type in ("Characters", "SpaceCharacters"):
-            if charactersToken is None:
-                charactersToken = {"type": "Characters", "data": token["data"]}
-            else:
-                charactersToken["data"] += token["data"]
+            pendingCharacters.append(token["data"])
         else:
-            if charactersToken is not None:
-                yield charactersToken
-                charactersToken = None
+            if pendingCharacters:
+                yield {"type": "Characters", "data": "".join(pendingCharacters)}
+                pendingCharacters = []
             yield token
-    if charactersToken is not None:
-        yield charactersToken
+    if pendingCharacters:
+        yield {"type": "Characters", "data": "".join(pendingCharacters)}
 
 
 def pprint(tokens):
