2

I am using regular expression to a remove comment tag in html file (Pattern is: "<!--(.|\s)*?--!?>")

But some sites are not using a standard html tag, sample:

<script language="javascript">
    <!-- 
     js code ...
    </script>

In this case, my regular expression will hang, and also try-catch does not catch error. How would I remedy this problem?

2 Answers 2

12

The problem with the performance of your regex is trivial. Don't do this:

(.|\s)*

Whether the quantifier is lazy or greedy is entirely besides the point. The problem is that . and \s are not mutually exclusive. Spaces can be matched by both . and \s. Thus if your regex encounters a space, it will first match the space with ., and if the remainder of the regex fails, it will match it again with \s. If you have two spaces, it will first match both with ., then the first with . and the second with \s, then the frist with \s and the second with ., and then both with \s. As you can see, your regex has a complexity of O(2^N) when it encounters a run of spaces followed by something the remainder of the regex cannot match. If you have 10 spaces, there are 1024 permutations. If you have 32 spaces, there are 4 billion permutations.

The reason you only see the problem when your regex fails is that when the regex succeeds, the . simply matches all the spaces, and \s never gets any of the action.

I know what you're trying to do: you want to match a run of "any" character, including line breaks, which are normally not matched by the dot. The proper solution is to set RegexOptions.SingleLine and use this regex instead:

.*

If you can't set RegexOptions.SingleLine, use this mode modifier to do the same:

(?s).*

If you can't use that mode modifier, e.g. because JavaScript doesn't support it, use a character class with two complementary shorthands:

[\S\s]*

Once you get that horrid (.|\s) alternation out of your regex it will work perfectly. There's no need to use any of the complicated regexes the others suggested. A single lazy quantifier always expands linearly. Alternation that is not mutually exclusive always kills your regex. I indeed call this catastrophic backtracking.

And if you want a regex that allows a tag to terminate a comment, try this:

(?s)<!--.*?(-->|</script>)
3
  • This (?s)<!--.*?(-->|</script>) can cause a timeout with large input texts that have no --> or </script>. Lazy matching is a poor solution for this case. Check out unroll-the-loop technique. However, in specific contexts, any regex will fail. Dec 16, 2015 at 14:42
  • When this regex encounters <!-- it will make a single pass throughout the remainder of the file to search for a --> or </script>. There is no way to do this more efficiently with a single regex if truly anything should be allowed between the <!-- and the --> or </script>. Unrolling the loop applies to certain regexes where the alternation is repeated, which is not the case here. Dec 17, 2015 at 9:37
  • One can't be too sure when it comes to regex: see your regex vs. my regex <!--[^-<]*(?:-(?!->)[^-]*|<(?!\/script>)[^<]*)*(-->|<\/script>). At least 20 times as efficient. Dec 17, 2015 at 10:01
2

You can rewrite the regex so that it fails as quickly as possible when no match is possible, like so:

<!--(?>(?:[^-]+|-(?!->))*)-->

If the unclosed comment in your example is followed by a complete comment further along, this regex will match from the the first <!-- to the first -->, like this:

<!-- blah <!-- blah -->

That's how your browser is supposed to treat SGML comments. In fact, if there's no matching -->, everything after the <!-- is commented out. So the regex should really be:

<!--(?>(?:[^-]+|-(?!->))*)(?:-->|\z)

But I suspect this isn't really what you want. For a better answer, we'll need to know what you want to do about malformed HTML like the snippet you posted.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.