55# URL: <https://www.nltk.org/>
66# For license information, see LICENSE.TXT
77
8+ from nltk import redos
89from nltk .corpus .reader .api import *
910from nltk .corpus .reader .xmldocs import XMLCorpusReader
1011from nltk .pathsec import open as pathsec_open
1112
12- PARA = re .compile (r"<p(?: [^>]*){0,1}>(.*?)</p>" )
13- SENT = re .compile (r"<s(?: [^>]*){0,1}>(.*?)</s>" )
13+ # These ``.*?`` patterns are applied with ``findall`` to (untrusted) corpus
14+ # blocks. On a malformed block -- e.g. many ``<p>`` with no ``</p>`` -- findall
15+ # tries each opening tag as a start and the lazy body scans to the end of the
16+ # block, which is O(k*n) = quadratic (CWE-407; part of GHSA-8mpw). Neither the
17+ # stdlib nor the ``regex`` optimiser linearises findall's multi-start scan, so
18+ # compile them through ``redos`` for a wall-clock backstop that bounds the CPU a
19+ # crafted block can burn instead of letting it grow without limit.
20+ PARA = redos .compile (r"<p(?: [^>]*){0,1}>(.*?)</p>" )
21+ SENT = redos .compile (r"<s(?: [^>]*){0,1}>(.*?)</s>" )
1422
15- TAGGEDWORD = re .compile (r"<([wc](?: [^>]*){0,1}>)(.*?)</[wc]>" )
16- WORD = re .compile (r"<[wc](?: [^>]*){0,1}>(.*?)</[wc]>" )
23+ TAGGEDWORD = redos .compile (r"<([wc](?: [^>]*){0,1}>)(.*?)</[wc]>" )
24+ WORD = redos .compile (r"<[wc](?: [^>]*){0,1}>(.*?)</[wc]>" )
1725
18- TYPE = re .compile (r'type="(.*?)"' )
19- ANA = re .compile (r'ana="(.*?)"' )
26+ TYPE = redos .compile (r'type="(.*?)"' )
27+ ANA = redos .compile (r'ana="(.*?)"' )
2028
21- TEXTID = re .compile (r'text id="(.*?)"' )
29+ TEXTID = redos .compile (r'text id="(.*?)"' )
2230
2331
2432class TEICorpusView (StreamBackedCorpusView ):
@@ -45,23 +53,47 @@ def __init__(
4553 def read_block (self , stream ):
4654 block = stream .readlines (self ._pagesize )
4755 block = concat (block )
48- while (block .count ("<text id" ) > block .count ("</text>" )) or block .count (
49- "<text id"
50- ) == 0 :
56+ # Track the '<text id' / '</text>' counts incrementally. Re-running
57+ # ``block.count(...)`` over the whole growing block on every appended
58+ # line is O(n^2) -- a file with no closing '</text>' makes the loop
59+ # swallow the whole file quadratically (CWE-407). Each marker contains
60+ # no newline and ``readline()`` splits on newlines, so a marker can
61+ # never straddle a line boundary and per-line counts are exact.
62+ open_count = block .count ("<text id" )
63+ close_count = block .count ("</text>" )
64+ while (open_count > close_count ) or (open_count == 0 ):
5165 tmp = stream .readline ()
5266 if len (tmp ) <= 0 :
5367 break
5468 block += tmp
69+ open_count += tmp .count ("<text id" )
70+ close_count += tmp .count ("</text>" )
5571
5672 block = block .replace ("\n " , "" )
5773
58- textids = TEXTID .findall (block )
5974 if self ._textids :
60- for tid in textids :
61- if tid not in self ._textids :
62- beg = block .find (tid ) - 1
63- end = block [beg :].find ("</text>" ) + len ("</text>" )
64- block = block [:beg ] + block [beg + end :]
75+ # Keep only the <text> elements whose id is requested, in a single
76+ # forward pass. ``str.find`` with a monotonically advancing cursor is
77+ # O(n) total; the original per-id ``block.find(tid)`` + string rebuild
78+ # was O(k*n) quadratic on many unwanted elements (CWE-407, part of
79+ # GHSA-8mpw).
80+ kept = []
81+ pos = 0
82+ while True :
83+ beg = block .find ("<text id" , pos )
84+ if beg < 0 :
85+ kept .append (block [pos :])
86+ break
87+ q1 = block .find ('"' , beg )
88+ q2 = block .find ('"' , q1 + 1 ) if q1 >= 0 else - 1
89+ tid = block [q1 + 1 : q2 ] if 0 <= q1 < q2 else ""
90+ close = block .find ("</text>" , beg )
91+ end = len (block ) if close < 0 else close + len ("</text>" )
92+ kept .append (block [pos :beg ])
93+ if tid in self ._textids :
94+ kept .append (block [beg :end ])
95+ pos = end
96+ block = "" .join (kept )
6597
6698 output = []
6799 for para_str in PARA .findall (block ):
0 commit comments