>> Actually, no, this is still O(N²) on `master` as well, still (the regexp >> search causes O(N) calls to `re_match` and *that* one is reduced to >> O(N)). > Ah, thanks for the explanation, I had missed that. On Emacs 31 my > timings grew linearly for the inputs I tried, but I can't rule out > a worse case.
In normal circumstances it's linear, indeed. > - as you said, nobody has hit a real false positive yet, so it only > fixes a problem that doesn't exist in practice so far. Also, IIRC the code is fairly safe in that false positives are harmless because we detect them "reliably" by checking for the presence of the corresponding file, so they simply emit a warning message. > If you think it's worth it now, or once a real case shows up, I'm > happy to send it as a patch. If not, no problem. I think I'll keep the current simplistic search for now. Maybe the only real fix we need is to make sure we don't let a false positive hide a real positive (which we could do by going back to (1+ (match-beginning 0)) before the next iteration of the search). === Stefan
